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

Data Structures and Algorithms

شماره درس: ۴۰۱۴ تعداد واحد: ۳
نوع درس: نظری پیش‌نیاز: برنامه‌سازی پایتون

اهداف درس

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

ریز مواد

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

ارزیابی

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

مراجع

  • محمد قدسی، "داده‌ساختارها و مبانی الگوریتم‌ها"، چاپ چهارم، انتشارات فاطمی، ۱۳۹۳.
  • محمد قدسی و آیدین نصیری شرق، "۶۰۰ مسئله‌ی چندگزینه‌ای از داده‌ساختارها و الگوریتم‌ها"، چاپ ششم، انتشارات فاطمی، ۱۳۹۷.
  • T. Cormen, C. Leiserson, R. Riverst, and C. Stein. Introduction to Algorithms. 3rd Edition, MIT Press, 2011.