Baccalauréat NSI (Numérique et Sciences Informatiques)

Les algorithmes avant les machines

Un algorithme est une suite finie et précise d'opérations élémentaires qui transforme des données en un résultat. La notion est bien plus ancienne que les ordinateurs. L'algorithme d'Euclide, qui calcule le plus grand commun diviseur de deux entiers par des divisions successives, date de l'Antiquité grecque (vers 300 av. J.-C.). Le mot « algorithme » vient du nom du mathématicien Al-Khwârizmî (IXe siècle), dont les traités de calcul décimal et d'algèbre ont transmis des méthodes de calcul écrites sous forme de procédures.

Pendant des siècles, ces procédures sont exécutées par des humains avec du papier, un boulier ou des tables numériques. Les machines n'apparaissent que lorsqu'on sait mécaniser l'exécution d'opérations élémentaires.

Les premières machines à calculer (XVIIe siècle)

Ces machines sont câblées pour un seul type de calcul : elles ne se programment pas. Le binaire de Leibniz, lui, prépare ce qui deviendra le codage universel des données dans les machines électroniques.

Les machines programmables du XIXe siècle

En 1801, Joseph-Marie Jacquard met au point un métier à tisser dont le motif est commandé par des cartes perforées. C'est l'une des premières fois qu'une séquence d'instructions est stockée sur un support extérieur à la machine, et que l'on peut changer le travail de la machine sans la reconstruire.

Charles Babbage conçoit à partir des années 1830 la machine analytique, qui n'a jamais été achevée : elle comprend une unité de calcul, une mémoire et une commande par cartes perforées, soit la même organisation générale que les ordinateurs actuels. Ada Lovelace, qui l'a décrite dans des notes publiées en 1843, y a détaillé un programme de calcul des nombres de Bernoulli, ce qui lui vaut d'être considérée comme l'une des premières personnes à avoir écrit un programme.

La logique se mathématise à la même époque. En 1854, George Boole publie Les Lois de la pensée, où il construit une algèbre sur les valeurs « vrai » et « faux » avec les opérations de conjonction, de disjonction et de négation : c'est l'algèbre de Boole. Elle deviendra la base des circuits logiques.

1936 : la machine universelle

Les années 1930 voient naître la théorie de la calculabilité. La question posée est de savoir ce qu'il est possible de calculer par une procédure mécanique, et avec quel modèle le dire précisément.

En 1936, Alan Turing décrit une machine abstraite, la machine de Turing, composée d'un ruban infini de cases, d'une tête de lecture et d'écriture, d'un état interne et d'une table de transitions. Il montre qu'il existe une machine de Turing universelle, capable de simuler n'importe quelle autre machine de Turing à partir de sa description placée sur le ruban. Cette idée est décisive : une même machine peut exécuter tous les algorithmes, à condition qu'on lui fournisse le programme comme une donnée.

Dans les mêmes mois, Alonzo Church propose un autre modèle, le lambda-calcul, fondé sur les fonctions. Les deux modèles calculent exactement les mêmes fonctions, et il en va de même pour tous les modèles proposés depuis. La thèse de Church-Turing affirme que tout ce qui est calculable par une procédure effective l'est par une machine de Turing. Ce n'est pas un théorème, puisque la notion de procédure effective est intuitive, mais aucun contre-exemple n'a été trouvé.

Turing montre aussi, dans ce même article, qu'il existe des problèmes qu'aucun algorithme ne peut résoudre : le problème de l'arrêt en est l'exemple (voir la note sur la calculabilité et la décidabilité).

1936 est ainsi la date où les notions de machine, d'algorithme, de langage et d'information sont pensées ensemble.

Information et architecture des machines

L'architecture de von Neumann est celle de presque tous les ordinateurs. Son principe, le programme enregistré en mémoire comme n'importe quelle autre donnée, est la réalisation concrète de la machine universelle de Turing.

Premiers ordinateurs

Les premiers calculateurs électroniques apparaissent au milieu des années 1940 (l'ENIAC est mis en service en 1945, mais se programme en recâblant). En 1948, la machine de l'université de Manchester exécute le premier programme enregistré en mémoire. L'EDSAC, à Cambridge, suit en 1949 et sert à des calculs scientifiques réguliers. Ces machines occupent des salles entières, consomment beaucoup d'énergie et restent réservées aux laboratoires et aux armées.