- Computational Complexity and Computational Cost.
- Computational Cost of Structured and Recursive Programs
- Computability and Decidability
- Turing Machines (Multi-tape, Non deterministic)
- Problem Reduction
- Complexity Classes P, NP, NP-Complete and NP-Hard.
- Other Models of Computation
1. Computational Cost of Algorithms.
1.1 Computational Complexity and Computational Cost.
1.2 Computational Cost of Structured Programs
1.3 Computational Cost of Recursive Programs
1.4 Probabilistic Analysis
2. Introduction to Computability Theory
2.1 Definition of Problem. Decision Problems
2.2 Turing Machines and Decidability
2.3 Computability and Decidability
3. Introduction to Complexity Theory
3.1 Problem Reduction
3.2 Classes P, NP and NP-Complete.
3.3 Classes PSpace, NPSpace.
3.3 Classes NP-Hard, Exp, CoP, CoNP
4. Models of Computation
4.1 Turing Machines (Multi-tape, Non deterministic)
4.3 Cellular Automata
4.4 Lindenmayer Systems