Cette synthèse de travaux de recherche concerne l'algorithmique dans les graphes et l'utilisation de la pro- grammation linéaire et semidéfinie positive (SDP) dans le cadre de la résolution exacte ou approchée de plusieurs problèmes fondamentaux de l'Optimisation Combinatoire. L'approche semidéfinie, qui conduit à des relaxations convexes mais non-linéaires, a permis d'obtenir de remarquables résultats théoriques en approximation et devient à présent utilisable en pratique (tout comme la programmation linéaire qui en est un cas particulier). Nos travaux comportent une forte composante algorithmique et des études de complexité de plusieurs problèmes d'optimisation dans les graphes. Nous considérons tout d'abord le problème de la recherche d'un sous-graphe dense de taille fixée pour lequel nous présentons un algorithme polynomial avec ga- ranties de performances fondé sur la programmation linéaire et quadratique. Puis, nous étudions les problèmes de multiflots entiers et de multicoupes pour lesquels nous avons identifié de nombreux cas po- lynomiaux dans des graphes particuliers importants en pratique : arborescences, grilles, anneaux. D'une part, les solutions fractionnaires fournies par certaines relaxations linéaires de ces problèmes sont le point de départ d'algorithmes de résolution efficaces. D'autre part, les propriétés des programmes linéaires uti- lisés nous permettent également d'élaborer des algorithmes purement combinatoires et de démontrer leur validité (matrices totalement unimodulaires, théorème des écarts complémentaires). Nous proposons également des approches systématiques pour élaborer des relaxations semidéfinies pour les programmes quadratiques, modèles de très nombreux problèmes combinatoires et continus. Plus précisément, nous étudions les liens entre relaxations semidéfinies et des relaxations lagrangiennes partielles de programmes quadratiques contenant des contraintes linéaires. En particulier, les fonctions quadratiques constantes sur une variété affine sont entièrement caractérisées. Ceci permet de facilement comparer les différentes familles de contraintes redondantes proposées dans la littérature dans l'approche semidéfinie dans le cadre unifié de l'approche lagrangienne. Puis, nous présentons un algorithme pour élaborer des relaxations semidéfinies à partir de relaxations linéaires existantes. L'objectif est de pro- fiter des résultats théoriques et expérimentaux obtenus dans l'approche linéaire. Nous avons développé un logiciel (SDP_S) grâce à ces résultats. Il permet de formuler automatiquement et facilement des relaxations semidéfinies pour tout problème pouvant être formulé comme un programme quadratique en variables bivalentes. Notre méthode peut se généraliser à certains programmes à variables mixtes. Enfin, nous appliquons les méthodes décrites précédemment à une série de problèmes combinatoires classiques. Nos expérimentations montrent que l'approche semidéfinie est à présent pertinente dans la pra- tique sous certaines conditions. Premièrement, nous présentons des méthodes de séparation/évaluation efficaces fondées sur la SDP pour la résolution exacte des problèmes max 2sat et Vertex-Cover. Deuxièmement, nous proposons plusieurs bornes par SDP de grande qualité pour des problèmes particu- lièrement difficiles à résoudre par les approches linéaires : k-cluster, CMAP (un problème de placement de tâches avec contraintes de ressources), et le problème de l'affectation quadratique (QAP). Pour ce dernier nous présentons également un algorithme de coupes performant fondé sur la programmation semidéfinie. Afin d'obtenir des algorithmes efficaces en pratique, nous mettons en oeuvre non seulement nos méthodes d'élaboration de relaxations SDP, mais également des techniques algorithmiques issues de l'approximation polynomiale, ainsi que des outils spécifiques de résolution numérique des programmes semidéfinis.

Les travaux présentés dans cette thèse traitent de l'utilisation de la Réalité Virtuelle (RV) et plus particulièrement du retour d'effort pour améliorer l'interaction dans les applications de Conception Assistée par Ordinateur (CAO). Dans ce document, nous décrivons le rôle actuel du Product Lifecycle Management (PLM) dans l'industrie, et plus spécifiquement la place tenue par l'outil CAO. Celui-ci offre de nombreuses fonctionnalités pour l'édition d'une maquette en trois dimensions, mais, actuellement, ne bénéficie pas pleinement des méthodes d'interactions les plus récentes. Notre positionnement de recherche concerne l'utilisation des dispositifs de visualisation ainsi que les nouvelles méthodes d'interaction offertes par la RV, pour rendre l'édition de forme plus intuitive. Toutefois, de nombreuses applications industrielles du PLM, telles que l'assemblage ou l'ergonomie, utilisent déjà des solutions de RV pour augmenter l'interaction avec le produit. Afin de bien appréhender les solutions haptiques que nous proposons, un rappel des principaux concepts de la CAO est effectué, en particulier relatif à ses modèles de données (B-Rep, graphe d'historique, persistent naming). On décrit également les informations perceptibles autour de trois principales catégories : référents, informations géométriques et guides, puis les retours tactiles et d'efforts envisagés pour traduire les différents types d'informations que l'on peut rencontrer. Le travail du concepteur s'articulant autour de deux catégories de tâches : la sélection et la modification de la maquette CAO, nous avons structuré nos travaux de recherche en haptique autour de ces deux grandes classes. De fait, nous abordons ensuite les problématiques de sélection dans une maquette 3d, sélection assistée par des retours haptiques adaptés, et ce en particulier pour permettre une perception fine des composants topologiques. Dans un second temps, nous présentons deux tâches représentatives des activités de modification en CAO : l'édition de courbes et surfaces et l'extrusion. Ces deux fonctionnalités permettent de montrer l'apport de l'haptique pour la manipulation de paramètres sur deux types d'édition CAO très différents. Nous nous intéressons à l'impact de différents facteurs comme le contexte de réalisation de la tâche, la manipulation simultanée des paramètres, la cohabitation de multiples retours haptiques, ou la prise en main, par les tilisateurs, des solutions haptiques. L'analyse des expérimentations relatées dans cette thèse montre des résultats mitigés sur l'apport de l'haptique. Si ce canal sensorimoteur est généralement plebiscité, il convient néanmoins de faire attention au paramétrage des retours d'effort et à la mise en relation des différentes méthodes haptiques, au risque de gener le travail de l'utilisateur du système CAO. Au demeurant, une fois cet écueil évité, les perspectives de l'intégration de l'interaction haptique pour l'aide 'a l'édition CAO semblent prometteuses. Nous concluons cette recherche en esquissant la méthodologie d'intégration RV-CAO qu'il conviendrait de suivre pour mener à bien une évaluation complète de nos solutions avec des utilisateurs CAO experts.

Le monde médical dispose de plus en plus de sources d'images différentes, non seulement pour réaliser un diagnostic mais aussi pour évaluer l'efficacité d'un traitement et pour être guidé dans les interventions chirurgicales. Parallèlement, le développement des techniques opératoires s'oriente vers la chirurgie non " à ciel ouvert ", notamment la coelioscopie, qui permet de diminuer les risques liés à l'intervention ainsi que le temps d'hospitalisation du patient. En revanche, elle rend moins intuitive la réalisation de l'acte chirurgical, notamment du fait de la vision réduite à l'utilisation d'une ou plusieurs caméras dans la région d'intérêt. Durant ma thèse, j'ai conçu et mis en oeuvre des nouvelles méthodes informatiques de traitement 3D d'images radiologiques ainsi que de nouvelles utilisations médicales de ces images. Les contributions présentées concernent la visualisation et le traitement des données, la segmentation de structures 3D, la fusion mono et multimodale et l'aide à la réalisation d'interventions. Les applications présentées concernent notamment la planification et la réalisation d'interventions sous coelioscopie et de ponctions mais aussi l'imagerie industrielle. L'utilisation conjointe de différentes modalités d'images permet d'améliorer la visualisation, la manipulation et la compréhension de scènes tridimensionnelles, conduisant à une plus grande compréhension des observations et à une meilleure prise de décision.

La surveillance d'entrepôts de produits chimiques est une opération délicate dans le sens où elle passe par une connaissance de la nature de chaque produit stocké, sur leur localisation, sur leur possible interaction et sur les actions à mettre en œuvre en cas d'alerte. Pour faciliter cette gestion de stockage, cette thèse propose d'utiliser le concept de l'ambiant où le produit possède son propre système d'information et de communication sans fil de façon à le rendre intelligent et autonome. Cette thèse propose et développe un modèle de comportement interne de produit actif permettant une approche distribuée de sécurité active. Celui-ci permet d'aboutir à un protocole de communication de niveau applicatif à embarquer dans les produits actifs. Ce protocole est évalué de façon formelle en utilisant les Réseaux de Petri colorés hiérarchiques. Finalement, ce protocole est implémenté dans le simulateur Castalia/Omnet++ pour l'analyser dans plusieurs scénarii et aussi pour l'éprouver lors du passage à l'échelle. Les résultats montrent l'intérêt et la faisabilité du concept de produit actif.

Les avancées technologiques poussent l'industrie des télécommunications à fournir la capacité et la qualité nécessaire pour satisfaire la demande croissante de services sans fil à haut débit. De plus, avec les progrès des technologies d'accès, le goulot d'étranglement des réseaux cellulaires se déplace progressivement de l'interface radio vers le backhaul -- la partie de l'infrastructure du réseau qui fournit l'interconnexion entre les réseaux d'accès et de coeur. Aussi, la possibilité de déployer rapidement des liens radio micro-ondes efficaces est essentielle pour apporter des solutions crédibles au problème de l'engorgement des réseaux backhaul. Toutefois, les solutions de backhaul disponibles avec cette technologie ont reçu peu d'attention de la communauté scientifique. Pourtant, la croissance des réseaux backhaul et l'augmentation de leur complexité posent de nombreux problèmes d'optimisation très intéressants. En effet, contrairement aux réseaux filaires, la capacité d'un lien radio micro-ondes est sujette à variation, soit due à des facteurs extérieurs (météo), soit par l'action de l'opérateur. Cette différence fondamentale soulève une variété de nouvelles questions qui doivent être abordées de façon appropriée. Il faut donc concevoir des méthodes adéquates pour l'optimisation des réseaux backhaul. Dans cette thèse, nous étudions les problèmes d'optimisation de réseaux liés à la conception et la configuration des liaisons terrestres sans fil à micro-ondes. Nous nous intéressons en particulier à la classe des problèmes de multiflot de coût minimum avec des fonctions de coût en escalier sur les liens du réseau. Ces problèmes sont parmi les problèmes d'optimisation combinatoire les plus importants et les plus difficiles dans l'optimisation des réseaux, et il n'est généralement possible de les résoudre que de façon approchée. Nous introduisons des modèles mathématiques pour certains de ces problèmes et présentons des approches de solution basées essentiellement sur la programmation entière mixte, la programmation sous contraintes probabilistes, des techniques de relaxation, des méthodes de coupe, ainsi que des méta-heuristiques hybrides. Ces travaux ont été effectués en collaboration avec la PME~3Roam, et partiellement dans le cadre du projet RAISOM (Réseaux de Collecte IP sans fil optimisés) entre le projet Mascotte et les PMEs 3Roam et Avisto. Cette thèse a été développée en co-tutelle entre l'Université de Nice-Sophia Antipolis et l'Université Federale du Ceará.

Ce mémoire de thèse est consacré à l'étude de quelques problèmes de probabilités provenant de l'informatique théorique. Dans une première partie, nous étudions un algorithme probabiliste qui compte le nombre de mots différents dans une liste. Nous montrons que l'étude peut se ramener à un problème d'estimation, et qu'en modifiant légèrement cet algorithme, il est d'une certaine manière optimal. La deuxième partie est consacrée à l'étude de plusieurs problèmes de convergences pour des systèmes finis de particules, nous envisageons différents types de passage à une limite infinie. La première famille de systèmes considérés est une classe particulière d'automates cellulaires. En dimension 1, il apparaît des marches aléatoires dont nous caractérisons de façon complète les comportements limites. En dimension 2, sur une grille carrée, nous étudions quelques-un des cas les plus représentatifs. Nous en déterminons le temps moyen de convergence vers une configuration fixe. Enfin, nous étudions un modèle d'urnes avec des boules à deux états. Dans la troisième partie, nous étudions deux problèmes particuliers de marches aléatoires. Ces deux questions sont initialement motivées par l'étude de certains automates cellulaires, mais nous les présentons de façon indépendante. Le premier de ces deux problèmes est l'étude de marches aléatoires sur un tore discret, réfléchies les unes sur les autres. On montre la convergence de ce processus vers une limite brownienne. Nous étudions enfin de façon entièrement combinatoire une famille de marches aléatoires sur un intervalle, biaisées vers le bas. Nous en déterminons le temps moyen de sortie vers le haut.

Les techniques de tatouage de bases de données permettent la dissimulation d'information pertinente dans les n-uplets, comme par exemple l'identité du propriétaire des données. Les techniques de tatouage sont nombreuses dans le domaine multimédia, mais le tatouage des bases de données présente de nombreuses spécificités. Certaines d'entre elles sont traitées dans ce document : comment tatouer une base de données numérique tout en préservant le résultat de requêtes d'agrégat importantes, comment tatouer un flux structuré, comme un flux XML typé ou une partition musicale symbolique, comment tatouer une base de données géographiques.

La fusion d'informations consiste à résumer plusieurs informations provenant des différentes sources en une information exploitable et utile pour l'utilisateur. Le problème de la fusion est délicat surtout quand les informations délivrées sont incohérentes et hétérogènes. Les résultats de la fusion ne sont pas souvent exploitable et utilisables pour prendre une décision, quand ils sont imprécis. C'est généralement due au fait que les informations sont incohérentes. Plusieurs méthodes de fusion sont proposées pour combiner les informations imparfaites et elles appliquent l'opérateur de fusion sur l'ensemble de toutes les sources et considèrent le résultat tel qu'il est. Dans ce travail, nous proposons une méthode de fusion fondée sur l'Analyse Formelle de Concepts, en particulier son extension pour les données numériques : les structures de patrons. Cette méthode permet d'associer chaque sous-ensemble de sources avec son résultat de fusion. Toutefois l'opérateur de fusion est choisi, alors un treillis de concept est construit. Ce treillis fournit une classification intéressante des sources et leurs résultats de fusion. De plus, le treillis garde l'origine de l'information. Quand le résultat global de la fusion est imprécis, la méthode permet à l'utilisateur d'identifier les sous-ensemble maximaux de sources qui supportent une bonne décision. La méthode fournit une vue structurée de la fusion globale appliquée à l'ensemble de toutes les sources et des résultats partiels de la fusion marqués d'un sous-ensemble de sources. Dans ce travail, nous avons considéré les informations numériques représentées dans le cadre de la théorie des possibilités et nous avons utilisé trois sortes d'opérateurs pour construire le treillis de concepts. Une application dans le monde agricole, où la question de l'expert est d'estimer des valeurs des caractéristiques de pesticide provenant de plusieurs sources, pour calculer des indices environnementaux est détaillée pour évaluer la méthode de fusion proposée.

Dans l'ouvrage [DBB06], Dutré et al. énumèrent dix problèmes d'Illumination Globale non résolus. Parmi ceux-ci, huit sont liés à la mesure et à l'intégration de données réelles dans les simulations. Cette thèse, en quatre parties et trois annexes, s'intéresse à cette problématique. Tout d'abord, les simulations de la propagation de la lumière dans les domaines du rendu physiquement réaliste, de l'éclairage, de la télédétection, de la conception de systèmes optiques... sont envisagées comme résolutions numériques d'un problème d'optique, fédérées par la notion de " photosimulation ". Dans le cadre de l'équation de rendu, les modèles réalistes de sources et le principe de la mesure goniophotométrique en champ lointain sont alors rappelés. La représentation des interactions lumière-matière est ensuite introduite par une exploration de l'apparence macroscopique, qui amène au rappel de la Fonction de Distribution de la Réflectance Bidirectionnelle et Spectrale (SBRDF), de ses principales propriétés et modèles. Le problème de la mesure pratique de la SBRDF d'une surface dans le visible est ensuite exploré. Id est, une taxonomie des méthodes de la littérature est établie ; qui allègue en faveur du développement de nouvelles approches. Un dispositif innovant, multispectral imageant, est alors présenté. Il se fonde sur la capture de la projection de la SBRDF sur un écran lambertien 3/4-sphérique, par une caméra multispectrale grand angle, assemblage d'un objectif fisheye, d'un filtre dynamique LCTF et d'une caméra CCD 12 bits. L'extraction des images capturées de l'information de la SBRDF repose sur un modéle radiométrique, qui explicite la transformation de la lumière en niveaux des pixels, dans le formalisme physique. Ce modèle soulève des problèmes de reconstruction multispectrale et d'interréflexions, pour lesquels de nouveaux algorithmes de résolution sont implantés. Les mesures de SBRDF produites semblent très prometteuses. Dans la troisième partie, le problème de la reconstruction d'une fonction directionnelle, identifié comme fondamental en photosimulation, est traité dans le cadre de la reconstruction de SBRDF discrètes. Pour cela, les propriétés mathématiques souhaitables des fonctions reconstruites sont envisagées. Puis, à l'aune de ce corpus, les approches de la littérature sont discutées ; justifiant la recherche d'algorithmes plus performants. Une nouvelle méthode est alors proposée, fondée sur une double triangulation sphérique des échantillons, et une généralisation à la surface d'un triangle sphérique de l'interpolant spline cubique de Hermite. La fonction reconstruite est interpolante, dérivable, quasi-déterministe, ne présente pas l'artéfact bidirectionnel, intègre la métrique sphérique non euclidienne, et prend en compte le difficile problème du masquage. Qualitativement comme quantitativement, les résultats obtenus semblent plaider en faveur du surcroît de complexité théorique qu'induit cette approche. Dans la dernière partie, cet algorithme de reconstruction est appliqué au problème de la " photométrie en champ proche ", ou, la caractérisation d'une source réelle par un solide photométrique étendu. La supériorité théorique du modèle étendu est d'abord démontrée. Puis, un état de l'art de la photométrie en champ proche est réalisé ; justifiant la mise en œuvre d'une nouvelle approche. Un nouveau dispositif est alors présenté. Il repose sur le déplacement d'un vidéoluminancemètre, couplage original d'une caméra CCD 12 bits avec un luxmètre, le long d'une trajectoire hémisphérique relative à la source. Les procédures de calibrage de l'instrument - géométrique, radiométrique, et photométrique - sont explicitées. Les sources de lumière caractérisées par cette approche ont été jugées suffisamment probantes pour être intégrées aux photosimulations spectrales du CSTB

Cette thèse étudie les structures dont la théorie au second ordremonadique est décidable, et en particulier la hiérarchie à pile. Onpeut définir celle-ci comme la hiérarchie pour $n$ des graphesd'automates à piles imbriquées $n$ fois ; une définition externe, partransformations de graphes, est également disponible. Nous nousintéressons à l'exemple des ordinaux. Nous montrons que les ordinauxplus petits que $epsilon_0$ sont dans la hiérarchie, ainsi que des graphesporteurs de plus d'information, que l'on appelle "graphecouvrants''. Nous montrons ensuite l'inverse : tous les ordinaux de lahiérarchie sont plus petits que $epsilon_0$. Ce résultat utilise le fait queles ordres d'un niveau sont en fait isomorphes aux structures desfeuilles des arbres déterministes dans l'ordre lexicographique, aumême niveau. Plus généralement, nous obtenons une caractérisation desordres linéaires dispersés dans la hiérarchie. Dans un troisièmetemps, nous resserons l'intérêt aux ordres de type $omega$ --- les mots infinis --- pour montrer que les mots du niveau 2 sont les motsmorphiques, ce qui nous amène à une nouvelle extension au niveau 3