Prednášky ADS2, ZS 2022/23, Po 15:40, N1 P1 3.10.2022 Slajdy 1-7 Úvod. Vyhledavaní řetězců, alg. Aho-Corasicková: interpretace P2 10.10.2022 Slajdy 8-15 Aho-Corasicková, alg. Knuth-Morris-Pratt zčásti (bude i alg. Rabin-Karp) P3 17.10. Slajdy 15-20 Alg. Knuth-Morris-Pratt dokončení, alg. Rabin-Karp (s hašováním) Toky v sítích, Reziduální síť. (před: Věta o max. toku a min. řezu) P4 24.10. Slajdy 21-28 Věta o max. tok a min. řezu, alg. zlepsujici cesty. Toky v sítích: Dinicův alg. Aplikace: max. párování v bipartitním grafu - stručně P5 31.10. Slajdy 29-35 Toky v sítích: Goldbergův alg. (v O(n^2 m), bez analýzy strategie nejvyššího vrcholu) Úvod: třídící sítě (10') P6 7.11. Slajdy 36-41+ Třídící sítě (Mergesort), úvod Sčítačka: jednobitová sčítačka, algoritmus s lineární hloubkou. P7 14.11. Slajdy 42-47 Aritmetické sítě: Hradlová síť pro sčítačku, spomenul jsem násobení v log. hloubce. Úvod FFT. P8 21.11.2022 Slajdy 48-54 FT a FFT, i hradla/butterfly obvod a nerekurzivní verze, bez slajdu 55: aplikace P9 28.11.2022 Slajdy 56-63 Třídy P, NP, NP-úplnost, převoditelnost, převod SAT -> Klika P10 5.12.2022 Slajdy 64-72 NP-úplné úlohy, "malé" převody, možnosti řešení NPÚ úloh. Aproximační algoritmy: úvod, vrcholové pokrytí, ham.kružnice s trojúh. nerovností P11 12.12.2022 Slajdy 73-77část neaproximovatelnost POC bez trojuh. nerovnosti, aproximační schéma pro součet podmnožiny. Pravděpodobnostní alg. (testování prvočíselnosti) - úvod. plán (podle 2020/21) P12 19.12.2022 Slajdy (77-77) UPDATE: Pravděpodobnostní testování prvočíselnosti. Kryptografie, Rozšířený Euklidův alg., RSA. P13 2.1.2023 Slajdy ((78-79, (80), 81část, 86-90, 91-93)) Kryptografie, Konvexní obal v rovině (a převod třídění). ------------------ 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