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

Cette thèse traite de l'étude des spanneurs multichemins, comme extension des spanneurs de graphes classiques. Un spanneur H d'un graphe G est un sous-graphe couvrant tel que pour toute paire de sommets du graphe a,b « appartient à » V(G) la distance dans le spanneur dh(a,b) n'est pas trop étirée par rapport à la distance dans le graphe d'origine dg(a,b). Ainsi il existe un facteur d'étirement (alpha, beta) tel que pour tout a,b« appartient à »V(G), dh(a,b)« est inférieur ou égal à » alpha dg(a,b)+beta. Motivés par des considérations de routage à plusieurs chemins et après la remarque que le concept de spanneur peut être étendu à toute métrique « non décroissante », nous introduisons la notion de spanneur multichemins. Après une introduction au domaine, nous parlerons des résultats obtenus concernant d'une part les spanneurs multichemins arêtes disjoints et d'autre part les spanneurs multichemins sommets disjoints. / This thesis deals with multipath spanners, as an extension of classical graph spanners. A spanner H of a graph G is a spanning subgraph such that for any pair of vertices a,b « is an element of » V(G) the distance measured in the spanner dh(a,b) isn't too much stretched compared to the distance measured in the original graph dg(a,b). As such there exists a stretch factor (alpha, beta) such that for all a,b« is an element of »V(G), dh(a,b)«is less than or equal to » alpha dg(a,b)+beta. Motivated by multipath routing and after noting that the concept of spanner can be extended to any “non decreasing” metric, we introduce the notion of multipath spanner. After an introduction to the topic, we will show the results obtained. The first part is devoted to edge-disjoint multipath spanners. The second part id devoted to vertex-disjoint spanners.

Des millions de réactions chimiques sont décrites dans des bases de données sous la forme de transformations de graphes moléculaires. Cette thèse propose différentes méthodes de fouille de donnés pour extraire des motifs pertinents contenus dans ces graphes et ainsi aider les chimistes à améliorer leurs connaissances des réactions chimiques et des molécules. Ainsi on commence par montrer comment le problème central de la recherche des schémas de réactions fréquents peut se résoudre à l'aide de méthodes existantes de recherche de sous-graphes fréquents. L'introduction du modèle général des motifs les plus informatifs permet ensuite de restreindre l'analyse de ces motifs fréquents à un nombre réduit de motifs peu redondants et représentatifs des données. Si l'application du modèle aux bases de réactions permet d'identifier de grandes familles de réactions, le modèle est inadapté pour extraire les schémas caractéristiques de méthodes de synthèse (schémas CMS) dont la fréquence est trop faible. Afin de surmonter cet obstacle, est ensuite introduite une méthode de recherche heuristique fondée sur une contrainte d’intervalle entre graphes et adaptée à l’extraction de motifs de très faible fréquence. Cette méthode permet ainsi de déterminer à partir d'exemples de réactions et sous certaines conditions le schéma CMS sous-jacent à une réaction donnée. La même approche est ensuite utilisée pour traiter le problème de la classification supervisée de sommets ou d'arêtes fondée sur leurs environnements puis exploitée pour évaluer la formabilité des liaisons d'une molécule. Les résultats produits ont pu être analysés par des experts de la synthèse organique et sont très encourageants. / Millions of chemical reactions are described in databases as transformations of molecular graphs. This thesis proposes different data-mining methods to extract relevant patterns included in those graphs and therefore to help chemists in improving knowledge about chemical reactions and molecules. One first shows how the central problem of searching frequent reaction patterns can be solved using existing graph-mining methods. Introducing the general model of most informative patterns then allows experts to reduce the analysis of these frequent patterns to a very small set of non-redundant patterns characteristic of data. If the application of this model to reaction database identifies large and characteristic families of reactions, the model doesn't allow in practice the extraction of reaction patterns characteristic of synthesis methods (abbr. CSM patterns) as their frequencies are far too low. In order to overcome this problem, is introduced a heuristic search algorithm based on a graph interval constraint and able to extract patterns with very low frequency. Thus this method determines from examples of chemical reactions and under some conditions the CSM pattern underlying a given input reaction. The same approach is then used to address the problem of supervised classification of vertices or edges based on their environment and then applied to evaluate formability of bonds in molecules. Experimental results have been analyzed by experts and are very encouraging.

L'interrogation de graphes de données est un problème fondamental qui connait un grand intérêt, en particulier pour les données structurées massives où les graphes constituent une alternative prometteuse aux bases de données relationnelles pour la modélisation des grandes masses de données. Cependant, l'interrogation des graphes de données est différente et plus complexe que l'interrogation des données relationnelles à base de tables. La tâche principale impliquée dans l'interrogation de graphes de données est la recherche d'isomorphisme de sous-graphes qui est un problème NP-complet.La recherche d'isomorphisme de sous-graphes est un problème très important impliqué dans divers domaines comme la reconnaissance de formes, l'analyse des réseaux sociaux, la biologie, etc. Il consiste à énumérer les sous-graphes d'un graphe de données qui correspondent à un graphe requête. Les solutions les plus connues de ce problème sont basées sur le retour arrière (backtracking). Elles explorent un grand espace de recherche, ce qui entraîne un coût de traitement élevé, notamment dans le cas de données massives.Pour réduire le temps et la complexité en espace mémoire dans la recherche d'isomorphisme de sous-graphes, nous proposons d'utiliser des graphes compressés. Dans notre approche, la recherche d'isomorphisme de sous-graphes est réalisée sur une représentation compressée des graphes sans les décompresser. La compression des graphes s'effectue en regroupant les sommets en super-sommets. Ce concept est connu dans la théorie des graphes par la décomposition modulaire. Il sert à générer une représentation en arbre d'un graphe qui met en évidence des groupes de sommets qui ont les mêmes voisins. Avec cette compression, nous obtenons une réduction substantielle de l'espace de recherche et par conséquent, une économie significative dans le temps de traitement.Nous proposons également une nouvelle représentation des sommets du graphe, qui simplifie le filtrage de l'espace de recherche. Ce nouveau mécanisme appelé compact neighborhood Index (CNI) encode l'information de voisinage autour d'un sommet en un seul entier. Cet encodage du voisinage réduit la complexité du temps de filtrage de cubique à quadratique. Ce qui est considérable pour les données massifs.Nous proposons également un algorithme de filtrage itératif qui repose sur les caractéristiques des CNIs pour assurer un élagage global de l'espace de recherche.Nous avons évalué nos approches sur plusieurs datasets et nous les avons comparées avec les algorithmes de l’état de l’art / Querying graph data is a fundamental problem that witnesses an increasing interest especially for massive structured data where graphs come as a promising alternative to relational databases for big data modeling. However, querying graph data is different and more complex than querying relational table-based data. The main task involved in querying graph data is subgraph isomorphism search which is an NP-complete problem. Subgraph isomorphism search, is an important problem which is involved in various domains such as pattern recognition, social network analysis, biology, etc. It consists to enumerate the subgraphs of a data graph that match a query graph. The most known solutions of this problem are backtracking-based. They explore a large search space which results in a high computational cost when we deal with massive graph data. To reduce time and memory space complexity of subgraph isomorphism search. We propose to use compressed graphs. In our approach, subgraph isomorphism search is achieved on compressed representations of graphs without decompressing them. Graph compression is performed by grouping vertices into super vertices. This concept is known, in graph theory, as modular decomposition. It is used to generate a tree representation of a graph that highlights groups of vertices that have the same neighbors. With this compression we obtain a substantial reduction of the search space and consequently a significant saving in the processing time. We also propose a novel encoding of vertices that simplifies the filtering of the search space. This new mechanism is called compact neighborhood Index (CNI). A CNI distills all the information around a vertex in a single integer. This simple neighborhood encoding reduces the time complexity of vertex filtering from cubic to quadratic which is considerable for big graphs. We propose also an iterative local global filtering algorithm that relies on the characteristics of CNIs to ensure a global pruning of the search space.We evaluated our approaches on several real-word datasets and compared them with the state of the art algorithms

Ce sujet de thèse concerne le développement d’analyse des propriétés structurelles en interaction avec des indicateurs de fiabilité. Notre étude porte sur des systèmes structurés (linéaire, bilinéaire ou linéaire à commutations), ces derniers doivent vérifier quelques propriétés importantes pour l’accomplissement de leur mission. Ces propriétés dépendent de la structure du système, d’où l’appellation "propriétés structurelles". La structure du système peut être représentée par un graphe composé de sommets et d’arcs. La vérification des propriétés structurelles dépend principalement de 4 conditions élémentaires de connectivité, de lien, de distance et de couplage complet. Nous avons développé des algorithmes permettant de les exprimer sous forme d’expressions booléennes basées sur les arcs du graphe représentant le système. Nous considérons que chaque arc est lié aux composants du système. Une défaillance au niveau des composants peut provoquer la modification de la structure du système, et donc peut rendre une propriété structurelle insatisfaite. Ainsi, les propriétés structurelles sont écrites sous forme d’expressions booléennes basées sur l’état de fonctionnement des composants. En utilisant les expressions booléennes associées aux propriétés structurelles, leur fiabilité et/ou disponibilité peut être calculée sachant les caractéristiques de sûreté de fonctionnement des composants du système. À travers cette étude, nous pouvons vérifier si, pendant le temps de mission du système, une propriété structurelle restera satisfaite et/ou respectera un niveau de performance exigé par un cahier des charges. / This thesis concerns the development of analysis of structural properties in interaction with indicators of reliability. Our study focuses on (linear, bilinear or switching) structured systems, they must verify some important properties for the accomplishment of their mission. Properties depend on the structure of the system, hence the term "structural properties". The structure of the system can be represented by a graph consisting of vertices and edges. Verification of structural properties depends mainly on four basic conditions of connectivity, link distance and complete linkage. We have developed algorithms to express the form of Boolean expressions based on the edges of the graph representing the system. We consider that each edge is linked to the system components. A failure at the component level can cause changes in the structure of the system, and therefore can make a structural property unsatisfied. Thus, the structural properties are written as boolean expressions based on the operating state of the components. Using boolean expressions associated to the structural properties, reliability and / or availability can be calculated knowing the characteristics of the system components. Through this study, we can check if during the mission time of the system, a structural property remain satisfied and / or comply with a level of performance required by the specifications

La théorie de la NP-complétude nous apprend que pour un certain nombre de problèmes d'optimisation, il est vain d'espérer un algorithme efficace calculant une solution optimale. Partant de ce constat, un moyen pour contourner cet obstacle est de réaliser un compromis sur chacun de ces critères, engendrant deux approches devenues classiques. La première, appelée approximation polynomiale, consiste à développer des algorithmes efficaces et retournant une solution proche d'une solution optimale. La seconde, appelée complexité paramétrée, consiste à développer des algorithmes retournant une solution optimale mais dont l'explosion combinatoire est capturée par un paramètre de l'entrée bien choisi. Cette thèse comporte deux objectifs. Dans un premier temps, nous proposons d'étudier et d'appliquer les méthodes classiques de ces deux domaines afin d'obtenir des résultats positifs et négatifs pour deux problèmes d'optimisation dans les graphes : un problème de partition appelé Sparsest k-Compaction, et un problème de recherche d'un sous-graphe avec une cardinalité fixée appelé Sparsest k-Subgraph. Dans un second temps, nous présentons comment les méthodes de ces deux domaines ont pu se combiner ces dernières années pour donner naissance au principe d'approximation paramétrée. En particulier, nous étudierons les liens entre approximation et algorithmes de noyaux. / The theory of NP-completeness tells us that for many optimization problems, there is no hope for finding an efficient algorithm computing an optimal solution. Based on this, two classical approaches have been developped to deal with these problems. The first one, called polynomial- time approximation, consists in designing efficient algorithms computing a solution that is close to an optimal one. The second one, called param- eterized complexity, consists in designing exact algorithms which com- binatorial explosion is captured by a carefully chosen parameter of the instance. The goal of this thesis is twofold. First, we study and apply classical methods from these two domains in order to obtain positive and negative results for two optimization problems in graphs: a partitioning problem called Sparsest k-Compaction, and a cardinality constraint subgraph problem called Sparsest k-Subgraph. Then, we present how the different methods from these two domains have been combined in recent years in a concept called parameterized approximation. In particular, we study the links between approximation and kernelization algorithms.

