kralka (AT) iuuk (atd.) Stránky Karla Krále
slivova (AT) iuuk (atd.) Stránky Veroniky Slívové
Zápis cvičení dění na cvičení a zadání domácích úkolů.
Body za domácí úkoly a reporty chyb.
Zde budou postupně přibývat domácí úkoly a příklady probírané na cvičení.
Opakování na zkoušku dle: pdf.
Příklady z pdf a domácí úkoly.
Příště budeme opakovat celý semestr. Odhlasováno bylo:
Příklady z pdf a domácí úkoly.
Verča povídala o NP. Příklady 1-5 z pdf
Příklady 1, 2, 3, 5, 6, 7, 8 z pdf se zadáním a domácím úkolem. Obvody, komparátory, konvexní obal.
Příklady 1-4 z pdf se zadáním a domácími úkoly. Ještě příklad na dynamické programování. Obvody a formule.
Příklady z pdf se zadáním a domácími úkoly. Poslední procházení FFT. Dynamické programování, základní myšlenky. Implementace v Pythonu (a reklama na Haskell). Příklady 1, 2, 3 (znalost ze základního kurzu programování), 4. Příklad 6 byl jen zadán. Pokud někdo vyřeší a sepíše příklad šest, dáme za něj body (tj. je to bonusový domácí úkol).
Příklady z pdf se zadáním a domácími úkoly. DFT na polynomech. Počítání FFT na polynomech a rychlé násobení. Kód FFT, diskuse o knihovnách a rychlosti.
Příklady z pdf se zadáním a domácími úkoly. DFT a algoritmus FFT. Příště budeme pokračovat. Pravděpodobně budeme napřed před přednáškou. Pokud jste cokoliv nepochopili nebo chcete zopakovat, tak neváhejte napsat (s předstihem) a můžeme to na cvičení zopakovat.
Příklady z pdf se zadáním a domácími úkoly. Pozor, část domácích úkolů má deadline jen jeden týden! Opakování komplexních čísel, ještě pár tokových úloh, opakování určování asymptotické složitosti algoritmů.
Opakování algoritmů na hledání toků, aplikace na jiné problémy. Nestihli jsme poslední příklad. První příklad první série můžete odevzdávat až do příštího týdne za plný počet bodů. pdf se zadáním a domácími úkoly.
Zadána třetí sada domácích úkolů. Do 9. listopadu za plný počet bodů!
Prodloužili jsme deadline prvního domácího úkolu z první série do příštího týdne (do 2. 11. za plný počet bodů). Zadali jsme ho totiž nejednoznačně. Chceme analýzu situace, kdy dostaneme na vstupu číslo N a následně dostáváme posloupnost přičtení a odečtení jedničky (například: 68 +1 +1 +1 -1 +1 +1 -1 -1 -1). Nechceme ani řešení, kde se sečtou +- jedničky a až potom se přičtou k zadanému N. Chceme opravdu reprezentovat každý mezivýsledek.
Rabin Karp, kostry a napravení reputace řezového lemmatu. Spousta koster a začátek toků -- Ford Fulkerson. Mimo příkladů 6, 7, pdf se zadáním a domácími úkoly.
Pro zájemce: Analýza union find (inverzní Ackermanova funkce).
Příklad, kde Ford Fulkerson nemusí ani konvergovat (při špatném výběru zlepšujících cest).
Zadána druhá sada domácích úkolů. Do 2. listopadu za plný počet bodů!
KMP dokončení a opakování Aho-Corasick. Příklady 1-6, příklad 7 naivní řešení, opravdové řešení rozmyslete doma. pdf se zadáním a domácími úkoly.
Zadána první sada domácích úkolů. Do 26. října za plný počet bodů! Prodloužen deadline pro první příklad z této série domácích úkolů, za plný počet bodů až do 2. 11.
KMP, lemma zajišťující jeho funkčnost (to se suffixy). Příklady z pdf.
Výsledky zveřejňuji jen pod přezdívkou. Pokud ji nemám, nezveřejňuji.
Získání alespoň 100 bodů za domácí úkoly. Budou vypsány domácí úkoly za aspoň 150 bodů.
Stránka přednášky prof. Kučery
Videa přednášek z MFF. Přihlašujte se loginem (jménem) do sisu. Obsahuje také (neúplnou) přednášku ADSII (jiný link) od Martina Mareše.
Algovize a kniha prof. Kučery.
Přednáška Martina Mareše o dalších grafových algoritmech.
Pro zvídavé studenty: IPS
Záznamy z přednášky Martina Mareše (Datové struktury II). Je zde například analýza Union find.
Pokud chcete procvičit základní matematické dovednosti Matematické dovednosti.
Pokud aspoň trochu rozumíte anglicky, doporučuji MIT OpenCourseWare.
Zjistěte, kde všude se využívají algoritmy, které se zde učíme (budete překvapeni) CS Theory ScackExchange.
Koukněte se, jak vypadá interview například u Google (anglicky). Zejména doporučuji komentář na konci!
Jestli se chcete naučit psát hezky matematiku, zkuste se podívat na LaTeX. Pro kreslení obrázků se bude hodit například program ipe. LaTeX můžete psát i online například na sharelatex. V případě zájmu vytvořím nějaký ukázkový soubor.