Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2024/2025

Complexity Theory

The course is not on the list Without time-table
Code Completion Credits Range
01TSLO ZK 3 3+0
Garant předmětu:
Lecturer:
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. NP-completeness 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 0-201-02988-X

Note:
Further information:
No time-table has been prepared for this course
The course is a part of the following study plans:
Data valid to 2024-03-29
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet12074805.html