Předmět: Teorie algoritmů a složitosti

« Zpět
Název předmětu Teorie algoritmů a složitosti
Kód předmětu MTI/TAS
Organizační forma výuky Přednáška + Cvičení
Úroveň předmětu Magisterský
Rok studia nespecifikován
Semestr Zimní
Počet ECTS kreditů 5
Vyučovací jazyk Čeština
Statut předmětu Povinný, Povinně-volitelný
Způsob výuky Kontaktní
Studijní praxe Nejedná se o pracovní stáž
Doporučené volitelné součásti programu Není
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.


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 mechatroniky, informatiky a mezioborových studií Studijní plán (Verze): Informační technologie (2013) Kategorie: Informatické obory 2 Doporučený ročník:2, Doporučený semestr: Zimní