PředmětyPředměty(verze: 902)
Předmět, akademický rok 2022/2023
   Přihlásit přes CAS
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)}
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
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ý

 
Univerzita Karlova | Informační systém UK