..:: Martin Kot ::..
Úvod do teoretické informatiky - šk. rok 2006/7
Obecné Aktuálně Ke stažení Projekty
 
Obecné údaje
Garant:  Ing. Zdeněk Sawa, Ph.D.
Počet kreditů:  6
Rozsah:  2/2/0/2
Ukončení:  Zkouška
Přednášející:  ,
Cvičící:  , , ,
, ,
 
Rozdělení bodů
Zápočet: 
  • 20b - písemná práce v polovině semestru z oblasti teorie jazyků a automatů
  • 10b - písemně vypracované řešení zadaného(ých) příkladu(ů) formou odborného textu (podrobnější informace na této stránce)
  • 5b - ústní předvedení řešení na cvičení
  • Bonusových 15b - písemné vypracování a ústní odreferování jednoho z vybraných obtížnějších příkladů. Za každý příklad má možnost získat body jen první úspěšný řešitel v ročníku.
  • Podmínkou na zápočet je odevzdání a předvedení řešení příkladu(ů) (uznáné cvičícím) a napsání semestrální písemky (bez minimálního limitu na získané body)
Zkouška: 
  • 65b - písemná zkouška
  • 0b - nepovinná ústní zkouška - možnost upravit body v obou směrech na základě konzultací nad písemkou
 
Anotace
Předmět je přehledovým úvodem do základních oblastí teoretické informatiky. Studenty seznámí s oblastmi formálních jazyků, automatů a algoritmické složitosti, včetně některých jejich aplikací pro řešení praktických programátorských úkolů. Konkrétně se jedná o použití regulárních výrazů, gramatik a konečných automatů při vyhledávání textu a pro syntaktickou analýzu. Dále jsou podány definice algoritmu a algoritmické složitosti problémů. Studenti se naučí rozlišovat lehké ("P") a těžké ("NP-úplné") algoritmické problémy. Na závěr kurzu jsou uvedeny některé modely paralelních a distribuovaných procesů a také zmíněny příklady nových trendů v teorii algoritmů.
 
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í            
LB260, LB288
J317
Moravec P.
LB278
J358
Polikarpov B.
LB282
J358
Polikarpov B.
   
               
LB280
J317
Delong P.
LB281
J317
Delong P.
   
               
LB286
K309
Kohut O.
LB276
K309
Kohut O.
   
úterý
LB287, LB267
J317
Moravec P.
LB266, LB284
J317
Moravec P.
LB285
J317
Moravec P.
   
LB277
J317
Moravec P.
       
středa          
Všichni
NA1
Kot M., Sawa Z.
     
LB279
D213
Raška Š.
LB291, LB290
D213
Raška Š.
čtvrtek
LB289
J317
Bača R.
LB283
J317
Bača R.
                   
pátek                            
 
Přednášky
Jazyky a Automaty
  • Elementární pojmy z teorie množin. Formální jazyky - zavedení pojmů.
  • Konečné automaty a regulární jazyky. Nedeterministické konečné automaty.
  • Vyhledávání řetězců, regulární výrazy.
  • Minimalizace automatů. Omezení konečných automatů, pumping lemma.
  • Bezkontextové jazyky.
  • Zásobníkové automaty.
Složitost Algoritmů
  • Výpočetní modely, Turingovy stroje, počítače a ekvivalence modelů.
  • Výpočetní složitost, asymptotická notace.
  • Matematické základy: Řešení rekurentních rovnic, asymptotické značení, kódování slov. Polynomiální redukce.
  • Třídy P a NP problémů, fenomén NP-úplnosti.
  • Některé NP-úplné problémy: SAT, barevnost, nezávislost, pokrytí.
 
Studijní literatura
Základní
Další
  • M. Chytil: Automaty a gramatiky, SNTL Praha, 1984.
  • 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.
Literatura není povinná, pouze doporučená, na přednáškách a cvičeních se dozvíte vše potřebné. (Toto není recitační kroužek, takže se nemusíte učit nazpaměť pasáže z knih. Lépe řečeno, nazpaměť se ani učit nesmíte, látce je třeba porozumět.)
Pokud máte k dispozici jiné úvodní knihy či skripta pro daný předmět, klidně je můžete používat. Jedna věc však platí pro všechny -- některé věci na přednášce se mohou líšit od literatury (například odchylky v definicích pojmů, které nejsou jednoznačně ustálené) a u zkoušky pak platí to, co bylo na přednášce.