Detail předmětu

Teoretická informatika

FIT-TINAk. rok: 2010/2011

Jazyk výuky

čeština

Počet kreditů

5

Garant předmětu

prof. RNDr. Milan Češka, CSc.

Zajišťuje ústav

Ústav inteligentních systémů (UITS)

Zařazení předmětu ve studijních plánech

  • Program IT-MGR-2 magisterský navazující

    obor MBI , 1 ročník, zimní semestr, povinný
    obor MBS , 1 ročník, zimní semestr, povinný
    obor MGM , 1 ročník, zimní semestr, povinný
    obor MIN , 1 ročník, zimní semestr, povinný
    obor MIS , 1 ročník, zimní semestr, povinný
    obor MMI , 1 ročník, zimní semestr, povinný
    obor MMM , 1 ročník, zimní semestr, povinný
    obor MPS , 1 ročník, zimní semestr, povinný
    obor MPV , 1 ročník, zimní semestr, povinný
    obor MSK , 1 ročník, zimní semestr, povinný

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Milan Češka, CSc.

Osnova

  1. Úvod, aplikace teorie formálních jazyků, modelovací a rozhodovací síla formálního modelu, operace nad jazyky.
  2. Regulární jazyky a jejich vlastnosti, Kleenova věta, Nerodova věta, věta o vkládání (Pumping theorem).
  3. Minimalizace konečného automatu, relace nerozlišitelnosti stavů, konstrukce redukovaného konečného automatu.
  4. Uzávěrové vlastnosti regulárních jazyků, regulární jazyky jako množinová Booleova algebra, rozhodnutelné problémy regulárních jazyků.
  5. Bezkontextové jazyky a jejich vlastnosti. Normální tvary bezkontextových gramatik, jednoznačné a deterministické bezkontextové jazyky, věta o vkládání pro bezkontextové jazyky.
  6. Uzávěrové vlastnosti bezkontextových jazyků, uzavřenost vzhledem k substituci, důsledky, rozhodnutelné problémy bezkontextových jazyků.
  7. Turingovy stroje (TS), definice TS a jazyka přijímaného TS, rekurzivně vyčíslitelné a rekurzivní jazyky a problémy, TS a funkce, metody konstrukce TS.
  8. Modifikace TS, TS s obousměrně nekonečnou páskou, s více páskami, nedeterministický TS, stroj se dvěma zásobníky, stroje s čitači.
  9. TS a jazyky typu 0, diagonalizace, vlastnosti rekurzivních a rekurzivně vyčíslitelných jazyků, lineárně ohraničené automaty a jazyky typu 1.
  10. Vyčíslitelné funkce, počáteční funkce, primitivně rekurzivní funkce, mí-rekurzivní funkce, vztah vyčíslitelných funkcí a Turingových strojů.
  11. Church-Turingova téze, univerzální TS, nerozhodnutelnost, problém zastavení TS, redukce, Postův korespondenční problém.
  12. Nerozhodnutelné problémy teorie formálních jazyků.
  13. Úvod do výpočetní složitosti, Turingovská složitost, třída P a NP problémů.

Projekt

13 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Milan Češka, CSc.