xviii
Introduction
données (de l’information, dont la représentation dépend de l’utilisation qui en
est faite) généralement stockées dans des structures de données (par exemple des
arbres), et va répondre au problème posé en renvoyant un résultat : pour les deux
exemples ci-dessus, les données triées en ordre croissant, ou bien la valeur cherchée,
dans la mesure où elle est effectivement présente. L’analyse (des performances) de
cet algorithme peut être décomposée en plusieurs étapes :
– Tout d’abord vient une phase de modélisation, qui a pour but d’établir un modèle
représentant les données, algorithmes, ou systèmes, qui sont l’objet de l’étude ;
nous nous limitons dans ce livre aux structures arborescentes et aux algorithmes
les utilisant. Les données étant le plus souvent aléatoires ou considérées comme
telles, le modèle inclut l’établissement d’une distribution de probabilité sur ces
données. À la fin de cette première étape, nous avons donc défini un modèle
avec données aléatoires ; pour ce qui nous intéresse dans ce livre, c’est un arbre
aléatoire, appelons-le τ .
– Dans un deuxième temps, il nous faut dégager les paramètres qui mesurent le
coût, ou la « complexité », de l’algorithme, typiquement son temps d’exécution,
ou la place mémoire pour représenter une structure de données. Pour fixer les
idées dans la suite, appelons c(τ ) ce coût de l’algorithme, exécuté sur un arbre τ .
– Vient alors une phase d’étude mathématique de ce coût d’exécution. L’arbre τ
défini dans la première phase est aléatoire ; en conséquence le coût c(τ ) est
une variable aléatoire. Suivant le type de résultat cherché, nous étudions le coût
moyen de c(τ ), ou bien ses moments, voire sa distribution de probabilité et sa
convergence éventuelle vers une distribution limite.
– La dernière phase est celle du retour au problème algorithmique ; bien
qu’essentielle, elle est souvent passée sous silence, ce qui est dommage car
nombre de résultats sur les paramètres d’arbres ont une traduction immédiate en
termes de performances de l’algorithme étudié.
Dans la phase de modélisation proprement dite, le modèle arborescent pour
représenter les données est souvent l’un de ceux présentés en chapitre 1 ; le modèle
probabiliste est issu du chapitre 2. Quant à la mise en évidence des propriétés
de l’arbre qui déterminent le coût, elle fait le plus souvent intervenir l’un des
paramètres classiques présentés à la fin du chapitre 1 en section 1.3. La troisième
étape, l’analyse des paramètres, constitue le sujet des chapitres 4 à 9 ; suivant le cas
analysé et selon le type de résultats cherchés, elle utilise des outils de combinatoire
analytique ou de probabilités.
Avant de présenter les arbres étudiés et les méthodes employées, illustrons la
modélisation des performances d’un algorithme et l’analyse de sa complexité sur
l’exemple (on ne peut plus classique !) des arbres binaires de recherche.
Introduction
données (de l’information, dont la représentation dépend de l’utilisation qui en
est faite) généralement stockées dans des structures de données (par exemple des
arbres), et va répondre au problème posé en renvoyant un résultat : pour les deux
exemples ci-dessus, les données triées en ordre croissant, ou bien la valeur cherchée,
dans la mesure où elle est effectivement présente. L’analyse (des performances) de
cet algorithme peut être décomposée en plusieurs étapes :
– Tout d’abord vient une phase de modélisation, qui a pour but d’établir un modèle
représentant les données, algorithmes, ou systèmes, qui sont l’objet de l’étude ;
nous nous limitons dans ce livre aux structures arborescentes et aux algorithmes
les utilisant. Les données étant le plus souvent aléatoires ou considérées comme
telles, le modèle inclut l’établissement d’une distribution de probabilité sur ces
données. À la fin de cette première étape, nous avons donc défini un modèle
avec données aléatoires ; pour ce qui nous intéresse dans ce livre, c’est un arbre
aléatoire, appelons-le τ .
– Dans un deuxième temps, il nous faut dégager les paramètres qui mesurent le
coût, ou la « complexité », de l’algorithme, typiquement son temps d’exécution,
ou la place mémoire pour représenter une structure de données. Pour fixer les
idées dans la suite, appelons c(τ ) ce coût de l’algorithme, exécuté sur un arbre τ .
– Vient alors une phase d’étude mathématique de ce coût d’exécution. L’arbre τ
défini dans la première phase est aléatoire ; en conséquence le coût c(τ ) est
une variable aléatoire. Suivant le type de résultat cherché, nous étudions le coût
moyen de c(τ ), ou bien ses moments, voire sa distribution de probabilité et sa
convergence éventuelle vers une distribution limite.
– La dernière phase est celle du retour au problème algorithmique ; bien
qu’essentielle, elle est souvent passée sous silence, ce qui est dommage car
nombre de résultats sur les paramètres d’arbres ont une traduction immédiate en
termes de performances de l’algorithme étudié.
Dans la phase de modélisation proprement dite, le modèle arborescent pour
représenter les données est souvent l’un de ceux présentés en chapitre 1 ; le modèle
probabiliste est issu du chapitre 2. Quant à la mise en évidence des propriétés
de l’arbre qui déterminent le coût, elle fait le plus souvent intervenir l’un des
paramètres classiques présentés à la fin du chapitre 1 en section 1.3. La troisième
étape, l’analyse des paramètres, constitue le sujet des chapitres 4 à 9 ; suivant le cas
analysé et selon le type de résultats cherchés, elle utilise des outils de combinatoire
analytique ou de probabilités.
Avant de présenter les arbres étudiés et les méthodes employées, illustrons la
modélisation des performances d’un algorithme et l’analyse de sa complexité sur
l’exemple (on ne peut plus classique !) des arbres binaires de recherche.