Précédent Remonter Suivant

Chapitre 1  Fondations


1.1  Calcul automatique

Le propos de cet ouvrage est d'apprendre à programmer les ordinateurs. N'importe quel ordinateur, puisqu'ils sont tous équivalents, et pour tout programme, puisque le propre d'un ordinateur est l'universalité, c'est-à-dire la capacité à traiter tous les problèmes traitables effectivement.

Avant de commencer, il convient de faire un tour d'horizon sommaire des questions mises en jeu par ces premiers mots.

L'informatique moderne est née de la recherche entreprise au début du XXème siècle par Bertrand Russel et Alfred North Whitehead sous le titre Principia Mathematica pour constituer les mathématiques en un système formel où toute proposition pourrait être démontrée par un calcul logique. David Hilbert et Kurt Gödel accomplissent des pas décisifs dans l'exploration de ce programme. En 1931 Gödel démontre que pour tout système formel suffisant pour représenter l'arithmétique il existe des propriétés vraies dont on ne peut démontrer la vérité ni la fausseté avec les règles du système lui-même. Le théorème de Gödel ruine le rêve de réunir les mathématiques dans un système déductif parfaitement cohérent, mais de l'effervescence intellectuelle autour du projet des Principia vont sortir les idées fondatrices de l'informatique.

En 1936 Alan Turing, à la suite de Gödel, s'attaque à un problème de décidabilité : un système est décidable s'il existe une procédure effective pour distinguer les propositions démontrables des autres. Pour définir plus rigoureusement la notion de procédure effective, Turing élabore un modèle d'automate, appelé par la suite machine de Turing, qui lui permet de préciser la notion d'exécution d'un algorithmealgorithme.

Inventer des procédures effectives (des algorithmes) consiste à déterminer un enchaînement d'opérations élémentaires qui exécuteront les calculs nécessaires à la solution de problèmes pour lesquels existent des solutions calculables (il y a des problèmes sans solution et des solutions incalculables). Ce livre expose l'art de réaliser des algorithmes. Turing montre que son modèle de calcul est universel, c'est-à-dire que toutes les machines de Turing sont équivalentes. Il formule la thèse selon laquelle tout algorithme est calculable par une machine de Turing. Ces idées fondent la théorie de la programmation des ordinateurs. Il revient à von Neumann de concevoir en 1945 l'architecture générale des appareils concrets qui vont réaliser les calculs selon le modèle de Turing, architecture si élégante que les ordinateurs d'aujourd'hui sont encore construits, pour l'essentiel, selon ses principes.


1.2  Modèle de l'ordinateur

L'architecture que von Neumann propose pour l'ordinateur est la suivante :


Figure 1.1 : Structure de l'ordinateur.


Les unités de contrôle1, arithmétique et d'entrée-sortie constituent à elles trois l'unité centrale, ou le processeur de l'ordinateur. Le processeur est constitué de circuits électroniques qui peuvent exécuter des actions. L'ensemble des actions « câblées » dans le processeur constitue le jeu d'instructions du processeur et détermine le langage élémentaire de son utilisation, appelé « langage machine ».

Le rôle de l'unité de contrôle consiste à permettre le déclenchement de l'action (l'instruction) voulue au moment voulu. Cette instruction peut appartenir à l'unité arithmétique, à l'unité d'entrée-sortie ou à l'unité de contrôle elle-même. Une instruction peut en outre consulter le contenu de la mémoire (la « lire ») ou modifier le contenu de la mémoire (y « écrire »). De façon générale, une action consiste soit à consulter ou à modifier l'état de la mémoire ou d'un des registres A ou R (qui sont des éléments de mémoire spéciaux incorporés à l'unité centrale), soit à déclencher une opération d'entrée-sortie (communication avec le monde extérieur et notamment l'utilisateur humain).

Comment indique-t-on à l'unité de contrôle le « moment voulu » pour déclencher telle ou telle action ? C'est écrit dans le texte d'un programme. Où est le programme ? Dans la mémoire.

La mémoire est constituée d'éléments susceptibles de prendre des états. Un élément de base de la mémoire peut prendre deux états distincts et peut servir à représenter une donnée élémentaire, ou bit (binary digit, chiffre binaire). Cette représentation d'une donnée par un élément de mémoire s'appelle un code. Une mémoire avec beaucoup de bits permet le codage de données complexes, dans la limite de la taille de la mémoire.

Le chemin par lequel unité centrale, mémoire et organes d'entrée-sortie communiquent s'appelle de façon générique un « bus ». De façon un peu formelle, un bus est un graphe connexe complet, ce qui veut dire en langage courant que tous les éléments connectés au bus peuvent communiquer entre eux.


1.3  Données



Le codage fait correspondre des groupes de bits à des symboles. Les symboles les plus simples sont les chiffres et les lettres. Pour représenter des données complexes on peut définir des méthodes, des règles pour regrouper des symboles puis associer un élément de donnée à un groupe de symboles construit selon les règles. On appellera langagelangage un ensemble de symboles ou de groupes de symboles, construits selon certaines règles, qui sont les motsmot du langage. La syntaxesyntaxe du langage est l'ensemble des règles de construction des mots du langage. La signification (ou encore la sémantiquesémantique) d'un mot d'un langage est affaire d'interprétation, et peut dépendre du contexte.

Les numéros d'immatriculation des automobiles, les numéros INSEE des personnes (dits faussement numéros de sécurité sociale), le langage machine d'un ordinateur sont des langages2.

La mémoire de l'ordinateur (c'est l'idée fondamentale de von Neumann) contient des données de deux types : des programmes et des données. Les programmes et les données sont représentés avec les mêmes symboles, seule la sémantique permet d'interpréter leurs textes respectifs. D'ailleurs, le texte d'un programme peut parfois être envisagé comme des données pour un autre programme, par exemple un programme de traduction d'un langage dans un autre.

1.3.1  L'information sous l'angle formel

Nous ne saurions omettre la mention d'une théorie formelle de l'information, même si le lecteur rebuté par les formules doit savoir qu'il pourra programmer toute sa vie en l'ignorant. Le nom de cette théorie est d'ailleurs malheureux : il serait plus approprié de dire « théorie de la communication », conformément d'ailleurs au titre de l'article de Shannon, \emph{A mathematical theory of communication, (Bell System Technical Journal, vol. 27, juillet et octobre 1948)}, ou « théorie des données ». L'ordinateur, ou le réseau de communication, contiennent et transmettent des données, qui ne deviennent de l'information que dans l'esprit d'un être humain, capable (et lui seul en est capable) de leur donner un \emph{sens}. Voir à ce sujet le texte de Michel Volle.

C'est en pensant aux systèmes de télécommunications que Henrik Nyquist et Claude Shannon ont élaboré cette théorie, mais des recherches ultérieures, notamment celles de von Neumann [40], en ont élargi la portée en la rattachant à la physique statistique par la notion d'entropie. Cette généralisation, qui dit que toute interaction entre deux systèmes peut être interprétée comme un signal porteur de message, fait de la théorie de l'information une théorie fondamentale au même titre que la théorie de la relativité ou la mécanique quantique.

1.3.2  Information et probabilités

probabilité

Le transfert de données dans un système de communication s'effectue par messages. Un message est une suite de signes (de symboles) tirés d'un alphabet. L'ensemble S = {m1 ... mi ... mn} des messages que l'on peut former à l'aide d'un alphabet donné constitue une source (discrète) de messages : un texte est une suite de messagesmessage.

La notion d'information est liée à l'ignorance du destinataire quant aux messagesmessage émis depuis S : il n'y a apport d'information que si le destinataire ignore le contenu du message qu'il va recevoir. L'incertitude, quant à la teneur du message, est d'autant plus grande que le message a une faible probabilité d'être émis ; inversement, la réception de ce message contribue à lever une incertitude d'autant plus grande, et apporte donc une plus grande quantité d'information ; ainsi apparaît une relation entre la quantité d'information d'un message mi et sa probabilité d'émission, pi, relation représentée par la fonction logarithmique suivante :
I(mi) = loga(1/pi) = - logapi

I étant l'incertitude, ou l'information, a le nombre de symboles de l'alphabet utilisé. On en déduit immédiatement que la valeur de l'unité d'information en base a est celle d'un message de probabilité 1/a. On prend généralement a = 2, l'unité correspondante étant le bit.

Cette définition probabiliste de la quantité d'information d'un message montre qu'elle dépend avant tout de la source de messages utilisée ; cette dernière peut être caractérisée par une quantité d'information (ou incertitude) moyenne, d'après l'expression :
H(S) = -
n
å
i=1
pi × logapi
qui permet d'évaluer a priori la quantité moyenne d'information que peut fournir un message ; sa valeur est maximale pour des messages équiprobables. Cette grandeur a la même forme que l'entropie thermodynamique et on l'appelle entropie de S.

L'entropie permet d'évaluer la richesse informationnelle d'un texte : Shannon a montré que si l'information moyenne d'un alphabetalphabet de 27 signes équiprobables était : log2 27 = 4,75 bits/lettre, le contenu d'un texte anglais ordinaire n'était que de 1 bitbit@bit/lettre, soit une redondance de : 1 - 1/4,75 , ou 80% de signes inutiles. Des calculs de cette forme sont effectués par les logiciels d'analyse de séquences biologiques.


1.4  Algorithme

algorithme
Ces lignes (et quelques autres) doivent beaucoup à l'ouvrage de Thérèse Accart Hardin et Véronique Donzeau-Gouge Viguié [2], dont la lecture ne saurait être trop recommandée au lecteur avide d'explications claires d'idées complexes.
L'informatique est la science du traitement de l'information (enfin, il vaudrait mieux dire des données). Nous avons donné une idée sommaire de la nature de l'information. Qu'est son traitement ? C'est, en partant d'informations connues appelée données, faire élaborer par un agent exécutant des informations nouvelles appelées résultats. Un traitement est l'application d'une méthode de passage d'un ensemble de données D à un ensemble de résultats R : à toute donnée d de D on fait correspondre un élément r de R. Cette définition est inspirée de la notion mathématique de fonction.

La méthode de passage invoquée doit être adaptée à l'agent exécutant. Par exemple, pour l'opération « somme de deux nombres entiers », la façon d'obtenir à partir d'un couple de nombres leur somme sera décrite différemment selon que l'agent exécutant sera un être humain muni d'un crayon et de papier ou le processeur d'un ordinateur.

Le traitement des données doit être effectif, c'est-à-dire que la méthode de passage doit pouvoir aboutir pratiquement au résultat. Prenons un exemple, soit D l'ensemble des numéros d'immatriculation des voitures immatriculées en France. Les symboles utilisés sont des chiffres et des lettres. Les règles de formation des numéros d'immatriculation sont la syntaxe du langage. La sémantique d'un numéro est l'identité de la voiture qui le porte. Considérons R, l'ensemble des départements français. La correspondance qui, à tout numéro d'immatriculation bien formé, fait correspondre le département d'immatriculation de la voiture qui le porte est un traitement de D, on sait comment le réaliser. Par contre la correspondance qui, à tout numéro d'immatriculation bien formé, ferait correspondre la commune d'immatriculation de la voiture associée n'est pas un traitement de D, car on ne sait pas élaborer cette information à partir du numéro, bien qu'elle existe sûrement. Cette correspondance ne peut pas être décrite de manière effective, c'est-à-dire par un algorithmealgorithme.

Un algorithme est la description, pour un exécutant donné, d'une méthode de résolution d'un problème, autrement dit d'une suite d'opérations qui fournissent le résultat cherché.

La description de la méthode, c'est-à-dire l'algorithme, doit être adaptée à l'exécutant chargé d'effectuer le traitement. L'exécutant sait effectuer un nombre fini d'actions, que l'on nomme ses primitives (ce sont par exemple les instructions du jeu d'instructions du processeur décrit ci-dessus). L'algorithme doit être constitué d'une combinaison de ces primitives. Pour construire toutes les combinaisons possibles de primitives, on démontre qu'il suffit de savoir réaliser l'enchaînement de deux primitives (effectuer une action à la suite d'une autre), la répétition d'une primitive donnée et le choix, pendant l'exécution d'un traitement, entre deux primitives selon le résultat d'un test.

Un algorithme fournit, pour un exécutant donné, la décomposition de la tâche à réaliser en primitives de l'exécutant.


1.5  Programme

programme

Au point où nous en sommes, si nous résumons notre description introductive et simplifiée de ce qu'est un ordinateur, nous dirons qu'il dispose d'un processeur capable d'effectuer des actions dites primitives, de les enchaîner dans l'ordre voulu, de les répéter et surtout de choisir, en fonction du résultat des actions précédentes, la prochaine action à effectuer entre deux ou plusieurs possibilités (ces cas possibles sont en nombre fini et connus à l'avance).

