Aller au contenu

Introduction aux grandes catégories de problèmes

Leçons de niveau 14
Une page de Wikiversité, la communauté pédagogique libre.
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 personnes sont prêtes à vous aider concernant ce cours :


Image logo Modifier cette liste