Au cours des dernières années, le volume des données qui sont capturées et générées a explosé. Les progrès des technologies informatiques, qui fournissent du stockage à bas prix et une très forte puissance de calcul, ont permis aux organisations d'exécuter des analyses complexes de leurs données et d'en extraire des connaissances précieuses. Cette tendance a été très importante non seulement pour l'industrie, mais a également pour la science, où les meilleures instruments et les simulations les plus complexes ont besoin d'une gestion efficace des quantités énormes de données.Le parallélisme est une technique fondamentale dans la gestion de données extrêmement volumineuses car il tire parti de l'utilisation simultanée de plusieurs ressources informatiques. Pour profiter du calcul parallèle, nous avons besoin de techniques de partitionnement de données efficaces, qui sont en charge de la division de l'ensemble des données en plusieurs partitions et leur attribution aux nœuds de calculs. Le partitionnement de données est un problème complexe, car il doit prendre en compte des questions différentes et souvent contradictoires telles que la localité des données, la répartition de charge et la maximisation du parallélisme.Dans cette thèse, nous étudions le problème de partitionnement de données, en particulier dans les bases de données parallèles scientifiques qui sont continuellement en croissance. Nous étudions également ces partitionnements dans le cadre MapReduce.Dans le premier cas, nous considérons le partitionnement de très grandes bases de données dans lesquelles des nouveaux éléments sont ajoutés en permanence, avec pour exemple une application aux données astronomiques. Les approches existantes sont limitées à cause de la complexité de la charge de travail et l'ajout en continu de nouvelles données limitent l'utilisation d'approches traditionnelles. Nous proposons deux algorithmes de partitionnement dynamique qui attribuent les nouvelles données aux partitions en utilisant une technique basée sur l'affinité. Nos algorithmes permettent d'obtenir de très bons partitionnements des données en un temps d'exécution réduit comparé aux approches traditionnelles.Nous étudions également comment améliorer la performance du framework MapReduce en utilisant des techniques de partitionnement de données. En particulier, nous sommes intéressés par le partitionnement efficient de données d'entrée

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.

Dans cette thèse nous proposons de nouveaux algorithmes d'analyse vidéo. La première contribution de cette thèse concerne le domaine de la segmentation de vidéos avec pour objectif d'obtenir une segmentation dense et spatio-temporellement cohérente. Nous proposons de combiner les aspects spatiaux et temporels d'une vidéo en une seule notion, celle de Fibre. Une fibre est un ensemble de trajectoires qui sont spatialement connectées par un maillage. Les fibres sont construites en évaluant simultanément les aspects spatiaux et temporels. Par rapport a l’état de l'art une segmentation de vidéo a base de fibres présente comme avantages d’accéder naturellement au voisinage grâce au maillage et aux correspondances temporelles pour la plupart des pixels de la vidéo. De plus, cette segmentation à base de fibres a une complexité quasi linéaire par rapport au nombre de pixels. La deuxième contribution de cette thèse concerne le suivi d'objets multiples. Nous proposons une approche de suivi qui utilise des caractéristiques des points suivis, la cinématique des objets suivis et l'apparence globale des détections. L'unification de toutes ces caractéristiques est effectuée avec un champ conditionnel aléatoire. Ensuite ce modèle est optimisé en combinant les techniques de passage de message et une variante de processus ICM (Iterated Conditional Modes) pour inférer les trajectoires d'objet. Une troisième contribution mineure consiste dans le développement d'un descripteur pour la mise en correspondance d'apparences de personne. Toutes les approches proposées obtiennent des résultats compétitifs ou meilleurs (qualitativement et quantitativement) que l’état de l'art sur des base de données. / In this thesis we propose novel algorithms for video analysis. The first contribution of this thesis is in the domain of video segmentation wherein the objective is to obtain a dense and coherent spatio-temporal segmentation. We propose joining both spatial and temporal aspects of a video into a single notion Fiber. A fiber is a set of trajectories which are spatially connected by a mesh. Fibers are built by jointly assessing spatial and temporal aspects of the video. Compared to the state-of-the-art, a fiber based video segmentation presents advantages such as a natural spatio-temporal neighborhood accessor by a mesh, and temporal correspondences for most pixels in the video. Furthermore, this fiber-based segmentation is of quasi-linear complexity w.r.t. the number of pixels. The second contribution is in the realm of multiple object tracking. We proposed a tracking approach which utilizes cues from point tracks, kinematics of moving objects and global appearance of detections. Unification of all these cues is performed on a Conditional Random Field. Subsequently this model is optimized by a combination of message passing and an Iterated Conditional Modes (ICM) variant to infer object-trajectories. A third, minor, contribution relates to the development of suitable feature descriptor for appearance matching of persons. All of our proposed approaches achieve competitive and better results (both qualitatively and quantitatively) than state-of-the-art on open source datasets.

Dans le cadre des contraintes économiques et des évolutions démographiques auxquelles doit faire face le secteur de la santé, l’Hospitalisation à Domicile (HAD) qui a été créée il y a une soixantaine d’années s’est largement développée en France durant cette dernière décennie. L’objectif principal de cette alternative à l’hospitalisation complète est de raccourcir les séjours hospitaliers voire même de les éviter en vue de remédier à l’engorgement des hôpitaux tout en améliorant les conditions de vie des patients. Dans cette thèse, nous nous intéressons à la gestion des opérations dans les structures d’HAD. Dans la première partie, nous développons une analyse qualitative de la gestion des opérations dans les établissements d’HAD. De façon plus détaillée, nous identifions les différents facteurs de complexité auxquels la gestion des opérations doit faire face dans ce type de structures. Ces facteurs peuvent concerner la diversité de l’offre des services, le lieu de production des soins, les sources d’incertitudes, etc. Nous présentons ensuite les travaux existants dans la littérature qui s’intéressent à la gestion des opérations dans les HADs. Sur la base de cette synthèse, nous identifions des pistes de recherche qui n’ont pas encore été traitées dans la littérature. Dans la deuxième partie, nous nous intéressons à la problématique de partitionnement géographique du territoire desservi par une structure d’HAD. Cette approche de partitionnement peut s’insérer dans une politique d’amélioration de la qualité du service des soins délivrés aux patients et des conditions de travail des équipes soignantes. Nous commençons d’abord par proposer une classification des différents critères utilisés dans la littérature pour modéliser ce problème. Nous proposons ensuite deux modèles de partitionnement prenant en compte un ensemble de critères tels que l’équilibre de la charge de travail, la compacité, la compatibilité et l’indivisibilité des unités de base. Nous présentons également quelques exploitations possibles de ces modèles et proposons deux extensions à la formulation de base. Après avoir formulé le problème avec une approche statique, nous développons également une extension dynamique qui permet d’intégrer les différentes variations pouvant être observées dans l’activité d’une HAD d’une période à l’autre. Nous introduisons un nouveau critère de partitionnement qui concerne la continuité des soins, évaluée sur la base de deux sous-critères. En fonction des préférences des décideurs par rapport à la prise en compte de la continuité des soins dans le problème de partitionnement, nous distinguons alors trois scénarii pour lesquels nous proposons les modèles associés / Within the framework of economic constraints and demographic changes which the health care sector is confronted to, the Home Health Care (HHC) which has been created sixty years ago, has known an important growth during this last decade. The main objective of this alternative to the traditional hospitalization consists in solving the problem of hospitals’ capacity saturation by allowing earlier discharge of patients from hospital or by avoiding their admission while improving or maintaining the medical, psychological and social welfare of these patients. In this thesis, we are interested in the operations management within the HHC structures. In the first part of this thesis, we develop a qualitative analysis of the operations management in the HHC context. More specifically, we identify the complexity factors that operations management has to face up within this type of structures. For each complexity factor, we discuss how it can affect the organization of the care delivery. These factors pertain to the diversity of the services proposed, the location of care delivery, the uncertainty sources, etc. Thereafter, we survey operations management based models proposed in the literature within the HHC context. Based on this literature review, we identify several emerging issues, relevant from an organizational point of view, that have not been studied in the literature and thus represent unexplored opportunities for operations management researchers. In the second part of this thesis, we are interested in the partitioning of the area where the HCC structure operates into districts. This districting approach fits the policies of improvement of the quality of care delivered to patients and the working conditions of care givers as well as costs’ reduction. We begin by proposing a classification of the different criteria that may be considered in the districting problem. We then propose two mathematical formulations for the HHC districting problem for which we consider criteria such as the workload balance, compactness, compatibility and indivisibility of basic units. After that, we present a numerical analysis of the computational experiments carried out on randomly generated instances to validate these two models. We also present two possible exploitations of these models and propose two extensions to these basic formulations. After formulating the problem with a static approach, we also develop a dynamic extension which allows the integration of the different variations that can be observed within the activities of an HHC structure from period to period. We then introduce a new partitioning criterion that concerns the continuity of care evaluated on the basis of two sub-criteria. Depending on the preferences of the decision-makers concerning the sub-criteria related to the continuity of care in the districting problem, we then distinguish three scenarios for which we propose the associated mathematical formulations.

Les simulations dites multi-physiques couplent plusieurs phases de calcul. Lorsqu’elles sont exécutées en parallèle sur des architectures à mémoire distribuée, la minimisation du temps de restitution nécessite dans la plupart des cas d’équilibrer la charge entre les unités de traitement, pour chaque phase de calcul. En outre, la distribution des données doit minimiser les communications qu’elle induit. Ce problème peut être modélisé comme un problème de partitionnement de graphe multi-critères. On associe à chaque sommet du graphe un vecteur de poids, dont les composantes, appelées « critères », modélisent la charge de calcul porté par le sommet pour chaque phase de calcul. Les arêtes entre les sommets, indiquent des dépendances de données, et peuvent être munies d’un poids reflétant le volume de communication transitant entre les deux sommets. L’objectif est de trouver une partition des sommets équilibrant le poids de chaque partie pour chaque critère, tout en minimisant la somme des poids des arêtes coupées, appelée « coupe ». Le déséquilibre maximum toléré entre les parties est prescrit par l’utilisateur. On cherche alors une partition minimisant la coupe, parmi toutes celles dont le déséquilibre pour chaque critère est inférieur à cette tolérance. Ce problème étant NP-Dur dans le cas général, l’objet de cette thèse est de concevoir et d’implanter des heuristiques permettant de calculer efficacement de tels partitionnements. En effet, les outils actuels renvoient souvent des partitions dont le déséquilibre dépasse la tolérance prescrite. Notre étude de l’espace des solutions, c’est-à-dire l’ensemble des partitions respectant les contraintes d’équilibre, révèle qu’en pratique, cet espace est immense. En outre, nous prouvons dans le cas mono-critère qu’une borne sur les poids normalisés des sommets garantit que l’espace des solutions est non-vide et connexe. Nous fondant sur ces résultats théoriques, nous proposons des améliorations de la méthode multi-niveaux. Les outils existants mettent en oeuvre de nombreuses variations de cette méthode. Par l’étude de leurs codes sources, nous mettons en évidence ces variations et leurs conséquences à la lumière de notre analyse sur l’espace des solutions. Par ailleurs, nous définissons et implantons deux algorithmes de partitionnement initial, se focalisant sur l’obtention d’une solution à partir d’une partition potentiellement déséquilibrée, au moyen de déplacements successifs de sommets. Le premier algorithme effectue un mouvement dès que celui-ci améliore l’équilibre, alors que le second effectue le mouvement réduisant le plus le déséquilibre. Nous présentons une structure de données originale, permettant d’optimiser le choix des sommets à déplacer, et conduisant à des partitions de déséquilibre inférieur en moyenne aux méthodes existantes. Nous décrivons la plate-forme d’expérimentation, appelée Crack, que nous avons conçue afin de comparer les différents algorithmes étudiés. Ces comparaisons sont effectuées en partitionnant un ensembles d’instances comprenant un cas industriel et plusieurs cas fictifs. Nous proposons une méthode de génération de cas réalistes de simulations de type « transport de particules ». Nos résultats démontrent la nécessité de restreindre les poids des sommets lors de la phase de contraction de la méthode multi-niveaux. En outre, nous mettons en évidence l’influence de la stratégie d’ordonnancement des sommets, dépendante de la topologie du graphe, sur l’efficacité de l’algorithme d’appariement « Heavy-Edge Matching » dans cette même phase. Les différents algorithmes que nous étudions sont implantés dans un outil de partitionnement libre appelé Scotch. Au cours de nos expériences, Scotch et Crack renvoient une partition équilibrée à chaque exécution, là où MeTiS, l’outil le plus utilisé actuellement, échoue une grande partie du temps. Qui plus est, la coupe des solutions renvoyées par Scotch et Crack est équivalente ou meilleure que celle renvoyée par MeTiS. / Multiphysics simulation couple several computation phases. When they are run in parallel on memory-distributed architectures, minimizing the simulation time requires in most cases to balance the workload across computation units, for each computation phase. Moreover, the data distribution must minimize the induced communication. This problem can be modeled as a multi-criteria graph partitioning problem. We associate with each vertex of the graph a vector of weights, whose components, called “criteria”, model the workload of the vertex for each computation phase. The edges between vertices indicate data dependencies, and can be given a weight representing the communication volume transferred between the two vertices. The goal is to find a partition of the vertices that both balances the weights of each part for each criterion, and minimizes the “edgecut”, that is, the sum of the weights of the edges cut by the partition. The maximum allowed imbalance is provided by the user, and we search for a partition that minimizes the edgecut, among all the partitions whose imbalance for each criterion is smaller than this threshold. This problem being NP-Hard in the general case, this thesis aims at devising and implementing heuristics that allow us to compute efficiently such partitions. Indeed, existing tools often return partitions whose imbalance is higher than the prescribed tolerance. Our study of the solution space, that is, the set of all the partitions respecting the balance constraints, reveals that, in practice, this space is extremely large. Moreover, we prove in the mono-criterion case that a bound on the normalized vertex weights guarantees the existence of a solution, and the connectivity of the solution space. Based on these theoretical results, we propose improvements of the multilevel algorithm. Existing tools implement many variations of this algorithm. By studying their source code, we emphasize these variations and their consequences, in light of our analysis of the solution space. Furthermore, we define and implement two initial partitioning algorithms, focusing on returning a solution. From a potentially imbalanced partition, they successively move vertices from one part to another. The first algorithm performs any move that reduces the imbalance, while the second performs at each step the move reducing the most the imbalance. We present an original data structure that allows us to optimize the choice of the vertex to move, and leads to partitions of imbalance smaller on average than existing methods. We describe the experimentation framework, named Crack, that we implemented in order to compare the various algorithms at stake. This comparison is performed by partitioning a set of instances including an industrial test case, and several fictitious cases. We define a method for generating realistic weight distributions corresponding to “Particles-in-Cells”-like simulations. Our results demonstrate the necessity to coerce the vertex weights during the coarsening phase of the multilevel algorithm. Moreover, we evidence the impact of the vertex ordering, which should depend on the graph topology, on the efficiency of the “Heavy-Edge” matching scheme. The various algorithms that we consider are implemented in an open- source graph partitioning software called Scotch. In our experiments, Scotch and Crack returned a balanced partition for each execution, whereas MeTiS, the current most used partitioning tool, fails regularly. Additionally, the edgecut of the solutions returned by Scotch and Crack is equivalent or better than the edgecut of the solutions returned by MeTiS.

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. / 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.

