Le but de cette thèse est de proposer des méthodes générales afin de contourner l’intractabilité de problèmes d’optimisation multi-objectifs.Dans un premier temps, nous essayons d’apprécier la portée de cette intractabilité en déterminant une borne supérieure, facilement calculable, sur le nombre de points non dominés, connaissant le nombre de valeurs prises par chaque critère.Nous nous attachons ensuite à produire des représentations discrètes et tractables de l’ensemble des points non dominés de toute instance de problèmes d’optimisation multi-objectifs. Ces représentations doivent satisfaire des conditions de couverture, i.e. fournir une bonne approximation, de cardinalité, i.e. ne pas contenir trop de points, et si possible de stabilité, i.e. ne pas contenir de redondances. En s’inspirant de travaux visant à produire des ensembles ε-Pareto de petite taille, nous proposons tout d’abord une extension directe de ces travaux, puis nous axons notre recherche sur des ensembles ε-Pareto satisfaisant une condition supplémentaire de stabilité. Formellement, nous considérons des ensembles ε-Pareto particuliers, appelés (ε, ε′)-noyaux, qui satisfont une propriété de stabilité liée à ε′. Nous établissons des résultats généraux sur les (ε, ε′)-noyaux puis nous proposons des algorithmes polynomiaux qui produisent des (ε, ε′)-noyaux de petite taille pour le cas bi-objectif et nous donnons des résultats négatifs pour plus de deux objectifs. / The goal of this thesis is to propose new general methods to get around the intractability of multi-objective optimization problems.First, we try to give some insight on this intractability by determining an, easily computable, upper bound on the number of nondominated points, knowing the number of values taken on each criterion. Then, we are interested in producingsome discrete and tractable representations of the set of nondominated points for each instance of multi-objective optimization problems. These representations must satisfy some conditions of coverage, i.e. providing a good approximation, cardinality, i.e. it does not contain too many points, and if possible spacing, i.e. it does not include any redundancies. Starting from works aiming to produce ε-Pareto sets of small size, we first propose a direct extension of these works then we focus our research on ε-Pareto sets satisfying an additional condition of stability. Formally, we consider special ε-Pareto sets, called (ε, ε′)-kernels, which satisfy a property of stability related to ε′. We give some general results on (ε, ε′)-kernels and propose some polynomial time algorithms that produce small (ε, ε′)-kernels for the bicriteria case and we give some negative results for the tricriteria case and beyond.

Este trabalho é dedicado ao estudo de propriedades teóricas dos operadores integrais positivos em \'L POT. 2\' (X; u), quando X é um espaço topológico localmente compacto ou primeiro enumerável e u é uma medida estritamente positiva. Damos ênfase à análise de propriedades espectrais relacionadas com extensões do Teorema de Mercer e ao estudo dos espaços de Hilbert de reprodução relacionados. Como aplicação, estudamos o decaimento dos autovalores destes operadores, em um contexto especial. Finalizamos o trabalho com a análise de propriedades de suavidade das funções do espaço de Hilbert de reprodução, quando X é um subconjunto do espaço euclidiano usual e u é a medida de Lebesgue usual de X / In this work we study theoretical properties of positive integral operators on \'L POT. 2\'(X; u), in the case when X is a topological space, either locally compact or first countable, and u is a strictly positive measure. The analysis is directed to spectral properties of the operator which are related to some extensions of Mercer\'s Theorem and to the study of the reproducing kernel Hilbert spaces involved. As applications, we deduce decay rates for the eigenvalues of the operators in a special but relevant case. We also consider smoothness properties for functions in the reproducing kernel Hilbert spaces when X is a subset of the Euclidean space and u is the Lebesgue measure of the space

