De nos jours, l’informatique arrive à accomplir de véritables miracles. Suite à quelques cours d’informatique, un étudiant peut croire avoir une bonne intuition concernant ce qu’il est possible d’accomplir avec un ordinateur. Cette intuition est parfois trompeuse. En fait, quelles sont les limites ultimes de l’informatique? Existe-t-il des problèmes impossibles à résoudre sur un ordinateur? Cela dépend-il du type d’ordinateur? Quels sont les problèmes qui sont réellement difficiles en pratique? Nous allons dans ce cours répondre à certaine de ces questions, mais aussi aborder les raisons qui rendent certaines d’entre elles particulièrement difficiles.

Une des tâches de l’informatique théorique est d’étudier la notion de calculabilité. Nous allons débuter le cours par l’étude d’un langage de programmation très simple n’ayant que 3 instructions. Nous allons voir que malgré les apparences on peut avec ce langage résoudre des problèmes arbitrairement complexes. Nous allons aussi étudier la Machine de Turing, le modèle de calcul par excellence en informatique théorique qui nous permet de formaliser précisément la notion de temps de calcul et d’espace mémoire dans un contexte de classification de problème.

Une des tâches principales de l’informatique théorique est effectivement de classer les problèmes en fonction des ressources nécessaires à leur résolution. Dans le cours, nous allons étudier une dizaine de classes de complexité qui chacune formalise un contexte de ressource spécifique.