Computability and Computational Complexity

A first goal is to introduce the notion of computability by means of simple programming languages. We recall that a fuction is computable (and a problem is called decidable) if it admits an algorithm for its computation (solution). In particular we aim to illustrate and motivate Church's Thesis, the undecidable problems and the main results of the theory of recursive functions. A second goal is devoted to the classification of decidable problem based on their computational complexity, given by the computation time and the memory space necessary to determine the solution. A special attention is paid to study and motivate the class of NP-complete problems.

Comprehension of the main notions of computability and decidability. Capability to recognize undecidable or hard problems in the main cases. Capability to formalize and study computational models.