Ce cours présente quelques définitions et idées générales qu'on rencontre souvent en informatique, à quelque niveau que l'on fréquente cette discipline (utilisateur, programmeur, constructeur, théoricien, etc.). Le pretexte de notre récit sera la réalisation d'un afficheur de messages défilants.

Abstraction

Commençons par observer une lampe :

Si nous voulons décrire cette lampe, nous pouvons tenir compte de nombreux attributs : sa forme ; sa masse ; le volume qu'elle occupe ; les matériaux qui la constituent ; sa date de fabrication ; le lieu où elle se trouve, son orientation ; sa solidité ; sa résistance électrique ; sa puissance électrique ; son état : allumée ou éteinte ; sa température ; sa couleur ; etc. Certains de ces attributs sont invariables, d'autres peuvent changer au cours du temps. Selon la raison pour laquelle on s'intéresse à cette lampe, chacun de ces attributs pourra revêtir plus ou moins d'importance.

Pour nous (on verra pourquoi plus loin), l'intérêt de cette lampe réside tout entier dans un seul de ses attributs : on peut l'allumer ou l'éteindre. En réduisant ainsi la description de notre lampe, nous simplifions et généralisons sa définition : peu importent les autres attributs, pour ce que nous voulons en faire, tout objet qui possède la propriété d'être allumable et éteignable nous convient. Ainsi, nous réalisons le premier pas d'un processus nommé abstraction. En d'autres termes, abstraire, c'est simplifier.

Nous pouvons aller plus loin dans l'abstraction : en réalité, ce qui nous est réellement utile dans cette lampe, c'est qu'il s'agit d'un système auquel on peut faire prendre un état parmi deux états distincts. Décomposons cette définition :

Système binaire

Un système à deux états peut être qualifié de binaire ; que ces deux états soient "allumé" et "éteint", ou autre chose, peu importe. Nous décrivons donc maintenant notre lampe comme "un système binaire". Cette abstraction est commune à tous les objets qui possèdent deux états distincts. Voici quelques exemples de systèmes binaires :

Chacun de ces systèmes possède deux états :

• une porte est soit ouverte soit fermée ;
• le temps est soit couvert soit beau ;
• un chiffre binaire est soit un 0 soit un 1 ;
• une lampe est soit éteinte soit allumée ;
• un chat est soit vivant soit mort (sauf le chat de Schrödinger) ;
• un verre est soit vide soit plein.

En fait, dans certains cas, la limite entre les deux états n'est pas absolument nette (par exemple, le verre peut être plus ou moins rempli), mais on peut toujours décider d'un seuil, qui nous permettra de distinguer sans ambiguité entre deux états. On dit alors que l'on discrétise les états.

Lecture et écriture

Pour être en mesure d'utiliser un système binaire, nous devons avoir la capacité de réaliser deux opérations dessus :

• connaître son état (capacité de lecture);
• choisir son état (capacité d'écriture).

Parmi les systèmes présentés ci-dessus, lesquels correspondent à notre définition ?

Remarquons que dans certains cas, nous devons admettre une hypothèse pour justifier notre réponse : allumer une lampe suppose qu'elle soit reliée à une source d'électricité ; pour remplir un verre, nous devons disposer d'une réserve de liquide ; etc. Quant au chat, notons qu'un chat normal peut à volonté être placé dans l'état "chat mort", mais cet état n'étant pas réversible, on ne peut pas raisonnablement considérer que le chat est un système dont on peut choisir l'état. Enfin, le chat de Schrödinger est le seul de nos systèmes dont on ne peut même pas connaître l'état : par définition, cet état est indéterminé (il dépend d'un processus quantique aléatoire).

En conclusion, nous disposons de quatre systèmes binaires à lecture et écriture. Ces quatre systèmes reçoivent la même abstraction, et nous pouvons donc utiliser indifféremment l'un quelconque de ces systèmes pour effectuer les opérations qui relèvent de cette abstraction. Ils sont absolument équivalents.

L'abstraction sous forme de 0 et de 1 est fréquemment utilisée lorsqu'on parle d'informatique. Mais à l'intérieur d'un ordinateur, il n'y a ni 0 ni 1 ! Il y a des composants électroniques à deux états (les transistors), et la notation sous forme de chiffres binaires est pertinente pour décrire l'état de ces composants, justement parce que les transistors, eux aussi, peuvent s'abstraire sous forme d'un système binaire à lecture et écriture.

Représentation

Convention

Un système binaire est le plus simple système permettant de communiquer : nous pouvons l'utiliser pour choisir entre deux messages. Exemples (avec une diode rouge) :

    signifie "NON"
    signifie "OUI"
OU BIEN :
    signifie "Le chat de Schrödinger est mort"
    signifie "Le chat de Schrödinger est vivant"
etc.

On peut multiplier les exemples à volonté, mais nous exprimerons toujours notre message par l'état de la lampe. Puisque la même lampe est supposée permettre d'exprimer n'importe quel message, voir une lampe éteinte ou allumée ne suffit pas à comprendre le message : il faut que l'émetteur du signal et son destinataire se soient auparavant mis d'accord pour attribuer une signification à chacun des états. En d'autres termes, la signification du message est nécessairement constituée de deux composants :

l'état du système
        ET
une convention préalable.

Quelque soit la paire de messages qu'on choisit, ce n'est rien d'autre qu'un système binaire de plus. La convention (ou code) définit donc la correspondance entre chaque état d'un sytème et un état d'un autre système.

Combien de messages ?

Si nous voulons pouvoir distinguer entre plus de deux messages, nous devons avoir un système à plus de deux états. Pour cela, nous pouvons :

• soit nous donner un système à plusieurs états : notre lampe à incandescence pourrait être alimentée avec une tension variable, mais alors il faudrait être certain de bien distinguer tous les états. Il peut être aisé de reconnaître un état "à moitié allumé", mais il est sans doute difficile d'aller au dela de cinq états différents.
• soit prendre plusieurs exemplaires d'un même système à deux états. Cette méthode est la plus souple, et c'est celle que nous adopterons.

Prenons un exemple dans le domaine de la médecine. Nous voulons décrire l'état d'un patient. Pour cela, nous répondons à deux questions par OUI ou par NON, et nous obtenons un diagnostic :

Avec deux lampes, nous pouvons donc distinguer quatre messages (diagnostics) différents. Chaque message est caractérisé par l'état des deux diodes, donné dans un ordre précis : 1-0 n'est pas identique à 0-1. En d'autres termes, ce n'est pas seulement le nombre de diodes allumées qui compte, c'est aussi leur répartition.

Ces propriétés définissent une représentation numérique (ou digitale) des messages.

On peut lui opposer la représentation analogique, dans laquelle une signification (par exemple, le numéro d'ordre d'un diagnostic dans une liste, ou la température du malade, etc) est directement reliée à une grandeur de l'état du système qui envoie le message (par exemple, le nombre de diodes allumées, ou l'intensité de la lumière, etc).

Ici, ces quatre messages sont des diagnostics, mais ils pourraient aussi bien n'avoir aucun rapport entre eux : seule compte la convention.

Notons que dans notre exemple, la relation entre le message (l'état des deux diodes) et sa signification (le diagnostic) est liée aux réponses à deux questions, et que le libellé de la deuxième question dépend de la première. Il y a donc un sens associé à l'état de la première lampe, mais si on ne connaît pas cet état, alors on ne sait pas interpréter le message de la deuxième lampe, puisqu'on ignore à quelle question il est répondu "oui" ou "non". Ce n'est bien évidemment pas toujours le cas, chaque question peut exister indépedamment des autres ; l'ordre dans lequel on pose les questions n'a alors aucune importance (mais il reste impératif de respecter la correspondance de position entre les questions et les diodes).

Avec deux lampes, nous pouvons distinguer quatre états. Si on rajoute une lampe, on en obtient huit, et en général, pour n lampes, on peut former 2ⁿ messages différents.

Si nous avons besoin de x messages différents, nous devons donc utiliser n diodes, en choisissant n tel que :

Par exemple, pour l'alphabet (26 symboles) il nous faut 5 lampes, car 32 est la plus petite puissance de 2 supérieure à 26 :

Comme on a plus de messages possibles que de lettres à représenter, on utilise six combinaisons pour coder des caractères spéciaux (le blanc, et "-", etc.).

Si maintenant on veut écrire un texte en combinant les lettres, il nous faut une série de cinq lampes par lettre :

Ce message nécessite 24 x 5 = 120 lampes. Le nombre total de messages différents qu'on peut composer avec ces 120 lampes est : 2¹²⁰ = 1,33 x 10³⁶

Naturellement, si on se limite à la convention "cinq diodes <-> une lettre", la plupart de ces messages sont dépourvus de sens pour un lecteur français, par exemple on peut écrire "BDOLEJ?I EKDSN-KQL.LPWKS". Mais on peut imaginer de changer de convention, et de donner un sens à chacun de ces messages (en théorie, car la définition de tous ces sens risque de prendre du temps : la terre est agée d'environ 1.4 x 10²⁰millisecondes !). Notons au passage que si nous avions choisi une représentation analogique telle que "le nombre de diodes allumées représente le numéro du message dans une liste", on ne pourrait avoir une liste que de 120 messages !

Algorithme

Une représentation des processus

Notre représentation précédente nous permet déja d'écrire de nombreux textes, mais elle présente un inconvéniant majeur : il ne nous est pas facile de reconnaître une lettre au premier regard sur une rangée de cinq diodes ! Une autre représentation peut sembler plus parlante : représenter chaque lettre par une disposition de diodes allumées qui rappelle sa forme. Par exemple :

Chaque lettre nécessite maintenant 42 lampes, et le nombre total de caractères possibles sur notre rectangle 6x7 est 2⁴² = 4,4 x 10 ¹². A nouveau, l'immense majorité de ces dispositions possibles sera constituée de dessins ne rappelant aucune lettre, ni même un quelconque caractère. Ce codage, directement interprétable, n'est donc pas très économique. Comme il nécessite beaucoup de diodes, nous ne pouvons pas afficher notre texte en entier (nous avons 210 diodes seulement). Nous allons donc en afficher une petite partie seulement, et faire défiler l'affichage. Pour faire défiler un texte, nous devons déplacer les caractères de droite à gauche. Voici le début du texte :

Et voici comment il apparaîtra après avoir avancé d'un caractère :

Avancer caractère par caractère risque de sembler un peu saccadé. Aussi, nous allons plutôt décomposer le mouvement et avancer seulement d'une colonne à la fois :

t=0 : 

t=1 : 

t=2 : 

etc.

En supposant qu'on dispose d'un interrupteur pour chaque diode, nous allons chercher à décrire comment il faut procéder pour obtenir ce comportement de la part de notre tableau de diodes. Peut-être même pourrions-nous demander à un robot de réaliser ce travail à notre place. Mais pour cela, nous devons nous exprimer dans la langue des robots : eux ne sont pas capables de comprendre nos explications, et si nous montrons nos trois images ci-dessus à l'un d'eux, il sera incapable d'en déduire ce qui peut se passer ensuite. Les robots et les ordinateurs actuels ne savent pas obéir à un ordre tel que "Fais afficher LE CHAT DE SCHRODINGER ! avec des diodes, en faisant défiler le texte, tu sais, pour que çà fasse comme les panneaux publicitaires". Il y a, dans cette manière de parler, trop d'ambiguités, et elle exige, pour être compréhensible, trop de connaissances sur le monde (que nous avons, vous et moi, mais pas le robot).

Tout d'abord, il nous faut repérer chaque diode individuellement. Nous pourrions attribuer à chacune un numéro de 1 à 120. Mais il nous sera sans doute plus facile de trouver une lampe donnée si nous connaissons sa ligne et sa colonne : nous allons utiliser les coordonnées cartésiennes. Comme origine du repère, on prend le coin en haut à gauche, et on note chaque lampe par son numéro de ligne suivi de son numéro de colonne. La lampe la plus en haut et à gauche est notée (1,1). Ainsi, si on considère les trois états successifs représentés ci-dessus, la lampe (4,9) est allumée dans l'état initial (t=0), allumée également dans le deuxième cas (t=1), et éteinte à la troisième étape (t=2). Pour une lampe située colonne C et ligne L, on note l'état à un instant t : Etat(l,c)_t et les valeurs possibles sont "allumé" et "éteint".

Pour que le texte défile de droite à gauche, il suffit qu'à un instant t, chaque diode prenne l'état qu'avait, à l'instant t-1, la diode située immédiatement à sa droite. En d'autres termes : Etat(l,c)_t = Etat(l,c+1)_t-1 selon notre notation. Il nous faut appliquer cette formule à toutes les lampes, à chaque nouvelle valeur de t. Si on appelle cmax le numéro de la colonne la plus à droite (pour nous, cmax = 30), et lmax le numéro de la ligne la plus en bas (pour nous, lmax = 7), alors on peut exprimer notre petite recette (intitulée Décaler) de la façon suivante :

Décaler :
Pour c allant de 1 à cmax faire :
    Pour l allant de 1 à lmax faire :
        Etat(l,c)t <- Etat(l,c+1)t-1

On a utilisé un formalisme qui permet de décrire le parcours de l'ensemble des lampes, et l'action à effectuer sur chacune d'elles : on fait varier c entre 1 et cmax, et pour chaque valeur de c, on fait varier l de 1 à lmax. Le fait que le parcours des valeurs de l soit répété pour chaque valeur de c est indiqué ici par le fait que "Pour l allant..." est en retrait par rapport à "Pour c allant ...". De même, pour chaque valeur de l qu'on rencontre (à chaque parcours effectué pour une valeur de c donnée), on effectue l'opération écrite en retrait : On donne à la lampe (l,c) l'état qu'avait la lampe (l,c+1) à l'instant précédent (la flêche indique que l'état qu'avait la lampe (l,c+1) au temps t-1 devient celui de la lampe (l,c) au temps t). Une recette, exprimée ainsi en utilisant un formalisme précis, est dénommée algorithme. Ainsi, le robot (ou un ordinateur) peut réaliser ce travail, car il est exprimé à l'aide d'un vocabulaire réduit et formel, et qu'il n'exige aucune connaissance préalable du contexte.

Qui est intelligent ?

Cet exemple nous montre un aspect très important du fonctionnement des ordinateurs : le robot se moque bien du contenu de notre texte, et ne cherche même pas à "comprendre" ce qu'il fait. Il applique à la lettre notre algorithme, et n'a, à aucun moment, la moindre conscience que faire prendre à des lampes, l'état qu'avait leur voisine de droite juste avant, cela résulte globalement en un déplacement vers la gauche du motif affiché. L'ordinateur ne travaille que sur la représentation des choses, pas sur leur signification. La signification de ce qui se déroule (qui, rappelons-le, nécessite une interprétation, et suppose une convention) n'est pas de son ressort, elle est de celui de l'humain. La question de savoir si un ordinateur est "intelligent" ou non n'a donc pas beaucoup de sens : l'intelligence est totalement étrangère à l'ordinateur.

Et pour finir, la mémoire.

Notre algorithme effectue le travail pour un déplacement unitaire. Il devra donc être répété autant que nécessaire pour faire défiler le texte, éventuellement le même texte plusieurs fois. Mais auparavant, examinons-le de plus pès.

En fait, ce algorithme est faux ! Pas complètement faux, heureusement, mais il souffre d'une petit imperfection (un bug) : si chaque diode prend l'état de la diode qui se trouve à sa droite, que se passe t-il pour les diodes situées le plus à droite du panneau d'affichage ? Une telle diode "ne sait pas quoi faire", puisqu'elle n'a pas de lampe à sa droite sur laquelle copier son état. Selon la bonne volonté du robot, celui-ci peut, par exemple :

• mettre cette lampe dans un état quelconque, aléatoire ;
• l'allumer systématiquement ;
• la laisser dans son état actuel ;
• arrêter dès la première qu'il rencontre, en maugréant qu'avec c=cmax, il n'y a pas de diode (l,c+1) !

Si nous regardons le schéma, nous voyons que les lampes à droite du panneau se mettent dans un état qui correspond à la suite du message. Il faut donc prendre connaissance de l'état souhaité, ailleurs que sur le panneau lui-même. L'ordinateur a besoin d'une mémoire où cette information soit présente, et d'un mécanisme (détaillé par l'algorithme) qui lui permette de transformer les informations de la mémoire en état à attribuer aux diodes. Différents moyens de stocker et traduire l'information sont envisageables, mais les expliciter dépasserait le cadre de ce cours. Supposons simplement qu'on puisse lire l'état de la colonne suivante dans une zone de la mémoire nommée Mem, qui comprend sept objets binaires (un par colonne) dont l'état est soit "0" soit "1". Mem est mise à jour par l'instruction Remplir Mem (qui fait exécuter un algorithme qu'on suppose avoir écrit par ailleurs) dont le rôle est de mettre les sept objets dans l'état correspondant à la prochaine colonne (et de revenir à la première colonne quand on est arrivé au bout du message). Ainsi, lorsque t=0, Remplir Mem a pour conséquence que Mem(1) est dans l'état 0, et Mem(5) dans l'état 1. Notre algorithme devient :

Défilant :
Remplir Mem
Pour t allant de 1 à 1000 faire :
    Pour c allant de 1 à (cmax-1) faire :
        Pour l allant de 1 à lmax faire :
            Etat(l,c)t <- Etat(l,c+1)t-1
    Pour l allant de 1 à lmax faire :
        Si Mem(c) = 1
            Etat(l,cmax) <- Allumé
        Sinon
            Etat(l,cmax) <- Eteint
    Remplir Mem

L'essentiel de notre panneau défilant est ainsi réalisé.

Conclusion

Les notions que nous venons de voir : abstraction, représentation, algorithme, sont partout présentes en informatique, plus ou moins apparentes.