Kurz datových struktur a algoritmů

Lekce 1 • Hašovací tabulky a základy hašování

Představuje ukládání klíč-hodnota pomocí hašovacích funkcí a polí přihrádek. Připravuje studenty na řešení kolizí a analýzu výkonu v průměrném případě.

Lekce 2 • Pole a dynamická pole

Představuje souvislé ukládání do paměti a přístup založený na indexech. Propojuje statická pole se strategiemi dynamické změny velikosti používanými v reálných implementacích.

Lekce 3 • Spojové seznamy a řetězce ukazatelů

Seznamuje s ukládáním založeným na uzlech s využitím ukazatelů nebo referencí. Porovnává spojové seznamy s poli, aby objasnil kompromisy při vkládání a procházení.

Lekce 4 • Paměť, proměnné a datové typy

Probírá, jak jsou data uložena v paměti a jak se liší primitivní typy. Vytváří mentální model potřebný pro veškerou následnou analýzu struktur.

Lekce 1 • Techniky empirického benchmarkingu

Propojuje teoretickou analýzu s měřenými experimenty běhu. Studenti navrhují kontrolované benchmarky k ověření nebo zpochybnění teoretických předpovědí.

Lekce 2 • Prostorová složitost a kompromisy

Analyzuje využití pomocného prostoru spolu s časovými náklady. Zdůrazňuje klasické časoprostorové kompromisy, které řídí praktický výběr algoritmu.

Lekce 3 • Rekurentní vztahy

Představuje rekurence jako nástroj pro analýzu rekurzivních algoritmů. Probírá Master Theorem a substituční metody pro jejich řešení.

Lekce 4 • Big-O, Big-Theta a Big-Omega

Definuje asymptotické notace a jejich matematický význam. Poskytuje slovník používaný v celém kurzu pro porovnávání výkonu algoritmů.

Lekce 1 • Elementární porovnávací třídění

Probírá bublinkové třídění, třídění výběrem a vkládáním s úplnou analýzou složitosti. Vytváří základní intuici před zavedením efektivnějších přístupů.

Lekce 2 • Třídění rozděl a panuj

Učí merge sort a quicksort pomocí rekurzivního rozkladu. Propojuje analýzu rekurzí z kapitoly 2 se skutečným výkonem třídění.

Lekce 3 • Výběr třídicího algoritmu

Syntetizuje veškeré znalosti o třídění do rozhodovacího rámce. Studenti přiřazují volbu algoritmu k velikosti vstupu, distribuci dat a paměťovým omezením.

Lekce 4 • Třídicí algoritmy s lineárním časem

Představuje counting sort, radix sort a bucket sort jako neporovnávací metody. Objasňuje podmínky, za kterých je dosažitelný lineární čas.

Lekce 1 • Memoizace a DP shora dolů

Rozšiřuje rekurzi o ukládání výsledků do mezipaměti pro eliminaci redundantních výpočtů. Slouží jako most k následující kapitole o plném dynamickém programování.

Lekce 2 • Lineární a binární vyhledávání

Porovnává sekvenční vyhledávání a vyhledávání založené na dělení na seřazených a neseřazených datech. Stanovuje předpoklady a záruky složitosti každého přístupu.

Lekce 3 • Strategie rozděl a panuj

Formalizuje paradigma rozděl-panuj-sluč nad rámec třídění. Studenti jej aplikují na problémy, jako je maximální podpole a nejbližší dvojice bodů.

Lekce 4 • Techniky backtrackingu

Představuje systematické prohledávání s prořezáváním pomocí backtrackingu. Propojuje rekurzivní stromy volání s problémy splňování omezení a kombinatorickými problémy.

Lekce 1 • Základy binárních stromů

Definuje terminologii stromů, vztahy mezi uzly a strukturální vlastnosti. Zakládá všechny následující stromové algoritmy na společném slovníku a mentálním modelu.

Lekce 2 • Červeno-černé stromy a B-stromy

Probírá pravidla obarvování červeno-černých stromů a strukturu vícecestných B-stromů. Propojuje je s případy použití v databázovém indexování a souborových systémech.

Lekce 3 • AVL stromy a rotace

Představuje výškově vyvážené AVL stromy a čtyři případy rotací. Studenti implementují samovyvažování pro zaručení operací O(log n).

Lekce 4 • Algoritmy procházení stromů

Probírá inorder, preorder, postorder a procházení po úrovních. Propojuje volbu procházení se specifickými požadavky na výstup a navazujícími algoritmy.

Lekce 1 • Prohledávání do hloubky (DFS)

Implementuje DFS rekurzivně a iterativně s časy objevení a dokončení. Propojuje DFS s detekcí cyklů, topologickým tříděním a komponentami souvislosti.

Lekce 2 • Topologické třídění

Odvozuje topologické uspořádání z časů dokončení DFS a Kahnova algoritmu. Aplikuje uspořádání na problémy řešení závislostí a plánování úloh.

Lekce 3 • Terminologie a reprezentace grafů

Definuje vrcholy, hrany, orientované vs. neorientované a vážené grafy. Porovnává reprezentace maticí sousednosti a seznamem sousednosti z hlediska prostoru a nákladů na přístup.

Lekce 4 • Prohledávání do šířky (BFS)

Implementuje BFS pomocí fronty a analyzuje jeho složitost O(V+E). Aplikuje BFS na hledání nejkratší cesty v nevážených grafech.

Lekce 1 • Minimální kostry: Kruskal

Vytváří MST hladovým přidáváním hran s minimální váhou pomocí Union-Find. Analyzuje správnost pomocí vlastnosti řezu a vlastnosti cyklu MST.

Lekce 2 • Dijkstrův algoritmus nejkratší cesty

Implementuje Dijkstru pomocí prioritní fronty s min-heap se složitostí O((V+E) log V). Probírá důkaz správnosti pomocí invariantu hladové relaxace.

Lekce 3 • Nejkratší cesty mezi všemi dvojicemi

Řeší nejkratší cesty mezi každou dvojicí vrcholů pomocí Floyda-Warshalla. Analyzuje formulaci dynamického programování O(V³) a rekonstrukci cesty.

Lekce 4 • Minimální kostry: Prim

Rozrůstá MST z počátečního vrcholu pomocí prioritní fronty v Primově algoritmu. Porovnává Prima s Kruskalem podle hustoty grafu a složitosti implementace.

Lekce 1 • Klasické 1D DP problémy

Řeší Fibonacciho, lezení po schodech a výměnu mincí pomocí 1D DP tabulek. Buduje intuici pro vyplňování tabulek před přechodem k 2D formulacím.

Lekce 2 • DP na stromech a grafech

Aplikuje DP na stromové struktury a DAG pro pokročilé optimalizační problémy. Probírá stromové DP pro průměr, nezávislé množiny a DP na cestách v DAG.

Lekce 3 • Problémy batohu a podmnožin

Řeší 0/1 batoh, neomezený batoh a součet podmnožiny pomocí DP tabulek. Propojuje je s alokací zdrojů a rozhodovacími problémy proveditelnosti.

Lekce 4 • Klasické 2D DP problémy

Rozšiřuje DP na dvourozměrné tabulky pro problémy s řetězci a mřížkami. Probírá editační vzdálenost, LCS a počítání cest v mřížce s úplnými odvozeními rekurencí.

Lekce 5 • Prostorová optimalizace v DP

Snižuje prostor DP tabulky z O(n²) na O(n) nebo O(1) pomocí klouzavých polí. Aplikuje prostorovou optimalizaci na batoh, LCS a editační vzdálenost.