Les réseaux phylogénétiques généralisent le modèle de l'arbre pour décrire l'évolution, en permettant à des arêtes entre les branches de l'arbre d'exprimer des échanges de matériel génétique entre espèces coexistantes. De nombreuses approches combinatoires - fondées sur la manipulation d'ensembles finis d'objets mathématiques - ont été conçues pour reconstruire ces réseaux à partir de données extraites de plusieurs arbres de gènes contradictoires. Elles se divisent en plusieurs catégories selon le type de données en entrées (triplets, quadruplets, clades ou bipartitions) et les restrictions de structure sur les réseaux reconstruits. Nous analysons en particulier la structure d'une classe de réseaux restreints, les réseaux de niveau k, et adaptons ce paramètre de niveau au contexte non enraciné. Nous donnons aussi de nouvelles méthodes combinatoires pour reconstruire des réseaux phylogénétiques, à partir de clades - méthode implémentée dans le logiciel Dendroscope - ou de quadruplets. Nous étudions les limites de ces méthodes combinatoires (explosion de complexité, bruit et silence dans les données, ambiguïté des réseaux reconstruits) et la façon de les prendre en compte, en particulier par un pré-traitement des données. Finalement, nous illustrons les résultats de ces méthodes de reconstruction sur des données réelles avant de conclure sur leur utilisation dans une méthodologie globale qui intègre des aspects statistiques. / Phylogenetic networks generalize the tree concept to model Evolution, by allowing edges between branches inside the tree to reflect genetic material exchanges between coexisting species. Lots of combinatorial approaches have been designed to reconstruct networks from data extracted from a set of contradictory gene trees. These approaches can be divided into several categories depending on the kind of input, i.e. triplets, quartets, clusters and splits, and on the kind of structure restrictions they impose on reconstructed networks.We particularly analyze the structure of one class of such restricted networks, namely level-k phylogenetic networks, and adapt this level parameter to the unrooted context. We also give new combinatorial methods to reconstruct phylogenetic networks from clusters - implemented in Dendroscope - or quartets. We study the limits of combinatorial methods (complexity explosion, noise and silence in the data, ambiguity in the reconstucted network), and the way to tackle them, in particular with an appropriate data preprocessing. Finally we illustrate the results of these reconstruction methods on a dataset, and we conclude on how to use them in a global methodology which integrates statistical aspects.

