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

مدرس: محمدعلی آبام گواهی: رسمی دوزبانه
ترم: زمستان ۱۴۰۳ پیش‌نیاز: برنامه‌سازی پایتون، ساختارهای گسسته
زمان ارائه: شنبه و دوشنبه ۱۴:۰۰ تا ۱۵:۳۰ محل برگزاری: کلاس مجازی

هدف کلی

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

سرفصل‌ها

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

ارزیابی

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

منابع

  • محمد قدسی، «داده‌ساختارها و مبانی الگوریتم‌ها»، چاپ دهم، انتشارات فاطمی، ۱۴۰۲.
  • T. Cormen, C. Leiserson, R. Riverst, and C. Stein. Introduction to Algorithms. 4th Edition, MIT Press, 2022.