Academic literature on the topic 'Complexité combinatoire'

Le texte littéraire constitue toujours, plus ou moins, une combinatoire des évaluations et des normes. C’est cette sorte d’algèbre que l’on voudra montrer en insistant sur la complexité de l’enchevêtrement normatif, sur les rôles et les qualifications des évaluateurs, sur les discordances des évaluations, sur la place qu’occupe le narrateur dans ce montage normatif.

AbstractCette contribution propose des outils de transcription et d'analyse des pratiques langagières de locuteurs sourds, dont les discours sont inscrits le plus souvent dans le bilinguisme, le contact de langues et la bimodalité. Réalisée sous le logiciel ELAN®, la grille hiérarchique que nous proposons et dont nous détaillons tous les niveaux d'analyse autorise des approches qualitatives et quantifiées des observables. Elle permet de rendre compte de la diversité des moyens utilisés (verbal/non verbal ; vocal/gestuel), de leur combinatoire et de leurs interactions. Elle permet également d'envisager des indices de complexité syntaxique et discursive, qui se construisent dans cette bilingualité particulière ancrée d'entrée de jeu dans la bimodalité. Les visées sont théoriques et descriptives et doivent trouver des prolongements psycholinguistiques et didactiques.

AbstractWe consider three problems concerning alpha conversion of closed terms (combinators).(1) Given a combinator M find the an alpha convert of M with a smallest number of distinct variables.(2) Given two alpha convertible combinators M and N find a shortest alpha conversion of M to N.(3) Given two alpha convertible combinators M and N find an alpha conversion of M to N which uses the smallest number of variables possible along the way.We obtain the following results.(1) There is a polynomial time algorithm for solving problem (1). It is reducible to vertex coloring of chordal graphs.(2) Problem (2) is co-NP complete (in recognition form). The general feedback vertex set problem for digraphs is reducible to problem (2).(3) At most one variable besides those occurring in both M and N is necessary. This appears to be the folklore but the proof is not familiar. A polynomial time algorithm for the alpha conversion of M to N using at most one extra variable is given.There is a tradeoff between solutions to problem (2) and problem (3) which we do not fully understand.

As computing capabilities are extending, the amount of source code to manage is inevitably becoming larger and more complex. No matter how hard we try, the bewildering complexity of the source code always ends up overwhelming its own creator, to the point of giving the appearance of chaos. As a solution to the cognitive complexity of source code, we are proposing to use the framework of Combinatory Logic to construct complex computational concepts that will provide a model of description of the code that is easy and intuitive to grasp. Combinatory Logic is already known as a model of computation but what we are proposing here is to use a logic of combinators and operators to reverse engineer more and more complex computational concept up from the source code. Through the two key notions of computational concept and abstract operator, we will show that this model offers a new, meaningful and simple way of expressing what the intricate code is about.

Object-oriented combinator chemistry (OOCC) is an artificial chemistry with composition devices borrowed from object-oriented and functional programming languages. Actors in OOCC are embedded in space and subject to diffusion; since they are neither created nor destroyed, their mass is conserved. Actors use programs constructed from combinators to asynchronously update their own states and the states of other actors in their neighborhoods. The fact that programs and combinators are themselves reified as actors makes it possible to build programs that build programs from combinators of a few primitive types using asynchronous spatial processes that resemble chemistry as much as computation. To demonstrate this, OOCC is used to define a parallel, asynchronous, spatially distributed self-replicating system modeled in part on the living cell. Since interactions among its parts result in the construction of more of these same parts, the system is strongly constructive. The system's high normalized complexity is contrasted with that of a simple composome.

AbstractThis paper is concerned with the combinator representation of numeral systems with logarithmic space complexity of symbols. The principle used is based on the lexicographic ordering of words over a finite alphabet.

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

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.

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

La théorie de la NP-complétude nous apprend que pour un certain nombre de problèmes d'optimisation, il est vain d'espérer un algorithme efficace calculant une solution optimale. Partant de ce constat, un moyen pour contourner cet obstacle est de réaliser un compromis sur chacun de ces critères, engendrant deux approches devenues classiques. La première, appelée approximation polynomiale, consiste à développer des algorithmes efficaces et retournant une solution proche d'une solution optimale. La seconde, appelée complexité paramétrée, consiste à développer des algorithmes retournant une solution optimale mais dont l'explosion combinatoire est capturée par un paramètre de l'entrée bien choisi. Cette thèse comporte deux objectifs. Dans un premier temps, nous proposons d'étudier et d'appliquer les méthodes classiques de ces deux domaines afin d'obtenir des résultats positifs et négatifs pour deux problèmes d'optimisation dans les graphes : un problème de partition appelé Sparsest k-Compaction, et un problème de recherche d'un sous-graphe avec une cardinalité fixée appelé Sparsest k-Subgraph. Dans un second temps, nous présentons comment les méthodes de ces deux domaines ont pu se combiner ces dernières années pour donner naissance au principe d'approximation paramétrée. En particulier, nous é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

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

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

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

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

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

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.

Developed predictive models, especially models based on probabilistic concept, regarding numerous potential combinatory states can be very complex. That complexity can cause uncertainty about which factors should have which values to achieve optimal value of output. An example of that problem is developed with a Bayesian network with numerous potential states and their interaction when we would like to find optimal value of nodes for achieving maximum probability on specific output node. This chapter shows a novel concept based on usage of the particle swarm optimization algorithm for finding optimal values within developed probabilistic models.