Cette thèse porte essentiellement sur les problématiques fondamentales d'optimisation combinatoire qui se dégagent de la modélisation structurelle et algorithmique du dimensionnement des réseaux de transport WDM tout-optiques. L'optimisation de ces réseaux est nécessaire aux opérateurs de télécommunication, qui demandent la garantie d'une exploitation efficace des ressources déployées. La thèse est organisée en trois parties. La première partie traite du problème de routage et affectation de longueur d'onde. Nous proposons de résoudre le problème considérant des demandes de trafic permanentes. Des méthodes à la fois exactes basées sur la programmation linéaire et approchées ont été développées. Nous étendons ensuite le modèle de trafic pour considérer simultanément des demandes de trafic pré-planifiées et des demandes de trafic aléatoires. Différent algorithmes de routage ont été développés. Les différents algorithmes ont été comparés en terme de taux de rejet global. La deuxième partie concerne le problème de routage et affectation de longueurs d'onde avec protection. Les ressources dédiées à la protection sont rarement sollicitées, nous cherchons à en minimiser le nombre grâce au multiplexage des circuits optiques de protection. Des méthodes exactes et approchées sont encore une fois proposées considérant les demandes de trafic citées ci-dessus. La dernière partie présente un algorithme de reroutage de canaux optiques afin d'améliorer le taux de rejet dans les réseaux tout-optiques sans convertisseurs en longueurs d'onde. Plusieurs variantes de l'algorithme ont été proposées. Les résultats obtenus montrent un gain intéressant en terme de taux de rejet.

Les travaux présentés dans ce mémoire de thèse abordent sous différents angles très intéressants, un sujet vaste et ambitieux : l'interprétation de plans cadastraux couleurs.Dans ce contexte, notre approche se trouve à la confluence de différentes thématiques de recherche telles que le traitement du signal et des images, la reconnaissance de formes, l'intelligence artificielle et l'ingénierie des connaissances. En effet, si ces domaines scientifiques diffèrent dans leurs fondements, ils sont complémentaires et leurs apports respectifs sont indispensables pour la conception d'un système d'interprétation. Le centre du travail est le traitement automatique de documents cadastraux du 19e siècle. La problématique est traitée dans le cadre d'un projet réunissant des historiens, des géomaticiens et des informaticiens. D'une part nous avons considéré le problème sous un angle systémique, s'intéressant à toutes les étapes de la chaîne de traitements mais aussi avec un souci évident de développer des méthodologies applicables dans d'autres contextes. Les documents cadastraux ont été l'objet de nombreuses études mais nous avons su faire preuve d'une originalité certaine, mettant l'accent sur l'interprétation des documents et basant notre étude sur des modèles à base de graphes. Des propositions de traitements appropriés et de méthodologies ont été formulées. Le souci de comblé le gap sémantique entre l'image et l'interprétation a reçu dans le cas des plans cadastraux étudiés une réponse.

La Science des Réseaux est apparue comme un domaine d'étude fondamental pour modéliser un grand nombre de systèmes synthetiques ou du monde réel. La découverte du graphe petit monde et du graphe sans échelle dans ces réseaux a révolutionné la façon d'étudier, d'analyser, de modéliser et de traiter ces réseaux. Dans cette thèse, nous nous intéressons à l'étude des réseaux ayant ces propriétés et souvent qualifiés de réseaux complexes. À notre avis, les recherches menées dans ce domaine peuvent être regroupées en quatre catégories: l'analyse, la structure, le processus/organisation et la visualisation. Nous abordons des problèmes relatifs à chacune de ces catégories tout au long de cette thèse. Les premiers chapitres introduisent l'état de l'art nécessaire aux lecteurs. Les chapitres 3,4,5,6 et 7 abordent chacun un problème spécifique auquel nous proposons une solution. Dans le chapitre 3, nous présentons une méthode de visualisation analytique pour analyser les réseaux complexes. En s'appuyant sur cette méthode, nous introduisons une nouvelle métrique pour déterminer la présence de sommets largement connectés. Nous détaillons dans le chapitre 4 un ensemble de modèles pour générer des réseaux artificiels ayant les propriétés petit monde et sans échelle. Nous proposons un nouveau modèle générant des réseaux de ce type et qui contiennent, de plus, des structures communautaires. En extension des résultats d'analyse obtenus au chapitre 3, nous introduisons un algorithme de clustering agglomératif dans le chapitre 5. Dans le chapitre 6, nous abordons la question de la visualisation de ces réseaux complexes grâce à un système qui combine simplification et clustering avec des algorithmes de mise en page dédiée. Nous abordons enfin dans le chapitre 7 la question de l'évaluation de la qualité des clusters pour les réseaux complexes qui n'ont pas de sommets largement connectés. Nous concluons chaque chapitre par des perspectives de recherches dédiées. Enfin, nous résumons nos résultats et concluons cette thèse en proposant quelques futurs axes de recherches basés sur nos découvertes.

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.

