Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (19.05.2021)
Přednáška o algoritmech a základech teoretické informatiky.
Navazuje na NTIN060 (ADS1), v učitelském studiu nahrazuje NTIN061 (ADS2) a NTIN071 (Automaty a gramatiky).
Sylabus
Poslední úprava: doc. RNDr. Martin Balko, Ph.D. (12.05.2023)
1. Vyhledávání v textu
notace pro řetězce
algoritmus Knuth-Morris-Pratt
algoritmus Aho-Corasicková
2. Toky v sítích
sítě, toky a řezy
Fordův-Fulkersonův algoritmus
Edmondsův-Karpův algoritmus (FF s nejkratší cestou)
párování v bipartitním grafu
vrcholově/hranově disjunktní cesty v grafech
3. Základní geometrické algoritmy v rovině
konvexní obal
princip zametání roviny řízeného událostmi
4. 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
5. 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
6. Konečné automaty
základní pojmy: slova už známe z vyhledávání v textu, jazyk je vlastně totéž co rozhodovací problém
definice konečného automatu (DFA), syntaxe a sémantika, regulární jazyk
příklad: 0^n1^n není regulární, důkaz principem holubníku
příklad: v KMP uvážíme uzávěr zpětných hran a máme DFA