Algoritmy a datové strukury II (NTIN061)

Konzultace po dohodě emailem (nejlépe ve středu nebo pátek na MS, 3. patro). Do subjektu emailů pište "ADS2019".

Odpřednesená látka

1. října: Algoritmus KMP pro vyhledávání podřetězců řetězci.
8. října: Algoritmus Aho-Corasickové pro vyhledávání vícero podřetězců naráz. Algortimus Rabin-Karp
15. října: Toky v síti: Ford Fulkersonův algoritmus a první část Dinicova algoritmu.
22. října: Toky v síti: Dinicův algoritmus a úvod do Goldbergova algoritmu
29. října: Goldbergův algoritmus
5. listopadu: Rychlá fourierova transformace
19. listopadu: Rychlá fourierova transformace: dokončení a aplikace (násobení polynomů, DCT a další). Hradlové sítě: úvod.
26. listopadu: Hradlové sítě: dokončení sčítání v logaritmickém čase. Třídicí sítě: bublinkové a bitonické třídění
3. prosince: Komparátor pro bitonické třídění. Složitost a NP-úplnost (úvod).
10. prosince: Složitost a NP-úplnost: převoditelnost problélmů, třída NP, příklady NP-úplných problémů, Cookova věta s náznakem důkazu.
17. prosince: Aproximační algoritmy. Základní definice. 2-aproximace obchodního cestujícího s trojúheníkovou verovností. Neaproximovatelnost obchodního cestujícího obecně. Aproximace pro batoh.
7. ledna: Plán: geometrické algoritmy. Pravděpodobností test prvočíselnosti.