Dans le cadre de l’aide à l’analyse de dialogues, un corpus de dialogues peut être représenté par un ensemble de tableaux d’annotations encodant les différents énoncés des dialogues. Afin d’identifier des schémas dialogiques mis en oeuvre fréquemment, nous définissons une méthodologie en deux étapes : extraction de motifs récurrents, puis partitionnement de ces motifs en classes homogènes constituant ces régularités. Deux méthodes sont développées afin de réaliser l’extraction de motifs récurrents : LPCADC et SABRE. La première est une adaptation d’un algorithme de programmation dynamique tandis que la seconde est issue d’une modélisation formelle du problème d’extraction d’alignements locaux dans un couple de tableaux d’annotations.Le partitionnement de motifs récurrents est réalisé par diverses heuristiques de la littérature ainsi que deux formulations originales du problème de K-partitionnement sous la forme de programmes linéaires en nombres entiers. Lors d’une étude polyèdrale, nous caractérisons des facettes d’un polyèdre associé à ces formulations (notamment les inégalités de 2-partitions, les inégalités 2-chorded cycles et les inégalités de clique généralisées). Ces résultats théoriques permettent la mise en place d’un algorithme de plans coupants résolvant efficacement le problème.Nous développons le logiciel d’aide à la décision VIESA, mettant en oeuvre ces différentes méthodes et permettant leur évaluation au cours de deux expérimentations réalisées par un expert psychologue. Des régularités correspondant à des stratégies dialogiques que des extractions manuelles n’avaient pas permis d’obtenir sont ainsi identifiées. / In the context of dialogue analysis, a corpus of dialogues can be represented as a set of arrays of annotations encoding the dialogue utterances. In order to identify the frequently used dialogue schemes, we design a two-step methodology in which recurrent patterns are first extracted and then partitioned into homogenous classes constituting the regularities. Two methods are developed to extract recurrent patterns: LPCA-DC and SABRE. The former is an adaptation of a dynamic programming algorithm whereas the latter is obtained from a formal modeling of the extraction of local alignment problem in annotations arrays.The partitioning of recurrent patterns is realised using various heuristics from the literature as well as two original formulations of the K-partitioning problem in the form of mixed integer linear programs. Throughout a polyhedral study of a polyhedron associated to these formulations, facets are characterized (in particular: 2-chorded cycle inequalities, 2-partition inequalities and general clique inequalities). These theoretical results allow the establishment of an efficient cutting plane algorithm.We developed a decision support software called VIESA which implements these different methods and allows their evaluation during two experiments realised by a psychologist. Thus, regularities corresponding to dialogical strategies that previous manual extractions failed to identify are obtained.

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.

