Pokročilá algoritmizace

Garant předmětu:

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:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/MI-PAL/

Další informace:

https://courses.fit.cvut.cz/MI-PAL/

Pro tento předmět se rozvrh nepřipravuje

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

• Mgr. obor Znalostní inženýrství, 2016-2017 (volitelný předmět)
• Mgr. obor Počítačové systémy a sítě, 2016-2019 (volitelný předmět)
• Mgr. obor Návrh a programování vestavných systémů, 2016-2019 (volitelný předmět)
• Mgr. obor Webové a softwarové inženýrství, zaměření Informační systémy a management, 2016-2019 (volitelný předmět)
• Mgr. obor Webové a softwarové inženýrství, zaměření Softwarové inženýrství, 2016-2019 (volitelný předmět)
• Mgr. obor Webové a softwarové inženýrství, zaměření Webové inženýrství, 2016-2019 (volitelný předmět)
• Mgr. program Informatika, pro fázi studia bez oboru, 2016-2019 (VO)
• Mgr. obor Systémové programování, zaměření Systémové programování, 2016-2019 (volitelný předmět)
• Mgr. obor Systémové programování, zaměření Teoretická informatika, 2016-2017 (povinný předmět zaměření)
• Mgr. obor Znalostní inženýrství, 2018-2019 (volitelný předmět)