Theoretical Computer Science

Lecturer:

Tutor:

Supervisor:

Department of Cybernetics

Synopsis:

The course provides a basic overview of the concepts and tasks of graph theory, focusing primarily on algorithmic questions and solutions to graph problems, effectively using knowledge of programming techniques. The presented graph algorithms include depth-first and breadth-first search, algorithms of Jarnik and Boruvka (minimum spanning tree), Dijsktra (shortest path) or Ford-Fulkerson (maximum flow in networks). Additional important topics covered by the course are the theory of formal languages (finite automata, grammars, Chomsky hierarchy), computability (Turing machines, undecidable problems) and computational complexity (classes P and NP, NP-completeness).

Requirements:

Basic knowledge of programming.

Syllabus of lectures:

1. Theoretical models, undirected graphs, basic properties

2. Directed graphs, strong connectivity, topological sort

3. Graphs representation in memory, depth-first and breadth-first traversals

4. Dominating and independent sets, distance, trees, spanning trees, circles

5. Minimum spanning trees, binary trees, algorithms of Boruvka and Jarnik, Huffman coding

6. Shortest path algorithms, dynamic programming

7. Flows in networks, maximum network flow

8. State space searching, heuristic search

9. Regular languages and finite automata

10. Grammars, Chomsky hierarchy, context-free languages

11. Turing Machines - structure and behavior

12. Generalization of Turing machines, undecidable problems

13. Complexity classes P and NP, NP-completeness

14. Reserved

Syllabus of tutorials:

1. Using basic tools of mathematics (proof, induction, recurrence)

2. Operational complexity of algorithms, calculations with recurrences

3. Undirected graphs - basic properties

4. Graph traversals, decomposition into components

5. Directed graphs - basic properties, depth-first search

6. Decomposition into strong components

7. Dominance, independence, trees

8. Spanning trees, minimum spanning trees

9. Shortest paths

10. Application of dynamic programming

11. Maximal flow in network, heuristic search algorithms

12. Regular languages and finite automata

13. Non-determinism

14. Assessment

Study Objective:

The course aims to give theoretical foundations of computer science and to develop abstract thinking in the design of algorithms. Graphs are used as the basic structure - for their easy conceivability and wide applicability in practical problems. The course can be seen as preparation for lectures, which include advanced topics in theoretical computer science.

Study materials:

1. Cormen, T.H. et al. : Introduction to Algorithms. Cambridge, Mass.: MIT

Press. 1990

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans: