دادهساختارها و الگوریتمها
Data Structures and Algorithms
شماره درس: ۲۰۱۴ | تعداد واحد: ۳ |
نوع درس: نظری | پیشنیاز: برنامهسازی پایتون، ساختارهای گسسته |
اهداف درس
در این درس دانشجو با روشهای تحلیل الگوریتمها، دادهساختارهای ساده اما مهم و نیز با برخی از الگوریتمهای مقدماتی آشنا میشود. در ارائهی مطالب این درس بر تحلیل و اثبات درستی الگوریتمها تاکید میشود. دانشجو باید از قبل با یکی از زبانهای برنامهنویسی آشنا باشد. الگوریتمهای درس مستقل از زبان ارائه میشود.
ریز مواد
- تحلیل الگوریتم (۲ جلسه)
- الگوریتمها و تحلیل زمانی آنها: $n$امین عنصر دنباله فیبوناچی و زیرآرابه با بزرگترین جمع
- رشد توابع: نمادهای $O, \Theta, \Omega$
- الگوریتمهای تقسیم و حل (۲ جلسه)
- مرتبسازی ادغامی، ، ضرب اعداد $n$ بیتی
- قضیه اصلی
- الگوریتمهای تصادفی (۱ جلسه)
- الگوریتمهای لاسوگاس و مونتوکارلو: مسئله میانه تقریبی
- جایگشت تصادفی و کاربردهای آن: مسئلهی استخدام
- مرتبهی آماری، مرتبسازی (۳ جلسه)
- انتخاب k-امین عنصر (الگوریتم قطعی)
- مرتبسازی غیرمقایسهای: شمارشی، مبنایی
- مرتبسازی مقایسهای: مرتبسازی سریع (تحلیل تصادفی)
- دادهساختارهای درخت (۲ جلسه)
- پیادهسازیهای مختلف درختها، درختهای دودویی جستجو
- صف اولویت (هرم کمینه و بیشینه)، مرتبسازی هرمی
- درهمسازی (۲ جلسه)
- درهمسازی زنجیرهای، درهمسازی باز، Bloom filter
- انواع توابع درهمساز: توابع k-سراسری و توابع سراسری
- الگوریتمهای حریصانه (۱ جلسه)
- خرد کردن پول، مسائل زمانبندی
- برنامهریزی پویا (۲ جلسه)
- اعداد فیبوناچی، زمانبندی بازههای وزندار
- خرد کردن پول، بزرگترین زیردنبالهی مشترک
- گرافها (۳ جلسه)
- روشهای مختلف پیادهسازی گراف
- جستوجوهای عمقاول و سطحاول و کاربردهای آنها
- کوتاهترین مسیر در گرافها: الگوریتمهای دایکسترا
ارزیابی
- تمرینهای عملی: ۳ نمره
- آزمونکها : ۳ نمره
- آزمون پایاندوره: ۱۴ نمره
مراجع
- محمد قدسی، "دادهساختارها و مبانی الگوریتمها"، چاپ چهارم، انتشارات فاطمی، ۱۳۹۳.
- محمد قدسی و آیدین نصیری شرق، "۶۰۰ مسئلهی چندگزینهای از دادهساختارها و الگوریتمها"، چاپ ششم، انتشارات فاطمی، ۱۳۹۷.
- T. Cormen, C. Leiserson, R. Riverst, and C. Stein. Introduction to Algorithms. 3rd Edition, MIT Press, 2011.