Theoretical Computer Science

The course cannot be taken simultaneously with:

Teoretická informatika (Dálk.) (-D36TI)

Lecturer:

Tutor:

Supervisor:

Department of Computer Science and Engineering

Synopsis:

The course reinforces abstraction and proof techniques in discrete structures presenting basic notions and problems of graph theory. Standard graph algorithms (as e.g. breadth-first and depth-first graph traversal, shortest paths algorithms of Dijkstra, Bellman-Ford, Floyd-Warshall, and Johnson, shortest spanning tree algorithms of Kruskal-Boruvka and Prim-Jarnik, max-flow algorithm of Ford-Fulkerson, etc.) are introduced and their complexity discussed. The course includes greedy algorithms and dynamic programming technique, complexity theory (P and NP complexity classes, NP-completeness), search problems in artificial intelligence, mathematical models of programs and computations (finite automata, Turing machines).

Requirements:

Syllabus of lectures:

Syllabus of tutorials:

Study Objective:

Study materials:

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans: