U letnjem semestru 2011 (sa početkom u martu) organizujemo dva doktorska kursa:
Kombinatorna optmizacija i Dizajn i analiza algoritama. Opis kurseva se nalazi dole. Ovi kursevi su od izuzetne važnosti svim studentima koji planiraju da se bave istraživanjem iz bilo koje oblasti algoritama, kombinatorike i optimizacije.
Svaki kurs će se sadržati od 32 časa, organizovanih u 8 dana po 4 časa. Kursevi će se održavati u naizmeničnim nedeljama ponedeljkom 13:00-17:00 na Računarskom Fakultetu (Knez Mihailova 6/6, Beograd) u učionici RG8.
Kursevi su besplatni i otvoreni svim postdiplomskim studentima. Molim sve zainteresovane da se hitno prijave slanjem poruke na e-mail.
Kurs 1: Kombinatorna optimizacija
Predavač:Nebojša Gvozdenović i gostujući predavač za poslednja 4 časa Janez Povh
Literatura i softver (podebljana je referenca koja će se najviše pratiti tokom kursa):
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 (Najpotrebniji softver može se skinuti ovde.)
Domaći zadaci: biće dozvoljeno formiranje grupa za izradu i biće napravljeno 2-3 domaća zadatka u toku kursa.
Pregled tema po časovima i danima:
- 1. dan (časovi 1.-4.) Šta je kombinatorna optimizacija, koji su to glavni optimizacioni problemi na grafovima, kako se modelira problem celobrojnim linearnim programom i šta je i kako se koristi relaksacija celobrojnog programa, kako se rešavaju kombinatorni optimizacioni problemi, algoritmi, teorija kompleksnosti, šta su to aproksimativni algoritmi, šta su heuristike i metaheuristike, primene.
- 2. dan (časovi 5.-8.) Problem najkraćeg puta u grafu, nenegativne cene na granama, bez negativnih kontura, Dijkstra algoritam, razapinjuća stabla, primene.
- 3. dan (časovi 9.-12.) Bipartitni grafovi: problemi sparivanja i prekrivanja, dogradivi putevi, Teoreme König-a, najbrojnije sparivanje u bipartitnom grafu, najteže sparivanje (grane grafa sa težinama), politop sparivanja, primene.
- 4. dan (časovi 13.-16.) Teorema Mengera, mrežni protoci, maksimalan protok, Teorema Hoffman-a, najjeftiniji protok, primene.
- 5. dan (časovi 17.-20.) Sparivanja (generalni slučaj, ne bipartitni), formula Tutte-Berge, najbrojnije sparivanje algoritam Edmonds-a, najteže sparivanje, politop sparivanja
- 6. dan (časovi 21.-24.) Klike, stabilni skupovi čvorova i problemi bojenja, teorema 4 boje, Brooks-ova teorema, bojenje grana, perfektni grafovi, primene
- 7. dan (časovi 25.-28. prvi predlog) Mrežni protoci sa više roba, disjunktni putevi, sa dve robe, disjunktni putevi u acikličnim orijentisanim grafovima, disjuntni u smislu čvorova i u smislu grana, tehnika generisanja kolona za rešavanje problema protoka sa više roba, primene.
- (7. dan alternativa, ukoliko se ispostavi da je prethodna tema manje zanimljiva) Matroidi-osnove
- 8. dan (časovi 29.-30.) Kako dobiti bolju aproksimaciju za konveksni omotač diskretnog skupa dopustivih rešenja od standardne relaksakcije celobrojnog linearnog programa, podizanje u prostor veće dimenzije i projekcije, kopozitivno, semidefinitno i polinomno programiranje u službi kombinatorne optimizacije, rezultati za MAX CUT (Goemans-Williamson), stepen stabilnosti grafa i hromatski broj grafa (Lovász).
Kurs 2: Dizajn i analiza algoritama
Predavač: Dragan Urošević
Pregled tema:
- Pojam algoritma. Dizajn i analiza algoritma. Dokazivanje korektnosti i ocenjivanje složenosti.
- Algoritamske paradigme: Podeli pa vladaj, Pohlepni algoritmi, Dinamičko programiranje
- Obilazak grafa u dubinu i algoritmi zasnovani na njemu: odredjivanje artikulacionih tačaka, odredjivanje mostova, odredjivanje komponenti dvostruke povezanosti, jako povezane komponente
- Obilazak grafa u širinu
- Najkraća rastojanja u grafu
- Minimalno povezujuće stablo
- Fibonačijev heap
- Binomijalni heap
- Splay stabla
- Mrežni protok – detalji implementacija najefikasnijih algoritama, maksimalni protok sa minimalnom cenom
- Uparivanje u grafu: uparivanje maksimalne kardinalnosti, maksimalno težinsko uparivanje
- Kompjuterska geometrija: konveksni omotač, Trijangulacija poligona, Voronoi dijagram, Delaunaj trijangulacija
- Heširanje: perfektno heširanje
- Algoritmi za uparivanje reči (string matching)
- Strukture podataka prilagodjene konkretnim primenama – obim zavisi od vremena