Search

Cet article présente une collaboration entre agronomes et informaticiens dans une démarche de modélisation spatiale visant à comparer des exploitations agricoles et à inférer leurs possibles modalités de fonctionnement. Pour les agronomes engagés dans ce projet pluridisciplinaire, il s’agit de faire progresser l’approche de l’organisation spatiale des cas étudiés et d’en stabiliser les outils, en particulier de modèles graphiques (chorèmes), empruntés à la géographie. Les connaissances ainsi acquises sont formalisées au moyen de graphes, de façon à permettre la mémorisation d’études de cas et faciliter leur mobilisation pour traiter de nouvelles observations, c’est-à-dire pour identifier et interpréter des structures spatiales. L’usage des deux outils, chorèmes et graphes, ouvre sur des connaissances généralisables sur la production et la transformation de représentations spatiales en agronomie. This paper presents how agronomists and computer engineers worked together on spatial modeling in order to compare farms and infer feasible functioning modes. Agronomists involved in this multidisciplinary project aimed at advances in dealing with spatial organization of studied cases, and in stabilizing related tools. A particular matter was graphic modeling with choremes borrowed from geography. Computer engineers formalized the knowledge thus obtained into graphs, as a way to memorize case studies and make their use easier for dealing with new cases: that is identifying and interpreting spatial structures. Joint use of choremes and graphs opens onto generic knowledge of spatial representations to be processed and transformed in agronomy. Este artículo presenta una colaboración entre agrónomos e informáticos en un proceso de modelización espacial, que apunta a comparar explotaciones agrícolas e inferir sus posibles modalidades de funcionamiento. Los agrónomos comprometidos en este proyecto pluridisciplinario quieren hacer progresar el enfoque de la organización espacial en los casos estudiados y de estabilizar las herramientas utilizadas. Se trata en particular de modelos gráficos, los coremas, que son tomados prestados de la geografía. Los conocimientos así adquiridos son formalizados por medio de grafos, de manera que permitan la memorización de estudios de casos y facilitar su movilización para tratar nuevas observaciones, es decir para identificar e interpretar estructuras espaciales. El uso de las dos herramientas, coremas y grafos, conduce a conocimientos generalizables sobre la producción y la transformación de representaciones espaciales en agronomía.

The Internet of Things is evolving rapidly, with more and more protocols and objects being deployed, on a large scale or in closed environments. However, with this proliferation of protocols comes new security issues. Indeed, IoT protocols are heterogeneous, specific to particular needs and used in various application domains, making them complex to secure. Several solutions exist to evaluate and improve the security of complex systems, including intrusion testing. In this thesis, we describe a methodology for modeling heterogeneous IoT networks, used as an analysis support to perform penetration testing. We focus this methodology on short-range IoT protocols such as Zigbee, BLE and OS4I. However, its modular approach allows it to be functional for the largest number of IoT protocols, avoiding modification to add a new protocol. For this purpose, we first present a generic approach, based on four criteria, which allows to describe and compare, according to a homogeneous model, several IoT protocols. We then present a classification of attacks on IoT protocols, in three parts, in order to understand and specify the target of the attack and its impact. These abstract and generic models allow us to build a generic structure, which we call generic packet. Our modeling process, composed of four graphs, is based on this generic packet. We propose an iterative scheme to build these graphs, from the graph representing the point-to-point communications of the network, to the one highlighting the applications detected in the network. The generation of each graph requires the use of functions, taking as input several patterns and the previous graph. Finally, we propose an experimentation platform, composed of several objects, mixing proprietary and configurable devices. It allows the evaluation of our modeling methodology under different experimental conditions. In the ideal case, we find that the modeling detects all the applications deployed in the network. The result is also relevant when we degrade our observation through encrypted communications. Indeed, we then find that all applications are detected, despite a higher number of false positives. All the functions and patterns defined in our modeling methodology are implemented in IoTMap, a framework, which we have released as open source., L’Internet des objets évolue rapidement, avec toujours plus de protocoles et d’objets déployés, à grande échelle ou dans des environnements cloisonnés. Cependant, avec cette émergence de protocoles, viennent de nouvelles problématiques de sécurité. En effet, les protocoles IoT sont hétérogènes, spécifiques à des besoins particuliers et utilisés dans des domaines d’applications divers, les rendant complexes à sécuriser. Plusieurs solutions existent pour évaluer et améliorer la sécurité des systèmes complexes, notamment le test d’intrusion. Dans cette thèse, nous décrivons une méthodologie de modélisation de réseaux IoT hétérogènes, utilisée comme support d’analyse dans la réalisation de tests d’intrusion. Nous centrons cette méthodologie sur des protocoles IoT à courte portée, tels que Zigbee, BLE et OS4I. Cependant, son approche modulaire lui permet d’être fonctionnelle pour le plus grand nombre de protocoles IoT, sans devoir être modifiée pour l’ajout ou l’évolution d’un protocole. Pour cela, nous présentons d’abord une approche générique, reposant sur quatre critères, qui permet de décrire et comparer, selon un modèle homogène, plusieurs protocoles IoT. Nous exposons, ensuite, une classification des attaques concernant les protocoles IoT, en trois parties, afin de comprendre, préciser la cible de l’attaque et son impact. Ces modèles abstraits et génériques nous permettent ainsi l’élaboration d’une structure générique, que nous appelons paquet générique. C’est sur ce dernier que repose notre processus de modélisation, composé de quatre graphes. Nous proposons une construction itérative de ces graphes, allant du graphe représentant les communications point à point du réseau, jusqu’à celui mettant en évidence les applications détectées dans le réseau. La génération de chaque graphe nécessite l’utilisation de fonctions, prenant en entrée plusieurs patterns et le graphe précédent. Nous proposons enfin une plateforme d’expérimentations, composée de plusieurs objets, mélangeant des dispositifs propriétaires et d’autres configurables. Elle permet notamment l’évaluation de notre méthodologie de modélisation dans des conditions expérimentales différentes. Dans le cas idéal, nous constatons que la modélisation détecte toutes les applications déployées dans le réseau. Le résultat est également pertinent lorsque nous dégradons notre observation par l’utilisation du chiffrement dans les communications. En effet, nous constatons alors que toutes les applications sont détectées, malgré un nombre plus important de faux positifs. L’ensemble des fonctions et patterns définis dans notre méthodologie de modélisation est implémenté dans IoTMap, un framework, que nous avons rendu open source.

National audience; Many authors use graphs to express the structures describing and explaining the performance under study. The cases of the scorecards, balanced scorecards, performance mind maps or conceptual maps show that the used tools suffer from shortcomings in terms of graphic modelling. This paper tries to overcome some of them by using SysML, which is an engineering graph-based language. This paper shows how to generate pergraphs by using design patterns derived from SysML diagrams. Under a future graph-based performance management, the proposed approach may be an intermediate between visual and non-formal graphs building and analytical graphs production; Il est habituel, en contrôle de gestion, d’employer les tableaux de bord, les cartes mentales ou cognitives pour exprimer graphiquement les structures décrivant ou expliquant la performance étudiée, ou pergraphes. Toutefois, ces outils manquent d’abstraction. Cet article propose de recourir à SysML, un langage graphique de l’ingénierie, pour modéliser de façon plus rigoureuse les pergraphes et définir les patrons à partir desquels les générer. Si un contrôle de gestion fondé sur les graphes venait à se développer, l’approche proposée occuperait une intermédiaire entre la construction de pergraphes visuels et informels et la production de graphes analytiques

In this article, by algebraic and geometrical techniques, I give a proof to the famous conjecture of Ulam [10] on the (-1)-reconstruction of the symmetric graphs with at least 3 elements conjectured in 1942, although was published only in 1960., Résumé : Dans cet article, par des techniques algébriques et géométriques, je donne une preuve à la célèbre conjecture d'Ulam [10] sur la (-1)-reconstruction des graphes symétriques à au moins 3 éléments conjecturé en 1942, quoique n'a été publié que en 1960 .

Cameras have become increasingly common in vehicles, smart phones, and advanced driver assistance systems. The areas of application of these cameras in the world of intelligent transportation systems are becoming more and more varied : pedestrian detection, line crossing detection, navigation ... Vision-based navigation has reached a certain maturity in recent years through the use of advanced technologies. Vision-based navigation systems have the considerable advantage of being able to directly use the visual information already existing in the environment without having to adapt any element of the infrastructure. In addition, unlike systems using GPS, they can be used outdoors and indoors without any loss of precision. This guarantees the superiority of these systems based on computer vision. A major area of {research currently focuses on mapping, which represents an essential step for navigation. This step generates a problem of memory management quite substantial required by these systems because of the huge amount of information collected by each sensor. Indeed, the memory space required to accommodate the map of a small city is measured in tens of GB or even thousands when one wants to cover large spaces. This makes impossible to integrate this map into a mobile system such as smartphones , cameras embedded in vehicles or robots. The challenge would be to develop new algorithms to minimize the size of the memory needed to operate this navigation system using only computer vision. It's in this context that our project consists in developing a new system able to summarize a3D map resulting from the visual information collected by several sensors. The summary will be a set of spherical views allow to keep the same level of visibility in all directions. It would also guarantee, at a lower cost, a good level of precision and speed during navigation. The summary map of the environment will contain geometric, photometric and semantic information.; Les caméras sont devenues de plus en plus communes dans les véhicules, les smartphones et les systèmes d'aide à la conduite ADAS (Advanced Driver Assistance Systèmes). Les domaines d'application de ces caméras dans le monde des systèmes intelligents de transport deviennent de plus en plus variés : la détection des piétons, les avertissements de franchissement de ligne, la navigation... La navigation basée sur la vision a atteint une certaine maturité durant ces dernières années grâce à l'utilisation de technologies avancées. Les systèmes de navigation basée sur la vision ont le considérable avantage de pouvoir utiliser directement les informations visuelles présentes dans l'environnement, sans devoir adapter le moindre élément de l'infrastructure. De plus, contrairement aux systèmes utilisant le GPS, ils peuvent être utilisés à l'extérieur ainsi qu'à l'intérieur des locaux et des bâtiments sans aucune perte de précision. C'est pour ces raisons que les systèmes basés sur la vision sont une bonne option car ils fournissent des informations très riches et précises sur l'environnement, qui peuvent être utilisées pour la navigation. Un axe important de recherche porte actuellement sur la cartographie qui représente une étape indispensable pour la navigation. Cette étape engendre une problématique de la gestion de la mémoire assez conséquente requise par ces systèmes en raison de la quantité d'informations importante collectées par chaque capteur. En effet, l'espace mémoire nécessaire pour accueillir la carte d'une petite ville se mesure en dizaines de GO voire des milliers lorsque l'on souhaite couvrir des espaces de grandes dimensions. Cela rend impossible son intégration dans un système mobile tel que les smartphones, les véhicules, les vélos ou les robots. Le défi serait donc de développer de nouveaux algorithmes permettant de diminuer au maximum la taille de la mémoire nécessaire pour faire fonctionner ce système de localisation par vision. C'est dans ce contexte que se situe notre projet qui consiste à développer un nouveau système capable de résumer une carte 3D qui contient des informations visuelles collectées par plusieurs capteurs. Le résumé sera un ensemble des vues sphériques permettant de garder le même niveau de visibilité dans toutes les directions. Cela permettrait aussi de garantir, à moindre coût, un bon niveau de précision et de rapidité lors de la navigation. La carte résumant l'environnement sera constituée d'un ensemble d'informations géométriques, photométriques et sémantiques.

Cameras have become increasingly common in vehicles, smart phones, and advanced driver assistance systems. The areas of application of these cameras in the world of intelligent transportation systems are becoming more and more varied : pedestrian detection, line crossing detection, navigation ... Vision-based navigation has reached a certain maturity in recent years through the use of advanced technologies. Vision-based navigation systems have the considerable advantage of being able to directly use the visual information already existing in the environment without having to adapt any element of the infrastructure. In addition, unlike systems using GPS, they can be used outdoors and indoors without any loss of precision. This guarantees the superiority of these systems based on computer vision. A major area of {research currently focuses on mapping, which represents an essential step for navigation. This step generates a problem of memory management quite substantial required by these systems because of the huge amount of information collected by each sensor. Indeed, the memory space required to accommodate the map of a small city is measured in tens of GB or even thousands when one wants to cover large spaces. This makes impossible to integrate this map into a mobile system such as smartphones , cameras embedded in vehicles or robots. The challenge would be to develop new algorithms to minimize the size of the memory needed to operate this navigation system using only computer vision. It's in this context that our project consists in developing a new system able to summarize a3D map resulting from the visual information collected by several sensors. The summary will be a set of spherical views allow to keep the same level of visibility in all directions. It would also guarantee, at a lower cost, a good level of precision and speed during navigation. The summary map of the environment will contain geometric, photometric and semantic information.; Les caméras sont devenues de plus en plus communes dans les véhicules, les smartphones et les systèmes d'aide à la conduite ADAS (Advanced Driver Assistance Systèmes). Les domaines d'application de ces caméras dans le monde des systèmes intelligents de transport deviennent de plus en plus variés : la détection des piétons, les avertissements de franchissement de ligne, la navigation... La navigation basée sur la vision a atteint une certaine maturité durant ces dernières années grâce à l'utilisation de technologies avancées. Les systèmes de navigation basée sur la vision ont le considérable avantage de pouvoir utiliser directement les informations visuelles présentes dans l'environnement, sans devoir adapter le moindre élément de l'infrastructure. De plus, contrairement aux systèmes utilisant le GPS, ils peuvent être utilisés à l'extérieur ainsi qu'à l'intérieur des locaux et des bâtiments sans aucune perte de précision. C'est pour ces raisons que les systèmes basés sur la vision sont une bonne option car ils fournissent des informations très riches et précises sur l'environnement, qui peuvent être utilisées pour la navigation. Un axe important de recherche porte actuellement sur la cartographie qui représente une étape indispensable pour la navigation. Cette étape engendre une problématique de la gestion de la mémoire assez conséquente requise par ces systèmes en raison de la quantité d'informations importante collectées par chaque capteur. En effet, l'espace mémoire nécessaire pour accueillir la carte d'une petite ville se mesure en dizaines de GO voire des milliers lorsque l'on souhaite couvrir des espaces de grandes dimensions. Cela rend impossible son intégration dans un système mobile tel que les smartphones, les véhicules, les vélos ou les robots. Le défi serait donc de développer de nouveaux algorithmes permettant de diminuer au maximum la taille de la mémoire nécessaire pour faire fonctionner ce système de localisation par vision. C'est dans ce contexte que se situe notre projet qui consiste à développer un nouveau système capable de résumer une carte 3D qui contient des informations visuelles collectées par plusieurs capteurs. Le résumé sera un ensemble des vues sphériques permettant de garder le même niveau de visibilité dans toutes les directions. Cela permettrait aussi de garantir, à moindre coût, un bon niveau de précision et de rapidité lors de la navigation. La carte résumant l'environnement sera constituée d'un ensemble d'informations géométriques, photométriques et sémantiques.

Reliably transmitting information over a transmission channel is a recurrent problem in Informatic Sciences. Whatever may be the channel used to transmit information, we automatically observe erasure of this information, or pure loss. Different solutions can be used to solve this problem, using forward error correction codes is one of them. In this thesis, we study a corrector code developped in 2014 and 2015 for Thales society during my second year of master of apprenticeship. It is currently used to ensure the reliability of a transmission based on the UDP protocole, and passing by a network diode, Elips-SD. Elip-SD is an optical diode that can be plugged on an optical fiber to physically ensure that the transmission is unidirectional. The main usecase of such a diode is to enable supervising a critical site, while ensuring that no information can be transmitted to this site. At the opposite, another usecase is the transmission from one or multiple unsecured emitters to one secured receiver who wants to ensure that no information can be robbed. The corrector code that we present is a linear corrector code for the binary erasure channel using packets, that obtained the NATO certification from the DGA ("Direction Générale de Armées" in French). We named it Fauxtraut, for "Fast algorithm using Xor to repair altered unidirectional transmissions". In order to study this code, presenting how it works, its performance and the modifications we added during this thesis, we first establish a state of the art of forward error correction, focusing on non-MDS linear codes such as LDPC codes. Then we present Fauxtraut behavior, and analyse it theorically and with simulations. Finally, we present different versions of this code that were developped during this thesis, leading to other usecases such as transmitting reliable information that can be altered instead of being erased, or on a bidirectionnal channel, such as the H-ARQ protocole, and different results on the number of cycles in particular graphs. In the last part, we present results that we obtained during this thesis and that finally lead to an article in the Technical Computer Science. It concerns a non-polynomial problema of Graphs theorie : maximum matching in temporal graphs. In this article, we propose two algorithms with polynomial complexity : a 2-approximation algorithm and a kernelisation algorithm forthis problema.; La transmission fiable de données sur un canal de transmission est un problème récurrent en Informatique. En effet, quel que soit le canal de transmission employé, on observe obligatoirement de la détérioration de l’information transmise, voire sa perte pure et simple. Afin de palier à ce problème, plusieurs solutions ont été apportées, notamment via l’emploi de codes correcteurs. Dans cette thèse, nous étudions un code correcteur développé en 2014 et 2015 pour l’entreprise Thales durant ma deuxième année de Master en apprentissage. Il s’agit d’un code actuellement utilisé par Thales pour fiabiliser une transmission UDP passant par un dispositif réseau, l’Elips-SD. L’Elips-SD est une diode réseau qu’on place sur une fibre optique et qui garantit physiquement que la transmission est unidirectionnelle. Le cas d’utilisation principal de cette diode est de permettre le suivi de la production d’un site sensible, ou encore de superviser son fonctionnement, tout en garantissant à ce site une protection face aux intrusions extérieures. A l’opposé, un autre cas d’utilisation est la transmission de données depuis un ou plusieurs sites non-sécurisés vers un site sécurisé, dont on souhaite s’assurer qu’aucune information ne pourra par la suite fuiter. Le code correcteur que nous étudions est un code correcteur linéaire pour le canal à effacements de paquets, qui a reçu la certification OTAN de la Direction Générale des Armées. Nous l’avons babtisé "Fauxtraut", anagramme de "Fast algorithm using Xor to repair altered unidirectionnal transmissions". Afin d’étudier ce code correcteur, de présenter son fonctionnement et ses performances, et les différentes modifications apportées durant cette thèse, nous établissons tout d’abord un état de l’art des codes correcteurs, en nous concentrant principalement sur les codes linéaires non-MDS, tels que les codes LDPC. Puis nous présentons le fonctionnement de Fauxtraut, et analysons son comportement (complexité, consommation mémoire, performances) par la théorie et par des simulations. Enfin, nous présenterons différentes versions de ce code correcteur développées durant cette thèse, qui aboutissent à d’autres cas d’utilisation, tels que la transmission d’information sur un canal unidirectionnel à erreurs ou sur un canal bidirectionnel, à l’image de ce que permet de faire le protocole H-ARQ. Dans cette partie, nous étudierons notamment le comportement de notre code correcteur via la théorie des graphes : calculer la probabilité de décoder convenablement ou non revient à connaître la probabilité d’apparition de cycles dans le sous-graphe de graphes particuliers, les graphes de Rook et les graphes bipartis complets. Le problème s’énonce simplement et s’avère compliqué, et nous espérons qu’il saura intéresser des chercheurs du domaine. Nous présentons une méthode permettant de calculer exactement cette probabilité pour de petits graphes (qui aboutit à un certain nombre de formules closes), et une fonction tendant asymptotiquement vers cette probabilité pour de plus grands graphes. Nous étudierons aussi la manière de paramétrer automatiquement notre code correcteur par le calcul modulaire et la combinatoire, utilisant la fonction de Landau, qui retourne un ensemble de nombres entiers dont la somme est fixée et le plus commun multiple est maximal. Dans une dernière partie, nous présentons un travail effectué durant cette thèse ayant conduit à une publication dans la revue Theoretical Computer Science. Il concerne un problème non-polynomial de la théorie des graphes : le couplage maximal dans les graphes temporels. Cet article propose notamment deux algorithmes de complexité polynomiale : un algorithme de 2-approximation et un algorithme de kernelisation pour ce problème. L’algorithme de 2- approximation peut notamment être utilisé de manière incrémentale : arêtes du flot de liens nous parviennent les unes après les autres, et on construit la 2-approximation au fur et à mesure de leur arrivée.

Reliably transmitting information over a transmission channel is a recurrent problem in Informatic Sciences. Whatever may be the channel used to transmit information, we automatically observe erasure of this information, or pure loss. Different solutions can be used to solve this problem, using forward error correction codes is one of them. In this thesis, we study a corrector code developped in 2014 and 2015 for Thales society during my second year of master of apprenticeship. It is currently used to ensure the reliability of a transmission based on the UDP protocole, and passing by a network diode, Elips-SD. Elip-SD is an optical diode that can be plugged on an optical fiber to physically ensure that the transmission is unidirectional. The main usecase of such a diode is to enable supervising a critical site, while ensuring that no information can be transmitted to this site. At the opposite, another usecase is the transmission from one or multiple unsecured emitters to one secured receiver who wants to ensure that no information can be robbed. The corrector code that we present is a linear corrector code for the binary erasure channel using packets, that obtained the NATO certification from the DGA ("Direction Générale de Armées" in French). We named it Fauxtraut, for "Fast algorithm using Xor to repair altered unidirectional transmissions". In order to study this code, presenting how it works, its performance and the modifications we added during this thesis, we first establish a state of the art of forward error correction, focusing on non-MDS linear codes such as LDPC codes. Then we present Fauxtraut behavior, and analyse it theorically and with simulations. Finally, we present different versions of this code that were developped during this thesis, leading to other usecases such as transmitting reliable information that can be altered instead of being erased, or on a bidirectionnal channel, such as the H-ARQ protocole, and different results on the number of cycles in particular graphs. In the last part, we present results that we obtained during this thesis and that finally lead to an article in the Technical Computer Science. It concerns a non-polynomial problema of Graphs theorie : maximum matching in temporal graphs. In this article, we propose two algorithms with polynomial complexity : a 2-approximation algorithm and a kernelisation algorithm forthis problema.; La transmission fiable de données sur un canal de transmission est un problème récurrent en Informatique. En effet, quel que soit le canal de transmission employé, on observe obligatoirement de la détérioration de l’information transmise, voire sa perte pure et simple. Afin de palier à ce problème, plusieurs solutions ont été apportées, notamment via l’emploi de codes correcteurs. Dans cette thèse, nous étudions un code correcteur développé en 2014 et 2015 pour l’entreprise Thales durant ma deuxième année de Master en apprentissage. Il s’agit d’un code actuellement utilisé par Thales pour fiabiliser une transmission UDP passant par un dispositif réseau, l’Elips-SD. L’Elips-SD est une diode réseau qu’on place sur une fibre optique et qui garantit physiquement que la transmission est unidirectionnelle. Le cas d’utilisation principal de cette diode est de permettre le suivi de la production d’un site sensible, ou encore de superviser son fonctionnement, tout en garantissant à ce site une protection face aux intrusions extérieures. A l’opposé, un autre cas d’utilisation est la transmission de données depuis un ou plusieurs sites non-sécurisés vers un site sécurisé, dont on souhaite s’assurer qu’aucune information ne pourra par la suite fuiter. Le code correcteur que nous étudions est un code correcteur linéaire pour le canal à effacements de paquets, qui a reçu la certification OTAN de la Direction Générale des Armées. Nous l’avons babtisé "Fauxtraut", anagramme de "Fast algorithm using Xor to repair altered unidirectionnal transmissions". Afin d’étudier ce code correcteur, de présenter son fonctionnement et ses performances, et les différentes modifications apportées durant cette thèse, nous établissons tout d’abord un état de l’art des codes correcteurs, en nous concentrant principalement sur les codes linéaires non-MDS, tels que les codes LDPC. Puis nous présentons le fonctionnement de Fauxtraut, et analysons son comportement (complexité, consommation mémoire, performances) par la théorie et par des simulations. Enfin, nous présenterons différentes versions de ce code correcteur développées durant cette thèse, qui aboutissent à d’autres cas d’utilisation, tels que la transmission d’information sur un canal unidirectionnel à erreurs ou sur un canal bidirectionnel, à l’image de ce que permet de faire le protocole H-ARQ. Dans cette partie, nous étudierons notamment le comportement de notre code correcteur via la théorie des graphes : calculer la probabilité de décoder convenablement ou non revient à connaître la probabilité d’apparition de cycles dans le sous-graphe de graphes particuliers, les graphes de Rook et les graphes bipartis complets. Le problème s’énonce simplement et s’avère compliqué, et nous espérons qu’il saura intéresser des chercheurs du domaine. Nous présentons une méthode permettant de calculer exactement cette probabilité pour de petits graphes (qui aboutit à un certain nombre de formules closes), et une fonction tendant asymptotiquement vers cette probabilité pour de plus grands graphes. Nous étudierons aussi la manière de paramétrer automatiquement notre code correcteur par le calcul modulaire et la combinatoire, utilisant la fonction de Landau, qui retourne un ensemble de nombres entiers dont la somme est fixée et le plus commun multiple est maximal. Dans une dernière partie, nous présentons un travail effectué durant cette thèse ayant conduit à une publication dans la revue Theoretical Computer Science. Il concerne un problème non-polynomial de la théorie des graphes : le couplage maximal dans les graphes temporels. Cet article propose notamment deux algorithmes de complexité polynomiale : un algorithme de 2-approximation et un algorithme de kernelisation pour ce problème. L’algorithme de 2- approximation peut notamment être utilisé de manière incrémentale : arêtes du flot de liens nous parviennent les unes après les autres, et on construit la 2-approximation au fur et à mesure de leur arrivée.

National audience; This article describes a variation of the spatio-temporal graph model defined by (Del Mondo et al., 2010). This variation allows to represent numerous spatio-temporal entities , that can be vague and disconnected. This model is used to represent data from the Land Parcel Identification System where farmers declare their crops with respect to European agricultural policy. A simplification method is described, that allows to reduce the graph size. Our final aim is to use this model for representing and analyzing big spatio-temporal data in environment sciences.; Dans cet article nous présentons une variante du graphe spatio-temporel défini par (Del Mondo et al., 2010), permettant de tenir compte d'entités spatio-temporelles nombreuses, imprécises, et non connectées. Le graphe proposé est appliqué aux données issues du registre parcellaire graphique, où les agriculteurs déclarent leurs cultures, en respect de la politique agricole européenne. Une méthode de simplification est proposée, afin de réduire la taille du graphe. Notre objectif final est d'utiliser ce modèle pour représenter et fouiller les grandes masses de données spatio-temporelles disponibles en sciences de l'environnement.

This thesis stay in between topology and combinatory. Our first concerned is the problem of realization of dual unit ball of intersection norms on orientable surfaces. We also show a certain relation between intersection norms and Thurston norms on 3-manifolds. On the other part, we show the existence of graph structure on unicellular maps on orientable surface coming from a surgery operation on unicellular maps: a surgery graph. Its happen that surgery graph on unicellular collections and cubic unicellular maps is connected.; Cette thèse se place à l'interface entre la topologie et la combinatoire. On s'intéresse dans un premier temps au problème de réalisation des boules unités duales des normes d'intersections sur les surfaces orientables. On montre aussi un certain lien entre les normes d'intersections et la norme de Thurston sur les 3-variétés.On montre par ailleurs l'existence d'un graphe dit de chirurgie sur l'ensemble des cartes unicellulaires d'une surface orientable. Dans le cas des collections unicellulaires et de cartes cubiques unicellulaires, le graphe de chirurgie s'avère connexe.

In this work, we propose a new approach to detect anomalous graphs in a stream of di- rected and labeled heterogeneous graphs. Our approach uses a new representation of graphs by vectors. This representation is flexible and allows to update the graph vectors as soon as a new edge arrives. In addition, it is applicable to any type of graph and optimizes memory space. Moreover, it allows the detection of anomalies in real-time.

Let $F$ be a family of graphs. Then for every graph $G$ the maximum number of disjoint subgraphs of $G$, each isomorphic to a member of $F$, is at most the minimum size of a set of vertices that intersects every subgraph of $G$ isomorphic to a member of $F$. We say that $F$ packs if equality holds for every graph $G$. Only very few families pack. As the next best weakening we say that $F$ has the Erdős-Posa property if there exists a function $f$ such that for every graph $G$ and integer $k>0$ the graph $G$ has either $k$ disjoint subgraphs each isomorphic to a member of $F$ or a set of at most $f(k)$ vertices that intersects every subgraph of $G$ isomorphic to a member of $F$. The name is motivated by a [classical 1965 result of Erdős and Posa](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93P%C3%B3sa_theorem) stating that for every graph $G$ and integer $k>0$ the graph $G$ has either $k$ disjoint cycles or a set of $O(k\log k)$ vertices that intersects every cycle. Thus the family of all cycles has the Erdős-Posa property with $f(k)=O(k\log k)$. In contrast, the family of odd cycles fails to have the Erdős-Posa property. For every integer $\ell$, a sufficiently large Escher Wall is a non-bipartite graph that has an embedding in the projective plane such that every face is even and every homotopically non-trivial closed curve intersects the graph at least $\ell$ times. In particular, it contains no set of strictly less than $\ell$ vertices such that each odd cycle contains at least one them, yet it has no two disjoint odd cycles. By now there is a large body of literature proving that various families $F$ have the Erdős-Posa property. A very general theorem of Robertson and Seymour says that for every planar graph $H$ the family $F(H)$ of all graphs with a minor isomorphic to $H$ has the Erdős-Posa property. (When $H$ is non-planar, $F(H)$ does not have the Erdős-Posa property.) The present paper proves that for every planar graph $H$ the family $F(H)$ has the Erdős-Posa property with $f(k)=O(k\log k)$, which is asymptotically best possible for every graph $H$ with at least one cycle.

With the evolution of 3D acquisition devices, point clouds have now become an essential representation of digitized scenes. Recent systems are able to capture several hundreds of millions of points in a single acquisition. As multiple acquisitions are necessary to capture the geometry of large-scale scenes, a historical site for example, we obtain massive point clouds, i.e., composed of billions of points. In this thesis, we are interested in the structuration and manipulation of point clouds from acquisitions generated by terrestrial LiDARs. From the structure of each acquisition, graphs, each representing the local connectivity of the digitized surface, are constructed. Created graphs are then linked together to obtain a global representation of the captured surface. We show that this structure is particularly adapted to the manipulation of the underlying surface of massive point clouds, even on computers with limited memory. Especially, we show that this structure allow to deal with two problems specific to that kind of data. A first one linked to the resampling of point clouds, by generating distributions of good quality in terms of blue noise thanks to a Poisson disk sampling algorithm. Another one connected to the construction of centroidal Voronoi tessellations, allowing to enhance the quality of generated distributions and to reconstruct triangular meshes.; Avec l'évolution des dispositifs d'acquisition 3D, les nuages de points sont maintenant devenus une représentation essentielle des scènes numérisées. Les systèmes récents sont capables de capturer plusieurs centaines de millions de points en une seule acquisition. Comme plusieurs acquisitions sont nécessaires pour capturer la géométrie de scènes de grande taille, un site historique par exemple, nous obtenons des nuages de points massifs, i.e., composés de plusieurs milliards de points. Dans cette thèse, nous nous intéressons à la structuration et à la manipulation de nuages de points issus d'acquisitions générées à partir de LiDARs terrestres. A partir de la structure de chaque acquisition, des graphes, représentant chacun la connectivité locale de la surface numérisée, sont construits. Les graphes créés sont ensuite liés entre eux afin d'obtenir une représentation globale de la surface capturée. Nous montrons que cette structure est particulièrement adaptée à la manipulation de la surface sous-jacente aux nuages de points massifs, même sur des ordinateurs ayant une mémoire limitée. Notamment, nous montrons que cette structure permet de traiter deux problèmes spécifiques à ce type de données. Un premier lié au ré-échantillonnage de nuages de points, en générant des distributions de bonne qualité en termes de bruit bleu grâce à un algorithme d'échantillonnage en disques de Poisson. Un autre lié à la construction de diagrammes de Voronoï centroïdaux, permettant l'amélioration de la qualité des distributions générées, ainsi que la reconstruction de maillages triangulaires.

Domination problems (dominating set, independant dominating set, ...) as well as covering problems (vertex-cover, Steiner tree, ...) are NP-complete. However, for most of these problems, it is always possible to construct a (eventually bad) solution in polynomial time, or at least it is possible to determine whether a solution exists. Those problems originally came from industry, but are simplified modelizations of the real life problems. We add additional constraints modeling plausible practical constraints : conflicts which are pairs of elements that cannot apear simultaneously in a solution (to modelize various incompatibilities), connexity in a second graph (elements of the solution must be able to communicate, and the communication links are a second graph), and obligations which are subsets of interdependant vertices which must be added simultaneously in a solution.We don't aim to model a specific real-world problem, but to study how these plausible constraints affect the complexity of the studied problems. We will see that, in many cases, even determining the existence of a solution (regardless of its size) become hard. The firefighter problem models firefighters aiming to contain a fire spreading turn by turn in a (eventually infinite) graph. We studied this problem with the addition of deplacement constraints for the firefighters (a limited moving speed between turns). We will see that, most of the time, this constraint increase the number of firefighters necessary to contain the fire, but does not trigger such major change as constraints studied in the others problems.; Les problèmes de domination (dominant, dominant indépendant, ...) et de couverture (vertex-cover, arbre de Steiner, ...) sont NP-complets. Pour autant, pour la plupart de ces problèmes, il existe toujours une solution constructible en temps polynomial (potentiellement de valeur objective très mauvaise), ou au moins, il est possible de déterminer facilement (en temps polynomial) l'existence ou non d'une solution. Ces problèmes, initialement issus de situations réelles, sont des modélisations simplistes de ces situations. Nous ajoutons donc des contraintes additionnelles modélisant des contraintes pratiques plausibles : les conflits, des paires d'éléments ne pouvant faire simultanément partie d'une solution (modélisant des incompatibilités diverses), la connexité dans un second graphe (les éléments doivent pouvoir communiquer, et le graphe correspondant à ces liens de communication n'est pas forcément le même) et les obligations, des sous-ensembles d'éléments interdépendants devant être ajoutés simultanément à une solution. Notre but ici n'est pas de modéliser un problème réel précis, mais d'étudier la manière dont ces contraintes modifient la complexité des problèmes étudiés. Nous verrons que dans un grand nombre de cas, déterminer l'existence même d'une solution devient difficile, même sans se préoccuper de leur optimisation. Le problème du firefighter modélise des pompiers tentant de contenir un feu se propageant au tour par tour dans un graphe (potentiellement infini). Nous avons étudié ce problème en ajoutant des contraintes sur le déplacement des pompiers (une vitesse de déplacement limitée entre deux tours). Nous verrons que ces contraintes augmentent en général le nombre de pompiers nécessaires mais ne provoquent pas de changements aussi importants que dans les problèmes précédents.

Our work is a contribution of the parallelization of the Watershed Transform in particular the Watershed cuts which are a notion of watershed introduced in the framework of Edge Weighted Graphs. We have developed a state of art on the sequential watershed algorithms in order to motivate the choice of the algorithm that is the subject of our study, which is the M-border Kernel algorithm. The main objective of this thesis is to parallelize this algorithm in order to reduce its running time. First, we presented a review on the works that have treated the parallelization of the different types of Watershed in order to identify the issues raised by this task and the appropriate solutions to our context. In a second place, we have shown that despite the locality of the basic operation of this algorithm which is the lowering of some edges named the M-border edges; its parallel execution raises a data dependency problem, especially at the M-border edges which have a common non-minimum vertex. In this context, we have proposed three strategies of parallelization of this algorithm that solve this problematic: the first strategy consists of dividing the initial graph into bands called partitions processed in parallel by P processors. The second strategy is to divide the edges of the initial graph alternately into subsets of independent edges. The third strategy consists in examining the vertices instead of the edges of the initial graph while preserving the thinning paradigm on which the sequential algorithm is based. Therefore, the set of non-minima vertices adjacent to the minima ones are processed in parallel. Finally, we studied the parallelization of a segmentation technique based on the M-border kernel algorithm. This technique consists of three main steps which are: regional minima detection, vertices valuation and M-border kernel computation. For this purpose, we began by studying the data dependency of the different stages of this technique and we proposed parallel algorithms for each one of them. In order to evaluate our contributions, we implemented the parallel algorithms proposed in this thesis, on a shared memory multi-core architecture. The results obtained showed a notable gain in terms of execution time. This gain is translated by speedup factors that increase with the number of processors whatever is the resolution of the input images, Notre travail s'inscrit dans le cadre de la parallélisation d’algorithmes de calcul de la Ligne de Partage des Eaux (LPE) en particulier la LPE d’arêtes qui est une notion de la LPE introduite dans le cadre des Graphes à Arêtes Valuées. Nous avons élaboré un état d'art sur les algorithmes séquentiels de calcul de la LPE afin de motiver le choix de l'algorithme qui fait l'objet de notre étude qui est l'algorithme de calcul de noyau par M-bord. L'objectif majeur de cette thèse est de paralléliser cet algorithme afin de réduire son temps de calcul. En premier lieu, nous avons présenté les travaux qui se sont intéressés à la parallélisation des différentes variantes de la LPE et ce afin de dégager les problématiques que soulèvent cette tâche et les solutions adéquates à notre contexte. Dans un second lieu, nous avons montré que malgré la localité de l'opération de base de cet algorithme qui est l’abaissement de la valeur de certaines arêtes nommées arêtes M-bord, son exécution parallèle se trouve pénaliser par un problème de dépendance de données, en particulier au niveau des arêtes M-bord qui ont un sommet non minimum commun. Dans ce contexte, nous avons proposé trois stratégies de parallélisation de cet algorithme visant à résoudre ce problème de dépendance de données. La première stratégie consiste à diviser le graphe de départ en des bandes appelées partitions, et les traiter en parallèle sur P processeurs. La deuxième stratégie consiste à diviser les arêtes du graphe de départ en alternance en des sous-ensembles d’arêtes indépendantes. La troisième stratégie consiste à examiner les sommets au lieu des arêtes du graphe initial tout en préservant le paradigme d’amincissement sur lequel est basé l’algorithme séquentiel initial. Par conséquent, l’ensemble des sommets non-minima adjacents aux sommets minima sont traités en parallèle. En dernier lieu, nous avons étudié la parallélisation d'une technique de segmentation basée sur l'algorithme de calcul de noyau par M-bord. Cette technique comprend les étapes suivantes : la recherche des minima régionaux, la pondération des sommets et le calcul des sommets minima et enfin calcul du noyau par M-bord. A cet égard, nous avons commencé par faire une étude relative à la dépendance des données des différentes étapes qui la constituent et nous avons proposé des algorithmes parallèles pour chacune d'entre elles. Afin d'évaluer nos contributions, nous avons implémenté les différents algorithmes parallèles proposés dans le cadre de cette thèse sur une architecture multi-cœurs à mémoire partagée. Les résultats obtenus ont montré des gains en termes de temps d’exécution. Ce gain est traduit par des facteurs d’accélération qui augmentent avec le nombre de processeurs et ce quel que soit la taille des images à segmenter

In this thesis we show that symbolic reasoning associated with arc consistency checking is an efficient tool for images interpretation. We first show that this theoretical framework makes it possible to verify the spatial organization of different components of a complex object in an image. We then propose to extend the use of this framework to the selective recognition of shapes described by mathematical equations, thanks to the notion of hyper-arc consistency with bi-levels constraint. The relevance and feasibility of this approach have been validated by multiple tests. In addition, the results obtained on over-segmented images show that the proposed method is noise-resistant, even under conditions where humans (in some cases visual agnosia) may fail. These results support the interest of symbolic reasoning in image understanding.; Dans cette thèse nous montrons que le raisonnement symbolique associé à la vérification de la consistance d'arc avec propagation de contraintes est un outil efficace pour interpréter les images. Nous montrons dans un premier temps que ce cadre théorique permet de vérifier l'organisation spatiale de différentes composantes d'un objet complexe dans une image. Nous proposons ensuite d'étendre l'utilisation de celui-ci à la reconnaissance sélective des formes décrites par des équations mathématiques, grâce à la notion de consistance d'hyper-arc à deux niveaux de contraintes. La pertinence et la faisabilité de cette approche ont été validées par de multiples tests. En outre, les résultats obtenus sur des images sur-segmentées montrent que la méthode proposée est résistante au bruit, même dans des conditions où les humains (dans certains cas d'agnosie visuelle) peuvent échouer. Ces résultats soutiennent l'intérêt du raisonnement symbolique dans la compréhension de l'image.

The scope of this PhD is twofold and can be integrated simultaneously in quantum infor­mation theory and energy transport. We theoretically study the excitonic quantum transport in order to transmit either quantum information or energy on complex molecular networks. In this context, we pay a special attention to the modulations that different quantum envi­ronments can generate on the excitonic transport. In a first part of the manuscript, we focus on the quantum transport of information in the presence of a local phononic environment. In this context, we introduce a theoretical approach, named PT*, treating on an equal footing exciton and phonons. Firstly, this theory is applied to a particular case : the star graph. Then, PT* is compared to exact numerical calculations realized on a collection of different graphs. In this context, we demonstrate that the PT* approach shows a very strong predictability but also several theoretical and numerical advantages (simulation duration, entanglement interpretations ... ). In a second part of the manuscript, we study the quantum transport of energy on a complex graph in contact with an external absorbing system. We focus on the optimisation of the absorption process ("superradiance transition"). We demonstrate that the topology of the considered network influences the absorption evolution. In order to extend this study, we then consider the presence of a local disorder breaking the inner symetry of the graph. In this context, we show that the disorder can benefically influence the absorption process.; Cette thèse théorique s'inscrit dans l'univers de l'Informatique quantique et celui du transfert d'énergie. Nous étudions le transport quantique d'un exciton utilisé dans le but de véhiculer une information quantique, ou de l'énergie, sur des graphes moléculaires complexes. Dans ce contexte, nous nous intéressons aux effets de différents environnements quantiques pouvant moduler le transport excitonique. Une première partie du manuscrit porte sur le transport d'information quantique en pré­sence d'un environnement de phonons locaux. Dans ce contexte, nous introduisons une ap­proche théorique appelée PT* permettant de traiter sur un pied d'égalité exciton et pho­nons. Cette théorie est tout d'abord appliquée au cas particulier du graphe en étoile. Par la suite, PT* est comparée à des calculs exacts menés sur une collection de graphes variés. Nous montrons ainsi que la théorie PT* possède une très grande force de prédictibilité et de multiples avantages théoriques et numériques ( durée de simulation, interprétations liées à l'intrication ... ) . Dans une deuxième partie du manuscrit, nous étudions le transport quantique d'énergie sur un graphe complexe en contact avec un système externe absorbant. Nous nous intéressons tout particulièrement à la caractérisation du phénomène d'absorption énergétique et son opti­misation (transition de superradiance). Nous mettons en évidence l'impact de la topologie du réseau sur l'évolution du processus d'absorption. Pour étendre cette étude, nous considérons ensuite la présence d'un désordre local brisant la symétrie du réseau de base. Nous montrons alors que le désordre peut influencer positivement l'évolution du processus d'absorption.

The scope of this PhD is twofold and can be integrated simultaneously in quantum infor­mation theory and energy transport. We theoretically study the excitonic quantum transport in order to transmit either quantum information or energy on complex molecular networks. In this context, we pay a special attention to the modulations that different quantum envi­ronments can generate on the excitonic transport. In a first part of the manuscript, we focus on the quantum transport of information in the presence of a local phononic environment. In this context, we introduce a theoretical approach, named PT*, treating on an equal footing exciton and phonons. Firstly, this theory is applied to a particular case : the star graph. Then, PT* is compared to exact numerical calculations realized on a collection of different graphs. In this context, we demonstrate that the PT* approach shows a very strong predictability but also several theoretical and numerical advantages (simulation duration, entanglement interpretations ... ). In a second part of the manuscript, we study the quantum transport of energy on a complex graph in contact with an external absorbing system. We focus on the optimisation of the absorption process ("superradiance transition"). We demonstrate that the topology of the considered network influences the absorption evolution. In order to extend this study, we then consider the presence of a local disorder breaking the inner symetry of the graph. In this context, we show that the disorder can benefically influence the absorption process.; Cette thèse théorique s'inscrit dans l'univers de l'Informatique quantique et celui du transfert d'énergie. Nous étudions le transport quantique d'un exciton utilisé dans le but de véhiculer une information quantique, ou de l'énergie, sur des graphes moléculaires complexes. Dans ce contexte, nous nous intéressons aux effets de différents environnements quantiques pouvant moduler le transport excitonique. Une première partie du manuscrit porte sur le transport d'information quantique en pré­sence d'un environnement de phonons locaux. Dans ce contexte, nous introduisons une ap­proche théorique appelée PT* permettant de traiter sur un pied d'égalité exciton et pho­nons. Cette théorie est tout d'abord appliquée au cas particulier du graphe en étoile. Par la suite, PT* est comparée à des calculs exacts menés sur une collection de graphes variés. Nous montrons ainsi que la théorie PT* possède une très grande force de prédictibilité et de multiples avantages théoriques et numériques ( durée de simulation, interprétations liées à l'intrication ... ) . Dans une deuxième partie du manuscrit, nous étudions le transport quantique d'énergie sur un graphe complexe en contact avec un système externe absorbant. Nous nous intéressons tout particulièrement à la caractérisation du phénomène d'absorption énergétique et son opti­misation (transition de superradiance). Nous mettons en évidence l'impact de la topologie du réseau sur l'évolution du processus d'absorption. Pour étendre cette étude, nous considérons ensuite la présence d'un désordre local brisant la symétrie du réseau de base. Nous montrons alors que le désordre peut influencer positivement l'évolution du processus d'absorption.

Disease spread among agricultural premises is greatly enhanced by cattle trade movements. Preventing spreading is a key issue for economical issues, for instance to prevent trade restrictions, but also for public health. Indeed, many animal diseases affect human beings, such as bovine tuberculosis. Tracing cattle trade movements is aiming at detecting the sources of infection, and thus, helps fighting against disease spread. Accessing databases recording cattle trade movements allows to study the structure and dynamic of the exchanges. To do so, methods developed for Social Network Analysis are more and more adapted and use for these purposes. The aim of this work is to use temporal models and methods to study cattle trade movements. As the development of temporal networks is relatively recent, few analyzes using these methods have been conduct on cattle trade data. Thus, contributions are twofold in this work: taking part to the development of analysis tools of temporal networks, and then, deducting potential ways of enhancement to control and fight against disease spread among holdings.; Les échanges d'animaux d'élevages entre exploitations agricoles favorisent la diffusion à grande échelle des maladies. L’enjeu est non seulement économique, de par les répercussions fortes sur les marchés de produits d’origine animale en cas de crise, mais également de santé publique, de nombreuses maladies animales étant transmissibles à l’homme (comme la tuberculose bovine). La traçabilité des animaux devient alors une question de plus en plus importante pour retrouver les foyers infectieux, et lutter contre la propagation des maladies. Le développement de ce type de données et leur accessibilité grandissante a permis l’émergence d’études sur leur organisation et leur dynamique. Les outils et modèles développés pour l’étude des réseaux sociaux ont été adaptés à l’étude de ces données. L'apport de cette thèse réside dans l’utilisation de mesures et de modèles intégrant l’information temporelle sur les échanges d’animaux. En effet, le développement des réseaux temporels est relativement récent, et peu d’études les ont à ce jour appliqué échanges d’animaux. L’objectif est donc double, participer au développement des outils d’analyse des réseaux temporels, et en déduire des pistes de développement de mesures de surveillance et de lutte contre la propagation des maladies entre exploitations.

In energy network, the knowledge of equipments, their locations and their functions are theimportant information for the distributor service operator. In fact, each operator has a networkplan often named synoptic schema. That schema shows the interconnexion between equipments inthe network. From this schema, some management decisions have taken for ensuring an optimalperformance of a network.Sometimes, a synoptic schema has some mistakes because the maintenance operations, such aschanged the connexion between equipments or replaced equipments, have not been updated orhave been written with errors. And these mistakes increase exploitation cost in the energy network.We consider an electric network of a datacenter. This network consists of physical topologymodelised by a DAG without circuit and measurements are on the edges of a DAG. The mainpoint of the network is that measurements are some mistakes and the topology is unknown i.ewe know edges but the nodes of edges are unknown. When measurements are correct then thecorrelations between pairwise edges provide the adjacency matrix of the linegraph of undirectedgraph of the DAG. A linegraph is a graph in which each node and the neighbor are partitionnedby one or deux cliques. However, with the mistakes in measurements, the obtained graph is nota linegraph because it contains more or less edges. If the obtained graph is a linegraph then it isa linegraph of the other DAG. Our problem is to discovery the topology of the DAG with somemistakes in measurements.We start by the state of art in the measurement correlations in order to choose the good methodfor our problem. Then, we propose two algorithms to resolve our problem. The first algorithmis the cover algorithm and it returns the set of cliques in the graph. The second algorithm is acorrection algorithm which adds or deletes edges in the graph for getting a nearest linegraph ofthe DAG. In the last, we evaluate the performances of the algorithms by checking the number ofedges corrected and the ability to return a nearest linegraph of the DAG.; Dans les réseaux énergétiques, la connaissance des équipements, leurs emplacements et leursfonctions sont les prérequis à l’exploitation de l’infrastucture. En effet, tout opérateur disposed’une carte appelée schéma synoptique indiquant les connexions entre les équipements. À partirde cette carte, sont prises des décisions pour un fonctionnement optimal du réseau.Ce schéma synoptique peut être érronné parce que des opérations de maintenance sur le réseaun’auraient pas été retranscrites ou mal saisies. Et cela peut entrainer des coûts supplémentairesd’exploitation du réseau énergetique.Nous considérons le réseau électrique d’un Datacenter. Ce réseau est composé d’une topologiephysique modélisée par un DAG sans circuit et de mesures électriques sur ces arcs. La particularitéde ce réseau est que les mesures contiennent des erreurs et cette topologie est inconnue c’est-à-direles arcs sont connus mais les extrémités des arcs sont inconnues. Dans le cas où ces mesuressont correctes alors la corrélation des arcs induit la matrice d’adjacence du line-graphe du graphenon-orienté sous-jacent de notre DAG. Un line-graphe est un graphe dans lequel chaque sommet etson voisinage peuvent être partitionnés par une ou deux cliques et que chaque arête est couvertepar une clique. Cependant, avec la présence des erreurs de mesures, nous avons un graphe avecdes arêtes en plus ou en moins qui n’est pas nécessairement un line-graphe. Si ce graphe est unline-graphe alors il n’est pas le line-graphe de notre DAG. Notre problème est de découvrir cettetopologie en se basant sur ces mesures électriques.Nous débutons par une étude bibliographique des corrélations de mesures possibles afin dedéterminer celle qui est pertinente pour notre problème. Ensuite nous proposons deux algorithmespour résoudre ce problème. Le premier algorithme est l’algorithme de couverture et il déterminel’ensemble des cliques qui couvre chaque sommet de notre graphe. Le second algorithme estl’algorithme de correction. Il ajoute ou supprime des arêtes au voisinage d’un sommet non couvertde telle sorte que son voisinage soit partitionné en une ou deux cliques. Enfin, nous évaluons lesperformances de nos algorithmes en vérifiant le nombre d’arêtes corrigées et la capacité à retournerle graphe le plus proche du line-graphe de notre DAG.

Graphs, usually used to model relations between entities, are continually growing mainly because of the internet (social networks for example). Graph visualization (also called drawing) is a fast way of collecting data about a graph. Internet graphs are often stored in a distributed manner, split between several machines interconnected. This thesis aims to develop drawing algorithms to draw very large graphs using the MapReduce paradigm, used for cluster computing. Among graph drawing algorithms, those which rely on a physical model to compute the node placement are generally considered to draw graphs well regardless of the type of graph. We developped two force-directed graph drawing algorithms in the MapReduce paradigm. GDAD, the fist distributed force-directed graph drawing algorithm ever, uses pivots to simplify computations of node interactions. MuGDAD, following GDAD, uses a recursive simplification to draw the original graph, keeping the pivots. We compare these two algorithms with the state of the art to assess their performances.; Les graphes, outil mathématique pour modéliser les relations entre des entités, sont en augmentation constante du fait d'internet (par exemple les réseaux sociaux). La visualisation de graphe (aussi appelée dessin) permet d'obtenir immédiatement des informations sur le graphe. Les graphes issus d'internet sont généralement stockés de manière morcelée sur plusieurs machines connectées par un réseau. Cette thèse a pour but de développer des algorithmes de dessin de très grand graphes dans le paradigme MapReduce, utilisé pour le calcul sur cluster. Parmi les algorithmes de dessin, les algorithmes reposants sur un modèle physique sous-jacent pour réaliser le dessin permettent d'obtenir un bon dessin indépendamment de la nature du graphe. Nous proposons deux algorithmes par modèle de forces conçus dans le paradigme MapReduce. GDAD, le premier algorithme par modèle de force dans le paradigme MapReduce, utilise des pivots pour simplifier le calcul des interactions entre les nœuds du graphes. MuGDAD, le prolongement de GDAD, utilise une simplification récursive du graphe pour effectuer le dessin, toujours à l'aide de pivots. Nous comparons ces deux algorithmes avec les algorithmes de l'état de l'art pour évaluer leurs performances.

Graphs, usually used to model relations between entities, are continually growing mainly because of the internet (social networks for example). Graph visualization (also called drawing) is a fast way of collecting data about a graph. Internet graphs are often stored in a distributed manner, split between several machines interconnected. This thesis aims to develop drawing algorithms to draw very large graphs using the MapReduce paradigm, used for cluster computing. Among graph drawing algorithms, those which rely on a physical model to compute the node placement are generally considered to draw graphs well regardless of the type of graph. We developped two force-directed graph drawing algorithms in the MapReduce paradigm. GDAD, the fist distributed force-directed graph drawing algorithm ever, uses pivots to simplify computations of node interactions. MuGDAD, following GDAD, uses a recursive simplification to draw the original graph, keeping the pivots. We compare these two algorithms with the state of the art to assess their performances., Les graphes, outil mathématique pour modéliser les relations entre des entités, sont en augmentation constante du fait d'internet (par exemple les réseaux sociaux). La visualisation de graphe (aussi appelée dessin) permet d'obtenir immédiatement des informations sur le graphe. Les graphes issus d'internet sont généralement stockés de manière morcelée sur plusieurs machines connectées par un réseau. Cette thèse a pour but de développer des algorithmes de dessin de très grand graphes dans le paradigme MapReduce, utilisé pour le calcul sur cluster. Parmi les algorithmes de dessin, les algorithmes reposants sur un modèle physique sous-jacent pour réaliser le dessin permettent d'obtenir un bon dessin indépendamment de la nature du graphe. Nous proposons deux algorithmes par modèle de forces conçus dans le paradigme MapReduce. GDAD, le premier algorithme par modèle de force dans le paradigme MapReduce, utilise des pivots pour simplifier le calcul des interactions entre les nœuds du graphes. MuGDAD, le prolongement de GDAD, utilise une simplification récursive du graphe pour effectuer le dessin, toujours à l'aide de pivots. Nous comparons ces deux algorithmes avec les algorithmes de l'état de l'art pour évaluer leurs performances.

International audience; As a result of half a century of transformations due to successive urban policies, Algiers today is a spread, fragmented and disjointed agglomeration. It also faces real challenges in terms of planning of transport and mobility. The automobile dependency status is reflected by the fact that it has become essential for daily movements for a large part of the population. The organization and efficiency of the transport system and urban form directly influences the mode of transport favored by the population. Our article proposes to compare the performance of private automotive system and public transport in terms of accessibility. Through the establishment of a GIS database and a comparative approach, the result of this work allowed us to better understand the space-time dimension in Algiers and the evolution of accessibility, that have happened to the various agglomerations between 2004 and 2015. Indeed, this approach has never been the subject of a deep analysis in the various researches on the city of Algiers. An accessibility modeling appears to be a very interesting approach, firstly to have a clear vision of “accessibility”, one of the decisive parameters of any transport policy and also to better appreciate the consequences of the various public transport policies.; Après un demi-siècle de transformations urbaines (conséquences de politiques urbaines successives), Alger d’aujourd’hui est une agglomération étalée, éclatée, fragmentée et discontinue. Elle est également confrontée à de véritables enjeux en matière de planification des transports et de la mobilité.Le concept de dépendance à l’automobile reflète le fait que cette dernière soit devenue indispensable pour l’ensemble des déplacements quotidiens d’une majeure partie de la population. L’organisation et l’efficacité du système des transports et la forme urbaine influencent directement le mode de transport privilégié par la population. Notre article se propose de comparer la performance du système automobile et du transport en commun sous l’angle de l’accessibilité.À travers la mise en place d’une base de données sous SIG et par une approche comparative, le résultat de ce travail nous a permis une meilleure lecture de la dimension espace- temps à Alger ainsi que l’évolution de l’accessibilité qu’ont subie les différentes agglomérations entre 2004 et 2015.En effet, cette approche n’a jamais fait l’objet d’une analyse profonde dans le cadre des différentes recherches sur la ville d’Alger. Une modélisation de l’accessibilité apparaît comme une ligne directrice très intéressante, d’une part pour avoir une vision claire de l’un des paramètres décisifs de toute politique de transport «l’accessibilité », et d’autre part pour mieux apprécier les conséquences des différentes politiques publiques en matière de transport.

This thesis gives a general framework for Laplaciansdefined in terms of the combinatorial structure of asimplicial complex. More precisely, we introduce thenotion of orientated triangle face in a connected,orientated and locally finite graph. This structure of a2-simplicial complex allows to define our discreteLaplacian which acts on the triplets of functions,1-forms and 2-forms. In this context, we are interestedin studying the essential self-adjointness of ourLaplacian. Thus, we introduce the geometricalhypothesis of x-completeness on triangulations toensure the essential self-adjointness of theGauß-Bonnet operator. This thesis deals also withquestions of specral theory of finite triangulations onour Laplacian. We find an estimate for the upperLaplacian spectral gap in a triangulation of a completegraph for which we generalize the definition of theCheeger constant which gives us an upper bound.Moreover, we obtain a lower bound of this estimate bythe first non-zero eigenvalue of the discrete Laplaciandefined on the space of functions on the vertices.; Cette thèse donne un cadre général pour lesLaplaciens définis en termes de structurecombinatoire d’un complexe simplicial. Plusprécisément, nous introduisons la notion de facetriangle orientée dans un graphe connexe, orienté etlocalement fini. Cette structure de 2-complexesimplicial permet de définir notre Laplacien discret quiagit sur les triplets de fonctions, 1-formes et 2-formes.Dans ce contexte, nous nous intéressons à l’étude ducaractère essentiellement auto-adjoint de notreLaplacien. Pour cela, on introduit l’hypothèsegéométrique de x-complétude sur les tiangulationspour garantir le caractère essentiellement auto-adjointà l’opérateur de Gauß-Bonnet. Cette thèse traiteégalement de questions de théorie spectrale destriangulations finies portant sur notre Laplacien. Noustrouvons une estimation pour le trou spectral duLaplacien supérieur dans une triangulation d’ungraphe complet pour lequel nous généralisons ladéfinition de la constante de Cheeger qui nous donneune majoration explicite. En outre, nous obtenons uneminoration de cette estimation par la première valeurpropre non nulle du Laplacien discret défini surl’espace des fonctions sur les sommets.

International audience; The visualisation of relations, exchanges, flows or traffic, constitutes a classical problem for spatial representation. Innovative ways of displaying data, in this case graphical web tools, allow us to explore new technical possibilities and to assess their interest. In this paper, we would like to propose a way to combine two visualisation techniques, complementary but often mutually exclusive: the network graph (node-link diagram) and the flow map. Indeed, a graph focuses on the structure, the organisation of the relations between nodes of the network (centrality, connectivity), albeit at the expense of the geography (localisation, distances). A flow map serve the inverse principle. Our paper will be based on two previous research datasets to uncover the advantages of the dual interactive visualisation we propose. The first dataset deals with the international waste trade and the second with scientific relations between cities (co-authorship and citation data).; La visualisation des relations, échanges, flux ou circulations, constitue un problème classique de la représentation des territoires. La disponibilité de moyens innovants, en l'occurrence les outils graphiques web interactifs, permet d'explorer de nouvelles possibilités techniques et d'en critiquer la mise en œuvre. Dans cette communication, nous proposons un moyen de combiner deux solutions de visualisation complémentaires mais souvent mutuellement exclusives : le graphe (diagramme noeuds-liens) et la carte de flux. En effet, le graphe se focalise sur la structure, l'organisation des relations entre les éléments du réseau (centralité, connectivité), mais aux dépens de la géographie (localisation, distances). La carte de flux présente la caractéristique inverse. La communication se basera sur des jeux de données travaillés précédemment pour dégager les avantages de notre proposition méthodologique : d'une part les données du commerce international de six matières premières recyclables et d'autre part les données mondiales de collaborations scientifiques entre villes.

The problems of continuous optimization are numerous, in economics, in signal processing, in neural networks, and so on. One of the best-known and most widely used solutions is the evolutionary algorithm, a metaheuristic algorithm based on evolutionary theories that borrows stochastic mechanisms and has shown good performance in solving problems of continuous optimization. The use of this family of algorithms is very popular, despite the many difficulties that can be encountered in their design. Indeed, these algorithms have several parameters to adjust and a lot of operators to set according to the problems to solve. In the literature, we find a plethora of operators described, and it becomes complicated for the user to know which one to select in order to have the best possible result. In this context, this thesis has the main objective to propose methods to solve the problems raised without deteriorating the performance of these algorithms. Thus we propose two algorithms:- a method based on the maximum a posteriori that uses diversity probabilities for the operators to apply, and which puts this choice regularly in play,- a method based on a dynamic graph of operators representing the probabilities of transitions between operators, and relying on a model of the objective function built by a neural network to regularly update these probabilities. These two methods are detailed, as well as analyzed via a continuous optimization benchmark, Les problèmes d'optimisation continue sont nombreux, en économie, en traitement de signal, en réseaux de neurones, etc. L'une des solutions les plus connues et les plus employées est l'algorithme évolutionnaire, métaheuristique basée sur les théories de l'évolution qui emprunte des mécanismes stochastiques et qui a surtout montré de bonnes performances dans la résolution des problèmes d'optimisation continue. L’utilisation de cette famille d'algorithmes est très populaire, malgré les nombreuses difficultés qui peuvent être rencontrées lors de leur conception. En effet, ces algorithmes ont plusieurs paramètres à régler et plusieurs opérateurs à fixer en fonction des problèmes à résoudre. Dans la littérature, on trouve pléthore d'opérateurs décrits, et il devient compliqué pour l'utilisateur de savoir lesquels sélectionner afin d'avoir le meilleur résultat possible. Dans ce contexte, cette thèse avait pour objectif principal de proposer des méthodes permettant de remédier à ces problèmes sans pour autant détériorer les performances de ces algorithmes. Ainsi nous proposons deux algorithmes :- une méthode basée sur le maximum a posteriori qui utilise les probabilités de diversité afin de sélectionner les opérateurs à appliquer, et qui remet ce choix régulièrement en jeu,- une méthode basée sur un graphe dynamique d'opérateurs représentant les probabilités de passages entre les opérateurs, et en s'appuyant sur un modèle de la fonction objectif construit par un réseau de neurones pour mettre régulièrement à jour ces probabilités. Ces deux méthodes sont détaillées, ainsi qu'analysées via un benchmark d'optimisation continue

I will prove the existence of a function $f_n$ with values in $\mathbb{N}$ on any Graph $G/\{X_1, \cdots, X_n\}$ with cardinal n , such that either $f_n(X_1) $is equal to $0$ or it is the sum of all hamiltonian cycles. The number of operations to be performed to calculate $f_n(X_1) $ is of the order $\mathcal{O}(n^3)$ and that it follows that we have $P=NP$, Je démontre l'existence d'une fonction $f_n$ à valeurs dans $\mathbb{N}$ sur tout Graphe $G/\{X_1, \cdots, X_n\}$ } de cardinal n , telle que soit $f_n(X_1) $ est égal à 0 soit elle est la somme de tous les cycles hamiltoniens. Le nombre d'opérations à effectuer pour calculer $f_n(X_1) $ est de l'ordre de $\mathcal{O}(n^3)$ et il en résulte qu'on a bien P=NP .

In energy network, the knowledge of equipments, their locations and their functions are theimportant information for the distributor service operator. In fact, each operator has a networkplan often named synoptic schema. That schema shows the interconnexion between equipments inthe network. From this schema, some management decisions have taken for ensuring an optimalperformance of a network.Sometimes, a synoptic schema has some mistakes because the maintenance operations, such aschanged the connexion between equipments or replaced equipments, have not been updated orhave been written with errors. And these mistakes increase exploitation cost in the energy network.We consider an electric network of a datacenter. This network consists of physical topologymodelised by a DAG without circuit and measurements are on the edges of a DAG. The mainpoint of the network is that measurements are some mistakes and the topology is unknown i.ewe know edges but the nodes of edges are unknown. When measurements are correct then thecorrelations between pairwise edges provide the adjacency matrix of the linegraph of undirectedgraph of the DAG. A linegraph is a graph in which each node and the neighbor are partitionnedby one or deux cliques. However, with the mistakes in measurements, the obtained graph is nota linegraph because it contains more or less edges. If the obtained graph is a linegraph then it isa linegraph of the other DAG. Our problem is to discovery the topology of the DAG with somemistakes in measurements.We start by the state of art in the measurement correlations in order to choose the good methodfor our problem. Then, we propose two algorithms to resolve our problem. The first algorithmis the cover algorithm and it returns the set of cliques in the graph. The second algorithm is acorrection algorithm which adds or deletes edges in the graph for getting a nearest linegraph ofthe DAG. In the last, we evaluate the performances of the algorithms by checking the number ofedges corrected and the ability to return a nearest linegraph of the DAG., Dans les réseaux énergétiques, la connaissance des équipements, leurs emplacements et leursfonctions sont les prérequis à l’exploitation de l’infrastucture. En effet, tout opérateur disposed’une carte appelée schéma synoptique indiquant les connexions entre les équipements. À partirde cette carte, sont prises des décisions pour un fonctionnement optimal du réseau.Ce schéma synoptique peut être érronné parce que des opérations de maintenance sur le réseaun’auraient pas été retranscrites ou mal saisies. Et cela peut entrainer des coûts supplémentairesd’exploitation du réseau énergetique.Nous considérons le réseau électrique d’un Datacenter. Ce réseau est composé d’une topologiephysique modélisée par un DAG sans circuit et de mesures électriques sur ces arcs. La particularitéde ce réseau est que les mesures contiennent des erreurs et cette topologie est inconnue c’est-à-direles arcs sont connus mais les extrémités des arcs sont inconnues. Dans le cas où ces mesuressont correctes alors la corrélation des arcs induit la matrice d’adjacence du line-graphe du graphenon-orienté sous-jacent de notre DAG. Un line-graphe est un graphe dans lequel chaque sommet etson voisinage peuvent être partitionnés par une ou deux cliques et que chaque arête est couvertepar une clique. Cependant, avec la présence des erreurs de mesures, nous avons un graphe avecdes arêtes en plus ou en moins qui n’est pas nécessairement un line-graphe. Si ce graphe est unline-graphe alors il n’est pas le line-graphe de notre DAG. Notre problème est de découvrir cettetopologie en se basant sur ces mesures électriques.Nous débutons par une étude bibliographique des corrélations de mesures possibles afin dedéterminer celle qui est pertinente pour notre problème. Ensuite nous proposons deux algorithmespour résoudre ce problème. Le premier algorithme est l’algorithme de couverture et il déterminel’ensemble des cliques qui couvre chaque sommet de notre graphe. Le second algorithme estl’algorithme de correction. Il ajoute ou supprime des arêtes au voisinage d’un sommet non couvertde telle sorte que son voisinage soit partitionné en une ou deux cliques. Enfin, nous évaluons lesperformances de nos algorithmes en vérifiant le nombre d’arêtes corrigées et la capacité à retournerle graphe le plus proche du line-graphe de notre DAG.

Disease spread among agricultural premises is greatly enhanced by cattle trade movements. Preventing spreading is a key issue for economical issues, for instance to prevent trade restrictions, but also for public health. Indeed, many animal diseases affect human beings, such as bovine tuberculosis. Tracing cattle trade movements is aiming at detecting the sources of infection, and thus, helps fighting against disease spread. Accessing databases recording cattle trade movements allows to study the structure and dynamic of the exchanges. To do so, methods developed for Social Network Analysis are more and more adapted and use for these purposes. The aim of this work is to use temporal models and methods to study cattle trade movements. As the development of temporal networks is relatively recent, few analyzes using these methods have been conduct on cattle trade data. Thus, contributions are twofold in this work: taking part to the development of analysis tools of temporal networks, and then, deducting potential ways of enhancement to control and fight against disease spread among holdings., Les échanges d'animaux d'élevages entre exploitations agricoles favorisent la diffusion à grande échelle des maladies. L’enjeu est non seulement économique, de par les répercussions fortes sur les marchés de produits d’origine animale en cas de crise, mais également de santé publique, de nombreuses maladies animales étant transmissibles à l’homme (comme la tuberculose bovine). La traçabilité des animaux devient alors une question de plus en plus importante pour retrouver les foyers infectieux, et lutter contre la propagation des maladies. Le développement de ce type de données et leur accessibilité grandissante a permis l’émergence d’études sur leur organisation et leur dynamique. Les outils et modèles développés pour l’étude des réseaux sociaux ont été adaptés à l’étude de ces données. L'apport de cette thèse réside dans l’utilisation de mesures et de modèles intégrant l’information temporelle sur les échanges d’animaux. En effet, le développement des réseaux temporels est relativement récent, et peu d’études les ont à ce jour appliqué échanges d’animaux. L’objectif est donc double, participer au développement des outils d’analyse des réseaux temporels, et en déduire des pistes de développement de mesures de surveillance et de lutte contre la propagation des maladies entre exploitations.

The current definitions of a critical infrastructure are not adapted to the actual attacks which are observed these days. The problem is the same for the definition of an attack and therefore, the term « cyber attack » tends to reduce the conceptual and operational field of the person in charge of the security. Most of the approaches are reduced to identify the technical and IT domain only, and they forget the others domains specific to the intelligence. Then, the main methodologies to identify and to manage risk (EBIOS or some similar methodologies) take into account a definition of a critical infrastructure which is restrictive, static and local. The model of attacker and attack is also extremely narrowed as the technical approaches and the angles of attack of an attacker tend to be restricted to the IT domain only, even if the « cyber » angles may not exist or may only be a small part of an attack scenario.Therefore, it is necessary to have a new definition of a critical infrastructure, more complete and made according to the attacker point of view. Indeed, critical infrastructures can be protected by assessing the threats and vulnerability. This thesis aims to develop new models of infrastructure and attack accurately, models which will based on graph theory, with or without the cyber part. This graph-based representation is already used a lot to describe infrastructure, it will be enriched in order to have a more exhaustive view of an infrastructure environment. The dependencies with other entities (people, others critical infrastructures, etc.) have to be taken into account in order to obtain pertinent attack scenarios. This enriched representation must lead to new models of attackers, more realistic and implementing external components of the infrastructure which belong to its immediate environment. The main objective is the research of optimal paths or other mathematical structures which can be translated into attack scenarios. This global approach provides a finer (and therefore more realistic) definition of security as the lowest cost of the attack path.The research program is structured in five stages. The first two steps are aimed at defining the models and objects representing the security infrastructures as well as the attackers they are confronted with. The major difficulty encountered in developing a relevant infrastructure model is its ability to describe. Indeed, the more the model is rich, the more it can describe the infrastructure and the adversaries that attack it. The counterpart of developing a relevant model is its exponential characteristic. In these security models, we therefore expect that the problem of finding the vulnerabilities of a security infrastructure is equivalent to difficult problems, i.e. NP-hard or even NP-complete. The locks to be lifted will therefore consist in the design of heuristics to answer these problems in finite time with an ``acceptable" response. The third step is to define a generic methodology for assessing the safety of a security infrastructure. In order to validate the proposed models and methodology, the thesis program provides for the development of a research demonstrator in the form of an evaluation platform. Finally, the last step will be to evaluate an existing system from the platform by implementing the proposed methodology. The objective of this last step is to validate the models and the methodology and to propose an improvement if necessary., Les définitions actuelles des infrastructures de sécurité (française, européenne, G-20) sont inadaptées à la réalité des attaques observées ou potentielles. Il en est de même des attaques elles-mêmes et en conséquence le terme « cyberattaque » réduit considérablement le champ conceptuel et opérationnel de celui qui est en charge de la protection et de la défense. La quasi-totalité des approches se réduit à identifier le champ strictement technique informatique (systèmes, réseaux) et à oublier d’autres dimensions propres au renseignement. Ainsi les principales méthodologies d’identification et de gestion du risque (EBIOS ou méthodologies similaires) considèrent une définition particulièrement restrictive, statique et locale de la notion d’infrastructure critique. La modélisation elle-même des attaquants et des attaques est extrêmement réduite. La principale erreur est de restreindre les approches techniques et les angles d’attaque d’un attaquant au seul champ informatique. Les angles « cyber » peuvent ne pas exister ou représenter un volet limitée dans un scenario global d’attaque. En outre, l’approche classique néglige le volet opérationnel gouvernant la préparation et la conduite de la manœuvre dans une attaque. Les modélisations par arbres d’attaques sont également très limitées du fait d’une restriction au seul champ cyber (systèmes et réseaux).Il est alors nécessaire de concevoir une définition très élargie, laquelle doit être dictée par la vision de l'attaquant et non celle du défenseur. Cette thèse vise à développer de nouveaux modèles d'infrastructure de sécurité basés sur la théorie des graphes et a modéliser de manière très élargie le concept d’attaque, incluant ou non un champ cyber. Cette représentation déjà utilisée pour décrire la topologie des infrastructures critiques sera enrichie pour appréhender de manière exhaustive l'environnement avec lesquelles elles interagissent. Les interdépendances avec d’autres entités (personnes, autres infrastructures critiques…) sont un élément clef dans la construction de scenarii d’attaques sophistiquées. Cette représentation enrichie doit aboutir à des nouveaux modèles d'attaquants, plus réalistes et mettant en œuvre des composants externes de l'infrastructure mais appartenant à son environnement proche. L'objectif majeur est la recherche de chemins optimaux dans un scénario d'attaque défini par l'objectif de l'adversaire. Cette approche globale, apporte une définition plus fine (et donc plus réaliste) de la sécurité comme étant le coût le plus faible du chemin d'attaque pris sur l'ensemble des adversaires réalistes (polynomiaux, i.e. agissant en temps fini).Le programme de recherche est structuré en cinq étapes. Les deux premières étapes visent à définir les modèles et les objets représentant les infrastructures de sécurité ainsi que les attaquants auxquelles elles sont confrontées. La troisième étape consiste en la définition d'une méthodologie générique pour évaluer la sécurité d'une infrastructure de sécurité. Cette étape doit aboutir à la conception d'heuristiques de recherche de vulnérabilités. Afin de valider les modèles et la méthodologie proposés, le programme de thèse prévoit le développement d'un démonstrateur recherche sous la forme d'une plate-forme d'évaluation. Enfin, la dernière étape consistera à l'évaluation d'un système existant à partir de la plate-forme en mettant en œuvre la méthodologie proposée. L'objectif de cette dernière étape est de valider les modèles et la méthodologie et d'en proposer une amélioration si nécessaire.

The current definitions of a critical infrastructure are not adapted to the actual attacks which are observed these days. The problem is the same for the definition of an attack and therefore, the term « cyber attack » tends to reduce the conceptual and operational field of the person in charge of the security. Most of the approaches are reduced to identify the technical and IT domain only, and they forget the others domains specific to the intelligence. Then, the main methodologies to identify and to manage risk (EBIOS or some similar methodologies) take into account a definition of a critical infrastructure which is restrictive, static and local. The model of attacker and attack is also extremely narrowed as the technical approaches and the angles of attack of an attacker tend to be restricted to the IT domain only, even if the « cyber » angles may not exist or may only be a small part of an attack scenario.Therefore, it is necessary to have a new definition of a critical infrastructure, more complete and made according to the attacker point of view. Indeed, critical infrastructures can be protected by assessing the threats and vulnerability. This thesis aims to develop new models of infrastructure and attack accurately, models which will based on graph theory, with or without the cyber part. This graph-based representation is already used a lot to describe infrastructure, it will be enriched in order to have a more exhaustive view of an infrastructure environment. The dependencies with other entities (people, others critical infrastructures, etc.) have to be taken into account in order to obtain pertinent attack scenarios. This enriched representation must lead to new models of attackers, more realistic and implementing external components of the infrastructure which belong to its immediate environment. The main objective is the research of optimal paths or other mathematical structures which can be translated into attack scenarios. This global approach provides a finer (and therefore more realistic) definition of security as the lowest cost of the attack path.The research program is structured in five stages. The first two steps are aimed at defining the models and objects representing the security infrastructures as well as the attackers they are confronted with. The major difficulty encountered in developing a relevant infrastructure model is its ability to describe. Indeed, the more the model is rich, the more it can describe the infrastructure and the adversaries that attack it. The counterpart of developing a relevant model is its exponential characteristic. In these security models, we therefore expect that the problem of finding the vulnerabilities of a security infrastructure is equivalent to difficult problems, i.e. NP-hard or even NP-complete. The locks to be lifted will therefore consist in the design of heuristics to answer these problems in finite time with an ``acceptable" response. The third step is to define a generic methodology for assessing the safety of a security infrastructure. In order to validate the proposed models and methodology, the thesis program provides for the development of a research demonstrator in the form of an evaluation platform. Finally, the last step will be to evaluate an existing system from the platform by implementing the proposed methodology. The objective of this last step is to validate the models and the methodology and to propose an improvement if necessary., Les définitions actuelles des infrastructures de sécurité (française, européenne, G-20) sont inadaptées à la réalité des attaques observées ou potentielles. Il en est de même des attaques elles-mêmes et en conséquence le terme « cyberattaque » réduit considérablement le champ conceptuel et opérationnel de celui qui est en charge de la protection et de la défense. La quasi-totalité des approches se réduit à identifier le champ strictement technique informatique (systèmes, réseaux) et à oublier d’autres dimensions propres au renseignement. Ainsi les principales méthodologies d’identification et de gestion du risque (EBIOS ou méthodologies similaires) considèrent une définition particulièrement restrictive, statique et locale de la notion d’infrastructure critique. La modélisation elle-même des attaquants et des attaques est extrêmement réduite. La principale erreur est de restreindre les approches techniques et les angles d’attaque d’un attaquant au seul champ informatique. Les angles « cyber » peuvent ne pas exister ou représenter un volet limitée dans un scenario global d’attaque. En outre, l’approche classique néglige le volet opérationnel gouvernant la préparation et la conduite de la manœuvre dans une attaque. Les modélisations par arbres d’attaques sont également très limitées du fait d’une restriction au seul champ cyber (systèmes et réseaux).Il est alors nécessaire de concevoir une définition très élargie, laquelle doit être dictée par la vision de l'attaquant et non celle du défenseur. Cette thèse vise à développer de nouveaux modèles d'infrastructure de sécurité basés sur la théorie des graphes et a modéliser de manière très élargie le concept d’attaque, incluant ou non un champ cyber. Cette représentation déjà utilisée pour décrire la topologie des infrastructures critiques sera enrichie pour appréhender de manière exhaustive l'environnement avec lesquelles elles interagissent. Les interdépendances avec d’autres entités (personnes, autres infrastructures critiques…) sont un élément clef dans la construction de scenarii d’attaques sophistiquées. Cette représentation enrichie doit aboutir à des nouveaux modèles d'attaquants, plus réalistes et mettant en œuvre des composants externes de l'infrastructure mais appartenant à son environnement proche. L'objectif majeur est la recherche de chemins optimaux dans un scénario d'attaque défini par l'objectif de l'adversaire. Cette approche globale, apporte une définition plus fine (et donc plus réaliste) de la sécurité comme étant le coût le plus faible du chemin d'attaque pris sur l'ensemble des adversaires réalistes (polynomiaux, i.e. agissant en temps fini).Le programme de recherche est structuré en cinq étapes. Les deux premières étapes visent à définir les modèles et les objets représentant les infrastructures de sécurité ainsi que les attaquants auxquelles elles sont confrontées. La troisième étape consiste en la définition d'une méthodologie générique pour évaluer la sécurité d'une infrastructure de sécurité. Cette étape doit aboutir à la conception d'heuristiques de recherche de vulnérabilités. Afin de valider les modèles et la méthodologie proposés, le programme de thèse prévoit le développement d'un démonstrateur recherche sous la forme d'une plate-forme d'évaluation. Enfin, la dernière étape consistera à l'évaluation d'un système existant à partir de la plate-forme en mettant en œuvre la méthodologie proposée. L'objectif de cette dernière étape est de valider les modèles et la méthodologie et d'en proposer une amélioration si nécessaire.

The one thing in common “archaeological”, “biodiversity” or “social systems” studies share is that data production is both expensive and few automated. Long time series and / or large spatial surveys are difficult to conduct, since it is necessary to use several observers. The robustness and reproducibility of the observation are also harder to get and is obviously impossible in archaeological sciences, even if modeling methods are improved. In a context of multi-source data production, the equivalence of observation systems and the inter-calibration of the observers become crucial. Multi-disciplinary integrative approaches become necessary to study systems where the output of data, in each discipline, is discontinuous, imprecise and poorly distributed. Yet, all variables (characterization of economic activities and human installation, productions studies, characteristics of the discovered or reconstituted objects, biotic or abiotic data, maps of anthropogenic and natural pressures, rendered services and feelings, societal perception...) of these systems interact over time and at each spatial scale. After a few years of existence, ArkeoGIS aggregates 67 databases representing over 50 000 objects (sites, analyzes...). With this standardization of archaeological and paleoenvironmental information, it seemed important to test new data mining methods, to see whether "related" and complex data can be linked to these archaeological data sets. The link between aggregated-bases extracts within ArkeoGIS allowed us to set up a cross-requesting and test possibilities in a prototype developed by the consortium IndexMed. This prototype, open source, allows the establishment of links between objects from different databases. The consortium IndexMed aims to identify and to raise the scientific challenges related to data quality and heterogeneity. The use of graphs allows us to consider data despite their disparity and without prioritization, and improve decision support using emerging data mining methods (collaborative clustering, machine learning, graphs approaches, representation knowledge). Adapting these methods in archeology allows us to go beyond the "simple" data aggregation: ArkeoGIS can therefore also be used to power such tools allowing us to mine our data and metadata., Un point commun des études en archéologie, en écologie ou sur les systèmes sociaux est que la production de données est à la fois coûteuse et peu automatisée. Les suivis de longues séries temporelles et/ou à larges emprises spatiales sont difficiles à mener, dès lors qu’il faut recourir sur une longue durée à plusieurs observateurs. La robustesse et la reproductibilité de l’observation sont aussi plus difficiles à obtenir, voire impossibles en archéologie, même si les méthodes de modélisation se développent. Dans un cadre de production de données multi-sources, l’équivalence des systèmes d’observations et l’inter-calibration d’observateurs deviennent cruciales. Des approches intégratives, pluri- ou trans- disciplinaires, deviennent nécessaires à l’étude de systèmes où la production de données dans chaque discipline est discontinue, plus ou moins précise et mal répartie. Pourtant, toutes les variables (caractérisation des activités économiques, des installations humaines, études des productions, objets reconstitués ou découverts, données biotiques et abiotiques, cartographies des pressions anthropiques et naturelles, services rendus et ressentis, image sociétale...) de ces systèmes interagissent dans le temps et à chaque échelle spatiale. Après quelques années d’existence, ArkeoGIS agrège aujourd'hui 67 bases de données représentant plus de 50 000 objets (sites, analyses...). Fort de cette normalisation de l’information archéologique et paléo-environnementale, il nous a semblé important de tester de nouvelles méthodes de fouille de données, afin de mettre en évidence de possibles données « connexes » et complexes possiblement reliables à ces jeux de données. Le lien entre les extraits des bases agrégées au sein d’ArkeoGIS nous a permis de tester ces approches grâce à un prototype “open source” développé par le consortium IndexMed. Ce prototype permet la mise en place de liens entre objets de bases de données différentes. Le consortium IndexMed a pour objectif d’identifier puis de lever les verrous scientifiques liés à la qualité des données et à leur hétérogénéité. La représentation de l'information sous forme de graphe rend possible la prise en compte des données malgré leur disparité et sans les hiérarchiser, et permet d’améliorer la précision des outils d’aide à la décision utilisant des méthodes émergentes d'analyse de données (clustering collaboratif, classification collective, fouille de graphes, analyse de réseau, extraction de communautés). Adapter ces méthodes à l’archéologie nous permet d’aller au-delà de la « simple » agrégation de données : ArkeoGIS peut donc aussi servir à alimenter les outils de fouille utilisés au sein de nos données et métadonnées.

National audience; La méthode proposée s’intéresse à l’analyse de corpus de textes en histoire. Elle vise à produire un réseau pondéré de documents liés par co-occurrences de mots-clés. L’historien est majoritairement confronté à des textes non-structurés au sens informatique du terme, organisés en corpus. Le corpus est le résultat d’un choix et d’une sélection cohérente ; son contenu est connu qualitativement (lu voire analysé). L’analyse quantitative associée aux connaissances de l’historien se révèle un puissant outil heuristique : elle permet la mise en évidence de nouvelles hypothèses de recherche ou en confirme d’autres déjà établies. Pour cela il faut faire l’hypothèse d’une analyse sans apprentissage ni pré-traitement, centrée sur lecontenu du corpus, sans orientation a priori. La mise en évidence de signaux faibles (co-occurrences d’expressions complexes) permet une analyse fine s’adressant à un spécialiste. Des inférences « bas-niveau » (calcul statistiques) pondèrent les liens de co-occurrences, laissant à l’historien les inférences « haut niveau » : l’interprétation. Le processus se divise en : 1) la gestion du corpus, 2) l’extraction d’expression-clé, 3) la supervisiondes résultats, 4) le calcul de pondération et création des liens. La gestion du corpus (1) peut selon le volume et hétérogénéité faire appel à un factorisation de matrice non-négative, l’extraction (2) est réalisé par un algorithme type C-value inspiré d’ANA (Enguehard, 1993) et propose de construire des catégories avec Wikipedia, la création et pondération des liens (4) est inspiré des fonctionnements de MED (Bu, 2010) et TF-IDF avec effets de seuils. La réduction du graphe multiple (chaque co-occurrence donne un lien entre 2 noeuds) à un graphe de liens simples (lien unique entre 2 nœuds) ainsi que la définition de seuils sur la pondération du lien (logique floue) permet de construire des vues du graphe en adaptant le niveau de détails.