Дисертації з теми "Combinatoire géométrique"
Щоб переглянути інші типи публікацій з цієї теми, перейдіть за посиланням: Combinatoire géométrique.
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся з топ-50 дисертацій для дослідження на тему "Combinatoire géométrique".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Переглядайте дисертації для різних дисциплін та оформлюйте правильно вашу бібліографію.
1
Sage, Marc. "Combinatoire algébrique et géométrique des nombres de Hurwitz." Phd thesis, Université Paris-Est, 2012. http://tel.archives-ouvertes.fr/tel-00804228.
Анотація:
Ce mémoire se veut une synthèse, destinée à la communauté combinatoricienne, de quelques outils développés pour aborder le problème d'Hurwitz ainsi qu'une présentation des résultats récoltés. Le problème d'Hurwitz consiste à évaluer, dans un groupe symétrique, le nombre (dit d'Hurwitz) de factorisations transitives de la permutation identité dont on a imposé le type cyclique des facteurs. Nous décrivons tout d'abord les origines topologiques de ce problème à travers le dénombrement des revêtements ramifiés de la sphère. Nous présentons également un cadre algébrique naturel, le monoïde des permutations scindées, qui permet d'exprimer les nombres d'Hurwitz comme coefficients de structure de l'algèbre de ce monoïde, plus précisément de la sous-algèbre engendrée par les classes de conjugaison, dont une base naturelle est indexée par les multipartitions (ou partitions scindées). La théorie des représentations de cette algèbre fournit un algorithme pour calculer les nombres d'Hurwitz à une partition dont la complexité (minimale, uniforme et exponentielle) est bien meilleure que celle d'une approche naïve. Ce cadre algébrique donne par ailleurs une formule décrivant les séries d'Hurwitz à plusieurs partitions comme polynômes en les séries d'Hurwitz à une seule partition. Nous présentons secondement le cadre géométrique dans lequel s'expriment d'une part la formule ELSV, laquelle décrit les nombres d'Hurwitz à une partition comme fonctions de certaines intégrales, d'autre part un théorème de M. Kazarian exprimant les séries de Hurwitz à une partition comme polynômes en certaines séries formelles dont l'étude asymptotique est achevée. Une fois décrit le fonctionnement de ce cadre intégral, nous récoltons l'asymptotique de tous les nombres d'Hurwitz
2
Siegel, Anne. "Représentations géométrique, combinatoire et arithmétique des systèmes subsitutifs de type Pisot." Aix-Marseille 2, 2000. http://www.theses.fr/2000AIX22075.
3
Skapin, Xavier. "Utilisation du produit cartésien en modélisation géométrique 4D pour l'animation." Poitiers, 2001. http://www.theses.fr/2001POIT2301.
Анотація:
Nous travaillons sur la modélisation géométrique 4D (spatio-temporelle) pour l'animation : son intérêt est d'homogénéiser des méthodes de modélisation 3D à la dimension 4, mais ses principales difficultés sont d'interpréter un objet 4D en termes d'animation et de contrôler sa construction. Notre utilisons des objets spatio-temporels de dimension inférieure à 4 comme opérandes de l'opération de produit cartésien, pour créer des objets de dimension supérieure dont l'interprétation se déduit de celle des opérandes. Une étude de cas sur des opérandes de base a mené à une méthode d'interprétation et de contrôle des objets 4D créés par produit cartésien. Un modeleur géométrique à base topologique 4D nous a permis de créer des animations complexes. Nous avons adapté la définition du produit cartésien aux ensembles semi-simpliciaux, aux cartes généralisées, aux cartes orientées et aux chaînes de cartes fermées (à chacune de ces définitions correspond un algorithme optimal en temps de calcul)We work in the scope of 4D (space-time) modelling for animation. Extending 3D modelling methods to dimension 4 is the main advantage of 4D modelling, but interpreting a 4D object as an animation and controlling the construction of this object are the main drawbacks of 4D modelling. Our method uses space-time objects of dimension lesser than 4 as operands of the cartesian product operation to create an object of greater dimension, whose interpretation is deduced from operands'. We made a case study about cartesian product of basic operands defined as point trajectories. This study led to a method for interpreting and controlling 4D objects resulting from cartesian product. We have created a topologically-based 4D geometrical modeler, allowing us to design elaborate animations. We have adapted cartesian product operation to semi-simplicial sets, generalized maps, n-maps and closed chains of maps. Each of these definitions corresponds to an algorithm with an optimal complexity in time
4
Ledent, Jérémy. "Sémantique géométrique pour la calculabilité asynchrone." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLX099/document.
Анотація:
Le domaine des protocoles tolérants aux pannes étudie quelles tâches concurrentes sont résolubles dans différents modèles de calcul avec pannes. Des outils mathématiques basés sur la topologie combinatoire ont été développés depuis les années 1990 pour aborder ces questions. Dans ce cadre, la tâche que l’on veut résoudre, et le protocole auquel on fait appel, sont modélisés par des complexes simpliciaux chromatiques. On définit qu’un protocole résout une tâche lorsqu’il existe une certaine application simpliciale entre ces complexes.Dans cette thèse, on étudie ces méthodes géométriques du point de vue de la sémantique. Le premier objectif est de fonder cette définition abstraite de résolution d’une tâche sur une autre plus concrète, basée sur des entrelacements de traces d’exécution. On examine diverses notions de spécifications pour les objets concurrents, afin de définir un cadre général pour la résolution de tâches par des objets partagés. On montre ensuite comment extraire de ce cadre la définition topologique de résolubilité de tâches.Dans la deuxième partie de la thèse, on prouve que les complexes simpliciaux chromatiques peuvent être utilisés pour évaluer des formules de logique épistémique. Cela permet d’interpréter les preuves topologiques d’impossibilité en fonction de la quantité de connaissances à acquérir pour résoudre une tâche.Enfin, on présente quelques liens préliminaires avec la sémantique dirigée pour les programmes concurrents. On montre comment la subdivision chromatique d’un simplexe peut être retrouvée en considérant des notions combinatoires de chemins dirigésThe field of fault-tolerant protocols studies which concurrent tasks are solvable in various computational models where processes may crash. To answer these questions, powerful mathematical tools based on combinatorial topology have been developed since the 1990’s. In this approach, the task that we want to solve, and the protocol that we use to solve it, are both modeled using chromatic simplicial complexes. By definition, a protocol solves a task when there exists a particular simplicial map between those complexes.In this thesis we study these geometric methods from the point of view of semantics. Our first goal is to ground this abstract definition of task solvability on a more concrete one, based on interleavings of execution traces. We investigate various notions of specification for concurrent objects, in order to define a general setting for solving concurrent tasks using shared objects. We then show how the topological definition of task solvability can be derived from it.In the second part of the thesis, we show that chromatic simplicial complexes can actually be used to interpret epistemic logic formulas. This allows us to understand the topological proofs of task unsolvability in terms of the amount of knowledge that the processes should acquire in order to solve a task.Finally, we present a few preliminary links with the directed space semantics for concurrent programs. We show how chromatic subdivisions of a simplex can be recovered by considering combinatorial notions of directed paths
5
Philippe, Eva. "Geometric realizations using regular subdivisions : construction of many polytopes, sweep polytopes, s-permutahedra." Electronic Thesis or Diss., Sorbonne université, 2024. http://www.theses.fr/2024SORUS079.
Анотація:
Cette thèse concerne trois problèmes de réalisations géométriques de structures combinatoires par des polytopes et des subdivisions polyédrales. Un polytope est l'enveloppe convexe d'un ensemble fini de points dans un espace euclidien R^d. Il est muni d'une structure combinatoire donnée par ses faces. Une subdivision est une collection de polytopes dont les faces s'intersectent correctement et dont l'union est convexe. Elle est régulière si elle peut être obtenue en prenant les faces inférieures d'un relèvement de ses sommets dans une dimension de plus.Nous présentons d'abord une nouvelle construction géométrique d'un grand nombre de polytopes combinatoirement distincts, de dimension et nombre de sommets fixés. Cette construction consiste à montrer que certains polytopes admettent un grand nombre de triangulations régulières. Elle nous permet d'améliorer la meilleure borne inférieure connue sur le nombre de types combinatoires de polytopes.Nous étudions ensuite les projections du permutoèdre, nommées polytopes de balayage (sweep polytopes) parce qu'elles modélisent les manières d'ordonner une configuration de points fixée en balayant l'espace par des hyperplans dans une direction constante. Nous introduisons également et étudions une abstraction combinatoire de ces structures : les matroïdes orientés de balayage, qui généralisent en dimension supérieure à 2 la théorie des suites admissibles de Goodman et Pollack.Enfin, nous proposons des réalisations géométriques de l'ordre s-faible, une structure combinatoire qui généralise l'ordre faible sur les permutations, paramétrée par un vecteur s à coordonnées entières strictement positives. En particulier, nous résolvons une conjecture de Ceballos et Pons en montrant que le s-permutoèdre peut être réalisé comme le graphe d'un complexe polytopal qui est une subdivision du permutoèdreThis thesis concerns three problems of geometric realizations of combinatorial structures via polytopes and polyhedral subdivisions. A polytope is the convex hull of a finite set of points in a Euclidean space R^d. It is endowed with a combinatorial structure coming from its faces. A subdivision is a collection of polytopes whose faces intersect properly and such that their union is convex. It is regular if it can be obtained by taking the lower faces of a lifting of its vertices in one dimension higher.We first present a new geometric construction of many combinatorially different polytopes of fixed dimension and number of vertices. This construction relies on showing that certain polytopes admit many regular triangulations. It allows us to improve the best known lower bound on the number of combinatorial types of polytopes.We then study the projections of permutahedra, that we call sweep polytopes because they model the possible orderings of a fixed point configuration by hyperplanes that sweep the space in a constant direction. We also introduce and study a combinatorial abstraction of these structures: the sweep oriented matroids, that generalize Goodman and Pollack's theory of allowable sequences to dimensions higher than 2.Finally, we provide geometric realizations of the s-weak order, a combinatorial structure that generalizes the weak order on permutations, parameterized by a vector s with positive integer coordinates. In particular, we answer Ceballos and Pons conjecture that the s-weak order can be realized as the edge-graph of a polytopal complex that is moreover a subdivision of a permutahedron
6
Diakité, Abdoulaye Abou. "Application des cartes combinatoires à la modélisation géométrique et sémantique des bâtiments." Thesis, Lyon 1, 2015. http://www.theses.fr/2015LYO10281/document.
Анотація:
Les modèles 3D de bâtiment sont largement utilisés dans l'industrie de la construction et sont nécessités par plusieurs applications telles que la représentation architecturale et les processus de simulation. Malheureusement, ces modèles manquent souvent d'informations d'une importance majeure pour permettre d'effectuer des opérations d'analyse et de calcul. Les modèles originaux sont alors souvent reconstruits par les différents acteurs qui les utilisent afin de les rendre plus adaptés à leur besoins. Dans le but de pallier ce problème, nous introduisons une approche permettant d'enrichir un modèle 3D de bâtiment et le rendre beaucoup plus interopérable. À partir de l'information géométrique seulement, nous rajoutons au modèle des informations topologiques et sémantiques. Une subdivision cellulaire de l'espace occupé par le bâtiment est d'abord effectuée en se basant sur sa géométrie, puis les relations topologiques entre les cellules sont reconstruites et explicitement définies. Des étiquettes sémantiques sont ensuite attribuées aux composants identifiés du bâtiment à l'aide de la topologie reconstruite et des règles heuristiques prédéfinies. Une structure de données topologique appelée carte combinatoire 3D (3-carte) est utilisée comme une base solide pour la mise au point des opération de reconstruction et le traitement des informations reconstruites. À partir du modèle enrichi, nous montrons comment extraire des données pour des applications dédiées, par exemple la simulation acoustique et lancer de rayon pour la navigation intérieure. Notre méthode se présente comme un pont entre les approches de modélisation et les applications d'analyse du bâtiment qui utilisent ces modèles. Il est entièrement automatique et présente des résultats intéressants sur plusieurs types de modèles3D building models are widely used in the civil engineering industry. While the models are needed by several applications, such as architectural representations and simulation processes, they often lack of information that are of major importance for the consistency of the calculations. The original models are then often rebuilt in the way that fits better to the intended applications. To overcome this drawback, we introduce a framework allowing to enrich a 3D model of a building presenting just a geometry, in a way more interoperable model, by adding to it topological and semantic information. A cellular subdivision of the building space is first performed relying on its geometry, then the topological relationships between the cells are explicitely defined. Semantic labels are then attributed to the identified components based on the topology and defined heuristic rules. A 3D combinatorial map data structure (3-map) is used to handle the reconstructed information. From the enriched model we show how to extract applications-driven information allowing to perform acoustic simulation and indoor ray tracing navigation. The approach stands as a bridge between the modeling approaches and the applications in building analysis using the model. It is fully automatic and present interesting results on several types of building models
7
Pacheco-Martínez, Ana María. "Extracting cell complexes from 4-dimensional digital images." Thesis, Poitiers, 2012. http://www.theses.fr/2012POIT2262/document.
Анотація:
Une image numérique peut être définie comme un ensemble de n-xels sur une grille constituée de n-cubes. La segmentation consiste à calculer une partition d'une image en régions. Les n-xels ayant des caractéristiques similaires (couleur, intensité, etc.) sont regroupés. Schématiquement, à chaque n-xel est attribuée une étiquette, et chaque région de l'image est constituée de n-xels de même étiquette. Les méthodes "de type" Marching cubes et Kenmochi et al. construisent des complexes représentant la topologie de la région d'intérêt d'une image numérique binaire de dimension 3. Dans la première méthode, l'algorithme construit un complexe simplicial, dont 0-cellules sont des points des arêtes de la grille duale. Dans la deuxième méthode, les auteurs construisent un complexe cellulaire sur une grille duale, c.a.d les 0-cellules du complexe sont des sommets de la grille duale. Afin de construire le complexe, Kenmochi et al. calculent (à rotations près) les différentes configurations de sommets blancs et noirs d'un cube, puis, ils construisent les enveloppes convexes des points noirs de ces configurations. Ces enveloppes convexes définissent les cellules du complexe, à rotations près. Le travail développé dans cette thèse étend la méthode de Kenmochi et al. en dimension 4. L'objectif est de construire un complexe cellulaire à partir d'une image numérique binaire définie sur une grille duale. Nous calculons d'abord les différentes configurations de sommets blancs et noirs d'un 4-cube (à isométries près), puis, nous construisons des enveloppes convexes définies par ces configurations. Ces enveloppes convexes sont construites par déformation du 4-cube d'origine, et nous distinguonA digital image can be defined as a set of n-xels on a grid made up by n-cubes. Segmentation consists in computing a partition of an image into regions. The n-xels having similar characteristics (color, intensity, etc.) are regrouped. Schematically, each n-xel is assigned a label, and each region of the image is made up by n-xels with the same label. The methods "type" Marching cubes and Kenmochi et al. construct complexes representing the topology of the region of interest of a 3-dimensional binary digital image. In the first method, the algorithm constructs a simplicial complex, whose 0-cells are points of the edges of the dual grid. Inthe second one, the authors construct a cell complex on a dual grid, i.e. the 0-cells of the complex are vertices of the dual grid. In order to construct the complex, Kenmochi et al. compute (up to rotations) the different configurations of white and black vertices of a cube, and then, they construct the convex hulls of the black points of these configurations. These convex hulls define the cells of the complex, up to rotations. The work developed in this thesis extends Kenmochi et al. method todimension 4. The goal is to construct a cell complex from a binary digital image defined on a dual grid. First, we compute the different configurations of white and black vertices of a 4-cube, up to isometries, and then, we construct the convex hulls defined by these configurations. These convex hulls are constructed by deforming the original 4-cube, and we distinguishseveral basic construction operations (deformation, degeneracy of cells, etc.). Finally, we construct the cell complex corresponding to the dual image by assembling the cells so o
Una imagen digital puede ser definida como un conjunto de n–xeles en un mallado constituido de n–cubos. Los n–xeles pueden ser identificados con: (1) los n–cubos del mallado, o con (2) los puntos centrales de estos n–cubos. En el primer caso, trabajamos con un mallado primal, mientras que en el segundo, trabajamos con un mallado dual construido a partir del mallado primal. La segmentación consiste en calcular una partición de una imagen en regiones. Los n–xeles que tienen características similares (color, intensidad, etc.) son reagrupados. Esquemáticamente, a cada n–xel se le asocia una etiqueta, y cada región de la imagen está constituida de n–xeles con la misma etiqueta. En particular, si las únicas etiquetas permitidas para los n–xeles son “blanca” y “negra”, la segmentación se dice binaria: los n–xeles negros forman el primer plano (foreground) o región de interés en cuestión de análisis de la imagen, y los n–xeles blancos forman el fondo (background). Ciertos modelos, como los Grafos de Adyacencia de Regiones (RAGs), los Grafos Duales (DGs) y la carta topológica, han sido propuestos para representar las particiones en regiones, y en particular para representar la topología de estas regiones, es decir las relaciones de incidencia y/o adyacencia entre las diferentes regiones. El RAG [27] es un precursor de este tipo de modelos, y ha sido una fuente de inspiración de los DGs [18] y de la carta topológica [9, 10]. Un RAG representa una imagen primal etiquetada por un grafo: los vértices del grafo corresponden a regiones de la imagen, y las aristas del grafo representan las relaciones de adyacencia entre la regiones. Los DGs son un modelo que permite resolver ciertos inconvenientes de los RAGs para representar imágenes de dimensión 2. La carta topológica es una extensión de los modelos anteriores definida para manipular imágenes primales de dimensión 2 y 3, representando no solamente las relaciones topológicas, sino también las relaciones geométricas
8
Dovgal, Sergey. "An interdisciplinary image of Analytic Combinatorics." Thesis, Paris 13, 2019. http://www.theses.fr/2019PA131065.
Анотація:
Cette thèse est consacrée au développement des outils et à l’utilisation des méthodes de la combinatoire analytique, notamment l’énumération exacte et asymptotique, les propriétés statistiques des objets aléatoires et la génération aléatoire. L’ingrédient clé est la multidisciplinarité du domaine, qui est soulignée par des exemples tirés de la programmation logique, de la mécanique statistique, de la biologie, de la statistique mathématique, des réseaux et de la théorie des files d’attenteThis thesis is devoted to the development of tools and the use of methods from Analytic Combinatorics, including exact and asymptotic enumeration, statistical properties of random objects, and random generation.The key ingredient is the multidisciplinarity of the domain, which is emphasised by using examples from computational logic, statistical mechanics, biology, mathematical statistics, networks and queueing theory
9
Janaqi, Stefan. "Quelques éléments de la géométrie des graphes : graphes médians, produits d'arbres, génération convexe des graphes de Polymino." Université Joseph Fourier (Grenoble), 1994. http://www.theses.fr/1995GRE10093.
Анотація:
La notion d'intervalle dans un graphe, traduit de façon naturelle la notion du segment dans les espaces euclidiens. Par analogie, un ensemble C de sommets est convexe si pour tout couple x, y de sommets de C, l'intervalle entre x et y est inclu dans C. En utilisant la convexité géodésique, Djokovic a caractérisé les graphes isométriquement plongeable dans l'hypercube. Une vingtaine d'années plus tard, Mulder a caractérisé les graphes médians comme des graphes isométriquement plongeable dans l'hypercube et qui sont fermés pour l'opération médian. La comprehension du lien apparent entre ces deux résultats, nous a permis de trouver une nouvelle caractérisation, d'inspiration géométrique, des graphes médians. Cette caractérisation nous a permis à reconnaître les graphes médians qui sont des produits d'arbres ou de chemins. Nous avons donné une caractérisation de ces produits par mineurs convexes exclus. Un autre groupe de résultats concerne des graphes définis naturellement à partir des polyminos. En cherchant le nombre minimum de sommets qui engendrent convexement un tel graphe G, nous avons trouvé que ce nombre est égal au nombre maximum de sommets de degré un d'un arbre obtenu à partir de G par la contraction d'arêtes bien choisies
10
Jacques, Isabelle. "Aspects combinatoires en modélisation 2D et 3D et application à l'énumération des cartes et des solides." Mulhouse, 1991. http://www.theses.fr/1991MULH0185.
Анотація:
Après les travaux de W. T. Tutte sur le comptage de diverses familles de cartes planaires, le point de vue adopté ici est celui de la définition de transformations topologiques sur les cartes à partir desquelles on déduit des équations sur leurs séries génératrices. Un premier résultat concerne l'énumération des cartes sur le tore en fonction du nombre d'arêtes et du degré d'une face distinguée. Une nouvelle équation sur la série génératrice est obtenue après une étude détaillée d'une transformation topologique consistant à contracter une face distinguée. Un second résultat concerne l'étude d'un problème d'évolution linéaire sur un multigraphe muni d'une valuation formelle. La résolution de ce problème conduit à une équation nouvelle attachée à tout graphe. Cette équation, appliquée dans le cas particulier de l'arbre infini naturellement associé à la famille des cartes planaires, conduit à une équation nouvelle pour la série génératrice de ces cartes planaires, exprimant celle-ci en fonction de la série génératrice des mots de Dyck. Le troisième résultat concerne une généralisation à trois dimensions au niveau des solides topologiques, des notions classiques sur les cartes. La notion de solide est introduite en termes de sommets, arêtes, faces et en y ajoutant une composante supplémentaire : celle de volume. Une propriété importante mise en évidence est celle d'effeuillabilité, celle-ci permettant de généraliser en 3D la notion d'arbre par celle de solide effeuillable. On donne alors l'énumération d'une classe particulière de tels solides effeuillables : les solides-arbres par la suite de Schröder-Etherington
11
Tallot, Didier. "Quelques propositions pour la mise en oeuvre d'algorithmes combinatoires." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 1985. http://tel.archives-ouvertes.fr/tel-00806984.
Анотація:
Le travail, exposé dans ce rapport, se divise en deux parties. La première partie a fait l'objet d'un rapport de recherche publié en Avril 1984 [Tall]. La deuxième partie résulte d'un travail qui s'est déroulé de juin 1984 i juin 1985. Pour produire des images de hautes qualités, on est obligé de manipuler des grandes quantités de données. D'où l' intérêt d'étudier des algorithmes et des structures de données efficaces pour résoudre ~es problèmes géométriques. On pourra ainsi obtenir des méthodes efficaces pour la manipulation de données graphiques. On peut citer i ce propos, les travaux pionners de SHAMOS dans le domaine de la complexité géométrique [Sham]. La deuxième partie contient la description d 'un logiciel interactif *de manipulation de graphes et d'ordres. A notre connaissnce, la plus ancienne réalisation de ce type de logiciel est le "Graph theory interactive system" de WOLFBERG [Wolf]. Suivant les travaux de GUIDO sur CABRI (CAhier de BRouillon Informatisé), nous desirons offrir un poste de travail sur les graphes pour des chercheurs en théorie des graphes. CABRI est une bonne approche du problème, mais reste d'un emploi malaisé. Nous avons donc étudiés de nouveau le problème en nous attachant à décrire une meilleure interface utilisateur. Nous nous sommes inspirés des travaux sur les logiciels interactif existant, comme ceux développés chez XEROX, au PALO-ALTO RESEARCH CENTER (Smit] chez NIEVERGELT [Sere].
12
Ghazo, Hanna Zeina. "Cycles combinatoires et géométriques." Thesis, Brest, 2020. http://www.theses.fr/2020BRES0006.
Анотація:
Le travail de cette thèse se situe dans les domaines de la théorie combinatoire des graphes, la combinatoire algébrique et la géométrie discrète. D'un part, il concerne l'énumération des chemins et cycles Hamiltoniens de type donné dans un tournoi ; de l'autre part, il étudie des suites numériques vérifiant une équation à différence quadratique. Parmi les résultats obtenus dans la première partie, on trouve : une égalité entre le nombre des chemins (resp. cycles) Hamiltoniens d’un type donné dans un tournoi et dans son complément; une expression du nombre de chemins Hamiltoniens d’un type donné pour un tournoi transitif en termes d'une fonction récursive F appelée « path-function »; la construction d'un algorithme pour le calcul de F. L'objet fondamental dans la deuxième partie est un graphe cyclique muni d'une solution d'une équation à différence quadratique. Un paramètre de cette équation distingue les solutions réelles et les solutions complexes. Une correspondance entre les solutions réelles et une classe de polynômes à coefficients entiers positifs est établie. Pour compléter la correspondance, les digraphes Eulériens à un pas interviennent. Une solution complexe détermine une marche fermée dans le plan pour laquelle à chaque pas on tourne à gauche ou à droite par un angle constant (l'angle tournant). Cette fois-ci les polynômes cyclotomiques jouent un rôle important. La caractérisation des polynômes qui déterminent de telles suites est un problème qu’on surmonte afin d'élucider des propriétés géométriques de tels cycles polygonaux. Notamment, lorsque la marche exploite les côtés d'un polygone régulier avec angle extérieur 2π/n, on trouve des phénomènes non anticipés lorsque n≥12The work in this thesis concerns the combinatorial theory of graphs, algebraic combinatorics and discrete geometry. On one side, it is about enumerating Hamiltonian paths and cycles of a given type in a tournament; On the other side, it studies numerical sequences verifying a quadratic difference equation.Concerning the results of the first part, we find: an equality between the number of Hamiltonians paths (resp. cycles) of a given type, in a tournament and its complement; an expression of the number of Hamiltonian oriented paths of a given type in a transitive tournament in terms of a recursive function F called the « path-function »; and the construction of an algorithm to compute F.In the second part of the work, we study cyclic graphs altogether with a solution to a quadratic difference equation.A parameter of this equation distinguishes real and complex sequences. A correspondence between real solutions and a class of polynomials with positive integer coefficients is established. To complete the correspondence, 1-step Eulerian digraphs interfere. A complex solution determines a closed planar walk in the plane, for which at each step we turn either left or right by a constant angle (the turning angle). This time, cyclotomic polynomials play a major role. Characterizing polynomials that determine such a solution is a problem that we study to the end of finding geometric properties of such polygonal cycles.When the walk exploits the sides of a regular polygon with exterior angle 2 π/n, we find unexpected phenomena when n≥ 12
13
Bienaise, Solène. "Tests combinatoires en analyse géométrique des données - Etude de l'absentéisme dans les industries électriques et gazières de 1995 à 2011 à travers des données de cohorte." Phd thesis, Université Paris Dauphine - Paris IX, 2013. http://tel.archives-ouvertes.fr/tel-00941220.
Анотація:
La première partie de la thèse traite d'inférence combinatoire en Analyse Géométrique des Données (AGD). Nous proposons des tests multidimensionnels sans hypothèse sur le processus d'obtention des données ou les distributions. Nous nous intéressons ici aux problèmes de typicalité (comparaison d'un point moyen à un point de référence ou d'un groupe d'observations à une population de référence) et d'homogénéité (comparaison de plusieurs groupes). Nous utilisons des procédures combinatoires pour construire un ensemble de référence par rapport auquel nous situons les données. Les statistiques de test choisies mènent à des prolongements originaux : interprétation géométrique du seuil observé et construction d'une zone de compatibilité.La seconde partie présente l'étude de l'absentéisme dans les Industries Electriques et Gazières de 1995 à 2011 (avec construction d'une cohorte épidémiologique). Des méthodes d'AGD sont utilisées afin d'identifier des pathologies émergentes et des groupes d'agents sensibles.
14
Tomasini, Jérôme. "Géométrie combinatoire des fractions rationnelles." Thesis, Angers, 2014. http://www.theses.fr/2014ANGE0032/document.
Анотація:
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
15
Gay, Joël. "Representation of Monoids and Lattice Structures in the Combinatorics of Weyl Groups." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLS209/document.
Анотація:
La combinatoire algébrique est le champ de recherche qui utilise des méthodes combinatoires et des algorithmes pour étudier les problèmes algébriques, et applique ensuite des outils algébriques à ces problèmes combinatoires. L’un des thèmes centraux de la combinatoire algébrique est l’étude des permutations car elles peuvent être interprétées de bien des manières (en tant que bijections, matrices de permutations, mais aussi mots sur des entiers, ordre totaux sur des entiers, sommets du permutaèdre…). Cette riche diversité de perspectives conduit alors aux généralisations suivantes du groupe symétrique. Sur le plan géométrique, le groupe symétrique engendré par les transpositions élémentaires est l’exemple canonique des groupes de réflexions finis, également appelés groupes de Coxeter. Sur le plan monoïdal, ces même transpositions élémentaires deviennent les opérateurs du tri par bulles et engendrent le monoïde de 0-Hecke, dont l’algèbre est la spécialisation à q=0 de la q-déformation du groupe symétrique introduite par Iwahori. Cette thèse se consacre à deux autres généralisations des permutations. Dans la première partie de cette thèse, nous nous concentrons sur les matrices de permutations partielles, en d’autres termes les placements de tours ne s’attaquant pas deux à deux sur un échiquier carré. Ces placements de tours engendrent le monoïde de placements de tours, une généralisation du groupe symétrique. Dans cette thèse nous introduisons et étudions le 0-monoïde de placements de tours comme une généralisation du monoïde de 0-Hecke. Son algèbre est la dégénérescence à q=0 de la q-déformation du monoïde de placements de tours introduite par Solomon. On étudie par la suite les propriétés monoïdales fondamentales du 0-monoïde de placements de tours (ordres de Green, propriété de treillis du R-ordre, J-trivialité) ce qui nous permet de décrire sa théorie des représentations (modules simples et projectifs, projectivité sur le monoïde de 0-Hecke, restriction et induction le long d’une fonction d’inclusion).Les monoïdes de placements de tours sont en fait l’instance en type A de la famille des monoïdes de Renner, définis comme les complétés des groupes de Weyl (c’est-à-dire les groupes de Coxeter cristallographiques) pour la topologie de Zariski. Dès lors, dans la seconde partie de la thèse nous étendons nos résultats du type A afin de définir les monoïdes de 0-Renner en type B et D et d’en donner une présentation. Ceci nous conduit également à une présentation des monoïdes de Renner en type B et D, corrigeant ainsi une présentation erronée se trouvant dans la littérature depuis une dizaine d’années. Par la suite, nous étudions comme en type A les propriétés monoïdales de ces nouveaux monoïdes de 0-Renner de type B et D : ils restent J-triviaux, mais leur R-ordre n’est plus un treillis. Cela ne nous empêche pas d’étudier leur théorie des représentations, ainsi que la restriction des modules projectifs sur le monoïde de 0-Hecke qui leur est associé. Enfin, la dernière partie de la thèse traite de différentes généralisations des permutations. Dans une récente séries d’articles, Châtel, Pilaud et Pons revisitent la combinatoire algébrique des permutations (ordre faible, algèbre de Hopf de Malvenuto-Reutenauer) en terme de combinatoire sur les ordres partiels sur les entiers. Cette perspective englobe également la combinatoire des quotients de l’ordre faible tels les arbres binaires, les séquences binaires, et de façon plus générale les récents permutarbres de Pilaud et Pons. Nous généralisons alors l’ordre faibles aux éléments des groupes de Weyl. Ceci nous conduit à décrire un ordre sur les sommets des permutaèdres, associaèdres généralisés et cubes dans le même cadre unifié. Ces résultats se basent sur de subtiles propriétés des sommes de racines dans les groupes de Weyl qui s’avèrent ne pas fonctionner pour les groupes de Coxeter qui ne sont pas cristallographiquesAlgebraic combinatorics is the research field that uses combinatorial methods and algorithms to study algebraic computation, and applies algebraic tools to combinatorial problems. One of the central topics of algebraic combinatorics is the study of permutations, interpreted in many different ways (as bijections, permutation matrices, words over integers, total orders on integers, vertices of the permutahedron…). This rich diversity of perspectives leads to the following generalizations of the symmetric group. On the geometric side, the symmetric group generated by simple transpositions is the canonical example of finite reflection groups, also called Coxeter groups. On the monoidal side, the simple transpositions become bubble sort operators that generate the 0-Hecke monoid, whose algebra is the specialization at q=0 of Iwahori’s q-deformation of the symmetric group. This thesis deals with two further generalizations of permutations. In the first part of this thesis, we first focus on partial permutations matrices, that is placements of pairwise non attacking rooks on a n by n chessboard, simply called rooks. Rooks generate the rook monoid, a generalization of the symmetric group. In this thesis we introduce and study the 0-Rook monoid, a generalization of the 0-Hecke monoid. Its algebra is a proper degeneracy at q = 0 of the q-deformed rook monoid of Solomon. We study fundamental monoidal properties of the 0-rook monoid (Green orders, lattice property of the R-order, J-triviality) which allow us to describe its representation theory (simple and projective modules, projectivity on the 0-Hecke monoid, restriction and induction along an inclusion map).Rook monoids are actually type A instances of the family of Renner monoids, which are completions of the Weyl groups (crystallographic Coxeter groups) for Zariski’s topology. In the second part of this thesis we extend our type A results to define and give a presentation of 0-Renner monoids in type B and D. This also leads to a presentation of the Renner monoids of type B and D, correcting a misleading presentation that appeared earlier in the litterature. As in type A we study the monoidal properties of the 0-Renner monoids of type B and D : they are still J-trivial but their R-order are not lattices anymore. We study nonetheless their representation theory and the restriction of projective modules over the corresponding 0-Hecke monoids. The third part of this thesis deals with different generalizations of permutations. In a recent series of papers, Châtel, Pilaud and Pons revisit the algebraic combinatorics of permutations (weak order, Malvenuto-Reutenauer Hopf algebra) in terms of the combinatorics of integer posets. This perspective encompasses as well the combinatorics of quotients of the weak order such as binary trees, binary sequences, and more generally the recent permutrees of Pilaud and Pons. We generalize the weak order on the elements of the Weyl groups. This enables us to describe the order on vertices of the permutahedra, generalized associahedra and cubes in the same unified context. These results are based on subtle properties of sums of roots in Weyl groups, and actually fail for non-crystallographic Coxeter groups
16
Khoshnoudirad, Daniel. "Aspects combinatoires des motifs linéaires en géométrie discrète." Thesis, Paris Est, 2016. http://www.theses.fr/2016PESC1046.
Анотація:
La Géométrie Discrète, comme Science de l'Informatique Théorique, étudie notamment les motifs linéaires tels que les primitives discrètes apparaissant dans les images : les droites discrètes, les segments discrets, les plans discrets, les morceaux de plans discrets par exemple. Dans ce travail, je me concentre tout particulièrement sur les diagrammes de Farey qui apparaissent lors de l'étude des primitives discrètes que sont les (m,n)-cubes, autrement dit les morceaux de plans discrets. J’étudie notamment la Combinatoire des droites formant les diagrammes de Farey, en établissant des formules exactes. Je montre alors que certaines méthodes utilisées auparavant ne permettront pas d'optimiser la Combinatoire des (m,n)-cubes. J'obtiens aussi une estimation asymptotique en utilisant la Théorie des Nombres Combinatoire. Puis, concernant les sommets apparaissant dans les diagrammes de Farey, j'obtiens une borne inférieure. J'analyse alors les stratégies déjà mises en place pour l'étude des $(m,n)$-cubes par les seuls diagrammes de Farey en deux dimensions. Afin d'obtenir de nouvelles bornes plus précises pour les $(m,n)$-cubes, une des seules méthodes actuellement existantes, est de proposer une généralisation de la notion de pré image d'un segment discret, à celle de pré image d'un $(m,n)$-cube, avec pour conséquence une nouvelle inégalité combinatoire sur le cardinal des (m,n)-cubes (inégalité qui pourrait même s'avérer être une égalité). Ainsi, nous introduisons la notion de diagramme de Farey en trois dimensionsDiscrete Geometry, as Theoretical Computer Science, studies in particular linear patterns such as discrete primitives in images: the discrete lines, discrete segments, the discrete planes, pieces of discrete planes, for example. In this work, I particularly focused on Farey diagrams that appear in the study of the $ (m, n) $ - cubes, ie the pieces of discrete planes. Among others, I study the Combinatorics of the Farey lines forming diagram Farey, establishing exact formulas. I also get an asymptotic estimate using Combinatorial Number Theory. Then, I get a lower bound for the cardinality of the Farey vertices. After that, we analyze the strategies used in the literature for the study of (m, n)- cubes only by Farey diagrams in two dimensions. In order to get new and more accurate bounds for (m, n)- cubes, one of the few available methods, is to propose a generalization for the concept of preimage of a discrete segment for (m, n) - cube, resulting in a new combinatorial inequality. Thus, we introduce the notion Farey diagram in three dimensions
17
Fossas, Ariadna. "Sur la géométrie et la combinatoire du groupe T de Thompson." Thesis, Grenoble, 2012. http://www.theses.fr/2012GRENM104/document.
Анотація:
Cette thèse concerne le groupe T de Thompson. Ce groupe simple infini et finiment présenté est généralement vu comme un sous-groupe du groupe des homéomorphismes dyadiques du cercle unité qui sont linéaires par morceaux et préservent l'orientation («T linéaire par morceaux»). Cependant, T peut aussi être vu comme: 1.- le groupe des classes d'équivalence des paires équilibrées d'arbres binaires finis («T combinatoire»), 2.- un sous-groupe du groupe des homéomorphismes de la droite projective réelle qui préservent l'orientation et sont «PSL(2,Z) par morceaux» («T projectif par morceaux»), et 3.- le groupe modulaire asymptotique de l'épaissi, dans le plan hyperbolique, de l'arbre régulier de valence 3 («T modulaire»).On montre d'abord que la copie canonique de PSL(2,Z) obtenue à partir de «T projectif par morceaux» est un sous-groupe non distordu de T. Pour cela, on transporte ce sous-groupe pour obtenir une caractérisation dans le «T combinatoire», ce qui permet d'estimer la longueur des mots de ses éléments. La non-distorsion est alors une conséquence des propriétés métriques de T établies par Burillo-Cleary-Stein-Taback. Comme corollaire, T a des sous-groupes non distordus isomorphes au groupe libre engendré par deux éléments. Qui plus est, PSL(2,Z) est aussi donné explicitement sous forme «linéaire par morceaux».Le deuxième résultat utilise «T modulaire» pour prouver qu'il y a exactement f(n) classes de conjugaison d'éléments d'ordre n dans T, où f est l'indicatrice d'Euler. Étant donné un élément de torsion t de T d'ordre n, on trouve une triangulation du disque de Poincaré qui est invariante sous l'action de T sauf dans un polygone convexe à n côtés. On construit ensuite un complexe cellulaire C contractile et simplement connexe sur lequel le groupe T agit par automorphismes, et qui est minimal pour ces propriétés. Le groupe d'automorphismes de C est essentiellement T lui même (c'est une extension de T par le groupe d'ordre 2). Ce complexe cellulaire peut être vu comme une généralisation des associaèdres deStasheff dans le cas d'un polygone convexe à une infinité de côtés. L'action de T sur C est transitive sur les arêtes et les sommets, et plus généralement, sur les cellules «de type associaèdre» de toute dimension.La partie finale décrit les premières étapes d'un programme de recherche. On utilise l'interprétation géométrique du 1-squelette de C en termes de triangulations dyadiques du disque de Poincaré pour définir un bord géométrique à l'infini. Bien qu'on ait prouvé auparavant que le 1-squelette de C n'est pas hyperbolique, la construction s'inspire de celle de Gromov et permet la description de certains points du bordThis PhD thesis is concerned with Thompson's group T. This infinite, finitely presented, simple group is usually seen as a subgroup of the group of dyadic, piecewise linear, orientation-preserving homeomorphisms of the unit circle (piecewise linear T). However, T can also be identified to: 1.- a group of equivalence classes of balanced pairs of finite binary trees (combinatorial T), 2.- a subgroup of piecewise PSL(2,Z), orientation-preserving homeomorphisms of the projective real line (piecewise projective T), and 3.- the asymptotic mapping class group of a fattened complete trivalent tree in the hyperbolic plane (modular T). The first result shows that the canonical copy of PSL(2,Z) obtained from the piecewise projective T is a non-distorted subgroup of T. For this, one carries over this subgroup to obtain a characterization into combinatorial T, from which the word length of its elements can be estimated. Then, non-distortion follows from the metric properties of T established by Burillo-Cleary-Stein-Taback. As a corollary, T has non-distorted subgroups isomorphic to the free non-abelian group of rank 2. Furthermore, PSL(2,Z) is also explicitly given in the piecewise linear form.The second result uses modular T to state that there are exactly f(n) conjugacy classes of elements of order n, where f is the Euler function. Given a torsion element t of T of order n, a dyadic triangulation of the Poincaré disc which is invariant under the action of t modulo a convex polygon with n sides is found.The third result constructs a minimal simply-connected contractible cellular complex C on which the group T acts by automorphisms. The automorphism group of C is essentially T itself (strictly speaking it is an extension of T by the group of order 2). The cellular complex C can be seen as a generalization of Stasheff's associahedra for an infinitely sided convex polygon. The action of T on C is transitive on vertices and edges and, plus generally, on associahedral type cells in all dimensions.The final part deals with the first steps of a research project. One uses the geometric interpretation of the 1-skeleton of C in term of dyadic triangulations of the Poincaré disc to define a geometric boundary at infinity. Although the 1-skeleton of C is proved not to be hyperbolic, the construction imitates Gromov's construction of the boundary of hyperbolic spaces, and allows the description of the nature of some of the boundary points
18
Pharamond, Layla dit D'Costa. "Géométrie réelle des dessins d'enfant." Paris 6, 2002. http://www.theses.fr/2002PA066298.
19
Jeanne, Hadrien. "Langages géométriques et polycubes." Rouen, 2010. http://www.theses.fr/2010ROUES007.
Анотація:
Ce mémoire comporte deux parties. La première concerne l'étude des langages géométriques au moyen d'outils de la théorie des automates et de géométrie discrète. Un langage géométrique est composé de mots définis sur un alphabet de taille d, en utilisant les images de Parikh de l'ensemble des préfixes de ces mots. Ce qui définit une figure de dimension d. Dans la seconde partie, il est question de l'étude de polycubes de dimension 3. Il y est défini des extensions de certaines própriétés des polyominos en dimension 3. Cela permet de définir différentes classes de polycubes, les polycubes plateaux, s-dirigés et verticalement convexes s-dirigés. Une méthode d'énumération de polycubes dirigés, basée sur la décomposition par strates des polyominos de Temperley, est appliquée à ces classes de polycubes afin de donner leurs fonctions génératricesThis thesis falls into two parts. The first one is about the study of geometrical languages using formal languages and automata theory, as well as discrete geometry tools. A geometrical language is composed of words over an alphabet of size d, using the Parikh images of the set of prefixes of the words. Those images define a figure of dimension d. The second part refers to the study of 3-dimensional polycubes. We define 3-dimensional extensions of some properties of polyominoes. That allow us to define subclasses of polycubes : plateau polycubes, s-directed polycubes and vertically-convex s-directed polycubes. We define an enumeration method over directed polycubes, based on the strate decomposition of polyominoes defined by Temperley, and we use it in order to give the generating functions of the classes of polycubes defined above
20
Guilbot, Robin. "Quelques aspects combinatoires et arithmétiques des variétés toriques complètes." Phd thesis, Université Paul Sabatier - Toulouse III, 2012. http://tel.archives-ouvertes.fr/tel-00832228.
Анотація:
Dans cette thèse nous étudions deux aspects distincts des variétés toriques, l'un purement géométrique, sur C, et l'autre de nature arithmétique, sur des corps quasi algébriquement clos (corps C1). Les courbes extrémales qui engendrent le cône de Mori d'une variété torique projective sont des courbes primitives (V. Batyrev). En 2009, D. Cox et C. von Renesse ont conjecturé que les courbes primitives engendrent le cône de Mori de toute variété torique dont l'éventail est à support convexe, de dimension maximale. Nous présentons une famille de contre-exemples à cette conjecture et en proposons une nouvelle formulation basée sur la notion de contractibilité locale, généralisant la notion de contractibilité de C. Casagrande. Grâce aux couloirs, outils combinatoires que nous introduisons, nous montrons comment écrire une classe de 1-cycle donnée comme combinaison linéaire à coefficients entiers de classes de courbes toriques. Les couloirs nous permettent de donner une décomposition explicite de toute classe qui n'est pas contractible (couloirs droits) ainsi que de certaines classes contractibles (couloirs circulaires). Les corps C1 sont les corps sur lesquels l'existence de points rationnels dans une variété Y est assurée par le plongement en petit degré de Y dans un espace projectif (par définition) ou dans un espace projectif pondéré (d'après un théorème facile de Kollar). Pour un diviseur ample dans une variété torique dont l'éventail est simplicial et complet, nous montrons qu'il existe encore une notion de petit degré qui assure l'existence de points rationnels. Ceci nous permet notamment de montrer l'existence de points rationnels sur une large classe de variétés rationnellement connexes.
21
Martinez, Sandoval Leonardo Ignacio. "Contributions en géométrie combinatoire : rayons du cercle circonscrit différentes, théorèmes géométriques de type Hall, théorèmes fractionnaires de type Turán, matroïdes chemin du réseau et transversales de Kneser." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT277/document.
Анотація:
La géométrie combinatoire est une large et belle branche des mathématiques. Cette thèse doctorale se compose de l'étude de cinq sujets différents dans ce domaine. Même si les problèmes et les techniques utilisés pour y faire face sont divers, ils partagent le mêeme objectif: Étudier l'interaction entre les structures combinatoires et géométriques. Dans le chapitre 1, nous étudions le problème suivant : pour un entier positif k, combien de points en position générale devons-nous prendre dans le plan de sorte que nous pouvons toujours trouver k d'entre eux définissant des triangles avec un rayon du cercle circonscrit distinct ? Cette question a été posée par Paul Erdös en 1975 qui a lui même proposé une solution en 1978. Toutefois, la preuve a omis par inadvertance un cas non trivial. Nous avons repris ce cas et donné une solution à la question en utilisant des outils de base de la géométrie algébrique et nous fournissons une borne polynomiale pour le nombre de points nécessaires.Dans le chapitre 2, nous sommes intéressés par de généralisations géométriques du critère de Hall pour les couplages dans les graphes bipartits (1935). Nous obtenons des théorèmes géométriques type Hall pour des ensembles convexes disjoints et pour points en position générale dans l'espace euclidien. Les outils de ce chapitre sont topologiques, et l'approche est motivés par une méthode remarquable introduite par Aharoni et Haxell en $2000$ ainsi que par ses généralisations.D'autre part, dans le chapitre 3, nous commençons par un théorème de Helly fractionné de 1979 due à A. Liu et M. Katchalski pour motiver un résultat combinatoire. Nous étudions des conditions combinatoires que des familles de graphes doivent avoir pour permettre d'obtenir des versions plus fine du théorème de Turán. Nous trouvons des liens intéressants entre les nombres de Turán, les nombres chromatiques et les nombres de clique dans la famille. Les outils de ce chapitre sont purement combinatoires.Dans le chapitre 4, nous nous concentrons sur l'obtention des résultats pour la bien connue classe des matroïde chemin du réseau introduite par Bonin, de Mier et Noy en 2003. La contribution principale est de prouver pour cette classe la validité d'une conjecture de Merino et Welsh (1999) sur une inégalité de certaines valeurs du polynôme de Tutte. Pour ce faire, nous introduisons et étudions des serpents, une classe spéciale de matroïdes chemin du réseau ``mince''.Enfin, dans le chapitre 5, nous étudions une variante d'un problème des transversales posé par J.L. Arocha, J. Bracho, L. Montejano et J.L. Ramírez-Alfonsín en 2010. Dans leur travaux originaux, ils ont rémarqué que si nous avons peu de points dans l'espace euclidien alors il est possible de trouver une transversale d'une dimension donnée qui travers les enveloppes convexes de tous les k-ensembles de points. De m&eme, ils montrent qu'il est impossible de trouver une telle transversale lorsque nous avons beaucoup de points. Les auteurs donnent des bornes spécifiques et ils laissent aussi quelques problèmes ouverts. Si la définition de transversale est légèrement plus restrictive, alors le problème peut être étudié en utilisant la théorie des matroïdes orientés. Dans la présente thèse, nous fournissons les détails de cette relation et nous donnons des bornes pour la famille de polytopes cycliquesCombinatorial geometry is a broad and beautiful branch of mathematics. This PhD Thesis consists of the study of five different topics in this area. Even though the problems and the tools used to tackle them are diverse, they share a unifying goal: To explore the interaction between combinatorial and geometric structures.In Chapter 1 we study a problem by Paul Erdös: for a positive integer k, how many points in general position do we need in the plane so that we can always find a k-subset of them defining triangles with distinct circumradii? This question was posed in 1975 and Erdös himself proposed a solution in 1978. However, the proof inadvertently left out a non-trivial case. We deal with the case using basic tools from algebraic geometry and we provide a polynomial bound for the needed number of points.In Chapter 2 we are interested in providing geometric extensions of Hall's criterion for matchings in bipartite graphs (1935). We obtain geometric Hall-type theorems for pairwise disjoint convex sets and for points in general position in euclidean space. The tools of this chapter are topological, and are motivated by a remarkable method introduced by Aharoni and Haxell in 2000 and its generalizations.On the other hand, in Chapter 3 we begin with a fractional Helly theorem from 1979 by A. Liu and M. Katchalski to motivate a combinatorial result. We study combinatorial conditions on families of graphs that allow us to have sharpened variants of Turán's theorem. We find interesting relations between the Turán numbers, the chromatic numbers and the clique numbers of graphs in the family. The tools in this chapter are only combinatorial.In Chapter 4 we focus on obtaining some results for the well studied class of lattice path matroids introduced by Bonin, de Mier and Noy in 2003. The main contribution is proving for this class the validity of a 1999 conjecture of Merino and Welsh concerning an inequality involving certain values of the Tutte polynomial. In order to do this, we introduce and study snakes, a special class of ``thin'' lattice path matroids.Finally, in Chapter 5 we explore a variant of a transversal problem posed by J.L. Arocha, J. Bracho, L. Montejano and J.L. Ramírez-Alfonsín in 2010. In their original work, they realized that if we have few points in euclidean space then it is possible to find a transversal of a given dimension that goes through all the convex hulls of k-subsets of points. Similarly, they show that it is impossible to find such a transversal when we have many points. The authors give some specific bounds and they also leave some open problems. If the definition of transversal is slightly more restrictive, then the problem can be tackled using oriented matroid theory. We provide the details of the relation and we give bounds for the family of cyclic polytopes
22
Gross, Clauoe. "Opérations topologiques et géométriques sur les multicartes combinatoires : application à la cartographie thématique." Université Louis Pasteur (Strasbourg) (1971-2008), 1989. http://www.theses.fr/1989STR13032.
Анотація:
A partir de la notion de cartes combinatoires topologiques, sont définis un modèle de carte topologique qui permet de décrire complètement la topologie d'une carte planaire et le modèle de carte géométrique qui associe à une carte topologique une représentation dans un plan euclidien. Ceci permet le développement d'un algorithme de saisie de cartes planaires qui détecte automatiquement la fermeture des polygones
23
Labbé, Sébastien. "Structure des pavages, droites discrètes 3D et combinatoire des mots." Thèse, Paris 7, 2012. http://www.archipel.uqam.ca/4940/1/D2363.pdf.
Анотація:
Cette thèse, constituée d'une série d'articles, considère des questions issues de la géométrie discrète en les traitant du point de vue de la combinatoire des mots qui s'avère un outil puissant et approprié pour les résoudre. Nous utilisons les mots soit pour représenter un chemin dans Z2 ou Z3, soit pour coder la suite des virages d'un chemin ou le contour d'une figure discrète fermée. Parmi les thèmes abordés, on compte les pavages du plan par polyominos, la notion de complexité en facteurs palindromes et la génération de droites discrètes 3D. La première partie concerne les pavages du plan où nous étudions le nombre de pavages réguliers du plan par une tuile carrée, c'est-à-dire une tuile ayant quatre tuiles adjacentes identiques. Il s'avère que certaines tuiles carrées pavent le plan de deux façons distinctes et elles sont appelées doubles carrées. Nous démontrons d'abord qu'il y a au plus deux tels pavages réguliers par une tuile carrée. Ensuite, nous considérons deux familles particulières de tuiles doubles carrées : les tuiles de Christoffel et les tuiles de Fibonacci. Ces deux familles décrivent les plus petits exemples de tuiles doubles carrées et peuvent être définies à partir des mots de Christoffel et du mot de Fibonacci par des règles de substitution et de concaténation. Les tuiles de Fibonacci définissent aussi une fractale, obtenue par un chemin auto-évitant, dont nous avons calculé plusieurs statistiques, comme le rapport de l'aire de la fractale sur l'aire de son enveloppe convexe. Dans l'article suivant, nous démontrons que tout double carré indécomposable est invariant sous une rotation de 180 degrés. Cette propriété géométrique est équivalente au fait que le mot de contour de la tuile se factorise en un produit de palindromes. Notre preuve repose sur une méthode de génération exhaustive des tuiles doubles carrées. La deuxième partie concerne la complexité palindromique - le nombre de facteurs palindromes distincts -, un sujet propre à la combinatoire des mots. Nous y considérons quatre classes de complexité palindromique qui découlent naturellement de la notion de défaut. Nous caractérisons notamment les mots de complexité palindromique minimale sur un alphabet à deux lettres et nous démontrons que les mots infinis obtenus par codage de rotations sur deux intervalles atteignent la complexité palindromique maximale. Dans une troisième partie, nous proposons une méthode basée sur des algorithmes de fractions continues multidimensionnelles pour la génération de droite discrètes 3D 6-connexes. Les expérimentations illustrent que la complexité en facteurs des mots ainsi générés serait linéaire. Cela se compare avantageusement aux autres définitions de droites discrètes 3D 6-connexes dont la complexité en facteurs est quadratique.
______________________________________________________________________________
MOTS-CLÉS DE L’AUTEUR : combinatoire des mots, géométrie discrète, pavage, polyomino, complexité palindromique, droite discrète, algorithme de fractions continues multidimensionnelles.
24
Pouyanne, Nicolas. "Quelques contributions au carrefour de la géométrie, de la combinatoire et des probabilités." Habilitation à diriger des recherches, Université de Versailles-Saint Quentin en Yvelines, 2006. http://tel.archives-ouvertes.fr/tel-00403659.
Анотація:
Ce travail est la synthèse de travaux de recherches en mathématiques, dont les thèmes sont empruntés à la géométrie algébrique, la combinatoire analytique et les probabilités. La première partie concerne les variétés algébriques complexes de dimension trois. On y présente un calcul de la cohomologie singulière de variétés toriques lisses non complètes, ainsi que la construction d'un modèle toroïdal des singularités-quotient, dont le calcul nécessite l'étude combinatoire fine de l'action des groupes finis de matrices unitaires sur le plan projectif. La deuxième partie développe une adaptation "hybride" de la méthode de Darboux et de l'analyse des singularités pour le développement asymptotique des coefficients d'une série entière dans certains cas de frontière naturelle d'analyticité. De nombreux exemples issus de l'analyse combinatoire sont ainsi traités, dont celui de l'analyse d'algorithmes de factorisation de polynômes sur les corps finis qui sont utilisés en calcul formel et pour les codes correcteurs d'erreurs. La troisième partie résout une conjecture sur les arbres $m$-aires de recherche qui sont une structure fondamentale de l'algorithmiques des ensembles de données. Le modèle considéré est un modèle d'urnes qui se généralise en la notion de processus aléatoires de Pòlya dont le comportement asymptotique général est étudié. Dans la quatrième partie, on construit un arbre aléatoire associé à la \emph{Chaos Game Representation} utilisée en bio-mathématique et en bio-informatique du génôme. Les asymptotiques de la hauteur et de la profondeur d'insertion de ces arbres y sont établies.
25
Braun, David. "Approche combinatoire pour l'automatisation en Coq des preuves formelles en géométrie d'incidence projective." Thesis, Strasbourg, 2019. http://www.theses.fr/2019STRAD020.
Анотація:
Ce travail de thèse s’inscrit dans le domaine de la preuve assistée par ordinateur et se place d'un point de vue méthodologique. L’objectif premier des assistants de preuves est de vérifier qu’une preuve écrite à la main est correcte; la question ici est de savoir comment à l’intérieur d’un tel système, il est possible d'aider un utilisateur à fabriquer une preuve formelle du résultat auquel il s'intéresse. Ces questions autour de la vérification de preuves, en particulier en certification du logiciel, et au delà de leur traçabilité et de leur lisibilité sont en effet devenues prégnantes avec l’importance qu’ont prise les algorithmes dans notre société. Bien évidemment, répondre à la question de l’aide à la preuve dans toute sa généralité dépasse largement le cadre de cette thèse. C’est pourquoi nous focalisons nos travaux sur la preuve en mathématiques dans un cadre particulier qui est bien connu dans notre équipe : la géométrie et sa formalisation dans le système Coq. Dans ce domaine, nous mettons premièrement en évidence les niveaux auxquels on peut oeuvrer à savoir le contexte scientifique à travers les méthodes de formalisation mais aussi le contexte méthodologique et technique au sein de l'assistant de preuve Coq. Dans un second temps, nous essayons de montrer comment nos méthodes et nos idées sont généralisables à d'autres disciplines. Nous mettons ainsi en place dans nos travaux les premiers jalons pour une aide à la preuve efficace dans un contexte géométrique simple mais omniprésent. À travers une approche classique fondée sur la géométrie synthétique et une approche combinatoire complémentaire utilisant le concept de rang issu de la théorie des matroïdes, nous fournissons à l'utilisateur des principes généraux et des outils facilitant l'élaboration de preuves formelles. Dans ce sens, nous comparons les capacités d'automatisation de ces deux approches dans le contexte précis des géométries finies avant de finalement construire un prouveur automatique de configuration géométrique d'incidenceThis thesis work is part of the general field of computer-assisted proof and is methodologically based. The primary objective of proof assistants is to verify that handwritten demonstration is correct; the question here is how within such a system, it is possible to help a user to make a formal proof of the result in which he is interested. These questions around the verification of proofs, in particular in software certification, and beyond their traceability and readability have indeed become significant with the importance that algorithms have taken on in our society. Obviously, answering the question of proof assistance in all its generality goes far beyond the scope of this thesis. This is why we focus our work on proof in mathematics in a particular framework that is well known in our team: geometry and its formalization in the Coq system. In this field, we first highlight the levels at which we can work, namely the scientific context through the formalization methods but also the methodological and technical context within the Coq proof assistant. In a second step, we try to show how our methods and ideas can be generalized to other disciplines. In this way, we are putting in place the first steps towards effective proof assistance in a simple but omnipresent geometric context. Through a classical approach based on synthetic geometry and a complementary combinatorial approach using the concept of rank from matroid theory, we provide the user with general principles and tools to facilitate the development of formal proof. In this sense, we compare the automation capabilities of these two approaches in the specific context of finite geometries before finally constructing an automatic prover of geometric configurations of incidence
26
Fresse, Lucas. "Une étude combinatoire de la géométrie des fibres de Springer de type A." Lyon 1, 2007. http://www.theses.fr/2007LYO10322.
Анотація:
On appelle fibre de Springer la variété des drapeaux stables par un endomorphisme nilpotent. Nous étudions cette variété et ses composantes irréductibles. Les points fixes d’un tore sur cette variété sont paramétrés par un ensemble de tableaux dits lignes-standards. Nous construisons une décomposition en cellules de la variété naturellement paramétrée par les tableaux lignes-standards, au sens où chaque cellule contient un point fixe, et dont la codimension des cellules est analogue une longueur de Bruhat. Cela permet un calcul pratique des nombres de Betti. Lorsque l’endomorphisme nilpotent est de type crochet, deux-lignes ou deux-colonnes, nous définissons une notion de constructibilité pour les tableaux lignes-standards qui permet de décrire les points fixes des composantes. Nous déduisons un calcul de la dimension d’une intersection finie de composantes et, dans le cas deux colonnes, un critère de singularitéThe variety of flags which are stable by a nilpotent endomorphism is called Springer fiber. We study this variety and its irreducible components. The fixed points of a torus on this variety are parameterized by a set of tableaux said row-standard. We construct a cell decomposition of the variety which is naturally parameterized by the row-standard tableaux, since each cell contains one fixed point, and such that the codimension of cells is analogous to a Bruhat length. This allows a handy calculation of the Betti numbers. When the nilpotent endomorphism is of hook, two-rows or two-columns type, we define a notion of constructibility for the row-standard tableaux which allows to describe the fixed points of the components. We deduce a calculation of the dimension of a finite intersection of components and, in the two-columns case, a criterion of singularity
27
Guilbot, Robin. "Quelques aspects combinatoires et arithmétiques des variétés toriques complètes." Phd thesis, Toulouse 3, 2012. http://thesesups.ups-tlse.fr/1905/.
Анотація:
Dans cette thèse nous étudions deux aspects distincts des variétés toriques, l'un purement géométrique, sur C, et l'autre de nature arithmétique, sur des corps quasi algébriquement clos (corps C1). Les courbes extrémales qui engendrent le cône de Mori d'une variété torique projective sont des courbes primitives (V. Batyrev). En 2009, D. Cox et C. Von Renesse ont conjecturé que les courbes primitives engendrent le cône de Mori de toute variété torique dont l'éventail est à support convexe, de dimension maximale. Nous présentons une famille de contre-exemples à cette conjecture et en proposons une nouvelle formulation basée sur la notion de contractibilité locale, généralisant la notion de contractibilité de C. Casagrande. Grâce aux couloirs, outils combinatoires que nous introduisons, nous montrons comment écrire une classe de 1-cycle donnée comme combinaison linéaire à coefficients entiers de classes de courbes toriques. Les couloirs nous permettent de donner une décomposition explicite de toute classe qui n'est pas contractible (couloirs droits) ainsi que de certaines classes contractibles (couloirs circulaires). Les corps C1 sont les corps sur lesquels l'existence de points rationnels dans une variété Y est assurée par le plongement en petit degré de Y dans un espace projectif (par définition) ou dans un espace projectif pondéré (d'après un théorème facile de Kollar). Pour un diviseur ample dans une variété torique dont l'éventail est simplicial et complet, nous montrons qu'il existe encore une notion de petit degré qui assure l'existence de points rationnels. Ceci nous permet notamment de montrer l'existence de points rationnels sur une large classe de variétés rationnellement connexesIn this thesis we study two distinct aspects of toric varieties, one purely geometric, over C, and the other of arithmetic nature, over quasi algebraically closed fields (C1 fields). Extremal curves, which generate the Mori cone of a projective toric variety, are primitive curves (V. Batyrev). In 2009, D. Cox and C. Von Renesse conjectured that the classes of primitive curves generate the Mori cone of any toric variety whose fan has full dimensional convex support. We present a family of counterexamples to this conjecture and propose a new formulation based on the notion of local contractibility, generalizing the contractibility defined by C. Casagrande. Using the corridors, a combinatorial tool that we introduce, we show how to write any given 1-cycle class as a linear combination with integer coefficients of toric curve classes. Corridors enable us to give an explicit decomposition of any class that is not contractible (straights corridors) as well as contractible classes in some particular cases (circular corridors). C1 fields are those over which the existence of rational points on a variety Y is ensured by any small degree embedding of Y in a projective space (by definition) or in a weighted projective space (according to an easy theorem of Kollar). For an ample divisor in a toric variety whose fan is simplicial and complete, we show that there is also a notion of small degree which ensures the existence of rational points. This way, we show the existence of rational points on a large class of rationally connected varieties
28
LIRA, DE LIMA ARILEIDE. "Groupes speciaux : aspects algebriques et combinatoires de la theorie des espaces d'ordres abstraits." Paris 7, 1996. http://www.theses.fr/1996PA077090.
Анотація:
Nous etudions les espaces d'ordres abstraits. D'abord, nous faisons une etude algebrique, en definissant sur le groupe associe a ces espaces, une relation d'equivalence qui satisfait un nombre fini d'axiomes formules dans un langage de premier ordre. Nous appelons cette structure groupe special. Nous prouvons alors qu'il existe une dualite entre la categorie des espaces d'ordres abstraits et la categorie des groupes speciaux reduits (avec une definition convenable de morphismes pour ces categories). Cette dualite permet, par exemple, de caracteriser un des axiomes (le moins clair) de la definition d'espace d'ordres abstrait, d'utiliser les techniques de la theorie de modeles pour l'etude de ces espaces et, plus generalement, de donner un nouveau point de vue pour la theorie algebrique reduite des formes quadratiques. Ensuite, nous nous interessons aux aspects geometriques des espaces d'ordres abstraits (en utilisant des techniques de la theorie des matroides). En effet, nous demontrons que les espaces d'ordres abstraits sont munis d'une structure de geometrie combinatoire binaire et bipartite (les circuits sont tous de cardinalite paire). En utilisant ces resultats, nous donnons un lemme technique (lemme technique a), qui classifie certaines geometries combinatoires finies qui representent des espaces d'ordres abstraits. Ce cercle d'idees permet d'obtenir des nouveaux resultats, ainsi que d'ameliorer, preciser et eclaircir le corpus deja connu de la theorie des espaces d'ordres abstraits
29
Glisse, Marc. "Combinatoire des droites et segments pour la visibilité 3D." Phd thesis, Université Nancy II, 2007. http://tel.archives-ouvertes.fr/tel-00192337.
Анотація:
Cette thèse présente principalement des résultats sur la combinatoire des droites et segments qui apparaissent naturellement dans l'étude des problèmes de visibilité en trois dimensions. Nous exposons en premier lieu des résultats sur la taille de la silhouette d'un objet vu d'un point, c'est à dire sur la complexite de l'ensemble des droites ou segments tangents à l'objet et passant par le point. Nous présentons en particulier les premières bornes théoriques non triviales pour des polyèdres non-convexes, à savoir que, sous des hypothèses raisonnables, la complexité moyenne de la silhouette est au plus la racine carrée de la complexité du polyèdre, phénomène largement observé en infographie. Nous présentons aussi des bornes, en moyenne et dans le cas le pire, sur le nombre de droites et segments tangents à quatre objets dans une scène composée d'objets polyédriques ou sphériques. Ces bornes donnent en particulier l'espoir que la complexité des structures de données globales comme le complexe de visibilité ne soit pas nécessairement prohibitive. Les bornes sur les polytopes sont également les premières à tirer parti des propriétés structurelles des scènes composées de triangles organisés en polytopes de facon réaliste, c'est à dire non nécessairement disjoints. Ces bornes induisent enfin les premières bornes non triviales sur la complexité des ombres induites par des sources lumineuses non ponctuelles. Les résultats presentés dans cette thèse améliorent significativement l'état de l'art sur les propriétés combinatoires des structures de visibilité en trois dimensions et devraient favoriser les développements algorithmiques futurs pour ces problèmes.
30
Hils, Martin. "Fusion libre et autres constructions génériques." Phd thesis, Université Paris-Diderot - Paris VII, 2006. http://tel.archives-ouvertes.fr/tel-00274128.
Анотація:
L'objet de cette thèse est l'étude des amalgames de Hrushovski dans le contexte relatif. D'abord, la fusion libre de deux théories simples de rang 1 T(1) et T(2) est construite, au-dessus d'un réduit commun T(0) qui est supposé fortement minimal et omega-catégorique. Dans bien des cas, il est montré que ses complétions sont simples. Si les T(i) sont fortement minimales et si une condition géométrique est satisfaite - par exemple si le réduit commun est un espace vectoriel sur un corps fini - la fusion libre est complète et omega-stable. En supposant de plus que les multiplicités sont définissables dans T(i), le collapse de la fusion libre sur une fusion fortement minimale est effectuée. Puis, des variations sur le thème de la fusion sont étudiées (courbe générique et structures bicolores). À titre d'exemple, il suit des résultats que l'on peut donner un sens à la notion d'une courbe générique dans un corps pseudofini. Enfin, l'axiomatisabilité de l'automorphisme générique est démontrée dans certains contextes issus d'une amalgamation à la Hrushovski dont la fusion libre et les théories des différents corps bicolores de Poizat (noir, rouge et vert).
31
Modolo, Marie-Eve. "Histoire de la normalisation canonique d'une famille de courbes algébriques : aspects algorithmiques, combinatoires et géométriques." Poitiers, 2007. http://www.theses.fr/2007POIT2277.
32
Chaboud, Thomas. "Pavages et graphes de Cayley planaires." Lyon, École normale supérieure (sciences), 1995. http://www.theses.fr/1995ENSL0004.
Анотація:
Les deux premiers chapitres introduisent les thèmes abordés et les définitions afférentes. Le chapitre 3 établit une généralisation d'un algorithme de Thurston de pavage par dominos dans la grille carrée et le réseau triangulaire. Nous montrons que les mêmes techniques permettent d'obtenir des pavages par dominos (deux faces partageant une arête) de parties finies simplement connexes de graphes planaires dont le dual est régulier et biparti, en temps linéaire sur la surface. Même dans les cas ou le graphe sous-jacent est régulier, nous remarquons qu'il n'admet pas en général d'étiquetage par un groupe ; les groupes de pavage de Conway ne suffisent donc pas à expliquer cette combinatoire. Le chapitre 4 établit une caractérisation des graphes planaires euclidiens ou hyperboliques gk, d réguliers (degré d), de dual régulier (degré k) admettant un étiquetage de graphe de Cayley. G admet un tel étiquetage ssi k a un facteur inférieur a d. La preuve est effective: On construit au moins un étiquetage pour tous les cas positifs. Le chapitre 5 prouve et expose un algorithme permettant d'obtenir toutes les présentations étiquetant un graphe planaire donné, s'il admet un plongement localement fini sur le plan euclidien ou hyperbolique ; nous montrons qu'un tel graphe induit toujours un pavage du plan par des polygones reguliers. Nous décrivons des graphes de Cayley planaires hors de cette classe. Enfin, le chapitre 6 montre une caractérisation linéaire des polyominos horizontalement et verticalement convexes admettant un pavage optimal par des dominos
33
De, Joannis de Verclos Rémi. "Applications des limites de structures combinatoires en géométrie et en théorie des graphes." Thesis, Université Grenoble Alpes (ComUE), 2018. http://www.theses.fr/2018GREAM037/document.
Анотація:
Cette thèse traite de problèmes liés à la théorie des limitesd'objets combinatoires, une récente théorie qui a permis de tisserdes liens entre différents domaines tels que la combinatoire,l'analyse, la géométrie ou la théorie de la probabilité.Cette thèse applique des méthode venant de cette théorie à des problèmesde combinatoire extrémale.Dans un premier chapitre, je développe une théorie des limites d'objetsappelés emph{types d'ordre}, un objets qui encode des configurationsd'ensembles de points du plan. Le type d'ordre d'un ensemble de pointssuffit à caractériser de nombreuses propriétés essentielles de cet ensemblede point comme, par exemple, son enveloppe convexe.Je montre qu'une limite de type d'ordre peut être représentée par un objetanalogue à un graphon à valeurs O ou 1.Je fais ensuite le lien entre limites de type d'ordre et la distributionnaturelle de limite de type d'ordre obtenue par l’échantillonnage de pointsdu plan suivant une certaine probabilité.De cette manière, toute probabilité sur le plan engendre une limite de typed'ordre. Je montre d'une part que cette correspondance n'est pas surjective-c'est à dire qu'il existe des limites de type d'ordre ne venant pas de probabilitédu plan- et j'étudie d'autre part son injectivité.Je montre que si le support d'une mesure de probabilité est assez gros, par exemple siil contient une boule ouvert, alors la limite que cette mesure engendre suffit à caractériser cette mesure à une transformation projective près.Un second chapitre traite de test de propriété.Un testeur de propriété est un algorithme aléatoire permettant de séparerles objets ayant une certaine propriété des objet à distance au moins εde l'avoir, au sens de la distance d'édition.Ce domaine donne des algorithmes extrêmement rapides, et en particulierdes algorithmes dont la complexité ne dépends pas de la taille de l'entréemais seulement du paramètre de précision ε.Un résultat fondamental de cet domaine pour les graphes montré par Alonet Shapira est le suivant : toute classe de graphe héréditaire possède un teltesteur.Cette thèse contribue à la question suivante :Quelles classes de graphes possède un testeur dont la complexité est unpolynôme en 1/ε ?Je montre qu'en particulier la classe des graphes d'intervales possède un teltesteur.La théorie des algèbres de drapeaux est un outil étroitement lié aux limites degraphes denses qui donne une méthode pour démontrer des bornes sur certainsparamètres combinatoires à l'aide d'un ordinateur.Dans un troisième chapitre, je présente un programme écrit durant ma thèsequi implémente cette méthode.Ce programme fonctionne comme une bibliothèque pour calculer dans les algèbresde drapeaux, manipuler des inégalités sur les drapeaux ou encoder des problèmesd'optimisations par une instance de programme semi-défini positif qui peutensuite être résolu par un solveur externe.Ce programme est en particulier utilisé pour obtenir un nouvelle borne pour le cas triangulaire de la conjecture de Caccetta-HäggkvistThis thesis is focused on problems related to the theory of combinatorial limits.This theory opened links between different fields such asanalysis, combinatorics, geometry and probability theory.In this thesis, we apply ideas coming from this framework toproblems in extremal combinatorics.In a first chapter we develop a theory of limits for emph{order types},a geometrical object that encodes configuration of a set of points in theplane by the mean of the orientations of their triangles.The order type of a point set suffices to determine many of its properties,such as for instance the boundary of its convex hull.We show that the limit of a converging sequence of order typescan be represented by random-free object analogous to a graphon.Further, we link this notion to the natural distributions of order typesarising from the sampling of random points from some probability measureof the plane.We observe that in this mean, every probability measure gives rise to a limitof order types.We show that this map from probability measure on the plane to limit oforder type is not surjective.Concerning its injectivity,we prove that if a measure has large enough support, for instance if its supportcontains an open ball, the limit of order types the measure generatessuffices to essentially determine this measure.A second chapter is focused on property testing.A tester is a randomized algorithm for distinguishing between objects satisfyinga property from those that are at some distance at least εfrom having itby means of the edition distance.This gives very efficient algorithms, and in particular algorithms whosecomplexity does not depend on the size of the input but only on the parameter ε.For graphs, it has been shown by Alon and Shapira that every hereditary propertyhas such a tester.We contribute to the following question :which classes of graphs have a one-sided property tester with a number of queries that is a polynomial in 1/ε ?We give a proof that the class of interval graphs has such a tester.The theory of flag algebras is a framework introduced by Razborovclosely related to dense limit of graphs, that gives a way to systematicallyderive bounds for parameters in extremal combinatorics.In a third chapter we present a program developed during my Phd.that implements this method.This program works as a library that can compute flag algebras,manipulate inequalities on densities and encode the optimization of some parameterin a semi-definite positive instance that can be given to a dedicated solverto obtain a bound on this parameter.This program is in particular used to obtain a new bound forthe triangle case of the Caccetta-Häggkvist conjecture
34
Vo, Phi Khanh. "Contributions à l'étude des arrangements : équivalences combinatoires et perturbations." Université Joseph Fourier (Grenoble), 1994. http://tel.archives-ouvertes.fr/tel-00344973.
Анотація:
Cette thèse est une contribution à l'étude des arrangements. L'idée est le calcul de la combinatoire d'un arrangement de courbes ou surfaces compte tenu du fait que les données et les opérations ne seront connues qu'à une précision près. Dans cette démarche, il se pose un problème qui est de savoir si la combinatoire d'un arrangement est stable lorsque les éléments constitutifs sont perturbés. Un préliminaire indispensable est alors d'établir une définition rigoureuse adaptée à nos besoin concernant l'équivalence des arrangements. Le travail consiste essentiellement en un développement des notions mathématiques nécessaires pour étudier l'équivalence, la construction, les perturbations d'arrangements. Quelques résultats en terme d'analyse de complexité sont également énoncés. Des résultats sont obtenus sur les perturbations d'arrangements d'hyperplans en dimension quelconque. Dans le plan est étudiée une méthode particulière de calcul des arrangements des courbes, avec un exemple détaillé sur les cercles. Utilisant des transformations classiques de dualité, des applications des propriétés d'équivalence des arrangements d'hyperplans aux configurations de points et aux diagrammes de Voronoï sont aussi données
35
Dehlinger, Christophe. "Spécifications et preuves en Coq pour les surfaces combinatoires et leur classification." Université Louis Pasteur (Strasbourg) (1971-2008), 2003. http://www.theses.fr/2003STR13236.
36
Delalleau, Guillaume. "Substitutions sur la droite et dans le plan." Paris 7, 2011. http://www.theses.fr/2011PA077218.
Анотація:
Ce mémoire est scindée en deux parties de trois chapitres chacune. Il est question dans la première partie d'écritures S-adiques de mots. On étudie dans le premier chapitre la con¬vergence des écritures S-adiques; on y propose une forme générale des valeurs d'adhérences de telles écritures, et en déduisons des conditions suffisantes générales pour leur convergence. Dans le second chapitre, nous spécifions des conditions auxquelles les écritures S-adiques pour un alphabet de substitutions donné forment un attracteur. Nous ébauchons sous ces conditions une démarche pouvant mener à la conjecture S-adique. Une estimation systématique de la complexité factorielle d'un point fixe de substitution est nécessaire; nous proposons pour cela de nous aider du graphe des ancêtres de cette substitution; des résultats partiels sont obtenus. Dans le troisième chapitre, la question de l'existence de fréquences pour les lettres dans les écritures S-adiques est abordée via l'action des substitutions sur le simplexe des fréquences. La seconde partie traite de pavages substitutifs du plan par des tuiles carrées et colorées. Dans le cinquième chapitre, on donne une représen¬tation des motifs par des graphes, et isolons des conditions nécessaires et suffisantes pour qu'un tel graphe représente un motif. Dans le sixième chapitre, nous définissons des substitutions bidimensionelle comme transformation des sommets et arêtes des graphes de lettres représentant des motifs; des conditions nécessaires et suffisantes pour que les graphes ainsi construits représentent des motifs sont dégagées. Dans le septième chapitre nous proposons un mode de construction de pavages S-adiques du planThis memoir is split in two parts of three chapters each. The theme of the first part is S-adic words. The first chapter is concerned with the convergence of S-adic sequences; we propose a general form for the accumulation points of S-adic sequences, and infer from it general sufficient conditions for the convergence. In the second chapter, conditions on the alphabet of substitutions for the S-adic words to form an attractor in the set of infinite words. When these conditions are met, we adumbrate a way to a solution of the S-adic conjecture. The first step, a more systematic study of the factorial complexity of fixed points of substitutions, is taken and partial results are obtained. In the third chapter, we touch upon the question of the existence of frequencies for letters in S-adic words through the action of substitutions on the frequency simplex. The second part is concerned with tilings of the plane with square and colored tiles. In the fifth chapter, we propose a representation of patches by graphs and give necessary and sufficient conditions for a graph to represent a patch. In the sixth chapter we define bidimensional substitutions as transformations of the vertices ans edges of the graph representing patches; necessary and sufficient conditions for a graph thus built to represent a patch are given. In the seventh chapter we propose a construction of S-adic tilings of the plane by square and colored tiles
37
Kyriakoglou, Revekka. "Morphismes itérés, combinatoire des mots et systèmes dynamiques symboliques." Thesis, Paris Est, 2019. http://www.theses.fr/2019PESC2050.
Анотація:
La thèse actuelle porte sur le thème de la combinatoire des mots et des systèmes dynamiques symboliques. Les systèmes dynamiques symboliques sont des objets permettant de coder les trajectoires de mots dans des systèmes dynamiques de transformations d’espaces topologiques. Parmi ces systèmes dynamiques, des exemples bien connus sont donnés par des mots sturmiens et par d'échange d’intervalles. Les mots sturmiens sont liés à des algorithmes de géométrie discrète et l’échange d’intervalles forme une classe intéressante de systèmes dynamiques. En outre, il convient de mentionner que certaines familles d'échanges fournissent des généralisations prometteuses de mots sturmiens. Le sujet principal de la thèse est la reconnaissabilité des mots générés par les morphismes primitifs. Le concept de reconnaissabilité des morphismes trouve son origine dans l’article de Martin [1] sous le terme de détermination. Host a utilisé ce terme pour la première fois dans son article sur la théorie ergodique des systèmes dynamiques [2]. La notion de reconnaissabilité est apparue après lintêrt manifesté par de nombreux scientifiques pour ses diverses applications théoriques dans divers domaines, de la combinatoire des mots à la dynamique symbolique. Une notion similaire est celle de la circularit. Les deux termes sont souvent, mais pas toujours utilisés comme synonymes. Ce manque de cohérence dans la littérature pourrait être source de confusion. À la connaissance de l’auteur, il n’y a pas encore d’étude qui rassemble ces définitions et prouve leur équivalence ou indique les différences qui existent entre elles. Une approche solide de ce sujet, utilisant une définition cohérente de la reconnaissabilité et de la circularité. La notion de reconnaissabilité associée à une technique utilisée dans [3] a été utilisée afin de démontrer la décidabilité de différentes propriétés de graphes d’extension (définis dans [18]) d’éléments d’un langage. Les familles d’ensembles peuvent être définies à partir des propriétés du graphe d’extension de leurs éléments, tels que les ensembles acycliques, les ensembles d’arbres, les ensembles neutres, etc. Plus précisément, pour un ensemble de mots S, on peut associer à chaque mot w ∈ S son extension graphique qui décrit les extensions gauche et droite possibles de w dans S. Nous montrons comment utiliser la reconnaissabilité pour fournir la décidabilité des graphes d’extension. En outre, la notion de reconnaissance est utilisée dans lobjet de semigroupes profinite. Nous décrivons la relation entre la reconnaissabilité des morphismes et les propriétés des semigroupes profinites libres [5].Bibliography[1] John C. Martin. Minimal flows arising from substitutions of non-constant length. Math. Systems Theory, 7:72–82, 1973.[2] B. Host. Valeurs propres des systèmes dynamiques définis par des substitutions de longueur variable. Ergodic Theory Dynam. Systems, 6(4):529–540, 1986.[3] Klouda, K. and Starosta, Š. "Characterization of circular D0L systems", arXiv preprint arXiv:1401.0038 (2013).[4] Berthé, V., De Felice, C., Dolce, F. et al. Monatsh Math (2015) 176: 521. https://doi.org/10.1007/s00605-014-0721-4[5]Kyriakoglou ,R., Perrin ,D. "Profinite semigroups", arXiv:1703.10088 (2017)The current thesis focuses on the topic of combinatorics on words and symbolic dynamical systems. The symbolic dynamical systems are objects for encoding word trajectories in dynamic systems of transformations in topological spaces. Among these dynamical systems, well-known examples are given by Sturmial words and by exchange of intervals. The Sturmian words are related to discrete geometry algorithms and the exchange of intervals form an interesting class of dynamical systems. Furthermore, it should be mentioned that some exchange families provide promising generalizations of Sturmian words.The main subject of the thesis is the recognizability of words generated by primitive morphisms. The concept of recognizability of morphisms originates in the paper of Martin [1] under the term of determinization. The term was first used by Host in his paper on the Ergodic theory of Dynamical Systems[2]. The notion of recognizability came in full bloom after the interest shown by many scientists due to its various theoretical applications in various topics, from combinatorics on words to symbolic dynamics. A similar notion is that of circularity. The two terms are often, but not always used as synonymous. This lack of consistency along the literature could result in confusion. To the best of the author’s knowledge, there is not, as of yet, any study that collects those definitions and proves their equivalence or indicates the differences among them. This thesis provides a solid approach to this subject, using a coherent definition of recognizability and circularity.The notion of recognizability alongside a technique used in [3] were used in order to prove the decidability of different properties of extension graphs (defined in [4]) of elements of a language. Families of sets can be defined from properties of the extension graph of their elements, such as acyclic sets, tree sets, neutral sets, etc. More precisely, given a set of words S, one can associate with every word w ∈ S it's extension graph which describes the possible left and right extensions of w in S. We show how to use the recognizability to provide decidability of extension graphs. Furthermore, recognizability is used in is the subject of Profinite Semigroups. We describe the relationship between the recognizability of morphisms and properties of the free profinite semigroups [5].Bibliography[1] John C. Martin. Minimal flows arising from substitutions of non-constant length. Math. Systems Theory, 7:72–82, 1973.[2] B. Host. Valeurs propres des systèmes dynamiques définis par des substitu-tions de longueur variable. Ergodic Theory Dynam. Systems, 6(4):529–540,1986.[3] Klouda, K. and Starosta, Š. "Characterization of circular D0L systems.", arXiv preprint arXiv:1401.0038 (2013).[4] Berthé, V., De Felice, C., Dolce, F. et al. Monatsh Math (2015) 176: 521. https://doi.org/10.1007/s00605-014-0721-4[5]Kyriakoglou ,R., Perrin ,D. "Profinite semigroups", arXiv:1703.10088 (2017)[6]Almeida, J., "Profinite semigroups and applications" In Structural theory of automata, semigroups, and universal algebra, volume 207 of NATO Sci.43 Ser. II Math. Phys. Chem., pages 1–45. Springer, Dordrecht, 2005. Notes taken by Alfredo Costa
38
Blondin, masse Alexandre. "A l'intersection de la combinatoire des mots et de la géométrie discrète : palindromes, symétries et pavages." Phd thesis, Université de Grenoble, 2011. http://tel.archives-ouvertes.fr/tel-00697886.
Анотація:
Dans cette thèse, différents problèmes de la combinatoire des mots et de géométrie discrète sont considérés. Nous étudions d'abord l'occurrence des palindromes dans les codages de rotations, une famille de mots incluant entre autres les mots sturmiens et les suites de Rote. En particulier, nous démontrons que ces mots sont pleins, c'est-à-dire qu'ils réalisent la complexité palindromique maximale. Ensuite, nous étudions une nouvelle famille de mots, appelés mots pseudostandards généralisés, qui sont générés à l'aide d'un opérateur appelé clôture pseudopalindromique itérée. Nous présentons entre autres une généralisation d'une formule décrite par Justin qui permet de générer de façon linéaire et optimale un mot pseudostandard généralisé. L'objet central, le f-palindrome ou pseudopalindrome est un indicateur des symétries présentes dans les objets géométriques. Dans les derniers chapitres, nous nous concentrons davantage sur des problèmes de nature géométrique. Plus précisément, nous don-nons la solution à deux conjectures de Provençal concernant les pavages par translation, en exploitant la présence de palindromes et de périodicité locale dans les mots de contour. À la fin de plusieurs chapitres, différents problèmes ouverts et conjectures sont brièvement présentés.
39
Blondin, Massé Alexandre. "A l'intersection de la combinatoire des mots et de la géométrie discrète : palindromes, symétries et pavages." Thesis, Grenoble, 2011. http://www.theses.fr/2011GRENM072/document.
Анотація:
Dans cette thèse, différents problèmes de la combinatoire des mots et de géométrie discrète sont considérés. Nous étudions d'abord l'occurrence des palindromes dans les codages de rotations, une famille de mots incluant entre autres les mots sturmiens et les suites de Rote. En particulier, nous démontrons que ces mots sont pleins, c'est-à-dire qu'ils réalisent la complexité palindromique maximale. Ensuite, nous étudions une nouvelle famille de mots, appelés mots pseudostandards généralisés, qui sont générés à l'aide d'un opérateur appelé clôture pseudopalindromique itérée. Nous présentons entre autres une généralisation d'une formule décrite par Justin qui permet de générer de façon linéaire et optimale un mot pseudostandard généralisé. L'objet central, le f-palindrome ou pseudopalindrome est un indicateur des symétries présentes dans les objets géométriques. Dans les derniers chapitres, nous nous concentrons davantage sur des problèmes de nature géométrique. Plus précisément, nous don-nons la solution à deux conjectures de Provençal concernant les pavages par translation, en exploitant la présence de palindromes et de périodicité locale dans les mots de contour. À la fin de plusieurs chapitres, différents problèmes ouverts et conjectures sont brièvement présentésIn this thesis, we explore different problems at the intersection of combinatorics on words and discrete geometry. First, we study the occurrences of palindromes in codings of rotations, a family of words including the famous Sturmian words and Rote sequences. In particular, we show that these words are full, i.e. they realize the maximal palindromic complexity. Next, we consider a new family of words called generalized pseudostandard words, which are generated by an operator called iterated pseudopalindromic closure. We present a generalization of a formula described by Justin which allows one to generate in linear (thus optimal) time a generalized pseudostandard word. The central object, the f-palindrome or pseudopalindrome, is an indicator of the symmetries in geometric objects. In the last chapters, we focus on geometric problems. More precisely, we solve two conjectures of Provençal about tilings by translation, by exploiting the presence of palindromes and local periodicity in boundary words. At the end of many chapters, different open problems and conjectures are briefly presented
40
Bouttier, Jérémie. "Physique statistique des surfaces aléatoires et combinatoire bijective des cartes planaires." Phd thesis, Université Pierre et Marie Curie - Paris VI, 2005. http://tel.archives-ouvertes.fr/tel-00010651.
Анотація:
Les cartes sont des objets combinatoires apparaissant en physique comme discrétisation naturelle des surfaces aléatoires employées pour la gravité quantique bidimensionnelle ou la théorie des cordes, ainsi que dans les modèles de matrices. Après rappel de ces relations, nous établissons des correspondances entre diverses classes de cartes et d'arbres, autres objets combinatoires de structure simple. Un premier intérêt mathématique de ces constructions est de donner des preuves bijectives, élémentaires et rigoureuses, de plusieurs résultats d'énumération de cartes. Par ailleurs, nous accédons ainsi à une information fine sur la géométrie intrinsèque des cartes, conduisant à des résultats analytiques exacts grâce à une propriété inattendue d'intégrabilité. Nous abordons enfin la question de l'existence d'une limite continue universelle.
41
Mora, Thierry. "Géométrie et inférence dans l'optimisation et en théorie de l'information." Paris 11, 2007. http://www.theses.fr/2007PA112162.
42
Salaün, Isabelle. "Deux problèmes de géométrie combinatoire : unimodalité de deux suites en théorie des matroïdes ; polyèdres : polyèdre régulier à vingt-quatre sommets de l'espace euclidien à quatre dimensions." Paris 6, 1988. http://www.theses.fr/1988PA066524.
Анотація:
On considère la suite des nombres de fermes de rang fixe (nombres de Whitney) et la suite des nombres d'indépendants de cardinal fixe d'un matroide. On obtient des résultats partiels concernant l'unimodalité conjecturée de ces suites (1972). On traite de matroides orientés. On étudie les polyèdres réguliers dans les espaces euclidiens a trois et quatre dimensions. On montre, en particulier, que le polyèdre régulier à vingt-quatre sommets de l'espace à quatre dimensions n'a qu'une classe d'orientations.
43
Bertault, François. "Génération et tracé de structures décomposables." Nancy 1, 1997. http://www.theses.fr/1997NAN10297.
Анотація:
L'objet de cette thèse est la réalisation d'algorithmes et d'outils d'aide à l'étude des propriétés de structures combinatoires particulières, les structures décomposables. Nous nous intéressons pour cela à la génération aléatoire et systématique de structures décomposables, puis à leur représentation graphique automatique. Ce travail se situe à la frontière entre calcul mathématique et visualisation. Les structures décomposables sont les structures combinatoires qu'il est possible de former récursivement en utilisant des constructeurs aux propriétés particulières. Le point de vue est similaire à celui adopté dans la théorie des espèces de structures, où l'on privilégie la description d'ensembles de structures à partir de transformations d'ensembles existants. Il est alors possible, grâce à des spécifications, de décrire une infinité d'ensembles de structures combinatoires parmi lesquels les permutations, les graphes fonctionnels, les arbres enracinés ou encore les hiérarchies. L'intérêt de cette démarche tient au fait que l'on sait résoudre des problèmes de dénombrement et de comportement asymptotique sur ces ensembles et générer aléatoirement de façon uniforme des structures de ces ensembles. Les applications concernent le calcul de complexité en moyenne d'algorithmes, et la génération de jeux de tests pour la validation expérimentale ou l'étalonnage d'algorithmes. Nous présentons dans cette thèse deux types de résultats. Les premiers concernent la génération de structures décomposables, les seconds leur représentation graphique. Nous présentons une implantation d'un algorithme classique de génération aléatoire de structures décomposables, et nous proposons des techniques permettant de générer tous les éléments d'un ensemble à partir de sa spécification. Nous proposons également un algorithme de tracé de graphes particuliers, pour lesquels il existe à la fois des relations d'adjacence et d'inclusion entre les noeuds. Ces graphes, que nous appelons les graphes composés, sont en effet bien adaptés à la représentation de la nature générique des structures décomposables. Ce travail est concrétisé par la réalisation de deux logiciels de tracé de structures combinatoires. Leur utilisation n'est cependant pas limitée à ce seule domaine et les aspsects liés à leur application à la visualisation de graphes en général sont abordésThe main goal of the thesis is to conceive algorithms and tools to assist people who study a special kind of combinatorial structures, namely decomposable structures. The two major questions we try to solve are: How to generate, randomly or by some systematic procedure, a decomposable structure; How to draw decomposable structures. Decornposable structures are combinatorial structures that are recursively described using a small set of constructors. The idea consists in considering a structure as a process of construction from simpler structures. The main interest of the decomposable structure theory is that we can describe an infinite number of different sets of structures, including permutations, varions kind of trees or functional graphs, for which we can solve counting and random generation problems. Possible applications are the average case analysis of algorithms and the production of test inputs for the experimental validation of programs. We propose an algorithm for drawing decomposable structures based on the translation into special graphs, that we call composed graphs, in which bath inclusion and adjacency relationships can exist. The principle is based on the translation of decomposable structures into composed graphs, i. E. Graphs with both inclusion and adjacency relationships. The drawing of composed graph is achieved by using different classical graph drawing algorithm together. The number of algorithms that can be used on a sarne drawing is infinite. The only restriction is that the algorithms must be able to draw graphs with arbitrary node sizes. We present two graph drawing software realisations that we wrote in order to validate the algorithms presented in the thesis. They can be linked to combinatorial structure generation programs in order to form integrated systems. We also investigate their use for the visualisation of large data structures
44
Orantin, Nicolas. "Du développement topologique des modèles de matrices à la théorie des cordes topologiques : combinatoire de surfaces par la géométrie algébrique." Phd thesis, Université Pierre et Marie Curie - Paris VI, 2007. http://tel.archives-ouvertes.fr/tel-00173162.
Анотація:
Le modèle à deux matrices a été introduit pour étudier le modèle d'Ising sur surface aléatoire. Depuis, le lien entre les modèles de matrices et la combinatoire de surfaces discrétisées s'est beaucoup développé Cette thèse a pour propos d'approfondir ces liens et de les étendre au delà des modèles de matrices en suivant l'évolution de mes travaux de recherche. Tout d'abord, je m'attache à définir rigoureusement le modèle à deux matrices hermitiennes formel donnant accès aux fonctions génératrices de surfaces discrétisées portant une structure de spin. Je montre alors comment calculer, par des méthodes de g'eométrie algébrique, tous les termes du développement topologique des observables comme formes différentielles définies sur une courbe algébrique associée au modèle: la courbe spectrale. Dans un second temps, je montre comment, imitant la construction du modèle à deux matrices, on peut définir de telles formes différentielles sur n'importe quelle courbe algébrique possédant de nombreuses propriétés d'invariance sous les déformations de la courbe algébrique considérée. En particulier, on peut montrer que si cette courbe est la courbe spectrale d'un modèle de matrices, ces invariants reconstituent les termes des développements topologiques des observables du modèle. Finalement,je montre que pour un choix particulier des paramètres, ces objets peuvent être rendus invariants modulaires et sont solutions des équations d'anomalie holomorphe de la théorie de Kodaira-Spencer donnant un nouvel élément vers la preuve de la conjecture de Dijkgraaf-Vafa.
45
Jartoux, Bruno. "On combinatorial approximation algorithms in geometry." Thesis, Paris Est, 2018. http://www.theses.fr/2018PESC1078/document.
Анотація:
L'analyse des techniques d'approximation est centrale en géométrie algorithmique, pour des raisons pratiques comme théoriques. Dans cette thèse nous traitons de l'échantillonnage des structures géométriques et des algorithmes d'approximation géométriques en optimisation combinatoire. La première partie est consacrée à la combinatoire des hypergraphes. Nous débutons par les problèmes de packing, dont des extensions d'un lemme de Haussler, particulièrement le lemme dit de Shallow packing, pour lequel nous donnons aussi un minorant optimal, conjecturé mais pas établi dans les travaux antérieurs. Puis nous appliquons ledit lemme, avec la méthode de partition polynomiale récemment introduite, à l'étude d'un analogue combinatoire des régions de Macbeath de la géométrie convexe : les M-réseaux, pour lesquels nous unifions les résultats d'existence et majorations existants, et donnons aussi quelques minorants. Nous illustrons leur relation aux epsilon-réseaux, structures incontournables en géométrie combinatoire et algorithmique, notamment en observant que les majorants de Chan et al. (SODA 2012) ou Varadarajan (STOC 2010) pour les epsilon-réseaux (uniformes) découlent directement de nos résultats sur les M-réseaux. La deuxième partie traite des techniques de recherche locale appliquées aux restrictions géométriques de problèmes classiques d'optimisation combinatoire. En dix ans, ces techniques ont produit les premiers schémas d'approximation en temps polynomial pour divers problèmes tels que celui de calculer un plus petit ensemble intersectant pour un ensemble de disques donnés en entrée parmi un ensemble de points donnés en entrée. En fait, il a été montré que pour de nombreux tels problèmes, la recherche locale de rayon Θ (1/epsilon²) donne une (1 + epsilon)-approximation en temps n^{O(1/epsilon²)}. Savoir si l'exposant de n pouvait être ramené à o (1/epsilon²) demeurait une question ouverte. Nous répondons par la négative : la garantie d'approximation de la recherche locale n'est améliorable pour aucun desdits problèmesThe analysis of approximation techniques is a key topic in computational geometry, both for practical and theoretical reasons. In this thesis we discuss sampling tools for geometric structures and geometric approximation algorithms in combinatorial optimization. Part I focuses on the combinatorics of geometric set systems. We start by discussing packing problems in set systems, including extensions of a lemma of Haussler, mainly the so-called shallow packing lemma. For said lemma we also give an optimal lower bound that had been conjectured but not established in previous work on the topic. Then we use this lemma, together with the recently introduced polynomial partitioning technique, to study a combinatorial analogue of the Macbeath regions from convex geometry: Mnets, for which we unify previous existence results and upper bounds, and also give some lower bounds. We highlight their connection with epsilon-nets, staples of computational and combinatorial geometry, for example by observing that the unweighted epsilon-net bound of Chan et al. (SODA 2012) or Varadarajan (STOC 2010) follows directly from our results on Mnets. Part II deals with local-search techniques applied to geometric restrictions of classical combinatorial optimization problems. Over the last ten years such techniques have produced the first polynomial-time approximation schemes for various problems, such as that of computing a minimum-sized hitting set for a collection of input disks from a set of input points. In fact, it was shown that for many of these problems, local search with radius Θ(1/epsilon²) gives a (1 + epsilon)-approximation with running time n^{O(1/epsilon²)}. However the question of whether the exponent of n could be decreased to o(1/epsilon²) was left open. We answer it in the negative: the approximation guarantee of local search cannot be improved for any of these problems. The key ingredient is a new lower bound on locally expanding planar graphs, which is then used to show the impossibility results
46
Bus, Norbert. "The use of geometric structures in graphics and optimization." Thesis, Paris Est, 2015. http://www.theses.fr/2015PESC1117/document.
Анотація:
Les données du monde réel ont manifestement une composante géométrique importante et suggère les patterns géométriques signifiants. Les méthodes qui utilisent la nature géométrique des données sont activement développés dans plusieurs domaines scientifiques, comme, par exemple, la géométrie algorithmique, la géométrie discrète, la synthèse d'images, la vision par ordinateur. Dans le travail présent, nous utilisons les structures géométriques afin de modéliser des algorithmes efficaces pour deux domaines, celui de synthèse d'images et de l'optimisation combinatoire. Dans la première partie il s'agit de la structure de données géométriques, appelé une décomposition bien-séparée, et son application pour un des problèmes les plus difficiles dans la synthèse d'images, un efficace rendu photo-réalistique. Une solution consiste à appliquer toute une famille de méthodes de many-lights qui fait une approximation d'illumination globale par calcule individuelle d'illumination avec un grand nombre de VPLs (virtual point light) répartis sur les surfaces. L'application individuelle de chacun VPL résulte dans un grand nombre des calculs. Une des stratégies de la réussite pour réduire les computations est de faire les clusteurs considérés qui sont consideré comme une seul émetteur. Nous utilisons la décomposition bien-séparée de points comme le fondement de la structure des données susceptible de procéder à un calcul préliminaire et de conserver d'une façon compacte un grand nombre des clusterisations individuels potentiels ce qui montre que la clusterisation des VPL plus correspondante peut être extraite de cette structure de données d'une manière efficace. Nous montrons qu'au lieu de regroupper les points et/ou VPL indépendemment il vaut mieux produire les clusteurs sur l'espace de produit du nombre des points à nuancer et un groupe de VPL à la base de l'illumination des paires induite. En plus, nous proposons une technique adaptive afin d'échantillonner pour réduire le nombre des demandes de vérifications de visibilité pour chaque clusteur de l'espace de produit. Notre méthode consiste à détenir chaque émetteur qui peut être rapproché par VPL, matériaux spéculaire et à performer les méthodes précédents réconnus les meilleurs jusqu'au présent. La deuxième partie est consacrée au développement de nouveaux algorithmes d'approximation pour un problème fondamental de NP complet dans la géométrie algorithmique, précisément le problème du hitting set, avec une précision pour le cas d'un groupe de points et d'un groupe de disques, nous souhaiterons calculer les plus petits nombre du points qui touche tous les disques. Il arrive que les algorithmes efficaces à détecter le hitting set repose sur une structure géométrique clée, appelée epsilon-net. Nous donnons un algorithme utilisant uniquement les triangulisations de Delaunay pour construire les epsilon-nets de taille 13.4/epsilon. Nous donnons une implémentation pratique de la technique à calculer les hitting sets dans le temps quasi-linéaire en utilisant des epsilon-nets de petites tailles. Nos résultats aboutissent à une approximation de 13.4 pour le problème de hitting set par un algorithme qui fonctionne même pour les grands ensembles de données. Pour les ensembles de taille plus petite, nous proposons une implémentation de la technique de recherche locale avec une approximation bornes supérieures, avec le résultat obtenu d'approximation de (8 + epsilon) dans le temps O(n^{2.34})Real-world data has a large geometric component, showing significant geometric patterns. How to use the geometric nature of data to design efficient methods has became a very important topic in several scientific fields, e.g., computational geometry, discrete geometry, computer graphics, computer vision. In this thesis we use geometric structures to design efficient algorithms for problems in two domains, computer graphics and combinatorial optimization. Part I focuses on a geometric data structure called well-separated pair decomposition and its usage for one of the most challenging problems in computer graphics, namely efficient photo-realistic rendering. One solution is the family of many-lights methods that approximate global illumination by individually computing illumination from a large number of virtual point lights (VPLs) placed on surfaces. Considering each VPL individually results in a vast number of calculations. One successful strategy the reduce computations is to group the VPLs into a small number of clusters that are treated as individual lights with respect to each point to be shaded. We use the well-separated pair decomposition of points as a basis for a data structure for pre-computing and compactly storing a set of view independent candidate VPL clusterings showing that a suitable clustering of the VPLs can be efficiently extracted from this data structure. We show that instead of clustering points and/or VPLs independently what is required is to cluster the product-space of the set of points to be shaded and the set of VPLs based on the induced pairwise illumination. Additionally we propose an adaptive sampling technique to reduce the number of visibility queries for each product-space cluster. Our method handles any light source that can be approximated with virtual point lights (VPLs), highly glossy materials and outperforms previous state-of-the-art methods. Part II focuses on developing new approximation algorithms for a fundamental NP-complete problem in computational geometry, namely the minimum hitting set problem with particular focus on the case where given a set of points and a set of disks, we wish to compute the minimum-sized subset of the points that hits all disks. It turns out that efficient algorithms for geometric hitting set rely on a key geometric structure, called epsilon-net. We give an algorithm that uses only Delaunay triangulations to construct epsilon-nets of size 13.4/epsilon and we provide a practical implementation of a technique to calculate hitting sets in near-linear time using small sized epsilon-nets. Our results yield a 13.4 approximation for the hitting set problem with an algorithm that runs efficiently even on large data sets. For smaller datasets, we present an implementation of the local search technique along with tight approximation bounds for its approximation factor, yielding an (8 + epsilon)-approximation algorithm with running time O(n^{2.34})
47
Bellet, Thomas. "Transformations de graphes pour la modélisation géométrique à base topologique." Thesis, Poitiers, 2012. http://www.theses.fr/2012POIT2261/document.
Анотація:
De nombreux domaines comme le jeu vidéo, l’architecture, l’ingénierie ou l’archéologie font désormais appel à la modélisation géométrique. Les objets à représenter sont de natures diverses, et leurs opérations de manipulation sont spécifiques. Ainsi, les modeleurs sont nombreux car tous spécialisés à leur domaine d’application. Or ils sont à la fois chers à développer, souvent peu robustes, et difficilement extensibles. Nous avons proposé dans la thèse l’approche alternative suivante :– fournir un langage dédié à la modélisation qui permet de définir les opérations quelque soit le domaine d’application ; dans ce langage, les objets sont représentés avec le modèle topologique des cartes généralisées, dont nous avons étendu la définition aux plongements ; les opérations sont elles définies par des règles de transformation de graphes, issues de la théorie des catégorie ;– garantir les opérations définies dans le langage à l’aide de conditions de cohérence ; une opération dont la définition vérifie ces conditions ne produit pas d’anomalie ;– développer un noyau de modeleur générique qui interprète ce langage ; les opérations définies sont directement appliquées dans le modeleur, sans implantation dans un langage de programmation ; l’outil assure également la vérification automatique des conditions du langage pour prévenir un utilisateur lorsqu’il propose une opération incohérente.Le langage et le modeleur développés se sont révélés performants à la fois en termes de temps de développement et en termes de temps machine. L’implantation d’une nouvelle opération par une règle ne prend que quelques minutes à l’aide des conditions du langage, au contraire de l’approche classiGeometric modeling is now involved in many fields such as: video games, architecture, engineering and archaeology. The represented objects are very different from one field to another, and so are their modeling operations. Furthermore, many specific types of modeling software are designed for high programing costs, but with a relatively low rate of effectiveness.The following is an alternative approach:– we have conceived a dedicated language for geometric modeling that will allow us to define any operation of any field; objects in this language are defined with the topological model of generalized maps, this definition has been extended to the embedding informations; here the operations are defined as graph transformation rules which originate from the category theory;– we have ensured operation definitions with consistency conditions; these operations that satisfy those conditions do not generate anomalies; – we have designed generic modeling software to serve as an interpreter of this language; the operation definitions are directly applied without the need for more programing; the software also automatically checks the language conditions and warns the user if he designs a non-consistent operation.The provided language and software prove to be efficient, and all for a low programing cost. Designing a new operation takes only minutes thanks to the language conditions, as opposed to hours of programming and debugging with the past approach
48
Damiand, Guillaume. "Contributions aux Cartes Combinatoires et Cartes Généralisées : Simplification, Modèles, Invariants Topologiques et Applications." Habilitation à diriger des recherches, INSA de Lyon, 2010. http://tel.archives-ouvertes.fr/tel-00538456.
Анотація:
Ce mémoire résume nos principales contributions aux cartes combinatoires et cartes généralisées, deux modèles combinatoires représentant des subdivisions d'objets en cellules (sommets, arêtes, faces, volumes, ...). Ces modèles possèdent plusieurs avantages qui justifient leurs utilisations dans plusieurs domaines comme la modélisation géométrique et l'analyse d'images : ils sont définis en dimension quelconque à partir d'un seul type d'élément ; ils décrivent les cellules de la subdivision ainsi que toutes les relations d'adjacence et d'incidence entre ces cellules ; des contraintes de cohérence permettent de tester la validité des objets manipulés ; ils autorisent la mise en oeuvre d'algorithmes locaux, qui sont simples et efficaces en complexité. Nos travaux portent sur l'étude de ces modèles et sur la définition d'algorithmes. Nous avons tout d'abord défini quatre opérations de base : la suppression, la contraction, l'insertion et l'éclatement. Ces opérations sont les briques de base permettant de modifier un objet et peuvent être vues comme une généralisation des opérateurs d'Euler. Elles sont définies de manière générale en dimension quelconque. Il est ensuite possible d'ajouter des contraintes supplémentaires selon les applications et selon les propriétés spécifiques à conserver. Ces opérations sont au coeur de nos travaux. Nous les avons utilisées pour définir la carte topologique 2D et 3D, un modèle décrivant la partition d'une image en régions, puis pour définir des opérations de fusion et de découpe sur les cartes topologiques. Nous avons également défini les pyramides généralisées qui peuvent être vues comme des piles de cartes, chacune étant obtenue par simplification de la carte précédente. Enfin, nous avons proposé des algorithmes de calcul d'invariants topologiques : la caractéristique d'Euler-Poincaré, le schéma polygonal canonique, les nombres de Betti et les groupes d'homologies. Dans ces quatre cas, nous avons à nouveau utilisé les opérations de base afin de proposer des méthodes de mise à jour locales, ou pour simplifier la carte dans l'objectif d'accélérer les calculs du fait de la diminution du nombre de cellules. Nous avons utilisé ces travaux théoriques dans différentes applications. En modélisation géométrique, nous présentons le modeleur Moka qui est un modeleur géométrique à base topologique. Différentes applications se sont basées sur ce modeleur et nous présentons plus en détail une méthode de reconstruction automatique de bâtiments 3D à partir de plans numériques 2D. En traitement d'images, nous avons utilisé les cartes topologiques afin de proposer des algorithmes de segmentation d'images 2D et 3D pouvant intégrer un contrôle topologique.
49
Cuneo, Rémi. "Généralisation d'une méthode de petites simplifications due à Mikhaïl Gromov et Yann Ollivier en géométrie des groupes." Thesis, Aix-Marseille 1, 2011. http://www.theses.fr/2011AIX10026/document.
Анотація:
Dans un article publié en 2003, M.Gromov propose une reformulation de la théorie des petites simplifications en géométrie des groupes. Dans cette version, un graphe fini définit une présentation finie de groupe; les générateurs du groupe sont les étiquettes du graphe; les relateurs sont les mots associés aux cycles; les morceaux, mots "courts " qui permettent les petites simplifications dans un groupe, sont des mots qui étiquettent deux chemins distincts du graphe. Cette thèse prend pour point de départ une brève description de cette théorie publiée par Y. Ollivier en 2006. Le concept de groupe de présentation finie à "petites simplifications", développé par R. Lyndon, M. Greendlinger et autres dans les années 60 et 70, est précurseur des groupes hyperboliques de M.Gromov à la fin des années 80, pour lesquels les propriétés combinatoires de la présentation entraînent des propriétés algébriques du groupe. Dans notre travail, nous fondons de manière rigoureuse la théorie des petites simplifications du point de vue des graphes, et développons le concept de base de "mégatuiles", utilisé implicitement par Y. Ollivier dans son article. Nous étendons ses résultats aux cas non-hyperboliques et non-métriques (par exemple$C(4)-T(4)$). Ce point de vue permet une nouvelle preuve, plus naturelle, de la résolubilité des problèmes du mot et de conjugaison pour les présentations des groupes des entrelacs alternés premiers. Nous prolongeons également les résultats d'un théorème de M. Greendlinger au cas non-métrique, répondant ainsi à une question d'I. KapovichIn a paper published in 2003, M.Gromov proposes a rewording of the small cancellation theory in geometric group theory. In this version, a finite graph defines a finitely presented group; generators of the group are the labels of the graph; relators are the words associated with cycles; pieces, "short" words which allow small cancellations in a group, are words which label two distinct paths in the graph.Our thesis relies on a brief description of this theory published in2006 by Y.Ollivier. The concept of finitely presented "small cancellation" group, developed by R.Lyndon, M.Greendlinger and others in the 60's and 70's, is a precursor of Gromovword-hyperbolic groups in the late of the 80's, for which combinatorial properties of the presentation imply algebraic properties of the group. In our work, we build a rigorous small cancellation theory in terms of graphs, and develop the basic concept of "megatiles", implicitly used by Y. Ollivier in his article. We extend his results to non-hyperbolic and non-metric cases (eg. $C(4)-T(4)$). This point of view allows a new proof, more natural, of thesolvability of word and conjugacy problems for presentations of prime alternating link groups. We also extend the results of a M.Greendlinger theorem to thenon-metric case, in response to a question of I. Kapovich
50
Gagneur, Julien. "Algorithms for decomposition of bio-molecular networks." Châtenay-Malabry, Ecole centrale de Paris, 2004. http://www.theses.fr/2004ECAP0943.
Анотація:
Les réseaux d'interactions bio-moléculairesà l'échelle de la cellule sont complexes. Définir des abstractions sur ces réseaux permet d'en avoir à la fois une meilleure vue d'ensemble et une meilleure compréhension. C'est ce que permettent les décompositions de réseaux. Cette thèse propose des algorithmes de décomposition pour deux types de réseaux: les réseaux métaboliques et les réseaux d'interaction de protéines. Ces algorithmes, de complexité polynomiale, sont rapides et applicables à l'échelle de la cellule comme cela est illustré sur Escherichia coli pour les réseaux métaboliques et sur la levure pour les réseaux d'interactions de protéines. Pour les décompositions de réseaux métaboliques, un cadre basé sur la notion d'encapsulation est introduit. Il fournit une méthode générale pour définir des sous-sytèmes de manière hiérarchique et rend possible une approche de type "diviser pour régner" au calcul des modes de flux élémentaires. Pour les réseaux d'interactions de protéines, des abstractions appelées modules sont introduites menant aussi à une décomposition hiérarchique. Cette dernière décrit les règles logiques suivies par les protéines lorsqu'elles s'assemblent et forment des complexes. Ces travaux sont supportés par des implémentations des algorithmes présentés et par leurs applications à l'analyse de réseaux réels.