Dissertations / Theses: 'Complexité combinatoire'

1

Bouras, Abdelghani. "Problème d'affectation quadratique de petit rang : modeèles, complexité et applications." Université Joseph Fourier (Grenoble), 1996. http://www.theses.fr/1996GRE10102.

Full text

Abstract:

Le probleme d'affectation quadratique (paq) traite un certain type du probleme de placement, ou il faut minimiser les distances entre les sites de construction et les flux de matieres entre les usines a construire. Dans cette etude, nous traitons le paq par la formulation algebrique quand le rang des matrices de distances a et de flots b sont petits. Cette ecriture permet de montrer que des problemes connus sont des cas particuliers du paq, comme le probleme du voyageur de commerce, du probleme de placement de lamelles autour d'un cylindre, plus connu sous le nom du probleme de la turbine hydraulique ainsi que du probleme de stockage de fichiers sur un disque dur. Nous nous inspirons d'une ecriture du paq, basee sur les valeurs et vecteurs propres de a et b, pour traiter des instances avec a et b de rang 1. Nous montrons que si a et b sont de signes quelconques et de rang 1, alors le probleme est np-difficile. A partir de ce probleme difficile, nous montrons que d'autres instances sont aussi np-difficiles, en augmentant les rangs de a de 1 a r et b de 1 a s. Une autre preuve est donnee sur la complexite du probleme. Le probleme reste extremement difficile meme si les rangs des matrices sont petits. Nous donnons quelques solutions exactes pour des matrices a structures particulieres quand le cas general est np-difficile et nous proposons une methode heuristique basee sur l'approximation des matrices par des matrices de plus petit rang, en particulier de rang 1. Des tests numeriques sont donnes et s'averent interessants pour certaines instances. Nous faisons des remarques sur les plus importantes bornes inferieures existantes et nous introduisons de nouvelles bornes pour le cas ou a et b sont de rang 1

APA, Harvard, Vancouver, ISO, and other styles

2

Chung, Yerim. "Optimisation combinatoire inverse et applications." Paris 1, 2010. http://www.theses.fr/2010PA010009.

Full text

Abstract:

L'optimisation combinatoire inverse a suscité beaucoup d'attention de la communauté de la recherche opérationnelle pendant les deux dernières décennies. Étant donnée une instance d'un problème d'optimisation combinatoire définie par un système de paramètres (coûts, profits, etc. ) et une solution réalisable, le problème inverse associé consiste à modifier au minimum les paramètres afin de rendre la solution fixée optimale dans l'instance modifiée. Dans le cadre de l'optimisation combinatoire, de nombreux problèmes inverses ont été étudiés, mais relativement peu d'études ont été menées sur des versions inverses de problèmes NP-difficiles. Dans cette thèse, nous considérons des problèmes combinatoires inverses généralisés. Nous commençons par imposer certaines contraintes aux paramètres à modifier. En particulier, des contraintes booléennes nous permettent de définir des versions inverses de problèmes non pondérés. Ainsi, des contraintes discrètes engendrent des problèmes combinatoires inverses eux-même combinatoires. Nous introduisons alors deux variantes de problèmes combinatoires inverses généralisés, à savoir "les problèmes inverses contre un algorithme spécifié" et "les problèmes inverses en valeur". Pour la première, un algorithme étant spécifié pour le problème d'origine, on cherche, pour une instance et une solution réalisable fixées, à modifier le moins possible l'instance pour que cette solution puisse être choisie par l'algorithme. Un problème inverse en valeur quant à lui est défini en spécifiant une valeur à atteindre au lieu d'une solution cible. L'objectif est de modifier le moins possible l'instance considerée de sorte que la valeur optimale de l'instance modifiée soit égale à la valeur fixée. Nous étudions différentes versions inverses de problèmes NP-difficiles. Les problèmes abordés sont le stable maximum d'un graphe (ensemble maximum de sommets 2 à 2 non adjacents), le voyageur de commerce minimum et la coloration minimum des sommets d'un graphe. Notre principal objectif est d'étudier la complexité et l'approximabilité de ces problèmes.

APA, Harvard, Vancouver, ISO, and other styles

3

Renotte-Jeudy, Laure. "Classes de complexité, complétude et préservation de l'approximation." Paris 9, 1996. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1996PA090064.

Full text

Abstract:

L'objet de cette thèse est l'étude de transformations entre problèmes d'optimisation combinatoires dont la version décision est NP-complète. Ces réductions doivent être adaptées au point de vue approximation c'est-à-dire non seulement faire correspondre les solutions optimales de deux problèmes mais surtout conserver diffèrent type d'information concernant les solutions qui sont simplement réalisables. Nous proposons tout d'abord un état de l'art sur les réductions préservant l'approximation en montrant comment l'évolution de cet outil permet de s'inscrire dans le cadre optimisation et surtout approximation. Nous présentons ensuite des résultats d'équivalence que nous établissons par la mise en œuvre de réductions continues. Ces résultats sont regroupés en hiérarchies à l'intérieur desquelles nous proposons des réductions continues entre les problèmes. Nous établissons également des réductions entres différentes hiérarchies. Des couches d'équi-approximabilité sont ainsi construites à l'intérieur de la classe des problèmes d'optimisation NP

APA, Harvard, Vancouver, ISO, and other styles

4

Watrigant, Rémi. "Approximation et complexité paramétrée de problèmes d’optimisation dans les graphes : partitions et sous-graphes." Thesis, Montpellier 2, 2014. http://www.theses.fr/2014MON20100/document.

Full text

Abstract:

La théorie de la NP-complétude nous apprend que pour un certain nombre de problèmes d'optimisation, il est vain d'espérer un algorithme efficace calculant une solution optimale. Partant de ce constat, un moyen pour contourner cet obstacle est de réaliser un compromis sur chacun de ces critères, engendrant deux approches devenues classiques. La première, appelée approximation polynomiale, consiste à développer des algorithmes efficaces et retournant une solution proche d'une solution optimale. La seconde, appelée complexité paramétrée, consiste à développer des algorithmes retournant une solution optimale mais dont l'explosion combinatoire est capturée par un paramètre de l'entrée bien choisi. Cette thèse comporte deux objectifs. Dans un premier temps, nous proposons d'étudier et d'appliquer les méthodes classiques de ces deux domaines afin d'obtenir des résultats positifs et négatifs pour deux problèmes d'optimisation dans les graphes : un problème de partition appelé Sparsest k-Compaction, et un problème de recherche d'un sous-graphe avec une cardinalité fixée appelé Sparsest k-Subgraph. Dans un second temps, nous présentons comment les méthodes de ces deux domaines ont pu se combiner ces dernières années pour donner naissance au principe d'approximation paramétrée. En particulier, nous étudierons les liens entre approximation et algorithmes de noyaux
The theory of NP-completeness tells us that for many optimization problems, there is no hope for finding an efficient algorithm computing an optimal solution. Based on this, two classical approaches have been developped to deal with these problems. The first one, called polynomial- time approximation, consists in designing efficient algorithms computing a solution that is close to an optimal one. The second one, called param- eterized complexity, consists in designing exact algorithms which com- binatorial explosion is captured by a carefully chosen parameter of the instance. The goal of this thesis is twofold. First, we study and apply classical methods from these two domains in order to obtain positive and negative results for two optimization problems in graphs: a partitioning problem called Sparsest k-Compaction, and a cardinality constraint subgraph problem called Sparsest k-Subgraph. Then, we present how the different methods from these two domains have been combined in recent years in a concept called parameterized approximation. In particular, we study the links between approximation and kernelization algorithms

APA, Harvard, Vancouver, ISO, and other styles

5

Duvillié, Guillerme. "Approximation, complexité paramétrée et stratégies de résolution de problèmes d'affectation multidimensionnelle." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT321/document.

Full text

Abstract:

Au cours de la thèse, nous nous sommes intéressés aux problèmes d'empilement de wafers. Ces problèmes apparaissent lors de la fabrication de processeurs en 3 dimensions. Au cours du processus de fabrication, les puces électroniques doivent être empilées les unes sur les autres. Jusqu'à peu, ces dernières, une fois gravées sur des plaques de silicium appelées wafers, étaient découpées, puis triées afin d'écarter les puces défectueuses et enfin assemblées les unes entre elles.Cependant empiler les wafers plutôt que les puces présente de nombreux avantages techniques et financiers. Naturellement, étant impossible d'écarter les puces défectueuses sans découper la plaque de silice, le problème de la superposition d'une puce viable avec une puce défectueuse se pose. Une pile de puces, étant considérées comme défectueuse si elle contient ne serait-ce qu'une puce défectueuse, la superposition non réfléchie des wafers entre eux mènerait à un rendement désastreux.Afin de générer un nombre minimum de piles défectueuses, une "cartographie" de chaque wafer candidat à la superposition est réalisée lors d'une phase de test, permettant de situer les puces défectueuses sur le wafer. Une fois cette cartographie réalisée, l'objectif est de sélectionner les wafers qui seront assemblés ensembles de manière à faire correspondre les défauts de chacun des wafers.Ce problème peut être modélisé à l'aide d'un problème d'affectation multidimensionnelle. Chaque wafer est représenté par un vecteur comportant autant de composantes que de puces sur le wafer qu'il représente. Une composante égale à zéro matérialise une puce défectueuse tandis qu'un un matérialise une puce viable. Chaque lot de wafers est représenté par un lot de vecteurs. Formellement, une instance d'empilement de wafers est représenté par m ensembles de n vecteurs binaires p-dimensionnels. L'objectif est alors de réaliser n m-uplets disjoints contenant exactement un vecteur par ensemble. Ces m-uplets représenteront les piles. Chaque m-uplet peut être représenté par un vecteur binaire p-dimensionnels, chaque composante étant calculée en réalisant le ET binaire des composantes correspondantes des vecteurs qui composent le m-uplet. Autrement dit, une composante du vecteur représentant le m-uplet est égale à un si et seulement si tous les vecteurs ont cette composante égale à un. Et donc une pile de puces est viables si toutes les puces qui la composent sont viables. L'objectif est alors de minimiser le nombre de zéros ou de maximiser le nombre de un.La thèse comporte deux grandes parties. Une partie théorique abordant la complexité des différentes versions du problèmes en fonction de certains paramètres tels que m, n, p ou encore le nombre maximum de zéros par vecteurs. Nous montrons entre autre que ces problèmes peuvent être utilisés pour modéliser des problèmes plus classiques tels que Maximum Clique, Minimum Vertex Cover ou encore k-Dimensional Matching, permettant de prouver un certain nombre de résultats négatifs que ce soit d'un point de vue de la complexité classique, l'approximabilité ou la complexité paramétrée. Nous fournissons également des résultats positifs pour des cas particuliers du problème.Dans un second temps, nous nous intéressons à la résolution pratique du problème en fournissant et comparant un certain nombre de formulations en Programmation Linéaire en Nombres Entiers. Mais nous nous intéressons également aux performances en pratique de certaines heuristiques à garantie de performances détaillées dans la partie théorique
In this thesis, we focused in the Wafer-to-Wafer integration problems. These problems come from IC manufacturing. During the production of three-dimensional processors, dies have to be superimposed. Until recent, the dies were engraved on a silicon disk called wafer, then were cut, tested and sorted to suppress faulty dies and lastly superimposed one to each other.However superimposing wafers instead of dies presents several technical and financial advantages. Since faulty dies can only be dismissed when cutting the wafer, superimpose two wafers can lead to superimpose a faulty die with a viable one. In this case, the resulting stack of dies is considered as faulty. It follows that a bad assignment between the wafers can lead to a disastrous yield.In order to minimize the number of faulty dies stacks, a "failure map" of each wafer is generated during a test phase. This map gives location of the faulty dies on the wafers. The objective is then to take advantage of this map to define an assignment of the wafers to each other in order to match as many failures as possible.This problem can be modelized with Multidimensional Assignment problems. Each wafer can be seen as a vector with as many dimensions as the number of dies engraved on it. A coordinate set to zero marks a faulty die while a coordinate set to one indicates a viable one. Each seat of wafers is represented by a set of vector. Formally, an instance of a Wafer-to-Wafer integration problem is represented by m sets of n p-dimensional vectors. The objective is then to partition the vectors into n disjoint m-tuples, each tuple containing exactly one vector per set. An m-tuple represents a stack of wafers. Every m-tuple can be represented by a p-dimensional vector. Each coordinate is computed by performing the bitwise AND between the corresponding coordinates of the vectors that compose the m-tuple. In other words, a coordinate of the representative vector is equal to one if and only if this coordinate is equal to one in every vector composing the tuple. It follows that a dies stack is viable if and only if all the dies composing the stack are viable. The objective is then to maximize the overall number of ones of to minimize the overall number of zeros.The first part of the thesis is a theoretical one. We study the complexity of the considered versions of the problem with regards to natural parameters such as m, n, p or the number of zeros per vector. We show that these problems can encode more classical problems such as Maximum Clique, Minimum Vertex Cover or k-Dimensional Matching. This leads to several negative results from computational complexity, approximability or even parameterized complexity point of view. We also provide several positive results for some specific cases of the problem.In a second part, we focus on the practical solving of the problem. We provide and compare several Integer Linear Programming formulations. We also focus on performances of some approximation algorithms that we detailed in the theoretical part

APA, Harvard, Vancouver, ISO, and other styles

6

Ould, Mohamed Lemine Mohamed. "Connaissance inter-entreprises et optimisation combinatoire." Thesis, Paris 9, 2014. http://www.theses.fr/2014PA090015/document.

Full text

Abstract:

