Příklady 1, 2, 6, 5, 4 z pdf.
NP-těžkost. Převody loupežníků na problém batohu a naopak, převod nezávislé množiny na kliku a naopak. 12. série domácích úkolů zadána: pdf.
11. série domácích úkolů zadána.
4. písemka NP-těžkost, NP-úplnost, převody problémů a převod rozhodovací verzi na hledání řešení (Turingova redukce). pdf.
10. série domácích úkolů zadána.
Dodělání FFT, odvození inverzní FFT, násobení polynomů pomocí FFT. Příklady jsou stejné jako minule, ale je nové zadání domácího úkolu pdf.
Začátek P, NP, převodů. Nástin toho, co budeme dělat.
9. série domácích úkolů zadána. Fourierova transformace - motivace řešení rovnic vedení tepla a vztah se spojitou verzí, vztah s ortonormálními bázemi, vztah s Fourierovými řadami z analýzy.
Reklama na mnohá použití -- zpracování zvuku, obrazu, radary, sonary, magnetická rezonance... Zmíněn videomikroskop podívejte se na stránku autorů s dostupnými články a videi nebo přímo na video (youtube, délka 2 minuty) (je to krásná aplikace jednak filtrů, které jsou umožnéně právě vlastnostmi Fourierovy transformace jednotlivých pixelů v čase a druhak Laplaceovy pyramidy (technika pro zpracování obrazu)). Pokud si to chcete vyzkoušet, tak na github je spousta implementací.
Probrána rychlá (diskrétní) Fourierova transformace Příklady 1, 2, 3 z pdf. Řešení příkladu 3.
Třetí písemka a zadána 8. série domácích úkolů (už je obodovaná). Geometrické algoritmy, úvod a základní myšlenky hledání konvexního obalu množiny bodů v rovině. Příklady 3, 4, 5 a začátek příkladu 6 z pdf.
Druhá písemka a zadána 7. série domácích úkolů. Obvody, složitost a procvičování. Příklady 1, 3 z pdf.
6. série domácích úkolů zadána. Motivace studia obvodů. Začátek obvodů, rozdíly mezi obvody a formulemi. Překlad obvodu na formuli -- pozorován nárůst velikosti. Příklady 4, 5, 6 z pdf.
5. série domácích úkolů zadána. Podrobný rozbor Dinitzova algoritmu. Příklady 2 a 3 z pdf.
4. série domácích úkolů zadána. První písemka napsána. Poslední procvičování vyhledávacích algoritmů. Začátek toků v sítích. Příklady 1 až 8 z pdf.
3. série domácích úkolů zadána. Další procvičování vyhledávacích algoritmů. Příklady 1, 2, 3, 4 z pdf.
2. série domácích úkolů zadána. Algoritmus Knuth-Morris-Pratt, jeho časová složitost s využitím amortizace, konstrukce automatu a použití. Příklady 1, 2, 3, 4 z pdf.
1. série domácích úkolů zadána. Opakování zimního semestru, motivační přemýšlení před přednáškou, atd. příklady 1-4 viz: pdf.
Výsledky zveřejňuji jen pod přezdívkou. Pokud ji nemám, nezveřejňuji.
Alespoň polovina bodů z občasných písemek a zároveň získání alespoň dvou třetin celkového počtu bodů. Další body se dají získat za řešení bonusových domácích úkolů (pokud nějaké budou), popřípadě za netriviální aktivitu na cvičení.
Písemky jsou na látku z přednášek, tj. znalosti definic a základní přehled o probraných algoritmech.
V dobře odůvodněných případech se dají písemky nahradit na předem domluvené konzultaci.
Úkoly se zadávají na každém cvičení a jsou bodovány plným počtem bodů při odevzdávání v prvním týdnu od zadání, druhý týden se body zmenšují na tři čtvrtiny a po zbytek semestru (po třetím týdnu od zadání) jsou za polovinu.