460-4005/01 – Theoretical Computer Science (TI)

Gurantor departmentDepartment of Computer ScienceCredits8
Subject guarantorprof. RNDr. Petr Jančar, CSc.Subject version guarantorprof. RNDr. Petr Jančar, CSc.
Study levelundergraduate or graduateRequirementChoice-compulsory
Year1Semestersummer
Study languageCzech
Year of introduction2010/2011Year of cancellation2014/2015
Intended for the facultiesFEIIntended for study typesFollow-up Master
Instruction secured by
LoginNameTuitorTeacher giving lectures
JAN59 prof. RNDr. Petr Jančar, CSc.
KOT06 Ing. Martin Kot, Ph.D.
MEC059 Ing. Ondřej Meca
S1A10 doc. RNDr. Petr Šaloun, Ph.D.
SAW75 doc. Ing. Zdeněk Sawa, Ph.D.
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 4+2
Combined Credit and Examination 10+0

Subject aims expressed by acquired skills and competences

On successful completion of the course, the student - is able to evaluate the possible extent of using the methods of finite automata, context-free grammars etc. by solving concrete practical problems, and is able to design, analyse and compare the respective solutions - is able to analyse computational complexity of practical problems, and to design algorithms for their solution - understands the notions like approximation algorithms, probabilistic algorithms, etc. and can evaluate the possibilities of their use in concrete practical situations

Teaching methods

Lectures
Tutorials
Project work

Summary

The course extends the theoretical background for computer science gained in bachelor studies, in particular in the areas of automata, languages, computability and complexity.

Compulsory literature:

Michael Sipser: Introduction to the Theory of Computation, Thomson 2006

Recommended literature:

Michael Sipser: Introduction to the Theory of Computation, Thomson 2006

Way of continuous check of knowledge in the course of semester

E-learning

Další požadavky na studenta

No additional requirements are placed on the student.

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

Lectures: Course introduction; overview and motivation. Basic notions from language theory. Finite automata. Nondeterministic finite automata and their realtion to the deterministic ones. Regular operations, regular languages. Closure properties of the class of regular languages. Regular expressions, relation to finite automata. Minimization of finite automata. Pumping lemma for regular languages and its use. Further variants of finite-state models (two-way finite automata, finite-state transducers,...) Context-free grammars and languages. Reduced grammars. Chomsky normal form. Pushdown automata. Relation between pushdown automata and context-free grammars. Closure properties of the class of context-free languages. Deterministic pushdown automata. Pumping lemma for context-free languages. General generative grammars. Chomsky hierarchy. Turing machines. Recursive and recursively enumerable languages. Complexity of algorithms. Random access machine (RAM). Asymptotic estimations, notation. Complexity analysis for selected (polynomial) algorithms. The worst-case vs. the average case. Problems, complexity classes, upper and lower bounds for problem complexity. Mutual polynomial simulation of reasonable computational models. Class PTIME, its robustness and significance. Class NPTIME. The P-NP question. Polynomial reducidability between problems. NP-completeness. Further time and space complexity classes and their interrelations. Provably intractable problems. Church-Turing thesis. Decidability and semi-decidability of problems. Recursive and recursively enumerable sets (languages). Recursive and partially recursive functions. Universal Turing machine. The diagonalization method. Undecidability of the halting problem. Recursive reducibility. Further undecidable problems. Rice's theorem. Brief introduction to approximation algorithms, probabilistic algorithms, parallel and distributed algorithms. Exercises: Basic language operations, in particular the quotient operations. Design of finite automata for simple languages. Construction of more complex automata from simpler ones. Algorithms for transforming into the normal form and for checking the isomorphism of finite automata. Algorithm of minimalization. Proofs of nonregularity of concrete languages. Design of nondeterministic finite automata; their transforming to deterministic ones. Regular expressions as a means for description of regular languages. Transformations among finite automata, regular expressions and regular grammars. Closure properties of the class of regular languages. Design of concrete context-free grammars. Examples of transforming ambiguous grammars to nonambiguous ones. Algorithms for reduction and epsilon-rules removing. Design of pushdown automata. Transformations between context-free grammars and pushdown automata. Design of deterministic pushdown automata. Closure properties of the class of context-free languages. Transformation into Chomsky normal form. Proofs of non-context-freeness by help of pumping lemma. Construction of Turing machines. Asymptotic growth of concrete functions. Design and analysis of complexity of concrete (polynomial) algorithms. Some concrete applications of general methods for design of polynomial algorithms. Mutual simulation between concrete computational models. Design of nondeterministic (polynomial) algorithms. Polynomial reducibility among concrete problems. Showing membership of concrete problems in PTIME, NPTIME, PSPACE, NPSPACE; demonstrating NP- and PSPACE-hardness. Construction of the universal Turing machine. Proofs of undecidability of concrete problems. Applications of Rice's Theorem. Selected exercises in the area of approximation and probabilistic algorithms. Projects: Each student will be assigned a selected topic related to the contents of the course (at the beginning of semester). The student will study the topic from the recommended or freely chosen sources. He/she will then elaborate his/her own text which will consicely explain the main ideas, within the given deadline and in (at least) the minimal given extent. The author will personally present the topic at some exercise session or in another way determined by the lecturer.

Conditions for subject completion

Full-time form (validity from: 2010/2011 Winter semester, validity until: 2014/2015 Summer semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Exercises evaluation and Examination Credit and Examination 100 (100) 51
        Exercises evaluation Credit 35 (35) 9
                Credit written test Written test 24  8
                Report Other task type 11  1
        Examination Examination 65  25
Mandatory attendence parzicipation:

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
2014/2015 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Choice-compulsory study plan
2014/2015 (N2647) Information and Communication Technology (2612T059) Mobile Technology P Czech Ostrava 1 Choice-compulsory study plan
2014/2015 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Choice-compulsory study plan
2014/2015 (N2647) Information and Communication Technology (2612T059) Mobile Technology K Czech Ostrava 1 Choice-compulsory study plan
2013/2014 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Choice-compulsory study plan
2013/2014 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Choice-compulsory study plan
2013/2014 (N2647) Information and Communication Technology (2612T059) Mobile Technology P Czech Ostrava 1 Choice-compulsory study plan
2013/2014 (N2647) Information and Communication Technology (2612T059) Mobile Technology K Czech Ostrava 1 Choice-compulsory study plan
2012/2013 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Choice-compulsory study plan
2012/2013 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Choice-compulsory study plan
2012/2013 (N2647) Information and Communication Technology (2612T059) Mobile Technology P Czech Ostrava 1 Choice-compulsory study plan
2012/2013 (N2647) Information and Communication Technology (2612T059) Mobile Technology K Czech Ostrava 1 Choice-compulsory study plan
2011/2012 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Choice-compulsory study plan
2011/2012 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Choice-compulsory study plan
2011/2012 (N2647) Information and Communication Technology (2612T059) Mobile Technology P Czech Ostrava 1 Choice-compulsory study plan
2011/2012 (N2647) Information and Communication Technology (2612T059) Mobile Technology K Czech Ostrava 1 Choice-compulsory study plan
2010/2011 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Choice-compulsory study plan
2010/2011 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Choice-compulsory study plan
2010/2011 (N2647) Information and Communication Technology (2612T059) Mobile Technology P Czech Ostrava 1 Choice-compulsory study plan
2010/2011 (N2647) Information and Communication Technology (2612T059) Mobile Technology K Czech Ostrava 1 Choice-compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner