..:: Martin Kot ::..
Teoretická informatika - šk. rok 2015/16
Obecné Aktuálně Ke stažení Referáty Kombinované studium
Obecné údaje
Garant:  Prof. RNDr. Petr Jančar, CSc.
Počet kreditů:  6
Rozsah:  3/3/0/0
Ukončení:  Zkouška
Web předmětu:  http://www.cs.vsb.cz/jancar/TEORET-INF/teoret-inf.htm
Přednášející: 
Cvičící:  , ,
 
Rozdělení bodů
Zápočet: 
  • 21b - krátká písemka
  • 10b - písemně vypracované a ústně předvedené řešení zadaného referátu (podrobnější informace na této stránce)
  • 7b - aktivita na cvičení
  • Podmínkou na zápočet je předvedení referátu (uznané cvičícím za dostatečné) a získaných alespoň 7 bodů z 21 z písemky.
Zkouška: 
  • 62b - písemná zkouška (minimálně je nutné získat 25b pro úspěšné absolvování předmětu)
  • 0b - nepovinná ústní zkouška - možnost upravit body v obou směrech na základě konzultací nad písemkou
 
Anotace
Kurs prohlubuje a rozšiřuje teoretické základy v oblasti formálních jazyků, automatů, gramatik, výpočtových problémů a algoritmů, které student měl v základní formě nabýt v bakalářském studiu.
 
Rozvrh hodin
7:15
8:00
8:00
8:45
9:00
9:45
9:45
10:30
10:45
11:30
11:30
12:15
12:30
13:15
13:15
14:00
14:15
15:00
15:00
15:45
16:00
16:45
16:45
17:30
17:45
18:30
18:30
19:15
pondělí      
EC2
Jančar P.
EB330
Meca O.
         
úterý      
EB230
Kot M.
   
EB330
Kot M.
     
středa            
EB330
Kot M.
         
čtvrtek                    
EB331
Šurkovský M.
 
pátek                            
sobota                            
 
Přednášky
Jazyky a Automaty
  • Úvod ke kursu: celkový přehled. Základní pojmy z oblasti formálních jazyků. Konečné automaty a jazyky jimi rozpoznávané. Modulární návrh konečných automatů.
  • Dosažitelné stavy u konečných automatů, normovaný tvar. Minimální automaty a algoritmus minimalizace. Regulární a neregulární jazyky; Charakterizace regulárních jazyků umožňující důkazy neregularity.
  • Nedeterministické konečné automaty; jejich uplatnění v návrhu deterministických konečných automatů. Regulární operace. Regulární výrazy jako prostředek popisu regulárních jazyků.
  • Ekvivalence konečných automatů, regulárních výrazů a regulárních gramatik. Uzávěrové vlastnosti třídy regulárních jazyků. Další varianty konečně stavových modelů (dvoucestné konečné automaty, konečně stavové převodníky, ...).
  • Bezkontextové gramatiky a jazyky. Ilustrace významu bezkontextových gramatik pro (syntaxí řízený) překlad, speciálně na gramatice generující regulární výrazy. Jednoznačné gramatiky. Redukované a nevypouštějící bezkontextové gramatiky.
  • Zásobníkové automaty. Vztah mezi zásobníkovými automaty a bezkontextovými gramatikami. Deterministické zásobníkové automaty. Uzávěrové vlastnosti třídy bezkontextových jazyků.
  • Chomského normální forma bezkontextových gramatik. Pumping lemma pro bezkontextové jazyky a jeho použití. Obecné generativní gramatiky. Turingovy stroje. Chomského hierarchie.
Vyčíslitelnost a složitost
  • Složitost algoritmu. Model RAM. Asymptotické odhady růstu funkcí, značení. Obecné metody návrhu (efektivní prohledávání, hltavé algoritmy, ...) a analýza složitosti vybraných (polynomiálních) algoritmů.
  • Další metody návrhu polynomiálních algoritmů (rozděl a panuj, dynamické programování, ...). Problémy, třídy složitosti problémů, horní a dolní odhady složitosti problémů. Vzájemná polynomiální simulace rozumných výpočetních modelů. Třída PTIME, její robustnost, význam.
  • Nedeterministické Turingovy stroje. Třída NPTIME. Otázka `P=NP~?'. Polynomiální převeditelnost mezi problémy. NP-úplnost a konkrétní NP-úplné problémy.
  • Další třídy časové i prostorové složitosti a jejich vzájemné vztahy. Dokazatelně nezvládnutelné problémy. Church-Turingova teze. Rozhodnutelnost a částečná rozhodnutelnost problémů.
  • Univerzální Turingův stroj. Metoda diagonalizace, nerozhodnutelnost problému zastavení. Algoritmická převeditelnost, další nerozhodnutelné problémy. Riceova věta.
  • Nástin problematiky aproximačních, pravděpodobnostních, paralelních a distribuovaných algoritmů.
 
Studijní literatura
Základní
Další
  • T. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms. The MIT Press, 1990.
  • John E. Hopcroft a Jeffrey D. Ullman: Formálne jazyky a automaty. Alfa Bratislava 1978.
  • J. Gruska: Foundation of Computing, International Thomson Computer Press 1997.
  • D. Kozen: Automata and Computability, Undergraduate Text in Computer Science, Springer Verlag 1997.
  • M. Sipser: Introduction to the Theory of Computation. PWS Publishing Company 1997.