الگوریتمستان

برنامه‌نویسی، طراحی الگوریتم و حل مسئله‌های الگوریتمی

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
نوشته‌ها با برچسب الگوریتم‌های حریصانه نوشته‌ها با برچسب الگوریتم‌های حریصانه - الگوریتمستان الگوریتمستان الگوریتمستان
نوشته‌ها با برچسب «

الگوریتم‌های حریصانه

»

مسئله

پل اردوش (اردیش - Paul Erdős) ریاضیدان مشهور و برجسته‌ی قرن بیستم است که تا پایان عمر خود تلاش گسترده‌ای برای انتشار مقالات علمی داشت و همکاری با وی در انتشار مقاله یک افتخار بزرگ برای هر ریاضیدان محسوب می‌گردد.

با توجه به آنکه همکاری با ایشان برای هر کس ممکن نبود، تلاش می‌کردند با نفراتی در انتشار مقاله‌ی علمی همکاری کنند که با این دانشمند بزرگ مقاله داشتند. این رویکرد باعث پدید آمدن عدد اردوش (Erdős number) یا فاصله‌ی همکاری اردوش شد؛ یعنی برای نویسندگانی که به صورت مستقیم با ایشان همکاری داشتند عدد 1 و برای کسانی که با این نفرات مقاله داشتند عدد 2 نسبت داده شد و ارتباطات دورتر نیز به همین ترتیب با اعداد طبیعی بعدی مشخص شدند.

ادامه ...

الگوریتم دایکسترا (دیکسترا، دایجسترا - Dijkstra) یک راهکار حریصانه برای یافتن کوتاهترین مسیر از مقصد ثابت (تک منبع) به سایر گره‌های گراف وزن‌دار است. این گراف می‌تواند معرف مسیرهای یک شهر و تقاطع‌های آن باشد که انبار شرکت در یک گره آن قرار داشته و هدف یافتن کوتاهترین مسیر به هر محل دیگر از این انبار است. طبیعتا این الگوریتم در یافتن کوتاهترین مسیر بین دو گره مشخص نیز کاربرد دارد. تنها شرط لازم برای استفاده از این الگوریتم نامنفی بودن وزن یال‌های گراف است.

ادامه ...

روش حریصانه (Greedy) یکی از روش‌های مشهور و پرکاربرد طراحی الگوریتم‌ها است که با ساختاری ساده در حل بسیاری از مسائل استفاده می‌شود. این روش اغلب در حل مسائل بهینه‌سازی استفاده شده و در پاره‌ای مواقع جایگزین مناسبی برای روش‌هایی مانند برنامه‌ریزی پویا است. در حالت کلی این روش سرعت و مرتبه‌ی اجرایی بهتری نسبت به روش‌های مشابه خود دارد؛ اما متناسب با مسئله ممکن است به یک جواب بهینه‌ی سراسری ختم نشود.

در روش حریصانه رسیدن به هدف در هر گام مستقل از گام قبلی و بعدی است. یعنی در هر مرحله برای رسیدن به هدف نهایی، مستقل از این که در مراحل قبلی چه انتخاب‌هایی صورت گرفته و انتخاب فعلی ممکن است چه انتخاب‌هایی در پی داشته باشد، انتخابی که در ظاهر بهترین انتخاب ممکن است صورت می‌پذیرد. به همین دلیل است که به این روش، روش حریصانه گفته می‌شود. زمانی که یک دزد عجول و حریص وارد خانه‌ای می‌شود، در مسیر حرکت خود هر وسیله و کالای با ارزشی را داخل کیسه می‌اندازد. وی در این حالت چندان توجهی نمی‌کند که چه اشیائی را قبلا برداشته و ممکن است در آینده چه اشیاء گرانبهاتری به دست آورد. او در هر گام تنها از بین اشیاء دم دست خود با ارزش‌ترین آن را انتخاب کرده و به وسایل قبلی اضافه می‌کند.

ادامه ...

