Theory of Algorithms

Aims of the course

The student is introduced to the basics of the theory of algorithms and to the most important algorithms for searching and optimization.

Course syllabus

1. Intuitive notion of an algorithm
2. Formalizations
2.1. Recursive functions
2.2. Turing machines
2.2.1. Turing computability
2.2.2. Universal Turing machine
3. Church thesis
4. Decidable and semidecidable sets
5. Time complexity
5.1. Class P, hard problems
5.2. Nondeterministic Turing machines
5.3. Class NP
5.4. NP-completeness
6. Various sorting algorithms and their time complexity
7. Searching for the minimal path in a directed graph
7.1. Dijkstra's algorithm
7.2. Directed search (A* algorithm)
8. AND/OR-graphs, solution subgraphs, optimal solution subgraphs
9. Searching for solution subgraphs
9.1. AO* algorithm
9.2. Algorithm for explicit AND/OR graphs
10. AND/OR graphs and project management
11. Hypergraphs, hyperpaths
12. Local optimization
12.1. Greedy search
12.2. Simulated annealing
12.3. Genetic algorithms

Course director(s)