LA DEMARCHE ALGORITHMIQUE

Notion d’algorithme

On peut définir le mot algorithme de trois manières : 1) Un algorithme est une suite finie et parfaitement déterminée d’opérations élémentaires dont la résolution aboutit au résultat d’un problème donné. 2) Un algorithme est la description logique et chronologique d’une suite d’opérations permettant d’obtenir un résultat bien spécifié sous les hypothèses de conditions initiales déterminées : c’est le modèle abstrait d’un programme concret. 3) Un algorithme est un ensemble de règles (ou instructions) ayant les cinq caractéristiques suivantes : – Il doit être fini et doit se terminer après un nombre fini d’opérations. – Il doit être défini et précis : chaque instruction doit être définie sans ambiguïté. – S’il y a des données d’entrée, le champ d’application doit être précisé (ex : nombres entiers, réels, caractères,…). – Il doit posséder au moins un résultat (donnée de sortie). – Il doit être effectif : toutes les opérations doivent pouvoir être effectuées exactement, et dans un temps fini, par un homme utilisant des moyens manuels. On dira qu’un problème est décidable, s’il existe au moins un algorithme permettant de résoudre ce problème. Il est important de savoir que certains problèmes ne sont pas décidables : aucun algorithme n’y apporte de solution. D’ailleurs, l’existence d’une solution à un problème, dans un cas particulier ou même sur plusieurs cas spécifiques, n’implique pas que le problème soit décidable.  Inversement, le fait de savoir qu’un problème n’est pas décidable n’implique pas qu’il n’ait pas de solutions, mais qu’il n’y a pas de méthode permettant d’obtenir ces solutions, dans tous les cas où elles existent. La résolution d’un problème concret en théorie des graphes passe par plusieurs phases : – Modélisation du problème sous forme de graphe. – Un algorithme permettant de résoudre le problème posé. – Détermination de la complexité de l’algorithme (ou efficacité de l’algorithme).

Phase de modélisation mathématique

La modélisation mathématique, en terme général, consiste à traduire en expressions mathématiques les mécanismes ou phénomènes physiques ou chimiques ou biologiques qui prennent place dans un système. Notons qu’un système est un ensemble d’éléments liés par un ensemble de relations, de telle sorte que toute modification d’un élément va entraîner une modification d’autres éléments. L’utilisation de cette description permet de déduire des extrapolations dans le déroulement de ces phénomènes. Elle permet aussi de déduire quel serait le fonctionnement du même système soumis à d’autres contraintes ou sollicitations. L’ensemble de toutes ces relations mathématiques est donc un modèle analogue à une maquette qui représente le système analysé. Son intérêt principal est de se prêter à remplacer le système lui même pour procéder à des expérimentations qui seraient soit onéreuses, soit totalement impraticables[1]. Par la suite, les résultats théoriques des modèles sont soigneusement comparés à toutes les observations disponibles, c’est la phase de validation.  Une validation insatisfaisante est un signal que les expressions mathématiques choisies pour décrire les processus physiques, chimiques ou biologiques ne sont pas correctes. Une validation satisfaisante indique que les modèles peuvent être utilisés à des fins de gestion et offrir certaines capacités prévisionnelles. La théorie des graphes est un moyen de modélisation et de résolution de problèmes concrets. Elle intervient dans les problèmes de plus court chemin (problème de transport, problème d’optimisation de réseau…) de conception et gestion de réseau d’optimisation de production etc. L’étape de modélisation consiste à transformer un problème concret sous forme de graphe G = (S, A). Les arcs ou arêtes de ce graphe représentent les relations entre les éléments de S. Les sommets du graphe pouvant représenter des villes des événements des entreprises… On associe au graphe G = (S, A) une fonction de pondération w : A →ℝ qui fait correspondre à chaque arc un poids à valeur réelle. Le poids d’arc peut représenter une distance, un temps, un coût, une pénalité ou n’importe qu’elle autre quantité qui s’accumule linéairement le long d’un chemin. Notons qu’il existe des graphes non pondérés, c’est à dire des graphes pour lesquels on considère que chaque arc possède un poids unitaire. Exemple. Problème de plus court chemin à origine unique. Un automobiliste veut trouver le plus court chemin entre Darou Salam et Darou djannah étant donné un extrait d’une carte (figure. 1), comment peut –il déterminer la route la plus courte ? Une possibilité consiste à énumérer toutes les routes de Darou Salam à Darou djannah et additionner les distances sur chacune d’elles et choisir la plus courte. Cependant lorsqu’il s’agit d’un problème de grande taille (carte routière d’un pays) on aura alors à faire des millions de calculs d’où la nécessité de modéliser le problème et de trouver un algorithme permettant de résoudre ce genre de problèmes à l’aide d’un ordinateur. Modélisation de l’exemple précédent On peut modéliser cette carte par un graphe G = (S, A) avec une fonction de pondération w : A→ℝ tel que : – Les sommets représentent des intersections de routes à l’intérieur des villages. – Les arcs représentent les portions de routes. – Les poids : les distances calculées à l’aide de l’échelle sur la carte.