Cette thèse propose une nouvelle approche pour estimer des propriétés de la topologie d’Internet. Contrairement aux approches historiques, qui se bases sur des données déclaratives très peu fiables, ou sur la lecture de cartes mesurées avec des outils de diagnostic, notre approche consiste à mettre au point des primitives de mesures très fiables, dont le fonctionnement, les hypothèses et les résultats sont bien définis formellement. Notre premier cas d’étude est celui de la distribution de degré de la topologie logique, ou L3. Nous utilisons l’outil traceroute dont nous étudions le fonctionnement, pour en déduire une primitive de mesure. Cette primitive de mesure, qui repose sur l’utilisation d’un ensemble de moniteurs distribué dans le réseau, permet d’obtenir une estimation du nombre de voisins dans la topologie logique, d’un routeur du cœur. Nous utilisons cette primitive vers un échantillon aléatoire de cibles, pour obtenir une estimation de la distribution de degré recherchée et établir les limites de cette approche. Notre deuxième cas d’étude est celui de la distribution de degré de la topologie physique, ou L2-L3. Nous utilisons l’outil UDP Ping, dont nous étudions le fonctionnement, pour en déduire une primitive de mesure. Elle est semblable à l’outil utilisé pour la topologie logique, mais repose sur des hypothèses bien plus clairement établies et vérifiées, et validée par des simulations très détaillées. Nous intégrons également au protocole de mesure, des garanties statistiques sur l’uniformité de l’échantillon de cibles, des routeurs du cœur, que nous mesurons. Nous obtenons une évaluation de la distribution de degré recherchée, d’une très grande fiabilité. Nous complétons ce cas d’étude par un travail complémentaire sur les tables de transmission des routeurs du cœur. Enfin, nous dressons un tableau assez large des perspectives qui s’ouvrent en se basant sur cette approche, par exemple en l’appliquant à d’autres types de réseaux (réseaux sociaux, etc.). / This thesis proposes a novel approach to reliably estimate properties of the Internet topology. Unlike historical approaches, based on declarative, hardly reliable data, or on readings from maps measured with diagnostic tools, our approach is to develop very reliable measure primitives, of which the operation, the hypotheses, and the results are well defined. Our first case study is the degree distribution of the logical topology, or L3. We use the traceroute tool, of which we study the operation, to derive a measurement primitive. This measurement primitive, which relies on using a distribution set of monitors over the network, allows us to get an estimation of the number of neighbors in L3 of a target core router. We use this primitive against a random sample of targets and obtain the sought distribution, and establish limits to this method. Our second case study is the degree distribution of the physical topology, or L2-L3. We use the UDP Ping tool, of which we study the operation, to derive a measurement primitive. It is alike the tool we used for the logical topology, but relies on much more clearly established and verified hypotheses, and is validated by very detailed simulations. We also include statistical guarantees of the sampling uniformity of the target core routers to the measurement protocol. We obtain an evaluation of the sought degree distribution, of an unprecedented reliability. We complete this case study by a complimentary study over the forwarding tables of the core routers. Finally, we picture the many perspectives opened by this approach, eg. By applying it to other types of networks (social networks, etc.).

