To see the other types of publications on this topic, follow the link: Algorithmique et combinatoire des monoïdes.
Dissertations / Theses on the topic 'Algorithmique et combinatoire des monoïdes'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 43 dissertations / theses for your research on the topic 'Algorithmique et combinatoire des monoïdes.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Charles, Balthazar. "Combinatorics and computations : Cartan matrices of monoids & minimal elements of Shi arrangements." Electronic Thesis or Diss., université Paris-Saclay, 2023. http://www.theses.fr/2023UPASG063.
Full textAbstract:
Cette thèse présente le résultat de recherches sur deux thèmes combinatoires distincts: le calcul effectif des matrices de Cartan en théorie des représentations des monoïdes et l'exploration des propriétés des éléments minimaux dans les arrangements de Shi des groupes de Coxeter. Bien que disparates, ces deux domaines de recherche partagent l'utilisation de méthodes combinatoires et d'exploration informatique, soit en tant que fin en soi pour le premier domaine, soit comme aide à la recherche pour le second. Dans la première partie de la thèse, nous développons des méthodes pour le calcul effectif des tables de caractères et des matrices de Cartan dans la théorie des représentations des monoïdes. À cette fin, nous présentons un algorithme basé sur nos résultats pour le calcul efficace des points fixes sous une action similaire à une conjugaison, dans le but de mettre en œuvre la formule de [Thiéry '12] pour la matrice de Cartan. Après une introduction largement auto-contenue aux notions nécessaires, nous présentons nos résultats sur le comptage des points fixes, ainsi qu'une nouvelle formule pour la table de caractères des monoïdes finis. Nous évaluons les performances des algorithmes résultants en termes de temps d'exécution et d'utilisation mémoire. Nous observons qu'ils sont plus efficaces par plusieurs ordres de grandeur que les algorithmes non spécialisés pour les monoïdes. Nous espérons que l'implémentation (publique) résultant de ces travaux contribuera à la communauté des représentations des monoïdes en permettant des calculs auparavant difficiles. La deuxième partie de la thèse se concentre sur les propriétés des éléments minimaux dans les arrangements de Shi. Les arrangements de Shi ont été introduits dans [Shi '87] et sont l'objet de la Conjecture 2 dans [Dyer, Hohlweg '14]. Initialement motivés par cette conjecture, après une introduction aux notions nécessaires, nous présentons deux résultats. Premièrement, une démonstration directe dans le cas des groupes de rang 3. Deuxièmement, dans le cas particulier des groupes de Weyl, nous donnons une description des éléments minimaux des régions de Shi en étendant une bijection issue de [Athanasiadis, Linusson '99] et [Armstrong, Reiner, Rhoades '15] entre les fonctions de parking et les régions de Shi permettant d'effectuer le calcul pratique des éléments minimaux. Comme application, à partir des propriétés de ce calcul, nous donnons une démonstration de la conjecture pour les groupes de Weyl indépendante de leur classification. Ces résultats révèlent une interaction intrigante entre les partitions non-croisées et non-embrassées dans le cas des groupes de Weyl classiques<br>This thesis presents an investigation into two distinct combinatorial subjects: the effective computation of Cartan matrices in monoid representation theory and the exploration of properties of minimal elements in Shi arrangements of Coxeter groups. Although disparate, both of these research focuses share a commonality in the utilization of combinatorial methods and computer exploration either as an end in itself for the former or as a help to research for the latter. In the first part of the dissertation, we develop methods for the effective computation of character tables and Cartan matrices in monoid representation theory. To this end, we present an algorithm based on our results for the efficient computations of fixed points under a conjugacy-like action, with the goal to implement Thiéry's formula for the Cartan matrix from [Thiéry '12]. After a largely self-contained introduction to the necessary background, we present our results for fixed-point counting, as well as a new formula for the character table of finite monoids. We evaluate the performance of the resulting algorithms in terms of execution time and memory usage and find that they are more efficient than algorithms not specialized for monoids by orders of magnitude. We hope that the resulting (public) implementation will contribute to the monoid representation community by allowing previously impractical computations. The second part of the thesis focuses on the properties of minimal elements in Shi arrangements. The Shi arrangements were introduced in [Shi '87] and are the object of Conjecture 2 from [Dyer, Hohlweg '14]. Originally motivated by this conjecture, we present two results. Firstly, a direct proof in the case of rank 3 groups. Secondly, in the special case of Weyl groups, we give a description of the minimal elements of the Shi regions by extending a bijection from [Athanasiadis, Linusson '99] and [Armstrong, Reiner, Rhoades '15] between parking functions and Shi regions. This allows for the effective computation of the minimal elements. From the properties of this computation, we provide a type-free proof of the conjecture in Weyl groups as an application. These results reveal an intriguing interplay between the non-nesting and non-crossing worlds in the case of classical Weyl groups
2
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.
Full textAbstract:
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 cristallographiques<br>Algebraic 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
3
Lévy, Bruno. "Topologie Algorithmique : combinatoire et Plongement." Vandoeuvre-les-Nancy, INPL, 1999. http://www.theses.fr/1999INPL094N.
Full textAbstract:
La modélisation 3D s’appuie sur deux principales familles de méthodes. L’une de ces familles de méthodes, appelée souvent courbes et surfaces, se fonde sur une représentation des objets à modéliser par des fonctions (le plus souvent polynomiales). L’autre famille de représentations consiste à discrétiser les objets en cellules (sommets, segments, polygones, polyèdres. . ). Nous étudions ici les problèmes liés à ce dernier type de représentation discrète des objets, ainsi que ses relations avec les « courbes et surfaces ». En utilisant le formalisme offert par la Topologie, une branche moderne des mathématiques, nous allons étudier les problèmes suivants : Définir des structures de données efficaces pour représenter la décomposition des objets en éléments discretsGénérer et éditer interactivement des objets, de manière à respecter des données ainsi que des contraintes globales concernant la forme des objets. - Constuire une paramétrisation sous contraintes d’une surface triangulée, afin de pouvoir facilement lui associer des valeurs. Le premier point sera traité en utilisant certains résultats de topologie combinatoire, et les deux derniers seront étudiés en termes d’homéomorphisme et de transformation continue. Nous présenterons également plusieurs applications de ces méthodes, permettant de résoudre des problèmes de modélisation en géologie numérique. Par exemple, nous montrerons comment modéliser de manière précise les variations de porosité de la roche à l’intérieur d’un réservoir naturel. Des applications possibles de nos méthodes à l’image de synthèse et au placage de textures seront également évoquées
4
Gély, Alain. "Algorithmique combinatoire : cliques, bicliques et systèmes implicatifs." Clermont-Ferrand 2, 2005. http://www.theses.fr/2005CLF22622.
Full textAbstract:
Cette thèse traite de l'algorithmique d'énumération. Après avoir présenté les concepts particuliers des algorithmes d'énumération, nous nous intéressons plus particuliérement à deux problèmes, l'énumération des cliques maximales et l'énumération des bicliques maximales d'un graphe. Pour ce dernier problème, trois variantes seront traitées : énumération des bicliques maximales induites, non induites et pour le cas particulier des graphes biparti. Cette thèse propose des liens entre les algorithmes existants pour ces problèmes. On s'intéresse à l'énumération des éléments d'une base minimun d'implications. Comme il n'existe pas à l'heure actuelle d'algorithme d'énumération polynomial pour ce problème, les approches présentées ici utilisent un autre angle d'approche : trouver une base minimun plus petite, ou plus rapide à calculer, permettant de reconstruire la base minimum initiale en temps polynomial. Dans ce but, deux résultats sont présentés : les éléments clones d'une relation et la famille des systèmes de fermeture partageant une certaine partie d'une base minimun
5
Durand, Marianne. "Combinatoire analytique et algorithmique des ensembles de données." Phd thesis, Ecole Polytechnique X, 2004. http://pastel.archives-ouvertes.fr/pastel-00000810.
Full textAbstract:
Cette thèse traite d'algorithmique des ensembles de données en adoptant le point de vue de la combinatoire analytique. On traite ici de trois problèmes qui illustrent cette approche: les listes à sauts associées à de l'analyse asymptotique bivariée, le hachage à essai aléatoire avec pagination et le comptage probabiliste. Les listes à sauts sont une structure de données intermédiaire entre les skiplists et les arbres binaires de recherche. L'étude de cette structure a donné lieu à un problème d'asymptotique bivariée avec coalescence de singularités. Le hachage avec essai aléatoire est un algorithme qui gère les collisions d'une table de hachage. Dans le contexte étudié qui est celui de la pagination, on obtient la moyenne, ainsi que tous les moments successifs du coût de construction. Les algorithmes de comptage probabilistes originaux Loglog et Super Loglog permettent d'estimer le cardinal d'un ensemble en utilisant un kilooctet de mémoire avec une précision d'environ 3%.
6
Pierrot, Adeline. "Combinatoire et algorithmique dans les classes de permutations." Paris 7, 2013. http://www.theses.fr/2013PA077056.
Full textAbstract:
Cette thèse porte sur l'étude des classes de permutations à motifs exclus. Une analyse combinatoire des permutations via leur décomposition par substitution permet d'obtenir des résultats algorithmiques. La première partie de la thèse étudie la structure des classes de permutations. Plus précisément on donne un algorithme pour calculer une spécification combinatoire pour une classe de permutations données par sa base de motifs exclus. La spécification est obtenue si et seulement si la classe contient un nombre fini de permutations simples, cette condition étant testée par l'algorithme lui-même. Cet algorithme puise sa source dans les travaux de Albert et Atkinson établissant qu'une classe ayant un nombre fini de permutations simples a une base finie et une série génératrice algébrique. Les méthodes développées utilisent la théorie des langages et des automates, les ensembles partiellement ordonnés, l'introduction de motifs obligatoires. La seconde partie de la thèse donne un algorithme polynomial décidant si une permutation donnée en entrée est triable par deux piles connectées en série. L'existence d'un algorithme polynomial résolvant cette question est un problème longtemps resté ouvert, que l'on clôt dans cette thèse en introduisant une nouvelle notion, le tri par sas, en utilisant un codage des procédures de tri par un bi-coloriage du diagramme des permutations. Puis on résout le problème général en montrant qu'une procédure de tri général correspond à plusieurs étapes de tri par sas<br>This work is dedicated to the study of pattern closed classes of permutations. Algorithmic results are obtained thanks to a combinatorial study of permutation classes through their substitution decomposition. The first part of the thesis focuses on the structure of permutation classes. More precisely, we give an algorithm which derives a combinatorial specification for a permutation class given by its basis of excluded patterns. The specification is obtained if and only if the class contains a finite number of simple permutations, this condition being tested algorithmically. This algorithm takes its root in the theorem of Albert and Atkinson stating that every permutation class containing a finite number of simple permutations has a finite basis and an algebraic generating function, and its developments by Brignall and al. The methods involved make use of languages and automata theory, partially ordered sets and mandatory patterns. The second part of the thesis gives a polynomial algorithm deciding whether a permutation given as input is sortable trough two stacks in series. The existence of a polynomial algorithm answering this question is a problem that stayed open for a long time, which is solved in this thesis by introducing a new notion, the pushall sorting, which is a restriction of the general stack sorting. We first solve the decision problem in the particular case of the pushall sorting, by encoding the sorting procedures through a bicoloring of the diagrams of the permutations. Then we solve the general base by showing that a sorting procedure in the general case corresponds to several steps of pushall sorting which have to be compatible
7
Giroire, Frédéric. "Réseaux, algorithmique et analyse combinatoire de grands ensembles." Paris 6, 2006. http://www.theses.fr/2006PA066530.
Full text
8
Kane, Ladji. "Combinatoire et algorithmique des factorisations tangentes à l'identité." Thesis, Paris 13, 2014. http://www.theses.fr/2014PA132059/document.
Full textAbstract:
La combinatoire a permis de résoudre certains problèmes en Mathématiques, en Physique et en Informatique, en retour celles-ci inspirent des questions nouvelles à la combinatoire. Ce mémoire de thèse intitulé "Combinatoire et algorithme des factorisations tangentes à l'identité" regroupe plusieurs travaux sur la combinatoire des déformations du produit de Shuffle. L'objectif de cette thèse est d'écrire des factorisations dont le terme principal est l'identité à travers l'utilisation d'outils portant principalement sur la combinatoire des mots (ordres, graduation etc.). Dans le cas classique, soit F une algèbre libre. En raison du fait que F est une algèbre enveloppante, on a une factorisation exacte de l'identité de End(F) = F*⨶F comme un produit infini d'exponentielles (End(F) étant muni du produit de Shuffle sur la gauche et de la concaténation sur la droite, une représentation fidèle du produit de convolution). La procédure est la suivante : premièrement on commence avec une base de Poincaré-Birkhoff-Witt, deuxièmement on calcule la famille des formes coordonnées et alors les propriétés (combinatoires) non triviales de ces familles en dualité donne la factorisation. Si on part de l'autre côté, l'écriture pour le même produit ne donne exactement l'identité que sous des conditions très restrictives que nous précisons ici. Dans de nombreux autres cas (déformés), la construction explicite des paires de bases en dualité nécessite une étude combinatoire et algorithmique que nous fournissons dans ce mémoire<br>Combinatorics has solved many problems in Mathematics, Physics and Computer Science, in return these domains inspire new questions to combinatorics. This memoir entitled "Combinatorics and algorithmics of factorization tangent to indentity includes several works on the combinatorial deformations of the shuffle product. The aim of this thesis is to write factorizations wich principal term is the identity through the use of tools relating mainly to combinatorics on the words (orderings, grading etc). In the classical case, let F be the free algebra. Due to the fact that F is an enveloping algebra, one has an exact factorization of the identity of End(F) = F⨶F as an infinite product of exponentials (End(F) being endowed with the shuffle product on the left and the concatenation on the right, a faithful representation of the convolution product) as follows : first on begins with a PBW basis, second one computes the family of coordinate forms and then non-trivial (combinatorial) properties of theses families in duality gives the factorization. Starting from the other side and writing the same product does give exactly identity only under very restrictive conditions that we clarify here. In many other (deformed) cases, the explicit construction of pairs of bases in duality requires combinatorial and algorithmic studies that we provide in this memoir
9
Chamboredon, Jérémy. "Algorithmique des tresses et de l’autodistributivité." Caen, 2011. http://www.theses.fr/2011CAEN2016.
Full textAbstract:
Ce travail porte sur les propriétés algébriques des groupes de tresses d'Artin et des systèmes autodistributifs à gauche, des objets intimement liés. La première partie est une analyse syntaxique de la forme normale de Bressaud pour les tresses. Le principal résultat est une traduction en termes de systèmes de réécriture de l'existence de la forme normale, initialement établie par des méthodes géométriques. La seconde partie est centrée sur la conjecture de plongement pour l'autodistributivité, un des énoncés ouverts principaux du domaine. On discute les multiples approches (y compris calculatoires) pouvant mener à cette conjecture, et on établit des résultats positifs partiels<br>In this work, we investigate algebraic properties for Artin's braid groups and self-distributive systems on the left, two objets which are linked. The first part is a syntactic analysis of Bressaud's normal formal for braids. The principal result is a translation in terms of rewriting systems of the existence of Bressaud's normal form, initially established by geometric methods. The second part deals with the embedding conjecture for self-distributivity, one of the principal open statements of the field. We discuss the various ways (including the computing ones) which could lead to this conjecture, and we establish some partial positive results
10
Lecouvey, Cédric. "Algorithmique et combinatoire des algèbres enveloppantes quantiques de type classique." Caen, 2001. http://www.theses.fr/2001CAEN2012.
Full textAbstract:
Cette thèse utilise la théorie des bases cristallines De Kashiwara pour étudier des problèmes algorithmiques et combinatoires liés aux algèbres quantiques de type B, C et D. Nous obtenons tout d'abord, pour tout poids dominant lambda, un algorithme général de calcul de la base globale d'un Uq (sp2n) module de dimension finie et de plus haut poids lambda. Nous avons de plus une description explicite de la base canonique lorsque lambda est un poids dominant. Nous donnons ensuite une présentation de monoi͏̈des, analogues pour les types B, C et D, au monoi͏̈de plaxique de Lascoux et Schützenberger. Nous décrivons alors les algorithmes d'insertion correspondant à ces monoi͏̈des. Dans le cas du type C, nous démontrons que nos relations plaxiques sont compatibles avec l'algorithme de glissement de Sheats ce qui nous permet d'obtenir un Jeu de Taquin complet pour les types B et C. Finallement, nous obtenons une généralisation de la correspondance de Robinson-Schensted aux autres types classiques qui prend en compte les représentations spinorielles des cas orthogonaux.
11
Albenque, Marie. "Tresses, animaux, cartes : à l'interaction entre combinatoire et probabilité." Paris 7, 2008. http://www.theses.fr/2008PA077178.
Full textAbstract:
Nous nous intéressons dans cette thèse à l'étude de certains objets situés à l'interface entre combinatoire et probabilités. Le premier thème abordé est l'énumération des tresses. Notre contribution principale consiste en une extension de la théorie des empilements de Viennot pour les monoïdes de traces à un cadre plus général incluant notamment les monoïdes de Garside, ce qui conduit entre autres à des résultats d'énumération nouveaux pour les monoïdes de tresses. Le second volet de cette thèse est consacré au lien entre l'énumération d'animaux dirigés et les modèles de gaz à particules dures. La définition de chaînes de Markov cycliques et l'établissement de leur convergence vers les chaînes de Markov ordinaires nous permet de donner une présentation unifiée des résultats d'énumération d'animaux sur de nombreux réseaux et d'accéder ainsi à une meilleure compréhension de la dépendance des résultats d'énumération en la forme de la source. La troisième et dernière partie traite des triangulations et quadrangulations en pile, et plus précisément de leurs comportements limites lorsque le nombre de sommets tend vers l'infini. Les contributions principales sont les convergences locales et de Gromov-Hausdorff ainsi que l'asymptotique de la loi des degrés pour les cartes sous la loi uniforme et la convergence comme espace métrique sous la loi historique. Ces résultats reposent sur des outils combinatoires et probabilistes variés : bijection entre arbres et cartes, convergence vers l'arbre continu d'Aldous, étude probabiliste fine du comportement asymptotique de certaines fonctionnelles d'arbres, processus de fragmentation, modèle d'urnes aléatoires,. .<br>We study in this work some objects lying on the boundary between combinatorics and probability. The first part deals with the enumeration of positive braids. Our most significant contribution here is an extension of Viennot's heaps of pieces theory to a wider frame which includes in particular Garside monoids, this leads to some new enumeration results for braid monoids. The second section is devoted to the link between enumeration of directed animals and hard particle gas models. The definition of cyclic Markov chains as well as some results about their convergence towards ordinary Markov chains enable us to give a unified presentation of enumeration of animals on various lattices and hence to provide a better understanding about the reliance between enumeration results and the form of the source. The third and last part deals with the stack triangulations and quadrangulations, and more precisely with their limiting behaviors when the number of vertices grows to infinity. The main contribution here are the local and Gromov-Hausdorff convergences and the asymptotic of the degree distribution for the maps under the uniform law and the convergence as metric space under the historical distribution. These results rely on numerous combinatorial and probabilistic tools: bijection between trees and maps, convergence towards Aldous' continuum random tree, subtle probabilistic study of some trees properties, fragmentation process, random urns model
12
Benachi, Saad. "Étude algorithmique des structures algébriques libres ou partiellement commutatives et mesure probabiliste du parallélisme." Nancy 1, 1991. http://www.theses.fr/1991NAN10383.
Full textAbstract:
Le cadre général du présent travail étant les ensembles connus par générateurs et relations. Dans les deux premiers chapitres de cette thèse, on s'est intéressé aux solutions algorithmiques de certains problèmes dans les structures algébriques du type groupe ou monoïde, libre ou partiellement commutatif. Cette étude a été couronnée par la conception du logiciel décidé possédant les fonctionnalités suivantes: 1) dans les cas des groupes à génération fini, il permet de résoudre les problèmes de: appartenance: un élément d'un groupe donne est-il membre d'un sous-groupe (le groupe et le sous-groupe sont connus par leurs générateurs); normalité: un sous-groupe d'un groupe donne possède-t-il une certaine propriété qui permet de le distinguer des autres sous-groupes. 2) il construit l'automate qui reconnait des parties de certains monoïdes partiellement commutatifs libres. Pour le cas des structures algébriques partiellement commutatifs, une extension au cas des groupes libres partiellement commutatifs est envisageable moyennant la résolution de deux problèmes annexes. L'utilisation des transducers finis pour la reconnaissabilité dans les monoïdes partiellement commutatifs libres a été démontrée pour un cas particulier. Dans le chapitre 3 sont exposes les différents algorithmes pour le calcul des éléments de la classe de commutation d'un mot et ceux de la génération uniforme des mots de Motzkin. Dans le chapitre 4, on s'est intéressé à une mesure probabiliste du parallélisme
13
Germain, Christian. "Etude algébrique, combinatoire et algorithmique de certaines structures non associatives (magmas, arbres, parenthésages)." Dijon, 1996. http://www.theses.fr/1996DIJOS018.
Full textAbstract:
Dans des structures non associatives du type arbres binaires, parenthésages, magmas binaires, on étudie un certain nombre de transformations définies par des règles de réécriture, d'un point de vue combinatoire (caractérisation, dénombrements), d'un point de vue algébrique (structure d'ordre engendrée, métrique) et d'un point de vue algorithmique (calcul effectif de certains objets et de la métrique). Dans une certaine famille de magmas binaires dits exponentiatifs, on aborde des problèmes du mot. Enfin on propose deux modelés permettant de résoudre rationnellement de façon virtuelle des systèmes linéaires de séries formelles définies dans un cadre non associatif ; l'un de ces modèles procède par plongement dans un magma pseudo-associatif
14
Virmaux, Aladin. "Théorie des représentations combinatoire de tours de monoïdes : Application à la catégorification et aux fonctions de parking." Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLS138/document.
Full textAbstract:
Cette thèse se situe en combinatoire algébrique, et plus particulièrement en théorie combinatoire des représentations linéaires des monoïdes finis.Rappelons qu'un monoïde est un ensemble fini M muni d'une multiplication et d'un élément neutre, et qu'une représentation de M est un morphisme de M dans le monoïde des matrices $M_n(ck)$ où $ck$ est un corps, typiquement $ck =CC$. Les résultats des dernières décennies donnent un contrôle assez fin sur les représentations des monoïdes, permettant souvent de se ramener à de la théorie des représentations des groupes et de la combinatoire sur des préordres.En 1996, Krob et Thibon ont montré que l'induction et la restriction des représentations irréductibles et projectives de la tour des $0$-algèbres de Hecke $H_n(0)$ permet de munir l'ensemble des caractères d'une structure d'algèbre de Hopf, qui est isomorphe a l'algèbre de Hopf $ncsf$ des fonctions symétriques non commutatives. Cela donne une emph{catégorification} de$ncsf$, c'est-à-dire une interprétation de celle-ci en terme de théorie des représentations. Ils prolongent ainsi un résultat dû à Frobenius établissant un lien entre l'anneau des caractères de la tour des groupes symétriques et lesfonctions symétriques. Un problème naturel depuis lors est d'essayer de catégorifier d'autres algèbres de Hopf -- par exemple l'algèbre $pbt$ desarbres binaires de Loday et Ronco -- par des tours d'algèbres.Deviner une telle tour d'algèbres est difficile en général. Dans le cadre de cemanuscrit on restreint le champ de recherche aux tours de monoïdes, afin de mieux contrôler leurs représentations. C'est naturel car ce cadre couvre enfait les deux exemples fondamentaux ci-dessus, tandis qu'il est impossible decatégorifier $ncsf$ avec seulement une tour de groupes.Nous commençons par donner quelques résultats sur les représentations des toursde monoïdes. Ensuite, nous nous intéressons à la catégorification par destours de semi-treillis, et en particulier de quotients du permutoèdre. Avecceux-ci, nous catégorifions la structure de cogèbre de $fqsym$ sur la base$gbasis$ et celle d'algèbre de $fqsym$ sur la base $fbasis$. Cela ne permetcependant pas de catégorifier simultanément toute la structure de Hopf de ces algèbres. Dans un second temps, nous menons une recherche exhaustive des catégorifications de $pbt$. Nous montrons que, sous des hypothèses naturelles,il n'existe pas de catégorification de $pbt$ par une tour de monoïdesapériodiques. Enfin, nous démontrons que, dans un certain sens, la tour des monoïdes $0$-Hecke est la tour de monoïdes la plus simple catégorifiant $ncsf$.La seconde partie porte sur les fonctions de parking, par application des résultats de la première partie. D'une part, nous étudions la théorie des représentations de la tour des fonctions de parking croissantes. D'autre part,dans un travail commun avec Jean-Baptiste Priez nous reprenons une généralisation des fonctions de parking due à Stanley et Pitman. Afin d'obtenir des formules d'énumérations, nous utilisons une variante -- plus efficace dansle cas présent -- de la théorie des espèces. Nous donnons une action de$H_n(0)$ (et non du groupe symétrique) sur les fonctions de parking généralisées, et utilisons le théorème de catégorification de Krob et Thibon,pour relever dans les fonctions symétriques non commutatives le caractère de cette action<br>This thesis is focused on combinatorical representation theory of finitemonoids within the field of algebraic combinatorics.A monoid $M$ is a finite set endowed with a multiplication and a neutralelement. A representation of $M$ is a morphism from $M$ into the monoid ofmatrices $M_n(ck)$ where $ck$ is a field; in this work it will typically bereferred to as $ck = CC$.The results obtained in the last decades allows us to use representation theoryof groups, and combinatorics on preorders in order to explore representationtheory of finite monoides.In 1996, Krob and Thibon proved that the induction and restriction rules ofirreducible and projective representations of the tower of $0$-Hecke monoidsendows its ring of caracters with a Hopf algebra structure, isomorph to thenon-commutative symmetric functions Hopf algebra $ncsf$. This gives acategorification of $ncsf$, which is an interpretation of the non-commutativesymmetruc functions in the language of representation theory. This extends atheorem of Frobenius endowing the character ring of symmetric groups to theHopf algebra of symmetric functions. Since then a natural problem is tocategorify other Hopf algebras -- for instance the Planar Binary Tree algebraof Loday and Ronco -- by a tower of algebras.Guessing such a tower of algebra is a difficult problem in general.In this thesis we restrict ourselves to towers of monoids in order to have abetter control on its representations. This is quite natural as on one hand,this setup covers both previous fundamental examples, whereas $ncsf$cannot be categorified in the restricted set of tower of group algebras.In the first part of this work, we start with some results about representationtheory of towers of monoids. We then focus on categorification with towers ofsemilatices, for example the tower of permutohedrons. We categorify thealgebra, and cogebra structure of $fqsym$, but not the full Hopf algebrastructure with its dual. We then make a comprehensive search in order tocategorify $pbt$ with a tower of monoids. We show that under naturalhypothesis, there exists no tower of monoids satisfying the categorificationaxioms. Finally we show that in some sense, the tower of $0$-Hecke monoids isthe simplest tower categorifying $ncsf$.The second part of this work deals with parking functions, applying resultsfrom the first part. We first study the representation theory of non decreasingparking functions. We then present a joint work with Jean-Baptiste Priez on ageneralization of parking functions from Pitman and Stanley. To obtainenumeration formulas, we use a variant of the species theory which was moreefficient in our case.We used an action of $H_n(0)$ instead of the symmetric group and use theKrob-Thibon theorem to lift the character of this action into the Hopf algebraof non-commutative symmetric functions
15
Rivano, Hervé. "Algorithmique et télécommunications : Coloration et multiflot approchés et applications aux réseaux d'infrastructure." Phd thesis, Université de Nice Sophia-Antipolis, 2003. http://tel.archives-ouvertes.fr/tel-00169842.
Full textAbstract:
Cette thèse s'intéresse aux problématiques fondamentales d'optimisation combinatoire qui se dégagent de la modélisation structurelle et algorithmique du dimensionnement des réseaux d'infrastructure de télécommunication. L'optimisation de ces réseaux est essentielle aux opérateurs de télécommunication, qui demandent la garantie d'une exploitation efficace des ressources déployées.<br /><br />Nous donnons une nouvelle modélisation des réseaux optiques WDM multifibres. En considérant un routage agrégé au niveau des câbles, nous optons pour une nouvelle lecture des contraintes d'affectation de longueurs d'onde fondée sur des conflits de groupe.<br /><br />Nous étudions aussi le problème de coloration de chemins, issu de l'affectation de longueurs d'onde dans les réseaux optiques monofibres. Nous développons, pour la relaxation linéaire de ce problème, un algorithme polynomial efficace dans les arbres de degré borné, puis, par extension, dans les graphes de largeur arborescente bornée. Nous majorons le coût d'une telle coloration dans les arbres binaires et donnons une (1+5/(3e)+o(1))-approximation aléatoire pour la coloration entière dans les arbres de degré borné, ce qui améliore le meilleur algorithme connu pour ce cas.<br /><br />Nous présentons enfin des avancées algorithmiques pour les problèmes de multiflot entier et fractionnaire. Nous donnons un algorithme d'arrondi aléatoire incrémental pour l'approximation du multiflot entier. Motivés par le besoin d'un calcul rapide de multiflot fractionnaire pour l'algorithme précédent, nous nous intéressons aux approximations combinatoires de ce problème. En employant des techniques de calcul dynamique des plus courts chemins, nous améliorons l'un des meilleurs algorithme de la littérature.<br />Webstats4U - Free web site statistics
16
Morcrette, Basile. "Combinatoire analytique et modèles d'urnes." Phd thesis, Université Pierre et Marie Curie - Paris VI, 2013. http://tel.archives-ouvertes.fr/tel-00843046.
Full textAbstract:
Cette thèse étudie les urnes de Pólya à travers le prisme de la combinatoire analytique. Les urnes sont des modèles, conceptuellement très simples, de dynamique de croissance ou d'extinction dont les comportements limites sont extrêmement variés. Ces modèles sont largement étudiés par des approches probabilistes mais la compréhension précise des diverses lois limites reste une question ouverte. Les travaux de Flajolet et al. en 2005 ont illustré que pour ces questions, une approche par combinatoire analytique peut se révéler très fructueuse: l'étude des propriétés (nature, singularités) des séries génératrices associées aux urnes donne accès à des lois limites avec grande précision. Cette thèse s'inscrit dans la continuité de ces travaux et commence par identifier les séries des urnes de nature algébrique, grâce à un algorithme sophistiqué issu du calcul formel (Divination/Preuve automatique). Pour les classes d'urnes algébriques, nous menons des analyses, exacte et asymptotique, afin de connaître avec précision les comportements limites (structures des moments, vitesse de convergence, aspects limites locaux). Puis, l'étude d'urnes non algébriques est faite au travers d'exemples concrets portant sur la modélisation de réseaux sociaux, ainsi que sur la combinatoire des formules booléennes. Enfin, à travers des modèles d'urnes plus généraux (absence d'équilibre, présence d'aléa au sein des règles de substitution), nous montrons que l'approche symbolique de la combinatoire analytique est robuste. En particulier, une étude combinatoire générale des urnes sans condition d'équilibre est réalisée pour la première fois, unissant toute urne à une équation aux dérivées partielles.
17
Herrbach, Claire. "Etude algorithmique et statistique de la comparaison des structures secondaires d'ARN." Bordeaux 1, 2007. http://www.theses.fr/2007BOR13432.
Full textAbstract:
Notre travail s'inscrit dans la problématique de la comparaison de structures d'ARN. Nous étudions en particulier le cas des structures secondaires sans pseudo-noeud, qu'il est possible de modéliser par des arbres ordonnés étiquetés. Il existe des algorithmes polynomiaux d'édition et d'alignement d'arbres. Cependant, les opérations d'édition utilisées par ces algorithmes ne sont pas adaptées pour l'ARN. D'un autre côté, il a été montré que si l'on utilise un jeu d'opérations réalistes d'un point de vue biologique, le problème de l'édition de structures secondaires sans pseudo-noeud est NP-complet. Dans cette thèse, nous étudions le problème de l'alignement, avec ce même jeu d'opérations réaliste, de structures secondaires d'ARN sans pseudo-noeud. Nous proposons un algorithme polynomial d'alignement global et ses variantes d'alignement local et de recherche d'un motif structurel. Puis nous montrons que cet algorithme, et par le même coup l'algorithme classique d'alignement d'arbres ordonnés, a une complexité moyenne en O(n2). Nous avons implanté notre algorithme d'alignement ainsi que ses variantes afin de comparer notre approche aux outils déjà existants, et nous présentons quelques résultats. Nous présentons ensuite un travail préliminaire sur la construction de matrices de scores pour chaque opération d'édition réaliste pour l'ARN. Enfin, nous étudions le problème de sous-structures secondaires communes à un ensemble de structures tertiaires d'ARN, de façon à maximiser le nombre d'empilements. Nous montrons que dans le cas général, ce problème est NP-complet. Cependant, nous donnons un algorithme polynomial dans le cas où le nombre de structures en entrée est fixé.
18
Coudert, David. "Algorithmique et optimisation dans les réseaux de télécommunications." Habilitation à diriger des recherches, Université de Nice Sophia-Antipolis, 2010. http://tel.archives-ouvertes.fr/tel-00466400.
Full textAbstract:
Le contexte général de mes travaux se situe dans les réseaux orientés connexions, que ce soit des réseaux optiques à multiplexage en longueur d'onde (WDM), des réseaux MPLS (multi-protocol label switching), ou encore des réseaux à faisceaux hertziens (wireless backhaul networks). Dans ces réseaux, je m'intéresse à router les flux d'information, à agréger des flux d'information bas débits dans des flux de plus hauts débits, à faire évoluer le routage en cas de variations dans la quantité de trafic à transporter ou dans la topologie du réseau, et à assurer la continuité du trafic en cas de panne simple ou multiple. Pour aborder ces questions, j'utilise des outils variés de l'algorithmique, de la théorie des graphes et de l'optimisation combinatoire.<br /> L'ensemble des résultats présentés dans ce document est le fruit de travaux collaboratifs avec les membres de l'équipe-projet MASCOTTE, des collègues d'autres universités, française ou étrangères, et des collègues de France Télécom, Alcatel-Lucent et 3Roam. L'introduction de ce manuscrit résume nos travaux sur le routage, le groupage de trafic, la tolérance aux pannes et la reconfiguration, ainsi que des travaux plus récents sur la minimisation du nombre d'étiquettes dans les réseaux MPLS, le dimensionnement de réseaux de collecte IP sans fil, et sur le routage disjoints d'ensembles particuliers de requêtes. Ensuite, je détaille nos travaux sur le groupage de trafic au travers d'un état de l'art dans le chapitre 3, nos contributions sur la notion de groupes de ressources partageant un risque dans le chapitre 4, et sur la reconfiguration de routages dans le chapitre 5. Le chapitre 6 conclut ce manuscrit en présentant avec quelques directions de recherches.
19
Fici, Gabriele. "Mots interdits minimaux et applications." Phd thesis, Université de Marne la Vallée, 2006. http://tel.archives-ouvertes.fr/tel-00628628.
Full textAbstract:
Dans cette thèse nous traitons des mots interdits minimaux, qui sont les plus petits mots qui n'apparaissent pas comme facteur d'un mot donné, et de leurs applications. Dans la première partie de la thèse nous exposons les propriétés des mots interdits minimaux, et nous considérons quelques cas particuliers, comme celui d'un mot fini, d'un ensemble fini de mots finis, et d'un langage factoriel régulier. Nous présentons aussi les procédures pour le calcul des objets considérés. Ensuite, nous généralisons les mots interdits minimaux au cas de l'existence d'une période, qui détermine les positions des occurrences des facteurs modulo un entier fixé. Ceux-ci sont appelés mots interdits minimaux périodiques. Nous étudions leurs propriétés principales et avec des algorithmes de test de ces propriétés. Dans la deuxième partie de la thèse nous montrons deux applications des mots interdits minimaux. La première est reliée aux systèmes contraints. Nous donnons une construction en temps polynomial de l'ensemble des séquences qui satisfont la contrainte définie par une liste finie de blocs interdits, avec un ensemble spécifié de positions de bit sans contrainte. Nous donnons aussi une construction en temps linéaire d'une présentation à états finis d'un système contraint défini par une liste périodique de blocs interdits. La deuxième application est relative à un problème de biologie : la reconstruction d'une séquence génomique à partir d'un ensemble de ses fragments. Nous donnons une formalisation théorique de ce problème qui le rend résoluble en temps linéaire en utilisant les mots interdits minimaux. Nous prouvons aussi que notre algorithme résout un cas particulier du "problème de la plus petite sur-séquence" (Shortest Superstring Problem).
20
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.
Full textAbstract:
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.
21
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.
Full textAbstract:
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<br>In 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
22
Chauve, Cedric. "Structures arborescentes : problèmes algorithmiques et combinatoires." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2000. http://tel.archives-ouvertes.fr/tel-00007388.
Full textAbstract:
La première partie de ce mémoire est consacrée à l'énumération de diverses familles de structures arborescentes, en général selon le nombre de sommets. Les trois premiers chapitres sont consacrés à l'étude des arborescences de Cayley telles que la racine est inférieure à ses fils et des arborescences alternantes. La plupart de nos résultats sont prouvés bijectivement. Nous nous intéressons ensuite aux arborescences coloriées, et plus particulièrement à la formule d'inversion de séries formelles multivariées de Good-Lagrange. Nous donnons une nouvelle preuve bijective d'une variante de cette formule et utilisons cette preuve pour prouver combinatoirement diverses formules d'énumération de structures arborescentes et en déduire des algorithmes de génération aléatoire pour ces structures (notamment les cactus planaires). Nous concluons cette première partie par un chapitre consacré aux constellations : en combinant notre preuve de la formule de Good-Lagrange et la conjugaison d'arborescences (due à Bousquet-Mélou et Schaeffer), nous prouvons bijectivement une formule (nouvelle) pour l'énumération de constellations selon le nombre de sommets et de faces. Dans la seconde partie, nous étudions le problème de la recherche de motifs dans une arborescence, en utilisant une structure de données classique pour les mots : l'arborescence des suffixes. Nous proposons notamment un algorithme de recherche de motifs dans une arborescence, basé sur un codage d'une arborescence par des mots et sur l'utilisation de l'arborescence des suffixes d'un de ces mots, qui semble avoir de bonnes propriétés expérimentales. Nous concluons en étendant la notion d'arborescence des suffixes des mots aux arborescences et en décrivant un algorithme de construction pour cette structure.
23
Blin, Guillaume. "Combinatoire and Bio-informatique : Comparaison de structures d'ARN et calcul de distances intergénomiques." Phd thesis, Nantes, 2005. http://www.theses.fr/2005NANT2067.
Full textAbstract:
Nous présentons un ensemble de résultats concernant deux types de problèmes biologiques: la comparaison de structures de molécules d'ARN et le calcul de distances intergénomiques en présence de gènes dupliqués. Dans ce manuscrit, nous déterminons la complexité algorithmique de problèmes liés soit à la comparaison de structures de molécules d'ARN, soit aux réarrangements génomiques. L'approche adoptée pour l'ensemble de ces problèmes a été de déterminer, si possible, des algorithmes exacts et rapides répondant aux problèmes posés. Pour tout problème pour lequel cela ne semblait pas possible, nous avons essayé de prouver qu'il ne peut être résolu de façon rapide. Pour ce faire, nous démontrons que le problème en question est algorithmiquement difficile. Enfin, le cas échéant, nous poursuivons l'étude de ce problème en proposant, essentiellement, trois types de résultats: Approximation, Complexité paramétrée, Heuristique. Nous utilisons, dans ce manuscrit, des notions d'optimisation combinatoire, de mathématiques, de théorie des graphes et d'algorithmique<br>We present a set of results concerning two types of biological problems: (1) RNA structure comparison and (2) intergenomic distance computation considering non trivial genomes. In this thesis, we determine the algorithmic complexity of a set of problems linked to either RNA structure comparison (edit distance, APS problem, 2-interval pattern extraction, RNA design), or genomic rearrangements (breakpoints and conserved intervals distances). For each studied problem, we try to find an exact and fast algorithm resolving it. If we do not find such an algorithm, we try to prove that it is impossible to find one. To do so, we prove that the corresponding problem is difficult. Finally, we continue the study of each difficult problem by proposing three types of results: (1) Approximation, (2) Parameterized complexity, (3) Heuristic. We use in this thesis notions of combinatorics, mathematics, graph theory and algorithmics
24
Chapdelaine, Philippe. "Contribution à la théorie de la complexité algorithmique : problèmes de contraintes, complétude et résultats de classification, complexité structurelle." Caen, 2004. http://www.theses.fr/2004CAEN2042.
Full textAbstract:
Cette thèse se divise en deux parties indépendantes ayant comme point commun la théorie de la complexité algorithmique. Dans la première partie, nous étudions la complexité des problèmes de satisfaction de contraintes. Nous montrons que celle-ci est fortement liée au pouvoir d'expression des contraintes, et que celui-ci peut être déterminé, grâce à une correspondance de Galois, par les propriétés de clôture de ces contraintes. Dans le cas booléen, la structure de ce système de clôture étant connue, nous en déduisons des classifications complètes de la complexité des problèmes de l'audit et du comptage pour les requêtes conjonctives. Nous donnons également, par une technique constructive, la classification de la complexité de la recherche locale pour la satisfaisabilité des contraintes booléennes. Dans la deuxième partie, nous nous intéressons à la classe de complexité du temps linéaire non déterministe, NLIN. Nous étudions des raffinements de celle-ci, notamment les classes obtenues en bornant l'espace. Nous montrons qu'elles contiennent de nombreux problèmes naturels, et nous donnons, pour ces classes, des caractérisations logiques et des problèmes complets. Dans un deuxième temps, nous détaillons la structure interne de NLIN. Nous établissons que, sous certaines hypothèses, il existe une infinité de niveaux de réductions linéaires incomparables entre le niveau du temps linéaire déterministe et celui des problèmes NLIN-complets. Nous développons également la notion d'isomorphie linéaire permettant de préciser la notion d'équivalence linéaire en montrant que des problèmes sont, non seulement de même complexité, mais également structurellement identiques.
25
Karaboghossian, Théo. "Invariants polynomiaux et structures algébriques d'objets combinatoires." Thesis, Bordeaux, 2020. http://www.theses.fr/2020BORD0123.
Full textAbstract:
Dans la première moitié de ce mémoire, nous étudions les invariants polynomiaux définis par Aguiar et Ardila dans arXiv:1709.07504 dans le contexte des monoïdes de Hopf. Nous donnons d'abord une interprétation combinatoire de ces polynômes pour les monoïdes de Hopf des permutaèdres généralisés et des hypergraphes,sur les entiers naturels et négatifs. Nous en déduisons ensuite des interprétations similaires sur d'autres objets combinatoires(graphes, complexes simpliciaux, building sets, etc).Dans la seconde moitié de ce mémoire, nous proposons une nouvelle façon de définir et d'étudier des opérades de multigraphes et d'objets similaires.Nous étudions en particulier deux opérades obtenues avec cette méthode. La première est une généralisation directe de l'opérade Kontsevich-Willwacher,qui peut être considérée comme une opérade canonique sur les multigraphes et possède de nombreuses sous-opérades intéressantes.La seconde est une extension naturelle de l'opérade pré-Lie et a aussi un lien avec l'opérade précédente.Nous présentons également divers résultats sur certaines sous-opérades finiment enegendrées et établissons des liens entre elles et les opérades commutative et commutative magmatique<br>In the first half of this dissertation, we study the polynomial invariants defined by Aguiar and Ardila in arXiv:1709.07504 in the context of Hopf monoids. We first give a combinatorial interpretation of these polynomials over the Hopf monoids of generalized permutahedra and hypergraphs in both non negative and negative integers. We then use them to deduce similar interpretation on other combinatorial objects(graphs, simplicial complexes, building sets, etc).In the second half of this disseration, we propose a new way of defining and studying operads on multigraphs and similar objects.We study in particular two operads obtained with our method. The former is a direct generalization of the Kontsevich-Willwacher operad.This operad can be seen as a canonical operad on multigraphs,and has many interesting suboperads.The latter operad is a natural extension of the pre-Lie operad in a sense developed here and it is related to the multigraph operad. We also present various results on some of the finitely generated suboperads of the multigraph operad and establish links between them and the commutative operad and the commutative magmatic operad
26
Paranthoën, Thomas. "Génération aléatoire et structure des automates à états finis." Rouen, 2004. http://www.theses.fr/2004ROUES032.
Full textAbstract:
La génération aléatoire de structures combinatoires en plus de permettre de mieux connaître les comportements des objets que l'on génère, permet de tester les algorithmes basés sur ces structures. Dans le cas des automates déterministes nous donnons les algorithmes de génération qui construisent ces objets sur n'importe quel alphabet. Nous observons que quasiment tous les automates déterministes complets et accessibles sont minimaux. Dans le cas des automates non déterministes nous établissons un protocole de génération probabiliste qui maximise la taille des déterminisés des automates générés. Par ailleurs, nous formalisons la technique de déterminisation partielle. Nous établissons une structure de données, les recouvrements d'automates, qui permet de manipuler et de donner des propriétés des automates non déterministes. Nous en déduisons une technique qui réduit la complexité de l'algorithme de déterminisation exhaustif classique<br>Random generation of combinatoric structures allows one to test algorithms based on this structure, and to investigate the behavior of these structures. In the case of deterministic automata, we give the generation algorithms that allow us to build these objects on any alphabets. We show that almost all complete accessible deterministic automata are minimal. In the case of nondeterministic automata we establish a probabilistic generation protocol that maximise the deterministic automata associated with these nondeterministic automata. Finally we continue the progress in the use of determinization for the pattern-matching problem. We formalize the technique of the partial determinization. We establish a data structure: the deterministic cover. This structure allows one to manipulate and to give properties of non-deterministic automata. We deduce from this structure a technique that reduces the complexity of the classical brute force determinization algorithm
27
Allamigeon, Xavier. "Analyse statique de manipulations de mémoire par interprétation abstraite -- Algorithmique des polyèdres tropicaux, et application à l'interprétation abstraite." Phd thesis, Ecole Polytechnique X, 2009. http://pastel.archives-ouvertes.fr/pastel-00005850.
Full text
28
Voge, Marie-Emilie. "Optimisation des réseaux de télécommunications : Réseaux multiniveaux, Tolérance aux pannes et Surveillance du trafic." Phd thesis, Université de Nice Sophia-Antipolis, 2006. http://tel.archives-ouvertes.fr/tel-00171565.
Full textAbstract:
Les problèmes étudiés dans cette thèse sont motivés par des questions issues de l'optimisation des réseaux de télécommunication. Nous avons abordé ces problèmes sous deux angles principaux. D'une part nous avons étudié leurs propriétés de complexité et d'inapproximabilité. D'autre part nous avons dans certains cas proposé des algorithmes exacts ou d'approximation ou encore des méthodes heuristiques que nous avons pu comparer à des formulations en programmes linéaires mixtes sur des instances particulières.<br /><br />Nous nous intéressons aussi bien aux réseaux de coeur qu'aux réseaux d'accès. Dans le premier chapitre, nous présentons brièvement les réseaux d'accès ainsi que les réseaux multiniveaux de type IP/WDM et l'architecture MPLS que nous considérons pour les réseaux de coeur. Ces réseaux sont composés d'un niveau physique sur lequel est routé un niveau virtuel. A leur tour les requêtes des utilisateurs sont routées sur le niveau virtuel. Nous abordons également la tolérance aux pannes dans les réseaux multiniveaux qui motive deux problèmes que nous avons étudiés.<br /><br />Le second chapitre est consacré à la conception de réseaux virtuels. Dans un premier temps nous modélisons un problème prenant en compte la tolérance aux pannes, puis nous en étudions un sous-problème, le groupage. Notre objectif est de minimiser le nombre de liens virtuels, ou tubes, à installer pour router un ensemble de requêtes quelconque lorsque le niveau physique est un chemin orienté.<br /><br />Le troisième chapitre traite des groupes de risque (SRRG) induits par l'empilement de niveaux au sein d'un réseau multiniveaux. Grâce à une modélisation par des graphes colorés, nous étudions la connexité et la vulnérabilité aux pannes de ces réseaux.<br /><br />L'objet du quatrième chapitre est le problème du placement d'instruments de mesure du trafic dans le réseau d'accès d'un opérateur. Nous considérons aussi bien les mesures passives qu'actives. La surveillance du trafic possède de nombreuses applications, en particulier la détection de pannes et l'évaluation des performances d'un réseau.
29
Baïz, Adam. "De l’innovation des instruments de politique publique : développement d'une méthode de conception combinatoire autour d'un langage algorithmique et application au dispositif des certificats d’économie d’énergie." Thesis, Paris Sciences et Lettres (ComUE), 2018. http://www.theses.fr/2018PSLEM053/document.
Full textAbstract:
En dépit de ses diverses caractérisations, la nature innovante des instruments de politique publique semble consacrer trois types d’innovation : (a) soit, des imitations, à un glissement de modalités près, d’instruments préexistants ; (b) soit des hybridations d’instruments plus ou moins contraignants ; (c) soit des assemblages d’instruments de nature méta-instrumentale. En admettant alors que tous les instruments découlent les uns des autres par le biais de ces trois chemins de conception, nous avons cherché à produire une méthode de conception fondant concomitamment, et autour d’un même modèle-objet, une capacité d’identification ex post des instruments innovants et une capacité ex ante d’innovation.Au terme d’une démarche de recherche-intervention, nous avons convenu de définir les instruments comme autant de chaînes de causalité préfigurées de l’action collective, et avons formulé un langage algorithmique autour d’un certain nombre d’éléments - des acteurs, des actions, des événements, des opérateurs logiques et des vecteurs d’impact – afin de les caractériser de façon ostensive. En consacrant une méthode d’évaluation de la nouveauté et de l’effectivité instrumentales, nous avons dès lors pu établir qu’un instrument est innovant s’il constitue une nouvelle chaîne de causalité opérant effectivement dans la réalité technico-sociale. De façon corollaire, innover un instrument revient alors à dessiner une nouvelle chaîne de causalité, ou à modifier les acteurs et les actions qui la composent.Afin d’illustrer et d’éprouver cette méthode de conception que nous qualifions de combinatoire, nous avons enfin cherché à interroger le caractère innovant du dispositif des certificats d’économie (CEE) et ce, en proposant un protocole d'évaluation et en formulant diverses pistes d'innovation<br>Although it is diversely characterized, the innovative nature of instruments seems to follow three types of innovation: (a) imitations of existing instruments; (b) hybridizations of more or less coercive instruments; (c) or meta-conglomerations of instruments. After admitting that all instruments originate from one another through these three innovation paths and a unique object model, we tried to provide a new design method that would both enable the identification of innovative instruments and their design.Within the frame of intervention research, we agreed to define an instrument as a specific intended causal chain of public action, and formulated an algorithmic language along some instrumental elements (actors, actions, events, logical operators and impact vectors) in order to characterize instruments in an ostensive way. After developing a method to evaluate the newness and the effectivity of any instrument, we could more precisely define an innovative instrument as a new causal chain that is effectively implemented in the technical and social reality. As a corollary, innovating an instrument consists in designing a new causal chain, or modifying the actors and actions in it.Eventually, and in order to apply and test what we called a combinatory design method, we chose to question the innovative nature of the Energy Savings Certificates scheme (ESC). For this purpose, we elaborated an evaluation protocol and formulated several possible lines of innovation
30
Marchal, Loris. "Communications collectives et ordonnancement en régime permanent sur plates-formes hétérogènes." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2006. http://tel.archives-ouvertes.fr/tel-00123193.
Full textAbstract:
Les travaux présentés dans cette thèse concernent l'ordonnancement<br />pour les plates-formes hétérogènes à grande échelle. Nous nous<br />intéressons principalement aux opérations de communications<br />collectives comme la diffusion de données, la distribution de données<br />ou la réduction. Nous étudions ces problèmes dans le cadre de leur<br />régime permanent, en optimisant le débit d'une série d'opérations de<br />communications, en vue d'obtenir un ordonnancement asymptotiquement<br />optimal du point de vue du temps d'exécution total. Après avoir<br />présenté un cadre général d'étude qui nous permet de connaître la<br />complexité du problème pour chaque primitive, nous développons, pour<br />le modèle de communication un-port bidirectionnel, une méthode de<br />résolution pratique fondée sur la résolution d'un programme linéaire<br />en rationnels. Cette étude du régime permanent est illustrée par des<br />expérimentations sur Grid5000 et se prolonge vers l'ordonnancement<br />d'applications multiples sur des grilles de calcul.
31
Hoché, Toussaint. "Heuristiques pour la gestion d'une flotte de taxis autonomes, électriques, réservables et partageables." Electronic Thesis or Diss., université Paris-Saclay, 2021. http://www.theses.fr/2021UPASG082.
Full textAbstract:
Le transport routier de personnes est actuellement en train de se transformer de multiples manières : automatisation des véhicules, électrification, intégration des Technologies de l'Information et de la Communication (TIC) aux systèmes de gestion, pour n'en nommer que trois. Ces transformations apportent de nouveaux challenges et de nouvelles opportunités dans le domaine de la mobilité individuelle. L'objectif de cette thèse est de mettre au point un service gérant de manière centralisée une flotte de taxis électriques, autonomes, et partagés traitant le plus de clients possible.Du point de vue de l'électrification, trois difficultés sont étudiées. 1) La distance pouvant être parcourue après chaque plein est plus faible que pour les véhicules à combustion. 2) La vitesse à laquelle un plein est effectué est plus faible. 3) L'usage de l'infrastructure de recharge est susceptible d'être limité. La gestion de la recharge des véhicules doit être la plus efficace possible, afin de maximiser le temps de fonctionnement utile des taxis. Nous étudions deux cas : statique et dynamique. Dans le cas statique, les requêtes des clients sont connus longtemps à l'avance, et le gestionnaire de la flotte de taxi peut choisir librement quel client traiter. Dans le cas dynamique, les clients sont découverts au fur et à mesure qu'ils réservent, et le gestionnaire doit indiquer en temps réel à chaque client qui réserve si sa demande est acceptée.Une approche holistique est utilisée dans cette thèse, afin d'intégrer cette gestion de la recharge dans un système complet. On considère ainsi l'impact du stationnement et du partage de course sur le comportement des taxis. Enfin, nos tests sont effectués sur des instances de grande taille, comptant des dizaines de milliers de clients, basées sur des données réelles.Pour résoudre ces instances, nous proposons une heuristique gloutonne myope, améliorée par deux méthode de recherche de voisinage. La première méthode est une montée de colline, et la seconde un recuit simulé. Nos résultats montrent que ces méthodes sont adaptés pour des instances comportant des dizaines de milliers de clients, mais que le temps de calcul requis par le recuit simulé est très élevé. Nos résultats montrent également comment ces méthodes doivent être paramétrées en fonction des caractéristiques de l'instance sur laquelle elles sont utilisées, et diverses pistes permettant d'obtenir de meilleurs résultats<br>Individual transportation is currently undergoing multiple transformations: Automation of vehicles, electrification, integration of Information & Communications Technologies (ICT) in management systems, to name only three. These transformations bring new challenges and opportunities to the domain of individual mobility. The objective of this thesis is to develop a centralised system managing a fleet of electrics, autonomous, and shared taxis treating as many customers as possible.Regarding electrification, three difficulties are studied. 1) The range of electric vehicles is lower than for internal combustion vehicles. 2) Refilling is slower. 3) The charging infrastructure usage may be constraint. The recharge of vehicles must therefore be as efficient as possible, to maximise their uptime. We study two cases: static and dynamic. In the static case, clients' requests are known long in advance, and the fleet manager can freely choose the clients to treat. In the dynamic cas, each client is discovered when he formulate his request to the fleet manager, who has to tell in real-time if the client's request is accepted.A holistic approach is used in this thesis, to integrate the recharge management in a complete system. Thus, we consider the impact of parking and ride-sharing on the behaviour of taxis. Finally, our tests are performed on large instances, involving dozens of thousands of clients, based on real data.To solve these instances, we propose a myopic greedy heuristic, improved by two neighbourhood search method. The first method is a hill climbing, and the second one is a simulated annealing. Our results show that these methods are fitting for instances with tens of thousands of customers, but that the computation time required for the simulated annealing is very high. Our results also show how these methods must be parametered depending on the caracteristics of the instances, and we propose various ways to improve these results
32
Saadi, Toufik. "Résolution séquentielles et parallèles des problèmes de découpe / placement." Phd thesis, Université Panthéon-Sorbonne - Paris I, 2008. http://tel.archives-ouvertes.fr/tel-00354737.
Full textAbstract:
Les problèmes de découpe et de placement sont des problèmes combinatoires. Ils sont classes dans la catégorie des problèmes NP-Complets et admettent de nombreuses applications en industrie, en systèmes multiprocesseurs. Nous proposons dans cette thèse, plusieurs méthodes de résolution exactes et approchées, séquentielles et parallèles du problème de découpe et de placement à deux dimensions.
33
Goaoc, Xavier. "Nombres de Helly, théorèmes d'épinglement et projection de complexes simpliciaux." Habilitation à diriger des recherches, Université Henri Poincaré - Nancy I, 2011. http://tel.archives-ouvertes.fr/tel-00650204.
Full textAbstract:
La résolution efficace de certaines questions de géométrie algorithmique, par exemple les calculs de visibilité ou l'approximation de forme, soulève de nouvelles questions de géométrie des droites, domaine classique dont l'origine remonte à la seconde moitié du 19e siècle. Ce mémoire s'inscrit dans ce cadre, et étudie les nombres de Helly de certains ensembles de droites, un indice reliée à certains théorèmes de la base apparaissant en optimimisation combinatoire. Formellement, le nombre de Helly d'une famille d'ensembles d'intersection vide est le cardinal de sa plus petite sous-famille d'intersection vide et minimale pour l'inclusion relativement à cette propriété. En 1957, Ludwig Danzer a formulé la conjecture que pour tout $d \ge 2$ il existe une constante $h_d$ telle que pour toute famille $\{B_1, \ldots, B_n\}$ de boules deux à deux disjointes et de même rayon, le nombre de Helly de $\{T(B_1), \ldots, T(B_n)\}$ est au plus $h_d$; ici, $T(B_i)$ désigne l'ensemble des droites coupant $B_i$. Danzer a, de plus, spéculé que la constante $h_d$ (minimale) croît strictement avec $d$. Nous prouvons que de telles constantes existent, et que $h_d$ est au moins $2d-1$ et au plus $4d-1$ pour tout $d \ge 2$. Cela prouve la première conjecture et étaye la seconde. Nous introduisons, pour étudier les conjectures de Danzer, un analogue local du nombre de Helly que nous appellons nombre d'épinglement et qui se rattache à la notion d'immobilisation étudiée en robotique. Nous montrons que le nombre d'épinglement est borné pour toute famille (suffisament générique) de polyèdres ou d'ovaloides de $R^3$, deux cas où les nombres de Helly peuvent être arbitrairement grands. Un théorème de Tverberg énonce que si $\{B_1, \ldots, B_n\}$ est une famille de convexes du plan disjoints et congruents par translation alors le nombre de Helly de $\{T(B_1), \ldots, T(B_n)\}$ est au plus $5$. Quoique relativement différentes, notre preuve et celle de Tverberg exploitent toutes deux le fait que toute intersection d'au moins deux $T(B_i)$ a un nombre borné de composantes connexes, chacune contractile. Par des considérations sur l'homologie de projections de complexes et d'ensembles simpliciaux, nous unifions ces deux preuves et montrons que cette condition topologique suffit à établir une borne explicite sur le nombre de Helly.
34
Rivoire, Olivier. "Phases vitreuses, optimisation et grandes déviations." Phd thesis, Université Paris Sud - Paris XI, 2005. http://tel.archives-ouvertes.fr/tel-00009956.
Full textAbstract:
Les problèmes d'optimisation combinatoires définis sur graphes aléatoires sont au coeur de la théorie de la complexité algorithmique. Ils sont également étroitement liés à une formulation champ moyen, dite approximation de Bethe, de modèles sur réseau de verres de spins et verres structuraux. Cette thèse s'appuie sur ce parallèle pour appliquer à des problèmes d'optimisation une approche issue de la physique statistique des systèmes désordonnés, la méthode de la cavité. Etant donné un ensemble d'entrées (instances) d'un problème d'optimisation, cette méthode permet de déterminer les propriétés des solutions des instances typiques, ainsi que celles des instances atypiques, dont les probabilités sont exponentiellement petites (grandes déviations sur la structure externe). Pour une instance donnée, la méthode de la cavité donne également accès à la thermodynamique des différentes solutions admissibles (grandes déviations sur la structure interne). D'un point de vue physique, de nombreux problèmes algorithmiquement difficiles se révèlent ainsi posséder une phase de type verre. Cette thèse est composée de trois parties destinées à exposer les principes, applications et limitations de la méthode de la cavité. La première partie rappelle, dans la perspective des grandes déviations, les liens entre physique statistique et optimisation combinatoire. La deuxième partie aborde les modèles définis sur graphes aléatoires et, pour différents ensembles de graphes, analyse les propriétés typiques et atypiques de ces modèles. La troisième partie est consacrée aux grandes déviations sur le "désordre interne", constitué par les solutions et quasi-solutions d'une instance donnée. Une attention particulière est dévolue au traitement des phases vitreuses où l'ensemble des solutions est fragmenté en un nombre exponentiel d'amas disjoints (structure dite à un pas de brisure de symétrie des répliques); il est montré comment la méthode de la cavité fournit dans de tels cas une description fine des propriétés géométriques de l'espace des solutions.
35
Lesfari, Hicham. "Fondements réseaux et l'IA." Electronic Thesis or Diss., Université Côte d'Azur, 2022. http://www.theses.fr/2022COAZ4056.
Full textAbstract:
Le domaine de l'Intelligence Artificielle (IA) a un large impact sur la société d'aujourd'hui, ayant conduit notamment à une interaction passionnante entre plusieurs disciplines scientifiques. À cet égard, un double intérêt émerge dans la littérature.D'une part, une tendance croissante dans les réseaux de télécommunication consiste à revisiter les problèmes d'optimisation classiques en utilisant des techniques d'apprentissage automatique afin d'exploiter leurs avantages potentiels. Nous nous focaliserons sur certains défis posés par la détection d'anomalies dans les réseaux ainsi que l'allocation des ressources dans le cadre des réseaux logiciels (SDN) et de la virtualisation des fonctions réseau (NFV). D'autre part, un effort substantiel a été consacré dans le but d'apporter une compréhension théorique du comportement collectif des réseaux. Nous nous focaliserons sur certains défis posés par l'étude de la dynamique majoritaire au sein des systèmes multi-agents ainsi qu'à la compression des réseaux de neurones artificiels dans le but d'augmenter leur efficacité.Dans cette étude, nous contextualisons les points focaux ci-dessus dans le cadre de l'étude de certains fondements de réseaux; vus sous l'angle des réseaux de télécommunications et des réseaux neuronaux. Nous nous concentrons d'abord sur le développement de mesures de similarité de graphes pour la détection d'anomalies dans les réseaux. Ensuite, nous étudions la dynamique majoritaire déterministe et stochastique dans les systèmes multi-agents. Ensuite, nous discutons du problème de la somme de sous-ensembles aléatoires dans le contexte de la compression des réseaux neuronaux. Enfin, nous passons en revue quelques problèmes généraux divers<br>The field of Artificial Intelligence (AI) has brought a broad impact on today's society, leading to a gripping interaction between several scientific disciplines. In this respect, there has been a strong twofold interest across the literature.On the one hand, a growing trend in telecommunication networks consists in revisiting classic optimization problems using machine learning techniques in order to exploit their potential benefits. We focus on some challenges brought by the detection of anomalies in networks, and the allocation of resources within software-defined networking (SDN) and network function virtualization (NFV).On the other hand, a substantial effort has been devoted towards the theoretical understanding of the collective behavior of networks. We focus on some challenges brought by the study of majority dynamics within multi-agent systems, and the compression of artificial neural networks with the aim at increasing their efficiency.In this study, we contextualize the above focal points in the framework of investigating some foundations of networks; viewed through the lens of telecommunications networks and neural networks. We first focus our attention on developing graph similarity measures for network anomaly detection. Next, we study deterministic and stochastic majority dynamics in multi-agent systems. Then, we discuss the random subset sum problem in the context of neural network compression. Finally, we walk through some other miscellaneous problems
36
Tsatcha, Dieudonné. "Contribution à l'extraction et à la représentation des connaissances de l'environnement maritime : proposition d'une architecture dédiée aux applications de navigation." Thesis, Brest, 2014. http://www.theses.fr/2014BRES0118/document.
Full textAbstract:
De nos jours, les applications informatiques autonomes sont au centre de grandes préoccupations de la recherche scientifique. Ces dernières sont destinées initialement à des systèmes d'aide à la décision dans des environnements contraints et dynamiques, communément appelés environnements complexes. Elles peuvent dès à présent, à l'aide des avancées de la recherche, permettre de construire et déduire leurs connaissances propres afin d'interagir en temps réel avec leur environnement. Cependant, elles sont confrontées à la difficulté d'avoir une modélisation fidèle du monde réel et des entités qui le composent. L'un des principaux objectifs de nos recherches est de capturer et modéliser la sémantique associée aux entités spatio-temporelles afin d'enrichir leur expressivité dans les SIG ou les systèmes d'aide à la décision. Un service de routage maritime dynamique a été déployé en exploitant cette modélisation. Cet algorithme a été démontré comme optimal en termes d'espace mémoire et de temps de calcul. La sémantique capturée se compose de l'affordance et de la saillance visuelle de l'entité spatiale. Les connaissances associées à cette sémantique sont par la suite représentées par une ontologie computationnelle qui intègre des approches spatio-temporelles. Ces connaissances sont soit déduites du savoir de l'expert du domaine, soit extraites de gros volumes de données textuelles en utilisant des techniques de traitement automatique du langage. L'ontologie computationnelle proposée nous a permis de définir un algorithme de routage maritime dynamique (fonction des évènements ou objets présents dans l'environnement) fondé sur une heuristique itérative monocritère de plus courte distance et bidirectionnelle. L'algorithme BIDA* proposé s'applique sur un graphe itératif qui est une conceptualisation d'une grille hexagonale itérative recouvrant la zone de navigation. Cet algorithme permet aussi la gestion de différents niveaux de résolution. Toujours dans l'initiative de produire un modèle aussi proche que possible du monde réel, l'algorithme BIDA* a été enrichi des stratégies multicritères afin de prendre en compte les différentes contraintes de la navigation maritime. Les contraintes globales et locales auxquelles nous nous sommes intéressés sont la profondeur des eaux, la distance de navigation et la direction de navigation. Le modèle proposé permet ainsi d'enrichir les capacités cognitives des utilisateurs évoluant dans les environnements maritimes et peut aussi être utilisé pour construire des systèmes complètement autonomes explorant ces environnements. Un prototype expérimental de navigation intelligente mettant en oeuvre cette modélisation et proposant un service de routage maritime a été développé dans le cadre de cette thèse<br>No
37
Sayadi, Mohamed Yosri. "Construction et analyse des algorithmes exacts et exponentiels : énumération input-sensitive." Electronic Thesis or Diss., Université de Lorraine, 2019. http://www.theses.fr/2019LORR0316.
Full textAbstract:
Moon et Moser ont prouvé que le nombre maximum des ensembles stables maximaux dans un graphe de n sommets est au plus 3^{n/3}. Cette borne, appelée borne supérieure, est stricte vu l’existence d’une famille des graphes avec un tel nombre appelée borne inférieure. Au contraire de l’énumération des ensembles stables maximaux, avoir deux bornes qui se qui se coïncident n’est pas évident du tout. Et c’est assez courant dans l’énumération « input-sensitive » d’avoir un grand écart. Ce problème concerne même les ensembles les plus classiques comme les ensembles dominants minimaux où le meilleur algorithme connu pour énumérer ces ensembles est en O(1.7159^n) et la meilleure borne inférieure connue est seulement 1.5704^n. Durant cette thèse, on a proposé un algorithme « Mesurer pour Conquérir » pour énumérer tous les ensembles dominants minimaux dans les graphes cordaux en O(1.5048^n). On a étudié aussi l’énumération des ensembles dominants connexes minimaux et les ensembles irredondants maximaux qui sont très proches des ensembles dominants minimaux. On a proposé un algorithme d’énumération des ensembles dominants connexes minimaux dans les graphes bipartis convexes en O(1.7254^n). On a conçu aussi des algorithmes d’énumération des ensembles irredondants maximaux dans les graphes cordaux, les graphes d’intervalles et les forêts en O(1.7549^n), O(1.6957^n ) et O(1.6181^n) respectivement au lieu de l’algorithme trivial en O*(2^n). On a proposé aussi comme une borne inférieure une famille de forêts avec Omega(1.5292^n) ensembles irredondants maximaux. Dans le cas des cographes, l'écart entre les deux bornes est réduit à néant en montrant que le nombre maximum de ces ensembles est Theta(15^{n/6}). Afin de varier, on a étudié un nouvel ensemble défini récemment : L’ensemble tropical connexe minimal. On a proposé une borne inférieure de 1.4961^n, mais sans réussir à améliorer la borne supérieure de 2^n. On a proposé des algorithmes d’énumération des ensembles tropicaux connexes minimaux dans les graphes cobipartis, les graphes d’intervalles et les graphes blocs en O*(3^{n/3}), O(1.8613^n) et O*(3^{n/3}) respectivement. On a établi une borne inférieure de 1.4766^n pour les graphes scindés et de 3^{n/3} pour les graphes cobipartis, les graphes d’intervalles et les graphes blocs. Finalement, comme perspective et pour attirer l’attention de la communauté sur l’énumération des ensembles dominants totaux minimaux, on a montré que le nombre maximum de ces ensembles est Ω(1.5848^n)<br>Moon and Moser proved that the maximum number of maximal independent sets in a graph of n vertices is at most 3^{n/3}. This maximum number, called upper bound, is tight given the existence of a family of graphs with such a number called lower bound. Unlike the enumeration of maximal independent sets, having a tight bounds is not obvious at all. And it’s quite common in the “input-sensitive” enumeration to have a big gap. This problem concerns even the most studied sets as minimal dominating sets where the best known algorithm to enumerate those sets runs in time O(1.7159^n) and the best known lower bound is only 1.5704^n. During this thesis, we proposed a "Measure and Conquer" algorithm to enumerate all minimal dominating sets for chordal graphs in time O(1.5048^n). Minimal connected dominating sets and maximal irredundant sets, which are closely related to minimal dominating sets, were also studied. An enumeration algorithm of minimal connected dominating sets in convex bipartite graphs has been proposed with a running time in O(1.7254^n). Enumeration algorithms of maximal irredundant sets have also been given for chordal graphs, interval graphs, and forests in times O(1.7549^n), O(1.6957^n) and O(1.6181^n) respectively instead of the trivial algorithm in time O*(2^n). We complement these upper bounds by showing that there are forest graphs with Omega(1.5292^n) maximal irredundant sets. We proved also that every maximal irredundant set of a cograph is a minimal dominating set. This implies that the maximum number of those sets in cographs is Theta(15^{n/6}). Finally, to vary, we studied a new set has been defined recently: The minimal tropical connected set. A lower bound of 1.4961^n has been proposed but we failed to improve the upper bound of 2^n. Enumeration algorithms of minimal tropical connected sets have been given for cobipartite, interval and block graphs in times O*(3^{n/3}), O(1.8613^n) and O*(3^{n/3}) respectively. A lower bound of 1.4766^n for splits graphs and 3^{n/3} for cobipartite, interval graphs and block graphs have been provided. We proposed a new lower bound of 1.5848^n, as a perspective and in order to draw community attention to the maximum number of minimal total dominating sets
38
Bourdache, Nadjet. "Élicitation incrémentale des préférences pour l’optimisation multi-objectifs : modèles non-linéaires, domaines combinatoires et approches tolérantes aux erreurs." Electronic Thesis or Diss., Sorbonne université, 2020. http://www.theses.fr/2020SORUS255.
Full textAbstract:
Les travaux effectués durant cette thèse s'inscrivent dans le cadre de la théorie de la décision algorithmique, domaine au carrefour de la théorie de la décision, de la recherche opérationnelle et de l'intelligence artificielle. Cette thèse vise à concevoir des méthodes d'optimisation interactive fondées sur l'élicitation incrémentale des préférences pour la prise de décision multicritère, multi-agents ou dans le risque. Nous nous intéressons plus précisément à l'élicitation incrémentale des paramètres de fonctions d'agrégation qui consiste à alterner questions préférentielles permettant de réduire l'incertitude concernant la valeur des paramètres modélisant les préférences particulières du décideur, et exploration de l'espace des solutions, jusqu'à pouvoir déterminer une recommandation de bonne qualité. L'intérêt d'alterner phases de questions et phases d'exploration est double: d'une part, les informations préférentielles récoltées durant une phase d'élicitation permettent de mieux focaliser la phase d'exploration suivante sur les solutions les plus intéressantes pour le décideur; d'autre part, l'exploration de l'espace des solutions permet de guider le choix des questions de manière à ce qu'elles soient les plus informatives possible. Nous introduisons dans cette thèse des méthodes d'élicitation dans différents contextes. Dans un premier temps, nous nous intéressons à des fonctions d'agrégation non-linéaires pour modéliser les préférences du décideur sur un ensemble combinatoire d'alternatives. Nous nous intéressons ensuite à la conception de méthodes d'élicitation prenant en compte la possibilité de la présence d'incohérences dans les réponses du décideur, d'abord sur domaine explicite, puis sur domaine combinatoire. Les algorithmes introduits sont génériques et peuvent s'appliquer à différents problèmes de choix multi-objectifs<br>This thesis work falls within the area of algorithmic decision theory, a research domain at the crossroad of decision theory, operations research and artificial intelligence. The aim is to produce interactive optimization methods based on incremental preference elicitation in decision problems involving several criteria, opinions of agents or scenarios. Preferences are represented by general decision models whose parameters must be adapted to each decision problem and each decision maker. Our methods interleave the elicitation of parameters and the exploration of the solution space in order to determine the optimal choice for the decision maker. The idea behind this is to use information provided by the elicitation to guide the exploration of the solution space and vice versa. In this thesis, we introduce new incremental elicitation methods for decision making in different contexts : first for decision making in combinatorial domains when the decision models are non-linear, and then in a setting where one takes into account the possibility of inconsistencies in the answers of te decision maker. All the algorithms that we introduce are general and can be applied to a wide range of multiobjective decision problems
39
Lannez, Sébastien. "Optimisation des tournées d'inspection des voies." Phd thesis, INSA de Toulouse, 2010. http://tel.archives-ouvertes.fr/tel-00595070.
Full textAbstract:
La SNCF utilise plusieurs engins spécialisés pour ausculter les fissures internes du rail. La fréquence d'auscultation de chaque rail est fonction du tonnage cumulé qui passe dessus. La programmation des engins d'auscultations ultrasonores est aujourd'hui décentralisée. Dans le cadre d'une étude de réorganisation, la SNCF souhaite étudier la faisabilité de l'optimisation de certaines tournées d'inspection. Dans le cadre de cette thèse de doctorat, l'optimisation de la programmation des engins d'auscultation à ultrasons est étudiée. Une modélisation mathématique sous forme de problème de tournées sur arcs généralisant plusieurs problèmes académiques est proposées. Une méthode de résolution exacte, appliquant la décomposition de Benders, est détaillée. À partir de cette approche, une heuristique de génération de colonnes et de contraintes est présentée et analysée numériquement sur des données réelles de 2009. Enfin, un logiciel industriel développé autour de cette approche est présenté.
40
Mustafa, Nabil. "Approximations of Points: Combinatorics and Algorithms." Habilitation à diriger des recherches, Université Paris-Est, 2013. http://tel.archives-ouvertes.fr/tel-01062825.
Full textAbstract:
At the core of successful manipulation and computation over large geometric data is the notion of approximation, both structural and computational. The focus of this thesis will be on the combinatorial and algorithmic aspects of approximations of point-set data P in d-dimensional Euclidean space. It starts with a study of geometric data depth where the goal is to compute a point which is the 'combinatorial center' of P. Over the past 50 years several such measures of combinatorial centers have been proposed, and we will re-examine several of them: Tukey depth, Simplicial depth, Oja depth and Ray-Shooting depth. This can be generalized to approximations with a subset, leading to the notion of epsilon-nets. There we will study the problem of approximations with respect to convexity. Along the way, this requires re-visiting and generalizing some basic theorems of convex geometry, such as the Caratheodory's theorem. Finally we will turn to the algorithmic aspects of these problems. We present a polynomial-time approximation scheme for computing hitting-sets for disks in the plane. Of separate interest is the technique, an analysis of local-search via locality graphs. A further application of this technique is then presented in computing independent sets in intersection graphs of rectangles in the plane.
41
Milosz, Robin. "Étude algorithmique et combinatoire de la méthode de Kemeny-Young et du consensus de classements." Thèse, 2018. http://hdl.handle.net/1866/21741.
Full text
42
Desharnais, Charles. "Étude combinatoire et algorithmique de la médiane de permutations sous la distance de Kendall-Tau." Thèse, 2019. http://hdl.handle.net/1866/22522.
Full text
43
Grosshans, Nathan. "The limits of Nečiporuk’s method and the power of programs over monoids taken from small varieties of finite monoids." Thèse, 2018. http://hdl.handle.net/1866/21738.
Full text