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. Plán: 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]. Informace o zkoušce.
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: Mělo by být ovšem možné navštěvovat cvičení i druhé české paralelky (budeme se snažit udržovat obě přednášky rozumně synchronní, až na epsilonovou chybu)

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

Knihy v angličtině: