Předmět Úvod do teoretické informatiky (UTI)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu UTI - Úvod do teoretické informatiky, Vysoká škola báňská - Technická univerzita Ostrava (VŠB-TU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
Posluchač umí zacházet se základními pojmy teoretickéinformatiky a umí je používat v běžné programátorské praxi. Zároveň jsoupředmětem podány teoretické základy nutné pro další studium informatiky na vyšším stupni.
Osnova
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.
Literatura
- 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).
Požadavky
Žádné
Garant
doc. Ing. Zdeněk Sawa, Ph.D.
Vyučující
Mgr. Pavla Dráždilová, Ph.D.Ing. Jakub HendrychIng. Martin Kot, Ph.D.Ing. Radim KunčickýMgr. Marek Menšík, Ph.D.doc. Ing. Zdeněk Sawa, Ph.D.Ing. Martin Šurkovský