Martin Kot - Osobní stránka

Úvod do teoretické informatiky - šk. rok 2012/13

Obecné údaje

Garant:	Ing. Zdeněk Sawa, Ph.D.
Počet kreditů:	6
Ukončení:	Zkouška
Web předmětu:	http://www.cs.vsb.cz/jancar/TEORET-INF/teoret-inf.htm
Tutor:

Rozdělení bodů

Zápočet:	22b - písemná práce na 5. tutoriálu (19.4.2013) s příklady z oblasti logiky a teorie jazyků a automatů Podmínkou na zápočet je získání alespoň 7 bodů ze zápočtové písemky
Zkouška:	78b - písemná zkouška rozdělená na 3 části po 26 bodech (logika, jazyky a automaty, vyčíslitelnost a složitost). Z každé části je nutno získat alespoň 10 bodů pro úspěšné absolvování zkoušky. 0b - nepovinná ústní zkouška - možnost upravit body v obou směrech na základě konzultací nad písemkou

Upozornění
Aktuální důležité informace se budou objevovat pod záložkou Aktuálně. Různé užitečné materiály ke stažení najdete pod záložkou Ke stažení.
Sledujte i oficiální stránku předmětu, kde garant předmětu Ing. Zdeněk Sawa, Ph.D. zveřejňuje informace platné pro všechny studenty předmětu UTI.

Průběh setkání

Zde je uveden plánovaný průběh jednotlivých setkání. Jedná se o rámcový plán, informace v něm uvedené budou vždy po setkání v případě potřeby doplněny.

1. setkání (22.2.2013)	Přehled náplně kursu, informace o požadavcích k zápočtu a o zkoušce, časový plán. Výroková logika a predikátová logika 1. řádu.
2. setkání (8.3.2013)	Dokončení učiva z oblasti logiky, konkrétně odvozování důsledků, různé typy důkazů a rezoluční metoda.
3. setkání (22.3.2013)	Základní pojmy z oblasti formálních jazyků (abeceda, slovo, jazyk, operace na jazycích) Úvod do teorie konečných automatů.
4. setkání (5.4.2013)	Dokončení zbylých partií z teorie konečných automatů a regulárních výrazů. Bezkontextové gramatiky.
5. setkání (19.4.2013)	Zápočtová písemka. Diskuse řešení písemky, případně dokončení oblasti teorie jazyků a automatů nebo úvod do vyčíslitelnosti a složitosti.
6. setkání (3.5.2013)	Diskuse opravených písemek. Základní pojmy z oblasti vyčíslitelnosti a složitosti - konkrétně co se rozumí algoritmickými problémy, jaké existují modely výpočtu (Turingovy stoje a stroje RAM). Výpočetní složitost algoritmů a používání asymptotické notace.
7. setkání (17.5.2013)	Složitost problémů, třídy složitosti a algoritmicky nerozhodnutelné problémy. Informace o zkoušce.

Studijní literatura

Základní

P. Jančar: Úvod do teoretické informatiky (výukový text)
Online animace

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.