SubjectsSubjects(version: 821)
Course, academic year 2017/2018
   Login via CAS
Introduction to Complexity and Computability - NTIN090
English title: Základy složitosti a vyčíslitelnosti
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2017
Semester: winter
E-Credits: 5
Hours per week, examination: winter s.:2/1 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Additional information:
Guarantor: doc. RNDr. Ondřej Čepek, Ph.D.
RNDr. Petr Kučera, Ph.D.
Class: Informatika Mgr. - učitelské studium informatiky
Informatika Mgr. - Softwarové systémy
Informatika Mgr. - Matematická lingvistika
M Mgr. MSTR > Povinně volitelné
Classification: Informatics > Theoretical Computer Science
Interchangeability : {Složitost I a Vyčíslitelnost I}
Incompatibility : NTIN062, NTIN064
Annotation -
Last update: T_KTI (28.04.2015)

This is a basic course on the theory of algorithms, computability and computational complexity. Roughly the first half of the course is devoted to the introduction to computability theory: Turing machines. Computable functions. Recursive and recursively enumerable languages and sets. Undecidable problems. The second half of the course is devoted to the study of space and time complexity classes: Equivalence of PSPACE and NPSPACE. Deterministic hierarchy theorems. Class NP. Polynomial reducibility among problems. Proofs of NP- completeness. Approximation algorithms and approximation schemes.
Aim of the course -
Last update: RNDr. Petr Kučera, Ph.D. (04.09.2014)

To teach basics of complexity theory and theory of computation.

Course completion requirements -
Last update: RNDr. Petr Kučera, Ph.D. (09.10.2017)

To finish the subject it is necessary to get the credit and then to pass the exam. To get get the credit, it is necessary to acquire a given number of points for homework which are being solved during the semester. In case a student does not have enough points at the end of semester, it is possible to get some additional points for additional homework. Due to the nature of conditions for getting the credit it is not possible to have substitute dates of obtaining the credit. It is necessary to have the credit before coming to exam.

Literature -
Last update: RNDr. Petr Kučera, Ph.D. (28.04.2015)

Lecture web pages (lecture presentation can be found there):

Sipser, M. Introduction to the Theory of Computation. Vol. 2. Boston: Thomson Course Technology, 2006.

Demuth O., Kryl R., Kučera A.: Teorie algoritmů I, II. SPN, 1984, 1989 (Only in Czech)

Soare R.I.: Recursively enumerable sets and degrees. Springer-Verlag, 1987

Odifreddi P.: Classical recursion theory, North-Holland, 1989

Garey, Johnson. Computers and intractability - a guide to the theory of NP-completeness, W.H. Freeman 1978

Arora S., Barak B.: Computational Complexity: A Modern Approach. Cambridge University Press 2009 (Draft available online).

Requirements to the exam -
Last update: RNDr. Petr Kučera, Ph.D. (08.10.2017)

The exam has two parts, the written part and the oral part. The written part precedes the oral part and in case when a student fails to pass the written part, the exam does not continue with the oral part. In case the exam is finished due to failing the oral part, it is necessary to pass both the written part and the oral part at the next exam. Grade depends on the number of points given for both parts.

The written part consists of three assignments which correspond to the lecture syllabus. These assignments are similar to the exercises which are given during the practicals.

The requirements of the oral part correspond to the lecture syllabus to extent which was presented on the lecture during the semester. A list of possible questions is published at the web pages related to the subject before the exam period starts.

Syllabus -
Last update: RNDr. Petr Kučera, Ph.D. (28.04.2015)

1) Turing machines and their variants, Church-Turing thesis.

2) Halting problem

3) RAM and their equivalence with Turing machines. Algorithmically computable functions.

4) Recursive and recursively enumerable languages and sets and their properties.

5) 1-reducibility and m-reducibility, 1-complete and m-complete sets.

6) Rice's theorem.

7) Nondeterministic Turing machines, basic complexity classes, classes P, NP, PSPACE, EXP.

8) Savitch's theorem - equivalence of PSPACE and NPSPACE.

9) Deterministic space and time hierarchy theorems.

10) Polynomial reducibility among problems. NP-hardness and NP-completeness.

11) Cook-Levin theorem, examples of NP-complete problems, proofs of NP-completeness.

12) Pseudopolynomial algorithms and strong NP-completeness.

13) Approximations of NP-hard optimization problems. Approximation algorithms and schemes.

14) Classes co-NP and #P.

Charles University | Information system of Charles University |