Algoritmy a datové strukury II (NTIN061)

Jan Hubička, hubicka@kam.mff.cuni.cz

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).

Odkazy