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

»    مسابقه‌ی برنامه‌نویسی CodeCup 2018

»    دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد

»    مسئله‌ی انتخابات

مباحث کاربردی در مسابقات برنامه‌نویسی - الگوریتمستان
الگوریتمستان
2513.925.00
  »  

       

عناوین بخشی از مباحث پرکاربرد در سوالات مسابقات برنامه‌نویسی

http://www.aachp.ir آنچه می‌خوانید ویراست جدید نوشته‌ای است که اولین بار با عنوان «چه چیزهایی لازم است؟» آذر ماه 1385 از طریق وبگاه برنامه‌نویسی و طراحی الگوریتم (عنوان و طرح پیشین وبگاه الگوریتمستان) منتشر شده بود.


یکی از سوالات رایج علاقه‌مندان شرکت در مسابقات برنامه‌نویسی معتبر همچون 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)

  [بازگشت به فهرست]

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

      

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


این نوشته آخرین بار در تاریخ دوشنبه، ۲۷ اردیبهشت ماه ۱۳۹۵ مورد بازنویسی نگارشی قرار گرفته است.

این نوشته آخرین بار در تاریخ مورد بازنویسی علمی قرار گرفته است.
نوشته‌های مرتبط
        متن فارسی مسئله‌ی Jolly Jumpers از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
        متن فارسی مسئله‌ی Gholam's Simple Game از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2010‌ منطقه‌ای سایت تهران
        مستندات دوره‌ی Introduction to Programming Contests دانشگاه استنفورد با موضوع ریاضیات، ساختمان داده‌ها و الگوریتم‌های مورد نیاز برای شرکت در مسابقات برنامه‌نویسی
        راه حل سوالات مسابقه‌ی جهانی ACM-ICPC 2016
        متن فارسی مسئله‌ی The Trip از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
        متن فارسی مسئله‌ی شماره‌ی 343 از UVa Online Judge، ار سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی
        متن فارسی مسئله‌ی 3n+1 Problem (حدس کولاتز یا حدس 3n+1) از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
        ویدئوهای آموزشی کلاس Programming Challenges شامل مباحث الگوریتم‌ها، ساختمان داده‌ها و ریاضیات محاسباتی برای آمادگی مسابقات برنامه‌نویسی
        متن فارسی مسئله‌ی Encrypted SMS از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2007 منطقه‌ای سایت تهران
        بررسی مسئله‌ی انتخابات، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2016 سایت تهران
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left

 


» aragorn

یکشنبه، ۲۵ بهمن ماه ۱۳۹۴، ساعت ۲۰:۰۴
مثل همیشه عالييييييي

» farhad

سه‌شنبه، ۱۵ مرداد ماه ۱۳۹۲، ساعت ۰۴:۴۰
سلام خوش حال شدم بلاگی مثل بلاگ شما را دیدم که بلاگ جدید من مانند آن است ،  خوشحال می شوم  تبادل لینک کنیم
open-mind.ir

» hadi0x7c7

دوشنبه، ۱۲ فروردین ماه ۱۳۹۲، ساعت ۰۰:۳۹
کتاب Competetive Programming  هم کتاب  خوبی هستش ! اگر گیرتون بیاد.
همچنین TopCoder

» مهمان

چهارشنبه، ۱ آذر ماه ۱۳۹۱، ساعت ۲۱:۰۴
سلام
میشه پیاده سازی مسئله خرد کردن پول رو به روش برنامه نویسی پویا هم آموزش بدید
ممنون

» ناصر باقری

دوشنبه، ۱۵ آبان ماه ۱۳۹۱، ساعت ۱۸:۳۳
تشکر 0606

» عرفان

سه‌شنبه، ۹ آبان ماه ۱۳۹۱، ساعت ۱۱:۰۰
سلام میخواستم در صورت امکان سوالات این مسابقات با پاسخ صحیح یا حدوی اونهارو داشته باشم .
مطالب بالاهم خیلی مفید بود . ممنون از فعالیتتون ...


سه‌شنبه، ۹ آبان ماه ۱۳۹۱، ساعت ۱۱:۳۸
مسعود:
ممنون از لطفتون.
سوالات رو از طریق گوگل یا سایت رسمی مسابقات (بازم گوگل!) پیدا کنید. یه جای خاص متمرکز نیستن. برای یه تعداد جواب هست و برای یه تعداد نیست. مسابقات جهانی معمولا جوابشون پیدا می‌شه.

» امیر بختیاری

دوشنبه، ۳۰ مرداد ماه ۱۳۹۱، ساعت ۰۲:۰۹
خیلی ممنون بابت مطالب خوبتون
06

» مصطفی

چهارشنبه، ۲۴ خرداد ماه ۱۳۹۱، ساعت ۰۹:۵۱
ممنون بابت راهنمایی های خوبتون