The dissertation covers two problems motivated by computational biology: genome rearrangements, and haplotype networks. Genome rearrangement problems are a particular case of edit distance problems, where one seeks to transform two given objects into one another using as few operations as possible, with the additional constraint that the set of allowed operations is fixed beforehand; we are also interested in computing the corresponding distances between those objects, i.e. merely computing the minimum number of operations rather than an optimal sequence. Genome rearrangement problems can often be formulated as sorting problems on permutations (viewed as linear orderings of {1,2,...,n}) using as few (allowed) operations as possible. In this thesis, we focus among other operations on ``transpositions', which displace intervals of a permutation. Many questions related to sorting by transpositions are open, related in particular to its computational complexity. We use the disjoint cycle decomposition of permutations, rather than the ``standard tools' used in genome rearrangements, to prove new upper bounds on the transposition distance, as well as formulae for computing the exact distance in polynomial time in many cases. This decomposition also allows us to solve a counting problem related to the ``cycle graph' of Bafna and Pevzner, and to construct a general framework for obtaining lower bounds on any edit distance between permutations by recasting their computation as factorisation problems on related even permutations. Haplotype networks are graphs in which a subset of vertices is labelled, used in comparative genomics as an alternative to trees. We formalise a new method due to Cassens, Mardulyn and Milinkovitch, which consists in building a graph containing a given set of partially labelled trees and with as few edges as possible. We give exact algorithms for solving the problem on two graphs, with an exponential running time in the general case but with a polynomial running time if at least one of the graphs belong to a particular class. / La thèse couvre deux problèmes motivés par la biologie: l'étude des réarrangements génomiques, et celle des réseaux d'haplotypes. Les problèmes de réarrangements génomiques sont un cas particulier des problèmes de distances d'édition, où l'on cherche à transformer un objet en un autre en utilisant le plus petit nombre possible d'opérations, les opérations autorisées étant fixées au préalable; on s'intéresse également à la distance entre les deux objets, c'est-à-dire au calcul du nombre d'opérations dans une séquence optimale plutôt qu'à la recherche d'une telle séquence. Les problèmes de réarrangements génomiques peuvent souvent s'exprimer comme des problèmes de tri de permutations (vues comme des arrangements linéaires de {1,2,...,n}) en utilisant le plus petit nombre d'opérations (autorisées) possible. Nous examinons en particulier les ``transpositions', qui déplacent un intervalle de la permutation. Beaucoup de problèmes liés au tri par transpositions sont ouverts, en particulier sa complexité algorithmique. Nous nous écartons des ``outils standards' utilisés dans le domaine des réarrangements génomiques, et utilisons la décomposition en cycles disjoints des permutations pour prouver de nouvelles majorations sur la distance des transpositions ainsi que des formules permettant de calculer cette distance en temps polynomial dans de nombreux cas. Cette décomposition nous sert également à résoudre un problème d'énumération concernant le ``graphe des cycles' de Bafna et Pevzner, et à construire une technique générale permettant d'obtenir de nouvelles minorations en reformulant tous les problèmes de distances d'édition sur les permutations en termes de factorisations de permutations paires associées. Les réseaux d'haplotypes sont des graphes dont une partie des sommets porte des étiquettes, utilisés en génomique comparative quand les arbres sont trop restrictifs, ou quand l'on ne peut choisir une ``meilleure' topologie parmi un ensemble donné d'arbres. Nous formalisons une nouvelle méthode due à Cassens, Mardulyn et Milinkovitch, qui consiste à construire un graphe contenant tous les arbres partiellement étiquetés donnés et possédant le moins d'arêtes possible, et donnons des algorithmes résolvant le problème de manière optimale sur deux graphes, dont le temps d'exécution est exponentiel en général mais polynomial dans quelques cas que nous caractérisons.

