Algoritmy vizuálně

Vztahy:

Podmínkou zápisu na předmět BI-AVI.21 je, že student v některém z předchozích semestrů úspěšně absolvoval předmět BI-PA1

Podmínkou zápisu na předmět BI-AVI.21 je, že si student v některém z předchozích semestrů zapsal předmět BI-PA2

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)
• Bc. specializace Informační bezpečnost, 2024 (volitelný předmět)
• Bc. program, pro fázi studia bez specializace, 2024 (volitelný předmět)
• Bc. specializace Manažerská informatika, 2024 (volitelný předmět)
• Bc. specializace Počítačová grafika, 2024 (volitelný předmět)
• Bc. specializace Softwarové inženýrství, 2024 (volitelný předmět)
• Bc. specializace Webové inženýrství, 2024 (volitelný předmět)
• Bc. specializace Počítačové sítě a Internet, 2024 (volitelný předmět)
• Bc. specializace Počítačové inženýrství, 2024 (volitelný předmět)
• Bc. specializace Počítačové systémy a virtualizace, 2024 (volitelný předmět)
• Bc. specializace Umělá inteligence, 2024 (volitelný předmět)
• Bc. specializace Teoretická informatika, 2024 (volitelný předmět)