1- شناسنامه درس:
1-1- نام درس:
الگوریتمهای گراف و شبکه
2-1- مقطع درس:
کارشناسی ارشد
3-1- تعداد واحد درس:
3 واحد
4-1- پیش‌نیاز درس:
ندارد
2- مشخصات درس:
1-2- اهداف آموزشی:
هدف از این درس آشنایی دانشجویان با مدلهای بهینه سازی مبتنی بر شبکه، مسائل زیرشاخه ای، انشعابات و کاربردهای آنها و روش های حل این مسائل و تحلیل و مقایسه الگوریتمهای حل آنها است.
2-2- مرجع اصلی درس:
شبکه جریان؛ تئوری، الگوریتمها و کاربردها، تالیف راویندار آهوجا، توماس ماگناتی و جیمز اورلین.
3- نمره‌بندی درس:
| عنوان بخش | درصد نمره |
|---|---|
| تکالیف | 20% |
| امتحانک‌ها | 10% |
| پروژه | 10% |
| امتحان میان‌ترم | 30% |
| امتحان پایان‌ترم | 30% |
4- محتوای درس:
| سرفصل | محتوا | مرجع | |||
|---|---|---|---|---|---|
| 1 | مقدمه | آشنایی با مدل مساله جریان با کمترین هزینه، مشخصات ماتریس نمایش، رابطه مساله خطی و شبکه جریان، زیرمسائل مهم مساله شبکه جریان | فصل 1 کتاب | ||
| 2 | مسیرها، درختها و دورها | آشنایی با مفاهیم و اصلاحات نظریه گراف، انواع نمایش مساله شبکه جریان، تبدیلات مساله شبکه جریان، قضایا و الگوریتمهای مرتبط با مسائل تبدیل یافته | فصل 2 کتاب | ||
| 3 | الگوریتمهای برچسب گذار | آشنایی با الگوریتمهای جستجو، کاربرد الگوریتمهای جستجو در تشخیص همبندی، مولفه های شبکه، دوبخشی بودن شبکه و ....، الگوریتم یافتن ترتیب توپولوژیکی در شبکه و ارتباط آن با وجود دور، الگوریتم تجزیه جریان، قضیه تجزیه جریان و دورهای افزایشی، الگوریتمهای برچسب گذار، درخت کوتاهترین مسیرها، مساله کوتاهترین مسیر در شبکه های بدون دور، الگوریتم دایجسترا | فصل 4 کتاب | ||
| 4 | االگوریتمهای اصلاح برچسب | آشنایی با شرایط بهینگی در مسائل شبکه جریان، قضیه دور منفی افزایشی، الگوریتمهای اصلاح برچسب کلی، الگوریتمهای اصلاح برچسب تعمیم یافته، یافتن دورهای منفی، مساله کوتاهترین مسیر در شبکه های فاقد هزینه منفی، مساله کوتاهترین مسیرها روی همه گره های شبکه و زیرمسائل منشعب از آن، مساله مینیمم دور روی نسبت هزینه به زمان، مساله مسیر با بیشترین ظرفیت، مساله مسیر با بیشترین ضریب اطمینان، مساله کوتاهترین مسیر مقید، قضیه شرط بهینه کوتاهترین مسیر، الگوریتمهای مبتنی بر تشخیص دور صفر و دور منفی، جوابهای پایه ای شدنی اولیه، روش دوفازی، روش M-بزرگ، مفاهیم تباهیدگی، دور و ایستایی در الگوریتمهای بهینه سازی | فصل 5 کتاب | ||
| 5 | مساله ماکزیمم جریان | ارتباط جریانها و برشها در شبکه، الگوریتم کلی مسیر افزایشی، قضیه ماکزیمم جریان و مینیمم برش، مساله یافتن جریان شدنی و کاربردهای آن، مفهوم شبکه باقیمانده و الگوریتمهای مرتبط، الگوریتم برچسب گذار در مسائل ماکزیمم جریان، قضیه مسیر افزایشی و انتگرالیتی | فصل 6 کتاب | ||
| 6 | الگوریتمهای چندجمله ای ماکزیمم جریان | آشنایی با برچسب های فاصله، الگوریتم مقیاس ظرفیت، الگوریتم کوتاهترین مسیر افزایشی، شبکه های لایه ای و برچسبهای فاصله، الگوریتم preflow-push، الگوریتم FIFO، الگوریتم Highest-Label، الگوریتم Excess Scaling، جریان در شبکه های با ظرفیت یک، جریان در شبکه های دوبخشی، جریان در شبکه های بدون جهت مسطح | فصل 7 و 8 کتاب |
5- تقویم درس:
| شماره هفته | شنبه | یکشنبه | سه‌شنبه | چهارشنبه |
|---|---|---|---|---|
| 1 | - | - | درس 1 | - |
| 2 | - | جشن نودانشجویان | درس 2 | - |
| 3 | تحویل تکلیف 1 | درس 2 | درس 3 | امتحانک 1 |
| 4 | تحویل تکلیف 2 | درس 3 | درس 3 | - |
| 5 | تحویل تکلیف 3 | درس 4 | درس 4 | امتحانک 2 |
| 6 | تحویل تکلیف 4 | درس 5 | درس 5 | - |
| 7 | تحویل تکلیف 5 | درس 6 | درس 6 | امتحانک 3 |
| 8 | تحویل تکلیف 6 | درس 7 | درس 7 | - |
| 9 | تحویل تکلیف 7 | درس 8 | درس 8 | امتحانک 4 |
| 10 | تحویل تکلیف 8 | درس 9 | درس 9 | - |
| 11 | تحویل تکلیف 9 | درس 10 | درس 10 | امتحانک 5 |
| 12 | تحویل تکلیف 10 | درس 11 | درس 11 | - |
| 13 | تحویل تکلیف 11 | - | - | امتحانک 6 |