Vyučující
|
-
Březina Jan, doc. Mgr. Ph.D.
-
Kosková Třísková Lenka, Ing. Ph.D.
|
Obsah předmětu
|
<u>Získané kompetence:</u> Získané znalosti představují skutečný základ teoretické informatiky a jsou stejně potřebné, jako studium Českého jazyka na středních školách, ačkoli se ze studentů nestávají spisovatelé. Předmět sám poskytuje přehled o algoritmicky možných konstrukcích a o existenci problémů, které nelze zvládnout žádnou výpočetní technikou. Dále je studována efektivnost algoritmů z hlediska časové a prostorové náročnosti pro počítač. <u>Témata přednášek:</u> Algoritmy a algoritmicky vyčíslitelné funkce. Churchova teze. Markovovy normální algoritmy. Turingovy stroje, Postovy stroje a konečné stroje se zásobníky. Ekvivalence strojů. Vícepáskové Turingovy stroje. Primitivně rekurzivní funkce. Rekurzivní funkce. Robinsonova věta. Ackermannova funkce. Operátor minimalizace. Rekurzivní a rekurzivně spočetné množiny a predikáty. Turingova věta. Postova věta. Universální Turingův stroj. Formální jazyky. Aritmetizace, Gödelova čísla. Třídy problémů typu ano/ne, problém zastavení pro Turingovy stroje. Kleeneho věta o normální formě. Problém ekvivalence pro semi-Thueovy systémy, Postův problém přiřazení. Produktivní a kreativní množiny. Pojem složitosti, časová a paměťová složitost. Úlohy řešitelné v polynomiálně omezeném čase, úlohy řešitelné nedeterministicky v polynomiálně omezeném čase. NP-úplné problémy. Nedeterministické stroje. Pravděpodobnostní analýza algoritmů. <u>Náplň cvičení:</u> Procvičuje se látka vyložená na přednáškách. V tématickém okruhu teorie algoritmů budou probrány konkrétní příklady konstrukce Turingových strojů, Postových strojů a strojů se zásobníky. V tématickém okruhu teorie složitosti budou vybrány příklady algoritmů z oblasti kombinatoriky, úlohy o srovnávání, o uspořádání, určení maxima a minima, třídění ap.. Průběžně budou poskytovány informace o zdrojích na internetu, které se vztahují k aktuálně probírané látce.
|
Studijní aktivity a metody výuky
|
Monologický výklad (přednáška, prezentace, vysvětlování)
- Účast na výuce
- 56 hodin za semestr
|
Výstupy z učení
|
Předmět reprezentuje úvod do dvou základních okruhů teoretické informatiky. Formulace matematických upřesnění pojmu algoritmus (efektivní vyčíslitelnost) a studium role, kterou pojem algoritmu hraje, je jedním z významných přínosů matematické logiky. Od dob svého vzniku se teorie algoritmů neobyčejně rozvinula a v dnešní době představuje teoretický základ vzdělání každého informatika.
Získané znalosti představují skutečný základ teoretické informatiky. Předmět sám poskytuje přehled o algoritmicky možných konstrukcích a o existenci problémů, které nelze zvládnout výpočetní technikou. Dále je studována efektivnost algoritmů z hlediska časové a prostorové náročnosti pro počítač.
|
Předpoklady
|
Podmínka registrace: není stanovena
|
Hodnoticí metody a kritéria
|
Kombinovaná zkouška
Turingovy stroje a jejich ekvivalenty, rekurzivní funkce, Robinsonova věta, aritmetizace, Gödelova čísla, problém zastavení, časová a paměťová složitost, nedeterministické stroje, pravděpodobnostní analýza. Základy logiky.
|
Doporučená literatura
|
-
Černý, M. Výpočty. Tři svazky. Professional Publishing, Praha, 2012.
-
Kučera, L. Kombinatorické algoritmy. Praha, SNTL 1989.
-
Mareš, J. Jazyky, gramatiky a automaty. Praha. Vydavatelství ČVUT, 2004.
-
MAREŠ, J. Teoretická kybernetika. ČVUT Praha, 1997.
-
Morávek, I. Složitost výpočtů a optimální algoritmy. Praha, Academia 1984.
-
Rogers, H. Theory of Recursive Functions and Effective Computability. New York.
-
Švejdar, V. Logika, neúplnost, složitost a nutnost. Praha, Academia, 2002.
|