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

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

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

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

• محمد قدسی، "داده‌ساختارها و مبانی الگوریتم‌ها"، چاپ چهارم، انتشارات فاطمی، ۱۳۹۳.
• محمد قدسی و آیدین نصیری شرق، "۶۰۰ مسئله‌ی چندگزینه‌ای از داده‌ساختارها و الگوریتم‌ها"، چاپ ششم، انتشارات فاطمی، ۱۳۹۷.