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

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 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
Rozvrh na zimní semestr 2023/2024:
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
místnost T9:348
Kučera L.
10:00–11:45
(přednášková par. 1)
Dejvice
NBFIT PC ucebna
místnost T9:348
Kučera L.
11:45–12:30
(přednášková par. 1
paralelka 101)

Dejvice
NBFIT PC ucebna
Út
St
Čt

Rozvrh na letní semestr 2023/2024:
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
St
místnost TH:A-1247
Kučera L.
09:15–10:45
(přednášková par. 1)
Thákurova 7 (budova FSv)
seminární místnost
místnost TH:A-1247
Kučera L.
11:00–11:45
(přednášková par. 1
paralelka 101)

Thákurova 7 (budova FSv)
seminární místnost
Čt

Předmět je součástí následujících studijních plánů:
Platnost dat k 23. 4. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6290306.html