Le probleme du voyageur de commerce, note TSP, consiste a trouver un parcours de longueur minimum que doit emprunter un voyageur pour visiter une et une seule fois chaque ville s'il demarre de la ville de son domicile et y revient en fin de parcours. Dans cette these, nous etudions une generalisation de ce probleme. Si on regroupe les villes par pays, on s'interesse a un parcours de longueur minimum qui visite une et une seule ville de chaque pays. Cette generalisation est ainsi appelee probleme du voyageur de commerce international, note ITSP. Le ITSP est un probleme NP-difficile. Dans une premiere partie, nous decrivons des heuristiques pour le ITSP et nous evaluons numeriquement une nouvelle heuristique pour le TSP basee sur des notions introduites par Glover. Nous decrivons une reduction polynomiale du ITSP au TSP et nous donnons une nouvelle formulation du ITSP en un programme lineaire en nombres entiers. La deuxieme partie est reservee a l'approche de resolution polyedrale. Nous definissons la relaxation graphique du ITSP et nous donnons des resultats sur la dimension et la structure faciale du polyedre associe. Nous etudions la relation polyedrale qui existe entre le ITSP et sa relaxation graphique et nous introduisons plusieurs classes de facettes du polytope du ITSP. L'etude polyedrale du ITSP nous a permis de developper un algorithme de branchement et de coupe pour sa resolution. Nous presentons des heuristiques et des algorithmes exacts pour la separation de certaines classes de facettes et nous donnons les principales modifications qu'il faut apporter a un algorithme de branchement et de coupe pour le TSP afin d'obtenir un tel algoritme pour le ITSP. Nous finissons cette etude en donnant quelques resultats numeriques et une anlyse de l'implantation que nous avons realisee.

Nous présentons un ensemble de travaux sur l'intégration de méthodes formelles et l'analyse multifacette de systèmes logiciels. %deuxième partie Partant de l'idée que les différentes facettes d'un système doivent être étudiées et développées avec les formalismes et outils appropriés, nous avons exploré, suite à d'autres chercheurs, des pistes pour l'intégration de méthodes formelles utilisées pour spécifier, analyser ou développer des parties des systèmes. La nécessité de l'intégration est relative au besoin de l'interaction entre différentes parties d'un même système ou bien à l'appréhension globale des propriétés du système. Nous explicitons les principaux problèmes de l'intégration de méthodes formelles : l'hétérogénéité syntaxique, l'hétérogénétité sémantique et la variété des systèmes logiques de raisonnement. Nous proposons alors la notion de compatibilité relative à ces trois niveaux pour assurer l'intégration de méthodes. L'idée principale est celle de l'interopérabilité sur une base sémantique (base d'intégration) ) sans laquelle aucun raisonnement n'est possible entre des parties assemblées d'un système. Les raisonnements formels sont alors effectués par plongement (embedding) des spécifications dans des logiques appropriées. Ce premier cadre est généralisé à des domaines de compatibilité plus larges que les bases d'intégration, et qui permettent de s'affranchir des langages et de travailler au niveau des paradigmes sous-jacents aux langages ; on obtient ainsi un cadre pour une intégration générique. Nous avons montré comment les formalismes intégrés existants tels que LOTOS, CSP-B, Circus rentrent dans ce cadre et nous avons mis en oeuvre ces idées pour de nouvelles intégrations par exemple B et les réseaux de Pétri. Dans une autre partie des travaux, nous présentons des extensions proposées autour de la méthode B, notamment la composition parallèle asynchrone de systèmes abstraits B à la manière de la composition parallèle dans les algèbres de processus. Notre proposition permet de combiner dans un même projet de développement formel la démarche descendante de la méthode B par une approche ascendante. Nous présentons ensuite une méthode de construction systématique de spécifications B pour des systèmes multi-processus à architecture dynamique. Ces travaux généralisent les précédents sur la composition de systèmes abstraits en définissant un opérateur de fusion de sous-systèmes qui est plus général que les opérateurs de composition parallèle. Une partie des travaux est consacrée à l'analyse multifacette de système ; notre proposition consiste à assurer la compatibilité des analyses des différentes facettes en partant non pas de modèles indépendants mais de modèles spécifiques dérivés à partir d'un modèle de référence qui permet d'assurer la cohésion globale de l'analyse. Cette approche est poursuivie par des expérimentations sur la combinaison de prouveurs et d'évaluateurs de modèles (model-checkers). Nous avons exploré d'autres voies pour l'analyse multifacette : élaborer une algèbre de spécifications multiparadigmes, ou différents aspects, relatifs aux facettes envisagées, peuvent être introduits dans une même unité de spécification. Les unités de spécification sont ensuite composées à l'aide des opérateurs de l'algèbre. Le lien est fait entre cette approche et celle de l'intégration de méthodes par plongement dans des logiques formelles. Une plateforme expérimentale est développée conjointement à ces travaux et relie les deux approches : elle permettra à terme de traduire, moyennant la compatibilité sémantique, différents formalismes d'entrées dans des formalismes cibles en passant par un modèle de référence ou pivot qui lui même est une spécification multiparadigme.

Préserver la biodiversité est peut être un des plus grands défis de notre époque. Mais dès lors que l'on parle de biodiversité et non de diversité biologique s'ouvre un champ si vaste que ce terme nous amène au flou sémantique du mot nature. La biodiversité est un point de rencontre entre sciences de la nature et société. Avec l'avènement du Développement Durable, la biodiversité se trouve associée au progrès économique et social (Principe 5 de la Déclaration de Rio). Elle déborde du strict domaine de la protection de la nature, sa préservation devient critère, contrainte ou support de développement, bref indissociable désormais des politiques (Principe 4 ). Dépassant, d'un point de vue théorique comme d'un point de vue politique, toutes mesures objectives, les études de biodiversité croisent plusieurs champs de perceptions et de représentations, ceux des différentes sciences comme ceux des différents peuples. A ce carrefour, nous avons abordé la gestion locale de la Biodiversité en Guinée Maritime par niveaux d'intégration : relations à l'espèce, pratiques de l'écosystème et gestion territorial de l'éco-complexe. L'analyse menée au sein des objets géographiques, hybrides de nature et de culture, que sont la facette éco-paysagère et le territoire, montre à la fois l'interdépendance qui existe entre les trois niveaux d'intégration, comme les liens puissants qui se tissent entre faits sociaux et processus écologiques. Toutes ces interactions se conjuguent aujourd'hui en faveur du maintien de la diversité biologique comme de ses capacités de résilience, contrariant de fait les discours catastrophistes parfois tenus sur l'environnement en Afrique.

.

On établit la dimension de l'enveloppe convexe des couplages maximums d'un graphe, avec un résultat sur le cas des couplages parfaits. On étudie le squelette des polytopes. On démontre que si chaque sommet du polytope peut être représenté par un vecteur à valeurs 0 ou 1 alors ce squelette est soit un hypercube soit Hamilton connexe. On considère le polyèdre associé au problème du voyageur de commerce. Une méthode de décomposition permet de décrire entièrement ce polyèdre dans un cas particulier. Pour une version dite graphique de ce problème, on donne un ensemble d'inéquations nécessaires a la description du polyèdre associé.

Cette thèse présente quelques avancées sur la représentation efficace de l'apparence matérielle dans une simulation de l'éclairage. Nous présentons deux contributions : un algorithme pratique de simulation interactive pour rendre la réflectance mesurée avec une géométrie dynamique en utilisant une analyse fréquentielle du transport de l'énergie lumineuse et le shading hiérarchique et sur-échantillonnage dans un contexte deferred shading, et une nouvelle fonction de distribution pour le modèle de BRDF de Cook-Torrance. Dans la première partie, nous présentons une analyse fréquentielle de transport de l'éclairage en temps réel. La bande passante et la variance sont fonction de l'éclairage incident, de la distance parcourue par la lumière, de la BRDF et de la texture, et de la configuration de la géométrie (la courbure). Nous utilisons ces informations pour sous-échantillonner l'image en utilisant un nombre adaptatif d'échantillons. Nous calculons l'éclairage de façon hiérarchique, en un seul passage. Notre algorithme est implémenté dans un cadre de deferred shading, et fonctionne avec des fonctions de réflectance quelconques, y compris mesurées. Nous proposons deux extensions : pré-convolution de l'éclairage incident pour plus d'efficacité, et anti-aliasing utilisant l'information de fréquence. Dans la deuxième partie, nous nous intéressons aux fonction de réflectance a base de micro-facette, comme le modèle de Cook-Torrance. En nous basant sur les réflectances mesurées, nous proposons une nouvelle distribution des micro-facettes. Cette distribution, Shifted Gamma Distribution, s'adapte aux donnée avec plus de précision. Nous montrons également comment calculer la fonction d'ombrage et de masquage pour cette distribution. Dans un deuxième temps, nous observons que pour certains matériaux, le coefficient de Fresnel ne suit pas l'approximation de Schlick. Nous proposons une généralisation de cette approximation qui correspond mieux aux données mesurées. Nous proposons par ailleurs une nouvelle technique d'optimisation, canal par canal, en deux étapes. Notre modèle est plus précis que les modèles existants, du diffus au spéculaire.

Cette thèse présente quelques avancées sur la représentation efficace de l’apparence matérielle dans une simulation de l’éclairage. Nous présentons deux contributions : un algorithme pratique de simulation interactive pour rendre la réflectance mesurée avec une géométrie dynamique en utilisant une analyse fréquentielle du transport de l’énergie lumineuse et le shading hiérarchique et sur-échantillonnage dans un contexte deferred shading, et une nouvelle fonction de distribution pour le modèle de BRDF de Cook-Torrance. Dans la première partie, nous présentons une analyse fréquentielle de transport de l’éclairage en temps réel. La bande passante et la variance sont fonction de l’éclairage incident, de la distance parcourue par la lumière, de la BRDF et de la texture, et de la configuration de la géométrie (la courbure). Nous utilisons ces informations pour sous-échantillonner l’image en utilisant un nombre adaptatif d’échantillons. Nous calculons l’éclairage de façon hiérarchique, en un seul passage. Notre algorithme est implémenté dans un cadre de deferred shading, et fonctionne avec des fonctions de réflectance quelconques, y compris mesurées. Nous proposons deux extensions : pré-convolution de l’éclairage incident pour plus d’efficacité, et anti-aliasing utilisant l’information de fréquence. Dans la deuxième partie, nous nous intéressons aux fonction de réflectance a base de micro-facette, comme le modèle de Cook-Torrance. En nous basant sur les réflectances mesurées, nous proposons une nouvelle distribution des micro-facettes. Cette distribution, Shifted Gamma Distribution, s’adapte aux donnée avec plus de précision. Nous montrons également comment calculer la fonction d’ombrage et de masquage pour cette distribution. Dans un deuxième temps, nous observons que pour certains matériaux, le coefficient de Fresnel ne suit pas l’approximation de Schlick. Nous proposons une généralisation de cette approximation qui correspond mieux aux données mesurées. Nous proposons par ailleurs une nouvelle technique d’optimisation, canal par canal, en deux étapes. Notre modèle est plus précis que les modèles existants, du diffus au spéculaire. / This thesis presents some advances in efficient representation of material appearance in a lighting simulation. The scope of this thesis is two-fold: an interactive shading algorithm to render measured reflectance with dynamic geometry using frequency analysis of light transport and hierarchical shading and up-sampling in deferred shading context, and a new normal distribution function for the Cook-Torrance micro-facet BRDF model, along with a new shadowing and masking function and a generalization of Schlick’s approximation of the Fresnel term. In the first part, we introduce a real-time frequency analysis of light transport framework that allows us to estimate the bandwidth and variance of the shading integrand. The bandwidth and variance are a function of frequencies in the illumination, distance traveled by light, BRDF and texture, and the geometry configuration (curvature). We use this information to under-sample the image, and also use an adaptive number of samples for shading. We devise a single-pass hierarchical shading and up-sampling scheme to assemble an image out of the sparsely shaded image pixels. We extend our interactive technique to use pre-convolved shading for real-time performance. We also take advantage of the bandwidth information to perform multi-sample anti-aliasing in deferred shading by subsampling only a small portion of image pixels whose bandwidth is smaller than 1 pixel^-1. In the second part, we propose a new distribution function for the Cook-Torrance micro-facet BRDF, based on our observations on the reflectance measurements. We isolate the distribution components of the reflectance data and directly observe that existing distribution functions are insufficient. Then we devise the Shifted Gamma Distribution (SGD) fitting more accurately to the data. We derive the shadowing and masking function from the distribution. We observe that not all materials have the Fresnel behavior expected by Schlick’s approximation. Hence, we generalize the Schlick’s approximation to more accurately fit the model to the measurements. We introduce a two-step fitting approach, that fits each RGB channel separately — accounting for wave-length dependent effects. We show that our shading model outperforms existing models and accurately represents a wider range of materials from diffuse to glossy and highly specular materials.

Dans cette thèse, nous étudions l'enveloppe convexe des arbres binaires à racine sur n feuilles.Ce sont les arbres de Huffman dont les feuilles sont labellisées par n caractères. à chaque arbre de Huffman T de n feuilles, nous associons un point xT , appelé point de Huffman, dans l'espace Qn où xT est le nombre d'arêtes du chemin reliant la feuille du ième caractère et la racine.L'enveloppe convexe des points de Huffman est appelé Huffmanoèdre. Les points extrêmes de ce polyèdre sont obtenus dans un premier temps en utilisant l'algorithme d'optimisation qui est l'algorithme de Huffman. Ensuite, nous décrivons des constructions de voisinages pour un point de Huffman donné. En particulier, une de ces constructions est principalement basée sur la construction des sommets adjacents du Permutoèdre. Puis, nous présentons une description partielle du Huffmanoèdre contenant en particulier une famille d'inégalités définissant des facettes dont les coefficients, une fois triés, forment une suite de Fibonacci. Cette description bien que partielle nous permet d'une part d'expliquer la plupart d'inégalités définissant des facettes du Huffmanoèdre jusqu'à la dimension 8, d'autre part de caractériser les arbres de Huffman les plus profonds, i.e. une caractérisation de tous les facettes ayant au moins un plus profond arbre de Huffman comme point extrême. La contribution principale de ce travail repose essentiellement sur les liens que nous établissons entre la construction des arbres et la génération des facettes / In this thesis, we study the convex hull of full binary trees of n leaves. There are the Huffman trees, the leaves of which are labeled by n characters. To each Huffman tree T of n leaves, we associate a point xT , called Huffman point, in the space Qn where xT i is the lengths of the path from the root node to the leaf node marked by the ith character. The convex hull of the Huffman points is called Huffmanhedron. The extreme points of the Huffmanhedron are first obtained by using the optimization algorithm which is the Huffman algorithm. Then, we describe neighbour constructions given a Huffman point x. In particular, one of these constructions is mainly based on the neighbour construction of the Permutahedron. Thereafter, we present a partial description of the Huffmanhedron particularly containing a family of inequalities-defining facets whose coeficients follows in some way the law of the well-known Fibonacci sequence. This description allows us, on the one hand, to explain the most of inequalities-defining facets of the Huffmanhedron up to the dimension 8, on the other hand, to characterize the Huffman deepest trees, i.e a linear characterization of all the facets containing at least a Huffman deepest tree as its extreme point. The main contribution of this work is essentially base on the link what we establish between the Huffman tree construction and the facet generation.

Dans cette thèse, on s'intéresse à deux problèmes de conception de réseaux, utilisant la technologie OFDM multi-bandes. Le premier problème concerne la conception d'un réseau mono-couche avec contraintes spécifiques. Nous donnons une formulation en PLNE pour ce problème et étudions le polyèdre associé à sa restriction sur un arc. Nous introduisons deux familles d'inégalités valides définissant des facettes et développons un algorithme de coupes et branchements pour le problème. Nous étudions la variante multicouche du problème précédent et proposons plusieurs PLNE pour le modéliser. Nous identifions plusieurs familles de facettes et discutons des problèmes de séparation associés. Nous développons un algorithme de coupes et branchements utilisant l'ensemble des contraintes identifiées. Enfin, une formulation compacte et deux formulations basées sur des chemins sont proposées pour le problème. Nous présentons deux algorithmes de génération de colonnes et branchements pour le problème. / In this thesis we consider two capacitated network design (CND) problems, using OFDM multi-band technology. The first problem is related to single-layer network design with specific requirements. We give an ILP formulation for this problem and study the polyhedra associated with its arc-set restriction. We describe two families of facet defining inequalities. We devise a Branch-and-Cut algorithm for the problem. Next, we investigate the multilayer version of CND using OFDM technology. We propose several ILP formulations and study the polyhedron associated with the first (cut) formulation. We identify several classes of facets and discuss the related separation problem. We devise a Branch-and-Cut algorithm embedding valid inequalities of both single-layer and multilayer problems. The second formulation is compact, and holds a polynomial number of constraints and variables. Two further path formulations are given which yield two efficient Branch-and-Price algorithms for the problem.

Eine in vielen Bibliothekskatalogen bislang nicht verwirklichte Recherchefunktion ist die gezielte Suche nach Literatur aus bestimmten Fachgebieten. Recherchen mit Notationen der im Katalog verwendeten Klassifikation oder mit Schlagwörtern können den Anspruch an eine fachgebietsumfassende Suche meist nicht erfüllen. Eine mögliche Lösung ist die Entwicklung einer bibliotheksspezifischen fachlichen Facette, in der jeder Titel über seine sachlichen Erschließungsdaten einem oder mehreren Fächern zugeordnet wird. Im Vortrag wird nach einem Überblick über bereits vorhandene fachliche Facettierungsmöglichkeiten in verschiedenen Bibliothekskatalogen die Konzeption einer fachlichen Facette für den Bibliothekskatalog der Universitätsbibliothek Mannheim erläutert. Hierbei wurden im Besonderen die vorliegenden Sacherschließungsdaten sowie die fachlichen Schwerpunkte der Medienbestände der Universitätsbibliothek Mannheim berücksichtigt. Das Ziel war die Definition und die Zusammenstellung von Fächern, die im Bibliothekskatalog in unterschiedlichen Varianten umgesetzt und verwendet werden können.