Cette habilitation présente une vue d'ensemble de mes travaux concernant l'analyse statistique et algorithmique de la structure des réseaux, et en particulier des réseaux biologiques. Il est structuré en trois parties. La première concerne l'étude de modèles de graphes aléatoires, notamment ceux basés sur la notion de mélange. Les questions de l'estimation de leur paramètres et de la classification des sommets y sont notamment abordées. La seconde partie est consacrée au développement statistique de la détection de motifs dans les réseaux, et en particulier dans le cadre de la notion de motif local. Enfin, le troisième chapitre reprend des thèmes liés à l'algorithmique et à la théorie des graphes en illustrant par deux exemples l'importance de la structure des cycles d'un réseau.

L'organisation structurée (graphe avec hiérarchies et propriétés sémantiques) d'objets du plan implique plusieurs opérations complexes qui doivent être effectuées en toute sécurité de cohérence topologique. La précision inhérente d'une machine étant nécessairement limitée, il faut souvent recourir à une arithmétique exacte couteuse. Cette thèse présente, à partir de travaux liés à la réalisation du module de facettisation d'un simulateur de vol industriel, une solution permettant l'utilisation d'une arithmétique mixte, de précision arbitraire et de coût très inférieur statistiquement a la solution exacte. On y trouve aussi l'unification des méthodes de construction d'un diagramme de Voronoi, d'une triangulation de Delaunay pour un nuage de points dans le plan et de la triangulation contrainte de Delaunay de la représentation par segments d'un graphe planaire, autour d'une technique incrémentale optimale, fondamentalement plus simple que la méthode diviser-pour-résoudre classique. La technique incrémentale permet, par ailleurs, de donner un algorithme linéaire et très simple de construction du diagramme de Voronoi et de la triangulation de Delaunay d'un nuage de points situes sur la frontière d'un polygone monotone ou convexe.

Notre enquête a été conduite auprès de membres d'un groupe d'anciens élèves hébergé sur le site de réseau social professionnel LinkedIn. Elle a permis de produire deux résultats. Le premier résultat est une typologie des figures du réseautage en ligne. Nous proposons trois figures. Le NetMining, qui relève d'un usage exploratoire du site et oùl'utilisateur cumule de nombreux contacts. Le NetWorking où l'utilisateur sélectionne des relations sur la base de critères précis. Le NetSticking où l'utilisateur reproduit en ligne un réseau personnel basé sur la confiance. Ces trois tendances permettent de souligner deux caractéristiques propres aux pratiques de réseautage en ligne. D'une part, elles reposent surune pluralité de dispositifs de communication où LinkedIn occupe une place tantôt centrale, tantôt marginale. D'autre part, ces pratiques ne reposent pas nécessairement sur la poursuite d'une action planifiée. Le second résultat produit par notre enquête est un dispositif d'étude des pratiques de réseautage. Il associe des techniques de visualisation de graphes et analyses d'entretiens semi-directifs

Les travaux présentés dans cette thèse portent sur la modélisation des familles de produits. Ces travaux se placent fondamentalement dans le domaine de l'Ingénierie Intégrée ou du Concurrent Engineering et portent sur la conception intégrée modulaire de famille de produits, ils sont une suite des travaux développés au LAB par l'équipe Méthodologie de l'Assemblage. Dans ce mémoire, nous proposons une modélisation de famille de produits s'appuyant sur des concepts de modularité, les grammaires de graphe et sur les transformations matricielles. <br />Dans le chapitre 1, nous présentons les concepts et les problèmatiques liés aux nouvelles formes et organisation de conception ainsi que l'orientation de nos travaux.<br />Le chapitre 2 présente les concepts liéa à l'architecture modulaire. Des principes d'organisation d'une architecture de famille de produits sont proposés.<br />Le chapitre 3 utilise les grammaires de graphe pour la modélisation de familles de produits. Cet outil a le double avantage de s'appuyer sur une formulation mathématique et des représentations graphiques. Son choix pour la modélisation d'une famille de produits se justifie car il permet de mettre en évidence les liaisons complexes entre les modules et les composants de la famille, ceci à travers la manipulation de la génération des variantes. Le développement et l'application du modèle sur une étude de cas industrielle démontrent le potentiel apporté par ce type de modélisation. <br />Le chapitre 4 contribue à une réflexion sur la complexité en conception par une approche matricielle. A partir d'une analyse structurelle des familles de produits, nous proposons des matrices de décomposition reliant les exigences fonctionnelles aux composants génériques constants, partiels et variants. A partir d'un exemple, nous montrons comment structurer les solutions technologiques associées aux fonctions sous forme de matrices diagonales par bloc. Chacun de ces blocs peut être vu comme un module d'une famille de produits et permet de regrouper les solutions technologiques associées à la fonction de ce module. Cette représentation permet de traduire le passage du fonctionnel à l'organique.

