Algoritmy a datové struktury 1

Přednáška z Algoritmů a datových struktur 1 [NTIN060] se koná v LS 2021/2021 ve čtvrtky od 10:40 (v N1, dá-li PES, jinak online).

Na přednášky používáme Zoom, odkaz jste dostali mailem. Pokud vám chybí, napište mi prosím. Videozáznamy přednášek se budou objevovat zde.

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
4. 3. Úvodní příklad s nejdelší rostoucí podposloupností a přehlídka způsobů, jak ho vyřešit. Pokus o definici algoritmu. Výpočetní model RAM: paměť, aritmetické instrukce. video tabule
11. 3. Výpočetní model RAM. Čas a prostor konkrétního výpočtu (různé varianty: jednotková cena, logaritmická cena, omezený rozsah čísel), časová prostorová paměťová 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, Ω, Θ). Prohledávání grafu do hloubky (DFS). Pokud vám nefungují videa, vypněte si AdBlock. Jedno z jeho pravidel zakazuje všechna URL s podřetězcem /ads1/ :D video tabule
18. 3. Aplikace DFS: Klasifikace hran v DFS (stromové, zpětné, dopředné, příčné). Hledání mostů. Detekce cyklů a topologické uspořádání. Algoritmy pro acyklické grafy (počet cest, plánování činností). Silná souvislost: úvod. video tabule
25. 3. Rozklad na komponenty silné souvislosti. Nejkratší cesty v ohodnocených grafech: trojúhelníková nerovnost pro vzdálenosti (neplatí v grafech se zápornými cykly), nejkratší cesta versus nejkratší sled. Odvození Dijkstrova algoritmu z BFS pomocí podrozdělování hran a „budíků“. video tabule
1. 4. Nejkratší cesty: Dijkstrův algoritmus, implementace pomocí různých hald (binárních a k-regulárních). Princip relaxace a důkaz korektnosti Dijkstrova algoritmu. Bellmanův-Fordův algoritmus. video tabule
8. 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 tabule
15. 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 a dolní odhad složitosti operací. Hloubkově vyvážené (AVL) stromy: definice a důkaz logaritmické hloubky. video tabule
22. 4. Vyvažování AVL stromů při Insertu a Deletu pomocí rotací. (a,b)-stromy: definice. video tabule
29. 4. (a,b)-stromy: odhad hloubky, Insert a Delete, nastavení parametrů. Červeno-černé stromy: definice LLRB stromu, isomorfismus s (2,4)-stromy, operace Insert. video tabule
6. 5. 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, dynamické rozšiřování tabulky a jeho amortizace. Hešování: c-univerzální systémy funkcí, konstrukce 1-univerzálního systému pomocí skalárního součinu. video tabule
13. 5. Hešování: Použití c-univerzálních systémů, otevřená adresace tabulek. Metoda Rozděl a panuj: třídění sléváním (Mergesort). video tabule
20. 5. Metoda 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. video tabule
27. 5. Lineární algoritmus na výběr k-tého nejmenšího prvku (trik s pěticemi). QuickSort: princip, analýza průměrné složitosti, lemma o harmonických číslech. Dynamické programování: Fibonacciho čísla, nejdelší rostoucí podposloupnost. video tabule
3. 6. Dynamické programování: editační vzdálenost, optimální vyhledávací strom, Floydův-Warshallův algoritmus pro výpočet matice vzdáleností v grafu. video tabule

Cvičení

Cvičení k této paralelce vedou:

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á 4. 6. (poslední den semestru).

Zkoušet budu každý týden zkouškového období až do 15. 7. Termíny vypíši i na září. Kdybyste chtěli zkoušku během prázdnin, napište; pokud zrovna budu v Praze, vyzkouším vás.

Termíny jsou vypsány v SISu, zapisujte se, prosím, tam. Existují jak prezenční, tak distanční termíny. Prezenční zkoušení výrazně preferuji, ale pokud bydlíte daleko a je pro vás problém přijet na otočku do Prahy, vyzkouším vás distančně. Pokud se termíny hodně zaplní, vypíši další.

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:

Kdybyste potřebovali vyzkoušet během prázdnin nebo v září, je to možné, dejte mi vědět.

Otázky z minulých zkoušek

Literatura

Ostatní zajímavé knihy:

Sbírky příkladů:

Různé:

Stránku spravuje Martin Mareš