L’informatique sans ordinateur

Pista azul El 21 agosto 2015  - Escrito por  Baptiste Mélès Ver los comentarios (7)

L’informatique a la fâcheuse réputation d’être la science des ordinateurs. Quelle que soit sa spécialité, un « informaticien » sera toujours appelé à réparer l’ordinateur de son beau-frère. Sa discipline ne porte-t-elle pas le nom anglais de computer science [1] ? Nous montrerons ici, à l’inverse, qu’une part non négligeable des concepts et méthodes de la discipline informatique est indépendante du monde des ordinateurs. Nous verrons ainsi :

  1. qu’on peut faire fonctionner Internet avec des pigeons voyageurs ;
  2. que l’algorithmique peut accélérer la recherche d’un mot dans le dictionnaire ;
  3. qu’il est parfois utile de faire de la programmation sur papier.

Par ces exemples, nous entendons montrer que l’informatique est, comme la logique et les mathématiques, plus qu’une simple technique : c’est une discipline formelle, c’est-à-dire qu’elle peut indifféremment s’appliquer à des supports matériels très différents, l’ordinateur n’étant qu’un cas particulier.

Internet par pigeons voyageurs

Contrairement à ce que l’on croit spontanément, le protocole Internet (IP) n’est pas nécessairement réservé aux ordinateurs. Certes, lorsqu’il fut défini en 1974 dans un article de Vinton Cerf et Robert Kahn [2], il s’agissait de concevoir un protocole de partage de ressources entre des réseaux d’ordinateurs :

« l’une des raisons principales du développement de ce type de réseaux fut de faciliter le partage de ressources informatiques (computer resources) ».

Mais si Internet fut d’abord conçu pour les ordinateurs, cela ne veut pas dire qu’il n’ait de sens que sur des ordinateurs.

Le partage de ressources par le protocole Internet consiste à décomposer le flux de données — par exemple une page web — en paquets, dont chacun contient une partie du message à transmettre. Ces paquets, appelés datagrammes, sont transportés indépendamment les uns des autres, et peuvent même être reçus dans le désordre, selon les aléas du routage.

Dans chaque datagramme, les données sont précédées par un en-tête. Celui-ci contient des « méta-informations », qui sont l’équivalent de ce que l’on écrit sur une enveloppe, quand on note l’adresse du destinataire, celle de l’expéditeur ainsi que diverses mentions comme « par avion » ou « fragile ». Ici, on doit préciser la version du protocole et d’autres informations, dont les plus importantes sont l’adresse source et l’adresse cible [3].

Dans le protocole IPv4, encore largement utilisé en 2015, ces adresses, connues sous le nom d’adresses IP, sont numérotées de 0.0.0.0 à 255.255.255.255, en passant donc par des adresses aussi expressives et faciles à mémoriser que 129.199.129.1 et 192.168.0.1 ! Ces fameuses adresses IP permettent d’identifier l’hôte d’un réseau. Dans les séries télévisées, le héros est toujours assisté d’un expert en informatique qui parvient à remonter jusqu’à l’adresse IP du criminel : cela ne permet pas toujours de connaître son identité, mais au moins de savoir quel ordinateur il a utilisé. Cette marge d’incertitude laisse ouverte la possibilité d’un rebondissement inattendu.

Mais si Internet a d’abord explicitement été conçu pour un monde d’ordinateurs, rien, dans le cahier des charges du protocole lui-même, n’exige que les informations circulent sous la forme de signaux échangés directement entre des ordinateurs sans intervention de la main humaine. Le protocole IP décrit seulement la forme que doit prendre l’information, mais il garde le silence sur le matériau qui permet de la transmettre. On connaît la fibre optique, les ondes radio, le courant porteur ; mais pourquoi pas des signaux de fumée, des sifflements, des clins d’œil ?

Dans le vocabulaire des réseaux, on dit qu’IP relève de la « couche réseau » et non de la « couche physique » qui lui est sous-jacente. Cette indépendance de la couche réseau par rapport à la couche physique permet notamment à des protocoles comme Internet de survivre aux conditions historiques et matérielles qui les ont vus naître, laissant le champ libre à l’invention de nouveaux moyens de transmission. Pour peu que l’information soit formatée correctement, le matériau utilisé pour le transfert est donc indifférent.

Ce constat a conduit David Waitzmann à publier un célèbre poisson d’avril le premier avril 1990, sous la forme d’un document officiel d’apparence très sérieuse : « Un standard pour la transmission des paquets IP sur pigeons voyageurs » (RFC 1149) [4].

Le protocole IP y est respecté à la lettre :

Le paquet IP est imprimé sur un petit rouleau de papier, en hexadécimal, les octets [5] séparés par du noir et du blanc. Le rouleau de papier est enroulé autour d’une des pattes du pigeon voyageur. Une bande de scotch est utilisée pour sécuriser les bords du paquet. La bande passante [6] est limitée par la taille de la patte. [...] Après réception, la bande de scotch est ôtée et la copie papier du paquet est numérisée et transformée dans un format électronique transmissible.

Le format des datagrammes étant parfaitement respecté, il s’agit d’une mise en œuvre tout à fait légitime du protocole IP, jusque dans ses limites intrinsèques :

Étant donné que IP ne garantit qu’une tentative de délivrance (best-effort delivery), la perte d’un pigeon peut être tolérée. Avec le temps, les pigeons se régénèrent automatiquement. On ne dispose pas de multi-diffusion, mais les orages peuvent causer des pertes de données. Il y aura des tentatives de livraison répétées, jusqu’à ce que le pigeon tombe.

JPEG - 260.9 KB
« Avec le temps, les pigeons se régénèrent automatiquement. »

Les caractéristiques des pigeons voyageurs peuvent ainsi être décrites dans le vocabulaire standard des réseaux informatiques, ce qui permet une comparaison technique avec d’autres supports :

Les pigeons voyageurs peuvent apporter un service impliquant un délai important, un faible débit et une grande altitude. La topologie de la liaison est limitée à une seule route point-à-point par pigeon, en utilisant des pigeons ordinaires [...]. Les pigeons ont un système d’évitement de collision intrinsèque, ce qui augmente leur disponibilité. Au contraire de certaines technologies réseau, comme les communications par radio, la communication ici n’est pas limitée par la ligne de vision directe.

Le système pourrait même être généralisé, moyennant quelques désagréments à la saison des amours : « il est possible d’utiliser un grand nombre de pigeons sans connaître d’interférences significatives, excepté au début du printemps » — saison où la noble mission des pigeons passe souvent au second rang de leurs préoccupations.

JPEG - 178.4 KB
Au printemps, des paquets peuvent se perdre en route.

De plus, il conviendra de s’entourer de précautions telles qu’un système de priorités permettant au pigeon d’aller picorer et un chiffrage du message s’il contient des données sensibles. Enfin, le chemin emprunté par le datagramme peut facilement être tracé : « Des traces sont automatiquement générées, et peuvent souvent être trouvées sur les journaux et les câbles ». Le système d’Internet par pigeons voyageurs est donc théoriquement viable ; plusieurs personnes se sont même amusées à l’expérimenter.

Sous ses dehors de simple poisson d’avril, la norme RFC 1149 est porteuse d’un message tout à fait sérieux : l’indépendance de la couche réseau par rapport à la couche physique. Le format du message est indépendant du matériau qui le transmet. Quoique initialement destiné aux ordinateurs, ce protocole est donc compatible avec un dispositif de papier, d’encre et de pigeons.

Ce constat est généralisable à de nombreux concepts et méthodes de l’informatique, qui valent indépendamment de leurs applications matérielles. Nous en donnerons ici deux autres exemples : la recherche d’un mot dans le dictionnaire et la programmation sur papier.

L’algorithmique du dictionnaire

Chercher un mot dans le dictionnaire semble être la chose la plus facile du monde ; mais qui sait le faire efficacement ?

Cherchons d’abord la définition du mot « pataquès » comme on le fait dans la vie de tous les jours. On parcourt quelques pages prises au hasard, puis, parvenu aux alentours des lettres O ou Q, on fait défiler sous le pouce une cinquantaine de pages, parfois en revenant sur ses pas si l’on est allé trop loin, et enfin on trouve la bonne page. Combien de pages intermédiaires a-t-on parcourues avant de trouver celle que l’on cherchait ? Souvent une bonne soixantaine.

Cette méthode n’est guère économique. On peut trouver bien mieux.

Chercher un mot dans un dictionnaire, c’est chercher une entrée dans une liste triée (ici dans l’ordre alphabétique). Ce type de problème est très fréquent en informatique, et plus précisément en algorithmique, la science qui cherche à optimiser les méthodes de calcul.

Voyons donc une méthode plus efficace pour trouver un mot dans le dictionnaire. Disons que notre dictionnaire compte environ 2000 pages. Ouvrons-le en deux et lisons l’en-tête : IRREG.

JPEG - 359.7 KB

Comme nous connaissons l’ordre alphabétique, nous savons que le mot « pataquès » se trouve dans la moitié de droite. Prenons donc cette moitié entre deux mains, et ouvrons-la à nouveau vers le milieu : RECEN.

JPEG - 449.6 KB

Isolons la partie comprise entre IRREG et RECEN, coupons-la en deux : nous obtenons OPPRI.

JPEG - 597.2 KB

Poursuivons de la sorte, et nous obtiendrons successivement PLINT, PATRI, PALPE, PARTI, PASSI et enfin PATEN. L’algorithme progresse très rapidement vers sa solution : nous n’aurons lu que 9 en-têtes avant de parvenir à la page recherchée. Que de temps économisé par rapport à la méthode naïve !

JPEG - 808.5 KB

Le nombre maximal d’en-têtes à lire dans le dictionnaire pour rechercher un mot quelconque dépend du nombre de pages du dictionnaire. Si le dictionnaire compte 2048 pages, c’est-à-dire $2^{11}$ pages, on peut trouver n’importe quel mot en parcourant moins de 11 en-têtes — ce que confirme notre exemple. Et si le dictionnaire contenait deux fois plus de pages, combien d’en-têtes supplémentaires devrait-on lire ? — Un seul, car la moitié que l’on isolerait immédiatement aurait la taille du dictionnaire de l’exemple précédent.

Cette méthode est d’un usage fréquent en programmation et dans les bases de données. Mais rien ne la prédestine exclusivement au monde des ordinateurs : elle s’applique à toute situation dans laquelle on recherche une entrée dans une liste dont on connaît l’ordre de tri (ici l’ordre alphabétique) et la taille, et dont on peut facilement localiser le milieu (par exemple en extrayant une entrée à partir de son adresse). C’est donc le cas lorsque l’on recherche un mot dans le dictionnaire, une adresse dans un bottin, le nom de la ville correspondant à un code postal donné, un livre dans les étagères d’une bibliothèque municipale, etc. C’est aussi le cas si quelqu’un nous dit de deviner un nombre compris par exemple entre 1 et 2000 et qu’il ne nous répond à nos tentatives que par « plus » ou « moins ».

Ainsi, les méthodes de l’algorithmique ne dépendent ni d’un support matériel ni d’un contexte particulier. Elles dépendent seulement de ce que l’on pourrait appeler un « squelette de situation », aussi abstrait que les structures qu’étudient les mathématiciens.

La programmation sur papier

Mais qu’en est-il de la programmation, l’activité informatique par excellence, qui consiste à donner des instructions à une machine ? Ne suppose-t-elle pas, par définition, l’usage d’un ordinateur ?

La réalisation d’un projet informatique, par exemple le portail informatique d’une bibliothèque, nécessite la participation de nombreux acteurs. Le problème est que les informaticiens ne connaissent pas tous les détails de l’administration d’une bibliothèque et que les bibliothécaires ne sont pas des spécialistes de l’informatique. C’est la source de nombreuses incompréhensions, d’une insatisfaction et de surcoûts ; c’est très gênant (surtout les surcoûts).

Plus encore, l’équipe des informaticiens peut être divisée en groupes qui pensent et parlent différemment : certains ne jurent que par les « bases de données » et parlent un langage qui s’appelle SQL, d’autres ne jurent que par la programmation orientée objet et ne parlent que les langages Java ou PHP. Comment faire collaborer efficacement tous ces groupes différents, qui ne parlent pas le même langage ?

PNG - 10.3 KB
Un programme en SQL
PNG - 11.7 KB
Un programme en Java

Une solution à ce problème fut proposée dans les années 1990 avec le langage UML (Unified Modeling Language : langage de modélisation unifiée). Il est enseigné dans des écoles d’informatique au même titre que les langages C, Java, PHP et SQL. Mais contrairement à ces derniers, son destin n’est pas d’être exécuté par une machine ni même tapé sur un ordinateur : il peut être tracé à la hâte sur un coin de nappe ou sur un bout de papier gras, pour être transmis en mains propres aux autres collaborateurs du projet. UML est un langage de programmation sur papier, qui n’est exécuté que par des êtres humains.

La partie centrale d’UML, les diagrammes de classes, consiste à tracer les lignes directrices du projet. Pour cela, on identifie les principaux types d’objets, leurs attributs, les opérations qu’ils peuvent subir et leurs interactions.

Un système de gestion de bibliothèque, par exemple, permettra de manipuler trois principales classes d’objets :

  • un objet de la classe « Œuvre » possède un titre, un nom d’auteur, un éditeur et un numéro ISBN ;
  • un objet de la classe « Exemplaire » possède un numéro d’inventaire et une indication de statut (en rayon, emprunté, manquant, en rénovation...) ;
  • un objet de la classe « Adhérent » possède un nom, un prénom, une adresse.

On peut ensuite énumérer les opérations associées à chaque classe d’objets :

  • une œuvre peut être enregistrée ou supprimée ;
  • un exemplaire peut être enregistré ou supprimé ;
  • un adhérent peut être enregistré, supprimé, recevoir un courrier.

Détaillons enfin les interactions possibles entre les classes d’objets :

  • une œuvre peut être incarnée par un exemplaire ;
  • un exemplaire peut être emprunté par un adhérent ;
  • un adhérent peut réserver une œuvre.

On peut ainsi tracer le diagramme de notre projet. Chaque classe (« Œuvre », « Exemplaire », « Adhérent ») est représentée par un cadre, dans lequel on note le nom de la classe, la liste des attributs, puis, sous un trait horizontal, toutes les opérations que les objets de cette classe peuvent subir. Les classes sont reliées entre elles par des lignes représentant leurs associations, c’est-à-dire les relations qui leur permettent d’interagir [7].

JPEG - 778.4 KB
Un diagramme de classes UML

Établir le diagramme de classes demande une certaine réflexion de la part des destinataires du système : ils doivent mettre à plat tous leurs besoins futurs. Mais une fois que leurs exigences ont été modélisées en UML, ils peuvent transmettre leurs schémas aux informaticiens. Les spécialistes de bases de données sauront alors immédiatement comment convertir ce diagramme en un schéma de bases de données, et les spécialistes de programmation orientée objet comment construire le programme et l’interface permettant de l’utiliser.

UML est donc un langage indépendant des machines, des langages et des logiciels, qui permet aux différents acteurs d’un projet de communiquer malgré la diversité de leurs approches. Il est enseigné jusque dans des écoles de gestion. Il s’agit donc d’un véritable outil de programmation sur papier. Comme tout langage informatique, il est formalisé, et se prête aisément à un traitement formel ; mais ce traitement est généralement effectué par un cerveau humain plutôt que par un processeur. Hormis son support matériel peu ordinaire — un bloc-notes ou un tableau noir — il a toutes les caractéristiques d’un langage informatique.

Conclusion

Ces trois exemples, empruntés à différents domaines — les réseaux, l’algorithmique, la programmation —, montrent que les applications des concepts et les méthodes du traitement automatique de l’information ne sont pas réservés au monde des ordinateurs. Ainsi, le projet pédagogique Computer Science Unplugged préconise d’enseigner l’informatique à l’aide de cartes, de ficelles et de crayons plutôt qu’en distribuant des tablettes numériques dans les écoles [8]. Maint autre exemple pourrait être cité, notamment dans la théorie des systèmes d’exploitation [9]. Si l’ordinateur est l’objet informatique par excellence, c’est simplement parce que les concepts et méthodes informatiques y sont mobilisés de façon massive — mais non de façon exclusive.

L’informatique est une discipline formelle, c’est-à-dire un domaine de recherche dont les concepts, les méthodes et les critères de vérité ne dépendent pas de faits ni de supports matériels particuliers. Comme la logique et les mathématiques, elle se nourrit en grande partie de ses applications pratiques, mais n’y est pas subordonnée : le logicien raisonne avec des flèches, le mathématicien compte sur ses doigts, mais le raisonnement est indépendant de la craie et le nombre est indépendant des doigts. Les innovations informatiques, comme celles de la logique et des mathématiques, apparaissent au gré d’une histoire qui souvent trébuche ou bégaie, mais elles ne dépendent pas conceptuellement de leurs circonstances d’apparition.

Si la logique nous apprend ce que c’est que penser et les mathématiques ce que c’est que connaître, l’informatique nous montre ce que c’est qu’agir rationnellement en s’aidant d’une matière en général, celle-ci étant laissée à notre discrétion.

Post-scriptum :

Pour en savoir plus, n’hésitez pas à visionner en ligne la captation audiovisuelle de cette séance du Séminaire d’histoire des mathématiques de l’IHP.

L’auteur remercie Liesbeth De Mol, Maarten Bullynck et Serge Abiteboul pour leurs précieuses remarques, Christine Proust et Anne Schmauch pour leurs belles photographies. Il remercie également pour leur grande attention les relecteurs dont les noms ou les pseudonymes sont Raphaël Alexandre, Mateo_13, janpol3, Rémi Coulon, bayéma, Marcus Mildner, Sébastien Martinez et Clément Caubel.

Article édité par Frédéric Brechenmacher

Notas

[1Dans l’article fondateur où Alan Turing décrit l’un des premiers modèles théoriques de l’ordinateur, il utilise fréquemment le terme de « computer »... dans le sens de « calculateur », l’être humain qui calcule. Voir Alan Turing, « On Computable Numbers, with an Application to the Entscheidungsproblem », Proceedings of the London Mathematical Society, 2e série, vol. 42, 1937. Le mot français d’« informatique » fut proposé en 1962 par Philippe Dreyfus et admis par l’Académie française en 1966.

[2Vinton Cerf et Robert Kahn, « A Protocol for Packet Network Intercommunication », IEEE Transactions on Communications, vol. COM-22, n°5, mai 1974, p. 637-648.

[3Les quatre premiers bits d’un datagramme décrivent la version du protocole Internet utilisée : 0100 pour la version 4 (surnommée IPv4) ou 0110 pour la version 6 (surnommée IPv6). Les quatre bits suivants contiennent la longueur de l’en-tête. Viennent ensuite notamment le type de service, la longueur totale du datagramme, la position du fragment, la durée de vie du paquet, les adresses source et cible, diverses options et enfin les données du paquet lui-même.

[4Voir aussi la traduction française de Samuel Tardieu.

[5Les octets sont des suites de huit chiffres binaires comme 00101010 ou 00011001.

[6La bande passante est le débit de la connexion, c’est-à-dire la quantité d’informations que l’on peut faire transiter en un temps donné.

[7Nous ne détaillerons pas ici la notion de « multiplicité » dans les diagrammes de classes d’UML, représentée sur notre diagramme par des « 1 » et des « 0..* ».

[8En France, l’algorithmique a fait son entrée dans les programmes de lycée en 2009 et elle est prévue dans les programmes de collège pour 2016.

[9On trouve ainsi des pratiques de défragmentation hors des systèmes de fichiers : « Excusez-moi Madame, accepteriez-vous de vous décaler d’une place afin que je puisse m’asseoir à côté de mon amie, s’il vous plaît ? ». Il existe également des algorithmes d’ordonnancement pour bien d’autres choses que des processus : « Prenez un ticket et le guichetier vous recevra lorsque viendra votre tour ».

Comparte este artículo

Para citar este artículo:

Baptiste Mélès — «L’informatique sans ordinateur» — Images des Mathématiques, CNRS, 2015

Créditos de las imágenes:

Imagen de portada - L’image en logo provient de l’article Pigdee : la livraison par pigeon voyageur du site Capitaine Commerce.
Au printemps, des paquets peuvent se perdre en route. - Baptiste Mélès
« Avec le temps, les pigeons se régénèrent automatiquement. » - Christine Proust
img_14408 - Baptiste Mélès
img_14785 - Baptiste Mélès

Comentario sobre el artículo

Voir tous les messages - Retourner à l'article

  • L’informatique sans ordinateur

    le 24 de agosto de 2015 à 11:44, par Baptiste Mélès

    Bonjour,

    Merci beaucoup pour votre témoignage. La programmation est tout à la fois à la fois une école de rigueur, comme les mathématiques, et une pratique aussi ludique que les jeux vidéo. Espérons que les élèves y prennent goût, comme l’exemple que vous citez...

    Bien cordialement,

    Baptiste Mélès.

    Répondre à ce message

Dejar un comentario

Foro sólo para inscritos

Para participar en este foro, debe registrarte previamente. Gracias por indicar a continuación el identificador personal que se le ha suministrado. Si no está inscrito/a, debe inscribirse.

Conexióninscribirse¿contraseña olvidada?

Registros

Este artículo es parte del registro «L’IHP, maison d’histoires» consulte el registro
La traducción del sitio del francés al castellano se realiza gracias al apoyo de diversas instituciones de matemáticas de América Latina.