Název:	Teorie algoritmů a složitosti
Zkratka:	TAS
Typ:	povinný
Rozsah:	14 týdnů, týdně 2 hodiny přednášek + 2 hodiny seminárních cvičení
Kredity:	5
Způsob ukončení:	zkouška
Katedra:	katedra softwarového inženýrství FM TUL
Přednášející:	Doc. Mgr. Ing. Václav Záda, CSc.

 
Stručná anotace předmětu:

V rámci předmětu budou studenti seznámeni se dvěma tématickými okruhy – základy teorie algoritmů (též teorie vyčíslitelnosti) a úvod do teorie složitosti.

 
Témata přednášek:

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

 
Náplň cvičení:

Procvičuje se látka vyložená na předchozích 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ů atd.. 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.

 
Literatura:

Hopcroft, J.E.-Ullman,J.D.: Formálne jazyky a automaty. Bratislava, Alfa 1978. (překlad z angličtiny)

Kučera, L.: Kombinatorické algoritmy. Praha, SNTL 1989.Manna, Z.:

Manna, Z.: Matematická teorie programů. Praha, SNTL 1981.

Mareš, J.: Teoretická kybernetika. Praha, Vydavatelství ČVUT 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

 
Prerekvizity: -

Navazující:    -

 
Datum poslední změny: 21. 12. 2001