Teoretická informatika 1

• 39 hod. přednášky
• 12 hod. cvičení
• 2 hod. pc laboratoře
• 12 hod. projekty

Teoretické znalosti využívané v problémech konstrukce překladačů, modelování, formální specifikace, automatizace návrhu, verifikace a umělé inteligence.

Osvojení základů teorie formálních jazyků využívaných v konstrukci překladačů a v modelování výpočetních systémů.

Nejsou žádné prerekvizity.

• Úvod, organizace předmětu, význam a aplikace teorie formalních jazyků, příklady jazyků a jejich specifikace.
• Formální jazyky, pojmy abeceda, řetězec, zřetězení, operace nad jazyky, algebra jazyků jako polookruh.
• Reprezentace jazyků, problém reprezentace, způsoby reprezentace formálních jazyků.
• Gramatiky, definice gramatiky, relace derivace, větná forma a jazyk generovaný gramatikou, Chomského klasifikace gramatik a formálních jazyků, ilustrační příklady.
• Jazyky přijímané konečnými automaty, definice konečného nedeterministického automatu, konfigurace automatu, relace přechodu, jazyk přijímaný konečným automatem, vztah deterministických a nedeterministických konečných automatů, vztah jazyků typu 3 a jazyků přijímaných konečnými automaty, ilustrační příklady.
• Regulární množiny a regulární výrazy, definice, algebra regulárních výrazů (identity), rovnice nad regulárními výrazy, vztah regulárních množin a jazyků typu 3, ilustrační příklady. Rozšířený konečný automat, převod regulárního výrazu na ekvivalentní deterministický konečný automat, ilustrační příklady.
• Minimalizace konečného automatu, relace nerozlišitelnosti stavů, konstrukce redukovaného konečného automatu ilustrační příklady.
• Vlastnosti regulárních jazyků, strukturální vlastnosti, Pumping theorem pro regulární jazyky, uzávěrové vlastnosti, rozhodnutelné problémy regulárních jazyků, ilustrační příklady a příklady k samostatnému řešení.
• Bezkontextové gramatiky, definice, levá a pravá derivace, víceznačnost gramatik, rekurze, problém syntaktické analýzy, klasifikace syntaktických analyzátorů, ilustrační příklady a příklady k samostatnému řešení.
• Transformace bezkontextových gramatik, ekvivalence bezkontextových gramatik, odstranění zbytečných symbolů, odstranění e-pravidel, odstranění jednoduchých pravidel, převod na vlastní gramatiku, odstranění levé rekurze, ilustrační příklady.
• Zásobníkové automaty, definice, varianty, ekvivalence jazyků typu 2 a jazyků přijímaných zásobníkovými automaty, deterministické zásobníkové automaty a deterministické bezkontextové jazyky, ilustrační příklady.
• Vlastnosti bezkontextových jazyků, normální tvary bezkontextových gramatik, Greibachové a Chomského normální forma, pumping theorem pro bezkontextové jazyky, uzávěrové vlastnosti bezkontextových jazyků, rozhodnutelné a nerozhodnutelné problémy bezkontextových jazyků, ilustrační příklady.
• Petriho sítě, definice, stavový prostor a přechodová funkce Petriho sítě, lineární algebraická reprezenatce Petriho sítě, ilustrační příklady.

• Operace nad jazyky, gramatiky, jejich klasifikace.
• Vzájemné převody mezi gramatikami typu 3, konečnými automaty a regulárními výrazy.
• Minimalizace konečných automatů, vlastnosti regulárních jazyků.
• Konstrukce bezkontextových gramatik, derivační stromy.
• Transformace bezkontextových gramatik.
• Konstrukce zásobníkových automatů, vlastnosti bezkontextových jazyků.

• Petri net tool PESIM.

Udělení zápočtu je podmíněno absolvováním polosemestrální písemné zkoušky a ziskem minimálně 25 bodů za bodované aktivity v průběhu semestru (půlsemestrální zkouška, domací úlohy).

Písemná půlsemestrální zkouška, průběžná kontrola a hodnocení projektů