Thèse doctorat : Informatique : Villeurbanne, INSA : 2003. / Titre provenant de l'écran-titre. Bibliogr. p. 140-148.

Thèse de doctorat : Informatique : Lyon, École normale supérieure (sciences) : 2006. / Bibliogr. p. 161-175.

Reproduction de : Thèse de doctorat : Informatique, programmation et systèmes : Toulouse, INPT : 2004. / Titre provenant de l'écran-titre. Bibliogr. 71 réf.

Thèse doctorat : Biologie. Bioinformatique : Rennes 1 : 2007. / Bibliogr. p. 171-183.

Thèse de doctorat : Informatique : Nice : 2006. / Bibliogr. p. 95-100. Résumés en français, en anglais et en portugais.

La conception d'architectures de systèmes est une tâche complexe qui implique des enjeux majeurs. Au cours de cette activité, les concepteurs du système doivent créer des alternatives de conception et doivent les comparer entre elles afin de sélectionner l'architecture la plus appropriée suivant un ensemble de critères. Dans le but d'étudier différentes alternatives, les concepteurs doivent généralement limiter leur étude comparative à une petite partie de l'espace de conception qui peut être composé d'un nombre immense de solutions. Traditionnellement, le processus de conception d'architecture est principalement dirigé par le jugement et l'expérience des concepteurs, et les alternatives sélectionnées sont des versions adaptées de solutions connues. Le risque est donc de sélectionner une solution pertinente mais sous-optimale. Pour gagner en confiance sur l'optimalité de la solution retenue, la couverture de l'espace de conception doit être augmentée. L'utilisation de méthodes de synthèse calculatoire d'architecture a prouvé qu'elle était un moyen efficace pour supporter les concepteurs dans la conception d'artefacts d'ingénierie (structures, circuits électriques...). Pour assister les concepteurs de systèmes durant le processus de conception d'architecture, une méthode calculatoire pour les systèmes complexes est définie. Cette méthode emploie une approche évolutionnaire (algorithmes génétiques) pour guider le processus d'exploration de l'espace de conception vers les zones optimales. La population initiale de l'algorithme génétique est créée grâce à une technique de synthèse calculatoire d'architecture qui permet de créer différentes architectures physiques et tables d'allocations pour une architecture fonctionnelle donnée. La méthode permet d'obtenir les solutions optimales du problème de conception posé. Ces solutions peuvent être ensuite utilisées par les concepteurs pour des études comparatives plus détaillées ou pour des négociations avec les fournisseurs de systèmes.

Thèse (Ph. D.)--Université Laval, 2003. / Bibliogr.: f. [183]-196. Publié aussi en version électronique.

Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished

L'analyse des techniques d'approximation est centrale en géométrie algorithmique, pour des raisons pratiques comme théoriques. Dans cette thèse nous traitons de l'échantillonnage des structures géométriques et des algorithmes d'approximation géométriques en optimisation combinatoire. La première partie est consacrée à la combinatoire des hypergraphes. Nous débutons par les problèmes de packing, dont des extensions d'un lemme de Haussler, particulièrement le lemme dit de Shallow packing, pour lequel nous donnons aussi un minorant optimal, conjecturé mais pas établi dans les travaux antérieurs. Puis nous appliquons ledit lemme, avec la méthode de partition polynomiale récemment introduite, à l'étude d'un analogue combinatoire des régions de Macbeath de la géométrie convexe : les M-réseaux, pour lesquels nous unifions les résultats d'existence et majorations existants, et donnons aussi quelques minorants. Nous illustrons leur relation aux epsilon-réseaux, structures incontournables en géométrie combinatoire et algorithmique, notamment en observant que les majorants de Chan et al. (SODA 2012) ou Varadarajan (STOC 2010) pour les epsilon-réseaux (uniformes) découlent directement de nos résultats sur les M-réseaux. La deuxième partie traite des techniques de recherche locale appliquées aux restrictions géométriques de problèmes classiques d'optimisation combinatoire. En dix ans, ces techniques ont produit les premiers schémas d'approximation en temps polynomial pour divers problèmes tels que celui de calculer un plus petit ensemble intersectant pour un ensemble de disques donnés en entrée parmi un ensemble de points donnés en entrée. En fait, il a été montré que pour de nombreux tels problèmes, la recherche locale de rayon Θ (1/epsilon²) donne une (1 + epsilon)-approximation en temps n^{O(1/epsilon²)}. Savoir si l'exposant de n pouvait être ramené à o (1/epsilon²) demeurait une question ouverte. Nous répondons par la négative : la garantie d'approximation de la recherche locale n'est améliorable pour aucun desdits problèmes / The analysis of approximation techniques is a key topic in computational geometry, both for practical and theoretical reasons. In this thesis we discuss sampling tools for geometric structures and geometric approximation algorithms in combinatorial optimization. Part I focuses on the combinatorics of geometric set systems. We start by discussing packing problems in set systems, including extensions of a lemma of Haussler, mainly the so-called shallow packing lemma. For said lemma we also give an optimal lower bound that had been conjectured but not established in previous work on the topic. Then we use this lemma, together with the recently introduced polynomial partitioning technique, to study a combinatorial analogue of the Macbeath regions from convex geometry: Mnets, for which we unify previous existence results and upper bounds, and also give some lower bounds. We highlight their connection with epsilon-nets, staples of computational and combinatorial geometry, for example by observing that the unweighted epsilon-net bound of Chan et al. (SODA 2012) or Varadarajan (STOC 2010) follows directly from our results on Mnets. Part II deals with local-search techniques applied to geometric restrictions of classical combinatorial optimization problems. Over the last ten years such techniques have produced the first polynomial-time approximation schemes for various problems, such as that of computing a minimum-sized hitting set for a collection of input disks from a set of input points. In fact, it was shown that for many of these problems, local search with radius Θ(1/epsilon²) gives a (1 + epsilon)-approximation with running time n^{O(1/epsilon²)}. However the question of whether the exponent of n could be decreased to o(1/epsilon²) was left open. We answer it in the negative: the approximation guarantee of local search cannot be improved for any of these problems. The key ingredient is a new lower bound on locally expanding planar graphs, which is then used to show the impossibility results

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.