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

Algoritmy vizuálně

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
BI-AVI.21 Z,ZK 4 2P+1C česky
Podmínkou zápisu předmětu je dřívější úspěšné absolvování předmětů:
Programování a algoritmizace 1 (BI-PA1)
Prerekvizita:
Programování a algoritmizace 2 (BI-PA2)
Přednášející:
Luděk Kučera (gar.)
Cvičící:
Luděk Kučera (gar.)
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
Rozvrh na zimní semestr 2022/2023:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
místnost T9:351
Kučera L.
14:30–16:00
(přednášková par. 1)
Dejvice
NBFIT PC ucebna
místnost T9:351
Kučera L.
16:15–17:00
(přednášková par. 1
paralelka 101)

Dejvice
NBFIT PC ucebna
St
Čt

Rozvrh na letní semestr 2022/2023:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 28. 11. 2022
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6290306.html