Complexity Theory
Code  Completion  Credits  Range  Language 

01TSLO  ZK  3  3+0  Czech 
 Lecturer:
 Vladan Majerech (guarantor)
 Tutor:
 Supervisor:
 Department of Mathematics
 Synopsis:

The course is devoted to incorporation of complexity questions during algorithm development, introduction to NP completeness and generally to complexity classes of deterministic or nondeterministic Turing machines bounded by time or space. Emphasis is placed on mutual relations among these classes. Aside from nondeterministic classes we examine probability classes. Class of interactive protocols is presented at the end of lecture course.
 Requirements:
 Syllabus of lectures:

1.Complexity dimensions  expected, randomized, amortized; basic data structures 2. Divide & conquer  recurrence, Strassen algorithm, sorting (+lower bound), median algorithm, prune and search 3. Fibonacci heaps, Dijkstra algorithm, minimum spanning tree  Fredman+Tarjan algorithm, Kruskal algorithm and DFU. 4. NPcompleteness and basic transforms (SAT, tiling, clique) 5. Further NP complete examples (Hamiltonian paths and cycles, knapsack) Fully polynomial approximation scheme for the knapsack problem 6. Turing machines, linear compression and speedup, tape reductions, universal machines 7. Constructability, inclusions among complexity classes, hierarchy theorems 8. Padding argument, Borodin?s theorem, Blum?s theorem 9. Generalised nondeterminism and probability classes 10. Polynomial hierarchy, complete problems. 11. Interactive protocols
 Syllabus of tutorials:
 Study Objective:

Learn to incorporate complexity questions during algorithms development, learn to think about lower bounds of problem?s complexities. Learn basic relations among complexity classes.
 Study materials:

Key references:
[1] J. L. Balcázar, J. Díaz, J Gabarró: „Structural Complexity I“, Springer  Verlag Berlin Heidelberg New York London Paris Tokyo 1988
Recommended references:
[2] Hopcroft, Ullmann „Introduction to Automata Theory and Computing“, ISBN 020102988X
 Note:
 Timetable for winter semester 2019/2020:
 Timetable is not available yet
 Timetable for summer semester 2019/2020:
 Timetable is not available yet
 The course is a part of the following study plans:

 Matematické inženýrství (elective course)
 Matematická informatika (compulsory course of the specialization)
 Aplikace softwarového inženýrství (elective course)