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

Algoritmy vizuálně

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
BI-AVI.21 Z,ZK 4 2P+1C česky
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ů:
Platnost dat k 27. 5. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6290306.html