Algorithme

En mathématiques et en informatique , un algorithme ( / ˈ æ l ɡ ə r ɪ ð əm / ( écouter ) ) est une séquence finie d’ instructions bien définies , généralement utilisée pour résoudre une classe de problèmes spécifiques ou pour effectuer un calcul . ^[1] Les algorithmes sont utilisés comme spécifications pour effectuer des calculs et traiter des données . En utilisant l’ intelligence artificielle, les algorithmes peuvent effectuer des déductions automatisées (appelées raisonnement automatisé ) et utiliser des tests mathématiques et logiques pour détourner le code par différentes 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”. ^[2]

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 b − a 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 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. ^[3]

En tant que méthode efficace , un algorithme peut être exprimé dans un espace et un temps finis, ^[4] et dans un langage formel bien défini ^[5] pour calculer une fonction . ^[6] À partir d’un état initial et d’une entrée initiale (peut-être vide ), ^[7] les instructions décrivent un calcul qui, lorsqu’il est exécuté , passe par un nombre fini ^[8] d’états successifs bien définis, produisant finalement une “sortie” ^{[ 9]} et se terminant à un état de fin final. Le passage d’un état à l’autre n’est pas forcément Déterministe; certains algorithmes, connus sous le nom d’ Algorithmes randomisés , intègrent une entrée aléatoire. ^[dix]

Histoire

Le concept d’algorithme 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. ^[11] Les mathématiciens grecs ont utilisé plus tard 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. ^[12] Des mathématiciens arabes comme al-Kindi au 9ème siècle ont utilisé des algorithmes cryptographiques pour déchiffrer le code, basé sur l’ analyse de fréquence . ^[13]

Le mot algorithme est dérivé du nom du mathématicien persan du IXe siècle Muḥammad ibn Mūsā al-Khwārizmī , dont la nisba (l’identifiant comme de Khwarazm ) a été latinisée en Algoritmi ( persan arabisé الخوارزمی c. 780–850). ^{[14] [15]} Muḥammad ibn Mūsā al-Khwārizmī é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 est maintenant en Ouzbékistan. ^{[16] [17]} Vers 825, al-Khwarizmi a écrit un traité en langue arabe sur le système numérique hindou-arabe , qui a été traduit en latin au 12ème 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. ^[18] 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 . ^[19] En latin médiéval tardif, algorismus , en anglais ‘ algorism’, la corruption de son nom, signifiait simplement le “système de numération décimale”. ^[20] Au XVe 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 d’abord attesté au 17ème siècle; le sens moderne a été introduit au 19ème siècle. ^[21]

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 . ^[22]

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. ^[23]

Un autre usage tôt du mot est depuis 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. ^[24]

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 ” ^[25] ou “méthode effective”. ^[26] Ces formalisations comprenaient les fonctions récursives de Gödel – Herbrand – Kleene de 1930, 1934 et 1935, le lambda calcul d’ Alonzo Church de 1936, la Formulation 1 d’ Emil Post de 1936 et la formule d’ Alan Turing .Machines de Turing de 1936-1937 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”, ^{[27] [ besoin d’une citation pour vérifier ]} 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 ^[28] ou recette de livre de cuisine . ^[29]

En général, un programme n’est un algorithme que s’il finit par s’arrêter ^[30] — 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. ^[31]

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”) ^[32] pour un processus rapide, efficace, “bon” ^[33] qui précise les “mouvements” de “l’ordinateur” (machine ou humain, équipé des moyens internes nécessaires informations et capacités contenues) ^[34] pour trouver, décoder, puis traiter des entiers/symboles d’entrée arbitraires m et n , symboles + et = … et “effectivement” ^[35] produire, en un temps “raisonnable”, ^{[36 ]} 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”. ^[37] Gurevich : “… L’argument informel de Turing en faveur de sa thèse justifie une thèse plus forte : tout 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”. ^[38]

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 : 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 mission 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. Pseudocode, organigrammes, drakon-chartset 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 de 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 comme une forme de code machine rudimentaire ou de code assembleur appelé “ensembles de quadruples” (voir Machine de Turing pour en savoir plus).

Les représentations d’algorithmes peuvent être classées en trois niveaux acceptés de description de la machine de Turing, comme suit : ^[39]

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 solution de la recherche opérationnelle , telles que la programmation dynamique et diviser pour mieux régner . Les techniques de conception et de mise en œuvre de conceptions d’algorithmes sont également appelées modèles de conception d’algorithmes, ^[40] 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 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 ^{[ clarification nécessaire ]}

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’emboîtement de ces structures dans des blocs d’affectation donne lieu à 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 son élégance , etc.” ^[41] 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” ^[42]

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 de procédure et la notion de fonction calculable par algorithme , c’est-à-dire le mappage produit par procédure. La même fonction peut avoir plusieurs algorithmes différents”. ^[43]

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 ^[44] ) est un type restreint de machine, un « dispositif mécanique Déterministe discret » ^[45] qui suit aveuglément ses instructions. ^[46] Les modèles primitifs de Melzak et Lambek ^[47] ont réduit cette notion à quatre éléments : (i) des emplacements discrets et distinguables , (ii) des compteurs discrets et indiscernables ^[48] (iii) un agent, et (iv) une liste d’instructions qui sont efficaces par rapport à la capacité de l’agent. ^[49]

Minsky décrit une variante plus sympathique du modèle “abaque” de Lambek dans ses “Bases très simples pour la calculabilité “. ^[50] 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) ^[51] : 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). ^[52] Il est rare qu’un programmeur doive écrire du “code” avec un jeu d’instructions aussi limité.Turing complet 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 une commodité ; 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”. ^[53] Mais qu’en est-il d’une simulation ou d’une exécution de la chose réelle ? 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. ^[54]

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 que “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 “. ^[55] 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é”.^[57] SEQUENCE, IF-THEN-ELSE et WHILE-DO, avec deux autres : DO-WHILE et CASE. ^[58] Un avantage supplémentaire d’un programme structuré est qu’il se prête à des preuves d’exactitude utilisant l’induction mathématique . ^[59]

Symboles d’organigramme canoniques ^[60] : L’aide graphique appelée organigramme , offre un moyen de décrire et de documenter un algorithme (et un programme informatique d’un). 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, 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 :

Algorithme le plus grand nombre Entrée : Une liste de nombres L . Sortie : Le plus grand nombre de la liste L . si L.size = 0 renvoie null plus grand ← L [0] pour chaque élément de L , faire si élément > plus grand , alors plus grand ← élément renvoie le plus grand

• “←” 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 du mathématicien grec ancien Euclide , qui l’a décrit pour la première fois dans ses Éléments (vers 300 avant JC). ^[61] C’est l’un des algorithmes les plus anciens 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 ; 28 reste ; puis de nouveau j’en soustrais le même 21 (car c’est possible) ; 7 reste ; 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, de même que 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 par rapport à 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 . ^[62] En termes modernes, reste r = l − q × s , q étant le quotient, ou reste rest le “module”, la partie entière-fractionnelle qui reste après la division. ^[63]

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 . ^[64] Alors que l’algorithme de Nicomaque est le même que celui d’Euclide, lorsque les nombres sont premiers l’un par rapport à l’autre, 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 “Inélégant” 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 [En deux endroits L et S mettre les nombres l et s qui représentent les deux longueurs] : ENTRÉE L, S 2 [Initialiser R : faire en sorte que la longueur restante r soit égale à la longueur de départ/initiale/d’entrée l ] : R ← L

E0 : [Assurez-vous que r ≥ s .]

3 [Assurez-vous que le plus petit des deux nombres est en S et le plus grand en R] : SI R > S ALORS le contenu de L est le plus grand nombre donc sautez les étapes d’échange 4 , 5 et 6 : PASSER À l’étape 7 AUTRE échangez le contenu de R et S. 4 L ← R (cette première étape est redondante, mais utile pour une discussion ultérieure). 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 SI S > R ALORS fini de mesurer ainsi ALLER À 10 AUTRE mesurer à nouveau, 8 R ← R − S 9 [Restant-boucle] : ALLER À 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 SI R = 0 ALORS fait PASSER À l’étape 15 AUTRE CONTINUEZ À l’étape 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 [Répéter le processus de mesure] : ALLER À 7

SORTIE :

15 [Terminé. S contient le plus grand diviseur commun ] : IMPRIMER S

FAIT :

16 ARRÊT, FIN, ARRÊT. 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. ^{[ clarifier ]} 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 Algorithme d’Euclide pour le plus grand diviseur commun 6 PRINT “Tapez deux entiers supérieurs à 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 ALLER A 20 80 IMPRIMER A 90 FIN

Comment “Elegant” fonctionne : à la place d’une “boucle Euclid” externe, “Elegant” alterne 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 :

// Algorithme d’Euclide pour le plus grand diviseur commun int euclidAlgorithm ( int A , int B ){ A = abs ( A ); B = abs ( B ); tandis que ( B != 0 ){ tandis que ( A > B ) A = A – B ; B = B – UNE ; } retourne 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 ^[65] 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” ^[66] 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,. 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”. ^[67] Tausworthe propose qu’une mesure de la complexité d’un programme soit la longueur de sa preuve d’exactitude. ^[68]

Mesurer et améliorer les algorithmes d’Euclid

Élégance (compacité) contre bonté (rapidité) : 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 ^[69] indique pourquoi c’est le cas : “Elegant” effectue deux tests conditionnels dans chaque boucle de soustraction, alors 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é ; ^[70] au contraire, cela ne peut se faire 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é algorithmiqueest finalement mis à 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. ^[71]

Efficacité d’exécution

Pour illustrer les améliorations potentielles possibles même dans des algorithmes bien établis, une innovation importante 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. ^[72] En général, les améliorations de vitesse dépendent des propriétés particulières du problème, qui sont très courantes dans les applications pratiques. ^[73] 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 façons 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 pgcd ( int A , int B ) { si ( B == 0 ) retourner A ; sinon si ( A > B ) retourner pgcd ( A – B , B ); autre retourner pgcd ( 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ïest bien compris 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 . ^[74] La composante logique exprime les axiomes qui peuvent être utilisés dans le calcul et la composante de contrôle 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. ^[75] 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. ^[76] Diviser et conquérir Un algorithme de division et de conquête 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 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 donc l’étape de conquête est 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 . ^[77] 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 avons (espérons-le) des 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 de retirer 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 . ^[78] Les problèmes qui peuvent être résolus avec la programmation linéaire incluent le problème d’écoulement maximum pour les graphes dirigé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 Floyd-Warshall , le chemin le plus court vers un objectif à partir d’un sommet dans un graphe pondéré peut être trouvé en utilisant le chemin le plus court vers l’objectif à partir de tous les sommets adjacents. Programmation dynamique et mémorisationaller ensemble. 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é simple 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 est de trouver l’arbre couvrant minimal où trouver la solution optimale est possible avec cette méthode. Arbre de Huffmann , 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 alors
• 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 . ^[79]

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 v. 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 Unisys’ Brevet LZW .

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 (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écrit le premier algorithme de division . ^[11] Pendant la dynastie Hammurabi vers 1800-1600 av. J.-C., des tablettes d’argile babyloniennes décrivaient des algorithmes pour calculer des formules . ^[80] 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. ^[81]

Des algorithmes pour l’arithmétique se trouvent également dans les Mathématiques égyptiennes anciennes , remontant au papyrus mathématique Rhind vers 1550 av. ^[11] Les algorithmes ont ensuite été utilisés dans les anciennes mathématiques hellénistiques . Deux exemples sont le tamis d’Ératosthène , qui a été décrit dans l’ introduction à l’arithmétique de Nicomaque , ^{[82] [12] : Ch 9.2} 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.). ^{[12] : Chapitre 9.1}

Symboles discrets et reconnaissables

Marques de pointage : Pour garder la trace de leurs troupeaux, de leurs sacs de céréales 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. ^[83] Cela a finalement abouti à la notion de Leibniz du ratiocinateur de calcul (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. ^[84]

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 . ^[13]

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 ^[85] qui nous fournit le tic-tac d’une horloge mécanique. “La machine automatique précise” ^[86] 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. ^[87]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 serait 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 telle sorte que n’importe quelle 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 trouvaient 21 touches comme celles d’un piano [etc.] … “. Avec cette machine, il pouvait analyser un ” syllogisme ou tout autre argument logique simple “. ^[88 ]

Il expose cette machine en 1870 devant les Fellows de la Royal Society. ^[89] Un autre logicien John Venn , cependant, dans sa Symbolic Logic de 1881 , tourna un œil jaunâtre à cet effort : pour moi, toutes les inventions actuellement connues ou susceptibles d’être découvertes méritent vraiment le nom de machines logiques » ; voir plus à Caractérisations d’algorithmes . Mais pour ne pas être en reste, il a lui aussi 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 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”. ^[90]

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. ^[91] 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) sont à 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” ^[92 ]

Davis (2000) 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.” ^[93]

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 ». ^[94]

Mais Heijenoort donne à Frege (1879) cette félicitation : Frege est « peut-être l’œuvre unique 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”. ^[95] 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 . ^[96] Les considérations résultantes 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 d’abord entrepris de définir ce que l’on entendait par une “méthode effective” ou “calcul effectif” ou “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 ^[97] une définition finement affinée de la “récurrence générale” tirée des travaux de Gödel agissant sur les suggestions de Jacques Herbrand (cf. Gödel’s Princeton lectures of 1934) et les simplifications ultérieures par Kleene. ^[98] Église’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 dans une séquence de pièces et pendant qu’il y marque ou efface un papier ou observe le papier et fait un oui -pas de décision sur la prochaine instruction. ^[100] La preuve d’Alan Turing que le problème d’Entscheidungsproblem était insoluble par l’utilisation de sa “a- [automatic-] machine” ^[101] – en fait presque identique à la “formulation” de Post, la définition de J. Barkley Rosser de “méthode efficace ” en termes de ” machine “. ^[102] Proposition de Kleene d’un précurseur de la ” thèse de l’Église “et quelques années plus tard, Kleene rebaptise sa thèse “Church’s Thesis” ^[104] et propose “Turing’s Thesis”. ^[105]

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]”. ^[106] Voir plus sur la machine post-Turing La statue d’Alan Turing à Bletchley Park

L’ouvrage d’ Alan Turing ^[107] a précédé celui 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'”. ^[108] Compte tenu de la prévalence du code Morse et de la télégraphie, des téléscripteurs et des téléscripteurs, nous ^{[ qui ? ]} pourrait conjecturer que tous étaient des influences.

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. ^[109]

“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 instant 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 donné. 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” si élémentaires qu’il n’est pas facile de les imaginer davantage décomposées.” ^[110]

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.” ^[110]

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”. ^[111]

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 équivalents est un argument très fort pour l’exactitude de l’un d’entre eux.” (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

• Machine abstraite
• Ingénierie algorithmique
• Caractérisations d’algorithmes
• Biais algorithmique
• Composition algorithmique
• Entités algorithmiques
• Synthèse algorithmique
• Technique algorithmique
• Topologie algorithmique
• Déchets à l’intérieur, déchets à l’extérieur
• Introduction aux algorithmes (manuel)
• Liste des algorithmes
• Liste des sujets généraux sur les algorithmes
• Liste des publications importantes en informatique théorique – Algorithmes
• Régulation des algorithmes
• Théorie du calcul
  • Théorie de la calculabilité
  • Théorie de la complexité computationnelle
• Mathématiques computationnelles

Remarques

1. ^ “Définition d’ALGORITHME” . Dictionnaire en ligne Merriam-Webster . Archivé de l’original le 14 février 2020 . Consulté le 14 novembre 2019 .
2. ^ Blair, Ann, Duguid, Paul, Goeing, Anja-Silvia et Grafton, Anthony. Informations : Un compagnon historique, Princeton : Princeton University Press, 2021. p. 247
3. ^ David A. Grossman, Ophir Frieder, Recherche d’informations: algorithmes et heuristiques , 2e édition, 2004, ISBN 1402030045
4. ^ “Tout algorithme mathématique classique, par exemple, peut être décrit en un nombre fini de mots anglais” (Rogers 1987 : 2).
5. ↑ Bien défini par rapport à l’agent qui exécute l’algorithme : « Il existe un agent informatique, généralement humain, qui peut réagir aux instructions et effectuer les calculs » (Rogers 1987 :2).
6. ^ “un algorithme est une procédure pour calculer une fonction (par rapport à une notation choisie pour les nombres entiers) … cette limitation (aux fonctions numériques) n’entraîne aucune perte de généralité”, (Rogers 1987: 1).
7. ^ “Un algorithme a zéro ou plusieurs entrées, c’est-à-dire des quantités qui lui sont initialement données avant le début de l’algorithme” (Knuth 1973: 5).
8. ^ “Une procédure qui a toutes les caractéristiques d’un algorithme sauf qu’elle manque peut-être de finitude peut être appelée une” méthode de calcul ” ” (Knuth 1973: 5).
9. ^ “Un algorithme a une ou plusieurs sorties, c’est-à-dire des quantités qui ont une relation spécifiée avec les entrées” (Knuth 1973: 5).
10. ^ Qu’un processus avec des processus intérieurs aléatoires (n’incluant pas l’entrée) soit ou non un algorithme est discutable. Rogers est d’avis que: “un calcul est effectué de manière discrète par étapes, sans l’utilisation de méthodes continues ou de dispositifs analogiques … reporté de manière Déterministe, sans recourir à des méthodes ou dispositifs aléatoires, par exemple des dés” (Rogers 1987: 2) .
11. ^ ^{un bc Chabert} , Jean-Luc (2012). Une histoire des algorithmes : du caillou à la micropuce . Springer Science et médias d’affaires. p. 7–8. ISBN 9783642181924.
12. ^ ^{un bc Cooke} , Roger L. (2005). L’histoire des mathématiques: un bref cours . John Wiley et fils. ISBN 978-1-118-46029-0.
13. ^ ^{un b} Dooley, John F. (2013). Une brève histoire de la cryptologie et des algorithmes cryptographiques . Springer Science et médias d’affaires. p. 12–3. ISBN 9783319016283.
14. ^ “Biographie d’Al-Khwarizmi” . www-history.mcs.st-andrews.ac.uk . Archivé de l’original le 2 août 2019 . Consulté le 3 mai 2017 .
15. ^ “Étymologie d’algorithme” . Dictionnaire des chambres . Archivé de l’original le 31 mars 2019 . Consulté le 13 décembre 2016 .
16. ^ Hogendijk, Jan P. (1998). « al-Khwarzimi » . Pythagore . 38 (2): 4–5. Archivé de l’original le 12 avril 2009.
17. ^ Oaks, Jeffrey A. “Al-Khwarizmi était-il un algébriste appliqué?” . Université d’Indianapolis . Archivé de l’original le 18 juillet 2011 . Récupéré le 30 mai 2008 .
18. ^ Brezina, Couronne (2006). Al-Khwarizmi : l’inventeur de l’algèbre . Le groupe d’édition Rosen. ISBN 978-1-4042-0513-0.
19. ^ Textes mathématiques les plus importants de l’histoire Archivé le 9 juin 2011 à la Wayback Machine , selon Carl B. Boyer .
20. ^ “algorismic” , The Free Dictionary , archivé de l’original le 21 décembre 2019 , récupéré le 14 novembre 2019
21. ^ Oxford English Dictionary , troisième édition, 2012 sv
22. ^ Sriram, MS (2005). “Algorithmes en mathématiques indiennes” . Dans Emch, Gérard G. ; Sridharan, R.; Srinivas, MD (éd.). Contributions à l’histoire des mathématiques indiennes . Springer. p. 153. ISBN 978-93-86279-25-5.
23. ^ Mehri, Bahman (2017). “D’Al-Khwarizmi à l’algorithme”. Olympiades d’informatique . 11 (2): 71–74. doi : 10.15388/ioi.2017.special.11 .
24. ^ “Abu Jafar Muhammad ibn Musa al-Khwarizmi” . membres.peak.org . Archivé de l’original le 21 août 2019 . Consulté le 14 novembre 2019 .
25. ^ Kleene 1943 dans Davis 1965: 274
26. ^ Rosser 1939 dans Davis 1965: 225
27. ^ Pierre 1973: 4
28. ^ Simanowski, Roberto (2018). L’algorithme de la mort et autres dilemmes numériques . Méditations intempestives. Vol. 14. Traduit par Chase, Jefferson. Cambridge, Massachusetts : MIT Press. p. 147. ISBN 9780262536370. Archivé de l’original le 22 décembre 2019 . Consulté le 27 mai 2019 . […] niveau d’abstraction suivant de la bureaucratie centrale : les algorithmes opérant globalement.
29. ^ Dietrich, Éric (1999). “Algorithme”. À Wilson, Robert Andrew; Keil, Frank C. (éd.). L’Encyclopédie MIT des sciences cognitives . Bibliothèque Cognet du MIT. Cambridge, Massachusetts : MIT Press (publié en 2001). p. 11. ISBN 9780262731447. Consulté le 22 juillet 2020 . Un algorithme est une recette, une méthode ou une technique pour faire quelque chose.
30. ^ Stone exige simplement qu ‘”il doit se terminer par un nombre fini d’étapes” (Stone 1973: 7–8).
31. ^ Boolos et Jeffrey 1974, 1999 : 19
32. ^ cf Pierre 1972: 5
33. ^ Knuth 1973: 7 déclare: “En pratique, nous ne voulons pas seulement des algorithmes, nous voulons de bons algorithmes … un critère de qualité est le temps nécessaire pour exécuter l’algorithme … d’autres critères sont l’adaptabilité de l’algorithme aux ordinateurs , sa simplicité, son élégance, etc.”
34. ^ cf Pierre 1973: 6
35. ^ Stone 1973: 7–8 déclare qu’il doit y avoir “… une procédure qu’un robot [c’est-à-dire un ordinateur] peut suivre afin de déterminer précisément comment obéir à l’instruction”. Stone ajoute la finitude du processus et la précision (n’ayant aucune ambiguïté dans les instructions) à cette définition.
36. ^ Knuth, loc. cit
37. ^ Minsky 1967 , p. 105
38. ^ Gourevitch 2000: 1, 3
39. ^ Sipser 2006: 157
40. ^ Goodrich, Michael T. ; Tamassia, Roberto (2002), Algorithm Design: Foundations, Analysis, and Internet Examples , John Wiley & Sons, Inc., ISBN 978-0-471-38365-9, archivé de l’original le 28 avril 2015 , récupéré le 14 juin 2018
41. ^ Knuth 1973: 7
42. ^ Chaitin 2005: 32
43. ^ Rogers 1987: 1-2
44. ↑ Dans son essai “Calculs by Man and Machine: Conceptual Analysis” Seig 2002 : 390 attribue cette distinction à Robin Gandy, cf Wilfred Seig, et al., 2002 Reflections on the foundations of statistics: Essays in honor of Solomon Feferman , Association for Logique symbolique, AK Peters Ltd, Natick, MA.
45. ^ cf Gandy 1980: 126, la thèse et les principes de l’église Robin Gandy pour les mécanismes apparaissant aux pages 123 à 148 dans J. Barwise et al. 1980 The Kleene Symposium , North-Holland Publishing Company.
46. ^ Un “robot”: “Un ordinateur est un robot qui exécute toute tâche pouvant être décrite comme une séquence d’instructions.” cf Stone 1972: 3
47. ^ Le “boulier” de Lambek est “un nombre infini d’emplacements (trous, fils, etc.) ainsi qu’un nombre illimité de compteurs (cailloux, perles, etc.). Les emplacements se distinguent, les compteurs ne le sont pas”. Les trous ont une capacité illimitée, et se tient prêt un agent qui comprend et est capable d’exécuter la liste des instructions » (Lambek 1961 : 295). Lambek fait référence à Melzak qui définit sa Q-machine comme « un nombre indéfiniment grand d’emplacements. .. une quantité indéfinie de compteurs répartis entre ces emplacements, un programme et un opérateur dont le seul but est d’exécuter le programme” (Melzak 1961: 283). BBJ (loc. cit.) ajoute la stipulation que les trous sont “capable de contenir n’importe quel nombre de pierres” (p. 46)., vol. 4, non. 3, septembre 1961.
48. ^ S’il n’y a pas de confusion, le mot “compteurs” peut être supprimé et on peut dire qu’un emplacement contient un seul “nombre”.
49. ↑ “On dit qu’une instruction est efficace s’il existe une procédure que le robot peut suivre afin de déterminer précisément comment obéir à l’instruction.” (Pierre 1972: 6)
50. ^ cf Minsky 1967: Chapitre 11 “Modèles informatiques” et Chapitre 14 “Bases très simples pour la calculabilité” pp. 255–281, en particulier,
51. ^ cf Knuth 1973: 3.
52. ^ Mais toujours précédé de IF-THEN pour éviter une soustraction incorrecte.
53. ^ Knuth 1973: 4
54. ^ Pierre 1972 : 5. Les méthodes d’extraction des racines ne sont pas triviales : voir Méthodes de calcul des racines carrées .
55. ^ Leeuwen, janvier (1990). Manuel d’informatique théorique : Algorithmes et complexité. Tome A. Elsevier. p. 85. ISBN 978-0-444-88071-0.
56. ^ John G. Kemeny et Thomas E. Kurtz 1985 Back to Basic: L’histoire, la corruption et l’avenir de la langue , Addison-Wesley Publishing Company, Inc. Reading, MA, ISBN 0-201-13433-0 .
57. ^ Tausworthe 1977: 101
58. ^ Tausworthe 1977: 142
59. ^ Knuth 1973 section 1.2.1, développée par Tausworthe 1977 aux pages 100ff et au chapitre 9.1
60. ^ cf Tausworthe 1977
61. ^ Heath 1908 : 300; L’édition 2005 de Hawking’s Dover dérive de Heath.
62. ^ ” ‘Laissez CD, mesurant BF, laisser FA moins que lui-même.’ C’est une abréviation soignée pour dire, mesurer le long de BA des longueurs successives égales à CD jusqu’à ce qu’un point F soit atteint tel que la longueur FA restante soit inférieure à CD ; en d’autres termes, soit BF le plus grand multiple exact de CD contenu dans BA” (Heath 1908:297)
63. ^ Pour les traitements modernes utilisant la division dans l’algorithme, voir Hardy et Wright 1979 : 180, Knuth 1973 : 2 (Volume 1), ainsi que plus de discussions sur l’Algorithme d’Euclide dans Knuth 1969 : 293–297 (Volume 2).
64. ↑ Euclide couvre cette question dans sa Proposition 1.
65. ^ “Éléments d’Euclide, Livre VII, Proposition 2” . Aleph0.clarku.edu. Archivé de l’original le 24 mai 2012 . Consulté le 20 mai 2012 .
66. ↑ Bien que cette notion soit largement utilisée, elle ne peut être définie avec précision.
67. ^ Knuth 1973 : 13-18. Il attribue « la formulation de la preuve d’algorithmes en termes d’assertions et d’induction » à RW Floyd, Peter Naur, CAR Hoare, HH Goldstine et J. von Neumann. Tausworth 1977 emprunte l’exemple d’Euclide de Knuth et étend la méthode de Knuth dans la section 9.1 Preuves formelles (pp. 288–298).
68. ^ Tausworthe 1997: 294
69. ^ cf Knuth 1973: 7 (Vol. I), et ses analyses plus détaillées aux pages 1969: 294–313 (Vol II).
70. ^ La panne se produit lorsqu’un algorithme tente de se compacter. Le succès résoudrait le problème Halting .
71. ^ Kriegel, Hans-Peter ; Schubert, Erich; Zimek, Arthur (2016). “L’art (noir) de l’évaluation d’exécution : comparons-nous des algorithmes ou des implémentations ?”. Connaissances et systèmes d’information . 52 (2): 341–378. doi : 10.1007/s10115-016-1004-2 . ISSN 0219-1377 . S2CID 40772241 .
72. ^ Gillian Conahan (janvier 2013). “De meilleures mathématiques rendent les réseaux de données plus rapides” . découvremagazine.com. Archivé de l’original le 13 mai 2014 . Consulté le 13 mai 2014 .
73. ^ Haitham Hassanieh, Piotr Indyk , Dina Katabi et Eric Price, ” Symposium ACM-SIAM sur les algorithmes discrets (SODA) Archivé le 4 juillet 2013 à la Wayback Machine , Kyoto, janvier 2012. Voir aussi la page Web sFFT Archivée le 21 février , 2012, à la Wayback Machine .
74. ^ Kowalski 1979
75. ^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Problèmes de sac à dos | Hans Kellerer | Springer . Springer. doi : 10.1007/978-3-540-24777-7 . ISBN 978-3-540-40286-2. Archivé de l’original le 18 octobre 2017 . Consulté le 19 septembre 2017 .
76. ^ Carroll, Sue; Daughtrey, Taz (4 juillet 2007). Concepts fondamentaux pour l’ingénieur qualité logiciel . Société américaine pour la qualité. p. 282 et suiv. ISBN 978-0-87389-720-4.
77. ^ Par exemple, le volume d’un polytope convexe (décrit à l’aide d’un oracle d’appartenance) peut être approché avec une grande précision par un algorithme de temps polynomial randomisé, mais pas par un Déterministe : voir Dyer, Martin ; Frise, Alan ; Kannan, Ravi (janvier 1991), “Un algorithme polynomial aléatoire pour approximer le volume des corps convexes”, J. ACM , 38 (1): 1–17, CiteSeerX 10.1.1.145.4600 , doi : 10.1145/102782.102783 , S2CID 13268711 .
78. ^ George B. Dantzig et Mukund N. Thapa. 2003. Programmation Linéaire 2 : Théorie et Extensions . Springer Verlag.
79. ^ Tsypkine (1971). Adaptation et apprentissage dans les systèmes automatiques . Presse académique. p. 54. ISBN 978-0-08-095582-7.
80. ^ Knuth, Donald E. (1972). “Anciens algorithmes babyloniens” (PDF) . Commun. ACM . 15 (7): 671–677. doi : 10.1145/361454.361514 . ISSN 0001-0782 . S2CID 7829945 . Archivé de l’original (PDF) le 24 décembre 2012.
81. ^ Aaboe, Asger (2001), Épisodes de l’histoire ancienne de l’astronomie , New York: Springer, pp. 40–62, ISBN 978-0-387-95136-2
82. ^ Ast, Courtney. “Eratosthène” . Université d’État de Wichita : Département de mathématiques et de statistique. Archivé de l’original le 27 février 2015 . Consulté le 27 février 2015 .
83. ^ Chabert, Jean-Luc (2012). Une histoire des algorithmes : du caillou à la micropuce . Springer Science et médias d’affaires. p. 2. ISBN 9783642181924.
84. ^ Davis 2000: 18
85. ^ Bolter 1984: 24
86. ^ Bolter 1984: 26
87. ^ Bolter 1984 : 33–34, 204–206.
88. ^ Toutes les citations de W. Stanley Jevons 1880 Elementary Lessons in Logic: Deductive and Inductive , Macmillan and Co., Londres et New York. Republié sous forme de googlebook ; voir Jevons 1880 :199–201. Louis Couturat 1914 l’Algèbre de la logique , The Open Court Publishing Company, Chicago et Londres. Republié sous forme de googlebook ; cf Couturat 1914:75-76 donne quelques détails supplémentaires ; il compare cela à une machine à écrire ainsi qu’à un piano. Jevons déclare que le compte se trouve au 20 janvier 1870 Les Actes de la Royal Society .
89. ^ Jevons 1880: 199-200
90. ^ Toutes les citations de John Venn 1881 Symbolic Logic , Macmillan and Co., Londres. Republié sous forme de googlebook. voir Venn 1881 :120–125. Le lecteur intéressé pourra trouver une explication plus approfondie dans ces pages.
91. ^ Diagramme de Bell et Newell 1971 : 39, cf. Davis 2000
92. ^ * Melina Hill, correspondante de Valley News, A Tinkerer Gets a Place in History , Valley News West Lebanon NH, jeudi 31 mars 1983, p. 13.
93. ^ Davis 2000: 14
94. ^ van Heijenoort 1967: 81ff
95. ^ Le commentaire de van Heijenoort sur le Begriffsschrift de Frege, un langage de formule, calqué sur celui de l’arithmétique, pour la pensée pure dans van Heijenoort 1967: 1
96. ^ Dixon 1906, cf. Kleene 1952 : 36–40
97. ^ cf. note de bas de page dans Alonzo Church 1936a dans Davis 1965:90 et 1936b dans Davis 1965:110
98. ^ Kleene 1935–6 à Davis 1965: 237ff, Kleene 1943 à Davis 1965: 255ff
99. ^ Église 1936 à Davis 1965: 88ff
100. ^ cf. “Processus combinatoires finis – Formulation 1“, Post 1936 dans Davis 1965 : 289–290
101. ^ Turing 1936–37 dans Davis 1965: 116ff
102. ^ Rosser 1939 dans Davis 1965: 226
103. ^ Kleene 1943 dans Davis 1965 : 273-274
104. ^ Kleene 1952 : 300, 317
105. ^ Kleene 1952: 376
106. ^ Turing 1936–37 dans Davis 1965 : 289–290
107. ^ Turing 1936 à Davis 1965, Turing 1939 à Davis 1965: 160
108. ^ Hodges, p. 96
109. ^ Turing 1936–37: 116
110. ^ ^{un b} Turing 1936–37 dans Davis 1965: 136
111. ^ Turing 1939 dans Davis 1965: 160

Bibliographie

• Axt, P (1959). “Sur une hiérarchie sous-récursive et des degrés récursifs primitifs” . Transactions de l’American Mathematical Society . 92 (1): 85-105. doi : 10.2307/1993169 . JSTOR 1993169 .
• Bell, C. Gordon et Newell, Allen (1971), Structures informatiques : Lectures et exemples , McGraw–Hill Book Company, New York. ISBN 0-07-004357-4 .
• Blass, Andreas ; Gourevitch, Yuri (2003). “Algorithmes: une quête de définitions absolues” (PDF) . Bulletin de l’Association européenne d’informatique théorique . 81 .Comprend une excellente bibliographie de 56 références.
• Bolter, David J. (1984). L’homme de Turing: la culture occidentale à l’ère informatique (éd. 1984). Chapel Hill, Caroline du Nord : The University of North Carolina Press. ISBN 978-0-8078-1564-9., ISBN 0-8078-4108-0
• Boolos, George ; Jeffrey, Richard (1999) [1974]. Calculabilité et logique (4e éd.). Cambridge University Press, Londres. ISBN 978-0-521-20402-6.: cf. Chapitre 3 Machines de Turing où ils discutent de “certains ensembles énumérables non effectivement (mécaniquement) énumérables”.
• Burgin, Mark (2004). Algorithmes super-récursifs . Springer. ISBN 978-0-387-95569-8.
• Campagnolo, ML, Moore, C. et Costa, JF (2000) Une caractérisation analogique des fonctions sous-récursives. Dans Proc. de la 4e conférence sur les nombres réels et les ordinateurs , Université d’Odense, pp. 91–109
• Église, Alonzo (1936). “Un problème insoluble de la théorie élémentaire des nombres”. Le Journal américain de mathématiques . 58 (2): 345–363. doi : 10.2307/2371045 . JSTOR 2371045 .Reproduit dans L’Indécidable , p. 89ff. La première expression de “Church’s Thèse”. Voir en particulier la page 100 ( L’Indécidable ) où il définit la notion de “calculabilité effective” en termes d'”algorithme”, et il utilise le mot “termine”, etc.
• Église, Alonzo (1936). « Une note sur le Entscheidungsproblem ». Le Journal de la logique symbolique . 1 (1): 40–41. doi : 10.2307/2269326 . JSTOR 2269326 . Église, Alonzo (1936). “Correction à une note sur l’Entscheidungsproblem”. Le Journal de la logique symbolique . 1 (3): 101–102. doi : 10.2307/2269030 . JSTOR 2269030 .Reproduit dans L’Indécidable , p. 110ff. Church montre que le problème d’Entscheidungsproblem est insoluble dans environ 3 pages de texte et 3 pages de notes de bas de page.
• Daffa’, Ali Abdullah al- (1977). L’apport musulman aux mathématiques . Londres : Croom Helm. ISBN 978-0-85664-464-1.
• Davis, Martin (1965). L’indécidable : articles de base sur les propositions indécidables, les problèmes insolubles et les fonctions calculables . New York : Raven Press. ISBN 978-0-486-43228-1.Davis commente avant chaque article. Les articles de Gödel , Alonzo Church , Turing , Rosser , Kleene et Emil Post sont inclus ; ceux cités dans l’article sont listés ici par nom d’auteur.
• Davis, Martin (2000). Moteurs de logique : les mathématiciens et l’origine de l’ordinateur . New York : WWNortion. ISBN 978-0-393-32229-3.Davis propose des biographies concises de Leibniz , Boole , Frege , Cantor , Hilbert , Gödel et Turing avec von Neumann dans le rôle du méchant voleur de spectacles. Très brèves biographies de Joseph-Marie Jacquard , Babbage , Ada Lovelace , Claude Shannon , Howard Aiken , etc.
• Cet article incorpore du matériel du domaine public du document NIST : Black, Paul E. “algorithm” . Dictionnaire des algorithmes et des structures de données .
• Doyen, Tim (2012). « Évolution et diversité morale » . Annuaire international baltique de la cognition, de la logique et de la communication . 7 . doi : 10.4148/biyclc.v7i0.1775 .
• Dennett, Daniel (1995). L’idée dangereuse de Darwin . Complexité . Vol. 2. New York : Touchstone/Simon & Schuster. p. 32-36 . Bibcode : 1996Cmplx…2a..32M . doi : 10.1002/(SICI)1099-0526(199609/10)2:1<32::AID-CPLX8>3.0.CO;2-H . ISBN 978-0-684-80290-9.
• Dilson, Jesse (2007). L’abaque ((1968, 1994) éd.). Presse de St. Martin, NY. ISBN 978-0-312-10409-2., ISBN 0-312-10409-X
• Yuri Gurevich , Sequential Abstract State Machines Capture Sequential Algorithms , ACM Transactions on Computational Logic, Vol 1, no 1 (juillet 2000), pp. 77–111. Comprend une bibliographie de 33 sources.
• van Heijenoort, Jean (2001). De Frege à Gödel, A Source Book in Mathematical Logic, 1879–1931 ((1967) éd.). Harvard University Press, Cambridge. ISBN 978-0-674-32449-7., 3e édition 1976[?], ISBN 0-674-32449-8 (pbk.)
• Hodges, Andrew (1983). Alan Turing : L’énigme . La physique aujourd’hui . Vol. 37. New York : Simon et Schuster . p. 107–108. Bibcode : 1984PhT….37k.107H . doi : 10.1063/1.2915935 . ISBN 978-0-671-49207-6., ISBN 0-671-49207-1 . Cf. Chapitre “L’Esprit de Vérité” pour une histoire menant à, et une discussion de, sa preuve.
• En ligneKleene, Stephen C. (1936). “Fonctions récursives générales des nombres naturels” . Annales Mathématiques . 112 (5): 727–742. doi : 10.1007/BF01565439 . S2CID 120517999 . Archivé de l’original le 3 septembre 2014 . Consulté le 30 septembre 2013 .Présenté à l’American Mathematical Society, septembre 1935. Reproduit dans The Undecidable , p. 237ff. La définition de Kleene de la “récursivité générale” (connue maintenant sous le nom de mu-récursivité) a été utilisée par Church dans son article de 1935 Un problème insoluble de la théorie élémentaire des nombres qui a prouvé que le “problème de décision” était “indécidable” (c’est-à-dire un résultat négatif).
• En ligneKleene, Stephen C. (1943). “Prédicats et quantificateurs récursifs” . Transactions de l’American Mathematical Society . 53 (1): 41–73. doi : 10.2307/1990131 . JSTOR 1990131 .Reproduit dans L’Indécidable , p. 255ff. Kleene a affiné sa définition de “récursion générale” et a procédé dans son chapitre “12. Théories algorithmiques” pour poser “Thèse I” (p. 274); il répétera plus tard cette thèse (dans Kleene 1952 : 300) et l’appellera “Church’s Thesis” (Kleene 1952 : 317) (c’est-à-dire la thèse de l’Église ).
• Kleene, Stephen C. (1991) [1952]. Introduction à la métamathématique (dixième éd.). Société d’édition de la Hollande du Nord. ISBN 978-0-7204-2103-3.
• Knuth, Donald (1997). Algorithmes fondamentaux, troisième édition . Reading, Massachusetts : Addison-Wesley. ISBN 978-0-201-89683-1.
• Knuth, Donald (1969). Volume 2/Algorithmes semi-numériques, L’art de la programmation informatique Première édition . Reading, Massachusetts : Addison-Wesley.
• Kosovsky, NK Elements of Mathematical Logic and its Application to the theory of Subrecursive Algorithms , LSU Publ., Leningrad, 1981
• Kowalski, Robert (1979). “Algorithme=Logique+Contrôle”. Communications de l’ACM . 22 (7): 424–436. doi : 10.1145/359131.359136 . S2CID 2509896 .
• AA Markov (1954) Théorie des algorithmes . [Traduit par Jacques J. Schorr-Kon et le personnel du PST] Mentions légales Moscou, Académie des sciences de l’URSS, 1954 [c’est-à-dire, Jérusalem, Programme israélien de traductions scientifiques, 1961 ; disponible auprès de l’Office of Technical Services, US Dept. of Commerce, Washington] Description 444 p. 28cm. Ajouté tp dans la traduction russe des travaux de l’Institut mathématique de l’Académie des sciences de l’URSS, v. 42. Titre original : Teoriya algerifmov. [QA248.M2943 Bibliothèque du Dartmouth College. US Department of Commerce, Office of Technical Services, numéro OTS 60-51085.]
• Minsky, Marvin (1967). Calcul : machines finies et infinies (première éd.). Prentice-Hall, falaises d’Englewood, NJ. ISBN 978-0-13-165449-5.Minsky développe son “… idée d’un algorithme – une procédure efficace …” au chapitre 5.1 Calculabilité, procédures efficaces et algorithmes. Machines infinies.
• Poste, Émile (1936). “Processus combinatoires finis, Formulation I”. Le Journal de la logique symbolique . 1 (3): 103–105. doi : 10.2307/2269031 . JSTOR 2269031 .Réimprimé dans L’Indécidable , pp. 289ff. Post définit un processus simple de type algorithmique d’un homme écrivant des marques ou effaçant des marques et allant de boîte en boîte et finalement s’arrêtant, alors qu’il suit une liste d’instructions simples. Ceci est cité par Kleene comme l’une des sources de sa ” Thèse I “, la soi-disant thèse de Church-Turing .
• Rogers, Jr, Hartley (1987). Théorie des fonctions récursives et calculabilité effective . La presse du MIT. ISBN 978-0-262-68052-3.
• Rosser, JB (1939). “Une exposition informelle des preuves du théorème de Godel et du théorème de Church”. Journal de logique symbolique . 4 (2): 53–60. doi : 10.2307/2269059 . JSTOR 2269059 .Reproduit dans L’Indécidable , p. 223ff. Voici la célèbre définition de la “méthode efficace” de Rosser : “… une méthode dont chaque étape est précisément prédéterminée et qui est certaine de produire la réponse en un nombre fini d’étapes… une machine qui résoudra ensuite tout 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” (p. 225-226, The Undecidable )
• Santos-Lang, Christopher (2014). “Approches d’écologie morale à l’éthique de la machine” (PDF) . Dans van Rysewyk, Simon; Pontier, Matthijs (dir.). Éthique médicale des machines . Systèmes intelligents, contrôle et automatisation : science et ingénierie. Vol. 74. Suisse : Springer. p. 111–127. doi : 10.1007/978-3-319-08108-3_8 . ISBN 978-3-319-08107-6.
• Scott, Michael L. (2009). Programmation pragmatique du langage (3e éd.). Éditions Morgan Kaufmann/Elsevier. ISBN 978-0-12-374514-9.
• Sipser, Michael (2006). Introduction à la théorie du calcul . Société d’édition PWS. ISBN 978-0-534-94728-6.
• Sobre, Elliott ; Wilson, David Sloan (1998). Vers les autres : l’évolution et la psychologie du comportement désintéressé . Cambridge : Harvard University Press. ISBN 9780674930469.
• Pierre, Harold S. (1972). Introduction à l’organisation informatique et aux structures de données (éd. 1972). McGraw Hill, New York. ISBN 978-0-07-061726-1.Cf. en particulier le premier chapitre intitulé : Algorithms, Turing Machines, and Programs . Sa définition informelle succincte : “…toute séquence d’instructions qui peut être obéie par un robot, s’appelle un algorithme ” (p. 4).
• Tausworthe, Robert C (1977). Développement standardisé de logiciels informatiques Partie 1 Méthodes . Englewood Cliffs NJ: Prentice – Hall, Inc.ISBN 978-0-13-842195-3.
• Turing, Alan M. (1936-1937). “Sur les nombres calculables, avec une application au problème d’entscheidungs”. Actes de la London Mathematical Society . Série 2. 42 : 230–265. doi : 10.1112/plms/s2-42.1.230 .. Corrections, ibid, vol. 43(1937) p. 544–546. Reproduit dans L’Indécidable , p. 116ff. Le célèbre article de Turing a été rédigé en tant que mémoire de maîtrise au King’s College de Cambridge au Royaume-Uni.
• Turing, Alan M. (1939). “Systèmes de logique basés sur des ordinaux”. Actes de la London Mathematical Society . 45 : 161–228. doi : 10.1112/plms/s2-45.1.161 . hdl : 21.11116/0000-0001-91CE-3 .Réimprimé dans L’Indécidable , pp. 155ff. L’article de Turing qui définissait “l’oracle” était sa thèse de doctorat à Princeton.
• Office des brevets et des marques des États-Unis (2006), 2106.02 **>Algorithmes mathématiques : 2100 Brevetabilité , Manuel de procédure d’examen des brevets (MPEP). Dernière révision août 2006

Lectures complémentaires

• Bellah, Robert Neelly (1985). Habitudes du cœur : individualisme et engagement dans la vie américaine . Berkeley : Presse de l’Université de Californie. ISBN 978-0-520-25419-0.
• Berlinski, David (2001). L’avènement de l’algorithme : le voyage de 300 ans d’une idée à l’ordinateur . Livres de récolte. ISBN 978-0-15-601391-8.
• Chabert, Jean-Luc (1999). Une histoire des algorithmes : du caillou à la micropuce . Édition Springer. ISBN 978-3-540-63369-3.
• Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introduction aux algorithmes (3e éd.). Presse du MIT. ISBN 978-0-262-03384-8.
• Harel, David; Feldman, Yishai (2004). Algorithmique : l’esprit de l’informatique . Addison-Wesley. ISBN 978-0-321-11784-7.
• Hertzke, Allen D.; McRorie, Chris (1998). “Le concept d’écologie morale”. Dans Lawler, Peter Augustin; McConkey, Dale (éd.). Communauté et pensée politique aujourd’hui . Westport, Connecticut : Praeger .
• Knuth, Donald E. (2000). Articles sélectionnés sur l’analyse des algorithmes . Stanford, Californie : Centre pour l’étude du langage et de l’information.
• Knuth, Donald E. (2010). Articles sélectionnés sur la conception d’algorithmes . Stanford, Californie : Centre pour l’étude du langage et de l’information.
• Wallach, Wendell; Allen, Colin (novembre 2008). Machines morales : Enseigner aux robots le bien du mal . États-Unis : Oxford University Press. ISBN 978-0-19-537404-9.
• Bleakley, Chris (2020). Poèmes qui résolvent des énigmes : l’histoire et la science des algorithmes . Presse universitaire d’Oxford. ISBN 978-0-19-885373-2.

Liens externes

Recherchez l’ algorithme dans Wiktionary, le dictionnaire gratuit.

Wikibooks a un livre sur le thème : Algorithmes

Sur Wikiversité , vous pouvez en savoir plus et enseigner aux autres l’ algorithme au Département d’algorithme

Wikimedia Commons a des médias liés aux algorithmes .

• “Algorithme” , Encyclopédie des mathématiques , EMS Press , 2001 [1994]
• Algorithmes chez Curlie
• Weisstein, Eric W. “Algorithme” . MathWorld .
• Dictionnaire des algorithmes et des structures de données – Institut national des normes et de la technologie

Référentiels d’algorithmes

• Le référentiel d’algorithmes de Stony Brook – Université d’État de New York à Stony Brook
• Algorithmes collectés de l’ACM – Association for Computing Machinery
• La Stanford GraphBase – Université de Stanford