Algoritmy a datové struktury 1

Přednáška z Algoritmů a datových struktur 1 [NTIN060] se koná v LS 2022/2023 v pondělky od 10:40 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
13. 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
20. 2. Přednáška se nekoná, místo toho bude dvojpřednáška z Programování 2. Naopak 6. 3. budou dvě přednášky z ADS1.
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.
9:00		 Aplikace DFS: Detekce cyklů a topologické uspořádání. Algoritmy pro acyklické grafy (počet cest, plánování činností). Rozklad na komponenty silné souvislosti. video
6. 3.
10:40		 Dokončení silné souvislosti. 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. video
13. 3. Nejkratší cesty: haldy pro Dijkstrův algoritmus (binární a d-regulární). Princip relaxace a důkaz korektnosti Dijkstrova algoritmu. Bellmanův-Fordův algoritmus. Omlouvám se za nekvalitní zvuk v nahrávce, zlobil mikrofon. video
20. 3. 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
27. 3. 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. Hloubkově vyvážené (AVL) stromy: definice a důkaz logaritmické hloubky, nástin vyvažování pomocí rotací. video
3. 4.
9:00		 AVL stromy: vyvažování při Insertu a Deletu. (a,b)-stromy: definice, odhad hloubky. video
3. 4.
10:40		 (a,b)-stromy: Insert a Delete, nastavení parametrů. Zmínka o červeno-černých stromech. Reprezentace řetězců pomocí písmenkových stromů (trie), použití pro čísla. Hešování: přihrádky s řetězci prvků, volba hešovací funkce, c-univerzální systémy funkcí a jejich použití. Přečtěte si v Průvodci: Konstrukce 1-univerzálního systému pomocí skalárního součinu (oddíl 11.5). video
10. 4. Přednáška se nekoná: Ēostre, Paasfees, Великден, Ülestõusmispühad, Πάσχα, Páskar, 復活祭, Pace.
17. 4. Přednáška se nekoná, místo toho bude dvojpřednáška z Programování 2.
24. 4. Ještě k hešování: dynamické rozšiřování tabulky a jeho amortizace. Metoda Rozděl a panuj: třídění sléváním (Mergesort), násobení n-ciferných čísel v čase O(nlog23), 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: 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). video
22. 5. Dynamické programování: Fibonacciho čísla, nejdelší rostoucí podposloupnost, editační vzdálenost, Floydův-Warshallův algoritmus pro výpočet matice vzdáleností v grafu. video

Cvičení

Existuje jen jedna česká paralelka přednášky, můžete si tedy vybrat libovolné cvičení.

Studentům kombinovaného studia doporučuji vybrat si libovolného cvičícího a domluvit se s ním na získání zápočtu za domácí úkoly. Účast na cvičení není nutná, ale hodí se alespoň občas se tam stavit, abyste měli přehled, co se dělá. Za mnou samozřejmě můžete přijít na konzultaci, domluvte se e-mailem.

Zkoušky

Předtermín se koná 22. 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š