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)}
Opinion survey results   Examination dates   WS schedule   Noticeboard   
Annotation - Czech
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).
Last update: Töpfer Pavel, doc. RNDr., CSc. (19.05.2021)
Syllabus - Czech
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ý

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