Algorithmique

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Algorithmes)
Aller à : navigation, rechercher

L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est-à-dire de processus systématiques de résolution d'un problème permettant de décrire les étapes vers le résultat. En d'autres termes, un algorithme est une suite finie et non-ambiguë d’instructions permettant de donner la réponse à un problème.

Si les instructions d'un algorithme s’exécutent les unes après les autres, l'algorithme est dit séquentiel, si elles s’exécutent en même temps, il est parallèle. Si l'algorithme exploite des tâches s’exécutant sur un réseau de processeurs on parle d’algorithme réparti, ou distribué.

Le mot « algorithme » vient du nom du mathématicien Al Khuwarizmi (latinisé au Moyen Âge en Algoritmi), qui, au IXe siècle écrivit le premier ouvrage systématique sur la solution des équations linéaires et quadratiques.

Histoire[modifier | modifier le code]

Antiquité[modifier | modifier le code]

Les premiers algorithmes dont on a retrouvé des descriptions datent des Babyloniens, au IIIe millénaire av. J.-C.. Ils décrivent des méthodes de calcul et des résolutions d'équations à l'aide d'exemples.

Un algorithme célèbre est celui qui se trouve dans le livre 7 des Éléments d'Euclide, et appelé algorithme d'Euclide. Il permet de trouver le plus grand diviseur commun, ou PGCD, de deux nombres. Un point particulièrement remarquable est qu’il contient explicitement une itération et que les propositions 1 et 2 démontrent sa convergence.

Étude systématique[modifier | modifier le code]

Le premier à avoir systématisé des algorithmes est le mathématicien arabophone Al Khuwarizmi, actif entre 813 et 833. Dans son ouvrage Abrégé du calcul par la restauration et la comparaison, il étudie toutes les équations du second degré et en donne la résolution par des algorithmes généraux. Il utilise des méthodes semblables à celles des Babyloniens, mais se différencie par ses explications systématiques là où les Babyloniens donnaient seulement des exemples.

Le savant arabe Averroès (1126-1198) évoque une méthode de raisonnement où la thèse s’affine étape par étape, itérativement, jusqu’à une certaine convergence et ceci conformément au déroulement d’un algorithme. À la même époque, au XIIe siècle, le moine Adelard de Bath introduit le terme latin de algorismus, par référence au nom de Al Khuwarizmi. Ce mot donne algorithme en français en 1554.

Au XVIIe siècle, on pourrait entrevoir une certaine allusion à la méthode algorithmique chez René Descartes dans la méthode générale proposée par le Discours de la méthode (1637), notamment quand, en sa deuxième partie, le logicien français propose de « diviser chacune des difficultés que j’examinerois, en autant de parcelles qu’il se pourroit, et qu’il seroit requis pour les mieux résoudre. » Sans évoquer explicitement les concepts de boucle, d’itération ou de dichotomie, l’approche de Descartes prédispose la logique à accueillir le concept de programme, mot qui naît en français en 1677.

L’utilisation du terme algorithme est remarquable chez Ada Lovelace, fille de Lord Byron et assistante de Charles Babbage (1791-1871).

Les temps modernes[modifier | modifier le code]

Avec l'informatique, l'algorithmique s'est beaucoup développée. Donald Knuth (né en 1938), auteur du traité The Art of Computer Programming, décrit de très nombreux algorithmes et posa des fondements mathématiques rigoureux pour l'analyse des algorithmes. La revue Communications de l'ACM (Association for Computing Machinery) a été consacrée principalement à la description et à l'analyse des algorithmes pendant plus de 20 ans.

Vocabulaire[modifier | modifier le code]

Le substantif algorithmique désigne la méthode utilisant des algorithmes. Le terme est également employé comme adjectif.

Un algorithme énonce une résolution sous la forme d’une série d’opérations à effectuer. La mise en œuvre de l’algorithme consiste en l’écriture de ces opérations dans un langage de programmation et constitue alors la brique de base d’un programme informatique.

Les informaticiens utilisent fréquemment l’anglicisme implémentation pour désigner cette mise en œuvre. L’écriture en langage informatique est aussi fréquemment désignée par le terme « codage », qui n’a ici aucun rapport avec la cryptographie, mais qui se réfère au terme « code source » pour désigner le texte, en langage de programmation, constituant le programme. L’algorithme devra être plus ou moins détaillé selon le niveau d’abstraction du langage utilisé, de même qu'une recette de cuisine doit être plus ou moins détaillée selon l’expérience du cuisinier.

Étude formelle[modifier | modifier le code]

De nombreux outils formels ou théoriques ont été développés pour décrire les algorithmes, les étudier, exprimer leurs qualités, pouvoir les comparer :

  • Ainsi, pour décrire les algorithmes, des structures algorithmiques ont été mises en évidence : structures de contrôle et structures de données.
  • Pour justifier de la qualité des algorithmes, les notions de correction, de complétude et de terminaison ont été mises en place.
  • Enfin, pour comparer les algorithmes, une théorie de la complexité des algorithmes a été définie.

