داده‌ساختارها و الگوریتم‌ها

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

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

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

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