Search

Ce mémoire étudie deux familles de fonctions orthogonales, soit les fonctions d'orbite de Weyl et les fonctions d'orbite de Hartley. Chacune de ces familles est associée à une algèbre de Lie simple et cette recherche se limite aux algèbres A₂, C₂ et G₂ de rang 2. Les fonctions d'orbite de Weyl ont été largement étudiées depuis des années en raison de leurs propriétés exceptionnelles. Nouvellement, elles ont été utilisées pour générer des polynômes de Chebyshev généralisés et calculer les fonctions génératrices de ces polynômes pour les algèbres de Lie simples de rang 2. Les fonctions d'orbite de Hartley, quant à elles, ont été récemment introduites par Hrivnák et Juránek et l'étude de ces dernières ne fait que débuter. L'objectif de ce mémoire est de définir des polynômes de Chebyshev généralisés associés aux fonctions de Hartley et de calculer les fonctions génératrices de ceux-ci pour les algèbres A₂, C₂ et G₂. Le premier chapitre introduit les systèmes de racines et le groupe de Weyl, original et affine, ainsi que leurs domaines fondamentaux, afin que le lecteur ait les notations et définitions pour comprendre les chapitres suivants. Le deuxième chapitre présente et étudie les fonctions de Weyl. Il définit également leurs polynômes de Chebyshev généralisés et se termine en présentant les différentes fonctions génératrices de ces polynômes pour les algèbres de Lie simples de rang 2. Finalement, le troisième chapitre contient les résultats originaux; il expose les fonctions de Hartley et certaines de leurs propriétés. Il définit les polynômes de Chebyshev généralisés de celles-ci et énonce également leurs relations d'orthogonalité discrète. Il conclut en calculant les fonctions génératrices de ces polynômes pour les algèbres A₂, C₂ et G₂., This master's thesis studies two families of orthogonal functions, the Weyl orbit functions and the Hartley orbit functions. Each of these families is associated to a simple Lie algebra and the present work is limited to the algebras A₂, C₂ and G₂ of rank 2. Weyl orbit functions have been widely studied for years because of their exceptional properties. Recently, these properties have been used to generate generalized Chebyshev polynomials and to compute the generating functions of these polynomials for the simple Lie algebras of rank 2. Hartley orbit functions, on the other hand, were recently introduced by Hrivnák and Juránek and the study of the latter has only begun. The objective of this thesis is to define the generalized Chebyshev polynomials of Hartley orbit functions and to compute their generating functions for the algebras A₂, C₂ and G₂. The first chapter introduces root systems and the Weyl group, original and affine, and their fundamental domains, so that the reader has the notations and definitions at hand to read the following chapters. The second chapter introduces and studies Weyl orbit functions. It also defines their generalized Chebyshev polynomials and ends by presenting the different generating functions of these polynomials for simple Lie algebras of rank 2. Finally, the third chapter contains the original contribution; it presents the Hartley functions and some of their properties. It defines the generalized Chebyshev polynomials of these and also states their discrete orthogonality relations. It concludes by computing the generating functions of these polynomials for the algebras A₂, C₂ and G₂.

Thèses en préparation à Montpellier , dans le cadre de I2S - Information, Structures, Systèmes , en partenariat avec BioSP - Biostatistique et Processus Spatiaux (laboratoire) depuis le 01-10-2014 .; We present a parametric family of probability distributions associated with a particular homogeneous one and multitype branching process in continuous time. With its simplicity and the relevance of the parameterization, this family is well adapted to describe branching dynamical systems of populations in interaction. Calculations and mathematical properties concerning probability distributions use the corresponding properties of generating functions and finally relate to solving linear partial differential equations.; L'objet de cette thèse concerne la proposition de modèles paramétriques des processus de branchement uni et multi-types. Nous mettons en valeur l’intérêt de la théorie des processus de branchement et du développement nécessaire des différents outils et de concepts propres à plusieurs domaines. Pour cela, nous commençons par rappeler quelques définitions et résultats de la théorie des processus de branchement uni et multi-types, et ce en temps discret comme en temps continu. On se consacre par la suite au développement méthodologique de ces modèles. Dans la deuxième partie de ce mémoire, nous étudions seulement l'évolution d’une seule population en temps continu, et présentons quelques familles de lois paramétriques, associées à des processus de branchement homogènes particuliers. Des méthodes récursives de calcul, ainsi que des propriétés pertinentes, concernant ces distributions de probabilité, sont dérivées des fonctions génératrices satisfaisant certaines équations aux dérivées partielles linéaires précisés. Les familles proposées seront utiles à la modélisation de systèmes plus cohérents en dynamique de populations, puisqu'on y montre que les hypothèses usuelles de distributions de Poisson ne peuvent être argumentées. Dans la troisième partie, nous étudions le comportement de l'évolution de plusieurs populations en interactions. Nous y présentons aussi des modèles paramétriques de lois, associés à des processus de branchement multi-types en temps continu et homogènes en temps. Nous considérons ensuite un modèle particulier, où une population ``mère donneuse" autonome alimente en individus K populations filles, qui sont, elles, en interaction. Ce modèle est bien adapté à l'étude des systèmes dynamiques des populations en interaction qui reste à la fois simple, mais riche en variétés de comportement. L'étude du système multi-types se fait via l'évolution des fonctions génératrices de la loi multidimensionnelles des effectifs. Pour cela, utilisant les équations différentielles ordinaires et aux dérivées partielles, nous établissons les équations implicites des distributions temporelles et multidimensionnelles, et discutons des méthodes analytiques ou numériques de leur résolution. Nous développons ensuite des exemples de modèles et en particulier celui concernant 3 et 4 populations. En conclusion, nous argumentons la pertinence de cette approche, et l’interprétation des paramètres, qui sont d'un grand intérêt pour le développement de méthodes d'inférence statistique, pour de nombreux domaines d'applications.

Cet article d’épistémologie est consacré à décrire la constitution par Dominique Foata d’un concept (le composé partitionnel Y+ d’une suite Y = Yn d’ensembles finis) et d’une certaine figure de pensée mathématique corrélative. Tous deux sont progressivement construits à partir d’identités d’analyse bien connues, associées par exemple à la fonction génératrice des polynômes d’Hermite. This epistemological paper is devoted a concept defined by Dominique Foata of a concept (the composé partitionnel Y+ of a sequence Y = Yn of finite sets) and of some associated mathematical themes of thought. Both are progressively introduced, starting from well known analytical identities, associated for instance to the generating function of Hermite polynomials.

We revisit classical textbook sorting or selecting algorithms under a complexity model that fully takes into account the elementary comparisons between symbols composing the records to be processed. Our probabilistic models belong to a broad category of information sources that encompasses memoryless (i.e., independent-symbols) and Markov sources, as well as many unbounded-correlation sources. Under this perspective, commonly accepted assertions, such as ``the complexity of Quicksort is O(n log n)'', are to be challenged, and the relative merits of sorting and searching methods relying on different principles (e.g., radix-based versus comparison-based) can be precisely assessed. For instance we establish that, under our conditions, the average-case complexity of QuickSort is O(n log2 n) (rather than O(n log n), classically),whereas that of QuickSelect remains O(n).In fact we propose a framework which allows to revisiting three sorting algorithms (QuickSort, Insertion Sort, Bubble Sort) and two selection algorithms (QuickSelect and Minimum Selection). For each algorithm a precise asymptotic estimate for the dominant term of the mean number of symbol comparisons is given where the constants involve various notions of coincidence depending on the algorithm. Explicit expressions for the implied constants are provided by methods from analytic combinatorics. As an aside, in our setting, we are able to derive a lower bound for the average number of symbol comparisons for algorithms solving the sorting problem and using usual comparisons between strings.; On revisite les algorithmes de tri et de recherche classiques en considérant que les entrées de l’algorithme sont des mots infinis et en prenant compte de comparaisons de symboles entre des mots. Nous travaillons sous des modèles probabilistes différents pour lesquels les symboles sont générés par une source générale qui comprend, par exemple, la source sans mémoire, la chaîne de Markov ou même des sources avec les corrélations non bornées. De ce point de vue, une assertion telle que ``la complexité de QuickSort est O(n log n)'' n’est plus vérifiée et il n’est pas aisé de comparer entre eux des algorithmes reposant sur des principes différents de comparaison. Dans ce cadre, nous trouvons que la complexité en moyenne pour le nombre de comparaisons de symboles de QuickSort devient O(n log^2 n) alors que celle de QuickSelect reste en O(n).Nous proposons une méthode générale qui permet de revisiter trois algorithmes de tri QuickSort, Tri Insertion et Tri à Bulles et deux algorithmes de sélection QuickSelect et Sélection du Minimum. Pour chaque algorithme, nous calculons les asymptotiques du nombre moyen de comparaisons de symboles. Les constantes pour les termes dominants sont reliées à des notions différentes de coïncidence et dépendantes des algorithmes. Nous empruntons des méthodes de la combinatoire analytique. Dans notre cadre, nous obtenons de plus une borne inférieure pour le nombre moyen de comparaisons de symboles effectuées par des algorithmes de tri utilisant la comparaison usuelle entre des chaînes de caractères.

We revisit classical textbook sorting or selecting algorithms under a complexity model that fully takes into account the elementary comparisons between symbols composing the records to be processed. Our probabilistic models belong to a broad category of information sources that encompasses memoryless (i.e., independent-symbols) and Markov sources, as well as many unbounded-correlation sources. Under this perspective, commonly accepted assertions, such as ``the complexity of Quicksort is O(n log n)'', are to be challenged, and the relative merits of sorting and searching methods relying on different principles (e.g., radix-based versus comparison-based) can be precisely assessed. For instance we establish that, under our conditions, the average-case complexity of QuickSort is O(n log2 n) (rather than O(n log n), classically),whereas that of QuickSelect remains O(n).In fact we propose a framework which allows to revisiting three sorting algorithms (QuickSort, Insertion Sort, Bubble Sort) and two selection algorithms (QuickSelect and Minimum Selection). For each algorithm a precise asymptotic estimate for the dominant term of the mean number of symbol comparisons is given where the constants involve various notions of coincidence depending on the algorithm. Explicit expressions for the implied constants are provided by methods from analytic combinatorics. As an aside, in our setting, we are able to derive a lower bound for the average number of symbol comparisons for algorithms solving the sorting problem and using usual comparisons between strings., On revisite les algorithmes de tri et de recherche classiques en considérant que les entrées de l’algorithme sont des mots infinis et en prenant compte de comparaisons de symboles entre des mots. Nous travaillons sous des modèles probabilistes différents pour lesquels les symboles sont générés par une source générale qui comprend, par exemple, la source sans mémoire, la chaîne de Markov ou même des sources avec les corrélations non bornées. De ce point de vue, une assertion telle que ``la complexité de QuickSort est O(n log n)'' n’est plus vérifiée et il n’est pas aisé de comparer entre eux des algorithmes reposant sur des principes différents de comparaison. Dans ce cadre, nous trouvons que la complexité en moyenne pour le nombre de comparaisons de symboles de QuickSort devient O(n log^2 n) alors que celle de QuickSelect reste en O(n).Nous proposons une méthode générale qui permet de revisiter trois algorithmes de tri QuickSort, Tri Insertion et Tri à Bulles et deux algorithmes de sélection QuickSelect et Sélection du Minimum. Pour chaque algorithme, nous calculons les asymptotiques du nombre moyen de comparaisons de symboles. Les constantes pour les termes dominants sont reliées à des notions différentes de coïncidence et dépendantes des algorithmes. Nous empruntons des méthodes de la combinatoire analytique. Dans notre cadre, nous obtenons de plus une borne inférieure pour le nombre moyen de comparaisons de symboles effectuées par des algorithmes de tri utilisant la comparaison usuelle entre des chaînes de caractères.

National audience; - Vallois et Tapiero (1994) ont étudié les deux premiers moments du processus d'amplitude d'une marche aléatoire. Dans cette Note, nous obtenons les mêmes résultats par une méthode plus directe. Cette démonstration permet de plus d'obtenir de nouvelles propriétés comme les moments centrés d'ordre 3 et 4, ainsi qu'une relation de récurrence permettant d'obtenir la fonction génératrice.

Since early 90s, timed automata and timed languages are extensively used for modelling and verification of real-time systems, and thoroughly explored from a theoretical standpoint. Recently Asarin and Degorre introduced the notions of volume and entropy of timed languages to quantify the size of these languages and the information content of their elements. In this thesis we build new developments of this theory (called by us volumetry of timed languages) and apply it to several problems occurring in various domains of theoretical computer science such as verification, enumerative combinatorics or information theory. Among other we (i) develop a theory of timed symbolic dynamics; (ii) characterize a dichotomy between bad behaving and well behaving timed automata; (iii) define a least biased stochastic process for a timed automaton; (iv) develop a timed theory of constrained channel coding; (v)count and generate randomly and uniformly permutations in certain classes, Depuis le début des années 90, les automates temporisés et les langages temporisés ont été largement utilisés pour modéliser et vérifier les systèmes temps réels. Ces langages ont été aussi été largement étudiés d'un point de vue théorique. Plus récemment Asarin et Degorre ont introduit les notions de volume et d'entropie des langages temporisés pour quantifier la taille de ces langages et l'information que ses éléments contiennent. Dans cette thèse nous construisons de nouveaux développements à cette théorie (que nous appelons volumétrie des langages temporisés) et l'appliquons a plusieurs problèmes apparaissant dans divers domaine de recherche tel que la théorie de l'information, la vérification, la combinatoire énumérative. Entre autre nous (i) développons une théorie de la dynamique symbolique temporisée~; (ii) caractérisons une dichotomie entre automate temporisé se comportant bien ou mal~; (iii) définissons pour un automate temporisé donné, un processus stochastique d'entropie maximale le moins biaisé possible~; (iv) développons une version temporisé de la théorie des codes sur canal contraint (v) énumérons et générons aléatoirement des permutations dans une certaine classe

The purpose of this thesis is to study a class of power series, which we call Mahlerian, solutions to certain functional equations. These series arise in combinatorial theory, for problems involving counting words, and in the analysis of algorithms, where they are related to divide and conquer recurrences. Methods of solution of Mahlerian equations are based on the properties of rational functions with respect to the fundamental operation, analogue of the derivative for differential equations, and on the arithmetic of operators implicit in these equations. The methods we describe furnish efficient procedures for calculation, qualitative results concerning the closure of this class, and, in the complex case, analytic properties of the solutions. An important subclass of Mahlerian series is provided by B-regular series, a generalization of B-automatic series. They are the translation, via base B arithmetic, of rational series in non- commutative variables, inheriting their properties, familiar in the theory of formal languages. One can define, for example, notions of linear representation, of rank, and of Hankel matrix. Under certain simple conditions, a Mahlerian series is B-regular; in particular most divide and conquer recurrences provide B-regular series. The asymptotic analysis of coefficients of complex Mahlerian series relies on a classification which reveals the significance of B-regular series, on methods from linear algebra, and on methods from the analytic theory of numbers. The results here obtained permit us to handle a number of frequently encountered practical examples. They show, for B-regular series, a connection between the asymptotic behavior of coefficients and the spectra of linear representations. In many cases we exhibit a phenomenon of logarithmic periodicity.; L'objet de cette thèse est l'étude d'une classe de séries entières solutions de certaines équations fonctionnelles, dites mahlériennes. Ces séries interviennent en combinatoire avec des problèmes de comptage de mots et en analyse d'algorithmes où elles sont liées aux récurrences diviser pour régner. La résolution des équations mahlériennes est fondée sur les propriétés des fractions rationnelles vis à vis de l'opérateur fondamental, analogue de la dérivation pour les équations différentielles, et sur l'arithmétique des opérateurs sous-jacents à ces équations. Les méthodes décrites fournissent à la fois des procédés effectifs de calcul et des résultats qualitatifs sur les propriétés de clôture de cette classe et, dans le cas complexe, sur les propriétés analytiques des solutions. Une sous-classe importante de séries mahlériennes est fournie par les séries B-régulières, généralisation des séries B-automatiques. Elles sont la traduction, via la numération en base B, des séries rationnelles en indéterminées non commutatives de la théorie des langages formels et héritent de leurs propriétés. On peut par exemple définir les notions de représentation linéaire, de rang et de matrice de Hankel. Sous certaines conditions simples, une série mahlérienne est B-régulière ; en particulier la plupart des récurrences diviser pour régner fournissent des séries B-régulières. L'analyse asymptotique des coefficients des séries mahlériennes complexes sàppuie sur une classification qui met en valeur l'importance des séries B-régulières, sur des techniques d'algèbre linéaire et sur des méthodes de théorie analytique des nombres. Les résultats obtenus permettent de traiter les exemples rencontrés dans la pratique. Ils montrent pour les séries B-régulières un lien entre le comportement asymptotique des coefficients et le spectre des représentations linéaires et dans beaucoup de cas un phénomène de périodicité en échelle logarithmique.

