Ecologie Informatique

Au fait, qu’est-ce que l’information ? Comment la relier aux autres grandeurs de base du monde physique comme le temps ou l’énergie ? Ces questions qui peuvent paraitre de nature philosophiques ont des retombées pratiques évidentes pour les fabricants de puces : fondamentalement, faut-il de l’énergie pour réaliser une addition ? Combien ? Et le temps ? Est-il possible de réaliser des opérations logiques “instantanées” comme le tri des spaghettis le laisse supposer ?

Ce chapitre aborde toutes ces intéressantes questions.

5.1 Le compromis temps/mémoire

Selon Lavoisier “rien ne se perd, rien ne se crée, tout se transforme”. Il n’a jamais pu prouver qu’il avait raison, aujourd’hui encore on n’en est pas certaines, mais son principe se vérifie tous les jours aussi bien que la loi de Murphy (“si quelque chose peut aller de travers, ça le fera”).

Il en va de même pour la loi de l’informaticien inconnu qui dit “le temps d’exécution et l’occupation de mémoire sont interchangeables”. Il est facile de voir que c’est vrai dans des cas simples :

1. si un algorithme rapide produit beaucoup de données, on préfère le ré-exécuter plutôt que de stocker les données.
2. à l’inverse, on peut stocker les résultats d’un algorithme lent dans une mémoire “tampon” et les restituer directement au lieu d’exécuter l’algorithme une seconde fois.

5.2 Compression

Notre “informaticien inconnu” nous dit que l’on peut remplacer des données par un programme qui les produit. On ne peut réaliser un bénéfice que si ce programme occupe une place mémoire plus faible que les données. Comme “tout n’est que bits”, on peut considérer le programme comme l’équivalent « comprimé » de données. Tout utilisateur de PC connait les fichier « .zip » contenant des données comprimées. Considérons par exemple ces 300 chiffres:


314159265358979323846264338327950288419716939
937510582097494459230781640628620899862803482
534211706798214808651328230664709384460955058
223172535940812848111745028410270193852110555
964462294895493038196442881097566593344612847
564823378678316527120190914564856692346034861
045432664821339360726024914127372458700660631

Cette suite a l’air parfaitement aléatoire. D’ailleurs, un programme de compression du type Lempel-Ziv (.zip) ne parvient à la comprimer que d’un facteur 3, proche des 3bits ½ par octet qui suffisent à représenter un chiffre de 0 à 9. Pourtant, certains reconnaitront les premières des 15′000 décimales de pi que le petit programme C suivant calcule à une vitesse phénoménale :

a[52514],b,c=52514,d,e,f=1e4,g,h;
main(){for(;b=c-=14;h=printf("%04d",e+d/f))
for(e=d%=f;g=--b*2;d/=g)
d=d*b+f*(h?a[b]:f/5),a[b]=d%--g;}

Or ce petit programme ne fait que 133 caractères, soit 100 fois moins que les résultats qu’il produit, et 30 fois moins que ces résultats comprimés par un programme qui ne sait pas ce qu’il comprime comme le fameux “zip”.

Kolmogorov s’est intéressé à ceci et a défini la “complexité de Kologorov” d’une information comme la taille minimale du programme capable de la produire. L’avantage n’est pas évident sur une donnée aussi simple, mais Kolmogorov ne vise pas de but pratique. La complexité de Kolmogorov est même une notion extrêmement théorique, inutilisable car on ne peut pas la déterminer autrement qu’en essayant successivement tous les programmes.

5.3 Irréversibilité et destruction d’information

La tortue de Turing souffre d’un grave défaut : elle est incapable de fonctionner à l’envers, car elle ne se rappelle pas les anciennes valeurs des cases du ruban lorsqu’elle y écrit. Un ordinateur n’est donc pas non plus capable d’effectuer un programme depuis la fin vers le début : un traitement informatique est “irréversible”, car plupart des opérations arithmétiques et logiques sont irréversibles : une fois qu’on a additionné 3 et 7 pour obtenir 10, pas moyen de retrouver 3 et 7 à partir du résultat, sauf si on a explicitement pris la précaution de mettre un des deux nombres en sureté pour pouvoir effectuer une soustraction. Dès qu’un résultat prend moins de place en mémoire que les données qui ont servi à le calculer, on est certain d’avoir perdu de l’information.

Si la taille des données est conservée, ce n’est pas forcément mieux. Par exemple, une liste occupe la même place en mémoire qu’elle soit triée ou non, et de nombreux algorithmes sont plus rapides sur une liste triée, ce qui laisse supposer qu’elles ne contiennent pas la même “quantité d’information”. Intuitivement on aurait tendance à penser que la liste triée contient plus d’information puisqu’elle est plus facile à exploiter, d’autant qu’elle a couté du temps de calcul au moment de son tri.

Pour en avoir le coeur n’est, j’ai posé la question sur un forum internet consacré à l’informatique théorique : “est-ce qu’une liste triée contient vraiment plus d’information qu’une liste non triée ?” Un érudit professeur m’a répondu : “ce contient d’ est information liste liste non plus qu’ triée triée une vraiment ?”. J’ai mis un moment à comprendre la profondeur de cette réponse : ma question, une fois les mots triés par ordre alphabétique, était devenue incompréhensible, et contenait donc moins d’information que la phrase originale !

En fait, aucune opérations effectuées par un ordinateur ne crée de l’information ! Un ordinateur copie, arrange, organise, manipule, calcule ou au mieux conserve de l’information, mais n’en crée jamais, sous aucune forme.

Si les algorithmes sont plus rapides sur une liste triée que sur une liste non triée, c’est parce que le tri a déjà effectuée une partie du travail que l’algorithme de recherche ou d’insertion va poursuivre méthodiquement : la destruction systématique de l’information qu’on lui a confiée !

5.4 Informatique et physique

La section précédente laisse entrevoir des relations entre l’informatique et la thermodynamique, la science qui étudie les échanges thermiques et qui aboutit entre autres à établir que “l’entropie augmente” dans tout système physique : une fois l’eau chaude mélangée à l’eau froide, plus moyen d’inverser le processus : l’Univers devient progressivement tiède.
Au XIXème siècle, le théoricien de l’électromagnétisme Maxwell imagina une expérience célèbre. Un récipient clos est séparé en deux volumes égaux par une paroi percée d’un tout petit trou. Le trou peut être obturé par un clapet muni d’un système restituant à la fermeture l’énergie nécessaire à l’ouvrir. Un petit “démon de Maxwell” se tient près du trou, ouvre le clapet lorsqu’une molécule de gaz se dirige du compartiment de droite vers celui de gauche en passant par le trou, et referme en vitesse le clapet si une molécule se dirige en sens inverse. Voilà, dit Maxwell, mon démon comprime le gaz dans une moitié du récipient aussi sûrement qu’avec une pompe, mais sans dépenser d’énergie : l’intelligence du démon la remplace !

Maxwell se doutait bien que quelque chose clochait dans son expérience, mais il fallut attendre les années 1990 pour qu’on trouve quoi : pour mesurer la trajectoire des molécules avec suffisamment de précision, il faut que le démon les “éclaire”, ou interagisse avec eux au sens de la mécanique quantique, donc dépense de l’énergie. Et là arrive la cerise sur le gâteau : l’énergie totale que doit dépenser le démon de Maxwell est rigoureusement identique à celle que consommerait une simple pompe !

5.5 Certitude quand tu nous tiens

Sur un groupe usenet dévolu aux algorithmes, quelqu’un demandait récemment de l’aide pour dire avec certitude si un nombre de 20 chiffres était ou n’était pas premier. Un professeur de maths lui demanda s’il acceptait le risque qu’un rayon cosmique change la valeur d’un bit pendant le calcul et fournisse un résultat faux. Un calcul approximatif montrait que la probabilité que ça arrive pendant les heures nécessaires au calcul était d’une chance sur 10⁴⁰. La personne répondit évidemment que ce risque était négligeable. Alors le professeur lui conseilla un algorithme probabiliste, qui en moins de 5 minutes fournissait un résultat avec un risque d’erreur inhérent à l’algorithme de 10^-50, en arguant qu’il fournissait un résultat plus rapidement un résultat plus fiable que l’algorithme déterministe!

5.6 Eloge de la complexité

L’impossibilité pratique de résoudre certains problèmes en raison de leur très forte complexité peut paradoxalement être utile. Le cryptage, pierre angulaire de la sécurité informatique, repose sur l’impossibilité d’effectuer certains algorithmes en un temps raisonnable. Les méthodes modernes dites « à clef révélée » comme PGP ou RSA utilisent de manière géniale quelques concepts développés plus haut dans ce chapitre.

On procède ainsi :

1. Bertha souhaite recevoir des messages en toute sécurité. Elle cherche deux nombres premiers assez grands (typiquement 64 bits chacun, soit de l’ordre de 10^20). Ceci peut se faire en quelques minutes grâce à l’algorithme probabiliste mentionné au paragraphe « Certitude quand tu nous tiens », avec une probabilité e se tromper totalement négligeable.
2. Bertha multiplie en quelques secondes les deux nombre pour en obtenir un de 128 bits, appelé « clef publique » parce que Bertha peut le communiquer sans précaution particulière aux personnes susceptibles de lui écrire. En effet, l’algorithme capable de retrouver les deux facteurs premiers à partir de la clef publique a une complexité exponentielle, et prendrait des mois, voire des années.
3. Si Alfred veut transmettre un message à Bertha, il le divise en paquets de bits qui sont combinés avec la clé par des algorithmes que nous ne détaillerons pas ici, mais qui effectuent grosso-modo une multiplication avec la clé puis effectuent des opérations « irréversibles » comme de ne conserver que le reste de divisions bien pensées, ce qui détruit irrémédiablement 128 bits. La puissance de ces méthodes est ici : même Alfred serait incapable de décoder son propre message !
4. Pour décoder, il faut absolument posséder les deux facteurs premiers : seule Bertha en est capable !