Algoritmy a automaty pro učitele - NUIN021
|
|
|
||
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (19.05.2021)
|
|
||
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (25.05.2022)
1. Vyhledávání v textu notace pro řetězcealgoritmus Knuth-Morris-Pratt algoritmus Aho-Corasicková 2. Toky v sítích sítě, toky a řezyFordů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í obalprincip 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émynedeterministické algoritmy, třídy P a NP NP-úplnost 5. Aproximační algoritmy použití aproximačních algoritmů, poměrová a relativní chybajeden 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émdefinice 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é jazykypravé 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ý automatbez 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ý |