Algorithms and automata for teachers

Syllabus

*

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 - regulární pumping lemma (zobecnění myšlenky předchozího důkazu) - příklad: 1^{prvočíslo} není regulární - součin automatů *

7. Regulární výrazy - nedeterministický konečný automat (NFA) - ekvivalence DFA ↔ 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 - Chomského normální forma - 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é - Turingův stroj (TM) - 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ý

Annotation

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