La connaissance inter-entreprises permet à chaque société de se renseigner sur ses clients, ses fournisseurs et de développer son activité tout en limitant le risque lié à la solvabilité ou retard de paiement de ses partenaires. Avec les tensions de trésorerie, la nécessité de la croissance et l'augmentation de la concurrence, ce domaine devient plus que jamais stratégique aussi bien pour les PME que pour les grands groupes. La quantité de données traitée dans ce domaine, les exigences de qualité et de fraîcheur, la nécessité de croiser ces données pour déduire des nouvelles informations et indicateurs, posent plusieurs problèmes pour lesquels l'optimisation en général et l'optimisation combinatoire en particulier peuvent apporter des solutions efficaces. Dans cette thèse, nous utilisons l'optimisation combinatoire, l'algorithmique du texte et la théorie des graphes pour résoudre efficacement des problèmes issus du domaine de la connaissance inter-entreprises et posés par Altares D&B. Dans un premier temps, nous nous intéressons à la qualité de la base de données des dirigeants. Ce problème combine la détection et suppression des doublons dans une base de données et la détection d'erreurs dans une chaîne de caractères. Nous proposons une méthode de résolution basée sur la normalisation des données et l'algorithmique de texte et de comparaison syntaxique entre deux chaînes de caractères. Les résultats expérimentaux montrent non seulement que cette méthode est pertinente dans la détection et la suppression des doublons mais aussi qu'elle est efficace de point du vue temps de traitement. Nous nous focalisons par la suite sur les données des liens capitalistiques et nous considérons le problème de calcul des liens indirects et l'identification des têtes des groupes. Nous présentons une méthode de résolution basée sur la théorie des graphes. Nous testons cette méthode sur plusieurs instances réelles. Nous prouvons l'efficacité de cette méthode par son temps de traitement et par l'espace de calcul qu'elle utilise. Enfin, nous remarquons que le temps de calcul de celui-ci augmente de façon logarithmique en fonction de la taille d'instance. Enfin, nous considérons le problème de l'identification des réseaux d'influence. Nous formalisons ce problème en termes de graphes et nous le ramenons à un problème de partitionnement de graphe qui est NP-difficile dans ce cas général. Nous proposons alors une formulation en programme linéaire en nombre entier pour ce problème. Nous étudions le polyèdre associé et décrivons plusieurs classes de contraintes valides. Nous donnons des conditions nécessaires pour que ces contraintes définissent des facettes et discutons des algorithmes de séparations de ces contraintes. En utilisant les résultats polyédraux obtenus, nous développons un algorithme de coupes et branchements. Enfin, nous donnons quelques résultats expérimentaux qui montrent l'efficacité de notre algorithme de coupes et branchements
The inter-companies knowledge allows to every partner to learn about its customers, its suppliers and to develop its activity. Also this permits to limit the risk related to the creditworthiness, or the late payment of its partners. With the cash flow pressures, the need for growth and increased competition, this area becomes more strategic than ever, for both small (PME) and large groups. The amount of data processed in this domain, the requirements of quality and freshness, the need to cross these data to obtain new information and indicators, yield several optimization problems for which the recent techniques and computational tools can bring effective solutions. In this thesis, we use combinatorial optimization, text algorithms as well as graph theory to solve efficiently problems arising in the field of inter-companies knowledge. In particular, such problems was encountered in Altares D&B. First, we focus on the quality of the managers database. This problem combines the detection and removal of duplicates in a database, as well as the error detection in a string. We propose a method for solving this problem, based on data normalization, text algorithms and syntactic comparison between two strings. Our experimental results show that this method is relevant for the detection and removal of duplicates, and it is also very efficient in terms of processing time. In a second part of the thesis, we address a problem related to the data of ownership links. We compute the indirect links, and identify the group heads. We propose a method for solving this problem using graph theory and combinatorial optimization. We then perform a set of experiments on several real-world instances. The computational results show the effectiveness of our method in terms of CPU-time and resource allocation. In fact, the CPU time for computation increases logarithmically with the size of the instances. Finally, we consider the problem of identifying influence networks. We give a description of this problem in terms of graphs, and show that it can reduce to a graph partitioning problem. The latter is NP-hard. We then propose an integer linear programming formulation to model the problem. We investigate the associated polyhedron and describe several classes of valid inequalities. We give some necessaryand sufficient conditions for these inequalities to define facets of the considered polyhedron, and we discuss the related separation problems. Based on the obtained polyhedral results, we devise a Branch-and-Cut algorithm to solve the problem. Some numerical results are presented to show the efficiency of our algorithm

APA, Harvard, Vancouver, ISO, and other styles

7

Davot, Tom. "A la recherche de l’échafaudage parfait : efficace, de qualité et garanti." Thesis, Montpellier, 2020. http://www.theses.fr/2020MONTS030.

Full text

Abstract:

Le séquençage est un processus en biologie qui permet de déterminer l'ordre des nucléotides au sein de la molécule d'ADN. Le séquençage produit un ensemble de fragments, appelés lectures, dans lesquels l'information génétique est connue. Seulement, la séquence génomique n'est connue que de façon parcellaire, pour pouvoir faire son analyse, il convient alors de la reconstituer à l'aide d'un certain nombre de traitements informatiques. Dans cette thèse, nous avons étudié deux problèmes mathématiques issus de ce séquençage : l'échafaudage et la linéarisation.L'échafaudage est un processus qui intervient après l'assemblage des lectures en contigs. Il consiste en la recherche de chemins et de cycles dans un graphe particulier appelé graphe d'échafaudage. Ces chemins et cycles représentent les chromosomes linéaires et circulaires de l'organisme dont l'ADN a été séquencée. La linéarisation est un problème annexe à l'échafaudage : quand on prend en compte le fait que les contigs puissent apparaitre plusieurs fois dans la séquence génomique, des ambiguïtés surviennent dans le calcul d'une solution. Celles-ci, si elles ne sont pas traitées, peuvent entrainer la production d'une séquence chimérique lors de l'échafaudage. Pour résoudre ce problème, il convient alors de dégrader de façon parcimonieuse une solution calculée par l'échafaudage. Dans tous les cas, ces deux problèmes peuvent être modélisés comme des problèmes d'optimisation dans un graphe.Dans ce document, nous ferons l'étude de ces deux problèmes en se concentrant sur trois axes. Le premier axe consiste à classifier ces problèmes au sens de la complexité. Le deuxième axe porte sur le développement d'algorithmes, exacts ou approchés, pour résoudre ces problèmes. Enfin, le dernier axe consiste à implémenter et tester ces algorithmes pour observer leurs comportements sur des instances réelles
Sequencing is a process in biology that determines the order of nucleotides in the DNA. It produces a set of fragments, called reads, in which the genetic information is known. Unfortunatly, the genomic sequence is decomposed in small pieces. In order to analyse it, it is necessary to reconstruct it using a number of computer processes. In this thesis, we studied two mathematical problems arising from this sequencing: the scaffolding and the linearization.The scaffolding is a process that takes place after the reads assembly into larger subsequences called contigs. It consists in the search of paths and cycles in a particular graph called scaffold graph. These paths and cycles represent the linear and circular chromosomes of the organism whose DNA has been sequenced. The linearization is a problem related to the scaffolding. When we take into account that contigs may appear several times in the genomic sequence, some ambiguities can arise. If this ambiguities are not deleted, then a chimeric sequence may be produced by the scaffolding. To solve this problem, a solution computed by the scaffolding should be wisely deteriorated. In any case, both problems can be modelized as optimization problems in a graph.In this document, we study both problems focusing on three aspects. The first aspect consists in the study of the complexity of these problems. The second aspect consists in the development of algorithms, exact or approximate, to solve these problems. Finally, the last aspect consists in implementing and testing these algorithms to look at their behaviors on real instances

APA, Harvard, Vancouver, ISO, and other styles

8

Le, Gonidec Marion. "Sur la complexité des mots q∞-automatiques." Aix-Marseille 2, 2006. http://theses.univ-amu.fr.lama.univ-amu.fr/2006AIX22080.pdf.

Full text

Abstract:

L’objet de cette thèse est l’étude de mots infinis, à valeurs dans un alphabet fini, engendrés par des q-automates dont l’ensemble des états est dénombrable (q est un nombre entier supérieur ou égal à 2). Ces mots, appelés mots q∞-automatiques, sont les images par morphismes « admissibles » de points fixes de substitutions de longueur constante sur un alphabet dénombrable et peuvent être perçus comme une généralisation des mots automatiques. Nous montrons que la fonction de complexité p du mot (2d)∞-automatique engendré par l’automate associé à la marche aléatoire régulière dans Zd vérifie p(n) = O(n logd+1 2d n). Lorsque d = 1, on montre que la fonction n log2 2 n est un équivalent de la fonction de complexité. Nous verrons également que l’on peut généraliser cette majoration de l’ordre de grandeur de la fonction de complexité aux mots q∞-automatiques engendrés par les automates associé aux marches aléatoires moins régulières dans Zd par la relation p(n) = O(n logq+1 q n). Dans le cadre plus général des mots q∞-automatiques engendrés par des automates de degré borné, nous montrons que la fonction de complexité est au plus polynomiale. Nous verrons, sur des exemples, comment améliorer ce résultat pour obtenir une majoration plus fine de l’ordre de grandeur de la fonction de complexité. Sur un exemple, associé au langage de Dyck sur deux types de parenthèses, on obtient même l’ordre de croissance exact de la complexité. Nous donnons également un résultat de majoration polynomiale de l’ordre de grandeur de la fonction de complexité pour les mots q∞-automatiques engendrés par des automates monotones
In this thesis, we study a class of infinite words on a finite alphabet, generated by q-automata with countable states set, for an integer q ≥ 2. Those words, called q∞-automatic words are images by some « admissibles » morphisms of fixed points of substitutions of constant length q over countable alphabets. In this sense, thoses words can be viewed as a generalisation of automatic words. We show that the complexity function p of the (2d)∞-automatic word generated by the automaton related to regular random walk on Zd satisfies p(n) = O(n logd+1 2d n). Mo-reover, in the one-dimension case, the function n log2 2 n is an equivalent of the complexity function. This result can be generalized to q∞-automatic words generated by automata related to more general random walks on Zd by the relation p(n) = O(n logq+1 q n). In the more general case of q∞-automatic words generated by bounded degree auto- mata, we prouve that the complexity function is at most a polynomial function. We show how this result can be improved on examples, to obtain a thiner majoration of the com- plexity function order of growth. Moreover, on one exemple related to the Dyck language over two types of parenthesis, we obtain the exact complexity function order of growth. We also give a polynomial majoration of the complexity function for q∞-automatic words generated by monotone automata

APA, Harvard, Vancouver, ISO, and other styles

9

Jost, Vincent. "Ordonnancement chromatique : polyèdres, complexité et classification." Université Joseph Fourier (Grenoble), 2006. http://www.theses.fr/2006GRE10158.

Full text

Abstract:

La coloration des graphes permet de modéliser certaines applications de la recherche opérationnelle. Souvent, le problème classique de la coloration minimum n'est pas assez souple pour exprimer les. . Contraintes qui apparaissent naturellement dans les applications. Certains des raffinements nécessaires sont déjà connus dans la théorie de l'ordonnancement. Cela mène à des formulations hybrides regroupées sous le terme "ordonnancement chromatique". Ces contraintes mènent à des problèmes comme la « coloration bornée », « l'extension pré-colorée» ou la « max-coloration ». Nous construisons de nouvelles bornes inférieures pour la valeur optimum de ces problèmes de minimisation. Les résultats principaux montrent que ces bornes inférieures donnent des formules min-max et mènent à des algorithmes efficaces dans des sous-classes de graphes parfaits. C'est en particulier le cas pour les compléments de graphes d'intervalles (fondamentaux dans les problèmes de production et de transport) ou les line-graphes de bipartis (fondamentaux dans les problèmes d'emploi du temps). Ces problèmes d'ordonnancement chromatique sont souvent NP-difficiles même dans les graphes bipartis (et donc dans les graphes parfaits). En fonction du problème et de la classe de graphe à laquelle on s'intéresse, nous avons tenté de tracer les frontières entre les cas polynomiaux, les cas NP-difficiles et les cas où la borne inférieure proposée donne une formule min-max. Ceci permet de résumer les principaux résultats connus et d'orienter les recherches pour trouver des bornes inférieures plus générales ainsi que des algorithmes ayant un bon rapport d'approximation
Some problems in operations research can be modelled as graph colouring problems. Often however, the classical problem of minimum colouring is not able to express some additional constraints that naturally appear in applied contexts. On the other hand, some of these constraints are weil known in scheduling theory. The scope of "chromatic scheduling" is to deal with these hybrid models. This includes problems such as "bounded colouring", "precolouring extension" or "max colouring". We provide new lower bounds for the optimum value of these minimization problems. The main results state that these lower bounds yield min-max formulas in subclasses of perfect graphs. Ln particular, we obtain min-max formulas and efficient algorithms for complement of interval graphs (which are fundamental in transport and production problems) and line-graphs of bipartite graphs (fundamental in timetabling problems). These chromatic scheduling problems are often NP-hard even for bipartite graphs (and therefore for perfect graphs). Depending on the problem and the graph class to which we restrict, we tried to draw the frontiers between polynomial cases, NP-hard cases and those cases for which the lower bound is tight. This allows to summarize the main known results and to design some more generallower bounds as weil as approximation alaorithms with aood Derformance ratios

APA, Harvard, Vancouver, ISO, and other styles

10

Madelaine, Florent. "Problèmes de satisfaction de contraintes : une étude logique et combinatoire." Caen, 2003. http://www.theses.fr/2003CAEN2005.

Full text

Abstract:

Feder et Vardi ont prouvé que la classe capturée par un fragment monadique de la logique du second ordre existentiel, MMSPN, est calculatoirement équivalente (via des réductions probabilistes) à la classe des problèmes de satisfaction de contraintes (CSP), mais que la seconde est strictement incluse dans la première. Je caractérise exactement cetteinclusion. J'introduis les problèmes de motifs interdits (FP) qui correspondent exactement à MMSNP et développe des outils algébriques originaux comme le recoloriage qui permettent de définir une forme normale et conduisent à une preuve de nature constructive : soit le problème donné est transformé en un problème de CSP, soit des contre-exemples sont construits. Je contraste par ailleurs ce résultat avec un résultat récent, dû à Tardif et Nesetril qui utilise une correspondance entre dualité et densité que je généralise par ailleurs à FP. Finalement, je considère les problèmes de contraintes dans le cas de fonctions unaires.

APA, Harvard, Vancouver, ISO, and other styles

11

Le, Bodic Pierre. "Variantes non standards de problèmes d'optimisation combinatoire." Thesis, Paris 11, 2012. http://www.theses.fr/2012PA112190.

Full text

Abstract:

Cette thèse est composée de deux parties, chacune portant sur un sous-domaine de l'optimisation combinatoire a priori distant de l'autre. Le premier thème de recherche abordé est la programmation biniveau stochastique. Se cachent derrière ce terme deux sujets de recherche relativement peu étudiés conjointement, à savoir d'un côté la programmation stochastique, et de l'autre la programmation biniveau. La programmation mathématique (PM) regroupe un ensemble de méthodes de modélisation et de résolution, pouvant être utilisées pour traiter des problèmes pratiques que se posent des décideurs. La programmation stochastique et la programmation biniveau sont deux sous-domaines de la PM, permettant chacun de modéliser un aspect particulier de ces problèmes pratiques. Nous élaborons un modèle mathématique issu d'un problème appliqué, où les aspects biniveau et stochastique sont tous deux sollicités, puis procédons à une série de transformations du modèle. Une méthode de résolution est proposée pour le PM résultant. Nous démontrons alors théoriquement et vérifions expérimentalement la convergence de cette méthode. Cet algorithme peut être utilisé pour résoudre d'autres programmes biniveaux que celui qui est proposé.Le second thème de recherche de cette thèse s'intitule "problèmes de coupe et de couverture partielles dans les graphes". Les problèmes de coupe et de couverture sont parmi les problèmes de graphe les plus étudiés du point de vue complexité et algorithmique. Nous considérons certains de ces problèmes dans une variante partielle, c'est-à-dire que la propriété de coupe ou de couverture dont il est question doit être vérifiée partiellement, selon un paramètre donné, et non plus complètement comme c'est le cas pour les problèmes originels. Précisément, les problèmes étudiés sont le problème de multicoupe partielle, de coupe multiterminale partielle, et de l'ensemble dominant partiel. Les versions sommets des ces problèmes sont également considérés. Notons que les problèmes en variante partielle généralisent les problèmes non partiels. Nous donnons des algorithmes exacts lorsque cela est possible, prouvons la NP-difficulté de certaines variantes, et fournissons des algorithmes approchés dans des cas assez généraux
This thesis is composed of two parts, each part belonging to a sub-domain of combinatorial optimization a priori distant from the other. The first research subject is stochastic bilevel programming. This term regroups two research subject rarely studied together, namely stochastic programming on the one hand, and bilevel programming on the other hand. Mathematical Programming (MP) is a set of modelisation and resolution methods, that can be used to tackle practical problems and help take decisions. Stochastic programming and bilevel programming are two sub-domains of MP, each one of them being able to model a specific aspect of these practical problems. Starting from a practical problem, we design a mathematical model where the bilevel and stochastic aspects are used together, then apply a series of transformations to this model. A resolution method is proposed for the resulting MP. We then theoretically prove and numerically verify that this method converges. This algorithm can be used to solve other bilevel programs than the ones we study.The second research subject in this thesis is called "partial cut and cover problems in graphs". Cut and cover problems are among the most studied from the complexity and algorithmical point of view. We consider some of these problems in a partial variant, which means that the cut or cover property that is looked into must be verified partially, according to a given parameter, and not completely, as it was the case with the original problems. More precisely, the problems that we study are the partial multicut, the partial multiterminal cut, and the partial dominating set. Versions of these problems were vertices are

APA, Harvard, Vancouver, ISO, and other styles

12

Afif, Mohammed. "Approches algorithmiques pour la résolution de certains problèmes NP-Complets." Paris 9, 1999. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1999PA090026.

Full text

Abstract:

L'objet de cette thèse est de présenter de nouvelles approches de résolution de certains problèmes combinatoires de la classe NP-Complet. Ces approches sont représentées par des algorithmes efficaces basés sur des métaphores physiques ou sur des modèles qui se caractérisent par des solutions non combinatoires. Dans la première partie nous définirons les problèmes combinatoires traites, et les modèles mathématiques que nous avons défini pour les étudier. Nous avons aussi, pour chacun des problèmes étudiés, défini les algorithmes classiques de résolution optimale et approchée, ainsi que les méthodes et les heuristiques proposées. Dans la seconde partie, nous avons illustré par une étude expérimentale et comparative, les performances ainsi que les lacunes des différents algorithmes présentés

APA, Harvard, Vancouver, ISO, and other styles

13

Tourniaire, Emeric. "Problèmes NP-difficiles : approximation modérément exponentielle et complexité paramétrique." Phd thesis, Université Paris Dauphine - Paris IX, 2013. http://tel.archives-ouvertes.fr/tel-00874599.

Full text

Abstract:

Nous détaillons dans cette thèse des algorithmes modérément exponentiels pour l'approximation du problème MAX SAT. Nous discutons d'une méthode générique pour la conception d'algorithmes exponentiels réalisant des schémas d'approximation dans un cadre plus général. Enfin, nous présentons des résultats paramétrés pour des problèmes de coupe à cardinalité contrainte.

APA, Harvard, Vancouver, ISO, and other styles

14

Kovalev, Sergey. "PROBLÈMES COMBINATOIRES EN CONFIGURATION DES LIGNES DE FABRICATION : ANALYSE DE COMPLEXITÉ ET OPTIMISATION." Phd thesis, Ecole Nationale Supérieure des Mines de Saint-Etienne, 2012. http://tel.archives-ouvertes.fr/tel-00849179.

Full text

Abstract:

L'objectif de la thèse est de créer et développer de nouvelles méthodes de résolution efficaces des problèmes combinatoires en configuration des lignes de fabrication. Deux problèmes ont été particulièrement étudiés: le problème d'équilibrage et de choix d'équipement pour des lignes dédiées et le problème de minimisation des coûts de changements de séries pour des lignes multi-produits. Une solution du premier problème consiste en une affectation admissible des ressources à un nombre de stations à déterminer de sorte que le coût total soit minimal. Afin de résoudre ce problème, nous l'avons réduit au problème de partition d'ensemble et l'avons résolu par des heuristiques gloutonnes et une méthode exacte de génération de contraintes. Les expérimentations sur différentes instances ont montré que la nouvelle approche de résolution surclasse les approches antérieures de la littérature en termes de qualité de solution et de temps de calcul. Pour le second problème deux critères sont considérés lexicographiquement : la minimisation du nombre de stations et la minimisation du coût de changement de séries. Nous avons examiné successivement les cas d'exécution parallèle et séquentielle des opérations. Des solutions approchées ont été trouvées par des heuristiques gloutonnes. Ensuite, nous avons proposé deux modèles de programmation linéaire en nombres entiers (PLNE) afin de trouver le nombre de stations minimal et ensuite d'obtenir le coût de changement de séries minimal. Les résultats des expérimentations sur ces nouveaux problèmes se sont avérés prometteurs à la fois en termes de qualité de solution et de temps de calcul.

APA, Harvard, Vancouver, ISO, and other styles

15

Labbé, Sébastien. "Structure des pavages, droites discrètes 3D et combinatoire des mots." Thèse, Paris 7, 2012. http://www.archipel.uqam.ca/4940/1/D2363.pdf.

Full text

Abstract:

Cette thèse, constituée d'une série d'articles, considère des questions issues de la géométrie discrète en les traitant du point de vue de la combinatoire des mots qui s'avère un outil puissant et approprié pour les résoudre. Nous utilisons les mots soit pour représenter un chemin dans Z2 ou Z3, soit pour coder la suite des virages d'un chemin ou le contour d'une figure discrète fermée. Parmi les thèmes abordés, on compte les pavages du plan par polyominos, la notion de complexité en facteurs palindromes et la génération de droites discrètes 3D. La première partie concerne les pavages du plan où nous étudions le nombre de pavages réguliers du plan par une tuile carrée, c'est-à-dire une tuile ayant quatre tuiles adjacentes identiques. Il s'avère que certaines tuiles carrées pavent le plan de deux façons distinctes et elles sont appelées doubles carrées. Nous démontrons d'abord qu'il y a au plus deux tels pavages réguliers par une tuile carrée. Ensuite, nous considérons deux familles particulières de tuiles doubles carrées : les tuiles de Christoffel et les tuiles de Fibonacci. Ces deux familles décrivent les plus petits exemples de tuiles doubles carrées et peuvent être définies à partir des mots de Christoffel et du mot de Fibonacci par des règles de substitution et de concaténation. Les tuiles de Fibonacci définissent aussi une fractale, obtenue par un chemin auto-évitant, dont nous avons calculé plusieurs statistiques, comme le rapport de l'aire de la fractale sur l'aire de son enveloppe convexe. Dans l'article suivant, nous démontrons que tout double carré indécomposable est invariant sous une rotation de 180 degrés. Cette propriété géométrique est équivalente au fait que le mot de contour de la tuile se factorise en un produit de palindromes. Notre preuve repose sur une méthode de génération exhaustive des tuiles doubles carrées. La deuxième partie concerne la complexité palindromique - le nombre de facteurs palindromes distincts -, un sujet propre à la combinatoire des mots. Nous y considérons quatre classes de complexité palindromique qui découlent naturellement de la notion de défaut. Nous caractérisons notamment les mots de complexité palindromique minimale sur un alphabet à deux lettres et nous démontrons que les mots infinis obtenus par codage de rotations sur deux intervalles atteignent la complexité palindromique maximale. Dans une troisième partie, nous proposons une méthode basée sur des algorithmes de fractions continues multidimensionnelles pour la génération de droite discrètes 3D 6-connexes. Les expérimentations illustrent que la complexité en facteurs des mots ainsi générés serait linéaire. Cela se compare avantageusement aux autres définitions de droites discrètes 3D 6-connexes dont la complexité en facteurs est quadratique. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : combinatoire des mots, géométrie discrète, pavage, polyomino, complexité palindromique, droite discrète, algorithme de fractions continues multidimensionnelles.

APA, Harvard, Vancouver, ISO, and other styles

16

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 text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

17

Lavallée, Ivan. "Contribution à l'algoritmique parallèle et distribuée : application à l'optimisation combinatoire." Paris 11, 1986. http://www.theses.fr/1986PA112275.

Full text

Abstract:

