Dans le cadre de cette thèse, nous considérons la complexité paramétrée de problèmes NP- complets. Plus précisément, nous nous intéressons à l'existence d'algorithmes de noyau polynomiaux pour des problèmes d'édition de graphes et de relations. Nous introduisons en particulier la notion de branches, qui permet d'obtenir des algorithmes polynomiaux pour des problèmes d'édition de graphes lorsque la classe de graphes cible respecte une décomposition d'adjacence. Cette technique nous permet ainsi d'élaborer les premiers algorithmes de noyaux polynomiaux pour les problèmes CLOSEST 3-LEAF POWER, COGRAPH EDITION et PROPER INTERVAL COMPLETION. Concernant les problèmes d'édition de relations, nous étendons la notion de Conflict Packing, qui a déjà été utilisée dans quelques problèmes paramétrés et permet d'élaborer des algorithmes de noyau linéaires pour différents problèmes. Nous présentons un noyau linéaire pour le problème FEEDBACK ARC SET IN TOURNAMENTS, et adaptons les techniques utilisées pour obtenir un noyau linéaire pour le problème DENSE ROOTED TRIPLET INCONSISTENCY. Dans les deux cas, nos résultats améliorent la meilleure borne connue, à savoir un noyau quadratique. Finalement, nous appliquons cette tech- nique sur les problèmes DENSE BETWEENNESS et DENSE CIRCULAR ORDERING, obtenant à nouveau des noyaux linéaires, qui constituent les premiers algorithmes de noyau polynomiaux connus pour ces problèmes.

RESUME : Les recherches en matière d'innovation démontrent que tous les types d'entreprises sont concernés par le sujet. De même il est avéré que l'innovation, pour s'inscrire dans une réalité qualitative et acceptable économiquement, doit en permanence veiller à être en contact avec son marché. Simultanément à ces exigences, accentuées par l'accélération de la circulation de l'information, les entreprises sont amenées à organiser la recherche et l'innovation au sein de leurs organisations collectives respectives, de façon distribuée auprès de chacun de leurs acteurs. La part des services est croissante dans ce contexte complexe de pilotage de connaissances et de compétences requises, s'agissant des principales caractéristiques des intervenants. Les entreprises sont dès lors amenées à solliciter de plus en plus ces derniers dont principalement le client ou l'usager. Il occupe désormais une place centrale dans ces processus de partage de savoirs et de mise en œuvre de projets innovants. Piloter l'innovation dans les métiers de services, ne peut donc se limiter à une transposition de méthodes industrielles documentées et aujourd'hui bien connues. Innover ne peut être un métier seulement technique et la prise en compte de spécificités des métiers de services est indispensable. L'objectif de notre thèse est de proposer une caractérisation générale de méthodes et d'organisation R&D rendues possibles et efficaces dans une entreprise de services. Notre travail nous a permis d'identifier quatre volets dont les paramètres peuvent être ajustés en fonction des nécessités : 1-Un volet d'ingénierie : la gestion du risque dont l'objectif est de donner un socle tangible à notre modèle de fonctionnement ; 2-Un volet organisationnel, indissociable d'une approche par les sciences humaines et sociales, qui nous permet de modéliser ou caractériser la notion de pôle de compétences indispensable au bon fonctionnement de l'organisation. Il est possible de l'illustrer à la façon d'un cluster de connaissances, compétences et pratiques opérationnelles. 3-Un volet technique dont l'objectif est de faire émerger des outils de conception en lien avec les spécificités de chaque pratique de service. 4-Un volet économique peut optionnellement et avantageusement compléter l'approche que nous proposons afin de consolider notre schéma d'ensemble par la recherche d'une pertinence instantanée et mesurable de l'ensemble de nos actions et la quantification de la performance des outils utilisés à ce titre. Notre travail a fait l'objet de 2 communications dans des colloques nationaux et de 2 publications dans des revues nationales à comité de lecture. Une publication a été soumise dans une revue internationale à comité de lecture. Les recherches et les expérimentations que nous avons menées se sont appuyées sur le Pôle R&D du Groupe FLO, créé en 2008 et dirigé par l'auteur de la thèse. Cette réalisation unique dans le secteur de la restauration commerciale à table, constitue l'aboutissement de notre travail de recherche partenariale.

