This is a page of the former Algo team's web site. It won't be updated any longer.
 
Welcome! Research Topics People Publications Seminars Software On-Line Applications Jobs & Internships

ALGO logo  

Marianne Durand's Home Page

Me contacter Enseignement Recherche/Articles Exposés

Thèse:

Je suis en dernière année de thèse au projet Algo sous la direction de Philippe Flajolet, le titre de ma thèse est Combinatoire analytique et algorithmique des ensembles de données.   Mon thème de recherche est l'analyse d'algorithmes et de structures combinatoires. Plus particulièrement, je m'intéresse à trois sujets :

  • Les algorithmes de comptage probabiliste,
  • Les algorithmes de hachage, pour des tables avec pagination,  
  •  L'extraction de coefficients de séries génératrices bivariées pour une configuration particulière des singularités, avec application aux jumplists (vous voulez en voir une?).

    Ces trois directions sont reliées entre elles : les méthodes de hachage peuvent fournir des méthodes de comptage probabilistes ; les algorithmes de comptage probabilistes requièrent très souvent un hachage préliminaire des valeurs étudiées ; et enfin, l'analyse de certaines méthodes de hachage débouche sur des séries génératrices multivariées.

  • Une version préliminaire de ma thèse  en ps ou en ps compressé(19 Avril).

    Soutenance de thèse.

    Ma soutenance a lieu le 30 avril à l'ecole Polytechnique (Palaiseau) à 11h, amphi Fresnel.
  • Comment se rendre à l'amphi Fresnel à l'école Polytechnique???
    Tout d'abord se rendre à l'ecole Polytechnique.
    Puis l'amphi Fresnel est situé près des laboratoires. Un plan général de l'X, et un plan des laboratoires (l'amphi Fresnel est situé au milieu du plan).


    Articles et Preprints:

                        Ou comment estimer le nombre de mots distincts dans les oeuvres complètes de Shakespeare en une seule lecture avec une précision de quelques pour cents et seulement un kilobit de mémoire? (Pourquoi Shakespeare? Parce que c'est en ligne et que c'est bien!)
                         Cet article présente un algorithme qui utilise des propriétés observables de la distribution des mots pour pouvoir répondre a ce type de question avec une mémoire en loglog n, ou n désigne le cardinal de l'ensemble étudié.  Cet algorithme est ensuite entièrement analysé, et est testé sur de nombreuses données d'origines variées (données aléatoires, romans, logs de pages webs...)                    Les jumplists sont une nouvelle structure de données, inspirée des skips-lists et proches des arbres binaires de recherche. Cet article présente tous les algorithmes de base pour cette structure : recherche-insertion-suppression, ainsi que l'analyse en moyenne de la plupart des coûts.
                     Bentley et McIlroy ont implémenté un algorithme de type quicksort en 1993,  qui expérimentalement est l'algorithme de tri générique le plus rapide. Cet algorithme est utilise dans la librairie standard C. Cet article présente l'analyse du coût moyen de cet algorithme, et permet de valider les résultats expérimentaux de Bentley et McIlroy. 
                    Lorsqu'on effectue des mises à jour d'un arbre binaire de recherche (suppression puis insertion d'un élément), le coût moyen de recherche diminue, ce qu'on nomme l'effet de Knott.  Cet effet est contrebalancé par l'effet d'Eppinger lorsque ces mises à jour utilisent un algorithme de suppression asymétrique.  La  contribution de cet article est de modéliser de façon séparée  différents effets qui peuvent influer sur  l'effet de Knott.
                  Ce mémoire rappelle les définitions et propriétés de la D-finitude et de l'holonomie, et étudie ensuite une série d'applications, notamment sur les arbres binaires de recherche, l'algorithme quicksort, les quadtrees et les arbres m-aires de recherche.

    Poster:



    En construction

    Exposés :


    Collaborations :



    Resumés de séminaire :

    Chaque exposé fait au séminaire Algo est ensuite résumé par un joyeux voontaire. L'ensemble de ces résumés est disponible ici, et voici la liste des résumés que j'ai écrit.

    1999/2000 2000/2001
    2001/2002 2002/2003


     Divers :


    Address


    Last modified: Mon Aug 25 16:37:06 CET 2003

    For problems involving this web page, please contact  Marianne Durand.