Cette thèse est divisée en trois parties : la première partie, précédée d'un chapitre 0 qui précise et justifie vocabulaire et notations, est composée de deux chapitres I et II, qui traitent du problème de la terminaison distribuée, apprentissage et détection, l'idée maîtresse étant celle de "mot circulant" qui généralise le concept de jeton circulant. Le mot circulant permettant un apprentissage de propriétés de l'algorithme distribué étudié. Le chapitre II fournit de plus un algorithme distribué d'identification des circuits élémentaires d'un graphe. La deuxième partie est consacrée à l'étude de trois grands problèmes combinatoires tels que : La recherche des plus courts chemins dans un graphe valué, pour la résolution duquel nous réutilisons des concepts du chapitre II et pour lequel l'algorithme distribué que nous construisons se distingue des autres algorithmes connus par sa totale asynchronicité. (Chapitre III). La recherche d'un arbre couvrant (chapitre IV) pour laquelle, en allant à contrario de quelques idées établies sur la question, on donne un algorithme distribué totalement asynchrone, minimisant le nombre de messages échangés, et ce, malgré des hypothèses moins restrictives (en particulier, nous admettons la possibilité d'arêtes équipondérées) que les autres algorithmes distribués élaborés pour ce faire. L'énumération implicite parallèle (chapitre V) pour laquelle on fait apparaître, en environnement parallèle, des phénomènes nouveaux, en particulier à propos des gains de performance en temps, qui tranchent avec quelques idées largement répandues. Pour ces trois chapitres, nous donnons la particularisation à un environnement parallèle type machine à mémoire partagée (PRAM), et pour les chapitres III et V, nous donnons, en annexe, les programmes, jeux d'essais et résultats de tests sur CRAY. La troisième partie, tirant les enseignements théoriques des deux précédentes, essaie de donner une définition du concept d'algorithme parallèle et distribuée qui soit cohérente avec ce qui se fait en séquentiel, et qui permette une évaluation et une comparaison des algorithmes parallèles ou distribués (chapitre VI). Le, tri, fusion, et le problème de l'arbre couvrant minimum du chapitre VII est une application du modèle du chapitre VI à quatre problèmes; recherche du maximum IV.

APA, Harvard, Vancouver, ISO, and other styles

18

Nakache, Elie. "Chemin optimal, conception et amélioration de réseaux sous contrainte de distance." Thesis, Aix-Marseille, 2016. http://www.theses.fr/2016AIXM4023/document.

Full text

Abstract:

Cette thèse porte sur différents problèmes d'optimisation combinatoire dont nous avons caractérisé la difficulté en décrivant des réductions et des algorithmes polynomiaux exacts ou approchés.En particulier, nous étudions le problème de trouver, dans un graphe orienté sans cycle dont les sommets sont étiquetés, un chemin qui passe par un maximum d'étiquettes différentes. Nous établissons qu'il n'existe pas d'algorithme polynomial avec un facteur constant pour ce problème. Nous présentons aussi un schéma qui permet d'obtenir, pour tout $epsilon >0$, un algorithme polynomial qui calcule un chemin collectant $ O(OPT^{1-epsilon})$ étiquettes.Nous étudions ensuite des variantes du problème de l'arbre couvrant de poids minimum auquel nous ajoutons des contraintes de distance et d'intermédiarité. Nous prouvons que certaines variantes se résolvent en temps polynomial comme des problèmes de calcul d'un libre de poids minimum commun à deux matroïdes. Pour une autre variante, nous présentons un algorithme d'approximation facteur 2 et nous prouvons qu'il n'existe pas d'algorithme polynomial avec un meilleur facteur constant.Enfin, nous étudions un problème d'améliorations de réseaux du point de vue du partage des coûts. Nous montrons que la fonction de coût associée à ce problème est sous-modulaire et nous utilisons ce résultat pour déduire un mécanisme de partage des coûts qui possède plusieurs bonnes propriétés
In this thesis, we investigate several combinatorial optimization problems and characterize their computational complexity and approximability by providing polynomial reductions and exact or approximation algorithms.In particular, we study the problem of finding, in a vertex-labeled directed acyclic graph, a path collecting a maximum number of distinct labels. We prove that no polynomial time constant factor approximation algorithm exists for this problem. Furthermore, we describe a scheme that produces, for any $epsilon >0$, a polynomial time algorithm that computes a solution collecting $O(OPT^{1-epsilon})$ labels. Then, we study several variants of the minimum cost spanning tree problem that take into account distance and betweenness constraints. We prove that most of these problems can be solved in polynomial time using a reduction to the weighted matroid intersection problem. For an other problem, we give a factor 2 approximation algorithm and prove the optimality of this ratio.Finally, we study a network improvement problem from a cost sharing perspective. We establish that the cost function corresponding to this problem is submodular and use this result to derive a cost sharing mechanism having several good properties

APA, Harvard, Vancouver, ISO, and other styles

19

Rouat, Valérie. "Validité de l'approche classification dans la réduction statistique de la complexité de #SAT." Rennes 1, 1999. http://www.theses.fr/1999REN10021.

Full text

Abstract:

Le problème abordé dans cette thèse est celui du dénombrement des solutions du problème de la satisfiabilité d'une formule booléenne sous forme normale conjonctive (problème #SAT). Ce problème est #P-complet et les résultats actuels montrent que la résolution de #SAT, même approchée, est, dans le pire des cas, exponentielle en temps. Notre approche utilise une algorithmique issue de l'analyse combinatoire des données et s'appuie sur une représentation ensembliste, géométrique et logique des clauses définies par une bijection entre clauses et sous-ensemble de l'ensemble des interprétations. Une telle représentation permet une vision synthétique du problème #SAT et la prise en compte de caractéristiques statistiques globales de l'instance. En appliquant le principe général "diviser pour résoudre", la méthode de résolution approchée de #SAT que nous proposons permet de réduire de facon considérable la complexité algorithmique du problème. Elle est basée sur la segmentation d'une sériation établie sur la table d'incidence associée à la formule. Nous montrons, dans le cas difficile des instances SAT aléatoires, l'intérêt de la sériation et de sa meilleure coupure en deux parties connexes et de tailles comparables. De plus, nous définissons la notion d'indépendance en probabilité entre clauses et entre ensembles de clauses. La méthode proposée est validée à la fois théoriquement et par une vaste expérimentation. Par ailleurs, nous nous intéressons à la distribution de probabilité du nombre de solutions d'une instance kSAT aléatoire. L'espérance et la variance du nombre de solutions sont connues, nous montrons en utilisant des tests statistiques que la distribution suit une loi log-normale.

APA, Harvard, Vancouver, ISO, and other styles

20

Blind, Sarah. "Output-sensitive algorithms for enumeration problems in graphs." Electronic Thesis or Diss., Université de Lorraine, 2019. http://www.theses.fr/2019LORR0323.

Full text

Abstract:

Cette thèse est une étude, d’un point de vue algorithmique, de la complexité de la résolution de certains problèmes d’énumération dans les graphes. Les algorithmes pour les problèmes d’énumération ont pour but la production de toutes les solutions d’un problème combinatoire, et ce sans répétition. Comme il existe un nombre potentiellement exponentiel de solutions à générer, différentes approches pour analyser la performance de ces algorithmes ont été développées: l’approche "input-sensitive" et l’approche "output-sensitive". La première est une mesure de la complexité basée sur la taille de l’entrée, elle consiste en l’analyse du temps total nécessaire à l’énumération des objets. La seconde est une mesure basée sur la taille de l’entrée et de la sortie. Nous nous intéresserons ici à l’approche output-sensitive et nous accorderons une attention particulière à la notion de délai, i.e., le temps nécessaire entre la production de deux solutions consécutives. La thèse est divisée en deux parties indépendantes. Dans la première, nous proposons un cadre général qui permet d’étudier l’énumération d’ensembles de sommets d’un graphe respectant une certaine propriété. Nous prouvons que lorsqu’une telle propriété peut être définie localement par rapport à un certain ordre sur l’ensemble des sommets du graphe, alors les ensembles de sommets respectant cette propriété peuvent être énumérés avec un délai linéaire. Notre méthode consiste à réduire le problème d’énumération considéré à l’énumération de chemins dans les graphes acycliques dirigés. Nous appliquons cette méthode générale pour énumérer avec un délai linéaire les ensembles dominants connexes minimaux et les ensembles irredondants maximaux dans les graphes d’intervalles et dans les graphes de permutation, ainsi que les ensembles irredondants maximaux dans les graphes arc-circulaires et dans les graphes permutation-circulaires. La deuxième partie de la thèse est consacrée à l’étude des orientations k-arc-connexes. Il s’agit d’orientations pour lesquelles il est nécessaire de supprimer au moins k arcs pour détruire la forte connexité. Nous présentons d’abord un algorithme simple pour énumérer les orientations k-arc-connexes respectant une séquence de degrés sortants. Ensuite nous présentons un algorithme simple pour énumérer les séquences de degrés sortants pour lesquelles il existe une orientation k-arc-connexe. En combinant ces deux algorithmes, nous obtenons un algorithme qui énumère toutes les orientations k-arc-connexes d’un graphe avec un délai de O(knm²) et un temps amorti de O(m²)
This thesis is a study, from an algorithmic point of view, of the complexity of solving some enumeration problems in graphs. Algorithms for enumeration problems are meant to produce all solutions of a combinatorial problem, without repetition. Because there is a potentially exponential number of solutions to be generated, different approaches to analyse the performance of those algorithms have been developed: the input-sensitive approach and the output-sensitive approach. The first is a measure of the complexity that is based on the size of the input, and which consists in analysing the total time needed to enumerate the objects. The second is a measure based on the size of the input and the output. Here we will be interested in an output-sensitive approach and we will pay special attention to the notion of delay, i.e., the time needed between the production of two consecutive solutions. The thesis is divided into two independent parts. In the first one we propose a general framework that allows for the study of enumeration of vertex set properties in graphs. We prove that when such a property is locally definable with respect to some order on the set of vertices, then it can be enumerated with linear delay. Our method is a reduction of the considered enumeration problem to the enumeration of paths in directed acyclic graphs. We apply this general method to enumerate with linear delay minimal connected dominating sets and maximal irredundant sets in interval graphs and in permutation graphs, as well as maximal irredundant sets in circular-arc graphs and in circular-permutation graphs. The second part of the thesis is dedicated to the study of k-arc-connected orientations. These are orientations for which at least k arcs have to be removed in order to destroy the strong connectivity. We first give a simple algorithm to enumerate the k-arc-connected orientations respecting some fix outdegree sequence. We then give a simple algorithm to enumerate the outdegree sequences attained by k-arc-connected orientations. Combining both yields an algorithm that enumerates all k-arc-connected orientations of a graph in delay O(knm²) and amortized time O(m²)

APA, Harvard, Vancouver, ISO, and other styles

21

Watel, Dimitri. "Approximation de l'arborescence de Steiner." Thesis, Versailles-St Quentin en Yvelines, 2014. http://www.theses.fr/2014VERS0025/document.

Full text

Abstract:

Dans un graphe orienté contenant un nœud appelé racine, un sous ensemble de nœuds appelés terminaux et une pondération sur les arcs, le problème de l’arborescence de Steiner (DST) consiste en la recherche d’une arborescence de poids minimum contenant pour chaque terminal un chemin de la racine vers ce terminal. Ce problème est NP-Complet. Cette thèse se penche sur l’étude de l’approximabilité de ce problème. Sauf si P=NP, il n’existe pas pour ce problème d’approximation de rapport constant ou logarithmique en k, oú k est le nombre de terminaux. Le plus petit rapport d’approximation connu est O (k") où " est un réel strictement positif. Dans la première partie, nous donnons trois algorithmes d’approximation : un algorithme glouton efficace qui associe deux techniques d’approximations connues pour DST, un algorithme dans le cas des graphes structurés en paliers qui étudie l’approximabilité du problème quand les terminaux sont éloignés de la racine, et un algorithme exponentiel qui combine un algorithme d’approximation et un algorithme exact, dont le rapport d’approximation et la complexité temporelle sont paramétrés par le nombre de terminaux couverts par l’algorithme exact. Dans la seconde partie, nous étudions deux problèmes issus de DST auquel est ajoutée une contrainte sur les nœuds de branchement. Cette contrainte réduit le nombre de solutions réalisables et peut faciliter la recherche d’une solution optimale parmi ce sous-ensemble de solutions. En fonction de la contrainte, nous étudions la possibilité de la trouver en temps polynomial et quel est le rapport d’approximation entre cette solution et la solution du problème non contraint
The directed Steiner tree problem (DST) asks, considering a directed weighted graph, a node r called root and a set of nodes X called terminals, for a minimum cost directed tree rooted in r spanning X. DST is an NP-complete problem. We are interested in the search for polynomial approximations for DST. Unless P = NP, DST can not be approximated neither within a constant ratio nor a logarithmic ratio with respected to k, where k is the number of terminals. The smallest known approximation ratio is O(kԑ)$ where ԑ is a positive real.In the first part, we provide three new approximation algorithms : a practical greedy algorithm merging two of the main approximation techniques for DST, an algorithm for the case where the graph is layered and where the distance between the terminals and the root is high, and an exponential approximation algorithm combining an approximation algorithm and an exact algorithm, parameterized with the number of terminals the exact algorithm must cover.In the last part we study DST with two branching constraints. With this technique, we are able to reduce the number of feasible solutions, and possibly facilitate the search for an optimal solution of the constraint problem. We study how it is possible to build such a solution in polynomial time and if this solution is a good approximation of an optimal solution of the non-constraint problem

APA, Harvard, Vancouver, ISO, and other styles

22

Grebinski, Vladimir. "Recherche combinatoire : problèmes de pesage, reconstruction de graphes et applications." Nancy 1, 1998. http://www.theses.fr/1998NAN10248.

Full text

Abstract:

La recherche combinatoire est une branche de l'algorithmique combinatoire qui est étroitement liée avec d'autres domaines des mathématiques et de l'informatique, tels que l'étude de la complexité d'algorithmes, la théorie des graphes, la théorie des nombres, la théorie des ensembles extrémaux. En termes très généraux, la recherche combinatoire étudié les problèmes d'identification d'un objet inconnu dans un ensemble d'objets à l'aide de questions indirectes sur cet objet. Les méthodes de la recherche combinatoire trouvent de nombreuses applications pratiques dans les domaines de la biologie, la médecine, la conception de réseaux, et d'autres. Le thème central de la thèse est le modèle additif en recherche combinatoire. Nous étudions la puissance de ce modèle en l'appliquant à quelques problèmes classiques de recherche combinatoire. Trois familles de problèmes sont considérées : les problèmes de pesage de monnaies, le problème de reconstruction de graphes d'une classe donnée et le problème de reconstruction de partitions. Pour les problèmes de reconstruction de graphes et de pesage, nous examinons les résultats connus et démontrons de nouveaux résultats plus généraux. Un des résultats les plus importants est l'obtention d'une borne supérieure pour le problème de reconstruction de vecteurs à poids borné. Nous introduisons également le problème de reconstruction de partitions, pour lequel nous développons des algorithmes efficaces dont nous analysons la complexité

APA, Harvard, Vancouver, ISO, and other styles

23

Genitrini, Antoine. "Expressions booléennes aléatoires : probabilité, complexité et comparaison quantitative de logiques propositionnelles." Versailles-St Quentin en Yvelines, 2009. http://www.theses.fr/2009VERS0010.

Full text

Abstract:

A travers ma thèse, j'étudie des systèmes propositionnels d'un point de vue probabilité/complexité. Je commence par deux distributions de probabilité sur les fonctions Booléennes, induites par des expressions Booléennes construites avec le connecteur Implication. On donne la structure de la plupart des expressions représentant une fonction donnée, quand le nombre de variables tend vers l'infini. On obtient ainsi l'équivalent asymptotique de la probabilité de la fonction, dépendant de sa complexité. Via la fonction Vrai, on compare quantitativement les logiques classique et intuitionniste de l'implication. Cette comparaison met en évidence certaines propriétés d'une classe d'expressions, qui se retrouvent dans le système propositionnel complet : on compare alors les deux logiques dans ce système. Enfin on étudie les expressions équilibrées des deux systèmes, de l'implication et des deux connecteurs Et et Ou. Dans les deux cas, on exhibe la distribution de probabilité sur les fonctions
In this thesis, I am interested in propositional systems from a probability/complexity point of view. I begin with two probability distributions on Boolean functions, induced by the Boolean expressions built with the Implication connective. I obtain the structure of most of the expressions representing a given function, when the number of variables tends to infinity. This gives the asymptotic equivalent of the probability of the function, depending on its complexity. Via the function True, we compare quantitatively the intuitionistic and classical logics of implication. This comparison highlights some properties of a class of expressions, that are found also in the full propositional system, and we can compare the two logics in this system. Finally we study balanced expressions in the two systems built on implication, or on the two connectors And and Or. In both cases, we exhibit the probability distribution of the functions

APA, Harvard, Vancouver, ISO, and other styles

24

Gire, Sophie. "Arbres, permutations à motifs exclus et cartes planaires : quelques problèmes algorithmiques et combinatoires." Bordeaux 1, 1993. http://www.theses.fr/1993BOR10534.

Full text

Abstract:

Dans ce travail, nous nous interessons aux arbres en tant que structure de donnees dans divers algorithmes et en tant qu'outil pour la generation d'objets combinatoires. Dans une premiere partie, nous donnons des valeurs exactes pour le cout au pire (complexite amortie) de certaines transformations sur les arbres intervenant dans plusieurs algorithmes, comme l'algorithme de gestion de partitions et l'algorithme d'exclusion mutuelle de naimi et trehel. Dans la seconde partie, nous resolvons quelques problemes d'enumeration de permutations a motifs exclus par le biais de la caracterisation d'arbres de generations de ces objets par un systeme de reecriture. En particulier, nous etablissons une bijection entre les permutations triables par deux passages consecutifs dans une pile et les cartes planaires pointees non separables et en deduisons des formules d'enumeration pour ces permutations suivant plusieurs parametres

APA, Harvard, Vancouver, ISO, and other styles

25

Cabon, Bertrand. "Problèmes d'optimisation combinatoire : évaluation de méthodes de la physique statistique." Toulouse, ENSAE, 1996. http://www.theses.fr/1996ESAE0024.

Full text

Abstract:

Nous abordons dans cette thèse trois approches pour la résolution de problèmes combinatoires difficiles. Nous montrons comment les méthodes du Recuit Simulé et de l'Approximation de Champ Moyen, issues de la Physique Statistique, peuvent être utilisées pour résoudre des problèmes d'optimisation discrète. Nous présentons également, dans le cadre CSP (Constraint Satisfaction Problems), des méthodes exactes de résolution sur le principe du "Branch and Bound". Les comportements de ces approches sont comparés sur différents problèmes combinatoires difficiles tels que le recalage d'images satellites, le problème d'allocation de f'équences radio, ou des problèmes CSP aléatoires. Enfin, nous montrons comment la méthode du Champ Moyen peut accélérer une méthode de type Branch and Bound en lui fournissant une bonne affectation initiale et deux heuristiques d'ordonnancement des variables et des valeurs. Nous présentons des résultats expérimentaux sur des problèmes CSP générés aléatoirement.

APA, Harvard, Vancouver, ISO, and other styles

26

Bedaride, nicolas. "Etude du billard polyédral." Phd thesis, Université de la Méditerranée - Aix-Marseille II, 2005. http://tel.archives-ouvertes.fr/tel-00009363.

Full text

Abstract:

Dans cette thèse, on s'intéresse au billard dans un polyèdre. On étudie cette application, en codant les orbites sur un alphabet fini. On étudie alors deux problèmes: la complexité des mots infinis obtenus, et l'existence de trajectoires périodiques. On montre que la complexité est reliée à la notion de diagonale généralisée : une diagonale généralisée est une trajectoire de billard, qui part d'une arête et qui arrive à une arête. On obtient alors, au premier chapitre, une nouvelle preuve du calcul de la complexité d'une rotation du tore $\mathbb(T)^2$, totalement irrationnelle. Cette preuve permet de plus, d'obtenir une estimation de la complexité directionnelle du billard dans certains prismes droits. Au deuxième chapitre, on obtient, grâce aux diagonales généralisées, une estimation de la complexité globale du billard cubique. On donne alors au chapitre trois une estimation valable dans n'importe quel polyèdre convexe: On montre en fait que le billard est d'entropie topologique nulle. Le chapitre quatre traite alors du problème des orbites périodiques. On donne une condition suffisante, pour qu'un mot soit stable. On montre de plus l'existence d'une trajectoire périodique dans le tétraèdre régulier. Pour finir on s'intéresse, dans le chapitre cinq, à une sous classe d'échange de rectangles. On montre que ces applications sont ergodiques, et de complexité quadratique. Ces applications sont reliées au billard puisque, à direction fixée, l'application de premier retour est une application affine par morceaux.

APA, Harvard, Vancouver, ISO, and other styles

27

Milioris, Dimitrios. "Trend Detection and Information Propagation in Dynamic Social Networks." Palaiseau, Ecole polytechnique, 2015. https://tel.archives-ouvertes.fr/tel-01152275/document.

Full text

Abstract:

Au cours de la dernière décennie, la dissémination de l'information au travers des réseaux sociaux a augmenté de façon spectaculaire. L'analyse des interactions entre les utilisateurs de ces réseaux donne la possibilité de la prédiction en temps réel de l'évolution de l'information. L'étude des réseaux sociaux présentent de nombreux défis scientifiques, comme par exemple : (a) peut on trouver un compromis entre la qualité, l'autorité, la pertinence et l'actualité du contenu ? (b) Peut on utiliser les interactions entre les groupes d'utilisateurs pour révéler les utilisateurs influents, pour prédire les pics de trafic ? (c) la publicité, les spams, et autres trafics non pertinent peuvent ils être détectés et écartés ? Dans cette thèse, nous proposons une nouvelle méthode pour effectuer la détections dans les textes courts des sujets et des tendances, et leur classification. Au lieu de découper les textes en mots ou en n-grames comme le font la plupart des autres méthodes qui utilisent des sac-de- mots, nous introduisons la Complexité Jointe, qui est définie comme le cardinal de l'ensemble des facteurs communs distincts entre les deux textes, un facteur étant une chaîne de caractères consécutifs. L'ensemble des facteurs d'un texte est décomposé en temps linéaire en une structure efficace de mémoire appelée arbre suffixe et on obtient par le superposition des deux arbres, en temps moyen sous-linéaire, la complexité jointe des deux textes. La méthode a été largement testée à grande échelle pour des sources de texte de Markov d'ordre fini et permet en effet une bonne discrimination des sources (langue, etc). La simulation de la production des textes par processus de Markov est une approximation satisfaisante de la génération de textes en langage naturel. La méthode de la complexité jointe est indépendante de la langue agnostique puisque nous pouvons détecter les similitudes entre deux textes sans avoir recours à l'analyse sémantique. Elle ne nécessite pas une analyse sémantique sur la base d'une grammaire spécifique, par conséquent, il ne est pas nécessaire de construire un dictionnaire spécifique. La méthode proposée peut aussi être utilisé pour détecter un changement de thème dans une conversation, ainsi qu'un changement de style d'un écrivain dans un texte. Dans la deuxième partie de la thèse, nous profitons de la faible densité de l'espace des données, ce qui nous a motivé de façon naturelle à appliquer la théorie de Compressive Sensing extrapolée du problème de la localisation des objets physiques. Le Compressive Sensing stipule que les signaux qui sont rares ou compressibles peuvent être récupérés à partir d'un nombre très réduit de projections aléatoires incohérentes dans une base appropriée, contrairement aux méthodes traditionnelles dominées par la théorie classique de Nyquist-Shannon de l'échantillonnage. Grâce à la faible densité spatiale des sujets, nous appliquons la théorie pour récupérer un vecteur d'indicateur, à partir de l'ensemble des tweets. Le procédé fonctionne en conjonction avec un filtre de Kalman pour mettre à jour des états d'un système dynamique comme étape de raffinement. Dans cette thèse, nous exploitons des ensembles de données recueillies en utilisant le flux de l'API de Twitter, sur des tweets collectés en plusieurs langues et nous obtenons des résultats très prometteurs lorsque l'on compare ces méthodes au meilleur de l'existant
During the last decade, the information within Dynamic Social Networks has increased dramatically. The ability to study the interaction and communication between users in these networks can provide real time valuable prediction of the evolution of the information. The study of social networks has several research challenges, e. G. (a) real time search has to balance between quality, authority, relevance and timeliness of the content, (b) studying the information of the correlation between groups of users can reveal the influential ones, and predict media consumption, network and traffic resources, (c) detect spam and advertisements, since with the growth of social networks we also have a continuously growing amount of irrelevant information over the network. By extracting the relevant information from online social networks in real time, we can address these challenges. In this thesis a novel method to perform topic detection, classification and trend sensing in short texts is introduced. Instead of relying on words as most other existing methods which use bag-of-words or n-gram techniques, we introduce Joint Complexity, which is defined as the cardinality of a set of all distinct common factors, subsequences of characters, of two given strings. Each short sequence of text is decomposed in linear time into a memory efficient structure called Suffix Tree and by overlapping two trees, in linear or sublinear average time, we obtain the cardinality of factors that are common in both trees. The method has been extensively tested for Markov sources of any order for a finite alphabet and gave good approximation for text generation and language discrimination. The proposed method is language-agnostic since we can detect similarities between two texts in any loosely character-based language. It does not use semantics or based on a specific grammar, therefore there is no need to build any specific dictionary or stemming technique. The proposed method can be used to capture a change of topic within a conversation, as well as the style of a specific writer in a text. In the second part of the thesis, we take advantage of the nature of the data, which motivated us in a natural fashion to use of the theory of Compressive Sensing driven from the problem of target localization. Compressive Sensing states that signals which are sparse or compressible in a suitable transform basis can be recovered from a highly reduced number of incoherent random projections, in contrast to the traditional methods dominated by the well- established Nyquist-Shannon sampling theory. Based on the spatial nature of the data, we apply the theory of Compressive Sensing to perform topic classification by recovering an indicator vector, while reducing significantly the amount of information from tweets. The method works in conjunction with a Kalman filter to update the states of a dynamical system as a refinement step. In this thesis we exploit datasets collected by using the Twitter streaming API, gathering tweets in various languages and we obtain very promising results when comparing to state-of-the-art methods

APA, Harvard, Vancouver, ISO, and other styles

28

Dandrieux, Jean-Pierre. "Contributions à l'analyse de la complexité de problèmes de résolution de contraintes." Lille 1, 2000. https://pepite-depot.univ-lille.fr/RESTREINT/Th_Num/2000/50376-2000-210.pdf.

Full text

Abstract:

Tout d'abord par une etude theorique du phenomene de seuil dans 3sat, une categorie du probleme de satisfaction de contraintes booleennes, sous forme normale conjonctive (cnf), avec exactement 3 variables par clauses. Soit g le rapport entre le nombre de clauses et le nombre de variables, experimentallement on a decouvert un seuil brutal pour g appele g 0 (= 4. 25), tel que, quand le nombre de variables tend vers l'infini, la proportion des expressions satisfiables s'effondre de 1 a 0 quand g passe d'inferieur a superieur a g 0. Peu de proprietes relatives au seuil sont prouvees. Son existence meme reste a etablir. De plus 3sat semble np dur en moyenne seulement au seuil, l'analyse de l'algorithme de davis-puttnam montrant que le probleme est polynomial en moyenne. Apres avoir ameliore (de 4. 60 a 4. 58) la valeur du plus petit majorant existant pour g 0, nous montrons que les techniques utilisees ne permettraient plus d'ameliorations significatives. Ensuite, chez detexis service contre-mesures, par l'etude d'un probleme de resolution de contraintes booleennes : l'identification de menaces en territoire inconnu, un probleme d'optimisation multifactorielle, np-complet pour plusieurs parametres. Il illustre les difficultes de l'informatique, a exprimer un probleme, a le modeliser convenablement puis a le resoudre en un temps raisonnable. Description du probleme : il s'agit, a partir de donnees electromagnetiques recues et d'une base de donnees des signatures electromagnetiques des appareils connus, de reconstituer l'environnement et d'anticiper les actions des appareils reconnus. Ici la pratique est souvent pragmatique (utilisation de coefficients de confiance). Nous y avons esquisse une approche probabiliste. En particulier, dans un cas simple, nous montrons comment cette approche permet de substituer a des calculs exhaustifs durs un calcul des solutions les plus dangereuses base sur des methodes formelles.

APA, Harvard, Vancouver, ISO, and other styles

29

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 text

Abstract:

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
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

APA, Harvard, Vancouver, ISO, and other styles

30

Wojcik, Caius. "Factorisations des mots de basse complexité." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSE1340.

Full text

Abstract:

Nous présentons dans ce doctorat de mathématiques le travail effectué pendant trois ans à l'Université Claude Bernard Lyon 1. Ce doctorat a été réalisé sous les directions de Boris Adamczewski et Luca Zamboni, tous deux chercheurs à l'UCBL. Le thème général abordé est la combinatoire des mots, sous la forme de deux contributions, l'une concernant la théorie de Ramsey développée dans la première partie, et l'autre la classe des mots sturmiens développée dans la seconde partie. La combinatoire des mots est un domaine à la croisée des mathématiques, et plus généralement des sciences. Avec l'essor de l'informatique théorique, ou encore des progrès de la génétique, l'étude des suites de symboles est devenu un sujet de recherche incontournable à l'importance grandissante. Les mots vus comme suites de symboles sont en effet intrinsèquement soumis à des lois mathématiques d'une profonde subtilité. L'exemple historique d'Axel Thue d'un mot infini sans facteurs carrés sur un alphabet à trois lettres a été un des points de départ de cette théorie, via une construction non-triviale d'un mot infini soumis à une condition pourtant très simple en apparence. Que ce soit dans la structure des décimales des nombre réels, dans les codes informatiques omniprésents dans le fonctionnement des ordinateurs, ou dans notre propre code génétique, la combinatoire des mots fournit un cadre commun pour une étude en profondeur de problématiques actuelles. Le présent doctorat s'inscrit naturellement dans ce processus scientifique. Directement inspiré par les travaux fondateurs d'Axel Thue, nous étudions dans la première partie les conditions d'existence d'objets combinatoires (en outre, des colorations) soumis à des contraintes d'apparence simples, et nous apportons une réponse optimale à une conjecture qui est restée ouverte pendant une décennie. Cette solution exploite les différences et liens entre les notions naturelles de préfixe et de suffixe en combinatoire des mots. Notre seconde partie, quant à elle, étudie une version infinie du système de numération d'Ostrowski, à l'aide des mots de basse complexité donnés par les mots infinis non-ultimement périodiques de plus petite fonction de complexité que sont les mots sturmiens. Construit d'une manière analogue aux nombres p-adiques, le formalisme introduit et développé concernant les intercepts formels en vue de donner une description combinatoire de la classe des mots sturmiens a pour conséquences plusieurs résultats concernant les factorisations de ces mots. Le calcul des compléments étudié à la fin de cette partie montre comment la comparaison des opérations de préfixe et de suffixe peut être utilisée pour obtenir des résultats non-triviaux concernant les factorisations des mots de basse complexité
We present in this PhD. in Mathematics the work effectuated during three years at the Lyon 1 University Chaude Bernard Lyon 1. This PhD. has been realied under the supervisions of Boris Adamczewki and Luca Zamboni, both researchers in the Lyon 1 University. The general topic is combinatorics on words, in the form of two contributions, one of them on the limits of Ramsey theory in this context developped in the first part, and the second on the links between the Ostrowski numeration system and factorisations of sturmian words. Combinatorics on words is a domain at the intersections of mathematics, and more generally of sciences. With the emergence of theoretical computer science, or of progresses in genetics, the study of sequences of symbols has become a unavoidable research subject of growing importance. Words seen as a sequence of symboles are indeed bound to deep and subtle mathematical laws. The historical example discovered by Axel Thue of an infinite square-free word over a 3-letter alphabet have been the start of this theory, with a non-trivial construction of a specific word submitted to a seemingly very simple condition. Whether it is within the structure of decimals of real numbers, in the code lines everywhere in computers or inside our own genetic information, combinatorics on words gives a comon theoretical set of tools for a deep study of a number of present scientific issues. The present PhD. lands naturally within this scientific process. Directly inspired by the fundamental work of Axel Thue, we study in the first part the condition for the existence of combinatorial objects, colorations, submitted to a monochromatic constraint, and provide an optimal answer to a conjecture that have remained open for 10 years. This solution exploits the differences and links between the notions of prefixes and suffixes in combinatorics on words. In a second part, we study a infinite version of the Ostrowski numeration system, with the use of the low complexity class of words formed by the sturmian words. Built in a similar way as the p-adic number, the introduced and developped formalism on formal intercepts with the purpose of describing combinatorially the class of sturmian words has several consequences with regards to their factorisations. The calculus of complement, presented at the end shows how comparison of the prefix and suffix operations can be used to derived non-trivial results on factorisation of low complecity words

APA, Harvard, Vancouver, ISO, and other styles

31

Chopin, Morgan. "Problèmes d'optimisation avec propagation dans les graphes : complexité paramétrée et approximation." Phd thesis, Université Paris Dauphine - Paris IX, 2013. http://tel.archives-ouvertes.fr/tel-00933769.

Full text

Abstract:

Dans cette thèse, nous étudions la complexité algorithmique de problèmes d'optimisation impliquant un processus de diffusion dans un graphe. Plus précisément, nous nous intéressons tout d'abord au problème de sélection d'un ensemble cible. Ce problème consiste à trouver le plus petit ensemble de sommets d'un graphe à "activer" au départ tel que tous les autres sommets soient activés après un nombre fini d'étapes de propagation. Si nous modifions ce processus en permettant de "protéger" un sommet à chaque étape, nous obtenons le problème du pompier dont le but est de minimiser le nombre total de sommets activés en protégeant certains sommets. Dans ce travail, nous introduisons et étudions une version généralisée de ce problème dans laquelle plus d'un sommet peut être protégé à chaque étape. Nous proposons plusieurs résultats de complexité pour ces problèmes à la fois du point de vue de l'approximation mais également de la complexité paramétrée selon des paramètres standards ainsi que des paramètres liés à la structure du graphe.

APA, Harvard, Vancouver, ISO, and other styles

32

Schmidt, Johannes. "Classification en complexité de problèmes de raisonnement non-monotone et d' énumération." Thesis, Aix-Marseille, 2012. http://www.theses.fr/2012AIXM4055/document.

Full text

Abstract:

Nous considérons dans cette thèse la complexité algorithmique de problèmes émanant de deux formalismes de raisonnement non-monotone: l'abduction et l'argumentation. Le premier est destiné à formaliser le processus de trouver des explications pour une manifestation observée, le second (et plus récent) offre un cadre théorique pour formaliser le processus de l'argumentation. Nous nous concentrons sur le problème d'existence d'une explication pour l'abduction et sur le problème d'existence d'un argument pour l'argumentation. Dans le cadre de la logique propositionnelle dans son ensemble ces problèmes sont considérés comme étant des tâches algorithmiques difficiles (ils sont souvent situés au deuxième niveau de l'hiérarchie polynomial). Notre but est d'une part de comprendre les sources de difficulté, et d'autre part d'identifier des fragments de la logique propositionnelle dans lequels ces problèmes sont résolubles efficacement. Pour cela nous considérons ces problèmes d'abduction et d'argumentation dans deux cadres bien-établis qui permettent des classifications de complexité : Le cadre de Post et celui de Schaefer. Dans le cadre de Post, des restrictions sont faites sur les connecteurs autorisés dans les formules utilisées. Dans le cadre de Schaefer, on considère les formules en forme normale conjonctive généralisée, les "clauses" sont alors des applications de relations booléennes à des variables et on restreint le type des relations autorisées
In this thesis we consider the computational complexity of problems from two central formalisms of nonmonotonic reasoning: abduction and argumentation. The first one is designed to formalize the process of finding explanations for some observed manifestation, the second (and more recent) one gives a theoretical framework to formalize the process of argumentation. We focus on the explanation-existence problem for abduction and on the argument-existence problem for argumentation. Considered in full propositional logic these problems are believed to be computationally costly tasks (they are often situated at the second level of the polynomial hierarchy). With the purpose of understanding sources of hardness and of identifying tractable fragments of propositional logic we consider several abduction and argumentation problems in two well-established settings allowing for complexity classifications. In the first one, Post's Framework, restrictions are made on the allowed connectives in the used formulae, whereas in the second one, Schaefer's Framework, one considers formulae in conjunctive normal form, where the clauses are generalized to applications of arbitrary Boolean relations to variables and one restricts the allowed type of relations. We discuss differences and common features between the explanation-existence and the argument-existence problem in function of the two chosen frameworks. Finally, we consider enumeration. In particular we consider the problem of enumerating all solutions (models) of a propositional formula by non-decreasing weight in Schaefer's framework (the weight of a model being the number of variables assigned to true)

APA, Harvard, Vancouver, ISO, and other styles

33

Bentz, Cédric. "Résolution exacte et approchée de problèmes de multiflot entier et de multicoupe : algorithmes et complexité." Paris, CNAM, 2006. http://www.theses.fr/2006CNAM0542.

Full text

Abstract:

Dans cette thèse, on s'intéresse à des problèmes de multiflot entier et de multicoupe, qui généralisent les problèmes classiques de flot maximum et de coupe minimum. Deux aspects de ces problèmes y sont étudiés en particulier : la résolution exacte en temps polynomial et l'approximation polynomiale. Du point de vue de la résolution exacte, nos principales contributions portent sur les sujets suivants : chemins disjoints dans les graphes de nombre cyclomatique borné ; multicoupes dans les graphes orientés sans circuits, dans les graphes non orientés de largeur d'arbre bornée et dans les graphes planaires ; multiflots entiers dans les anneaux ; multicoupes et multiflots entiers dans certains cas particuliers de grilles. Du point de vue de l'approximation polynomiale, nos principales contributions portent sur les sujets suivants : chemins disjoints dans les graphes planaires à k niveaux d'arêtes ; multiflots entiers dans les graphes de nombre cyclomatique borné ; multicoupes dans les graphes orientés non pondérés de largeur d'arbre et de degré maximum bornés ; flots multiterminaux entiers dans les graphes orientés. Nous décrivons également une nouvelle heuristique pour trouver un multiflot entier maximum dans un graphe non orienté, et la testons sur des instances générées aléatoirement
In this thesis, we consider integral multiflow and multicut problems, which generalize the classical max flow and min cut problems. Two aspects of these problems are studied in particular : polynomial-time resolution and polynomial approximation. Concerning the first aspect, our main contributions focus on the following points : disjoint paths in graphs of bounded cyclomatic number ; multicuts in directed acyclic graphs, in undirected graphs of bounded tree-width and in planar graphs ; integral multiflows in rings ; multicuts and integral multiflows in several special types of grids. Concerning the second aspect, our main contributions focus on the following points : disjoint paths in k-edge-outerplanar graphs ; integral multiflows in graphs of bounded cyclomatic number ; multicuts in unweighted digraphs of bounded maximum degree and bounded tree-width ; integral multiterminal flows in digraphs. We also describe a new heuristic to find a maximum integral multiflow in an undirected graph, and test it on randomly generated graphs

APA, Harvard, Vancouver, ISO, and other styles

34

Rottner, Cécile. "Aspects combinatoires du Unit Commitment Problem." Electronic Thesis or Diss., Sorbonne université, 2018. http://www.theses.fr/2018SORUS272.

Full text

Abstract:

Le Min-up/min-down Unit Commitment Problem (MUCP) consiste à trouver un plan de production de coût minimum pour un ensemble d’unités de production électrique sur un intervalle de temps discrétisé. A chaque pas de temps, la production totale doit satisfaire la demande prévue. Chaque unité respecte des temps minimum de marche et d’arrêt. Nous montrons que le MUCP est fortement NP-difficile, mettant ainsi en valeur l’impact du couplage dynamique des contraintes de demande sur la difficulté du problème. Pour appréhender cette difficulté, nous introduisons les inégalités interval up-set, généralisant les contraintes de min-up et les extended cover du sac à dos. Les facettes sont caractérisées, et un Branch & Cut est implémenté. Afin de briser les symétries du problème, nous définissons les sous-symétries comme des symétries apparaissant dans des sous-ensembles de solution. Nous considérons des PLNE dont les groupes de sous-symétrie sont des groupes symétriques agissant sur certaines sous-colonnes des matrices solutions. Nous proposons un cadre générique pour gérer les sous-symétries apparaissant dans ce type de problèmes. Deux techniques pour briser les sous-symétries sont proposées : la première est un algorithme de fixing orbitopal pour le full sub-orbitope, la seconde est basée sur des inégalités. Les résultats expérimentaux montrent que les techniques proposées sont plus performantes que les techniques de la littérature. Enfin, nous comparons différentes structures de décomposition pour le MUCP. Des bornes de bonne qualité sont obtenues par dualisation des contraintes dynamiques. Notre Branch&Price&Cut montre que les interval up-set sont utiles dans ce contexte
The Min-up/min-down Unit Commitment Problem (MUCP), is to find a minimum-cost production plan on a discrete time horizon for a set of units producing electric power. At each time period, the total production has to meet a forecast demand. Each unit must satisfy minimum up and down time constraints. We show that the MUCP is strongly NP-hard, thus highlighting that the dynamic coupling of demands by minimum up and down time constraints represents one major source of difficulty. To cope with this difficulty, we introduce interval up-set inequalities, a new class of valid inequalities for the MUCP polytope, generalizing both min-up and extended cover inequalities from the 0-1 knapsack polytope. Facet defining cases are characterized and a Branch & Cut algorithm is devised. To deal with the symmetries impairing the solution process, we define sub-symmetries, as symmetries arising from a solution subset. We focus on integer linear programs whose (sub-)symmetry groups are symmetric groups acting on sub-columns of solution matrices. We propose a general framework to handle sub-symmetries in such problems. On this basis, two symmetry-breaking techniques are introduced. The first technique is an orbitopal fixing algorithm for the full (sub-)orbitope. The second technique is based on sub-symmetry breaking inequalities. Experimental results on MUCP instances show that the proposed techniques outperform state-of-the-art techniques. Finally we compare various Dantzig-Wolfe structures for the MUCP. We show that good quality lower bounds can be obtained by dualization of time-coupling constraints. Branch & Price results show that interval up-set inequalities are useful in this context

APA, Harvard, Vancouver, ISO, and other styles

35

Serrière, Fabrice. "Approximation polynomiale du recouvrement d'ensemble." Paris 9, 2005. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=2005PA090018.

Full text

Abstract:

Cette thèse a pour objet l'approximation polynomiale du problème NP_difficile de recouvrement d'ensemble, dit set covering problem dans la littérature. Dans la première partie, nous situons le problème de recouvrement au sein du domaine de la complexité avant de relater les plus importants résultats relatifs à l'approximation classique et à l'inapproximation classique de ce dernier. Dans la seconde partie, nous travaillons sur l'approximation différentielle du problème pour des instances pondérées et non pondérées, en commençant par situer les limites de la problématique puis en obtenant des bornes inférieures et supérieures du rapport différentiel pour certains algorithmes dont le célèbre algorithme glouton. Dans la troisième partie nous étudions la problématique probabiliste relative au recouvrement non pondéré et prouvons qu'elle est équivalente à la problématique pondérée du problème pour la stratégie que nous proposons. Dans la quatrième et dernière partie, nous étudions l'approximation du recouvrement sous son angle expérimental en testant les algorithmes étudiés au cours du document et en testant de nouveaux algorithmes sur les instances de la littérature et sur des instances générées par nos soins. La première annexe est dédiée à un certain nombre d'analyses d'algorithme. La seconde propose une méthode générale d'analyse pouvant s'adapter à de nombreux problèmes. La troisième présente la globalité des résultats expérimentaux, et la dernière annexe est une question relative à l'énumération sous contrainte
This thesis deals with the polynomial approximation of the NP_Hard set covering problem. In the first part, we locate the problem of covering within the field of complexity before reporting the most significant results relating to the classical approximation and the traditional inapproximation of it. In the second part, we work on the differential approximation of the problem for weighted and unweighted cases, while starting by locating the limits of the problems then by proving lower and higher bounds for the differential ratio for certain algorithms whose well known greedy one. In the third part we study the probabilistic problems relating to unweighted set cover and prove that it is equivalent to the weighted one for the strategy which we propose. In the fourth and last part, we study the approximation of covering under its experimental angle by testing the algorithms studied during the document and by testing new algorithms on the instances of the literature and instances that we generated. The first appendix is dedicated to well known analyses of algorithm for set covering problem. The second one proposes a general method of analysis adaptable to many combinatorial problems. The third gives the experimental results studied in the forth part, and the last appendix is a question relating to the enumeration under constraint

APA, Harvard, Vancouver, ISO, and other styles

36

Lonca, Emmanuel. "Optimisation booléenne multiobjectif : complexité sous contraintes compilées et résolution via SAT." Thesis, Artois, 2015. http://www.theses.fr/2015ARTO0405/document.

Full text

Abstract:

L’aide à la décision a pour but d’assister un opérateur humain dans ses choix. La nécessité d’employer de telles techniques s’est imposée avec la volonté de traiter des problèmes dépendant d’une quantité de données toujours plus importante. L’intérêt de l’aide à la décision est encore plus manifeste lorsqu’on souhaite obtenir non pas une solution quelconque, mais une des meilleures solutions d’un problème combinatoire selon un critère donné. On passe alors d’un problème de décision (déterminer l’existence d’une solution) à un problème d’optimisation monocritère (déterminer une des meilleures solutions possibles selon un critère). Un décideur peut aussi souhaiter considérer plusieurs critères, et ainsi faire passer le problème de décision initial à un problème d’optimisation multicritère. La difficulté de ce type de problèmes provient du fait que les critères considérés sont généralement antagonistes, et qu’il n’existe donc pas de solution meilleure que les autres pour l’ensemble des critères. Dans ce cas, il s’agit plutôt de déterminer une solution qui offre un bon compromis entre les critères. Dans cette thèse, nous étudions dans un premier temps la complexité théorique de tâches d’optimisation complexes sur les langages de la logique propositionnelle, puis nous étudions leur résolution pratique via le recours à des logiciels bâtis pour résoudre de manière efficace en pratique des problèmes de décision combinatoires, les prouveurs SAT
Decision aiding aims at helping a decision-maker to pick up a solution among several others. The usefulness of such approaches is as prominent as the size of the problems under consideration increases. The need of decision aiding techniques is salient when the problem does not just consist in deciding whether a solutions exists, but to find one of the best solutions according to a given criterion. In this case, the problem goes from a decision problem (decide whether a solution exists) to a single criterion optimization problem (find one of the best solutions according to a criterion). A decision-maker may even want to consider multiple criteria, which turns the initial decision problem into a multicriteria optimization problem. The main issue arising in such cases lies in the fact that the criteria under consideration are often antagonistic, which implies that there is no solution which is the best for each of the objectives. In this case, a good compromise solution is looked for. In this thesis, we first focus on the complexity of optimization requests based on a set of propositional languages. We then study the practical aspects of the resolution of such problems, using pieces of software designed for dealing with combinatorial decision problems, namely SAT solvers

APA, Harvard, Vancouver, ISO, and other styles

37

Manouvrier, Jean-François. "Méthode de décomposition pour résoudre des problèmes combinatoires sur les graphes." Compiègne, 1998. http://www.theses.fr/1998COMP1152.

Full text

Abstract:

Les travaux de cette thèse utilisent une méthode de décomposition pour résoudre des problèmes combinatoires NP-difficiles énoncés sous la forme de problèmes de graphes. Parmi les méthodes exactes existantes, les méthodes utilisant une décomposition-arbre du graphe permettent de résoudre certains problèmes NP-difficiles en temps polynomial pour un graphe de largeur-arbre inferieur à K. K est une constante fixée en fonction du problème et des capacités de la machine utilisée. Nous nommons ces méthodes de programmation dynamique : méthodes de décomposition. Dans cette thèse, nous utilisons une décomposition-chemin du graphe, basée sur une numérotation linéaire des sommets du graphe, pour résoudre certains problèmes NP-difficiles. Les problèmes que nous avons ainsi traites sont les problèmes de la fiabilité des réseaux (fiabilité tous-terminaux et fiabilité 2-arête-connexe tous-terminaux), le problème du voyageur de commerce et le problème de l'arbre de Steiner minimal. Pour chacun de ces problèmes, nous étudions les autres méthodes existantes, nous démontrons que la méthode de décomposition peut être appliquée, en modélisant des classes d'équivalences regroupant des solutions partielles, et nous analysons l'implémentation de ces méthodes. Une des difficultés essentielles de l'implémentation des programmes de décomposition consiste à gérer efficacement en mémoire les classes. Pour la fiabilité 2-arête-connexe tous-terminaux, la structure des classes nous a contraints à introduire un concept de forêts fictives et à développer un algorithme énumérant ces forêts. Nous obtenons ainsi des algorithmes de décomposition résolvant ces problèmes, dont les complexités en temps sont linéaires en fonction de la taille du graphe pour des graphes de largeur-chemin bornée.

APA, Harvard, Vancouver, ISO, and other styles

38

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 text

Abstract:

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.

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.

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é.

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.

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.

APA, Harvard, Vancouver, ISO, and other styles

39

Mora, Thierry. "Géométrie et inférence dans l'optimisation et en théorie de l'information." Paris 11, 2007. http://www.theses.fr/2007PA112162.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Perrault, Pierre. "Apprentissage efficient dans les problèmes de semi-bandits stochastiques combinatoires." Thesis, université Paris-Saclay, 2020. http://www.theses.fr/2020UPASM023.

Full text

Abstract:

Les problèmes de semi-banditsstochastiques combinatoires se présentent naturellement dans de nombreux contextes où le dilemme exploration/exploitation se pose, tels que l’optimisation de contenu web (recommandation/publicité en ligne) ou encore les méthodes de routage à trajet minimal. Ce problème est formulé de la manière suivante : un agent optimise séquentiellement une fonction objectif inconnue et bruitée, définie sur un ensemble puissance mathcal{P}([n]). Pour chaque ensemble A testé,l'agent subit une perte égale à l'écart espéré par rapport à la solution optimale tout en obtenant des observations lui permettant de réduire son incertitude sur les coordonnées de A.Notre objectif est d'étudier l'efficience des politiques pour ce problème, en nous intéressant notamment aux deux aspects suivants : l'efficience statistique, où le critère considéré est le regret subi par la politique (la perte cumulée) qui mesure la performance d'apprentissage ; et l'efficience computationnelle (i.e., de calcul). Il est parfois difficile de réunir ces deux aspects dans une seule politique. Dans cette thèse, nous proposons différentes directions pour améliorer l'efficience statistique, tout en essayant de maintenir l'efficience computationnelle des politiques. Nous avons notamment amélioré les méthodes optimistes en développant des algorithmes d'approximation et en affinant les régions de confiance utilisées. Nous avons également exploré une alternative aux méthodes optimistes, à savoir les méthodes randomisées, et avons constaté qu'elles constituent un candidat sérieux pour pouvoir réunir les deux types d'efficience
Combinatorial stochastic semi-bandits appear naturally in many contexts where the exploration/exploitation dilemma arises, such as web content optimization (recommendation/online advertising) or shortest path routing methods. This problem is formulated as follows: an agent sequentially optimizes an unknown and noisy objective function, defined on a power set mathcal{P}([n]). For each set A tried out, the agent suffers a loss equal to the expected deviation from the optimal solution while obtaining observations to reduce its uncertainty on the coordinates from A. Our objective is to study the efficiency of policies for this problem, focusing in particular on the following two aspects: statistical efficiency, where the criterion considered is the regret suffered by the policy (the cumulative loss) that measures learning performance; and computational efficiency. It is sometimes difficult to combine these two aspects in a single policy. In this thesis, we propose different directions for improving statistical efficiency, while trying to maintain the computational efficiency of policies.In particular, we have improved optimistic methods by developing approximation algorithms and refining the confidence regions used. We also explored an alternative to the optimistic methods, namely randomized methods, and found them to be a serious candidate for combining the two types of efficiency

APA, Harvard, Vancouver, ISO, and other styles

41

Griffon, Aurelien. "Etude de la complexité des éléments Cis-régulateurs chez les mammifères en utilisant des approches à haut débit." Thesis, Aix-Marseille, 2015. http://www.theses.fr/2015AIXM4017.

Full text

Abstract:

La régulation des gènes est à l’origine de la diversité cellulaire en permettant aux cellules de se différencier et de se spécialiser. La régulation génique repose largement sur l’existence de séquences d’ADN non codantes dans le génome, appelées "éléments cis-régulateurs", qui vont permettre de recruter de nombreux facteurs de transcription afin de former d’importants complexes (nucléo)protéiques qui vont agir sur le niveau de transcription des gènes. Ce recrutement est notamment contrôlé par des modifications épigénétiques. Le développement des techniques de séquençage et des méthodes d’analyse bioinformatiques permettent d’intégrer de grandes quantités de données pour étudier le fonctionnement des éléments régulateurs. Dans un premier temps, l’intégration de l’ensemble des données ChIP-seq disponibles dans les bases de données nous a permis de créer un catalogue d’éléments régulateurs putatifs chez l’Homme. L’analyse de ce catalogue nous a alors mené à caractériser ces éléments et à mettre en évidence la complexité combinatoire des facteurs de transcription. Dans un deuxième temps, nous avons réalisé une étude basée sur l’analyse des éléments régulateurs impliqués dans la différenciation précoce des lymphocytes T chez la souris. Cette étude a permis de mettre en évidence deux niveaux de complexité impliqués dans la régulation des gènes : le premier est basé sur la combinatoire des facteurs de transcription au sein des éléments régulateurs et le second repose sur la combinatoire des éléments eux-mêmes. Finalement, nous avons développé une nouvelle technique d’analyse quantitative et à haut débit de l’activité régulatrice de régions génomiques chez les mammifères
Gene regulation is responsible for cell diversity by allowing cell differentiation and specialisation. Gene expression regulation relies mainly on the existence of non-coding DNA sequences in the genome, called "cis-regulatory elements", which recruit numerous transcription factors to form (nucleo)protein complexes which act on the gene transcription level. This recruitment is controlled in particular by epigenetic modifications. The rapid development of sequencing technologies and bioinformatics methods makes possible the integration of large amounts of data to study regulatory elements. First, the integration of ChIP-seq data for all transcription factors available in public databases has allowed us to create an extensive catalogue of putative regulatory elements in the human genome. The overall analysis of this catalogue led us to further characterize these elements and to highlight the high level of combinatorial complexity of transcription factors in the genome. Secondly, we conducted a more specific study based on the analysis of the regulatory elements involved in the early differentiation of T-cells in mice. This study provided an opportunity to highlight two levels of complexity based on regulatory elements and involved in gene regulation: the first rests on the transcription factor combinatorial in regulatory elements and the second is based on the combinatorial of elements themselves within loci. Finally, to validate experimentally the regulatory elements, we have developed a new quantitative and high-throughput technique to assess the regulatory activity of genomic regions in mammals

APA, Harvard, Vancouver, ISO, and other styles

42

Legay, Sylvain. "Quelques problèmes d'algorithmique et combinatoires en théorie des grapphes." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLS030/document.

Full text

Abstract:

Le sujet de cette thèse est la théorie des graphes. Formellement, un graphe est un ensemble de sommets et un ensemble d’arêtes, c’est à dire de paires de sommets, qui relient les sommets. Cette thèse traite de différents problèmes de décisions binaires ou de minimisations liés à la notion de graphe, et cherche, pour chacun de ces problèmes, à déterminer sa classe de complexité, ou à fournir un algorithme. Le premier chapitre concerne le problème de trouver le plus petit sous-graphe connexe tropical dans un graphe sommet-colorié, c’est à dire le plus petit sous-graphe connexe contenant toutes les couleurs. Le deuxième chapitre concerne les problèmes d’homomorphisme tropical, une généralisation des problèmes de coloriage de graphe. On y trouve un lien entre ces problèmes et plusieurs classes de problèmes d’homomorphismes, dont la classe des Problèmes de Satisfaction de Contraintes. Le troisième chapitre concerne deux variantes lointaines du problème de domination, nommément les problèmes d’alliances globales dans un graphe pondéré et le problème de l’ensemble sûr. Le quatrième chapitre concerne la recherche d’une décomposition arborescente étoilée, c’est à dire une décomposition arborescente dont le rayon des sacs est 1. Enfin, le cinquième chapitre concerne une variante du problème de décider du comportement asymptotique de l’itéré du graphe des bicliques
This thesis is about graph theory. Formally, a graph is a set of vertices and a set of edges, which are pair of vertices, linking vertices. This thesis deals with various decision problem linked to the notion of graph, and, for each of these problem, try to find its complexity class, or to give an algorithm. The first chapter is about the problem of finding the smallest connected tropical subgraph of a vertex-colored graph, which is the smallest connecter subgraph containing every colors. The second chapter is about problems of tropical homomorphism, a generalization of coloring problem. A link between these problems and several other class of homomorphism problems can be found in this chapter, especially with the class of Constraint Satisfaction Problem. The third chapter is about two variant of the domination problem, namely the global alliance problems in a weighted graph and the safe set problem. The fourth chapter is about the problem of finding a star tree-decomposition, which is a tree-decomposition where the radius of bags is 1. Finally, the fifth chapter is about a variant of the problem of deciding the asymptotic behavior of the iterated biclique graph

APA, Harvard, Vancouver, ISO, and other styles

43

Fouks, Jean-Denis. "La résolution du problème de satisfiabilité." Mulhouse, 1991. http://www.theses.fr/1991MULH0175.

Full text

Abstract:

A titre de motivation, nous donnons, dans le chapitre un, une famille d'instances difficiles pour le populaire problème du voyageur de commerce. Les deux chapitres suivants rappellent alors la théorie sous-jacente (classes P et NP, problèmes NP- complets) et se terminent sur le caractère NP-complet pour le voyageur de commerce. L'étude de la résolution débute au chapitre quatre par l'introduction des trames et évaluations, outils qui redonnent d'importants résultats et s'avèrent très utiles par la suite. Au chapitre cinq, nous étudions en toute géneralité la complexité de la résolution sur les formules de Tseitin (définies par des graphes). Notre méthode consiste à interpréter la génération des clauses intermédiaires par des opérations sur le graphe. Pour la mettre en oeuvre, nous devons nous placer dans le cadre des multigraphes quelconques et introduire la notion de cohésion cyclomatique. La complexité de la résolution sur ces formules est alors minorée exponentiellement par cette cohésion. Ce résultat est plus général que celui de A. Urquhart et permet non seulement une minoration mais aussi un calcul de la complexité. Au chapitre six, nous donnons un algorithme de méta-résolution en temps linéaire pour les formules de Tseitin. Cet algorithme repose paradoxalement sur les propriétés qui ont permis de prouver leur caractère intraitable par la résolution

APA, Harvard, Vancouver, ISO, and other styles

44

Garnero, Valentin. "(Méta)-noyaux constructifs et linéaires dans les graphes peu denses." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT328/document.

Full text

Abstract:

En algorithmique et en complexité, la plus grande part de la recherche se base sur l’hypothèse que P ≠ NP (Polynomial time et Non deterministic Polynomial time), c'est-à-dire qu'il existe des problèmes dont la solution peut être vérifiée mais non construite en temps polynomial. Si cette hypothèse est admise, de nombreux problèmes naturels ne sont pas dans P (c'est-à-dire, n'admettent pas d'algorithme efficace), ce qui a conduit au développement de nombreuses branches de l'algorithmique. L'une d'elles est la complexité paramétrée. Elle propose des algorithmes exacts, dont l'analyse est faite en fonction de la taille de l'instance et d'un paramètre. Ce paramètre permet une granularité plus fine dans l'analyse de la complexité.Un algorithme sera alors considéré comme efficace s'il est à paramètre fixé, c'est-à-dire, lorsque sa complexité est exponentielle en fonction du paramètre et polynomiale en fonction de la taille de l'instance. Ces algorithmes résolvent les problèmes de la classe FPT (Fixed Parameter Tractable).L'extraction de noyaux est une technique qui permet, entre autre, d’élaborer des algorithmes à paramètre fixé. Elle peut être vue comme un pré-calcul de l'instance, avec une garantie sur la compression des données. Plus formellement, une extraction de noyau est une réduction polynomiale depuis un problème vers lui même, avec la contrainte supplémentaire que la taille du noyau (l'instance réduite) est bornée en fonction du paramètre. Pour obtenir l’algorithme à paramètre fixé, il suffit de résoudre le problème dans le noyau, par exemple par une recherche exhaustive (de complexité exponentielle, en fonction du paramètre). L’existence d'un noyau implique donc l'existence d'un algorithme à paramètre fixé, la réciproque est également vraie. Cependant, l’existence d'un algorithme à paramètre fixé efficace ne garantit pas un petit noyau, c'est a dire un noyau dont la taille est linéaire ou polynomiale. Sous certaines hypothèses, il existe des problèmes n’admettant pas de noyau (c'est-à-dire hors de FPT) et il existe des problèmes de FPT n’admettant pas de noyaux polynomiaux.Un résultat majeur dans le domaine des noyaux est la construction d'un noyau linéaire pour le problème Domination dans les graphes planaires, par Alber, Fellows et Niedermeier.Tout d'abord, la méthode de décomposition en régions proposée par Alber, Fellows et Niedermeier, a permis de construire de nombreux noyaux pour des variantes de Domination dans les graphes planaires. Cependant cette méthode comportait un certain nombre d’imprécisions, ce qui rendait les preuves invalides. Dans la première partie de notre thèse, nous présentons cette méthode sous une forme plus rigoureuse et nous l’illustrons par deux problèmes : Domination Rouge Bleue et Domination Totale.Ensuite, la méthode a été généralisée, d'une part, sur des classes de graphes plus larges (de genre borné, sans-mineur, sans-mineur-topologique), d'autre part, pour une plus grande variété de problèmes. Ces méta-résultats prouvent l’existence de noyaux linéaires ou polynomiaux pour tout problème vérifiant certaines conditions génériques, sur une classe de graphes peu denses. Cependant, pour atteindre une telle généralité, il a fallu sacrifier la constructivité des preuves : les preuves ne fournissent pas d'algorithme d'extraction constructif et la borne sur le noyau n'est pas explicite. Dans la seconde partie de notre thèse nous effectuons un premier pas vers des méta-résultats constructifs ; nous proposons un cadre général pour construire des noyaux linéaires en nous inspirant des principes de la programmation dynamique et d'un méta-résultat de Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh et Thilikos
In the fields of Algorithmic and Complexity, a large area of research is based on the assumption that P ≠ NP(Polynomial time and Non deterministic Polynomial time), which means that there are problems for which a solution can be verified but not constructed in polynomial time. Many natural problems are not in P, which means, that they have no efficient algorithm. In order to tackle such problems, many different branches of Algorithmic have been developed. One of them is called Parametric Complexity. It consists in developing exact algorithms whose complexity is measured as a function of the size of the instance and of a parameter. Such a parameter allows a more precise analysis of the complexity. In this context, an algorithm will be considered to be efficient if it is fixed parameter tractable (fpt), that is, if it has a complexity which is exponential in the parameter and polynomial in the size of the instance. Problems that can be solved by such an algorithm form the FPT class.Kernelisation is a technical that produces fpt algorithms, among others. It can be viewed as a preprocessing of the instance, with a guarantee on the compression of the data. More formally, a kernelisation is a polynomial reduction from a problem to itself, with the additional constraint that the size of the kernel, the reduced instance, is bounded by a function of the parameter. In order to obtain an fpt algorithm, it is sufficient to solve the problem in the reduced instance, by brute-force for example (which has exponential complexity, in the parameter). Hence, the existence of a kernelisiation implies the existence of an fpt algorithm. It holds that the converse is true also. Nevertheless, the existence of an efficient fpt algorithm does not imply a small kernel, meaning a kernel with a linear or polynomial size. Under certain hypotheses, it can be proved that some problems can not have a kernel (that is, are not in FPT) and that some problems in FPT do not have a polynomial kernel.One of the main results in the field of Kernelisation is the construction of a linear kernel for the Dominating Set problem on planar graphs, by Alber, Fellows and Niedermeier.To begin with, the region decomposition method proposed by Alber, Fellows and Niedermeier has been reused many times to develop kernels for variants of Dominating Set on planar graphs. Nevertheless, this method had quite a few inaccuracies, which has invalidated the proofs. In the first part of our thesis, we present a more thorough version of this method and we illustrate it with two examples: Red Blue Dominating Set and Total Dominating Set.Next, the method has been generalised to larger classes of graphs (bounded genus, minor-free, topological-minor-free), and to larger families of problems. These meta-results prove the existence of a linear or polynomial kernel for all problems verifying some generic conditions, on a class of sparse graphs. As a price of generality, the proofs do not provide constructive algorithms and the bound on the size of the kernel is not explicit. In the second part of our thesis, we make a first step to constructive meta-results. We propose a framework to build linear kernels based on principles of dynamic programming and a meta-result of Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh and Thilikos

