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

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

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

الگوریتم

»

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

ادامه ...

بسیاری از فرآیندهای طبیعی از جمله ترکیب ساختار بدن موجودات زنده نظم مشخصی دارند و از دنباله‌ی اعدادی تبعیت می‌کنند که امروزه با نام دنباله‌ی اعداد فیبوناچی (فیبوناتچی - Fibonacci) شناخته می‌شود. مشهورترین خاصیت این اعداد نسبت دو جمله‌ی متوالی آنها به ازای جملات بزرگ دنباله است که به عدد طلایی مشهور است.

این دنباله از جمله دنباله‌های عددی است که در طراحی سوالات مسابقات برنامه‌نویسی نیز استفاده می‌شود و گاهی در حل سوالات کاربرد دارد. از این رو آشنایی با روش‌های مختلف تولید جملات آن حائز اهمیت است.

تعریف: دنباله‌ی اعداد فیبوناچی روی اعداد حسابی به صورت زیر تعریف می‌شود:

ادامه ...

الگوریتم جستجوی اول عمق (Depth First Search - DFS) الگوریتمی مشابه الگوریتم جستجوی اول سطح (BFS) برای پیمایش گراف است. این دو الگوریتم خواص و کاربردهای مشترک بسیاری دارند و تفاوت اصلی در این است که در هر تکرار الگوریتم DFS تنها یکی از گره‌های مجاور گره پردازش شده برای مرحله‌ی بعد انتخاب می‌شود. به این ترتیب، الگوریتم DFS به جای صف از یک پشته برای مشخص کردن مسیر پیمایش استفاده می‌کند.

ادامه ...

الگوریتم فلوید-وارشال (Floyd-Warshall) یک الگوریتم مبتنی بر روش برنامه‌نویسی پویا برای محاسبه‌ی کوتاهترین مسیر بین هر دو جفت گره گراف‌های وزن‌دار است. دو الگوریتم رایج دایکسترا و بلمن-فورد روش‌های محاسبه‌ی کوتاهترین مسیر از مبدأ ثابت هستند که در صورت تکرار آنها به ازای هر گره عملکردی همانند الگوریتم فلوید-وارشال دارند. اما این الگوریتم ویژگی‌هایی دارد که آن را برجسته می‌کند:

ادامه ...

الگوریتم پیمایش اول سطح یا جستجوی اول سطح (Breadth First Search - BFS) از جمله الگوریتم‌های مشهور پیمایش و جستجوی گراف است که در حل مسائل الگوریتمی و هوش مصنوعی کاربرد دارد. این الگوریتم برای پیمایش و جستجوی گراف از یک صف برای نگهداری ترتیب جستجو استفاده می‌کند.

الگوریتم BFS با وارد کردن گره مبدأ به صف پردازش شروع شده و تا خالی نشدن این صف مراحل زیر را تکرار می‌شود:

1- عنصر جلوی صف را به عنوان گره جاری انتخاب و از صف حذف کن.

2- گره جاری را پردازش کن.

ادامه ...

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

ادامه ...

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

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

ادامه ...

مرتب‌سازی هرمی (Heap Sort) یکی از روش‌های مشهور مرتب‌سازی داده‌ها است که بر اساس خصوصیات درخت heap (هیپ، هرم یا کپه)  و عملکرد آن پیاده‌سازی شده است.

بر اساس تعریف درخت heap، در یک max-heap (یا min-heap) بزرگترین (یا کوچکترین) مقدار بین داده‌ها همواره در ریشه‌ی درخت قرار دارد. یافتن بزرگترین (یا کوچکترین) عنصر بین عناصر، هزینه‌ی ثابت ( Ө( 1 دارد. با حذف این عنصر از درخت، بزرگترین (یا کوچکترین) عنصر بعدی مجددا در ریشه قرار می‌گیرد. به این ترتیب با حذف متوالی عناصر درخت heap و درج آنها در محل جدید، یک آرایه‌ی مرتب‌شده‌ی نزولی (یا صعودی) به دست خواهد آمد.

ادامه ...

روش مرتب‌سازی ادغامی (Merge Sort) یک روش مرتب‌سازی مبتنی بر مقایسه‌ی عناصر با استفاده از روش تقسیم و غلبه است. این روش از مراحل بازگشتی زیر تشکیل یافته است:

1- آرایه را به دو زیرآرایه با اندازه‌ی تقریبا یکسان تقسیم کن.

2- دو زیرآرایه را به روش مرتب‌سازی ادغامی مرتب کن.

3- دو زیرآرایه‌ی مرتب‌شده را ادغام کن.

ادامه ...

روش مرتب‌سازی سریع (Quick Sort) یکی از الگوریتم‌های مشهور مرتب‌سازی داده‌ها است. این الگوریتم طی مراحل بازگشتی زیر یک روش تقسیم و غلبه برای مرتب کردن داده‌ها ارائه می‌نماید:

1- انتخاب عنصر محوری: یکی از عناصر آرایه به عنوان عنصر محوری (pivot) - به عنوان مثال عنصر اول - انتخاب می‌شود.

2- تقسیم آرایه: چینش عناصر آرایه به قسمی تغییر داده می‌شود که تمامی عناصر کوچکتر یا مساوی محور در سمت چپ آن و تمامی عناصر بزرگتر در سمت راست آن قرار بگیرند. این دو قسمت زیر آرایه‌های چپ و راست نامیده می‌شوند.

ادامه ...

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

   

 

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