Dans cette thèse, nous nous sommes intéressés à deux problèmes industriels dans le domaine du transport. Le premier est un problème de conception de réseau de service avec gestion de ressources pour un transport régulier de fret. Le second est le problème de gestion de perturbation dans le domaine aérien, sujet du challenge ROADEF'2009. Dans les deux cas, il s'agit de problèmes pratiques difficiles qui comportent des contraintes complexes non standard. Le défi est d'autant plus marqué que les instances à résoudre sont de grandes tailles et que les problèmes comportent une dimension temporelle forte. Nous avons analysé la complexité des problèmes en étudiant la complexité de problèmes combinatoires purs, sous-problèmes au cœur de nos problèmes industriels. Nous présentons différentes formulations MIP du problème de conception d'un réseau de service avec gestion de flotte. Il ressort de notre étude que les formulations à base de cycles pour les véhicules sont très prometteuses. Finalement, nous présentons notre contribution au challenge ROADEF'2009. Nous proposons une méthode de résolution rapide, basée sur une décomposition, permettant de trouver de bonnes solutions à un problème industriel complexe en temps limité.

Le territoire rural de marge est une " entité paradoxale " à la fois tiraillée entre de puissants voisins, des influences culturelles différentes, mais disposant d'une personnalité singulière. Dotée de ressources endogènes limitées, elle est dépendante des aires urbaines de son environnement proche et lointain pour bénéficier d'emplois divers et bien rémunérés, ainsi que pour accéder à des services variés. Pour autant, elle continue à s'individualiser comme une entité propre. De par ses carences, le territoire rural de marge est tributaire d'apports exogènes. Toutefois, cette ouverture est très sélective et autorégulée. L'identité d'un tel territoire se joue à différentes échelles de temps dans une succession de phases d'ouverture et de refondation. Elle est un objet particulièrement complexe. Sa modélisation requiert une exploration, une analyse et une exploitation de cette complexité. Nous la relevons à différents niveaux : emboîtements d'échelle, liaison entre des acteurs divers, de même qu'entre ces acteurs et le territoire lui-même. Nous fondons notre approche de l'objet sur un présupposé majeur : l'identité d'un territoire se décline à l'échelle collective comme à l'échelle individuelle. Il existe entre l'identité territoriale collective et les identités territoriales individuelles une liaison complexe. Notre démarche consiste de ce fait à retrouver les dimensions de l'univers territorial collectif à partir de celles d'une collection d'individus représentatifs du territoire. Par conséquent, la pierre angulaire du travail a été la conception d'un modèle de l'identité territoriale individuelle, dont la traduction graphique est une silhouette. Le profil identitaire collectif est obtenu par la confrontation des profils individuels. L'application du modèle à l'Alsace Bossue et à deux périodes distantes de près de 100 ans a livré quelques résultats. En 1920-30, l'identité de l'Alsace Bossue est une identité insulaire étroite composant avec une ouverture très sélective à des espaces de circulation intergénérationnels. En 2010, l'identité est marquée par une plus grande ouverture, cependant régulée par un arbitrage et une tension généralisés entre des attaches et un besoin d'émancipation, ce que l'on appelle une synergie des contraires.

The primary goal of the thesis is to study localization of Laplacian eigenfunctions in bounded domains when an eigenfunction is mainly supported by a small region of the domain and vanishing outside this region. The high-frequency and low-frequency localization in simple and irregular domains has been investigated for both Dirichlet and Neumann boundary conditions. Three types of high-frequency localization (whispering gallery, bouncing ball, and focusing eigemodes) have been revisited in circular, spherical and elliptical domains by deriving explicit inequalities on the norm of eigenfunctions. In turn, no localization has been found in most rectangular domains that led to formulating an open problem of characterization of domains that admit high-frequency localization. Using the Maslov-type differential inequalities, the exponential decay of low-frequency Dirichlet eigenfunctions has been extensively studied in various domains with branches of variable cross-sectional profiles. Under an explicit condition, the L2-norm of an eigenfunction has been shown to exponentially decay along the branch with an explicitly computed decay rate. This rigorous upper bound, which is applicable in any dimension and for both finite and infinite branches, presents a new achievement in the theory of classical and quantum waveguides, with potential applications in microelectronics, optics and acoustics. For bounded quantum waveguides with constant cross-sectional profiles, a sufficient condition on the branch lengths has been derived for getting a localized eigenfunction. The existence of trapped modes in typical finite quantum waveguides (e.g L-shape, bent strip and cross of two strips) has been proven provided that their branches are long enough, with an accurate estimate on the required minimal length. The high sensitivity of the localization character of eigenmodes to the length of branches and to the shape of the waveguide may potentially be used for switching devices in microelectronics and optics. The properties of localized eigenmodes in a class of planar spectral graphs have been analyzed. An efficient divide-and-conquer algorithm for solving the eigenproblem of the Laplacian matrix of undirected weighted graphs has been proposed and shown to run faster than traditional algorithms. A spectral approach has been developed to investigate the survival probability of reflected Brownian motion in reactive media. The survival probabilities have been represented in the form of a spectral decomposition over Laplacian eigenfunctions. The role of the geometrical structure of reactive regions and its influence on the overall reaction rate in the long-time regime has been studied. This approach presents a mathematical basis for designing optimal geometrical shapes of efficient catalysts or diffusive exchangers.

