Dans cette thèse, nous nous intéressons aux propriétés topologiques des surfaces, i.e. celles qui sont préservées par des déformations continues. Intuitivement, ces propriétés peuvent être imaginées comme étant celles qui décrivent le forme générale des surfaces. Nous utilisons des cartes combinatoires pour décrire les surfaces. Elles ont le double avantage d'être de naturels objets mathématiques et de pouvoir être transformées naturellement en structure de données.Nous étudions trois problèmes différents. Premièrement, nous donnons des algorithmes pour calculer le nombre géométrique d'intersection de courbes dessinées sur des surfaces. Nous avons obtenu un algorithm quadratique pour calculer le nombre minimal d'auto-intersections dans une classe d'homotopie, un algorithme quartique pour construire un représentant minimal et un algorithme quasi-linéaire pour décider si une classe d'homotopie contient une courbe simple. Ensuite, nous donnons des contre-exemples à une conjecture de Mohar et Thomassen au sujet de l'existence de cycles de partage dans les triangulations. Finalement, nous utilisons les travaux récents de Lévèque et Gonçalves à propos des bois de Schnyder toriques pour construire une bijection entre les triangulations du tore et certaines cartes unicellulaires analogue à le célèbre bijection de Poulalhon et Schaeffer pour les triangulations planaires.Plusieurs points de vue sont utilisés au cours de cette thèse. Nous proposons donc un important chapitre préliminaire où nous insistons sur les connections entre ces différents points de vue. / In this thesis, we focus on the topological properties of surfaces, i.e. those that are preserved by continuous deformations. Intuitively, it can be understood as the properties that describe the general shape of surfaces. We describe surfaces as combinatorial maps. They have the double advantage of being well defined mathematical objects and of being straightforwardly transformed into data-structures.We study three distinct problems. Firstly, we give algorihtms to compute geometric intersection numbers of curves on surfaces. We obtain a quadratic algorithm to compute the minimal number of self-intersections in a homotopy class, a quartic one to construct a minimal representative and a quasi-linear one to decide if a homotopy class contains a simple curve. Secondly, we give counter-examples to a conjecture of Mohar and Thomassen about the existence of splitting cycles in triangulations. Finally, we use the recent work of Gonçalves and Lévèque about toiroidal Schnyder woods to describe a bijection between toroidal triangulations and toroidal unicellular maps analogous to the well known bijection of Poulalhon and Schaeffer for planar triangulations.Many different points of view are involved in this thesis. We thus propose a large preliminary chapter where we provide connections between the different viewpoints.

Studies indicate that global self-esteem, an individual's overall sense of self-worth, and academic self-esteem, self-worth related to academics, are positively related to academic achievement. This relationship holds for white adolescents. However, while still positive, this relationship is weaker for African Americans, who have high global and academic self-esteem, but very low academic achievement. Patterns for Mexican Americans are less clear, but their global and academic self-esteem appear to fall between the range for white and African American adolescents, while their academic achievement is similar to that of African Americans. To address this, I construct Combinatoric Identity Theory (CIT), a symbolic interactionist theory that incorporates the importance of racial/ethnic and student identities into our current understandings of self-esteem and achievement. I then apply CIT to data collected on Mexican American and white tenth-graders.After a discussion of the relevant literature on education, self-esteem, and identity, I discuss my data collection strategy and techniques. This is followed by empirical analysis. Results indicate that identity processes do affect self-esteem, and that they operate in similar ways for Mexican American and white adolescents. Implications of these results and directions for future research are then presented.

Generating functions are important tools that are used in many areas of mathematics and especially statistics. Besides analyzing the general structure of sequences and their asymptotic behavior / these functions, which can be roughly thought as the transformation of sequences into functions, are also used effciently to solve combinatorial problems. In this thesis, the effects of the transformations of generating functions on their corresponding sequences and the effects of the change in sequences on the generating functions are examined. With these knowledge, the generating functions for the resulting sequence of some combinatorial problems such as number of partitions, number of involutions, Fibonacci numbers and Catalan numbers are found. Moreover, some mathematical identities are proved by using generating functions. The sequences are the bases of especially symmetric key cryptosystems in cryptography. It is seen that by using generating functions, linear complexities and periods of sequences generated by constant coeffcient linear homogeneous recursions, which are used in linear feedback shift register (LFSR) based stream ciphers, can be calculated. Hence studying generating functions leads to have a better understanding in them. Therefore, besides combinatorial problems, such recursions are also examined and the results are used to observe the linear complexity and the period of LFSR&rsquo / s combined in different ways to generate &ldquo / better&rdquo / system of stream cipher.

