Algoritmy a dátové štruktúry

Materiály 2022

Tu budeme postupne uverejňovať zoznam odprednášaných tém a materiály vzniknuvšie a prezentované na jednotlivých prednáškach.

01: Povinná byrokracia na úvod. Stable marriage problem. pythonovský kód prezentovaný na prednáške
02: Zdôvodnenie potreby efektívnych algoritmov. Motivácia ku skúmaniu asymptotickej časovej zložitosti. pythonovský kód prezentovaný na prednáške
03: Definícia asymptotickej časovej zložitosti, O-notácia.
04: Analýzia triedení MergeSort a StoogeSort, Master Theorem.
05: Amortizovaná časová zložitosť. Fronta pomocou dvoch zásobníkov. Neefektívne spôsoby implementácie prioritnej fronty. "Prioritná fronta chudobného muža" pomocou blokov veľkosti sqrt(n).
06: Zásobník, fronta: implementácie pomocou poľa pevnej veľkosti a spájaných zoznamov. Vektor: pole premennej veľkosti.
07: Dôkaz zložitosti push_back pre vektor technikou "Vhadzujem mince do pokladničky"- Obojsmerná fronta (deque). Halda. Algoritmy pre vkladanie do haldy a výber maxima. Implementácia binárnej haldy v poli. Prioritná fronta pomocou haldy.
08: HeapSort. Výroba haldy v lineárnom čase. Binárne vyhľadávanie, dolný odhad Omega(log n), invarianty. Binárne vyhľadávacie stromy (BST). Vkladanie do BST. Výber prvku z BST.
09: Vyvážené stromy - ich rôzne odrody (AVL, 2-3, B-stromy). Rotácie vo vyváženom strome. Iterátory v BST - inkrement/dekrement iterátora, iterátor umožňujúci rýchle vyhladávanie k-teho prvku
10: dátové štruktúry set a map (usporiadaná množina a asociatívna mapa). Dolné odhady: vyhľadávanie v usporiadanom poli je Omega(log n), triedenie porovnávaním je Omega(n log n).
11: CountSort, stabilné triedenie, efektívne triedenie pre špeciálne prípady: RadixSort, BucketSort.
12: Iterovanie cez všetky kombinatorické objekty: podmnožiny, permutácie, podmnožiny fixnej veľkosti. c++ kód vzniknuvší počas prednášky
17: Dynamické programovanie a memoizácia 1: Funkcie v matematickom a informatickom zmysle, Fibonaciho postuponosť a analýza rekurzívneho riešenia, vylepšenie rekurzívneho riešenia memoizáciou, analýza rastu Fibonaciho postupnosti. pythonovský kód vzniknuvší počas prednášky
18: Dynamické programovanie a memoizácia 2: Najväčší súčet nesusediacih prvkov (Optimálne pitie fliaš v bare), počet ciest na mriežke (prechádzky cez ľubovoľné mesto USA), riešenia memoizáciou aj iteratívnym spôsobom dynamického programovania. pythonovský kód vzniknuvší počas prednášky, ľubovoľné mesto USA, iné ľubovoľné mesto USA

Prezentácie z prednášok (priebežne dopĺňané)

Zadania domácich úloh

DU 1 do 7. 10. 2022
DU 2 do ~~25. 10. 2022~~ 2. 11. 2022 - odovzdávanie cez testovač
DU 3 9. 11. 2022 - odovzdávanie cez testovač
DU 4 ~~16. 11. 2022~~19. 11. 2022 - odovzdávanie cez testovač
DU 5 23. 11. 2022 - odovzdávanie cez testovač
DU 6 3. 12. 2022 - odovzdávanie cez testovač
DU 7 10. 12. 2022 - odovzdávanie cez testovač
DU 7 17. 12. 2022 - odovzdávanie cez testovač

Prednášky 2020

Nahraté prednášky z tohto semestra nájdete v tomto playliste. Pre poriadok nechávame aj sylabus prednášok, ktorý bol použitý pre tento semeter.

