Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 19 Avril 2016

Commun avec le groupe de travail "mots et entropie" (LMNO+GREYC)

par Thierry Lecroq (LITIS, Rouen), Pierre Calka (LMRS, Rouen), Valérie Girardin (LMNO, Caen)

Programme

Résumés

Thierry Lecroq: Répétitions abéliennes dans les mots sturmiens

Travail en commun avec Gabriele Fici, Alessio Langiu, Arnaud Lefebvre, Filippo Mignosi, Jarkko Peltomäki et Elise Prieur-Gaston

Dans cet exposé nous étudions les répétitions abéliennes dans les mots sturmiens. Nous exploitons une bijection entre les facteurs des mots sturmiens et des intervalles du segment unitaire qui permet d'étudier les périodes des répétitions abéliennes en utilisant des résultats classiques de la théorie des nombres. Si k_m est l'exposant maximal d'un répétition abélienne de période m, nous montrons que la limite supérieure k_m/m est supérieure ou égale à racine de 5 pour tout mot sturmien et qu'elle est égale à racine de 5 dans le cas du mot infini de Fibonacci. Nous montrons de plus que le plus long préfixe du mot infini de Fibonacci qui est une répétition abélienne de période F_j, j > 1, a pour longueur F_j(F_{j+1} + F_{j-1} + 1) - 2 si j est pair et F_j(F_{j+1} + F_{j-1}) - 2 si j est impair. Cela nous permet de donner une formule exacte pour la plus petite période abélienne d'un mot fini de Fibonacci.

Pierre Calka. Probabilités géométriques et géométrie algorithmique : étude asymptotique d'enveloppes convexes et autres exemples

Cet exposé vise à présenter des résultats de probabilités géométriques portant sur des structures qui apparaissent naturellement en géométrie algorithmique (polyèdres, graphes géométriques, triangulations...). On s'intéressera plus particulièrement au cas des enveloppes convexes de grands nuages de points aléatoires et on montrera comment obtenir des moyennes et variances limites de leurs caractéristiques géométriques telles que le nombre de points extrémaux ou de faces de dimension fixée, le volume, etc.

Par ailleurs, on établira des théorèmes limites et on exhibera dans certains cas l'existence de formes limites. En fonction du temps, on pourra aussi aborder d'autres exemples de structures géométriques telles que les cellules de Voronoi. Les résultats présentés sont utiles dans le cadre de l'analyse de complexité en moyenne en géométrie algorithmique.

Valérie Girardin. Taux d'entropie renormalisés. Application aux chaînes de Markov.

(Travaux communs avec Gabriela Ciuperca, Loick Lhote et Philippe Regnault) Nous étudions le problème de définition, calcul et estimation de taux d'entropie et de divergence généralisées pour des processus stochastiques à temps discret et à nombre d'états dénombrable. Les fonctionnelles considérées incluent la plupart de celles rencontrées dans la littérature, dont les entropies et divergences associées de Shannon, Rényi, Tsallis, Kullback-Leibler, Sharma-Mittal, etc.

Usuellement, en théorie des processus, le taux est défini par moyenne sur le nombre d'unités de temps. Lorsque cette normalisation n'est pas adaptée au comportement asymptotique du processus, les taux induits sont triviaux. Nous montrons alors qu'une renormalisation adéquate permet d'obtenir des taux significatifs, étendant ainsi le champ de leurs nombreuses applications à une large classe de processus et de fonctionnelles.

Des formules de taux explicites sont obtenues dès que le processus vérifie une hypothèse de régularité bien connue en théorie des systèmes dynamiques, la propriété de quasi-puissance. Pour les chaînes de Markov finies ou dénombrables, la propriété est vérifiée sous des conditions simples sur la matrice de transition de la chaîne. Le taux peut alors s'exprimer de différentes manières, à partir de la matrice de transition perturbée par le paramètre adéquat.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr