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:

Loglog Counting of large cardinalities en ps en collaboration avec Philippe Flajolet (accepté à ESA03).

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...)

Randomized Jumplists: A Jump-and-Walk Dictionary DataStructure en pdf, en collaboration avec Frédéric Cazals et Hervé Brönnimann (accepté à STACS03).

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.

Asymptotic analysis of an optimized quicksort en ps, Inf. Process. Lett., vol. 85, n°2, 2003, pages 73--77.

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.

Emerging Behavior as Binary Search Trees are Symmetrically Updated en collaboration avec Stephen Taylor, en ps, TCS 1-3(297): 425-445 (2003).

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.

Mon mémoire de DEA intitulé Holonomie et applications en analyse d'algorithmes et combinatoire (Sept 2000) en dvi ou en ps compressé.

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:

Jumplists and a bivariate asymptotics problem (format A4), présenté à AofA 2003 (San Miniato).

En construction

Exposés :

2000-2001

Exposé de Dea
Tout ce que vous avez toujours voulu savoir sur Quicksort ... (Oct 2001). Slides ps (Version courte) et slides ps (Version longue)
Alea01

2001-2002

Probabilistic Couting AofA02 (Strobl) et séminaire Algo.

2002-2003

Collaborations :

2000-2001 : avec Mordecai Golin (Hong-Kong)
2002-2003 : avec Michael Drmota (Vienne) et Alfredo Viola (Montevideo)
2003-2004 : avec Michael Drmota (Vienne)

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

Random Group Automata, par Cyril Nicaud.

2000/2001

Thirty Years of Integer Factorization, par François Morain.
Random Matrices and Queues in Series, par Yuliy Baryshnikov.
On the Convergence of Borel Approximants, par Donald Lutz. La worksheet maple associée Borel Resummation of Divergent Series Using Gfun (accessible en .mws, .pdf, .ps).

2001/2002

Une approche hyperasymptotique de la méthode du col multi-dimensionnelle, par Éric Delabaere.
Irrationalité des valeurs de la fonction zêta de Riemann aux entiers impairs, par Tanguy Rivoal.

2002/2003

Élection économe d'un leader dans un réseau, par Jean-François Marckert.
Patterns in Trees, par Thomas Klausner.

Divers :

Pcoq, une interface graphique de Coq, sur lequel j'ai fait mon stage de maîtrise.
L'ESF, encyclopedia of special functions, développée par mon co-bureau Ludovic.

Address

E-mail:
Marianne.Durand at inria.fr
Business address:
Marianne Durand
Projet ALGO
INRIA Rocquencourt
78153 Le Chesnay Cedex
FRANCE
Telephone: (33) 1 39 63 59 04
Fax number: (33) 1 39 63 55 96

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

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