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

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

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

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

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