Toto je starší verze dokumentu!

Přednáška z Algoritmů a datových struktur I 2019/20

Přednáším Diskrétní matematiku (NTIN060) každé úterý v 10:40 v učebně S11.

Pokud se mnou chcete cokoliv probrat, jste vítáni v mé pracovně S326 na Malé Straně. Případně napište e-mail na adresu koutecky+ads1@iuuk.mff.cuni.cz a/nebo uveďte v předmětu text [ADS1].

V druhé paralelce přednáší Jan Hric, přednášku se budeme snažit udržovat synchronní.

datum	co se přednášelo [zdroj]
18. 2.	Hledání nejbohatšího úseku. Snaha o definici algoritmu. Von Neumannův výpočetní model, Ǒčková notace ($\mathcal{O}, \mathcal{o}, \Omega, \omega$), výpočetní model RAM [L 1.1, 2]
25. 2.	Základní grafové algoritmy: prohledávání do šířky (BFS), prohledávání do hloubky (DFS) na neorientovaném grafu, detekce mostů, DFS na orientovaném grafu [L 5.1-5.6]
3. 3.	Pokračování DFS: topologické číslování; detekce komponent silné souvislosti v lineárním čase; úvod do nejkratších cest [L 5.7-6.1]
10. 3.	Nejkratší cesty: Dijkstrův algoritmus pořádně; obecný relaxační algoritmus; Bellman-Ford umí detekovat záporný cyklus; Floyd-Warshall umí spočítat matici vzdáleností [L 6.1-6.4]
17. 3.	Minimální kostry: Jarníkův (Primův, Dijkstrův) algoritmus, Borůvkův algoritmus, Kruskalův algoritmus, keříková struktura Union-Find [L 7.1-7.4], přednáška, "zápis" z přednášky
24. 3.	Plán: stromové datové struktury: binární vyhledávací stromy, AVL-stromy [L 8] přednáška, zápis z přednášky (OneNote)
31. 3.	Plán: $(a,b)$-stromy, červeno-černé stromy [L 8]

Užitečné zdroje

Mareš, Valla: Průvodce labyrintem algoritmů [L]
Video přednášky Martina Mareše