Search

This report discusses a new algorithm for makespan minimization on situations where the workload can be partitioned among heterogeneous resources. Without making any assumptions regarding the behavior or shape of the functions giving the execution time on a resource, we are able to provide optimal solutions with a dynamic programming algorithm in O(T^2n) for a workload of T tasks and n heterogeneous resources. This report includes a short state of the art, the problem's model, the algorithm, and its optimality proof.; Ce rapport discute d'un nouvel algorithme pour la minimisation du makespan dans des situations où la charge de travail peut être partitionnée entre des ressources hétérogènes. Sans faire aucune hypothèse sur le comportement ou la forme des fonctions donnant le temps d'exécution sur une ressource, nous sommes capables de fournir des solutions optimales avec un algorithme de programmation dynamique en O(T^2n) pour une charge de travail de T tâches et n ressources hétérogènes.Ce rapport comprend un bref état de l'art, le modèle du problème, l'algorithme, et sa preuve d'optimalité.

International audience; The arrival of quantum machines may revolutionize many fields, in particular that of combinatorial algorithms. Indeed, these machines propose several optimization algorithms, such as QAOA for "Quantum Approximate Optimization Algorithm", VQE for "Variational Quantum Eigensolver" and the oracle-based search algorithm published by Lov Grover. These algorithms each bring a theoretical gain on the computation time for some combinatorial problems. However, to date there are several different technologies allowing the design of a quantum chip, none of which is dominant at the moment. In this work we are interested in machines called "gate machines" and "quantum annealing" machines. The executions for the gate machines are realized on IBM simulators and machines using the Qiskit library and the Ocean library of D-Wave for the quantum annealing machines.The objective is to propose different models with their associated quantum circuits for the hypergraph partitioning problem and to measure the complexity in space and in number of gates of the different optimization algorithms chosen.; L'arrivée des machines quantiques risque de révolutionner de nombreux domaines, en particulier celui des algorithmes combinatoires. En effet, ces machines proposent plusieurs algorithmes d'optimisation, tels que, QAOA pour "Quantum Approximate Optimization Algorithm", VQE pour "Variational Quantum Eigensolver" ainsi que l'algorithme de recherche à partir d'un oracle publié par Lov Grover. Ces algorithmes apportent chacun un gain théorique sur le temps de calcul pour certains problèmes combinatoires. Cependant, à ce jour il existe plusieurs technologies différentes permettant de concevoir une puce quantique dont aucune n'est pour l'instant dominante. Dans ce travail nous nous intéressons aux machines appelées "machines à portes" et aux machines dites à "recuit quantique". Les exécutions pour les machines à portes sont réalisées sur les simulateurs et les machines d'IBM à l'aide de la bibliothèque Qiskit et de la bibliothèque Ocean de D-Wave pour les machines de type recuit quantique.L'objectif est de proposer plusieurs modèles avec leurs circuits quantiques associés pour le problème de partitionnement d'hypergraphes et de mesurer la complexité en espace et en nombre de portes des différents algorithmes d'optimisation choisis.

International audience; Un hypergraphe est une extension de la notion de graphe dans lequel les hyperarêtes contiennent au moins un sommet. Les hypergraphes modélisent de nombreux objets comme par exemple, un circuit électronique, un ensemble de données ou un ensemble de tâches/calculs à réaliser. Le partitionnement d'un hypergraphe consiste à séparer les sommets en plusieurs sous-ensembles appelés parties, de taille plus ou moins similaire. L'objectif est de minimiser le nombre d'hyperarêtes partagées entre les parties. Dans ce travail, nous nous intéressons au problème de partitionnement sur une sous-classe d'hypergraphes modélisant des circuits électroniques. Ces hypergraphes sont composés de sous-hypergraphes orientés sans cycles, inter-connectés par les sommets sources et les sommets puits de ces derniers. Nous proposons aussi d'étendre la fonction objectif mesurant le coût de coupe afin tenir compte de la minimisation de la longueur des chemins au sein des sous-hypergraphes orientéssans cycle. Dans notre contexte, une hyperarête coupée sera pénalisée et augmentera la longueur des chemins incluant cette dernière. Afin de traiter ce problème nous proposons dans cette étude de comparer deux méthodes basées sur une approche multi-niveaux.

The objective of this thesis is to define efficient methods for optimization of free-form surfaces machining time. Specifically, 3-axis and 3+2-axis by zone end-milling, using parallel-planes strategy are considered under quality constraints (maximum scallop height). The first chapter presents the prerequisites to know about the machining problem, as well as the basic notions necessary to understand the rest of this work.The second chapter is devoted to a new methodology of approximation of free-form surfaces by planes, using Principal Component Analysis (PCA). In the third chapter, the clustering of free-form surfaces is treated. A new metric is introduced to take into account the kinematic behavior of the machine, also, different clustering algorithms are tested and compared. In the last chapter, the machining of free-form surfaces is formulated as an optimization problem where we seek to minimize the machining time under the scallop height constraint. An original formulation integrating the clustering and machining steps is proposed. The resulting optimization problem is a black-box problem solved by the NOMAD software. A heuristic approach combining PCA and optimization is also proposed, this approach allows to obtainconsiderable gains compared to the results we have obtained so far and those from the literature; Cette thèse a pour objet la définition de méthodes efficaces pour l’optimisation du temps d’usinage en bout et par zones des surfaces gauches sur les machines 3-axes et 3+2-axes, sous contrainte de qualité (hauteur de crête maximale) en utilisant la stratégie plans parallèles. Le premier chapitre présente les prérequis à savoir sur le problème d’usinage, ainsi que les notions de bases nécessaires à la compréhension de la suite de ce travail. Le second chapitre est consacré à une nouvelle méthodologie d’approximation des surfaces gauches par des plans, à l’aide de l’Analyse en Composantes Principales (ACP). Dans le troisième chapitre , le partitionnement des surfaces gauches est traité. Une nouvelle métrique est intro-duite permettant prendre en compte le comportement cinématique de la machine, de plus différents algorithmes de partitionnement sont testés et comparés. Dans le dernier chapitre, l’usinage de surfaces gauches est formulé comme un problème d’optimisation où on cherche à minimiser le temps d’usinage sous contrainte de hauteur de crête. Une formulation originale intégrant les étapes de partitionnement et d’usinage est proposée. Le problème d’optimisation ainsi obtenu est de type boite noire et résolu par le logiciel NOMAD. Une approche heuristique combinant ACP et optimisation est également proposée. Cette approche permet d’obtenir des gains considérables par rapport aux résultats que nous avons obtenus jusqu’ici etceux de la littérature.

As event data becomes an ubiquitous source of information, data science techniques represent an unprecedented opportunity to analyze and react to the processes that generate this data. Process Mining is an emerging field that bridges the gap between traditional data analysis techniques, like Data Mining, and Business Process Management. One core value of Process Mining is the discovery of formal process models like Petri nets or BPMN models which attempt to make sense of the events recorded in logs. Due to the complexity of event data, automated process discovery algorithms tend to create dense process models which are hard to interpret by humans. Fortunately, Conformance Checking, a sub-field of Process Mining, enables relating observed and modeled behavior, so that humans can map these two pieces of process information. Conformance checking is possible through alignment artefacts, which associate process models and event logs. Different types of alignment artefacts exist, namely alignments, multi-alignments and anti-alignments. Currently, only alignment artefacts are deeply addressed in the literature. It allows to relate the process model to a given process instance. However, because many behaviors exist in logs, identifying an alignment per process instance hinders the readability of the log-to-model relationships.The present thesis proposes to exploit the conformance checking artefacts for clustering the process executions recorded in event logs, thereby extracting a restrictive number of modeled representatives. Data clustering is a common method for extracting information from dense and complex data. By grouping objects by similarities into clusters, data clustering enables to mine simpler datasets which embrace the similarities and the differences contained in data. Using the conformance checking artefacts in a clustering approach allows to consider a reliable process model as a baseline for grouping the process instances. Hence, the discovered clusters are associated with modeled artefacts, that we call model-based trace variants, which provides opportune log-to-model explanations.From this motivation, we have elaborated a set of methods for computing conformance checking artefacts. The first contribution is the computation of a unique modeled behavior that represents of a set of process instances, namely multi-alignment. Then, we propose several alignment-based clustering approaches which provide clusters of process instances associated to a modeled artefact. Finally, we highlight the interest of anti-alignment for extracting deviations of process models with respect to the log. This latter artefact enables to estimate model precision, and we show its impact in model-based clustering. We provide SAT encoding for all the proposed techniques. Heuristic algorithms are then added to deal with computing capacity of today’s computers, at the expense of loosing optimality.; Les données d'événements devenant une source d'information omniprésente, les techniques d'analyse de données représentent une opportunité sans précédent pour étudier et réagir aux processus qui génèrent ces données. Le Process Mining est un domaine émergent qui comble le fossé entre les techniques d'analyse de données, comme le Data Mining, et les techniques de management des entreprises, à savoir, le Business Process Management. L'une des bases fondamentales du Process Mining est la découverte de modèles de processus formels tels que les réseaux de Petri ou les modèles BPMN qui tentent de donner un sens aux événements enregistrés dans les journaux. En raison de la complexité des données d'événements, les algorithmes de découverte de processus ont tendance à créer des modèles de processus denses, qui sont difficiles à interpréter par les humains. Heureusement, la Vérification de Conformité, un sous-domaine du Process Mining, permet d'établir des liens entre le comportement observé et le comportement modélisé, facilitant ainsi la compréhension des correspondance entre ces deux éléments d'information sur les processus. La Vérification de Conformité est possible grâce aux artefacts d'alignement, qui associent les modèles de processus et les journaux d'événements. Il existe différents types d'artefacts d'alignement, à savoir les alignements, les multi-alignements et les anti-alignements. Actuellement, seuls les alignements sont traités en profondeur dans la littérature scientifique. Un alignement permet de relier le modèle de processus à une instance de processus donnée. Cependant, étant donné que de nombreux comportements existent dans les logs, l'identification d'un alignement par instance de processus nuit à la lisibilité des relations log-modèle.La présente thèse propose d'exploiter les artefacts de conformité pour regrouper les exécutions de processus enregistrées dans les journaux d'événements, et ainsi extraire un nombre restrictif de représentations modélisées. Le regroupement de données, communément appelé partitionnement, est une méthode courante pour extraire l'information de données denses et complexes. En regroupant les objets par similarité dans des clusters, le partitionnement permet d'extraire des ensembles de données plus simples qui englobent les similarités et les différences contenues dans les données. L'utilisation des artefacts de conformité dans une approche de partitionnement permet de considérer un modèle de processus fiable comme une base de référence pour le regroupement des instances de processus. Ainsi, les clusters découverts sont associés à des artefacts modélisés, que nous appelons variantes modélisées des traces, ce qui fournit des explications opportunes sur les relations entre le journal et le modèle.Avec cette motivation, nous avons élaboré un ensemble de méthodes pour calculer les artefacts de conformité. La première contribution est le calcul d'un comportement modélisé unique qui représente un ensemble d'instances de processus, à savoir le multi-alignement. Ensuite, nous proposons plusieurs approches de partitionnement basées sur l'alignement qui fournissent des clusters d'instances de processus associés à un artefact modélisé. Enfin, nous soulignons l'intérêt de l'anti-alignement pour extraire les déviations des modèles de processus par rapport au journal. Ce dernier artefact permet d'estimer la précision du modèle. Nous montrons son impact sur nos approches de partitionnement basées sur des modèles. Nous fournissons un encodage SAT pour toutes les techniques proposées. Des heuristiques sont ensuite ajoutées pour tenir compte de la capacité de calcul des ordinateurs actuels, au prix d'une perte d'optimalité.

Supervised learning models are usually trained on data with limited constraints. Unfortunately, data are generally scarce, incomplete and biased in real-world use cases, which hampers efficient model design. Such data can and should still be leveraged to discover relevant patterns, glean insight and develop meaningful conclusions. In this thesis, we investigate an unsupervised learning approach to isolate minority samples encompassed within a larger population. Our review includes two different use cases: Amyotrophic Lateral Sclerosis prognosis and identification of potential innovation funding recipients. Despite differences in their purpose, these contexts face similar issues: poor data availability of partial and unrepresentative samples. In both cases, the aim is to detect samples from a minority population: patients with a poorer 1-year prognosis and companies that are more likely to be successful funding applicants. Data are projected into a lower-dimensional space using Uniform Manifold Approximation and Projection (UMAP), a nonlinear dimension reduction technique. Differences in data distributions are harnessed and used to isolate the target minority population, using Density Based Clustering of Applications with Noise (DBSCAN) and alpha shapes. Correlations between input and target variables become visible within the projection space and minority samples are isolated from the remaining data. As a result, in spite of poor data quality, we provide additional insight with regard to recently diagnosed patients and potential funding applicants.; Les modèles d'apprentissage supervisé sont généralement entraînés sur des données aux contraintes limitées. Malheureusement, les données sont souvent rares, incomplètes et biaisées dans de nombreux cas d’applications, et cela entrave la conception de modèles efficaces. De telles données peuvent et doivent néanmoins être exploitées, car elles demeurent des sources précieuses d’information. Elles permettent de découvrir des corrélations pertinentes et de parvenir à des conclusions significatives. Dans cette thèse, nous étudions une approche d'apprentissage non supervisé pour isoler des échantillons minoritaires compris à l’intérieur d’une population plus large. Notre étude intègre deux contextes applicatifs: le pronostic de la Sclérose Latérale Amyotrophique (SLA) et la recommandation aux entreprises de dispositifs publics de financement de l’innovation. Malgré des différences dans leur objectif, ces contextes sont confrontés à des problèmes similaires: une faible disponibilité des données associée à des échantillons non représentatifs et incomplets. Dans les deux cas, l'objectif est de détecter des échantillons d'une population minoritaire: les patients dont le pronostic à un an est défavorable et les sociétés qui ont plus de chances d'obtenir des financements. Les données sont projetées dans un espace bidimensionnel à l'aide de la méthode d’approximation et de projection de variété uniforme (UMAP), une technique de réduction de dimension non linéaire. Les différences de distribution des données sont exploitées de manière à isoler la population minoritaire cible, à l'aide du partitionnement spatial par densité (DBSCAN) et des formes alpha. Les corrélations entre les caractéristiques d'entrée et d’intérêt, que sont la survie à 1 an et l’obtention de financements, deviennent visibles dans l'espace de projection et les échantillons minoritaires sont isolés du reste des données. En dépit des contraintes sur les données, notre approche se révèle pertinente et informative au regard de patients récemment diagnostiqués avec la SLA et d'entreprises qui postulent pour un financement.

This thesis is interested in unsupervised statistical learning methods and their applications to health monitoring of aircraft engines at an industrial scale. Our first objective is to make health monitoring methodologies scale to massive datasets and allow engineering team to flexibly deploy various use cases. Besides the engineering aspects, we also try to address two fundamental theoretical challenges in unsupervised learning. First, the links between cluster structure and representation.And second, the very definition of structure, arising from the problem of model selection in clustering.Modern aircraft engines generate growing amounts of data during manufacturing,tests and flights, that can be leveraged for health monitoring and predictive maintenance, in order to improve safety, availability and reduce costs. In this work, we use sensor measurements collected on board of civil short and mid-range aircraft.These data sets are temporal and highly multidimensional due to the large number of sensors and sampling frequencies. Hence, applications need to scale to the large volumes of data, driven by the growing number of daily operating engines.Among all unsupervised learning approaches, clustering and self-organizing maps (SOM) provide useful insights on the distribution of complex and high-dimensional unlabeled data sets. To describe the internal state of an engine, expert indicators or features need to be extracted from raw data, before applying clustering algorithms.Our first contribution is to scale these methodologies using Big Data tools and distributed computing, in order to process entire fleets. We propose a generic and scalable pipeline enabling engineers to analyze flight data on a cluster. In addition,we present an new application to monitoring of vibration signatures.Another option is to automatically extract relevant features with deep neural networks, known as deep learning, which had a great impact in many areas of machine learning. Recently, its ability to improve clustering has been investigated. A second contribution of this thesis is a Deep Embedded SOM, a neural network-based model performing joint representation learning with an autoencoder and self-organization of the cluster prototypes. The third contribution of this thesis concerns model selection, which is perhaps the most difficult problem in clustering. We adopt the framework of cluster stability analysis, and propose a novel concept of within-cluster stability, leading to a criterion called Stadion (stability difference criterion) able to effectively select the number of clusters in a data set. We also apply Stadion to time series clustering validation by leveraging invariant transformations of the data., Cette thèse porte sur des méthodes d’apprentissage statistique non supervisées et leurs applications à la surveillance de santé (health monitoring) des moteurs d’avion à une échelle industrielle. Notre premier objectif est de faire passer les méthodologies de health monitoring à l’échelle de jeux de données massifs et de permettre aux ingénieurs de déployer de manière agile divers cas d’utilisation. Outre les aspects d’ingénierie, nous aborderons également deux défis théoriques fondamentaux en apprentissage non supervisé. Premièrement, les liens entre structure de partitionnement et représentation. Et deuxièmement, la définition même de la structure,découlant du problème de sélection du modèle en partitionnement de données(clustering). Aujourd’hui, les moteurs d’avion génèrent des quantités croissantes de données au cours de leur fabrication, des essais et des vols, pouvant être exploitées pour la surveillance et la maintenance prédictive, afin d’améliorer la sécurité, la disponibilité et de réduire les coûts. Dans ce travail, nous utiliserons des mesures de capteurs embarqués à bord d’avions civils court et moyen courrier. Ces jeux de données sont temporels et hautement multidimensionnels en raison du nombre de capteurs et leurs fréquences d’échantillonnage. Par conséquent, les applications doivent s’adapter aux grands volumes de données qui ne cessent de croître avec la hausse du trafic aérien.Parmi les approches d’apprentissage non supervisées, le clustering et les cartes auto-organisées (SOM) fournissent des informations utiles sur la distribution de jeux de données non étiquetés complexes et en grande dimension. Pour décrire l’état interne d’un moteur, des indicateurs experts doivent être extraits des données brutes, avant d’appliquer des algorithmes de clustering. Notre première contribution est de faire passer à l’échelle ces méthodologies via les outils du Big Dataet le calcul distribué, afin de traiter des flottes entières. Nous proposons une chaîne de traitement générique permettant aux ingénieurs d’analyser les données de vol stockées sur un cluster. En outre, nous présentons une application à la surveillance de signatures vibratoires.Une autre option, appelée apprentissage profond, consiste à extraire automatique-ment des caractéristiques pertinentes à l’aide de réseaux de neurones profonds.Cette approcha a bouleversé de nombreux domaines de l’apprentissage automatique ces dernières années. Récemment, sa capacité à améliorer le clustering a été étudiée. Une deuxième contribution de cette thèse est un modèle SOM profond (Deep Embedded SOM), basé sur des réseaux neurones combinant l’apprentissage de représentations via un auto-encodeur et l’auto-organisation des prototypes.La troisième contribution de cette thèse concerne la sélection de modèle, l’un des problèmes les plus ardus en clustering. Nous adoptons le cadre de l’analyse de stabilité, et proposons un nouveau concept de stabilité intra-cluster, conduisant à un critère appelé Stadion (critère de différence de stabilité) capable de sélectionner efficacement le nombre de clusters dans un jeu de données. Nous appliquerons également Stadion à la validation du clustering de séries temporelles en tirant parti des transformations invariantes des données.

Due to the great impact of deep learning on variety fields of machine learning, recently their abilities to improve clustering approaches have been investi- gated. At first, deep learning approaches (mostly Autoencoders) have been used to reduce the dimensionality of the original space and to remove possible noises (also to learn new data representations). Such clustering approaches that utilize deep learning approaches are called Deep Clustering. This thesis focuses on developing Deep Clustering models which can be used for different types of data (e.g., images, text). First we propose a Deep k-means (DKM) algorithm where learning data representations (through a deep Autoencoder) and cluster representatives (through the k-means) are performed in a joint way. The results of our DKM approach indicate that this framework is able to outperform similar algorithms in Deep Clustering. Indeed, our proposed framework is able to truly and smoothly backpropagate the loss function error through all learnable variables.Moreover, we propose two frameworks named SD2C and PCD2C which are able to integrate respectively seed words and pairwise constraints into end-to-end Deep Clustering frameworks. In fact, by utilizing such frameworks, the users can observe the reflection of their needs in clustering. Finally, the results obtained from these frameworks indicate their ability to obtain more tailored results.; En raison du grand impact de l’apprentissage profond sur divers domaines de l’apprentissage automatique, leurs capacités à améliorer les approches de clustering ont récemment été étudiées. Dans un premier temps, des approches d’apprentissage profond (principalement des autoencodeurs) ont été utilisées pour réduire la dimensionnalité de l’espace d’origine et pour supprimer les éventuels bruits (également pour apprendre de nouvelles représentations de données). De telles approches de clustering qui utilisent des approches d’apprentissage en profondeur sont appelées deep clustering. Cette thèse se concentre sur le développement de modèles de deep clustering qui peuvent être utilisés pour différents types de données (par exemple, des images, du texte). Tout d’abord, nous proposons un algorithme DKM (Deep k-means) dans lequel l’apprentissage des représentations de données (via un autoencodeur profond) et des représentants de cluster (via k-means) est effectué de manière conjointe. Les résultats de notre approche DKM indiquent que ce modèle est capable de surpasser des algorithmes similaires en Deep Clustering. En effet, notre cadre proposé est capable de propager de manière lisse l’erreur de la fonction de coût à travers toutes les variables apprenables.De plus, nous proposons deux modèles nommés SD2C et PCD2C qui sont capables d’intégrer respectivement des mots d’amorçage et des contraintes par paires dans des approches de Deep Clustering de bout en bout. En utilisant de telles approches, les utilisateurs peuvent observer le reflet de leurs besoins en clustering. Enfin, les résultats obtenus à partir de ces modèles indiquent leur capacité à obtenir des résultats plus adaptés.

Due to the great impact of deep learning on variety fields of machine learning, recently their abilities to improve clustering approaches have been investi- gated. At first, deep learning approaches (mostly Autoencoders) have been used to reduce the dimensionality of the original space and to remove possible noises (also to learn new data representations). Such clustering approaches that utilize deep learning approaches are called Deep Clustering. This thesis focuses on developing Deep Clustering models which can be used for different types of data (e.g., images, text). First we propose a Deep k-means (DKM) algorithm where learning data representations (through a deep Autoencoder) and cluster representatives (through the k-means) are performed in a joint way. The results of our DKM approach indicate that this framework is able to outperform similar algorithms in Deep Clustering. Indeed, our proposed framework is able to truly and smoothly backpropagate the loss function error through all learnable variables.Moreover, we propose two frameworks named SD2C and PCD2C which are able to integrate respectively seed words and pairwise constraints into end-to-end Deep Clustering frameworks. In fact, by utilizing such frameworks, the users can observe the reflection of their needs in clustering. Finally, the results obtained from these frameworks indicate their ability to obtain more tailored results.; En raison du grand impact de l’apprentissage profond sur divers domaines de l’apprentissage automatique, leurs capacités à améliorer les approches de clustering ont récemment été étudiées. Dans un premier temps, des approches d’apprentissage profond (principalement des autoencodeurs) ont été utilisées pour réduire la dimensionnalité de l’espace d’origine et pour supprimer les éventuels bruits (également pour apprendre de nouvelles représentations de données). De telles approches de clustering qui utilisent des approches d’apprentissage en profondeur sont appelées deep clustering. Cette thèse se concentre sur le développement de modèles de deep clustering qui peuvent être utilisés pour différents types de données (par exemple, des images, du texte). Tout d’abord, nous proposons un algorithme DKM (Deep k-means) dans lequel l’apprentissage des représentations de données (via un autoencodeur profond) et des représentants de cluster (via k-means) est effectué de manière conjointe. Les résultats de notre approche DKM indiquent que ce modèle est capable de surpasser des algorithmes similaires en Deep Clustering. En effet, notre cadre proposé est capable de propager de manière lisse l’erreur de la fonction de coût à travers toutes les variables apprenables.De plus, nous proposons deux modèles nommés SD2C et PCD2C qui sont capables d’intégrer respectivement des mots d’amorçage et des contraintes par paires dans des approches de Deep Clustering de bout en bout. En utilisant de telles approches, les utilisateurs peuvent observer le reflet de leurs besoins en clustering. Enfin, les résultats obtenus à partir de ces modèles indiquent leur capacité à obtenir des résultats plus adaptés.

This thesis focuses on multi-objective optimization problems arising when running scientific applications on high performance computing platforms and streaming applications on embedded systems. These optimization problems are all proven to be NP-complete, hence our efforts are mainly on designing efficient heuristics for general cases, and proposing optimal solutions for special cases.Some scientific applications are commonly modeled as rooted trees. Due to the size of temporary data, processing such a tree may exceed the local memory capacity. A practical solution on a multiprocessor system is to partition the tree into many subtrees, and run each on a processor, which is equipped with a local memory. We studied how to partition the tree into several subtrees such that each subtree fits in local memory and the makespan is minimized, when communication costs between processors are accounted for.Then, a practical work of tree scheduling arising in parallel sparse matrix solver is examined. The objective is to minimize the factorization time by exhibiting good data locality and load balancing. The proportional mapping technique is a widely used approach to solve this resource-allocation problem. It achieves good data locality by assigning the same processors to large parts of the task tree. However, it may limit load balancing in some cases. Based on proportional mapping, a dynamic scheduling algorithm is proposed. It relaxes the data locality criterion to improve load balancing. The performance of our approach has been validated by extensive experiments with the parallel sparse matrix direct solver PaStiX.Streaming applications often appear in video and audio domains. They are characterized by a series of operations on streaming data, and a high throughput. Multi-Processor System on Chip (MPSoC) is a multi/many-core embedded system that integrates many specific cores through a high speed interconnect on a single die. Such systems are widely used for multimedia applications. Lots of MPSoCs are batteries-operated. Such a tight energy budget intrinsically calls for an efficient schedule to meet the intensive computation demands. Dynamic Voltage and Frequency Scaling (DVFS) can save energy by decreasing the frequency and voltage at the price of increasing failure rates. Another technique to reduce the energy cost and meet the reliability target consists in running multiple copies of tasks. We first model applications as linear chains and study how to minimize the energy consumption under throughput and reliability constraints, using DVFS and duplication technique on MPSoC platforms.Then, in a following study, with the same optimization goal, we model streaming applications as series-parallel graphs, which are more complex than simple chains and more realistic. The target platform has a hierarchical communication system with two levels, which is common in embedded systems and high performance computing platforms. The reliability is guaranteed through either running tasks at the maximum speed or triplication of tasks. Several efficient heuristics are proposed to tackle this NP-complete optimization problem.; Cette thèse se concentre sur les problèmes d'optimisation multi-objectifs survenant lors de l'exécution d'applications scientifiques sur des plates-formes de calcul haute performance et des applications de streaming sur des systèmes embarqués. Ces problèmes d'optimisation se sont tous avérés NP-complets, c'est pourquoi nos efforts portent principalement sur la conception d'heuristiques efficaces pour des cas généraux et sur la proposition de solutions optimales pour des cas particuliers.Certaines applications scientifiques sont généralement modélisées comme des arbres enracinés. En raison de la taille des données temporaires, le traitement d'une telle arborescence peut dépasser la capacité de la mémoire locale. Une solution pratique sur un système multiprocesseur consiste à partitionner l'arborescence en plusieurs sous-arbres, et à exécuter chacun d'eux sur un processeur, qui est équipé d'une mémoire locale. Nous avons étudié comment partitionner l'arbre en plusieurs sous-arbres de sorte que chaque sous-arbre tienne dans la mémoire locale et que le makespan soit minimisé, lorsque les coûts de communication entre les processeurs sont pris en compte. Ensuite, un travail pratique d'ordonnancement d'arbres apparaissant dans un solveur de matrice clairsemée parallèle est examiné. L'objectif est de minimiser le temps de factorisation en présentant une bonne localisation des données et un équilibrage de charge. La technique de cartographie proportionnelle est une approche largement utilisée pour résoudre ce problème d'allocation des ressources. Il réalise une bonne localisation des données en affectant les mêmes processeurs à de grandes parties de l'arborescence des tâches. Cependant, cela peut limiter l'équilibrage de charge dans certains cas. Basé sur une cartographie proportionnelle, un algorithme d'ordonnancement dynamique est proposé. Il assouplit le critère de localisation des données pour améliorer l'équilibrage de charge. La performance de notre approche a été validée par de nombreuses expériences avec le solveur direct à matrice clairsemée parallèle PaStiX. Les applications de streaming apparaissent souvent dans les domaines vidéo et audio. Ils se caractérisent par une série d'opérations sur le streaming de données et un débit élevé. Le système multiprocesseur sur puce (MPSoC) est un système embarqué multi / plusieurs cœurs qui intègre de nombreux cœurs spécifiques via une interconnexion haute vitesse sur une seule puce. De tels systèmes sont largement utilisés pour les applications multimédias. De nombreux MPSoC fonctionnent sur piles. Un budget énergétique aussi serré nécessite intrinsèquement un calendrier efficace pour répondre aux demandes de calcul intensives. La mise à l'échelle dynamique de la tension et de la fréquence (DVFS) peut économiser de l'énergie en diminuant la fréquence et la tension au prix d'une augmentation des taux de défaillance. Une autre technique pour réduire le coût énergétique et atteindre l'objectif de fiabilité consiste à exécuter plusieurs copies de tâches. Nous modélisons d'abord les applications sous forme de chaînes linéaires et étudions comment minimiser la consommation d'énergie sous des contraintes de débit et de fiabilité, en utilisant DVFS et la technique de duplication sur les plates-formes MPSoC.Ensuite, dans une étude suivante, avec le même objectif d'optimisation, nous modélisons les applications de streaming sous forme de graphes série-parallèle, plus complexes que de simples chaînes et plus réalistes. La plate-forme cible dispose d'un système de communication hiérarchique à deux niveaux, ce qui est courant dans les systèmes embarqués et les plates-formes informatiques hautes performances. La fiabilité est garantie par l'exécution des tâches à la vitesse maximale ou par la triplication des tâches. Plusieurs heuristiques efficaces sont proposées pour résoudre ce problème d'optimisation NP-complet.

Sequential pattern mining techniques permit to discover recurring structures or patterns from very large datasets, with a very large field of applications. It aims at extracting a set of attributes, shared across time among a large number of objects in a given database. It is a challenging problem since mining algorithms are well known to be both time and memory consuming for large databases. In this paper, we extend the traditional problem of mining frequent sequences with intra-periodicity constraints. Then, we study issues related to intra-periodicity constraints such as search space pruning and partitioning. This study leads to a new efficient algorithm called Intra-Periodic Frequent Sequence Miner (IPFSM). Experimental results confirm the efficiency of IPFSM., Les techniques de recherche des motifs séquentiels permettent de découvrir des structures ou modèles récurrents à partir de très grandes bases de données, avec un très large champ d'applications. Elles visent à extraire un ensemble d'attributs, partagés dans le temps entre un grand nombre d'objets dans une base de données. C'est un problème difficile, car les algorithmes de recherche des motifs séquentiels sont gourmandes en temps CPU et en mémoire sur des grandes bases de données. Dans ce papier, nous étendons le problème traditionnel de l'extraction des séquences fréquentes avec des contraintes d'intra-périodicité. Ensuite, nous étudions les problèmes liés aux contraintes de périodicité, notament l'élagage et le partitionnement de l'espace de recherche. Cette étude conduit à un nouvel algorithme efficace appelé Intra-Periodic Frequent Sequence Miner (IPFSM). Les résultats expérimentaux confirment l'éfficacité de l'IPFSM.

The present study investigates the production and partial biochemical characterization of an extracellular thermostable xylanase from the Bacillus oceanisediminis strain SJ3 newly recovered from Algerian soil using three phase partitioning (TPP). The maximum xylanase activity recorded after 2 days of incubation at 37 °C was 20.24 U/ml in the presence of oat spelt xylan. The results indicated that the enzyme recovered in the middle phase of TPP system using the optimum parameters were determined as 50% ammonium sulfate saturation with 1.0:1.5 ratio of crude extract: t-butanol at pH and temperature of 8.0 and 10 °C, respectively. The xylanase was recovered with 3.48 purification fold and 107% activity recovery. The enzyme was optimally active at pH 7.0 and was stable over a broad pH range of 5.0–10. The optimum temperature for xylanase activity was 55 °C and the half-life time at this temperature was of 6 h. At this time point the enzyme retained 50% of its activity after incubation for 2 h at 95 °C. The crude enzyme resist to sodium dodecyl sulfate and β-mercaptoethanol, while all the tested ions do not affect the activity of the enzyme. The recovered enzyme is, at least, stable in tested organic solvents except in propanol where a reduction of 46.5% was observed. Further, the stability of the xylanase was higher in hydrophobic solvents where a maximum stability was observed with cyclohexane. These properties make this enzyme to be highly thermostable and may be suggested as a potential candidate for application in some industrial processes. To the best of our knowledge, this is the first report of xylanase activity and recoverey using three phase partitioning from B. oceanisediminis.

In Electronic Warfare, radar signals identification is a supreme asset for decision making in military tactical situations. By providing information about the presence of threats, classification and clustering of radar signals have a significant role ensuring that countermeasures against enemies are well-chosen and enabling detection of unknown radar signals to update databases. Most of the time, Electronic Support Measures systems receive mixtures of signals from different radar emitters in the electromagnetic environment. Hence a radar signal, described by a pulse-to-pulse modulation pattern, is often partially observed due to missing measurements and measurement errors. The identification process relies on statistical analysis of basic measurable parameters of a radar signal which constitute both quantitative and qualitative data. Many general and practical approaches based on data fusion and machine learning have been developed and traditionally proceed to feature extraction, dimensionality reduction and classification or clustering. However, these algorithms cannot handle missing data and imputation methods are required to generate data to use them. Hence, the main objective of this work is to define a classification/clustering framework that handles both outliers and missing values for any types of data. Here, an approach based on mixture models is developed since mixture models provide a mathematically based, flexible and meaningful framework for the wide variety of classification and clustering requirements. The proposed approach focuses on the introduction of latent variables that give us the possibility to handle sensitivity of the model to outliers and to allow a less restrictive modelling of missing data. A Bayesian treatment is adopted for model learning, supervised classification and clustering and inference is processed through a variational Bayesian approximation since the joint posterior distribution of latent variables and parameters is untractable. Some numerical experiments on synthetic and real data show that the proposed method provides more accurate results than standard algorithms.; En Guerre Electronique, l’identification des signaux radar est un atout majeur de la prise de décisions tactiques liées au théâtre d’opérations militaires. En fournissant des informations sur la présence de menaces, la classification et le partitionnement des signaux radar ont alors un rôle crucial assurant un choix adapté des contre-mesures dédiées à ces menaces et permettant la détection de signaux radar inconnus pour la mise à jour des bases de données. Les systèmes de Mesures de Soutien Electronique enregistrent la plupart du temps des mélanges de signaux radar provenant de différents émetteurs présents dans l’environnement électromagnétique. Le signal radar, décrit par un motif de modulations impulsionnelles, est alors souvent partiellement observé du fait de mesures manquantes et aberrantes. Le processus d’identification se fonde sur l’analyse statistique des paramètres mesurables du signal radar qui le caractérisent tant quantitativement que qualitativement. De nombreuses approches mêlant des techniques de fusion de données et d’apprentissage statistique ont été développées. Cependant, ces algorithmes ne peuvent pas gérer les données manquantes et des méthodes de substitution de données sont requises afin d’utiliser ces derniers. L’objectif principal de cette thèse est alors de définir un modèle de classification et partitionnement intégrant la gestion des valeurs aberrantes et manquantes présentes dans tout type de données. Une approche fondée sur les modèles de mélange de lois de probabilités est proposée dans cette thèse. Les modèles de mélange fournissent un formalisme mathématique flexible favorisant l’introduction de variables latentes permettant la gestion des données aberrantes et la modélisation des données manquantes dans les problèmes de classification et de partionnement. L’apprentissage du modèle ainsi que la classification et le partitionnement sont réalisés dans un cadre d’inférence bayésienne où une méthode d’approximation variationnelle est introduite afin d’estimer la loi jointe a posteriori des variables latentes et des paramètres. Des expériences sur diverses données montrent que la méthode proposée fournit de meilleurs résultats que les algorithmes standards.

International audience

The big scientific data generated by modern observation telescopes, raises recurring problems of performances, in spite of the advances in distributed data management systems. The main reasons are the complexity of the systems and the difficulty to adapt the access methods to the data. This thesis proposes new physical and logical optimizations to optimize execution plans of astronomical queries using transformation rules. These methods are integrated in ASTROIDE, a distributed system for large-scale astronomical data processing.ASTROIDE achieves scalability and efficiency by combining the benefits of distributed processing using Spark with the relevance of an astronomical query optimizer.It supports the data access using the query language ADQL that is commonly used.It implements astronomical query algorithms (cone search, kNN search, cross-match, and kNN join) tailored to the proposed physical data organization.Indeed, ASTROIDE offers a data partitioning technique that allows efficient processing of these queries by ensuring load balancing and eliminating irrelevant partitions. This partitioning uses an indexing technique adapted to astronomical data, in order to reduce query processing time.; Les masses de données scientifiques générées par les moyens d'observation modernes, dont l’observation spatiale, soulèvent des problèmes de performances récurrents, et ce malgré les avancées des systèmes distribués de gestion de données. Ceci est souvent lié à la complexité des systèmes et des paramètres qui impactent les performances et la difficulté d’adapter les méthodes d’accès au flot de données et de traitement.Cette thèse propose de nouvelles techniques d'optimisations logiques et physiques pour optimiser les plans d'exécution des requêtes astronomiques en utilisant des règles d'optimisation. Ces méthodes sont intégrées dans ASTROIDE, un système distribué pour le traitement de données astronomiques à grande échelle.ASTROIDE allie la scalabilité et l’efficacité en combinant les avantages du traitement distribué en utilisant Spark avec la pertinence d’un optimiseur de requêtes astronomiques.Il permet l'accès aux données à l'aide du langage de requêtes ADQL, couramment utilisé.Il implémente des algorithmes de requêtes astronomiques (cone search, kNN search, cross-match, et kNN join) en exploitant l'organisation physique des données proposée.En effet, ASTROIDE propose une méthode de partitionnement des données permettant un traitement efficace de ces requêtes grâce à l'équilibrage de la répartition des données et à l'élimination des partitions non pertinentes. Ce partitionnement utilise une technique d’indexation adaptée aux données astronomiques, afin de réduire le temps de traitement des requêtes.

In Electronic Warfare, radar signals identification is a supreme asset for decision making in military tactical situations. By providing information about the presence of threats, classification and clustering of radar signals have a significant role ensuring that countermeasures against enemies are well-chosen and enabling detection of unknown radar signals to update databases. Most of the time, Electronic Support Measures systems receive mixtures of signals from different radar emitters in the electromagnetic environment. Hence a radar signal, described by a pulse-to-pulse modulation pattern, is often partially observed due to missing measurements and measurement errors. The identification process relies on statistical analysis of basic measurable parameters of a radar signal which constitute both quantitative and qualitative data. Many general and practical approaches based on data fusion and machine learning have been developed and traditionally proceed to feature extraction, dimensionality reduction and classification or clustering. However, these algorithms cannot handle missing data and imputation methods are required to generate data to use them. Hence, the main objective of this work is to define a classification/clustering framework that handles both outliers and missing values for any types of data. Here, an approach based on mixture models is developed since mixture models provide a mathematically based, flexible and meaningful framework for the wide variety of classification and clustering requirements. The proposed approach focuses on the introduction of latent variables that give us the possibility to handle sensitivity of the model to outliers and to allow a less restrictive modelling of missing data. A Bayesian treatment is adopted for model learning, supervised classification and clustering and inference is processed through a variational Bayesian approximation since the joint posterior distribution of latent variables and parameters is untractable. Some numerical experiments on synthetic and real data show that the proposed method provides more accurate results than standard algorithms., En Guerre Electronique, l’identification des signaux radar est un atout majeur de la prise de décisions tactiques liées au théâtre d’opérations militaires. En fournissant des informations sur la présence de menaces, la classification et le partitionnement des signaux radar ont alors un rôle crucial assurant un choix adapté des contre-mesures dédiées à ces menaces et permettant la détection de signaux radar inconnus pour la mise à jour des bases de données. Les systèmes de Mesures de Soutien Electronique enregistrent la plupart du temps des mélanges de signaux radar provenant de différents émetteurs présents dans l’environnement électromagnétique. Le signal radar, décrit par un motif de modulations impulsionnelles, est alors souvent partiellement observé du fait de mesures manquantes et aberrantes. Le processus d’identification se fonde sur l’analyse statistique des paramètres mesurables du signal radar qui le caractérisent tant quantitativement que qualitativement. De nombreuses approches mêlant des techniques de fusion de données et d’apprentissage statistique ont été développées. Cependant, ces algorithmes ne peuvent pas gérer les données manquantes et des méthodes de substitution de données sont requises afin d’utiliser ces derniers. L’objectif principal de cette thèse est alors de définir un modèle de classification et partitionnement intégrant la gestion des valeurs aberrantes et manquantes présentes dans tout type de données. Une approche fondée sur les modèles de mélange de lois de probabilités est proposée dans cette thèse. Les modèles de mélange fournissent un formalisme mathématique flexible favorisant l’introduction de variables latentes permettant la gestion des données aberrantes et la modélisation des données manquantes dans les problèmes de classification et de partionnement. L’apprentissage du modèle ainsi que la classification et le partitionnement sont réalisés dans un cadre d’inférence bayésienne où une méthode d’approximation variationnelle est introduite afin d’estimer la loi jointe a posteriori des variables latentes et des paramètres. Des expériences sur diverses données montrent que la méthode proposée fournit de meilleurs résultats que les algorithmes standards.

The big scientific data generated by modern observation telescopes, raises recurring problems of performances, in spite of the advances in distributed data management systems. The main reasons are the complexity of the systems and the difficulty to adapt the access methods to the data. This thesis proposes new physical and logical optimizations to optimize execution plans of astronomical queries using transformation rules. These methods are integrated in ASTROIDE, a distributed system for large-scale astronomical data processing.ASTROIDE achieves scalability and efficiency by combining the benefits of distributed processing using Spark with the relevance of an astronomical query optimizer.It supports the data access using the query language ADQL that is commonly used.It implements astronomical query algorithms (cone search, kNN search, cross-match, and kNN join) tailored to the proposed physical data organization.Indeed, ASTROIDE offers a data partitioning technique that allows efficient processing of these queries by ensuring load balancing and eliminating irrelevant partitions. This partitioning uses an indexing technique adapted to astronomical data, in order to reduce query processing time., Les masses de données scientifiques générées par les moyens d'observation modernes, dont l’observation spatiale, soulèvent des problèmes de performances récurrents, et ce malgré les avancées des systèmes distribués de gestion de données. Ceci est souvent lié à la complexité des systèmes et des paramètres qui impactent les performances et la difficulté d’adapter les méthodes d’accès au flot de données et de traitement.Cette thèse propose de nouvelles techniques d'optimisations logiques et physiques pour optimiser les plans d'exécution des requêtes astronomiques en utilisant des règles d'optimisation. Ces méthodes sont intégrées dans ASTROIDE, un système distribué pour le traitement de données astronomiques à grande échelle.ASTROIDE allie la scalabilité et l’efficacité en combinant les avantages du traitement distribué en utilisant Spark avec la pertinence d’un optimiseur de requêtes astronomiques.Il permet l'accès aux données à l'aide du langage de requêtes ADQL, couramment utilisé.Il implémente des algorithmes de requêtes astronomiques (cone search, kNN search, cross-match, et kNN join) en exploitant l'organisation physique des données proposée.En effet, ASTROIDE propose une méthode de partitionnement des données permettant un traitement efficace de ces requêtes grâce à l'équilibrage de la répartition des données et à l'élimination des partitions non pertinentes. Ce partitionnement utilise une technique d’indexation adaptée aux données astronomiques, afin de réduire le temps de traitement des requêtes.

Graphs are ubiquitous in many fields of research ranging from sociology to biology. A graph is a very simple mathematical structure that consists of a set of elements, called nodes, connected to each other by edges. It is yet able to represent complex systems such as protein-protein interaction or scientific collaborations. Graph clustering is a central problem in the analysis of graphs whose objective is to identify dense groups of nodes that are sparsely connected to the rest of the graph. These groups of nodes, called clusters, are fundamental to an in-depth understanding of graph structures. There is no universal definition of what a good cluster is, and different approaches might be best suited for different applications. Whereas most of classic methods focus on finding node partitions, i.e. on coloring graph nodes so that each node has one and only one color, more elaborate approaches are often necessary to model the complex structure of real-life graphs and to address sophisticated applications. In particular, in many cases, we must consider that a given node can belong to more than one cluster. Besides, many real-world systems exhibit multi-scale structures and one much seek for hierarchies of clusters rather than flat clusterings. Furthermore, graphs often evolve over time and are too massive to be handled in one batch so that one must be able to process stream of edges. Finally, in many applications, processing entire graphs is irrelevant or expensive, and it can be more appropriate to recover local clusters in the neighborhood of nodes of interest rather than color all graph nodes. In this work, we study alternative approaches and design novel algorithms to tackle these different problems. The novel methods that we propose to address these different problems are mostly inspired by variants of modularity, a classic measure that accesses the quality of a node partition, and by random walks, stochastic processes whose properties are closely related to the graph structure. We provide analyses that give theoretical guarantees for the different proposed techniques, and endeavour to evaluate these algorithms on real-world datasets and use cases., Les graphes sont omniprésents dans de nombreux domaines de recherche, allant de la biologie à la sociologie. Un graphe est une structure mathématique très simple constituée d’un ensemble d’éléments, appelés nœuds, reliés entre eux par des liens, appelés arêtes. Malgré cette simplicité, les graphes sont capables de représenter des systèmes extrêmement complexes, comme les interactions entre protéines ou les collaborations scientifiques. Le partitionnement ou clustering de graphe est un problème central en analyse de graphe dont l’objectif est d’identifier des groupes de nœuds densément interconnectés et peu connectés avec le reste du graphe. Ces groupes de nœuds, appelés clusters, sont fondamentaux pour une compréhension fine de la structure des graphes. Il n’existe pas de définition universelle de ce qu’est un bon cluster, et différentes approches peuvent s’avérer mieux adaptées dans différentes situations. Alors que les méthodes classiques s’attachent à trouver des partitions des nœuds de graphe, c’est-à-dire à colorer ces nœuds de manière à ce qu’un nœud donné n’ait qu’une et une seule couleur, des approches plus élaborées se révèlent nécessaires pour modéliser la structure complexe des graphes que l’on rencontre en situation réelle. En particulier, dans de nombreux cas, il est nécessaire de considérer qu’un nœud donné peut appartenir à plus d’un cluster. Par ailleurs, de nombreux systèmes que l’on rencontre en pratique présentent une structure multi-échelle pour laquelle il est nécessaire de partir à la recherche de hiérarchies de clusters plutôt que d’effectuer un partitionnement à plat. De plus, les graphes que l’on rencontre en pratique évoluent souvent avec le temps et sont trop massifs pour être traités en un seul lot. Pour ces raisons, il est souvent nécessaire d’adopter des approches dites de streaming qui traitent les arêtes au fil de l’eau. Enfin, dans de nombreuses applications, traiter des graphes entiers n’est pas nécessaire ou est trop coûteux, et il est plus approprié de retrouver des clusters locaux dans un voisinage de nœuds d’intérêt plutôt que de colorer tous les nœuds. Dans ce travail, nous étudions des approches alternatives de partitionnement de graphe et mettons au point de nouveaux algorithmes afin de résoudre les différents problèmes évoqués ci-dessus.

This work focuses on the problem of point and variable clustering, that is the grouping of either similar vectors or similar components of a vector in a metric space. This has applications in many relevant fields including pattern recognition in image analysis or gene expression data classification. Through adequate modeling of the similarity between points or variables within a cluster we analyse the statistical properties of known clustering algorithms such as K-means.When considering homoscedastic elements for all groups the K-means algorithm is equivalent to a maximum-likelihood procedure. Otherwise the algorithm shows bias in the sense that it tends to separate groups with larger dispersion, regardless of actual group separation. By using a semi definite positive reformulation of the estimator, we suggest a pattern of correction for the algorithm that leads to the construction of computational algorithm with quasiminimax properties for hard clustering of points or variables. Those results can be studied under the classical mixture model or latent variables model, and can be extended to more general and robust class of G-block models. The stochastic controls can be made adaptive to the unknown number of classes as well as to the effective dimension of the problem. They help understand the behavior of the class of spectral estimators that are also widely used for clustering problems. They are supported by extensive simulation studies as well as data analysis stemming from the biological field.When focus is brought on the computational aspect of those algorithms, we exploit ideas based on a strong connexion with the domain of convex optimisation and specifically the technique of low-rank relaxation, of importance when dealing with high dimensional problems.; Ces travaux traitent de la problématique du partitionnement d'un ensemble d'observations ou de variables en groupes d'éléments similaires. Elle sert de nombreuses applications essentielles comme la classification de gènes en biologie ou l'apprentissage automatique en analyse d'image. Les travaux modélisent la notion de similarité entre éléments pour analyser les propriétés statistiques d'algorithmes de partitionnement, comme l'estimateur des K-moyennes. Ce dernier est équivalent au maximum de vraisemblance quand les groupes considérés sont homoscedastiques ; dans le cas contraire, on s'aperçoit que l'estimateur est biaisé, en ce qu'il tend à séparer les groupes ayant une plus grande dispersion. En utilisant une formulation équivalente qui fait intervenir l'optimisation semi-définie positive, on propose une correction opérationnelle de ce biais. On construit et étudie ainsi des algorithmes de complexité polynomiale qui sont quasi-minimax pour le partitionnement exact dans les deux contextes étudiés. Ces résultats s'interprètent dans le cadre de modèles standards comme le modèle de mélange ou le modèle à variables latentes, et s'étendent à de nouveaux modèles plus généraux et plus robustes, les modèles G-block. Les contrôles peuvent être adaptés au nombre intrinsèque de groupes, ainsi qu'à la dimension effective de l'espace des données. Ils apportent une meilleure compréhension d'estimateurs classiques du partitionnement comme les estimateurs spectraux. Ils sont appuyés par des expériences extensives sur données de synthèse, ainsi que sur des jeux de données réelles. Enfin lorsqu'on cherche à améliorer l'efficacité computationnelle des algorithmes étudiés, on peut utiliser une connexion forte avec le domaine de l'optimisation convexe et notamment exploiter des techniques de relaxation de faible rang motivées par des problématiques de grande dimension.

This work focuses on the problem of point and variable clustering, that is the grouping of either similar vectors or similar components of a vector in a metric space. This has applications in many relevant fields including pattern recognition in image analysis or gene expression data classification. Through adequate modeling of the similarity between points or variables within a cluster we analyse the statistical properties of known clustering algorithms such as K-means.When considering homoscedastic elements for all groups the K-means algorithm is equivalent to a maximum-likelihood procedure. Otherwise the algorithm shows bias in the sense that it tends to separate groups with larger dispersion, regardless of actual group separation. By using a semi definite positive reformulation of the estimator, we suggest a pattern of correction for the algorithm that leads to the construction of computational algorithm with quasiminimax properties for hard clustering of points or variables. Those results can be studied under the classical mixture model or latent variables model, and can be extended to more general and robust class of G-block models. The stochastic controls can be made adaptive to the unknown number of classes as well as to the effective dimension of the problem. They help understand the behavior of the class of spectral estimators that are also widely used for clustering problems. They are supported by extensive simulation studies as well as data analysis stemming from the biological field.When focus is brought on the computational aspect of those algorithms, we exploit ideas based on a strong connexion with the domain of convex optimisation and specifically the technique of low-rank relaxation, of importance when dealing with high dimensional problems.; Ces travaux traitent de la problématique du partitionnement d'un ensemble d'observations ou de variables en groupes d'éléments similaires. Elle sert de nombreuses applications essentielles comme la classification de gènes en biologie ou l'apprentissage automatique en analyse d'image. Les travaux modélisent la notion de similarité entre éléments pour analyser les propriétés statistiques d'algorithmes de partitionnement, comme l'estimateur des K-moyennes. Ce dernier est équivalent au maximum de vraisemblance quand les groupes considérés sont homoscedastiques ; dans le cas contraire, on s'aperçoit que l'estimateur est biaisé, en ce qu'il tend à séparer les groupes ayant une plus grande dispersion. En utilisant une formulation équivalente qui fait intervenir l'optimisation semi-définie positive, on propose une correction opérationnelle de ce biais. On construit et étudie ainsi des algorithmes de complexité polynomiale qui sont quasi-minimax pour le partitionnement exact dans les deux contextes étudiés. Ces résultats s'interprètent dans le cadre de modèles standards comme le modèle de mélange ou le modèle à variables latentes, et s'étendent à de nouveaux modèles plus généraux et plus robustes, les modèles G-block. Les contrôles peuvent être adaptés au nombre intrinsèque de groupes, ainsi qu'à la dimension effective de l'espace des données. Ils apportent une meilleure compréhension d'estimateurs classiques du partitionnement comme les estimateurs spectraux. Ils sont appuyés par des expériences extensives sur données de synthèse, ainsi que sur des jeux de données réelles. Enfin lorsqu'on cherche à améliorer l'efficacité computationnelle des algorithmes étudiés, on peut utiliser une connexion forte avec le domaine de l'optimisation convexe et notamment exploiter des techniques de relaxation de faible rang motivées par des problématiques de grande dimension.

It is primordial to establish effective and robust methods to extract pertinent information from datasets. We focus on datasets that can be represented as point clouds in some metric space, e.g. Euclidean space R^d; and that are generated according to some distribution. Of the natural questions that may arise when one has access to data, three are addressed in this thesis. The first question concerns the comparison of two sets of points. How to decide whether two datasets have been generated according to similar distributions? We build a statistical test allowing to one to decide whether two point clouds have been generated from distributions that are equal (up to some rigid transformation e.g. symmetry, translation, rotation...).The second question is about the decomposition of a set of points into clusters. Given a point cloud, how does one make relevant clusters? Often, it consists of selecting a set of k representatives, and associating every point to its closest representative (in some sense to be defined). We develop methods suited to data sampled according to some mixture of k distributions, possibly with outliers. Finally, when the data can not be grouped naturally into k clusters, e.g. when they are generated in a close neighborhood of some sub-manifold in R^d, a more relevant question is the following. How to build a system of k representatives, with k large, from which it is possible to recover the sub-manifold? This last question is related to the problems of quantization and compact set inference. To address it, we introduce and study a modification of the k-means method adapted to the presence of outliers, in the context of quantization. The answers we bring in this thesis are of two types, theoretical and algorithmic. The methods we develop are based on continuous objects built from distributions and sub-measures. Statistical studies allow us to measure the proximity between the empirical objects and the continuous ones. These methods are easy to implement in practice, when samples of points are available. The main tool in this thesis is the function distance-to-measure, which was originally introduced to make topological data analysis work in the presence of outliers., Le volume de données disponibles est en perpétuelle expansion. Il est primordial de fournir des méthodes efficaces et robustes permettant d'en extraire des informations pertinentes. Nous nous focalisons sur des données pouvant être représentées sous la forme de nuages de points dans un certain espace muni d'une métrique, e.g. l'espace Euclidien R^d, générées selon une certaine distribution. Parmi les questions naturelles que l'on peut se poser lorsque l'on a accès à des données, trois d'entre elles sont abordées dans cette thèse. La première concerne la comparaison de deux ensembles de points. Comment décider si deux nuages de points sont issus de formes ou de distributions similaires ? Nous construisons un test statistique permettant de décider si deux nuages de points sont issus de distributions égales (modulo un certain type de transformations e.g. symétries, translations, rotations...). La seconde question concerne la décomposition d'un ensemble de points en plusieurs groupes. Étant donné un nuage de points, comment faire des groupes pertinents ? Souvent, cela consiste à choisir un système de k représentants et à associer chaque point au représentant qui lui est le plus proche, en un sens à définir. Nous développons des méthodes adaptées à des données échantillonnées selon certains mélanges de k distributions, en présence de données aberrantes. Enfin, lorsque les données n'ont pas naturellement une structure en k groupes, par exemple, lorsqu'elles sont échantillonnées à proximité d'une sous-variété de R^d, une question plus pertinente est de construire un système de k représentants, avec k grand, à partir duquel on puisse retrouver la sous-variété. Cette troisième question recouvre le problème de la quantification d'une part, et le problème de l'approximation de la distance à un ensemble d'autre part. Pour ce faire, nous introduisons et étudions une variante de la méthode des k-moyennes adaptée à la présence de données aberrantes dans le contexte de la quantification. Les réponses que nous apportons à ces trois questions dans cette thèse sont de deux types, théoriques et algorithmiques. Les méthodes proposées reposent sur des objets continus construits à partir de distributions et de sous-mesures. Des études statistiques permettent de mesurer la proximité entre les objets empiriques et les objets continus correspondants. Ces méthodes sont faciles à implémenter en pratique lorsque des nuages de points sont à disposition. L'outil principal utilisé dans cette thèse est la fonction distance à la mesure, introduite à l'origine pour adapter les méthodes d'analyse topologique des données à des nuages de points corrompus par des données aberrantes

When scheduling a directed acyclic graph (DAG) of tasks on computationalplatforms, a good trade-off between load balance and data locality isnecessary. List-based scheduling techniques are commonly used greedy approachesfor this problem. The downside of list-scheduling heuristicsis that they are incapable of making short-term sacrifices for the globalefficiency of the schedule. In this work, we describe newlist-based scheduling heuristics based on clustering for homogeneousplatforms, under the realistic duplex single-port communication model. Our approach uses an acyclic partitioner for DAGs for clustering.The clustering enhances the data locality of the scheduler with a global viewof the graph. Furthermore, since the partition is acyclic, we can scheduleeach part completely once its input tasks are ready to be executed. Wepresent an extensive experimental evaluation showing the trade-offs betweenthe granularity of clustering and the parallelism, and how this affects the scheduling.Furthermore, we compare our heuristics to the best state-of-the-art list-scheduling and clustering heuristics, and obtain more than three times better makespan in caseswith many communications.; Lors de l'ordonnancement d'un graphe dirigé acyclique (DAG) de tâches sur une plate-forme, un bon compromis entre équilibrage de charge et localité des données est nécessaire.Les techniques d'ordonnancement de liste sont des approches gloutonnescommunément utilisées pour ce problème. Les inconvénients de telles heuristiques de liste sont qu'ellessont incapables de faire des sacrifices à court terme pour que l'ordonnancementglobal soit plus efficace. Dans ces travaux, nous décrivons de nouvelles heuristiques d'ordonnancement de listepour des plates-formes homogènes, avec un modèle de communications duplexe un-port réaliste. Notre approche se base sur un partitionnement acycliquedu DAG, car les parties ainsi formées permettent d'avoir une bonne localité des donnéestout en conservant une vue générale du graphe. De plus, étant donné que la partition est acyclique,nous pouvons ordonnancer chaque partie entièrement une fois que ses tâches d'entrée sont prêtes à être exécutées. Nous présentons une évaluation expérimentale des algorithmes pour montrerles compromis entre la granularité des partitions et le parallélisme, et commentcela affecte l'ordonnancement. De plus, nous comparons nos heuristiques aux meilleurscompétiteurs de la littérature, et nous obtenons un temps d’exécution total plus de trois fois meilleur dans des cas avec de nombreuses communications.

When scheduling a directed acyclic graph (DAG) of tasks on computationalplatforms, a good trade-off between load balance and data locality isnecessary. List-based scheduling techniques are commonly used greedy approachesfor this problem. The downside of list-scheduling heuristicsis that they are incapable of making short-term sacrifices for the globalefficiency of the schedule. In this work, we describe newlist-based scheduling heuristics based on clustering for homogeneousplatforms, under the realistic duplex single-port communication model. Our approach uses an acyclic partitioner for DAGs for clustering.The clustering enhances the data locality of the scheduler with a global viewof the graph. Furthermore, since the partition is acyclic, we can scheduleeach part completely once its input tasks are ready to be executed. Wepresent an extensive experimental evaluation showing the trade-offs betweenthe granularity of clustering and the parallelism, and how this affects the scheduling.Furthermore, we compare our heuristics to the best state-of-the-art list-scheduling and clustering heuristics, and obtain more than three times better makespan in caseswith many communications.; Lors de l'ordonnancement d'un graphe dirigé acyclique (DAG) de tâches sur une plate-forme, un bon compromis entre équilibrage de charge et localité des données est nécessaire.Les techniques d'ordonnancement de liste sont des approches gloutonnescommunément utilisées pour ce problème. Les inconvénients de telles heuristiques de liste sont qu'ellessont incapables de faire des sacrifices à court terme pour que l'ordonnancementglobal soit plus efficace. Dans ces travaux, nous décrivons de nouvelles heuristiques d'ordonnancement de listepour des plates-formes homogènes, avec un modèle de communications duplexe un-port réaliste. Notre approche se base sur un partitionnement acycliquedu DAG, car les parties ainsi formées permettent d'avoir une bonne localité des donnéestout en conservant une vue générale du graphe. De plus, étant donné que la partition est acyclique,nous pouvons ordonnancer chaque partie entièrement une fois que ses tâches d'entrée sont prêtes à être exécutées. Nous présentons une évaluation expérimentale des algorithmes pour montrerles compromis entre la granularité des partitions et le parallélisme, et commentcela affecte l'ordonnancement. De plus, nous comparons nos heuristiques aux meilleurscompétiteurs de la littérature, et nous obtenons un temps d’exécution total plus de trois fois meilleur dans des cas avec de nombreuses communications.

The rise of AFDX networks as a communication infrastructure between on-board equipment of civil aircraft motivates many research projects to reduce communication delays while guaranteeing a high level of determination and quality of service. This thesis deals with the effect of the back-ot-back frame reception on the reception End System, in particular, on the internal buffer, in order to guarantee a non-loss of frames and optimal memory dimensioning. A worst-case modeling of the frame flow is carried out according to a first pessimistic method, based on a periodic frame flow. Then a more optimistic method is presented based on the reception intervals and an iterative frame placement. A probabilistic study implements Gaussian distributions to evaluate the occurrence probabilities of the worst back-to-back frames and provides an illumination that opens a discussion on the relevance of not considering the worst-case modeling to size the reception buffer. Additional memory gain can be achieved by implementing LZW lossless compression., L’essor des réseaux AFDX comme infrastructure de communication entre les équipements de bord des aéronefs civils motive de nombreux travaux de recherche pour réduire les délais de communication tout en garantissant un haut niveau de déterminisme et de qualité de service. Cette thèse traite de l’effet des accolements de trames sur l’End System de réception, notamment sur le buffer interne afin de garantir une non perte de trames et un dimensionnement mémoire optimal. Une modélisation pire cas du flux de trames est réalisée selon une première méthode pessimiste, basée sur un flux de trames périodiques ; puis une seconde, plus optimiste, basée sur des intervalles de réception et un placement de trames itératif. Une étude probabiliste met en œuvre des distributions gaussiennes pour évaluer les probabilités d’occurrences des pires cas d’accolements et apporte un éclairage qui ouvre une discussion sur la pertinence de ne considérer que la modélisation pire cas pour dimensionner le buffer de réception. Un gain mémoire supplémentaire peut être obtenu par la mise en œuvre de la compression sans perte LZW.

Blockchains have a storage scalability issue. Their size is not bounded and they grow indefinitely as time passes. As of August 2017, the Bitcoin blockchain is about 120 GiB big while it was only 75 GiB in August 2016. To benefit from Bitcoin full security model, a bootstrapping node has to download and verify the entirety of the 120 GiB. This poses a challenge for low-resource devices such as smartphones. Thankfully, an alternative exists for such devices which consists of downloading and verifying just the header of each block. This partial block verification enables devices to reduce their bandwidth requirements from 120 GiB to 35 MiB.However, this drastic decrease comes with a safety cost implied by a partial block verification. In this work, we enable low-resource devices to fully verify subchains of blocks without having to pay the onerous price of a full chain download and verification; a few additional MiB of bandwidth suffice. To do so, we propose the design of diet nodes that can securely query full nodes for shards of the UTXO set, which is needed to perform full block verification and can otherwise only be built by sequentially parsing the chain.; Les blockchains telles que Bitcoin passent mal à l’échelle, notamment du fait de leurs besoins important de stockage. Les besoins de stockage d’une blockchain typique ne sont pas limités et croissent indéfiniment. Par exemple, en août 2017, les données contenues dans la blockchainBitcoin représentaient environ 120 GiB, contre 75 GiB un an auparavant, en août 2016. Pour bénéficier des garanties complètes de sécurité apportées par Bitcoin, un noeud qui rejoint le réseau doit télécharger et vérifier l’intégralité des 120 GiB de données. Cette nécessité pose un défi pour les appareils à faibles ressources tels que les smartphones. Heureusement, une alternative existe pour de tels dispositifs qui consiste à télécharger et à vérifier seulement l’en-tête de chaque bloc de la blockchain. Cette vérification partielle des blocs permet aux appareils de réduire leurs besoins en bande passante de 120 GiB à 35 MiB, mais cette diminution drastique ne permet qu’une vérification partielle des blocs, et diminue grandement les garanties de sécurité offertes aux noeuds qui l’utilisent.Dans ce travail, nous proposons une approche qui permet aux appareils à faibles ressources de vérifier entièrement des sous-chaînes de blocs sans avoir à payer le prix onéreux d’un téléchargement et d’une vérification complète de la chaîne ; quelques MiB supplémentaires de bande passante suffisent. Pour ce faire, nous proposons d’introduire des noeuds Dietcoin qui sont capables en toute sécurité d’interroger des noeuds exécutant le protocole complet pour obtenir des fragments d’un ensemble appelé UTXO, nécessaire à la vérification complète des blocs.

Synopsis Chromosome and plasmid segregation in bacteria are mostly driven by ParABS systems. These DNA partitioning machineries rely on large nucleoprotein complexes assembled on centromere sites (parS). However, the mechanism of how a few parS-bound ParB proteins nucleate the formation of highly concentrated ParB clusters remains unclear despite several proposed physico-mathematical models. We discriminated between these different models by varying some key parameters in vivo using the F plasmid partition system. We found that "Nucleation & caging" is the only coherent model recapitulating in vivo data. We also showed that the stochastic self-assembly of partition complexes (i) is a robust mechanism, (ii) does not directly involve ParA ATPase, (iii) results in a dynamic structure of discrete size independent of ParB concentration, and (iv) is not perturbed by active transcription but is by protein complexes. We refined the "Nucleation & caging" model and successfully applied it to the chromosomally encoded Par system of Vibrio cholerae, indicating that this stochastic self-assembly mechanism is widely conserved from plasmids to chromosomes.

In Press, Corrected Proof; Downstream processing is a major cost in the production of macromolecules, including proteins and enzymes. Thus, development of efficient and economical downstream processing strategies has become an important area in microbiology, biochemistry and biotechnology. The trend is to develop protocols, which have fewer steps, do not require any preprocessing and have unit processes, which integrate well. This chapter deals with these aspects and explores one of the interesting aqueous separation methods, Three Phase Partitioning (TPP), as an emerging nonchromatography technique for the extraction and recovery of macromolecules from different biological sources. This chapter serves as a one-stop-reference by highlighting the application of TPP to purify macromolecules of interest and its potential use for studying extremophiles, mainly to prepare small quantities of molecules for early-stage exploratory research. TPP is proposed as a fast, one-step recovery tool to be used during screening of macromolecules from microorganisms of atypical environments as it can be easily used in downstream purification processes where it magnifies the advantages of the process. The chapter further summarizes the partitioning mechanisms of TPP, the main factors influencing the recovery process and also the variants and unique characteristics of TPP as an emerging elegant nonchromatographical tool for the separation and recovery of macromolecules from different sources, including fermentation broths and extremophile microorganisms.

Le cadmium (Cd) est un élément trace présent dans les sols agricoles qui contamine la chaîne alimentaire en étant prélevé par les plantes et accumulé dans les produits végétaux consommés. La biodisponibilité du Cd est un concept au cœur de l’évaluation des risques de transfert excessif du Cd du sol vers les plantes. Les plantes prélevant essentiellement l’ion Cd2+ dans la solution de sol, la biodisponibilité est fonction de deux principaux processus, la spéciation du Cd en solution (les différentes formes chimiques prises par le Cd en solution) et le partitionnement du Cd2+ entre la phase solide et la solution. L’objectif principal de ce travail a été d’élaborer des modèles simples à visée opérationnelle prédictifs de la concentration en Cd2+ dans la solution de sols agricoles, en modélisant soit la spéciation du Cd en solution de sol, soit le partitionnement phase solide-solution du Cd2+, celui-ci permettant de renseigner en outre la capacité de la phase à réapprovisionner la solution de sol lors de l’absorption racinaire. Nous avons également recherché des modèles pour la prédiction des teneurs en Cd2+ retrouvées dans les grains de blé dur. Nous avons développé deux approches de modélisation. La première, statistique, permet de produire des modèles simples à visée opérationnelle. La seconde, géochimique, permet de comprendre les mécanismes dominants et donc de juger de la cohérence de modèles statistiques simples pour représenter des processus physico-chimiques complexes. Ces deux approches ont montré de manière cohérente que pour les sols agricoles faiblement contaminés, le Cd qui s’échange entre la phase solide et la solution est vraisemblablement sorbé faiblement et peut-être estimé par le Cd extrait par NH4NO3 1 M minoré par une fraction fixée à des oxydes de manganèse. Les modélisations ont également montré l’importance du pH et de la teneur en Ca en solution comme variables contrôlant la solubilité de Cd2+, probablement en raison de leur rôle à régir la disponibilité des sites de sorption et de complexation vis-à-vis du Cd. Le modèle statistique le plus performant pour prédire la teneur en Cd dans le grain de blé dur reprend également ces variables, suggérant ainsi que les modèles statistiques simples de prédiction de la spéciation en solution et de partitionnement sol-solution du Cd sont des modèles pertinents pour estimer la biodisponibilité et qu’ils peuvent permettre de classer des sols en fonction des risques de transfert du Cd du sol vers une culture. Par rapport à l’évolution du contexte réglementaire, le modèle statistique prédictif de la teneur en Cd dans le grain a montré par validation croisée qu’il pourrait discerner de façon assez fiable (88 %) des différences de 0.05 mg Cd.kg-1 de grain et que sa fiabilité serait moindre (65 %) pour des différences de 0.025 mg Cd.kg-1., Cadmium (Cd) is a trace element found in agricultural soils which can contaminate the food chain by being taken up by plants and accumulated in consumed plant products. The bioavailability of Cd is a concept at the centre of the risk assessment of Cd transfer from soil to plants. Plants, taking up essentially the free form of Cd (Cd2+) in the soil solution, bioavailability is a function of two main processes, the Cd speciation in solution (the different chemical forms taken by the Cd in solution) and the partitioning of Cd2+ between the solid phase and the solution. The main objective of this work was to develop simple predictive operational models of Cd2+ concentrations in agricultural soil solution, by modelling either Cd speciation in soil solution or Cd2+ solid-solution partitioning, the latter to further inform the ability of the phase to replenish the soil solution during root absorption. We also looked for models for the prediction of Cd2+ levels found in durum wheat grains. We have developed two modelling approaches. The first, statistical, allows to produce simple models for operational purposes. The second, geochemical, allows to understand the dominant mechanisms and thus to judge the coherence of simple statistical models to represent complex physicochemical processes. These two approaches have consistently shown that for poorly contaminated agricultural soils, the exchanged Cd between the solid phase and the solution is likely to be weakly sorbed and can be estimated by the Cd extracted by 1M NH4NO3 minus a fraction attached to amorphous manganese oxides. Modelling also showed the importance of pH and Ca content in solution as variables controlling the solubility of Cd2+, probably because of their role in controlling the sorption site availability and Cd complexation. The best-performing statistical model for predicting Cd content in durum wheat also picks up these variables, suggesting that simple statistical models for speciation in solution and soil-solution partitioning of Cd are relevant models to estimate bioavailability and that they can be used to classify soils according to the risks of the transfer of soil Cd to a crop. Compared to the evolution of the regulatory context, the statistical model predictive of the Cd content in the grain shown by cross validation that it could discern relatively reliably (88%) the differences of 0.05 mg Cd.kg-1 of grain and that its reliability would be less (65%) for differences of 0.025 mg Cd.kg-1.

Adaptive systems based on Field-Programmable Gate Arrays (FPGA) architectures can benefit greatly from the high degree of flexibility offered by dynamic partial reconfiguration (DPR). Thanks to DPR, hardware tasks composing an adaptive system can be allocated and relocated on demand or depending on the dynamically changing environment. Existing design flows and commercial tools have evolved to meet the requirements of reconfigurables architectures, but that are limited in functionality. These tools do not allow an efficient placement and relocation of variable-sized hardware tasks. The main objective of this thesis is to propose a new methodology and a new approaches to facilitate to the designers the design phase of an adaptive and reconfigurable system and to make it operational, valid, optimized and adapted to dynamic changes in the environment. The first contribution of this thesis deals with the issues of relocation of variable-sized hardware tasks. A design methodology is proposed to address a major problem of relocation mechanisms: storing a single configuration bitstream to reduce memory requirements and increasing the reusability of generating hardware modules. A reconfigurable region partitioning technique is applied in this proposed relocation methodology to increase the efficiency of use of hardware resources in the case of reconfigurable tasks of variable sizes. This methodology also takes into account communication between different reconfigurable regions and the static region. To validate the design method, several cases studies are implemented. This validation shows an efficient use of hardware resources and a significant reduction in reconfiguration time. The second part of this thesis presents and details a mathematical formulations in order to automate the floorplanning of the reconfigurable regions in the FPGAs. The algorithms presented in this thesis are based on the optimization technique MILP (mixed integer linear programming). These algorithms allow to define automatically the location, the size and the shape of the dynamic reconfigurable region. We are mainly interested in this research to satisfy the constraints of placement of the reconfigurable zones and those related to the relocation. In addition, we consider the optimization of the hardware resources in the FPGA taking into account the tasks of variable sizes. Finally, an evaluation of the proposed approach is presented, Les systèmes adaptatifs basés sur les architectures FPGA (Field-Programmable Gate Arrays) peuvent bénéficier grandement de la grande flexibilité offerte par la reconfiguration partielle dynamique (DPR). Grâce au DPR, les tâches matérielles composant un système adaptatif peuvent être allouées et re-allouées à la demande ou en fonction de l'environnement dynamique. Les flots de conceptions disponibles et les outils commerciaux ont évolué pour répondre aux exigences des architectures reconfigurables qui sont toutefois limitées dans leurs fonctionnalités. Ces outils ne permettent pas un placement et une relocation efficaces de tâches matérielles de tailles variables. L'objectif principal de ces travaux de thèse consiste à proposer des nouvelles méthodologies et de nouvelles approches pour faciliter au concepteur la phase de conception d'un système adaptatif reconfigurable opérationnelle, valide, optimisé et adapté aux changements dynamiques de l'environnement. La première contribution de cette thèse porte sur la problématique de la relocation des tâches matérielles de tailles différentes. Une méthodologie de conception est proposée pour répondre à un problème majeur des mécanismes de relogement : le stockage d'une unique bitstream de configuration pour réduire les besoins de la mémoire et pour accroître la réutilisable des modules matériels générés. Une technique de partitionnement de la région reconfigurable est appliquée dans la méthodologie de relogement proposée pour augmenter l'efficacité d'utilisation des ressources matérielles dans le cas des tâches reconfigurables de tailles variables. Cette méthodologie prend en compte aussi la communication entre différentes régions reconfigurables et la région statique. Pour valider la méthode, plusieurs études de cas sont implémentées. Cette validation montre une utilisation efficace des ressources matérielles ainsi une réduction importante du temps de reconfiguration. La deuxième partie de cette thèse présente et détaille une formulation mathématique afin d'automatiser le floorplanning des zones reconfigurables dans les FPGAs. Les algorithmes de recherche présentés dans cette thèse sont basés sur la technique d'optimisation PLMNE (programmation linéaire mixte en nombres entiers). Ces algorithmes permettent de définir automatiquement l'emplacement, la taille et la forme de la zone reconfigurable dynamique. Nous nous intéressons principalement dans cette recherche à la satisfaction des contraintes de placement des zones reconfigurables et celles liées à la relocation. De plus, nous considérons l’optimisation des ressources matérielles dans le FPGA en tenant compte des tâches de tailles variables. Finalement, une évaluation de l'approche proposée est présentée