Dans cette thèse, nous abordons des problèmes NP-difficiles à l'aide de techniques combinatoires, en se focalisant sur le domaine de la complexité paramétrée. Les principaux problèmes que nous considérons sont les problèmes de Multicoupe et d'Arbre Orienté Couvrant avec Beaucoup de Feuilles. La Multicoupe est une généralisation naturelle du très classique problème de coupe, et consiste à séparer un ensemble donné de paires de sommets en supprimant le moins d'arêtes possible dans un graphe. Le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles consiste à trouver un arbre couvrant avec le plus de feuilles possible dans un graphe dirigé. Les résultats principaux de cette thèse sont les suivants. Nous montrons que le problème de Multicoupe paramétré par la taille de la solution est FPT (soluble à paramètre fixé), c'est-à-dire que l'existence d'une multicoupe de taille $k$ dans un graphe à $n$ sommets peut être décidée en temps $f(k)*poly(n)$. Nous montrons que Multicoupe dans les arbres admet un noyau polynomial, c'est-à-dire est réductible aux instances de taille polynomiale en $k$. Nous donnons un algorithme en temps $O^*(3.72^k)$ pour le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles et le premier algorithme exponentiel exact non trivial (c'est-à-dire meilleur que $2^n$). Nous fournissons aussi un noyau quadratique et une approximation à facteur constant. Ces résultats algorithmiques sont basés sur des résultats combinatoires et des propriétés structurelles qui concernent, entre autres, les décompositions arborescentes, les mineurs, des règles de réduction et les $s-t$ numberings. Nous présentons des résultats combinatoires hors du domaine de la complexité paramétrée: une caractérisation des graphes de cercle Helly comme les graphes de cercle sans diamant induit, et une caractérisation partielle des classes de graphes 2-bel-ordonnées. / This thesis tackles NP-hard problems with combinatorial techniques, focusing on the framework of Fixed-Parameter Tractability. The main problems considered here are Multicut and Maximum Leaf Out-branching. Multicut is a natural generalisation of the cut problem, and consists in simultaneously separating prescribed pairs of vertices by removing as few edges as possible in a graph. Maximum Leaf Out-branching consists in finding a spanning directed tree with as many leaves as possible in a directed graph. The main results of this thesis are the following. We show that Multicut is FPT when parameterized by the solution size, i.e. deciding the existence of a multicut of size $k$ in a graph with $n$ vertices can be done in time $f(k)*poly(n)$. We show that Multicut In Trees admits a polynomial kernel, i.e. can be reduced to instances of size polynomial in $k$. We give an $O^*(3.72^k)$ algorithm for Maximum Leaf Out-branching and the first non-trivial (better than $2^n$) exact algorithm. We also provide a quadratic kernel and a constant factor approximation algorithm. These algorithmic results are based on combinatorial results and structural properties, involving tree decompositions, minors, reduction rules and $s-t$ numberings, among others. We present results obtained with combinatorial techniques outside the scope of parameterized complexity: a characterization of Helly circle graphs as the diamond-free circle graphs, and a partial characterisation of 2-well-quasi-ordered classes of graphs.

La super-résolution est une technique de traitement d'images qui consiste en la reconstruction d'une image hautement résolue à partir d'une ou plusieurs images bassement résolues.Cette technique est apparue dans les années 1980 pour tenter d'augmenter artificiellement la résolution des images et donc de pallier, de façon algorithmique, les limites physiques des capteurs d'images.Comme beaucoup des techniques de reconstruction en traitement d'images, la super-résolution est connue pour être un problème mal posé dont la résolution numérique est mal conditionnée. Ce mauvais conditionnement rend la qualité des images hautement résolues reconstruites très sensible au choix du modèle d'acquisition des images, et particulièrement à la modélisation de la réponse impulsionnelle de l'imageur.Dans le panorama des méthodes de super-résolution que nous dressons, nous montrons qu'aucune des méthodes proposées par la littérature ne permet de modéliser proprement le fait que la réponse impulsionnelle d'un imageur est, au mieux, connue de façon imprécise. Au mieux l'écart existant entre modèle et réalité est modélisé par une variable aléatoire, alors que ce biais est systématique.Nous proposons de modéliser l'imprécision de la connaissance de la réponse impulsionnelle par un ensemble convexe de réponses impulsionnelles. L'utilisation d'un tel modèle remet en question les techniques de résolution. Nous proposons d'adapter une des techniques classiques les plus populaires, connue sous le nom de rétro-projection itérative, à cette représentation imprécise.L'image super-résolue reconstruite est de nature intervalliste, c'est à dire que la valeur associée à chaque pixel est un intervalle réel. Cette reconstruction s'avère robuste à la modélisation de la réponse impulsionnelle ainsi qu'à d'autres défauts. Il s'avère aussi que la largeur des intervalles obtenus permet de quantifier l'erreur de reconstruction. / Super-resolution is an image processing technique that involves reconstructing a high resolution image based on one or several low resolution images. This technique appeared in the 1980's in an attempt to artificially increase image resolution and therefore to overcome, algorithmically, the physical limits of an imager.Like many reconstruction problems in image processing, super-resolution is known as an ill-posed problem whose numerical resolution is ill-conditioned. This ill-conditioning makes high resolution image reconstruction qualityvery sensitive to the choice of image acquisition model, particularly to the model of the imager Point Spread Function (PSF).In the panorama of super-resolution methods that we draw, we show that none of the methods proposed in the relevant literature allows properly modeling the fact that the imager PSF is, at best, imprecisely known. At best the deviation between model and reality is considered as being a random variable, while it is not: the bias is systematic.We propose to model scant knowledge on the imager's PSF by a convex set of PSFs. The use of such a model challenges the classical inversion methods. We propose to adapt one of the most popular super-resolution methods, known under the name of "iterative back-projection", to this imprecise representation. The super-resolved image reconstructed by the proposed method is interval-valued, i.e. the value associated to each pixel is a real interval. This reconstruction turns out to be robust to the PSF model and to some other errors. It also turns out that the width of the obtained intervals quantifies the reconstruction error.

