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