La notion de connexité est fondamentale en théorie des graphes. Nous proposons une étude approfondie d'un récent développement dans ce domaine, en ajoutant des contraintes de matroïdes.Dans un premier temps, nous exhibons deux opérations de réduction sur les graphes connectés avec contraintes de matroïdes. Ces opérations permettent de généraliser le théorème de caractérisation de la connectivité de Menger et le théorème de packing d'arborescences d'Edmonds.Cependant, cette extension du théorème d'Edmonds ne garantie plus que les arborescences soient couvrantes. Il a été conjecturé que l'on peut toujours trouver de telles arborescences couvrantes. Nous prouvons cette conjecture dans certains cas particuliers, notamment pour les matroïdes de rang deux et pour les matroïdes transversaux. Nous réfutons cette conjecture dans le cas général en construisant un contre-exemple à plus de 300 sommets, sur une extension parallèle du matroïde de Fano.Enfin, nous explorons d'autres notions de connexité avec contraintes de matroïdes: pour des graphes mixtes, des hypergraphes, et avec condition d'atteignabilité. / The notion of connectivity is fundamental in graph theory. We study thoroughly a recent development in this field, with the addition of matroid constraints.Firstly, we exhibit two reduction operations on connected graphs with matroid constraints. Using these operations, we generalize the Menger's theorem on connectivity and Edmond's theorem on packing of arborescences.However, this extension of Edmond's theorem does not ensure that the arborescences are spanning. It has been conjectured that one can always find such spanning arborescences. We prove this conjecture in some cases, including matroids of rank two and transversal matroids. We disprove this conjecture in the general case by providing a counter-example with more than 300 vertices, on a parallel extension of the Fano matroid.Finally, we explore other generalizations of connectivity with matroid constraints: in mixed graphs, hypergraphs and with reachability conditions.

Nous proposons une approche de gestion des processus métier configurables (cBP) offrant une vue consolidée des variantes de ces processus. Une variante est le résultat de l'ajustement d'un cBP en réponse à des besoins fonctionnels et / ou structurels. Cette approche utilise une base de connaissances pour suivre les spécificités de chaque variante représentée sous la forme d'arborescence de structure de processus configurable (cPST). Une implémentation de l'approche consistant à générer un cPST à partir d'un cBP est proposée. Nous appliquons cette approche pour calculer la complexité des processus métier configurables et prouver son avantage pour améliorer la qualité du cBP / We propose an approach for managing configurable Business Processes (cBP) that offer a consolidated view over these processes’ variants. A variant is the result of adjusting a BP in response to functional and/or structural needs. The approach uses a knowledge base to track the specificities of each variant that is represented as configurable Process Structure Tree (cPST). An implementation of the approach that consists of generating a cPST from a cBP is proposed. We apply this approach to compute configurable business process complexity and to prove its advantage for improving cBP quality

Nesta tese estudamos dois problemas em digrafos: um problema de empacotamento e um problema de contagem. Estudamos o problema de empacotamento máximo de arborescências no digrafo aleatório D(n,p), onde cada possvel arco é inserido aleatoriamente ao acaso com probabilidade p = p(n). Denote por (D(n,p)) o maior inteiro possvel 0 tal que, para todo 0 l , temos ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}| Provamos que a quantidade máxima de arborescências em D(n,p) é (D(n,p)) assintoticamente quase certamente. Nós também mostramos estimativas justas para (D(n, p)) para todo p [0, 1]. As principais ferramentas que utilizamos são relacionadas a propriedades de expansão do D(n, p), o comportamento do grau de entrada do digrafo aleatório e um resultado clássico de Frank que serve como ligação entre subpartições em digrafos e a quantidade de arborescências. Para o problema de contagem, estudamos a densidade de subtorneios fortemente conexos com 5 vértices em torneios grandes. Determinamos a densidade assintótica máxima para 5 torneios bem como as famlias assintóticas extremais de cada torneios. Como subproduto deste trabalho caracterizamos torneios que são blow-ups recursivos de um circuito orientado com 3 vértices como torneios que probem torneios especficos de tamanho 5. Como principal ferramenta para esse problema utilizados a teoria de álgebra de flags e configurações combinatórias obtidas através do método semidefinido. / In this thesis we study two problems dealing with digraphs: a packing problem and a counting problem. We study the problem of packing the maximum number of arborescences in the random digraph D(n,p), where each possible arc is included uniformly at random with probability p = p(n). Let (D(n,p)) denote the largest integer 0 such that, for all 0 l , we have ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}|. We show that the maximum number of arc-disjoint arborescences in D(n, p) is (D(n, p)) asymptotically almost surely. We also give tight estimates for (D(n, p)) for every p [0, 1]. The main tools that we used were expansion properties of random digraphs, the behavior of in-degree of random digraphs and a classic result by Frank relating subpartitions and number of arborescences. For the counting problem, we study the density of fixed strongly connected subtournaments on 5 vertices in large tournaments. We determine the maximum density asymptotically for five tournaments as well as unique extremal sequences for each tournament. As a byproduct of this study we also characterize tournaments that are recursive blow-ups of a 3-cycle as tournaments that avoid three specific tournaments of size 5. We use the theory of flag algebras as a main tool for this problem and combinatorial settings obtained from semidefinite method.

Avec l'explosion de la quantité de données biologiques disponible, développer de nouvelles méthodes de traitements efficaces est une problématique majeure en bioinformatique. De nombreuses structures biologiques sont modélisées par des structures arborescentes telles que les structures secondaires d'ARN et l'architecture des plantes. Ces structures contiennent des motifs répétés au sein même de leur structure mais également d'une structure à l'autre. Nous proposons d'exploiter cette propriété fondamentale afin d'améliorer le stockage et le traitement de tels objets. En nous inspirant du principe de filtres sur les séquences, nous définissons dans cette thèse une méthode de filtrage sur les arborescences ordonnées, permettant de rechercher efficacement dans une base de données, un ensemble d'arborescences ordonnées proches d'une arborescence requête. La méthode se base sur un découpage de l'arborescence en graines et sur une recherche de graines communes entre les structures. Nous définissons et résolvons le problème de chaînage maximum sur des arborescences. Nous proposons dans le cas des structures secondaires d'ARN une définition de graines (l−d) centrées. Dans un second temps, en nous basant sur des techniques d'instanciations utilisées, par exemple, en infographie et sur la connaissance des propriétés de redondances au sein des structures biologiques, nous présentons une méthode de compression permettant de réduire l'espace mémoire nécessaire pour le stockage d'arborescences non-ordonnées. Après une détermination des redondances, nous utilisons une structure de données plus compacte pour représenter notamment l'architecture de la plante, celle-ci pouvant contenir des informations topologiques mais également géométriques.

.

Le piano de Xenakis, comme tous les langages instrumentaux du compositeur, reste un objet assez singulier dans la littérature de l’instrument. Encore aujourd’hui rarement abordé par les pianistes, il semble d’une difficulté vertigineuse, et les voies qui mènent à sa réalisation restent dissimulées. L’originalité du langage musical du compositeur génère une technique extrêmement détachée de la tradition pianistique, et un pianiste manque souvent de savoir-faire et d’outils pour parvenir à l’exécution. Dans cette recherche nous essaierons d’aborder ce lien entre les principaux concepts xénakiens (musique stochastique, musique symbolique, mouvement brownien et pans ondulatoires, arborescences, cribles) et son langage pianistique, afin de mieux identifier cette écriture instrumentale et envisager des chemins pouvant favoriser l’interprétation de cette musique. Nous étudions la totalité des œuvres avec piano, puis nous explorons chacun des grands concepts du compositeur, pour établir ensuite leur connexion avec le langage pianistique dans quatre œuvres majeures pour le piano : Herma, Synaphaï, Evryali, Mists. Pour chacune de ces œuvres nous effectuons une analyse, puis proposons une approche pianistique visant le travail, l’exécution et l’interprétation. / Xenakis’ piano, like all the composers’ instrumental languages, remains a rather peculiar issue in the literature of the instrument, still rarely approached by pianists, not only because of its obvious difficulty, but mostly because of the great number of question raised by it, questions related to its feasibility and execution. The originality of the composer’s musical language generates a technic extremely detached from piano tradition, and a pianist often lacks the savoir-faire and the tools to reach a convincing execution of these works. In this research we try to approach the link between the principal xenakian concepts (stochastic music, symbolic music, Brownian movement and wave-like sides, arborescences, sieves) and the pianistic language related to it, in order to identify Xebakis’ writing for the instrument and consider the ways that the performance of this music can take place. We study briefly the whole output of Xenakis’ piano works (solo, concerto, chamber music, piano in the orchestra), then we explore each of the composer’s main concepts, in order to establish their connection to the pianistic language in four major works for piano : Herma, Synaphaï, Evryali, Mists. For each one of these works, we first perform an analysis, then we propose a pianistic approach aiming at the preparation and the performance.

Avec l’explosion de la quantité de données biologiques disponible, développer de nouvelles méthodes de traitements efficaces est une problématique majeure en bioinformatique. De nombreuses structures biologiques sont modélisées par des structures arborescentes telles que les structures secondaires d’ARN et l’architecture des plantes. Ces structures contiennent des motifs répétés au sein même de leur structure mais également d’une structure à l’autre. Nous proposons d’exploiter cette propriété fondamentale afin d’améliorer le stockage et le traitement de tels objets.En nous inspirant du principe de filtres sur les séquences, nous définissons dans cette thèse une méthode de filtrage sur les arborescences ordonnées permettant de rechercher efficacement dans une base de données un ensemble d’arborescences ordonnées proches d’une arborescence requête. La méthode se base sur un découpage de l’arborescence en graines et sur une recherche de graines communes entre les structures. Nous définissons et résolvons le problème de chainage maximum sur des arborescences. Nous proposons dans le cas des structures secondaires d’ARN une définition de graines (l−d) centrées.Dans un second temps, en nous basant sur des techniques d’instanciations utilisées, par exemple, en infographie et sur la connaissance des propriétés de redondances au sein des structures biologiques, nous présentons une méthode de compression permettant de réduire l’espace mémoire nécessaire pour le stockage d’arborescences non-ordonnées. Après une détermination des redondances nous utilisons une structure de données plus compacte pour représenter notamment l’architecture de la plante, celle-ci pouvant contenir des informations topologiques mais également géométriques. / The explosion of available biological data urges the need for bioinformatics methods. Manybiological structures are modeled by tree structures such as RNA secondary structure and plantsarchitecture. These structures contain repeating units within their structure, but also betweendifferent structures. We propose to exploit this fundamental property to improve storage andtreatment of such objects.Following the principle of sequence filtering, we define a filtering method on ordered treesto efficiently retrieve in a database a set of ordered trees close from a query. The method isbased on a decomposition of the tree into seeds and the detection of shared seeds between thesestructures. We define and solve the maximum chaining problem on trees. We propose for RNAsecondary structure applications a definition of (l−d) centered seed.Based on instantiation techniques used for instance in computer graphics and the repetitivenessof biological structures, we present a compression method which reduces the memoryspace required for plant architecture storage. A more compact data structure is used in order torepresent plant architecture. The construction of this data structure require the identification ofinternal redundancies and taking into account both topological and geometrical informations.

Nesta tese estudamos dois problemas em digrafos: um problema de empacotamento e um problema de contagem. Estudamos o problema de empacotamento máximo de arborescências no digrafo aleatório D(n,p), onde cada possvel arco é inserido aleatoriamente ao acaso com probabilidade p = p(n). Denote por (D(n,p)) o maior inteiro possvel 0 tal que, para todo 0 l , temos ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}| Provamos que a quantidade máxima de arborescências em D(n,p) é (D(n,p)) assintoticamente quase certamente. Nós também mostramos estimativas justas para (D(n, p)) para todo p [0, 1]. As principais ferramentas que utilizamos são relacionadas a propriedades de expansão do D(n, p), o comportamento do grau de entrada do digrafo aleatório e um resultado clássico de Frank que serve como ligação entre subpartições em digrafos e a quantidade de arborescências. Para o problema de contagem, estudamos a densidade de subtorneios fortemente conexos com 5 vértices em torneios grandes. Determinamos a densidade assintótica máxima para 5 torneios bem como as famlias assintóticas extremais de cada torneios. Como subproduto deste trabalho caracterizamos torneios que são blow-ups recursivos de um circuito orientado com 3 vértices como torneios que probem torneios especficos de tamanho 5. Como principal ferramenta para esse problema utilizados a teoria de álgebra de flags e configurações combinatórias obtidas através do método semidefinido. / In this thesis we study two problems dealing with digraphs: a packing problem and a counting problem. We study the problem of packing the maximum number of arborescences in the random digraph D(n,p), where each possible arc is included uniformly at random with probability p = p(n). Let (D(n,p)) denote the largest integer 0 such that, for all 0 l , we have ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}|. We show that the maximum number of arc-disjoint arborescences in D(n, p) is (D(n, p)) asymptotically almost surely. We also give tight estimates for (D(n, p)) for every p [0, 1]. The main tools that we used were expansion properties of random digraphs, the behavior of in-degree of random digraphs and a classic result by Frank relating subpartitions and number of arborescences. For the counting problem, we study the density of fixed strongly connected subtournaments on 5 vertices in large tournaments. We determine the maximum density asymptotically for five tournaments as well as unique extremal sequences for each tournament. As a byproduct of this study we also characterize tournaments that are recursive blow-ups of a 3-cycle as tournaments that avoid three specific tournaments of size 5. We use the theory of flag algebras as a main tool for this problem and combinatorial settings obtained from semidefinite method.

Les moteurs traditionnels offrent à l'utilisateur des résultats de plus en plus pertinents, mais, dans la plupart des cas, les résultats similaires ont tendance à se regrouper. L'utilisateur peut être intéressé pour retrouver des documents qui soient certes tous pertinents par rapport à sa requête, mais aussi qui soient différents les uns des autres. Dans cette thèse, nous considérons le problème de la diversité pour la recherche d'images. Nous avons focalisé notre attention sur la diversité par l'exploitation du clustering, plus spécialement par une approche hiérarchique (AHC), car sa hiérarchie de clusters peut bien correspondre à la nature hiérarchique de la diversité. De plus, nous proposons une nouvelle approche pour exploiter des ressources plus riches, telle qu'une « arborescence de concepts », pour augmenter la diversité. Différentes approches sont comparées sur trois benchmarks : un qui a été annoté manuellement et qui possède une haute pertinence; et deux publics assez différents et plus généraux. Les résultats montrent que l'exploitation hiérarchique des résultats de l'AHC augmente la diversité en comparaison avec des méthodes de clustering plat standard et avec une méthode de diversité par optimisation. Les résultats montrent aussi l'intérêt d'utiliser une arborescence de concepts comme descripteur pour augmenter la diversité. Enfin, nous avons développé un prototype complet avec la prise en compte des contraintes fortes de temps de calcul ce qui le rend adapté pour être utilisable dans le moteur de recherche de l'entreprise. / Conventional search engines return relevant results but often the retrieved items are similar. Moreover, the similar results tend to appear together. The user may be interested to find documents that are relevant and diverse at the same time.In this thesis, we consider the problem of the diversity in image retrieval. We have focused our attention on diversity by clustering, especially in an approach based on an agglomerative hierarchical clustering (AHC) to address the hierarchical nature of the diversity. Furthermore, we propose a novel approach for exploiting richer description resources, such as a «tree of concepts», to increase the diversity.The different approaches are compared on a highly relevant and manually annotated benchmark: the XiloDiv benchmark; and on the most general: ImageClef2008 and MediaEval2013 benchmarks. The experimental results show that a hierarchical exploitation of the results of the AHC increases the diversity in comparison with two flat clustering methods and a method of diversity by optimization. The results also show that it is better to use concept features than visual features from a diversity point of view. In addition, on the Mediaeval2013 benchmark, we show that an interesting strategy to improve diversity is to increase the relevance using the text, and then to exploit visual based clustering to diversify the results.Finally, we developed a complete prototype in particular taking into account the strong constraints of response time which makes it suitable to be used in the company's search engine.

Cette thèse présente le sous-système ISIS, une méthode d'expression et de contrôle de l'intégrité sémantique, dans les bases de données relationnelles. Celle-ci est réglée par un ensemble de lois appelées contraintes d'intégrité sémantique (CIS). Une réalisation est effectuée dans le cadre du projet MICROBE