Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2023/2024
UPOZORNĚNÍ: Jsou dostupné studijní plány pro následující akademický rok.

Algoritmy a grafy 1

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
BIK-AG1 Z,ZK 6 14KP+4KC česky
Garant předmětu:
Přednášející:
Cvičící:
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/

Další informace:
https://courses.fit.cvut.cz/BIK-AG1/
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. 3. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet3469006.html