مسئله‌ی ضرب زنجیره‌ای ماتریس‌ها و پرانتزبندی بهینه‌ی آن یکی از مثال‌های مشهور کاربرد برنامه‌نویسی پویا در حل مسائل بهینه‌سازی است.

فرض کنید قصد داریم حاصلضرب عبارت ماتریسی $ A_{3 \times 7} \times B_{7 \times 8 } \times C_{8 \times 4} $ را محاسبه کنیم. می‌دانیم که ضرب ماتریس‌ها خاصیت شرکت‌پذیری داشته، اما خاصیت جابجایی ندارد. بنابراین رعایت ترتیب ضرب آنها مهم است. پرانتزبندی‌های مختلف ضرب ماتریس‌ها حالت‌های مختلف محاسبه آن را به ما می‌دهند:

  

\[1: A \times (B \times C) \]

ادامه ...

الگوریتمستان در تلگرام

   

 

پیوند کوتاه:
»  دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد
ویدئوهای آموزشی دوره‌ی Algorithms: Design and Analysis دانشگاه استنفورد با زیرنویس انگلیسی
برچسب‌ها
#حل سوالات Timus Online Judge #مسأله‌های الگوریتمی #محاسبات ریاضی #آموزش الگوریتم #معرفی وب‌سایت #الگوریتم‌های عقبگرد #نمونه سوال فارسی مسابقه‌ی ACM #گراف #حل مسئله‌‌ی الگوریتمی #حل سوالات مسابقات برنامه‌نویسی #سوالات مسابقات برنامه‌نویسی بیان #الگوریتم فلوید-وارشال #حل سوالات UVa Online Judge #الگوریتم‌های تقسیم و غلبه #کتاب الکترونیکی #الگوریتم‌های برنامه‌نویسی پویا #الگوریتم‌های حریصانه #کتاب الگوریتم #الگوریتم #الگوریتم دایکسترا #جستجوی اول سطح #مسئله‌های برنامه‌نویسی #وبلاگ #تمرین طراحی الگوریتم #کتاب مسابقات برنامه‌نویسی #ساختمان داده #مسئله‌های الگوریتمی #الگوریتم‌های مسیریابی #ترجمه فارسی سوالات کتاب Programming Challenges #مسابقه برنامه نویسی #تمرین مسابقه برنامه‌نویسی #سوالات چالشی برنامه‌نویسی #مسابقات برنامه‌نویسی #الگوریتم‌های گراف #ترجمه‌ی فارسی سوالات برنامه‌نویسی #نکات برنامه‌نویسی #ویدئوی آموزشی #ترجمه‌ی فارسی سوالات UVa Online Judge #تمرین مسابقه‌ی برنامه‌نویسی ای‌سی‌ام #سوالات UVa Online Judge #آمادگی المپیاد کامپیوتر #تکنیک‌های طراحی الگوریتم #مسأله‌های برنامه‌نویسی #ترجمه‌ی فارسی سوالات ACM #مسابقه برنامه‌نویسی #آموزش طراحی الگوریتم #آموزش برنامه‌نویسی ++C #سوالات مسابقات ACM-ICPC #الگوریتم‌های مرتب‌سازی #تمرین المپیاد کامپیوتر #ماتریس #آموزش ساختمان داده‌ها #جستجوی اول عمق #آمادگی مسابقه ACM #برنامه‌نویسی ++C #پیمایش گراف #Python #نمونه سوالات مسابقه برنامه‌نویسی #برنامه‌نویسی #درخت‌ها #آمادگی مسابقه برنامه‌نویسی #نمونه سوال فارسی مسابقات برنامه‌نویسی #صف #حل سوالات ACM-ICPC #سوالات برنامه‌نویسی #نمونه سوال مسابقه ACM #منبع آموزشی #مسئله‌ی کوله‌پشتی #نمونه سوال فارسی مسابقات ACM #درخت پوشا #الگوریتم‌های بازگشتی #کتابخانه قالب استاندارد ++C #دانلود کتاب #مسابقات برنامه‌نویسی ACM #الگوریتم‌های کوتاهترین مسیر