Předmět Teoretické základy informatiky (KMI / SZZZI)
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 KMI / SZZZI - Teoretické základy informatiky, Přírodovědecká fakulta, Univerzita Palackého v Olomouci (UP).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Obsah
nová verze; pro studenty, kteří zahájili studium v roce 2009 a pozdějiFormální jazyky a jejich hierarchie. Regulární jazyky (definice, uzávěrové vlastnosti). Konečné automaty deterministické a nedeterministické. Regulární výrazy, automaty s epsilon-přechody. Minimalizace konečného deterministického automatu. Pumping lemma. Bezkontextové jazyky a jejich vlastnosti (uzávěrové vlastnosti, jednoznačnost). Zásobníkové automaty a jejich modifikace. Deterministické zásobníkové automaty. Deterministické bezkontextové jazyky.Turingův stroj (TS), nedeterministický TS. Jazyk přijímaný TS, jazyk rozhodovaný TS. Church-Turingova teze, varianty TS. Částečně rekurzivní a rekurzivní jazyky, jazyky a rozhodovací problémy. Vztah rekurzivních a částečně rekurzivních jazyků. Uzávěrové vlastnosti jazyků TS. Riceova věta. Vztah jazyků TS k jazykům Chomského hierarchie. Věta o rekurzi.Složitost algoritmu (časová a paměťová). Třída P, třída NP, důvody jejich zavedení, jejich vzájemný vztah. NP-úplné problémy. Cook-Levinova věta. Příklady NP-úplných problémů, dokazovaní NP-úplnosti. Třída PSPACE, její vztah k třídám P a NP, PSPACE-úplné problémy. Třídy N a NL a NL-úplné problémy.Výroková logika: jazyk, formule, pravdivostní ohodnocení, tautologie, tabulková metoda, sémantické vyplývání, normální formy formulí, úplné systémy spojek. Axiomatický systém výrokové logiky, syntaktické vyplývání. Ve?ta o dedukci. Ve?ty o korektnosti a úplnosti výrokové logiky. Predikátová logika: jazyk, termy a formule, struktury pro jazyk, ohodnocení termu? a formulí. Axiomatický systém predikátové logiky, syntaktické vyplývání. Ve?ty o korektnosti a úplnosti predikátové logiky. Neklasické logiky, fuzzy logika. Základy logického programování, úvod do Prologu.==================================================stará verze vizhttp://www.inf.upol.cz/bakalarska-statni-zkouska
Požadavky
Schopnost odborně popsat a shrnout problematiku (motivaci, prostředky,výsledky).
Garant
prof. RNDr. Radim Bělohlávek, Ph.D., DSc.