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".
- Přednáška: Út 12:20, S3
- Cvičení:
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.
Odkazy