Algorithme -Algorithm

Organigramme d'un algorithme (algorithme d'Euclide ) permettant de calculer le plus grand commun diviseur (pgcd) de deux nombres a et b aux emplacements nommés A et B. L'algorithme procède par soustractions successives en deux boucles : SI le test B ≥ A donne "oui" ou "vrai" (plus précisément, le nombre b à l'emplacement B est supérieur ou égal au nombre a à l'emplacement A) ALORS, l'algorithme spécifie B ← B − A (ce qui signifie que le nombre ba remplace l'ancien b). De même, SI A > B, ALORS A ← A − B. Le processus se termine lorsque (le contenu de) B est égal à 0, ce qui donne le pgcd dans A. (Algorithme dérivé de Scott 2009 : 13 ; symboles et style de dessin de Tausworthe 1977) .
Diagramme d' Ada Lovelace de "note G", le premier algorithme informatique publié

En mathématiques et en informatique , un algorithme ( / ˈ æ l ɡ ə r ɪ ð əm / ( écouter ) ) est une séquence finie d' instructions rigoureuses , généralement utilisée pour résoudre une classe de problèmes spécifiques ou pour effectuer un calcul . Les algorithmes sont utilisés comme spécifications pour effectuer des calculs et traiter des données . Des algorithmes plus avancés peuvent effectuer des déductions automatisées (appelées raisonnement automatisé ) et utiliser des tests mathématiques et logiques pour détourner l'exécution du code par diverses voies (appelées prise de décision automatisée ). L'utilisation de caractéristiques humaines comme descripteurs de machines de manière métaphorique était déjà pratiquée par Alan Turing avec des termes tels que "mémoire", "recherche" et "stimulus".

En revanche, une heuristique est une approche de résolution de problèmes qui peut ne pas être entièrement spécifiée ou ne pas garantir des résultats corrects ou optimaux, en particulier dans les domaines problématiques où il n'y a pas de résultat correct ou optimal bien défini.

En tant que méthode efficace , un algorithme peut être exprimé dans un espace et un temps finis, et dans un langage formel bien défini pour calculer une fonction . À partir d'un état initial et d'une entrée initiale (peut-être vide ), les instructions décrivent un calcul qui, lorsqu'il est exécuté , passe par un nombre fini d'états successifs bien définis, produisant finalement une "sortie" et se terminant à un état final final. Le passage d'un état à l'autre n'est pas nécessairement déterministe ; certains algorithmes, connus sous le nom d' algorithmes randomisés , intègrent une entrée aléatoire.

Histoire

Le concept d'algorithmes existe depuis l'Antiquité. Les algorithmes arithmétiques , tels qu'un algorithme de division , ont été utilisés par les anciens mathématiciens babyloniens c. 2500 avant JC et mathématiciens égyptiens c. 1550 av. Les mathématiciens grecs ont ensuite utilisé des algorithmes en 240 avant JC dans le crible d'Eratosthène pour trouver des nombres premiers, et l' algorithme euclidien pour trouver le plus grand diviseur commun de deux nombres. Les mathématiciens arabes tels qu'al-Kindi au 9ème siècle ont utilisé des algorithmes cryptographiques pour briser le code , basés sur l'analyse de fréquence .

Le mot algorithme est dérivé du nom du mathématicien persan du IXe siècle Muhammad ibn Musa al-Khwarizmi . Al-Khwarizmi était un mathématicien, astronome , géographe et érudit de la Maison de la Sagesse à Bagdad , dont le nom signifie "le natif de Khwarazm ", une région qui faisait partie du Grand Iran et se trouve maintenant en Ouzbékistan . Vers l'an 825, al-Khwarizmi écrivit un traité en langue arabe sur le système numérique hindou-arabe , qui fut traduit en latin au XIIe siècle. Le manuscrit commence par la phrase Dixit Algorizmi ("Ainsi parlait Al-Khwarizmi"), où "Algorizmi" était la latinisation du nom d'Al-Khwarizmi par le traducteur. Al-Khwarizmi était le mathématicien le plus lu en Europe à la fin du Moyen Âge, principalement à travers un autre de ses livres, l' Algèbre . En latin médiéval tardif, algorismus , anglais « algorism », la corruption de son nom, signifiait le « système de numération décimale ». Au 15ème siècle, sous l'influence du mot grec ἀριθμός ( arithmos ), "nombre" ( cf. "arithmétique"), le mot latin a été modifié en algorithmus , et le terme anglais correspondant "algorithme" est attesté pour la première fois au 17ème siècle; le sens moderne a été introduit au 19ème siècle.

Les mathématiques indiennes étaient principalement algorithmiques. Les algorithmes représentatifs de la tradition mathématique indienne vont des anciens Śulbasūtrās aux textes médiévaux de l' école du Kerala .

En anglais, le mot algorithme a été utilisé pour la première fois vers 1230, puis par Chaucer en 1391. L'anglais a adopté le terme français, mais ce n'est qu'à la fin du 19ème siècle que "algorithme" a pris le sens qu'il a en anglais moderne.

Une autre utilisation précoce du mot est à partir de 1240, dans un manuel intitulé Carmen d'Algorismo composé par Alexandre de Villedieu . Cela commence par :

Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris.

qui se traduit par :

L'algorisme est l'art par lequel nous utilisons actuellement ces chiffres indiens, qui sont au nombre de deux fois cinq.

Le poème est long de quelques centaines de lignes et résume l'art de calculer avec les nouveaux dés indiens de style ( Tali Indorum ), ou chiffres hindous.

Une formalisation partielle du concept moderne d'algorithme a commencé avec des tentatives pour résoudre le problème d' Entscheidungsproblem (problème de décision) posé par David Hilbert en 1928. Les formalisations ultérieures ont été encadrées comme des tentatives de définition de la « calculabilité effective » ou de la «méthode efficace». Ces formalisations comprenaient les fonctions récursives de GödelHerbrandKleene de 1930, 1934 et 1935, le lambda calcul d' Alonzo Church de 1936, la Formulation 1 d' Emil Post de 1936 et les machines de Turing d' Alan Turing de 1936–37 et 1939.

Définition informelle

Une définition informelle pourrait être "un ensemble de règles qui définit précisément une séquence d'opérations", qui inclurait tous les programmes informatiques (y compris les programmes qui n'effectuent pas de calculs numériques), et (par exemple) toute procédure bureaucratique prescrite ou recette de livre de cuisine .

En général, un programme n'est un algorithme que s'il finit par s'arrêter, même si des boucles infinies peuvent parfois s'avérer souhaitables.

Un exemple prototypique d'un algorithme est l' algorithme euclidien , qui est utilisé pour déterminer le diviseur commun maximal de deux entiers ; un exemple (il y en a d'autres) est décrit par l' organigramme ci-dessus et comme exemple dans une section ultérieure.

Boolos, Jeffrey & 1974, 1999 proposent une signification informelle du mot "algorithme" dans la citation suivante :

Aucun être humain ne peut écrire assez vite, ou assez longtemps, ou assez petit† (†"de plus en plus petit sans limite... vous essaieriez d'écrire sur des molécules, sur des atomes, sur des électrons") pour lister tous les membres d'un ensemble infini dénombrable en écrivant leurs noms, l'un après l'autre, dans une certaine notation. Mais les humains peuvent faire quelque chose d'aussi utile, dans le cas de certains ensembles dénombrables infinis : ils peuvent donner des instructions explicites pour déterminer le n ième membre de l'ensemble , pour n fini arbitraire . De telles instructions doivent être données assez explicitement, sous une forme telle qu'elles pourraient être suivies par une machine à calculer , ou par un humain qui n'est capable d'effectuer que des opérations très élémentaires sur des symboles.

Un "ensemble dénombrable infini" est celui dont les éléments peuvent être mis en correspondance biunivoque avec les nombres entiers. Ainsi Boolos et Jeffrey disent qu'un algorithme implique des instructions pour un processus qui "crée" des entiers de sortie à partir d'un entier "d'entrée" arbitraire ou d'entiers qui, en théorie, peuvent être arbitrairement grands. Par exemple, un algorithme peut être une équation algébrique telle que y = m + n (c'est-à-dire deux "variables d'entrée" arbitraires m et n qui produisent une sortie y ), mais les tentatives de divers auteurs pour définir la notion indiquent que le mot implique bien plus que cela, quelque chose de l'ordre de (pour l'exemple d'addition):

Des instructions précises (dans un langage compris par "l'ordinateur") pour un processus rapide, efficace et "bon" qui spécifie les "mouvements" de "l'ordinateur" (machine ou humain, équipé des informations et capacités internes nécessaires) pour trouver, décoder, puis traiter des entiers/symboles d'entrée arbitraires m et n , symboles + et = ... et produire "effectivement", dans un temps "raisonnable", un entier de sortie y à un endroit spécifié et dans un format spécifié.

Le concept d' algorithme est également utilisé pour définir la notion de décidabilité , une notion centrale pour expliquer comment les systèmes formels naissent à partir d'un petit ensemble d' axiomes et de règles. En logique , le temps nécessaire à un algorithme pour se terminer ne peut pas être mesuré, car il n'est apparemment pas lié à la dimension physique habituelle. De ces incertitudes, qui caractérisent les travaux en cours, découle l'indisponibilité d'une définition de l' algorithme qui convienne à la fois à l'usage concret (dans un certain sens) et abstrait du terme.

La plupart des algorithmes sont destinés à être implémentés sous forme de programmes informatiques . Cependant, les algorithmes sont également mis en œuvre par d'autres moyens, comme dans un réseau de neurones biologiques (par exemple, le cerveau humain mettant en œuvre l' arithmétique ou un insecte à la recherche de nourriture), dans un circuit électrique ou dans un dispositif mécanique.

Formalisation

Les algorithmes sont essentiels à la façon dont les ordinateurs traitent les données. De nombreux programmes informatiques contiennent des algorithmes qui détaillent les instructions spécifiques qu'un ordinateur doit exécuter - dans un ordre spécifique - pour effectuer une tâche spécifique, comme le calcul des chèques de paie des employés ou l'impression des bulletins des étudiants. Ainsi, un algorithme peut être considéré comme n'importe quelle séquence d'opérations qui peut être simulée par un système Turing-complet . Les auteurs qui affirment cette thèse incluent Minsky (1967), Savage (1987) et Gurevich (2000) :

Minsky : "Mais nous soutiendrons aussi, avec Turing... que toute procédure qui pourrait "naturellement" être qualifiée d'efficace, peut, en fait, être réalisée par une (simple) machine. Bien que cela puisse paraître extrême, les arguments... . en sa faveur sont difficiles à réfuter". 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 … selon Savage [1987], un algorithme est un processus de calcul défini par une machine de Turing".

Les machines de Turing peuvent définir des processus de calcul qui ne se terminent pas. Les définitions informelles des algorithmes exigent généralement que l'algorithme se termine toujours. Cette exigence rend la tâche de décider si une procédure formelle est un algorithme impossible dans le cas général - en raison d'un théorème majeur de la théorie de la calculabilité connu sous le nom de problème d'arrêt .

Généralement, lorsqu'un algorithme est associé au traitement d'informations, les données peuvent être lues à partir d'une source d'entrée, écrites sur un périphérique de sortie et stockées pour un traitement ultérieur. Les données stockées sont considérées comme faisant partie de l'état interne de l'entité exécutant l'algorithme. En pratique, l'état est stocké dans une ou plusieurs structures de données .

Pour certains de ces processus de calcul, l'algorithme doit être rigoureusement défini : et spécifié dans la manière dont il s'applique dans toutes les circonstances possibles qui pourraient survenir. Cela signifie que toute démarche conditionnelle doit être systématiquement traitée, au cas par cas ; les critères pour chaque cas doivent être clairs (et calculables).

Parce qu'un algorithme est une liste précise d'étapes précises, l'ordre de calcul est toujours crucial pour le fonctionnement de l'algorithme. Les instructions sont généralement supposées être répertoriées explicitement et sont décrites comme commençant "du haut" et allant "de bas en bas" - une idée qui est décrite plus formellement par le flux de contrôle .

Jusqu'à présent, la discussion sur la formalisation d'un algorithme a supposé les prémisses de la programmation impérative . C'est la conception la plus courante - celle qui tente de décrire une tâche par des moyens discrets et «mécaniques». Unique à cette conception d'algorithmes formalisés est l' opération d'affectation , qui fixe la valeur d'une variable. Il découle de l'intuition de la « mémoire » comme bloc-notes. Un exemple d'une telle affectation peut être trouvé ci-dessous.

Pour certaines conceptions alternatives de ce qui constitue un algorithme, voir programmation fonctionnelle et programmation logique .

Exprimer des algorithmes

Les algorithmes peuvent être exprimés dans de nombreux types de notation, y compris les langages naturels , le pseudocode , les organigrammes , les drakon-charts , les langages de programmation ou les tables de contrôle (traités par des interpréteurs ). Les expressions en langage naturel des algorithmes ont tendance à être verbeuses et ambiguës, et sont rarement utilisées pour des algorithmes complexes ou techniques. Le pseudo-code, les organigrammes, les diagrammes drakon et les tables de contrôle sont des moyens structurés d'exprimer des algorithmes qui évitent de nombreuses ambiguïtés courantes dans les déclarations basées sur le langage naturel. Les langages de programmation sont principalement destinés à exprimer des algorithmes sous une forme exécutable par un ordinateur, mais sont également souvent utilisés pour définir ou documenter des algorithmes.

Il existe une grande variété de représentations possibles et on peut exprimer un programme de machine de Turing donné comme une séquence de tables machine (voir machine à états finis , table de transition d'état et table de contrôle pour plus), sous forme d'organigrammes et de drakon-charts (voir diagramme d'état pour en savoir plus), ou sous forme de code machine rudimentaire ou de code assembleur appelé "ensembles de quadruples" (voir Machine de Turing pour en savoir plus).

Les représentations des algorithmes peuvent être classées en trois niveaux acceptés de description de la machine de Turing, comme suit :

1 Description de haut niveau
"... prose pour décrire un algorithme, en ignorant les détails d'implémentation. A ce niveau, nous n'avons pas besoin de mentionner comment la machine gère sa bande ou sa tête."
2 Description de la mise en œuvre
"...la prose utilisée pour définir la façon dont la machine de Turing utilise sa tête et la façon dont elle stocke les données sur sa bande. A ce niveau, nous ne donnons pas de détails sur les états ou la fonction de transition."
3 Description formelle
Le plus détaillé, "niveau le plus bas", donne la "table d'état" de la machine de Turing.

Pour un exemple de l'algorithme simple "Add m+n" décrit dans les trois niveaux, voir Exemples .

Concevoir

La conception d'algorithmes fait référence à une méthode ou à un processus mathématique de résolution de problèmes et d'algorithmes d'ingénierie. La conception d'algorithmes fait partie de nombreuses théories de solutions, telles que diviser pour mieux régner ou la programmation dynamique dans la recherche opérationnelle . Les techniques de conception et de mise en œuvre de conceptions d'algorithmes sont également appelées modèles de conception d'algorithmes, avec des exemples comprenant le modèle de méthode de modèle et le modèle de décorateur.

L'un des aspects les plus importants de la conception d'algorithmes est l'efficacité des ressources (durée d'exécution, utilisation de la mémoire) ; la notation grand O est utilisée pour décrire par exemple la croissance du temps d'exécution d'un algorithme à mesure que la taille de son entrée augmente.

Étapes typiques du développement d'algorithmes :

  1. Définition du problème
  2. Développement d'un modèle
  3. Spécification de l'algorithme
  4. Conception d'un algorithme
  5. Vérification de l' exactitude de l'algorithme
  6. Analyse d'algorithme
  7. Implémentation de l'algorithme
  8. Test du programme
  9. Préparation de la documentation

Algorithmes informatiques

Algorithme logique NAND implémenté électroniquement dans la puce 7400
Exemples d'organigrammes des structures canoniques de Böhm-Jacopini : la SEQUENCE (rectangles descendant la page), le WHILE-DO et le IF-THEN-ELSE. Les trois structures sont constituées du GOTO conditionnel primitif ( IF test THEN GOTO step xxx, représenté par un losange), du GOTO inconditionnel (rectangle), de divers opérateurs d'affectation (rectangle) et de HALT (rectangle). L'imbrication de ces structures à l'intérieur des blocs d'affectation donne des diagrammes complexes (cf. Tausworthe 1977 : 100, 114).

Programmes "élégants" (compacts), programmes "bons" (rapides) : La notion de "simplicité et élégance" apparaît de manière informelle chez Knuth et précisément chez Chaitin :

Knuth: "... nous voulons de bons algorithmes dans un sens esthétique vaguement défini. Un critère ... est le temps nécessaire pour exécuter l'algorithme .... D'autres critères sont l'adaptabilité de l'algorithme aux ordinateurs, sa simplicité et élégance, etc."
Chaitin : "... un programme est 'élégant', je veux dire par là que c'est le plus petit programme possible pour produire la sortie qu'il fait"

Chaitin fait précéder sa définition par : "Je vais montrer que vous ne pouvez pas prouver qu'un programme est 'élégant ' " - une telle preuve résoudrait le problème de Halting (ibid).

Algorithme versus fonction calculable par un algorithme : Pour une fonction donnée plusieurs algorithmes peuvent exister. Cela est vrai, même sans étendre le jeu d'instructions disponible à la disposition du programmeur. Rogers observe que "Il est ... important de faire la distinction entre la notion d' algorithme , c'est-à-dire la procédure et la notion de fonction calculable par algorithme , c'est-à-dire le mappage produit par la procédure. La même fonction peut avoir plusieurs algorithmes différents".

Malheureusement, il peut y avoir un compromis entre la qualité (vitesse) et l'élégance (compacité) - un programme élégant peut prendre plus d'étapes pour effectuer un calcul qu'un programme moins élégant. Un exemple qui utilise l'algorithme d'Euclide apparaît ci-dessous.

Ordinateurs (et ordinateurs), modèles de calcul : Un ordinateur (ou "ordinateur" humain) est un type restreint de machine, un "dispositif mécanique déterministe discret" qui suit aveuglément ses instructions. Les modèles primitifs de Melzak et Lambek ont ​​réduit cette notion à quatre éléments : (i) des emplacements discrets et distinguables , (ii) des compteurs discrets et indiscernables (iii) un agent, et (iv) une liste d'instructions qui sont efficaces par rapport à la capacité du agent.

Minsky décrit une variante plus sympathique du modèle "abaque" de Lambek dans ses "Bases très simples pour la calculabilité ". La machine de Minsky procède séquentiellement à travers ses cinq (ou six, selon la façon dont on compte) les instructions à moins qu'un IF-THEN GOTO conditionnel ou un GOTO inconditionnel ne modifie le déroulement du programme hors séquence. Outre HALT, la machine de Minsky comprend trois opérations d'affectation (remplacement, substitution) : ZERO (par exemple, le contenu de l'emplacement remplacé par 0 : L ← 0), SUCCESSOR (par exemple, L ← L+1) et DECREMENT (par exemple, L ← L − 1 ). Il est rare qu'un programmeur doive écrire du "code" avec un jeu d'instructions aussi limité. Mais Minsky montre (comme le font Melzak et Lambek) que sa machine est Turing complète avec seulement quatre types généraux d'instructions : GOTO conditionnel, GOTO inconditionnel, affectation/remplacement/substitution et HALT. Cependant, quelques instructions d'assignation différentes (par exemple DECREMENT, INCREMENT et ZERO/CLEAR/EMPTY pour une machine de Minsky) sont également requises pour l'exhaustivité de Turing ; leur spécification exacte dépend quelque peu du concepteur. Le GOTO inconditionnel est pratique ; il peut être construit en initialisant à zéro un emplacement dédié par exemple l'instruction « Z ← 0 » ; ensuite l'instruction IF Z=0 THEN GOTO xxx est inconditionnelle.

Simulation d'un algorithme : langage informatique (informatique) : Knuth conseille au lecteur que "la meilleure façon d'apprendre un algorithme est de l'essayer... immédiatement prendre un stylo et du papier et travailler sur un exemple". Mais qu'en est-il d'une simulation ou d'une exécution de la réalité ? Le programmeur doit traduire l'algorithme dans un langage que le simulateur/ordinateur/ordinateur peut exécuter efficacement . Stone en donne un exemple : lors du calcul des racines d'une équation quadratique, l'ordinateur doit savoir prendre une racine carrée. Si ce n'est pas le cas, l'algorithme, pour être efficace, doit fournir un ensemble de règles pour extraire une racine carrée.

Cela signifie que le programmeur doit connaître un "langage" efficace par rapport à l'agent informatique cible (ordinateur/ordinateur).

Mais quel modèle utiliser pour la simulation ? Van Emde Boas observe "même si nous basons la théorie de la complexité sur des machines abstraites plutôt que concrètes, l'arbitraire du choix d'un modèle demeure. C'est à ce stade qu'intervient la notion de simulation ". Lorsque la vitesse est mesurée, le jeu d'instructions est important. Par exemple, le sous-programme de l'algorithme d'Euclide pour calculer le reste s'exécuterait beaucoup plus rapidement si le programmeur disposait d'une instruction " module " plutôt que d'une simple soustraction (ou pire : juste le "décrément" de Minsky).

Programmation structurée, structures canoniques : selon la thèse de Church-Turing , tout algorithme peut être calculé par un modèle connu pour être complet de Turing , et selon les démonstrations de Minsky, l'exhaustivité de Turing ne nécessite que quatre types d'instructions : GOTO conditionnel, GOTO inconditionnel, affectation, HALT. Kemeny et Kurtz observent que, alors que l'utilisation « indisciplinée » des GOTO inconditionnels et des GOTO IF-THEN conditionnels peut entraîner un « code spaghetti », un programmeur peut écrire des programmes structurés en utilisant uniquement ces instructions ; d'autre part "il est aussi possible, et pas trop difficile, d'écrire des programmes mal structurés dans un langage structuré". Tausworthe augmente les trois structures canoniques de Böhm-Jacopini : SEQUENCE, IF-THEN-ELSE et WHILE-DO, avec deux autres : DO-WHILE et CASE. Un avantage supplémentaire d'un programme structuré est qu'il se prête à des preuves d'exactitude utilisant l'induction mathématique .

Symboles d'organigramme canoniques : L'aide graphique appelée organigramme offre un moyen de décrire et de documenter un algorithme (et un programme informatique qui lui correspond). Comme le déroulement du programme d'une machine Minsky, un organigramme commence toujours en haut d'une page et continue vers le bas. Ses principaux symboles ne sont que quatre : la flèche dirigée indiquant le déroulement du programme, le rectangle (SEQUENCE, GOTO), le losange (IF-THEN-ELSE) et le point (OR-tie). Les structures canoniques Böhm-Jacopini sont faites de ces formes primitives. Les sous-structures peuvent "s'emboîter" dans des rectangles, mais seulement si une seule sortie se produit depuis la superstructure. Les symboles et leur utilisation pour construire les structures canoniques sont présentés dans le diagramme.

Exemples

Exemple d'algorithme

L'un des algorithmes les plus simples consiste à trouver le plus grand nombre dans une liste de nombres d'ordre aléatoire. Pour trouver la solution, il faut regarder chaque numéro de la liste. De là découle un algorithme simple, qui peut être énoncé dans une description de haut niveau en prose anglaise, comme suit :

Description de haut niveau :

  1. S'il n'y a pas de nombres dans l'ensemble, alors il n'y a pas de nombre le plus élevé.
  2. Supposons que le premier nombre de l'ensemble est le plus grand nombre de l'ensemble.
  3. Pour chaque nombre restant dans l'ensemble : si ce nombre est supérieur au plus grand nombre actuel, considérez ce nombre comme étant le plus grand nombre de l'ensemble.
  4. Lorsqu'il ne reste plus de nombres dans l'ensemble à itérer, considérez que le plus grand nombre actuel est le plus grand nombre de l'ensemble.

Description (quasi-)formelle : Écrit en prose mais beaucoup plus proche du langage de haut niveau d'un programme informatique, voici le codage plus formel de l'algorithme en pseudocode ou code pidgin :

Algorithm LargestNumber
Input: A list of numbers L.
Output: The largest number in the list L.
if L.size = 0 return null
largestL[0]
for each item in L, do
    if item > largest, then
        largestitem
return largest
  • "←" indique une affectation . Par exemple, « plus grandélément » signifie que la valeur du plus grand change pour la valeur de l'élément .
  • " return " termine l'algorithme et renvoie la valeur suivante.

Algorithme d'Euclide

En mathématiques , l' algorithme d'Euclide , ou algorithme d'Euclide , est une méthode efficace pour calculer le plus grand diviseur commun (PGCD) de deux entiers (nombres), le plus grand nombre qui les divise tous les deux sans reste . Il porte le nom de l'ancien mathématicien grec Euclide , qui l'a décrit pour la première fois dans ses Éléments ( vers  300 av . J.-C. ). C'est l'un des plus anciens algorithmes couramment utilisés. Il peut être utilisé pour réduire les fractions à leur forme la plus simple et fait partie de nombreux autres calculs de théorie des nombres et cryptographiques.

L'exemple de diagramme de l'algorithme d'Euclide de TL Heath (1908), avec plus de détails ajoutés. Euclide ne va pas au-delà d'une troisième mesure et ne donne aucun exemple numérique. Nicomaque donne l'exemple de 49 et 21 : « Je soustrais le moins du plus grand ; il reste 28 ; puis de nouveau j'en soustrais le même 21 (car c'est possible) ; il reste 7 ; je soustrais ceci de 21, 14 est à gauche ; auquel je soustrais encore 7 (car cela est possible) ; il reste 7, mais 7 ne peut pas être soustrait de 7. » Heath commente que "La dernière phrase est curieuse, mais sa signification est assez évidente, tout comme la signification de la phrase sur la fin 'à un seul et même nombre'." (Heath 1908: 300).

Euclide pose ainsi le problème : "Étant donné deux nombres non premiers l'un de l'autre, trouver leur plus grande commune mesure". Il définit « Un nombre [être] une multitude composée d'unités » : un nombre comptant, un entier positif ne comprenant pas zéro. "Mesurer" consiste à placer une longueur de mesure plus courte s successivement ( q fois) le long de la longueur l jusqu'à ce que la partie restante r soit inférieure à la longueur s la plus courte . En termes modernes, le reste r = l - q × s , q étant le quotient, ou le reste r est le "module", la partie entière-fractionnelle restante après la division.

Pour que la méthode d'Euclide réussisse, les longueurs de départ doivent satisfaire à deux exigences : (i) les longueurs ne doivent pas être nulles, ET (ii) la soustraction doit être "correcte" ; c'est-à-dire qu'un test doit garantir que le plus petit des deux nombres est soustrait du plus grand (ou les deux peuvent être égaux pour que leur soustraction donne zéro).

La preuve originale d'Euclide ajoute une troisième exigence : les deux longueurs ne doivent pas être premières l'une par rapport à l'autre. Euclide a stipulé cela afin qu'il puisse construire une preuve reductio ad absurdum que la mesure commune des deux nombres est en fait la plus grande . Alors que l'algorithme de Nicomaque est le même que celui d'Euclide, lorsque les nombres sont premiers les uns par rapport aux autres, il donne le nombre "1" pour leur mesure commune. Donc, pour être précis, ce qui suit est vraiment l'algorithme de Nicomaque.

Une expression graphique de l'algorithme d'Euclide pour trouver le plus grand diviseur commun pour 1599 et 650.
 1599 = 650×2 + 299
 650 = 299×2 + 52
 299 = 52×5 + 39
 52 = 39×1 + 13
 39 = 13×3 + 0

Langage informatique pour l'algorithme d'Euclide

Seuls quelques types d'instructions sont nécessaires pour exécuter l'algorithme d'Euclide - certains tests logiques (GOTO conditionnel), GOTO inconditionnel, affectation (remplacement) et soustraction.

  • Un emplacement est symbolisé par une ou plusieurs lettres majuscules, par exemple S, A, etc.
  • La quantité variable (nombre) dans un emplacement est écrite en lettre(s) minuscule(s) et (généralement) associée au nom de l'emplacement. Par exemple, l'emplacement L au début peut contenir le nombre l = 3009.

Un programme inélégant pour l'algorithme d'Euclide

"Inelegant" est une traduction de la version de l'algorithme de Knuth avec une boucle de reste basée sur la soustraction remplaçant son utilisation de la division (ou une instruction "module"). Dérivé de Knuth 1973 : 2–4. Selon les deux nombres, "Inelegant" peut calculer le pgcd en moins d'étapes que "Elegant".

L'algorithme suivant est encadré comme la version en quatre étapes de Knuth d'Euclide et de Nicomaque, mais, plutôt que d'utiliser la division pour trouver le reste, il utilise des soustractions successives de la longueur la plus courte s de la longueur restante r jusqu'à ce que r soit inférieur à s . La description de haut niveau, indiquée en gras, est adaptée de Knuth 1973 : 2–4 :

ENTRÉE :

1 [Into two locations L and S put the numbers l and s that represent the two lengths]:
INPUT L, S
2 [Initialize R: make the remaining length r equal to the starting/initial/input length l]:
R ← L

E0 : [Assurez-vous que rs .]

3 [Ensure the smaller of the two numbers is in S and the larger in R]:
IF R > S THEN
the contents of L is the larger number so skip over the exchange-steps 4, 5 and 6:
GOTO step 7
ELSE
swap the contents of R and S.
4 L ← R (this first step is redundant, but is useful for later discussion).
5 R ← S
6 S ← L

E1 : [Trouver le reste] : jusqu'à ce que la longueur restante r dans R soit inférieure à la longueur la plus courte s dans S, soustrayez à plusieurs reprises le nombre de mesure s dans S de la longueur restante r dans R.

7 IF S > R THEN
done measuring so
GOTO 10
ELSE
measure again,
8 R ← R − S
9 [Remainder-loop]:
GOTO 7.

E2 : [Le reste est-il nul ?] : SOIT (i) la dernière mesure était exacte, le reste dans R est nul, et le programme peut s'arrêter, SOIT (ii) l'algorithme doit continuer : la dernière mesure a laissé un reste dans R inférieur au nombre de mesure dans S.

10 IF R = 0 THEN
done so
GOTO step 15
ELSE
CONTINUE TO step 11,

E3 : [Interchange s et r ] : La noix de l'algorithme d'Euclide. Utilisez le reste r pour mesurer ce qui était auparavant un plus petit nombre s ; L sert d'emplacement temporaire.

11 L ← R
12 R ← S
13 S ← L
14 [Repeat the measuring process]:
GOTO 7

SORTIE :

15 [Done. S contains the greatest common divisor]:
PRINT S

FAIT :

16 HALT, END, STOP.

Un programme élégant pour l'algorithme d'Euclide

La version suivante de l'algorithme d'Euclide ne nécessite que six instructions de base pour faire ce que treize sont tenus de faire par "Inelegant" ; pire, "Inelegant" nécessite plus de types d'instructions. L'organigramme de "Elegant" se trouve en haut de cet article. Dans le langage Basic (non structuré), les étapes sont numérotées et l'instruction est l'instruction d'affectation symbolisée par ←. LET [] = []

  5 REM Euclid's algorithm for greatest common divisor
  6 PRINT "Type two integers greater than 0"
  10 INPUT A,B
  20 IF B=0 THEN GOTO 80
  30 IF A > B THEN GOTO 60
  40 LET B=B-A
  50 GOTO 20
  60 LET A=A-B
  70 GOTO 20
  80 PRINT A
  90 END

Comment "Elegant" fonctionne : à la place d'une "boucle Euclid" externe, "Elegant" va et vient entre deux "co-boucles", une boucle A > B qui calcule A ← A − B, et une boucle B ≤ A qui calcule B ← B − A. Cela fonctionne parce que, quand enfin la diminution M est inférieure ou égale à la soustraction S (Différence = Minuend − Subtrahend), la diminution peut devenir s (la nouvelle longueur de mesure) et la soustraction peut devient le nouveau r (la longueur à mesurer); autrement dit le "sens" de la soustraction s'inverse.

La version suivante peut être utilisée avec les langages de programmation de la famille C :

// Euclid's algorithm for greatest common divisor
int euclidAlgorithm (int A, int B) {
     A = abs(A);
     B = abs(B);
     while (B != 0) {
          while (A > B) {
               A = A-B;
          }
          B = B-A;
     }
     return A;
}

Tester les algorithmes d'Euclide

Un algorithme fait-il ce que son auteur veut qu'il fasse ? Quelques cas de test donnent généralement une certaine confiance dans la fonctionnalité de base. Mais les tests ne suffisent pas. Pour les cas de test, une source utilise 3009 et 884. Knuth a suggéré 40902, 24140. Un autre cas intéressant est les deux nombres relativement premiers 14157 et 5950.

Mais des "cas exceptionnels" doivent être identifiés et testés. "Inelegant" fonctionnera-t-il correctement lorsque R > S, S > R, R = S ? Idem pour "Elegant" : B > A, A > B, A = B ? (Oui à tous). Que se passe-t-il lorsqu'un nombre est nul, les deux nombres sont nuls ? ("Inelegant" calcule pour toujours dans tous les cas ; "Elegant" calcule pour toujours lorsque A = 0.) Que se passe-t-il si des nombres négatifs sont saisis ? Nombres fractionnaires ? Si les nombres d'entrée, c'est-à-dire le domaine de la fonction calculée par l'algorithme/programme, ne doivent inclure que des entiers positifs incluant zéro, alors les échecs à zéro indiquent que l'algorithme (et le programme qui l' instancie ) est une fonction partielle plutôt que une fonction totale . Un échec notable dû à des exceptions est l'échec de la fusée Ariane 5 Flight 501 (4 juin 1996).

Preuve de l'exactitude du programme par l'utilisation de l'induction mathématique : Knuth démontre l'application de l'induction mathématique à une version "étendue" de l'algorithme d'Euclide, et il propose "une méthode générale applicable pour prouver la validité de tout algorithme". Tausworthe propose qu'une mesure de la complexité d'un programme soit la longueur de sa preuve d'exactitude.

Mesurer et améliorer les algorithmes d'Euclid

Élégance (compacité) contre bonté (vitesse) : Avec seulement six instructions de base, "Elegant" est le grand gagnant, comparé à "Inelegant" à treize instructions. Cependant, "Inelegant" est plus rapide (il arrive à HALT en moins d'étapes). L'analyse de l'algorithme indique pourquoi c'est le cas : "Elegant" effectue deux tests conditionnels dans chaque boucle de soustraction, tandis que "Inelegant" n'en effectue qu'un. Comme l'algorithme nécessite (généralement) de nombreuses boucles, on perd en moyenne beaucoup de temps à faire un "B = 0?" test qui n'est nécessaire qu'après le calcul du reste.

Les algorithmes peuvent-ils être améliorés ? : Une fois que le programmeur juge un programme "adapté" et "efficace" - c'est-à-dire qu'il calcule la fonction voulue par son auteur - alors la question devient, peut-il être amélioré ?

La compacité de "Inelegant" peut être améliorée par l'élimination de cinq étapes. Mais Chaitin a prouvé que le compactage d'un algorithme ne peut pas être automatisé par un algorithme généralisé ; au contraire, cela ne peut être fait que de manière heuristique ; c'est-à-dire par recherche exhaustive (exemples à trouver chez Busy beaver ), essai et erreur, intelligence, perspicacité, application du raisonnement inductif , etc. Observez que les étapes 4, 5 et 6 sont répétées dans les étapes 11, 12 et 13. Comparaison avec "Elegant" indique que ces étapes, ainsi que les étapes 2 et 3, peuvent être éliminées. Cela réduit le nombre d'instructions de base de treize à huit, ce qui le rend "plus élégant" que "Elegant", à neuf étapes.

La vitesse de "Elegant" peut être améliorée en déplaçant le "B=0?" test en dehors des deux boucles de soustraction. Cette modification nécessite l'ajout de trois instructions (B = 0?, A = 0?, GOTO). Désormais, "Elegant" calcule les numéros d'exemple plus rapidement ; si c'est toujours le cas pour n'importe quel A, B et R, S donnés, cela nécessiterait une analyse détaillée.

Analyse algorithmique

Il est souvent important de savoir quelle quantité d'une ressource particulière (telle que le temps ou le stockage) est théoriquement nécessaire pour un algorithme donné. Des méthodes ont été développées pour l' analyse d'algorithmes afin d'obtenir de telles réponses quantitatives (estimations) ; par exemple, un algorithme qui additionne les éléments d'une liste de n nombres aurait une exigence de temps de O(n) , en utilisant la notation big O . À tout moment, l'algorithme n'a besoin de se souvenir que de deux valeurs : la somme de tous les éléments jusqu'à présent et sa position actuelle dans la liste d'entrée. Par conséquent, on dit qu'il a un besoin d'espace de O(1) , si l'espace requis pour stocker les nombres d'entrée n'est pas compté, ou O(n) s'il est compté.

Différents algorithmes peuvent accomplir la même tâche avec un ensemble d'instructions différent en moins ou plus de temps, d'espace ou d'« effort » que d'autres. Par exemple, un algorithme de recherche binaire (avec un coût O(log n) ) surpasse une recherche séquentielle (coût O(n) ) lorsqu'il est utilisé pour des recherches de table sur des listes ou des tableaux triés.

Formelle versus empirique

L' analyse et l'étude des algorithmes est une discipline de l'informatique et est souvent pratiquée de manière abstraite sans l'utilisation d'un langage de programmation ou d'une implémentation spécifique. En ce sens, l'analyse d'algorithmes ressemble à d'autres disciplines mathématiques en ce sens qu'elle se concentre sur les propriétés sous-jacentes de l'algorithme et non sur les spécificités d'une implémentation particulière. Habituellement, le pseudocode est utilisé pour l'analyse car il s'agit de la représentation la plus simple et la plus générale. Cependant, en fin de compte, la plupart des algorithmes sont généralement implémentés sur des plates-formes matérielles/logicielles particulières et leur efficacité algorithmique est finalement mise à l'épreuve en utilisant du code réel. Pour la solution d'un problème "ponctuel", l'efficacité d'un algorithme particulier peut ne pas avoir de conséquences significatives (à moins que n ne soit extrêmement grand), mais pour les algorithmes conçus pour un usage scientifique interactif rapide, commercial ou de longue durée, cela peut être critique. La mise à l'échelle d'un petit n à un grand n expose fréquemment des algorithmes inefficaces qui sont autrement bénins.

Les tests empiriques sont utiles car ils peuvent révéler des interactions inattendues qui affectent les performances. Des repères peuvent être utilisés pour comparer avant/après les améliorations potentielles d'un algorithme après l'optimisation du programme. Cependant, les tests empiriques ne peuvent pas remplacer l'analyse formelle et ne sont pas triviaux à effectuer de manière équitable.

Efficacité d'exécution

Pour illustrer les améliorations potentielles possibles même dans des algorithmes bien établis, une innovation significative récente, relative aux algorithmes FFT (largement utilisés dans le domaine du traitement d'images), peut réduire jusqu'à 1 000 fois le temps de traitement pour des applications comme l'imagerie médicale. En général, les améliorations de la vitesse dépendent des propriétés particulières du problème, qui sont très courantes dans les applications pratiques. Des accélérations de cette ampleur permettent aux appareils informatiques qui utilisent largement le traitement d'image (comme les appareils photo numériques et les équipements médicaux) de consommer moins d'énergie.

Classification

Il existe différentes manières de classer les algorithmes, chacune avec ses propres mérites.

Par implémentation

Une façon de classer les algorithmes est par les moyens de mise en œuvre.

int gcd(int A, int B) {
    if (B == 0)
        return A;
    else if (A > B)
        return gcd(A-B,B);
    else
        return gcd(A,B-A);
}
Implémentation C récursive de l'algorithme d'Euclide à partir de l' organigramme ci -dessus
Récursivité
Un algorithme récursif est un algorithme qui s'invoque (se réfère) à plusieurs reprises jusqu'à ce qu'une certaine condition (également connue sous le nom de condition de terminaison) corresponde, ce qui est une méthode commune à la programmation fonctionnelle . Les algorithmes itératifs utilisent des constructions répétitives comme des boucles et parfois des structures de données supplémentaires comme des piles pour résoudre les problèmes donnés. Certains problèmes sont naturellement adaptés à une implémentation ou à l'autre. Par exemple, les tours de Hanoï sont bien comprises en utilisant une implémentation récursive. Chaque version récursive a une version itérative équivalente (mais éventuellement plus ou moins complexe), et vice versa.
Logique
Un algorithme peut être considéré comme une déduction logique contrôlée . Cette notion peut être exprimée par : Algorithme = logique + contrôle . La composante logique exprime les axiomes pouvant être utilisés dans le calcul et la composante de commande détermine la manière dont la déduction est appliquée aux axiomes. C'est la base du paradigme de la programmation logique . Dans les langages de programmation logique pure, le composant de contrôle est fixe et les algorithmes sont spécifiés en fournissant uniquement le composant logique. L'attrait de cette approche est la sémantique élégante : un changement dans les axiomes produit un changement bien défini dans l'algorithme.
Série, parallèle ou distribué
Les algorithmes sont généralement discutés avec l'hypothèse que les ordinateurs exécutent une instruction d'un algorithme à la fois. Ces ordinateurs sont parfois appelés ordinateurs série. Un algorithme conçu pour un tel environnement est appelé un algorithme sériel, par opposition aux algorithmes parallèles ou aux algorithmes distribués . Les algorithmes parallèles tirent parti des architectures informatiques où plusieurs processeurs peuvent travailler sur un problème en même temps, tandis que les algorithmes distribués utilisent plusieurs machines connectées à un réseau informatique . Les algorithmes parallèles ou distribués divisent le problème en sous-problèmes plus symétriques ou asymétriques et rassemblent les résultats. La consommation de ressources dans de tels algorithmes n'est pas seulement des cycles de processeur sur chaque processeur, mais également la surcharge de communication entre les processeurs. Certains algorithmes de tri peuvent être parallélisés efficacement, mais leur surcharge de communication est coûteuse. Les algorithmes itératifs sont généralement parallélisables. Certains problèmes n'ont pas d'algorithmes parallèles et sont appelés problèmes intrinsèquement sériels.
Déterministe ou non déterministe
Les algorithmes déterministes résolvent le problème avec une décision exacte à chaque étape de l'algorithme, tandis que les algorithmes non déterministes résolvent les problèmes par supposition, bien que les suppositions typiques soient rendues plus précises grâce à l'utilisation d' heuristiques .
Exact ou approximatif
Alors que de nombreux algorithmes parviennent à une solution exacte, les algorithmes d'approximation recherchent une approximation plus proche de la vraie solution. L'approximation peut être obtenue en utilisant une stratégie déterministe ou aléatoire. De tels algorithmes ont une valeur pratique pour de nombreux problèmes difficiles. L'un des exemples d'algorithme approché est le problème du sac à dos , où il existe un ensemble d'éléments donnés. Son objectif est d'emballer le sac à dos pour obtenir la valeur totale maximale. Chaque article a un certain poids et une certaine valeur. Le poids total pouvant être transporté ne dépasse pas un nombre fixe X. Ainsi, la solution doit tenir compte du poids des articles ainsi que de leur valeur.
Algorithme quantique
Ils fonctionnent sur un modèle réaliste de calcul quantique . Le terme est généralement utilisé pour les algorithmes qui semblent intrinsèquement quantiques, ou qui utilisent certaines caractéristiques essentielles de l'informatique quantique telles que la superposition quantique ou l'intrication quantique .

Par paradigme de conception

Une autre façon de classer les algorithmes est par leur méthodologie de conception ou leur paradigme . Il existe un certain nombre de paradigmes, différents les uns des autres. De plus, chacune de ces catégories comprend de nombreux types d'algorithmes différents. Certains paradigmes courants sont :

Recherche brutale ou exhaustive
C'est la méthode naïve d'essayer toutes les solutions possibles pour voir laquelle est la meilleure.
Diviser et conquérir
Un algorithme diviser pour régner réduit à plusieurs reprises une instance d'un problème à une ou plusieurs instances plus petites du même problème (généralement de manière récursive ) jusqu'à ce que les instances soient suffisamment petites pour être résolues facilement. Un tel exemple de diviser pour mieux régner est le tri par fusion . Le tri peut être effectué sur chaque segment de données après avoir divisé les données en segments et le tri de données entières peut être obtenu dans la phase de conquête en fusionnant les segments. Une variante plus simple de diviser pour mieux régner est appelée un algorithme de diminution et de conquête , qui résout un sous-problème identique et utilise la solution de ce sous-problème pour résoudre le plus gros problème. Diviser pour régner divise le problème en plusieurs sous-problèmes et l'étape de conquête est donc plus complexe que les algorithmes de diminution et de conquête. Un exemple d'algorithme de diminution et de conquête est l' algorithme de recherche binaire .
Recherche et énumération
De nombreux problèmes (comme jouer aux échecs ) peuvent être modélisés comme des problèmes sur des graphes . Un algorithme d'exploration de graphe spécifie des règles pour se déplacer dans un graphe et est utile pour de tels problèmes. Cette catégorie comprend également les algorithmes de recherche , l' énumération des branches et des liens et le retour arrière .
Algorithme randomisé
De tels algorithmes effectuent certains choix de manière aléatoire (ou pseudo-aléatoire). Ils peuvent être très utiles pour trouver des solutions approximatives à des problèmes où il peut être impossible de trouver des solutions exactes (voir la méthode heuristique ci-dessous). Pour certains de ces problèmes, on sait que les approximations les plus rapides doivent impliquer un certain caractère aléatoire . La question de savoir si les algorithmes randomisés avec une complexité temporelle polynomiale peuvent être les algorithmes les plus rapides pour certains problèmes est une question ouverte connue sous le nom de problème P versus NP . Il existe deux grandes classes de tels algorithmes :
  1. Les algorithmes de Monte Carlo renvoient une réponse correcte avec une probabilité élevée. Par exemple , RP est la sous-classe de ceux-ci qui s'exécutent en temps polynomial .
  2. Les algorithmes de Las Vegas renvoient toujours la bonne réponse, mais leur temps d'exécution n'est lié que de manière probabiliste, par exemple ZPP .
Réduction de la complexité
Cette technique consiste à résoudre un problème difficile en le transformant en un problème mieux connu pour lequel nous disposons (espérons-le) d'algorithmes asymptotiquement optimaux . Le but est de trouver un algorithme réducteur dont la complexité n'est pas dominée par celle de l'algorithme réduit résultant. Par exemple, un algorithme de sélection pour trouver la médiane dans une liste non triée implique d'abord de trier la liste (la partie chère) puis d'extraire l'élément du milieu dans la liste triée (la partie bon marché). Cette technique est également connue sous le nom de transformer et conquérir .
Retour en arrière
Dans cette approche, plusieurs solutions sont construites progressivement et abandonnées lorsqu'il est déterminé qu'elles ne peuvent pas conduire à une solution complète valide.

Problèmes d'optimisation

Pour les problèmes d'optimisation, il existe une classification plus spécifique des algorithmes ; un algorithme pour de tels problèmes peut appartenir à une ou plusieurs des catégories générales décrites ci-dessus ainsi qu'à l'une des suivantes :

Programmation linéaire
Lors de la recherche de solutions optimales à une fonction linéaire liée à des contraintes d'égalité et d'inégalité linéaires, les contraintes du problème peuvent être utilisées directement pour produire les solutions optimales. Il existe des algorithmes capables de résoudre n'importe quel problème de cette catégorie, comme l' algorithme populaire du simplexe . Les problèmes qui peuvent être résolus avec la programmation linéaire incluent le problème de flux maximal pour les graphes orientés. Si un problème nécessite en outre qu'une ou plusieurs des inconnues soient un nombre entier , il est classé dans la programmation des nombres entiers . Un algorithme de programmation linéaire peut résoudre un tel problème s'il peut être prouvé que toutes les restrictions pour les valeurs entières sont superficielles, c'est-à-dire que les solutions satisfont de toute façon à ces restrictions. Dans le cas général, un algorithme spécialisé ou un algorithme qui trouve des solutions approchées est utilisé, selon la difficulté du problème.
Programmation dynamique
Lorsqu'un problème présente des sous- structures optimales - ce qui signifie que la solution optimale à un problème peut être construite à partir de solutions optimales à des sous-problèmes - et des sous- problèmes qui se chevauchent , ce qui signifie que les mêmes sous-problèmes sont utilisés pour résoudre de nombreuses instances de problème différentes, une approche plus rapide appelée programmation dynamique évite de recalculer des solutions qui ont déjà été calculés. Par exemple, l'algorithme de Floyd-Warshall , le chemin le plus court vers un but à partir d'un sommet dans un graphe pondéré peut être trouvé en utilisant le chemin le plus court vers le but à partir de tous les sommets adjacents. Programmation dynamique et mémorisation vont de pair. La principale différence entre la programmation dynamique et diviser pour régner est que les sous-problèmes sont plus ou moins indépendants dans diviser pour régner, alors que les sous-problèmes se chevauchent dans la programmation dynamique. La différence entre la programmation dynamique et la récursivité directe réside dans la mise en cache ou la mémorisation des appels récursifs. Lorsque les sous-problèmes sont indépendants et qu'il n'y a pas de répétition, la mémorisation n'aide pas ; la programmation dynamique n'est donc pas une solution à tous les problèmes complexes. En utilisant la mémorisation ou en maintenant un tableau des sous-problèmes déjà résolus, la programmation dynamique réduit la nature exponentielle de nombreux problèmes à une complexité polynomiale.
La méthode gourmande
Un algorithme glouton s'apparente à un algorithme de programmation dynamique en ce sens qu'il fonctionne en examinant des sous-structures, en l'occurrence non pas du problème mais d'une solution donnée. De tels algorithmes commencent par une solution, qui peut être donnée ou a été construite d'une certaine manière, et l'améliorent en apportant de petites modifications. Pour certains problèmes, ils peuvent trouver la solution optimale tandis que pour d'autres, ils s'arrêtent à des optima locaux , c'est-à-dire à des solutions qui ne peuvent pas être améliorées par l'algorithme mais qui ne sont pas optimales. L'utilisation la plus populaire des algorithmes gloutons consiste à trouver l'arbre couvrant minimal où trouver la solution optimale est possible avec cette méthode. Huffman Tree , Kruskal , Prim , Sollin sont des algorithmes gourmands qui peuvent résoudre ce problème d'optimisation.
La méthode heuristique
Dans les problèmes d'optimisation , les algorithmes heuristiques peuvent être utilisés pour trouver une solution proche de la solution optimale dans les cas où trouver la solution optimale n'est pas pratique. Ces algorithmes fonctionnent en se rapprochant de plus en plus de la solution optimale au fur et à mesure de leur progression. En principe, s'ils sont exécutés pendant une durée infinie, ils trouveront la solution optimale. Leur mérite est de pouvoir trouver une solution très proche de la solution optimale en un temps relativement court. Ces algorithmes comprennent la recherche locale , la recherche tabou , le recuit simulé et les algorithmes génétiques . Certains d'entre eux, comme le recuit simulé, sont des algorithmes non déterministes tandis que d'autres, comme la recherche tabou, sont déterministes. Lorsqu'une borne sur l'erreur de la solution non optimale est connue, l'algorithme est en outre classé comme un algorithme d'approximation .

Par domaine d'études

Chaque domaine scientifique a ses propres problèmes et a besoin d'algorithmes efficaces. Les problèmes connexes dans un domaine sont souvent étudiés ensemble. Quelques exemples de classes sont les algorithmes de recherche , les algorithmes de tri , les algorithmes de fusion , les algorithmes numériques , les algorithmes de graphe , les algorithmes de chaîne , les algorithmes géométriques de calcul , les algorithmes combinatoires , les algorithmes médicaux , l' apprentissage automatique , la cryptographie , les algorithmes de compression de données et les techniques d' analyse syntaxique .

Les domaines ont tendance à se chevaucher, et les progrès de l'algorithme dans un domaine peuvent améliorer ceux d'autres domaines, parfois complètement indépendants. Par exemple, la programmation dynamique a été inventée pour optimiser la consommation de ressources dans l'industrie, mais elle est maintenant utilisée pour résoudre un large éventail de problèmes dans de nombreux domaines.

Par complexité

Les algorithmes peuvent être classés en fonction du temps dont ils ont besoin pour se terminer par rapport à leur taille d'entrée :

  • Temps constant : si le temps nécessaire à l'algorithme est le même, quelle que soit la taille de l'entrée. Par exemple, un accès à un élément de tableau .
  • Temps logarithmique : si le temps est une fonction logarithmique de la taille de l'entrée. Par exemple , algorithme de recherche binaire .
  • Temps linéaire : si le temps est proportionnel à la taille de l'entrée. Par exemple, le parcours d'une liste.
  • Temps polynomial : si le temps est une puissance de la taille de l'entrée. Par exemple, l' algorithme de tri à bulles a une complexité temporelle quadratique.
  • Temps exponentiel : si le temps est une fonction exponentielle de la taille de l'entrée. Par exemple , la recherche par force brute .

Certains problèmes peuvent avoir plusieurs algorithmes de complexité différente, tandis que d'autres problèmes peuvent n'avoir aucun algorithme ou aucun algorithme efficace connu. Il existe également des mappages de certains problèmes à d'autres problèmes. De ce fait, il s'est avéré plus approprié de classer les problèmes eux-mêmes plutôt que les algorithmes dans des classes d'équivalence basées sur la complexité des meilleurs algorithmes possibles pour eux.

Algorithmes continus

L'adjectif "continu" lorsqu'il est appliqué au mot "algorithme" peut signifier :

  • Un algorithme opérant sur des données qui représentent des quantités continues, même si ces données sont représentées par des approximations discrètes - de tels algorithmes sont étudiés en analyse numérique ; ou
  • Un algorithme sous la forme d'une équation différentielle qui opère en continu sur les données, s'exécutant sur un ordinateur analogique .

Probleme juridique

Les algorithmes, en eux-mêmes, ne sont généralement pas brevetables. Aux États-Unis, une revendication consistant uniquement en de simples manipulations de concepts abstraits, de nombres ou de signaux ne constitue pas des « processus » (USPTO 2006) et, par conséquent, les algorithmes ne sont pas brevetables (comme dans Gottschalk v. Benson ). Cependant, les applications pratiques des algorithmes sont parfois brevetables. Par exemple, dans Diamond c. Diehr , l'application d'un algorithme de rétroaction simple pour faciliter le durcissement du caoutchouc synthétique a été jugée brevetable. Le brevetage des logiciels est très controversé et il existe des brevets très critiqués impliquant des algorithmes, en particulier des algorithmes de compression de données, tels que le brevet LZW d' Unisys .

De plus, certains algorithmes cryptographiques ont des restrictions d'exportation (voir export de cryptographie ).

Historique : Développement de la notion "d'algorithme"

Proche-Orient ancien

La première preuve d'algorithmes se trouve dans les mathématiques babyloniennes de l'ancienne Mésopotamie (l'Irak moderne). Une tablette d'argile sumérienne trouvée à Shuruppak près de Bagdad et datée d'environ 2500 av. J.-C. décrivait le premier algorithme de division . Pendant la dynastie Hammurabi vers 1800-1600 avant JC, des tablettes d'argile babyloniennes décrivaient des algorithmes pour calculer des formules . Des algorithmes ont également été utilisés dans l'astronomie babylonienne . Les tablettes d'argile babyloniennes décrivent et utilisent des procédures algorithmiques pour calculer l'heure et le lieu d'événements astronomiques importants.

Des algorithmes pour l'arithmétique se trouvent également dans les mathématiques égyptiennes anciennes , remontant au papyrus mathématique Rhind vers 1550 av. Les algorithmes ont ensuite été utilisés dans les anciennes mathématiques hellénistiques . Deux exemples sont le crible d'Ératosthène , qui a été décrit dans l' introduction à l'arithmétique de Nicomaque , et l' algorithme d'Euclide , qui a été décrit pour la première fois dans les éléments d'Euclide ( vers  300 av . J.-C. ).

Symboles discrets et reconnaissables

Marques de pointage : Pour garder la trace de leurs troupeaux, de leurs sacs de grains et de leur argent, les anciens utilisaient le pointage : accumuler des pierres ou des marques gravées sur des bâtons ou faire des symboles discrets en argile. Grâce à l'utilisation babylonienne et égyptienne des marques et des symboles, les chiffres romains et l' abaque ont finalement évolué (Dilson, p. 16-41). Les marques de pointage apparaissent en bonne place dans l' arithmétique du système numérique unaire utilisée dans les calculs de la machine de Turing et de la machine post-Turing .

Manipulation de symboles comme "placeholders" pour les nombres : algèbre

Muhammad ibn Mūsā al-Khwārizmī , un mathématicien persan , a écrit l' Al-jabr au IXe siècle. Les termes « algorithme » et « algorithme » sont dérivés du nom al-Khwārizmī, tandis que le terme « algèbre » est dérivé du livre Al-jabr . En Europe, le mot «algorithme» était à l'origine utilisé pour désigner les ensembles de règles et de techniques utilisées par Al-Khwarizmi pour résoudre des équations algébriques, avant d'être généralisé plus tard pour désigner tout ensemble de règles ou de techniques. Cela a finalement abouti à la notion de calculus ratiocinator de Leibniz ( vers  1680 ):

Un bon siècle et demi en avance sur son temps, Leibniz a proposé une algèbre de la logique, une algèbre qui spécifierait les règles de manipulation des concepts logiques de la même manière que l'algèbre ordinaire spécifie les règles de manipulation des nombres.

Algorithmes cryptographiques

Le premier algorithme cryptographique pour déchiffrer le code chiffré a été développé par Al-Kindi , un mathématicien arabe du IXe siècle , dans A Manuscript On Deciphering Cryptographic Messages . Il a donné la première description de la cryptanalyse par analyse de fréquence , le premier algorithme de décryptage .

Dispositifs mécaniques à états discrets

L'horloge : Bolter attribue à l'invention de l' horloge à poids "l'invention clé [de l'Europe au Moyen Âge]", en particulier l' échappement à verge qui nous fournit le tic-tac d'une horloge mécanique. "La machine automatique précise" a conduit immédiatement aux " automates mécaniques " à partir du 13ème siècle et finalement aux "machines computationnelles" - le moteur de différence et les moteurs analytiques de Charles Babbage et de la comtesse Ada Lovelace , milieu du 19ème siècle. Lovelace est crédité de la première création d'un algorithme destiné au traitement sur un ordinateur - le moteur analytique de Babbage, le premier appareil considéré comme un véritable ordinateur complet de Turing au lieu d'une simple calculatrice - et est parfois appelé "le premier programmeur de l'histoire" en conséquence, bien qu'une mise en œuvre complète du deuxième appareil de Babbage ne soit réalisée que des décennies après sa vie.

Machines logiques 1870 - "Balier logique" et "machine logique" de Stanley Jevons : Le problème technique était de réduire les équations booléennes lorsqu'elles étaient présentées sous une forme similaire à ce qui est maintenant connu sous le nom de cartes de Karnaugh . Jevons (1880) décrit d'abord un simple "abaque" de "planches de bois garnies d'épingles, conçues de manière à ce que toute partie ou classe des combinaisons [logiques] puisse être sélectionnée mécaniquement ... Plus récemment, cependant, j'ai réduit le système à une forme complètement mécanique, et ont ainsi incarné l'ensemble du processus d'inférence indirecte dans ce qu'on peut appeler une Machine Logique " Sa machine était équipée de " certaines tiges de bois mobiles " et " au pied se trouvent 21 touches comme celles de un piano [etc.]...". Avec cette machine, il pouvait analyser un « syllogisme ou tout autre argument logique simple ».

Il expose cette machine en 1870 devant les Fellows de la Royal Society. Un autre logicien , John Venn , cependant, dans sa Logique symbolique de 1881 , tourna un regard jaunâtre sur cet effort : « Je n'ai moi-même aucune estimation élevée de l'intérêt ou de l'importance de ce qu'on appelle parfois des machines logiques... il ne me semble pas que tous les artifices actuellement connus ou susceptibles d'être découverts méritent vraiment le nom de machines logiques » ; voir plus à Caractérisations d'algorithmes . Mais pour ne pas être en reste, il a également présenté "un plan quelque peu analogue, je crois, au boulier du professeur Jevon ... [Et] [a] gain, correspondant à la machine logique du professeur Jevons, l'artifice suivant peut être décrit. Je préfère pour l'appeler simplement une machine à diagramme logique ... mais je suppose qu'elle pourrait faire très complètement tout ce que l'on peut rationnellement attendre de n'importe quelle machine logique ».

Métier Jacquard, cartes perforées Hollerith, télégraphie et téléphonie – le relais électromécanique : Bell et Newell (1971) indiquent que le métier Jacquard (1801), précurseur des cartes Hollerith (cartes perforées, 1887), et les « technologies de commutation téléphonique » en sont les racines d'un arbre menant au développement des premiers ordinateurs. Au milieu du XIXe siècle, le télégraphe , le précurseur du téléphone, était utilisé dans le monde entier, son codage discret et distinct des lettres sous forme de «points et tirets» un son commun. À la fin du 19e siècle, le téléscripteur ( vers les  années 1870 ) était utilisé, tout comme l'utilisation des cartes Hollerith lors du recensement américain de 1890. Puis vint le téléimprimeur ( vers  1910 ) avec son utilisation sur papier perforé du code Baudot sur bande.

Les réseaux de commutation téléphonique de relais électromécaniques (inventés en 1835) étaient à l'origine des travaux de George Stibitz (1937), l'inventeur du dispositif d'addition numérique. Alors qu'il travaillait dans les laboratoires Bell, il a observé l'utilisation "lourde" des calculatrices mécaniques à engrenages. "Il rentra chez lui un soir de 1937 avec l'intention de tester son idée... Lorsque le bricolage fut terminé, Stibitz avait construit un dispositif d'addition binaire" .

Le mathématicien Martin Davis observe l'importance particulière du relais électromécanique (avec ses deux "états binaires" ouvert et fermé ) :

Ce n'est qu'avec le développement, à partir des années 1930, des calculatrices électromécaniques utilisant des relais électriques, que des machines ont été construites ayant la portée envisagée par Babbage."

Mathématiques du XIXe siècle jusqu'au milieu du XXe siècle

Symboles et règles : En succession rapide, les mathématiques de George Boole (1847, 1854), Gottlob Frege (1879) et Giuseppe Peano (1888–1889) ont réduit l'arithmétique à une suite de symboles manipulés par des règles. Les principes de l'arithmétique, présentés par une nouvelle méthode (1888) de Peano furent « la première tentative d'axiomatisation des mathématiques dans un langage symbolique ».

Mais Heijenoort donne à Frege (1879) cette félicitation : Frege est « peut-être l'œuvre la plus importante jamais écrite en logique. ... dans laquelle nous voyons un » « langage de formule », c'est-à-dire une lingua characterica , un langage écrit avec des symboles spéciaux , "pour la pensée pure", c'est-à-dire exempte d'embellissements rhétoriques ... construits à partir de symboles spécifiques qui sont manipulés selon des règles définies ". Le travail de Frege a été encore simplifié et amplifié par Alfred North Whitehead et Bertrand Russell dans leurs Principia Mathematica (1910-1913).

Les paradoxes : Parallèlement, un certain nombre de paradoxes troublants apparaissent dans la littérature, notamment le paradoxe de Burali-Forti (1897), le paradoxe de Russell (1902-03) et le paradoxe de Richard . Les considérations qui en ont résulté ont conduit à l' article de Kurt Gödel (1931) - il cite spécifiquement le paradoxe du menteur - qui réduit complètement les règles de récursivité aux nombres.

Calculabilité effective : Dans un effort pour résoudre le problème d' Entscheidungsproblem défini précisément par Hilbert en 1928, les mathématiciens ont commencé par définir ce que l'on entendait par une "méthode effective" ou un "calcul effectif" ou une "calculabilité effective" (c'est-à-dire un calcul qui réussirait ). En succession rapide, les éléments suivants sont apparus : Alonzo Church , Stephen Kleene et le λ-calcul de JB Rosser une définition finement affinée de la "récursion générale" du travail de Gödel agissant sur les suggestions de Jacques Herbrand (cf. les conférences de Gödel à Princeton de 1934) et simplifications ultérieures par Kleene. La preuve de Church que le problème d'Entscheidungsproblem était insoluble, la définition d' Emil Post de la calculabilité effective en tant que travailleur suivant sans réfléchir une liste d'instructions pour se déplacer à gauche ou à droite à travers une séquence de pièces et pendant qu'il y est soit marquer ou effacer un papier ou observer le papier et faire une décision oui-non concernant la prochaine instruction. La preuve d'Alan Turing que le problème d'Entscheidungsproblem était insoluble par l'utilisation de sa "a- [automatic-] machine" - en fait presque identique à la "formulation" de Post, la définition de J. Barkley Rosser de "méthode efficace" en termes de "une machine". La proposition de Kleene d'un précurseur de la « thèse de l'Église » qu'il a appelée « Thèse I », et quelques années plus tard, Kleene a renommé sa thèse « Thèse de l'Église » et a proposé « La thèse de Turing ».

Emil Post (1936) et Alan Turing (1936-1937, 1939)

Emil Post (1936) a décrit les actions d'un "ordinateur" (être humain) comme suit :

"...deux concepts sont impliqués : celui d'un espace de symboles dans lequel le travail menant du problème à la réponse doit être effectué, et un ensemble de directions fixes et inaltérables .

Son espace symbolique serait

"une séquence infinie d'espaces ou de boîtes dans les deux sens ... Le solutionneur de problèmes ou le travailleur doit se déplacer et travailler dans cet espace de symboles, être capable d'être et d'opérer dans une seule boîte à la fois ... une boîte est de n'admettre que deux conditions possibles, c'est-à-dire être vide ou non marqué, et avoir une seule marque, disons un trait vertical.
"Une case doit être choisie et appelée le point de départ. ... un problème spécifique doit être donné sous forme symbolique par un nombre fini de cases [c'est-à-dire INPUT] marquées d'un trait. De même, la réponse [c'est-à-dire , OUTPUT] doit être donné sous forme symbolique par une telle configuration de cases marquées...
"Un ensemble de directions applicables à un problème général met en place un processus déterministe lorsqu'il est appliqué à chaque problème spécifique. Ce processus ne se termine que lorsqu'il s'agit de la direction de type (C ) [c'est-à-dire STOP]". Voir plus sur Machine post-Turing
La statue d'Alan Turing à Bletchley Park

L'œuvre d' Alan Turing a précédé celle de Stibitz (1937) ; on ne sait pas si Stibitz était au courant des travaux de Turing. Le biographe de Turing pensait que l'utilisation par Turing d'un modèle semblable à une machine à écrire découlait d'un intérêt de jeunesse : "Alan avait rêvé d'inventer des machines à écrire quand il était petit ; Mme Turing avait une machine à écrire, et il aurait bien pu commencer par se demander ce que signifiait appeler une machine à écrire 'mécanique ' ". Étant donné la prévalence à l'époque du code Morse, de la télégraphie, des téléscripteurs et des téléscripteurs, il est fort possible que tous aient influencé Turing pendant sa jeunesse.

Turing - son modèle de calcul s'appelle maintenant une machine de Turing - commence, tout comme Post, par une analyse d'un ordinateur humain qu'il réduit à un simple ensemble de mouvements de base et d '«états d'esprit». Mais il va plus loin et crée une machine comme modèle de calcul des nombres.

"Le calcul se fait normalement en écrivant certains symboles sur du papier. Nous pouvons supposer que ce papier est divisé en carrés comme un livre d'arithmétique pour enfant... Je suppose alors que le calcul est effectué sur du papier unidimensionnel, c'est-à-dire sur une bande divisée en carrés. Je supposerai aussi que le nombre de symboles qui peuvent être imprimés est fini...
"Le comportement de l'ordinateur à tout moment est déterminé par les symboles qu'il observe, et son "état d'esprit" à ce moment. On peut supposer qu'il existe une borne B au nombre de symboles ou de carrés que l'ordinateur peut observer à un moment. S'il veut observer davantage, il doit utiliser des observations successives. Nous supposerons aussi que le nombre d'états d'esprit dont il faut tenir compte est fini...
"Imaginons que les opérations effectuées par l'ordinateur soient décomposées en "opérations simples" qui sont si élémentaires qu'il n'est pas facile de les imaginer davantage décomposées."

La réduction de Turing donne :

« Les opérations simples doivent donc comprendre :
"(a) Changements du symbole sur l'un des carrés observés
"(b) Changements de l'un des carrés observés vers un autre carré à l'intérieur des L carrés de l'un des carrés précédemment observés.

"Il se peut que certains de ces changements appellent nécessairement un changement d'état d'esprit. L'opération unique la plus générale doit donc être considérée comme l'une des suivantes :

"(A) Un possible changement (a) de symbole accompagné d'un éventuel changement d'état d'esprit.
"(B) Un possible changement (b) des carrés observés, ainsi qu'un possible changement d'état d'esprit"
"Nous pouvons maintenant construire une machine pour faire le travail de cet ordinateur."

Quelques années plus tard, Turing élargit son analyse (thèse, définition) par cette expression énergique :

"Une fonction est dite "effectivement calculable" si ses valeurs peuvent être trouvées par un processus purement mécanique. Bien qu'il soit assez facile d'avoir une compréhension intuitive de cette idée, il est néanmoins souhaitable d'avoir une définition exprimable mathématiquement plus précise. ... [il discute de l'histoire de la définition à peu près telle qu'elle est présentée ci-dessus en ce qui concerne Gödel, Herbrand, Kleene, Church, Turing et Post] ... Nous pouvons prendre cette affirmation à la lettre, en comprenant par un processus purement mécanique celle qui pourrait être réalisée par une machine. Il est possible de donner une description mathématique, sous une certaine forme normale, des structures de ces machines. Le développement de ces idées conduit à la définition par l'auteur d'une fonction calculable, et à l'identification de calculabilité † avec calculabilité effective...
"† Nous utiliserons l'expression "fonction calculable" pour désigner une fonction calculable par une machine, et nous laisserons "effectivement calculable" se référer à l'idée intuitive sans identification particulière avec aucune de ces définitions".

JB Rosser (1939) et SC Kleene (1943)

J. Barkley Rosser a défini une "méthode [mathématique] efficace" de la manière suivante (italiques ajoutés):

« Méthode efficace » est utilisé ici dans le sens assez spécial d'une méthode dont chaque étape est déterminée avec précision et qui est certaine de produire la réponse en un nombre fini d'étapes. Avec cette signification particulière, trois définitions précises différentes ont été données. à ce jour [sa note de bas de page n° 5 ; voir la discussion ci-dessous]. La plus simple d'entre elles (due à Post et Turing) dit essentiellement qu'une méthode efficace pour résoudre certains ensembles de problèmes existe si l'on peut construire une machine qui résoudre n'importe quel problème de l'ensemble sans intervention humaine au-delà de l'insertion de la question et (plus tard) de la lecture de la réponse . Les trois définitions sont équivalentes, donc peu importe celle qui est utilisée. De plus, le fait que les trois soient équivalentes est un argument très fort pour la justesse de n'importe qui." (Rosser 1939 : 225-226)

La note de bas de page n ° 5 de Rosser fait référence aux travaux de (1) Church et Kleene et à leur définition de la λ-définissabilité, en particulier l'utilisation par Church de celle-ci dans son An Unsolvable Problem of Elementary Number Theory (1936); (2) Herbrand et Gödel et leur utilisation de la récursivité, en particulier l'utilisation de Gödel dans son célèbre article On Formally Undecidable Propositions of Principia Mathematica and Related Systems I (1931) ; et (3) Post (1936) et Turing (1936–37) dans leurs mécanismes-modèles de calcul.

Stephen C. Kleene a défini comme sa désormais célèbre " Thèse I " connue sous le nom de thèse Church-Turing . Mais il l'a fait dans le contexte suivant (en gras dans l'original) :

"12. Théories algorithmiques ... En établissant une théorie algorithmique complète, ce que nous faisons est de décrire une procédure, exécutable pour chaque ensemble de valeurs des variables indépendantes, laquelle procédure se termine nécessairement et de telle manière qu'à partir du résultat, nous pouvons lire une réponse définitive, « oui » ou « non », à la question : « la valeur du prédicat est-elle vraie ? » (Kleene 1943 : 273)

Histoire après 1950

Un certain nombre d'efforts ont été dirigés vers un affinement supplémentaire de la définition d '«algorithme», et l'activité se poursuit en raison de problèmes entourant, en particulier, les fondements des mathématiques (en particulier la thèse Church-Turing ) et la philosophie de l'esprit (en particulier les arguments à propos de l'intelligence artificielle ). Pour plus d'informations, consultez Caractérisations d'algorithmes .

Voir également

Remarques

Bibliographie

Lectures complémentaires

Liens externes

Référentiels d'algorithmes