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. AVL stromy: rotace, vyvažování při Insertu a Deletu. Externí vrcholy, myšlenka vícecestných vyhledávacích stromů. video
24. 4. (a,b)-stromy: definice, odhad hloubky, Insert a Delete, nastavení parametrů. Zmínka o červeno-černých stromech a izomorfismu s (2,4)-stromy. Hešování: přihrádky s řetězci prvků, otevřená adresace. Dynamické rozšiřování tabulky a jeho amortizace. video
28. 4.
17:20		 Hešování: příklady hešovacích funkcí, c-univerzální systémy funkcí a jejich použití. Konstrukce 1-univerzálního systému pomocí skalárního součinu. Metoda Rozděl a panuj: třídění sléváním (Mergesort), obecná technika rozboru rekurzivních algoritmů pomocí stromů rekurze. video
1. 5. Přednáška se nekoná: Státní svátek.
8. 5. Přednáška se nekoná: Státní svátek.
15. 5. Plán: Rozděl a panuj: násobení n-ciferných čísel v čase O(nlog23), věta o časové složitosti rekurzivních algoritmů (kuchařka alias Master theorem). Strassenovo násobení matic (vzorce). Hledání k-tého nejmenšího prvku a různé způsoby volby pivota. Randomizace a průměrná časová složitost. QuickSort: princip, analýza průměrné složitosti. Lineární algoritmus na výběr k-tého nejmenšího prvku (trik s pěticemi).
22. 5. Plán: Dynamické programování: Fibonacciho čísla, nejdelší rostoucí podposloupnost, editační vzdálenost,

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š