Algorithms and automata for teachers - NUIN021

• Title: Algoritmy a automaty pro učitele
• Guaranteed by: Department of Applied Mathematics (32-KAM)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2022
• Semester: winter
• E-Credits: 5
• Hours per week, examination: winter s.:2/2, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech
• Teaching methods: full-time
• Teaching methods: full-time
• Guarantor: Mgr. Martin Mareš, Ph.D.
• Interchangeability : {Algoritmy a datové struktury (NTIN061) a Automaty a gramatiky (NTIN071)}

Annotation

Last update: 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).

Syllabus

Last update: doc. RNDr. Martin Balko, Ph.D. (12.05.2023)

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ý