Algoritmy a grafy 1

Jakub Roupec, FIT ČVUT Václav Vítek, FIT ČVUT Tadeáš Báča, FIT ČVUT

Obsah

1 Úvod

1.1 Obsah předmětu

1.2 Doporučená literatura

2 Grafy

2.1 Grafy

2.2 Okolí a stupeň vrcholu

2.3 Sled, cesta a kružnice v grafu

2.4 Souvislost a izomorfismus

2.5 Reprezentace grafu

3 Stromy

3.1 Stromy

3.2 Zakořeněný strom

3.3 Binární strom

3.4 Binomiální strom

3.5 Binární vyhledávací strom

3.6 AVL

3.7 Dub

4 Kostry

4.1 Kostra grafu

4.2 Minimální kostra grafu

5 Základní grafové algoritmy

5.1 BFS

5.2 DFS

5.3 TopSort

6 Nejkratší cesty v ohodnocených grafech

6.1 Nejkratší cesty

6.2 Dijkstrův algoritmus

6.3 Relaxace

6.4 Bellman-Fordův algoritmus

7 Složitost

7.1 Amortizovaná složitost

8 Haldy

8.1 Binární halda

8.2 Binomiální halda

8.3 Srovnání binární a binomiální haldy

9 Randomizace

9.1 Pravděpodobnost

9.2 Randomizace a její využití

9.3 Hešování

10 Řazení

10.1 Řazení

10.2 Základní řadící algoritmy

10.3 Merge Sort

10.4 QuickSelect

11 Dynamické programování