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

یادداشت‌های یک معلم علاقه‌مند به نوشتن از آنچه آموخته و یاد می‌دهد
 

  

✤  مباحث کاربردی در مسابقات برنامه‌نویسی

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

کتاب Art of Programming Contest به عنوان یک کتاب اختصاصی آمادگی مسابقات برنامه‌نویسی با بررسی مباحث بسیار مفید در مورد مفاهیم و اصول مورد نیاز برای شرکت موفق در چنین مسابقاتی، به چنین سوالاتی پاسخ داده است. این کتاب با بحث در مورد شیوه‌های برنامه‌نویسی مطلوب با زبان برنامه‌نویسی C و استفاده موثر از مفاهیم مختلف طراحی الگوریتم‌ها و ساختمان داده‌ها، نه تنها برای شرکت‌کنندگان مسابقات که برای هر علاقه‌مند به حل مسائل چالش‌برانگیز الگوریتمی مناسب و مفید است.

در قسمتی از کتاب نویسنده به مباحثی اشاره می‌کند که آشنایی و تسلط بر آنها برای کسب موفقیت در مسابقات برنامه‌نویسی بسیار کارآمد است. در ادامه قسمتی از این مباحث شرح داده شده است. بیشتر این مباحث در کتاب به صورت مبسوط بررسی شده‌اند.

  

اعداد اول، پیمانه‌ها و سایر مفاهیم نظریه اعداد

  [برگرد بالا]

مباحث مربوط به نظریه اعداد از جمله مباحث ظریف در طراحی سوالات مسابقات برنامه‌نویسی هستند. تعاریف و قضایای بسیاری در نظریه اعداد وجود دارند که بسیاری از محاسبات حجیم را ساده کرده و از صرف هزینه در محاسبات جلوگیری می‌کنند.

  

فاکتوریل، مفاهیم شمارش و اصول ترکیبیات

  [برگرد بالا]

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

  

دنباله‌های اعداد

  [برگرد بالا]

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

  

مسئله طولانی‌ترین زیردنباله مشترک (LCS)

  [برگرد بالا]

در این مسئله هدف یافتن طولانی‌ترین زیردنباله مشترک بین دو دنباله است. در این زیردنباله متوالی بودن عناصر اهمیتی نداشته و تنها ترتیب آنها مهم است. به عنوان مثال، برای دو دنباله ABCDEFGH و EDAGBCFH زیردنباله ABCFH طولانی‌ترین زیردنباله مشترک است. برای حل این مسئله راه‌های مختلفی وجود دارد که استفاده از روش برنامه‌نویسی پویا یکی از آنها است.

  

مسئله طولانی‌ترین زیردنباله مرتب

  [برگرد بالا]

در این مسئله هدف یافتن طولانی‌ترین زیردنباله از یک دنباله است که عناصر آن به صورت صعودی (LIS) یا نزولی (LDS) مرتب باشند. برای حل این مسئله نیز می‌توان از روش برنامه‌نویسی پویا استفاده کرد.

  

مسئله فاصله ویرایش یا حجم ویرایش (Edit Distance)

  [برگرد بالا]

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

  

مسئله کوله‌پشتی صفر و یک

  [برگرد بالا]

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

  

مسئله خرد کردن پول

  [برگرد بالا]

در این مسئله هدف تولید مبلغ مشخصی پول با حداقل استفاده از سکه‌ها و اسکناس‌های موجود است. در مورد این مسئله نیز راهکارهایی با استفاده از روش‌های حریصانه و برنامه‌نویسی پویا ارائه شده است که روش اول لزوما به جواب بهینه ختم نمی‌شود.

  

مسئله ضرب زنجیره‌ای ماتریس‌ها

  [برگرد بالا]

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

  

مسئله حداکثر مجموع

  [برگرد بالا]

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

  

گراف‌، پیمایش‌ها و عملیات جستجو‌

  [برگرد بالا]

