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.

No description available.

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.

Les résultats obtenus dans cette thèse portent principalement sur l'étude des "communications dans les réseaux optiques par multiplexage en longueur d'onde". Ils s'inscrivent dans une thématique d'allocation des ressources en vue de réaliser des communications dans un réseau. La problématique générale que nous avons considérée peut se résumer de la manière suivante. Il s'agit de satisfaire dans un réseau optique une famille de requêtes de connexion, appelée instance de communication et formée de couples de noeuds (source, destination). La satisfaction d'une requête passe par l'attribution d'un chemin dans le réseau et d'une longueur d'onde sur les liens utilisés, avec la contrainte que deux requêtes ne peuvent pas utiliser le même lien avec la même longueur d'onde. L'objectif dans ce cadre est de minimiser l'utilisation des ressources optiques, c'est-à-dire le nombre total de longueurs d'onde permettant de satisfaire l'instance donnée. Dans le chapitre 1, nous présentons la technologie optique pour les télécommunications, afin de préciser le cadre technique de notre recherche et d'aider le lecteur informaticien à la compréhension des contraintes physiques sous-jacentes à la modélisation théorique. Dans le chapitre 2, nous posons la problématique étudiée au cours de la thèse et nous donnons la modélisation qui a servi de base à nos recherches. Le chapitre 3 est une synthèse des résultats obtenus dans la littérature concernant principalement le problème du routage optique. Le reste de la thèse est constituée des annexes qui rassemblent les articles publiés, dans le format des rapports de recherche.

Ce travail est axé autour de l'analyse assistée par ordinateur, dans un cadre musicologique ciblant la musique contemporaine. Une approche computationnelle de l'analyse musicale pose la question de sa modélisation et de sa formalisation, puisque touchant à une activité souvent empirique et dont la pratique n'est pas définie à l'aide de normes communes. Cette question implique la mesure de l'importance de la représentation graphique dans l'interprétation analytique. Face au rôle croissant de la représentation, nous nous intéressons d'une part à la manière dont elle relie l'analyse et la composition en proposant, à partir d'une analyse connue des Structures IA de Pierre Boulez réalisée par le compositeur György Ligeti, des modèles de machinerie informatique en vue de générer des pièces musicales sous deux interfaces, OpenMusic et Rubato. Parmi ces deux environnements de programmation visuelle, le second se base sur un puissant paradigme mathématique reposant sur la théorie des catégories. Ce paradigme constitue également une base pour modéliser les K-réseaux, outil d'analyse reposant sur des graphes décrivant les relations entre les notes. Ces relations sont formalisées dans la Set Theory d'Allen Forte qui propose une méthode de classification des structures musicales à partir des douze hauteurs de la gamme chromatique occidentale. Une application de ces réseaux et plus généralement l'apport des structures de graphe est abordée ensuite dans la modélisation de l'analyse d'une autre pièce, le Klavierstück III de Karlheinz Stockhausen : cette analyse a été faite par le théoricien David Lewin en deux étapes que nous étudierons dans leurs aspects à la fois computationnel et d'interface-homme machine. En premier lieu, la segmentation, non expliquée par l'analyste, fait l'objet d'une reconstitution dans laquelle nous tentons de la retrouver par le biais d'une exploration dans un ensemble de segmentations possibles. Il s'agit ainsi non seulement de reconstituer mais également de voir s'il est possible de la dépasser et l'améliorer selon des critères comme la couverture de la partition. Nous verrons dans ce cadre si les K-réseaux peuvent affiner cette analyse et en constituer un angle d'attaque pertinent. En second lieu, Lewin organise ses segments selon un réseau qui ne suit plus un quelconque agencement chronologique mais une disposition spatiale qui offre un nouveau parcours de la pièce. Cette difficulté s'inscrit dans le contexte plus général de la sélection et de la formation d'un graphe décrivant la structure d'une oeuvre musicale, que nous envisageons à l'intérieur du problème de l'utilisation d'un réseau en analyse computationnelle.

L'objet de cette thèse est d'obtenir une description des plongements élémentaires (au sens de la logique du premier ordre) dans un groupe hyperbolique sans torsion. Le résultat principal décrit ces plongements en terme d'une structure définie par Sela dans sa solution au problème de Tarski: la structure de tour hyperbolique. Ainsi, si H est plongé élementairement dans un groupe hyperbolique sans torsion G, on peut obtenir G en amalgamant successivement des groupes de surfaces à bord à un produit libre de H avec des groupes libres et des groupes de surfaces sans bord. Ceci permet en corollaire de montrer qu'un sous-groupe plongé élémentairement dans un groupe libre de type fini est un facteur libre. Les techniques utilisées pour obtenir cette description sont essentiellement géométriques: actions sur des arbres réels ou simpliciaux, existence de décompositions JSJ. On s'appuie également sur des résultats d'existence d'ensembles de factorisation qui affirment que pour certains groupes A de type fini, étant donné un groupe hyperbolique sans torsion G, il existe un ensemble fini de quotients de A tel que tout morphisme non injectif de A vers G se factorise par l'un de ces quotients après précomposition par un automorphisme de A. On expose une preuve de ces résultats, y compris une version complète et détaillée du shortening argument de Rips et Sela. Le shortening argument montre, grâce à l'analyse de Rips des actions sur des arbres réels, que si une suite d'action d'un groupe A sur des espaces hyperboliques converge vers un A-arbre réel d'un certain type, alors une infinité de ces actions peuvent être raccourcies.