The purpose of this thesis is to study a class of power series, which we call Mahlerian, solutions to certain functional equations. These series arise in combinatorial theory, for problems involving counting words, and in the analysis of algorithms, where they are related to divide and conquer recurrences. Methods of solution of Mahlerian equations are based on the properties of rational functions with respect to the fundamental operation, analogue of the derivative for differential equations, and on the arithmetic of operators implicit in these equations. The methods we describe furnish efficient procedures for calculation, qualitative results concerning the closure of this class, and, in the complex case, analytic properties of the solutions. An important subclass of Mahlerian series is provided by B-regular series, a generalization of B-automatic series. They are the translation, via base B arithmetic, of rational series in non- commutative variables, inheriting their properties, familiar in the theory of formal languages. One can define, for example, notions of linear representation, of rank, and of Hankel matrix. Under certain simple conditions, a Mahlerian series is B-regular; in particular most divide and conquer recurrences provide B-regular series. The asymptotic analysis of coefficients of complex Mahlerian series relies on a classification which reveals the significance of B-regular series, on methods from linear algebra, and on methods from the analytic theory of numbers. The results here obtained permit us to handle a number of frequently encountered practical examples. They show, for B-regular series, a connection between the asymptotic behavior of coefficients and the spectra of linear representations. In many cases we exhibit a phenomenon of logarithmic periodicity.; L'objet de cette thèse est l'étude d'une classe de séries entières solutions de certaines équations fonctionnelles, dites mahlériennes. Ces séries interviennent en combinatoire avec des problèmes de comptage de mots et en analyse d'algorithmes où elles sont liées aux récurrences diviser pour régner. La résolution des équations mahlériennes est fondée sur les propriétés des fractions rationnelles vis à vis de l'opérateur fondamental, analogue de la dérivation pour les équations différentielles, et sur l'arithmétique des opérateurs sous-jacents à ces équations. Les méthodes décrites fournissent à la fois des procédés effectifs de calcul et des résultats qualitatifs sur les propriétés de clôture de cette classe et, dans le cas complexe, sur les propriétés analytiques des solutions. Une sous-classe importante de séries mahlériennes est fournie par les séries B-régulières, généralisation des séries B-automatiques. Elles sont la traduction, via la numération en base B, des séries rationnelles en indéterminées non commutatives de la théorie des langages formels et héritent de leurs propriétés. On peut par exemple définir les notions de représentation linéaire, de rang et de matrice de Hankel. Sous certaines conditions simples, une série mahlérienne est B-régulière ; en particulier la plupart des récurrences diviser pour régner fournissent des séries B-régulières. L'analyse asymptotique des coefficients des séries mahlériennes complexes sàppuie sur une classification qui met en valeur l'importance des séries B-régulières, sur des techniques d'algèbre linéaire et sur des méthodes de théorie analytique des nombres. Les résultats obtenus permettent de traiter les exemples rencontrés dans la pratique. Ils montrent pour les séries B-régulières un lien entre le comportement asymptotique des coefficients et le spectre des représentations linéaires et dans beaucoup de cas un phénomène de périodicité en échelle logarithmique.