- 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).
Úvod do teoretické informatiky
| Jazyk výuky | angličtina, čeština |
|---|---|
| Kód | 456-0511 |
| Zkratka | UTI |
| Název předmětu česky | Úvod do teoretické informatiky |
| Název předmětu anglicky | Introduction to Theoretical Computer Science |
| Garantující katedra | Katedra informatiky |
| Garant předmětu | doc. Ing. Zdeněk Sawa, Ph.D. |
Anotace
Předmět je přehledovým úvodem do základních oblastí teoretické informatiky.
Studenty seznámí se základy logiky, formálních jazyků, automatů, algoritmické složitosti, včetně některých jejich aplikací pro řešení praktických programátorských úkolů. Konkrétně se studenti seznámí se se základy výrokové a predikátové logiky. Naučí se formalizovat tvzení v jazyce těchto logik a naučí se používat několik metod logického vyvozování. Dozví se o použití konečných automatů, regulárních výrazů a bezkontextových gramatik při tvorbě překladačů (lexikální a syntaktická analýza) a při vyhledávání v textu.
Studenti se seznámí se základy teorie vyčíslitelnosti a složitosti. Naučí se posuzovat výpočetní složitost algoritmu a používat asymptotickou notaci.
Stručně se také seznámí se složitostí problémů a se třídami složitosti.
Dozví se také, že některé problémy jsou algoritmicky nerozhodnutelné, a jakým způsobem se to dá dokázat.
Studenty seznámí se základy logiky, formálních jazyků, automatů, algoritmické složitosti, včetně některých jejich aplikací pro řešení praktických programátorských úkolů. Konkrétně se studenti seznámí se se základy výrokové a predikátové logiky. Naučí se formalizovat tvzení v jazyce těchto logik a naučí se používat několik metod logického vyvozování. Dozví se o použití konečných automatů, regulárních výrazů a bezkontextových gramatik při tvorbě překladačů (lexikální a syntaktická analýza) a při vyhledávání v textu.
Studenti se seznámí se základy teorie vyčíslitelnosti a složitosti. Naučí se posuzovat výpočetní složitost algoritmu a používat asymptotickou notaci.
Stručně se také seznámí se složitostí problémů a se třídami složitosti.
Dozví se také, že některé problémy jsou algoritmicky nerozhodnutelné, a jakým způsobem se to dá dokázat.
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.