Le sujet de cette thèse est la généralisation non-commutative de résultats probabilistes venant de la théorie des représentations. Les résultats obtenus se divisent en trois parties distinctes. Dans la première partie de la thèse, le concept de groupe quantique easy est étendu au cas unitaire. Tout d'abord, nous donnons une classification de l'ensemble des groupes quantiques easy unitaires dans le cas libre et classique. Nous étendons ensuite les résultats probabilistes de au cas unitaire. La deuxième partie de la thèse est consacrée à une étude du produit en couronne libre. Dans un premier temps, nous décrivons les entrelaceurs des représentations dans le cas particulier d'un produit en couronne libre avec le groupe symétrique libre: cette description permet également d'obtenir plusieurs résultats probabilistes. Dans un deuxième temps, nous établissons un lien entre le produit en couronne libre et les algèbres planaires: ce lien mène à une preuve d'une conjecture de Banica et Bichon. Dans la troisième partie de la thèse, nous étudions un analoque du graphe de Young qui encode la structure multiplicative des fonctions fondamentales quasi-symétriques. La frontière minimale de ce graphe a déjà été décrite par Gnedin et Olshanski. Nous prouvons que la frontière minimale coïncide avec la frontière de Martin. Au cours de cette preuve, nous montrons plusieurs résultats combinatoires asymptotiques concernant les diagrammes de Young en ruban / The subject of this thesis is the non-commutative generalization of some probabilistic results that occur in representation theory. The results of the thesis are divided into three different parts. In the first part of the thesis, we classify all unitary easy quantum groups whose intertwiner spaces are described by non-crossing partitions, and develop the Weingarten calculus on these quantum groups. As an application of the previous work, we recover the results of Diaconis and Shahshahani on the unitary group and extend those results to the free unitary group. In the second part of the thesis, we study the free wreath product. First, we study the free wreath product with the free symmetric group by giving a description of the intertwiner spaces: several probabilistic results are deduced from this description. Then, we relate the intertwiner spaces of a free wreath product with the free product of planar algebras, an object which has been defined by Bisch and Jones. This relation allows us to prove the conjecture of Banica and Bichon. In the last part of the thesis, we prove that the minimal and the Martin boundaries of a graph introduced by Gnedin and Olshanski are the same. In order to prove this, we give some precise estimates on the uniform standard filling of a large ribbon Young diagram. This yields several asymptotic results on the filling of large ribbon Young diagrams

On s'intéresse à deux classes de chaînes de Markov combinatoires. On commence avec les chaînes de Markov de Jonglage, inspirées du modèle de jonglage introduit par Warrington, pour lesquelles on définit des généralisations multivariées des modèles existants. On en calcule les mesures stationnaires et les facteurs de normalisation que l'on exprime par des formules explicites. On s'intéresse également au cas limite où la hauteur maximale à laquelle le jongleur peut lancer ses balles tend vers l'infini. On propose alors une reformulation de la chaîne de Markov en termes de partitions d'entiers, ce qui permet aussi de définir un modèle où le jongleur manipule une infinité de balles. Les preuves sont obtenues en utilisant une chaîne enrichie sur les partitions d'ensembles. On exhibe également, pour l'un des modèles, une propriété de convergence ultrarapide : la mesure stationnaire y est atteinte en un nombre fini d'étapes. Dans le Chapitre suivant, on s'intéresse à des généralisations multivariées de ces modèles : on considère cette fois un jongleur manipulant des balles de différents poids, et lorsqu'une balle entre en collision avec une balle plus légère, cette dernière est éjectée vers le haut, pouvant à son tour en heurter une autre plus légère, jusqu'à ce qu'une balle atteigne l'emplacement le plus élevé. On donnera ici encore une formule explicite pour les mesures stationnaires et les facteurs de normalisation. Dans le dernier Chapitre, on s'intéresse cette fois au modèle du tas de sable stochastique, pour lequel on démontre une conjecture posée par Selig, selon laquelle la mesure stationnaire ne dépend pas de la loi d'ajout des grains de sable. / We consider two types of combinatoric Markov chains. We start with Juggling Markov chains, inspired from Warrington's model. We define multivariate generalizations of the existing models, for which we give stationary mesures and normalization factors with closed-form expressions. We also investigate the case where the maximum height at which the juggler may send balls tends to infinity. We then reformulate the Markov chain in terms of integer partitions, which allows us to consider the case where the juggler interacts with infinitely many balls. Our proofs are obtained through an enriched Markov chain on set partitions. We also show that one of the models has the ultrafast convergence property : the stationary mesure is reached after a finite number of steps. In the following Chapter, we consider multivariate generalizations of those models : the juggler now juggles with balls of different weights, and when a heavy ball collides with a lighter one, this light ball is bumped to a higher position, where it might collide with a lighter one, until a ball reaches the highest position. We give closed-form expressions for the stationary mesures and the normalization factors. The last Chapter is dedicated to the stochastic sandpile model, for which we give a proof for a conjecture set by Selig : the stationary mesure does not depend on the law governing sand grains additions.

Cette thèse se situe dans les domaines de la combinatoire algébrique, bijective et énumérative.Elle s'intéresse à l'étude des fonctions de parking généralisées suivant ces trois axes.medskip. Dans une première partie, on s'intéresse aux fonctions de parking généralisées en tant qu'espèce de structures combinatoires (théorie introduite par A.nom{Joyal} et développée F. nom{Bergeron}, G. nom{Labelle} et P.nom{Leroux}). On définit cette espèce à partir d'une équation fonctionnelle faisant intervenir l'espèce des séquences d'ensembles.On obtient un relèvement non-commutatif de la série indicatrice de cycles dans les fonctions symétriques non-commutatives, exprimé dans différentes bases.Par spécialisation, on obtient de nouvelles formules d'énumérations des fonctions de parking généralisées et de leurs types d'isomorphismes.En remplaçant l'espèce des ensembles par d'autres espèces dans l'équation fonctionnelle, on définit de nouvelles structures: les $seqPF$-tables de parking. Dans les cas particuliers où $seqPF : m mapsto a + b(m-1)$, on établit une bijection entre les $seqPF$-tables de parking et de nouvelles structures arborescentes, généralisant la bijection de C. H.nom{Yan} entre les $seqPF$-fonctions de parking et les séquences de $a$forêts de $b$-arbres.medskip. Dans une seconde partie, on s'intéresse à l'énumération d'automates. On commence par construire une bijection simple entre les automates(non-initiaux) et les séquences d'ensembles. À partir de cette bijection, on extrait la sous-famille des automates quasi-distingués (c'est-à-dire les automates pour lesquels les couples status de terminaison et fonction de transition des états sont distincts). L'énumération de ces automates quasi-distingués fournit une meilleure borne supérieure pour le nombre d'automates minimaux que celle obtenue par M.nom{Domaratzki} & textit{al}. Ensuite, on construit une nouvelle bijection entre les $2m^k$-fonctions de parking et les automates acycliques (non-initiaux) sur un alphabet à $k$ symboles. De cette dernière, on extrait, directement sur les fonctions parking, denombreuses informations de structure sur les automates, en particulier des informations liées à la minimalité.À partir de ces informations, on déduit une formule d'énumération des automates acycliques minimaux.medskipDans une troisième partie, on formalise la technique commune de réalisation polynomiale des algèbres de Hopf: fqsym, wqsym, pqsym, etc. Pour ceci, ondéfinit la notion de type d'alphabet et d'application partitionnante. La notion d'application partitionnante formalise les bonnes propriétés de la standardisation, le tassement, la parkisation, etc associées à ces précédentes algèbres de Hopf. On montre que certaines opérations, produit cartésien, coloration, union ouencore intersection, stabilisent ces notions.À partir de celles-ci, on définit deux constructions d'algèbres de Hopf combinatoire en dualité; et l'on montre qu'elles sont automatiquement munies de structures d'algèbres dendriformes et du produit $#$. En guise d'applications, on définit, pour toute famille de $seqPF$-fonctions deparking, une application généralisant la parkisation. On montre que cette dernière est une application partitionnante si et seulement si $seqPF : nmapsto 1 + m(n-1)$. Ceci permet de retrouver les algèbres de Hopf sur les$m$-fonctions de parking généralisées de J.-C. nom{Novelli} et J-.Y.nom{Thibon}. / This thesis comes within the scope of algebraic, bijective and enumerative combinatorics. It deals with the study of generalized parking functions following those axes.In the first part, we are interested in generalized parking as a species of combinatorial structures. We define this species from a functional equation involving the species of set sequences. We lift the cycle index serie to the non-commutative symmetric functions, express in several bases. By specialization, we obtain new enumeration formula of generalized parking and their isomorphism types.In the functional equation, the species of sets can be replaced by some other species. This defines new structures: the $chi$-parking tables. In particular cases with $chi : m mapsto a + b(m-1)$, we define a bijection between the $chi$-parking tables and new tree structures. This defines a generalization of the C. H. Yan bijection.In the second part, we are interested in the enumeration of automata. Firstly, we construct a simple bijection between (non-initial) automata and sequences of sets. From this bijection we extract a subfamily of quasi-distinguished automata. We obtain a better upper bound of the number of minimal automata than the one of M. Domaratzki.Then we construct a new bijection between $2m^k$-parking functions and (non-initial) acyclic automata over an alphabet of $k$ symbols. From this bijection we extract, from parking function, informations about automata structures. We deduce an enumeration formula of the minimal acyclic automata.In a third part, we formalize the common technique of polynomial realization of Hopf algebras: FQSym, WQSym, PQSym, etc.. We define a notion of type of alphabet and partitioning map. We highlight some operation which stabilizes these notions. Based on this, we define two constructions of dual combinatorial Hopf algebra; and we show that they are automatically endowed of dendriform coalgebra, and $#$-product.As an application, we define, for every family of $chi$-parking functions, a generalization of the parkization. We show that this is a partitionning map if and only if $chi : m mapsto 1 + b(m-1)$.

This thesis deals with optimization problems with main focus on logistic Vehicle Routing Problem (VRP). In the first part term optimization is established and most important optimization problems are presented. Next section deals with methods, which are capable of solving those problems. Furthermore it is explored how to apply those methods to specific VRP, along with presenting some enhancement of those algorithms. This thesis also introduces learning method capable of using knowledge of previous solutions. At the end of the paper, experiments are performed to tune the parameters of used algorithms and to discuss benefit of suggested improvements.

Cette thèse regroupe plusieurs travaux de combinatoire énumérative sur les permutations et permutations d'ensemble. Elle comporte 4 parties.Dans la première partie, nous répondons aux conjectures de Steingrimsson sur les partitions ordonnées d'ensemble. Plus précisément, nous montrons que les statistiques de Steingrimsson sur les partitions ordonnées d'ensemble ont la distribution euler-mahonienne. Dans la deuxième partie, nous introduisons et étudions une nouvelle classe de statistiques sur les mots : les statistiques "maj-inv". Ces dernières sont des interpolations graphiques des célèbres statistiques "indice majeur" et "nombre d'inversions". Dans la troisième partie, nous montrons que la distribution conjointe des statistiques"nombre de croisements" et "nombre d'imbrications" sur les partitions d'ensemble est symétrique. Nous étendrons aussi ce dernier résultat dans le cadre beaucoup plus large des 01-remplissages de "polyominoes lunaires".La quatrième et dernière partie est consacrée à l'étude combinatoire des q-polynômes de Laguerre d'Al-Salam-Chihara. Nous donnerons une interprétation combinatoire de la suite de moments et des coefficients de linéarisations de ces polynômes. / This thesis consists of four chapters, each on a different topic in enumerative combinatorics, all related in some way to the enumeration of permutations or set partitions. In the first chapter, we prove and generalize Steingrimsson's conjectures on Euler-Mahonian statistics on ordered set partitions. In the second chapter, we introduce and study a new class of statistics on words: the "maj-inv" statistics. These are graphical interpolation of the well-known "major index" and "inversion number".In the third chapter, we show that the joint distribution of the numbers of crossings and nestings on set partitions is symmetric. We also put this result in the larger context of enumeration of increasing and decreasing chains in 01-fillings of moon polyominoes.In the last chapter, we decribe various aspects of the Al-Salam-Chihara q-Laguerre polynomials. These include combinatorial descriptions of the polynomials, the moments, the orthogonality relation and a combinatorial interpretation of the linearization coefficients.

En cryptographie, l'utilisation de nombres aléatoires est fréquente (graine, token, ...) et une mauvaise génération d'aléa peut compromettre toute la sécurité d'un protocole, comme en témoigne régulièrement l'actualité. Les générateurs de nombres aléatoires à usage cryptographique sont des composants formés de trois modules : la source brute qui produit de l'aléa (un algorithme ou un phénomène physique), un retraitement pour corriger les défauts de la source, et un retraitement cryptographique pour obtenir l'aléa final. Cette thèse se focalise sur l'analyse des générateurs issus d'une source physique, en vue de dégager des retraitements adaptés à leurs propriétés et résistants à des perturbations de leur environnement d'utilisation. La complexité des dispositifs entravant souvent la formulation explicite d'un modèle stochastique prouvé, leur évaluation repose principalement sur une analyse statistique. Or, les tests statistiques, principale méthode recommandée par les institutions gouvernementales (ANSSI, BSI, NIST) pour certifier ces composants, peuvent détecter des anomalies mais ne permettent pas de les identifier, et de les caractériser. Les travaux de cette thèse structurent la modélisation d'une source d'aléa, vue comme une suite de variables aléatoires, affinent les tests statistiques, et ajoutent une analyse temporelle pour détecter et expliciter ses anomalies au niveau global ou local. Les résultats ont été implantés dans une librairie composée d'un simulateur de perturbations, des outils statistiques et temporels obtenus, des batteries de tests recommandées (FIPS, AIS31, Test U01, SP800), et de retraitements appropriés à certaines anomalies. La structure mise en place a permis d'extraire des familles d'anomalies de motifs dont les propriétés rendent certains tests incapables de distinguer la source anormale d'une source idéalement aléatoire. L'analyse des faiblesses inhérentes aux méthodes statistiques a montré que l'interprétation d'un test par intervalle de rejet ou taux de réussite n'est pas adapté à la détection de certaines fautes de transition. Elle a aussi permis d'étudier les méthodes d'estimations d'entropie, notamment les estimateurs proposés dans la norme SP800-90. Par ailleurs, les paramètres de spécifications de certains générateurs, dont un déduit du standard de chiffrement AES, se sont avérés distinguables grâce aux statistiques de test. Les outils temporels développés évaluent la structure des anomalies, leur évolution au cours du temps et analysent les motifs déviants au voisinage d'un motif donné. Cela a permis d'une part d'appliquer les tests statistiques avec des paramètres pertinents, et d'autre part de présenter des retaitements dont la validité repose sur la structure des anomalies et non sur leur amplitude. / While random numbers are frequently used in cryptography (seed, token, ...), news regurlarly prove how bad randomness generation can compromise the wole security of a protocol. Random number generators for crypthography are components with three steps : a source (an algorithm or physical phenomenon) produces raw numbers which are two times postprocessed to fix anomalies. This thesis focuses on the analysis of physical random bit generators in order to extract postprocessing which will be adapted to the anomalies of the source. As the design of a physical random bit generator is complex, its evaluation is mainly a statistical analysis with hypothesis testing. However, the current standards (AIS31, FIPS140-2, Test U01, SP800) can not provide informations to characterize anomalies. Thus, this thesis adjust several tests and add a time analysis to identify and to make global and local anomalies explicit. A C library was developped, providing anomalies simulator and tools to apply statistical and time analysis results on random bit generators.