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ů:

Bc. program Informatika, pro fázi studia bez oboru, kombi., 2015 - 2020 (povinný předmět programu)
Bc. obor Bezpečnost a informační technologie, kombi., 2015 - 2019 (povinný předmět programu)
Bc. obor Webové a softwarové inženýrství, zaměření Softwarové inženýrství, kombi., 2015 - 2020 (povinný předmět programu)
Bc. obor Bezpečnost a informační technologie, kombinovaná forma studia, 2020 (povinný předmět programu)