داده‌ساختارها و الگوریتم‌ها
Data Structures and Algorithms
| مقطع: کارشناسی | گرایش: نرم‌افزار |
| نوع درس: نظری | تعداد واحد: ۳ |
| پیش‌نیاز: ریاضیات گسسته | هم‌نیاز: برنامه‌سازی پیشرفته |
هدف کلی
در این درس دانشجویان با روش‌های تحلیل الگوریتم‌ها، داده‌ساختارهای پایه‌ای و نیز برخی الگوریتم‌های مقدماتی آشنا می‌شوند. در ارائه‌ی مطالب این درس بر تحلیل و اثبات درستی الگوریتم‌ها تاکید می‌شود. دانشجو باید از قبل با یکی از زبان‌های برنامه‌نویسی و نیز روش‌های بازگشتی در حل مسئله‌ها آشنا باشد. الگوریتم‌های درس مستقل از زبان ارائه می‌شود.
سرفصل‌ها
- مقدمات (۱ جلسه)
- سطوح انتزاع
- مراحل مختلف حل مسئله و انتزاع
- داده‌مدل‌ها، داده‌گونه‌ها، داده‌ساختارها، داده‌گونه‌ی انتزاعی، شی‌ء
- تحلیل الگوریتم (۳ جلسه)
- تحلیل زمانی الگوریتم: مرتب‌سازی درجی
- رشد توابع
- روش‌های تحلیل سرشکن
- تقسیم و حل (۲ جلسه)
- مرتب‌سازی ادغامی، محاسبه‌ی تعداد نابجایی، زیردنباله‌ی متوالی، ضرب اعداد
- قضیه اصلی
- تحلیل الگوریتم‌های تصادفی (۱ جلسه)
- محاسبه‌ی میانه‌ی تقریبی، مسئله‌ی استخدام
- داده‌ساختارهای پایه (۱ جلسه)
- صف و پشته
- لیست پیوندی
- داده‌ساختارهای درخت (۵ جلسه)
- پیاده‌سازی‌های مختلف درخت‌ها، پیمایش درخت‌ها، استقرای ساختاری
- درخت عبارت، تبدیل نگارش‌های مختلف یک عبارت ریاضی
- داده‌ساختار ترای
- درخت دودویی جستجو
- صف اولویت (هرم کمینه و بیشینه)
- مرتب‌سازی (۴ جلسه)
- درخت تصمیم و کران پایین
- مرتب‌سازی هرمی
- مرتب‌سازی سریع (تحلیل تصادفی)
- مرتب‌سازی با تعداد مقایسه‌های بهینه
- مرتب‌سازی خطی: شمارشی، مبنایی، سطلی
- مرتب‌سازی خارجی (اختیاری)
- مرتبه‌ی آماری (۲ جلسه)
- محاسبه‌ی کمینه و بیشینه
- انتخاب k-امین عنصر (الگوریتم تصادفی و قطعی)
- درهم‌سازی (۲ جلسه)
- درهم‌سازی زنجیره‌ای
- درهم‌سازی سراسری
- درهم‌سازی باز
- درهم‌سازی کامل
- داده‌ساختارهای پیشرفته (۳ جلسه)
- مجموعه‌های مجزا
- درخت‌های دودویی متوازن: درخت قرمز-سیاه
- درخت بازه
- گراف‌ها (۳ جلسه)
- روش‌های مختلف پیاده‌سازی گراف
- جست‌وجوهای عمق‌اول و سطح‌اول و کاربردهای آن‌ها
- ترتیب توپولوژیکی، مؤلفه‌های قویاً همبند
- کوتاه‌ترین مسیر در گراف‌ها: الگوریتم‌های دایکسترا و بلمن-فورد
ارزیابی پیشنهادی
- پنج تمرین عملی (۳ نمره)
- پنج تمرین نظری (۳ تحویل)
- آزمون میان‌ترم (۶ نمره)
- آزمون پایانی (۸ نمره)
منابع پیشنهادی
- T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. 4th Edition, MIT Press, 2022.
- D. Knuth. The Art of Computer Programming: Sorting and Searching. Volume 3, 2nd Edition, Pearson Education, 1998.