Pour traiter un graphe de manière répartie, le partitionnement est une étape préliminaire importante car elle influence de manière significative le temps final d’exécutions. Dans cette thèse nous étudions le problème du partitionnement réparti de graphe. Des travaux récents ont montré qu’une approche basée sur le partitionnement des sommets plutôt que des arêtes offre de meilleures performances pour les graphes de type power-laws qui sont courant dans les données réelles. Dans un premier temps nous avons étudié les différentes métriques utilisées pour évaluer la qualité d’un partitionnement. Ensuite nous avons analysé et comparé plusieurs logiciels d’analyse de grands graphes (Hadoop, Giraph, Giraph++, Distributed GrahpLab et PowerGraph), les comparant `a une solution très populaire actuellement, Spark et son API de traitement de graphe appelée GraphX. Nous présentons les algorithmes de partitionnement les plus récents et introduisons une classification. En étudiant les différentes publications, nous arrivons à la conclusion qu’il n’est pas possible de comparer la performance relative de tous ces algorithmes. Nous avons donc décidé de les implémenter afin de les comparer expérimentalement. Les résultats obtenus montrent qu’un partitionneur de type Hybrid-Cut offre les meilleures performances. Dans un deuxième temps, nous étudions comment il est possible de prédire la qualité d’un partitionnement avant d’effectivement traiter le graphe. Pour cela, nous avons effectué de nombreuses expérimentations avec GraphX et effectué une analyse statistique précise des résultats en utilisation un modèle de régression linéaire. Nos expérimentations montrent que les métriques de communication sont de bons indicateurs de la performance. Enfin, nous proposons un environnement de partitionnement réparti basé sur du recuit simulé qui peut être utilisé pour optimiser une large partie des métriques de partitionnement. Nous fournissons des conditions suffisantes pour assurer la convergence vers l’optimum et discutons des métriques pouvant être effectivement optimisées de manière répartie. Nous avons implémenté cet algorithme dans GraphX et comparé ses performances avec JA-BE-JA-VC. Nous montrons que notre stratégie amène a` des améliorations significatives. / In distributed graph computation, graph partitioning is an important preliminary step because the computation time can significantly depend on how the graph has been split among the different executors. In this thesis we explore the graph partitioning problem. Recently, edge partitioning approach has been advocated as a better approach to process graphs with a power-law degree distribution, which are very common in real-world datasets. That is why we focus on edge partition- ing approach. We start by an overview of existing metrics, to evaluate the quality of the graph partitioning. We briefly study existing graph processing systems: Hadoop, Giraph, Giraph++, Distributed GrahpLab, and PowerGraph with their key features. Next, we compare them to Spark, a popular big-data processing framework with its graph processing APIs — GraphX. We provide an overview of existing edge partitioning algorithms and introduce partitioner classification. We conclude that, based only on published work, it is not possible to draw a clear conclusion about the relative performances of these partitioners. For this reason, we have experimentally compared all the edge partitioners currently avail- able for GraphX. Results suggest that Hybrid-Cut partitioner provides the best performance. We then study how it is possible to evaluate the quality of a parti- tion before running a computation. To this purpose, we carry experiments with GraphX and we perform an accurate statistical analysis using a linear regression model. Our experimental results show that communication metrics like vertex-cut and communication cost are effective predictors in most of the cases. Finally, we propose a framework for distributed edge partitioning based on distributed simulated annealing which can be used to optimize a large family of partitioning metrics. We provide sufficient conditions for convergence to the optimum and discuss which metrics can be efficiently optimized in a distributed way. We implemented our framework with GraphX and performed a comparison with JA-BE-JA-VC, a state-of-the-art partitioner that inspired our approach. We show that our approach can provide significant improvements.

É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. / 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.