Algoritmy vizuálně
| Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
|---|---|---|---|---|
| BI-AVI.21 | Z,ZK | 4 | 2P+1C | česky |
- Garant předmětu:
- Luděk Kučera
- Přednášející:
- Luděk Kučera
- Cvičící:
- Luděk Kučera
- Předmět zajišťuje:
- katedra teoretické informatiky
- Anotace:
-
Jedná se o doplňkový předmět k výuce algoritmů. Přednášky přinášejí poznatky o konkrétních algoritmech z různých oblastí informatiky, které podstatným způsobem rozšiřují znalosti, které student získá v předmětu BI-AG1, případně i BI-AG2. Velký okruh pokrývaných témat je umožněn intenzivním využíváním vizualizací systému Algovize (http://www.algovision.org), které velmi usnadňují pochopení základní myšlenky algoritmu.
- Požadavky:
-
Vstupní znalostní požadavky nejsou.
- Osnova přednášek:
-
1. Stromové datové struktury (obecné metody a algoritmy neprobrané v AG1 a AG2, např. červeno-černé stromy)
2. Hledání nejkratších cest (jiný pohled na Dijkstrův a Bellman-Fordův algoritmus)
3. Největší toky v sítích metodou zlepšující cesty (Dinitz a 3 Indové)
4. Největší toky v sítích metodou pre-flow (Goldberg)
5. Diskrétní Fourierova transformace a algoritmus FFT
6. Algoritmy sčítání čísel (Kogge-Stone, Ladner-Fischer, Brent-Kung)
7. Geometrické algoritmy (konvexní obal, Voronoi diagram - Fortune)
8. Obvody pro třídění a přepínání (bitonické třídění, licho-sudé třídění)
9. Metoda konjugovaných gradientů
10. Využití vlastních čísel (minimální řez v grafu)
11. Lineární programování (simplexová metoda a věta o dualitě)
12. Kvantové algoritmy (základní pojmy - bit, entanglement,
Grooverův a Simonův algoritmus, naznačení Shorova algoritmu pro faktorizaci čísel)
13. Kvantové algoritmy (pokračování)
- Osnova cvičení:
-
1. Stromové datové struktury (obecné metody a algoritmy neprobrané v AG1 a AG2, např. červeno-černé stromy)
2. Hledání nejkratších cest (jiný pohled na Dijkstrův a Bellman-Fordův algoritmus)
3. Největší toky v sítích metodou zlepšující cesty (Dinitz a 3 Indové)
4. Největší toky v sítích metodou pre-flow (Goldberg)
5. Diskrétní Fourierova transformace a algoritmus FFT
6. Algoritmy sčítání čísel (Kogge-Stone, Ladner-Fischer, Brent-Kung)
7. Geometrické algoritmy (konvexní obal, Voronoi diagram - Fortune)
8. Obvody pro třídění a přepínání (bitonické třídění, licho-sudé třídění)
9. Metoda konjugovaných gradientů
10. Využití vlastních čísel (minimální řez v grafu)
11. Lineární programování (simplexová metoda a věta o dualitě)
12. Kvantové algoritmy (základní pojmy - bit, entanglement,
Grooverův a Simonův algoritmus, naznačení Shorova algoritmu pro faktorizaci čísel)
13. Kvantové algoritmy (pokračování)
- Cíle studia:
- Studijní materiály:
-
1. L. Kučera: Algovize, aneb procházka krajinou algoritmů, Blatenská tiskárna, 2009, ISBN 8090293859, 9788090293854. Dostupné z http://www.algovision.org
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, MIT Press, 1990, 2009, ISBN 978-0-262-03384-8
3. B. Barak, S. Arora: Computational Complexity: A Modern Approach, 2007, Cambridge Univ. Press, ISBN 978-0521424264
- Poznámka:
-
Chybí požadavky.
- Další informace:
- http://www.algovision.org/FIT-BI-AVI.html
- Pro tento předmět se rozvrh nepřipravuje
- Předmět je součástí následujících studijních plánů:
-
- Bc. program Informatika, pro fázi studia bez oboru, 2015-2020 (volitelný předmět)
- Bc. obor Bezpečnost a informační technologie, 2015-2020 (volitelný předmět)
- Bc. obor Teoretická informatika, 2015-2020 (volitelný předmět)
- Bc. obor Počítačové inženýrství, 2015-2020 (volitelný předmět)
- Bc. obor Informační systémy a management, 2015-2020 (volitelný předmět)
- Bc. obor Webové a softwarové inženýrství, zaměření Softwarové inženýrství, 2015-2020 (volitelný předmět)
- Bc. obor Webové a softwarové inženýrství, zaměření Webové inženýrství, 2015-2020 (volitelný předmět)
- Bc. obor Webové a softwarové inženýrství, zaměření Počítačová grafika, 2015-2020 (volitelný předmět)
- Bc. obor Znalostní inženýrství, 2018-2020 (volitelný předmět)
- Bc. specializace Informační bezpečnost, 2021 (volitelný předmět)
- Bc. specializace Manažerská informatika, 2021 (volitelný předmět)
- Bc. specializace Počítačová grafika, 2021 (volitelný předmět)
- Bc. specializace Počítačové inženýrství, 2021 (volitelný předmět)
- Bc. program, pro fázi studia bez specializace, 2021 (volitelný předmět)
- Bc. specializace Webové inženýrství, 2021 (volitelný předmět)
- Bc. specializace Umělá inteligence, 2021 (volitelný předmět)
- Bc. specializace Teoretická informatika, 2021 (volitelný předmět)
- Bc. specializace Softwarové inženýrství, 2021 (volitelný předmět)
- Bc. specializace Počítačové systémy a virtualizace, 2021 (volitelný předmět)
- Bc. specializace Počítačové sítě a Internet, 2021 (volitelný předmět)
- Study plan for Ukrainian refugees (volitelný předmět)