460-2005/02 – Úvod do teoretické informatiky (UTI)
Garantující katedra | Katedra informatiky | Kredity | 6 |
Garant předmětu | doc. Ing. Zdeněk Sawa, Ph.D. | Garant verze předmětu | doc. Ing. Zdeněk Sawa, Ph.D. |
Úroveň studia | pregraduální nebo graduální | | |
| | Jazyk výuky | angličtina |
Rok zavedení | 2015/2016 | Rok zrušení | 2018/2019 |
Určeno pro fakulty | FEI | Určeno pro typy studia | bakalářské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Posluchač umí zacházet se základními pojmy teoretické informatiky a umí je používat v běžné programátorské praxi. Zároveň jsou předmětem podány teoretické základy nutné pro další studium informatiky na vyšším stupni.
Vyučovací metody
Přednášky
Cvičení (v učebně)
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.
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.
Forma způsobu ověření studijních výsledků a další požadavky na studenta
Průběžná kontrola studia:
- Písemka v průběhu semestru (za 22 bodů).
Požadavky na zápočet:
Pro udělení zápočtu musí student získat z písemky nejméně 7 bodů.
Zkouška:
- Zkouška bude písemná a případně může být doplněna o volitelnou ústní
část, která slouží zejména k vyjasnění případných nejasností v písemné části.
Zkouška se bude skládat ze tří částí věnovaných následujícím oblastem:
- úvod do logiky
- teorie formálních jazyků a automatů
- vyčíslitelnost a složitost
Celkem je možné získat za zkoušku až 78 bodů.
Pro absolvování zkoušky je nutné získat z každé z jejích tří částí minimálně 10 bodů.
E-learning
Další požadavky na studenta
Další požadavky na studenta nejsou kladeny.
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
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.
Podmínky absolvování předmětu
Podmínky absolvování jsou definovány pouze pro konkrétní verzi předmětu a formu studia
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky