algorithme - Algorithm


Un article de Wikipédia, l'encyclopédie libre

Ordinogramme d'un algorithme ( l'algorithme d'Euclide ) pour calculer le plus grand diviseur commun (GCD) de deux nombres a et b dans des endroits nommé 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 dans l' emplacement b est supérieur ou égal au nombre d' un dans l' emplacement a) ALORS, l'algorithme spécifie b ← b - a ( ce qui signifie le nombre b - un remplace l'ancien b ). De même, si A> B, A ← A - B. Le procédé se termine lorsque le contenu de (B) est de 0, ce qui donne le pgcd dans A. (algorithme dérivé de Scott 2009: 13; les symboles et le style de dessin à partir Tausworthe 1977) .

En mathématiques et l'informatique , un algorithme ( / æ l ɡ ə r ɪ ð əm /  ( écouter )A propos de ce son ) est une spécification non ambiguë de la façon de résoudre une classe de problèmes. Les algorithmes peuvent effectuer le calcul , le traitement des données et le raisonnement automatisé des tâches.

En tant que méthode efficace , un algorithme peut être exprimé dans une quantité limitée d'espace et le temps et dans un langage formel bien défini pour le calcul d' une fonction . A partir d'un état initial et l' entrée initiale (peut - être vide ), les instructions décrivent un calcul qui, lorsque exécuté , passe par un nombre fini d'états successifs bien définies, par la suite la production de « sortie » et se terminant à un état de fin final. Le passage d'un état à l'autre est pas nécessairement déterministe ; certains algorithmes, appelés algorithmes randomisés , entrée aléatoire intègrent.

Le concept de l' algorithme existe depuis des siècles. Mathématiciens grecs ont utilisé des algorithmes, par exemple, le tamis d'Ératosthène pour trouver les nombres premiers et l' algorithme d' Euclide pour trouver le plus grand commun diviseur de deux nombres.

Le mot algorithme lui - même dérive du mathématicien 9ème siècle Al-Khwârizmî , latinisé Algoritmi . Une formalisation partielle de ce qui allait devenir le concept moderne de l' algorithme a commencé avec des tentatives pour résoudre le Entscheidungsproblem (problème de décision) posée par David Hilbert en 1928. formalisations ultérieures ont été encadrées comme des tentatives pour définir « calculabilité efficace » ou « méthode efficace ». Ces formalisations comprenaient la Gödel - Herbrand - Kleene fonctions récursives de 1930, 1934 et 1935, Alonzo Church 's calcul lambda de 1936, Emil post ' s Formulation 1 de 1936, et Alan Turing de machines de Turing de 1936-1937 et 1939.

Étymologie

Le mot « algorithme » a ses racines dans latinizing le nom de Al-Khwârizmî dans une première étape à Algorismus . Al-Khwarizmi ( persan : خوارزمی ., C 780-850) était un Persan mathématicien, astronome , géographe et chercheur à la Maison de la Sagesse à Bagdad , dont le nom signifie « le natif de Khwarezm », une région qui faisait partie de grand Iran et est maintenant en Ouzbékistan .

A propos de 825, al-Khwarizmi a écrit une langue arabe traité sur le système de nombre hindou-arabe , qui a été traduit en latin au 12e siècle sous le titre Algoritmi de Indorum numero . Ce titre signifie « Algoritmi sur le nombre des Indiens », où « Algoritmi » était le traducteur latinisation du nom d'Al-Khwarizmi. Al-Khwarizmi est le mathématicien le plus lu en Europe à la fin du Moyen Age, principalement par une autre de ses livres, l' algèbre . À la fin du latin médiéval, Algorismus , anglais « algorisme », la corruption de son nom, signifie simplement le « système de nombre décimal ». Au 15ème siècle, sous l'influence du mot grec ἀριθμός « nombre » ( cf. « arithmétique »), le mot latin a été modifié pour 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.

En anglais, il a d' abord été utilisé dans environ 1230, puis par Chaucer en 1391. anglais a adopté le terme français, mais il a fallu attendre la fin du 19e siècle que « algorithme » a le sens qu'il a en anglais moderne.

Une autre utilisation précoce du mot est de 1240, dans un manuel intitulé Carmen de Algorismo composée par Alexandre de Villedieu . Il commence ainsi:

Haec Algorismus ars praesens dicitur, en qua / Talibus Indorum fruimur bis quinque figuris.

qui se traduit par:

Algorisme est l'art par lequel à l'heure actuelle, nous utilisons ces chiffres indiens, qui sont au nombre de deux fois cinq.

Le poème est à quelques centaines de lignes long et résume l'art du calcul avec le nouveau style de dés indiens, ou Talibus Indorum ou chiffres hindous.

définition informelle

Une définition informelle pourrait être « un ensemble de règles qui définit précisément une séquence d'opérations. » qui inclurait tous les programmes informatiques, y compris les programmes qui ne fonctionnent pas de calculs numériques. En général, un programme est seulement un algorithme si elle arrête finalement.

Un exemple typique d'un algorithme est l' algorithme d' Euclide pour déterminer le diviseur commun maximum de deux nombres entiers; un exemple (il y en a d' autres) est décrite par l' organigramme ci - dessus et , par exemple , dans une section ultérieure.

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

Aucun être humain ne peut écrire assez vite, ou assez longtemps ou assez petit † († « plus petit et plus petit sans limite ... vous devriez essayer d'écrire sur des molécules, sur les atomes, sur les électrons ») à la liste tous les membres d'une enumerably ensemble infini en écrivant leurs noms, l' un après l' autre, dans une certaine notation. Mais les humains peuvent faire quelque chose tout aussi utile, dans le cas de certains ensembles infinis enumerably: Ils peuvent donner des instructions explicites pour déterminer la n ième membre de l'ensemble , pour fini arbitraire n . Ces instructions doivent être données tout à fait explicitement, sous une forme dans laquelle ils pourraient être suivis par une machine informatique ou par un humain qui est capable d'effectuer des opérations élémentaires que très sur les symboles.

Un « ensemble enumerably infini » est celui dont les éléments peuvent être mis en relation un-à-un avec les nombres entiers correspondance. Ainsi, Boolos et Jeffrey disent qu'un algorithme implique des instructions pour un processus qui « crée » des entiers de sortie d'un quelconque entier « d'entrée » ou des nombres entiers, en théorie, peut être arbitrairement grand. Ainsi , un algorithme peut être une équation algébrique tel que y = m + n - deux « variables d'entrée » arbitraires m et n qui produisent un signal de sortie y . Mais diverses tentatives des auteurs pour définir la notion indiquent que le mot implique beaucoup plus que cela, quelque chose de l'ordre de (pour l'exemple d'addition):

Des instructions précises (en langue comprise par « l'ordinateur ») pour un processus rapide et efficace, « bon » qui spécifie les « mouvements » de « l'ordinateur » (machine ou humain, équipé du nécessaire en interne contenaient des informations et des capacités) pour trouver , décoder, et ensuite traiter les nombres entiers arbitraires entrée / symboles m et n , les symboles + et = ... et « efficace » de produire, dans un temps « raisonnable », entier de sortie y en un lieu déterminé et dans un format spécifié.

Le concept de l' algorithme est également utilisé pour définir la notion de décidabilité . Cette notion est essentielle pour expliquer comment les systèmes formel entrent en étant à partir d'un petit ensemble d' axiomes et de règles. Dans la logique , le temps qu'un algorithme afin de compléter ne peut pas être mesurée, car il est apparemment pas lié à notre dimension physique habituelle. De telles incertitudes, qui caractérisent les travaux en cours, découle l'absence d'une définition de l' algorithme qui convient à la fois concrète (dans un sens) et de l' utilisation abstraite du terme.

Formalisation

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

Minsky: « Mais nous allons aussi maintenir, avec Turing que toute procédure qui pourrait... « Naturellement » être appelé efficace, peut, en effet, être réalisé par une machine (simple) Bien que cela puisse sembler extrême, les arguments... . en sa faveur sont difficiles à réfuter ».

Gourevitch: « ... l'argument informel de Turing en faveur de sa thèse justifie une thèse forte: chaque algorithme peut être simulé par une machine de Turing ... selon Savage [1987], un algorithme est un processus de calcul défini par une machine de Turing » .

Typiquement, quand un algorithme est associé au traitement de l' information, les données peuvent être lues à partir d' une source d'entrée, écrites sur un dispositif de sortie et stockée pour un traitement ultérieur. Les données mémorisées sont considérées comme faisant partie de l'état interne de l'entité effectuant l'algorithme. Dans la pratique, l'état est stocké dans une ou plusieurs structures de données .

Pour certains ce processus de calcul, l'algorithme doit être rigoureusement défini: spécifié dans la façon dont il applique dans toutes les circonstances possibles qui pourraient survenir. Cela est, les mesures conditionnelles doivent être systématiquement traitées, au cas par cas; les critères pour chaque cas doivent être claires (et calculable).

Parce qu'un algorithme est une liste précise des étapes précises, l'ordre de calcul est toujours indispensable au bon fonctionnement de l'algorithme. Les instructions sont généralement supposés être énumérés explicitement, et sont décrites comme à partir « du haut » et aller « vers le bas », une idée qui est décrit de façon plus formelle par flux de contrôle .

Jusqu'à présent, cette discussion de la formalisation d'un algorithme a pris les locaux de la programmation impérative . Ceci est la conception la plus courante, et il tente de décrire une tâche discrète, des moyens « mécaniques ». Unique à cette conception d'algorithmes formalisés est l' opération d'affectation , le réglage de la valeur d'une variable. Il découle de l'intuition de la « mémoire » comme un bloc - notes. Il est un exemple ci - dessous d'une telle cession.

Pour certaines conceptions différentes de ce qui constitue un algorithme voir la programmation fonctionnelle et la programmation logique .

algorithmes exprimant

Les algorithmes peuvent être exprimés dans de nombreux types de notation, y compris les langues naturelles , pseudocode , diagrammes , graphiques Drakon- , les langages de programmation ou tables de contrôle (traitées par des interprètes ). Expressions en langage naturel d'algorithmes ont tendance à être bavard et ambigu, et sont rarement utilisés pour des algorithmes complexes ou techniques. Pseudocode, organigrammes, diagrammes Drakon- et tables de contrôle sont des moyens structurés pour exprimer des algorithmes qui permettent d' éviter un grand nombre des ambiguïtés communes dans les déclarations de langage naturel. Les langages de programmation sont principalement destinés à exprimer des algorithmes sous une forme qui peut être exécuté par un ordinateur , mais sont souvent utilisés comme un moyen de définir ou des algorithmes de documents.

Il y a une grande variété de représentations possibles et on peut exprimer une donnée machine de Turing programme comme une séquence de tables de machines (voir plus à la machine à états finis , table de transition d'état et table de contrôle ), comme des organigrammes et des tableaux de Drakon- (voir plus à diagramme d'état ), ou comme une forme de rudimentaire code machine ou code assembleur appelés « ensembles de quadruplets » (voir plus à l' machine de Turing ).

Les représentations d'algorithmes peuvent être classés en trois niveaux acceptés de description de la machine de Turing:

1 Description de haut niveau
« ... la prose pour décrire un algorithme, en ignorant les détails de mise en œuvre. A ce niveau, on n'a pas besoin de mentionner comment la machine gère sa bande ou de la tête. »
2 Description de 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 il stocke les données sur la bande. A ce niveau, nous ne donnons pas les détails des états ou la fonction de transition. »
3 Description formelle
Le plus détaillé, « plus bas niveau », donne « la table d'état » de la machine de Turing.

Pour un exemple de l'algorithme simple « Ajouter m + n » décrit dans les trois niveaux, voir l' algorithme # Exemples .

Conception

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

L' un des aspects les plus importants de la conception de l' algorithme crée un algorithme qui a une exécution efficace, aussi connu comme Big O .

étapes typiques dans le développement d'algorithmes:

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

la mise en oeuvre

NAND logique algorithme mis en oeuvre par voie électronique en 7400 puce

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

Des algorithmes informatiques

Des exemples Flowchart canoniques structures Böhm-Jacopini : SEQUENCE (rectangles descendant la page), le TOUT-DO et IF-THEN-ELSE. Les trois structures sont faites de la GOTO primitive conditionnelle ( IF Test = true ALORS GOTO étape xxx ) (un diamant), le GOTO (rectangle) sans conditions, les différents opérateurs d'affectation (rectangle), et HALT (rectangle). Nesting de ces structures à l' intérieur des blocs d'affectation résultat des diagrammes complexes (cf Tausworthe 1977: 100.114).

Dans les systèmes informatiques , un algorithme est essentiellement une instance de logique écrite dans le logiciel par les développeurs de logiciels, pour être efficace pour l'ordinateur destiné « cible » (s) pour produire la sortie de donnée (peut - être nulle) entrée . Un algorithme optimal, même en cours d' exécution dans le vieux matériel, produirait des résultats plus rapides qu'un non-optimale (plus la complexité temporelle algorithme) dans le même but, en cours d' exécution dans le matériel plus efficace; c'est pourquoi les algorithmes, comme le matériel informatique, sont la technologie envisagée.

Programmes, « bons » programmes (rapide) « élégants » (compact) : La notion de « simplicité et élégance » apparaît de façon informelle dans Knuth et précisément dans Chaitin :

Knuth:.. » .Nous veulent bien ...... Algorithmes dans un certain sens esthétique vaguement défini un critère est la durée du temps nécessaire pour effectuer l'algorithme .. D' autres critères sont l' adaptabilité de l'algorithme à l' informatique, sa simplicité et de l' élégance , etc"
Chaitin: «.. Un programme est « élégant », je veux dire que c'est le plus petit programme possible pour produire la sortie qu'il fait »

Chaitin préfaces sa définition avec: « Je vais vous montrer que vous ne pouvez pas prouver qu'un programme est « élégant » » -such une preuve résoudrait le problème de l' arrêt (ibid).

Algorithme par rapport à la fonction calculable par un algorithme : Pour une fonction donnée plusieurs algorithmes peuvent exister. Cela est vrai, même sans augmenter le jeu d'instructions disponibles à la disposition du programmeur. Rogers fait remarquer qu ' « il est... Important de distinguer la notion d' algorithme , à savoir la procédure et la notion de fonction calculable par un algorithme , à savoir la cartographie produits par la procédure. La même fonction peut avoir plusieurs algorithmes différents ».

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

Ordinateurs (et computors), des modèles de calcul : est un type de machine restreint, un « dispositif mécanique déterministe discret » qui suit aveuglément ses instructions d' un ordinateur (ou « Computor » humaine). Modèles primitifs de Melzak et Lambek réduit cette notion de quatre éléments: (i) discrètes, discernables d' emplacements , (ii) discrets, indiscernables compteurs (iii) un agent, et (iv) une liste d'instructions qui sont efficaces par rapport à la capacité de la agent.

Minsky décrit une variante plus agréable du modèle « boulier » de Lambek dans ses « bases très simples pour calculabilité ». La machine de Minsky procède de manière séquentielle à travers ses cinq (ou six, selon la façon dont on compte des instructions), à moins que ce soit une condition IF-THEN GOTO ou un GOTO inconditionnel change le déroulement du programme hors séquence. En plus HALT, la machine de Minsky comprend trois missions opérations (remplacement, substitution): ZERO (par exemple , le contenu de l' emplacement remplacé par 0: L ← 0), SUCCESSEUR (par exemple L ← L + 1), et DIMINUER (par exemple L ← L - 1 ). Rarement doit écrire un programmeur « code » avec un tel jeu d'instructions limité. Mais Minsky montre (comme le font Melzak et Lambek) que sa machine est Turing complet avec seulement quatre généraux types d'instructions: GOTO conditionnelle, inconditionnelle GOTO, cession / remplacement / substitution et HALT.

Simulation d'un algorithme: ordinateur (computor) Langue : Knuth conseille au lecteur que «.. La meilleure façon d'apprendre un algorithme est d'essayer de prendre immédiatement stylo et du papier et le travail par un exemple ». Mais qu'en est- une simulation ou l' exécution de la chose réelle? Le programmeur doit se traduire par l'algorithme dans un langage que le simulateur / ordinateur / computor peuvent effectivement exécuter. Pierre donne un exemple: lors du calcul des racines d'une équation du second degré le computor doit savoir comment prendre une racine carrée. Si elles ne le font pas, alors l'algorithme, pour être efficace, doit fournir un ensemble de règles pour extraire une racine carrée.

Cela signifie que le programmeur doit connaître un « langage » qui est efficace par rapport à l'agent de calcul cible (ordinateur / computor).

Mais quel modèle doit être utilisé pour la simulation? Van Emde Boas observe « même si nous basons théorie de la complexité sur abstraite au lieu de machines en béton, l' arbitraire du choix d'un modèle reste. Il est à ce point que la notion de simulation entre ». Lorsque la vitesse est mesurée, l'ensemble d' instructions questions. Par exemple, le sous - programme dans l'algorithme d'Euclide pour calculer le reste exécuterait beaucoup plus rapide si le programmeur avait un « module instruction » disponible plutôt que la soustraction (ou pire: juste « décrémentation » Minsky).

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

Symboles d'organigramme Canonical : L'aide graphique appelé un 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 se déroule vers le bas. Ses principaux symboles ne sont que quatre: la flèche indiquant le déroulement du programme dirigé, le rectangle (SEQUENCE, GOTO), le diamant (IF-THEN-ELSE), et le point (OR-cravate). Les structures canoniques Böhm-Jacopini sont faits de ces formes primitives. Les sous-structures peuvent « nid » en rectangles, mais seulement si une sortie unique se produit à partir de la superstructure. Les symboles et leur utilisation pour construire les structures canoniques sont représentées dans le diagramme.

Exemples

par exemple l'algorithme

Une animation de l' algorithme de tri rapide de tri d' un tableau de valeurs aléatoires. Les barres rouges marquent l'élément de pivot; au début de l'animation, le plus éloigné de l' élément sur le côté de droite est choisi comme pivot.

L'un des algorithmes les plus simples est de trouver le plus grand nombre dans une liste de numéros d'ordre aléatoire. Trouver la solution, il faut regarder à chaque numéro dans la liste. De ce fait suite à un algorithme simple, qui peut être indiqué dans une description de haut niveau en prose anglais, comme:

Description de haut niveau:

  1. S'il n'y a pas de chiffres dans l'ensemble il n'y a pas plus grand nombre.
  2. Supposons que le premier numéro dans l'ensemble est le plus grand nombre dans l'ensemble.
  3. Pour chaque numéro restant dans l'ensemble: si ce nombre est plus grand que le plus grand nombre actuel, pensez que ce nombre soit le plus grand nombre dans l'ensemble.
  4. Quand il n'y a pas de chiffres disponible dans le jeu à itérer, compte le plus grand nombre actuel d'être le plus grand nombre de l'ensemble.

(Quasi) description formelle: en prose , mais beaucoup plus proche du langage de haut niveau d'un programme informatique, ce qui suit est le codage plus formel de l'algorithme pseudo - code ou le code pidgin :

Algorithm LargestNumber
  Input: A list of numbers L.
  Output: The largest number in the list L.
  if L.size = 0 return null
  largestL[0]
  for each item in L, do
    if item > largest, then
      largestitem
  return largest
  • « ← » désigne l' affectation . Par exemple, « le plus grandélément » signifie que la valeur des plus grands changements à la valeur de l' article .
  • « Retour » met fin à l'algorithme et fournit la valeur suivante.

L'algorithme d'Euclide

L'exemple diagramme de l'algorithme d'Euclide de TL Heath (1908), avec plus de détails ajouté. Euclide ne va pas au-delà d'une troisième mesure et donne pas d'exemples numériques. Nicomaque donne l'exemple de 49 et 21: « Je soustrais moins de plus, 28 est à gauche, puis à nouveau je soustrais de ce même 21 (pour cela est possible), 7 est à gauche, je soustrais ce de 21, 14 est à gauche, à partir de laquelle je soustrais encore 7 (pour cela est possible), 7 est à gauche, mais 7 ne peut être soustrait de 7. » Heath commente que « La dernière phrase est curieuse, mais le sens de celui-ci est assez évident, comme aussi le sens de l'expression de mettre fin à« l'un et le même nombre. »(Heath 1908: 300).

Euclide l » algorithme pour calculer le plus grand commun diviseur (PGCD) à deux chiffres apparaît comme la proposition II dans le Livre VII ( « théorie des nombres élémentaire ») de ses éléments . Euclide pose le problème ainsi: « Compte tenu de deux nombres premiers pas les uns aux autres, de trouver leur plus grand dénominateur commun ». Il définit « Un certain nombre [A] une multitude composée d'unités »: un certain nombre de comptage, un nombre entier positif ne comprenant pas zéro. Pour « mesure » consiste à placer une plus courte longueur de mesure s (successivement q fois) le long de plus grande longueur L jusqu'à ce que la partie restante r est inférieure à la plus courte longueur s . En d'autres termes modernes, reste r = l - q × s , q étant le quotient, ou reste r est le « module », la partie entière fractionnaire reste après la division.

Pour la méthode d'Euclide pour réussir, les longueurs de départ doivent satisfaire à deux exigences: (i) les longueurs ne doivent pas être zéro, et (ii) la soustraction doit être « propre »; à savoir, un test doit garantir que le plus petit des deux nombres est soustraite de la plus grande (en variante, les deux peuvent être égaux de sorte que leurs rendements de soustraction zéro).

La preuve originale d'Euclide ajoute une troisième exigence: les deux longueurs ne doivent pas être premiers entre eux. Euclide stipulait ce afin qu'il puisse construire une reductio ad absurdum preuve que les deux commune mesure de numéros est en fait le plus grand . Alors que l'algorithme de Nicomaque est le même que celui d'Euclide, lorsque les chiffres sont premiers entre eux, il donne le chiffre « 1 » pour leur commune mesure. 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 commun diviseur 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 instructions types sont nécessaires pour exécuter algorithme des tests logiques d'Euclide (GOTO conditionnelle), l' affectation GOTO, sans conditions (remplacement), et la soustraction.

  • Un emplacement est symbolisé par lettre majuscule (s), par exemple S, A, etc.
  • La quantité variable (nombre) dans un endroit est écrit dans la lettre minuscule (s) et (généralement) associé au nom de l'emplacement. Par exemple, l' emplacement L au début peut contenir le nombre l = 3009.

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

« Inélégant » est une traduction de la version de Knuth de l'algorithme avec une boucle de reste sur la base de soustraction, en remplacement de son utilisation de division (ou une instruction « module »). Dérivé de Knuth 1973: 2-4. Selon les deux nombres « inélégant » peut calculer le GCD en moins d'étapes que « élégant ».

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

ENTRÉE :

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

E0: [Assurez -vous rs .]

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

E1: [Trouver reste] : Jusqu'à ce que la longueur restante r dans R est inférieure à la longueur plus courte s dans S, soustraire de manière répétée le nombre de mesure s en S à partir de la longueur restante r R.

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

E2: [Le zéro reste?] : (I) la dernière mesure était exacte, le reste dans R est égal à zéro, et le programme peut arrêter, OU (ii) l'algorithme doit continuer: la dernière mesure a laissé un reste dans R moins de mesure du nombre de S.

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

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

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

SORTIE :

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

FAIT :

16 HALT, END, STOP.

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

La version suivante de l'algorithme d'Euclide ne nécessite que six instructions de base pour faire ce que treize sont tenus de le faire « inélégant »; Pire encore, « inélégant » nécessite plus de types d'instructions. L'organigramme de la « élégante » se trouve en haut de cet article. Dans le (non structuré) la langue de base, les étapes sont numérotées, et l'instruction est l'instruction d'affectation symbolisée par ←. LET [] = []

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

La version suivante peut être utilisée avec des langages orientés objet:

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

Comment « élégant » fonctionne : Au lieu d'une « boucle Euclide », « élégant » externe déplace d' avant en arrière entre les deux « co-boucles », un A> boucle B qui calcule A ← A - B et B ≤ A boucle qui calcule B ← B - A. Cela fonctionne parce que, quand enfin le M de diminuende est inférieure ou égale à la soustraction s (Différence = diminuende - diminuteur), le diminuende peut devenir s (la nouvelle longueur de mesure) et la soustraction peuvent devenir le nouveau r (la longueur à mesurer); autrement dit le « sens » de la soustraction inverse.

Test des algorithmes Euclide

Est -ce un algorithme faire ce que son auteur veut qu'il fasse? Quelques cas de test suffisent généralement pour confirmer les fonctionnalités de base. Une source utilise 3009 et 884. Knuth a suggéré 40902, 24140. Un autre cas intéressant est le deux premiers entre les numéros 14157 et 5950.

Mais des cas exceptionnels doivent être identifiés et testés. Est-ce que "inélégant" effectuer correctement lorsque R> S, S> R, R = S? Même chose pour "élégant": B> A, A> B, A = B? (Oui à tous). Qu'est - ce qui se passe quand un nombre est égal à zéro, les deux chiffres sont nuls? ( « Inélégant » calcule toujours dans tous les cas, « élégant » pour toujours quand A calcule = 0.) Qu'advient - il si négatif chiffres sont entrés? Nombres fractionnaires? Si les numéros d'entrée, à savoir le domaine de la fonction calculée par l'algorithme / programme, est d'inclure uniquement des nombres entiers positifs , y compris zéro, alors les échecs à zéro indiquent que l'algorithme (et le programme qui instancie elle) est une fonction partielle plutôt que une fonction totale . Une défaillance notable en raison des exceptions est le 5 Ariane Vol 501 échec de la fusée (4 Juin, 1996).

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

Mesurer et améliorer les algorithmes Euclide

Elegance (compacité) par rapport à la bonté (vitesse) : Avec seulement six instructions de base, « élégant » est le grand vainqueur, par rapport à « inélégant » à treize instructions. Cependant, « inélégant » est plus rapide (il arrive à HALT en moins d' étapes). L' algorithme d' analyse indique pourquoi il en est le cas: « élégante » fait deux tests conditionnels dans chaque boucle de soustraction, alors que « inélégant » ne fait qu'une seule. Comme l'algorithme ( en général) nécessite de nombreuses boucles traversées, en moyenne beaucoup de temps est gaspillée faire un « B = 0? » test qui est nécessaire seulement après que le reste est calculé.

Peut les algorithmes être améliorés? : Une fois que le programmeur juges un programme « apte » et « efficace » , c'est, il calcule la fonction voulue par son auteur, la question devient alors, peut - il être amélioré?

La compacité de « inélégant » peut être améliorée par l'élimination de cinq étapes. Mais Chaitin a prouvé que le compactage un algorithme ne peut pas être automatisé par un algorithme généralisé; plutôt, il ne peut se faire heuristically ; à savoir, par recherche exhaustive (exemples se trouvent à castor occupé ), essais et erreurs, l' intelligence, la perspicacité, l' application du raisonnement inductif , etc. Observons que les étapes 4, 5 et 6 sont répétées dans les étapes 11, 12 et 13. Comparaison avec « élégant » donne une indication que ces étapes, ainsi que les étapes 2 et 3, peuvent être éliminés. Cela réduit le nombre d'instructions de base treize à huit, ce qui le rend « plus élégant » que « élégant », à neuf étapes.

La vitesse de « élégante » peut être améliorée en déplaçant le « B = 0? » essai à l'extérieur des deux boucles de soustraction. Ce changement nécessite l'ajout de trois instructions (B = 0 ?, A = 0 ?, GOTO). Maintenant « élégant » calcule les exemples de numéros plus rapide; que ce soit toujours le cas pour une donnée A, B et R, S nécessiterait une analyse détaillée.

analyse algorithmiques

Il est souvent important de savoir à quel point une ressource particulière (comme le temps ou le stockage) est théoriquement nécessaire pour un algorithme donné. Des méthodes ont été mises au point pour l' analyse des algorithmes pour obtenir ces réponses quantitatives (estimations); par exemple, l'algorithme de tri ci - dessus a une exigence de temps de O ( n ), en utilisant la notation grand O avec n comme étant la longueur de la liste. En tout temps l'algorithme a besoin de se rappeler que deux valeurs: le plus grand nombre trouvé à ce jour, et sa position actuelle dans la liste d'entrée. Il est donc dit d'avoir une exigence spatiale de O (1) , si l'espace nécessaire pour stocker les numéros d'entrée ne sont pas comptés, ou O ( n ) si elle est comptée.

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

Formel ou empirique

L' analyse et l' étude des algorithmes est une discipline de l'informatique , et est souvent pratiquée abstraitement sans l'utilisation d'un spécifique langage de programmation ou la mise en œuvre. En ce sens, l' analyse de l' algorithme ressemble à d' autres disciplines mathématiques en ce sens qu'elle met l' accent sur les propriétés sous - jacentes de l'algorithme et non sur les détails de toute mise en œuvre particulière. Habituellement pseudocode est utilisé pour l' analyse car il est 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 mis en œuvre sur des plateformes matérielles / logicielles particulières et leur efficacité algorithmique est finalement mis à l'épreuve en utilisant le code réel. Pour la solution d'un problème « d' une off », l'efficacité d'un algorithme particulier ne peut pas avoir des conséquences importantes ( à moins que n est extrêmement importante) , mais pour les algorithmes conçus pour rapide interactif, commercial ou longue utilisation scientifique de la vie , il peut être critique. Mise à l' échelle de la petite n à grande n expose souvent des algorithmes inefficaces qui sont par ailleurs bénignes.

Les tests empiriques est utile , car il peut découvrir des interactions inattendues qui affectent les performances. Repères peuvent être utilisés pour comparer avant / après des améliorations potentielles à un algorithme après optimisation du programme. Les tests empiriques ne peuvent pas remplacer l' analyse formelle, cependant, et ne sont pas négligeables pour effectuer de manière équitable.

l'efficacité de l'exécution

Pour illustrer les améliorations possibles des algorithmes possibles même bien établies, une innovation récente importante, ayant trait à la FFT algorithmes (largement utilisé dans le domaine du traitement d'image), peut réduire le temps de traitement jusqu'à 1000 fois pour des applications comme l' imagerie médicale. En général, l' amélioration de la vitesse dépendent des propriétés particulières du problème, qui sont très fréquents dans les applications pratiques. Speedups de cette ampleur permettent des dispositifs informatiques qui font usage intensif de traitement d'images (comme les appareils photo numériques et des équipements médicaux) à consommer moins d' énergie.

Classification

Il existe différentes façons de classer les algorithmes, chacun avec ses propres mérites.

par la mise en œuvre

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

récursion
Un algorithme récursif est une qui appelle (fait référence à) lui - même à plusieurs reprises jusqu'à ce qu'une certaine condition (également connu sous condition de terminaison) correspond, ce qui est une méthode courante pour la programmation fonctionnelle . Itératives algorithmes 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 à la mise en œuvre d' une ou l'autre. Par exemple, les tours de Hanoï est bien compris en utilisant la mise en œuvre récursive. Toutes les versions récursive a un équivalent (mais peut - être plus ou moins complexe) version itérative, et vice versa.
Logique
Un algorithme peut être considéré comme contrôlé déduction logique . Cette notion peut être exprimée sous la forme: algorithme = logique + contrôle . Le composant logique exprime les axiomes qui peuvent être utilisées dans le calcul et le composant de commande détermine la façon dont la déduction est appliquée sur les axiomes. Ceci est la base de la programmation logique paradigme. Dans les langages de programmation logique pure, le composant de commande est fixe et les algorithmes sont spécifiés en fournissant uniquement le composant logique. L'appel de cette approche est l'élégante sémantique : un changement dans les axiomes produit un changement bien défini dans l'algorithme.
Série, parallèle ou distribuée
Les algorithmes sont habituellement 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 de série. Un algorithme conçu pour un tel environnement est appelé un algorithme de série, par opposition à la parallèle des algorithmes ou des algorithmes distribués . Algorithmes parallèles tirer parti des architectures informatiques où plusieurs processeurs peuvent travailler sur un problème en même temps, alors que les algorithmes distribués utilisent plusieurs machines connectées à un réseau informatique . Algorithmes parallèles ou distribués divisent le problème en sous - plus symétriques ou asymétriques et recueillir les résultats ensemble. La consommation des ressources dans ces algorithmes ne sont pas seulement des cycles de processeur sur chaque processeur , mais aussi les frais généraux de communication entre les processeurs. Certains algorithmes de tri peuvent être parallélisés efficacement, mais leurs frais généraux de communication est coûteux. Algorithmes itératifs sont généralement parallélisables. Certains problèmes ont pas des algorithmes parallèles et sont appelés problèmes intrinsèquement série.
Déterministes ou non déterministe
Algorithmes déterministes résoudre le problème à la décision exacte à chaque étape de l'algorithme alors que les algorithmes non déterministes résoudre des problèmes par le biais de devinettes , bien que des suppositions typiques sont faits plus précis grâce à l'utilisation des heuristiques .
Exacte ou approximative
Alors que de nombreux algorithmes atteignent une solution exacte, les algorithmes d'approximation cherchent une approximation qui est plus proche de la vraie solution. Le rapprochement peut être atteint soit en utilisant un déterministe ou une stratégie aléatoire. Ces algorithmes ont une valeur pratique pour de nombreux problèmes difficiles. L' un des exemples d'un algorithme approximatif est le problème Knapsack . Le problème est un problème Knapsack où il y a un ensemble d'éléments donnés. L'objectif du problème est d'emballer le sac pour obtenir la valeur totale maximale. Chaque élément a un certain poids et une certaine valeur. Le poids total que l' on peut transporter est pas plus un nombre fixe X. Donc, nous devons considérer le poids des articles ainsi que leur valeur.
algorithme quantique
Ils fonctionnent sur un modèle réaliste de calcul quantique . Le terme est généralement utilisé pour les algorithmes qui semblent intrinsèquement quantiques, ou utilisent une caractéristique essentielle de l' informatique quantique , comme 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 d'un paradigme. Il y a un certain nombre de paradigmes, chacun différent de l'autre. En outre, chacune de ces catégories comprend différents types d'algorithmes. Certains paradigmes communs sont:

Force brute ou recherche exhaustive
Ceci est la méthode naïve d'essayer toutes les solutions possibles pour voir qui est le meilleur.
Diviser et conquérir
Une fracture et de l' algorithme Conquer réduit de façon répétée une instance d'un problème à un ou plusieurs petits cas du même problème (généralement récursive ) jusqu'à ce que les instances sont assez petits pour résoudre facilement. Un tel exemple de diviser pour mieux régner est le tri de fusion . Le tri peut se faire sur chaque segment de données après avoir divisé les données en segments et le tri des données entières peuvent être obtenues dans la phase de conquête par la fusion des segments. Une variante plus simple de diviser pour mieux régner est appelé une diminution et algorithme conquérir , qui permet de résoudre un sous - problème identique et utilise la solution de ce sous - problème pour résoudre le plus grand problème. Diviser pour mieux régner divise le problème en plusieurs sous - problèmes et donc le stade de Conquer est plus complexe que diminuer et algorithmes conquer. Un exemple d'un algorithme de réduction et conquer est l' algorithme de recherche binaire .
Recherche et dénombrement
De nombreux problèmes (comme le jeu d' échecs ) peuvent être modélisés comme des problèmes sur des graphiques . Un algorithme d'exploration graphique spécifie les règles pour se déplacer dans un graphique et est utile pour de tels problèmes. Cette catégorie comprend également des algorithmes de recherche , branch and bound énumération et retours en arrière .
algorithme aléatoire
Ces algorithmes font des choix au hasard (ou pseudo-aléatoire). Ils peuvent être très utiles pour trouver des solutions approchées pour des problèmes où trouver des solutions exactes peuvent être peu pratique (voir 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 . Que ce soit des algorithmes randomisés avec la complexité polynomiale peuvent être les algorithmes les plus rapides pour certains problèmes est une question ouverte connue sous le problème P par rapport à NP . Il existe deux grandes classes de ces algorithmes:
  1. Algorithmes Monte Carlo renvoient une réponse correcte avec une grande probabilité. Par exemple , RP est la sous - classe de ces qui fonctionnent en temps polynomial .
  2. Las Vegas algorithmes renvoient toujours la bonne réponse, mais leur temps de fonctionnement est uniquement lié probabilistes, par exemple ZPP .
Réduction de la complexité
Cette technique consiste à résoudre un problème difficile en le transformant en un problème plus connu pour laquelle nous avons (espérons -le ) asymptotiquement optimaux algorithmes. L'objectif est de trouver un algorithme dont la réduction de la complexité n'est pas dominé par l'algorithme réduit résultant de. Par exemple, une sélection algorithme pour trouver la médiane dans une liste non triée implique d' abord trier la liste (la partie chère), puis en tirant l'élément central dans la liste triée (la partie pas cher). Cette technique est également connue sous le nom de transformer et de conquérir .
Retour suivi
Dans cette approche, plusieurs solutions sont construites progressivement abandonnées et lorsqu'il est déterminé qu'ils ne peuvent pas conduire à une solution complète valide.

Les problèmes d'optimisation

Pour des problèmes d'optimisation il existe une classification plus précise des algorithmes; un algorithme pour ces problèmes peut tomber dans une ou plusieurs des catégories décrites ci - dessus, ainsi que dans l' un des éléments suivants:

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és directement dans la production des solutions optimales. Il existe des algorithmes qui peuvent résoudre tout problème dans cette catégorie, comme le célèbre algorithme simplex . Les problèmes qui peuvent être résolus avec la programmation linéaire comprennent le problème de débit maximal pour les graphes dirigés. Si un problème exige en outre que l' un ou plusieurs des inconnues doit être un entier , alors il est classé dans la programmation entière . Un algorithme de programmation linéaire peut résoudre un tel problème si l' on peut prouver que toutes les restrictions pour les valeurs entières sont superficielles, à savoir les solutions satisfont à ces restrictions de toute façon. Dans le cas général, un algorithme spécialisé ou un algorithme qui trouve des solutions approximatives sont utilisées, en fonction de la difficulté du problème.
Programmation dynamique
Lorsqu'un problème montre des sous - structures optimales - ce qui signifie la solution à un problème peut être construit à partir des solutions optimales à sous - problèmes - et sous - problèmes qui se chevauchent , ce qui signifie les mêmes sous - problèmes sont utilisés pour résoudre de nombreux cas de problème, une approche plus rapide appelée programmation dynamique évite les solutions recalcul que ont déjà été calculés. Par exemple, l' algorithme de Floyd-Warshall , le plus court chemin vers un but d'un sommet dans un pondéré graphique peut être trouvé en utilisant le plus court chemin vers l'objectif de tous les sommets adjacents. La programmation dynamique et memoization vont de pair. La principale différence entre la programmation dynamique et diviser pour régner est que sous - problèmes sont plus ou moins indépendante à diviser pour régner, alors que sous - problèmes se chevauchent dans la programmation dynamique. La différence entre la programmation dynamique et récursion directe est mise en mémoire cache ou memoization des appels récursifs. Lorsque sont indépendants et sous - problèmes , il n'y a pas de répétition, memoization ne permet pas; par conséquent , la programmation dynamique n'est pas une solution pour tous les problèmes complexes. En utilisant memoization ou le maintien d' un tableau de sous - problèmes déjà résolus, la programmation dynamique réduit la nature exponentielle de nombreux problèmes à la complexité polynomiale.
Le procédé gourmand
Un algorithme glouton est similaire à un algorithme de programmation dynamique en ce qu'elle fonctionne en examinant substructures, dans ce cas , pas du problème , mais d'une solution donnée. Ces algorithmes commencent par une solution qui peut être donné ou ont été construits d'une manière, et l' améliorer en faisant de petites modifications. Pour certains problèmes , ils peuvent trouver la solution optimale pour d' autres , ils arrêtent à optima locaux , à savoir, à des solutions qui ne peuvent pas être améliorées par l'algorithme , mais 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. Huffman Arbre , Kruskal , Prim , Sollin sont algorithmes gloutons qui peuvent résoudre ce problème d'optimisation.
La méthode heuristique
Dans les problèmes d'optimisation , algorithmes heuristiques peuvent être utilisés pour trouver une solution proche de la solution optimale dans les cas où trouver la solution optimale est peu pratique. Ces algorithmes fonctionnent en se rapprochant et plus proche de la solution optimale à mesure qu'ils progressent. En principe, si elle est exécutée pour une quantité infinie de temps, ils trouveront la solution optimale. Leur mérite est qu'ils peuvent trouver une solution très proche de la solution optimale dans un temps relativement court. Ces algorithmes comprennent la recherche locale , recherche tabu , recuit simulé et 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 de tabu, sont déterministes. Quand 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 de la science a ses propres problèmes et a besoin d' algorithmes efficaces. Les problèmes liés dans un domaine sont souvent étudiés ensemble. Certaines classes d'exemple sont des algorithmes de recherche , des algorithmes de tri , fusion des algorithmes , des algorithmes numériques , des algorithmes de graphes , algorithmes de chaîne , des algorithmes géométriques de calcul , des algorithmes combinatoires , algorithmes médicaux , l' apprentissage automatique , la cryptographie , compression de données des algorithmes et des techniques d'analyse syntaxique .

Les champs ont tendance à se chevaucher, et les progrès de l'algorithme dans un domaine peuvent améliorer ceux des autres, parfois sans aucun rapport, les champs. Par exemple, la programmation dynamique a été inventé pour l'optimisation de la consommation des ressources dans l'industrie, mais est maintenant utilisé pour résoudre un large éventail de problèmes dans de nombreux domaines.

par la complexité

Les algorithmes peuvent être classés par la quantité de temps dont ils ont besoin pour compléter par rapport à leur taille d'entrée:

  • Constante de temps: si le temps nécessaire par l'algorithme est le même, quelle que soit la taille d'entrée. Par exemple , un accès à un réseau élément.
  • Le temps linéaire: si le temps est proportionnel à la taille de l'entrée. Par exemple, la traversée d'une liste.
  • Temps logarithmique: si le temps est une fonction logarithmique de la taille d'entrée. Par exemple , l' algorithme de recherche binaire .
  • Polynomiale: si le temps est une puissance de la taille d'entrée. Par exemple , le tri à bulles algorithme a une complexité quadratique du temps.
  • Exponential temps: si le temps est une fonction exponentielle de la taille d'entrée. Par exemple , la recherche force brute .

Certains problèmes peuvent avoir plusieurs algorithmes de complexité différente, alors que d'autres problèmes peuvent avoir aucun algorithme ou pas d'algorithmes efficaces connus. Il y a aussi des correspondances de certains problèmes à d'autres problèmes. En raison de cela, il a été jugé plus approprié pour classer les problèmes eux-mêmes au lieu des algorithmes en classes d'équivalence en fonction de la complexité des meilleurs algorithmes possibles pour eux.

algorithmes continus

L'adjectif « continu » lorsqu'il est appliqué sur le mot « algorithme » peut signifier:

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

Probleme juridique

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

En outre, certains algorithmes de chiffrement ont des restrictions à l'exportation (voir l' exportation de la cryptographie ).

Histoire: le développement de la notion de « algorithme »

Proche-Orient ancien

Les algorithmes ont été utilisés dans la Grèce antique. Deux exemples sont les Crible d'Eratosthène , qui a été décrit dans Introduction à Arithmétique par Nicomaque , et l' algorithme d' Euclide , qui a été décrit dans les Éléments d'Euclide (c. 300 BC). Tablettes d'argile babyloniennes décrivent et utilisent des procédures algorithmiques pour calculer le temps et le lieu des événements astronomiques importants.

symboles discrets et distincts

Tally marques : Pour garder une trace de leurs troupeaux, leurs sacs de céréales et leur argent les anciens utilisés récoltant: accumuler des pierres ou des marques griffées sur des bâtons ou de faire des symboles discrets dans l' argile. Grâce à l'utilisation de Babylone et égyptien des marques et symboles, éventuellement chiffres romains et le boulier évolué (Dilson, p. 16-41). Marques Tally apparaissent en bonne place dans le système numérique unaire arithmétique utilisé dans la machine de Turing et la machine post-Turing calculs.

La manipulation des symboles comme des « porteurs » pour placer les numéros: algèbre

Le travail des anciens géomètres grecs ( algorithme euclidienne ), le mathématicien indien Brahmagupta , et le mathématicien perse Al-Khwarizmi (de nom de laquelle les termes « algorisme » et « algorithme » sont dérivés), et les mathématiciens d' Europe occidentale ont abouti à Leibniz « s notion de ratiocinator de calcul (ca 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 précise les règles de manipulation des concepts logiques de la manière que l'algèbre ordinaire spécifie les règles de manipulation des chiffres.

dispositifs mécaniques avec des états discrets

L'horloge : Bolter attribue l'invention du à poids horloge comme « L'invention clé [de l' Europe au Moyen Age] », en particulier, l' échappement à bord qui nous fournit la tique et tac d'une horloge mécanique. « La machine automatique précise » conduit immédiatement à « mécanique des automates » à partir du 13ème siècle , et enfin à « machines de calcul » -le moteur de différence et les moteurs d' analyse de Charles Babbage et de la comtesse Ada Lovelace , milieu du 19e siècle. Lovelace est crédité de la première création d'un algorithme destiné à la transformation sur un ordinateur - moteur d' analyse de Babbage, le premier dispositif considéré comme un réel complet Turing ordinateur au lieu d'une calculatrice - et est parfois appelé « premier programmeur de l' histoire » en conséquence, si une mise en œuvre complète du second dispositif de Babbage ne se réaliserait que des décennies après sa vie.

Machines logiques 1870- Stanley Jevons « boulier logique » et de « machine logique » : Le problème technique était de réduire les équations booléennes lorsqu'ils sont présentés sous une forme similaire à ce qui est maintenant connu sous le nom des cartes Karnaugh . Jevons (1880) décrit d' abord un simple « Abacus » de « bouts de bois fournis avec des épingles, arrangé de sorte que toute partie ou la classe des cependant.. Plus récemment , des combinaisons [logiques] peuvent être cueillies mécaniquement., Je l' ai réduit la système à une forme complètement mécanique, et ont ainsi réalisé l'ensemble du processus indirect de l' inférence dans ce qu'on peut appeler une machine logique « Sa machine était équipée « certaines tiges en bois mobiles » et » au pied sont 21 touches comme celles de un piano [etc]... ". Avec cette machine , il pourrait analyser un « syllogisme ou tout autre argument logique simple ».

Cette machine a affiché en 1870 devant les membres de la Société royale. Une autre logicien John Venn , cependant, dans son 1881 Logique symbolique , un mauvais œil tourné à cet effort: « Je ne me estimer élevé de l'intérêt ou de l' importance de ce que l' on appelle parfois des machines logiques ... il ne me semble pas que les stratagèmes actuellement connus ou susceptibles d'être découverts méritent vraiment le nom des machines logiques »; voir plus à caractérisations algorithme . Mais ne pas être en reste , lui aussi , a présenté « un plan quelque peu analogue, je pense, à Prof. Jevon la abaque ... [Et] [a] gain, correspondant à la machine logique du professeur Jevons, le suivant peut être contrivance décrit. Je préfère l'appeler simplement une machine logigramme ... mais je suppose que cela pourrait faire très complètement tout ce qui peut être rationnellement attendre d'une machine logique ».

Métier à tisser Jacquard, Hollerith cartes perforées, télégraphie et de téléphonie , le relais électromécanique : Bell et Newell (1971) indiquent que le métier à tisser Jacquard (1801), précurseur de cartes Hollerith (cartes perforées, 1887), et « technologies de commutation téléphoniques » ont les racines d'un arbre menant au développement des premiers ordinateurs. Au milieu du 19ème siècle , le télégraphe , le précurseur du téléphone, était utilisé dans le monde entier, son encodage discret et distinguer des lettres comme des « points et de traits » un son commun. A la fin du 19ème siècle , le téléscripteur (années 1870 ca) était en cours d' utilisation, comme l'utilisation des cartes Hollerith dans le recensement des États - Unis 1890. Puis vint le téléscripteur (vers 1910) avec son utilisation-papier perforé de code Baudot sur bande.

Des réseaux de commutation téléphonique de électromécaniques relais (inventé 1835) est à l' origine du travail de George Stibitz (1937), l'inventeur de l'appareil numérique d' addition. Comme il a travaillé dans les laboratoires Bell, il a observé la « utilisation lourde » des calculateurs mécaniques à engrenages. « Il est rentré chez lui un soir en 1937 avec l' intention de tester son idée ... Lorsque le bricoler était terminée, Stibitz avait construit un dispositif d' addition binaire » .

Davis (2000) observe l'importance particulière du relais électromécanique (avec ses deux « états binaires » ouverts et fermés ):

Ce ne fut qu'avec le développement, à partir des années 1930, des calculateurs électromécaniques utilisant des relais électriques, que les machines ont été construites ayant la portée Babbage avait envisagé « .

Mathématiques au cours du 19ème s au milieu du 20e siècle

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

Mais Heijenoort donne Frege (1879) cette Kudos: est « peut - être le travail le plus important jamais écrit dans la logique ... dans laquelle nous voyons. » Frege « langage de formule », qui est un characterica lingua , une langue écrite avec des symboles spéciaux , « pour la pensée pure », qui est, sans fioritures rhétoriques ... construit à partir des symboles spécifiques qui sont manipulés selon des règles précises ». Le travail de Frege a encore été simplifiée et amplifiée par Alfred North Whitehead et Bertrand Russell dans leur Principia Mathematica (1910-1913).

Les paradoxes : En même temps , un certain nombre de paradoxes inquiétants est apparu dans la littérature, en particulier, le paradoxe Burali-Forti (1897), le paradoxe Russell (1902-1903), et Richard Paradox . Les considérations qui en découlent ont conduit à Kurt Gödel papier de (1931) -hê cite spécifiquement le paradoxe du menteur qui réduit complètement les règles de récursion aux chiffres.

Calculabilité efficace : Dans un effort pour résoudre le Entscheidungsproblem défini précisément par Hilbert en 1928, les mathématiciens d' abord mis sur le point de définir ce que l' on entend par « méthode efficace » ou « calcul efficace » ou « calculabilité efficace » (c. -à- un calcul qui succéderait ). Dans une succession rapide qui suit est apparu: Alonzo Church , Stephen Kleene et JB Rosser de -calcul λ une définition aiguisée de « récursion générale » du travail de Gödel agissant sur les suggestions de Jacques Herbrand (conférences voir Princeton Gödel de 1934) et par la suite par Kleene simplifications. La preuve de l' Eglise que le Entscheidungsproblem était impossible à résoudre, Emil après la définition de de calculabilité efficace en tant que travailleur sans réfléchir suite à une liste d'instructions à se déplacer à gauche ou à droite par une suite de chambres et bien qu'il soit marque ou la suppression d' un papier ou d' observer le papier et faire un oui aucune décision concernant l'instruction suivante. La preuve de ce que le Entscheidungsproblem d'Alan Turing était impossible à résoudre par l' utilisation de sa « a- la machine [Automatique-] » effet -dans presque identique à la « formulation » Post, J. Barkley Rosser définition de de « méthode efficace » en termes de « machine". SC Kleene proposition d'un précurseur de « la thèse de l' Eglise » qu'il a appelé « I thèse », et quelques années plus tard renommage sa thèse « Thèse de l' Eglise » de Kleene et de proposer « la thèse de Turing ».

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

Voici une remarquable coïncidence de deux hommes ne se connaissant pas, mais décrivant un processus d'hommes-as-ordinateurs travaillant sur des calculs et ils donnent des définitions pratiquement identiques.

Emil après (1936) a décrit les actions d'un « ordinateur » (être humain) comme suit:

» ... deux concepts sont impliqués: celle d'un espace de symbole dans lequel le travail menant de problème à répondre est à réaliser, et un fixe inaltérables ensemble de directions .

Son espace symbole serait

« Une suite infinie dans les deux sens des espaces ou des boîtes ... Le solveur de problème ou d'un travailleur est de déplacer et de travailler dans cet espace de symbole, étant capable d'être dans, et opérant dans mais fenêtre à la fois .... une boîte est d'admettre, mais deux conditions, à savoir, être vide ou non marqué, et ayant une marque unique, dites une course verticale.
« Une boîte est d'être choisi et appelé le point de départ. ... un problème spécifique doit être donnée sous forme symbolique par un nombre fini de boîtes [c.-à-INPUT] étant marqué par un accident vasculaire cérébral. De même, la réponse [à savoir SORTIE] doit être donnée sous forme symbolique d'une telle configuration de boîtes marquées ...
« Un ensemble de directions applicables à un problème général met en place un processus déterministe lorsqu'elle est appliquée à chaque problème spécifique. Ce processus se termine seulement en ce qui concerne le sens de type (C) [ à savoir, STOP] ». Voir plus à la machine Post-Turing
La statue d'Alan Turing à Bletchley Park

Alan Turing travail de précédait celle de Stibitz (1937); on ne sait pas si Stibitz connaissait les travaux de Turing. Le biographe de Turing croyait que l'utilisation turation d'un modèle semblable à la machine à écrire dérivé d'un intérêt jeune: « Alan avait rêvé d'inventer des machines à écrire comme un garçon, Mme turation avait une machine à écrire, et il aurait bien pu commencer par se demander ce que voulait dire en appelant une machine à écrire «mécanique ». Compte tenu de la prévalence du Code Morse et télégraphie, machines à téléscripteur, et téléscripteurs on peut conjecturer que tous étaient des influences.

Turation-son modèle de calcul est maintenant appelé une machine de Turing -entreprend, comme Post, une analyse d'un ordinateur humain qu'il Whittles à un ensemble simple des mouvements de base et « états d'esprit ». Mais il continue un peu plus loin et crée une machine comme un modèle de calcul des nombres.

« Computing se fait normalement en écrivant certains symboles sur papier. On peut supposer ce document est divisé en carrés comme le livre d'arithmétique d'un enfant ... Je suppose alors que le calcul est effectué sur le papier à une dimension, par exemple, sur une bande divisée en carrés. Je suppose aussi que le nombre de symboles qui peuvent être imprimés est fini ...
« Le comportement de l'ordinateur à tout moment est déterminé par les symboles qu'il observe, et son « état d'esprit » à ce moment-là. On peut supposer qu'il y ait un B lié au nombre de symboles ou carrés que l'ordinateur peut observer à un moment. S'il veut observer plus, il doit utiliser des observations successives. Nous supposons également que le nombre d'états d'esprit qui doit être prise en compte est fini ...
« Imaginons que les opérations effectuées par l'ordinateur pour être divisés en « opérations simples » qui sont si élémentaires qu'il est difficile de les imaginer plus divisés. »

La réduction de turation donne les éléments suivants:

« Les opérations simples doivent donc inclure:
« (A) Les changements du symbole sur l'une des places observées
« (B) Modification de l'une des places observés à une autre place à l'intérieur de carrés L de l'une des places précédemment observés.

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

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

Quelques années plus tard, a élargi son analyse Turing (thèse, définition) avec cette expression énergique de celui-ci:

« Une fonction est dite « effectivement calculable » si ses valeurs peuvent être trouvées par un procédé purement mécanique. Bien qu'il soit assez facile d'obtenir une compréhension intuitive de cette idée, il est néanmoins souhaitable d'avoir un peu plus précis, la définition exprimable mathématique ... [il parle de l'histoire de la définition à peu près tel que présenté ci-dessus par rapport à Gödel, Herbrand, Kleene, Eglise, Turing et post]... Nous pouvons prendre cette déclaration littéralement, la compréhension par un processus purement mécanique pourrait être réalisée par une machine. Il est possible de donner une description mathématique, dans une certaine forme normale, des structures de ces machines. le développement de ces idées conduit à la définition d'une fonction calculable de l'auteur, et une identification calculabilité † avec calculabilité efficace....
« † Nous utiliserons l'expression « fonction chiffrable » pour désigner une fonction calculable par une machine, et nous laissons « effectivement calculable » font référence à l'idée intuitive sans identification particulière avec l'une de ces définitions ».

JB Rosser (1939) et SC Kleene (1943)

J. Barkley Rosser définit une « méthode [mathématique] efficace » de la manière suivante (italicization ajouté):

« Méthode efficace» est utilisé ici dans le sens assez particulier d'une méthode chaque étape qui est déterminée avec précision et qui est certain de produire la réponse dans un nombre fini d'étapes. Avec ce sens particulier, trois définitions précises ont été données à ce jour [sa note n ° 5, voir la discussion immédiatement ci - dessous]. Le plus simple à l'autre ( en raison de post et Turing) dit essentiellement que. une méthode efficace de résoudre certains types de problèmes existe si l' on peut construire une machine qui sera ensuite résoudre tout problème de l'ensemble sans intervention humaine au - delà de l' insertion de la question et (plus tard) lire la réponse les trois définitions sont équivalentes, donc il n'a pas d' importance que l' on sert.. de plus, le fait que tous les trois sont équivalents est un argument très fort pour l'exactitude de quiconque « . (Rosser 1939: 225-6)

Note no 5 de Rosser fait référence au travail de (1) Eglise et Kleene et leur définition de λ-définissabilité, dans l'usage particulier de l' Eglise dans son Un problème de irrémédiables Nombre élémentaire Théorie (1936); (2) Herbrand et Gödel et leur utilisation de la récursivité dans l'utilisation particulière Gödel dans son fameux papier Sur Formellement indécidables Les propositions de Principia Mathematica et des systèmes connexes I (1931); et (3) Post (1936) et Turing (1936-1937) dans leur mécanisme modèles de calcul.

Stephen C. Kleene défini comme son désormais célèbre « Thèse I » connu comme la Thèse de Church . Mais il a fait cela dans le contexte suivant (dans l' original gras):

« 12. théories algorithmiques ... Dans la mise en place d' une théorie algorithmique complète, ce que nous faisons est de décrire une procédure, performable pour chaque ensemble de valeurs des variables indépendantes, la procédure qui se termine nécessairement et de telle sorte que le résultat que nous pouvons lire une réponse définitive, « oui » ou « non » à la question, « est la valeur sous - jacente vrai? » »(Kleene 1943: 273)

Histoire après 1950

Un certain nombre d'efforts ont été dirigés vers une plus grande amélioration de la définition de « algorithme », et l' activité est en cours en raison de problèmes environnants, en particulier, les fondations des mathématiques ( en particulier la thèse Church-Turing ) et la philosophie de l' esprit ( en particulier les arguments A propos de l' intelligence artificielle ). Pour plus, voir caractérisations algorithme .

Voir également

Remarques

Bibliographie

  • Axt, P (1959). « Sur une Subrecursive Hiérarchie et primitives récursives degrés ». Transactions de la Société mathématique américaine . 92 : 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 ; Gurevich, Yuri (2003). "Algorithmes: A Quest for Définitions absolues" (PDF) . Bulletin de l' Association européenne pour la science théorique informatique . 81 . Comprend une excellente bibliographie de 56 références.
  • Bolter, David J. (1984). L'homme de turation: la culture occidentale à l'ère informatique (1984 ed.). L'Université de Caroline du Nord Press, Chapel Hill NC. ISBN  0-8078-1564-0 ., ISBN  0-8078-4108-0 PBK.
  • Boolos, George ; Jeffrey, Richard (1999) [1974]. Calculabilité et logique (4e éd.). Cambridge University Press, Londres. ISBN  0-521-20402-X .: Cf. Chapitre 3 machines de Turing où ils discutent « certains ensembles dénombrables pas efficacement (mécaniquement) dénombrable ».
  • Burgin, Mark (2004). Les algorithmes Super-récursives . Springer. ISBN  978-0-387-95569-8 .
  • Campagnolo, ML, Moore, C. , et Costa, JF (2000) Une caractérisation analogique des fonctions subrecursive. Dans Proc. de la 4e Conférence sur les nombres réels et ordinateurs , Université d' Odense, pp. 91-109
  • Eglise, Alonzo (1936a). « Un problème de irrémédiables Nombre élémentaire Théorie ». The American Journal of mathématiques . 58 (2): 345-363. doi : 10,2307 / 2371045 . JSTOR  2371045 .Reproduit dans l'indécidable , p. 89ff. La première expression de la « thèse de l' Église ». Voir en particulier la page 100 ( Le indécidable ) où il définit la notion de « calculabilité efficace » en termes de « un algorithme », et il utilise le mot « fin », etc.
  • Eglise, Alonzo (1936b). « Une note sur la Entscheidungsproblem ». Le Journal de la logique symbolique . 1 (1): 40-41. doi : 10,2307 / 2269326 . JSTOR  2269326 .Eglise, Alonzo (1936). « Correction à une note sur la Entscheidungsproblem ». Le Journal de la logique symbolique . 1 (3): 101-102. doi : 10,2307 / 2269030 . JSTOR  2269030 .Reproduit dans l'indécidable , p. 110ff. Eglise montre que le Entscheidungsproblem est dans environ 3 unsolvable pages de texte et 3 pages de notes.
  • Daffa », Ali Abdullah al (1977). La contribution musulmane aux mathématiques . Londres: Croom Helm. ISBN  0-85664-464-1 .
  • Davis, Martin (1965). Le indécidable: Documents de base sur indécidables, des problèmes insolubles propositions et fonctions calculables . New York: Raven Press. ISBN  0-486-43228-9 .Davis donne le commentaire avant chaque article. Documents de Gödel , Alonzo Church , Turing , Rosser , Kleene et Emil Poste sont inclus; ceux qui sont cités dans l'article sont énumérés ici par le nom de l' auteur.
  • Davis, Martin (2000). Moteurs de logique: Mathématiciens et l'origine de l'ordinateur . New York: WW Nortion. ISBN  0-393-32229-7 .Davis offre des informations biographiques de Leibniz , Boole , Frege , Cantor , Hilbert , Gödel et Turing avec von Neumann comme le méchant show-vol. Très courtes biographies de Joseph-Marie Jacquard , Babbage , Ada Lovelace , Claude Shannon , Howard Aiken , etc.
  •  Cet article incorpore la matière de domaine public  du  NIST document:  noir, Paul E. "algorithme" . Dictionnaire des algorithmes et structures de données .
  • Dean, Tim (2012). « L' évolution et la diversité morale ». Baltic Annuaire international de Cognition, logique et de la communication . 7 .
  • Dennett, Daniel (1995). Idée dangereuse de Darwin . New York: Touchstone / Simon & Schuster. ISBN  0-684-80290-2 .
  • Dilson, Jesse (2007). L'Abacus (ed (1968,1994).). Press, NY St. Martin. ISBN  0-312-10409-X ., ISBN  0-312-10409-X (PBK).
  • Yuri Gurevich , Machines séquentielle Etat Résumé Capturer séquentielle Algorithmes , ACM Transactions on Computational Logic, vol 1, no 1 (Juillet 2000), pages 77-111. Comprend une bibliographie de 33 sources.
  • van Heijenoort, Jean (2001). De Frege à Gödel, A Source Book dans la logique mathématique, 1879-1931 ((1967) éd.). Harvard University Press, Cambridge, MA. ISBN  0-674-32449-8 ., 3e édition 1976 [?], ISBN  0-674-32449-8 (pbk.)
  • Hodges, Andrew (1983). Alan Turing: The Enigma . New York: Simon et Schuster . ISBN  0-671-49207-1 ., ISBN  0-671-49207-1 . Cf. Chapitre « L'Esprit de Vérité » pour une histoire menant à, et une discussion, sa preuve.
  • Kleene, Stephen C. (1936). « Fonctions générales récursive des nombres naturels » . Mathematische Annalen . 112 (5): 727-742. doi : 10.1007 / BF01565439 .Présenté à l'American Mathematical Society, Septembre 1935. Reproduit dans l'indécidable , p. 237ff. La définition de kleene de « récursion général » (connu maintenant comme mu-récursion) a été utilisé par l' Église dans son article 1935 Un problème insoluble de Numéro élémentaire théorie qui a prouvé le « problème de la décision » d'être « indécidable » (c. -à- un résultat négatif).
  • Kleene, Stephen C. (1943). « Récursive prédicats et quantificateurs ». Transactions American Mathematical Society . 54 (1): 41-73. doi : 10,2307 / 1990131 . JSTOR  1990131 .Reproduit dans l'indécidable , p. 255ff. Kleene affiné sa définition de « récursion générale » et a procédé dans son chapitre « 12. théories algorithmiques » à poser « Thèse I » (p 274.); il répétera plus tard cette thèse (en 1952 Kleene: 300) et nommez - le « Thèse de l' Eglise » (1952 Kleene: 317) (c. -à- la thèse Eglise ).
  • Kleene, Stephen C. (1991) [1952]. Introduction à Metamathematics (ed dixième.). North-Holland Publishing Company. ISBN  0-7204-2103-9 . Excellente accessible, source de référence lisible pour « fondations » mathématiques.
  • Knuth, Donald (1997). Les algorithmes fondamentaux, troisième édition . Reading, Massachusetts: Addison-Wesley. ISBN  0-201-89683-4 .
  • Knuth, Donald (1969). Volume 2 / Seminumerical algorithmes, L'art de la programmation informatique Première édition . Reading, Massachusetts: Addison-Wesley.
  • Kosovsky, NK Éléments de logique mathématique et son application à la théorie des algorithmes Subrecursive , LSU Publ., Leningrad, 1981
  • Kowalski, Robert (1979). "Algorithme = Logic + Control". Communications de l'ACM . 22 (7): 424-436. doi : 10,1145 / 359131,359136 .
  • Markov AA (1954) Théorie des algorithmes . [Traduit par Jacques J. Schorr-Kon et le personnel PST] Enseigne d' imprimeur de Moscou, Académie des Sciences de l'URSS, 1954 [ie, Jérusalem, Israël Programme pour les traductions scientifiques, 1961; disponible auprès du Bureau des services techniques, US Department of Commerce, Washington] Description de 444 p. 28 cm. Tp ajouté en traduction russe des travaux de l'Institut de mathématiques, Académie des sciences de l'URSS, v 42. Titre original:. Teoriya algerifmov. [Bibliothèque QA248.M2943 Dartmouth College. US Department of Commerce, Bureau des services techniques, le numéro OTS 60-51085.]
  • Minsky, Marvin (1967). Calcul: Machines fini et infini (première éd.). Prentice-Hall, Englewood Cliffs, NJ. ISBN  0-13-165449-7 .Minsky élargit son « ... idée d'un algorithme d' une procédure efficace ... » au chapitre 5.1 calculabilité, des procédures efficaces et algorithmes. Infinies machines.
  • Post, Emil (1936). "Processus combinatoires finis, Formulation I". Le Journal de la logique symbolique . 1 (3): 103-105. doi : 10,2307 / 2269031 . JSTOR  2269031 .Reproduit dans l'indécidable , p. 289ff. Poster définit un processus simple comme algorithmiques d'un homme d' écriture des marques ou des marques d' effacer et d' aller de case en case et éventuellement arrêter, comme il suit une liste d'instructions simples. Ceci est cité par Kleene comme une source de son « I thèse », le soi-disant Thèse de Church .
  • Rogers, Jr., Hartley (1987). Théorie des fonctions récursives et efficace calculabilité . Le MIT Press. ISBN  0-262-68052-1 .
  • Rosser, JB (1939). « Une Exposition informelle des preuves de théorème de Godel et le théorème de l' Eglise ». Journal of Logic symbolique . 4 (2): 53-60. doi : 10,2307 / 2269059 . JSTOR  2269059 .Reproduit dans l'indécidable , p. 223ff. Là est la célèbre définition de Rosser de « méthode efficace »: » ... une méthode chaque étape qui est précisément prédéterminée et qui est certaine de produire la réponse dans un nombre fini d'étapes ... une machine qui sera ensuite résoudre tout problème de l'ensemble sans intervention humaine au - delà de l' insertion de la question et (plus tard) lire la réponse »(p. 225-226, l'indécidable )
  • Santos-Lang, Christopher (2014). « L' écologie morale approches de l' éthique Machine ». Dans van Rysewyk, Simon; Pontier, Matthijs. Machine éthique médicale (PDF) . Suisse: Springer. pp. 111-127. doi : 10.1007 / 978-3-319-08108-3_8 .
  • Scott, Michael L. (2009). Langage de programmation Pragmatique (3e éd.). Morgan Kaufmann Publishers / Elsevier. ISBN  978-0-12-374514-9 .
  • Sipser, Michael (2006). Introduction à la théorie de calcul . PWS Publishing Company. ISBN  0-534-94728-X .
  • Sobre, Elliott; Wilson, David Sloan (1998). Autres: Unto L'évolution et la psychologie du comportement Unselfish . Cambridge: Harvard University Press.
  • Stone, Harold S. (1972). Introduction à l' informatique et organisation des structures de données (1972 ed.). McGraw-Hill, New York. ISBN  0-07-061726-0 .Cf. en particulier le premier chapitre intitulé: Les algorithmes, les machines de Turing et programmes . Sa définition informelle succincte: « ... toute séquence d'instructions qui peuvent être respectées par un robot, est appelé un algorithme » (p . 4).
  • Tausworthe, Robert C (1977). Développement de logiciels informatiques normalisés Partie 1 Méthodes . Englewood Cliffs NJ: Prentice-Hall, Inc. ISBN  0-13-842195-1 .
  • Turation, Alan M. (1936-1937). « Le nombres calculables, avec une application au Entscheidungsproblem ». Compte rendu de la London Mathematical Society . Série 2. 42 : 230-265. doi : 10,1112 / MPJS / s2-42.1.230 .. Corrections, ibid, vol. 43 (1937) pp. 544-546. Reproduit dans l'indécidable , p. 116ff. Papier célèbre turation complété comme mémoire de maîtrise tout au College de Cambridge au Royaume - Uni King.
  • Turation, Alan M. (1939). « Les systèmes de logique basée sur Ordinaux ». Compte rendu de la London Mathematical Society . 45 : 161-228. doi : 10,1112 / MPJS / s2-45.1.161 .Reproduit dans l'indécidable , p. 155ff. Le papier de Turing qui a défini « l'oracle » était sa thèse de doctorat à Princeton en Etats - Unis.
  • États-Unis Office des brevets et des marques (2006), 2106,02 **> Les algorithmes mathématiques: 2100 Brevetabilité , Manuel de procédure d' examen des brevets (MPEP). Dernière révision Août 2006

Pour en savoir plus

Liens externes

référentiels de l'algorithme
Notes de lecture