Kombinované studium – Formální jazyky a automaty

Název předmětu: Formální jazyky a automaty (KMI/YZTI)

Počet kreditů: 9

Ročník: 3

Semestr: letní

Vyučující/Tutor: Mgr. Petr Osička, Ph.D.

Konzultace

Prezenční


Pondělí 14:00 - 15:30

E-mailová

Průběžně na petr.osicka@upol.cz

Telefonem

585 634 721

Studijní materiály

Prezentace z přednášky

(prozatim verze z minulych let, pravdepodobne je letos upravím) Ke stažení formální jazyky (poslední změna 2. 3. 2018) vyčíslitelnost (pdf verze, poslední změna 20. 4. 2018), složitost (pdf verze, poslední změna 20. 4. 2018).

Zkoušení

Termíny jsou vypsány ve STAGu. Seznam otázek a další info ke zkoušce [pdf]

Plán výuky

  1. Formální jazyky a automaty: gramatiky, konečné automaty (deterministické a nedeterministické)
  2. Formální jazyky a automaty: regulární výrazy (automaty s epsilon přechody, uzávěrové vlastnosti regulárních jazyků, regulární výrazy)
  3. Formální jazyky a automaty: minimalizace konečného automatu, pumping lemma
  4. Vyčíslitelnost, existence nerozhodnutelných problémů
  5. Složitost, teorie NP-úplnosti
  6. Správce stránky: Petr Osička  |  Aktualizace: 14.02.2019, 09:37:36