گراف‌ها و انواع آن از جمله ابزارهای بسیار پرکاربرد در حل مسائل برنامه‌نویسی هستند. در این میان روش‌های پیمایش و جستجوی گراف قسمت مهمی را به خود اختصاص می‌دهند. در یک گراف - که ممکن است وزن‌دار و جهت‌دار نیز باشد - روش‌های پیمایش و جستجوی مختلفی وجود دارد که قسمت عمده‌ای از آنها در مباحث طراحی الگوریتم و هوش مصنوعی مورد بررسی قرار می‌گیرند. چنین عملیاتی کاربرد بسیار وسیعی در حل مسائل الگوریتمی و یافتن جواب مطلوب از میان جواب‌های مختلف دارد. جستجوهای ناآگاهانه‌ای مانند جستجوی اول عمق (DFS)، جستجوی اول عمق عمیق‌شونده تکراری (DF-ID)، جستجوی اول سطح (BFS)، جستجو با هزینه یکنواخت (UCS)، جستجوی عمق محدود (DLS) و جستجوهای آگاهانه‌ای مانند جستجوی اولین بهترین حریصانه (Greedy Best First) و جستجوی *A از جمله روش‌های جستجوی مشهور در این حوزه هستند.

  

مسئله کوتاهترین مسیر در گراف

  [برگرد بالا]

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

  

مسئله درخت پوشای کمینه (MST)

  [برگرد بالا]

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

  

توجه: آنچه که مطرح شد تمام مباحث مورد نیاز جهت آمادگی برای چنین مسابقاتی نیست. اگرچه در ظاهر بعضی از این مسائل کاربرد چندانی نداشته یا قابل توسعه نیستند؛ اما درک مفهوم و روش حل آنها دید وسیعتری را برای حل مسائل الگوریتمی فراهم می‌کند.

مسعود اقدسی فام

مسعود اقدسی فام هستم.

دانش‌آموخته علوم کامپیوتر و فعال حوزه‌های برنامه‌نویسی پایتون، علم داده و یادگیری ماشین

algs.ir/sp51si5     اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram
نوشته‌ها از این دست
       ✦   مسئله Jolly Jumpers
       ✦   معمای هشت وزیر
       ✦   مسئله‌ The Trip
آخرین نوشته‌ها
نوشته‌های پرمخاطب
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

پست الکترونیک (محرمانه):

متن پیام: *  

01 02 06 07 08 09 10 11 12 13 14

• azadeh
۷ دی ۱۳۸۵، ساعت ۰۹:۳۵

salam

yek barname dar morede tarahi algoritm mikhastam

moteshakeram

• آرزوی گل
۸ دی ۱۳۸۵، ساعت ۰۱:۳۸

سلام

آقا یه خبببببببببببببببببببببببببر خوش !!!!

ما هم به جمع کامپیوتریست ها پیوستیم...یعنی هی دبیر مبانی مون اصرار کرد ما گفتیم نه!

هی گفت هی ما گفتیم نه!!!!! خلاصه با اصرار و التماس زیاد ما رو برای المپیاد کامپیوتر نوشتند.....

• رضا
۳۱ اردیبهشت ۱۳۸۶، ساعت ۱۹:۴۷

سلام وخسته نباشید

جا داره  بابت ساخت و راه اندازی این سایت مفید بهتون تبریک بگم.

من دوست دارم تو مسابقات برنامه نویسی شرکت کنم ولی نمیدونم مسابقات برنامه نویسی به چه صورت هست، از چه زبانی استفاده میشه. و دیگر مسائل...

اگه ممکنه منو راهنمایی کنید. ممنون میشم

این هم پست الکترونیکی من ::::>>>

re.bavali@gmail.com

sedaye_eshgh321@yahoo.com

آرزومند بهترین آرزوها برای شما     (رضا / 18  /  خوزستان /  برنامه نویس(دلفی))

خدا نگهدار

• RP
۲۲ خرداد ۱۳۸۶، ساعت ۲۱:۴۶

سلام. من یه برنامه میخوام که برام پشتک وارو بزنه. فوری....

ممنون.

-----------------------------------------------------------------------------

چه خبره؟ مگه اینجا........................................................

مسعود اقدسی فام
۲۳ خرداد ۱۳۸۶، ساعت ۱۰:۰۱

RP عزیز برنامه تون حاضره.

