Worldlex Wiki Note G est un algorithme informatique traditionnellement attribué à Ada Lovelace qui a été conçu pour calculer les nombres de Bernoulli en utilisant la machine analytique hypothétique conçue par Charles Babbage .
L'algorithme constituait la dernière note d'une série étiquetée de « A » à « G », utilisée comme aide visuelle pour accompagner la traduction anglaise par Lovelace de la transcription française de Luigi Menabrea (1842) de l'unique conférence de Charles Babbage sur la machine analytique. Sa traduction, ainsi que ses notes substantielles sur les possibilités de la machine analytique, furent publiées en 1843.
Dans ses mémoires de 1864, Babbage évoque la création des différentes notes avec Lovelace, notamment la note « Sol ». Il lui fournit les formules mathématiques pour le calcul des nombres de Bernoulli, qu’Ada convertit en un tableau d’instructions détaillé pour la machine analytique ; elle lui signale également un bug :
Nous avons discuté ensemble des différentes illustrations à introduire : j’en ai suggéré plusieurs, mais le choix lui revenait entièrement. Il en fut de même pour la résolution algébrique des différents problèmes, à l’exception, bien sûr, de celle relative aux nombres de Bernoulli , que j’avais proposée de faire pour épargner cette peine à Lady Lovelace. Elle me la renvoya pour correction, ayant décelé une grave erreur que j’avais commise.
— Charles Babbage, Passages de la vie d'un philosophe (1864)
Des historiens comme Allan G. Bromley ont relevé plusieurs dizaines de programmes d'exemple préparés par Babbage entre 1837 et 1840 (tous bien antérieurs aux notes explicatives), bien qu'ils n'aient jamais été publiés et qu'ils soient nettement plus simples , ce qui a conduit, dans la culture populaire, à considérer la Note G comme le premier algorithme spécifiquement conçu pour un ordinateur et Lovelace comme le premier programmeur informatique .
Le programme décrit dans la note G n'a pas été testé du vivant de Babbage ni de Lovelace, car la machine analytique n'a jamais été construite. À l'ère moderne, l'algorithme a été testé à l'aide de méthodes de calcul modernes et il s'est avéré qu'il contenait un bogue logiciel dû à l'inversion de deux variables lors d'une division.
En 1840, Charles Babbage fut invité à donner un séminaire à Turin sur sa machine analytique , la seule explication publique qu'il en ait jamais donnée . Durant la conférence de Babbage, le mathématicien Luigi Menabrea rédigea une description de la machine en français . Un ami de Babbage, Charles Wheatstone , suggéra à Lovelace de traduire cette description afin d'y contribuer Babbage lui proposa alors d'enrichir sa traduction d'appendices, qu'elle compila à la fin sous la forme de sept « notes » intitulées AG. Sa traduction fut publiée en août 1843 dans les Mémoires scientifiques de Taylor [ où Lovelace signait « AAL ». Dans ces notes, Lovelace décrit les capacités de la machine analytique de Babbage si elle devait être utilisée pour le calcul, esquissant un plan plus ambitieux pour la machine que celui que Babbage lui-même avait conçu.
Les notes de Lovelace pour l'article étaient trois fois plus longues que l'article lui-même. Dans les premières notes, elle explore des perspectives au-delà des ambitions numériques que Babbage nourrissait pour la machine, et suggère que celle-ci pourrait tirer parti du calcul pour aborder les domaines de la musique, du graphisme, et du langage.
la machine à différences de Babbage antérieure et compare son fonctionnement à celui de la machine Jacquard [ puisqu'elle utilisait des cartes perforées binaires pour représenter le langage machine . Dans la note C, ce point est approfondi par le fait que la machine peut effectuer des actions simultanées et itérées , garantissant ainsi que toute carte ou ensemble de cartes peut être utilisé plusieurs fois pour résoudre un même problème , anticipant de fait les méthodes modernes de contrôle de flux et de bouclage . Ces idées ont atteint leur apogée dans la dernière note, G, où Lovelace s'est efforcée de démontrer un exemple de calcul .La note G n'utilisait que les quatre opérations arithmétiques : addition, soustraction, multiplication et division, conformément à la vision de Babbage :
la variable ) et un numéro d'indice indiquant la colonne à laquelle il est fait référence.Fonction
L'algorithme utilisait une équation récursive pour calculer les nombres de Bernoulli, dans laquelle il utilisait les valeurs précédentes d'une équation pour générer la suivante. La méthode fonctionnait ainsi :
où est un coefficient binomial ,
Les nombres de Bernoulli peuvent être calculés de nombreuses manières , mais l'auteur a délibérément choisi une méthode élaborée afin de démontrer la puissance de la machine. Dans la Note G, Lovelace déclare : « Nous terminerons ces Notes en détaillant les étapes par lesquelles la machine pourrait calculer les nombres de Bernoulli, ce qui constitue (sous la forme que nous allons en donner) un exemple assez complexe de ses puissances. » L'algorithme particulier utilisé dans la Note G génère le huitième nombre de Bernoulli (noté , car il commence par .)
Notation
Le tableau de l'algorithme organise chaque commande dans l'ordre. Chaque commande désigne une opération effectuée sur deux termes. La deuxième colonne indique uniquement l'opérateur utilisé. Les variables sont notées « [c] », représente le nombre de valeurs différentes auxquelles la variable a été affectée, et l'indice représente son numéro d'affectation, c'est-à-dire la variable elle-même. (Par exemple, « [c] » fait référence à la deuxième affectation de la variable numéro 4. Les variables non définies jusqu'à présent ont un exposant de 0.) Les variables sont numérotées à partir de 0. La troisième colonne indique précisément à l'ordinateur la commande exécutée (par exemple, à la ligne 1, la commande exécutée est « [c] » : la première itération de la variable 2 est multipliée par la première itération de la variable 3). Elle ne comporte qu'une seule opération entre deux termes par ligne. La colonne 4, « Variables recevant les résultats », indique où stocker le résultat de l'opération de la colonne 3. Ainsi, l'exposant des variables de cette colonne est incrémenté de 1 à chaque affectation. (par exemple, à la ligne 1, le résultat de est affecté aux variables , , et .)
La colonne 5 indique si l'une des variables utilisées dans l'exécution de la commande a été modifiée. Encadrées par des accolades, deux lignes par commande placent la variable d'origine à gauche du signe égal et la nouvelle variable à droite ; autrement dit, si la variable a été modifiée, son exposant est incrémenté de un, sinon il reste inchangé. (Par exemple, la ligne trois affecte le résultat de la deuxième itération de la variable , et la cinquième colonne le reflète en indiquant ;
Dans la colonne 6, « Résultats », la valeur exacte de la variable de la colonne 4 est affichée, calculée à partir des valeurs des deux termes précédemment attribués. (Par exemple, à la ligne 1, la variable a été initialement initialisée à , et la variable a a été initialisée à . Par conséquent, , en notation mathématique .) Cette colonne n'est apparemment pas calculée par le moteur et semble plutôt servir à améliorer la clarté et la compréhension des étapes du programme. (Par exemple, à la ligne 5, une fraction est divisée par deux, ce qui est noté comme une multiplication par un demi, probablement par souci de cohérence et pour simplifier la mise en forme d'une fraction imbriquée.) Elle utilise également une notation de variables distincte, en dehors du programme : les variables et , qui sont multipliées successivement pour obtenir la valeur finale, , ainsi :
De plus, chaque colonne successive affiche les valeurs d'une variable donnée au fil du temps. Chaque fois qu'une variable change ou que sa valeur devient pertinente du fait de sa présence comme terme de la commande courante, sa valeur est indiquée ou réaffirmée dans sa colonne respective. Sinon, elle est marquée de points de suspension pour indiquer son inutilité. Ceci imite vraisemblablement le besoin de l'ordinateur de ne recevoir que les informations pertinentes, permettant ainsi de suivre la valeur d'une variable pendant l' analyse syntaxique du programme .
Méthode
Le programme cherchait à calculer ce que l'on appelle par convention moderne le huitième nombre de Bernoulli, noté , car Lovelace commence à compter à partir de .
Erreur
Dans l'opération 4, la division censée avoir lieu est « », à stocker dans la variable . Cependant, le « Relevé de résultats » indique que la division devrait être :
En réalité, la division est inversée ; il s'agit de la deuxième itération de , comme on peut le constater dans l'opération 2. De même, il s'agit de la deuxième itération de , comme on peut le constater dans l'opération 3. Par conséquent, l'opération 4 ne devrait pas être , mais plutôt . Ce bug signifie que si le moteur devait exécuter cet algorithme dans cet état, il ne parviendrait pas à générer correctement les nombres de Bernoulli et trouverait que sa valeur cible finale
implémentations modernes
Le programme de Lovelace peut être implémenté dans un langage de programmation moderne , mais en raison de l'erreur mentionnée ci-dessus, sa transcription exacte renverrait une valeur finale incorrecte . Le programme original, généralisé en pseudocode, est le suivant :
0: V[6] = V[6] - V[1] V[7] = V[1] + V[7] V[8] = V[6] / V[7] V[11] = V[8] * V[11] V[6] = V[6] - V[1] V[7] = V[1] + V[7] V[9] = V[6] / V[7] V[11] = V[9] / V[11] V[12] = V[22] * V[11] V[13] = V[12] + V[13] V[10] = V[10] - V[1] V[24] = V[13] + V[24] V[3] = V[1] + V[3] " V[1] = 1 V[2] = 2 V[3] = n /* n = 4 dans le programme de Lovelace. */ /* Commencer */ V[4], V[5], V[6] = V[2] * V[3] V[4] = V[4] - V[1] V[5] = V[5] + V[1] V[11] = V[5] / V[4] V[11] = V[11] / V[2] V[13] = V[13] - V[11] /* Les variables sont initialement nulles, cf. ci-dessous. */ V[10] = V[3] - V[1] V[7] = V[2] + V[7] V[11] = V[6] / V[7] V[12] = V[21] * V[11] V[13] = V[12] + V[13] V[10] = V[10] - V[1] TANT QUE V[10] > 0 : V[6] = V[6] - V[1] V[7] = V[1] + V[7] V[8] = V[6] / V[7] V[11] = V[8] * V[11] V[6] = V[6] - V[1] V[7] = V[1] + V[7] V[9] = V[6] / V[7] V[11] = V[9] / V[11] V[12] = V[22] * V[11] V[13] = V[12] + V[13] V[10] = V[10] - V[1] V[24] = V[13] + V[24] V[3] = V[1] + V[3]
L'implémentation en pseudocode met en évidence le fait que les langages informatiques définissent les variables sur une pile , ce qui évite d'avoir à suivre et à spécifier l'itération courante d'une variable. De plus, le programme de Lovelace n'autorisait la définition de variables qu'en effectuant une addition , une soustraction , une multiplication ou une division sur deux termes qui étaient des variables préalablement définies. La syntaxe moderne permettrait d'effectuer chaque calcul de manière plus concise. Cette restriction apparaît dès l'opération 6 ( ). Ici, Lovelace définit une variable jusque-là indéfinie ( ) par elle-même, supposant ainsi que toutes les variables indéfinies sont automatiquement égales à 0, ce qui, dans la plupart des langages de programmation modernes, générerait une erreur. Elle voulait en réalité utiliser « », mais s'était contrainte à n'utiliser que des variables comme termes. De même, dans l'opération 8 ( ), la notation stricte de l'arithmétique à deux termes devient complexe, car pour définir comme 2, Lovelace lui assigne sa valeur (0) plus (2). C'est à cause de cette notation restrictive que est définie ainsi.