Neste trabalho analisamos a positividade definida estrita de núcleos contínuos sobre um espaço compacto 2-homogêneo. R. Gangolli (1967) apresentou uma caracterização completa para os núcleos que são contínuos, isotrópicos e positivos definidos sobre um espaço compacto 2-homogêneo Md: a parte isotrópica do núcleo é uma série de Fourier uniformemente convergente, com coeficientes não negativos, em relação a certos polinômios de Jacobi atrelados a Md. Uma das contribuições de nosso trabalho é uma caracterização para a positividade definida estrita de tais núcleos, complementando a caracterização apresentada por Chen et al. (2003) no caso em que Md é uma esfera unitária de dimensão maior ou igual a 2. Outra contribuição do trabalho é uma extensão do resultado de Gangolli para núcleos sobre produtos cartesianos de espaços compactos 2-homogêneos, e a consequente caracterização para núcleos estritamente positivos definidos neste mesmo contexto. Por fim, a última contribuição do trabalho envolve a análise do grau de diferenciabilidade da parte isotrópica de um núcleo contínuo, isotrópico e positivo definido sobre Md e a aplicabilidade de tal análise em resultados envolvendo a positividade definida estrita. / In this work we analyze the strict positive definiteness of continuous kernels on compact two-point homogeneous spaces Md. R. Gangolli (1967) presented a complete characterization for continuous, isotropic and positive definite kernels on Md: the isotropic part of the kernel is a uniformly convergent Fourier series of certain Jacobi polynomials associated to Md, with nonnegative coefficients. One of the contributions of our work is a characterization for the strict positive definiteness of such kernels, completing that one presented by Chen et al. (2003) in the case Md is the unit sphere of dimension at least 2. Another contribuition of this work is an extension of Gangolli\'s result for kernels on a product of compact two-point homogeneous spaces, and the subsequent characterization of strict positive definiteness in this same context. Finally, the last contribution in this work involves the analysis of the differentiability of the isotropic part of a continuous, isotropic and positive definite kernel on Md and the applicability of such analysis in results involving the strict positive definiteness.

Cette étude a pour sujet les hypergraphes. / This study has for subject the hypergraphs.

Neste trabalho analisamos o papel das funções layout de um núcleo positivo definido K sobre um espaço topológico de Hausdor E com relação a duas propriedades específicas: a universalidade de K e a ortogonalidade no espaço de Hilbert de reprodução de K a partir de suportes disjuntos. As funções layout sempre existem mas podem não ser únicas. De uma maneira geral, a função layout e uma aplicação que transfere, convenientemente, informações do espaço E para um espaço com produto interno de dimensão alta, onde métodos lineares podem ser usados. Tanto a universalidade quanto a ortogonalidade pressupõem a continuidade do núcleo. O primeiro conceito exige que para cada compacto não vazio X de E, o conjunto de \"seções\" {K(., y) : y \'PERTENCE\' X} seja total no espaço de todas as funções contínuas com domínio X, munido da topologia da convergência uniforme. Um dos resultados principais do trabalho caracteriza a universalidade de um núcleo K através de uma propriedade de universalidade semelhante da função layout. A ortogonalidade a partir de suportes disjuntos almeja então a ortogonalidade de quaisquer duas funções do espaço de Hilbert de reprodução de K quando seus suportes não se intersectam / We analyze the role of feature maps of a positive denite kernel K acting on a Hausdorff topological space E in two specific properties: the universality of K and the orthogonality in the reproducing kernel Hilbert space of K from disjoint supports. Feature maps always exist but may not be unique. A feature map may be interpreted as a kernel based procedure that maps the data from the original input space E into a potentially higher dimensional \"feature space\" in which linear methods may then be used. Both properties, universality and orthogonality from disjoint supports, make sense under continuity of the kernel. Universality of K is equivalent to the fundamentality of {K(. ; y) : y \'IT BELONGS\' X} in the space of all continuous functions on X, with the topology of uniform convergence, for all nonempty compact subsets X of E. One of the main results in this work is a characterization of the universality of K from a similar concept for the feature map. Orthogonality from disjoint supports seeks the orthogonality of any two functions in the reproducing kernel Hilbert space of K when the functions have disjoint supports

<p>Computation-intensive algorithms require a high level of parallelism and programmability, which </p><p>make them good candidate for hardware acceleration using fine-grained processor arrays. Using </p><p>Hardware Description Language (HDL), it is very difficult to design and manage fine-grained </p><p>processing units and therefore High-Level Language (HLL) is a preferred alternative. </p><p> </p><p>This thesis analyzes HLL programming of fine-grained architecture in terms of achieved </p><p>performance and resource consumption. In a case study, highly computation-intensive algorithms </p><p>(interpolation kernels) are implemented on fine-grained architecture (FPGA) using a high-level </p><p>language (Mitrion-C). Mitrion Virtual Processor (MVP) is extracted as an application-specific </p><p>fine-grain processor array, and the Mitrion development environment translates high-level design </p><p>to hardware description (HDL). </p><p> </p><p>Performance requirements, parallelism possibilities/limitations and resource requirement for </p><p>parallelism vary from algorithm to algorithm as well as by hardware platform. By considering </p><p>parallelism at different levels, we can adjust the parallelism according to available hardware </p><p>resources and can achieve better adjustment of different tradeoffs like gates-performance and </p><p>memory-performance tradeoffs. This thesis proposes different design approaches to adjust </p><p>parallelism at different design levels. For interpolation kernels, different parallelism levels and </p><p>design variants are proposed, which can be mixed to get a well-tuned application and resource </p><p>specific design.</p>

Computation-intensive algorithms require a high level of parallelism and programmability, which make them good candidate for hardware acceleration using fine-grained processor arrays. Using Hardware Description Language (HDL), it is very difficult to design and manage fine-grained processing units and therefore High-Level Language (HLL) is a preferred alternative. This thesis analyzes HLL programming of fine-grained architecture in terms of achieved performance and resource consumption. In a case study, highly computation-intensive algorithms (interpolation kernels) are implemented on fine-grained architecture (FPGA) using a high-level language (Mitrion-C). Mitrion Virtual Processor (MVP) is extracted as an application-specific fine-grain processor array, and the Mitrion development environment translates high-level design to hardware description (HDL). Performance requirements, parallelism possibilities/limitations and resource requirement for parallelism vary from algorithm to algorithm as well as by hardware platform. By considering parallelism at different levels, we can adjust the parallelism according to available hardware resources and can achieve better adjustment of different tradeoffs like gates-performance and memory-performance tradeoffs. This thesis proposes different design approaches to adjust parallelism at different design levels. For interpolation kernels, different parallelism levels and design variants are proposed, which can be mixed to get a well-tuned application and resource specific design.

Les traitements de radiothérapie nécessitent la délivrance d'une dose précise au niveau de la tumeur et une bonne connaissance de la dose dans les zones avoisinantes. Ce calcul, habituellement réalisé par les TPS, exige des outils précis et rapides. La plate-forme de simulation Monte-Carlo GATE, basée sur le code GEANT4, offre un outil performant pour les applications de la médecine nucléaire mais aussi des fonctionnalités permettant de faire des calculs dosimétriques de façon fiable et rapide. Dans cette thèse, deux études ont été menées en parallèle: la validation de la plate-forme GATE pour la modélisation de sources d'électrons et de photons de basse énergie et l'exploitation optimisée des infrastructures de grille informatique pour réduire les temps de calculs des simulations. GATE a été validé pour le calcul de points kernels de dose d'électrons mono-énergétiques et comparé avec les résultats d'autres études Monte-Carlo. Une étude détaillée a été faite sur la gestion du dépôt d'énergie au cours du transport des électrons dans GEANT4. Nous nous sommes intéressés aussi à la validation de GATE concernant le dépôt de dose de photons de très basse énergie ( < 35 keV). Pour cela, trois modèles de sources radioactives utilisés en curiethérapie et contenant de l'iode 125 (modèle 2301 de Best Medical International ; Symmetra de UroMed/Bebig et 6711 d'Amersham) ont été simulés. Plusieurs caractéristiques dosimétriques ont été étudiées selon les recommandations du groupe de travail N°43 de l'AAPM (American Association of Physicists in Medecine). Les résultats obtenus montrent une bonne concordance entre GATE et les études prises comme référence et recommandées par l'AAPM. L'utilisation de simulations Monte-Carlo dans les applications médicales pour une meilleure définition de la dose déposée dans un volume tumoral, nécessite des temps de calculs longs. Afin de réduire ces temps, nous avons exploité l'infrastructure de la grille EGEE sur laquelle nos simulations sont distribuées en utilisant des techniques novatrices pour la prise en compte de l'état de la grille de calcul. Les temps nécessaires pour la simulation d'une radiothérapie utilisant des électrons ont été réduits jusqu'à un facteur 30. Une plate-forme web basée sur le portail GENIUS a été développée pour rendre accessible de façon simple toutes les modalités de soumission et de gestion des simulations ainsi que la gestion de données médicales (informations sur les patients, images CT, IRM...) sur les ressources de la grille. L'objectif final visé est de faire de GATE un outil fiable et utilisé en clinique pour des planifications de traitements de radiothérapie avec des temps de calculs acceptables (pas plus de 12 heures de calcul).