Sciences de l’information : là où le temps sous-tend tant et tant  

En informatique, le temps est une variable omni-présente, mais sous des formes parfois inattendues qui, mal comprises, conduisent à de fâcheux contre-temps. En présentant les contenus d'Interstices qui parlent du temps, essayons de démystifier les différents concepts qui se relient au temps.

Prenons donc le temps de regarder deux facettes du temps :

• Temps logique, relatif, d'aucuns diront « temps de calcul », c'est bien ce concept de temps qui permet à un logiciel d'aller là où on l'attend.
• Temps physique, absolu, mesurable plus ou moins finement, ce concept-là est utilisé notamment pour le traitement du signal.

© INRIA / Photo Jim Wallace

1. Premier temps : le temps qui défie l'informatique

La notion du temps est intrinsèquement liée à l'informatique , puisqu'il est vite apparu que presque tous les calculs étaient possibles, mais que voilà... ils pouvaient durer incommensurablement longtemps ! Ainsi, à énumérer tous les cas possibles pour effectuer une opération, cela peut durer tant et tant... qu'au bilan, on aura perdu son temps.

Temps de calcul : entre jamais et trop longtemps

Les mécanismes de base de l'informatique sont les algorithmes . C'est par le nombre d'opérations élémentaires à exécuter pour réaliser la tâche qui a permis de les spécifier qu'est défini le temps de calcul. Ainsi, l'exemple suivant :

où la variable x prend la valeur 5 et y vaut 6, nécessite deux additions et deux affectations. (La valeur correspondant au résultat de la première addition est affectée à x, celle de la seconde à y). En tout, quatre opérations sont exécutées. De même, trier un tableau de n éléments nécessite un nombre d'opérations qui augmente avec n. Pour les algorithmes de tri peu évolués, ce nombre d'opérations est proportionnel à n² (le carré de n). Les algorithmes de tri les plus malins se contentent d'augmenter en n log₂n. Prenez l'annuaire téléphonique francilien : 10 millions d'entrées. La différence est énorme : les tris les plus malins utiliseront de l'ordre de 100 millions d'opérations (c'est beaucoup mais jouable) ; les autres plus de 100 mille milliards ! (là c'est perdu d'avance). À grande échelle, le temps se multiplie vite.

Où le temps explose

Mais il y a pire, la complexité algorithmique est parfois exponentielle. Un exemple concret permet de l'illustrer. Imaginons qu'une compagnie d'électricité cherche à déterminer le chemin le plus court pour relever les compteurs dans un petit village un peu tarabiscoté. À chaque carrefour, le releveur aura au minimum deux choix, disons donc pour simplifier qu'il en a deux (même si dans la réalité ce serait souvent un peu plus). Comment faire ? Eh bien, il suffit de faire partir plusieurs releveurs en même temps, un groupe de T releveurs, et à chaque carrefour, une partie du groupe ira à gauche, l'autre à droite et ainsi de suite, jusqu'à ce que le releveur (ou le groupe) le plus chanceux (celui qui de choix en choix aura pris le chemin le plus court) arrive au bout du parcours le premier et envoie un message à tous les autres : j'ai fini les amis ! Quel algorithme apparemment fructueux : il est si simple, et puis il va vite ! Avec un nombre T de releveurs suffisamment grand, nous avons résolu le problème (grâce au releveur le plus chanceux) en un temps égal au trajet le plus court. Merveilleux ? Presque. Où est le hic ? Le nombre T de releveurs ! Eh oui, si le village compte L carrefours et que le choix (simplifié) est binaire (partir à gauche ou à droite), le nombre de releveurs qu'il faudra au départ sera au moins de 2 x 2 x 2... x 2 (ceci L fois), sinon à un carrefour donné un releveur sera tout seul et ne pourra aller à la fois à gauche et à droite. Bref, il faut au moins : T > 2^L releveurs, et c'est énorme. S'il y a 10 carrefours, cela fait un peu plus de 1000 releveurs ; avec 100 carrefours (Paris en compte bien plus), plus de 1000 000 000 000 000 000 000 000 000 000 releveurs. Ingérable. Mais très riche en enseignement. C'est bien à cause de ce genre de problème que des algorithmes plus élaborés ont été proposés pour trouver le plus court chemin .

Complexité polynomiale et exponentielle

Un algorithme de tri a une complexité qui augmente avec la taille du problème, mais sans « exploser », c'est une complexité polynomiale. L'algorithme du plus court chemin tel que décrit précédemment a lui une complexité qui explose très vite en augmentant, une complexité exponentielle (la taille du problème L est en exposant). Le temps de calcul est explosif.

Et la très mauvaise nouvelle est que de nombreux problèmes intéressants à résoudre sont hélas exponentiellement compliqués (notamment tous les problèmes de recherche opérationnelle , qui consistent à chercher la meilleure solution d'un problème où il faut combiner des éléments : file d'attente, ordonnancement, etc.). On observe même un tel phénomène de complexité combinatoire dans un jeu aussi simple que le sudoku .

Complexité et taille mémoire

Comment simuler mes T releveurs sur un unique ordinateur ? En gardant en mémoire l'état de chaque releveur (ici le chemin qu'il a parcouru) et en simulant pour chacun tour à tour le fait qu'il arrive à un carrefour puis choisisse d'aller à gauche ou à droite, etc. Facile, mais... mais cela signifie qu'il faudra une taille mémoire qui elle aussi augmente proportionnellement à T. Le temps de calcul sur mon ordinateur unique va augmenter proportionnellement au nombre T de releveurs et proportionnellement au nombre de carrefours L. Au-delà de cet exemple, le lien entre temps de calcul et taille mémoire est parfois complexe. Plus le problème est compliqué, plus la taille mémoire et le temps de calcul augmentent (ici exponentiellement). En revanche, dans d'autres cas, garder en mémoire les résultats intermédiaires pour ne pas les recalculer limite le temps de calcul.

En pratique, les algorithmes sont analysés et modifiés de façon à minimiser le nombre d'opérations et d'accès mémoire. Pour diminuer les accès mémoire, il suffit parfois de changer l'ordre des calculs dans une boucle, ou d'utiliser judicieusement le contenu de la mémoire cache de la machine en chargeant à l'avance les données qui vont être utilisées dans les calculs à venir.

