Introduction aux grandes catégories de problèmes/Présentation du cours

Ce cours aborde les points suivants :

• introduction à la notion de complexité sous forme expérimentale ;
• notion de problème indécidable: le problème de l’arrêt ;
• définition informelle des classes de problème P, NP, NP-Complet ;
• comparaison de problèmes, notion de réduction ;

La question P=?NP, historique et importance ;

• notions de solutions parfaites et imparfaites (approximations, heuristiques, algorithmes probabilistes) ;
• étude de quelques problèmes en mentionnant leurs applications, des solutions exactes ou approchées: - SAT et variantes, algorithme polynomial pour 2-SAT, réduction 3SAT-SAT ;
• coloration de graphes, application à l’allocation de fréquences ou de registres ;
• cas des graphes 2 coloriables ;
• problème du sac à dos, applications (découpe de matériaux, chargement de véhicules) ;
• résolution approchée (algorithme glouton) et exacte ;
• problème du voyageur de commerce.