Prednášky ADS2, ZS 2020/21, Po 15:40, Zoom (původně S3)

P0 28.9.2020 x

P1 5.10.2020
Slajdy 1-8 zač.
Uvod, Vyhledavani retezcu, alg. Aho-Corasicková: interpretace

P2 12.10.2020
Slajdy 8-14, cast 15
Aho-Corasicková, alg. Knuth-Morris-Pratt (bude i Rabin-Karp)

P3 19.10.2020
Slajdy 16-22, část 23 
Hledani vzorků: Rabin-Karp.
Toky v sitich, Věta o max. tok a min. rez, alg. zlepsujici cesty (zatím bez dk.)

P4 26.10.2020
Slajdy 23-28+
Dinicův alg., aplikace: max. párování v bipartitním grafu

P5  2.11.2020
Slajdy 29-35
Toky v síti: Goldbergův alg. (v O(n^2 m))

P6  9.11.2020
Slajdy 36-41+
Třídící sítě (Mergesort), úvod Sčítačka

P7 16.11.2020
Slajdy 42-47+
Hradlová síť pro sčítačku, úvod FFT

P8 23.11.2020
Slajdy 48-55
FT a FFT, bez hradel/butterfly a nerekurzivní verze

P9 30.11.2020
Slajdy 56-63
NP-úplnost, převoditelnost, převody

P10 7.12.2020
Slajdy 64-69
NP-úplné úlohy, převody, možnosti jejich řešení. Aproximační algoritmy - úvod

P11 14.12.2020
Slajdy 69-73
Aproximační algoritmy: vrcholové pokrytí

P12 21.12.2020
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.
Pravděpodobnostní alg., (testování prvočíselnosti) - úvod.

P13 4.1.2021
Slajdy 78-79, (80), 81část, 86-90, 91-93
Pravděpodobnostní alg.: Rabinův-Millerův test prvočíselnosti.
Kryptografie, Rozšířený Euklidův alg., RSA.
Konvexní obal v rovině (a převod třídění).

plán: ...

..Px: 

----
Volitelné témy:

[algoritmus Rabin-Karp] 	Ano
[hledání maximálního toku minimální ceny] asi ne
[příbuzné transformace (kosinová - JPEG komprese)] asi stručně
třídící sítě (implementace jednoho třídícího algoritmu - buď merge-sort Ano
  nebo bitonic-sort) asi ne
[Voroného diagram a Delaunayova triangulace (Fortunův algoritmus)] 	Ne


------------------------------
Dříve:
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