Le mot "Algorithme" vient du nom du célèbre mathématicien Al Khowarizmi, astronome et géographe musulman, persan ou arabe. Un de ses grands travaux, écrit en 830, fut Hisab Al-jabr w'al-mugabala, appelé "textes fondateurs" de l’algèbre, et donna naissance au mot Algèbre. Ce traité classifie les solutions des équations quadratiques. Cormen et al. [ 1 ] donne la définition suivante "un algorithme est une procédure de calcul bien définie qui prend en entrée une valeur, ou un ensemble de valeurs, et qui donne en sortie une valeur, ou un ensemble de valeurs. Un algorithme est donc une séquence d'étapes de calcul qui transforment l'entrée en sortie".

Knuth et al., dans The Art of Computer Programming [ 2 ], insistent sur l'importance d'une conception de l'algorithme hautement reliée à son analyse, afin d'obtenir des résultats performants et de comprendre le pourquoi d'une telle réussite. L'efficacité d'un algorithme ne doit pas être le fruit de quelques réglages astucieux efficace pour quelques instances d'un problème. Elle est souvent liée à sa vitesse d'exécution pour produire le résultat escompté ainsi qu'à son encombrement mémoire. Ce temps de machine disponible se doit d'être optimisé, car même dans les scénarios les plus optimistes où les ressources deviennent de plus en plus performantes, le temps machine reste limité et la mémoire coûteuse. Cormen et al. [ 2 ] présentent les algorithmes comme une ``technologie'' à part entière qui ne cesse de progresser. On retrouve des algorithmes dans le compilateur, l'interpréteur, le routage d'informations, l'interface graphique et bien sûr dans l'application elle-même. Ils sont au coeur de tout système et donc se doivent d'avoir une haute performance informatique.

La notion de performance fait référence ici au terme anglais "High Performance Technical Computation" (H.P.T.C.). La définition de la performance proposée par Estellon B., Gardi F. et Nouioua K. [ 5 ] est la suivante : "un algorithme capable de fournir en un temps très court une solution de très grande qualité". Pour répondre à cet objectif, il convient de respecter des contraintes de conception d'algorithme ainsi que d'ingénierie logicielle. On parlera "d'ingénierie algorithmique" pour reprendre les termes introduit par Moret [ 6 ].

La conception efficace d'algorithme nécessite sa preuve de validité. Mitchell [ 3 ] présente dans son manuel des travaux en matière de démonstration de la justesse des programmes. En informatique, établir la preuve de correction d'un algorithme est une tâche importante et difficile. Lapoire [ 4 ] rappelle que "la première qualité attendue d'un algorithme est bien sûr sa terminaison" avant même d'évaluer ses performances. Pour cela, on va devoir prouver "qu'il n'admette aucune instance pour laquelle l'exécution rentre dans une boucle infinie". Il n'existe aucune méthode universelle pour prouver qu'un algorithme se termine, mais une mise en oeuvre rigoureuse et une analyse précise permet bien souvent de conclure à sa validité.

Knuth et al. [ 2 ], insiste sur l'importance de procéder à une analyse de l'algorithme, définie comme la prévision des ressources nécessaires à son bon fonctionnement (la mémoire, la bande passante, le temps de calcul, etc.). Les travaux présentés ici dans cette thèse ne font pas appel à du calcul distribué, ni à du multi-threading (pas d'opérations simultanées). L'analyse s'en retrouve simplifiée mais ne perd rien de son importance. Nous supposerons que nos algorithmes fonctionnent sur un modèle de calcul générique basé sur une machine à accès aléatoire (RAM) à processeur unique. L'analyse de l'algorithme consiste à évaluer la taille de l'entrée et le temps d'execution. On peut mesurer ce temps en comptabilisant le nombre d'étapes élémentaires effectuées par la RAM ou encore le nombre de lignes de pseudo code. L'analyse du code s'intéresse aussi bien au cas le plus défavorable qu'au cas moyen (qui permet de déduire le temps d'execution attendu).

Les autres caractéristiques de la performance algorithmique sont sa fiabilité, sa robustesse, sa portabilité et sa maintenabilité. Ces termes sont plus reliés à des notions d'informatique de production. Les algorithmes doivent être en mesure de traiter tout type d'instances de manière effective et efficace, en ayant pris en compte toutes les contraintes de l'environnement :

• Temps de calcul accordé pour l'exécution en production du logiciel,
• Mémoire allouée au moteur,
• Hétérogénéité des instances,
• Fréquence d'ajout de nouvelles contraintes,
• Nature de l'équipe de support du moteur (nécessité de transfert de connaissance, évolutions futures réalisées par d'autres équipes, etc.)
• Nécessité d'adapter le moteur pour des versions allégées en mobilité.
• etc...

Toutes ces contraintes influencent l'algorithmique sous-jacente car elle nécessite une adaptation des structures, des accès mémoire, des éventuelles décompositions, des temps alloués à chaque étape de l'algorithme, etc.

Les travaux de Moret [ 6 ] et les travaux remarquables d'Helsgaun [ 7 ] sur le problème du voyageur de commerce sont des compléments de lecture très intéressants sur ces sujets de performance algorithmique. Les travaux de Moret mettent en évidence l'importance de l'algorithmique expérimentale qui étudie à la fois l'efficacité des algorithmes mais aussi les structures de données. C'est ce qu'il entend par ingénierie algorithmique qui transforme les algorithmes ``papier-crayon'' en des implémentations efficaces et utiles. Ces améliorations peuvent faire gagner un facteur 3 sur le temps de calcul [ 6 ].

Voici le plan de cette introduction à la recherche locale :

• Les notions de base :
  • La Recherche Locale
  • Algorithmie
    
    
• Méthodologie :
• Heuristique de Recherche
• Les Mouvements
• Implémentation
  

Plus d'infos sur le sujet de la Recherche Locale, consultez la note suivante (Estellon B., Gardi F. et Nouioua K.) : Cliquez ici. Questions, commentaires, compléments d'informations : antoinejeanjean@gmail.com

Références :

[ 1 ] Cormen Thomas H., Leiserson C., Rivest Ronald L. Stein Clifford, Introduction to Algorithms, 1990.

[ 2 ] Knuth et al., The arts of computer programming, 1968

[ 3 ] Mitchell (John C.). Foundations for Programming Languages. MIT Press, 1996.

[ 4 ] Denis Lapoire, Initialisation à l'algorithmique, 2006

[ 5 ] Estellon B., Gardi F. et Nouioua K. Recherche Locale Haute Performance, 2009

[ 6 ] B.M.E. Moret (2002). Towards a discipline of experimental algorithmics. In Data Structures, Near
Neighbor Searches, and Methodology : 5th and 6th DIMACS Implementation Challenges (sous la direction
de M.H. Goldwasser, D.S. Johnson et C.C. McGeoch), DIMACS Monographs, Vol. 59, pp. 197-213.
American Mathematical Society, Providence, RI.

[ 7 ] K. Helsgaun (2000). An effective implementation of the Lin-Kernighan traveling salesman heuristic, European Journal of Operational Research 126(1), pp. 106-130.