CHAPITRE I. LE PROBLÈME D'EMPLOI DE TEMPS
On peut ainsi établir un ordre sur les
fonctions les plus connues, afin de les utilisées dans
q
l'estimation de la complexité (trouver g) :
log(n) « (n) « n «
n.log(n) « 2h « eh
« n!
Un algorithme polynomial est un algorithme dont la
complexité est è(g(n)) où g
est une fonction polynomiale et n dénote la taille des
entrées.
On dit qu'un problème P1 se réduit
à un problème P2, par la réduction polynomiale,
s'il existe un algorithme polynomial A construisant, à partir
d'une donnée D1 de P1, une donnée D2
de P2 telle que la réponse pourD1 soit oui si et
seulement si la réponse pour D2 est oui.
On dit aussi qu'un problème P1 se
réduit à un problème P2 par la réduction
de Turing s'il existe pour résoudre P1 un algorithme A1
utilisant comme sous-programme un algorithme A2 résolvant
P2 , de telle sorte que la complexité de A1 est
polynomiale, quand on remplace A2 par une constante qui
l'évalue.
En basant sur les notions citées
précédemment, on peut facilement présenter les
différentes classes de complexité :
- La classe P (Polynomial time). Engendre les problèmes
pour lesquels on peut construire une machine de Turing déterministe
dont le temps d'exécution est de complexité polynomiale. Les
algorithmes qui résoudre ce type de problèmes sont
qualifiés par efficaces.
- La classe NP (Non-deterministic Polynomial time). Engendre
les problèmes pour lesquels on peut construire une machine de Turing
non déterministe dont le temps d»exécution est de
complexité polynomiale.
- La classe NP-complets. Engendre un sous ensemble de la
classe NP qui contient les problèmes les plus difficiles et qui
possèdent la propriété que tout problème dans NP
peut être réduit en ceux-ci en temps polynomial.
- La classe NP-difficile. Engendre les problèmes qui
n'appartient pas à la classe NP. Mais, ont la propriété
que tout problème dans NP-complet peut être réduit en
ceux-ci par la réduction de Turing.
I.2 Types des problèmes
Un problème combinatoire est un problème
où il s'agit de trouver une combinaison adéquate parmi
un ensemble très grand de combinaisons, où chacune peut
être évaluée et présente une solution
admissible.
La réponse à la question : Est-ce-que une
solution x est la meilleure solution dans un domaine de recherche?
engendre un type de problèmes dite problèmes de
décision où
4
| 