Structures algorithmiques[modifier | modifier le code]

Les concepts en œuvre en algorithmique, par exemple selon l'approche de N. Wirth pour les langages les plus répandus (Pascal, C, etc.), sont en petit nombre. Ils appartiennent à deux classes :

Ce découpage est parfois difficile à percevoir pour certains langages (Lisp, Prolog…) plus basés sur la notion de récursivité où certaines structures de contrôle sont implicites et, donc, semblent disparaître.

Correction, complétude, terminaison[modifier | modifier le code]

Ces trois notions « correction », « complétude », « terminaison » sont liées, et supposent qu'un algorithme est écrit pour résoudre un problème.

La terminaison est l'assurance que l'algorithme terminera en un temps fini. Les preuves de terminaison font habituellement intervenir une fonction entière positive strictement décroissante à chaque « pas » de l'algorithme.

Étant donnée la garantie qu'un algorithme terminera, la preuve de correction doit apporter l'assurance que si l'algorithme termine en donnant une proposition de solution, alors cette solution est correcte — c'est-à-dire qu'elle est effectivement une solution au problème posé.

La preuve de complétude garantit que, pour un espace de problèmes donné, l'algorithme, s'il termine, donnera toutes les solutions.

Complexité algorithmique[modifier | modifier le code]

Les principales notions mathématiques dans le calcul du coût d’un algorithme précis sont les notions de domination (notée O(f(n)), « grand o »), où f est une fonction mathématique de n, variable désignant la quantité d’informations (en bits, en nombre d’enregistrements, etc.) manipulée dans l’algorithme. En algorithmique on trouve souvent des complexités du type :

Notation Type de complexité
O(1) complexité constante (indépendante de la taille de la donnée)
O(\log(n)) complexité logarithmique
O(n) complexité linéaire
O(n \log(n)) complexité quasi-linéaire
O(n^{2}) complexité quadratique
O(n^{3}) complexité cubique
O(n^p) complexité polynomiale
O(n^{\log(n)}) complexité quasi-polynomiale
O(2^{n}) complexité exponentielle
O(n!) complexité factorielle

