Leçons de niveau 14

Introduction aux grandes catégories de problèmes

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
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

Les objectifs de ce cours sont :

  • familiarisation avec la notion de complexité ;
  • connaître l’existence de problèmes NP-Complets.

image logo modifier ces objectifs.
Niveau et prérequis conseillés

Cours de niveau 14. Les prérequis conseillés sont :

  • aucun.

Image logo modifier ces prérequis.
Référents

Ces contributeurs sont prêts à vous aider concernant ce cours :


Image logo modifier les référents.