Název: Algoritmy a gramatiky Zkratka: AG Typ: povinný Rozsah: 14 týdnů, týdně 2 hodiny přednášek + 1 hodina seminárního cvičení Způsob ukončení: zkouška Katedra: katedra softwarového inženýrství FM TUL Přednášející: Doc. Ing. Mgr. Václav Záda, CSc.
Stručná anotace předmětu:Předmět seznamuje studenty se základy teorie automatů, gramatik a vybranými partiemi teorie algoritů. Cílem je dosáhnout sjednocení zdánlivě rozdrobených znalostí studentů a vytvořit teoretický základ pro ostatní předměty informatiky na základě sjednocujícího hlediska.
Témata přednášek:Konečné automaty, jazyky rozpoznatelné konečnými automaty, Nerodova věta. Redukce konečného automatu a dekompozice strojů. Přechodové grafy.
Nedeterministické konečné automaty a jejich využití. Mooreho věta o existenci algoritmu rozhodujícího ekvivalenci automatů.
Regulární výrazy a jazyky. Kleeneho věta o ekvivalenci regulárních jazyků a jazyků rozpoznatelných konečnými automaty.
Definice gramatik, Chomského hierarchie. Regulární gramatiky, souvislost s regulárními jazyky.
Redukované gramatiky, kanonické derivace, derivační stromy. Zásobníkové automaty a bezkontextové jazyky. Chomského normální forma.
Syntaktická analýza, jazyky LL a LR. Stochastické gramatiky.
Churchova-Turingova teze. Turingovy stroje a jazyky typu 0. Postovy stroje, ekvivalence s Turingovými stroji a se stroji se dvěma zásobníky.
Nedeterministické stroje.
Primitivně a parciálně rekurzivní funkce.
Turingovy stroje jako algoritmy, rozhodnutelnost tříd problémů typu ANO\NE, problém zastavení pro Turingovy stroje, algoritmicky neřešitelné problémy, jejich redukce na nerozhodnutelnost problému zastavení. Parciální rozhodnutelnost tříd problémů typu ANO\NE.
Časová a paměťová složitost algoritmů. Principy prohledávání grafů, Backtracking, porovnání složitosti kombinatorických algoritmů. Třídy úloh typu P a NP, NP úplnost úloh.
Náplň cvičení:Příklady jednoduchých konečných automatů, užití Nerodovy věty v úloze rozpoznatelnosti jazyka konečným automatem. Redukce automatu.
Návrh konečného automatu přes nedeterministický automat, jeho převod na automat deterministický.
Technické realizace a programové implementace konečných automatů. Typické problémy, pro jejichž řešení je vhodé použít konečné automaty. Návrh nápojového automatu.
Využití gramatik v úlohách rozpoznávání. Celulární automaty, jejich použití v simulaci úloh o proudění tekutin.
Konstrukce zjednodušeného překladače.
Vybrané algoritmy operační analýzy, CPM. Třídění v čase. Toky v sítích, maximální párování.
Hamiltonovské kružnice a problém obchodního cestujícího, barvení grafu, jejich využití v chemii, barvířství, dopravě.
NP úplnost úloh: určování splnitelnosti logických formulí, rozvrhování pro jeden procesor, barvení grafu, problém obchodního cestujícího, minimální kostra grafu, nejdelší a nejkratší cesta v grafu ap.
Literatura:Chytil, M.: Automaty a gramatiky. Praha, SNTL 1984.
Hopcroft, J.E.-Ullman,J.D.: Formálne jazyky a automaty. Bratislava, Alfa 1978. (překlad z angličtiny)
Manna, Z.: Matematická teorie programů. Praha, SNTL 1981.
Molnár,L. a kol.: Gramatiky a jazyky. Bratislava, Alfa 1987.
Kučera, L.: Kombinatorické algoritmy. Praha, SNTL 1989.
Morávek, I.: Složitost výpočtů a optimální algoritmy. Praha, Academia 1984.
Rogers, H.: Theory of Recursive Functions and Effective Computability. New York, McGraw-Hill Book Comp. 1967.
Prerekvizity: -Navazující: -
Datum poslední změny: 7.1. 2002