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 [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ý