Pokročilá algoritmizace

Přednášející:

Luděk Kučera (gar.)

Cvičící:

Robert Kessl

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Studenti se naučí nejdůležitější pokročilé algoritmy a datové struktury z různých odvětví informatiky, které nejsou pokryty přednáškami bakalářského stupně a jinými přednáškami magisterského stupně. Poznají také způsoby zvládnutí úloh, které dle dnešních poznatků nejsou zvládnutelné optimálním způsobem v polynomiálně omezeném výpočetním čase.

Požadavky:

Osnova přednášek:

1. Pokročilé algoritmy pro toky v sítích.

2. Párování: hledání v bipartitním i obecném grafu, nejlacinější párování, paralelní pravděpodobnostní algoritmus.

3. Rovinné grafy: podmínky rovinnosti, testování rovinnosti, isomorfismus rovinných grafů.

4. Zpracování digitálního signálu: rychlá Fourierova transformace a metody spektrální komprese.

5. Geometrické algoritmy: konvexní obal a Voroného diagram, a další.

6. Proudové (streaming) algoritmy.

7. Prvočíselnost: testování pravděpodobnostní a deterministické, důkaz prvočíselnosti.

8. Aproximační algoritmy.

9. Aproximační schémata.

10. Online algoritmy.

11. Obecné heuristické metody: simulované žíhání, tabu search, genetické algoritmy.

12. Specializované heuristické metody: spektrální heuristiky, TSP.

13. Pravděpodobnostní algoritmy a pravděpodobnostní analýza algoritmů.

Osnova cvičení:

1. [2] Pomalost/nekonečnost FF algoritmu, ověření paralelního algoritmu pro párování, speciální případy párování.

2. Kuratowského věta jako algoritmus testování planarity, nerovinnost K5 a K33, rovinná nakreslení málo souvislých grafů, pravděpodobnostní důkaz neisomorfismu.

3. Fourierovy obrazy základních funkcí, konvoluce a FT, kosinová transformace.

4. Aplikace konvexního obalu a Voroného diagramu a jejich souvislost.

5. Základní příklady proudových algoritmů.

6. Aproximace problému loupežníků a bin-packing.

7. Základní poznatky spektrální teorie grafů.

8. Příklady pravděpodobností analýzy jednoduchých heuristik.

9. [5] Referáty studentů o experimentálním zkoumání jimi naprogramovaných algoritmů.

Cíle studia:

Cílem předmětu je poskytnout přehled nejdůležitějších algoritmů a datových struktur z různých odvětví informatiky, na jejich základě ilustrovat obecné zásady a principy tvorby efektivních algoritmů a ukázat způsoby zvládnutí úloh, které dle dnešních poznatků nejsou zvládnutelné optimálním způsobem v polynomiálně omezeném výpočetním čase.

Studijní materiály:

Kučera, L. ''Algovize''. Praha: Univerzita Karlova, 2009. ISBN 978-80-902938-5-4.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. ''Introduction to Algorithms (3d Edition)''. The MIT Press, 2009. ISBN 0262033844.

Kleinberg, J., Tardos, E. ''Algorithm Design''. Addison Wesley, 2005. ISBN 0321295358.

Poznámka:

Rozsah=prednasky+proseminare+cviceni2p+1c, Prednasejici: prof. RNDr. Luděk Kučera DrSc.

Rozvrh na zimní semestr 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 2011/2012:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po	místnost T9:302 Kessl R. 16:15–17:45 LICHÝ TÝDEN (přednášková par. 1 paralelka 101) Dejvice NBFIT učebna místnost T9:302 Kessl R. 16:15–17:45 SUDÝ TÝDEN (přednášková par. 1 paralelka 102) Dejvice NBFIT učebna
Út	místnost T9:349 Kučera L. 14:30–16:00 (přednášková par. 1) Dejvice NBFIT místnost
St
Čt
Pá

Předmět je součástí následujících studijních plánů:

• Zaměření Teoretická informatika - verze pro ty, kteří se zapsali v roce 2010 (povinný předmět zaměření)
• Zaměření Teoretická informatika - verze pro ty, kteří se zapsali v roce 2011 (povinný předmět zaměření)
• Zaměření Teoretická informatika - verze pro ty, kteří se zapsali v roce 2012 (povinný předmět zaměření)