Martin Kot - Personal webpage

Introduction to theoretical computer science

General facts

Guarantee:	Ing. Zdeněk Sawa, Ph.D.
Number of credits:	6
Completition:	Exam
Web page:	http://www.cs.vsb.cz/jancar/TEORET-INF/teoret-inf.htm
Lecturers:

Division of points

Accreditation:	22pts - term written exam Condition for accreditation is to obtain at least 7 points
Exam:	78pts - written exam 10pts from each of 3 parts of the exam is required. 0pts - optional oral exam - consultation of written exam

Notice
Also informations under tabs Actual and Download are valid for combined students.
Informations on official web page may be also useful.

Tutorials

Preliminary plan of tutorials, it will be updated according to reality.

1^st tutorial	Informations about course and its organization. Propositional logic and 1^st order predicate logic.
2^nd tutorial	Deduction, proofs, resolution method.
3^rd tutorial	Formal languages, language operations. Finite automata.
4^th tutorial	Regular expressions. Context free grammars.
5^th tutorial	Term written exam. Discussion about solution of the exam.
6^th tutorial	Discussion about corrected exams. Introduction to computability and complexity. Complexity of algorithms, asymptotic notation.
7^th tutorial	Complexity of problems, complexity classes. Informations about exam.

Study literature

Basic

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

Other

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.