Ce cours de première année de master a pour objectif de familiariser les étudiants d'informatique avec trois théories extrêmement riches et dont les développements récents ont été spectaculaires : la théorie de la calculabilité et de la décidabilité, la théorie de la complexité et la théorie de l'ap­pro­xi­ma­tion. La théorie de la programmation, qui englobe ces trois théories, cherche à répondre formellement à trois questions fondamentales posées de manière in­for­mel­le : 

• Que peut-on calculer ? 
• Que peut-on calculer efficacement ?
• Que peut-on approximer efficacement ?

La première question est la question clef de la théorie de la calculabilité et la décidabilité (un problème est décidable si on peut répondre par oui ou non à la question formulée), la deuxième est celle de la théorie de la complexité et la dernière celle de la théorie de l'approximation.