Dans cette UE, nous nous attaquerons à l’étude des problèmes difficiles d’optimisation dont la résolution se heurte à une explosion du nombre de combinaisons à explorer. Plusieurs types de problèmes seront passés en revue tels que les problèmes de satisfaction de contraintes (SAT et CSP), ainsi que des problèmes d’optimisation sur des graphes (colorations, dominations, stabilité, recherche de sous-graphes, etc). Une partie du cours sera également consacrée à l’étude de la complexité et la classification de ces problèmes en classes NP-Complet, NP-difficile, etc. De même, nous verrons les différentes approches de résolution de ces problèmes proposées dans la littérature.