La modélisation 3d automatique d'un environnement à partir d'images est un sujet toujours d'actualité en vision par ordinateur. Ce problème se résout en général en trois temps : déplacer une caméra dans la scène pour prendre la séquence d'images, reconstruire la géométrie, et utiliser une méthode de stéréo dense pour obtenir une surface de la scène. La seconde étape met en correspondances des points d'intérêts dans les images puis estime simultanément les poses de la caméra et un nuage épars de points 3d de la scène correspondant aux points d'intérêts. La troisième étape utilise l'information sur l'ensemble des pixels pour reconstruire une surface de la scène, par exemple en estimant un nuage de points dense.Ici nous proposons de traiter le problème en calculant directement une surface à partir du nuage épars de points et de son information de visibilité fournis par l'estimation de la géométrie. Les avantages sont des faibles complexités en temps et en espace, ce qui est utile par exemple pour obtenir des modèles compacts de grands environnements comme une ville. Pour cela, nous présentons une méthode de reconstruction de surface du type sculpture dans une triangulation de Delaunay 3d des points reconstruits. L'information de visibilité est utilisée pour classer les tétraèdres en espace vide ou matière. Puis une surface est extraite de sorte à séparer au mieux ces tétraèdres à l'aide d'une méthode gloutonne et d'une minorité de points de Steiner. On impose sur la surface la contrainte de 2-variété pour permettre des traitements ultérieurs classiques tels que lissage, raffinement par optimisation de photo-consistance ... Cette méthode a ensuite été étendue au cas incrémental : à chaque nouvelle image clef sélectionnée dans une vidéo, de nouveaux points 3d et une nouvelle pose sont estimés, puis la surface est mise à jour. La complexité en temps est étudiée dans les deux cas (incrémental ou non). Dans les expériences, nous utilisons une caméra catadioptrique bas coût et obtenons des modèles 3d texturés pour des environnements complets incluant bâtiments, sol, végétation ... Un inconvénient de nos méthodes est que la reconstruction des éléments fins de la scène n'est pas correcte, par exemple les branches des arbres et les pylônes électriques.

A PARTIR DU FORMALISME DES SYSTEMES DE REGLES DE DECISION, ON DEFINIT DEUX TYPES DE PROCESSUS DECISIONNELS: LES PROCESSUS FERMES (PDF) PORTANT SUR DES SYSTEMES REPRESENTES DANS DES ESPACES FINIS; ET LES PROCESSUS OUVERTS (PDO) POUR DES SYSTEMES A ESPACES D'ETATS INFINIS. ON CONSIDERE CES PROCESSUS COMME DES ALGORITHMES PARTICULIERS ET ON S'INTERESSE A LEUR MODELISATION, LEUR ANALYSE ET L'OPTIMISATION DE LEUR COMPLEXITE, SELON DIFFERENTS CRITERES, EN TENANT COMPTE DE LA COMPLEXITE DE LA TACHE D'OPTIMISATION ELLE-MEME. LA CARACTERISATION DE CETTE TACHE, EN TANT QUE PROBLEME NP-DUR AU SENS FORT ET APPROXIMATION NP-DUR, CONDUIT A DEVELOPPER DES SCHEMAS D'APPROXIMATION QUI GENERALISENT LES ALGORITHMES DE RECHERCHE HEURISTIQUE DANS LES GRAPHES ET HYPERGRAPHES EN PROCEDURES EPSILON -ADMISSIBLES. DEUX PROCESSUS DECISIONNELS EN ROBOTIQUE SONT TRAITES: L'UN FERME PORTANT SUR L'APPRENTISSAGE D'UN CLASSIFIEUR POUR L'IDENTIFICATION D'OBJETS, ET L'AUTRE OUVERT POUR LA GENERATION DE PLANS