Dans de nombreuses applications telles que la médecine, l'environnement ou les biotechnologies par exemple, la découverte de nouveau processus de régulations de gènes permet une meilleure compréhension des réponses phénotypiques des cellules à des stimuli externes. Pour cela, il est alors d'usage de générer et d'analyser les données transcriptomiques issues d'expériences de types puces à ADN ou plus récemment de RNAseq. Ainsi, pour chaque gène d'un organisme d'étude placé dans différentes conditions expérimentales, un ensemble de niveau d'expression est obtenu. A partir de ces données, les mécanismes de régulation des gènes peuvent être obtenus à travers un ensemble de liens dans des graphes. Dans ces réseaux, les nœuds correspondent aux gènes. A lien entre deux nœuds est identifié si une relation de régulation existent entre les deux gènes correspondant. De tels réseaux sont appelés Réseaux de Régulation de Gènes (RRGs). Malgré la profusion de méthodes d'inférence disponible, leur construction et leur analyse restent encore à ce jour un défi.Dans cette thèse, nous proposons de répondre au problème d'inférence de réseaux par des techniques d'optimisation dans des graphes. A partir d'information de régulation sur l'ensemble des couples de gènes, nous proposons de déterminer la présence d'arêtes dans le RRG final en adoptant une formulation de fonction objectif intégrant des contraintes. Des a priori à la fois biologiques (sur les interactions entre les gènes) et structuraux (sur la connectivité des nœuds) ont été considérés pour restreindre l'espace des solutions possibles. Les différents a priori donnent des fonctions objectifs ayant des propriétés différentes, pour lesquelles des stratégies d'optimisation adaptées (continue et/ou discrète) peuvent être appliquées. Les post-traitement que nous avons développé ont mené à un ensemble de méthodes nommés BRANE, pour "Biologically-Related A priori for Network Enhancement". Pour chacune des méthodes développées (BRANE Cut, BRANE Relax et BRANE Clust), nos contributions sont triples : formulation de la fonction objectif à l'aide d'a priori, développement de la stratégie d'optimisation et validation (numérique et biologique) sur des données de parangonnage issues des challenges DREAM4 et DREAM5, montrant ainsi des améliorations pouvant atteindre 20%.En complément de l'inférence de réseaux, notre travail s'est étendu à des traitements de données sur graphe plus génériques, tels que les problèmes inverses. Nous avons notamment étudié HOGMep, une approche Bayésienne utilisant des stratégies d'approximation Bayésienne variationnelle. Cette méthode a été développée pour résoudre de façon conjointe, des problèmes de restauration et de classification sur des données multi-composantes (signaux et images). Les performances d'HOGMep dans un contexte de déconvolution d'image couleur montrent de bonnes qualités de reconstruction et de segmentation. Une étude préliminaire dans un contexte de classification de données médicales liant génotype et phénotype a également montré des résultats prometteurs pour des adaptions à venir en bioinformatiques. / The discovery of novel gene regulatory processes improves the understanding of cell phenotypicresponses to external stimuli for many biological applications, such as medicine, environmentor biotechnologies. To this purpose, transcriptomic data are generated and analyzed from mi-croarrays or more recently RNAseq experiments. For each gene of a studied organism placed indifferent living conditions, they consist in a sequence of genetic expression levels. From thesedata, gene regulation mechanisms can be recovered by revealing topological links encoded ingeometric graphs. In regulatory graphs, nodes correspond to genes. A link between two nodesis identified if a regulation relationship exists between the two corresponding genes. Such net-works are called Gene Regulatory Networks (GRNs). Their construction as well as their analysisremain challenging despite the large number of available inference methods.In this thesis, we propose to address this network inference problem with recently developedtechniques pertaining to graph optimization. Given all the pairwise gene regulation informa-tion available, we propose to determine the presence of edges in the final GRN by adoptingan energy optimization formulation integrating additional constraints. Either biological (infor-mation about gene interactions) or structural (information about node connectivity) a priorihave been considered to reduce the space of possible solutions. Different priors lead to differentproperties of the global cost function, for which various optimization strategies can be applied.The post-processing network refinements we proposed led to a software suite named BRANE for“Biologically-Related A priori for Network Enhancement”. For each of the proposed methodsBRANE Cut, BRANE Relax and BRANE Clust, our contributions are threefold: a priori-based for-mulation, design of the optimization strategy and validation (numerical and/or biological) onbenchmark datasets.In a ramification of this thesis, we slide from graph inference to more generic data processingsuch as inverse problems. We notably invest in HOGMep, a Bayesian-based approach using aVariation Bayesian Approximation framework for its resolution. This approach allows to jointlyperform reconstruction and clustering/segmentation tasks on multi-component data (for instancesignals or images). Its performance in a color image deconvolution context demonstrates bothquality of reconstruction and segmentation. A preliminary study in a medical data classificationcontext linking genotype and phenotype yields promising results for forthcoming bioinformaticsadaptations.

