..:: Martin Kot ::..
Úvod do teoretické informatiky - šk. rok 2007/8
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
Oficiální stránka:  http://www.cs.vsb.cz/sawa/uti/
Přednášející:  , ,
Cvičící:  , , ,
, , ,
,
 
Rozdělení bodů
Zápočet: 
  • 2x10b - písemné práce v průběhu semestru, jedna z oblasti logiky a druhá z teorie jazyků a automatů
  • 10b - písemně vypracované řešení zadaného 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 získání alespoň 10 bodů v součtu referátu a zápočtových písemek
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
Studenti se seznámí se základy výrokové a predikátové logiky. Probereme pojem přímého a nepřímého důkazu a základní metody pro důkaz logické pravdivosti a platnosti úsudku. Dále se studenti seznámí se základními oblastmi formálních jazyků a automatů (regulární a bezkontextové jazyky, konečné a zásobníkové automaty). Ve třetí části budou studenti seznámeni se základy teorie algoritmů (složitost algoritmů a problémů, NP-úplnost, algoritmická nerozhodnutelnost).
 
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í                    
LB291
K309
Raška Š.
LB289
K309
Raška Š.
úterý    
LB286
K309
Bača R.
LB288
K309
Bača R.
   
LB284
K309
Polikarpov B.
LB295, LB271
K309
Polikarpov B.
   
středa                
LB294, LB270
D210
Číhalová M.
LB287
D209
Dráždilová P.
   
         
Všichni
PorNA1
Sawa Z., Kot M.
 
LB282, LB252
D209
Dráždilová P.
LB285
D210
Číhalová M.
   
čtvrtek    
LB272
K309
Moravec P.
   
LB292
J360
Kuchař Š.
LB293, LB260
J360
Kuchař Š.
       
   
LB283
K308
Dráždilová P.
LB280
K309
Moravec P.
LB290
J358
Kučera T.
LB281, LB251
J358
Kučera T.
       
pátek                            
sobota                            
 
Přednášky
Matematická logika
  • Úvod. Základy teorie množin, relací a funkcí.
  • Analýza vět přirozeného jazyka v jazyce predikátové nebo výrokové logiky.
  • Odvozování důsledků. Množinové / sémantické důkazy.
  • Základy rezoluční metody.
Jazyky a Automaty
  • Formální jazyky. Konečné automaty.
  • Konstrukce konečných automatů. Nedeterministické konečné automaty.
  • Převod nedeterministických konečných automatů na deterministické. Regulární výrazy.
  • Bezkontextové gramatiky jazyky.
Vyčíslitelnost a složitost
  • Algoritmické problémy. Modely výpočtu.
  • Asymptotická notace. Složitost algoritmů.
  • Složitost problémů. Třídy složitosti. Převody mezi problémy. Třída NPTIME.
  • Algoritmicky nerozhodnutelné problémy.
 
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.
  • Ding-Zhu Du, Ker-I Ko: Problem Solving in Automata, Languages, and Complexity, Wiley, 2001.
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.