22
Complexité
catégories : les problèmes pour lesquels il n’existe pas d’algorithme et les
problèmes pour lesquels un algorithme existe. Parmi ces derniers, on mesure l’e!cacité de l’algorithme selon la croissance de la durée de leur exécution en fonction de la taille du problème. Pour un problème de taille q,
on considère comme e!caces les algorithmes dont la croissance est polynomiale et ine!caces ou di!cilement exploitables les algorithmes dont la
croissance est exponentielle. On dit qu’un algorithme n’est pas résoluble ou
décidable s’il n’est pas justiciable d’une solution à l’aide d’un algorithme.
On distingue plusieurs classes.
La classe P (Polynomial ) représente la classe des langages décidables en
un temps polynomial : ce sont les problèmes qui admettent une solution sur
une machine de Turing en temps polynomial. La résolution d’un problème
est obtenue en un temps inférieur à une puissance donnée de la taille q
du problème : si la taille q du problème augmente, le nombre d’étapes de
l’algorithme reste toujours plus petit qu’une certaine puissance de q.
La classe NP (Non deterministic polynomial ) représente la classe des langages décidables en temps non déterministe polynomial. Ce sont des problèmes pour lesquels, si une solution est proposée, on peut vérifier que cette
solution répond bien au problème en un temps polynomial. Pour certains
problèmes de cette classe, on ne connaît aucun algorithme polynomial. On
sait que la classe P est contenue dans la classe NP et on conjecture que
S 6 = QS. Le coloriage d’une carte est un problème de la classe NP. En
1975, Kenneth Appel et Wolfgang Haken ont “démontré” sur ordinateur
qu’il su!t de quatre couleurs pour colorier une carte en évitant que deux
pays voisins aient la même couleur.
La classe NP-complet représente les problèmes de la classe NP qui sont liés :
si un problème de cette classe peut être résolu par un algorithme en temps
polynomial, alors tous les problèmes de la classe NP seront solubles par un
algorithme e!cace. Si on trouve un tel algorithme, on aura alors identité
des classes P et NP. Le problème du voyageur de commerce, qui consiste à
trouver le chemin le plus court reliant une série de villes, est un problème
NP-complet. Le problème du sac à dos : étant donné un sous-ensemble S
de l’ensemble des entiers naturels et p un nombre positif, peut-on trouver
une partie A de S telle que la somme de ses éléments soit égale à l’entier
p, est un problème NP-complet.
La complexité des algorithmes se mesure en ne retenant que des ordres
de grandeurs. Si W (q) désigne le nombre d’instructions élémentaires exécutées par une machine formelle, on dira que le temps d’exécution est en
R(W (q)) ou que la complexité de l’algorithme est proportionnelle à i (q) si
en notation de Landau
W (q)=R(i (q))
Complexité
catégories : les problèmes pour lesquels il n’existe pas d’algorithme et les
problèmes pour lesquels un algorithme existe. Parmi ces derniers, on mesure l’e!cacité de l’algorithme selon la croissance de la durée de leur exécution en fonction de la taille du problème. Pour un problème de taille q,
on considère comme e!caces les algorithmes dont la croissance est polynomiale et ine!caces ou di!cilement exploitables les algorithmes dont la
croissance est exponentielle. On dit qu’un algorithme n’est pas résoluble ou
décidable s’il n’est pas justiciable d’une solution à l’aide d’un algorithme.
On distingue plusieurs classes.
La classe P (Polynomial ) représente la classe des langages décidables en
un temps polynomial : ce sont les problèmes qui admettent une solution sur
une machine de Turing en temps polynomial. La résolution d’un problème
est obtenue en un temps inférieur à une puissance donnée de la taille q
du problème : si la taille q du problème augmente, le nombre d’étapes de
l’algorithme reste toujours plus petit qu’une certaine puissance de q.
La classe NP (Non deterministic polynomial ) représente la classe des langages décidables en temps non déterministe polynomial. Ce sont des problèmes pour lesquels, si une solution est proposée, on peut vérifier que cette
solution répond bien au problème en un temps polynomial. Pour certains
problèmes de cette classe, on ne connaît aucun algorithme polynomial. On
sait que la classe P est contenue dans la classe NP et on conjecture que
S 6 = QS. Le coloriage d’une carte est un problème de la classe NP. En
1975, Kenneth Appel et Wolfgang Haken ont “démontré” sur ordinateur
qu’il su!t de quatre couleurs pour colorier une carte en évitant que deux
pays voisins aient la même couleur.
La classe NP-complet représente les problèmes de la classe NP qui sont liés :
si un problème de cette classe peut être résolu par un algorithme en temps
polynomial, alors tous les problèmes de la classe NP seront solubles par un
algorithme e!cace. Si on trouve un tel algorithme, on aura alors identité
des classes P et NP. Le problème du voyageur de commerce, qui consiste à
trouver le chemin le plus court reliant une série de villes, est un problème
NP-complet. Le problème du sac à dos : étant donné un sous-ensemble S
de l’ensemble des entiers naturels et p un nombre positif, peut-on trouver
une partie A de S telle que la somme de ses éléments soit égale à l’entier
p, est un problème NP-complet.
La complexité des algorithmes se mesure en ne retenant que des ordres
de grandeurs. Si W (q) désigne le nombre d’instructions élémentaires exécutées par une machine formelle, on dira que le temps d’exécution est en
R(W (q)) ou que la complexité de l’algorithme est proportionnelle à i (q) si
en notation de Landau
W (q)=R(i (q))