.

Nesta tese, estudamos um arcabouço, introduzido por Frank, que denominamos de sistemas generalizados de núcleos. Provamos teoremas sobre empacotamentos de certos objetos combinatórios neste arcabouço, tanto para o caso inteiro quanto para o fracionário. Estes teoremas, em particular, implicam em uma melhora nos limitantes superiores de Schrijver, para o empacotamento de ramificações, e de Gabow e Manu, para o empacotamento de arborescências. Além disso, também provamos que o problema de minimização num poliedro relacionado pode ser resolvido em tempo polinomial, dado um oráculo de separação. / We study a framework, which we call a generalized kernel system, introduced by Frank. We prove some integral and fractional packing theorems on this framework which, in particular, imply an improvement on the best upper bounds currently known, one due to Schrijver, for packing branchings from a given root-sets, and another, due to Gabow and Manu, for packing spanning arborescences from a given root. We also establish the polynomial time complexity, modulo a separation oracle, of a related minimization problem involving a polyhedron derived from this framework.

Nesta tese, estudamos um arcabouço, introduzido por Frank, que denominamos de sistemas generalizados de núcleos. Provamos teoremas sobre empacotamentos de certos objetos combinatórios neste arcabouço, tanto para o caso inteiro quanto para o fracionário. Estes teoremas, em particular, implicam em uma melhora nos limitantes superiores de Schrijver, para o empacotamento de ramificações, e de Gabow e Manu, para o empacotamento de arborescências. Além disso, também provamos que o problema de minimização num poliedro relacionado pode ser resolvido em tempo polinomial, dado um oráculo de separação. / We study a framework, which we call a generalized kernel system, introduced by Frank. We prove some integral and fractional packing theorems on this framework which, in particular, imply an improvement on the best upper bounds currently known, one due to Schrijver, for packing branchings from a given root-sets, and another, due to Gabow and Manu, for packing spanning arborescences from a given root. We also establish the polynomial time complexity, modulo a separation oracle, of a related minimization problem involving a polyhedron derived from this framework.

La première partie de ce mémoire est consacrée à l'énumération de diverses familles de structures arborescentes, en général selon le nombre de sommets. Les trois premiers chapitres sont consacrés à l'étude des arborescences de Cayley telles que la racine est inférieure à ses fils et des arborescences alternantes. La plupart de nos résultats sont prouvés bijectivement. Nous nous intéressons ensuite aux arborescences coloriées, et plus particulièrement à la formule d'inversion de séries formelles multivariées de Good-Lagrange. Nous donnons une nouvelle preuve bijective d'une variante de cette formule et utilisons cette preuve pour prouver combinatoirement diverses formules d'énumération de structures arborescentes et en déduire des algorithmes de génération aléatoire pour ces structures (notamment les cactus planaires). Nous concluons cette première partie par un chapitre consacré aux constellations : en combinant notre preuve de la formule de Good-Lagrange et la conjugaison d'arborescences (due à Bousquet-Mélou et Schaeffer), nous prouvons bijectivement une formule (nouvelle) pour l'énumération de constellations selon le nombre de sommets et de faces. Dans la seconde partie, nous étudions le problème de la recherche de motifs dans une arborescence, en utilisant une structure de données classique pour les mots : l'arborescence des suffixes. Nous proposons notamment un algorithme de recherche de motifs dans une arborescence, basé sur un codage d'une arborescence par des mots et sur l'utilisation de l'arborescence des suffixes d'un de ces mots, qui semble avoir de bonnes propriétés expérimentales. Nous concluons en étendant la notion d'arborescence des suffixes des mots aux arborescences et en décrivant un algorithme de construction pour cette structure.

Les nouveaux acteurs, les nouveaux services et les nouveaux contenus multimédias qui transitent sur le réseau internet génèrent un trafic et des débits de plus en plus élevés. Ceci peut occasionner une congestion, source de latence et de dépréciation de la qualité de service ressentie par les utilisateurs. Un fournisseur d'accès à internet dont l'objectif est de garantir un réseau d'excellence doit donc prendre des mesures pour améliorer sans cesse la fluidité de son réseau. Cela passe notamment par la mise en place d'un réseau de distribution de contenus (déploiement de dispositifs sur le réseau existant). Dans un premier temps cette thèse s'articule à présenter des approches de programmation dynamique de localisation de serveurs optimales dans des arborescences. Nous présentons également un approche pour résoudre le problème de déploiement de CDN et de k serveurs/caches à l'aide de l'algorithme exact et polynomial d'intersection de matroïdes. Nous explicitons ensuite ce qu'est un cache et quelles sont ses caractéristiques. Nous définissons ensuite les hypothèses effectuées et la modélisation associée pour le déploiement de caches transparents dans une arborescence, et le liens avec les algorithmes existants présentés précédemment. Nous présentons alors un modèle complet pour un programme linéaire en nombres entiers (PLNE) et un nouveau paradigme de programmation dynamique pour résoudre ce même problème. Nous montrons alors en quoi cette approche se généralise à des problèmes connexes de localisation dans les arborescences, ainsi que les performances pratiques d'une telle approche. D'un regard plus théorique, nous mesurons la capacité d'un réseau donné par le routage optimal de ses demandes, et, de ce fait, ses liens critiques. Nous manipulons alors le problème de flot concurrent maximal (FCM), un problème classique de la littérature de recherche opérationnelle. Nous exhibons alors de nouvelles formulations exactes pour résoudre ce problème, ainsi que les problèmes de multi-flots de manière plus générale. Une heuristique de construction de formulation pour le FCM est également proposée, pour tirer parti de la distribution spécifique des capacités d'une instance. Nous montrons alors la supériorité des performances de ces nouvelles formulations par le biais de comparaisons. Enfin, nous décrivons le premier algorithme exact et fortement polynomial pour résoudre le problème de flot concurrent maximal dans le cas d'une seule source; et nous montrons l'efficacité pratique d'une telle approche, comparée aux meilleures formulations explicitées précédemment / Streaming requirements on internet network are even more driven by new actors, new services and new digital contents. This leads to high probability of congestion, latency and therefore, a critical decrease of quality of service and/or experience for customers. An internet service provider (ISP) whose goal is to guarantee a first-class performance, needs to take measures to constantly enhance the fluidity of the traffic streaming on its network. One way to face the problem, is to build a Content Delivery Network (CDN). A CDN mainly consists in the deployment of different devices on an existing network. First of all, this thesis presents dynamic programming approaches to tackle server location problems in tree networks. Then, we address a variation of the matroïd intersection algorithm to solve the k-server/cache location problem. We start by giving the definition and characteristics of transparent-caching, as well as the hypothesis that we will use it to build models for transparent cache location in tree network. We tract it to a Mixed Integer Program, and formulate a new paradigm of dynamic programming. We show the relevance of such approach for our problem, and to what extent it can be tractable in other related problems. From a more theoretical point of view, we manage to measure the capacity of a network which is given by the optimal routing strategy, and hence, to identify its critical links. We deal with the Maximum Concurrent Flow (MCF), a classical combinatorial optimization problem. We propose new models and formulations to solve this problem exactly, and more general multi-flows problems as well. A heuristic is also given, to adapt the model to the specific instance values. We experiment these formulations to show the improvements they can provide. Finally, we describe the first strongly polynomial algorithm to solve the maximum concurrent flow to optimality, in the single source case. We show the efficiency of such an approach, even compared to the best models previously presented

Nous nous intéressons à des modèles statistiques pour les données indexées par des arborescences. Dans le contexte de l'équipe Virtual Plants, équipe hôte de cette thèse, les applications d'intérêt portent sur le développement de la plante et sa modulation par des facteurs environnementaux et génétiques. Nous nous restreignons donc à des applications issues du développement de la plante, à la fois au niveau microscopique avec l'étude de la lignée cellulaire du tissu biologique servant à la croissance des plantes, et au niveau macroscopique avec le mécanisme de production de branches. Le catalogue de modèles disponibles pour les données indexées par des arborescences est beaucoup moins important que celui disponible pour les données indexées par des chemins. Cette thèse vise donc à proposer un cadre de modélisation statistique pour l'étude de patterns pour données indexées par des arborescences. À cette fin, deux classes différentes de modèles statistiques, les modèles de Markov et de détection de ruptures, sont étudiées. / We address statistical models for tree-indexed data.Tree-indexed data can be seen as a generalization of path-indexed data since directed path graphs are directed tree graphs where there is at most one child per vertex.In the context of the Virtual Plants team, host team of this thesis, applications of interest focus on plant development and its modulation by environmental and genetic factors.We thus focus on plant developmental applications, both at the microscopic level with the study of the cell lineage in the biological tissue responsible for the plant growth, and at the macroscopic level with the mechanism of production of branches. The catalog of models available for tree-indexed data is far less important than the one available for path-indexed data.This thesis therefore aims at proposing a statistical modeling framework for studying patterns in tree-indexed data.To this end, two different classes of statistical models, Markov and change-point models, are investigated.

La théorie des jeux a développé, à ses débuts, une vocation pour les sciences sociales et économiques, avec des applications disparates, comme par exemple le traitement de données médicales. Elle apparaît aujourd'hui comme un paradigme de concepts et de techniques très général, dont le potentiel reste encore à exploiter en informatique. Dans cette thèse nous étudions une branche particulière, la théorie des jeux combinatoires (à deux joueurs), pour en tirer bénéfice dans le domaine, très actif, des sémantiques formelles des langages de programmation. D'un jeu, nous pouvons séparer l'aspect syntaxique, inhérent aux dénouements possibles des matchs, de l'aspect sémantique, inhérent aux prévisions sur le gagnant et la quantification de son gain (en termes d'un enjeu quelconque, tel que l'argent ou le préstige). Pour modeliser la notion de gain, la structure d'évaluation choisie ne doit pas forcément être celle des booléens (gagné ou perdu), ou celle des entiers naturels ou relatifs. Il suffit qu'elle vérifie des propriétés, assez faibles, garantissant l'existence d'une sémantique même lorsque le jeu donne lieu à des matchs infinis, comme dans le cas du jeu de la bisimulation entre processus concurrents, et du jeu de la programmation logique. Dans ce travail, nous étudions la caractérisation sémantique d'un langage logique (avec ou sans contrainte) en termes de jeu à deux joueurs. Au-delà du modèle intuitif des jeux, dont la valeur pédagogique mériterait d'être approfondie, une telle interprétation permet de réutiliser un des algorithmes les plus utilisés dans la théorie des jeux combinatoire, Alpha-Bêta, comme moteur de résolution pour les langages logiques. Les résultats récents et spectaculaires obtenus par les programmes d'échecs (souvenons-nous de la défaite du champion du monde Kasparov contre le programme Deep Blue d'IBM) témoignent d'une forme d'intelligence artificielle développée dans ces programmes qui peut être transposée et exploitée dans la résolution des langages logiques. La résolution d'interrogations existentielles conjonctives dans une théorie de clauses de Horn du premier ordre est en particulier concernée. En effet, la capacité d'Alpha-Bêta à simplifier le calcul ou, en d'autres termes, sa capacité à éliminer les coups inintéressants, n'est pas intimement liée à un type de jeu ou à un type de gain particuliers, mais demande juste des propriétés algébriques qui sont satisfaites dans le jeu de la programmation logique. La correction d'Alpha-Bêta est prouvée de façon formelle pour un éventail de structures très large. Les valeurs calculées pourront être aussi bien des entiers naturels, comme dans le cas du jeu d'échecs, que des substitutions ou des contraintes, comme dans le cas des langages logiques.