Ivan Lavallée nous introduit à l’algorithmique, comme l’un des grands enjeux de l’informatique d’aujourd’hui, et l’incontournable des sciences du XXIe siècle. L’ordinateur qui a déjà bouleversé nos modes de vie, irait-il jusqu’à bouleverser nos modes de pensées ?

Que peut-il y avoir de commun entre, internet, la ola dans un stade, une observation faite par un corsaire en 1580, les dinosaures, un vol d’oiseaux, Darwin, une horde de Kangourous et un système opératoire d’ordinateur? Non, il ne s’agit pas ici de faire du Prévert, mais de se donner de nouveaux outils de compréhension du monde.

La simulation informatique intervient aujourd’hui dans quasiment toutes les activités humaines, la manifestation la plus spectaculaire en étant peut-être la prévision du temps. Les récentes images du typhon Haiyan dont la trajectoire a pu être prévue, permettant des évacuations et l’économie de vies humaines en sont une manifestation. De même le chirurgien Jacques Marescaux, a réalisé, depuis New York, devant des collègues états-uniens médusés, l’ablation d’une vésicule sur une patiente à Strasbourg. Mais au-delà de l’aspect spectaculaire des images sur l’écran de l’ordinateur, et de la puissance de calcul de celui-ci, ce qui est déterminant ce sont les programmes sous-jacents qui ne sont euxmêmes que le codage en un langage compréhensible par l’ordinateur, d’algorithmes. Jusqu’à une période récente les algorithmes de simulation n’étaient sensés eux-mêmes que « mettre en musique » des équations mathématiques, un langage informatique s’appelle d’ailleurs FORTRAN pour FORmula TRANslator. Or il est des domaines dans lesquels les mathématiques classiques ne peuvent à elles seules satisfaire.

ALGORITHMES ET NATURE

Les algorithmes ont été formalisés à l’origine par Alan Mathison Turing en 1936. Il a montré que tout ce qui est calculable peutêtre décomposé en étapes élémentaires, chacune pouvant être effectuée par une machine. C’est la Machine de Turing, qui a donné ses lettres de noblesse à l’informatique en tant que science.

La fin du XIXe siècle et les premières décennies du XXe ont vu les physiciens mettre le monde en équations. La phénoménale (déraisonnable selon Wigner1) puissance des mathématiques a permis aux physiciens de résumer les lois qui commandent notre monde inanimé en quelques équations qui tiennent sur une page de format A4. Mais malgré des travaux de haute volée, de Turing à Thom, la biologie est rétive au langage mathématique classique.

Les mathématiques telles que nous les pratiquons sont paradoxalement plutôt inefficaces en biologie et dans les sciences humaines, hors la statistique. La compréhension de la circulation sanguine ou du fonctionnement du système immunitaire ne saurait être résumée en quelques termes ou équations. Comme le fait remarquer Bernard Chazelle, « La raison en est simple. L’univers physique est bâti sur des principes de symétrie et d’invariance (…) qui font cruellement défaut en biologie. » La différence essentielle selon nous, vient de l’action du temps, deus ex machina.

En biologie, le temps, briseur de symétrie, agit beaucoup plus rapidement qu’en physique. Là où les objets physiques ne s’altèrent pas sur des milliards d’années, les êtres biologiques ont évolué, les laps de temps peuvent être beaucoup plus courts; ainsi nous mourons, et si les étoiles meurent aussi, cela se passe sur des constantes de temps qui échappent à notre « bon sens ». Ainsi, peut-on écrire qu’un ADN d’aujourd’hui est le résultat de l’ADN d’une entité biologique il y a quelques millions d’années sur lequel a agi le temps et plus particulièrement l’histoire. C’est-à-dire que cette entité biologique s’est modifiée pendant ce temps, a échangé de l’information avec son environnement et a été modelée par ces échanges et ces corruptions, c’est la sélection naturelle. D’où l’équation : ADN = Chimie + Histoire
C’est la simulation informatique qui vient prêter main-forte aux mathématiques aujourd’hui. Et qui dit informatique dit nécessairement algorithmique.

L’école française d’informatique théorique est orientée non seulement sur les langages mais aussi sur l’algorithmique, la science des algorithmes, et la complexité, en particulier sur les domaines nouveaux en la matière que sont les réseaux, le parallélisme et la simulation des phénomènes de la nature. Les algorithmes offrent un langage souple et puissant pour la modélisation des systèmes biologiques et sociaux. Ils fournissent la base pour des simulations numériques ainsi qu’un cadre puissant pour leur analyse. Mais les algorithmes étaient jusqu’à il y a peu, confinés dans le strict domaine de l’informatique, destinés à la conduite des ordinateurs tous basés sur le concept de Machine de Turing, algorithmique par définition. Aujourd’hui, la compréhension des systèmes dits naturels augmentant, les algorithmes franchissent leur frontière naturelle et viennent concurrencer le rôle que jouent depuis longtemps les équations différentielles dans la simulation du monde physique.

SIMULER LES PHÉNOMÈNES NATURELS

Ainsi est-on amené à comprendre et simuler des phénomènes comme la formation d’un vol d’oiseaux migrateurs par exemple, le comportement individuel de chacun pouvant être résumé par trois règles simples énoncées en 1987 par Reynolds :
1 – Séparation : maintenir une distance avec les autres de façon à éviter les collisions ;
2 – Alignement: se déplacer vers ce qu’on considère comme étant le centre du groupe;
3 -Cohésion : aligner sa vitesse sur celle des autres.

Or dans cette démarche, rien n’est dit sur le comportement du groupe. C’est la dialectique des comportements individuels ici qui fait groupe et génère les vols bien connus des oiseaux migrateurs.

Vers 1580 le corsaire Sir Francis Drake rapporte un phénomène qui l’a frappé. À San Francisco, lorsque vient la nuit, la baie est illuminée par des milliers de lucioles, qui petit à petit, se mettent toutes à clignoter ensemble, en phase. On obtient un résultat analogue en posant des métronomes à balancier sur une planche elle-même posée sur deux rouleaux. Même si on ne les a pas réglés au départ sur la même fréquence, au bout d’un temps plus ou moins long, ils battent en cadence. C’est ce qu’on appelle un système à influence ou oscillateurs couplés. C’est le même phénomène à l’oeuvre lors de la formation d’une « ola » dans un stade. Peuton simuler les phénomènes de mutations génétiques qui ressortissent à une algorithmique particulière dont la modélisation peut désormais être étudiée?

La base théorique de l’algorithmique est, nous l’avons vu, la Machine de Turing, machine abstraite dont le concept a été exposé par Alan Mathison Turing en 1936 et qui est le modèle générique de tous les processeurs actuels, micros ou pas. Cette machine est constituée d’un ruban, qui est son seul moyen de communiquer avec le monde extérieur, sur lequel elle peut lire et écrire. Elle lit une information sur le ruban, la traite suivant son programme interne et éventuellement écrit sur ledit ruban, le tout de façon purement séquentielle et complètement déterministe. Cet outil théorique, était destiné originellement à répondre à une question en théorie des nombres et en logique. Il a donné naissance à l’informatique théorique et plus particulièrement à l’algorithmique. La pratique a posé de nouveaux problèmes avec l’apparition des réseaux d’ordinateurs et du parallélisme dans les processeurs, ce qui a donné lieu à des travaux théoriques majeurs, portés en particulier par une équipe française d’universitaires (voir le congrès OPOPAC de 1999, et sonsuccesseur OPODIS).

UNE NOUVELLE AVANCÉE EST EN COURS

En algorithmique des réseaux, on considère des ordinateurs qui communiquent entre eux (comme dans Internet) et tout le problème consiste à faire fonctionner correctement le réseau, c’est-à-dire les communications. Mais si au lieu d’ordinateurs communiquant entre eux, on considère des oiseaux, des avions, des lucioles, des métronomes ou des kangourous, on est dans la même problématique, ce qu’on avait déjà remarqué sans le développer il y a vingt-cinq ans.

D’où l’idée d’essayer de théoriser les algorithmes naturels qui gèrent ces comportements. Mais on peut aller plus loin et avoir une vue synthétique de tous ces algorithmes, ne pas considérer d’un côté les algorithmes naturels et de l’autre, les autres mais disposer d’un modèle conceptuel qui contienne à la fois les algorithmes stricto sensu au sens de ceux utilisés en informatique classique et les autres phénomènes c’est ce qu’on nomme algorithmes de la nature. Ce modèle (2) contient à la fois celui de Turing, la logique des communications et l’aspect aléatoire de la sélection naturelle. Ainsi sur le dessin ci-joint, les bandes horizontales représentent les 60 premiers éléments, les nucléotides, d’une séquence génétique de 5 espèces, l’homme, la vache, la souris, le rat et le poulet.

Sur le diagramme en bas, on voit ce qui est commun aux hommes, aux vaches, aux souris et aux rats et ce qui a changé: avec notamment 46 nucléotides identiques sur les 60, et par exemple seulement deux différences entre l’humain et la vache. Si on regarde une bande, on peut l’assimiler au ruban d’une machine de Turing et c’est le code interne de la machine qui interprète les nucléotides et qui fait la réplication de cet ADN ou ARN, selon. Que survienne un événement tel qu’une modification du champ magnétique, un rayonnement atomique, une action chimique, etc. cette réplication peut-être faussée et générer une autre séquence génétique. Sur une période très longue de quelques millions d’années et sur des millions d’individus, certaines séquences ainsi formées vont être viables et vont se développer si les conditions sont favorables. La probabilité est extrêmement faible mais sur de très longues périodes (ici des milliards d’années), un événement de probabilité très faible a une très forte probabilité de se produire. On tient là un modèle conceptuel qui permet ainsi de simuler les algorithmes.

(1) Eugene Paul Wigner 17/11/1902-01/01/1995, physicien hongrois naturalisé états-unien, Nobel de physique 1963.
(2) Voir sur http://arxiv.org/abs/1304.5604