Groupe Analyse dynamique d'algorithmes


Groupe Analyse dynamique d'algorithmes

 

Groupe Analyse dynamique d'algorithmes Groupe Analyse Dynamique d'Algorithmes L'analyse en moyenne d'algorithmes vise à déterminer le comportement "moyen" des algorithmes. Par opposition à la complexité dans le pire des cas, la complexité moyenne d'un algorithme permet d'appréhender les performances de l'algorithme de manière "réaliste". Il est maintenant classique, en analyse d'algorithmes, de travailler avec un outil essentiel, celui des séries génératrices. Les principales opérations algébriques sur les structures de données ou les algorithmes se traduisent en opérations formelles sur les séries génératrices. Quand les séries génératrices sont vues comme des fonctions de variable complexe, leur singularité dominante permet d'obtenir des renseignements précieux sur le comportement asymptotique moyen de l'algorithme. Cependant, quand les algorithmes sont trop corrélés, cette méthodologie ne peut plus s'appliquer, car les opérations sur les algorithmes ne se traduisent plus aisément en opérations sur les séries génératrices. C'est alors une idée tout à fait naturelle que de considérer un algorithme et l'ensemble de ses données comme un système dynamique. Les données sont alors les particules du système qui sont soumises au "champ" créé par les opérations que leur font subir l'algorithme. A un système dynamique, on associe classiquement, depuis Ruelle, un opérateur appelé opérateur de transfert, ou opérateur de Ruelle, qui permet de décrire l'évolution du système. Cet opérateur dépend d'un paramètre s, est désigné par Hs et agit sur un espace de fonctions d'une variable. Opérateur de transfert = opérateur générateur. L'idée originale consiste à détourner l'opérateur de transfert de son usage habituel et à le considérer comme un opérateur "super??générateur", en ce sens qu'il engendre lui?même les séries génératrices associées à l'algorithme. De plus, les opérations sur les algorithmes continuent à se traduire en opérations sur ces opérateurs générateurs. Par ailleurs, aussitôt que le système dynamique possède de "bonnes propriétés", cet opérateur a des propriétés spectrales dominantes : il existe une valeur propre dominante $\lambda(s)$ qui concentre les propriétés essentielles du système et qui va jouer le même rôle que la singularité dominante dans le cadre classique des séries génératrice. Elle et va ainsi permettre d'appréhender le comportement asymptotique moyen de l'algorithme, même quand celui?ci est "corrélé". C'est la philosophie générale. Mais, de fait, les opérateurs de transfert ne peuvent pas vraiment être utilisés "tels que" en analyse d'algorithmes, ils ont souvent besoin d'être généralisés, afin d'opérer sur des fonctions de plusieurs variables. Les domaines d'application. Cette méthodologie peut s'appliquer à deux domaines algorithmiques larges, l'algorithmique arithmétique et l'algorithmique du texte. Dans chacun de ces domaines, la méthode prouve son efficacité en permettant de résoudre des problèmes inaccessibles à la méthode classique. La démarche est différente dans les deux domaines : en algorithmique arithmétique, on cherche à analyser des algorithmes existants et utilisés. En algorithmique du texte, il y a une double volonté : on cherche à modéliser le concept de source, qui est le mécanisme sous?jacent à tous les algorithmes de texte, puisque c'est lui qui produit le texte ; on cherche ensuite à analyser les algorithmes quand les textes sont produits sous ce modèle. Il y a ainsi un transfert de méthodes de l'un des domaines à l'autre : en algorithmique arithmétique, le concept a été utilisé pour des systèmes dynamiques de plus en plus complexes, qui se sont "spontanément" présentés, lors de l'analyse d'algorithmes classiques existant, et ont permis d'élargir l'expertise. Il était alors tentant d'utiliser cette plus grande compétence en élargissant la possible modélisation dans le contexte de l'algorithmique du texte, et en généralisant progressivement la définition des sources dynamiques. 1/3 Quelques publications La méthodologie générale de l'analyse dynamique se trouvent expliquée dans le cours donné par Brigitte Vallée et Viviane Baladi aux journées ALEA 2002 : Notes du cours, prises par Frederic Chazal, Veronique Maume Deschamps et Brigitte Vallée. Vous trouverez ci?dessous quelques publications de l'équipe, classées par thèmes. Systèmes Dynamiques : quelques articles sur des paramètres intervenant en analyse dynamique Computation of a Class of Continued Fraction Constants, Loïck Lhote. ? Exponential Decay of Correlations for Surface Semi?Flows Without Finite Markov Partition ( Version PDF ) Brigitte Vallée, Viviane Baladi ? Algorithmes Euclidiens : c'est dans l'étude de ces algorithmes que le lien algorithmes ? systèmes dynamiques est apparu pour la première fois. Cette correspondance a permit d'analyser une très large classe d'algorithmes, parfois liés à des systèmes de natures très differentes. Euclidean Algorithms Are Gaussians (version PDF), Brigitte Vallée, Viviane Baladi ? Distributional Analyses of Euclidean Algorithms (version PDF), Brigitte Vallée, Viviane Baladi ? Dynamical Analysis of a Class of Euclidean Algorithms, Brigitte Vallée, Theoretical Computer Science 1?3(297), (2003), pp 447??486 ? Dynamical Analysis of the Parameterized Lehmer?Euclid Algorithm, Benoît Daireaux, Brigitte Vallée. ? Dynamical Analysis of ??Euclidean Algorithms, Jérémie Bourdon, Benoît Daireaux, Brigitte Vallée, Journal of algorithms 44, (2002), pp 246?285. ? Digits and Continuants in Euclidean algorithms. Ergodic versus Tauberian theorems, Brigitte Vallée Journal de Théorie des Nombres de Bordeaux 12, (2000), pp 531?570. ? Dynamics of the Binary Euclidean Algorithm: Functional Analysis and Operators, Brigitte Vallée, Algorithmica 22, (1998), no. 4, pp660??685. ? An average?case analysis of the Gaussian algorithm for lattice reduction, H. Daudé, P. Flajolet, et B. Vallée.Combinatorics, Probability and Computing 6 (4), (1997), pp. 397?433. ? Algorithmique du texte : dans ce domaine, les systèmes dynamiques ne jouent plus le rôle de modélisation d'algorithmes, mais de sources émettant des symboles. Cette approche permet d'étudier de nombreux problèmes de théorie de l'information. Hidden Word Statistics, Philippe Flajolet, Wojtek Szpankowski et Brigitte Vallée, soumis à Journal of the A.C.M. ? Generalized Pattern Matching Statistics, Jérémie Bourdon, Brigitte Vallée, Mathematics and Computer Science II: Algorithms, Trees, Combinatorics and Probabilities, Proceedings of Versailles Colloquium, Birhäuser Verlag, (2002), pp. 249?265. ? Hidden Patterns Statistics, Philippe Flajolet, Yves Guivarc'h, Wojtek Szpankowski et Brigitte Vallée, Proceedings of ICALP'01, Crete, July 2001. Lecture Notes in Computer Science,Vol. 2076, pp. 152??165. ? Dynamical Sources in Information Theory: Fundamental intervals and Word Prefixes, Brigitte Vallée, Algorithmica 29(1/2), (2001), pp. 262?306. ? Erratum to : Dynamical Sources in Information Theory: Fundamental intervals and Word Prefixes (version PDF), Frederic Chazal, Véronique Maume?Deschamps, Brigitte Vallée.. ? Arbres, tries : finalement, les techniques d'analyse dynamique sont très adaptées à l'étude de structures de données apparaissant notament en théorie de l'information (arbres, tries, Patricia tries). 2/3 Size and Path length of Patricia Tries: Dynamical Sources Context, Jérémie Bourdon, Random Structures and Algorithms, John Wiley and Sons, 19 (3?4), pp. 289??315. ? On the Stack?Size of General Tries, Jérémie Bourdon, Markus Nebel, Brigitte Vallée, Theoretical Informatics and Applications, EDP Sciences, 35, pp. 163??185. ? The Analysis of Hybrid Trie Structures, Julien Clément, Philippe Flajolet, et Brigitte Vallée, Proceedings of the Ninth ACM_SIAM Symposium on Discrete Algorithms (SODA'98), San Francisco, January 1998, pp. 531?539. ? Dynamical Systems and the Analysis of General Tries, Brigitte Vallée, ? Membres: B. Vallée (GREYC) ? A. Akhavi (GREYC) ? J. Bourdon (GREYC) ? B. Daireaux (GREYC) ? L. Lhote (GREYC) ? Liens: Pages personnelles : Veronique Maume?Deschamps, Université de Dijon ? Frederic Chazal, Université de Dijon ? Viviane Baladi ? Philippe Flajolet, INRIA ? Julien Clement, Université de Marne?la?Vallée ? Julien Fayolle, INRIA ? Autres : Groupe de travail ALEA ? Analysis of Algorithms homepage ? 3/3

PARTAGER SUR

Envoyer le lien par email
4935
READS
2
DOWN
7
FOLLOW
5
EMBED
DOCUMENT # TAGS
#algorithme  #maths 

licence non indiquée


DOCUMENT # INDEX
Mathematiques, Sciences 
img

Partagé par  macuche

 Suivre

Auteur:
Source:Non communiquée