Sylabus
Toky v sítích: Rychlé implementace Ford-Fulkersonova algoritmu (algoritmy Dinitzův a 3 Indů) a Goldbergův algoritmus. Aritmetické a algebraické algoritmy: sčítání binárních čísel (obecná metoda a implementace Kogge-Stone, Brent-Kung, Ladner-Fisher, Han-Carlson), Diskrétní Fourierova transformace (motivace a algoritmus FFT). Geometrické algoritmy: konvexní obal a Voroného diagram (obojí v rovině) Vyhledávání řetězců: Algoritmus Knuth-Morris-Pratt a jeho zobecnění Aho-Corasick. Simplexový algoritmus lineárního programování. Rozpis na jednotlivé lekce:
1. Toky v sítích - Dinitzův algoritmus
2. Toky v sítích - algoritmus 3 Indů
3. Toky v sítích - Goldbergův algoritmus
4. Sčítání binárních čísel (obecná metoda a implementace Kogge-Stone, Brent-Kung, Ladner-Fisher, Han-Carlson)
5. Motivace diskrétní Fourierovy transformace
6. Algoritmus rychlé Fourierovy transformace (FFT - Fast Fourier Transform)
7. Konvexní obal konečné množiny v rovině
8. Voroného diagram
9. Voroného diagram - pokračování
10. Vyhledávání řetězců - algoritmus Knuth-Morris-Pratt
11. Vyhledávání řetězců - algoritmus Aho-Corasick
12. Simplexový algoritmus lineárního programování
Anotace
Předmět navazuje na předmět NTIN061 Algoritmy a datové struktury II, algoritmy vyučované v rámci ADS II ukazuje pod jiným úhlem pohledu a zaměřuje se na detailní ilustraci algoritmických myšlenek, na kterých jsou založeny. Algoritmy jsou presentovány pomoci vizualizací, které jsou vytvářeny tak, aby tyto myšlenky presentovaly graficky a ilustrovaly především invarianty algoritmů.
Cílem předmětu je ukázat studentům algoritmy jako tvůrčí oblast informatiky a naučit je o chování a vlastnostech algoritmů přemýšlet exaktním matematickým způsobem.