Adaptive systems based on Field-Programmable Gate Arrays (FPGA) architectures can benefit greatly from the high degree of flexibility offered by dynamic partial reconfiguration (DPR). Thanks to DPR, hardware tasks composing an adaptive system can be allocated and relocated on demand or depending on the dynamically changing environment. Existing design flows and commercial tools have evolved to meet the requirements of reconfigurables architectures, but that are limited in functionality. These tools do not allow an efficient placement and relocation of variable-sized hardware tasks. The main objective of this thesis is to propose a new methodology and a new approaches to facilitate to the designers the design phase of an adaptive and reconfigurable system and to make it operational, valid, optimized and adapted to dynamic changes in the environment. The first contribution of this thesis deals with the issues of relocation of variable-sized hardware tasks. A design methodology is proposed to address a major problem of relocation mechanisms: storing a single configuration bitstream to reduce memory requirements and increasing the reusability of generating hardware modules. A reconfigurable region partitioning technique is applied in this proposed relocation methodology to increase the efficiency of use of hardware resources in the case of reconfigurable tasks of variable sizes. This methodology also takes into account communication between different reconfigurable regions and the static region. To validate the design method, several cases studies are implemented. This validation shows an efficient use of hardware resources and a significant reduction in reconfiguration time. The second part of this thesis presents and details a mathematical formulations in order to automate the floorplanning of the reconfigurable regions in the FPGAs. The algorithms presented in this thesis are based on the optimization technique MILP (mixed integer linear programming). These algorithms allow to define automatically the location, the size and the shape of the dynamic reconfigurable region. We are mainly interested in this research to satisfy the constraints of placement of the reconfigurable zones and those related to the relocation. In addition, we consider the optimization of the hardware resources in the FPGA taking into account the tasks of variable sizes. Finally, an evaluation of the proposed approach is presented; Les systèmes adaptatifs basés sur les architectures FPGA (Field-Programmable Gate Arrays) peuvent bénéficier grandement de la grande flexibilité offerte par la reconfiguration partielle dynamique (DPR). Grâce au DPR, les tâches matérielles composant un système adaptatif peuvent être allouées et re-allouées à la demande ou en fonction de l'environnement dynamique. Les flots de conceptions disponibles et les outils commerciaux ont évolué pour répondre aux exigences des architectures reconfigurables qui sont toutefois limitées dans leurs fonctionnalités. Ces outils ne permettent pas un placement et une relocation efficaces de tâches matérielles de tailles variables. L'objectif principal de ces travaux de thèse consiste à proposer des nouvelles méthodologies et de nouvelles approches pour faciliter au concepteur la phase de conception d'un système adaptatif reconfigurable opérationnelle, valide, optimisé et adapté aux changements dynamiques de l'environnement. La première contribution de cette thèse porte sur la problématique de la relocation des tâches matérielles de tailles différentes. Une méthodologie de conception est proposée pour répondre à un problème majeur des mécanismes de relogement : le stockage d'une unique bitstream de configuration pour réduire les besoins de la mémoire et pour accroître la réutilisable des modules matériels générés. Une technique de partitionnement de la région reconfigurable est appliquée dans la méthodologie de relogement proposée pour augmenter l'efficacité d'utilisation des ressources matérielles dans le cas des tâches reconfigurables de tailles variables. Cette méthodologie prend en compte aussi la communication entre différentes régions reconfigurables et la région statique. Pour valider la méthode, plusieurs études de cas sont implémentées. Cette validation montre une utilisation efficace des ressources matérielles ainsi une réduction importante du temps de reconfiguration. La deuxième partie de cette thèse présente et détaille une formulation mathématique afin d'automatiser le floorplanning des zones reconfigurables dans les FPGAs. Les algorithmes de recherche présentés dans cette thèse sont basés sur la technique d'optimisation PLMNE (programmation linéaire mixte en nombres entiers). Ces algorithmes permettent de définir automatiquement l'emplacement, la taille et la forme de la zone reconfigurable dynamique. Nous nous intéressons principalement dans cette recherche à la satisfaction des contraintes de placement des zones reconfigurables et celles liées à la relocation. De plus, nous considérons l’optimisation des ressources matérielles dans le FPGA en tenant compte des tâches de tailles variables. Finalement, une évaluation de l'approche proposée est présentée

With the advent of the Big Data era come new challenges for Information Visualization. First, the amount of data to be visualized exceeds the available screen space. Second, the data cannot be stored and processed on a conventional computer. To alleviate both of these problems, a Big Data visualization system must provide perceptual and performance scalability. In this thesis, we propose to use multi-scale abstractions as a solution to both of these issues. Several levels of detail can be precomputed using a Big Data Infrastructure in order to visualize big datasets up to several billion points. For that, we propose two approaches to implementing the canopy clustering algorithm for a distributed computation cluster. We present applications of our method to geolocalized data visualized through a heatmap, and big graphs. Both of these applications use the dynamic visualization library, which is also presented in this thesis, L’augmentation de la quantité de données à visualiser due au phénomène du Big Data entraîne de nouveaux défis pour le domaine de la visualisation d’information. D’une part, la quantité d’information à représenter dépasse l’espace disponible à l’écran, entraînant de l’occlusion. D’autre part, ces données ne peuvent pas être stockées et traitées sur une machine conventionnelle. Un système de visualisation de données massives doit permettre la scalabilité de perception et de performances. Dans cette thèse, nous proposons une solution à ces deux problèmes au travers de l’abstraction multi-échelle des données. Plusieurs niveaux de détail sont précalculés sur une infrastructure Big Data pour permettre de visualiser de grands jeux de données jusqu’à plusieurs milliards de points. Pour cela, nous proposons deux approches pour implémenter l’algorithme de canopy clustering sur une plateforme de calcul distribué. Nous présentons une application de notre méthode à des données géolocalisées représentées sous forme de carte de chaleur, ainsi qu’à des grands graphes. Ces deux applications sont réalisées à l’aide de la bibliothèque de visualisation dynamique Fatum, également présentée dans cette thèse.

In subduction zones, the 3D geometry of the plate interface is one of the key parameters that controls margin tectonic deformation, interplate coupling and seismogenic behavior. The North American plate subducts below the Caribbean plate with a convergence rate of 20 mm/y. The seismic activity is heterogeneous and increases locally under the Virgin Islands platform. The northward increasing convergence obliquity is favorable in partitioning which deformations were not really observed. This PhD confirms that the forearc crust is a crust of oceanic affinity thickened by hotspot magmatism and poorly affected by subduction magmatism. Two structures accommodating the partitioning of the deformation were identified. The Bunce Fault is a 850-kmlength sinistral strike-slip fault extending from Hispaniola to the east of Barbuda decoupling the accretionary prism from the Caribbean substratum. The Anegada Passage, whose extension towards the NE is highlighted, entailed deeply the forearc. The structures are reactivated in sinistral strike-slip faults compatible with the partitioning of the deformation after formation in extension due to the collision of the Bahamas Bank with the northern margin. We image for the first time the characteristics of a slow ridge formation (partly complex core and partly oceanic grain) entering in subduction. It affects the morphology of the accretion prism and probably the seismogenic potential of the subduction interface. We have highlighted a shallower slab which is located under the NE Anegada Passage and where earthquakes and partitioning deformations increase locally. Thus, the shallowing slab might results in a local greater interplate coupling favoring seismic activity and tectonic partitioning beneath the Anegada Passage., Dans les zones de subduction, la géométrie du slab est l'un des paramètres qui contrôle les déformations tectoniques de la marge, le couplage et le potentiel sismogénique. La subduction des Antilles résulte du chevauchement de la plaque Caraïbe vers le NE sur les plaques Amériques, à une vitesse de convergence de 2 cm/an. La sismicité est hétérogène et augmente localement sous la plateforme des Iles Vierges. D’une obliquité croissante vers le nord, cette zone est favorable à un partitionnement dont les déformations sont très peu observées. Ces travaux ont permis de confirmer un substratum d’une affinité de croûte océanique épaissie par un panache mantellique et faiblement épaissi par le magmatisme formant les arcs volcaniques Deux structures accommodant le partitionnement de la déformation ont été mis en évidence. La faille de Bunce est une faille décrochante sénestre de 850 km s’étendant d’Hispaniola jusqu’à Barbuda découplant le prisme d’accrétion du substratum. Le Passage d’Anegada, dont nous avons découvert son extension vers le NE, entaille profondément l’avant-arc. Formé par extension due à la collision du Banc des Bahamas sur le nord de la marge caribéenne, ces structures sont réactivées en décrochement sénestre compatible avec du partitionnement. Les caractéristiques d’une dorsale lente (core complexe et grain océanique) entrant en subduction sont imagées pour la première fois. Elles affectent probablement la morphologie du prisme d’accrétion et le potentiel sismogène. Là où les séismes et les déformations de partitionnement (Passage d’Anegada) s'accentuent localement, le slab est moins profond. Ainsi, le couplage interplaque pourrait augmenter localement et favoriser l'activité sismique et le partitionnement tectonique sous le Passage d'Anegada.

Énumérer une collection, c'est traiter une fois et un seule chaque élément de cette collection. Pour que cette contrainte soit réalisée (une fois et une seule), il va falloir que l'élève s'organise et mette en place des stratégies. De nombreux chercheurs ont développé les difficultés rencontrées dans des situations d'énumération dans le plan et ont analysé les différentes stratégies et procédures mises en place pour réussir cette tâche. Qu'en est-il alors de l'énumération des faces d'un solide ? La situation que nous proposons de travailler immerge le sujet dans un espace 3D où les éléments que l'on cherche à dénombrer ne sont plus organisés dans le plan mais dans l'espace. Notre objectif est donc de savoir dans quelle mesure tout ce que l'on sait sur l'énumération d'une collection dans le plan va être encore robuste dans un espace 3D.

Given G=(V,E) a connected undirected graph and a positive integer β(n), where n is number ofvertices, the vertex separator problem (VSP) is to find a partition of V into three classes A,B and Csuch that there is no edge between A and B, max{|A|,|B|}less than or equal β(n), and |C| isminimum. In this thesis, we consider aninteger programming formulation for this problem. Wedescribe some valid inequalties and using these results to develop algorithms based onneighborhood scheme.We also study st-connected vertex separator problem. Let s and tbe two disjoint vertices of V, notadjacent. A st-connected separator in the graph G is a subset S of V\{s,t} such that there are no morepaths between sand tin G[G\S] and the graph G[S] is connected . The st-connected vertex speratorproblem consists in finding such subset with minimum cardinality. We propose three formulationsfor this problem and give some valid inequalities for the polyhedron associated with this problem.We develop also an efficient heuristic to solve this problem., Étant donné G = (V, E) un graphe non orienté connexe et un entier positif β (n), où n est le nombrede sommets de G, le problème du séparateur (VSP) consiste à trouver une partition de V en troisclasses A, B et C de sorte qu'il n'y a pas d'arêtes entre A et B, max {| A |, | B |} est inférieur ou égal àβ (n) et | C | est minimum. Dans cette thèse, nous considérons une modélisation du problème sous laforme d'un programme linéaire en nombres entiers. Nous décrivons certaines inégalités valides et etdéveloppons des algorithmes basés sur un schéma de voisinage.Nous étudions également le problème du st-séparateur connexe. Soient s et t deux sommets de Vnon adjacents. Un st-séparateur connexe dans le graphe G est un sous-ensemble S de V \ {s, t} quiinduit un sous-graphe connexe et dont la suppression déconnecte s de t. Il s'agit de déterminer un stséparateur de cardinalité minimum. Nous proposons trois formulations pour ce problème et donnonsdes inégalités valides du polyèdre associé à ce problème. Nous présentons aussi une heuristiqueefficace pour résoudre ce problème.

