..:: Martin Kot ::..
Úvod do teoretické informatiky - šk. rok 2005/6
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ímonday              
D210
LB285
Raška Š.
D210
LB281
Raška Š.
 
D210
LB289
Polikarpov B.
úterýtuesday    
D209
LB278
Delong P.
D209
LB279
Delong P.
               
   
D210
LB275
Moravec P.
D210
LB270
Moravec P.
       
D210
LB287
Polikarpov B.
   
středawednesday
D210
LB288
Moravec P.
D210
LB283
Moravec P.
D210
LB280
Raška Š.
               
čtvrtekthursday  
B5
LB276-81
Kot M.
C3
LB270, LB275, LB282-9
Sawa Z.
                 
 
D210
LB284
Bača R.
D210
LB276
Bača R.
   
D210
LB277
Bača R.
D210
LB282
Kohut O.
D210
LB286
Kohut O.
 
pátekfriday                            
 
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.