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

Algoritmy a grafy 1

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
BIK-AG1 Z,ZK 6 14KP+4KC česky
Přednášející:
Pavel Tvrdík (gar.), Jiří Chludil
Cvičící:
Pavel Tvrdík (gar.), Jiří Chludil
Předmět zajišťuje:
katedra teoretické informatiky
Anotace:
Požadavky:
Osnova přednášek:

1. Grafové modely, neorientované grafy, izomorfismus, sousednost.

2. Sledy, tahy, cesty, souvislost, orientované grafy.

3. Silná souvislost, acyklické grafy, reprezentace grafů, procházení do šířky.

4. Procházení do hloubky, topologické uspořádání, silně souvislé komponenty.

5. Stromy, kostry, kružnice, minimální kostry.

6. Algoritmy řazení.

7. Rozptylovací tabulky (rozptylovací funkce, synonyma, řešení kolizí, různé implementace a jejich složitosti).

8. Stromy jako datové struktury, základní vlastnosti, binární haldy, prioritní fronta, HeapSort.

9. Rekurzivní algoritmy a metoda Rozděl-a-panuj.

10. Dynamické programování.

11. Algoritmy hledání nejkratších cest 1-n v grafech.

12. Toky v sítích, určení maximálního toku v síti.

13. Vyhledávání a vyhledávací stromy, vyvažování, AVL stromy, trie.

Osnova cvičení:
Cíle studia:

Předmět pokrývá to nejzákladnější z efektivních algoritmů, datových struktur a teorie grafů, které by měl znát každý informatik.Spolupracuje se souběžně vyučovanými předměty BI-AAG a BI-ZDM, ve kterých studenti získají znalosti a dovednosti nezbytné pro vyhodnocování operační a paměťové složitosti algoritmů a naučí se prakticky používat asymptotickou matematiku.

Studijní materiály:

[1] Cormen, T. H. - Leiserson, C. E. - Rivest, R. L. - Stein, C.: Introduction to Algorithms, 3rd Edition, MIT Press, 2009, 978-0262033848,

Poznámka:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/BIK-AG1/

14+0+4

Další informace:
https://courses.fit.cvut.cz/BIK-AG1/
Rozvrh na zimní semestr 2019/2020:
Rozvrh není připraven
Rozvrh na letní semestr 2019/2020:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 22. 9. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet3469006.html