APA, Harvard, Vancouver, ISO, and other styles

45

Tallot, Didier. "Quelques propositions pour la mise en oeuvre d'algorithmes combinatoires." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 1985. http://tel.archives-ouvertes.fr/tel-00806984.

Full text

Abstract:

Le travail, exposé dans ce rapport, se divise en deux parties. La première partie a fait l'objet d'un rapport de recherche publié en Avril 1984 [Tall]. La deuxième partie résulte d'un travail qui s'est déroulé de juin 1984 i juin 1985. Pour produire des images de hautes qualités, on est obligé de manipuler des grandes quantités de données. D'où l' intérêt d'étudier des algorithmes et des structures de données efficaces pour résoudre ~es problèmes géométriques. On pourra ainsi obtenir des méthodes efficaces pour la manipulation de données graphiques. On peut citer i ce propos, les travaux pionners de SHAMOS dans le domaine de la complexité géométrique [Sham]. La deuxième partie contient la description d 'un logiciel interactif *de manipulation de graphes et d'ordres. A notre connaissnce, la plus ancienne réalisation de ce type de logiciel est le "Graph theory interactive system" de WOLFBERG [Wolf]. Suivant les travaux de GUIDO sur CABRI (CAhier de BRouillon Informatisé), nous desirons offrir un poste de travail sur les graphes pour des chercheurs en théorie des graphes. CABRI est une bonne approche du problème, mais reste d'un emploi malaisé. Nous avons donc étudiés de nouveau le problème en nous attachant à décrire une meilleure interface utilisateur. Nous nous sommes inspirés des travaux sur les logiciels interactif existant, comme ceux développés chez XEROX, au PALO-ALTO RESEARCH CENTER (Smit] chez NIEVERGELT [Sere].

