news rss feed
Staré písomky
- 2015-12 ukážka možných úloh na skúške: zadania aj riešenia v jednom
- 2016-01-18 skúšková písomka: zadania, riešenia
- 2016-01-26 skúšková písomka: zadania
- 2017-01-05 skúšková písomka: zadania
- 2017-01-29 skúšková písomka: zadania
Obsah jednotlivých prednášok
Tu sa bude postupne zjavovať stručný popis obsahu jednotlivých prednášok.
Témy uvedené kurzívou nebudú predmetom skúšky.
- 28. 9.: Harmonické čísla.
- Coupon collector.
- Skladanie tehál na seba.
- Analýza vkladania do BST v náhodnom poradí.
- Analýza randomizovaného quicksortu.
- Implementácia treapov (kód tu, ak treba text prežeňte cez gtranslate :)).
- 4. 10.: Game Theory (riadky začínajúce * sú vo Fergusonovej knižke, viď dole linka)
- Rošády v šachu: problém od Tima Krabbé, 1972
- * Úvod do kombinatorických hier. Vyhrávajúce a prehrávajúce pozície.
- * Rekurzívna definícia vyhrávajúcich a prehrávajúcich pozícií, dokazovanie hypotézy o nich.
- Symetria pozície, hra s margarétkou.
- * K-kopový všeobecný NIM a jeho riešenie pomocou bitového xoru.
- * Northcottova hra (biele a čierne figúrky v riadkoch).
- * Sprague-Grundyho čísla ako detailnejšia charakteristika pozície
- * Súčet (symetrických konečných) hier.
- * Sprague-Grundyho veta: "každá pozícia každej symetrickej hry sa 'podobá' na nejakú kôpku NIMu".
- 11. 10.: viac Game Theory
- Hra s margarétkou, všeobecná štartovacia pozícia
- * Hry Rims a Rayles.
- * Misère NIM.
- * Hackenbush, hra s lámaním čokolády a voľné rozprávanie o asymetrických hrách a ich analýze.
- Prisoner's dilemma a stručný úvod do ekonomických hier.
- Príklad dominujúcej stratégie a príklad sedlového bodu v maticovej zero-sum hre.
- Príklad riešenia malej zero-sum maticovej hry (Odd aj Even volí 1 alebo 2, víťaz dostane súčet).
- 18. 10.: Párovania a matice
- Hra "nestúp dvakrát na rovnaké políčko". (Viď analýza úlohy z GCJ 2008.)
- Dláždenie dlaždicami 2x1: párovania, permanent.
- #P a #P-úplné problémy.
- Todova veta o tom ako ťažké je #P-complete
- Počítanie lineárnych rekurencií pomocou násobenia maticou.
- 25. 10.: Viac matíc a kombinatoriky (článok o celej dnešnej prednáške)
- Odhadovanie rýchlosti rastu riešenia rekurencie pomocou vlastných čísiel jej matice.
- Počet pokrytí pomocou dynamického programovania: DP cez stĺpce, DP cez "zlomené profily"
- Rýchlejšie vyhodnocovanie DP pomocou umocňovania matice.
- Počty iných kombinatorických objektov: zakázaná malá podmatica, zakázané podslovo.
- (1. 11. nebolo)
- 8. 11.: DFT: draft poznámok
- Násobenie a interpolácia polynómov.
- Karatsubov algoritmus. (Maticová analógia: Strassen)
- Diskrétna Fourierova transformácia (DFT).
- (15. 11. nebolo)
- 22. 11.: viac DFT
- Inverzné DFT.
- DFT počíta cyklické konvolúcie
- Korelácie a autokorelácie
- Blur pomocou DFT
- Vyhľadávanie najpodobnejšieho výskytu vzorky v texte
- Number-theoretic transform: DFT nad konečným poľom
- 29. 11.: tranzitívne uzávery a najkratšie cesty (Kozen, lectures 5-7)
- reflexívno-tranzitívny uzáver pomocou umocňovania: A^* = (A+I)^(n-1)
- reflexívno-tranzitívny uzáver šikovnejšou rekurziou v čase násobenia matíc
- Kleeneho algebry
- all-pairs najkratšie cesty v čase násobenia matíc
- konverzia NFA na regex
- dolný odhad zložitosti reflexívno-tranzitívneho uzáveru
- 6. 12.: Najkratšie cesty v grafoch v praxi
- prehľadávanie z oboch koncov naraz
- algoritmus A*
- prípustné (admissible) a monotónne (monotone, consistent) heuristiky
- landmarks heuristika a reach
- Algoritmy na stromoch 1: efektívne updaty celých podstromov naraz
- 13. 12.: Algoritmy na stromoch
- Centroid stromu a centroidová dekompozícia: viď figure 2, iné slajdy, ešte iný popis
- Viac centroidovej dekompozície: úloha "kde je najbližší zaujímavý vrchol"
- Najbližší spoločný predok v strome.
- Heavy-light dekompozícia stromu a úlohy o cestách v strome.
- Separátory v grafoch, špeciálne Planar separator theorem
- 20. 12.: Optimalizácie dynamického programovania
- Treewidth a DP na tree dekompozícii
- Hirschbergova finta na O(n) pamäť pri LCS.
- Dynamické programovanie cez všetky podreťazce: Mongoli, pílenie laty, konštrukcia optimálneho BST.
- Unimodálne správanie sa ceny optimálneho riešenia: binárne/ternárne vyhľadávanie.
- Knuthova-Yaovej optimalizácia
Skriptá a oficiálne materiály
Zatiaľ žiadne neexistujú, predmet bude vyučovaný podľa vybraných pasáží zo zahraničných materiálov.
Materiály z iných končín sveta
Odporúčam výbornú knižku od Dextera Kozena: The design and analysis of algorithms. Obzvlášť ak si pri mäsku nepotrpíte na zbytočnú omáčku okolo :) Ak si túto knižku neviete zohnať sami, opýtajte sa.
Ku teórii hier (oboch druhov) odporúčam voľne dostupnú knihu od Toma Fergusona.