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

Pokročilá algoritmizace

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
MI-PAL Z,ZK 4 2P+1C česky
Přednášející:
Luděk Kučera (gar.)
Cvičící:
Tomáš Valla
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

Rozvrh na zimní semestr 2018/2019:
Rozvrh není připraven
Rozvrh na letní semestr 2018/2019:
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
Út
místnost T9:347
Kučera L.
11:00–12:30
(přednášková par. 1)
Dejvice
NBFIT učebna
místnost T9:347
Valla T.
14:30–16:00
LICHÝ TÝDEN

(přednášková par. 1
paralelka 101)

Dejvice
NBFIT učebna
St
Čt

Předmět je součástí následujících studijních plánů:
Platnost dat k 23. 5. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet1430806.html