Chapitre deuxième : METHODOLOGIE DU TRAVAIL
Ce chapitre de notre travail nous permettra de donner une
présentation générale des différentes
méthodes que nous aurons à utiliser pour trouver solution
à l'énoncé théorique de notre problème. Les
concepts qui nous intéresserons dans ce chapitre sont : la
méthode algorithmique, le prototypage, l'expérimentation et
l'argumentation.
II.1.Methode Algorithmique
Un algorithme répond à un problème. Il
est composé d'un ensemble d'étapes simples nécessaires
à la résolution d'un problème, dont le nombre varie en
fonction du nombre d'éléments à traiter. D'autre part,
plusieurs algorithmes peuvent répondre à un même
problème. Pour savoir quelle méthode est plus efficace il faut
les comparer. Pour cela, on utilise une mesure que l'on appelle la
complexité. Elle représente le nombre
d'étapes qui seront nécessaires pour résoudre le
problème pour une entrée de taille donnée.
II.1.1. Problèmes algorithmiques
Un problème algorithmique est un problème
posé de façon mathématique, c'est-à-dire qu'il est
énoncé rigoureusement dans le langage des mathématiques.
On distingue deux types de problèmes :
- Les problèmes de décision :
ils posent une question dont la réponse est oui ou non
;
18
- Les problèmes d'optimisation : ils
comportent une question ou plutôt une injonction de la forme «
trouver un élément tel que ...» dont la réponse
consiste à fournir un tel élément.
La théorie de la complexité étudie
principalement (mais pas uniquement) les problèmes de décisions.
Dans ce travail le type de problème dont nous aurons à traiter
est celui d'optimisation.
II.1.2. Classes de Complexité
La théorie de la complexité est
un domaine des mathématiques, et plus précisément de
l'informatique théorique, qui étudie formellement la
quantité de ressources (en temps et en espace)
nécessaire pour la résolution de problèmes au
moyen de l'exécution d'un algorithme. Il s'agit donc d'étudier la
difficulté intrinsèque de problèmes posés
mathématiquement.
Les classes de complexité sont des ensembles de
problèmes qui ont la même complexité selon un certain
critère. Dans ce qui suit nous allons définir trois classes de
complexité les plus étudiées en une liste qui va de la
complexité la plus basse à la complexité la plus haute :
la classe P, la classe NP et la classe NP-C.
a. La classe P
Un problème de décision est dans P
s'il peut être décidé sur une machine
déterministe en temps polynomial par rapport à la taille
de la donnée. On qualifie
alors le problème de polynomial. C'est un
problème de complexité O(nk),
pour un certain k. On admet, en
général, que les problèmes dans P sont ceux qui sont
faciles à
résoudre.
b. La classe NP
La classe NP possède une
définition moins naturelle que celle de P, et ne
signifie pas "non polynomial", mais polynomial
non-déterministe. La classe NP est donc une
19
extension de la classe P, en
autorisant des choix non déterministes pendant l'exécution de
l'algorithme. Si le modèle de calcul est celui des machines de Turing,
on autorise plusieurs transitions à partir d'un état et d'un
symbole lu sur la bande.
c. La classe NP-Complet
En théorie de la complexité, un
problème NP-complet est un problème
vérifiant les propriétés suivantes :
- Il est possible de vérifier une solution efficacement
(en temps polynomial) ; la classe des problèmes vérifiant cette
propriété est notée NP.
- Tous les problèmes de la classe NP se ramènent
à celui-ci via une réduction polynomiale ; cela signifie que le
problème est au moins aussi difficile que tous les autres
problèmes de la classe NP.
Un problème NP-difficile est un
problème qui remplit la seconde condition, et donc peut être dans
une classe de problème plus large et donc plus difficile que la classe
NP.
Bien qu'on puisse vérifier rapidement toute
solution proposée d'un problème NP-complet, on ne sait pas en
trouver efficacement. C'est le cas, par exemple, du problème du
voyageur de commerce, celui du sac à dos ou encore celui de remplissage
des paniers.
Une question reste ouverte et fait partie des problèmes
non résolus en mathématiques les plus importants à ce
jour. Celui de prouver s'il existe un algorithme polynomial pour
résoudre un quelconque des problèmes NP-complets, si oui, alors
tous les problèmes de la classe NP peuvent être résolus en
temps polynomial. Trouver un algorithme polynomial pour un problème
NP-complet ou prouver qu'il n'en existe pas permettrait de savoir si P
= NP ou P ? NP.
20
En pratique, les informaticiens et les développeurs
sont souvent confrontés à des problèmes NP-complets, ce
qui est d'ailleurs le cas pour nous dans ce travail. Savoir que le
problème sur lequel on travaille est NP-complet est une indication du
fait que le problème est difficile à résoudre, donc qu'il
vaut mieux chercher des solutions approchées en utilisant des
algorithmes d'approximation ou des
heuristiques pour trouver des solutions approximatives.
| 
