Theoretical Computer Science

The course cannot be taken simultaneously with:

Theoretical Computer Science (Y36TIN)

The course is a substitute for:

Theoretical Computer Science (Y36TIN)

Lecturer:

Daniel Průša (gar.)

Tutor:

Karel Zimmermann, Daniel Průša (gar.)

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:

Time-table for winter semester 2011/2012:

Time-table is not available yet

Time-table for summer semester 2011/2012:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
Tue
Fri
Thu
Fri	roomKN:E-126 Zimmermann K. 09:15–10:45 (lecture parallel1 parallel nr.101) Karlovo nám. Trnkova posluchárna K5roomKN:E-126 Zimmermann K. 11:00–12:30 (lecture parallel1 parallel nr.102) Karlovo nám. Trnkova posluchárna K5roomKN:E-107 Průša D. 12:45–14:15 (lecture parallel1) Karlovo nám. Zengerova posluchárna K1

The course is a part of the following study plans:

• Softwarové inženýrství (compulsory elective course)
• Web a multimedia (compulsory elective course)