Ukončeno v akademickém roce 2018/2019

Úvod do teoretické informatiky

Typ studia	bakalářské
Jazyk výuky	čeština
Kód	460-2005/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.

Osnova předmětu

Náplň přednášek:
- Úvod. Logika. Důkazy. Logické spojky.
- Další logické spojky. Syntaxe a sémantika v logice.
- Tabulková metoda. Ekvivalentní úpravy. Predikátová logika.
- Kvantifikátory. Naivní teorie množin.
- 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.

Povinná literatura

- doc. Ing. Zdeněk Sawa, Ph.D.: Úvod do teoretické informatiky - slidy (k dispozici na adrese http://www.cs.vsb.cz/sawa/uti/slides/uti-cz.pdf,
anglická verze na adrese http://www.cs.vsb.cz/sawa/uti/slides/uti-en.pdf)
- doc. Ing. Zdeněk Sawa, Ph.D.: Úvod do teoretické informatiky - logika a algoritmy, (k dispozici na adrese http://www.cs.vsb.cz/sawa/uti/materialy/uti-2014.02.09.pdf)
- 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).

Doporučená literatura

- 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.
- Suppes, P.: Introduction to Logic, Dover Publications, 1999.
- Tarski, A.: Introduction to Logic and to the Methodology of Deductive Sciences, Dover Publications, 1995.
- Devlin, K.: Introduction to Mathematical Thinking, Keith Devlin, 2012.

zpět na vyhledávání