Complexité Algorithmique - Kolmogorov

    <p class=default>
      
        <b>La notion de complexité définie par Kolmogorov</b>
      
    <br/>

      
        Reprenons d’abord l’exposé des travaux de Kolmogorov. C’est sans doute dans sa publication 
        de 1965 qu’il perçoit le mieux toute la richesse de la définition qu’il a choisie pour 
        mesurer quantitativement l’information. Le texte de sept pages qu’il fait paraître porte 
        pour titre “ Trois approches de la définition quantitative de l’information ”. Il commence 
        par décrire les deux premières, qu’il trouve “ communes ”, l’approche combinatoire et 
        l’approche probabiliste. Dans le premier cas, si une variable 
      
      
        <i>x</i>
      
      
         prend ses valeurs dans un ensemble X contenant 
      
      
        <i>N</i>
      
      
         éléments, on peut commencer par définir l’information par H(
      
      
        <i>x</i>
      
      
        ) = log2 
      
      
        <i>N</i>
      
      
        . C’est cette définition qui convient pour l’analyse de l’entropie associée à un texte, 
        une fois que l’on a défini des fréquences. Commentant plus tard cette approche 
        combinatoire, Kolmogorov montre que c’est ainsi que l’on peut lire la publication de 
        Hartley de 1928. On peut d’ailleurs retrouver la définition de Shannon suivant cette 
        approche, en s’appuyant sur le concept de fréquence, et l’intérêt ‘pédagogique’ de cette 
        démarche (souci constant dans l’śuvre du mathématicien) est de montrer qu’il est possible 
        de définir quantitativement l’information sans introduire les probabilités.
      
      
        <u>fn 3 <ch9bft.htm></u>
      
      
         
      
      
        
      
    <br/>

      
        Dans le cas justement de l’approche probabiliste, il souligne le paradoxe selon lequel 
        l’information apportée par une variable sur une autre peut être négative et que 
        l’assimilation entre fréquences et probabilités n’est que rarement justifiable. Il conclut 
        ainsi au sujet de cette approche : “ Si quelque chose ne va pas ici, c’est que le problème 
        se situe dans le vague de nos idées sur les relations entre théorie mathématique des 
        probabilités et événements aléatoires réels en général. ”
      
      
        <u>fn 4 <ch9bft.htm></u>
      
      
         Pour calculer la quantité d’information contenue dans 
      
      
        <i>Guerre et paix</i>
      
      
        , explique-t-il, on est dans la même insurmontable difficulté que lorsqu’on s’intéresse à 
        “ la question à la mode de la “quantité d’information héréditaire”. ” Kolmogorov se montre 
        en fait tout aussi réticent que Shannon quant aux applications de ces définitions 
        scientifiques de l’information qui ne respectent absolument pas les conditions du 
        formalisme mathématique qui les accompagnent (que l’on pense aux processus de Markov et 
        aux conditions d’ergodicité). 
      
      
        
      
    <br/>

      
        C’est la troisième approche, l’approche “ algorithmique ” qui semble pour lui la plus 
        féconde et la plus novatrice. Un point essentiel est que l’information peut alors être 
        définie au niveau individuel, et non en référence à toute une collection de messages comme 
        dans la théorie probabiliste de Shannon qui repose, en définitive, sur la théorie de la 
        mesure. L’information apportée par une série de nombres sur une autre est mesurée à une 
        constante additive près en fonction de l’algorithme utilisé pour construire la seconde 
        série et Kolmogorov se rapporte sans plus d’explications aux “ méthodes universelles de 
        programmation ”. Si ces méthodes restent indéterminées, Kolmogorov définit tout de même la 
        complexité 
      
      
        <i>K</i>
      
      
        (x)
      
      
        <u>fn 5 <ch9bft.htm></u>
      
      
         en fonction de la taille minimale d’un tel programme (il pose simplement que la 
        complexité est infinie lorsqu’un tel minimum n’existe pas) et estime ainsi qu’il est 
        possible selon cette approche de définir l’information apportée par un texte en tenant 
        compte de connaissances 
      
      
        <i>a priori</i>
      
      
         sur le style de l’auteur, le contenu narratif etc., et qu’on peut imaginer parvenir “ en 
        principe à une définition correcte de la “quantité d’information héréditaire” ”, même s’il 
        reste sceptique sur ce dernier point.
      
      
         
      
    <br/>

      
        Là encore, à la fin de sa publication, Kolmogorov fait part de ses travaux en cours et 
        annonce en l’occurrence une étude à venir sur les relations entre la complexité nécessaire 
        du programme de cette machine universelle et la “ difficulté autorisée ”, ce qui suppose 
        par exemple de s’intéresser au temps dont un programme a besoin pour s’arrêter. Ne perdant 
        pas de vue une analyse plus générale de la notion de hasard, il affirme que l’approche 
        algorithmique permet non seulement de définir l’information indépendamment des 
        probabilités (comme dans l’approche combinatoire) mais aussi d’entrevoir un moyen de “ 
        fournir une nouvelle base au calcul des probabilités ”.
      
      
         
      
    <br/>

      
        
      
    </p>