Algoritmy a datové struktury 2

Sylabus

Volitelná témata v hranatých závorkách, zbytek je povinný.

1. Vyhledávání v textu - algoritmus Knuth-Morris-Pratt - algoritmus Aho-Corasicková - [algoritmus Rabin-Karp]

2. Toky v sítích - algoritmus zlepšující cesty - Dinicův algoritmus - Goldbergův algoritmus - párování v bipartitním grafu - [hledání maximálního toku minimální ceny]

3. Algebraické algoritmy - diskrétní Fourierova transformace, její motivace a aplikace - algoritmus FFT a jeho implementace obvodem „butterfly“ - [příbuzné transformace (kosinová - JPEG komprese)]

4. Paralelní aritmetické algoritmy - třídící sítě (implementace jednoho třídícího algoritmu - buď merge-sort nebo bitonic-sort) - carry look-ahead algoritmus pro sčítání čísel

5. Základní geometrické algoritmy v rovině - konvexní obal - princip zametání roviny řízeného událostmi - [Voroného diagram a Delaunayova triangulace (Fortunův algoritmus)]

6. Převoditelnost problémů a třídy časové složitosti - polynomiální transformace a redukce mezi rozhodovacími problémy - nedeterministické algoritmy, třídy P a NP - NP-úplnost

7. Aproximační algoritmy - použití aproximačních algoritmů, poměrová a relativní chyba - jeden až dva jednoduché příklady aproximačních algoritmů (knapsack, bin-packing, rozvrhování na paralelních strojích) včetně horního odhadu pro jejich poměrovou (nebo relativní) chybu - aproximační schéma: princip a příklad

8. Pravděpodobnostní algoritmy a kryptografie - algoritmy typu Monte Carlo (Rabinův-Millerův test prvočíselnosti) - šifrování s veřejným klíčem (algoritmus RSA)

Anotace

Přednáška o různých typech algoritmů a jejich časové složitosti (navazuje na NTIN060 Algoritmy a datové struktury 1).