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

Data Structures and Algorithms

شماره درس: ۴۰۲۵۴ تعداد واحد: ۳
مقطع: کارشناسی نوع درس: نظری
پیش‌نیاز: ساختمان‌های گسسته هم‌نیاز: برنامه‌سازی پیشرفته

اهداف درس

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

ریز مواد

  • مقدمات (۱ جلسه)
    • سطوح انتزاع
    • مراحل مختلف حل مسئله و انتزاع
    • داده‌مدل‌ها، داده‌گونه‌ها، داده‌ساختارها، داده‌گونه‌ی انتزاعی، شی‌
  • تحلیل الگوریتم (۳ جلسه)
    • تحلیل زمانی الگوریتم: مرتب‌سازی درجی
    • رشد توابع
    • روش‌های تحلیل سرشکن
  • تقسیم و حل (۲ جلسه)
    • مرتب‌سازی ادغامی، محاسبه‌ی تعداد نابجایی، زیردنباله‌ی متوالی، ضرب‌اعداد
    • قضیه اصلی
  • تحلیل الگوریتم‌های تصادفی (۱ جلسه)
    • محاسبه‌ی میانه‌ی تقریبی، مسئله‌ی استخدام
  • داده‌ساختارهای پایه (۱ جلسه)
    • صف و پشته
    • لیست پیوندی
  • داده‌ساختارهای درخت (۵ جلسه)
    • پیاده‌سازی‌های مختلف درخت‌ها، پیمایش درخت‌ها، استقراء ساختاری
    • درخت عبارت، تبدیل نگارش‌های مختلف یک عبارت ریاضی
    • داده‌ساختار ترای
    • درخت دودویی جستجو
    • صف اولویت (هرم کمینه و بیشینه)
  • مرتب‌سازی (۴ جلسه)
    • درخت تصمیم و کران پایین
    • مرتب‌سازی هرمی
    • مرتب‌سازی سریع (تحلیل تصادفی)
    • مرتب‌سازی با تعداد مقایسه‌های بهینه
    • مرتب‌سازی خطی: شمارشی، مبنایی، سطلی
    • مرتب‌سازی خارجی (اختیاری)
  • مرتبه‌ی آماری (۲ جلسه)
    • محاسبه‌ی کمینه و بیشینه
    • انتخاب k-امین عنصر (الگوریتم تصادفی و قطعی)
  • درهم‌سازی (۲ جلسه)
    • درهم‌سازی زنجیره‌ای
    • درهم‌سازی سراسری
    • درهم‌سازی باز
    • درهم‌سازی کامل
  • داده‌ساختارهای پیشرفته (۳ جلسه)
    • مجموعه‌های مجزا
    • درخت‌های دودویی متوازن: درخت قرمز-سیاه
    • درخت بازه
  • گراف‌ها (۳ جلسه)
    • روش‌های مختلف پیاده‌سازی گراف
    • جست‌وجوهای عمق‌اول و سطح‌اول و کاربردهای آن‌ها
    • ترتیب توپولوژیکی، مؤلفه‌های قویاً همبند
    • کوتاه‌ترین مسیر در گراف‌ها: الگوریتم‌های دایکسترا و بلمن-فورد

ارزیابی

  • پنج بسته تمرین داده خواهد شد (هر بسته شامل تعدادی مسئله نظری و چند مسئله برنامه‌نویسی است)؛ نیازی به تحویل مسئله‌های نظری نیست.
  • پنج آزمون کوتاه از مسئله‌های نظری بالا + یک مسئله مشابه (۳ نمره)
  • پنج تمرین عملی بالا (۳ نمره)
  • آزمون‌ میان‌ترم (۶ نمره)
  • آزمون نهایی (۸ نمره)

مراجع

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