Sans entrer dans les détails mathématiques, le calcul de l’efficacité d’un algorithme (sa complexité algorithmique) consiste en la recherche de deux quantités importantes. La première quantité est l’évolution du nombre d’instructions de base en fonction de la quantité de données à traiter (par exemple, pour un algorithme de tri, il s'agit du nombre de données à trier), que l’on privilégiera sur le temps d'exécution mesuré en secondes (car ce dernier dépend de la machine sur laquelle l'algorithme s'exécute). La seconde quantité estimée est la quantité de mémoire nécessaire pour effectuer les calculs. Baser le calcul de la complexité d’un algorithme sur le temps ou la quantité effective de mémoire qu’un ordinateur particulier prend pour effectuer ledit algorithme ne permet pas de prendre en compte la structure interne de l’algorithme, ni la particularité de l’ordinateur : selon sa charge de travail, la vitesse de son processeur, la vitesse d’accès aux données, l’exécution de l’algorithme (qui peut faire intervenir le hasard) ou son organisation de la mémoire, le temps d’exécution et la quantité de mémoire ne seront pas les mêmes.

Souvent, on examine les performances "au pire", c'est-à-dire dans les configurations telles que le temps d'exécution (ou l'espace mémoire) est le plus grand. Il existe également un autre aspect de l'évaluation de l'efficacité d'un algorithme : les performances "en moyenne". Cela suppose d'avoir un modèle de la répartition statistique des données de l'algorithme, tandis que la mise en œuvre des techniques d'analyse implique des méthodes assez fines de combinatoire et d'évaluation asymptotique, utilisant en particulier les séries génératrices et des méthodes avancées d'analyse complexe. L'ensemble de ces méthodes est regroupé sous le nom de combinatoire analytique.

On trouvera dans l’article sur la théorie de la complexité des algorithmes d’autres évaluations de la complexité qui vont en général au-delà des valeurs proposées ci-dessus et qui répartissent les problèmes (plutôt que les algorithmes) en classes de complexité.

Quelques indications sur l’efficacité des algorithmes[modifier | modifier le code]

Souvent, l’efficacité d’un algorithme n’est connue que de manière asymptotique, c’est-à-dire pour de grandes valeurs du paramètre n. Lorsque ce paramètre est suffisamment petit, un algorithme de complexité supérieure peut en pratique être plus efficace. Ainsi, pour trier un tableau de 30 lignes (c’est un paramètre de petite taille), il est inutile d’utiliser un algorithme évolué comme le Tri rapide (l’un des algorithmes de tri les plus efficaces en moyenne) : l’algorithme de tri le plus trivial sera suffisamment efficace.

Entre deux algorithmes dont la complexité est identique, on cherchera à utiliser celui dont l’occupation mémoire est la plus faible. L’analyse de la complexité algorithmique peut également servir à évaluer l’occupation mémoire d’un algorithme. Enfin, le choix d’un algorithme plutôt qu’un autre doit se faire en fonction des données que l’on s’attend à lui fournir en entrée. Ainsi, le Quicksort (ou tri rapide), lorsque l’on choisit le premier élément comme pivot, se comporte de façon désastreuse si on l’applique à une liste de valeurs déjà triée. Il n’est donc pas judicieux de l’utiliser si on prévoit que le programme recevra en entrée des listes déjà presque triées.

Un autre paramètre à prendre en compte est la localité de l’algorithme. Par exemple pour un système à mémoire virtuelle qui dispose de peu de mémoire (par rapport au nombre de données à traiter), le Tri rapide sera normalement plus efficace que le Tri par tas car le premier ne passe qu’une seule fois sur chaque élément de la mémoire tandis que le second accède à la mémoire de manière discontinue (ce qui augmente le risque de swapping).

Enfin, il existe certains algorithmes dont la complexité est dite amortie. Cela signifie que, pour certaines exécutions de l’algorithme (cas marginaux), la complexité de l’algorithme sera très supérieure au cas moyen. Bien sûr, on n’utilise la notion de complexité amortie que dans les cas où cette réaction est très marginale.

Approches pratiques[modifier | modifier le code]

L'algorithmique a développé quelques stratégies pour résoudre les problèmes :

  • algorithme glouton : un premier algorithme peut souvent être proposé en étudiant le problème très progressivement : on résout chaque sous-problème localement en espérant que l'ensemble de leurs résultats composera bien une solution du problème global. On parle alors d'algorithme glouton. L'algorithme glouton n'est souvent qu'une première étape dans la rédaction d'un algorithme plus performant.
  • diviser pour régner : pour améliorer les performances des algorithmes, une technique usuelle consiste à diviser les données d'un problème en sous-ensembles de tailles plus petites, jusqu'à obtenir des données que l'algorithme pourra traiter au cas par cas. Une seconde étape dans ces algorithmes consiste à « fusionner » les résultats partiels pour obtenir une solution globale. Ces algorithmes sont souvent associés à la récursivité.
  • recherche exhaustive (ou combinatoire) : une méthode utilisant l'énorme puissance de calcul des ordinateurs consiste à regarder tous les cas possibles. Cela n'est pour autant possible que dans certains cas particuliers (la combinatoire est souvent plus forte que l'énorme puissance des ordinateurs, aussi énorme soit-elle)
  • aléatoire, ou par approximations successives : certains algorithmes utilisent des recherches aléatoires, ou par approches successives, donnant de meilleurs résultats (en moyenne) que des recherches directes ou explicites.
  • décomposition top-down / bottom-up : les décompositions top-down consistent à essayer de décomposer le problème en sous-problèmes à résoudre successivement, la décomposition allant jusqu'à des problèmes triviaux faciles à résoudre. L'algorithme global est alors donné par la composée des algorithmes définis au cours de la décomposition. La démarche bottom-up est la démarche inverse, elle consiste à partir d'algorithmes simples, ne résolvant qu'une étape du problème, pour essayer de les composer pour obtenir un algorithme global.
  • pré-traitement / post-traitement : parfois, certains algorithmes comportent une ou deux phases identifiées comme des pré-traitements (à faire avant l'algorithme principal), ou post-traitement (à faire après l'algorithme principal), pour simplifier l'écriture de l'algorithme général.

Les heuristiques[modifier | modifier le code]

Pour certains problèmes, les algorithmes ont une complexité beaucoup trop grande pour obtenir un résultat en temps raisonnable, même si l’on pouvait utiliser une puissance de calcul phénoménale. On est donc amené à rechercher une solution la plus proche possible d’une solution optimale en procédant par essais successifs. Puisque toutes les combinaisons ne peuvent être essayées, certains choix stratégiques doivent être faits. Ces choix, généralement très dépendants du problème traité, constituent ce qu’on appelle une heuristique. Le but d’une heuristique n'est donc pas d'essayer toutes les combinaisons possibles afin de trouver celle répondant au problème, mais de trouver une solution approchée convenable (qui peut être exacte dans certains cas) dans un temps raisonnable. C’est ainsi que les programmes de jeu d’échecs ou de jeu de go (pour ne citer que ceux-là) font appel de manière très fréquente à des heuristiques qui modélisent l’expérience d’un joueur. Certains logiciels antivirus se basent également sur des heuristiques pour reconnaître des virus informatiques non répertoriés dans leur base, en s’appuyant sur des ressemblances avec des virus connus.

Exemples d’algorithmes, de problèmes, d'applications ou domaines d'application[modifier | modifier le code]

Il existe un certain nombre d’algorithmes classiques, utilisés pour résoudre des problèmes ou plus simplement pour illustrer des méthodes de programmation. On se référera aux articles suivants pour de plus amples détails (voir aussi liste des algorithmes) :

Voir aussi[modifier | modifier le code]

Sur les autres projets Wikimedia :

Articles connexes[modifier | modifier le code]