وبگاه دروس وبگاه دروس

« بازگشت

طراحی الگوریتم 1

نام درس طراحی الگوریتم 1
کد درس 8101424
تعداد واحد 3
دروس هم نیاز
دروس پیش نیاز

 

نام درس

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

شماره درس (واحد)

8101424   (3واحد)

نیمسال

دوم سال تحصیلی 93-92

گرایش

نرم افزار

پیش نیاز

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

زمان ارائه

یکشنبه ها و سه‌شنبه ها ساعت 10:30 تا 12:00

مکان

کلاس 3 ساختمان شماره 1 دانشکده مهندسی برق و کامپیوتر

 

 

 

نام و نام خانوادگی

مسعود اسدپور

دفتر

اتاق 720 ساختمان 2 دانشکده مهندسی برق و کامپیوتر

شماره تماس

4951

پست الکترونیکی

asadpour@ut.ac.ir

 

 

 

شرح درس

در این درس روش‌های مختلف طراحی و تحلیل الگوریتم‌های سریع و کارا برای حل مسایل مختلف گفته می‌شوند. در ارائه‌ی مطالب بر استفاده از داده‌ساختارهای مناسب و اثبات درستی و تحلیل الگوریتم‌ها تاکید می‌شود.

اهداف درس

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

دانشجویانی که این درس را با موفقیت پشت سر بگذارند قادر خواهند بود

·         یک درک کلی از روشهای حل مسائل الگوریتمی داشته باشند.

·    با مسائل NP-complete اشنا شده و NP-complete بودن یک مساله را ثابت کنند.

·         پیچیدگی زمانی یک الگوریتم را محاسبه کنند.

·    درکی از الگوریتمهای رایج و مهم داشته و راه حلهای مختلف آنها را از نظر پیچیدگی مقایسه کنند و بدانند هر الگوریتم را در کجا استفاده نمایند.

·         از توابع کتابخانه ای موجود برای الگوریتمهای رایج استفاده نمایند.

ریز جلسات درس

1.      تحلیل سرشکن (Amortized Analysis)

2.   روش Brute Force: ضرب ساده، ب م م، تشخیص اعداد اول، لیست اعداد اول، Selection Sort ، تطابق رشته، Convex-Hull، Closest-pair، Exhaustive Search، مسایل کوله پشتی، فروشنده دوره گرد، جایگشتها، ترکیبها (همگی در حد معرفی و ارائه راه حل Brute-Force)

3.   ‎‎ روش تقسیم و حل (Divide & Conquer): درخت دودویی، درخت جستجوی دودویی، ضرب اعداد بزرگ، ضرب ماتریس به روش استراسن، مساله کاشی کاری (فرش کردن)

4.   روش کاهش و حل (Decrease & Conquer): توان، ب م م، Insertion Sort، پیمایش گراف، ترتیب توپولوژیک، تولید جایگشت به روش جانسون- تروتر، تولید زیر مجموعه، ضرب به روش دهقان روسی، مسایل ترتیب، جستجو به روش درونیابی

5.   روش تبدیل و حل (Transform & Conquer): پیش‌مرتب سازی، اعضای تکراری لیست، مد، جستجوی آیتمها، حذف گاوسی، LU decomposition، معکوس ماتریس، محاسبه دترمینان، روش گاوس جردن، اشاره به درختهای جستجوی بالانس، اشاره به heap sort، قانون هُرنر، ک م م، محاسبه تعداد مسیرها در گراف، تبدیل به مسایل گراف

6.   روش برنامه نویسی پویا (Dynamic Programming): ضرب ماتریس‌ها، زمان‌بندی خط تولید، بزرگترین زیردنباله مشترک، درخت جستجوی دودویی بهینه، روش بخاطرسپاری (memoization) و تفاوتهای آن با برنامه نویسی پویا

7.   مسایل کوله پشتی: کوله‌پشتی صفر و یک، کوله پشتی محدود، کوله پشتی نامحدود، جمع زیرمجموعه ها، خرد کردن پول

