|
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.
|