Le classement des objets est une des questions importantes et typiques dans notre vie quotidienne. De nombreuses applications ont besoin de classifier des objets en fonction de certains critères, parfois simple comme de classifier les étudiants dans une classe en fonction de relevé de notes ou plus compliqué comme le classement des universités. Classifier des objets consiste à les ordonner selon certains critères exigés par une application spécifique.Avec la popularisation de l’Internet, un problème typique qui a émergé des deux dernières décennies est le classement des résultats renvoyés par les moteurs de recherche. Dans les moteurs de recherche classiques (comme Google, Yahoo ou Bing ),l’importance d’une page web est la base pour le classement. Cette valeur est calculée sur la base de l’analyse des hyper-liens entre les pages Web. Avec un ensemble de documents V={v1, ..., vn}, quand il y a une requête q d’un utilisateur arrivant, le moteur de recherche cherche des documents dans V correspondant à la requête q, puis trie les documents dans l’ordre décroissant de leur pertinence pour la requête. Ce processus peut être réalisé grâce à une fonction de classement qui permet de cal culer la similarité sim(q, vi) entre la requête q et un document vi ∈ V. La fonction de classement peut être considérée comme le noyau qui détermine essentiellement la qualité du moteur de recherche. / Ranking objects is one of the important and typical issues in our daily life. Many applications need to rank objects according to certain criteria, as simple as ranking students in a class according to average grades, or more complicated as ranking universities. Ranking objects means to arrange them in accordance with some criteria depending on the specific application.In the era of the Internet, a typical problem emerging in the last decades is the ranking of results returned by search engines. In conventional search engines (like Google, Yahoo or Bing ), the importance of a web page is the basis for ranking. This value is determined based on the analysis of graph links between web pages. With a set of documents V={v1, ..., vn}, when there is a user’s query q arriving, the search engine looks for documents in V matching the query q, then sorts the documents according to their relevance to the query in descending order. This process can be done thanks to a ranking function which allows us to compute the similarity s(q,vi) between the query q and a document vi ∈ V . Obviously, the ranking function can be seen as the core and significantly determines the quality of the search engine.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Cette thèse présente des résultats obtenus dans deux domaines : la théorie des langages, et la théorie des graphes. En théorie des langages, on s’intéresse à des problèmes de caractérisation de classes de langages réguliers. Le problème générique consiste à déterminer si un langage régulier donné peut être défini dans un certain formalisme. Les méthodes actuelles font intervenir un problème plus général appelé séparation. On présente ici deux types de contributions : une généralisation d’un résultat de décidabilité au cadre des langages de mots infinis, ainsi que des bornes inférieures pour la complexité du problème de séparation. En théorie des graphes, on considère le problème classique de coloration de graphes, où on cherche à attribuer des couleurs aux sommets d’un graphe de sorte que les sommets adjacents reçoivent des couleurs différentes, le but étant d’utiliser le moins de couleurs possible. Dans le cas des graphes peu denses, la méthode de déchargement est un atout majeur. Elle a notamment joué un rôle décisif dans la preuve du théorème des quatre couleurs. Cette méthode peut être vue comme une construction non conventionnelle d’un schéma de preuve par induction, spécifique à la classe de graphes et à la propriété considérées, et où la validité du schéma est rarement immédiate. On utilise des variantes de la méthode de déchargement pour étudier deux types de problèmes de coloration. / In this thesis, we present results obtained in two fields: formal language theory and graph theory. In formal language theory, we consider some problems of characterization of classes of regular languages. The generic problem consists in determining whether a given regular language can be defined in a fixed formalism. The current approaches use a more general problem called separation. We present here two types of contributions: a generalization of a decidability result to the setting of infinite words, together with lower bounds for the complexity of the separation problem. In graph theory, we consider the classical problem of graph coloring, where we assign colors to vertices of a graph in such a way that two adjacent vertices receive different colors. The goal is to use the fewest colors. When the graphs are sparse, a crucial tool for this is the discharging method. It is most notably decisive in the proof of the Four-Color Theorem. This method can be seen as an unconventional construction of an inductive proof scheme, specific to the considered problem and graph class, where arguing the validity of the scheme is rarely immediate. We use variants of the discharging method to study two types of coloring problems.

Étude de certains problèmes d'optimisation combinatoire. Le premier concerne un problème de régulation de trafic pour lequel on donne une formulation mathématique et on propose une méthode permettant de le résoudre. Le deuxième problème traité est un des problèmes de la physique statistique qui relève de la combinatoire et de l'optimisation, celui du fondamental d'un verre de spins (modèle d'Ising). Enfin on étudie, deux autres problèmes d'optimisation combinatoire: l'absorbant et le Ki-recouvrement de poids minimum

Le problème d'alignement de graphes, qui joue un rôle central dans différents domaines de la reconnaissance de formes, est l'un des plus grands défis dans le traitement de graphes. Nous proposons une méthode approximative pour l'alignement de graphes étiquetés et pondérés, basée sur la programmation convexe concave. Une application importante du problème d'alignement de graphes est l'alignement de réseaux d'interactions de protéines, qui joue un rôle central pour la recherche de voies de signalisation conservées dans l'évolution, de complexes protéiques conservés entre les espèces, et pour l'identification d'orthologues fonctionnels. Nous reformulons le problème d'alignement de réseaux d'interactions comme un problème d'alignement de graphes, et étudions comment les algorithmes existants d'alignement de graphes peuvent être utilisés pour le résoudre. Dans la formulation classique de problème d'alignement de graphes, seules les correspondances bijectives entre les noeuds de deux graphes sont considérées. Dans beaucoup d'applications, cependant, il est plus intéressant de considérer les correspondances entre des ensembles de nœuds. Nous proposons une nouvelle formulation de ce problème comme un problème d'optimisation discret, ainsi qu'un algorithme approximatif basé sur une relaxation continue. Nous présentons également deux résultats indépendants dans les domaines de la traduction automatique statistique et de la bio-informatique. Nous montrons d'une part comment le problème de la traduction statistique basé sur les phrases peut être reformulé comme un problème du voyageur de commerce. Nous proposons d'autre part une nouvelle mesure de similarité entre les sites de fixation de protéines, basée sur la comparaison 3D de nuages atomiques.

Diverses techniques de modélisation sont utilisées en synthèse d'images et en CAO (conception assistée par ordinateur) pour produire des images réalistes et analyser les propriétés géométriques des objets solides modélisés. Cependant, malgré les progrès récents, la conception de formes géométriques reste une tâche complexe. Les objets géométriques que veut modéliser l'utilisateur doivent vérifier certaines propriétés, traditionnellement appelées contraintes. Pour pallier ces inconvénients certains systèmes de modélisation fournissent des outils de spécification des formes par des contraintes géométriques. Nous proposons dans cette thèse deux méthodes de résolution du système de contraintes. La première méthode étudie les graphes bipartis sous-jacents aux systèmes d'équations. Nous montrons qu'il est possible de décomposer polynomialement ces systèmes en sous-systèmes sur-contraints (plus d'équations que d'inconnues), sous-contraints (plus d'inconnues que d'équations) et bien-contraints (autant d'équations que d'inconnues) a partir du graphe biparti. La deuxième méthode proposée étudie les différentes configurations induites par des contraintes de distances, d'angles et de tangences entre points, droites et cercles. Les entités géométriques sont déterminées par un algorithme de réduction de graphes et un système à base de règles.

On considère R une relation d'équivalence borélienne standard de type I I1 sur un espace de probabilités (X, µ). On étudie une certaine propriété d'homogénéité pour un graphage fixé de la relation R : on suppose que les feuilles du graphage sont toutes isomorphes à un certain graphe transitif (connexe, infini, localement fini) Γ. Que peut-on dire sur la relation ? Dans ce cas, en considérant une action "à la Mackey", on montre qu'il existe (Z ,η) un revêtement standard probabilisé de (X, µ), une action libre (qui préserve η) sur Z du groupe G (localement compact, à base dénombrable d'ouverts) des automorphismes du graphe et un isomorphisme stable des groupoïdes mesurés associés. On fait le lien entre les propriétés du groupe G et celles de la relation de départ ; en particulier la propriété (T), (H) et la moyennabilité "passent" du graphe à la relation et réciproquement. On déduit aussi de la construction quelques couplages d'équivalence mesurée (ou plus généralement des "randembeddings") entre certains sous-groupes des automorphismes de Γ et tout groupe qui contient orbitalement la relation R. Dans un deuxième chapitre, on aborde le cas particulier de la propriété (T) relative pour les paires de groupes (ΓxZ^2, Z^2), où Γ est un sous-groupe non moyennable de SL(2,Z). Cette propriété a d'abord été prouvée par Marc Burger, puis "re-démontrée" plus "visuellement" quelques années plus tard dans le cas de SL(2,Z)xZ^2 par Y. Shalom, en utilisant des découpages du plan. On reprend cette technique dans le cas général du théorème de Burger afin d'obtenir par un algorithme des constantes de Kazhdan explicites pour toute paire (ΓxZ^2, Z^2).

On considère R une relation d’équivalence borélienne standard de type I I1 sur un espace de probabilités (X, µ). On étudie une certaine propriété d’homogénéité pour un graphage fixé de la relation R : on suppose que les feuilles du graphage sont toutes isomorphes à un certain graphe transitif (connexe, infini, localement fini) Γ. Que peut-on dire sur la relation ? Dans ce cas, en considérant une action "à la Mackey", on montre qu’il existe (Z ,η) un revêtement standard probabilisé de (X, µ), une action libre (qui préserve η) sur Z du groupe G (localement compact, à base dénombrable d’ouverts) des automorphismes du graphe et un isomorphisme stable des groupoïdes mesurés associés. On fait le lien entre les propriétés du groupe G et celles de la relation de départ ; en particulier la propriété (T), (H) et la moyennabilité "passent" du graphe à la relation et réciproquement. On déduit aussi de la construction quelques couplages d’équivalence mesurée (ou plus généralement des "randembeddings") entre certains sous-groupes des automorphismes de Γ et tout groupe qui contient orbitalement la relation R. Dans un deuxième chapitre, on aborde le cas particulier de la propriété (T) relative pour les paires de groupes (ΓxZ^2, Z^2), où Γ est un sous-groupe non moyennable de SL(2,Z). Cette propriété a d’abord été prouvée par Marc Burger, puis "re-démontrée" plus "visuellement" quelques années plus tard dans le cas de SL(2,Z)xZ^2 par Y. Shalom, en utilisant des découpages du plan. On reprend cette technique dans le cas général du théorème de Burger afin d’obtenir par un algorithme des constantes de Kazhdan explicites pour toute paire (ΓxZ^2, Z^2). / We consider a measure preserving standard borel equivalence relation R on a standard probability space (X,µ). We study a particular property of homogeneity for a fixed graphing of the relation R : We assume that the leaves of the graphing are all isomorphic to a given transitive graph Γ (connected, infinite, locally finite). What can be known about the relation ?In this case, considering a « Mackey action », we show that there exists a standard covering of (X,µ) i.e. a standard space Z; a probability measure η; a free, measure-preserving action on Z of G the (locally compact, second countable) group of all graph automorphisms of Γ and a stable isomorphism of the associated measured groupoid with R. We investigate some links between properties of G (resp. of the graph Γ) and those of R. In particular, Kazhdan property (T), Haagerup property (H) and amenability are preserved from the graph to the relation and conversely. We also deduce from the construction some couplings of measured equivalence (more generally some randembeddings) between subgroups of G and any group orbitally containing R. In a second chapter, we deal with the relative property (T) for the pairs (ΓxZ^2,Z^2), where Γ is a non-amenable subgroup of SL(2,Z). This property was first proved by M. Burger. Later on, Y. Shalom gave a more geometrical proof in the case of SL(2,Z)xZ^2, by using partitions of the plane. Following the same techniques in the general case of Burger's theorem, we develop an algorithm producing explicit constants for all pairs (ΓxZ^2,Z^2).