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

»    مسابقه‌ی برنامه‌نویسی آنلاین 20 Quera

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

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

بستن پنجره
وبگاه
این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter
اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
بستن پنجره
وبگاه     این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
مباحث کاربردی در مسابقات برنامه‌نویسی - الگوریتمستان
الگوریتمستان
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

» مصطفی

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