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. Dynamické programování: princip, Fibonacciho čísla [Pruv 12.1], editační vzdálenost (opakování + iterativní verze a grafový pohled) [Pruv 12.3], nejdelší rostoucí podposloupnost [Pruv 12.2], optimální binární vyhledávací strom [Pruv 12.4]. Floydův-Warshallův algoritmus pro výpočet matice vzdáleností v grafu [Pruv 6.4] (jen stručně). Pomocné slajdy Záznam.
23. 5. 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]. QuickSelect a QuickSort na náhodných vstupech [Pruv 11.2] (jen stručně). Dolní odhad třídění deterministickými porovnávacími algoritmy [Pruv 3.3]. Pomocné slajdy Záznam.

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í. Nemusíte sepisovat detaily (např. detailní pseudokódy), jde mi o to, jestli rozumíte tomu, jak dané algoritmy a datové struktury fungují, jak ukázat jejich správnost a časovou složitost. 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 jsou vypsány v SISu. V září mohu vypsat pár termínů – nejlepší bude, když se mi předem ozvete. 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).

Zkouškové okruhy.

Brzy se zde objeví okruhů. Zadané úlohy na minulých zkouškách:

17. 5.
  • Hledání nejrychlejšího spojení v železniční síti s daným jízdním řádem.
  • Datová struktura nad posloupností, která umí zpracovávat změny (popř. i intervalové updaty) a pro zadaný interval umí rychle zjistit, jestli je na něm aktuální posloupnost rostoucí.
22. 5.
  • 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é).
  • Mějme matici A celých čísel, která roste v řádcích i sloupcích. Existují v ní indexy i,j takové, že A_i,j je rovno i+j?
29. 5. (dopo)
  • 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.
  • Hledání artikulací v grafu (nebo alespoň mostů).
29. 5. (odpo)
  • 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án strom s vrcholy ohodnocenými váhami. Cílem je najít nezávislou množinu největší váhy.
30. 5.
  • Dány dvě posloupnosti. Najděte nejkratší společnou nadposloupnost.
  • Stavba treapu (= tree+heap): 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. Půjde tedy zároveň o BVS dle klíčů a haldu dle priorit.
31. 5.
  • Datová struktura pro dynamický slovník dvojic (klíč, hodnota), která umí efektivně spočíst součet hodnot klíčů v zadaném intervalu (dynamická znamená, že umíme efektivně přidávat a odebírat dvojice)
  • Triangulace konvexního mnohoúhelníku pomocí úhlopříček o co nejmenším součtu délek.
3. 6.
  • Nejpravděpodobnější cesta: Počítačovou síť popíšeme orientovaným grafem, jehož vrcholy odpovídají routerům a hrany linkám mezi nimi. Pro každou linku známe pravděpodobnost toho, že bude funkční. Pravděpodobnost, že bude funkční nějaká cesta, je dána součinem pravděpodobností jejích hran. Jak pro zadané dva routery najít nejpravděpodobnější cestu mezi nimi?
  • Problém 3SUM: v zadané posloupnosti najít trojici čísel, která se sečte na 0.
5. 6.
  • Datová struktura pro reprezentaci množiny čísel umožňující přidávání, mazání a hledání k-tého nejmenšího.
  • Nejlevnější vrcholové pokrytí stromu: 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ů.
6. 6.
  • Dáno bludiště (čtvercová mapa se zdmi a volnými políčky), poloha hrdiny, poloha pokladu a poloha krumpáčů. 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.
  • Dešifrovali jsme tajnou depeši o n znacích, ale chybí v ní mezery. Známe však slovník všech slov, která se v depeši mohou vyskytnout. Najděte algoritmus na rozdělení depeše na co nejméně slov ze slovníku. Jaký parametr slovníku se hodí uvažovat pro analýzu časové složitosti? Můžete předpokládat, že abeceda má konstantní velikost (třeba 26) a že slovník máte načtený v trii (písmenkovém stromě).
12. 6.
  • Počítání inverzí v posloupnosti.
  • Hledání všech hran, které leží na nějaké nejkratší cestě v grafu s nezápornými délkami hran.
14. 6.
  • Dán orientovaný graf. Najděte všechny vrcholy, které se vyskytují na nějakém orientovaném cyklu.
  • ě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í.
19. 6.
  • Zjistěte, jestli je graf k-degenerovaný pro zadané k.
  • Navrhněte datovou strukturu pro posloupnost, která bude umět změnu čísla posloupnosti a zjistit součet na zadaném intervalu.
21. 6.
  • Mějme mapu města ve tvaru orientovaného grafu. Každou hranu ohodnotíme podle toho, jaký nejvyšší kamion po dané ulici může projet. Po cestě tedy projede maximálně tak vysoký náklad, kolik je minimum z ohodnocení jejích hran. Jak pro zadané dva vrcholy najít cestu, po níž projede co nejvyšší náklad?
  • Vyřešte rekurence časové složitosti
    1. T(n) = T(n/5) + T(7n/10) + n
    2. T(n) = T(n/5) + T(4n/5) + n
26. 6.

Literatura a zdroje

Knihy v angličtině: