Předmět Theoretical Informatics (KIKM / ATINF)

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 KIKM / ATINF - Theoretical Informatics, Fakulta informatiky a managementu, Univerzita Hradec Králové (UHK).

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

Obsah

Konečné automaty, ekvivalence automatů, iterační lemma, dosažitelnost a ekvivalence stavů, redukce a normalizace konečných automatů, nedeterministické konečné automaty.Regulární výrazy, Kleenova věta, převod regulárního výrazu na automat, převod automatu na regulární výraz.Chomského hierarchie gramatik, bezkontextové gramatiky, derivační stromy, zásobníkové automaty, přijímání prázdným zásobníkem a koncovým stavem, iterační (pumping) lemma.Kontextové gramatiky, Turingovy stroje, různé typy Turingových strojů, definice algoritmu, univerzální Turingův stroj.Rozhodovací problémy, problém zastavení Turingova stroje, Postův problém přiřazení a jeho aplikace.Teorie složitosti, časová a prostorová složitost, analýza algoritmu a měření složitosti.Definice tříd P a NP, polynomiální převoditelnost problémů, pojem NP-úplnosti, příklady NP-úplných problémů, přibližná řešení těžkých problémů.

Získané způsobilosti

Absolvováním předmětu student získá základní přehled v oblasti teorie automatů a formálních gramatik, teorie vyčíslitelnosti a teorie složitosti. Kromě teoretických poznatků a důrazu na zvládnutí formálního aparátu teoretické informatiky, jsou cvičení k tomuto předmětu zaměřena na praktické dopady a možnosti využití nabytých teoretických poznatků.

Literatura

Sipser, Michael. Introduction to the theory of computation. 2nd ed., International ed. Boston, 2006. ISBN 0-619-21764-2.Garey, Michael R. Computers and intractability. New York, 1979. ISBN 0-7167-1045-5.Cormen, Thomas H. Introduction to algorithms. Cambridge, MA, 1998. ISBN 0-262-53091-0.Hopcroft, John E. Introduction to automata theory, languages, and computation. 2nd ed. Boston, 2001. ISBN 0-201-44124-1.Kučera, Luděk. Kombinatorické algoritmy. Praha, 1989.

Požadavky

Docházka na cvičení je zaznamenávána a může být použita jako doprovodné kritérium pro rozhodování v případě, kdy student nesplňuje požadavky k zápočtu. Účast na termínech cvičení, ve kterém probíhá test, je povinná.V polovině semestru (obvykle 7. týden) je v rámci cvičení psán zápočtový test. Na získání zápočtu je třeba získat nejméně 70 % bodů.

Garant

prof. RNDr. Josef Hynek, Ph.D., MBA

Vyučující

prof. RNDr. Josef Hynek, Ph.D., MBARNDr. Andrea Ševčíkováprof. RNDr. Josef Hynek, Ph.D., MBARNDr. Andrea Ševčíková