Cette publication est accessible gratuitement
Lire

Définition de : INFORMATION, mathématique

De
6 pages
Article publié par Encyclopaedia Universalis INFORMATION, mathématique Quand on parle d'information, on pense souvent « information ayant une certaine valeur », ou « information pouvant servir à... ». Existe-t-il une théorie générale de l'information ? La théorie de l'information de Shannon (1949) a souvent été présentée comme cette théorie attendue. On admet aujourd'hui que les résultats qui en ont été tirés en biologie ou en informatique ne sont pas à la mesure des ambitions annoncées. Une seconde théorie de l'information, dite théorie algorithmique de l'information et due indépendamment à Andreï Kolmogorov et Gregory Chaitin (1965), se fonde sur la théorie du calcul d'Alan Turing (1936). Nous allons voir que ces deux théories sont liées l'une à l'autre. Les exemples suivants de suites de caractères contenant de l'information doivent faire réfléchir : (a) la suite des caractères du texte du roman Les Misérables de Victor Hugo ; (b) la liste des emplacements des lance-missiles américains ; (c) une table de logarithmes ; (d) le génome complet d'un virus ; (e) un disque compact avec les concertos pour piano de Chopin ; (f) le programme du traitement de texte utilisé par l'auteur pour écrire cet article, tel qu'il est dans la mémoire de son ordinateur ; (g) le programme de ce même traitement de texte avant qu'il n'ait été compilé, qu'on appelle « programme source ».
Voir plus Voir moins
INFORMATION, mathématique

Quand on parle d'information, on pense souvent « information ayant une certaine valeur », ou « information pouvant servir à... ». Existe-t-il une théorie générale de l'information ? La théorie de l'information de Shannon (1949) a souvent été présentée comme cette théorie attendue. On admet aujourd'hui que les résultats qui en ont été tirés en biologie ou en informatique ne sont pas à la mesure des ambitions annoncées. Une seconde théorie de l'information, dite théorie algorithmique de l'information et due indépendamment à Andreï Kolmogorov et Gregory Chaitin (1965), se fonde sur la théorie du calcul d'Alan Turing (1936). Nous allons voir que ces deux théories sont liées l'une à l'autre.

Les exemples suivants de suites de caractères contenant de l'information doivent faire réfléchir : (a) la suite des caractères du texte du roman Les Misérables de Victor Hugo ; (b) la liste des emplacements des lance-missiles américains ; (c) une table de logarithmes ; (d) le génome complet d'un virus ; (e) un disque compact avec les concertos pour piano de Chopin ; (f) le programme du traitement de texte utilisé par l'auteur pour écrire cet article, tel qu'il est dans la mémoire de son ordinateur ; (g) le programme de ce même traitement de texte avant qu'il n'ait été compilé, qu'on appelle « programme source ».

Dans chaque cas, il s'agit d'objets possédant un contenu en information et ayant une certaine valeur : ils ont pu être vendus et achetés, on a dépensé de l'argent pour les produire, on continue d'en dépenser pour les conserver. Le contenu brut d'information pour chacun de ces objets est donné par le nombre de bits (éléments de mémoire binaire, 0 ou 1) nécessaires pour enregistrer la chaîne de caractères dans la mémoire d'un ordinateur quand on ne lui fait subir aucun traitement particulier. Le contenu brut d'information d'une chaîne de caractères s de longueur n est n si s ne comporte que des 0 et des 1 et c'est n log m /log 2 si la chaîne comporte des caractères pris parmi m. Dans nos exemples, l'objet ayant le contenu brut d'information le plus grand est le disque compact. Celui ayant le plus de valeur marchande est le programme non compilé de traitement de texte. Celui ayant le moins de valeur aujourd'hui est sans doute la table de logarithmes.

Bien sûr, le contenu brut d'information ne détermine pas la valeur de l'information. La valeur de l'information d'une chaîne de caractères est relative à un certain but et à une certaine situation. Nous noterons Val(s, B) la valeur de l'information contenue dans s relativement au but B. Nous allons découvrir qu'en précisant le but B on obtient différentes théories, dont la théorie de l'information de Shannon et la théorie algorithmique de l'information.

Théorie algorithmique de l'information

Si l'on se fixe pour but de compresser la chaîne de caractères s et si l'on suppose qu'on dispose pour cela d'une machine M, alors la valeur de l'information de s est la longueur du plus petit programme (écrit en binaire) qui, lorsqu'il fonctionne dans M, reconstitue la chaîne s.

La puissance des machines n'est pas sans limite. Dès qu'on a affaire à des machines d'une certaine puissance, leur puissance théorique est la même. C'est là la découverte fondamentale de Turing en 1936 : il y a des mécanismes universels de calcul et n'importe quel ordinateur contemporain est un tel mécanisme universel. Si l'on se donne un mécanisme universel de calcul, la notion de plus petit programme engendrant s ne dépend pas de la machine utilisée, ou plus précisément, ne dépend de cette machine que par une constante additive qu'on peut négliger en première approximation si on traite des suites assez longues. La découverte de ce résultat d'indépendance fonde la théorie algorithmique de l'information.

La notion de valeur de l'information qu'on obtient est particulièrement séduisante. C'est la notion de complexité de Kolmogorov ou de contenu en information de Kolmogorov. Elle correspond à notre définition générale lorsqu'on prend comme but B : [compresser pour la machine universelle M]. Cette notion d'information est sans doute la moins arbitraire de toutes et c'est à elle de préférence que toute théorie générale doit se référer.

Théorie de Shannon

Lorsque le but poursuivi est de transmettre une chaîne de caractère s à un récepteur disposant de la connaissance des fréquences p(i) des lettres de l'alphabet {a1a2, ..., an}, on définira la valeur en information de s relativement à p(i) et ai, valeur appelée entropie et notée E(s, {p(i)}), par :

Dans cette conception de l'information, on suppose implicitement que le récepteur est capable de faire certains calculs pour reconstituer s à partir de ce qu'on lui transmet. En définitive, la machine M qui fait le décodage peut être prise comme référence et l'on découvre alors que la théorie de Shannon doit être vue comme une version probabiliste de la théorie algorithmique de l'information. On démontre d'ailleurs que le contenu moyen d'information de Kolmogorov des chaînes de caractères s de longueur n, pondérées par les probabilités résultant des fréquences supposées p(i) pour les ai, K(s, {p(i)}) vérifie la relation : |E(s, {p(i)}) – K(s, {p(i)})| < constante.

La théorie de l'information de Shannon est donc aussi une théorie de l'information par compression, qui, au lieu de considérer des suites quelconques, suppose que les suites qu'on transmet vérifient certaines propriétés statistiques. Finalement, la théorie de Shannon est une théorie du contenu en information relativement à un but de compression et à une certaine distribution statistique des suites. Ce n'est donc pas une théorie de l'information limitée au problème de la transmission, comme on le dit parfois.

La théorie de l'information de Shannon est compatible avec celle de Kolmogorov. Chacune a un rôle à jouer et, par exemple, dans la théorie de la mesure et de l'entropie physique de Wojciech Zurek (1989), c'est le jeu complémentaire des deux théories qui est considéré. Pour Zurek, une situation pour laquelle on dispose de peu d'éléments est assimilée à la situation typique dans l'ensemble des situations compatibles avec ce que l'on sait (utilisation de la théorie de Shannon), puis, au fur et à mesure des précisions qu'on acquiert par des mesures, la théorie de Kolmogorov prend le relais et finit par devenir prépondérante.

Valeur de l'information

Dans nos exemples, nous avons envisagé un programme de traitement de texte. Il est clair que la compilation d'un programme source en un programme exécutable crée de l'information de valeur. Le but recherché est double : avoir une forme compacte d'un algorithme rapide réalisant une famille de calculs. Notons que :

– plus le code est rapide plus la compilation possède de valeur ;

– plus le code compilé est compact plus il a de la valeur (aujourd'hui, contrairement à ce qui se passait dans les années 1970, on favorise la rapidité aux dépens de l'espace) ;

– plus nombreux sont les problèmes traités par le programme compilé, plus sa valeur est grande.

La valeur de l'information contenue dans un programme compilé est un mélange de ces trois qualités (rapidité, compacité, variété des problèmes traités), et d'autres encore comme l'originalité, la portabilité, etc. La valeur de l'information d'un programme compilé ne se laisse donc pas réduire à un seul aspect : le contenu en information d'un programme compilé n'est ni l'information algorithmique de Kolmogorov, ni l'information donnée par la théorie de Shannon. De même, si l'on considère que le but poursuivi est de nature pratique, par exemple survivre dans un milieu donné, ou gagner le plus possible d'argent tel jour à la Bourse de Paris, alors la valeur de l'information d'une chaîne de caractères s se mesurera en fonction du but. Une information de grande valeur, ce sera l'endroit où aller chercher tel aliment, ou ce sera le nom de l'action boursière qui va monter. Aucune théorie générale de l'information ne prend en compte tous les aspects pragmatiques déterminant la valeur des chaînes de caractères. Que les théories générales (comme celles de Kolmogorov ou Shannon) puissent jouer des rôles particuliers en physique, en biologie ou ailleurs ne fait pas de doute, mais il faut garder à l'esprit qu'aucune ne constituera jamais la théorie générale de l'information.

Auteur: Jean-Paul DELAHAYE
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin