Přednáška z Algoritmů a datových struktur I v LS 21/22 (č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 21/22 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. Druhou paralelku vede Jan Hric.

Mezi 19. a 27. zářím mohu ještě vypsat jednu zkoušku (ale mezi 21. a 23. nejsem dostupný), v případě zájmu se mi ozvěte emailem.

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 po přednášce (vhodný čas je třeba ve čtvrtek v 10:00, ale můžeme se domluvit i jinak). Můžete mě též najít v kanceláři S323 v budově na Malé Straně (v chodbě KAM/IUUK ve 3. patře, zhruba 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.
17. 2. Úvodní informace k předmětu a příklad různých způsobů hledání nejdelší rostoucí podposloupnosti [Pruv 12.2]; představení výpočetního modelu RAM [Pruv 2.5]. Slajdy a záznam.
24. 2. Časová a paměťová složitost na RAMu, O-notace (O, Ω, Θ, o, ω; viz slajd 8 z 1. prezentace) [Pruv 2.4-2.5]. Grafové algoritmy: opakování reprezentace grafu [Pruv 5.3], prohledávání do hloubky (DFS) v neorientovaných grafech (DFS strom, klasifikace hran) [Pruv 5.6], aplikace na hledání mostů (bude dokončeno příště) [Pruv 5.7]. Záznam (prvních cca 6 min. opakování z minula)
3. 3. Dokončení 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: detekce cyklů, topologické uspořádání a počítání cest [Pruv 5.8], silná a slabá souvislost orientovaných grafů a hledání komponent silné souvislosti (zatím jen nástin kvadratického algoritmu, lineární algoritmus bude příště) [Pruv 5.9]. Pomocné slajdy. Záznam.
10. 3. Dokončení hledání komponent silné souvisloti (algoritmus Kosaraju-Sharir) [Pruv 5.9]. Nejkratší cesty v grafech s délkami hran: vlastnosti vzdáleností (trojúhelníková nerovnost), problémy se zápornými cykly, opakování hledání nejkratších cest z počátečního vrcholu na neohodnocených grafech pomocí BFS, odvození Dijkstrova algoritmu z BFS pomocí "budíků", rozbor časové složitosti Dijkstrova algoritmu pomocí různých typů hald: binární, d-regulární, Fibonacciho (bez vysvětlení) [Pruv 6.1 a 6.2]. Pomocné slajdy. Záznam.
17. 3. Nejkratší cesty [Pruv 6.3]: Relaxační algoritmy (zobecnění Dijkstrova algoritmu) a jejich analýza. Důkaz správnosti Dijkstrova algoritmu a Bellmanův-Fordův algoritmus pro grafy se zápornými hranami. Floydův-Warshallův algoritmus pro výpočet matice vzdáleností [Pruv 6.4]. Pomocné slajdy (8-9). Záznam.
24. 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 (10-13) Záznam.
31. 3. Datové struktury: úvodní obecné informace [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. Záznam.
7. 4. Stromové datové struktury: vyvažování AVL stromů rotacemi pro vkládání i mazání [Pruv 8.2]. Více klíčů ve vrcholech: (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.
14. 4. Červeno-černé stromy ve variantě "left-leaning" (probrána definice, bijekce z (2,4)-stromů a vkládání, vynechali jsme mazání) [Pruv 8.4]. Další stromové datové struktury: 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í a amortizovaná složitost vkládání [Pruv 11.3]. Pomocné slajdy. Záznam.
21. 4. Hešování [Pruv 11.3-11.5]: souvislost hešování a narozeninového paradoxu, otevřená adresace (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í), praktické hešovací funkce (příklady z učebnice + pro zajímavost zmíněn MurmurHash), univerzální hešování (1-univerzalita skalárního součinu, nástin důkazu pro lineární kongrenci). Pomocné slajdy. Záznam.
28. 4. 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]. Informace o zkoušce. Pomocné slajdy. Záznam.
5. 5. Strassenův algoritmus pro násobení matic [Pruv 10.5]. Dynamické programování: Fibonacciho čísla [Pruv 12.1], opakování nejdelší rostoucí podposloupnosti [Pruv 12.2], editační vzdálenost [Pruv 12.3], optimální binární vyhledávací strom (zatím jen definice a náznak algoritmu) [Pruv 12.4]. Pomocné slajdy. Záznam.
12. 5. Dynamické programování pro optimální BVS [Pruv 12.4]. QuickSelect a QuickSort: nejlepší a nejhorší případy, skoromediány [Pruv 10.6-10.7], náhodná volba pivota (pravděpodobnostní analýza) [Pruv 11.2], výběr k-tého nejmenšího v lineárním čase deterministicky [Pruv 10.8]. Pomocné slajdy. Záznam.
19. 5. QuickSelect a QuickSort na náhodných vstupech [Pruv 11.2], dolní odhad na binární vyhledávání a třídění porovnávacími algoritmy [Pruv 3.3]. Pomocné slajdy. Záznam první půlky.
Dále host Karel Tesař (ShipMonk) na téma algoritmické problémy v praxi.

Cvičení

Cvičení k této paralelce vedou:

Zkouška

Mezi 19. a 27. zářím mohu ještě vypsat jednu zkoušku (ale mezi 21. a 23. nejsem dostupný), v případě zájmu se mi ozvěte emailem.

Zkouška bude ústní s písemnou přípravou a to jak z teorie z přednášky (dvě otázky na 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 neefektivně. 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.

Termíny jsou vypisovány v SISu, zatím jsou vypsány termíny do konce června (v týdnech od 13.6 a 20.6. termíny nebudou, neboť budu pryč na konferencích). V září vypíši pár termínů dle zájmu. V červenci a srpnu mohu vypsat 1-2 termíny (v týdnu od 18.7. nebo v druhé půli srpna), v případě zájmu se mi ozvěte emailem. 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).

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ší výsledky).

Zkouškové okruhy a zadané úlohy na minulých zkouškách:

16. 5.
  • Dáno městečko ve tvaru stromu (ulice odpovídají hranám a křižovatky vrcholům). Chceme na křižovatky umístit strážníky, aby každá ulice měla strážníka alespoň na jednom konci. Každá křižovatka má danou cenu, za kterou na ní lze umístit strážníka. Cílem je najít nejlevnější rozmístění strážníků.
  • Je dán text rozdělený na slova. Spočítejte počet výskytů každého slova a poté slova v textu vypište v pořadí dle četnosti.
20. 5.
  • Barvení rovinného grafu 6 barvami.
  • Navrhněte datovou strukturu, která si bude pamatovat posloupnost 2n levých a pravých závorek a bude umět zpracovávat následující operace: (1) zjištění, jestli je posloupnost dobře uzávorkovaná, (2) otočení závorky na pozici i. Posloupnost závorek je dobře uzávorkovaná, pokud se levé a pravé závorky dají spárovat (perfektním párováním) tak, že dva páry závorek se buď neprotínají, tedy ...(...)...(...)..., nebo je jeden pár obsažen v druhém, tedy ...(...(...)...).... Např. posloupnost (()())(()) je dobře uzávorkovaná, ale (()()))(() není.
24. 5.
  • Mějme plán bludiště s hrdinou a pokladem a cílem je najít nejkratší cestu hrdiny k pokladu. K tomu se navíc v bludišti vyskytují dveře a klíče tří barev, přičemž k otevření dveří potřebuje hrdina nejprve sebrat klíč stejné barvy.
  • Dána (nesetříděná) posloupnost délky n a číslo k < n. Cílem je najít maximum z mediánů intervalů délky k.
25. 5.
  • Počítání inverzí v posloupnosti.
  • Sloučení dvou BVS do jednoho dokonale vyváženého BVS.
26. 5. (dopo)
  • Dány dvě posloupnosti. Najděte nejkratší společnou nadposloupnost.
  • Vstupem jen množina d-dimenzionálních vektorů. Zjistěte, jestli se v této množině vyskytují dva vektory, které se sečtou na nulový vektor (tedy jsou navzájem opačné).
26. 5. (odpo)
  • Dána posloupnost celých čísel. Najděte v ní nejdelší úsek, jehož součet je dělitelný 17.
  • Dán slovník, tedy množina slov (nad malou abecedou, např. a-z). Cílem je navrhnout datovou strukturu, která bude umět pro zadané slovo nalézt všechny jeho přesmyčky ve slovníku.
1. 6. (dopo)
  • V orientovaném grafu s délkami hran najděte nejkratší orientovaný 4-cyklus (tedy se čtyřmi hranami).
  • Navrhněte datovou strukturu pro reprezentaci slovníku (klíč, hodnota), kde klíče i hodnoty jsou číselné, tak abychom mohli přidávat a mazat tyto dvojice a efektivně zodpovídat dotazy na sumu hodnot pro klíče ze zadaného intervalu. Bonus: operace intervalový update, tedy přičtení Delta k hodnotám všech klíčů ležících v zadaném intervalu.
1. 6. (odpo)
  • V zadaném orientovaném grafu s šířkami hran najděte nejširší cestu mezi zadanými vrcholy, tedy cestu, na které je minimální šířka nejvyšší možná.
  • Setřiďte posloupnost, o které víte, že pozice každého prvku se liší maximálně o k od jeho pozice v setříděné posloupnosti.
2. 6. (dopo)
  • Vstupem je souvislý neorientovaný graf s hranami ohodnocenými čísly {1, ..., k} pro malé k. Najděte minimální kostru.
  • Dán binární řetězec (posloupnost jedniček a nul). Najděte co nejdelší souvislý úsek, ve kterém se nachází stejně jedniček jako nul.
2. 6. (odpo)
  • Mějme n lamp a n vypínačů. Každé světlo je ovládáno právě jedním vypínačem a opačně. Chceme zjistit přiřazení světel vypínačům pomocí co nejmenšího počtu následujících operací: zapni vypínač, vypni vypínač, zjisti, jestli dané světlo svítí.
  • Dán strom s nezápornými délkami hran. Cílem je najít nejdelší cestu ve stromě.
8. 6. (dopo)
  • Dáno bludiště (čtvercová mapa se zdmi a volnžmi políčky), poloha hrdiny a poloha východu z bludiště. Hrdina má krumpáč, kterým zvládne prokopat zeď, přičemž toto prokopání trvá L krát déle než projít volné políčko. Najděte pro hrdinu nejkratší cestu ven.
  • Dána posloupnost. Chceme datovou strukturu, která bude umět zpracovávat následující operace: (i) pro zadaný úsek (interval) posloupnosti zjistit, jestli je na něm posloupnost rostoucí, a (ii) pro zadaný úsek (interval) a číslo Delta přičíst ke každému prvku v úseku Delta (tedy intervalový update).
8. 6. (odpo)
  • Hledání artikulací v grafu.
  • Problém 3SUM: v zadané posloupnosti najít trojici čísel, která se sečte na 0.
9. 6. (dopo)
  • Dán graf, v němž má každá hrana přiřazená pravděpodobnost. Najděte mezi zadanými dvěma vrcholy nejpravděpodobnější cestu, tedy cestu, na které je součin pravděpodobností jejích hran co největší.
  • Pro daný slovník navrhněte datovou strukturu, která pro zadané slovo vrátí nejlepší rým (tedy slovo ze slovníku s nejdelším společným suffixem).
9. 6. (odpo)
  • Pro zadaný graf zjistěte, jestli je 7-degenerovaný (graf je d-degenerovaný, pokud můžeme vrcholy seřadit na přímku tak, že každého vrcholu vede maximálně 7 hran doprava).
  • Stavba treapu: dány seřazené klíče, z nichž každý má přiřazenu prioritu (priority i klíče jsou různé). Postavte z klíčů BVS takový, že v kořeni je klíč s maximální prioritou a oba podstromy kořene jsou také treapy.
27. 6.
  • Pro zadaný orientovaný graf s vyznačenými vrcholy rozhodněte, jestli existuje cyklus obsahující vyznačený vrchol.
  • Datová struktura pro reprezentaci množiny čísel umožňující přidávání, mazání a hledání k-tého nejmenšího.
28. 6.
  • Pro zadaný graf se sudými stupni najděte Eulerovský tah.
  • Dán slovník (množina slov) a text bez mezer. Cílem je rozdělit text na co nejméně slov ze slovníku.
15. 8.
  • Pro zadaný orientovaný graf s kladně ohodnocenými hranami a dva dané vrcholy s a t nalezněte hrany, které leží na všech nejkratších cestách mezi s a t.
  • Dáno k setříděnlých posloupností o celkové délce n. Jak z nich vytvořit jednu setříděnou posloupnost délky n?
15. 9.
  • N týmů sehrálo zápasy každý s každým (remíza nikdy nenastala). V paměti máme uloženou tabulku výsledků, tedy matici A, kde A_ij je 1, pokud tým i porazil tým j, nebo -1, pokud tým i prohrál s týmem j, nebo 0 pokud i = j. Cílem je zjistit, jestli existuje tým, který porazil všechny ostatní týmy v lepším než kvadratickém čase.
  • Pro danou množinu matic o velikosti k krát k vytvořte datovou strukturu, která bude umět efektivně operace contains(A) (zjistí, jestli matice A je v množině) a add(A) (přidá matici A do množiny).

Literatura a zdroje

Knihy v angličtině: