"Complexité" en informatique

15 juin 2002

(cf. "Complexité et complication") 

En informatique, on dit qu’une opération est « complexe » si elle est logiquement possible mais en pratique irréalisable.

Une première forme de « complexité » informatique provient de la représentation des nombres dans la mémoire de l’ordinateur. Celle-ci ne pouvant contenir qu’une quantité limitée de chiffres, les calculs informatisés portent sur un sous-ensemble des nombres rationnels, approximations des nombres réels. La précision des calculs est donc limitée même si le nombre de chiffres que contient la mémoire est élevé. Il en résulte de grandes difficultés mathématiques ([Knuth] vol 2 p. 229).

Une deuxième forme de « complexité » informatique est liée au nombre de calculs élémentaires que nécessite une opération. En notant n le cardinal de l’ensemble sur lequel on travaille, on dira que la « complexité » est linéaire si elle demande de l’ordre de n calculs élémentaires, quadratique si elle en demande de l’ordre de n², « exponentielle » si elle en demande de l’ordre de eⁿ ou, pire, de nⁿ.

Si par exemple il faut réaliser le calcul élémentaire sur chaque couple d’éléments de l’ensemble, la « complexité » est quadratique car le nombre des couples est égal à n(n – 1)/2. S’il faut calculer sur chacune des parties de l’ensemble, la « complexité » est exponentielle car le nombre des parties est égal à 2ⁿ. Enfin, si l’on doit calculer sur chacune des permutations des éléments de l’ensemble, leur nombre est n ! (factorielle de n) et la « complexité » est alors de l'ordre de nⁿ car n! ~ (2πn)^½(n/e)ⁿ (formule de Stirling, [Knuth] vol 1 p. 45).

Certains problèmes à la formulation simple peuvent exiger une durée de calcul de l’ordre de l’âge de l’univers : c’est le cas du « problème du commis voyageur » dès que n atteint quelques dizaines[1] (pour trouver l’itinéraire optimal passant par plusieurs villes il faut calculer la longueur de n! itinéraires).

La « complexité » permet d’évaluer la faisabilité d’un calcul : si n dépasse quelques centaines (c’est le cas de la plupart des bases de données d’une entreprise), un calcul linéaire sera facile, un calcul quadratique difficile et un calcul exponentiel impossible. L’informatique rencontre ici une limite (les traitements impossibles). Le programmeur qualifié arrive parfois à rendre possible un traitement qui, programmé de façon sommaire, aurait été impossible ou difficile : s’il s’agit par exemple de faire un tri, un calcul rustique sera quadratique mais un calcul bien conçu sera d’ordre nLog(n) seulement.

Une troisième forme de « complexité » informatique provient des limites de la logique elle-même : comme l'a démontré Gödel, aucun système logique ne peut contenir la démonstration de toutes les vérités logiques. Le domaine de la pensée pure est donc lui aussi complexe, puisque aucun système fini ne peut en rendre compte (cf. petit résumé du théorème de Gödel : il résulte de ce théorème qu'il est impossible de mettre au point un programme qui serait capable de vérifier tous les programmes). 

*

*  *

La « complexité » informatique n’a rien à voir avec la complexité du réel (sauf sous la dernière des trois formes de « complexité » ci-dessus). En effet, même si l’opération qui consiste à répéter un grand nombre de fois un calcul élémentaire demande un temps très long, elle n’est pas au plan logique plus complexe que le calcul élémentaire lui-même, et celui-ci est aussi simple que l’idée qui a guidé sa conception. Il en est de même pour les difficultés mathématiques liées à la représentation des nombres réels par des nombres rationnels. La « complexité » informatique est un homonyme de la complexité du réel. C’est pourquoi nous avons utilisé les guillemets pour la noter.

Retour à "Sortir de l'embarras"