Introduction
xvii
quand l’environnement change – de la charge du système à un moment donné
(toute observation modifie le système observé), etc. De plus, pour mesurer les
performances d’un système il faut l’avoir déjà réalisé : comment faire, si nous
voulons les prédire avant même la réalisation ? Faire des choix de conception
entre plusieurs possibilités ?
– Les simulations peuvent elles aussi dépendre de la machine, de l’art de la
personne qui a programmé la simulation, etc. Elles sont moins liées à un système
existant que les mesures, et sont intéressantes pour obtenir des analyses ou des
prédictions lorsque nous ne pouvons pas construire de modèle mathématique, ou
qu’un modèle précis est trop complexe pour être exploitable.
– Les analyses théoriques fournissent des théorèmes ; une fois mis en évidence,
le coût « théorique » est indépendant de l’art du programmeur et de la machine.
Cette approche demande la maîtrise d’outils mathématiques parfois sophistiqués.
Les résultats fournis sont idéalement complétés par des mesures ; par exemple, si
un algorithme nécessite n 2 opérations unitaires (lecture de symbole, comparaison
de clés, envoi de message) où n est un paramètre connu du système (nombre
de symboles à lire, de données à trier, d’agents à synchroniser), encore faut-il
connaître, pour une machine donnée, le temps pris par une opération unitaire
pour évaluer la durée d’exécution de cet algorithme.
Le présent ouvrage se place dans le cadre des analyses théoriques, et s’intéresse
à des aspects précis de parties d’un système informatique : l’analyse fine du
comportement d’un algorithme, agissant sur une structure de données arborescente.
Il y a plusieurs manières d’envisager cette analyse :
– soit nous nous intéressons aux cas extrémaux, i.e. au comportement de
l’algorithme dans le pire (ou le meilleur) des cas ;
– soit nous cherchons plutôt à caractériser un comportement moyen, ou mieux
encore la distribution de probabilité d’un paramètre du système.
La première approche conduit par exemple à identifier des classes de problèmes
résolubles dans le pire des cas en un temps polynomial en la taille des données, et
d’autres qui ne le sont pas : c’est la « théorie de la complexité ». La seconde repose
sur l’idée que le comportement d’un algorithme est souvent caractérisé de façon
plus pertinente par ses performances sur la plupart des données d’entrée que sur des
cas exceptionnels. C’est ce qui est couramment appelé « analyse d’algorithmes » ou
(de façon indûment restrictive) « analyse en moyenne », et c’est ce qui sous-tend les
analyses présentées dans ce livre.
Une démarche générale
Prenons donc un algorithme, c’est-à-dire une méthode de résolution pour un certain
problème, par exemple le tri d’un grand nombre de données, ou la recherche d’une
valeur dans un ensemble de grande taille. Cet algorithme prend en entrée des
xvii
quand l’environnement change – de la charge du système à un moment donné
(toute observation modifie le système observé), etc. De plus, pour mesurer les
performances d’un système il faut l’avoir déjà réalisé : comment faire, si nous
voulons les prédire avant même la réalisation ? Faire des choix de conception
entre plusieurs possibilités ?
– Les simulations peuvent elles aussi dépendre de la machine, de l’art de la
personne qui a programmé la simulation, etc. Elles sont moins liées à un système
existant que les mesures, et sont intéressantes pour obtenir des analyses ou des
prédictions lorsque nous ne pouvons pas construire de modèle mathématique, ou
qu’un modèle précis est trop complexe pour être exploitable.
– Les analyses théoriques fournissent des théorèmes ; une fois mis en évidence,
le coût « théorique » est indépendant de l’art du programmeur et de la machine.
Cette approche demande la maîtrise d’outils mathématiques parfois sophistiqués.
Les résultats fournis sont idéalement complétés par des mesures ; par exemple, si
un algorithme nécessite n 2 opérations unitaires (lecture de symbole, comparaison
de clés, envoi de message) où n est un paramètre connu du système (nombre
de symboles à lire, de données à trier, d’agents à synchroniser), encore faut-il
connaître, pour une machine donnée, le temps pris par une opération unitaire
pour évaluer la durée d’exécution de cet algorithme.
Le présent ouvrage se place dans le cadre des analyses théoriques, et s’intéresse
à des aspects précis de parties d’un système informatique : l’analyse fine du
comportement d’un algorithme, agissant sur une structure de données arborescente.
Il y a plusieurs manières d’envisager cette analyse :
– soit nous nous intéressons aux cas extrémaux, i.e. au comportement de
l’algorithme dans le pire (ou le meilleur) des cas ;
– soit nous cherchons plutôt à caractériser un comportement moyen, ou mieux
encore la distribution de probabilité d’un paramètre du système.
La première approche conduit par exemple à identifier des classes de problèmes
résolubles dans le pire des cas en un temps polynomial en la taille des données, et
d’autres qui ne le sont pas : c’est la « théorie de la complexité ». La seconde repose
sur l’idée que le comportement d’un algorithme est souvent caractérisé de façon
plus pertinente par ses performances sur la plupart des données d’entrée que sur des
cas exceptionnels. C’est ce qui est couramment appelé « analyse d’algorithmes » ou
(de façon indûment restrictive) « analyse en moyenne », et c’est ce qui sous-tend les
analyses présentées dans ce livre.
Une démarche générale
Prenons donc un algorithme, c’est-à-dire une méthode de résolution pour un certain
problème, par exemple le tri d’un grand nombre de données, ou la recherche d’une
valeur dans un ensemble de grande taille. Cet algorithme prend en entrée des