See outcomes "Talen en Automaten" and "Machines en Berekenbaarheid"
In the first part of the course a number of models of computation are considered: RAM, RASP, Turing Machine. These models can be viewed as mathematical formalisms for the expression of algorithms; they differ in the choice of operations and data structures. Based on these models the notions of time and space complexity are introduced, and the models are compared. Then these notions of complexity are applied to a number of concrete algorithms. The complexity of problems (as opposed to algorithms) is considered, leading to a number of classical results concerning NP-completeness and complexity classes. Finally we briefly discuss te complexity of randomized and distributed algorithms.
Hopcroft, Motwani, Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley
prof. dr. Dirk Janssens (Dirk.Janssens@ua.ac.be)