Discrete-event simulation, in a context of DEVS formalism, has been experiencing a boom over the recent years. In a situation of increasing demand in terms of model size and consequently in calculation time, it is necessary to build up tools to ensure optimality, or even better, an excellent response to simulation times.Admittedly, there exist parallelization and distribution tools like PDEVS, but the distribution of models within compute nodes is under the modeler s sole responsability.The Ph.D. main scope is to propose an optimization approach of parallel and distributed simulation times, restructuring the hierarchy of models. The new founded hierarchy can thus guarantee a simultaneous execution of a maximum quantity of atomic models while minimizing the number of exchanges between models, which are not associated with the same calculation node (i.e. with the same sub-model). Accordingly, optimizing simulation time goes through a simultaneous implementation of a maximum quantity of atomic models, but in a distributed context it is highly important to minimize the adaptation transfer via the network to avoid overcharges related to its use. Ther exist deifferent ways of structuring a DEVS model : some scientist use a multi-leveled hierarchical structure, and others opt for a "flat" structure. Our objective focuses on the latter. Indeed, it is possible to obtain a single graph of models, corresponding to the connection network linking all the atomic models. From this graph the creation of a model hierarchy optimized by the distributed simulation focuses on the partitioning of this model graph. In such cases, the graph theory reveals a certain numbers of tools to partition the graph to meet some constraints. In our study, the resulting model partition must not only balance calculation needs but also minimize the message transfer between sub-models. The Ph.D. main scope it to propose not only an optimization approach but also partitioning and learning tools to achieve full compliance in our processing methods. In such cases, the model graph using the flat structure does not provide us with all the necessary information related to partitioning. That is the reason whi it is highly necessary to assign a weighting in the graph that best reflects the individual dynamics of models composing it. This weighting comes from learning, using the Hidden Markov Models (HMM). The use of learning in DEVS context results in some adjustments ti consider all the specificities. The thesis also ensures the complete validation phase, either in a parallel context to validate the simulation node behavior and observe the limits of atomic model behavior, or in a distributed context. This dissertation in its final state also includes a pratice-oriented approach to sustainably manage potato blight. The current fungus Phytophthora infestans simulation model is conceived for a plot scale. In collacoration with agronomists, we provide a few changes to update the Phytophthora infestans model to extend the scope of action and propose a new scale of values., La simulation à évènements discrets, dans le contexte du formalisme DEVS, est en plein essor depuis quelques années. Face à une demande grandissante en terme de taille de modèles et par conséquent en temps de calcul, il est indispensable de construire des outils tel qu'ils garantissent une optimalité ou au mieux une excellente réponse en terme de temps de simulations. Certes, des outils de parallélisation et de distribution tel que PDEVS existent, mais la répartition des modèles au sein des noeuds de calculs reste entièrement à la charge du modélisateur. L'objectif de cette thèse est de proposer une démarche d'optimisation des temps de simulation parallèle et distribuée, en restructurant la hiérarchie de modèles. La nouvelle hiérarchie ainsi créée doit garantir une exécution simultanée d'un maximum de modèles atomiques, tout en minimisant le nombre d'échanges entre modèles n'appartenant pas au même noeud de calculs (i.e. au même sous-modèle). En effet, l'optimisation des temps de simulation passe par une exécution simultanée d'un maximum de modèles atomiques, mais dans un contexte distribué, il est important de minimiser le transfert d'évènements via le réseau pour éviter les surcoûts liés à son utilisation. Il existe différentes façons de structurer un modèle DEVS : certains utilisent une structure hiérarchique à plusieurs niveaux, d'autres optent pour une structure dite "à plat". Notre approche s'appuie sur cette dernière. En effet, il est possible d'obtenir un unique graphe de modèles, correspondant au réseau de connexions qui lient l'ensemble des modèles atomiques. À partir de ce graphe, la création d'une hiérarchie de modèles optimisée pour la simulation distribuée repose sur le partitionnement de ce graphde de modèles. En effet, la théorie des graphes offre un certain nombre d'outils permettant de partitionner un graphe de façon à satisfaire certaines contraintes. Dans notre cas, la partition de modèles obtenue doit être équilibrée en charge de calcul et doit minimiser le transfert de messages entre les sous-modèles. L'objectif de cette thèse est de présenter la démarche d'optimization, ainsi que les outils de partitionnement et d'apprentissage utilisés pour y parvenir. En effet, le graphe de modèles fournit par la structure à plat ne contient pas toutes les informations nécessaires au partitionnement. C'est pourquoi, il est nécessaire de mettre en place une pondération de celui qui reflète au mieux la dynamique individuelle des modèles qui le compose. Cette pondération est obtenue par apprentissage, à l'aide de chaînes de Markov cachées (HMM). L'utilisation de l'apprentissage dans un contexte DEVS a nécessité quelques modifications pour prendre en compte toutes ces spécificités. Cette thèse présente également toute une phase de validation : à la fois, dans un contexte parallèle dans le but de valider le comportement du noyau de simulation et d'observer les limites liées au comportement des modèles atomiques, et d'autre part, dans un contexte distribué. Pour terminer, cette thèse présente un aspect applicatif lié à la gestion durable du mildiou de la pomme de terre. Le modèle mildiou actuel est conçu pour être utilisé à l'échelle de la parcelle. En collaboration avec des agronomes, nous proposons d'apporter quelques modifications à ce dernier pour étendre son champ d'action et proposer une nouvelle échelle spatiale.

This manuscript is partitioned in three parts. The first one is written in French and contains an extended resume. I start by briefly presenting my main teaching activities as well as my main contributions to the formation proposed at ENSEM. An important part summarizes my research activity startingwith the contributions of my Ph.D. thesis and finishing with the last results that I obtained at CRAN. The presentation includes the list of Ph.D. and Master students that I supervised. This part also contains complete lists of grants and publications in which I was involved.For the sake of accessibility, the last two parts of the manuscript are written in English.The second part of this work provides a selection of results that I obtained on the topic of multi-agent systems. The basis of this research is the fact that real large-scale networks are partitioned in several clusters. The first question that arises in this context is related to the cluster detection in a decentralized way. It is also natural to analyze these networks from the perspective of continuous interactions inside clusters and sporadic-discrete ones outside. The first chapter is dedicated to the description of the basic concepts and the main results existing in the consensus literature. Chapter 2 presents a class of discrete time multi-agent systems modeling opinion dynamics with decaying confidence. This opinion dynamics model is applied to address the problem of community detection in graphs. Basically the convergence speed is higher inside clusters and the decaying confidence allows to cut the links between different clusters. Chapter 3 addresses the problem of coordination in heterogeneous networks containing both linear and linear impulsive agents. Precisely we assume that several clusters/communities exist in the network. The agents inside one cluster can continuously interact with each others. On top of this, few agents in each cluster can interact at some discrete time instants outside their own cluster. We finish the presentation with one part containing some of my research perspectives. A first research direction of my future works is at the intersection of singular perturbation theory and multi-agent systems’ analysis. Two different aspects will be addressed. The first one is directly related to the results presented in Part 2. Precisely, the presence of clusters in the network generates, as pointed out before, a time-scale separation. In other words, the agents will agree faster inside a cluster than in the whole network. The second aspect considers the consensus problem in networks of singularly perturbed agentse.g. whose state components evolve on different time-scales. A second research direction focusses on the analysis of opinion dynamics in social networks. We propose a consensus like model based on quantized information about the neighbors opinion. The main advantages of this model are that it capturesoscillatory behaviors of opinions as well as the dissensus in the network.

International audience; L'exécution de simulations numériques sur des supercalculateurs nécessite de distribuer les données à traiter sur les différentes unités de calcul disponibles. Cette étape est réalisée à l'aide d'outils de partitionnement classiques, qui ont pour but d'équilibrer les temps de calcul sur chaque unité. Cependant, l'espace mémoire de chaque unité de calcul ayant tendance à diminuer sur les calculateurs modernes, il devient nécessaire de prendre en compte la consommation mémoire de manière explicite lors du calcul du partitionnement. Or les approches classiques ne le permettent pas car une grande partie des simulations mettent en œuvre des schémas numériques de type éléments ou volumes finis. Ces méthodes utilisent une distribution des données avec recouvrement (mailles fantômes) et cette duplication de données n'est pas représentable par un simple partitionnement de graphes. Nous proposons une nouvelle modélisation du problème de partitionnement de maillages avec une prise en compte explicite de la contrainte mémoire et, à l'aide de la programmation linéaire en nombres entiers, nous la comparons avec les formulations classiques du partitionnement.

International audience; 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.

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.

I focus on three major oblique transform faults in Tibet and in Southern California, in order to better measure and quantify the present-day strain accumulation on these structures. Interferometric synthetic Aperture Radar (InSAR) has the potential to map and localize precisely the deformation over wide areas and thus constrain the deep geometry of these structures. However, its application in natural environments in hindered by strong decorrelation of the radar phase due to vegetation, relief, and freeze and thaw cycles, but also due to variable tropospheric phase delays across topographic feature and long-wavelength residual orbital ramps. Here, I develop methodologies to circumvent these limitations and separate tectonic from other parasite signals. In Tibet, I process data from the Envisat satellite archives, at the boundary of the Tibetan plateau, in two seismic gaps, which appear interesting to study the partitioning of the convergence: the Haiyuan Fault system in northeastern Tibet and the left-lateral Altyn Tagh Fault, in northwestern Tibet. A specific focus on the permafrost related deformation signal allows us to: (1) correctly unwrap interferograms from north to south, (2) quantify the temporal behavior of the freeze/thaw cycles, and (3) isolate bedrock pixels that are not affected by the permafrost signal for further tectonic analysis. I show that the seasonal subsidence depends greatly on the geological land unit and that lower elevations are thawing faster than higher elevations. I analyze the atmospheric signal across the high plateau margin and estimate proxy for the uncertainty on atmospheric corrections. I observe a strike-slip deformation of around 11-15 mm/yr across the Altyn Tagh fault, a clear line of concentrated strike-slip deformation of around 3 mm/yr within the Tarim basin, trending parallel to the Altyn Tagh Fault trace, as well as thrust signal uplifting terraces at a rate of 1 mm/yr. This work also shows a strain accumulation around the west extension of the south trace of the Kunlun Fault, redefining the block boundaries in northwestern Tibet. In parallel this data acquisition, I develop Monte Carlo inversion tools in order to explore the various geometries in agreement with observations and estimate the compatibility of actual surface displacements with long-term slip partitioning models. I thus show a uniform convergence rate of 8.5-11.5 mm/yr with a N81-98E across the Haiyuan fault system and quantify the partitioning along the various structures. I also apply my approach in Southern California, across the « Big Bend » of the San Andreas Fault, where, in analogy with structural geological models, I use conservation of motion to help constraining the geometry and the kinematics of blind thrust faults. I show the compatibility of surface displacements with a large-scale décollement and quantify a loading rate of 2.5 mm/yr along the major thrust structure developing under Los Angeles., Je me focalise sur trois grands systèmes de failles transformantes obliques au Tibet et en Californie du Sud, et ce, afin de mieux comprendre et quantifier les relations entre les différentes structures qui les définissent. L'interférométrie radar à Synthèse d'Ouverture (InSAR) dispose du potentiel pour cartographier et localiser précisément la déformation sur des zones étendues et ainsi contraindre la géométrie des structures profondes. Cependant son utilisation en milieu naturel se trouve fortement entravée par la décorrelation due à la végétation, au relief, et aux cycles de gel et dégel, mais aussi par les délais troposphériques et les rampes orbitales résiduelles. J'ai développé des méthodes pour palier ces limitations. Au Tibet, j'ai ainsi traité les archives du satellite Envisat au niveau de deux zones de lacune sismique, à la bordure Nord du plateau, se présentant comme des zones intéressantes pour étudier le partitionnement de la convergence: le système de faille de Haiyuan au north-est Tibet et la faille sénestre de l'Altyn Tagh, au nord-ouest du plateau. Une attention spécifique sur les déformations liées au pergélisol m'a permis de (1) retrouver la continuité du signal sur de grandes zones, (2) de quantifier le comportement temporel des cycles de gel et dégel des sédiments recouvrant le pergélisol, (3) d'isoler les zones stables des sédiments se déformant. Je montre que les déformations saisonnières sont fortement dépendantes des unités géomorphologiques et que la fonte du pergélisol est plus important à faible qu'à haute altitude. J'analyse aussi le signal saisonnier au travers la marche topographique et je définie un proxy pour les incertitudes de la correction atmosphérique. J'observe un gradient de déformation au travers la faille de l'Altyn Tagh de l'ordre de 11-15 mm/an et un alignement claire de la déformation dans le Tarim, parallèle à la faille de l'Altyn Tagh, ainsi que des soulèvements de l'ordre de 1 mm/an associés à des chevauchements. Ce travail montre aussi un gradient de déformation associé à la terminaison ouest de la faille du Kunlun, re-définissant ainsi la géométrie des blocs tectoniques dans cette région. Parallèlement à cette acquisition de données, je développe des outils d'inversion basés sur des algorithmes de Monte Carlo afin d'explorer l'ensemble des géométries en accord avec les observations et d'estimer la compatibilité de la déformation actuelle avec des modèles tectoniques long-termes. Je montre ainsi une convergence uniforme de 8.5-11.5 mm/an et d'orientation N81-98E à travers le système de faille d'Haiyuan et quantifie son partitionnement le long des différentes structures. Par ailleurs, j'applique mon approche en Californie du Sud, au niveau du « Big Bend » de la faille de San Andreas où, en analogie avec des modèles structuraux géologiques, j'utilise des lois de conservations du mouvement pour contraindre la géométrie des chevauchements aveugles. Je montre la compatibilité du champs de déformation actuel avec un décollement grande échelle et quantifie une accumulation de contrainte de 2.5 mm/an le long de la structure majeure sous Los Angeles.