Докторски курсеви 2011

У летњем семестру 2011 (са почетком у марту) организујемо два докторска курса:
Комбинаторна оптмизација и Дизајн и анализа алгоритама. Опис курсева се налази доле. Ови курсеви су од изузетне важности свим студентима који планирају да се баве истраживањем из било које области алгоритама, комбинаторике и оптимизације.

Сваки курс ће се садржати од 32 часа, организованих у 8 дана по 4 часа.  Курсеви ће се одржавати у наизменичним недељама понедељком 13:00-17:00 на Рачунарском Факултету (Кнез Михаилова 6/6, Београд) у учионици РГ8.

Курсеви су бесплатни и отворени свим постдипломским студентима. Молим све заинтересоване да се хитно пријаве слањем поруке на Ova adresa el. pošte je zaštićena od spambotova. Omogućite JavaScript da biste je videli.##14###.

 

Курс 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 тријангулација
  • Хеширање: перфектно хеширање
  • Алгоритми за упаривање речи (стринг матцхинг)
  • Структуре података прилагодјене конкретним применама – обим зависи од времена