La connectivité marine est le transfert de larves et/ou d'individus entre des habitats marins éloignés. Grâce à la connectivité, les populations marines éloignées peuvent faire face à la pression de l'habitat en s'appuyant sur le transfert qui vient des populations éloignées de la même espèce. Le transfert entre les populations éloignées dans l'océan est possible par le transport dû aux courants. Cependant, il est pas encore clair si le champ des courants détermine totalement la persistance des espèces marines ou si la démographie locale joue un rôle. Les mesures in situ de la connectivité sont extrêmement difficiles. Par conséquence, notre connaissance de la connectivité est déduite des simulations numériques de dispersion. Le but de cette thèse est de préciser si la persistance de la connaissance du champ des courants et d’étudier l'effet des paramétrisations numériques dans l'estimation de la connectivité. Premièrement, je compare la théorie des graphes et le modèle de métapopulation pour déterminer si les courants ont un rôle prédominant. Cela permet d'identifier quelles mesures de la théories des graphes identifient de manière fiable les sites reproductifs importants pour la persistance en s'appuyant sur la connaissance des seuls courants. Deuxièmement, j’étudie les avantages et les lacunes de différents schémas de fermeture de turbulence. Ceci permet de préciser quel schéma reproduit mieux l'activité de turbulence dans des modèles numériques. Troisièmement, j'étudie les mécanismes générateurs de turbulence aux limites du fond. Ceci permet de connaître le coefficient de traînée effectif dû aux flux sur la topographie brute et de mieux estimer les flux turbulents. / Marine connectivity is the transfer of larvae and/or individuals between distant marine habitats. Thanks to connectivity, distant marine population can face habitat pressure by relying on the transfer from distant populations of the same species. The transfer between distant populations in the ocean is made possible by the transport due to the currents. However, it is still not clear if the current field totally determines the persistence of the marine species or if the local demography plays a role. Crucially, in situ measurements of connectivity are extremely difficult. Therefore, our knowledge about connectivity is inferred from numerical dispersal simulations. The aim of this thesis is to clarify if we can deduce the persistence from the knowledge of the current field and to investigate the effect of numerical turbulence parameterizations in estimating connectivity. Firstly, I compare graph theory and metapopulation model to determine if currents have a predominant role. This allows to identify which graph theory measures reliably identifies reproductive sites important for persistence by relying on the knowledge of currents only. Secondly, I investigate the advantages and shortcomings of different turbulence closure models. This allows to clarify which TCS better reproduces turbulence activity in numerical models. Thirdly, I investigate generating mechanisms of bottom boundary turbulence. This allows to know the effective drag coefficient due to flow over rough topography and better estimate turbulent fluxes.

Cette thèse porte sur l'extraction de descripteurs hiérarchiques et multi-échelles d'images, en vue de leur interprétation, caractérisation et segmentation. Elle se décompose en deux parties.La première partie expose des éléments théoriques et méthodologiques sur l'obtention de classifications hiérarchiques des nœuds d'un graphe valué aux arêtes. Ces méthodes sont ensuite appliquées à des graphes représentant des images pour obtenir différentes méthodes de segmentation hiérarchique d'images. De plus, nous introduisons différentes façons de combiner des segmentations hiérarchiques. Nous proposons enfin une méthodologie pour structurer et étudier l'espace des hiérarchies que nous avons construites en utilisant la distance de Gromov-Hausdorff entre elles.La seconde partie explore plusieurs applications de ces descriptions hiérarchiques d'images. Nous exposons une méthode pour apprendre à extraire de ces hiérarchies une bonne segmentation de façon automatique, étant donnés un type d'images et un score de bonne segmentation. Nous proposons également des descripteurs d'images obtenus par mesure des distances inter-hiérarchies, et exposons leur efficacité sur des données réelles et simulées. Enfin, nous étendons les potentielles applications de ces hiérarchies en introduisant une technique permettant de prendre en compte toute information spatiale a priori durant leur construction. / This thesis deals with the extraction of hierarchical and multiscale descriptors on images, in order to interpret, characterize and segment them. It breaks down into two parts.The first part outlines a theoretical and methodological approach for obtaining hierarchical clusterings of the nodes of an edge-weighted graph. In addition, we introduce different approaches to combine hierarchical segmentations. These methods are then applied to graphs representing images and derive different hierarchical segmentation techniques. Finally, we propose a methodology for structuring and studying the space of hierarchies by using the Gromov-Hausdorff distance as a metric.The second part explores several applications of these hierarchical descriptions for images. We expose a method to learn how to automatically extract a segmentation of an image, given a type of images and a score of evaluation for a segmentation. We also propose image descriptors obtained by measuring inter-hierarchical distances, and expose their efficiency on real and simulated data. Finally, we extend the potential applications of these hierarchies by introducing a technique to take into account any spatial prior information during their construction.

Le concept de radio logicielle (SDR) est une solution pertinente pour concevoir des équipements multi-standards. Une façon de réaliser de tels équipements est d'identifier les fonctions et opérateurs communs entre les standards. Cette approche s’appelle la paramétrisation et est divisée en deux catégories : l'approche pragmatique qui est une version pratique pour créer et développer des opérateurs communs à partir d’opérateurs existants, et l'approche théorique dont l’objectif est de réaliser une exploration graphique d’un équipement multi-standards selon différents niveaux de granularité, accompagnée d’un problème d'optimisation. C’est cette dernière approche qui a constitué le sujet de base de cette thèse. Ainsi, une fonction de coût doit être optimisée afin de sélectionner les opérateurs communs entre les différentes normes, ce qui permet de proposer une configuration optimale à partir de laquelle sont déduits les opérateurs communs. Dans notre travail, nous avons dans un premier temps modélisé théoriquement la structure graphique d’un système multi-standards par un hypergraphe orienté. En outre, nous avons fourni une expression mathématique alternative de la fonction de coût suggérée, en utilisant des définitions propres à la théorie des graphes. Ensuite, nous avons montré que le problème d'optimisation associé était un problème NP sous une certaine contrainte, ce qui a entraîné une preuve d'exclusion de certaines configurations dont les coûts ne peuvent être minimaux. Ceci a constitué la deuxième contribution de cette thèse. Enfin, nous avons proposé un nouvel algorithme permettant de résoudre le problème d'optimisation donné, et dont l'intérêt est de donner une solution optimale du problème au lieu d’une solution approchée fournie par les méthodes heuristiques classiques. Un programme associé à cet algorithme a été développé en langage C, puis appliqué à plusieurs exemples de cas génériques afin d’en étudier les performances. / The Software-Defined Radio (SDR) concept is emerging as a potential and efficient solution for designing flexible future-proof multi-standard systems. A way of realizing a multi-standard terminal is to identify the appropriate common functions and operators inside and between the standards. This is what's called the parametrization approach, which can be divided into two categories: the pragmatic approach which is a practical version to create and develop common operators, and the theoretical approach which represents a graphical exploration of the SDR multi-standard system at different levels of granularity accompanied with an optimization problem. It’s in this last approach where our thesis subject dwells. In this context, a suggested cost function (in previous work) has to be optimized in order to select the convenient common operators between the different standards, enabling to construct an optimal design. In our work, we theoretically model a previously proposed graph structure of an SDR multi-standard system as a directed hypergraph as well as provide an alternative mathematical formal expression of the suggested cost function, using various graph theoretical definitions and notations. Afterwards, we prove that the associated optimization problem is an NP-problem under a certain constraint, which entails a proof of exclusion of some particular design options when searching for a minimum cost design. This was the second contribution in this thesis before we finally present a new algorithm (which exploits various modelization aspects of directed hypergraphs) that can solve the optimization problem, whose interest is in it giving an exact-optimal solution to our problem instead of a near-optimal one provided by heuristics. A program code for this algorithm was developed in C-language, and then it was applied on several generic case examples in order to explore its performance skills.

Cette thèse considère principalement trois problèmes dans le domaine du contrôle distribué coopératif des systèmes multi-agents(SMA): le consensus, la navigation en formation et le maintien en formation d’un groupe d’agents lorsqu’un agent disparait. Nous proposons 3 algorithmes pour résoudre le problème du calcul distribué d’un consensus à partir de l’approche leadeur-suiveur dans le contexte SMA à dynamique non-linéaire. La référence est définie comme un leader virtuel dont on n’obtient, localement, que les données de position et de vitesse. Pour résoudre le problème du suivi par consensus pour les SMA à dynamique non-linéaire, nous considérons le suivi par consensus pour SMA de premier ordre. On propose des résultats permettant aux suiveurs de suivre le leadeur virtuel en temps fini en ne considérant que les positions des agents. Ensuite, nous considérons le suivi par consensus de SMA de second. Dans le cas de la planification de trajectoire et la commande du mouvement de la formation multi-agents. L’idée est d’amener la formation, dont la dynamique est supposée être en 3D, d’une configuration initiale vers une configuration finale (trouver un chemin faisable en position et orientation) en maintenant sa forme tout le long du chemin en évitant les obstacles. La stratégie proposée se décompose en 3 étapes. Le problème du Closing-Rank se traduit par la réparation d’une formation rigide multi-agents "endommagée" par la perte de l'un de ses agents. Nous proposons 2 algorithmes d’autoréparation systématique pour récupérer la rigidité en cas de perte d'un agent. Ces réparations s’effectuent de manière décentralisée et distribuée n’utilisant que des informations de voisinage / This dissertation focuses on distributed cooperative control of multi-agent systems. First, the leader-following consensus for multi-agent systems with nonlinear dynamics is investigated. Three consensus algorithms are proposed and some sufficient conditions are obtained for the states of followers converging to the state of virtual leader globally exponentially. Second, the consensus tracking for multi-agent systems with nonlinear dynamics is investigated. Some consensus tracking algorithms are developed, and some sufficient conditions are obtained. Based on these consensus tracking algorithms and sufficient conditions, it is shown that in first-order multi-agent systems all followers can track the virtual leader in finite time, and in second-order multi-agent systems the consensus tracking can be achieved at least globally exponentially. Third, the path planning and motion control of multi-agent formation is studied, where a practical framework is provided. In order to find a collision-free and deadlock-free feasible path for the whole formation, an optimizing algorithm is given to optimize the path generated by A* search algorithm. In order to realize the cohesive motion of a persistent formation in 3-dimensional space, a set of decentralized control laws is designed. Finally, the formation keeping problem is studied. We mainly focus on the closing ranks problem, which deals with the addition of links to a rigid multi-agent formation that is “damaged" by losing one of its agents, in order to recover rigidity. Some graph theoretical results are obtained, and some systematic ’self-repair’ operations are proposed to recover the rigidity in case of agent removals

De nos jours la protection des données numériques est un problème très important. Que ce soit pour des applications de confidentialité, de communication, de traçabilité ou d'identification par exemple, il est nécessaire de développer des techniques adaptées. Dans le cadre de cette thèse en collaboration avec la société STRATEGIES S.A., la méthode choisie pour la protection de maillages 3D est l'insertion de données cachées, également appelée tatouage numérique. Pour des données 3D, un des problèmes les plus importants est la phase de synchronisation qui intervient dans les algorithmes d'insertion et d'extraction des données. Cette phase permet de repérer, de sélectionner et d'ordonner les « zones » qui sont privilégiées pour la dissimulation d'information. Nous avons choisi d'orienter le manuscrit sur cette phase. Ainsi, nous proposons une classification des méthodes de tatouages en fonction de leur méthode de synchronisation. Puis en se basant sur des techniques de synchronisation par des structures de données, telle que les arbres couvrants de poids minimum, nous proposons une analyse théorique de cette structure. Dans un premier temps nous expliquons les raisons de la sensibilité des arbres à la mobilité des points. Puis connaissant ses faiblesses, nous proposons une autre technique de synchronisation toujours basée sur les arbres couvrants de poids minimum. / Data security is one of the main issue in computer science. We need to develop solutions for confidentiality, communication, fingerprinting or identification applications for exemple. In this thesis made with STRATEGIES S.A., the chosen method to protect 3D meshes is watermarking.Watermarking is divided in two steps, the embedding and the extraction. In both of them a synchronization phase is needed. It is one of the most important step for 3D mesh because it permits to look for areas available to embed information, and order them. All the thesis is devoted to the synchronization step. First of all, we propose a classification of watermarking techniques based on the type of synchronization method instead of evaluation criterions such as robustness or capacity.Then, from methods based on Euclidean minimum spanning tree, we propose a theoritical analysis of the mobility of the vertices in that kind of structure. First, we explain the reasons of the sensibility of the structure. Secondly, we propose another scheme based on the Euclidean minimum spanning tree knowing its fragility.

La raison initiale du sujet de cette thèse est l'introduction, pour la première fois en France, d'éléments de théorie des graphes dans un curriculum de l'enseignement secondaire, à savoir celui de la spécialité mathématiques de la Terminale économique et sociale (ES) en 2002.<br />Après une brève étude historique de la genèse – relativement récente – du graphe en tant que concept mathématique et de la signification épistémologique de cette genèse, nous analysons les choix faits pour la transposition de ce concept, en particulier les énoncés proposés aux élèves, qui montrent le décalage entre les intentions affichées et la réalité. Cette partie du programme de terminale ES se particularise par sa mise en œuvre « axée sur le seule résolution de problèmes ».<br />Or, nous montrons que les manuels scolaires sont dans ce chapitre composés d'exercices et non de problèmes. L'enseignement de théorie des graphes, s'il se limite à la résolution, locale, de ces exercices ou de « casse-tête » mathématiques, ne permet pas aux élèves de comprendre les concepts mathématiques sous-jacents ni surtout d'accéder au sens du raisonnement mathématique (en particulier autour de la modélisation et de la preuve) et à la richesse de la démarche scientifique, ce qu'aurait dû permettre ce domaine facilement abordable des mathématiques.<br />Une étude théorique et expérimentale du problème de « parcours eulériens dans les graphes » a ensuite été menée, du primaire au supérieur, sous des formes différentes (situations-recherche en classe avec ou sans support matériel, étude de documents). Des éléments didactiques ont aussi été tirés de deux stages de formation d'enseignants en théorie des graphes pour la Terminale ES.<br />Ces différentes études nous ont conduit à proposer un nouvel ensemble organisé de problèmes à destination des enseignants de Terminale ES, accompagnés de leur résolution et d'analyses didactiques qui attestent que des mathématiques plus consistantes peuvent être abordées et construites sur ce thème.

.

Notre travail s'intègre dans la conception et la réalisation d'un environnement informatique sur la manipulation directe d'objets mathématiques, en l'occurrence l'extension de Cabri-graphes dans le cadre du projet Cabri. Dans la première partie, nous exposons le concept d'interface de manipulation directe. Nous présentons une évolution des principes associés à la manipulation directe. Nous montrons l'importance accordée à ce mode d'interaction. Dans une deuxième partie, nous exposons des motivations associées à la mise en oeuvre d'environnements informatiques sur la théorie des graphes. Nous analysons plusieurs environnements en fonction de trois critères : la visualisation, les fonctionnalités, et le mode d'interaction. Dans une troisième partie, nous construisons un éditeur de graphes en fonction des principes de manipulation directe énoncés dans la première partie. Nous établissons les limites d'une telle interface en fonction des outils à notre disposition. Dans la quatrième partie, plus théorique, nous présentons une étude sur le produit fibré de graphes, et sur la contraction de graphes comme un outil de visualisation de graphes.

Le contexte général de mes travaux se situe dans les réseaux orientés connexions, que ce soit des réseaux optiques à multiplexage en longueur d'onde (WDM), des réseaux MPLS (multi-protocol label switching), ou encore des réseaux à faisceaux hertziens (wireless backhaul networks). Dans ces réseaux, je m'intéresse à router les flux d'information, à agréger des flux d'information bas débits dans des flux de plus hauts débits, à faire évoluer le routage en cas de variations dans la quantité de trafic à transporter ou dans la topologie du réseau, et à assurer la continuité du trafic en cas de panne simple ou multiple. Pour aborder ces questions, j'utilise des outils variés de l'algorithmique, de la théorie des graphes et de l'optimisation combinatoire.<br /> L'ensemble des résultats présentés dans ce document est le fruit de travaux collaboratifs avec les membres de l'équipe-projet MASCOTTE, des collègues d'autres universités, française ou étrangères, et des collègues de France Télécom, Alcatel-Lucent et 3Roam. L'introduction de ce manuscrit résume nos travaux sur le routage, le groupage de trafic, la tolérance aux pannes et la reconfiguration, ainsi que des travaux plus récents sur la minimisation du nombre d'étiquettes dans les réseaux MPLS, le dimensionnement de réseaux de collecte IP sans fil, et sur le routage disjoints d'ensembles particuliers de requêtes. Ensuite, je détaille nos travaux sur le groupage de trafic au travers d'un état de l'art dans le chapitre 3, nos contributions sur la notion de groupes de ressources partageant un risque dans le chapitre 4, et sur la reconfiguration de routages dans le chapitre 5. Le chapitre 6 conclut ce manuscrit en présentant avec quelques directions de recherches.

De l'analyse des méthodes existantes à la recherche d'une méthodologie, du raisonnement au développement, de la réalisation à l'application, nous pouvons conclure qu'une nouvelle méthode (REMODE) a été développée pour reconstituer une matrice origine-destination de trafic interurbain à partir des comptages. Cette méthode, inspirée de la programmation dynamique et des théories des graphes, modélise les comportements des voyageurs d'une part, et tire avantage du calcul mathématique d'autre part. Le but de la fonction objectif est de minimiser la différence entre le comptage et la valeur estimée sur les compteurs. A partir de cela, tous les processus, notamment ceux de génération, distribution et affectation, sont conçus d'une façon continue afin de garantir leur cohérence ainsi que le sens global de chaque élément concerné. Les principales nouveautés de cette méthode sont : (1) Le calibrage autonome du modèle est assuré par le programme lui-même. (2) La simulation de l'écoulement du trafic est fondée sur la désagrégation des voyageurs et l'offre du transport. (3) Les définitions des priorités au calcul ont été également entreprises dans le développement de la fonction objectif. Cette méthode a été calibrée et appliquée au réseau routier français et les données de comptages en 1990. Les principales matrices origine-destination reconstituées (matrices régionale, départementale et intermédiaire) sont interprétables du point de vue mathématique et socio-économique du transport.