Theoretical Computer Science
Code | Completion | Credits | Range |
---|---|---|---|
X36TIN | Z,ZK | 5 | 2+2s |
- The course is a substitute for:
- Theoretical Computer Science (Y36TIN)
- Lecturer:
- Josef Kolář, Neurčen (gar.), Andrej Chu, Daniel Průša, Karel Zimmermann
- Tutor:
- Josef Kolář, Neurčen (gar.), Andrej Chu, Daniel Průša, Karel Zimmermann
- 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:
-
Final exam grading is in part derived from the quality of presented homework and activity at seminars.
- Syllabus of lectures:
-
1. Theoretical models, undirected graphs, basic properties
2. Directed graphs, strong connectivity, topological sort
3. Graph representation, breadth-first and depth-first traversals
4. Euler's graphs, dominating and independent sets, distance
5. Trees and spanning trees, circuits, minimum spanning trees, binary trees
6. Algorithms of Boruvka and Jarník, Huffman's coding
7. Shortest paths algorithms, dynamic programming
8. Flow networks, maximum flow in network
9. General problem solving, state space, heuristic search
10. Regular languages and finite automata
11. Turing machines - structure and behavior
12. Generalized 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, homework
5. Directed graphs - basic properties, depth-first search
6. Decomposition into strong components, homework consultation
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, homework consultation
14. Assessment
- Study Objective:
- Study materials:
-
1. Kolář, J.: Theoretical Computer Science. Prague: CTU Publishing House. 1998
2. 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 - The course is a part of the following study plans:
-
- Computer Technology- structured studies (compulsory course)
- Manažerská informatika (elective specialized course)
- Inteligentní systémy (elective specialized course)