Algoritmy a automaty pro učitele - NUIN021

• Anglický název: ?
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2021
• Semestr: zimní
• E-Kredity: 5
• Rozsah, examinace: zimní s.:2/2 Z+Zk [hodiny/týden]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• Virtuální mobilita / počet míst: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Garant: Mgr. Martin Mareš, Ph.D.
• Záměnnost : {Algoritmy a datové struktury (NTIN061) a Automaty a gramatiky (NTIN071)}

Anotace

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. Pavel Töpfer, CSc. (25.05.2022)

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ý