Voici le programme, les exposés auront lieu en salle S3 247.

lundi 9 mai

Pierre Calka Université de Rouen 14h30 Fractales aléatoires générées par des suites de pavages réguliers du plan

On considère un pavage régulier du plan (carré, triangulaire, hexagonal) et on construit une suite croissante d’ensembles aléatoires obtenus par réunion de tuiles d’homothétiques de ce pavage. On montre que cette suite converge vers un ensemble aléatoire compact dont on calcule explicitement les dimensions de boîte et de Hausdorff. On verra que la méthode s’appuie sur un codage de la construction itérative par un processus de branchement multi-types. Collaboration avec Yann Demichel Université Paris Nanterre.

Julien Clément 15h15 Analyse en moyenne des tries

Le trie est une structure de donnés de type dictionnaire qui permet de représenter efficacement un ensemble de mots pour les opérations usuelles (insérer ou insérer un mot, tester si un mot est présent). Dans cet exposé je présenterai l’analyse en moyenne de paramètre de tries dans un cadre probabiliste particulier relativement simple : les mots sont produits indépendamment par une source dynamique d’entropie de Shannon positive. Les méthodes sont principalement celles de la combinatoire analytique et font intervenir des séries génératrices reliées à la source et au paramètre étudié.

Cet exposé plutôt introductif se base sur d’anciens travaux en collaboration avec Philippe Flajolet et Brigitte Vallée.

Pause 16h

Brigitte Vallée GREYC 16h30-17h15 Construction explicite de sources d’entropie nulle : changement d’échelle et insertion de délais.

La plupart des sources qui apparaissent de manière naturelle en théorie de l’information ont une entropie positive. Elles sont bien étudiées. Nous cherchons ici à construire de manière explicite des sources naturelles d’entropie nulle, via un changement d’échelle, ou l’insertion de délais. Ces deux processus (changement d’échelle, insertion de délais) sont d’ailleurs essentiellement les mêmes : ils ne modifient pas les intervalles fondamentaux de la source, mais seulement la « profondeur » à laquelle ces intervalles fondamentaux sont utilisés, ou la « vitesse » à laquelle on les subdivise. Nous commençons avec une source d’entropie positive, bien connue, et utilisons une classe naturelle de changements d’échelle, de croissance sous-linéaire. Les sources obtenues héritent ainsi de beaucoup de propriétés de la source de départ —au changement d’échelle près— et peuvent être finement analysées. Nous nous concentrons sur deux questions importantes: nous exhibons des lois asymptotiquement normales à la Shannon-MacMillan-Breiman, et nous analysons la profondeur moyenne des tries construits sur ces sources. Dans chacun des deux cas, nous obtenons une classe de comportements précis, paramétrée par le changement d’échelle utilisé. Nous utilisons des méthodes de combinatoire analytique, qui font jouer un rôle important aux séries génératrices des sources.

Collaboration avec Ali Akhavi GREYC, Frédéric Paccaut Université de Picardie.

mardi 10 mai

Philippe Regnault Université de Reims 10h15

Existence d’un taux d’entropie non trivial : la bonne fonctionnelle d’entropie pour le bon processus (et réciproquement).

Dans cet exposé, on s’intéresse à un critère de pertinence pour qu’une fonctionnelle d’entropie soit une mesure d’information adaptée à un processus stochastique : l’existence d’un taux d’entropie non trivial (différent de 0 ou de l’infini). L’existence d’un tel taux est, par définition, caractérisée par le fait que la suite des entropies marginales du processus croisse (asymptotiquement) linéairement avec le nombre de coordonnées ; propriété que l’on dénommera linéarité de la fonctionnelle pour ce processus. Dans un premier temps, en se basant sur des résultats antérieurs de Girardin, Lhote et Regnault, on établit qu’il existe trois familles de fonctionnelles linéaires pour les processus vérifiant la propriété dite de quasi-puissance: l’entropie de Shannon, les entropies de Rényi et les entropies « log-Taneja ». Dans un second temps, on propose une méthode de construction de processus simples tels qu’une fonctionnelle d’entropie donnée soit linéaire pour ces processus.

Collaboration avec Valérie Girardin/

Pause 11h

Mathieu Dien GREYC 11h15 Comptage des extensions linéaires et calcul du volume de polytopes convexes

Dans cet exposé, nous présenterons le problème du calcul d’extensions linéaires d’un ordre partiel et son lien avec le problème du calcul de volume de polytopes convexes particuliers. Nous présenterons rapidement des applications en lien avec ce problème, puis des algorithmes plus ou moins efficaces pour le résoudre. Nous conclurons sur plusieurs pistes de généralisations de ces résultats.