APA, Harvard, Vancouver, ISO, and other styles

46

Barrot, Nathanaël. "Sur les aspects computationnels du vote par approbation." Thesis, Paris Sciences et Lettres (ComUE), 2016. http://www.theses.fr/2016PSLED006/document.

Full text

Abstract:

L'objet de cette thèse est l'étude des aspects algorithmiques du vote par approbation. Il s'agit principalement d'une étude théorique des enjeux computationnels soulevés par le vote par approbation dans des contextes de décisions variés. Cependant, j'étudie aussi des questions plus proches de la théorie classique du choix social et je conduis de brèves études expérimentales.Dans un premier temps, l'étude se porte sur une famille générale de règles de vote pour les élections de comités et les référendums multiples à l'aide du vote par approbation. Dans un second temps, je porte mon attention sur un contexte plus général, le vote par approbation sur domaines combinatoires en se basant sur des préférences conditionnelles. Finalement, je me place dans le cadre du vote avec préférences incomplètes pour étudier les problèmes de vainqueurs possibles et nécessaires dans le vote par approbation
The subject of this thesis is the study of computational aspects of approval voting. Most of the works are theoretical results about computational issues raised by approval voting, in many different settings. However, I also study some questions that are more related to classical choice theory, and some problems are investigated through experimental analysis.Firstly, I study a general family of rules for approval voting in the context of committee elections and multiple referenda. Secondly, I focus on a more general setting, approval voting in combinatorial domains, based on conditional preferences. Finally, I consider approval voting in the context of incomplete preferences, to study the possible and necessary winner problems

APA, Harvard, Vancouver, ISO, and other styles

47

Yalaoui, Alice. "Allocation de fiabilité et de redondance dans les systèmes parallèle-série et série-parallèle." Troyes, 2004. http://www.theses.fr/2004TROY0009.

Full text

Abstract:

L'intégration de la notion de conception et de reconception des systèmes s'inscrit dans l'esprit de proximité et de flexibilité de la gestion contemporaine des entreprises. L'optimisation de la fiabilité, aussi bien des produits fabriqués que de l'outil de production y est d'une grande importance. Nous nous sommes intéressés particulièrement aux problèmes d'allocation de fiabilité et de redondance. Dans le cas où les fiabilités des composants peuvent être des valeurs quelconques entre zéro et un, nous avons développé, pour la maximisation de la fiabilité sous contrainte de coût, un algorithme convergeant vers l'optimum, pour les systèmes parallèle-série. Dans le cas des systèmes parallèle-série, nous avons proposé des résultats théoriques et une méthode approchée pour la minimisation du coût sous contrainte de fiabilité. Nous nous sommes aussi intéressés au cas où les fiabilités des composants sont à choisir parmi un ensemble de valeurs discrètes. Cette hypothèse rend compte de la disponibilité en composants sur le marché. Des algorithmes pseudopolynomiaux pour les problèmes d'allocation de fiabilité et de redondance ont été développés, pour des structures série-parallèle et parallèle-série. Ces algorithmes sont dédiés à la minimisation du coût sous contrainte de fiabilité et au problème dual de maximisation de la fiabilité. Nous les avons généralisés à des structures plus complexes
The integration of the system's design notion takes share in the spirit of proximity and flexibility of companies' contemporary management. The reliability optimization, as well of the products manufactured as of the production equipment, is there of great importance. We were interested particularly in the problems of reliability and redundancy allocation. If reliabilities of the components may be unspecified values between zero and one, we developed, for the maximization of reliability under cost constraint, an algorithm which converges towards the optimum, for the systems parallel-series. In the case of the systems parallel-series, we proposed theoretical results and an approximate methode for the cost minimization under a reliability constraint. We were also interested in the case of reliabilities of the components which can be chosen among a whole of discrete values. This assumption takes account of the avaibility in components on the market. Pseudopolynomial algorithms for the problems of reliability and redundancy allocation were developed, for parallel series and parallel-series structures. These algorithms are dedicated to the minimization of the cost under reliability constraint and to the dual problem of reliability maximization. We generalized them for more complex structures

APA, Harvard, Vancouver, ISO, and other styles

48

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 text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

49

Colares, Rafael. "Exploring Combinatorial Aspects of the Stop Number Problem." Thesis, Université Clermont Auvergne‎ (2017-2020), 2019. http://www.theses.fr/2019CLFAC050.

Full text

Abstract:

Le Problème du Nombre d'Arrêts se présente dans la gestion d'un système de transport à la demande utilisant des véhicules électriques autonomes. Dans un tel système, une flotte de véhicules identiques parcourt un circuit prédéfini avec des stations fixes afin de desservir un ensemble de clients qui demandent un trajet entre une station d'origine et une station de destination. Notez que plusieurs clients peuvent partager les mêmes stations d'origine et/ou de destination. Le Problème du Nombre d'Arrêts consiste à affecter chaque demande à un véhicule de façon à ce qu'aucun véhicule ne soit surchargé. L'objectif est de minimiser le nombre d'arrêts effectués par la flotte de véhicules pour la collecte et la livraison des clients. Lorsque chaque client demande exactement une place dans un véhicule, le Problème du Nombre d'Arrêts est appelé Problème du Nombre d'Arrêts Unitaire. Dans cette thèse, le Problème du Nombre d'Arrêts Unitaire est traité comme un problème d'optimisation combinatoire.Tout d'abord, nous examinons la complexité du problème. D'une part, nous étudions certaines propriétés des solutions optimales et dérivons une série de cas particuliers dont la résolution peut être réalisée en temps polynomial. D'autre part, nous montrons que le Problème du Nombre d'Arrêts Unitaire est NP-Difficile même lorsqu'il est restreint au cas où chaque véhicule peut prendre au maximum deux clients à la fois et que le graphe induit par les demandes des clients est planaire bipartie. Ce résultat - qui répond positivement à une conjecture connue dans la littérature - est ensuite étendu à d'autres problèmes associés tels que le k-Edge Partitioning et le Traffic Grooming, améliorant ainsi leurs standards de complexité connus dans la littérature.Dans une deuxième partie, nous considérons une formulation de programmation linéaire en nombres entiers connue dans la littérature pour résoudre le Problème du Nombre d'Arrêts Unitaire. Une analyse préliminaire est effectuée afin de prouver la faiblesse de cette formulation. Par la suite, cette formulation est renforcée à l'aide d'une approche polyédrale. Nous fournissons une étude de faciale du polytope associée aux solutions de ce problème. De nouvelles inégalités valides sont introduites et les conditions nécessaires et suffisantes pour lesquelles elles définissent des facettes sont indiquées.Enfin, sur la base des résultats de l'approche polyédrale discutée, nous dérivons un nouvel algorithme de coupes et branchements efficace. Des fonctionnalités améliorant les performances de l’algorithme, telles que les méthodes de rupture de symétrie et l'élimination/relaxation des variables, sont également étudiées et mises en œuvre. Les résultats démontrent de manière convaincante la pertinence du renforcement des inégalités valides et donc de notre algorithme de coupes et branchements
The Stop Number Problem arises in the management of a dial-a-ride system with small autonomous electric vehicles. In such a system, a fleet of identical capacitated vehicles travels along a predefined circuit with fixed stations in order to serve clients requesting for a ride from an origin station to a destination station. Notice that multiple clients may share the same origin and/or destination stations. The Stop Number Problem consists of assigning each client request to avehicle such that no vehicle gets overloaded. The goal is to minimize the number of times the fleet of vehicles stops for picking up or delivering clients. When every client requests for exactly one seat in a vehicle, Stop Number Problem is called Unit Stop Number Problem. In this thesis, Unit Stop Number Problem is addressed as a combinatorial-optimization problem.First, we investigate the complexity of such problem. On the one hand, we study some properties of optimal solutions and derive a series of particular cases that are shown to be solvable in polynomial time. On the other hand, we show that Unit Stop Number Problem is NP-Hard even when restricted to case where each vehicle can take at most two clients at once and the graph induced by the client requests is planar bipartite. Such result -- which positively answers a conjecture known in the literature -- is then extended to other related problems such as the k-Edge Partitioning and the Traffic Grooming problem, improving their respective state-of-the-art complexity standards.In a second part, we consider an integer-programming formulation known in the literature for solving the Unit Stop Number Problem. A preliminary analysis is conducted in order to prove the weakness of such formulation. Afterwards, such formulation is reinforced through a polyhedral approach. We provide a facial study of the polytope associated with the solutions of this problem. New valid inequalities are introduced and necessary and sufficient conditions for which they are facet-defining are given.Finally, based on the discussed polyhedral results, we derive a new efficient branch-and-cut algorithm. Performance boosting features such as symmetry breaking methods and variable elimination/relaxation are also investigated and implemented into the developed framework. Results convincingly demonstrate the strength of the reinforcing valid inequalities and therefore of our branch-and-cut algorithm

APA, Harvard, Vancouver, ISO, and other styles

50

Baccouche, Mohamed. "Métaheuristiques hybrides d'optimisation d'atterrissage d'avions multipistes." Le Havre, 2007. http://www.theses.fr/2007LEHA0008.

Full text

Abstract:

Nous avons étudié dans cette thèse un problème complexe, mixte d'ordonnancement des avions et d'affectation des pistes, le problème d'atterrissage des avions. La complexité de ce problème d'optimisation résulte de son aspect combinatoire (taille de problème), de la forte interdépendance des fonctions (affectation et ordonnancement), des contraintes et des perturbations. Les capacités d'atterrissage des aéroports constituent de véritables goulots d'étranglement qui ne permettent pas de répondre à une augmentation du trafic aérien. Les plate-formes les plus importantes sont déjà au maximum de leur capacité et seule une optimisation accrue des séquences d'atterrissage permettra de faire face. Nous avons développé et testé différentes approches hybride basées sur des techniques métaheuristiques comme les algorithmes génétiques et la recherche taboue et des méthodes exactes. Nous avons comparé les différentes approches avec un large choix des paramètres, analysé la complexité de calcul et les performances et évalué les meilleures solutions trouvées. Nous avons utilisé la méthode des plans d'expériences pour optimiser le choix des paramètres des algorithmes développés
We studied in this thesis a complex problem, mixed aircraft scheduling and runway assignment, the Aircraft landing Problem. The complexity of this optimization problem is the result of its combinatorial aspects (problems size), of the strong interdependence between functions (assignment and scheduling), constraints and perturbations. Airport landing capacities constitute genuine bottlenecks, making it impossible to respond to an increase in air traffic. The largest airports are already operating at maximum capacity and only increased optimization of the landing sequences will make it possible to cope. We developed and tested different hybrid approaches based on metaheuristics techniques such as evolutionary algorithms and taboo search and on exact methods. We have compared different approaches with a large choice of parameters, analyzed computational complexity and performances and discussed the best values. We used the experience plans method in order to optimize the choice of parameters of developed algorithms

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Complexité combinatoire'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles