Algoritmy a datové struktury 1

Přednáška z Algoritmů a datových struktur 1 [NTIN060] se koná v LS 2024/2025 ve čtvrtky od 12:20 v N1.

Kdybyste čemukoliv nerozuměli, rád si s vámi domluvím konzultaci. Ozvěte se mi prosím na adresu mares+ads@kam.mff.cuni.cz.

Přednášky 20.3., 27.3., 1.5., 8.5. odpadají. Místo toho se bude konat 17.3. a 28.4. náhradní přednáška od 17:20 v N1. Náhradní přednášky budu nahrávat.

Co se přednášelo

datum téma video
20. 2. Pokus o definici algoritmu. Výpočetní model RAM: paměť, aritmetické a řídicí instrukce. Čas a prostor konkrétního výpočtu (různé varianty: jednotková cena, logaritmická cena, omezený rozsah čísel), časová a prostorová složitost algoritmu. Programování na RAMu a počítání složitosti: příklad s bublinkovým tříděním. Připomenutí asymptotické notace (O, Ω, Θ). Pokud vám nefungují videa, vypněte si AdBlock. Jedno z jeho pravidel zakazuje všechna URL s podřetězcem /ads1/ :D video
27. 2. Prohledávání grafu do hloubky (DFS). Klasifikace hran v DFS (stromové, zpětné, dopředné, příčné). Hledání mostů. video
6. 3. Aplikace DFS: Detekce cyklů a topologické uspořádání. Algoritmy pro acyklické grafy (počet cest). Komponenty silné souvislosti. video
13. 3. Nejkratší cesty v ohodnocených grafech: trojúhelníková nerovnost pro vzdálenosti, nejkratší cesta versus nejkratší sled, problémy se zápornými cykly. Odvození Dijkstrova algoritmu z BFS pomocí podrozdělování hran a „budíků“. Dijkstrův algoritmus, implementace pomocí haldy (binární a zmínka o ostatních). video
17. 3.
17:20		 Nejkratší cesty: Obecný relaxační algoritmus, důkaz korektnosti Dijkstrova algoritmu pro obecné délky hran, Bellmanův-Fordův algoritmus. Floydův-Warshallův algoritmus pro výpočet matice vzdáleností v grafu. video
20. 3. Přednáška odpadá.
27. 3. Přednáška odpadá.
3. 4. Problém minimální kostry: Jarníkův a Borůvkův algoritmus, lemma o řezech. Jednoznačnost minimální kostry a její určenost uspořádáním hran. Kruskalův algoritmus, udržování komponent souvislosti a Union-Find problem. video
10. 4. Datové struktury: obecný úvod, problém reprezentace slovníku a množiny. Binární vyhledávací stromy a operace s nimi. Dokonale vyvážené stromy. Dolní odhad složitosti operací. Hloubkově vyvážené (AVL) stromy: definice a důkaz logaritmické hloubky. video
17. 4. Plán: AVL stromy: rotace, vyvažování při Insertu a Deletu. (a,b)-stromy: definice, odhad hloubky.

Cvičení

Existuje dvě české paralelky přednášky, ale budeme je udržovat synchronní. Můžete si tedy vybrat libovolné cvičení.

Literatura

Ostatní zajímavé knihy:

Sbírky příkladů:

Různé:

Stránku spravuje Martin Mareš