Les techniques de segmentation de graphe sont souvent utilisées en traitement d'images puisque ces dernières peuvent être vues comme des graphes valués. Dans cette thèse, nous montrons des liens existant entre plusieurs paradigmes de segmentation de graphes valués. Nous présentons tout d'abord différentes définitions de ligne de partage des eaux et sélectionnons celle dont le cadre permet la comparaison avec des forêts couvrantes particulières. Nous montrons qu'une telle ligne de partage des eaux relative à des marqueurs arbitraires est équivalente à une coupe induite par une forêt couvrante de chemins de moindre altitude. Ensuite, les coupes induites par des forêts couvrantes de poids minimum sont démontrées comme étant des cas particuliers ayant l'avantage d'éviter certaines segmentations non souhaitées. Enfin, nous montrons qu'une coupe minimale coïncide avec une coupe induite par une forêt couvrante de poids maximum pour certaines fonctions de poids particulières. Dans une seconde partie, nous présentons deux applications utilisant la segmentation de graphe : la renaissance d'images et le mélange de textures pour la reconstruction 3D

Une carte est le plongement d'un graphe dans une surface, à un homéomorphisme près. Ainsi, une carte est un objet topologique énumérable, en fonction du nombre de ses sommets, de ses arêtes et de ses faces. Les cartes admettent des symétries internes qui rendent leur énumération difficile. On n'envisage dans ce travail que l'énumération des cartes pointées, le pointage supprimant toutes les symétries. Le nombre exact de cartes pointées sur une surface donnée n'est connu que pour les surfaces de petit genre, comme la sphère (genre 0), le tore ou le plan projectif (genre 1). En effet, la complexité des méthodes de calcul de ces nombres augmente rapidement avec le genre des surfaces. Un travail important de cette thèse a été de convertir l'une de ces méthodes de calcul en une preuve de l'existence d'une structure commune à toutes les séries génératrices de cartes pointées de genre non nul. Pour chaque surface orientable, on réduit le problème à la détermination d'un polynôme, dont le degré est majoré par une fonction simple du genre de la surface. Un résultat analogue est obtenu pour les cartes pointées sur les surfaces non orientables. Des conséquences pratiques et une implantation logicielle de tous ces résultats sont décrites. De nouvelles formules explicites d'énumération sont données. Indépendamment, une bijection géométrique nouvelle est exposée, entre certaines cartes 2-coloriables et les partitions de polygones, énumérées par les nombres de Schröder.

.

.

Dans cette thèse nous étudions le problème de détection et localisation de défauts (FDI) diagonal avec une banque d'observateurs. Nous étudions ce problème sur la classe des systèmes linéaires structurés avec leurs graphes associés. Les systèmes structurés sont une classe particulière des systèmes linéaires où les éléments des matrices sont soit fixés à zéro soit des paramètres libres. On présente une condition nécessaire et suffisante pour la solubilité générique du problème FDI. Cette condition est à vérifier sur le graphe orienté associé au système structuré. Dans le cas où cette condition n'est pas vérifiée, nous présentons une décomposition du système qui donne des informations structurelles sur le placement de capteurs additionnels qui sont nécessaires pour remplir la condition. Dans le cas où la condition de solubilité générique du problème FDI est vérifiée, nous présentons aussi une classification des capteurs selon leur importance pour la solubilité générique du problème FDI.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.

Les schémas de routage locaux basés sur des coordonnées prises dans le plan hyperbolique ont attiré un intérêt croissant depuis quelques années. Cependant, les solutions proposées sont toutes appliquées à des réseaux au topologie aléatoire et au nombre de nœuds limités. Dans le même temps, plusieurs travaux se sont concentrés sur la création de modèle topologique basé sur les lois de la géométrie hyperbolique. Dans ce cas, Il est montré que les graphes ont des topologies semblables à Internet et qu'un routage local hyperbolique atteint une efficacité proche de la perfection. Cependant, ces graphes ne garantissent pas le taux de réussite du routage même si aucune panne ne se produit. Dans cette thèse, l'objectif est de construire un système passant à l'échelle pour la création de réseau recouvrant capable de fournir à ses membres un service d'adressage et de routage résilient dans un environnement dynamique. Ensuite, nous étudions de quelle manière les réseaux P2PTV pourraient supporter un nombre d'utilisateur croissant. Dans cette thèse, nous essayons de répondre à cette question en étudiant les facteurs d'efficacité et de passage à l'échelle dans un système de diffusion vidéo P2P typique. Au travers des données fournies par Zattoo, producteur de réseau P2PTV, nous réalisons des simulations dont les résultats montrent qu'il y a encore des obstacles à surmonter avant que les réseaux P2P de diffusion vidéo puissent dépendre uniquement de leurs utilisateurs. / Local routing schemes based on virtual coordinates taken from the hyperbolic plane have attracted considerable interest in recent years.However, solutions have been applied to ad-hoc and sensor networks having a random topology and a limited number of nodes. In other hand, some research has focused on the creation of network topology models based on hyperbolic geometric laws. In this case, it has been shown that these graphs have an Internet-like topology and that local hyperbolic routing achieves a near perfect efficiency. However, with these graphs, routing success is not guaranteed even if no failures happen. In this thesis, we aim at building a scalable system for creating overlay networks on top of the Internet that would provide reliable addressing and routing service to its members in a dynamic environment.Next, we investigate how well P2PTV networks would support a growing number of users. In this thesis, we try to address this question by studying scalability and efficiency factors in a typical P2P based live streaming network. Through the use of the data provided by Zattoo a production P2PTV network, we carry out simulations whose results show that there are still hurdles to overcome before P2P based live streaming could depend uniquely of their users.

Les sciences qui traitent de la réalité, qu'elles soient naturelles, de la société ou de la vie, fonctionnent avec des modèles. Une partie de ces modèles décrivent les relations entre certaines grandeurs mesurables de la réalité, sans aller jusqu'au détail des interactions entre les éléments qui la composent. D'autres modèles décrivent ces interactions en prenant le point de vue des individus qui constituent le système, le comportement global n'est alors plus décrit à priori, mais observé à posteriori. Nous faisons le constat que dans les deux cas le scientifique a peu de liberté pour décrire les structures, en particulier spatiales, susceptibles de porter ces interactions. Nous proposons une approche de modélisation que l'on peut situer à mi-chemin entre les deux, et qui incite à étudier un système à travers la nature de ses interactions et des structures de graphes qui peuvent les porter. En plaçant au même niveau les relations spatiales, fonctionnelles, sociales ou hiérarchiques, nous tentons aussi de nous affranchir des contraintes induites par le choix effectué souvent à priori d'une forme de représentation de l'espace. Nous avons formalisé les concepts de base de cette approche, et ceux-ci ont constitué les éléments d'un langage métier, nommé Ocelet, que nous avons défini. Les outils permettant la mise en œuvre de ce langage ont été développés et intégrés sous la forme d'un environnement de modélisation et de simulation. Enfin nous avons pu expérimenter notre nouvelle approche de modélisation et le langage Ocelet à travers la réalisation de plusieurs modèles présentant des situations variées de dynamiques paysagères / Sciences dealing with reality be it related to nature, society or life, use models. Some of these models describe the relations that exist between measurable properties of that reality, without detailing the interactions between its components. Other models describe those interactions from the point of view of the individuals that form the system, in which case the overall behaviour is not defined a priori but observed a posteriori. In both cases, it can be noted that the scientist is often limited in its capacity to describe the structures, especially those spatial, which support the interactions. We propose a modelling approach that can be considered intermediate, where the system is studied by examining the nature of the interactions involved and the graph structures needed to support them. By unifying the description of spatial, functional, social or hierarchical relationships, we attempt to lift constraints induced by the form of spatial representation that are often chosen a priori. The basic concepts of this approach have been formalized, and were used to define and build a domain specific language, called Ocelet. The tools related to the implementation of the language have also been developed and assembled into an integrated modelling and simulation environment. It was then possible to experiment our new modelling approach and the Ocelet language by developing models for a variety of dynamic landscapes situations

Cette thèse théorique s'inscrit dans l'univers de l'Informatique quantique et celui du transfert d'énergie. Nous étudions le transport quantique d'un exciton utilisé dans le but de véhiculer une information quantique, ou de l'énergie, sur des graphes moléculaires complexes. Dans ce contexte, nous nous intéressons aux effets de différents environnements quantiques pouvant moduler le transport excitonique. Une première partie du manuscrit porte sur le transport d'information quantique en pré­sence d'un environnement de phonons locaux. Dans ce contexte, nous introduisons une ap­proche théorique appelée PT* permettant de traiter sur un pied d'égalité exciton et pho­nons. Cette théorie est tout d'abord appliquée au cas particulier du graphe en étoile. Par la suite, PT* est comparée à des calculs exacts menés sur une collection de graphes variés. Nous montrons ainsi que la théorie PT* possède une très grande force de prédictibilité et de multiples avantages théoriques et numériques ( durée de simulation, interprétations liées à l'intrication ... ) . Dans une deuxième partie du manuscrit, nous étudions le transport quantique d'énergie sur un graphe complexe en contact avec un système externe absorbant. Nous nous intéressons tout particulièrement à la caractérisation du phénomène d'absorption énergétique et son opti­misation (transition de superradiance). Nous mettons en évidence l'impact de la topologie du réseau sur l'évolution du processus d'absorption. Pour étendre cette étude, nous considérons ensuite la présence d'un désordre local brisant la symétrie du réseau de base. Nous montrons alors que le désordre peut influencer positivement l'évolution du processus d'absorption. / The scope of this PhD is twofold and can be integrated simultaneously in quantum infor­mation theory and energy transport. We theoretically study the excitonic quantum transport in order to transmit either quantum information or energy on complex molecular networks. In this context, we pay a special attention to the modulations that different quantum envi­ronments can generate on the excitonic transport. In a first part of the manuscript, we focus on the quantum transport of information in the presence of a local phononic environment. In this context, we introduce a theoretical approach, named PT*, treating on an equal footing exciton and phonons. Firstly, this theory is applied to a particular case : the star graph. Then, PT* is compared to exact numerical calculations realized on a collection of different graphs. In this context, we demonstrate that the PT* approach shows a very strong predictability but also several theoretical and numerical advantages (simulation duration, entanglement interpretations ... ). In a second part of the manuscript, we study the quantum transport of energy on a complex graph in contact with an external absorbing system. We focus on the optimisation of the absorption process ("superradiance transition"). We demonstrate that the topology of the considered network influences the absorption evolution. In order to extend this study, we then consider the presence of a local disorder breaking the inner symetry of the graph. In this context, we show that the disorder can benefically influence the absorption process.

La quantité incroyable de contenu disponible dans les services en ligne rend le contenu intéressant incroyablement difficile à trouver. La manière la plus emblématique d’aider les utilisateurs consiste à faire des recommandations. Le graphe des K-plus-proches-voisins (K-Nearest-Neighbours (KNN)) connecte chaque utilisateur aux k autres utilisateurs qui lui sont les plus similaires, étant donnée une fonction de similarité. Le temps de calcul d’un graphe KNN exact est prohibitif dans les services en ligne. Les approches existantes approximent l’ensemble de candidats pour chaque voisinage pour diminuer le temps de calcul. Dans cette thèse, nous poussons plus loin la notion d’approximation : nous approximons les données de chaque utilisateur, la similarité et la localité de données. L’approche obtenue est nettement plus rapide que toutes les autres. / The incredible quantity of available content in online services makes content of interest incredibly difficult to find. The most emblematic way to help the users is to do item recommendation. The K-Nearest-Neighbors (KNN) graph connects each user to its k most similar other users, according to a given similarity metric. The computation time of an exact KNN graph is prohibitive in online services. Existing approaches approximate the set of candidates for each user’s neighborhood to decrease the computation time. In this thesis we push farther the notion of approximation : we approximate the data of each user, the similarity and the data locality. The resulting approach clearly outperforms all the other ones.