Cette thèse est proposée en deux parties. Une première partie se concentre sur la segmentation d’image. C’est en effet un problème fondamental pour la vision par ordinateur. En particulier, la segmentation non supervisée d’images est un élément important dans de nombreux algorithmes de haut niveau et de systèmes d’application. Dans cette thèse, nous proposons trois méthodes qui utilisent la segmentation d’images se basant sur différentes méthodes de graphes qui se révèlent être des outils puissants permettant de résoudre ces problèmes. Nous proposons dans un premier temps de développer une nouvelle méthode originale de construction de graphe. Nous analysons également différentes méthodes similaires ainsi que l’influence de l’utilisation de divers descripteurs. Le type de graphe proposé, appelé graphe local/global, encode de manière adaptative les informations sur la structure locale et globale de l’image. De plus, nous réalisons un groupement global en utilisant une représentation parcimonieuse des caractéristiques des superpixels sur le dictionnaire de toutes les caractéristiques en résolvant un problème de minimisation l0. De nombreuses expériences sont menées par la suite sur la base de données <Berkeley Segmentation>, et la méthode proposée est comparée avec des algorithmes classiques de segmentation. Les résultats démontrent que notre méthode peut générer des partitions visuellement significatives, mais aussi que des résultats quantitatifs très compétitifs sont obtenus en comparaison des algorithmes usuels. Dans un deuxième temps, nous proposons de travailler sur une méthode reposant sur un graphe d’affinité discriminant, qui joue un rôle essentiel dans la segmentation d’image. Un nouveau descripteur, appelé patch pondéré par couleur, est développé pour calculer le poids des arcs du graphe d’affinité. Cette nouvelle fonctionnalité est en mesure d’intégrer simultanément l’information sur la couleur et le voisinage en représentant les pixels avec des patchs de couleur. De plus, nous affectons à chaque pixel une pondération à la fois local et globale de manière adaptative afin d’atténuer l’effet trop lisse lié à l’utilisation de patchs. Des expériences approfondies montrent que notre méthode est compétitive par rapport aux autres méthodes standards à partir de plusieurs paramètres d’évaluation. Finalement, nous proposons une méthode qui combine superpixels, représentation parcimonieuse, et une nouvelle caractéristisation de mi-niveau pour décrire les superpixels. Le nouvelle caractérisation de mi-niveau contient non seulement les mêmes informations que les caractéristiques initiales de bas niveau, mais contient également des informations contextuelles supplémentaires. Nous validons la caractéristisation de mi-niveau proposée sur l’ensemble de données MSRC et les résultats de segmentation montrent des améliorations à la fois qualitatives et quantitatives par rapport aux autres méthodes standards. Une deuxième partie se concentre sur le suivi d’objets multiples. C’est un domaine de recherche très actif, qui est d’une importance majeure pour un grand nombre d’applications, par exemple la vidéo-surveillance de piétons ou de véhicules pour des raisons de sécurité ou l’identification de motifs de mouvements animaliers. / Image segmentation is a fundamental problem in computer vision. In particular, unsupervised image segmentation is an important component in many high-level algorithms and practical vision systems. In this dissertation, we propose three methods that approach image segmentation from different angles of graph based methods and are proved powerful to address these problems. Our first method develops an original graph construction method. We also analyze different types of graph construction method as well as the influence of various feature descriptors. The proposed graph, called a local/global graph, encodes adaptively the local and global image structure information. In addition, we realize global grouping using a sparse representation of superpixels’ features over the dictionary of all features by solving a l0-minimization problem. Extensive experiments are conducted on the Berkeley Segmentation Database, and the proposed method is compared with classical benchmark algorithms. The results demonstrate that our method can generate visually meaningful partitions, but also that very competitive quantitative results are achieved compared with state-of-the-art algorithms. Our second method derives a discriminative affinity graph that plays an essential role in graph-based image segmentation. A new feature descriptor, called weighted color patch, is developed to compute the weight of edges in an affinity graph. This new feature is able to incorporate both color and neighborhood information by representing pixels with color patches. Furthermore, we assign both local and global weights adaptively for each pixel in a patch in order to alleviate the over-smooth effect of using patches. The extensive experiments show that our method is competitive compared to the other standard methods with multiple evaluation metrics. The third approach combines superpixels, sparse representation, and a new midlevel feature to describe superpixels. The new mid-level feature not only carries the same information as the initial low-level features, but also carries additional contextual cue. We validate the proposed mid-level feature framework on the MSRC dataset, and the segmented results show improvements from both qualitative and quantitative viewpoints compared with other state-of-the-art methods. Multi-target tracking is an intensively studied area of research and is valuable for a large amount of applications, e.g. video surveillance of pedestrians or vehicles motions for sake of security, or identification of the motion pattern of animals or biological/synthetic particles to infer information about the underlying mechanisms. We propose a detect-then-track framework to track massive colloids’ motion paths in active suspension system. First, a region based level set method is adopted to segment all colloids from long-term videos subject to intensity inhomogeneity. Moreover, the circular Hough transform further refines the segmentation to obtain colloid individually. Second, we propose to recover all colloids’ trajectories simultaneously, which is a global optimal problem that can be solved efficiently with optimal algorithms based on min-cost/max flow. We evaluate the proposed framework on a real benchmark with annotations on 9 different videos. Extensive experiments show that the proposed framework outperforms standard methods with large margin.

La modélisation et la simulation de dynamiques spatiales, en particulier pour l'étude de l'évolution de paysages ou de problématiques environnementales pose la question de l'intégration des différentes formes de représentation de l'espace au sein d'un même modèle. Ocelet est une approche de modélisation de dynamiques spatiales basée sur le concept original de graphe d'interaction. Le graphe porte à la fois la structure d'une relation entre entités d’un modèle et la sémantique décrivant son évolution. Les relations entre entités spatiales sont ici traduites en graphes d'interactions et ce sont ces graphes que l'on fait évoluer lors d'une simulation. Les concepts à la base d'Ocelet peuvent potentiellement manipuler les deux formes de représentation spatiale connues, celle aux contours définis (format vecteur) ou la discrétisation en grille régulière (format raster). Le format vecteur est déjà intégré dans la première version d'Ocelet. L'intégration du format raster et la combinaison des deux restaient à étudier et à réaliser. L'objectif de la thèse est d'abord étudier les problématiques liées à l'intégration des champs continus et leur représentation discrétisée en pavage régulier, à la fois dans le langage Ocelet et dans les concepts sur lesquels il repose. Il a fallu notamment prendre en compte les aspects dynamiques de cette intégration, et d'étudier les transitions entre données géographiques de différentes formes et graphe d'interactions à l'aide de concepts formalisés. Il s'est agi ensuite de réaliser l'implémentation de ces concepts dans la plateforme de modélisation Ocelet, en adaptant à la fois son compilateur et son moteur d'exécution. Enfin, ces nouveaux concepts et outils ont été mis à l'épreuve dans trois cas d'application très différents : deux modèles sur l’île de la Réunion, le premier simulant le ruissellement dans le bassin versant de la Ravine Saint Gilles s'écoulant vers la Côte Ouest de l'île, l’autre simulant la diffusion de plantes invasives dans les plaines des hauts à l'intérieur du Parc National de La Réunion. Le dernier cas décrit la spatialisation d'un modèle de culture et est appliqué ici pour simuler les rendements de cultures céréalières sur l’ensemble de l’Afrique de l’Ouest, dans le contexte d'un système d'alerte précoce de suivi des cultures à l'échelle régionale. / The modelling and simulation of spatial dynamics, particularly for studying landscape changes or environmental issues, raises the question of integrating different forms of spatial representation within the same model. Ocelet is an approach for modelling spatial dynamics based on the original concept of interaction graph. Such a graph holds both the structure of a relation between entities of a model and the semantics describing its evolution. The relationships between spatial entities are here translated into interaction graphs and these graphs are made to evolve during a simulation. The concepts on which Ocelet is based can potentially handle two known forms of spatial representation: shapes with contours (vector format) or regular grid cells (raster). The vector format is already integrated in the first version of Ocelet. The integration of raster and the combination of the two remained to be studied and carried out. The aim of the thesis is to first study the issues related to the integration of continuous fields and their representation by regular tiling, both in the Ocelet language and the concepts on which it is based. The dynamic aspects of this integration had to be taken into account and transitions between different forms of geographic data and interaction graphs had to be studied in the light of the concepts formalized. The concepts were then implemented in the Ocelet modelling platform, with the adaptation of both its compiler and runtime. Finally, these new concepts and tools were tested in three very different cases: two models on Reunion Island, the first simulating runoff in Ravine Saint Gilles watershed in the West Coast of the island, the other simulating the spread of invasive plants in the high plains inside the Reunion National Park. The last case describes the spatialisation of a crop model and is applied here to simulate the cereal crop yields in West Africa, in the context of an early warning system for regional crop monitoring.