طراحی الگوریتم‌ها
| مدرس: دکتر محمدعلی آبام | پیش‌نیاز: داده‌ساختارها و الگوریتم‌ها |
| ترم: | محل برگزاری: کلاس مجازی |
| زمان ارائه: پنج‌شنبه ۸:۳۰ تا ۱۱:۳۰ | مشاهده: دریافت لایسنس |
معرفی درس
طراحی الگوریتم؛ از ایده‌های بنیادی تا الگوریتم‌های کارا و پیشرفته
طراحی الگوریتم یکی از مباحث بنیادی علوم کامپیوتر است که به بررسی روش‌های ساخت الگوریتم‌های کارا برای حل مسائل محاسباتی می‌پردازد. در بسیاری از مسائل، یافتن یک راه‌حل کافی نیست؛ الگوریتم باید از نظر زمان اجرا و منابع مصرفی نیز کارا باشد و درستی آن به‌صورت دقیق قابل اثبات باشد. این درس با تمرکز بر این جنبه‌ها، روش‌های متداول طراحی الگوریتم و ابزارهای تحلیل آن‌ها را بررسی می‌کند.
در این درس، با رویکردهای مهمی مانند الگوریتم‌های مبتنی بر استقرا، تقسیم و حل، روش‌های حریصانه، برنامه‌ریزی پویا و جست‌وجوی فضای حالت آشنا می‌شوید. این روش‌ها با استفاده از مسائل نمونه‌ای مانند مسئله نزدیک‌ترین زوج نقاط، کدگذاری هافمن و مسئله کوله‌پشتی بررسی می‌شوند. همچنین، با تحلیل کارایی الگوریتم‌ها، نمادهای مجانبی و شیوه‌های اثبات درستی آن‌ها آشنا خواهید شد تا بتوانید راه‌حل‌های محاسباتی را با دیدی دقیق‌تر ارزیابی کنید.
بخش مهم دیگری از درس به داده‌ساختارهای پیشرفته و الگوریتم‌های گراف اختصاص دارد. در این بخش، ساختارهایی مانند درخت‌های AVL و قرمز-سیاه، مجموعه‌های مجزا و درخت‌های ترای، در کنار الگوریتم‌های مسیر کوتاه، درخت فراگیر کمینه و مؤلفه‌های قویاً همبند بررسی می‌شوند. در ادامه، شبکه‌های شار و کاربردهای آن‌ها، از جمله تطابق در گراف‌های دوبخشی، و نیز برنامه‌ریزی خطی و الگوریتم سیمپلکس معرفی خواهند شد. این مجموعه مباحث، ابزارهای نظری و الگوریتمی متنوعی برای حل مسائل پیچیده‌تر در اختیار شما قرار می‌دهد.
در پایان این درس چه توانایی‌هایی کسب می‌کنید؟
- شناخت روش‌های متداول طراحی الگوریتم و انتخاب رویکرد مناسب برای حل مسائل محاسباتی
- تحلیل کارایی الگوریتم‌ها و درک نمادهای مجانبی، از جمله \(o\) و \(\omega\)
- طراحی الگوریتم با استفاده از استقرا، تقسیم و حل، روش‌های حریصانه، برنامه‌ریزی پویا و جست‌وجوی فضای حالت
- آشنایی با روش‌های پس‌گرد (Backtracking) و انشعاب و حد (Branch and Bound)
- درک تحلیل سرشکن و کاربرد داده‌ساختارهای پیشرفته، از جمله درخت‌های متوازن، مجموعه‌های مجزا و درخت ترای
- طراحی و تحلیل الگوریتم‌های گراف برای مرتب‌سازی توپولوژیکی، یافتن مؤلفه‌های قویاً همبند، محاسبه مسیرهای کوتاه و یافتن درخت فراگیر کمینه
- آشنایی با الگوریتم‌های بلمن–فورد، فلوید–وارشال، جانسون، کروسکال و پریم و شناخت کاربردهای آن‌ها
- درک مسئله شار بیشینه و برش کمینه و آشنایی با کاربردهای شبکه‌های شار در مسائلی مانند تطابق در گراف‌های دوبخشی و یافتن مسیرهای مجزا
- آشنایی با مدل‌سازی مسائل به کمک برنامه‌ریزی خطی و استفاده از الگوریتم سیمپلکس برای حل آن‌ها
- تقویت توانایی تحلیل دقیق مسائل، اثبات درستی الگوریتم‌ها و ارزیابی راه‌حل‌ها از نظر کارایی
این درس برای دانشجویان علوم کامپیوتر و مهندسی کامپیوتر، به‌ویژه علاقه‌مندان به الگوریتم‌ها، حل مسئله و مبانی نظری محاسبات، مناسب است. مباحث آن همچنین برای کسانی که قصد دارند دانش خود را در زمینه طراحی الگوریتم‌های پیشرفته و داده‌ساختارهای کارا گسترش دهند، مفید خواهد بود.
پیش‌نیاز
آشنایی مناسب با ساختمان داده‌ها، الگوریتم‌های پایه و تحلیل پیچیدگی زمانی برای بهره‌گیری بهتر از این درس ضروری است. همچنین، تسلط بر مبانی ریاضیات گسسته، استقرا و استدلال ریاضی به درک اثبات درستی الگوریتم‌ها و تحلیل آن‌ها کمک می‌کند.
سرفصل‌ها
- مقدمات و مسائل نمونه (۱ جلسه)
- مسئله‌ی ۳-مجموع، معرفی نمادهای o و ω
- الگوریتم‌های مبتنی بر استقرا (۱ جلسه)
- ارزیابی چندجمله‌ای‌ها، نگاشت یک‌به‌یک، ستاره‌ی مشهور
- تقسیم و حل (۱ جلسه)
- نزدیک‌ترین زوج نقاط
- الگوریتم‌های حریصانه (۱ جلسه)
- کدگذاری هافمن
- برنامه‌ریزی پویا (۱ جلسه)
- خرد کردن پول، کوله‌پشتی، محاسبه‌ی مجموعه‌ی مستقل روی درخت
- جست‌وجوی فضای حالت (۱ جلسه)
- روش پس‌گرد، انشعاب و حد
- داده‌ساختارهای پیشرفته (۳ جلسه)
- تحلیل سرشکن
- د.د.ج. متوازن: درخت قرمز-سیاه، درخت AVL
- مجموعه‌های مجزا
- درخت ترای
- الگوریتم‌های گراف (۳ جلسه)
- ترتیب توپولوژیکی، مؤلفه‌های قویاً همبند
- کوتاه‌ترین مسیر در گراف‌ها: الگوریتم‌های بلمن-فورد
- کوتاه‌ترین مسیر بین تمام رأس‌ها: الگوریتم‌های فلوید-وارشال و جانسون
- درخت فراگیر کمینه: الگوریتم‌های کروسکال و پریم
- شبکه‌های شار (۲ جلسه)
- شار بیشینه و برش کمینه: الگوریتم فورد-فالکرسن
- گونه‌ها و کاربردها: تطابق در گراف دوبخشی، مسیرهای مجزا، گرد کردن ماتریس
- برنامه‌ریزی خطی (۲ جلسه)
- فرم استاندارد، مدل‌سازی مسائل با برنامه‌ریزی خطی
- الگوریتم سیمپلکس برای حل برنامه‌ریزی خطی
ارزیابی
- تمرین‌های عملی: ۳ نمره
- آزمونک‌ها: ۳ نمره
- آزمون پایان‌دوره: ۱۴ نمره
منابع
- T. Cormen, C. Leiserson, R. Riverst, and C. Stein. Introduction to Algorithms. 4th Edition, MIT Press, 2022.
- J. Kleinberg and E. Tardos. Algorithm Design. Addison Wesley, 2005.
- U. Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989.
- G. Brassard, P. Bratley. Algorithmics: Theory and Practice. Prentice-Hall, 1988.