- 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).
Ukončeno v akademickém roce 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. |
Osnova předmětu
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.
- 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.
Povinná literatura
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.
- 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.