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

Data Structures and Algorithms

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

اهداف درس

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

ریز مواد

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

ارزیابی

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

مراجع

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

T. Cormen, C. Leiserson, R. Riverst, and C. Stein. Introduction to Algorithms. 3rd Edition, MIT Press, 2011.