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

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.