Předmět: Složitost a vyčíslitelnost

» Seznam fakult » FP » NTI
Název předmětu Složitost a vyčíslitelnost
Kód předmětu NTI/SVA
Organizační forma výuky Přednáška + Cvičení
Úroveň předmětu Magisterský
Rok studia nespecifikován
Semestr Zimní a letní
Počet ECTS kreditů 2
Vyučovací jazyk Čeština
Statut předmětu Povinný
Způsob výuky Kontaktní
Studijní praxe Nejedná se o pracovní stáž
Doporučené volitelné součásti programu Není
Vyučující
  • Kosková Třísková Lenka, Ing. Ph.D.
Obsah předmětu
Přednášky: 1. Matematické modely výpočtů, Turingův stroj. 2. Rozhodnutelnost, problém zastavení, Postův problém. 3. Vyčíslitelnost, rekurzivní funkce, Turingova a Churchova teze. 4. Algoritmická složitost. 5. Asymptotická složitost. 6. Rozhodnutelnost v polynomiálním čase. 7. NP-jazyky, NP-problémy, NP-úplnost.

Studijní aktivity a metody výuky
Monologický výklad (přednáška, prezentace, vysvětlování)
  • Účast na výuce - 14 hodin za semestr
Výstupy z učení
Třídy složitosti úloh, polynomiální, NP, exponenciální, NP-úplné problémy. Prvočíselnost. Kryptografie. Vyčíslitelnost: Turingovy stroje, primitivně rekurzivní funkce, Kleeneho věta o normální formě, algoritmicky neřešitelné problémy, rekurzivní a rekurzivně spočetné množiny.
Studenti získají přehled o základních pojmech souvisejících s teoretickou vyčíslitelností a složitostí algoritmů.
Předpoklady
Nespecifikováno

Hodnoticí metody a kritéria
Kombinovaná zkouška

Podmínkou zápočtu je aktivní účast na cvičeních, úspěšné absolvování testů.
Doporučená literatura
  • Hopcroft, J. E., Ullman, J. D. Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979.
  • Jiří Vaníček. Teoretické základy informatiky. Praha, 2007. ISBN 9788090396241.


Studijní plány, ve kterých se předmět nachází
Fakulta Studijní plán (Verze) Kategorie studijního oboru/specializace Doporučený ročník Doporučený semestr
Fakulta: Fakulta přírodovědně-humanitní a pedagogická Studijní plán (Verze): Učitelství informatiky pro střední školy (20) Kategorie: Pedagogika, učitelství a sociální péče - Doporučený ročník:-, Doporučený semestr: Zimní