داده‌ساختارها و الگوریتم‌ها؛ از برنامه‌نویسی تا حل مسئله حرفه‌ای

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

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

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

این مهارت‌ها کجا به کار می‌آیند؟

• طراحی راه‌حل‌های کارا برای مسائل پیچیده برنامه‌نویسی
• درک بهتر عملکرد برنامه‌ها و شناسایی راهکارهای ناکارآمد
• آمادگی علمی برای مسابقات برنامه‌نویسی و حل مسائل الگوریتمی
• تقویت پایه نظری و عملی برای مطالعه مباحث پیشرفته‌تر علوم کامپیوتر
• توسعه توانایی تحلیل و حل مسئله، به‌عنوان یکی از مهارت‌های مهم در فعالیت حرفه‌ای نرم‌افزار

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

آشنایی قبلی با دست‌کم یک زبان برنامه‌نویسی ضروری است. الگوریتم‌های این درس مستقل از زبان برنامه‌نویسی ارائه می‌شوند؛ بنابراین، تمرکز اصلی بر روش حل مسئله، طراحی الگوریتم و تحلیل کارایی آن‌هاست.

• تحلیل الگوریتم (۲ جلسه)
  • الگوریتم‌ها و تحلیل زمانی آن‌ها: دنباله فیبوناچی و زیر آرایه با بزرگترین جمع
  • رشد توابع: نمادهای O، Ω و Θ
• الگوریتم‌های تقسیم و حل (۲ جلسه)
  • مرتب‌سازی ادغامی، ، ضرب اعداد $n$ بیتی
  • قضیه اصلی
• الگوریتم‌های تصادفی (۱ جلسه)
  • الگوریتم‌های لاس‌وگاس و مونتوکارلو: مسئله میانه تقریبی
  • جایگشت تصادفی و کاربردهای‌ آن: مسئله‌ی استخدام
• مرتبه‌ی آماری، مرتب‌سازی (۳ جلسه)
  • انتخاب k-امین عنصر (تصادفی و قطعی)
  • مرتب‌سازی مقایسه‌ای: مرتب‌سازی سریع (تحلیل تصادفی)
  • کران پایین الگوریتم‌های مقایسه‌ای، مرتب‌سازی غیرمقایسه‌ای: شمارشی، مبنایی
• داده‌ساختارها (۴ جلسه)
  • لیست، صف و پشته
  • درخت‌های دودویی جستجو
  • صف اولویت (هرم کمینه و بیشینه)، مرتب‌سازی هرمی
  • درهم‌سازی و توابع درهم‌‌ساز
• الگوریتم‌های حریصانه (۱ جلسه)
  • خرد کردن پول، مسائل زمان‌بندی
• برنامه‌ریزی پویا (۱ جلسه)
  • اعداد فیبوناچی، زمان‌بندی بازه‌های وزن‌دار، بزرگ‌ترین زیردنباله‌ی مشترک
• گراف‌ها (۲ جلسه)
  • پیاده‌سازی گراف و پیمایش گراف‌ها
  • کوتاه‌ترین مسیر در گراف‌ها: الگوریتم‌های دایکسترا

• تمرین‌های عملی: ۳ نمره
• تمرین‌های تئوری : ۲ نمره
• کوییز از تمرین‌ها: ۳ نمره
• آزمون پایان‌دوره: ۱۲ نمره

• محمد قدسی، «داده‌ساختارها و مبانی الگوریتم‌ها»، چاپ دهم، انتشارات فاطمی، ۱۴۰۲.