Prednášky ADS2, ZS 2017/18, Ut 14:00, S5

Prednasky budou (dle moznosti) synchronizovany s anglickou paralelkou s ohledem na poradi probiranych temat.


1P 3.10.2017
Slajdy 1-6
Uvod, Vyhledavani retezcu, alg. Aho-Corasicková: interpretace

P2 10.10.2017
Slajdy 7-14, cast 15
Aho-Corasicková, strucne alg. Knuth-Morris-Pratt

P3 17.10.2017
Slajdy 15-21
Toky v sitich, teorie max. tok a min. rez, alg. zlepsujici cesty

P4 24.10.2017
Slajdy 21-27
Dinicův alg., Goldbergův alg. - začátek

P5 31.10.2017
Slajdy 27-33
Goldbergův alg.; začátek Hradlové sítě ...

P6 7.11.2017
Slajdy 33-40
Třídící sítě (Mergesort), úvod Sčítačka

P7 14.11.2017
Slajdy 40-44
Hradlová síť pro sčítačku, úvod FFT

P8 21.11.2017
Slajdy 44-50
FT a FFT, bez hradel/butterfly a nerekurzivní verze

P9 28.11.2017
Slajdy 54-57, 45-47(část)
 ! Pridávám do slajdů obrázky, tak se čísla slajdů globálně mění.
Dokončení FFT, Konvexní obal (bez převodu třídění)

P10 5.12.2017
Slajdy 47, 58-62
Dokončení konv. obalu: převod třídění; Úvod NP-úplnost, převoditelnost

P11 12.12.2017
Slajdy 63-68
NP-úplnost, převody (bez zaverecneho povidani)

P12 19.12.2017
Slajdy  68-73
NPÚ závěr: co s tím, převody na SAT.
Aproximacni algoritmy: vrcholové pokrytí

P13 (2.1.2018)

P14 9.1.2018
Slajdy 73-77
Aproximační alg.: Aproximace POC s trojuh. nerovností, 
neaproximovatelnost POC bez trojuh. nerovnosti, 
aproximační schéma pro součet podmnožiny