01: Povinná byrokracia na úvod. Stable marriage problem.
02: Zdôvodnenie potreby efektívnych algoritmov. Motivácia ku skúmaniu asymptotickej časovej zložitosti.
03: Definícia asymptotickej časovej zložitostie, O-notácia. Analýza hľadania úseku s daným súčtom v poli kladných čísel.
04: Analýza triedení MergeSort a StoogeSort. Master theorem.
05: Amortizovaná časová zložitosť. Fronta pomocou dvoch zásobníkov. Neefektívne spôsoby implementácie prioritnej fronty. "Prioritná fronta chudobného muža" pomocou blokov veľkosti sqrt(n).
06: Zásobník, fronta: implementácie pomocou poľa pevnej veľkosti a spájaných zoznamov. Vektor: pole premennej veľkosti.
07: Obojsmerná fronta (deque). Vlastnosť haldy. Algoritmy pre vkladanie do haldy a výber maxima. Implementácia binárnej haldy v poli. Výroba haldy v lineárnom čase. Prioritná fronta a triedenie HeapSort.
08: Binárne vyhľadávanie, invarianty, polo-otvorené intervaly. Binárne vyhľadávacie stromy (BST). Vkladanie do BST. Výber prvku z BST. AVL stromy a iné odrody vyvažovaných stromov. Rotácia ako základná štrukturálna zmena BST.
09: Odhad hĺbky vyváženého AVL stromu. Pre-, post- a in-order výpis stromu a ich časová zložitosť. Poľská notácia pre aritmetické výrazy. Iterátory do BST, inkrementovanie iterátora. Vylepšené BST podporujúce efektívne hľadanie k-teho prvku.
10: Dátové štruktúry set a map (usporiadaná množina a usporiadané asociatívne pole). Dolné odhady zložitosti: vyhľadávanie v usporiadanom poli je Omega(log n), triedenie porovnávaním je Omega(n log n).
11: CountSort. Stabilné triedenia. Efektívne triedenia pre špeciálne prípady: RadixSort, BucketSort.
12: Iterovanie cez všetky kombinatorické objekty: podmnožiny, permutácie, podmnožiny fixnej veľkosti.
13: Pažravé algoritmy 1: nákup zlata, pokrytie dediny min. zastávkami, výber najväčšej sady disjunktných prednášok.
14: Pažravé algoritmy 2: voda do vedierok, lexikograficky najmenšie zreťazenie reťazcov, zrýchlenia (maximalizuj plochu pod grafom), scheduling unit-size jobov s deadlineami a pokutami.
15: Kombinácie a variácie pevnej veľkosti. Platenie najmenším počtom mincí.
16: Spojitá a diskrétna verzia problému batoha. Technika meet in the middle.
17: Memoizácia a dynamické programovanie 1: Rozdiely medzi funkciami v matematickom a informatickom zmysle. Fibonacciho čísla a memoizácia rekurzívnej funkcie. Rýchlosť rastu Fibonacciho čísel.
18: Memoizácia a dynamické programovanie 2: Maximálny súčet nesusedných prvkov poľa. Počet ciest po mriežke.
19: Memoizácia a dynamické programovanie 3: Rozdiely medzi memoizáciou a dynamickým programovaním: "hustý" vs. "riedky" priestor stavov, šetrenie pamäťou. Najdlhšia rastúca podpostupnosť. Rekonštrukcia jedného optimálneho riešenia.
20: Memoizácia a dynamické programovanie 4: Platenie najmenej mincami, problém batoha: pseudopolynomiálne algoritmy. Optimálne miesto stretnutia na priamke.
21: Memoizácia a dynamické programovanie 5: Optimálne miesto stretnutia v Manhattane a v rovine. Medián postupnosti, quickselect. Optimálne rozmiestnenie zastávok v dedine. Problém obchodného cestujúceho.
22: Hešovanie 1: Princípy. Kolízie a narodeninový paradox. Riešenie kolízií zreťazením.
23: Hešovanie 2: Porovnávanie veľkých súborov hešovaním modulo náhodné prvočíslo. Univerzálne hešovanie.
24: Generovanie rovnomerne náhodných celých čísel v počítači (rejection sampling). Náhodné (aj nie úplne náhodné) preusporiadanie poľa. Náhodný sampling.
25: Náhodný sampling zo streamu. Bloom filter.

Playlist 2018

V zime 2018 boli prednášky predmetu natáčané, playlist s nimi je dostupný na kanáli FMFI UK.

Skriptá a oficiálne materiály

Skriptá k aktuálnej verzii predmetu postupne vznikajú. V nasledujúcom zozname sú kusy toho, čo existuje:

skriptá: Stabilné manželstvá.
skriptá: Časová zložitosť.
skriptá: Viac časovej zložitosti (zatiaľ len po anglicky).
skriptá: Haldy.
skriptá: Stromy.
skriptá: Rekurzia.
pomôcka: Prehľad dátových štruktúr.
pomôcka: Áno/nie kvíz.
linka: Projekt Kuba Kováča: applet simulujúci rôzne druhy stromových dátových štruktúr. Ak si nie ste istí, ako funguje niektorá dátová štruktúra, pohrajte sa s ňou!

Ukážkové staré písomky

písomka: Zadania ukážkovej písomky.
písomka: Vzorové riešenia ukážkovej písomky.
písomka: Zadania písomky z 21. 12. 2010.
písomka: Vzorové riešenia písomky z 21. 12. 2010.
písomka: Zadania písomky z 7. 1. 2011.
písomka: Vzorové riešenia písomky z 7. 1. 2011.
písomka: Zadania písomky z 13. 1. 2011.
písomka: Vzorové riešenia písomky z 13. 1. 2011.
písomka: Zadania písomky z 21. 12. 2011.
písomka: Vzorové riešenia písomky z 21. 12. 2011.
písomka: Zadania písomky z 13. 1. 2012.
písomka: Vzorové riešenia písomky z 13. 1. 2012.
písomka: Zadania písomky z 18. 1. 2012.
písomka: Vzorové riešenia písomky z 18. 1. 2012.
písomka: Zadania písomky z 19. 12. 2012.
písomka: Vzorové riešenia písomky z 19. 12. 2012.
písomka: Zadania písomky z 7. 1. 2013.
písomka: Vzorové riešenia písomky z 7. 1. 2013.
písomka: Zadania písomky z 11. 1. 2013.
písomka: Vzorové riešenia písomky z 11. 1. 2013.
písomka: Zadania písomky z 20. 12. 2013.
písomka: Vzorové riešenia písomky z 20. 12. 2013.

Materiály z iných končín sveta

Klasickou knihou, ktorá je najčastejšie používaná pri výučbe tohto predmetu vo svete, je tzv. "biely spellbook", tiež nazývaný "CLRS" podľa mien autorov:

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (3rd ed.). MIT Press. ISBN 0-262-03384-4.

Čítaním tejto knihy nič nepokazíte, skôr naopak.

V rámci MIT OpenCourseWare sú k dispozícii výborné videá prednášok, ktoré podľa tejto knihy robili Charles Leiserson a Erik Demaine na MIT.

Možno stojí za pozretie: Aho, Ullman: Foundations of Computer Science, Sedgewick: Algorithms. .

1-INF-220 Algoritmy a dátové štruktúry