Přednáška z Algoritmů a datových struktur I v LS 23/24 (čtvrtek 14:00, N1, kód předmětu NTIN060)
Stránka přednášky Pavla Veselého z Algoritmů a datových struktur I (ADS1), která probíhá v LS 23/24 každý čtvrtek od 14:00 v učebně N1 (pavilon IMPAKT v Tróji). Budeme navazovat na předmět Algoritmizace. Představu o přednášce si můžete udělat z loňské přednášky Martina Mareše nebo mojí předloňské. Druhou paralelku vede Jan Hric.
Pokud máte nějaký dotaz, pište na vesely+ads1 (zavináč) iuuk.mff.cuni.cz, případně se zeptejte po přednášce. Také budu rád, když se během cvičení budete ptát, jakmile vám nebude něco jasné. Chcete-li konzultaci, ozvěte se mi emailem nebo před/po přednášce. Někdy mě můžete též najít v kanceláři S326 v budově na Malé Straně (v chodbě KAM/IUUK ve 3. patře naproti učebně S3), ale je lepší se ozvat předem.
Pokud nemůžete přijít (nemoc, izolace, ...), pusťte si stream, podívejte se na záznam (podaří-li se ho pořídit) nebo si nastudujte příslušnou část skript (viz odkazy na sekce níže).
Co jsme dělali / plán
U každého tématu jsou odkazy na učebnici. Na záznamech je hlavně tabule, slajdy najdete níže.22. 2. | Úvodní informace k předmětu a motivační příklad algoritmického problému: editační vzdálenost a tři způsoby řešení: hrubá síla (enumerace), rekurzivní řešení a zrychlení na čas O(m*n) pomocí kešování výsledků, tedy dynamické programování [Pruv 12.3]. Představení výpočetního modelu RAM [Pruv 2.5], včetně diskuse ceny jednotlivých operací a ukázky přepisu pseudokódu bublinkového třídění do programu pro RAM (viz také simulátor od Radka Huška). Pomocné slajdy (až po slajd 9; na slajdu 9 jsem udělal opravu v definice logaritmické ceny instrukce, konkrétně tam byl logaritmus navíc). Záznam. |
29. 2. | Formální zavedení časové a paměťové složitosti, asymptotická "Óčková" notace (O, Ω, Θ a navíc také o, ω) [Pruv 2.4-2.5] (viz také slajd 10 z minula). Grafové algoritmy: opakování reprezentace grafu a BFS [Pruv 5.2 a 5.3], prohledávání do hloubky (DFS) v neorientovaných grafech (DFS strom, klasifikace hran, souvislost s uzávorkováním) [Pruv 5.6]. Aplikace na hledání mostů [Pruv 5.7] (zatím kombinatorická charakterizace). Záznam. |
7. 3. | Dokončení algoritmu pro hledání mostů. Definice artikulace a lemma se základní vlastností (algoritmus pro artikulace bude na cvičeních) [Pruv 5.7], DFS na orientovaných grafech (klasifikace hran a souvislost s uzávorkováním) a jeho aplikace na detekci cyklů. Algoritmy pro DAGy: topologické uspořádání a počítání cest [Pruv 5.8]. Pomocné slajdy (po slajd č. 3). Záznam. |
14. 3. | Silná a slabá souvislost orientovaných grafů a hledání komponent silné souvislosti (algoritmus Kosaraju-Sharir) [Pruv 5.9]. Nejkratší cesty v grafech s délkami hran: vlastnosti vzdáleností (trojúhelníková nerovnost) a opakování hledání nejkratších cest z počátečního vrcholu na grafech s jednotkovými délkami hran pomocí BFS. Odvození Dijkstrova algoritmu z BFS pomocí "budíků" pro nezáporné celočíselné délky. Časová složitost za použití pole a haldy pro hledání "budíku", který zazvoní nejdříve [Pruv 6.1 a 6.2]. Pomocné slajdy (hlavně slajd 4, slajd 5 o Tarjanově algoritmu pro nedostatek času vynechán, ale je "bonusový"). Záznam. |
21. 3. | Rozbor časové složitosti Dijkstrova algoritmu pomocí různých typů hald: binární, d-regulární, Fibonacciho (Fibonacciho halda bez vysvětlení). Relaxační algoritmy (zobecnění Dijkstrova algoritmu) a jejich analýza [Pruv 6.3]. Nejkratší cesty i se zápornými hranami: Problémy se zápornými cykly. Důkaz správnosti Dijkstrova algoritmu a Bellmanův-Fordův algoritmus pro grafy se zápornými hranami [Pruv 6.3]. Pomocné slajdy (slajdy 6-8). Záznam. |
28. 3. | Minimální kostry a jejich hledání dle pánů Jarníka, Borůvky a Kruskala [Pruv 7.1-7.4]. Důkazy nalezení minimální kostry přes řezové lemma. Implementace Jarníkova algoritmu podobná Dijkstrovu algoritmu. Datové struktury pro Union-Find problém (pole, keře). Pomocné slajdy (slajdy 9-11). Záznam. |
4. 4. | Datové struktury: úvodní obecné informace dle slajdů [Pruv 4.1]. Binární vyhledávací stromy [Pruv 8.1]: základní operace, dokonalá vyváženost a nemožnost jejího udržování (s důkazem). Hloubkově vyvážené (AVL) stromy [Pruv 8.2]: definice, důkaz logaritmické hloubky, vyvažování rotacemi a dvojrotacemi po přidávání prvku (bude doděláno příště). Pomocné slajdy (slajdy 1-2). Záznam. |
11. 4. | Stromové datové struktury: vyvažování AVL stromů rotacemi pro vkládání (zbytek z minula) i mazání [Pruv 8.2]. Více klíčů ve vrcholech, neboli vícecestné vyhledávací stromy, konkrétně (a,b)-stromy (definice, důkaz logaritmické hloubky, údržba po přidání / odebrání klíče) [Pruv 8.3]. Pomocné slajdy. Záznam. |
18. 4. | ZOO DS (datových struktur): Posledních pár poznámek k (a,b)-stromům: slučování vrcholů nepokazí podmínky, co se stane při podtečení kořene, B-stromy, a k čemu se hodí parametr a mnohem větší než 2. Červeno-černé stromy ve variantě "left-leaning" (definice, bijekce s (2,4)-stromy a vkládání, vynechali jsme mazání) [Pruv 8.4]. Další stromové datové struktury (stručně): písmenkové stromy (trie) [Pruv 4.3] a intervalové stromy [Pruv 4.5]. Hešování: hešovací funkce a tabulka, kolize, řešení kolizí spojovými seznamy (řetízky), průměrná a střední hodnota délky řetízku, přehešovávání při velkém zaplnění tabulky (analýza bude příště] [Pruv 11.3]. Pomocné slajdy. Záznam. |
25. 4. | Hešování [Pruv 11.3-11.5]: amortizovaná složitost vkládání při přehešování na dvojnásobnou velikost tabulky [založené na části Pruv 9.1]. Řešení kolizí otevřenou adresací: vkládání a hledání (mazání viz doplněný slajd), implementace lineárním přidáváním a dvojitým hešováním, analýza střední hodnoty počtu navštívených buněk pro neúspěšné hledání (důkaz se zkoušet nebude). Souvislost hešování a narozeninového paradoxu (jen stručně). Praktické hešovací funkce (příklady z učebnice + tabelace + pro zajímavost zmíněn MurmurHash) a univerzální hešování: 1-univerzalita skalárního součinu, lemma o počtu kolizí pro libovolný prvek a náznak důkazu pro lineární kongrenci. Pomocné slajdy (doplněno pár detailů k otevřené adresaci). Záznam. |
2. 5. | Rozděl a panuj: třídění sléváním (Mergesort) [Pruv 10.2], násobení dlouhých čísel Karacubovým algoritmem [Pruv 10.3], Kuchařková věta (Master Theorem) o časové složitosti rekurzivních algoritmů [Pruv 10.4], Strassenův algoritmus pro násobení matic [Pruv 10.5] (jen stručně, viz slajdy). Informace o zkoušce. Pomocné slajdy Záznam. |
9. 5. | Přednáška odpadá |
16. 5. | Plán: Dynamické programování: princip, nejdelší rostoucí podposloupnost [Pruv 12.2], editační vzdálenost (opakování) [Pruv 12.3], optimální binární vyhledávací strom [Pruv 12.4]. Pokud zbyde čas, také Floydův-Warshallův algoritmus pro výpočet matice vzdáleností v grafu [Pruv 6.4]. |
Cvičení
Cvičení k této paralelce vedou:- Matej Lieskovský (dvě cvičení)
- Jonáš Havelka
- Jakub Komárek
- Pavel Veselý
Zkouška
Zkouška bude ústní s písemnou přípravou a to jak z teorie z přednášky (algoritmy, datové struktury a jejich analýzu), tak z algoritmických úloh podobných úlohám řešeným na cvičení (dvě úlohy). Na začátku tedy zadám úlohy a poté budete mít dostatek času (a papíru) na rozmyšlení a sepsání odpovědí. Až budete připraveni (nebo s blížícím se koncem zkoušky) se o teorii i řešení úloh pobavíme, popř. vám dám nějakou nápovědu k řešení (která se ovšem promítne do hodnocení).
Pro úspěšné složení zkoušky bude potřeba znám definice a algoritmy z přednášky a vyřešit alespoň jednu úlohu s nápovědou nebo neoptimálně. Na dvojku je navíc potřeba znát vlastnosti algoritmů a datových struktur z přednášky (např. časovou složitost, popř. jiná tvrzení dokazovaná na přednášce) a vyřešit obě úlohy s nápovědou. Na jedničku je potřeba umět v zásadě vše z přednášky včetně důkazů a umět řešit úlohy téměř samostatně, popř. pouze s malou nápovědou.
Není třeba se učit zpaměti detaily, ale je potřeba znát ideu výpočetního modelu RAM (např. sadu operací), vyvažování AVL stromu po operaci Insert/Delete, Strassenova algoritmu na násobní matic. Není také potřeba se učit zajímavosti na pomocných slajdech (např. jaké jsou nejlepší známé výsledky nebo další varianty různých datových struktur).
Termíny budou vypsány v SISu koncem semestru. Před zkouškou nebude nutné získat zápočet, ale je to silně doporučené (mj. si procvičíte řešení algoritmických úloh).
Literatura a zdroje
- Martin Mareš, Tomáš Valla: Průvodce labyrintem algoritmů (hlavní zdroj, digitální verze volně dostupné) [Pruv] (mělo by stačit první vydání, modulo drobnosti)
- Videozáznamy Martina Mareše z roku 2023 (popř. z roku 2021)
- Programátorské kuchařky KSP (úvodní a méně formální texty o základních algoritmech a datových strukturách)
- Pavel Töpfer: Algoritmy a programovací techniky (pěkná kniha pokrývající základy, ale vše z přednášky v ní nenajdete)
- Animovaný výklad algoritmů v Algovision od prof. Luďka Kučery
- Gnarley trees* – applet demonstrující vyhledávací stromy a jiné datové struktury
- Robert Sedgewick: Left-Leaning Red-Black Trees
- Dasgupta, Papadimitriou, Vazirani: Algorithms
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (2nd Edition), Mc Graw Hill 2001