Předmět Teorie algoritmů a složitosti (MTI / TAS)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu MTI / TAS - Teorie algoritmů a složitosti, Fakulta mechatroniky a MIS, Technická univerzita v Liberci (TUL).

Materiál	Typ	Datum	Počet stažení

Obsah

Přednášky:1. Úvod do vyčíslitelnosti. -definovatelné funkce, Churchova teze. Konečné stroje, akceptování slov, ekvivalentní stroje.2. Definice Turingova stroje, ekvivalentní definice. Konfigurace, akceptování slov. Vícepáskové stroje.3. Postovy stroje, věta o ekvivalenci Turingových a Postových strojů, důkaz věty.4. Konečné stroje se zásobníky. Věta o ekvivalenci Turingových strojů a strojů se dvěma zásobníky, důkaz.5. Nedeterministické konečné stroje, porovnání s deterministickými stroji.6. Kódování Turingových strojů. Turingovy stroje jako algoritmy. Problém zastavení - věta a důkaz. Alternativní problémy.7. Parciální rozhodnutelnost tříd problémů. Univerzální Turingův stroj. Postův problém přiřazení.8. Aplikace Postova problému. Jazyky typu 0 a Turingovy stroje. Problém zániku matic.9. Algoritmicky nerozhodnutelné problémy pro kontextové a bezkontextové jazyky (jazyky typu 1 a 2).10. Rekurzivní a rekurzivně spočetné množiny, rekurzivní a primitivně rekurzivní funkce a predikáty.11. Predikátová logika 1. řádu. Formule, termy, pravdivost formulí, principy odvozování. Existence axiomatických systémů.12. Predikátová logika 2. řádu. Termy, formule, sémantika, logicky pravdivé formule. Neexistence formálního systému odvozování.13. Gödelova věta o parciální nerozhodnutelnosti logiky 2. řádu. Churchova věta o nerozhodnutelnosti, ale parciální rozhodnutelnosti predikátové logiky 1. řádu.14. Časová a paměťová složitost. Úlohy řešitelné v polynomiálně omezeném čase, NP-úplné problémy.Cvičení:1. Opakování Nerodovy věty, jazyky nerozpoznatelné konečnými automaty. Zadání vybraných typů úloh.2. Navrhování jednoduchých Turingových strojů.3. Konstrukce jednoduchých Postových strojů.4. Návrhy konečných strojů s jedním, resp. dvěma zásobníky. Stroje bez zásobníků jako ekvivalenty konečných automatů.5. Návrhy nedeterministických strojů. Porovnání s deterministickými.6. Ekvivalence Turingových, Postových strojů a strojů se dvěma zásobníky. Porovnání na konkrétních úlohách.7. Časová složitost algoritmů, konkrétní úlohy, demonstrace na TS.8. Semi-Thueův problém. Rozbor algoritmu redukce.9. Aplikace Postova problému na úlohách.10. Metoda redukce vybraných tříd problémů typu ANO/NE.11. Tablová metoda dokazování v logice - výhodnost algoritmu oproti klasické tabulkové metodě výrokové logiky. Řešení úloh.12. Tablová metoda logiky 1. řádu. Formulace slovně zadaných úloh, přepis do jazyka logiky a dokazování formulí. Dokazatelnost.13. Přepis slovních úloh do jazyka logiky a dokazování formulí.14. Časová a prostorová náročnost úloh, zápočty.

Získané způsobilosti

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

Literatura

Mareš, J. Jazyky, gramatiky a automaty. Praha. Vydavatelství ČVUT, 2004. Kučera, L. Kombinatorické algoritmy. Praha, SNTL 1989. Švejdar, V. Logika, neúplnost, složitost a nutnost. Praha, Academia, 2002. Morávek, I. Složitost výpočtů a optimální algoritmy. Praha, Academia 1984. MAREŠ, J. Teoretická kybernetika. ČVUT Praha, 1997. Rogers, H. Theory of Recursive Functions and Effective Computability. New York. Černý, M. Výpočty. Tři svazky. Professional Publishing, Praha, 2012.

Požadavky

Podmínkou zápočtu je aktivní účast na cvičeních, úspěšné absolvování testů. Zkouška je písemná a ústní.

Garant

doc. Mgr. Ing. Václav Záda, CSc.

Vyučující

doc. Mgr. Ing. Václav Záda, CSc.Ing. Jan Strnaddoc. Mgr. Ing. Václav Záda, CSc.