ساختمان داده‌ها و الگوریتم‌ها
Data Structures and Algorithms
| شماره درس: ۴۰۲۵۴ | تعداد واحد: ۳ |
| مقطع: کارشناسی | نوع درس: نظری |
| پیش‌نیاز: ساختمان‌های گسسته | هم‌نیاز: برنامه‌سازی پیشرفته |
اهداف درس
در این درس دانشجو با روش‌های تحلیل الگوریتم‌ها، داده‌ساختارهای ساده و کمی پیشرفته اما مهم و نیز با برخی از الگوریتم‌های مقدماتی آشنا می‌شود. در ارائه‌‌ی مطالب این درس بر تحلیل و اثبات درستی الگوریتم‌ها تاکید می‌شود. دانشجو باید از قبل با یکی از زبان‌های برنامه‌نویسی C++ یا Java و نیز روش‌های بازگشتی در حل مسئله‌ها آشنا باشد. الگوریتم‌های درس مستقل از زبان و مطابق دستورهای کتاب مرجع گفته می‌شود.
ریز مواد
- مقدمات (۱ جلسه)
- سطوح انتزاع
- مراحل مختلف حل مسئله و انتزاع
- داده‌مدل‌ها، داده‌گونه‌ها، داده‌ساختارها، داده‌گونه‌ی انتزاعی، شی
- تحلیل الگوریتم (۳ جلسه)
- تحلیل زمانی الگوریتم: مرتب‌سازی درجی
- رشد توابع
- روش‌های تحلیل سرشکن
- تقسیم و حل (۲ جلسه)
- مرتب‌سازی ادغامی، محاسبه‌ی تعداد نابجایی، زیردنباله‌ی متوالی، ضرب‌اعداد
- قضیه اصلی
- تحلیل الگوریتم‌های تصادفی (۱ جلسه)
- محاسبه‌ی میانه‌ی تقریبی، مسئله‌ی استخدام
- داده‌ساختارهای پایه (۱ جلسه)
- صف و پشته
- لیست پیوندی
- داده‌ساختارهای درخت (۵ جلسه)
- پیاده‌سازی‌های مختلف درخت‌ها، پیمایش درخت‌ها، استقراء ساختاری
- درخت عبارت، تبدیل نگارش‌های مختلف یک عبارت ریاضی
- داده‌ساختار ترای
- درخت دودویی جستجو
- صف اولویت (هرم کمینه و بیشینه)
- مرتب‌سازی (۴ جلسه)
- درخت تصمیم و کران پایین
- مرتب‌سازی هرمی
- مرتب‌سازی سریع (تحلیل تصادفی)
- مرتب‌سازی با تعداد مقایسه‌های بهینه
- مرتب‌سازی خطی: شمارشی، مبنایی، سطلی
- مرتب‌سازی خارجی (اختیاری)
- مرتبه‌ی آماری (۲ جلسه)
- محاسبه‌ی کمینه و بیشینه
- انتخاب k-امین عنصر (الگوریتم تصادفی و قطعی)
- درهم‌سازی (۲ جلسه)
- درهم‌سازی زنجیره‌ای
- درهم‌سازی سراسری
- درهم‌سازی باز
- درهم‌سازی کامل
- داده‌ساختارهای پیشرفته (۳ جلسه)
- مجموعه‌های مجزا
- درخت‌های دودویی متوازن: درخت قرمز-سیاه
- درخت بازه
- گراف‌ها (۳ جلسه)
- روش‌های مختلف پیاده‌سازی گراف
- جست‌وجوهای عمق‌اول و سطح‌اول و کاربردهای آن‌ها
- ترتیب توپولوژیکی، مؤلفه‌های قویاً همبند
- کوتاه‌ترین مسیر در گراف‌ها: الگوریتم‌های دایکسترا و بلمن-فورد
ارزیابی
- پنج بسته تمرین داده خواهد شد (هر بسته شامل تعدادی مسئله نظری و چند مسئله برنامه‌نویسی است)؛ نیازی به تحویل مسئله‌های نظری نیست.
- پنج آزمون کوتاه از مسئله‌های نظری بالا + یک مسئله مشابه (۳ نمره)
- پنج تمرین عملی بالا (۳ نمره)
- آزمون میان‌ترم (۶ نمره)
- آزمون نهایی (۸ نمره)
مراجع
- محمد قدسی، "داده‌ساختارها و مبانی الگوریتم‌ها"، چاپ چهارم، انتشارات فاطمی، ۱۳۹۳.
- محمد قدسی و آیدین نصیری شرق، "۶۰۰ مسئله‌ی چندگزینه‌ای از داده‌ساختارها و الگوریتم‌ها"، چاپ ششم، انتشارات فاطمی، ۱۳۹۷.
- T. Cormen, C. Leiserson, R. Riverst, and C. Stein. Introduction to Algorithms. 3rd Edition, MIT Press, 2011.