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.

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. Rozděl a panuj: Karacubův algoritmus – 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. Na cvičení: QuickSort: princip, analýza průměrné složitosti. video
22. 5. Lineární algoritmus na výběr k-tého nejmenšího prvku (trik s pěticemi). Dynamické programování: Fibonacciho čísla, nejdelší rostoucí podposloupnost, editační vzdálenost. video

Cvičení

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

Zkoušky

Předtermín se koná 23. 5. (poslední den semestru). Pozor, zkouším i látku z poslední přednášky; měla by nicméně být pokryta doporučenou literaturou.

Zkoušet budu každý týden zkouškového období. Termíny jsou vypsány v SISu, zapisujte se, prosím, tam. Kdybyste potřebovali vyzkoušet během prázdnin nebo v září, je to možné, dejte mi vědět.

Zkouška bude ústní s písemnou přípravou: Na začátku zadám otázky. Vy si odpovědi rozmyslíte (času bude dost) a sepíšete. Pak si o nich spolu popovídáme a na základě toho dostanete buďto známku, nebo nápovědu k další práci. Cílem je, aby každý vyřešil všechno, a známka se bude odvíjet od toho, jak moc jsem vám musel napovídat :)

Ke zkoušce je potřeba:

Otázky z minulých zkoušek

Literatura

Ostatní zajímavé knihy:

Sbírky příkladů:

Různé:

Stránku spravuje Martin Mareš