Search

National audience; Le Dictionnaire Électronique des synonymes (DES) du laboratoire CRISCO de l'Université de Caen est connu principalement par son interface web simple interrogée de 150.000 à 200.000 fois par jour. Il est également accompagné d'un certain nombre d'autres outils informatiques qui explorent pleinement et sous d'autres angles de vue les données stockées. Nous nous proposons dans cette courte présentation de les passer en revue.

The objective of this thesis is to perform schedulability analysis of probabilistic real-time systems. The task execution is described using a probabilistic Worst Case Execution Time (pWCET) which is a probability distribution. The pWCETs are assumed given. The tasks are scheduled to ensure that all tasks are allowed a processor time. In order to ensure that all tasks are scheduled, schedulability analysis is performed. Because task execution is described probabilistically, the schedulability analysis must also be probabilistic. This implies a probabilistic modelling of the system to probabilistically ensure that all tasks are scheduled.Assuming continuous pWCET distribution, a formal approach towards the probabilistic analysis of the system through Continuous Time Markov Chain (CTMCh) uses CTMCh to model jobs of the tasks which are scheduled using Earliest Deadline First or Fixed Priority scheduling algorithm. Differences between continuous and discrete pWCET distributions are highlighted with the advantages and disadvantages of each.Searching for reducing pessimism through real-time systems by using a Discrete Time Markov Chain (DTMCh) model for a Mixed Criticality (MC) probabilistic Real-Time System (pRTS) allows to quantify the probability of the system entering high criticality. Moreover that pessimism can be further reduced in a probabilistic environment by letting go of the classical schedulability algorithms.A schedule which is safe and ensures schedulability of high criticality jobs is obtained using the graph based exploratory model for MC pRTS developed in this thesis. At the same time, the low criticality jobs are scheduled whenever possible. This approach drops the classical idea of suspending all low criticality jobs when a high criticality job enters high criticality mode. Here, probabilities can only be quantified because they arrive from pWCET and pWCET does not depend on the schedule.Tasks enter high criticality at runtime implying that response time, and not execution time, must be used to decide criticality modes. Since the response time is affected by the schedule, this schedule can be optimized with respect to a probability criterion. Usability and hidden assumptions are presented for the classical convolution operation between pWCET distributions in the context of real-time systems. It leads to a MC schedule with minimal probability of system entering high criticality. At the same time, if the system does enter high criticality, the schedulability of high criticality jobs is ensured with allowing low criticality jobs to execute. The schedule is also adaptive, which means that depending on the when and which job enters high criticality, the following schedule is decided accordingly. The schedule is ensured in the worst case. A first step towards dependence between the tasks which is apart from the scheduling is also presented., L'objectif de cette thèse est d'effectuer une analyse d'ordonnancement des systèmes temps réel probabilistes. L'exécution de la tâche est décrit par un probabilistic Worst Case Execution Time (pWCET) qui est une distribution probabiliste de temp d'exécution de la tâche. Les pWCET sont supposé donné. Les tâches sont planifiées avec une ordonnance pour garantir que toutes les tâches disposent d'un temps processeur. Afin de garantir l'exécution de tous les tâches planifiées, une analyse de l'ordonnancement est effectuée. Étant donné que l'exécution des tâches est décrite de manière probabiliste, le l'analyse de l'ordonnancement doit également être probabiliste. Cela implique une modélisation probabiliste du système de manière probabiliste nous assure que toutes les tâches exécutant.En supposant une distribution continue de pWCET, une approche formelle vers l'analyse probabiliste du système à travers la Chaîne de Markov temps continu (CTMCh) pour modéliser les occurrences (jobs) des tâches planifiées à l'aide d'une algorithme de ordonnance à Earliest Deadline First ou à Fixed Priority. Différences entre les distributions pWCET continues et discrètes sont mis en évidence avec les avantages et les inconvénients de chacun. Recherche de réduction du pessimisme des systèmes temps réel, en utilisant un modèle de Chaîne de Markov temps discret (DTMCh) pour un système temps réel probabiliste (pRTS) à criticité mixte (MC) permet de quantifier la probabilité d'entrée du système à haute criticité. De plus, ce pessimisme peut être encore réduit dans un environnement probabiliste en abandonnant le classique algorithmes d'ordonnançabilité.Un ordonnance sûr et garantissant l'ordonnancement des jobs à haute criticité est obtenu à l'aide de l'explorateur basé sur les modèles graphe pour MC pRTS développé dans cette thèse. En même temps, les travaux à faible criticité sont planifiés chaque fois que possible. Cette approche abandonne l'idée classique de suspendre tous les jobs à faible criticité lorsqu'un job à criticité élevée entre dans une mode de criticité élevée. Ici, les probabilités peuvent être quantifiées mais ils ne sont pas affectés parce qu'elles proviennent de pWCET et pWCET ne dépend pas sur l'ordonnance.Les tâches change vers une mode criticité élevée lors de l'exécution, ce qui implique que le temps de réponse, et pas le temps d'exécution, doit être utilisé pour décider modes de criticité. Le temps de réponse étant affecté par le planning, ce ordonnance peut être optimisé par rapport à un critère de probabilité. L'utilisabilité et les hypothèses cachées sont présentées pour l'opération de convolution classique entre distributions de pWCET dans le contexte de systèmes en temps réel. Cela conduit à un programme MC avec une probabilité minimale de système entrant dans une criticité élevée. En même temps, si le système atteint une criticité élevée, l'ordonnancement des jobs à criticité élevée est assurée en permettant l'exécution de jobs à faible criticité. L'ordonnance est également adaptatif, ce qui signifie qu'en fonction de la quand et quel job entre vers criticité élevée, l'ordonnance est décidé en conséquence. L'ordonnance est assuré dans le pire cas. Une première étape vers la dépendance entre les tâches en dehors de l'ordonnancement est également présentée.

This thesis is a study, from an algorithmic point of view, of the complexity of solving some enumeration problems in graphs. Algorithms for enumeration problems are meant to produce all solutions of a combinatorial problem, without repetition. Because there is a potentially exponential number of solutions to be generated, different approaches to analyse the performance of those algorithms have been developed: the input-sensitive approach and the output-sensitive approach. The first is a measure of the complexity that is based on the size of the input, and which consists in analysing the total time needed to enumerate the objects. The second is a measure based on the size of the input and the output. Here we will be interested in an output-sensitive approach and we will pay special attention to the notion of delay, i.e., the time needed between the production of two consecutive solutions. The thesis is divided into two independent parts. In the first one we propose a general framework that allows for the study of enumeration of vertex set properties in graphs. We prove that when such a property is locally definable with respect to some order on the set of vertices, then it can be enumerated with linear delay. Our method is a reduction of the considered enumeration problem to the enumeration of paths in directed acyclic graphs. We apply this general method to enumerate with linear delay minimal connected dominating sets and maximal irredundant sets in interval graphs and in permutation graphs, as well as maximal irredundant sets in circular-arc graphs and in circular-permutation graphs. The second part of the thesis is dedicated to the study of k-arc-connected orientations. These are orientations for which at least k arcs have to be removed in order to destroy the strong connectivity. We first give a simple algorithm to enumerate the k-arc-connected orientations respecting some fix outdegree sequence. We then give a simple algorithm to enumerate the outdegree sequences attained by k-arc-connected orientations. Combining both yields an algorithm that enumerates all k-arc-connected orientations of a graph in delay O(knm²) and amortized time O(m²)., Cette thèse est une étude, d’un point de vue algorithmique, de la complexité de la résolution de certains problèmes d’énumération dans les graphes. Les algorithmes pour les problèmes d’énumération ont pour but la production de toutes les solutions d’un problème combinatoire, et ce sans répétition. Comme il existe un nombre potentiellement exponentiel de solutions à générer, différentes approches pour analyser la performance de ces algorithmes ont été développées: l’approche "input-sensitive" et l’approche "output-sensitive". La première est une mesure de la complexité basée sur la taille de l’entrée, elle consiste en l’analyse du temps total nécessaire à l’énumération des objets. La seconde est une mesure basée sur la taille de l’entrée et de la sortie. Nous nous intéresserons ici à l’approche output-sensitive et nous accorderons une attention particulière à la notion de délai, i.e., le temps nécessaire entre la production de deux solutions consécutives. La thèse est divisée en deux parties indépendantes. Dans la première, nous proposons un cadre général qui permet d’étudier l’énumération d’ensembles de sommets d’un graphe respectant une certaine propriété. Nous prouvons que lorsqu’une telle propriété peut être définie localement par rapport à un certain ordre sur l’ensemble des sommets du graphe, alors les ensembles de sommets respectant cette propriété peuvent être énumérés avec un délai linéaire. Notre méthode consiste à réduire le problème d’énumération considéré à l’énumération de chemins dans les graphes acycliques dirigés. Nous appliquons cette méthode générale pour énumérer avec un délai linéaire les ensembles dominants connexes minimaux et les ensembles irredondants maximaux dans les graphes d’intervalles et dans les graphes de permutation, ainsi que les ensembles irredondants maximaux dans les graphes arc-circulaires et dans les graphes permutation-circulaires. La deuxième partie de la thèse est consacrée à l’étude des orientations k-arc-connexes. Il s’agit d’orientations pour lesquelles il est nécessaire de supprimer au moins k arcs pour détruire la forte connexité. Nous présentons d’abord un algorithme simple pour énumérer les orientations k-arc-connexes respectant une séquence de degrés sortants. Ensuite nous présentons un algorithme simple pour énumérer les séquences de degrés sortants pour lesquelles il existe une orientation k-arc-connexe. En combinant ces deux algorithmes, nous obtenons un algorithme qui énumère toutes les orientations k-arc-connexes d’un graphe avec un délai de O(knm²) et un temps amorti de O(m²).

This thesis is a study, from an algorithmic point of view, of the complexity of solving some enumeration problems in graphs. Algorithms for enumeration problems are meant to produce all solutions of a combinatorial problem, without repetition. Because there is a potentially exponential number of solutions to be generated, different approaches to analyse the performance of those algorithms have been developed: the input-sensitive approach and the output-sensitive approach. The first is a measure of the complexity that is based on the size of the input, and which consists in analysing the total time needed to enumerate the objects. The second is a measure based on the size of the input and the output. Here we will be interested in an output-sensitive approach and we will pay special attention to the notion of delay, i.e., the time needed between the production of two consecutive solutions. The thesis is divided into two independent parts. In the first one we propose a general framework that allows for the study of enumeration of vertex set properties in graphs. We prove that when such a property is locally definable with respect to some order on the set of vertices, then it can be enumerated with linear delay. Our method is a reduction of the considered enumeration problem to the enumeration of paths in directed acyclic graphs. We apply this general method to enumerate with linear delay minimal connected dominating sets and maximal irredundant sets in interval graphs and in permutation graphs, as well as maximal irredundant sets in circular-arc graphs and in circular-permutation graphs. The second part of the thesis is dedicated to the study of k-arc-connected orientations. These are orientations for which at least k arcs have to be removed in order to destroy the strong connectivity. We first give a simple algorithm to enumerate the k-arc-connected orientations respecting some fix outdegree sequence. We then give a simple algorithm to enumerate the outdegree sequences attained by k-arc-connected orientations. Combining both yields an algorithm that enumerates all k-arc-connected orientations of a graph in delay O(knm²) and amortized time O(m²)., Cette thèse est une étude, d’un point de vue algorithmique, de la complexité de la résolution de certains problèmes d’énumération dans les graphes. Les algorithmes pour les problèmes d’énumération ont pour but la production de toutes les solutions d’un problème combinatoire, et ce sans répétition. Comme il existe un nombre potentiellement exponentiel de solutions à générer, différentes approches pour analyser la performance de ces algorithmes ont été développées: l’approche "input-sensitive" et l’approche "output-sensitive". La première est une mesure de la complexité basée sur la taille de l’entrée, elle consiste en l’analyse du temps total nécessaire à l’énumération des objets. La seconde est une mesure basée sur la taille de l’entrée et de la sortie. Nous nous intéresserons ici à l’approche output-sensitive et nous accorderons une attention particulière à la notion de délai, i.e., le temps nécessaire entre la production de deux solutions consécutives. La thèse est divisée en deux parties indépendantes. Dans la première, nous proposons un cadre général qui permet d’étudier l’énumération d’ensembles de sommets d’un graphe respectant une certaine propriété. Nous prouvons que lorsqu’une telle propriété peut être définie localement par rapport à un certain ordre sur l’ensemble des sommets du graphe, alors les ensembles de sommets respectant cette propriété peuvent être énumérés avec un délai linéaire. Notre méthode consiste à réduire le problème d’énumération considéré à l’énumération de chemins dans les graphes acycliques dirigés. Nous appliquons cette méthode générale pour énumérer avec un délai linéaire les ensembles dominants connexes minimaux et les ensembles irredondants maximaux dans les graphes d’intervalles et dans les graphes de permutation, ainsi que les ensembles irredondants maximaux dans les graphes arc-circulaires et dans les graphes permutation-circulaires. La deuxième partie de la thèse est consacrée à l’étude des orientations k-arc-connexes. Il s’agit d’orientations pour lesquelles il est nécessaire de supprimer au moins k arcs pour détruire la forte connexité. Nous présentons d’abord un algorithme simple pour énumérer les orientations k-arc-connexes respectant une séquence de degrés sortants. Ensuite nous présentons un algorithme simple pour énumérer les séquences de degrés sortants pour lesquelles il existe une orientation k-arc-connexe. En combinant ces deux algorithmes, nous obtenons un algorithme qui énumère toutes les orientations k-arc-connexes d’un graphe avec un délai de O(knm²) et un temps amorti de O(m²).

This work was (partially) funded by the ANR grant BLIZAAR ANR-15-CE23-0002-01 and the FNR grant BLIZAAR INTER/ANR/14/9909176.; International audience; Ce poster explique comment utiliser l'eDOI, une métrique d'estimation de l'intérêt, afin de procéder à une navigation via des vues partielles successives dans les réseaux multicouches.

National audience; Présentation pour l'atelier VIF d'EGC 2017 (Atelier Visualisation d'informations, interaction et fouille de données). Il s'agit de la mise en forme d'une version exploratoire de l'algorithme "Degree of Interest" adaptable aux graphes dynamiques et multicouches.

Les simulations numériques de grande taille nécessitent d'être effectuées en parallèle. L'équilibre de la charge entre les nœuds de calcul est alors primordial. Dans le cas de simulations multi-physiques, on modélise le problème d'équilibrage de charge par celui du partitionnement multi-critères de graphes, problème NP-Difficile pour lequel les outils existants reposent sur des heuristiques largement améliorables. Nous présentons ici une méthode de partitionnement multi-critères de graphe utilisant un schéma multi-niveaux adapté. Notamment, nous proposons un nouvel algorithme de partitionnement initial et nous démarquons de l'existant concernant la phase de raffinement, conçue pour respecter strictement les tolérances d'équilibre. En mono-critère, notre méthode est compétitive par rapport à des logiciels de référence comme Scotch et MeTiS. En multi-critères, contrairement à MeTiS, notre méthode retourne dans tous les cas des solutions valides par rapport aux tolérances prescrites.

In this thesis, we deal with risk prevention and crisis management requiring evacuation. Road network structure and mobility process are studied by using swarmintelligencemethods. Risk prevention is treated by analyzing the vulnerability of the network represented by a multigraph, at different scale levels thanks to betweenness centrality and hierarchical clustering methods. Crisis management during an evacuation is also treated. A microscopic traffic model is developed and a micro-evacuation simulator is proposed to organize an evacuation, beginning from crisis occurrence until vehicles evacuation, taking into account dangerous areas enclosing and itineraries choice strategies to evacuate those areas. Our model is adaptive, it takes into consideration multigraph structure and its elements vulnerability at different scale levels, and unexpected events during an evacuation., Le travail présenté dans cette thèse a pour cadre la prévention des risques et la gestion de crises nécessitant une évacuation. La structure du réseau viaire est étudiée mais également les processus de mobilité qui s'y développent. Nous utilisons en particulier des techniques d'intelligence en essaim pour étudier la morphodynamique du réseau. La prévention des risques est considérée en analysant la vulnérabilité du réseau représenté par un multigraphe. Sa structure est étudiée à différents niveaux d'échelle, par des méthodes de calcul de la centralité d'intermédiarité et de clustering hiérarchique. La gestion de crise lors d'une évacuation a aussi été traitée et a conduit à l'étude de la dynamique des déplacements au sein du réseau routier et à un traitement et une analyse multi-échelle. Nous avons développé un modèle microscopique de trafic ainsi qu'un modèle de microévacuation permettant d'organiser une évacuation depuis l'occurrence de la crise jusqu'à l'évacuation des véhicules en passant par la délimitation d'éventuelles zones en danger et par les stratégies de choix d'itinéraires afin de les évacuer. Le modèle est adaptatif, il prend en compte la structure du multigraphe, la vulnérabilité des éléments à différents niveaux d'échelle, les événements inattendus lors d'une évacuation et permet d'amener des éléments de réponse aux décideurs gérant le risque.

In pattern recognition, the coding of information extracted from the data is a decisive phase, and the use of structures seems to be the most pertinent choice. However, the coding in the form of numeric feature vectors offers the advantage of enabling, in the sequel, the use of numerous efficient algorithms specifically developed for the classification of numeric vectors in fields connected to pattern recognition. From this observation was born a research field devoted to the statistical characterization of structure spaces. At the same time have been developed a set of works based on a transformation of structures into numeric vectors. Finally, probabilities are a widely used paradigm for the classification of structured data, via the modelling of distributions of structures and a massive use of the maximum likelihood classifier. In this thesis, we propose the translation to structure spaces of criteria enabling to define the statistical notions of uniformity and normality of probability laws. We propose as well a reflection on the definition of structural random variables taking their values in a vector space, having in prospect the possibility of applying, in the structural domain, the central limit theorem, a fundamentally important result in probability theory and statistics. From an applicative point of view, we evaluate the contribution of a part of our work for the resolution of typical problems in pattern recognition, namely the classification of DNA sequences and the classification of images of handwritten digits., En reconnaissance de formes, le codage de l'information extraite des données est une étape décisive, et l'utilisation de structures semble être le choix le plus pertinent. Cependant, le codage sous forme de vecteurs de caractéristiques numériques offre l'avantage de permettre l'utilisation de nombreux algorithmes efficaces développés spécifiquement pour la classification de vecteurs numériques dans des disciplines connexes à la reconnaissance de formes. De ce constat est né un champs de recherche dédié à la caractérisation statistique des espaces de structures. Parallèlement, ont vu le jour un ensemble des travaux basés sur une transformation des structures sous forme de vecteurs numériques. Enfin, les probabilités sont un paradigme largement utilisé pour la classification de données structurées, via la modélisation de distribution de structures et l'utilisation massive du classifieur par maximisation de vraisemblance. Dans cette thèse, nous proposons la traduction aux espaces structurels de critères permettant de définir les notions statistiques d'uniformité et de normalité de lois de probabilités. Nous proposons également une réflexion sur la définition de variables aléatoires de structures à valeur dans un espace vectoriel, avec pour perspective la possibilité d'application, dans le domaine structurel, du théorème central limite, résultat d'importance fondamentale en théorie des probabilités et statistique. D'un point de vue applicatif, nous évaluons les apports d'une partie de nos travaux pour la résolution de problèmes typiques en reconnaissance de formes, à savoir la classification de séquences d'ADN et la classification d'images de chiffres dessinés à la main.

Many applications such as e.g., information retrieval and classification, involve measuring graph distance or similarity, i.e., matching graphs to identify and quantify their common features. Different kinds of graph matchings have been proposed, giving rise to different graph similarity or distance measures. Exact graph matchings such as graph or subgraph isomorphism can be used in order to show graph equivalence or inclusion. However, in many applications, the assumption of the existence of such an "exact" matching is too strong. As a consequence, error-tolerant graph matchings such as maximum common subgraph and graph edit distance have been proposed. Such matchings drop the condition that the matching must preserve all vertices and edges and look for a "best" matching, i.e., one which preserves a maximum number of vertices and edges. Most recently, three different approaches proposed to go one step further by introducing multivalent matchings where a vertex may be matched with a set of vertices. This kind of matching handles the fact that, due to different description granularity levels, one object component may "play the same role" than a set of components of another object. Un first goal of this work is to define a new graph distance based on the search of a best matching between the graph vertices, i.e., a matching that minimizes vertex and edge distance functions. This distance is generic in the sense that it allows both univalent and multivalent matchings and it is parameterized by vertex and edge distance functions defined by the user depending on the considered application. We show how to use this graph distance generic framework to model existing graph distance or similarity measure. A second goal of this work is to propose an algorithm to compute this generic graph distance. We propose a reactive tabu local search ables to solve many different graph matching problems and give some experimental results. We then focus our attention on solving the graph isomorphism problem with constraint programming. We propose a global constraint dedicated to this problem, a partial consistency for this constraint and an algorithm to establish this consistency. We show that using this consistency makes the constraint programming competitive with algorithms dedicated to this problem., De nombreuses applications, comme par exemple la recherche ou la classification d'informations, nécessitent de mesurer la distance ou la similarité entre deux graphes, i.e., apparier --mettre en correspondance-- les sommets des graphes afin d'identifier leurs points communs et leurs différences. Il existe différents types d'appariements de graphes donnant chacun lieu à une définition différente de la distance entre deux graphes. Les appariements exacts (isomorphisme de graphes ou de sous-graphe) permettent de montrer que deux graphes sont identiques ou qu'un graphe est inclus dans un autre graphe. Cependant, dans de nombreuses applications, supposer l'existence d'un tel appariement est une hypothèse trop forte. Par conséquent, des appariements de graphes à tolérance d'erreurs tels que la recherche du plus grand sous-graphe commun à deux graphes ou la distance d'édition de graphes ont été proposés. L'appariement recherché est alors un "meilleur" appariement, i.e., un appariement devant préserver le plus grand nombre de sommets et d'arcs des graphes sans pour autant nécessairement tous les préserver. Plus récemment, trois différentes approches ont proposé d'aller un cran plus loin en introduisant la notion d'appariement multivoque où le sommet d'un graphe peut être apparié à un ensemble de sommets de l'autre graphe. Ce type d'appariement permet de prendre en compte le fait que le composant d'un objet modélisé par un graphe peut "jouer le même rôle" que plusieurs composants d'un autre objet modélisé par un autre graphe. Un premier objectif de cette thèse est de définir une nouvelle distance de graphe basée sur la recherche d'un meilleur appariement entre les sommets de deux graphes, i.e., un appariement qui minimise des fonctions de distance de sommets et d'arcs. Cette distance de graphe est générique dans le sens où elle permet des appariements univoques ou multivoques et où elle est paramétrable en fonction de l'application considérée. Nous montrons comment utiliser ce cadre générique de définition de la distance entre deux graphes pour modéliser les mesures de distance ou de similarité de graphes existantes. Un second objectif de cette thèse est de proposer une solution algorithmique permettant le calcul de notre mesure générique de la distance de deux graphes. Nous proposons et expérimentons un algorithme de recherche locale taboue capable de résoudre de nombreux problèmes différents d'appariement de graphes. Nous nous intéressons ensuite plus spécifiquement à la résolution du problème de l'isomorphisme de deux graphes à l'aide de la programmation par contraintes. Nous proposons une contrainte globale dédiée à ce problème, une consistance partielle pour cette contrainte et l'algorithme permettant de l'établir. Nous montrons alors que l'utilisation de cette contrainte globale permet à la programmation par contraintes de devenir compétitive avec des approches dédiées à ce problème.

Pathwidth and treewidth have been introduced by Robertson and Seymour in their work on graph minors. Informally, pathwidth (resp. treewidth) measures the "distance" between a given graph and the class of paths (resp. trees). Given an arbitrary graph G=(V,E), an interval graph H=(V,F) containing G is called an interval completion of G. Computing pathwidth comes to computing an interval completion of minimum cliquesize of the input graph. Unfortunately the pathwidth problem is NP-hard. We focus on minimal interval completions of G, that is interval completions H such that no proper subgraph of H is an interval completion of G. We give several algorithms for computing minimal interval completions of an input graph, an also an algorithm computing a minimal proper interval completion. Eventually, we show that pathwidth can be polinomially computed for circular-arc graphs., La largeur linéaire et la largeur arborescente ont été introduites par Robertson et Seymour dans leurs travaux sur les mineurs de graphes. De manière informelle, la largeur linéaire (resp. la largeur arborescente) d'un graphe mesure l'écart entre ce graphe et la classe des chaînes (des arbres). Les deux paramètres se sont révélés très puissants de point de vue algorithmique, car de nombreux problèmes NP-difficiles deviennent polynomiaux lorsque l'on se restreint à des classes de graphes de largeur linéaire ou de largeur arborescente bornée. Etant donné un graphe G=(V,E) quelconque, un graphe d'intervalles H=(V,F) contenant G est appelé complétion d'intervalles de G. Calculer la largeur linéaire de G revient à trouver une complétion d'intervalles H, tout en minimisant la clique maximum de H. Le problème étant NP-difficile, nous calculerons des complétions d'intervalles minimales, où l'on demande seulement que l'ensemble d'arêtes rajoutées F\E soit minimal par inclusion parmi toutes les complétions possibles. Une approche similaire, à travers les triangulations minimales, est fortement utilisée pour comprendre et calculer la largeur arborescente. Ce mémoire présente nos résultats sur les complétions d'intervalles minimales. Nous donnons trois algorithmes calculant une complétion d'intervalles minimale, basés sur des approches différentes. Nous présentons également un algorithme calculant une complétion d'intervalles propres minimale. Enfin, nous montrons que la largeur linéaire des graphes d'intervalles circulaires peut être calculée en temps polynomial.

The identification of the interactions occurring at the molecular level is crucial to understand the life process. The aim of this work was to develop methods to model and to predict these interactions for the metabolism and the regulation of transcription. We modeled these systems by graphs and automata.Firstly, we developed a method to test and to predict the flux distribution in a metabolic network, which consider the formulation of several constraints. We showed that this method can better mimic the in vivo phenotype of the energy metabolism of the parasite Trypanosoma brucei. The results enabled to provide a good explanation of the metabolic flux flexibility, which were consistent with the experimental data. Secondly, we have considered a particular class of non-coding RNAs called sRNAs, which are involved in the regulation of the cellular response to environmental changes. We developed an approach to better predict their interactions with other RNAs based on the interaction prediction, an enrichment analysis, and by developing a visualization system adapted to the manipulation of these data. We applied our method to the study of the sRNAs interactions within the bacteria Escherichia coli. The predictions were in agreement with the available experimental data, and helped to propose several new target candidates., L'identification des interactions survenant au niveau moléculaire joue un rôle crucial pour la compréhension du vivant. L'objectif de ce travail a consisté à développer des méthodes permettant de modéliser et de prédire ces interactions pour le métabolisme et la régulation de la transcription. Nous nous sommes basés pour cela sur la modélisation de ces systèmes sous la forme de graphes et d'automates. Nous avons dans un premier temps développé une méthode permettant de tester et de prédire la distribution du flux au sein d'un réseau métabolique en permettant la formulation d'une à plusieurs contraintes. Nous montrons que la prise en compte des données biologiques par cette méthode permet de mieux reproduire certains phénotypes observés in vivo pour notre modèle d'étude du métabolisme énergétique du parasite Trypanosoma brucei. Les résultats obtenus ont ainsi permis de fournir des éléments d'explication pour comprendre la flexibilité du flux de ce métabolisme, qui étaient cohérentes avec les données expérimentales. Dans un second temps, nous nous sommes intéressés à une catégorie particulière d'ARN non codants appelés sRNAs, qui sont impliqués dans la régulation de la réponse cellulaire aux variations environnementales. Nous avons développé une approche permettant de mieux prédire les interactions qu'ils effectuent avec d'autres ARN en nous basant sur une prédiction des interactions, une analyse par enrichissement du contexte biologique de ces cibles, et en développant un système de visualisation spécialement adapté à la manipulation de ces données. Nous avons appliqué notre méthode pour l'étude des sRNAs de la bactérie Escherichia coli. Les prédictions réalisées sont apparues être en accord avec les données expérimentales disponibles, et ont permis de proposer plusieurs nouvelles cibles candidates.