Ce mémoire de création littéraire se divise en deux parties. La première propose une série de chansons intitulée Chansons Fleuve. Ce sont huit pièces créées autour de l'idée de l'intime, dont j'ai composé les paroles et la musique1. Elles ont été enregistrées sur un support audio qui accompagne la copie papier de ce mémoire. La seconde partie consiste en une analyse des rapports qu'entretiennent le texte et la musique d'"Arbre à fruits, arbre à fruits" de Marie-Jo Thério, avec l'intime. À travers les paroles de la pièce, les marques de l'intime sont présentes comme contenu (l'essence de l'intime, les thématiques) et comme forme (les relations, les situations, le temps, l'espace). Dans l'enregistrement de la voix et l'interprétation, sont véhiculées plusieurs émotions qui installent un climat d'intimité, appuient le texte et contribuent à rapprocher le public de l'artiste.

L'objectif de cette thèse est l'étude des approximations et des vitesses de convergence pour des fonctionnelles de grands graphes discrets vers leurs limites continues. Nous envisageons deux cas de graphes discrets: des arbres (i.e. des graphes connexes et sans cycles) et des graphes finis, simples et denses. Dans le premier cas, on considère des fonctionnelles additives sur deux modèles d'arbres aléatoires: le modèle de Catalan sur les arbres binaires (où un arbre est choisi avec probabilité uniforme sur l'ensemble des arbres binaires complets ayant un nombre de nœuds donné) et les arbres simplement générés (et plus particulièrement les arbres de Galton-Watson conditionnés par leur nombre de nœuds).Les résultats asymptotiques reposent sur les limites d'échelle d'arbres de Galton-Watson conditionnés. En effet, lorsque la loi de reproduction est critique et de variance finie (ce qui est le cas des arbres binaires de Catalan), les arbres de Galton-Watson conditionnés à avoir un grand nombre de nœuds convergent vers l'arbre brownien continu qui est un arbre réel continu qui peut être codé par l'excursion brownienne normalisée. Par ailleurs, les arbres binaires sous le modèle de Catalan peuvent être construits comme des sous arbres de l'arbre brownien continu. Ce plongement permet d'obtenir des convergences presque-sûres de fonctionnelles. Plus généralement, lorsque la loi de reproduction est critique et appartient au domaine d'attraction d'une loi stable, les arbres de Galton-Watson conditionnés à avoir un grand nombre de nœuds convergent vers des arbres de Lévy stables, ce qui permet d'obtenir le comportement asymptotique des fonctionnelles additives pour certains arbres simplement générés. Dans le second cas, on s'intéresse à la convergence de la fonction de répartition empirique des degrés ainsi qu'aux densités d'homomorphismes de suites de graphes finis, simples et denses. Une suite de graphes finis, simples, denses converge si la suite réelle des densités d'homomorphismes associées converge pour tout graphe fini simple. La limite d'une telle suite de graphes peut être décrite par une fonction symétrique mesurable appelée graphon. Etant donné un graphon, on peut construire par échantillonnage, une suite de graphes qui converge vers ce graphon. Nous avons étudié le comportement asymptotique de la fonction de répartition empirique des degrés et de mesures aléatoires construites à partir des densités d'homomorphismes associées à cette suite particulière de graphes denses / The aim of this thesis is the study of approximations and rates of convergence for functionals of large dicsrete graphs towards their limits. We contemplate two cases of discrete graphs: trees (i.e. connected graphs without cycles) and dense simple finite graphs. In the first case, we consider additive functionals for two models of random trees: the Catalan model for binary trees (where a tree is chosen uniformly at random from the set of full binary trees with a given number of nodes) and the simply generated trees (and more particulary the Galton-Watson trees conditioned by their number of nodes).Asymptotic results are based on scaling limits of conditioned Galton-Watson trees. Indeed, when the offspring distribution is critical and with finite variance (that is the case of Catalan binary trees), the Galton-Watson trees conditioned to have a large number of nodes converge towards the Brownian continuum tree which is a real tree coded which can be coded by the normalized Brownian excursion. Furthermore, binary trees under the Catalan model can be built as sub-trees of the Brownian continuum tree. This embedding makes it possible to obtain almost sure convergences of functionals. More generally, when the offspring distribution is critical and belongs to the domain of attraction of a stable distribution, the Galton-Watson trees conditioned to have a large number of nodes converge to stable Levy trees giving the asymptotic behaviour of additive functionals for some simply generated trees. In the second case, we are interested in the convergence of the empirical cumulative distribution of degrees and the homomorphism densities of sequences of dense simple finite graphs. A sequence of dense simple finite graphs converges if the real sequence of associated homomorphism densities converges for all simple finite graph. The limit of such a sequence of dense graphs can be described as a symmetric measurable function called graphon.Given a graphon, we can construct by sampling, a sequence of graphs which converges towards this graphon. We have studied the asymptotic behaviour of the empirical cumulative distribution of degrees and random measures built from homomorphism densities associated to this special sequence of dense graphs

La popularité des réseaux informatiques et d'Internet s'accompagne d'un essor des applications communicantes et de la multiplication des protocoles dont le fonctionnement est plus ou moins compliqué, ce qui implique également des performances différentes en termes de robustesse. Un premier objectif de cette thèse est d'approfondir plus en détails la robustesse de protocoles s'illustrant par d'extraordinaires performances empiriques tels que les botnets. Différents protocoles employés par les botnets sont donc modélisés dans cette thèse. Par ailleurs, l'essor et la diversité des protocoles s'accompagnent d'un manque de spécification volontaire ou non que la rétro-ingénierie tente de retrouver. Une première phase essentielle est notamment de découvrir les types de messages. La technique mise en \oe uvre dans cette étude s'appuie sur les machines à vecteurs de supports tout en ayant au préalable spécifié de nouvelles représentations des messages dont la complexité de calcul est très réduite par rapport aux autres techniques existantes. Enfin, il existe généralement un grand nombre d'applications distinctes pour un même protocole et identifier précisément le logiciel ou le type d'équipement utilisé (marque, version) est un atout essentiel dans plusieurs domaines tels que la supervision ou la sécurité des réseaux. S'appuyant uniquement sur les types de messages, le comportement d'un équipement, c'est-à-dire la manière dont il interagit avec les autres, est une information très avantageuse lorsqu'elle est couplée avec les délais entre les messages. Enfin, la grammaire d'un protocole connu permet de construire les arbres syntaxiques des messages, dont le contenu et la structure sémantiquement riche, avaient peu été étudiés jusqu'à maintenant dans le cadre de l'identification des équipements.

La géométrie fractale, développée par Mandelbrot dans les années 70, a connu un essor considérable ces 20 dernières années. Dans cette thèse, je m'intéresse à la génération de signaux dits fractals et multifractals. J'étudie en particulier 2 modèles, dont leur point commun est leur structure d'arbre de branchement sous jacente.<br />Le premier modèle est une généralisation des Systèmes de fonctions Itérés ou IFS, introduits par Hutchinson dans les années 80. Les IFS constituent un moyen simple et efficace pour produire des ensembles et des processus fractals en itérant un nombre fixed d'opérateurs. L'idée est d'autoriser un nombre aléatoire d'opérateurs aléatoires à chaque itération de l'algorithme. Nous donnons des conditions simples et faciles à vérifier sous lesquelles l'IFS admet un point fixe. Quelques propriétés du point fixe sont également étudiées. Le deuxième modèle, que nous appellons Multifractal Embedded Branching Process (MEBP), s'obtient à l'aide d'un changement de temps multifractal d'un processus à invariance d'échelle discrète, le processus EBP Canonique (CEBP). Nous donnons un algorithm efficace de simulation "on-line" de ces processus, permettant de générer X(n + 1) à partir de X(n) en O(log n) opérations. Nous obtenons également un borne supérieure pour le spectre multifractal du changement de temps et confirmons les résultats théoriques à l'aide de simulations. Les mouvements Browniens en temps multifractal sont des cas particuliers des processus MEBP, ce qui suggère une application potentielle des processus MEBP en finance. Enfin, nous proposons d'imiter un mouvement Brownien fractionnaire à l'aide d'un processus MEBP.

Le système dynamique Chaos Game Representation associe une suite de lettres dans un alphabet fini, une mesure empirique sur un ensemble. Fournit-elle plus d'information<br />que les méthodes de comptage de mots classiques ? A<br />partir d'une caractérisation basée sur la CGR, on propose une nouvelle famille de<br />tests donnant l'ordre d'une chaîne de Markov homogène.<br />On définit ensuite une construction d'arbres digitaux de recherche,<br />inspirés par la CGR, en insérant successivement les préfixes retournés d'une chaîne de Markov. On montre que les longueurs des branches critiques se comportent, au premier ordre, comme si les<br />séquences insérées étaient indépendantes entre elles.<br />La dernière partie est consacrée à l'étude de la convergence presque sûre des moments normalisés de tout ordre de martingales vectorielles dans le théorème de la limite centrale<br />presque sûr. Les résultats sont appliqués aux erreurs d'estimation et de prédiction dans les régressions linéaires et les processus de branchement.

Un graphe arête-colorié Gc est un graphe dont les arêtes sont coloriées par un ensemble de couleurs données. Un sous-graphe de Gc est dit proprement colorié s'il ne contient pas d'arêtes adjacentes de même couleur. Un graphe ou multigraphe c-arête-colorié Gc, est dit k-lié (respectivement k-arête-lié) si et seulement si quelque soient 2k sommets distincts de V(Gc), notés, x1 y1 , x2 y2 , ..., xk yk , il existe k chaînes élémentaires sommet-disjointes (respectivement arête-disjointes) proprement arête-coloriées, reliant x1 à y1 , x2 à y2 , ... , xk à yk .Un arbre couvrant propre d'un graphe Gc est un sous-graphe de Gc qui est un arbre couvrant proprement colorié.Un arbre couvrant faiblement colorié est une arborescence telle qu'il existe une chaîne proprement coloriée entre la racine et chaque sommet du graphe.Dans la première partie de cette thèse, nous donnons des conditions suffisantes pour qu'un graphe arête-colorié soit k-lié. C'est un problème classique en théorie des graphes, avec des applications multiples. Ainsi, nous avons établi entre autres les résultats suivants.A) Tout multigraphe 2-arête-colorié d'ordre n ≥ 242k tel que dc(Gc) ≥ n/2+k -1, est k-lié. B) Tout multigraphe c-arête-colorié d'ordre n ≥ 2k et de taille m≥ cn(n-1)/2 - c(n-2k +1)+1 est k-lié.C) Tout multigraphe c-arête-colorié d'ordre n ≥ 2k tel que dc(x) ≥ n/2 pour tout sommet x, est k-arête-lié.D) Tout multigraphe 2-arête-colorié d'ordre n ≥ 2k ≥ 10 et de taille m ≥ n2 -5n + 11 tel que dc(x) ≥ 1 pour tout sommet x, est k-arête-lié.Dans la seconde partie de cette thèse, deux autres problèmes classiques en théorie des graphes sont traités dans la version arête-coloriée. Il s'agit des arbres couvrants et des chaînes hamiltoniennes. Nous donnons ci-dessous quelques résultats.E) Tout graphe simple c-arête-colorié k-connexe d'ordre n ≥ C²k+1 + k + 2 avec c ≥ C²n-k-1 + k +1, a un arbre couvrant propre.F) Tout graphe Gc connexe c-arête-colorié de degré rainbow rd(Gc)=k et d'ordre n ≥ C²k+1 + k + 2 avec c ≥ C²n-k-1 + k +1, possède un arbre couvrant propre.G) Tout graphe simple c-arête-colorié k-connexe d'ordre n ≥ ((k + j)2 + 3(k + j) - 2)/2 avec c ≥ ((n - k - j)(n - k - j - 1))/2 + 2 , où j(j -1)=k , possède un arbre couvrant faiblement colorié.H) Tout multigraphe Gc d'ordre n ≥ 14 et de taille m ≥ (n - 3)(n - 4) + 3n - 2 tel que rd(Gc) = 2, possède une chaîne hamiltonienne propre. I) Tout multigraphe c-arête-colorié d'ordre n ≠ 5, 7 et de taille m ≥ n2 - 3n + 4, possède une chaîne hamiltonienne propre.La plupart des résultats exposés, sont les meilleurs possibles relativement aux propriétés sur les conditions suffisantes.

Ce travail est consacré à l'étude de limites d'échelle de différentes fonctionnelles de marches aléatoires sur un arbre de Galton-Watson, potentiellement en milieu aléatoire. La marche aléatoire que nous considérons sur cet arbre est une marche aux plus proches voisins récurrente nulle, dont les probabilités de transition dépendent de l'environnement. Plus particulièrement, nous étudions la trace de la marche, c'est-à-dire le sous-arbre constitué des sommets visités par celle-ci. Nous considérons d'abord le cas où dans un certain sens l'environnement est à variance finie, et nous montrons que bien renormalisée la trace converge vers la forêt brownienne. Nous considérons ensuite des hypothèses plus faibles, et nous montrons que la fonction de hauteur de la marche (c'est-à-dire la suite des hauteurs prises par la marche) converge vers le processus de hauteur en temps continu d'un processus de Lévy spectralement positif strictement stable, et que la trace de la marche converge vers l'arbre réel codé par ce même processus. La stratégie employée pour établir ces résultats repose sur l'étude d'un type d'arbres que nous introduisons dans cette thèse : ceux-ci sont des arbres de Galton-Watson à deux types, l'un des types étant stérile, et à longueur d'arête. Notre principal résultat concernant ces arbres assure que leur fonction de hauteur satisfait un principe d'invariance, similaire à celui vérifié par les arbres de Galton-Watson simples. Ces arbres trouvent également une application directe dans les arbres de Galton-Watson multitype à infinité de types, un lien explicite entre les deux nous permettant de montrer qu'ils satisfont également le même principe d'invariance. / This work is devoted to the study of scaling limits of different functionals of random walks on a Galton-Watson tree, potentially in random environment. The randow walk we consider is a null recurrent nearest-neigbout random walk, the probability transition of which depend on the environment. More precisely, we study the trace of the walk, that is the sub-tree made up of the vertices visited by the walk. We first consider the case where in a certain sense the environment has finite variance, and we show that when well-renormalised, the trace converges towards the Brownian forest. We then consider hypotheses of regular variation on the environement, and we show that the height function of the walk (that is the sequence of heights in the tree of the walk) converges towards the continuous time height process of a spectrally positive strictly stable Lévy process, and that the trace of the walk converges towards the real tree coded by this very process. The strategy used to prove these two results is based on the study of a certain kind of trees that we introduce in this thesis: they are Galton-Watson trees with two types, one of which being sterile, and with edge lengths. Our main result about these trees states that their height functions satisfies an invariance principle, similar to that verified by simple Galton-Watson trees. These trees also find a direct application in multitype Galton-Watson trees with infinitely many types, as an explicit link between these two kind of trees allow us to show that they satisfy also the same invariance principle.

Cette thèse porte sur l'inférence de réseaux. Le cadre statistique naturel à ce genre de problèmes est celui des modèles graphiques, dans lesquels les relations de dépendance et d'indépendance conditionnelles vérifiées par une distribution multivariée sont représentées à l'aide d'un graphe. Il s'agit alors d'apprendre la structure du modèle à partir d'observations portant sur les sommets. Nous considérons le problème d'un point de vue bayésien. Nous avons également décidé de nous concentrer sur un sous-ensemble de graphes permettant d'effectuer l'inférence de manière exacte et efficace, à savoir celui des arbres couvrants. Il est en effet possible d'intégrer une fonction définie sur les arbres couvrants en un temps cubique par rapport au nombre de variables à la condition que cette fonction factorise selon les arêtes, et ce malgré le cardinal super-exponentiel de cet ensemble. En choisissant les distributions a priori sur la structure et les paramètres du modèle de manière appropriée, il est possible de tirer parti de ce résultat pour l'inférence de modèles graphiques arborescents. Nous proposons un cadre formel complet pour cette approche.Nous nous intéressons également au cas où les observations sont organisées en série temporelle. En faisant l'hypothèse que la structure du modèle graphique latent subit un certain nombre de brusques changements, le but est alors de retrouver le nombre et la position de ces points de rupture. Il s'agit donc d'un problème de segmentation. Sous certaines hypothèses de factorisation, l'exploration exhaustive de l'ensemble des segmentations est permise et, combinée aux résultats sur les arbres couvrants, permet d'obtenir, entre autres, la distribution a posteriori des points de ruptures en un temps polynomial à la fois par rapport au nombre de variables et à la longueur de la série. / In this dissertation we investigate the problem of network inference. The statistical frame- work tailored to this task is that of graphical models, in which the (in)dependence relation- ships satis ed by a multivariate distribution are represented through a graph. We consider the problem from a Bayesian perspective and focus on a subset of graphs making structure inference possible in an exact and e cient manner, namely spanning trees. Indeed, the integration of a function de ned on spanning trees can be performed with cubic complexity with respect to number of variables under some factorisation assumption on the edges, in spite of the super-exponential cardinality of this set. A careful choice of prior distributions on both graphs and distribution parameters allows to use this result for network inference in tree-structured graphical models, for which we provide a complete and formal framework.We also consider the situation in which observations are organised in a multivariate time- series. We assume that the underlying graph describing the dependence structure of the distribution is a ected by an unknown number of abrupt changes throughout time. Our goal is then to retrieve the number and locations of these change-points, therefore dealing with a segmentation problem. Using spanning trees and assuming that segments are inde- pendent from one another, we show that this can be achieved with polynomial complexity with respect to both the number of variables and the length of the series.

Dans un monde déterministe, toute donnée d'un problème d'optimisation est censée être connue avec certitude. Dans le monde réel, on est souvent confronté à des cas où certains paramètres sont incertains. La démarche consistant à considérer un seul jeu de paramètres, supposant que ceci représente suffisamment bien la réalité, est vite mise en cause. On considère travailler sur plusieurs périodes temporelles et sur un espace d'incertitude discrétisé, en introduisant ainsi les notions d'arbres de scénarios et des modèles multi-étapes. Les dimensions de ces problèmes augmentent de façon exponentielle avec le nombre de périodes d'étude, rendant les méthodes directes impossibles à appliquer. Le problème qui a motivé ce travail est issu d'une application industrielle réelle et concerne la souscription de contrats dans un marché gazier. Les prix du marché spot, ainsi que la demande clientèle sont considérés incertains, et représentés par un arbre de scénarios. Le modèle qui ressort possède une structure ressemblant à une grande famille de problèmes dynamiques de dimensionnement. A l'issue d'un travail bibliographique, mené particulièrement sur les méthodes de résolution des modèles multi-étapes, la décomposition imbriquée est la méthode qui est retenue. Sur les très grandes instances, même les méthodes de décomposition peuvent s'avérer longues à converger. Cette thèse est consacrée à de nouvelles mises en oeuvre de la décomposition imbriquée, le but étant de pouvoir traiter plus de scénarios en moins de temps. Certains aspects de la méthode sont remis en cause, nous permettant de réduire le nombre d'itérations jusqu'à ce que la convergence soit atteinte. D'autres aspects sont également étudiés dans l'objectif de réduire le temps de calcul passé sur chaque itération séparément. Les démarches proposées sont validées à travers plusieurs séries d'expériences qui mettent en valeur la supériorité de l'approche proposée par rapport à l'approche classique.

Thèse diffusée initialement dans le cadre d'un projet pilote des Presses de l'Université de Montréal/Centre d'édition numérique UdeM (1997-2008) avec l'autorisation de l'auteur.