Notre ordinateur dispose aussi d'une mémoire qui contient des informations codées, qqui sont de deux types : des programmes et des données. Pour l'instant nous pouvons nous contenter de dire que des conventions sémantiques relatives au contexte de démarrage de l'ordinateur permettent de distinguer le programme des données à traiter : lorsqu'il commence à agir, le processeur va par convention aller chercher dans la mémoire, à un emplacement convenu, le texte de la première instruction à exécuter. Les règles d'enchaînement du langage assurent en principe le déroulement cohérent de la suite.

Le programme est le texte rédigé dans le langage machine de l'ordinateur de l'algorithme dont l'exécution est désirée. Ce texte énumère les primitives de l'ordinateur dont l'exécution mènera à la production du résultat recherché. Le programme est dit juste s'il se termine 3.


1.6  Langage

Fondamentalement, un ordinateur est une machine qui effectue les traitements décrits par des algorithmes rédigés dans son langage machine. Il existe, heureusement, beaucoup d'autres langages de programmation.

Un langage de programmation est un système de notation au moyen duquel un être humain peut transmettre un algorithme à un ordinateur ou à un autre être humain. Toute une gradation existe entre les langages bien adaptés aux ordinateurs mais difficiles à comprendre pour les personnes et les langages proches de notations habituelles aux personnes mais difficiles à faire interpréter par un ordinateur. Chaque ordinateur possède un langage qui lui est intrinsèque, son langage machine, et les programmes écrits dans des langages plus commodes doivent, pour être exécutés, être traduits en langage machine. Cette traduction est effectuée par des programmes spéciaux dont il existe deux grandes catégories : les compilateurscompilateur et les interprètesinterprète.

Le premier problème posé par l'usage des ordinateurs fut de communiquer des algorithmes à la machine. À l'origine le seul moyen disponible était la programmation directe en langage machine, chaque instruction codée en binaire correspondant à un circuit logique de l'unité centrale, et les données étant désignées par leur adresse, c'est-à-dire le rang de la « case » mémoire les contenant. Dès l'EDSAC (le premier ordinateur, en 1949) fut utilisé un langage permettant de désigner les instructions par un code alphabétique mnémonique et d'utiliser des adresses symboliques (alphabétiques) au lieu des adresses physiques : ce type de langage est appelé un assembleur. Il faut un programme de traduction (ou assembleur) pour le traduire en langage machine, et notamment pour traduire les symboles en adresses (physiques).

Mais le besoin se faisait sentir de langages moins dépendants de la structure de l'ordinateur et plus adaptés à la description des problèmes à traiter, que l'on appellera les langages évolués, traduits en langage machine par des compilateurs ou des interprètes, et qui sont des métalangages par rapport à l'assembleur.

Les premiers langages évolués qui apparurent sont des langages dits « impératifs », fondés sur la notion d'état de la mémoire. Ces langages, inspirés du modèle de von Neumann, John von, comportent comme le langage machine des instructions qui produisent des modifications de la mémoire (instruction d'affectation). La rédaction d'un programme en langage impératif consiste à écrire la suite des instructions qui vont causer les états successifs par lesquels devra passer la mémoire pour que, en partant d'un état initial permettant l'initialisation du programme, elle arrive dans un état final fournissant les résultats recherchés. Un tel programme explicite comment réaliser le traitement voulu par le programmeur. Le langage que nous utiliserons au cours de cette introduction n'est pas un langage impératif.

Une autre approche pour concevoir des langages de programmation est de s'inspirer du modèle de la machine de Turing. Ces langages reposent sur la notion de fonction, et sont donc appelés langages fonctionnels 4. Ils ne comportent pas d'instructions, mais le calcul est exprimé par des fonctions qui, appliquées à des arguments, rendent le résultat recherché. Des programmes rédigés avec de tels langages explicitent quoi réaliser pour obtenir le résultat voulu. Pour cette introduction nous utiliserons un langage fonctionnel.


1.7  Équivalence turingienne

Il importe de se convaincre (ce ne sera pas en un jour) que tous les programmes que nous pourrons écrire dans différents langages sont équivalents. La machine de Turing est un modèle d'automate dont on trouvera ci-dessous une description très terre à terre. Alonzo Church, le directeur de thèse d'Alan Turing à Princeton, pour approfondir la notion de fonction, invente le l-calcul, dont on montre que les expressions bien formées sont équivalentes à des machines de Turing. Les langages fonctionnels dérivent étroitement du l-calcul. L'architecture de von Neumann, conçue pour réaliser efficacement les traitements décrits par une machine de Turing, engendre les langages impératifs. Tout programme, fonctionnel ou impératif, destiné à être exécuté, sera traduit dans un langage impératif, le langage machine de l'ordinateur utilisé. La cohérence de l'informatique, et l'équivalence sémantique des programmes écrits en divers langages, qui assurent la validité de cette opération, sont le fruit non pas du hasard, mais d'une conception théorique originelle commune. Gödel, Church, von Neumann et Turing étaient tous à Princeton en 1936.

Le lecteur curieux trouvera en annexe C quelques précisions sur les liens entre le modèle de la machine de Turing, la définition axiomatique des nombres entiers et les fonctions récursives.

Description de la machine de Turing

machine de Turing

Un modèle formel pour une procédure effective (pour décrire un algorithme) doit posséder certaines propriétés. Premièrement, chaque procédure doit recevoir une définition finie. Deuxièmement, la procédure doit être composée d'étapes distinctes, dont chacune doit pouvoir être accomplie mécaniquement. Dans sa simplicité, la machine de Turing déterministe composée des éléments suivants répond à ce programme : La configuration d'une machine de Turing peut être représentée par un triplet (q, m, u) où q est l'état de la machine, m le mot qui apparaît sur le ruban avant la position de la tête de lecture, u le mot figurant sur le ruban entre la position de la tête de lecture et le dernier caractère non blanc.

Un arc du graphe de la fonction de transition peut être représenté par un quintuplet (qi, si, sj, x, qj) où : Pour se donner une intuition de la chose, imaginons une M.T. (machine de Turing) avec un alphabet {0, 1, <espace>} ; nous conviendrons d'utiliser le système de numération unaire (celui que vous utilisez pour marquer les points au ping-pong, autrement dit « les bâtons ») et de séparer les nombres par des 0. Pouvons nous additionner deux nombres ?


Figure 1.2 : Un modèle théorique.


Le ruban mentionne successivement les nombres 4 et 3. Pour les additionner il suffit que la tête de lecture lise successivement les quatre chiffres unaires qui constituent le nombre 4, dont la fin sera indiquée par l'occurrence du signe zéro. Il faudra alors supprimer le zéro et réécrire d'une case à droite les chiffres du nombre 3, jusqu'à la rencontre d'un signe zéro, qui subira le même traitement, pour obtenir 7. L'écriture de la table des transitions constituera pour le lecteur un exercice amusant.

On peut doter sa Machine de Turing de l'alphabet fini de son choix. Son ruban peut être infini dans les deux sens ou dans un seul. Elle peut même avoir plusieurs rubans. On montre que ces diverses machines sont équivalentes.


1
Une traduction plus exacte de l'anglais control unit serait « unité de commande ». L'usage a entériné l'impropriété.
2
La suite nous réserve un raffinement plus grand de la notion de langage.
3
On souhaite aussi généralement qu'il donne en se terminant un résultat pertinent. La caractérisation de la justesse d'un programme par le fait de sa terminaison peut choquer le lecteur. C'est néanmoins une condition logique primordiale, susceptible de démonstration formelle, d'où son importance. Une fois qu'elle est satisfaite, il est loisible de formuler des exigences sur la relation qui peut exister entre le domaine des données D et celui des résultats R.
4
Le terme fonctionnel suggère « programmation avec des fonctions ». Certains pensent que l'adjectif « applicatif » qualifierait mieux ces langages. Sans doute. Fonctionnel est entré dans l'usage.
© copyright Éditions Technip et Laurent Bloch 2001
Précédent Remonter Suivant