Skip to content
Snippets Groups Projects
Select Git revision
  • e86cf016c6e0fe9199f8d2875940634f1e8b5a78
  • master default
  • navrh-automaty-gramatiky
3 results

AG.md

Blame
    • AG.md 3.14 KiB

    Automaty a složitost (návrh)

    Sylabus

    1. Konečné automaty (2 přednášky)

      • základní pojmy: abeceda, slovo, jazyk (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ů
      • TODO: Možná Myhill-Nerode (ve verzi se syntaktickou kongruencí?)

    2. Regulární výrazy (1 přednáška)

      • nedeterministický konečný automat (NFA)
      • ekvivalence DFA :left_right_arrow: NFA
      • ε-přechody, ekvivalence ε-NFA :left_right_arrow: NFA
      • uzavřenost na množinové operace
      • regulární výrazy popisují právě regulární jazyky

    3. Gramatiky (3 přednášky)

      • bezkontextové gramatiky, derivační stromy, generované jazyky
      • pravé a levé lineární gramatiky generují regulární jazyky
      • obecné lineární gramatiky generují i neregulární jazyky
      • jednoznačnost gramatiky
      • Chomského normální forma
      • algoritmus testující příslušnost slova do bezkontextového jazyka pomocí dynamického programování
      • iterační lemma pro bezkontextové jazyky
      • nedeterministický zásobníkový automat (NPDA)
      • NPDA rozhodují bezkontextové jazyky

    4. Turingovy stroje (2 přednášky)

      • Turingův stroj (TM) a jeho výpočet
      • TM může příjímat zastavením (částečně rozhodnutelné jazyky), přijímat stavem (rozhodnutelné jazyky) nebo vydávat výstup na pásce (vyčíslitelné funkce)
      • varianty TM:
        • páska jen pro čtení => obousměrný konečný automat Důkaz ekvivalence s klasickým DFA.
        • více pásek: důkaz ekvivalence s jednopáskovým TM
        • nedeterministický TM
      • vztah mezi TM a RAMem

    5. Základy vyčíslitelnosti (2 přednášky)

      • univerzální Turingův stroj, kódování strojů (bez detailů konstrukce)
      • univerzální jazyk a diagonální jazyk
      • halting problem je částečně rozhodnutelný, ale není rozhodnutelný
      • Postova věta => doplněk halting problemu není částečně rozhodnutelný
      • jazyk je částečně rozhodnutelný <=> jeho slova lze vyjmenovat
      • převoditelnost jazyků
      • nerozhodnutelné problémy ohledně bezkontextových gramatik
      • Riceova věta

    6. Polynomiálni složitost a P vs. NP (2 přednášky)

      • třídy DTIME(f)
      • redukce počtu pásek a univerzální TM zpomalují jen polynomiálně, stejně tak převody TM <-> RAM => třída P je nezávislá na modelu
      • třída NP definovaná pomocí certifikátů
      • převoditelnost v polynomiálním čase
      • příklady převodů mezi problémy
      • NP-úplnost
      • Cookova-Levinova věta
      • třída co-NP, tautologičnost

    Možné rozšíření

    1. Další složitostní třídy
      • třídy DSPACE(f), PSPACE
      • nedeterministické třídy NTIME(f), NSPACE(f), NP, NPSPACE
      • DTIME(f) ⊆ NTIME(f) ⊆ DSPACE(f) ⊆ NSPACE(f) ⊆ DTIME(2^O(f))
      • důsledek: P ⊆ NP ⊆ PSPACE ⊆ NPSPACE ⊆ DTIME(2^poly(n))
      • důsledek: DSPACE(log n) ⊆ NSPACE(log n) ⊆ P
      • základný myšlenky fine-grained složitosti

    (celkem 12 přednášek)