Předmět Matematické základy informatiky (4PS115)

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 4PS115 - Matematické základy informatiky, Fakulta informatiky a statistiky, Vysoká škola ekonomická v Praze (VŠE).

Materiál	Typ	Datum	Počet stažení

Obsah

Množinové operace, binární relace a jejich vlastnosti, ekvivalentní množiny, nejvýše spočetné množiny, booleovské funkce.Základní pojmy z teorie grafů, reprezentace binární relace grafem. Stromy, kořenové stromy, binární stromy, třídící, vyhledávací, kódovací a rozhodovací stromy, ohodnocené grafy, délky cest, kritická cesta.Výroková logika, formule výrokové logiky, pravdivostní ohodnocení, sémantický důsledek, tautologická ekvivalence, úplné systémy logických spojek, disjunktivní normální formy, konjunktivní normální formy, booleovský kalkul. Rezolventy, rezoluční princip ve výrokové logice. Predikátová logika, jazyk predikátové logiky, formule predikátové logiky, sémantika (tautologie, kontradikce, splnitelná sentence, konsekvence, tautologická ekvivalence), rezoluční metoda v predikátové logice.Formální jazyky, abeceda, operace s jazykyKonečné automaty, normovaný tvar, nedeterministický konečný automat, regulární jazyky a gramatiky. Zásobníkové automaty, vlastnosti bezkontextových jazyků, bezkontextové gramatiky, odvození aritmetických výrazů.Turingovy stroje, generativní gramatiky, Chomského hierarchie.Problémy, algoritmy a výpočetní modely, Churchova-Turingova teze, kódování vstupů a výstupůRozhodnutelné a nerozhodnutelné problémy.Výpočetní složitost, analýza algoritmů, asymptotická složitost, složitost Turingových strojů.Efektivní algoritmy,efektivnost a složitost, některé „rychlé“ algoritmy.Složitost problémů, třída P, polynomiální převod.NP-úplnost, třída NPTIME, NP-úplné problémy, P vs.NP.

Získané způsobilosti

Po úspěšném absolvování budou studenti schopni se orientovat v matematických základech informatiky, speciálně v logických a algoritmických prostředcích pro řešení problémů. Studenti budou seznámeni se širokým spektrem metod i modelů, které umožňují algoritmické řešení úloh v reálném čase.

Literatura

TypAutorNázevMísto vydáníNakladatelRokISBNZIVÁNEK, J. -- PÁNKOVÁ, V.Základy matematické informatiky. [Část] 2, Množinové struktury.Praha:Vysoká škola ekonomická, 1985.ZIVÁNEK, J.Základy matematické informatiky I : Informace a automaty.Praha:SPN, 1991.990000120XDCoufal, J. (kandidátská disertační práce): Několik poznámek o výpočtové složitosti algoritmů,1991DDemlová, M. - Pondělíček, B.: Matematická logika,1999DHabiballa, H.: Teoretické základy informatiky, ISBN 80-7042-859-7, 2003DJančar, P.: Teoretická informatika, ISBN 978-80-248-1487-2,2007

Požadavky

žádné

Garant

Ing. Jiří Pátek, CSc.

Vyučující

Ing. Jiří Pátek, CSc.