Calculabilité et Complexité

Ects : 5
Volume horaire : 18

Description du contenu de l'enseignement :
Caractériser les problèmes pour lesquels un algorithme executable en temps fini existe pour leur solution, et caractériser les problèmes pour lesquels un algorithme efficace existe et les problèmes pour lesquels des algorithmes efficaces n'existent pas, indépendamment de la technologie de calcul utilisée.

Calculabilité : Ensembles dénombrables (rappels) Programme WHILE, machines de Turing, Décidabilité
Complexité : Problèmes et réductions P vs. NP