Université d’Alger 1 Benyoucef Benkhedda
Département de Mathématiques et Informatique
Optimisation Combinatoire:
Problèmes NP et NP-complets
Le niveau: Année universitaire:
1ère année master ASD 2021/2022
Le plan
• Types de problèmes
1
• Classes de problèmes
2
2
Types de problèmes
Types de problèmes
Problèmes de décision
Problèmes de recherche de
solutions.
Problèmes d’optimisation.
Problèmes de
dénombrement de solutions.
16/05/2022 3
Types de problèmes
Problèmes
Problèmes de
de décision recherche
de solutions. Problème dont la
L’objet X vérifie-t- réponse attendue
il la propriété P ? est l’ensemble
des solutions.
la réponse
Plus difficile à
attendue est oui
résoudre
ou non
16/05/2022 4
Types de problèmes
Problèmes de
Problèmes dénombrement
d’optimisation. de solutions..
Maximisation Problème
ou dont la
minimisation réponse
d’une attendue est
certaine le nombre de
fonction. solutions.
16/05/2022 5
Exemple
Le problème Le type
existe-t-il un circuit Hamiltonien dans G ? Problèmes de décision
Trouver un ou plusieurs circuits Hamiltoniens Poblèmes de recherche de
de G ? solutions.
Quel est le circuit qui passe une et une seule Problèmes d’optimisation.
fois par le maximum nombre de sommets de
G?
Quel est le nombre de circuits Hamiltoniens du Problèmes de dénombrement
graphe G? de solutions..
16/05/2022 6
Le plan
• Types de problèmes
1
• Classes de problèmes
2
7
Classes de problèmes
Classes de
problèmes
Classe NP-
Classe P Classe NP
complets
16/05/2022 8
Classe P ‘Polynomial time’
La classe P englobe tous
les problèmes qui ont un
algorithme de résolution
dont la complexité du pire
cas est polynomiale
16/05/2022 9
Exemple
Considérons le problème de la somme des arêtes
appelé PSA énoncé comme suit :
Instance : G= (S, A) un graphe non orienté où S est
un ensemble de n sommets et A l’ensemble des
arêtes, un poids de valeur réelle strictement positive
associé à chaque arête du graphe G et k un nombre
réel.
Question : La somme des poids associés aux arêtes
est-elle égale à k ?
16/05/2022 10
Exemple
16/05/2022 11
Classe NP ‘Non-Deterministic
Polynomial time’
La classe de complexité NP englobe tous les
problèmes pour lesquels il existe un algorithme non
déterministe pour les résoudre en temps polynomial.
Un algorithme est dit non déterministe polynomial
s’il est structuré en deux phases de la manière
suivante:
1 er phase: engendrer une solution quelconque
(bonne ou mauvaise) à l’instance.
2 ème phase: vérifier la validité de la solution en un
temps polynomial.
16/05/2022 12
Exemple ‘le problème du circuit
hamiltonien ’
1ère phase: Engendrer un circuit pour le graphe G,
soit s = {s1, s2, …, sn} ce circuit. Stockons le dans
un tableau S tel que S[i]= si pour tout i = 1 à n.
2 ème phase : Développer un algorithme pour
vérifier si s représente un circuit hamiltonien ou pas.
Structure de données utilisées: un tableau appelé
occurrence contenant les occurrences des sommets
du graphe appartenant à s, donc ceux stockés dans
le tableau S. L’algorithme de vérification est donc le
suivant :
16/05/2022 13
Exemple ‘le problème du circuit
hamiltonien ’
16/05/2022 14
La classe des problèmes NP-
complets
La classe des problèmes NP-complets englobe les
problèmes de décision les plus difficiles de la classe
NP
Un problème Π est NP-complet s’il vérifie les deux
conditions suivantes :
1- Π appartient à la classe NP
2- Tout problème appartenant à la classe NP peut être
réduit au problème Π via une transformation
polynomiale.
16/05/2022 15
La transformation polynomiale
Une transformation polynomiale entre un problème
Π1 et un problème Π2 est une fonction ayant comme
domaine de départ les solutions de Π1 et comme
domaine d’arrivée les solutions de Π2
f : Π1 → Π2
s1 → s2 = f(s1) et telle que :
- 1) pour toute solution positive de Π1 correspond
une solution positive de Π2 et vice versa.
2) le calcul de f(s1) se fait en temps polynomial
16/05/2022 16
Relation entre les différentes
classes
16/05/2022 17