8.   ‎‎روش حریصانه (Greedy): کوله پشتی کسری، انتخاب فعالیت و Interval Scheduling، Interval Partitioning، Weighted Interval Scheduling، ، کد هافمن، خردکردن پول

9.   ‎‎ جست‌وجوی کامل: روش پس‌گرد (backtracking)، درخت بازی، هرس α-β ‎‎، روش انشعاب ‌و حد (Branch-and-Bound)، مسئله‌ی فروشنده‌ی دوره‌گرد.

10. ‎‎‎مرور بسیار سریع الگوریتم‌های گراف (تدریس شده در درس ساختمان داده)

a)      ‎‎ جست‌وجوی گراف به‌صورت عمق-اول، سطح-اول

b)   ‎‎ مرتب‌سازی توپولوژیکی (topological sort)، پیداکردن دور، اجزای همبند، اجزای دوهمبند

c)   ‎‎ درخت پوشای کمینه: الگوریتم‌های Prim و  Kruskal، اثبات صحت همراه با تحلیل سرشکن و معرفی ساختمان داده های مناسب آن

d)   ‎‎ کوتاه‌ترین مسیر میان دو نود: الگوریتم‌های Bellman-Ford، Dijkstra و تحلیل سرشکن الگوریتمها

11. کوتاهترین مسیر میان تمام نودها: روش مبتنی بر تعریف مجدد ضرب ماتریس، الگوریتم فلوید-وارشال، الگوریتم جانسون

12. شارش بیشینه (Maximum Flow): الگوریتم‌های Ford-Fulkerson  و  Edmonds-Karp، Bipartite Matching

13.  ‎‎‎شبکه های مرتب ساز (Sorting Networks)

14.  ‎‎ مسایل ان‌پی-تمام: مقدمات، نظریه‌ی ان‌پی-تمام، مسایل اصلی (SAT،  3-Sat، Independent Set، Vertex-Cover، Set-Cover، Set-Packing، Clique، دور همیلتونی) روش‌های اثبات ان‌پی-تمام بودن یک مسئله، استفاده از این موضوع  برای تحلیل الگوریتم‌ها.

و در صورت داشتن وقت

15. هندسه محاسباتی (Computational Geometry): الگوریتمهای دیگر Convex-Hull و Closest-pair، مثلث بندی چند ضلعی

16.  تطابق رشته‌ها  (String Matching)

17.  برنامه ریزی خطی (Linear Programming)

18.  ضرب چند جمله ای و تبدیل فوریه

 

مراجع

1.      T. Cormen, C. Leiserson, R. Riverst, C. Stein (CLRS) Introduction to Algorithms, MIT Press, Sept. 3rd Edition, 2009.

2.      Levitin, Introduction to the Design and Analysis of Algorithms, Addiso Wesley, 2007

3.      J. Kleinberg, E. Tardos, Algorithm Design, Addison Wesley, 2005.

 

مراجع کمکی

1.      U. Manber, Introduction to Algorithms: A Creative Approach, Addison Wesley, 1989.

2.      محمد قدسی و محمد مهدیان، مسئله­های الگوریتمی، انتشارات فاطمی، 1387.

 

 

 


 

 

تکالیف

12 تکلیف (6 تکلیف برنامه نویسی، 6 تکلیف دستی)

امتحان میان ترم

یکشنبه 31 فرودین 1393 ساعت 10:30 صبح

امتحان پایان ترم

شنبه 17 خرداد 1393 ساعت 8 صبح

زمان حل تمرین و رفع اشکال

سه‌شنبه ها ساعت 12:30 تا 14:00

مکان حل تمرین

کلاس 3 ساختمان شماره 1 دانشکده مهندسی برق و کامپیوتر

 

 

 

نمره دهی

30%

تکالیف

10%

کوییز

25%

امتحان میان ترم

35%

امتحان پایان ترم

 

سایر ملاحظات

 

زمان تهیه شرح درس

09/11/1392