طراحی الگوریتم‌ها

مدرس: دکتر محمدعلی آبام پیش‌نیاز: داده‌ساختارها و الگوریتم‌ها
ترم: محل برگزاری: کلاس مجازی
زمان ارائه: پنج‌شنبه ۸:۳۰ تا ۱۱:۳۰ مشاهده: دریافت لایسنس

معرفی درس

طراحی الگوریتم؛ از ایده‌های بنیادی تا الگوریتم‌های کارا و پیشرفته

طراحی الگوریتم یکی از مباحث بنیادی علوم کامپیوتر است که به بررسی روش‌های ساخت الگوریتم‌های کارا برای حل مسائل محاسباتی می‌پردازد. در بسیاری از مسائل، یافتن یک راه‌حل کافی نیست؛ الگوریتم باید از نظر زمان اجرا و منابع مصرفی نیز کارا باشد و درستی آن به‌صورت دقیق قابل اثبات باشد. این درس با تمرکز بر این جنبه‌ها، روش‌های متداول طراحی الگوریتم و ابزارهای تحلیل آن‌ها را بررسی می‌کند.

در این درس، با رویکردهای مهمی مانند الگوریتم‌های مبتنی بر استقرا، تقسیم و حل، روش‌های حریصانه، برنامه‌ریزی پویا و جست‌وجوی فضای حالت آشنا می‌شوید. این روش‌ها با استفاده از مسائل نمونه‌ای مانند مسئله نزدیک‌ترین زوج نقاط، کدگذاری هافمن و مسئله کوله‌پشتی بررسی می‌شوند. همچنین، با تحلیل کارایی الگوریتم‌ها، نمادهای مجانبی و شیوه‌های اثبات درستی آن‌ها آشنا خواهید شد تا بتوانید راه‌حل‌های محاسباتی را با دیدی دقیق‌تر ارزیابی کنید.

بخش مهم دیگری از درس به داده‌ساختارهای پیشرفته و الگوریتم‌های گراف اختصاص دارد. در این بخش، ساختارهایی مانند درخت‌های AVL و قرمز-سیاه، مجموعه‌های مجزا و درخت‌های ترای، در کنار الگوریتم‌های مسیر کوتاه، درخت فراگیر کمینه و مؤلفه‌های قویاً همبند بررسی می‌شوند. در ادامه، شبکه‌های شار و کاربردهای آن‌ها، از جمله تطابق در گراف‌های دوبخشی، و نیز برنامه‌ریزی خطی و الگوریتم سیمپلکس معرفی خواهند شد. این مجموعه مباحث، ابزارهای نظری و الگوریتمی متنوعی برای حل مسائل پیچیده‌تر در اختیار شما قرار می‌دهد.

در پایان این درس چه توانایی‌هایی کسب می‌کنید؟

این درس برای دانشجویان علوم کامپیوتر و مهندسی کامپیوتر، به‌ویژه علاقه‌مندان به الگوریتم‌ها، حل مسئله و مبانی نظری محاسبات، مناسب است. مباحث آن همچنین برای کسانی که قصد دارند دانش خود را در زمینه طراحی الگوریتم‌های پیشرفته و داده‌ساختارهای کارا گسترش دهند، مفید خواهد بود.

پیش‌نیاز

آشنایی مناسب با ساختمان داده‌ها، الگوریتم‌های پایه و تحلیل پیچیدگی زمانی برای بهره‌گیری بهتر از این درس ضروری است. همچنین، تسلط بر مبانی ریاضیات گسسته، استقرا و استدلال ریاضی به درک اثبات درستی الگوریتم‌ها و تحلیل آن‌ها کمک می‌کند.

سرفصل‌ها

ارزیابی

منابع

  1. T. Cormen, C. Leiserson, R. Riverst, and C. Stein. Introduction to Algorithms. 4th Edition, MIT Press, 2022.
  2. J. Kleinberg and E. Tardos. Algorithm Design. Addison Wesley, 2005.
  3. U. Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989.
  4. G. Brassard, P. Bratley. Algorithmics: Theory and Practice. Prentice-Hall, 1988.