La recherche de performances toujours plus élevées conduit les systèmes de positionnement à dynamique élevée à la limite de leurs possibilités technologiques et structurelles, invalidant de ce fait l'hypothèse classiquement retenue d'une dynamique d'ensemble assimilable à celle d'un corps rigide. Il s'ensuit que la commande du système ne peut plus sous-estimer l'influence des phénomènes vibratoires sur la qualité du suivi de profil, mais doit moduler les efforts moteurs afin de réaliser l'adéquation entre les caractéristiques intrinsèques au système et les critères de rapidité et de précision escomptés. Les travaux développés dans cette étude visent une amélioration du comportement dynamique du système par une action sur la génération de commande. La génération de commande s'articule autour de deux principales fonctions: (1) l'élaboration d'une loi de mouvement pour la ou les variables du système à contrôler servant de référence pour les asservissements (commande indirecte) (2) la définition d'une précommande transformant la loi de mouvement en un signal de référence pour l'entrée du système physique (commande directe). Ces deux fonctions, correctement gérées, permettent de découpler les problèmes de régulation et de suivi de profil. Dans un premier temps, elles sont traitées spécifiquement pour le cas du mouvement d'un système monoaxe. Ainsi, l'influence de différentes classes de lois de mouvement (harmoniques, polynomiales, polynomiales par morceaux ou bang-bang) sur les vibrations et la durée du mouvement est formalisée. Une méthodologie d'élaboration d'une précommande adaptée aux souplesses d'un axe est présentée elle permet de mettre en exergue les contrainte.

Les jeux des gendarmes et du voleur dans les graphes traitent de la<br />capture d'un voleur qui se déplace dans un réseau par une équipe de<br />gendarmes. Ces jeux trouvent leurs motivations en informatique<br />fondamentale, notamment dans le cadre de la théorie de la complexité<br />et dans celui de la théorie des mineurs de graphes. Ces jeux ont<br />également des applications en intelligence artificielle et en<br />robotique. Quel que soit le contexte, le nombre de gendarmes utilisés<br />a un coût et doit être minimisé. Dans cette thèse, nous étudions<br />diverses contraintes auxquelles les stratégies de capture sont<br />soumises, ainsi que le coût de ces contraintes en terme de nombre de<br />gendarmes. Nous distinguons principalement trois cadres d'étude.<br /><br />Dans la première partie de cette thèse, nous définissons une variante<br />de stratégie de capture qui établit un pont entre la largeur<br />arborescente et la largeur linéaire des graphes. En particulier, nous<br />prouvons la monotonie de cette variante générale et donnons un<br />algorithme exponentiel exact pour calculer de telles stratégies.<br /><br />Dans la seconde partie de cette thèse, nous nous intéressons aux<br />stratégies dites connexes qui doivent assurer que la partie propre du<br />réseau est constamment connexe. Nous prouvons plusieurs bornes<br />supérieures et inférieures du coût de cette contrainte en terme de<br />nombre de gendarmes. Nous étudions également la propriété de monotonie<br />des stratégies de capture connexe.<br /><br />Dans la troisième partie de cette thèse, nous étudions les stratégies<br />de capture dans un contexte décentralisé. Nous proposons plusieurs<br />algorithmes décentralisés qui permettent aux gendarmes de calculer<br />eux-mêmes la stratégie qu'ils doivent réaliser.

Reproduction de : Thèse de doctorat : Informatique : Université de Nice-Sophia Antipolis : 1996. / Résumés en français et en anglais. En annexe articles en anglais. L'Impr. INRIA a attribué un n° de coll, TU 386 associé à un code-barres en 4e de couv. Bibliogr. p. 79-82.

La vision permet aux animaux de recueillir une information riche et détaillée sur leur environnent proche ou lointain. Les machines ont aussi accès à cette information riche via leurs caméras. Mais, elles n'ont pas encore le logiciel adéquat leur permettant de la traiter pour transformer les valeurs brutes des pixels de l'image en information plus utile telle que la nature, la position, et la fonction des objets environnants. Voilà une des raisons pour laquelle il leur est difficile de se mouvoir dans un environnement inconnu, et d'interagir avec les humains ou du matériel dans des scénarios non-planifiés. Cependant, la conception de ce logiciel comporte de multiples défis. Parmi ceux-ci, il est difficile de comparer deux images entre elles, par exemple, afin que la machine puisse reconnaître que ce qu'elle voit est similaire à une image qu'elle a déjà vue et identifiée. Une des raisons de cette difficulté est que la machine ne sait pas, a priori, quelles parties des deux images se correspondent, et ne sait donc pas quoi comparer avec quoi. Cette thèse s'attaque à ce problème et propose une série d'algorithmes permettant de trouver les parties correspondantes entre plusieurs images, ou en d'autre terme d'aligner les images. La première méthode proposée permet d'apparier ces parties de manière cohérente en prenant en compte les interactions entre plus de deux d'entre elles. Le deuxième algorithme proposé applique avec succès une méthode d'alignement pour déterminer la catégorie d'un objet centré dans une image. Le troisième est optimisé pour la vitesse et tente de détecter un objet d'une catégorie donné où qu'il soit dans l'image.

Les systèmes de positionnement ont connu un progrès indéniable. Actuellement, la précision atteint quelques centimètres sous certaines conditions : espace ouvert, ciel dégagé, technique très spécifique, etc. Néanmoins, le problème du positionnement dans un environnement intérieur demeure persistant : les trajets multiples qui compliquent les modèles de propagation, l'atténuation, etc. Différents systèmes ont vu le jour, utilisant des technologies telles que l'UWB, le WiFi ou l'Infrarouge. Ces systèmes apportent des résultats de positionnement intéressants, atteignant l'ordre du mètre. Cette précision reste liée à certaines contraintes : une infrastructure, une technologie utilisée, une calibration, une technique de calcul, etc. Afin de réduire toutes ces contraintes, nous proposons une nouvelle approche de positionnement. Notre approche utilise tous les équipements réseaux présents dans un environnement. Elle se base sur deux étapes fondamentales : l'étude de visibilité et l'élaboration de liens géographiques. L'étude de visibilité permet d'obtenir les équipements visibles par un équipement. Nous avons exposé plusieurs modèles de visibilité et nous avons effectué une comparaison des résultats. L'élaboration de liens géographiques permet de construire un graphe géographique tridimensionnel reliant tous les équipements de l'environnement. Ce graphe nous permet de visualiser la répartition des équipements et d'estimer les positions géographiques de chaque équipement. Pour la mise en œuvre de notre approche, nous avons développé un simulateur sous Matlab. Le simulateur élaboré évalue d'abord le nombre d'équipements visibles. Il estime les distances séparant cet équipement de chaque équipement visible. Enfin, il construit un graphe géographique et calcul les positions géographiques. Des résultats de simulations sont présentés pour valider notre approche qui permet d'aboutir à un système capable d'opérer, sans aucune infrastructure additionnelle, un positionnement dans un environnement intérieur et extérieur