Définition du terme algorithme

Un algorithme est un automate déterministe pour l'accomplissement d'un but qui, à partir d'un état initial donné, va s'achever dans un état final. La qualité de l'implémentation tient à la vitesse, la taille, la consommation en ressources.

Sommaire

Qu'est-ce qu'un algorithme?

Il n'existe par de définition universellement admise du mot "algorithme".
Une définition simple: Un ensemble d'instructions pour résoudre un problème.

L'algorithme est soit implémenté par un programme, soit simulé. Les algorithmes ont souvent des étapes qui itèrent (se répètent) ou requièrent des décisions logiques ou de comparaison.

Un exemple très simple d'algorithme est la multiplication de deux nombres: sur les premiers ordinateur aux processeurs limités, elle était accomplie par une routine qui, dans un nombre de boucle basé sur le premier nombre ajoutait le second nombre. L'algorithme traduit une méthode en commandes d'ordinateur.

Les algorithmes sont essentiels au traitement de l'information par les ordinateurs parcequ'un programme est en fait un algorithme qui donne à l'ordinateur les étapes à accomplir, et dans quel ordre pour accomplir une tâche donnée, comme calculer les salaires des employés ou les notes des étudiants. Donc un algorithme peut être considéré comme tout séquence d'opération qui peut être exécutée par un system Turing-complet. Parmi les auteurs qui soutiennent cette thèse, citons Gurevich:

"L'argument informel de Turing en faveur de sa thèse justifie une thèse plus forte: chaque algorithme peut être simulé par une machine de Turing."
et Savage:
"Un algorithme est un processus de traitement défini par une machine de Turing."

Typiquement, quand un algorithme est impliqué dans le traitement de l'information, les données sont lues sur une source en entrée, ou un périphérique, écrites dans une sortie, ou un périphérique, et/ou stockées pour un traitement ultérieur. L'enregistrement de données est vu comme la partie interne de l'entité exécutant l'algorithme. En pratique, l'état est stocké dans une structure de données.

Pour tous ces processus de calculs, l'algorithme doit être rigoureusement défini: la façon dont il se comporte dans toutes les circonstances possible doit être définie. Ceci étant, toutes les étapes conditionnelles doivent être systématiquement considérées au cas par cas; les critères de chacun doivent être clairs et calculables.

Parcequ'un algorithme est une liste précise d'étapes précices, l'ordre de calcul sera toujours critique pour le fonctionnement de l'algorithme. Les instructions doivent être explicitement définies, et sont décrites en allant du sommet au détail, une idée formellement exprimée sous le terme de contrôle de flux.

Jusque là, la discussion sur la définition d'un algorithme suppose en prémisse une programmation impérative. C'est la conception la plus commune, cela tente de décrire une tâche par des moyens discrets, "mécaniques". La notion d'assignement d'une valeur à une variable est propre à cette conception. Il en découle la vision de la "mémoire" comme une feuille de brouillon.

La programmation fonctionnelle ou la programmation logique offrent des conceptions différentes de ce qu'est un algorithme.

Définitions du mot algorithme

Blass et Gurevich

Blass et Gurevich décrivent leur travail comme inspiré des machines de Turing, des machines de Kolmogorov-Uspensky (machines KU), celle de Schönhage (SMM, Storage Modification Machine, et machines à pointeur définies par Knuth. Gandy et Markov sont aussi vus comme des précurseurs ayant eu leur influence.

Gurevich offre une définition bien affirmée de ce qu'est un algorithme (résumée ici):

L'argument informel de Turing en faveur de sa thèse justifie une thèse plus forte: chaque algorithme peut être simulé par une machine de Turing. En pratique, cela pourrait paraitre grotesque. Pourrait-on généraliser les machines de sorte que tout algorithme, quel que soit son degré d'abstraction, soit modélisé par une machine générale? Mais supposons qu'une machine de Turing aussi généralisée existe. Quels seraient ses états? Une structure du premier ordre... Un petit ensemble d'instructions particulier suffirait dans tous les cas. Le traitement serait une évolution de l'état. Cela pourrait être non-déterministe, pourrait interargir avec son environnement, être parallèle et multi-agents, avoir une sémantique dynamique. Les deux pivots de leur travail sont: les thèses de Turing's et la notion de structure de premier ordre de Tarski.

La phrase ci-dessus, "traitement comme évolution de l'état" diffère notablement de la définition de Knuth et Stone, l'algorithme comme un programme de la machine de Turing. Il correspond plutôt à ce que Turing appelait le configuration complète, et qui inclut à la fois l'instruction en cours (l'état) et le statut de la bande. Kleene (1952) montre un exemple d'une bande avec 6 symboles dessus, toutes les autres cases étant blanches, et comment "Gödelizer" le statut combiné table-bande.

Boolos et Jeffrey

Leur définition est la suivante :

"Des instructions explicites pour déterminer le nième membre d'un ensemble, pour n arbitrairement fini. De telles instructions sont données de façon bien explicite, sous une forme qui puisse être utilisée par une machine à calculer ou par un humain qui est capable de transposer des opérations très élémentaires en symboles".

Knuth

Knuth (1968, 1973) a donné une liste de cinq propriétés qui sont largement reconnues comme les pré-requis d'un algorithme:

  1. Finitude: "Un algorithme doit toujours se terminer après un nombre fini d'étapes."
  2. Définition précise: "Chaque étape d'un algorithme doit être définie précisément; les actions à transposer doivent être spécifiées rigoureusement et sans ambiguité pour chaque cas."
  3. Entrées: "...des quantités qui lui sont données avant qu'un algorithme ne commence. Ces entrées sont prises dans un ensemble d'objets spécifié."
  4. Sorties: "...des quantités qui ont une relation spécifiée avec les entrées."
  5. Rendement: "... toutes les opérations que l'algorithme doit accomplir, doivent être suffisamment basiques pour pouvoir être en principe réalisées dans une durée finie par un homme utilisant du papier et un crayon."

Knuth offre comme exemple l'algorithme d'Euclide pour déterminer le plus grand commun diviseur des deux nombres entiers naturels.

Knuth admet que, même si sa description de ce qu'est un algorithme peut être intuitivement claire, il lui manque la rigueur formelle, tandis que n'est pas exactement clair ce que "précisément défini" veut dire, ou "spécifié rigoureusement et sans ambiguité" signifie, ou "suffisamment basique", et ainsi de suite. Il fait un effort dans cette direction dans son premier volume ou il définit en detail ce qu'il appelle le "langage machine", pour son "mythique MIX... le premier ordinateur polyinsaturé au monde". Beaucoup d'algorithmes du livre sont écrit en langage MIX. Il utilise aussi des diagrammes arborescents, de flux, et des diagrammes d'états.

Markov

A. A. Markov (1954) donne cette définition d'algorithme:

"En mathématiques, "algorithme" se comprend généralement comme une prescription exacte, définissant une processus de traitement qui mène à partir de données initiales variées, au résultat voulu..."
"Les trois caractéristiques suivantes sont propres aux algorithmes et déterminent leur rôle en mathématique:
a) la précision de la prescription, ne laissant aucune place à l'arbitraire, et sa compréhensibilité universelle, donc l'aspect défini de l'algorithme;
b) la possibilité de démarrer avec des données initiales, pouvant varier dans des limites données: la généralité de l'algorithme;
c) l'orientation de l'algorithme dans la recherche d'un résultat voulu, qui doit s'obtenir en finale à partir de ses données initiales propres: la propriété de conclusion de l'algorithme."

Il admet que sa définition "ne prétend pas avoir une précision mathématique". Sa monographie de 1954 était une tentative de définir algorithme plus précisement; il voyait le définition résultante - son algorithme formel - comme "équivalent au concept d'une fonction récursive". Cette définition incluait quatre composants majeurs:

"1. Séparer les étapes élémentaire, chacune étant accomplie en accord avec une des règles de substitution données au départ .
2. Des étapes de nature locale.
3. Un schéma de l'algorithme: des règles pour substituer des formules.
4. Un moyen d'indentifier une substitution pour la conclusion."

Dans son Introduction Markov a observé que "l'entière signification pour les mathématiques" des efforts pour définir plus précisement algorithme pourrait se faire en connexion avec le problème d'une fondation constructive pour les mathématiques.

Minsky

Minsky (1967) affirme qu'un algorithme est une procédure effective et en fait un synonyme.
Ce terme est utilisé par d'autres auteurs, sont Knuth. Ce que Minsky appelle une " effective procedure" est défini ainsi:

"Un ensemble de règles qui nous dit, d'instant en instant, comment précisément se comporter."

Cependant il reconnait que cela porte à critique:

"L'interprétation des règles est laissée à disposition de quelque personne ou agent."

Cela le conduit à une amélioration pour spécifier "en même temps que les instructions des règles, le détail du mécanisme qui les interprête. Pour éviter le processus fastidieux d'avoir à le faire toujours pour chaque nouvelle procédure il escompte identifier une famille raisonablement uniforme de méchanismes suivant les règles. Ce qu'il formule ainsi:

"(1) un langage dans lequel des ensembles de règles de comportement sont exprimés, et
(2) une seule machine qui peut interpréter les instructions dans le langage et ainsi transposer les étapes du processus spécifié."

A la fin toutefois il déplore encore qu'un coté subjectif demeure Des gens différents peuvent ne pas être d'accord avec le fait qu'une procédure donnée puisse être considérée comme effective.

Mais Minsky ne désarme pas. Il produit immédiatement "Turing's Analysis of Computation Process". Il y décrit ce qu'il appelle le thèse de Turing:

Tout processus qui pourrait naturellement être appelé une procédure effective peut être réalisé par une machine de Turing.
Ce qui est aussi appelé la thèse de Church.

Après l'analyse de "l'Argument de Turing" il observe une équivalence de nombreuses formulations intuitives de Turing, Church, Kleene, Post, et Smullyan qui conduit à supposer qu'il y a bien une notion objective ou absolue.

Stone

Stone (1972) et Knuth étaient professeurs à l'Université de Stanford University à la même époque aussi n'est-on pas surpris de trouver des similitudes dans leurs définitions:

"En résumé, nous définissons un algorithme comme un ensemble de règles qui définit précisément une séquence d'opérations de sorte que chaque règle soit effective et définie et que la séquence se termine dans un temps fini."
Il faut remarquer que dans ses commentaires détaillés de ce qui constitue une règle effective pour un robot, ou personne agissant comme un robot, celle-ci doit posséder une information et capacité intrinsèque, qui ne sont pas être fournies dans l'algorithme:
"Pour ceux qui suivent les règles de l'algorithme, elles doivent être formulées de sorte qu'elles soient suivies mécaniquement, sans avoir à penser... toutefois, si les instructions (dans son exemple pour résoudre une équation quadratique) sont faites par quelqu'un qui sait faire des opérations arithmétiques mais qui ne sait pas extraire une racine carrée, alors on doit fournir un ensemble de règles pour extraire une racine carrée, afin de satisfaire à le définition de l'algorithme.
...toutes les instructions ne sont pas acceptable, parcequ'elles peuvent demander au robot des capacités qui dépassent ce que l'on considère comme raisonable."

Il donne l'exemple d'un robot confronté avec la question "Si Henry VIII est un roi d'Angleterre, afficher 1, sinon afficher 0", mais le robot n'a pas été préalablement instruit de cette information. Et pire encore, si on demande au robot si Aristote était un roi d'Angleterre et que l'on fournisse seulement cinq noms au robot, il ne pourrait connaître la réponse. Par conséquent:

"Une définition intuitive de séquence d'instructions acceptable est quand chaque instruction est définie précisément de sorte que qu'il soit garanti que le le robot puisse lui obéir."

Après avoir fourni sa définition, Stone introduit le modèle de machine de Turing et pose que l'ensemble de 5-uples qui sont les instructions de la machine est un algorithme... connu comme programme de la machine de Turing. Puis il affirme qu'un traitement par une machine de Turing est décrit en posant:

1. L'alphabet de la bande
2. La forme sous laquelle les paramètres sont donnés à la bande
3. L'état initial de la machine de Turing
4. La forme sous laquelle les réponses seront représentées sur la bande lorsque la machine de Turing s'arrêtera
5. Le programme de la machine.

Cela est dans l'esprit de Blass and Gurevich.

Quelques problèmatiques

Expression d'algorithmes

Les algorithmes peuvent être transcrits sous diverses sortes de notations:
- La transcription en langage naturel tendant à être verbeuse et ambigüe, elle est rarement utilisée pour les algorithmes complexes.
- Pseudo-code et organigrammes sont conçus pour éviter ces ambiguïtés et sont indépendants de toute implémentation.
- Les langages de programmation servent avant tout à les transcrire sous une forme qui puisse être traitée par ordinateur, mais peuvent être utilisés aussi pour décrire les algorithmes.

Un algorithme doit-il s'arrêter?

Certains auteurs restreignent la définition du mot aux procédures qui vont s'arrêter. D'autres dont Kleene, incluent les procédures qui peuvent tourner indéfiniment, de telles procédures pouvant être appellés "méthode de traitement" par Knuth ou "procédure de calcul ou algorithme" par Kleene. Toutefois, Kleene déclare qu'une telle méthode doit néammoins posséder quelque finalité.

Minksy (1967) fait l'observation que si un algorithme ne se termine pas, alors comment peut-on répondre à la question: "Va-t'il terminer avec la réponse correcte?'"

Dans ce cas la réponse est: indécidable. On ne peut jamais savoir ni rien faire pour le trouver. On appelle l'analyse d'un algorithme pour les chances qu'il se termine "Analyse de terminaison".

Analyse d'algorithme

Le terme "analyse d'algorithme" a été lancé par Knuth. La plupart de ceux qui implémentent des algorithmes veulent savoir quelles ressources, comme le temps, l'espace de stockage, seront requis pour son execution. Des méthodes ont été développée pour l'analyse des algorithmes en vue d'obtenir des réponses quantifiées.

L'analyse et l'étude des algorithmes est une discipline de la science informatique, et se fait souvent de façon abstraite sans utiliser de langage ou matériel spécifique. Mais le code Scriptol est assez portable, simple et abstrait pour une telle analyse.

Example simple: la multiplication 

int multiply(int x, int y) 
   int sum = 0 
   while y > 0 
      sum + x 
   let y - 1 
return sum 

int a = 5 
int b = 7 

print a,"x", b, "=", multiply(a, b)

Références

Algorithmes Définition du mot algorithme - Classification - Histoire de l'algorithmique - Liste des algorithmes - Crible d'Eratosthenes - Nombre de Fibonacci