Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2019/2020

Pokročilá algoritmizace

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
MI-PAL.16 Z,ZK 5 2P+1C česky
Přednášející:
Cvičící:
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: 2p+1c

Další informace:
Pro tento předmět se rozvrh nepřipravuje
Předmět je součástí následujících studijních plánů:
Platnost dat k 14. 12. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet4656206.html