J'ai eu la responsabilité (96-97) du cours de décidabilité et complétude , dit M1, de la maîtrise de la faculté des sciences et techniques de Toulon. L'ojectif de ce demi-module est d'alerter l'étudiant d'informatique sur l'impossibilité théorique ou pratique de résoudre certains problèmes, même avec un ordinateur...Les machines : le modèle de Turing, la machine à RAM, la thèse de Church. Le langage des problèmes est présenté : intance, question, solution. La notion d'ensemble dénombrable est revisitée. L'argument diagonal permet de montrer l'indécidabilité de l'arrêt d'un programme. Les notions de temps de calculs et de complexité sont revues. Le théorème de Cooke fournit le premier exemple de problème NP-complet. La notion de réductions permet de dresser une liste de problèmes NP-complet.