والا منم نمی دونم اینجا چه خبره!!!

• zendegi
۲ شهریور ۱۳۸۶، ساعت ۲۱:۳۶

سلام

راهنمايي مي خواستم در مورد تبديلات اوليه مثل انتقال انعكاس دوران بر روي

اشكال در گرافيك كامپيوتري

با تشكر

• vahid saneei
۱۶ آبان ۱۳۸۶، ساعت ۲۲:۴۶

سلام,خسته نباشید.

این کتابی که معرفی کردید رو چطور میتونم پیدا کنم.(Art of Programming )

متشکر.

• zahra
۶ آذر ۱۳۸۶، ساعت ۲۰:۰۵

salam jenabe aghay aghdasi fam age lotf konid man ye barnamey webi be zaban c# da mored saite ye darokhone mikhastam niaz fori va foti daram baray poroject term akharam lotfan mano rahnamaii konid.mamnoon misham az lotfetoon

• aja
۱۷ بهمن ۱۳۸۶، ساعت ۱۴:۴۱

salam

file ketab amadegi baraye ACM az jash bardashte shode,lotfan dobare bezarid

tashakor

• ثنا
۳۱ تیر ۱۳۸۷، ساعت ۱۱:۵۳

salam,man daneshjoye computeram,kheili be barname nevisi alaghe daram v dost daram dar ayandei nazdik ye barnamenevise herfei sham,vali rahesho nemidonam darzemn barnamenvisim badak nist mishe lotfan rahnamaim konid

مسعود اقدسی فام
۱ مرداد ۱۳۸۷، ساعت ۱۲:۵۵

دوست دارید با چه زبانی کار کنید ثنا خانم؟

• vahid
۷ دی ۱۳۸۷، ساعت ۰۰:۱۹

Hi please send "Art of Programming Contest" Ebook for me.tanks a lot

• مصطفی
۲۴ خرداد ۱۳۹۱، ساعت ۰۹:۵۱

ممنون بابت راهنمایی های خوبتون

• امیر بختیاری
۳۰ مرداد ۱۳۹۱، ساعت ۰۲:۰۹

خیلی ممنون بابت مطالب خوبتون

06

• عرفان
۹ آبان ۱۳۹۱، ساعت ۱۱:۰۰

سلام میخواستم در صورت امکان سوالات این مسابقات با پاسخ صحیح یا حدوی اونهارو داشته باشم .

مطالب بالاهم خیلی مفید بود . ممنون از فعالیتتون ...

۹ آبان ۱۳۹۱، ساعت ۱۱:۳۸
• مسعود اقدسی فام

ممنون از لطفتون.

سوالات رو از طریق گوگل یا سایت رسمی مسابقات (بازم گوگل!) پیدا کنید. یه جای خاص متمرکز نیستن. برای یه تعداد جواب هست و برای یه تعداد نیست. مسابقات جهانی معمولا جوابشون پیدا می‌شه.

• ناصر باقری
۱۵ آبان ۱۳۹۱، ساعت ۱۸:۳۳

تشکر 0606

• مهمان
۱ آذر ۱۳۹۱، ساعت ۲۱:۰۴

سلام

میشه پیاده سازی مسئله خرد کردن پول رو به روش برنامه نویسی پویا هم آموزش بدید

ممنون

• hadi0x7c7
۱۲ فروردین ۱۳۹۲، ساعت ۰۰:۳۹

کتاب Competetive Programming  هم کتاب  خوبی هستش ! اگر گیرتون بیاد.

همچنین TopCoder

• farhad
۱۵ مرداد ۱۳۹۲، ساعت ۰۴:۴۰

سلام خوش حال شدم بلاگی مثل بلاگ شما را دیدم که بلاگ جدید من مانند آن است ،  خوشحال می شوم  تبادل لینک کنیم

open-mind.ir

• aragorn
۲۵ بهمن ۱۳۹۴، ساعت ۲۰:۰۴

مثل همیشه عالييييييي

• پارسالیپ
۱۹ مهر ۱۳۹۹، ساعت ۰۲:۳۵

ممنون بابت مطالب مفیدتون