Partenaires

CNRS
Logo tutelle
Logo tutelle
Logo tutelle


Rechercher

Sur ce site

Sur le Web du CNRS


Accueil du site > Séminaires > Probabilités Statistiques et réseaux de neurones > Analyse probabiliste des heuristiques Move-To-Front et Move-To-Root avec poids aléatoires.

Vendredi 27 février 2004, à 11h

Analyse probabiliste des heuristiques Move-To-Front et Move-To-Root avec poids aléatoires.

Christian Paroissin (Université Paris X)

Résumé : Considérons n objets ayant des poids aléatoires indépendants, ce qui permet de définir un vecteur de popularité de ces objets. On souhaite ranger ces objets dans une structure de données de sorte que les objets les plus populaires soient accessibles le plus rapidement possible. Nous allons considérons successivement deux structures de données : une liste et un arbre binaire de recherche. Deux heuristiques, Move-To-Front et Move-To-Root, ont été introduites pour s’approcher de la forme optimale que devrait avoir ces structures de données. A chaque requête, l’objet demandé est placé, selon la structure considérée, soit en tête de liste, soit à la racine de l’arbre. Dans les deux cas, on obtient une chaîne de Markov ayant une unique mesure stationnaire. Dans ce travail, nous nous intéressons au coût de recherche d’un objet lorsque la chaîne est dans l’état stationnaire. La première partie est dédiée à l’heuristique MTF : nous donnons la transformée de Laplace du coût et une approximation lorsque le nombre d’objets tend vers l’infini. La seconde partie est consacrée à l’heuristique MTR : nous donnons les deux premiers moments du coût de recherche. Dans chacun des cas, des exemples sont donnés. Une comparaison du coût de recherche correspondant aux deux heuristiques est brièvement faite.

Dans la même rubrique :