Ces dernières années ont connu l'avènement des réseaux sans fil, dopés par leur facilité de déploiement et par leur usage dans de multiples domaines : réseaux domestiques Wi-Fi, téléphonie mobile, réseaux ad-hoc, réseaux de capteurs, ... L'objet de cette thèse porte sur l'étude de problèmes algorithmiques directement inspirés des contraintes de fonctionnement rencontrées dans de tels réseaux, et se découpe en trois parties.<br />La première partie de nos travaux s'intéresse à l'étude du problème de la diffusion d'un message émis depuis un noeud source unique vers l'ensemble des noeuds participant au réseau. Ce problème est abordé dans plusieurs modèles de communication, qui supposent tous des émissions omnidirectionnelles à portée fixée et l'existence de phénomènes d'interférences. Il en résulte l'incapacité pour un noeud donné de garantir la réception correcte de deux transmissions voisines simultanées. Nous étudions la complexité de ce problème et proposons des stratégies de résolution exactes ou avec garantie de performance. <br />Dans une seconde partie, l'un des modèles de communication précédemment introduits sert de support à l'étude d'un autre problème algorithmique, dont l'objet est la satisfaction de requêtes de communications. Les travaux menés sur ce problème visent à établir sa complexité ainsi que les facteurs dont elle dépend. <br />La dernière partie nous amène au problème de conception de réseaux sans fil. L'objectif est d'assurer une distribution de flux depuis des noeuds sources vers des noeuds clients, en minimisant le coût de l'infrastructure déployée. Les communications établies ici à l'aide d'antennes directionnelles ne sont pas sujettes aux phénomènes d'interférences. La difficulté du problème réside dans la satisfaction de contraintes de déploiement (nombre d'antennes limitées par noeud, résistance aux pannes, ...). Nous étudions la complexité de ce problème, et proposons plusieurs méthodes de résolution exactes et approchées pour des instances de taille raisonnable.

Ce manuscrit de thèse développe certains aspects autour de trois thèmes généraux, sur la représentation arborescente des familles d'ensembles, les décompositions de graphes, et les algorithmes de graphes. Les thèmes abordés vont de la combinatoire théorique à l'algorithmique en bio-informatique, en passant par plusieurs décompositions de graphes et aussi par l'optimisation combinatoire.<br /><br />La première moitié du manuscrit développe deux études. D'abord, afin d'estimer le nombre de familles d'ensembles satisfaisant certains axiomes de clôture, de nouveaux outils et techniques pour obtenir des représentations arborescentes de celles-ci ont été développés. Puis, l'étude se poursuit avec une des applications des propriétés ci-dessus : celle concernant les décompositions de graphes.<br /><br />La deuxième moitié du manuscrit est consacrée aux applications des décompositions de graphes dans l'algorithmique de graphes. Trois problèmes algorithmiques seront à l'étude.<br />Dans chacun des trois, il est montré pourquoi et comment on peut appliquer l'idée de la décomposition de graphes pour résoudre le problème posé de manière efficace.<br />Il est également montré comment appliquer les trois solutions proposées pour résoudre trois autres problèmes d'algorithmique de graphes.

Apprendre une nouvelle langue signifie exploiter, plus ou moins consciemment,l'espace de la proximité du système linguistique cible avec d'autres langues. Cette proximité encourage les transferts entre les systèmes linguistiques, qui acquièrent une valeur positive ou négative à l'intérieur de l'interlangue vue comme le troisième système linguistique développé par l'apprenant, différent de la langue source et de la langue cible. Nous nous intéressons à ces transferts et à l'influence que ceux-ci exercent sur l'interlangue, dans le cas des apprenants roumains de FLE, étudiant aussi l'italien et l'espagnol. L'analyse des données nous permet de rendre compte du rapport qui s'établit entre la conformité avec la norme et la complexité de l'interlangue et aussi de déterminer le rôle des transferts linguistiques positifs et négatifs par rapport à ces deux dimensions de l'interlangue (la complexité et la conformité)