De nombreux problèmes de la vie réelle sont NP-Difficiles et ne peuvent pas être résolus en temps polynomial. Deux paradigmes notables pour les résoudre quand même sont: l'approximation et la complexité paramétrée. Dans cette thèse, on présente une nouvelle technique appelée "gloutonnerie-Pour-La-Paramétrisation". On l'utilise pour établir ou améliorer la complexité paramétrée de nombreux problèmes et également pour obtenir des algorithmes paramétrés pour des problèmes à cardinalité contrainte sur les graphes bipartis. En vue d'établir des résultats négatifs sur l'approximabilité en temps sous-Exponentiel et en temps paramétré, on introduit différentes méthodes de sparsification d'instances préservant l'approximation. On combine ces "sparsifieurs" à des réductions nouvelles ou déjà connues pour parvenir à nos fins. En guise de digestif, on présente des résultats de complexité de jeux comme le Bridge et Havannah. / Several real-Life problems are NP-Hard and cannot be solved in polynomial time.The two main options to overcome this issue are: approximation and parameterized complexity. In this thesis, we present a new technique called greediness-For-Parameterization and we use it to improve the parameterized complexity of many problems. We also use this notion to obtain parameterized algorithms for some problems in bipartite graphs. Aiming at establishing negative results on the approximability in subexponential time and in parameterized time, we introduce new methods of sparsification that preserves approximation. We combine those "sparsifiers" with known or new reductions to achieve our goal. Finally, we present some hardness results of games such as Bridge and Havannah.

O objetivo desse trabalho é o estudo dos operadores p-compactos e da propriedade de p-aproximação. Estes conceitos estão relacionados a importantes resultados de A. Gröthendieck sobre compacidade e a propriedade de aproximação que foram generalizados em [21] e estudados em [3], [6] e [7]. / The purpose of this work is the study of p-compact operators and the p-approximation property. These concepts are connected with important results by A. Gröthendieck about compactness and approximation property that were generalized in [21] and studied in [3], [6] and [7].

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.

This thesis is primarily concerned in studying the relationship between different exponents of Diophantine approximation, which are quantities arising naturally in the study of rational approximation to a fixed n-tuple of real irrational numbers. As Khinchin observed, these exponents are not independent of each other, spurring interest in the study of the spectrum of a given family of exponents, which is the set of all possible values that can be taken by said family of exponents. Introduced in 2009-2013 by Schmidt and Summerer and completed by Roy in 2015, the parametric geometry of numbers provides strong tools with regards to the study of exponents of Diophantine approximation and their associated spectra by the introduction of combinatorial objects called n-systems. Roy proved the very surprising result that the study of spectra of exponents is equivalent to the study of certain quantities attached to n-systems. Thus, the study of rational approximation can be replaced by the study of n-systems when attempting to determine such spectra. Recently, Roy proved two new results for the case n=3, the first being that spectra are semi-algebraic sets, and the second being that spectra are stable under the minimum with respect to the product ordering. In this thesis, it is shown that both of these results do not hold in general for n>3, and examples are given. This thesis also provides non-trivial examples for n=4 where the spectra is stable under the minimum. An alternate and much simpler proof of a recent result of Marnat-Moshchevitin proving an important conjecture of Schmidt-Summerer is also given, relying only on the parametric geometry of numbers instead. Further, a conjecture which generalizes this result is also established, and some partial results are given towards its validity. Among these results, the simplest, but non-trivial, new case is also proven to be true. In a different vein, this thesis considers certain generalizations theta(q) of the classical theta q-series. We show under conditions on the coefficients of the series that theta(q) is neither rational nor quadratic irrational for each integer q>1.

Huang Changquan. / "April 2002." / Thesis (Ph.D.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (p. 62-71). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. Ann Arbor, MI : ProQuest Information and Learning Company, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Mode of access: World Wide Web. / Abstracts in English and Chinese.

Les modifications physiologiques dans la configuration spatiale des organes pelviens sont de plus en plus diagnostiquées et traitées pour améliorer la qualité de vie des patientes. Le projet MoDyPe (ANR-09-SYSC-008) a été créé pour concevoir un simulateur chirurgical patiente-spécifique, et quantifier le geste médical en mode pré-opératoire. La modélisation géométrique des organes se fait à partir de nuages de points épars bruités. Les formes sont considérées fermées, lisses, creuses et à membrane épaisse. Le processus est décomposé en deux étapes : la construction de la surface et l'ajout d'une épaisseur.Afin de respecter les contraintes physiologiques, de manipuler la géométrie et de localiser précisément un point sur la surface, une B-spline de genre 0 au moins C1-continue est ajustée aux données. La fonction à minimiser est basée sur une énergie bidirectionnelle, caractérisant la dissimilarité des données sur l'échantillonnage et inversement. Sa réduction repose sur un schéma alternant re-paramétrisation et descente de gradient à pas optimal.Une surface-offset est ensuite générée vers l'intérieur de l'organe, via un maillage discret, en traitant le problème d'auto-intersection. Elle exploite la forme allongée des organes, grâce à un axe curviligne décrivant leur diamètre généralisé.Finalement, un maillage hexaédrique est créé à partir de la surface ajustée et de l'offset, qui sert à la simulation mécanique du comportement des organes à l'étape suivante du projet. / Physiological changes in the spatial configuration of the organs in the pelvic area are increasingly taken into account and treated to enhance the comfort of patients. MoDyPe project (ANR-09-SYSC-008 french support) has been created to develop a patient-specific simulator and to quantify the surgical gesture for preoperative purposes. The geometric modeling of the organs starts with noisy scattered point clouds. The shapes have been considered closed, smooth, hollow with a thick membrane. The process can be divided into two main parts: the construction of the surface and the addition of a thickness.In order to meet the physiological constraints, to manipulate the geometry and to accurately localize a point on the surface, a 0-genus B-spline surface is fitted to the data. It minimizes a bidirectional energy, characterizing the dissimilarities between the surface sampling and the input dataset. Its reduction is based on an alternate scheme between re-parametrization and optimal steepest descent step.Once achieved, an offset-surface is generated inwards, helped by a mesh to overcome self-intersection problems. The method created takes into account the elongated shapes of the organs, based on a curvilinear axis describing their generalized diameter.Finally, a hexahedral mesh is created from the fitted surface and its offset. It is the start point for the next step of the project consisting in mechanically simulating the dynamic behavior of the organs.

No description available.

Ce travail a pour cadre la diffusion des ondes électromagnétiques par une ou deux interfaces rugueuses séparant des milieux homogènes. Il s'intéresse plus particulièrement aux modèles asymptotiques, qui permettent de résoudre le problème posé de manière rapide, au détriment d'un domaine de validité restreint.<br />Pour le cas simple interface, après un panorama des méthodes existantes, une étude approfondie de l'approximation dite de Kirchhoff est menée pour le cas de la diffraction en réflexion et en transmission par une simple interface. Cette méthode est réduite à l'approximation dite de l'optique géométrique, valide pour des interfaces fortement rugueuses comparativement à la longueur d'onde, pour calculer plus simplement et plus rapidement la puissance diffusée. Le phénomène d'ombrage de la surface, bien connu pour le cas de la réflexion, l'est beaucoup moins pour le cas de la transmission ; c'est pourquoi il est étudié en détail dans cette thèse. <br />Pour le cas double interface, une étude bibliographique des méthodes existantes nous permet de constater l'absence de méthode basée sur l'extension de l'approximation de Kirchhoff au cas de deux interfaces fortement rugueuses. Ainsi, la méthode développée dans cette thèse permet de pallier ce manque. Cette méthode est exposée en supposant que les deux surfaces sont décorrélées, afin de pouvoir obtenir une expression de la puissance diffusée simple à mettre en œuvre. Par comparaison avec une méthode numérique de référence, la méthode développée a été validée dans le cas bidimensionnel. Une application à la détection de nappes de pétrole sur la surface de la mer est présentée, et la méthode est étendue au cas tridimensionnel.

On propose des conditions de bout pour les fonctions spines polynomiales d'interpolation de degré p (p≥2) associées aux abscisses équidistantes qui économisent le calcul et entraînent un ordre de convergence optimal. Cette fonction spline peut être interprétée comme une fonction spline cardinale tronquée avec une correction convenable. La technique utilisée pour les fonctions splines polynomiales est applicable dans le cas des fonctions splines sous tension. On donne aussi quelques résultats pour les fonctions splines cubiques de lissage

On étudie le problème de l'interpolation et du lissage de données avec conditions de forme (positivité, monotonie, convexité) dans le plan réel. Pour sa résolution on utilise cinq classes de méthodes :1) splines polynomiales, 2) splines rationnelles, 3) splines sous tension, 4) programmation mathématique, 5) splines avec repoussoir