Segui questo link per vedere altri tipi di pubblicazioni sul tema: Combinatoire.
Tesi sul tema "Combinatoire"
Cita una fonte nei formati APA, MLA, Chicago, Harvard e in molti altri stili
Vedi i top-50 saggi (tesi di laurea o di dottorato) per l'attività di ricerca sul tema "Combinatoire".
Accanto a ogni fonte nell'elenco di riferimenti c'è un pulsante "Aggiungi alla bibliografia". Premilo e genereremo automaticamente la citazione bibliografica dell'opera scelta nello stile citazionale di cui hai bisogno: APA, MLA, Harvard, Chicago, Vancouver ecc.
Puoi anche scaricare il testo completo della pubblicazione scientifica nel formato .pdf e leggere online l'abstract (il sommario) dell'opera se è presente nei metadati.
Vedi le tesi di molte aree scientifiche e compila una bibliografia corretta.
1
Fossat, Jean-Michel. "La combinatoire". Lyon 3, 1987. http://www.theses.fr/1987LYO31019.
Testo completoAbstract (sommario):
Cette these etudie deux principales idees du de arte combinatoria de leibniz et leurs developpements au cours des trois derniers siecles. La premiere de ces deux idees est la generation d'une totalite par combinaison d'elements primitifs. La seconde est le concept d'expression ou isomorphisme dans les mathematiques contemporaines. D'un point de vue philosophique, ce travail expose l'irreductible opposition entre raison calculante et raison organiqueThis thesis studies two main ideas of leibniz's de arte combinatoria and their developments during the last three centuries. The first of these two ideas is the generation of a totality by combinations of primitive elements. The second is the concept of expression or isomorphism in the contemporary mathematics. From a philosophical point of vew. This work shows the irreducible opposition between calculating reason and organic reason
2
Lass, Bodo. "Calcul combinatoire ensembliste". Université Louis Pasteur (Strasbourg) (1971-2008), 2001. http://www.theses.fr/2001STR13173.
Testo completo
3
Delobel, Philippe. "De la combinatoire". Grenoble 2 : ANRT, 1987. http://catalogue.bnf.fr/ark:/12148/cb376044411.
Testo completo
4
Zhou, Jian-Hua. "Combinatoire des dérivations". Marne-la-Vallee, 1996. http://www.theses.fr/1996MARN0003.
Testo completo
5
Giraudo, Samuele. "Combinatoire algébrique des arbres". Phd thesis, Université Paris-Est, 2011. http://pastel.archives-ouvertes.fr/pastel-00674619.
Testo completoAbstract (sommario):
Cette thèse se situe dans le domaine de la combinatoire algébrique et porte sur la construction de plusieurs structures combinatoires et algébriques sur différentes espèces d'arbres. Après avoir défini un analogue du monoïde plaxique dont les classes d'équivalence sont indexées par les couples d'arbres binaires jumeaux, nous proposons un analogue de la correspondance de Robinson-Schensted dans ce contexte. À partir de ce monoïde, nous construisons une sous-algèbre de Hopf de l'algèbre de Hopf des fonctions quasi-symétriques libres dont les bases sont indexées par les couples d'arbres binaires jumeaux. Ensuite, nous proposons un foncteur combinatoire de la catégorie des monoïdes vers la catégorie des opérades ensemblistes. En utilisant ce foncteur, nous construisons plusieurs opérades qui mettent en jeu divers objets combinatoires. Par le biais d'une construction qui à une opérade associe une algèbre de Hopf non commutative, nous obtenons à partir de l'une des opérades obtenue par notre construction, une algèbre de Hopf basée sur les forêts ordonnées d'arbres plans enracinés. Nous proposons une réalisation polynomiale de cette dernière. Finalement, nous établissons certaines propriétés vérifiées par les arbres binaires équilibrés dans le treillis de Tamari. Nous montrons que l'ensemble des arbres binaires équilibrés y est clos par intervalle et que les intervalles d'arbres binaires équilibrés ont la forme d'hypercubes. Dans l'objectif de dénombrer ces intervalles, nous introduisons une nouvelle sorte de grammaires d'arbres, les grammaires synchrones. Celles-ci permettent d'obtenir une équation fonctionnelle de point fixe pour la série génératrice des arbres qu'elles engendrent
6
Dasse-Hartaut, Sandrine. "Combinatoire des tableaux escalier". Paris 7, 2014. http://www.theses.fr/2014PA077070.
Testo completoAbstract (sommario):
Les tableaux escalier sont des objets combinatoires définis par S. Corteel et L. Williams, qui généralisent les tableaux de permutations et les tableaux alternatifs. Ils ont été utilisés pour donner une formule combinatoire pour les moments des polynômes d'Askey-Wilson. Les tableaux escalier sont également liés au processus d'exclusion asymétrique sur un réseau unidimensionnel avec bords ouverts, l'ASEP, un modèle de physique statistique important et sujet de nombreuses études, et ont permis de donner une formule combinatoire pour en exprimer la probabilité stationnaire. On montre ici différentes approches des tableaux escalier : une approche probabiliste permet d'en déduire des propriétés exactes et asymptotiques, une approche bijective permet de découvrir des propriétés de sous-ensembles de ces tableaux, via les tree-like tableaux ou des tables d'inversion. Enfin, une chaîne de Marov sur un sous-ensemble des tableaux escalier confirme intuitivement les formules obtenues par le calcul de la probabilité stationnaire du PASEPA relatively new combinatorial structure, called staircase tableaux, was introduced in recent work of S. Corteel and L. Williams. Staircase tableaux are a generalisation of permutation tableaux and alternative tableaux. Their study gave a combinatorial formula for the moments of Askey-Wilson polynomials. Staircase tableaux are also related to the asymmetric exclusion process on a one-dimensional lattice with open boundaries (ASEP), an important and heavily studied particle model in statistical mechanics. The study of the generating function of the staircase tableau has given a combinatorial formula for the steady state probability of the ASEP. We use differents approaches to study the staircase tableaux : with a probabilistic approach, we prove the asymptotic normality of some parameters of the staircase tableaux ; with bijective combinatorics, we get the properties of some subsets of staircase tableaux, using for example tree-like tableaux or permutations. Finally, a Markov chain on a subset of staircase tableaux confirms intuitively the formula for the steady state probability without using the matrix ansatz
7
PROSPER, VINCENT. "Combinatoire des polynomes multivaries". Paris 7, 1999. http://www.theses.fr/1999PA077208.
Testo completoAbstract (sommario):
La premiere partie presente l'anneau des polynomes symetriques et les outils combinatoires habituellement introduits pour la definition de differentes bases lineaires de cet anneau, ainsi que la structure multiplicative. Les operations sur les ensembles de variables conduisent a utiliser les polynomes symetriques comme des operateurs sur les polynomes a coefficients reels (l'anneau des polynomes est muni d'une structure de lambda-anneau). Outre l'avantage de fournir des notations compactes, ceci montre que toute formule impliquant les fonctions symetriques provient des trois axiomes de definition des lambda-anneaux, la formule de cauchy jouant un role fondamental. Differentes specialisations permettent de retrouver des objets combinatoires classiques. La deuxieme partie expose plusieurs calculs multivaries lies a l'action des differences divisees sur les polynomes. Les puissances modifiees et les polynomes de schubert presentent des proprietes de factorisation en rapport avec l'interpolation de newton. Les specialisations des alphabets fournissent la encore des generalisations de nombres classiques. En outre, la factorisation de la q-specialisation des polynomes de schubert donne comme sous-produit une statistique double sur les tableaux de young standards qui etend la charge. Nous examinons les cas particuliers de la factorisation des fonctions de schur factorielles et q-factorielles. La troisieme partie du document consiste en une description technique d'un outil informatique qui s'inspire non seulement des deux themes precedents, mais se veut aussi un environnement de calcul general en combinatoire algebrique pour le logiciel de calcul formel mupad. Nous avons integre a cet environnement la possibilite d'interagir avec un autre logiciel performant et specialise en combinatoire des groupes. Les calculs traitables par cet environnement concernent les lambda-anneaux, les groupes symetriques, les fonctions symetriques, ainsi que les polynomes de schubert.
8
Champeimont, Raphael. "Combinatoire des mutations génétiques". Thesis, Paris 6, 2014. http://www.theses.fr/2014PA066636/document.
Testo completoAbstract (sommario):
Dans une première partie, je présente le travail que j’ai accompli sur la coévolution moléculaire. Je présente le contexte biologique et les différentes mesures qui permettent de détecter la conservation et la coévolution à l’échelle des acides aminés. Ensuite, je montre une application de ces mesures à la détection des résidus critiques dans la protéine P53 liée au cancer. Dans ce but, j’ai créé une évaluation des différentes méthodes de prédiction. J’utilise ensuite la même méthodologie sur une base de données de mutations liées à des maladies génétiques. Je montre également comment la coévolution au niveau des résidus permet de découvrir des interactions protéine-protéine sur le virus de l’hépatite C. Enfin, je présente l’algorithme PruneTree, qui permet de filtrer des ensembles de séquences utilisés comme entrée par les programmes de détection de coévolution.Dans une deuxième partie, je m’intéresse à l’étude de l’évolution à l’échelle du génome, en particulier aux mécanismes de recombinaison méiotique. Pour cela j’ai considéré le taux de recombinaison le long du génome et sa cause, les cassures double-brin de l’ADN. Je présente alors un modèle de la distribution de ces cassures et de la liaison des différentes protéines liées à la recombinaison. Je présente également une méthode de détection de périodicité le long du génome basée sur les transformées de Fourier.Enfin, dans la dernière partie, je présente un nouvel algorithme pour simuler l’évolution des génomes de façon à évaluer les outils de reconstruction, et le paquet R-CLAG permettant d’utiliser l’algorithme de classification CLAG depuis RIn a first part, I show the work I have done on molecular evolution. I present the general biological background and the measures that allow us to detect both conservation and coevolution at the amino-acid level. Then, I present an application of these measures to the detection of critical residues in the cancer protein P53. To this end, I have made a benchmark of different prediction methods. I then use the same methodology on a large scale database of pathogenic mutations linked to genetic diseases. After that, I show how residue-level coevolution can help us discover protein-protein interactions in the hepatitis C virus. Finally, I present the PruneTree algorithm, which allows filtering sequence sets used as input for molecular coevolution detection methods. In a second part, I have studied evolution at the genome level, in particular the recombination mechanisms that occur during meiosis. I have looked at the recombination rates along the genomes and its primary cause, the double-strand breaks, but also at the density of other proteins involved in recombination. I also present a method based on Fourier transforms to analyze these genomic signals, and a model for the distribution along the genome of double-strand breaks and recombination proteins. Finally, I present the other tools I have developed. I describe a novel algorithm that can simulate the evolution of genomes in order to benchmark the phylogenetic reconstruction algorithm PhyChro. Finally, I present the R-CLAG package that allows for easy use of the clustering algorithm CLAG
9
Champeimont, Raphael. "Combinatoire des mutations génétiques". Electronic Thesis or Diss., Paris 6, 2014. http://www.theses.fr/2014PA066636.
Testo completoAbstract (sommario):
Dans une première partie, je présente le travail que j’ai accompli sur la coévolution moléculaire. Je présente le contexte biologique et les différentes mesures qui permettent de détecter la conservation et la coévolution à l’échelle des acides aminés. Ensuite, je montre une application de ces mesures à la détection des résidus critiques dans la protéine P53 liée au cancer. Dans ce but, j’ai créé une évaluation des différentes méthodes de prédiction. J’utilise ensuite la même méthodologie sur une base de données de mutations liées à des maladies génétiques. Je montre également comment la coévolution au niveau des résidus permet de découvrir des interactions protéine-protéine sur le virus de l’hépatite C. Enfin, je présente l’algorithme PruneTree, qui permet de filtrer des ensembles de séquences utilisés comme entrée par les programmes de détection de coévolution.Dans une deuxième partie, je m’intéresse à l’étude de l’évolution à l’échelle du génome, en particulier aux mécanismes de recombinaison méiotique. Pour cela j’ai considéré le taux de recombinaison le long du génome et sa cause, les cassures double-brin de l’ADN. Je présente alors un modèle de la distribution de ces cassures et de la liaison des différentes protéines liées à la recombinaison. Je présente également une méthode de détection de périodicité le long du génome basée sur les transformées de Fourier.Enfin, dans la dernière partie, je présente un nouvel algorithme pour simuler l’évolution des génomes de façon à évaluer les outils de reconstruction, et le paquet R-CLAG permettant d’utiliser l’algorithme de classification CLAG depuis RIn a first part, I show the work I have done on molecular evolution. I present the general biological background and the measures that allow us to detect both conservation and coevolution at the amino-acid level. Then, I present an application of these measures to the detection of critical residues in the cancer protein P53. To this end, I have made a benchmark of different prediction methods. I then use the same methodology on a large scale database of pathogenic mutations linked to genetic diseases. After that, I show how residue-level coevolution can help us discover protein-protein interactions in the hepatitis C virus. Finally, I present the PruneTree algorithm, which allows filtering sequence sets used as input for molecular coevolution detection methods. In a second part, I have studied evolution at the genome level, in particular the recombination mechanisms that occur during meiosis. I have looked at the recombination rates along the genomes and its primary cause, the double-strand breaks, but also at the density of other proteins involved in recombination. I also present a method based on Fourier transforms to analyze these genomic signals, and a model for the distribution along the genome of double-strand breaks and recombination proteins. Finally, I present the other tools I have developed. I describe a novel algorithm that can simulate the evolution of genomes in order to benchmark the phylogenetic reconstruction algorithm PhyChro. Finally, I present the R-CLAG package that allows for easy use of the clustering algorithm CLAG
10
AIt, Yahia Karim. "Techniques de recherche opérationelle appliquées à la gestion d'entrepôts et de terminaux portuaires". Le Havre, 2010. http://www.theses.fr/2010LEHA0018.
Testo completo
11
El, Ghaziri Hassan. "Algorithmes connexionnistes pour l'optimisation combinatoire /". [S.l.] : [s.n.], 1993. http://library.epfl.ch/theses/?nr=1167.
Testo completo
12
Tomasini, Jérôme. "Géométrie combinatoire des fractions rationnelles". Thesis, Angers, 2014. http://www.theses.fr/2014ANGE0032/document.
Testo completoAbstract (sommario):
Le but de cette thèse est d’étudier, à l’aide d’outils combinatoires simples, différentes structures géométriques construites à partir de l’action d’un polynôme ou d’une fraction rationnelle. Nous considérerons d’abord la structure de l'ensemble des solutions séparatrices d’un champ de vecteurs polynomial ou rationnel. Nous allons établir plusieurs modèles combinatoires de ces cartes planaires, ainsi qu’une formule fermée énumérant les différentes structures topologiques dans le cas polynomial. Puis nous parlerons de revêtements ramifiés de la sphère que nous modéliserons, via un objet combinatoire nommée carte équilibrée, à partir d’une idée originale de W.Thurston. Ce modèle nous permettra de démontrer (géométriquement) de nombreuses propriétés de ces objets, et d’offrir une nouvelle approche et de nouvelles perspectives au problème d’Hurwitz, qui reste encore aujourd’hui un problème ouvert. Et enfin nous aborderons le sujet de la dynamique holomorphe via les primitives majeures dont l’utilité est de permettre de paramétrer les systèmes dynamiques engendrés par l’itération de polynômes. Cette approche nous permettra de construire une bijection entre les suites de parking et les arbres de Cayley, ainsi que d’établir une formule fermée liée à l’énumération d’un certain type d’arbres relié à la fois aux primitives majeures et aux revêtements ramifiés polynomiauxThe main topic of this thesis is to study, thanks to simple combinatorial tools, various geometric structures coming from the action of a complex polynomial or a rational function on the sphere. The first structure concerns separatrix solutions of polynomial or rational vector fields. We will establish several combinatorial models of these planar maps, as well as a closed formula enumerating the different topological structures that arise in the polynomial settings. Then, we will focus on branched coverings of the sphere. We establish a combinatorial coding of these mappings using the concept of balanced maps, following an original idea of W. Thurston. This combinatorics allows us to prove (geometrically) several properties about branched coverings, and gives us a new approach and perspective to address the still open Hurwitz problem. Finally, we discuss a dynamical problem represented by primitive majors. The utility of these objects is to allow us to parameterize dynamical systems generated by the iterations of polynomials. This approach will enable us to construct a bijection between parking functions and Cayley trees, and to establish a closed formula enumerating a certain type of trees related to both primitive majors and polynomial branched coverings
13
Morcrette, Basile. "Combinatoire analytique et modèles d'urnes". Phd thesis, Université Pierre et Marie Curie - Paris VI, 2013. http://tel.archives-ouvertes.fr/tel-00843046.
Testo completoAbstract (sommario):
Cette thèse étudie les urnes de Pólya à travers le prisme de la combinatoire analytique. Les urnes sont des modèles, conceptuellement très simples, de dynamique de croissance ou d'extinction dont les comportements limites sont extrêmement variés. Ces modèles sont largement étudiés par des approches probabilistes mais la compréhension précise des diverses lois limites reste une question ouverte. Les travaux de Flajolet et al. en 2005 ont illustré que pour ces questions, une approche par combinatoire analytique peut se révéler très fructueuse: l'étude des propriétés (nature, singularités) des séries génératrices associées aux urnes donne accès à des lois limites avec grande précision. Cette thèse s'inscrit dans la continuité de ces travaux et commence par identifier les séries des urnes de nature algébrique, grâce à un algorithme sophistiqué issu du calcul formel (Divination/Preuve automatique). Pour les classes d'urnes algébriques, nous menons des analyses, exacte et asymptotique, afin de connaître avec précision les comportements limites (structures des moments, vitesse de convergence, aspects limites locaux). Puis, l'étude d'urnes non algébriques est faite au travers d'exemples concrets portant sur la modélisation de réseaux sociaux, ainsi que sur la combinatoire des formules booléennes. Enfin, à travers des modèles d'urnes plus généraux (absence d'équilibre, présence d'aléa au sein des règles de substitution), nous montrons que l'approche symbolique de la combinatoire analytique est robuste. En particulier, une étude combinatoire générale des urnes sans condition d'équilibre est réalisée pour la première fois, unissant toute urne à une équation aux dérivées partielles.
14
Tannier, Eric. "Evolution Combinatoire, Algorithmique des Chromosomes". Habilitation à diriger des recherches, Université Claude Bernard - Lyon I, 2011. http://tel.archives-ouvertes.fr/tel-00750199.
Testo completoAbstract (sommario):
Ce mémoire est une présentation de certains de mes travaux de recherches effectués en bioinformatique au laboratoire de Biométrie et Biologie Evolutive de l'université de Lyon 1 depuis 2003, date de mon arrivée en post-doctorat à l'INRIA, suivie de la stabilisation de mon poste un an après.
15
Aval, Jean-Christophe. "Combinatoire autour du groupe symétrique". Habilitation à diriger des recherches, Université Sciences et Technologies - Bordeaux I, 2013. http://tel.archives-ouvertes.fr/tel-00978093.
Testo completoAbstract (sommario):
Cette HDR présente mes travaux récents en combinatoire (énumérative et algébrique) autour du groupe symétrique, et répartis sur trois axes principaux : les co-quasi-invariants polynomiaux, les matrices à signes alternants et les tableaux boisés.
16
Deneufchâtel, Matthieu. "Intégrales Itérées en Physique Combinatoire". Phd thesis, Université Paris-Nord - Paris XIII, 2012. http://tel.archives-ouvertes.fr/tel-00736727.
Testo completoAbstract (sommario):
Nous présentons différents résultats liés par les outils et les structures qu'ils font intervenir (intégrales itérées, produits de mélange). Dans la première partie, nous considérons le calcul de certaines intégrales de type Selberg et leurs limites lorsque le nombre de variables tend vers l'infini. Dans le cas général, on montre que le résultat s'exprime comme un produit dont le nombre de facteurs ne dépend pas du nombre de variables (sous certaines conditions). Si la puissance du déterminant de Vandermonde vaut 2, il est possible de calculer la limite de ces intégrales lorsque le nombre de variables tend vers l'infini à l'aide d'opérateurs liés à l'interpolation de Newton. Dans la seconde partie, nous étudions les propriétés de dépendance linéaire de familles de fonctions obtenues par intégrales itérées et donnons un critère qui permet d'assurer l'indépendance linéaire d'une famille infinie de fonctions à partir de l'étude des relations entre les fonctions obtenues par intégrales simples. Nous montrons comment construire effectivement les corps de germes de fonctions analytiques nécessaires et en donnons quelques exemples qui permettent d'étendre les résultats connus sur les hyperlogarithmes. Ensuite, nous étudions certaines bases de l'algèbre libre dans le but d'appliquer la factorisation de Schützenberger. Nous rappelons quelques résultats classiques, puis nous intéressons à la famille obtenue à partir des mots de Lyndon. Celle-ci ne permet pas d'écrire la factorisation qui nous intéresse mais nous précisons les caractéristiques de sa famille duale. Enfin, nous donnons un critère relatif à deux familles en dualité assurant que l'on peut écrire cette factorisation.
17
Mouyart-Tassin, Annie-Françoise. "Combinatoire constructive : carrés et hyperétoiles". Lille 1, 1985. http://www.theses.fr/1985LIL10076.
Testo completoAbstract (sommario):
Étude de deux familles de configurations : les carrés, dérivés des carrés latins et les décompositions de l'hypergraphe complet en sous-hypergraphes isomorphes. Définition de quelques carrés. Existence des carrés doubles symétriques inséparables. Hyperétoiles. Un problème de documentation automatique. Décomposition de l'hypergraphe régulier complet. Hyperétoiles à rayons simples. Hyperétoiles à centre simple.
18
Hivert, Florent. "Combinatoire des fonctions quasi-symétiques". Université de Marne-la-Vallée, 1999. http://www.theses.fr/1999MARN0051.
Testo completoAbstract (sommario):
Nous introduisons de nouvelles actions du groupe symetrique et de son algebre de hecke sur les polynomes, pour lesquelles les invariants sont les polynomes quasi-symetriques. Nous interpretons cette construction en termes de caracteres de demazure d'un groupe quantique degenere. Nous utilisons l'action de l'algebre de hecke generique pour definir des analogues quasi-symetriques et non commutatifs des fonctions de hall-littlewood. Nous montrons que ces fonctions generalisees ont un certain nombre de proprietes communes avec les fonctions classiques. Dans un deuxieme temps, nous construisons une generalisation des fonctions quasi-symetriques appelee fonctions quasi-symetriques matricielles. Ceci peut etre vue comme une generalisation de l'algebre de convolution des permutations de malvenuto-reutenauer. Enfin nous etudions un analogue du monoide plaxique appele monoide chinois. Nous definissons un objet combinatoire qui joue le role des tableaux de young pour ce monoide, et en particulier, nous donnons un analogue de la correspondance de robinson-schensted
19
Bordat, Jean-Paul. "Sur l'algorithmique combinatoire d'ordres finis". Montpellier 2, 1992. http://www.theses.fr/1992MON20060.
Testo completoAbstract (sommario):
Cet ouvrage propose tout d'abord des algorithmes de resolution de problemes polynomiaux (calcul de la fermeture et de la reduction transitives, reconnaissance) sur les classes d'ordre classiques: ordres gradues, semi-modulaires, treillis distributifs, ce qui permet dans une deuxieme phase d'aborder des problemes plus difficieles (calcul du nombre de sauts, de la dimension, isomorphisme), et de resoudre efficacement ces derniers sur la classe des ordres decomposables en ordres de largeur bornee
20
Rouillon-Couture, Nadine. "Calcul et image en combinatoire". Bordeaux 1, 1994. http://www.theses.fr/1994BOR10626.
Testo completoAbstract (sommario):
Cette these a pour objet l'etude et la realisation d'un environnement logiciel destine aux chercheurs en combinatoire: calico, acronyme de calcul et image en combinatoire. Calico permet, dans un environnement distribue, de manipuler des objets combinatoires, tant sur le plan graphique que sur le plan mathematique. La collaboration, au sein d'un meme environnement federateur, d'ateliers graphiques, d'ateliers de calcul et d'une base de connaissances, fait de calico un outil puissant d'aide a la reflexion. Les premiers offrent la possibilite de travailler sur le dessin des objets et les deuxiemes sur leurs representations formelles. En particulier, l'atelier de calcul, ecrit en maple, archive et classe suivant des criteres mathematiques tout objet qui transite par lui. Cette approche permet par des methodes automatiques, de collecter les proprietes verifiees par des objets manipules. Enfin la couleur est une composante essentielle de calico: elle est le support visuel qui transcrit les statistiques calculees sur les objets
21
Boria, Nicolas. "Optimisation combinatoire et environnements dynamiques". Paris 9, 2011. http://basepub.dauphine.fr/xmlui/handle/123456789/7232.
Testo completo
22
Deneufchatel, Matthieu. "Intégrales Itérées en Physique Combinatoire". Paris 13, 2012. http://scbd-sto.univ-paris13.fr/intranet/edgalilee_th_2012_deneufchatel.pdf.
Testo completoAbstract (sommario):
Nous présentons différents résultats liés par les outils et les structures qu’ils font intervenir (intégrales itérées, produits de mélange). Dans la première partie, nous considérons le calcul de certaines intégrales de type Selberg et leurs limites lorsque le nombre de variables tend vers l’infini. Dans le cas général, on montre que le résultat s’exprime comme un produit dont le nombre de facteurs ne dépend pas du nombre de variables (sous certaines conditions). Si la puissance du déterminant de Vandermonde vaut 2, il est possible de calculer la limite de ces intégrales lorsque le nombre de variables tend vers l’infini à l’aide d’opérateurs liés à l’interpolation de Newton. Dans la seconde partie, nous étudions les propriétés de dépendance linéaire de familles de fonctions obtenues par intégrales itérées et donnons un critère qui permet d’assurer l’indépendance linéaire d’une famille infinie de fonctions à partir de l’étude des relations entre les fonctions obtenues par intégrales simples. Nous montrons comment construire effectivement les corps de germes de fonctions analytiques nécessaires et en donnons quelques exemples qui permettent d’étendre les résultats connus sur les hyperlogarithmes. Ensuite, nous étudions certaines bases de l’algèbre libre dans le but d’appliquer la factorisation de Schützenberger. Nous rappelons quelques résultats classiques, puis nous intéressons à la famille obtenue à partir des mots de Lyndon. Celle-ci ne permet pas d’écrire la factorisation qui nous intéresse mais nous précisons les caractéristiques de sa famille duale. Enfin, nous donnons un critère relatif à deux familles en dualité assurant que l’on peut écrire cette factorisationWe present several results linked by the tools and by the underlying structures we use (iterated integrals, shuffle products). In the first part, we are interested in the computation of integrals of Selberg type and in their asymptotics when the number of variables tends to infinity. In the general case, we show that the result can be expressed as a product whose number of factors does not depend on the number of variables (under certain conditions). If the power of the Vandermonde determinant equals 2, the limit of the integral when the number of variables tends to infinity can be computed with operators related to Newton’s interpolation. The second part has two sections which are related to special functions called hyperlogarithms. We start with the question of the linear independence of a family of functions obtained by iterated integrals and give a criterion that links the properties of the whole family to the behavior of the functions obtained by simple integrals. We show how to construct the required fields of germs of analytic functions which play an important role. Several examples allow us to extend the known results. Then we come back to the free algebra and the properties of dual families, our main interest being Schützenberger’s factorisation. We recall some classical results in the partially commutative case ; then we consider the family obtained by dualisation from the Lyndon words. It is not possible to write the factorisation for these dual families but we make precise the nature of the elements of the family obtained by duality. Finally, we present a criterion that gives a condition on the dual families for the factorisation to hold
23
Chung, Yerim. "Optimisation combinatoire inverse et applications". Paris 1, 2010. http://www.theses.fr/2010PA010009.
Testo completoAbstract (sommario):
L'optimisation combinatoire inverse a suscité beaucoup d'attention de la communauté de la recherche opérationnelle pendant les deux dernières décennies. Étant donnée une instance d'un problème d'optimisation combinatoire définie par un système de paramètres (coûts, profits, etc. ) et une solution réalisable, le problème inverse associé consiste à modifier au minimum les paramètres afin de rendre la solution fixée optimale dans l'instance modifiée. Dans le cadre de l'optimisation combinatoire, de nombreux problèmes inverses ont été étudiés, mais relativement peu d'études ont été menées sur des versions inverses de problèmes NP-difficiles. Dans cette thèse, nous considérons des problèmes combinatoires inverses généralisés. Nous commençons par imposer certaines contraintes aux paramètres à modifier. En particulier, des contraintes booléennes nous permettent de définir des versions inverses de problèmes non pondérés. Ainsi, des contraintes discrètes engendrent des problèmes combinatoires inverses eux-même combinatoires. Nous introduisons alors deux variantes de problèmes combinatoires inverses généralisés, à savoir "les problèmes inverses contre un algorithme spécifié" et "les problèmes inverses en valeur". Pour la première, un algorithme étant spécifié pour le problème d'origine, on cherche, pour une instance et une solution réalisable fixées, à modifier le moins possible l'instance pour que cette solution puisse être choisie par l'algorithme. Un problème inverse en valeur quant à lui est défini en spécifiant une valeur à atteindre au lieu d'une solution cible. L'objectif est de modifier le moins possible l'instance considerée de sorte que la valeur optimale de l'instance modifiée soit égale à la valeur fixée. Nous étudions différentes versions inverses de problèmes NP-difficiles. Les problèmes abordés sont le stable maximum d'un graphe (ensemble maximum de sommets 2 à 2 non adjacents), le voyageur de commerce minimum et la coloration minimum des sommets d'un graphe. Notre principal objectif est d'étudier la complexité et l'approximabilité de ces problèmes.
24
Lévy, Bruno. "Topologie Algorithmique : combinatoire et Plongement". Vandoeuvre-les-Nancy, INPL, 1999. http://www.theses.fr/1999INPL094N.
Testo completoAbstract (sommario):
La modélisation 3D s’appuie sur deux principales familles de méthodes. L’une de ces familles de méthodes, appelée souvent courbes et surfaces, se fonde sur une représentation des objets à modéliser par des fonctions (le plus souvent polynomiales). L’autre famille de représentations consiste à discrétiser les objets en cellules (sommets, segments, polygones, polyèdres. . ). Nous étudions ici les problèmes liés à ce dernier type de représentation discrète des objets, ainsi que ses relations avec les « courbes et surfaces ». En utilisant le formalisme offert par la Topologie, une branche moderne des mathématiques, nous allons étudier les problèmes suivants : Définir des structures de données efficaces pour représenter la décomposition des objets en éléments discretsGénérer et éditer interactivement des objets, de manière à respecter des données ainsi que des contraintes globales concernant la forme des objets. - Constuire une paramétrisation sous contraintes d’une surface triangulée, afin de pouvoir facilement lui associer des valeurs. Le premier point sera traité en utilisant certains résultats de topologie combinatoire, et les deux derniers seront étudiés en termes d’homéomorphisme et de transformation continue. Nous présenterons également plusieurs applications de ces méthodes, permettant de résoudre des problèmes de modélisation en géologie numérique. Par exemple, nous montrerons comment modéliser de manière précise les variations de porosité de la roche à l’intérieur d’un réservoir naturel. Des applications possibles de nos méthodes à l’image de synthèse et au placage de textures seront également évoquées
25
Laubie, Paul. "Combinatoire, homotopie et plongements d’opérades". Electronic Thesis or Diss., Strasbourg, 2024. http://www.theses.fr/2024STRAD008.
Testo completoAbstract (sommario):
Les opérades algébriques sont un outil algébrique permettant d’encoder certaines variétés d’algèbres non-nécessairement associatives, comme les algèbres de Lie ou les algèbres pre-Lie. De plus, les opérades algébriques peuvent elles-mêmes être vues comme des algèbres dans une catégorie bien choisie. Cette remarque permet l’étude des opérades via les puissants outils de l’algèbre homologique. En parallèle, la catégorie monoïdale telle que les objets en monoïde de cette catégorie sont les opérades est la catégorie des espèces combinatoires munie du pléthysme. Cela permet d’adopter un point de vue très combinatoire sur les opérades donnant ainsi des descriptions très explicites des objets considérés. Ces deux approches synergisent très bien ensemble et cette thèse se concentrera sur l'interaction entre ces deux points de vue. En effet, nous utiliserons des outils homotopiques tels que la dualité de Koszul opéradique pour obtenir des informations combinatoires sur les opérades que nous étudions. Nous utilisons ensuite celles-ci pour obtenir des descriptions combinatoires permettant d'effectuer des calculs explicites. Cette thèse est divisée en trois parties. La première partie est une introduction à la théorie des espèces. Ensuite, nous donnons une introduction à la théorie des opérades algébriques et à la dualité de Koszul opéradique. Enfin, nous calculons certaines descriptions combinatoires d’opérades, et les appliquons pour prouver une conjecture de Dotsenko sur un plongement de l'opérade encodant la structure algébrique sur le champ de vecteurs des variétés de FrobeniusAlgebraic operads are an algebraic tool for encoding some varieties of algebras, not necessarily associative, such as Lie algebras or pre-Lie algebras. Moreover, algebraic operads can themselves be viewed as algebras in a well-chosen category. This observation allows the study of operads using the powerful tools of homological algebra. Simultaneously, the monoidal category where the monoid objects are operads is the category of combinatorial species equipped with plethysm. This enables a very combinatorial perspective on operads, providing explicit descriptions of the considered objects. These two approaches synergize well together, and this thesis will focus on the interaction between these two viewpoints. Indeed, we will use homotopical tools such as operadic Koszul duality to obtain combinatorial information on the operads we study. We then use this information to derive combinatorial descriptions that allow for explicit computations. This thesis is divided into three parts. The first part is an introduction to the theory of species. Next, we provide an introduction to the theory of algebraic operads and operadic Koszul duality. Finally, we compute descriptions of operads and apply them to prove a conjecture by Dotsenko on embedding the operad encoding the algebraic structure on the vector field of Frobenius manifolds
26
El, Maftouhi Abdelhakim. "Méthodes probabilistes en combinatoire et théorie des graphes". Paris 11, 1994. http://www.theses.fr/1994PA112408.
Testo completoAbstract (sommario):
Cette thèse rassemble plusieurs travaux dont le point commun est l'utilisation de méthodes probabilistes. La première partie concerne l'étude des paramètres de domination et d'irredondance dans les graphes aléatoires de probabilité d'arête 1/2. Nos résultats apportent un point final à l'étude du trio: irredondance, domination et stabilité dans ces graphes. Dans la deuxième partie on délaisse momentanément les probabilités pour aborder les graphes signés. On s'intéresse plus particulièrement au problème de l'équilibre dans ces graphes. On introduit la notion de sous-graphes équilibrants dont on donne quelques caractérisations qui permettent d'obtenir de nouveaux résultats. Nous introduisons dans la troisième partie la notion de graphes signés aléatoires et nous étudions les principales propriétés statistiques de ces graphes. La quatrième partie est consacrée à l'énumération d'une classe d'ordres partiels. Nous donnons une procédure pour calculer le nombre d'ordres partiels gradués de largeur et de rang donnes. Pour une largeur fixée la procédure utilise un temps de calcul qui est une fonction linéaire du rang. Finalement, dans la dernière partie, on étudie le problème de la satisfiabilité d'un ensemble de 3-clauses aléatoires
27
Rebreyend, Pascal. "Algorithmes génétiques hybrides en optimisation combinatoire". Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 1999. http://tel.archives-ouvertes.fr/tel-00010950.
Testo completoAbstract (sommario):
Cette thèse aborde le problème de la résolution des problèmes combinatoires à l'aide d'algorithmes génétiques. Ce type d'algorithme présente en effet nombres d'avantages. Cependant, ils sont généralement relativement lents. Cette thèse est donc centrée sur les algorithmes hybrides, c'est-à-dire des algorithmes construits à l'aide de plusieurs méthodes différentes. Dans notre cas, nous étudions les algorithmes qui réunissent algorithmes génétiques et heuristiques. Il existe deux méthodes pour générer de tels algorithmes qui sont la représentation directe et la représentation indirecte. Ces deux méthodes sont étudiés au travers de trois problèmes distincts : l'ordonnancement statique de programmes parallèles, le placement de composants électroniques et la planification de réseaux cellulaires. Pour chacun des trois problèmes, les algorithmes hybrides ont montrés leur efficacité. Pour le problème de la planification de réseaux cellulaires, une nouvelle modélisation a été faite. Cette modélisation permet d'effectuer en même temps le placement des émetteurs et l'allocation de fréquences.
28
Ould, Mohamed Lemine Mohamed. "Connaissance inter-entreprises et optimisation combinatoire". Thesis, Paris 9, 2014. http://www.theses.fr/2014PA090015/document.
Testo completoAbstract (sommario):
La connaissance inter-entreprises permet à chaque société de se renseigner sur ses clients, ses fournisseurs et de développer son activité tout en limitant le risque lié à la solvabilité ou retard de paiement de ses partenaires. Avec les tensions de trésorerie, la nécessité de la croissance et l'augmentation de la concurrence, ce domaine devient plus que jamais stratégique aussi bien pour les PME que pour les grands groupes. La quantité de données traitée dans ce domaine, les exigences de qualité et de fraîcheur, la nécessité de croiser ces données pour déduire des nouvelles informations et indicateurs, posent plusieurs problèmes pour lesquels l'optimisation en général et l'optimisation combinatoire en particulier peuvent apporter des solutions efficaces. Dans cette thèse, nous utilisons l'optimisation combinatoire, l'algorithmique du texte et la théorie des graphes pour résoudre efficacement des problèmes issus du domaine de la connaissance inter-entreprises et posés par Altares D&B. Dans un premier temps, nous nous intéressons à la qualité de la base de données des dirigeants. Ce problème combine la détection et suppression des doublons dans une base de données et la détection d'erreurs dans une chaîne de caractères. Nous proposons une méthode de résolution basée sur la normalisation des données et l'algorithmique de texte et de comparaison syntaxique entre deux chaînes de caractères. Les résultats expérimentaux montrent non seulement que cette méthode est pertinente dans la détection et la suppression des doublons mais aussi qu'elle est efficace de point du vue temps de traitement. Nous nous focalisons par la suite sur les données des liens capitalistiques et nous considérons le problème de calcul des liens indirects et l'identification des têtes des groupes. Nous présentons une méthode de résolution basée sur la théorie des graphes. Nous testons cette méthode sur plusieurs instances réelles. Nous prouvons l'efficacité de cette méthode par son temps de traitement et par l'espace de calcul qu'elle utilise. Enfin, nous remarquons que le temps de calcul de celui-ci augmente de façon logarithmique en fonction de la taille d'instance. Enfin, nous considérons le problème de l'identification des réseaux d'influence. Nous formalisons ce problème en termes de graphes et nous le ramenons à un problème de partitionnement de graphe qui est NP-difficile dans ce cas général. Nous proposons alors une formulation en programme linéaire en nombre entier pour ce problème. Nous étudions le polyèdre associé et décrivons plusieurs classes de contraintes valides. Nous donnons des conditions nécessaires pour que ces contraintes définissent des facettes et discutons des algorithmes de séparations de ces contraintes. En utilisant les résultats polyédraux obtenus, nous développons un algorithme de coupes et branchements. Enfin, nous donnons quelques résultats expérimentaux qui montrent l'efficacité de notre algorithme de coupes et branchementsThe inter-companies knowledge allows to every partner to learn about its customers, its suppliers and to develop its activity. Also this permits to limit the risk related to the creditworthiness, or the late payment of its partners. With the cash flow pressures, the need for growth and increased competition, this area becomes more strategic than ever, for both small (PME) and large groups. The amount of data processed in this domain, the requirements of quality and freshness, the need to cross these data to obtain new information and indicators, yield several optimization problems for which the recent techniques and computational tools can bring effective solutions. In this thesis, we use combinatorial optimization, text algorithms as well as graph theory to solve efficiently problems arising in the field of inter-companies knowledge. In particular, such problems was encountered in Altares D&B. First, we focus on the quality of the managers database. This problem combines the detection and removal of duplicates in a database, as well as the error detection in a string. We propose a method for solving this problem, based on data normalization, text algorithms and syntactic comparison between two strings. Our experimental results show that this method is relevant for the detection and removal of duplicates, and it is also very efficient in terms of processing time. In a second part of the thesis, we address a problem related to the data of ownership links. We compute the indirect links, and identify the group heads. We propose a method for solving this problem using graph theory and combinatorial optimization. We then perform a set of experiments on several real-world instances. The computational results show the effectiveness of our method in terms of CPU-time and resource allocation. In fact, the CPU time for computation increases logarithmically with the size of the instances. Finally, we consider the problem of identifying influence networks. We give a description of this problem in terms of graphs, and show that it can reduce to a graph partitioning problem. The latter is NP-hard. We then propose an integer linear programming formulation to model the problem. We investigate the associated polyhedron and describe several classes of valid inequalities. We give some necessaryand sufficient conditions for these inequalities to define facets of the considered polyhedron, and we discuss the related separation problems. Based on the obtained polyhedral results, we devise a Branch-and-Cut algorithm to solve the problem. Some numerical results are presented to show the efficiency of our algorithm
29
Laburthe, François. "Contraintes et algorithmes en optimisation combinatoire". Paris 7, 1998. http://www.theses.fr/1998PA077236.
Testo completoAbstract (sommario):
Ce travail evalue la programmation par contraintes (ppc) pour la resolution de problemes d'optimisation combinatoire. Sur un ensemble de grands problemes (d'allocation de ressources, d'ordonnancement, d'optimisation de parcours et d'emplois du temps), on etudie et on propose de renforcer la resolution en ppc par des regles de coupes redondantes, des algorithmes de propagation issus de la recherche operationnelle et des arbres de recherche dedies. On compare ensuite l'efficacite d'une resolution par contraintes avec des algorithmes traditionnels de recherche operationnelle, ce qui permet d'etablir une cartographie de la resolution des problemes combinatoires consideres, mettant en relation les problemes (leur type et leur taille) avec les methodes de resolution appropriees (programmation par contraintes et algorithmes de recherche operationnelle). Cette cartographie montre l'interet de developper, pour les problemes complexes de grandes taille, des algorithmes hybrides, utilisant la programmation par contraintes en cooperation avec d'autres grandes methodes de resolution, comme l'optimisation locale par exemple. Pour permettre la programmation de tels algorithmes complexes, on propose un langage de haut niveau, salsa, permettant de specifier le controle d'algorithmes de recherche complexes. On illustre son utilisation pour la resolution de problemes divers d'optimisation par des algorithmes hybrides et on presente une semantique operationnelle a partir de laquelle a ete realise l'implementation prototype.
30
VERHOEVEN, YANN. "Quelques utilisations des arbres en combinatoire". Paris 11, 2001. http://www.theses.fr/2001PA112160.
Testo completoAbstract (sommario):
Les phenomenes de seuil dans une structure aleatoire ont ete mis en evidence par erdos et renyi lors de leur etude de la taille des composantes connexes dans le modele de graphe aleatoire independant. De tels phenomenes ont pu etre mis en evidence pour d'autres problemes d'informatique theorique et sont lies aux transitions de phase existants en physique statistique. Dans cette these nous nous interessons a l'approximation de la fonction du seuil de satisfaisabilite d'une formule aleatoire sous forme 2-cnf sur un variable. Soit e fixe, on considere le rapport entre le nombre de clauses m de la formule et le nombre de variables n. Il a ete montre par chvatal et reed et par goerdt que lorsque ce rapport est inferieur a 1e alors la formule aleatoire est presque surement satisfaisable tandis que lorsque ce rapport est superieur a 1 + e, la formule est presque surement insatisfaisable. Nous donnons ici des bornes pour la valeur du rapport m/n en fonction d'une puissance de n. La borne inferieure est obtenue en ameliorant une preuve due a goerdt tandis que la borne superieure resulte d'une analyse d'algorithme a l'aide d'arbres de galton-watson. Nous etudions aussi les composantes fortement connexes dans le graphe aleatoire oriente et en particulier la taille de la composante geante. En effet, lorsque suffisamment d'aretes ont ete ajoutees, karp a montre que l'on assiste avec grande probabilite a l'apparition soudaine d'une composante fortement connexe de taille lineaire. Nous ameliorons les bornes donnees par karp concernant la taille de cette composante geante en utilisant des arbres de galton-watson dans une analyse d'algorithme.
31
LE, GALL ARMELLE. "Incrementalite et adaptativite en optimisation combinatoire". Paris 11, 1997. http://www.theses.fr/1997PA112356.
Testo completoAbstract (sommario):
Dans cette these, nous nous interessons a accroitre l'efficacite de methodes permettant de resoudre un probleme d'optimisation combinatoire pour une serie d'instances. Nous developpons des versions adaptatives aux methodes conventionnelles, i. E. Qui utilisent des informations provenant d'une precedente resolution. Dans le cas particulier ou la nouvelle instance ne se distingue de la precedente que par le nombre de variables, on parle de methodes incrementales. Une etude menee sur differents problemes polynomiaux a confirme l'interet des algorithmes incrementaux. L'utilisation de fonctions d'evaluation incrementales dans les methodes de separation-evaluation permet un gain important car les evaluations sont realisees a maintes reprises et pour des instances tres voisines. Nous proposons trois methodes qui different sur la position de l'instance de reference dans l'arbre de recherche. Elles sont validees sur le probleme np-difficile du placement de taches sur un systeme distribue. Nous avons mis en evidence les capacites adaptatives des reseaux de neurones : nous avons defini comment perturber un reseau pour que celui-ci quitte un etat stable et converge vers un nouvel etat representatif d'une solution a une nouvelle instance, voisine de la precedente. Cette methode presente un interet pratique evident car elle est independante du probleme et de la transformation appliquee a l'instance. Les differentes versions du modele de hopfield presentent un manque de selectivite qui se traduit experimentalement par des neurones qui conservent des activations loin a la fois de 0 et de 1. Comme le mecanisme d'activation competitive est particulierement apte a realiser cette separation, nous avons generalise les regles permettant son instauration pour definir une nouvelle extension du modele de hopfield. L'etude sur l'adaptativite est menee avec ce modele dont la validite a ete confirmee sur le probleme du recouvrement d'ensembles.
32
Novelli, Jean-Christophe. "Combinatoire des tableaux et des rubans". Paris 7, 1999. http://www.theses.fr/1999PA077185.
Testo completoAbstract (sommario):
Ce memoire constitue une contribution sur la combinatoire bijective et sur la combinatoire algebrique. La premiere partie est consacree a la combinatoire bijective et la seconde a la combinatoire algebrique. Nous presentons tout d'abord une synthese rapide des principaux outils de la combinatoire classique utilises dans le memoire. Nous nous interessons ensuite a la formule des equerres et nous en donnons une nouvelle demonstration bijective. Puis nous proposons la premiere etude combinatoire du monoide chinois, un monoide proche du monoide plaxique. Nous montrons ainsi que de nombreuses proprietes valables dans le cas classique se generalisent au cas chinois. Enfin, nous presentons une contribution sur le vaste sujet des permutations a motif exclu, ou nous montrons que l'ensemble des permutations evitant le motif de la permutation maximale est un ideal pour l'ordre de bruhat faible puis nous en etudions les elements maximaux. Dans le second partie, nous presentons tout d'abord les concepts de base de la combinatoire algebrique puis nous faisons une etude purement combinatoire du monoide hypoplaxique, un analogue non-commutatif du monoide plaxique. Nous en donnons tout d'abord une nouvelle definition puis nous utilisons celle-ci pour etablir facilement des proprietes generalisant dans ce cas les proprietes classiques du monoide plaxique. Nous etudions ensuite l'utilisation des fonctions symetriques non-commutatives dans le cadre des calculs dans les algebres de lie et nous obtenons en particulier un algorithme efficace pour evaluer l'idempotent de klyachko. Enfin, dans l'annexe a, nous presentons une etude d'un probleme issu de la telephonie mobile : le codage de la voix. Nous comparons ainsi deux algorithmes temps-reel qui repondent a la question. Le premier algorithme est optimal et le second est l'algorithme utilise en pratique.
33
INCITTI, ROBERTO. "Combinatoire des groupes a croissance polynomiale". Paris 7, 1995. http://www.theses.fr/1995PA077209.
Testo completoAbstract (sommario):
Dans cette these, nous etudions d'un point de vue combinatoire le theoreme de m. Gromov sur les groupes a croissance polynomiale. Nous donnons un apercu de la demonstration geometrique de gromov, et nous presentons une construction qui permet de visualiser certains espaces metriques qu'il definit. Nous abordons ensuite le probleme de la recherche d'une demonstration combinatoire. Nous montrons qu'il y a une difference qualitative entre le cas de la croissance lineaire et celui d'une croissance de degre strictement superieur a un. Nous montrons qu'elle nait d'un probleme de periodicite de mots infinis. Ce point de vue nous permet de redemontrer le resultat de gromov dans le cas lineaire avec un argument combinatoire. Pour aborder le cas de croissance plus grand, nous introduisons une propriete, que nous appellons rigidite. Elle permet de ramener a des problemes de combinatoire des mots une partie importante de l'etude algebrique des groupes a croissance superieure a un ; nous l'utilisons pour montrer d'une facon combinatoire qu'un groupe dont la croissance est inferieure a une certaine fonction quadratique ne peut pas etre periodique. La partie finale de la these est consacree a l'extension des resultats au cas des semigroupes
34
Koubi, Vassilada. "Reseaux de neurones et optimisation combinatoire". Paris 5, 1994. http://www.theses.fr/1994PA05S014.
Testo completoAbstract (sommario):
Les problemes d'optimisation combinatoire ont des donnees assez structurees qui conviennent au traitement d'une architecture neuronale. Ces problemes qui appartiennent en general a la classe np-complet, necessitent une grande puissance de calcul. L'objectif de ce travail est d'appliquer le modele de reseau de neurones aleatoires aux problemes d'optimisation combinatoire. L'application du reseau neuronal aleatoire de gelenbe, a un probleme d'optimisation combinatoire, est caracterisee par l'evolution des entrees externes, qui correspondent au gradient de la fonction objective, en contradiction avec les autres methodes neuronales ou les entrees sont en general constantes. Deux alternatives de resolution sont proposees : l'approche gradient, application de l'algorithme du gradient sur la fonction et l'approche dynamique, introduction du gradient de la fonction aux equations dynamiques qui sont liees au probleme considere. Nous avons resolu un probleme classique d'optimisation combinatoire, le probleme du voyageur de commerce, et un probleme de satisfaction des contraintes, le probleme de reines non attaquantes. De plus nous avons propose la solution pour d'autres problemes. Le reseau neuronal aleatoire applique au probleme du voyageur de commerce a ete evalue et compare avec les autres methodes connexionnistes. Les resultats obtenus sont assez satisfaisants, de qualite similaire (ou meme meilleure) a ceux obtenus par d'autres methodes. Le probleme de reines a ete resolu par deux modelisations. La premiere consiste a resoudre directement ce probleme, alors que dans la seconde on considere le probleme des reines comme un probleme du stable maximal. Quelque soit la methode retenue, toutes les solutions possibles, ou presque, pour ce probleme ont ete obtenues.
35
BENCHEKROUN, SAAD. "Combinatoire bijective des systemes de parenthesages". Paris 6, 1994. http://www.theses.fr/1994PA066486.
Testo completoAbstract (sommario):
On presente les principales proprietes enumeratives des systemes de parenthesages relatives a differents parametres descriptifs: la longueur, la hauteur, le nombre d'arches et le nombre de piles, ou de montees paires, ou de doubles montees ou encore de sequences non terminales longues. On donne des bijections nouvelles explicatives de ces proprietes. On definit une nouvelle bijection entre les arbres ordonnes et les systemes de parenthesages permettant de retrouver facilement plusieurs proprietes de ces derniers
36
Jambu, Michel. "Arrangements d'hyperplans : topologie, geometrie et combinatoire". Nantes, 1989. http://www.theses.fr/1989NANT2040.
Testo completoAbstract (sommario):
La plupart des proprietes topologiques du complement d'une famille finie d'hyperplans de c#n sont codees dans le treillis des intersections de ces hyperplans: la cohomologie de ce complement est decrite a l'aide des circuits brises: les treillis associes aux arrangements de type fibre sont hyperresolubles et l'algebre d'holonomie de lie du complement admet une factorisation comme espace vectoriel, definie par une chaine maximale modulaire ce qui permet de donner une demonstration tres simple de la propriete lcs
37
Libralesso, Luc. "Recherches arborescentes anytime pour l'optimisation combinatoire". Thesis, Université Grenoble Alpes, 2020. http://www.theses.fr/2020GRALM026.
Testo completoAbstract (sommario):
Les recherches arborescentes sont utilisées dans un grand nombre d'applications (MIP, CP, SAT, metaheuristiques avec Ant Colony Optimization et GRASP) et également dans des communautés IA/planning. Toutes ces techniques présentent des bases communes et de nombreuses techniques peuvent être transférées d'une communauté à une autre. Les résultats préliminaires indiquent que ces techniques sont très performantes comparé aux metaheuristiques généralement utilisés en recherche opérationnelle.Dans ces travaux, nous dressons un état de l'art et une classification de différentes techniques de recherche arborescente que l'on retrouve dans les metaheuristiques, dans les méthodes exactes et en IA/planning.Nous développons un framework générique qui permet l'élaboration rapide d'algorithmes de recherche arborescente.Enfin, nous utilisons ces techniques pour proposer des méthodes compétitives avec les metaheuristiques généralement utilisées en recherche opérationnelle. Nous présentons de nouvelles méthodes de recherche arborescente pour plusieurs problèmes d'optimisation combinatoire ainsi que de nouvelles meilleures solutions connuesTree search algorithms are used in a large variety of applications (MIP, CP, SAT, metaheuristics with Ant Colony Optimization and GRASP) and also in AI/planning communities. All of these techniques present similar components and many of those components can be transferred from one community to another. Preliminary results indicate that anytime tree search techniques are competitive compared to commonly used metaheuristics in operations research.In this work, we detail a state of the art and a classification of the different tree search techniques that one can find in metaheuristics, exact methods and AI/planning. Then, we present a generic framework that allows the rapid prototyping of tree search algorithms. Finally, we use this framework to develop anytime tree search algorithms that are competitive with the commonly-used metaheuristics in operations research. We report new tree search applications for some combinatorial optimization problems and new best-known solutions
38
HOUDAYER, JEROME. "Verres de spins et optimisation combinatoire". Paris 11, 1999. http://www.theses.fr/1999PA112205.
Testo completoAbstract (sommario):
Les systemes desordonnes et frustres sont un des sujets actifs de la physique statistique actuelle dont l'etude analytique est particulierement difficile. L'approximation de champ moyen est une approche fructueuse, mais sa pertinence pour les systemes en dimension finie est encore debattue. Dans cette these, j'etudie la validite de cette approximation et la nature du paysage d'energie pour deux systemes differents : le couplage minimal et les verres de spins. Les techniques utilisees sont essentiellement numeriques, mais contrairement a ce qu'on voit habituellement il ne s'agit pas ici de simulations de type monte carlo. La methode que j'ai retenue permet d'etudier un systeme a temperature nulle et consiste a calculer l'etat fondamental et les excitations de faible energie par des methodes d'optimisation combinatoire. L'optimisation combinatoire est la branche de l'informatique qui s'interesse aux problemes d'optimisation d'une fonction sur un ensemble fini de configurations. Trouver le fondamental d'un systeme desordonne et frustre est un probleme de ce type ce qui cree des liens interessants entre les deux domaines. Les apports de cette these peuvent etre decomposes en trois parties : premierement une etude approfondie du couplage minimal (un probleme de dimerisation), dont la conclusion principale est l'existence de deux echelles, l'echelle macroscopique bien decrite par le champ moyen et l'echelle microscopique decrite par une theorie de type gouttelettes. Deuxiemement, une etude des verres de spins en dimension finie qui semble indiquer l'absence de la ligne de transition at en champ magnetique predite par le champ moyen. Et finalement le developpement d'un nouveau type d'algorithme d'optimisation combinatoire base sur l'idee de renormalisation qui s'avere etre a la fois general et tres puissant.
39
Hillairet, Caroline. "Catalyse combinatoire pour la polymérisation d'oléfines". Rennes 1, 2003. http://www.theses.fr/2003REN10063.
Testo completoAbstract (sommario):
L'intérêt porté aux catalyseurs de polymérisation d'oléfines ± non-métallocènes α a connu un essor remarquable depuis le milieu des années 1990. L'étude bibliographique de ce manuscrit détaille quelques exemples de catalyseurs pour la polymérisation de l'éthylène. Une première partie détaille l'activité de système imino-pyridines ou bis-thiazolines du Pd(II). La seconde partie de ce travail reporte comment la catalyse combinatoire en parallèle peut être utilisée pour découvrir de nouveaux catalyseurs de polymérisation d'oléfines, en homogène ou sur support solide et a permis de découvrir une nouvelle famille de complexes bis-(pyrazolyl)amine du Ni(II) pour l'oligomérisation de l'éthylène (C4>84%) et un tout nouveau complexe à base de nickel, très actif en oligomérisation d'oléfines (50 t/mol/h).
40
Jolivet, Timothée. "Combinatoire de substitutions de type Pisot". Paris 7, 2013. http://www.theses.fr/2013PA077146.
Testo completoAbstract (sommario):
Les substitutions sont des applications qui remplacent chaque lettre d'un alphabet par un mot sur le même alphabet. Elle agissent naturellement sur des suites infinies de symboles, et produisent des systèmes très structurés ayant beaucoup de propretés. Cette thèse porte sur l'étude d'une classe particulière vérifiant des restriction algébriques, les substitutions de type Pisot, et leurs objets associés, de nature dynamique, fractale ou combinatoire. Nous commençons par l'étude combinatoire de certaines propriétés qualitatives des motifs bi-dimensionnels engendrés par une version "duale" des substitutions de type Pisot. On applique ces résultats à l'étude des familles infinies de substitutions définies comme l'ensemble des produits finis sur un ensemble fini de susbtitutions. On obtient des propriétés dynamiques des systèmes symboliques associés, des caractérisations de certaines propriétés topologiques des fractals de Rauzy associés, des propriétés des valeurs propres Pisot associées, et des applications en géométrie discrète. Une attention particulière est portée sur les substitutions associées aux algorithmes de fraction continues multidimensionnels d'Arnoux-Rauzy, Brun et Jacobi-Perron. Ensuite nous donnons des constructions explicites pour donner une description complète des groupes fondamentaux de fractals de Rauzy planaires, dans le cas où le groupe est dénombrable. Dans les deux derniers chapitres, on s'affranchit de la condition algébrique Pisot, pour étudidier des objets plus généraux provenant des outils combinatoires utilisés dans les précédents chapitres, en insistant sur des questions d'(in)décidabilité calculatoireSubstitutions are mappings which replace each symbol of a given alphabet by a word over the same alphabet. They naturally act over infinite sequences of symbols, and produce highly ordered Systems with many properties. This thesis concerns a particular class with algebraic restrictions, Pisot substitutions, and their related objects of dynamical, fractal o combinatorial nature. We begin with the combinatorial study of some qualitative properties of the two-dimensional patterns generated by iterating a two-dimensional "dual" version of Pisot substitutions. We apply these results to study the infinite families of substitutions obtained by taking arbitrary products over a finite set of Pisot substitutions. Applications include dynamica properties of the associated symbolic Systems, some language theoretical characterization of some topological properties of their associated Rauzy fractals, some number-theoretical properties of their associated Pisot numbers, and some results in discrete geometry. Particular focus is set on the substitutions associated with the Arnoux-Rauzy, Brun and Jacobi-Perron multidimensional continued fraction algorithms Next we give explicit construction to give a complete description of the possible fondamental groups of planar Rauzy fractals in the case where the group is countable. In the last two chapters, we "step back" from the Pisot algebraic assumption to study some more general objects arising from the combinatorial tools used in the previous chapters, focusing on some computational (un)decidability questions
41
Rebreyend, Pascal. "Algorithmes genetiques hybrides en optimisation combinatoire". Lyon, École normale supérieure (sciences), 1999. http://www.theses.fr/1999ENSL0108.
Testo completoAbstract (sommario):
Cette these porte sur les problemes d'optimisation combinatoire et sur leur resolution grace aux algorithmes genetiques, notamment ceux hybrides. Cette these traite les trois problemes suivants : l'ordonnancement de programmes paralleles, le placement de composants sur circuits imprimes et la construction de reseaux de telephonie cellulaire. Ces problemes sont resolus par l'utilisation d'algorithmes genetiques hybrides. Les algorithmes genetiques sont une methode interessante et facilement parallelisable pour trouver une solution sous-optimale d'un probleme combinatoire. Ils sont bases sur la theorie de l'evolution des especes. Leur methode consiste donc a faire evoluer une population d'individus ou de solutions. Cette these examine et compare les deux principales facons de coupler un algorithme genetique avec une heuristique. Ces deux methodes sont nommees representation directe et representation indirecte. Dans le cas de la representation directe, l'heuristique est introduite au sein de l'algorithme genetique en modifiant les operateurs de croisement ou de mutation. La representation indirecte consiste a utiliser l'algorithme genetique pour determiner un ordre total sur les elements du probleme. On utilise alors une heuristique ou algorithme de liste qui construit la solution pas a pas en tenant compte de cet ordre. A part le probleme de l'ordonnancement, cette these presente et explique la modelisation de chaque probleme, modelisation qui est necessaire afin de pouvoir exploiter au mieux les caracteristiques des algorithmes genetiques. Les trois problemes etudies ont permis d'experimenter les deux types d'algorithmes genetiques hybrides. Les algorithmes hybrides testes ont montre leur efficacite par rapport aux heuristiques classiques. Les resultats obtenus confirment l'interet d'adapter l'algorithme genetique au probleme traite.
42
Hocini, Fadila. "Combinatoire énumérative de plusieurs structures finies". Paris 6, 1986. http://www.theses.fr/1986PA066210.
Testo completoAbstract (sommario):
On construit deux bijections entre d'une part l'ensemble des "forêts standards ordinaires" et l'ensemble des "ponts ordinaires" et d'autre part entre l'ensemble des "forêts standards pondérés" et l'ensemble des "ponts faiblement surdiagonaux dont les longueurs des sauts et des paliers sont paires". On construit aussi une bijection entre l'ensemble des "forêts standards pondérés de poids n, ayant deux arbres" et l'ensemble des "forêts standards pondérés de poids n, ayant trois arbres.
43
Pirillo, Giuseppe. "Contribution à la combinatoire des mots". Paris 7, 2007. http://www.theses.fr/2007PA077159.
Testo completoAbstract (sommario):
Nous étudions: a)un cas spécial de régularités inévitables, la répétitivité introduite et étudiée par Justin et liée aux résultats de Thue, au Théorème de Ramsey, et au Théorème de van der Waerden; b)la notion de semi-groupe permutable (liée au théorème de Shirshov) et certaines conditions de finitude des semi-groupes finiment engendrés; c)les mots Sturmiens (dont l'étude, très ancienne, a récemment progressé surtout par les nombreuses et intéressantes contributions de Berstel) et les mots épisturmiens. Nous mentionnons également quelques-unes de nos contributions récentes à la biologie théorique et certaines contributions à la didactique de la mathématique et de l'informatique. Ce travail n'est pas un survol (tour d'horizon) de l'état de nos recherches, et ne contient pas une analyse détaillée des résultats déjà obtenus, mais c'est un moment de réflexion pour mieux organiser nos recherches futuresWe study: a)a special case of unavoidable reguiarities, the repetitivity introduced and studied by Justin. This field is in relation with the results of Thue, the Theorem of Ramsey and the Theorem of van der Waerden; b) the notion of permutable semigroupe (in relation with the Theorem of Shirshov) and some finiteness conditions forfinitely generated semigroups. C) the Sturmians words (of which the study, very old, has recently progressed under the impulsion of many interesting contributions of Berstel) and the episturmian words. We also mention some our recent contributions to the theoretical biology and some contributions to mathematical and computer science education. This work is not a survey of our research activity and does not contain a detailed analysis of our results but is a moment of reflexion in order to better organize our future work
44
Delecroix, Vincent. "Combinatoire et dynamique du flot de Teichmüller". Phd thesis, Université de la Méditerranée - Aix-Marseille II, 2011. http://tel.archives-ouvertes.fr/tel-00653165.
Testo completoAbstract (sommario):
Ce travail de thèse porte sur la dynamique du flot linéaire des surfaces de translation et de sa renormalisation par le flot de Teichmüller introduite par H. Masur et W. Veech en 1982. Une version combinatoire de cette renormalisation, l'induction de Rauzy sur les échanges d'intervalles, fût introduite auparavant par G. Rauzy en 1979. D'une part, nous faisons une étude combinatoire des classes de Rauzy qui forment une partition de l'ensemble des permutations irréductibles et interviennent dans l'algorithme d'induction de Rauzy. Nous donnons une formule pour la cardinalité de chaque classe. D'autre part, nous étudions un modèle de billard infini $\ZZ^2$-périodique dans le plan appelé le \og vent dans les arbres \fg introduit dans une version stochastique par P.~et T. Ehrenfest en 1912 et par J. Hardy et J. Weber en 1980 dans la version périodique. Nous construisons une famille de directions pour lesquelles le flot du billard est divergent donnant ainsi des exemples de $\ZZ^2$-cocycles divergents au-dessus d'échanges d'intervalles. De plus, nous démontrons que le taux polynomial de diffusion générique est $2/3$ autrement dit que la distance maximale atteinte par une particule au temps $t$ est de l'ordre de $t^{2/3}$.
45
Eric, Fusy. "Combinatoire des cartes planaires et applications algorithmiques". Phd thesis, Ecole Polytechnique X, 2007. http://pastel.archives-ouvertes.fr/pastel-00002931.
Testo completoAbstract (sommario):
Cette these traite de l'algorithmique des cartes planaires (graphes dessines dans le plan sans intersection d'aretes) et propose des procedures efficaces pour le codage, la generation aleatoire, et le dessin de plusieurs familles importantes: 3-connexes, triangulations, quadrangulations... En particulier, on decrit le premier algorithme optimal de codage des incidences faces-aretes-sommets des maillages polygonaux de topologie spherique, qui atteint la borne inferieure de 2bits par arete. En partant d'un generateur de cartes 3-connexes, on developpe un nouveau generateur aleatoire uniforme de graphes planaires dont la complexite est la meilleure connue actuellement: quadratique (en esperance) en taille exacte et lineaire (en esperance) en taille approchee. Enfin, on donne plusieurs algorithmes de dessin en lignes droites (aretes representees par des segments) de cartes planaires sur la grille. Les procedures de dessin sont a la fois tres simples a decrire et donnent les meilleures performance (en probabilite) pour le dessin de deux familles de cartes: les triangulations du carre sans 3-cycle rempli —dite irreductibles— et les quadrangulations. Pour developper les algorithmes presentes dans la these, on exploite plusieurs structures combinatoires sur les cartes (orientations specifiques, partitions en arbres couvrants...) ainsi que de nouvelles constructions bijectives.
46
Chapuy, Guillaume. "Combinatoire bijective des cartes de genre supérieur". Phd thesis, Ecole Polytechnique X, 2009. http://pastel.archives-ouvertes.fr/pastel-00005289.
Testo completoAbstract (sommario):
Cette thèse est une contribution à l'étude énumérative et statistique d'objets combinatoires appelés cartes. Une carte est une surface discrète formée par le recollement d'un nombre fini de polygones, ou de manière équivalente un graphe qui a été plongé sans croisements d'arêtes dans une surface orientable. Si de nombreux travaux concernent la combinatoire des cartes planaires, nous nous intéressons ici aux cartes de genre g>0, c'est-à-dire dont la surface sous-jacente possède g anses indépendantes. Nous donnons des bijections nouvelles reliant les cartes de genre fixé à des objets de nature arborescente. Nous en déduisons des résultats énumératifs (formules et identités combinatoires, formules d'énumération asymptotique), des résultats probabilistes concernant la limite continue de ces objets (caractérisation du profil métrique limite d'une grande carte de genre g), et de génération aléatoire (algorithmes efficaces pour engendrer ces objets).
47
Delanoy, Ewan. "Définition combinatoire des polynômes de Kazhdan-Lusztig". Phd thesis, Université Claude Bernard - Lyon I, 2006. http://tel.archives-ouvertes.fr/tel-00137528.
Testo completoAbstract (sommario):
La théorie des groupes de Coxeter, qui a pour origine l'étude des groupesd'isométries, permet de relier entre eux divers domaines d'algèbre et de
géométrie, allant de la théorie des representations (des groupes de Coxeter
et de Lie, des algèbres de Lie et de Hecke) et de la géométrie algébrique
(variétés de Schubert) à la combinatoire (ordre de Bruhat). Les polynômes
de Kazhdan-Lusztig apparaissent sous des formes assez différentes dans plusieurs
de ces domaines : ces polynômes
peuvent être définis comme coordonnées d'une base
remarquable de l'algèbre de Hecke (ce qui donne une représentation non triviale
de cette algèbre), leur valeur au point 1 intervient dans la décomposition de certains
modules de Verma, et leur coefficients peuvent être interprétés comme des dimensions
de certains espaces d'homologie locale. La définition originale de ces polynômes
se traduit par une formule de récurrence compliquée qui conduit naturellement à
s'interroger sur une éventuelle définition purement combinatoire. Ce rapport essaye
de montrer quelques développements récents dans les tentatives de réponse à cette
question. Notre résultat principal est le suivant : un isomorphisme entre
deux intervalles initiaux préserve les polynômes de Kazhdan-Lusztig. Nous explicitons
également des arguments (théoriques et calculatoires)
tendant à confirmer la conjecture que cela reste vrai pour un isomorphisme entre des intervalles
complètement compressibles dans des groupes de Coxeter finis.\newline
Mots-clés : groupe de Coxeter, polynôme de Kazhdan-Lusztig,
sous-groupe de réflections, intervalle de Bruhat, couplage distingué,
intervalle complètement compressible
48
Darlay, Julien. "Analyse combinatoire de données : structures et optimisation". Phd thesis, Université de Grenoble, 2011. http://tel.archives-ouvertes.fr/tel-00683651.
Testo completoAbstract (sommario):
Cette thèse porte sur des problèmes d'exploration de données avec le point de vue de la recherche opérationnelle. L'exploration de données consiste en l'apprentissage de nouvelles connaissances à partir d'observations contenues dans une base de données. La nature des problèmes rencontrés dans ce domaine est proche de celle des problèmes de la recherche opérationnelle: grandes instances, objectifs complexes et difficulté algorithmique. L'exploration de données peut aussi se modéliser comme un problème d'optimisation avec un objectif partiellement connu. Cette thèse se divise en deux parties. La première est une introduction à l'exploration de données. Elle présente l'Analyse Combinatoire de Données (ACD), une méthode d'exploration de données issue de l'optimisation discrète. Cette méthode est appliquée à des données médicales originales et une extension aux problèmes d'analyse de temps de survie est proposée. L'analyse de temps de survie consiste à modéliser le temps avant un événement (typiquement un décès ou une rechute). Les heuristiques proposées utilisent des techniques classiques de recherche opérationnelle telles que la programmation linéaire en nombres entiers, la décomposition de problème, des algorithmes gloutons. La seconde partie est plus théorique et s'intéresse à deux problèmes combinatoires rencontrés dans le domaine de l'exploration de données. Le premier est un problème de partitionnement de graphes en sous-graphes denses pour l'apprentissage non supervisé. Nous montrons la complexité algorithmique de ce problème et nous proposons un algorithme polynomial basé sur la programmation dynamique lorsque le graphe est un arbre. Cet algorithme repose sur des résultats de la théorie des couplages. Le second problème est une généralisation des problèmes de couverture par les tests pour la sélection d'attributs. Les lignes d'une matrice sont coloriées en deux couleurs. L'objectif est de trouver un sous-ensemble minimum de colonnes tel que toute paire de lignes avec des couleurs différentes restent distinctes lorsque la matrice est restreinte au sous-ensemble de colonnes. Nous montrons des résultats de complexité ainsi que des bornes serrées sur la taille des solutions optimales pour différentes structures de matrices.
49
Le, Bodic Pierre. "Variantes non standards de problèmes d'optimisation combinatoire". Thesis, Paris 11, 2012. http://www.theses.fr/2012PA112190.
Testo completoAbstract (sommario):
Cette thèse est composée de deux parties, chacune portant sur un sous-domaine de l'optimisation combinatoire a priori distant de l'autre. Le premier thème de recherche abordé est la programmation biniveau stochastique. Se cachent derrière ce terme deux sujets de recherche relativement peu étudiés conjointement, à savoir d'un côté la programmation stochastique, et de l'autre la programmation biniveau. La programmation mathématique (PM) regroupe un ensemble de méthodes de modélisation et de résolution, pouvant être utilisées pour traiter des problèmes pratiques que se posent des décideurs. La programmation stochastique et la programmation biniveau sont deux sous-domaines de la PM, permettant chacun de modéliser un aspect particulier de ces problèmes pratiques. Nous élaborons un modèle mathématique issu d'un problème appliqué, où les aspects biniveau et stochastique sont tous deux sollicités, puis procédons à une série de transformations du modèle. Une méthode de résolution est proposée pour le PM résultant. Nous démontrons alors théoriquement et vérifions expérimentalement la convergence de cette méthode. Cet algorithme peut être utilisé pour résoudre d'autres programmes biniveaux que celui qui est proposé.Le second thème de recherche de cette thèse s'intitule "problèmes de coupe et de couverture partielles dans les graphes". Les problèmes de coupe et de couverture sont parmi les problèmes de graphe les plus étudiés du point de vue complexité et algorithmique. Nous considérons certains de ces problèmes dans une variante partielle, c'est-à-dire que la propriété de coupe ou de couverture dont il est question doit être vérifiée partiellement, selon un paramètre donné, et non plus complètement comme c'est le cas pour les problèmes originels. Précisément, les problèmes étudiés sont le problème de multicoupe partielle, de coupe multiterminale partielle, et de l'ensemble dominant partiel. Les versions sommets des ces problèmes sont également considérés. Notons que les problèmes en variante partielle généralisent les problèmes non partiels. Nous donnons des algorithmes exacts lorsque cela est possible, prouvons la NP-difficulté de certaines variantes, et fournissons des algorithmes approchés dans des cas assez générauxThis thesis is composed of two parts, each part belonging to a sub-domain of combinatorial optimization a priori distant from the other. The first research subject is stochastic bilevel programming. This term regroups two research subject rarely studied together, namely stochastic programming on the one hand, and bilevel programming on the other hand. Mathematical Programming (MP) is a set of modelisation and resolution methods, that can be used to tackle practical problems and help take decisions. Stochastic programming and bilevel programming are two sub-domains of MP, each one of them being able to model a specific aspect of these practical problems. Starting from a practical problem, we design a mathematical model where the bilevel and stochastic aspects are used together, then apply a series of transformations to this model. A resolution method is proposed for the resulting MP. We then theoretically prove and numerically verify that this method converges. This algorithm can be used to solve other bilevel programs than the ones we study.The second research subject in this thesis is called "partial cut and cover problems in graphs". Cut and cover problems are among the most studied from the complexity and algorithmical point of view. We consider some of these problems in a partial variant, which means that the cut or cover property that is looked into must be verified partially, according to a given parameter, and not completely, as it was the case with the original problems. More precisely, the problems that we study are the partial multicut, the partial multiterminal cut, and the partial dominating set. Versions of these problems were vertices are
50
Nunge, Arthur. "Combinatoire énumérative et algébrique autour du PASEP". Thesis, Paris Est, 2018. http://www.theses.fr/2018PESC1116/document.
Testo completoAbstract (sommario):
Cette thèse se situe à l'interface de la combinatoire énumérative et algébrique et porte sur l'étude des probabilités du processus d'exclusion partiellement asymétrique (PASEP).Dans un premier temps, nous démontrons bijectivement une conjecture de Novelli-Thibon-Williams concernant l'interprétation combinatoire de coefficients de matrices de transition dans l'algèbre des fonctions symétriques non-commutatives. Plus précisément, ces matrices expriment les coefficients de changement de base des bases complètes et rubans d'une part vers les bases monomiales et fondamentales introduites par Tevlin d'autre part. Les coefficients de ces matrices donnent un raffinement des probabilités du PASEP et sont décrits en utilisant de nouvelles statistiques sur les permutations. La conjecture stipule que ce raffinement peut se formuler via des statistiques déjà connues dans le monde du PASEP. Nous nous intéressons ensuite à une généralisation du PASEP avec deux types de particules dans le modèle : le 2-PASEP. Nous donnons ainsi plusieurs interprétations combinatoires des probabilités de ce modèle. Pour ce faire, nous introduisons une nouvelle famille de chemins généralisant les histoires de Laguerre : les histoires de Laguerre marquées. Nous généralisons ensuite la bijection de Françon-Viennot entre les histoires de Laguerre et les permutations pour définir les permutations partiellement signées qui nous donneront une seconde interprétation combinatoire de ces probabilités. Dans une troisième partie, nous généralisons les travaux de Tevlin afin de définir des bases monomiales et fondamentales dans l'algèbre des compositions segmentées. Afin de décrire les matrices de changement de base entre ces bases et d'autres déjà connues dans cette algèbre, nous définissons une algèbre indexée par les permutations partiellement signées en utilisant les statistiques définies précédemment pour décrire la combinatoire du 2-PASEP. Nous définissons également des q-analogues de ces bases afin de faire le lien avec les probabilités du 2-PASEP en fonction du paramètre q de ce modèle. Enfin, en utilisant le fait que les permutations partiellement signées sont en bijection avec les permutations segmentées, nous nous inspirons des statistiques définies précédemment pour introduire des descentes sur ces objets et ainsi définir une généralisation des polynômes eulériens sur les permutations segmentées. Pour étudier ces polynômes, nous utilisons les outils algébriques développés dans la partie précédenteThis thesis comes within the scope of enumerative and algebraic combinatorics and studies the probabilities of the partially asymmetric exclusion process (PASEP).First, we bijectively prove a conjecture of Novelli-Thibon-Williams concerning the combinatorial interpretation of the entries of the transition matrices between some bases of the noncommutative symmetric functions algebra. More precisely, these matrices correspond to the transition matrices of, on the one hand the complete and ribbon bases and on the other hand the monomial and fundamental bases, both introduced by Tevlin. The coefficients of these matrices provide a refinement of the probabilities of the PASEP and are described using new statistics on permutations. This conjecture states that this refinement can also be described using classical statistics of the PASEP. In the second part, we study a generalization of the PASEP using two kinds of particles: the 2-PASEP. Hence, we give several combinatorial interpretations of the probabilities of this model. In order to do so, we define a new family of paths generalizing the Laguerre histories: the marked Laguerre histories. We also generalize the Françon-Viennot bijection between Laguerre histories and permutations to define partially signed permutations giving another combinatorial interpretation of these probabilities. In a third part, we generalize Tevlin's work in order to define a monomial basis and a fundamental basis on the algebra over segmented compositions. In order to describe the transition matrices between these bases and other bases already known in this algebra, we define an algebra indexed by partially signed permutations using the statistics previously defined to describe the combinatorics of the 2-PASEP. We also define some q-analogues of these bases related to the probabilities of the 2-PASEP according to the q parameter of this model. Finally, using the fact that partially signed permutations and segmented permutations are in bijection, we use the statistics defined previously to define descents on these objects and get a generalization of the Eulerian polynomials on segmented permutations. To study these polynomials, we use the algebraic tools introduced in the previous part