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
Zadania domácich úloh
- DU 1 do 7. 10. 2022
- DU 2 do
25. 10. 20222. 11. 2022 - odovzdávanie cez testovač - DU 3 9. 11. 2022 - odovzdávanie cez testovač
- DU 4
16. 11. 202219. 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. .