Předmět Vyčíslitelnost a složitost (VAS)
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 VAS - Vyčíslitelnost a složitost, Provozně ekonomická fakulta, Mendelova univerzita v Brně (MENDELU).
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
1.Opakování základních teoretických znalostí (dotace 2/2) a.Matematická indukceb.Jazyky a gramatiky, Chomského klasifikacec.Regulární jazyky a konečné automatyd.Bezkontextové jazyky a zásobníkové automaty2.Teorie vyčíslitelnosti (dotace 12/6) a.Turingův stroj jako výpočetní model. Definice, varianty, výpočet funkcíb.Kódování Turingova stroje, Univerzální Turingův stroj, Churchova tezec.Redukce, diagonalizaced.Rozhodnutelné, částečně rozhodnutelné a nerozhodnutelné problémy3.Teorie složitosti (dotace 10/4) a.RAM stroj jako výpočetní modelb.Definice složitosti, druhy složitosti, složitostní třídyc.NP úplné problémyd.Složitost paralelních výpočtů
Získané způsobilosti
Všeobecné kompetence: -kapacita k učení se-kapacita vytvářet nové myšlenky (kreativita)-odhodlání k úspěchu-schopnost analýzy a syntézy-schopnost řešit problémy-vědecko-výzkumné dovednostiOborově specifické kompetence: -Analýza časové a prostorové složitosti algoritmu-Porozumění Chomského hierarchi formálních jazyků-Proozumění vztahu mezi třídami gramatik a formálními automaty pro jejich rozhodování-schopnost klasifikace problémů z hlediska možnosti jejich algoritmického řešení
Literatura
TypAutorNázevMísto vydáníNakladatelRokISBNZČEŠKA, M. a kol.Vyčíslitelnost a složitostBrnoCERM1992ZHOPCROFT, J E. -- MOTWANI, R. -- ULLMAN, J D.Introduction to automata theory, languages, and computationBostonPearson/Addison Wesley20070-321-45536-3DSIPSER, M.Introduction to the theory of computationBostonThomson Course Technology20060-534-95097-3DKOZEN, D C.Automata and computabilityNew York, NY [u.a.]Springer19990-387-94907-0
Požadavky
Studenti plní průběžné domácí úkoly, celkem 5 úkolů po 10 bodech. Pro získání zápočtu je třeba 30 bodů. Neúspěšní studenti mohou psát zápočtovou písemku, na kterou lze získat max. 15 bodů a jejíž výsledek se přičítá k bodům za úkoly. Po získání zápočtu studenti skládají ústní zkoušku.
Garant
prof. RNDr. Jiří Hřebíček, CSc.
Vyučující
Ing. Mgr. Jana Dannhoferová, Ph.D.Mgr. Tomáš Foltýnek, Ph.D.prof. RNDr. Jiří Hřebíček, CSc.