Poslední úprava: doc. RNDr. Martin Balko, Ph.D. (12.05.2023)
1. Vyhledávání v textu
- algoritmus Knuth-Morris-Pratt
- algoritmus Aho-Corasicková
2. Toky v sítích
- 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ě
- 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
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
- regulární pumping lemma (zobecnění myšlenky předchozího důkazu)
- příklad: 1^{prvočíslo} není regulární
7. Regulární výrazy
- nedeterministický konečný automat (NFA)
- ε-přechody, ekvivalence ε-NFA ↔ NFA
- uzavřenost na množinové operace
- regulární výrazy popisují právě regulární jazyky
8. Gramatiky
- gramatiky, jimi generované jazyky
- pravé a levé lineární gramatiky generují regulární jazyky
- obecné lineární gramatiky generují i neregulární jazyky
- bezkontextové gramatiky, derivační stromy, jednoznačnost
- algoritmus testující příslušnost slova do bezkontextového jazyka pomocí dynamického programování
9. Turingovy stroje
- obousměrný konečný automat
- bez důkazu: obousměrné automaty jsou stejně silné jako jednosměrné
- TM může příjímat zastavením (rekurzivně spočetné jazyky), přijímat stavem (rekurzivní jazyky) nebo vydávat výstup na pásce (vyčíslitelné funkce)
- neformálně: vztah mezi TM a RAMem
- TM jsou ekvivalentní s obecnými gramatikami
- univerzální Turingův stroj, kódování strojů (bez detailů konstrukce)
- halting problem je rekurzivně spočetný, ale není rekurzivní
- Postova věta => doplněk halting problemu není rekurzivně spočetný
|