Un exemple classique de ce type d'astuce est l'implantation rapide de la transformée de Fourier discrète (FFT, pour Fast Fourier Transform). Un tel travail est nécessaire pour implanter efficacement un algorithme dans une architecture de calcul dédiée (comme les circuits de type FPGA ou Field Programmable Gate Array, qui sont des réseaux de circuits logiques à connexions programmables), ou même dans un processeur de signal (DSP). En effet, il faut non seulement implémenter le calcul le plus rapidement possible, mais aussi de manière suffisamment simple (avec une liste d'instructions spécifiques) pour qu'il puisse s'exécuter efficacement sur des architectures dédiées. Chercher une telle optimisation n'est certes pas sans risque .

Il y a toujours un compromis à faire entre temps de calcul et mémoire . C'est le cas tout particulièrement pour les algorithmes récursifs ou en programmation synchrone, dont il est question plus loin.

Complexité et parallélisme

Imaginons que plusieurs ordinateurs puissent fonctionner en parallèle, chacun simulant une partie de mes T releveurs. Cela va aller plus vite. Certes. Mais pas énormément. Car il faudrait ici un nombre exponentiellement grand d'ordinateurs, plus que le nombre total d'ordinateurs jamais construits. Le parallélisme est très utile pour économiser du temps de calcul pour des problèmes de complexité polynomiale, c'est beaucoup moins simple si elle est exponentielle. C'est même aujourd'hui un enjeu international sur les grilles informatiques .

Pour en savoir plus sur le parallélisme, nous vous proposons de télécharger un cours de l'École Polytechnique sur ce sujet, disponible en PDF (1 Mo).

Pourtant, des systèmes physiques pourraient permettre de briser cette barrière de la complexité : les ordinateurs quantiques . Dans ce cas, un nombre justement exponentiellement grand d'opérations élémentaires pourraient être effectuées simultanément, ainsi certains problèmes explosifs deviendraient... raisonnablement compliqués.

Être sûr qu'un temps de calcul est exponentiellement compliqué n'est pas forcément une malédiction : c'est l'inverse dans le cas de la cryptographie . Quand vous protégez vos données avec un mot de passe, vous êtes acquis à l'idée que tout le monde pourra y accéder, pourvu qu'il ait la chance de tomber sur le bon mot de passe, ou qu'il essaie toutes les possibilités. C'est bien le fait qu'essayer toutes les possibilités prend du temps (un temps de calcul explosif) qui protège vos données. Un exemple historique, la machine Enigma , illustre bien ce fait.

Où le temps devient infiniment grand

Le temps de calcul peut être encore pire qu'explosif... il peut être infini !

Voici un exemple tout à fait idiot :

Pour cette opération, x vaut d'abord 1, puis tant qu'il est supérieur à 0, ce qui reste toujours le cas, il va augmenter de 1, etc. Et l'opération ne s'arrêtera jamais... jusqu'à ce que la valeur devienne suffisamment grande pour bloquer le calcul !

Faut-il être bête pour écrire un algorithme pareil. Certes. Mais combien de fois votre ordinateur familial ne s'est-il pas bloqué indéfiniment sur une boucle aussi idiote que celle-ci sûrement, mais d'une complexité inouïe à détecter... car ce n'est pas un algorithme d'une ligne, mais des centaines de milliers de lignes d'algorithmes qui font tourner votre ordinateur ! Détecter ces « boucles » est un problème un peu plus que compliqué !

Comme pour le problème de notre releveur de compteurs, il faut sûrement explorer tous les cas possibles, cela semble donc exponentiellement compliqué. En un sens oui. Mais là nous parlons de boucle infinie, donc explorer « tous » les cas possibles conduit à explorer... un espace sans limite. C'est un problème indécidable .

Cette notion, point dur en sciences de l'information , a été formalisée il y plus d'un demi-siècle par un logicien : Gödel . Elle est au cœur des problèmes les plus intenses de cette science.

S'assurer qu'un algorithme général ne bouclera pas est un problème indécidable, pour concevoir des logiciels sûrs il faut alors se mettre dans un cadre plus précis, où toutes les opérations ne sont pas permises. Démontrer qu'un algorithme va réaliser l'opération souhaitée dans un temps imparti est un problème crucial (par exemple en chirurgie assistée par ordinateur ) mais hélas, indécidable. Il a été pourtant résolu dans des cas précis .

Beaucoup de problèmes de décisions sont semi-décidables : si la réponse est « non », alors la réponse se trouve en temps fini, si la réponse est « oui », alors impossible de s'en assurer, sauf à exécuter un algorithme dont le temps de calcul est infiniment long. Pour avoir tort, c'est facile, il suffit de se tromper, mais pour avoir vraiment raison, il faut attendre un temps illimité, puisqu'un contre-exemple pourra toujours surgir inopinément. Cet état de fait, présenté ici en une phrase, correspond à un raisonnement rigoureux.

Informatique en temps réel : rien ne sert d'aller vite, il faut juste être à temps

Beaucoup de problèmes informatiques pratiques se résolvent fort heureusement sans exploser en temps. On parle alors de temps réel, pour dire que le résultat du calcul va arriver à temps.

L'exemple le plus célèbre est celui de la prédiction des phénomènes météorologiques où il y a quelques années déjà le temps du lendemain matin était prédit avec précision... en trois jours de calcul ! Dans ce cas, c'est la technologie qui a permis de gagner sur le temps. Avec la loi de Moore , le temps de calcul augmente assez vite pour rendre possible ce qui ne l'était pas hier, sans toutefois oublier les grands problèmes cités précédemment. Mais ne nous trompons pas : la clé de la performance n'est pas essentiellement technologique.

Ce sont des méthodes modernes d'analyse statique de pire temps d'exécution de programmes qui permettent aujourd'hui de s'assurer de la performance de tel ou tel calcul.

De même, les traitements qui réclament de très grands calculs comme l'exploration et l'analyse des textes des génomes sont rendus possibles tant par l'augmentation de la vitesse des processeurs que par les progrès de l'algorithmique qui propose des méthodes de plus en plus performantes.

Robot marcheur BIP. Le but n'est pas de reproduire le fonctionnement du corps humain, ce qui dépasserait les capacités de la technologie actuelle, mais de reproduire les principales caractéristiques du système locomoteur. © INRIA / Photo Jim Wallace

L'interaction avec un automatisme, par exemple un système robotique , est rendue possible uniquement si le temps de calcul peut-être très précisément borné, c'est le temps réel au sens strict. Les méthodes de programmation synchrone permettent de garantir non seulement le résultat du calcul, mais aussi l'instant où ce résultat sera disponible. Pour cela, tous les choix possibles ont pu être prévus à l'avance, mémorisés, ce qui conduit à un algorithme qui réagit quasiment sans délai. On parle d'automate à états finis, et les transitions d'un état à un autre ont été compilés dans une table. On est dans un cas limite où l'espace mémoire permet de gagner sur le temps. Les théoriciens de ces méthodes supposent d'ailleurs que l'ordinateur réagit... infiniment vite ! D'où le nom de synchrone. Et cette simplification, finalement bien réaliste dans ce contexte, leur permet de déduire beaucoup de propriétés temporelles très importantes pour garantir des logiciels sûrs. Ces recherches théoriques, non seulement permettent de garantir le temps, mais aussi, grâce au cadre logique rigoureux, de garantir d'autres propriétés sémantiques.

Pour en savoir plus sur la programmation synchrone, vous pouvez télécharger le rapport de recherche fondateur, disponible en PDF (1 Mo).

Temps réel ne veut pas forcément dire « aller vite » : interagir avec un utilisateur nécessite des temps de réaction de quelques dizaines de millisecondes, avec un système mouvement de quelques centaines de microsecondes, avec un système végétal de plusieurs minutes. Non seulement l'échelle de temps varie, mais sa précision aussi : dans le réseau internet , des temps d'attente sporadiques sont acceptables, en informatique médicale , c'est inenvisageable.

Par de nombreux aspects, le temps est présent dans les travaux de recherche en sciences de l'information, à des échelles très différentes. La simulation de la croissance des plantes , où il faut modéliser l'évolution au cours de très longues périodes de temps, en est un exemple extrême. Lors de l'analyse du mouvement au niveau de la perception visuelle, les variables liées au temps, comme la vitesse, deviennent l'objet même de l'étude.