Terminated in academic year 2009/2010

Úvod do teoretické informatiky

Typ studia	bakalářské
Jazyk výuky	čeština
Kód	456-0511/01
Zkratka	UTI
Název předmětu česky	Úvod do teoretické informatiky
Název předmětu anglicky	Introduction to Theoretical Computer Science
Kreditů	6
Garantující katedra	Katedra informatiky
Garant předmětu	doc. Ing. Zdeněk Sawa, Ph.D.

Subject syllabus

Náplň přednášek:
- Základy výrokové a predikátové logiky.
- Analýza vět přirozeného jazyka v jazyce výrokové a predikátové logiky.
- Odvozování důsledků. Množinové / sémantické důkazy.
- Základy rezoluční metody.Přednášky:
- Formální jazyky - základní pojmy (abeceda, slovo, jazyk). Operace na
jazycích. Konečné automaty.
- Konstrukce konečných automatů. Nedeterministické konečné automaty.
- Převod nedeterministických konečných automatů na deterministické.
Regulární výrazy.
- Bezkontextové gramatiky a jazyky.
- Algoritmické problémy. Modely výpočtu (Turingovy stroje a stroje RAM).
- Asymptotická notace. Složitost algoritmů.
- Složitost problémů. Třídy složitosti. Převody mezi problémy. NP-úplné
problémy.
- Algoritmicky nerozhodnutelné problémy.

Cvičení:
- Zopakování základů teorie množin, relací a funkcí a teorie grafů.
- Výroková a predikátová logika.
- Analýza vět přirozeného jazyka v jazyce výrokové a predikátové logiky.
- Odvozování důsledků. Množinové / sémantické důkazy.
- Rezoluční metoda.
- Operace s jazyky.
- Konstrukce konečných automatů.
- Převod nedeterministických automatů na deterministické.
- Regulární výrazy.
- Bezkontextové gramatiky.
- Turingovy stroje a stroje RAM.
- Asymptotická notace. Složitost algoritmů.
- Složitost problémů. Třídy složitosti.

Literature

- prof. RNDr. Petr Jančar, CSc.: Úvod do teoretické informatiky - učební
text, 2007, (k dispozici na adrese http://www.cs.vsb.cz/sawa/uti/materialy/uti.pdf).
- doc. RNDr. Marie Duží, CSc.: Matematická logika, (k dispozici na adrese
http://www.cs.vsb.cz/sawa/uti/materialy/Matlogika.pdf).

Advised literature

- Sipser, M.: Introduction to the Theory of Computation, PWS Publishing Company, 1997.
- Kozen, D.: Automata and Computability. Undergraduate Text in Computer Science, Springer
Verlag, 1997.
- Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993.
- Hopcroft, J.E., Motwani, R., Ullman, J, D.: Introduction to Automata Theory, Languages,
and Computation (3rd Edition), Addison Wesley, 2006.
- Gruska, J.: Foundation of Computing. International Thomson Computer Press, 1997.
- Huth, M., Ryan, M.: Logic in Computer Science: Modelling and Reasoning about Systems,
Cambridge University Press, 2004.
- Švejdar, V.: Logika - neúplnost, složitost a nutnost, Academia, 2002.

back to search page