Introduction aux grandes catégories de problèmes
Introduction aux grandes catégories de problèmes
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.
[ ]
Objectifs
ces objectifs
Les objectifs de ce cours sont :
- familiarisation avec la notion de complexité ;
- connaître l’existence de problèmes NP-Complets.
![image logo](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Question_book-2.svg/24px-Question_book-2.svg.png)
Niveau et prérequis conseillés
ces prérequis
Cours de niveau 14. Les prérequis conseillés sont :
- aucun.
![Image logo](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Question_book-2.svg/24px-Question_book-2.svg.png)
![Image logo indiquant les ressources](http://upload.wikimedia.org/wikipedia/commons/thumb/3/3f/Sciences_humaines.svg/45px-Sciences_humaines.svg.png)