У летњем семестру 2011 (са почетком у марту) организујемо два докторска курса:
Комбинаторна оптмизација и Дизајн и анализа алгоритама. Опис курсева се налази доле. Ови курсеви су од изузетне важности свим студентима који планирају да се баве истраживањем из било које области алгоритама, комбинаторике и оптимизације.
Сваки курс ће се садржати од 32 часа, организованих у 8 дана по 4 часа. Курсеви ће се одржавати у наизменичним недељама понедељком 13:00-17:00 на Рачунарском Факултету (Кнез Михаилова 6/6, Beograd) у учионици РГ8.
Курсеви су бесплатни и отворени свим постдипломским студентима. Молим све заинтересоване да се хитно пријаве слањем поруке на е-маил.
Курс 1: Комбинаторна оптимизација
Предавач: Небојша Гвозденовић и гостујући предавач за последња 4 часа Janez Povh
Литература и софтвер (подебљана је референца која ће се највише пратити током курса):
C. H. Papadimitriou, K. Steiglitz: Combinatorial optimization; algorithms and complexity
A. Schrijver: A Course in Combinatorial Optimization
A. Schrijver: Combinatorial Optimization; Polyhedra and Efficiency
W. Hochstättler: CATBox, An interactive course in combinatorial optimization (Најпотребнији софтвер може се скинути овде.)
Домаћи задаци: биће дозвољено формирање група за израду и биће направљено 2-3 домаћа задатка у току курса.
Преглед тема по часовима и данима:
- 1. дан (часови 1.-4.) Шта је комбинаторна оптимизација, који су то главни оптимизациони проблеми на графовима, како се моделира проблем целобројним линеарним програмом и шта је и како се користи релаксација целобројног програма, како се решавају комбинаторни оптимизациони проблеми, алгоритми, теорија комплексности, шта су то апроксимативни алгоритми, шта су хеуристике и метахеуристике, примене.
- 2. дан (часови 5.-8.) Проблем најкраћег пута у графу, ненегативне цене на гранама, без негативних контура, Dijkstra алгоритам, разапињућа стабла, примене.
- 3. дан (часови 9.-12.) Бипартитни графови: проблеми спаривања и прекривања, доградиви путеви, Teoreme König-а, најбројније спаривање у бипартитном графу, најтеже спаривање (гране графа са тежинама), политоп спаривања, примене.
- 4. дан (часови 13.-16.) Теорема Mengera, мрежни протоци, максималан проток, Теорема Hoffman-а, најјефтинији проток, примене.
- 5. дан (часови 17.-20.) Спаривања (генерални случај, не бипартитни), формула Tutte-Berge, најбројније спаривање алгоритам Edmonds-а, најтеже спаривање, политоп спаривања
- 6. дан (часови 21.-24.) Клике, стабилни скупови чворова и проблеми бојења, теорема 4 боје, Brooks-ова теорема, бојење грана, перфектни графови, примене
- 7. дан (часови 25.-28. први предлог) Мрежни протоци са више роба, дисјунктни путеви, са две робе, дисјунктни путеви у ацикличним оријентисаним графовима, дисјунтни у смислу чворова и у смислу грана, техника генерисања колона за решавање проблема протока са више роба, примене.
- (7. дан алтернатива, уколико се испостави да је претходна тема мање занимљива) Matroidi-основе
- 8. дан (часови 29.-30.) Како добити бољу апроксимацију за конвексни омотач дискретног скупа допустивих решења од стандардне релаксакције целобројног линеарног програма, подизање у простор веће димензије и пројекције, копозитивно, семидефинитно и полиномно програмирање у служби комбинаторне оптимизације, резултати за MAX CUT (Goemans-Williamson), степен стабилности графа и хроматски број графа (Lovász).
Курс 2: Дизајн и анализа алгоритама
Предавач: Драган Урошевић
Преглед тема:
- Појам алгоритма. Дизајн и анализа алгоритма. Доказивање коректности и оцењивање сложености.
- Алгоритамске парадигме: Подели па владај, Похлепни алгоритми, Динамичко програмирање
- Обилазак графа у дубину и алгоритми засновани на њему: одредјивање артикулационих тачака, одредјивање мостова, одредјивање компоненти двоструке повезаности, јако повезане компоненте
- Обилазак графа у ширину
- Најкраћа растојања у графу
- Минимално повезујуће стабло
- Fibonačijev heap
- Биномијални heap
- Splay стабла
- Мрежни проток – детаљи имплементација најефикаснијих алгоритама, максимални проток са минималном ценом
- Упаривање у графу: упаривање максималне кардиналности, максимално тежинско упаривање
- Компјутерска геометрија: конвексни омотач, Тријангулација полигона, Voronoi дијаграм, Delaunaj тријангулација
- Хеширање: перфектно хеширање
- Алгоритми за упаривање речи (стринг матцхинг)
- Структуре података прилагодјене конкретним применама – обим зависи од времена