Cette thèse est divisée en deux parties. La première partie concerne la commutation rapide des informations dans les réseaux ATM. Dans le chapitre 2, nous décrivons la technologie ATM. Dans le chapitre 3, nous modélisons le problème du positionnement des chemins virtuels et définissons les deux paramètres étudiés, charge et nombre de sauts d'un VPL. Nous discutons l'orientation du modèle, la complexité du problème, puis proposons une synthèse des résultats de la littérature. Les démonstrations des résultats originaux se trouvent dans les chapitres 4 et 5. La seconde partie concerne l'échange total dans les réseaux d'interconnexion entre processeurs. Dans le chapitre 6, nous introduisons les notions de théorie des groupes nécessaires ainsi que la motivation du problème. L'objet du chapitre 7 est de caractériser les graphes de Cayley admettant un certain automorphisme de graphe (appelé rotation complète) permettant de construire d'une manière simple un protocole d'échange total optimal. Nous mettons en évidence des conditions nécessaires sur le groupe pour que le graphe admette une rotation complète. Nous donnons la liste exhaustive des graphes de Cayley admettant une rotation complète parmi les graphes de Cayley engendrés par des transpositions.

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.

Les personnes dirigent souvent leur attention vers les objets avec lesquels ils interagissent. Une premiere etape que doivent franchir les systemes informatiques pour s'adapter aux utilisateurs et ameliorer leurs interactions avec eux est de localiser leur emplacement, et en particulier la position de leur tete dans l'image. L'etape suivante est de suivre leur foyer d'attention. C'est pourquoi nous nous interessons aux techniques permettant d'estimer et de suivre le regard des utilisateurs, et en particulier l'orientation de leur tete.<br /><br />Cette these presente une approche completement automatique et independante de l'identite de la personne pour estimer la pose d'un visage a partir d'images basse resolution sous conditions non contraintes. La methode developpee ici est evaluee et validee avec une base de donnees d'images echantillonnee. Nous<br />proposons une nouvelle approche a 2 niveaux qui utilise les apparences globales et locales pour estimer l'orientation de la tete. Cette methode est simple, facile a implementer et robuste a l'occlusion partielle. Les images de visage sont normalisees en<br />taille dans des images de faible resolution a l'aide d'un<br />algorithme de suivi de visage. Ces imagettes sont ensuite projetees dans des memoires autoassociatives et entraineespar la regle d'apprentissage de Widrow-Hoff. Les memoires autoassociatives ne necessitent que peu de parametres et evitent l'usage de couches cachees, ce qui permet la sauvegarde et le chargement de prototypes de poses du visage humain. Nous obtenons une premiere estimation de l'orientation de la tete sur des sujets connus et inconnus.<br /><br />Nous cherchons ensuite dans l'image les traits faciaux saillants du visage pertinents pour chaque pose. Ces traits sont decrits par des champs receptifs gaussiens normalises a l'echelle intrinseque. Ces descripteurs ont des proprietes interessantes et sont moins couteux que les ondelettes de Gabor. Les traits saillants du visage detectes par les champs receptifs gaussiens motivent la construction d'un modele de graphe pour chaque pose. Chaque noeud du graphe peut etre deplace localement en fonction de la saillance du point facial qu'il represente. Nous recherchons parmi les poses voisines de celle trouvee par les memoires autoassociatives le graphe qui correspond le mieux a l'image de test. La pose correspondante est selectionnee comme la pose du visage de la personne sur l'image. Cette methode n'utilise pas d'heuristique, d'annotation manuelle ou de connaissances prealables sur le visage et peut etre adaptee pour estimer la pose d'autres objets deformables.

Le chapitre~2 retrace rapidement la problématique du routage, notamment dans l'Internet (qui servira d'exemple introductif dans la plupart des chapitres), les réseaux ad hoc, le graphe du web et les réseaux de pair à pair. Le chapitre~3 est consacré au routage «~de l'un vers tous~», c'est à dire au problème de diffusion d'un message à tous les membres d'un réseau. Le chapitre~4 traite du routage dans son sens le plus classique, c'est-à-dire quand il s'agit d'envoyer un message «~d'un n{\oe}ud vers tel autre~». Nous considérerons ensuite le problème plus pratique qui consiste à envoyer un message vers un n{\oe}ud défini de manière indirecte, ce que j'ai appelé «~de l'un vers celui qui~». Les deux derniers chapitres s'intéressent enfin à la dynamique des réseaux concernant l'algorithmique distribuée entre les n{\oe}uds ou le réseau lui-même. Le chapitre~6 décrit ainsi une classe très générale d'algorithmes de réseau à base d'itérations asynchrones qui fonctionne dès que des messages envoyés régulièrement sont reçus «~de temps à autre~». Le chapitre~7 développe ensuite quelques points liés à l'aspect dynamique de certains réseaux~: «~quand ça bouge~» tant du point de vue des connexions entre n{\oe}uds que de la présence des n{\oe}uds.

Les travaux présentés dans cette thèse constituent une contribution à la modélisation, à l'analyse et à la commande des systèmes de transport public par l'adaptation des réseaux de Petri (RdP) et algèbre des dioïdes. Nous étudions en particulier la gestion optimisée des correspondances par une planification des horaires d'un réseau de transport en commun. Nous développons dans ce sens des modèles capables d'apporter des solutions aux problèmes d'amélioration de la qualité de service de transport en commun, par les minimisations des temps de correspondance et des ressources matérielles utilisées. Notre travail est effectué en considérant deux études de cas de fonctionnement des bus au niveau des arrêts de correspondance où des échanges de passagers sont susceptibles de se produire. Un fonctionnement synchronisé pour lequel nous utilisons un modèle graphe d'événements temporisés (GET) et un modèle (max, +) linéaire stationnaire qui lui est associé. Un fonctionnement non-synchronisé modélisé par un graphe d'événements temporisés avec retrait dynamique de jetons (GETRDJ). Ce dernier modèle graphique, possédant des conflits structurels, a une description analytique dans l'algèbre (max, +) de forme linéaire non-stationnaire. La résolution mathématique du modèle obtenu passe par une politique de résolution des conflits associés au modèle graphique. Nous proposons dans ce sens une politique de routage déterminée a priori prenant en compte les caractéristiques du système. Cette politique permet d'une part, d'arbitrer les conflits sur le modèle graphique, et d'autre part, de résoudre le modèle mathématique. L'analyse des solutions obtenues ainsi que les éléments propres de la matrice caractéristique du modèle (max, +) permet de déterminer les différents temps de correspondance des voyageurs et d'estimer ainsi les performances du système étudié. Dans le souci de minimiser les temps de correspondance des voyageurs et améliorer la qualité de service, nous proposons une politique de commande de ces réseaux de bus. Deux approches sont alors proposées. La première permet de synthétiser une commande basée sur les techniques développées dans le cadre de la théorie de la résiduation dans les dioïdes. La seconde est fondée sur des résultats de simulation qui permettent d'obtenir une commande à partir des optima globaux des fonctions objectifs. Les résultats obtenus sont validés sur une partie du réseau de transport en commun de la ville de Montbéliard.