Search

In this thesis, we consider two families of computational problems defined on graphs: proper edge-labellings and combinatorial games. We attack these problems in a similar (and classical) way: we show that they are computationally hard, and then find efficient algorithms for instances with specific structure.First we focus on problems related to proper labellings of graphs. For some natural number k, a k-labelling is a weight function on the edges of a graph G, assigning weights, called labels in this context, from {1, . . . , k}. A k-labelling induces a vertex-colouring of G, where each vertex receives as colour the sum of the labels of its incident edges. A k-labelling is proper if the induced vertex-colouring is proper, i.e., such that any two adjacent vertices of G are assigned different colours. According to the so-called 1-2-3 Conjecture, any connected graph of order at least 3 should admit a proper 3-labelling. We consider three variations of this conjecture. We look into equitable proper k-labellings, for which the assigned labels appear an equal number of times. We then focus on proper labellings that also minimise the sum of labels being used, and finally, proper 3-labellings that also minimise the number of times that the label 3 is assigned. The choice to study these variations is natural. Indeed, an equitable version of the 1-2-3 Conjecture claims that almost every graph G should admit an equitable proper 3-labelling. Also, the sum of labels of such a labelling would be at most 2|E(G)| and it would assign label 3 on at most one third of the edges of G. We prove that the introduced optimisation problems are NP-hard. Furthermore, through structural and algorithmical results, we propose new conjectures for the upper bounds of the parameters that we study, which we verify for specific graph classes (e.g. complete, bipartite, regular, 3-chromatic, etc.). Interestingly, our work gives further evidence that stronger variations of the 1-2-3 Conjecture could hold. We close our study of proper labellings by considering the problem of finding a largest induced subgraph of a given graph that admits a proper 1-labelling. This problem is proven to be computationally hard and not approximable within a ratio of O(|V (G)|^(1-1/c)) for every natural number c. Nevertheless, we provide efficient parameterised algorithms.In the second part of the thesis, we introduce and study the Maker-Breaker largest connected subgraph game. This game is played by two players, Alice and Bob, on a shared, initially uncoloured graph G. The two players take turns colouring the vertices of G, each one with their own colour, until there remains no uncoloured vertex. Alice is the winner of the game if, by the end, the largest connected subgraph of G induced by her colour is of order greater than k, where the natural number k is also given at the start of the game. Otherwise Bob wins the game. We also consider a Maker-Maker version of the same game, played in the same way, but in which the winner is the player whose colour induces the largest connected subgraph of G by the end of the game. We first prove that deciding the outcome of both of these games is PSPACE-hard, and then proceed by providing efficient algorithms when the games are played on particular graph classes (e.g. paths, cycles, cographs, (q, q-4)-graphs, etc.). Comparing the behaviour of these games, one of the main differences we observe is that Bob can never win the Maker-Maker version (if Alice plays optimally). Nevertheless, if Alice can win the Maker-Breaker version when playing on G for a value of k equal to half the order of G (the best outcome she can hopefor), then she can build a connected subgraph of the same order for the Maker-Maker version; such graphs are called A-perfect. We then study regular graphs that are A-perfect and prove that, surprisingly, any 3-regular A-perfect graph has order at most 132. We finish by providing sufficient conditions for a graph to be A-perfect.; Cette thèse considère deux familles de problèmes définis sur des graphes : les étiquetages d'arêtes propres et les jeux combinatoires. Nous traitons ces problèmes de façon similaire (et classique) : nous montrons que les problèmes considérés sont difficiles à résoudre, puis nous trouvons des algorithmes efficaces sur des instances restreintes.Nous nous concentrons d'abord sur des problèmes concernant des étiquetages propres de graphes. Pour un entier k fixé, un k-étiquetage d'un graphe G est une fonction associant à chaque arête de G une étiquette parmi {1, . . . , k}. Un k-étiquetage induit une coloration des sommets de G, où chaque sommet reçoit comme couleur la somme des étiquettes de ses arêtes incidentes. Un k-étiquetage est propre si, dans la coloration induite, deux sommets adjacents de G reçoivent des couleurs différentes. D'après la Conjecture 1-2-3, tout graphe connexe d'ordre au moins 3 admet un 3-étiquetage propre. Nous considérons trois variantes de cette conjecture. Nous étudions les k-étiquetages propres équilibrés, pour lesquels les étiquettes assignées apparaissent dans les mêmes proportions. La deuxième variante concerne les étiquetages propres qui minimisent la somme des étiquettes utilisées. Enfin, nous nous intéressons aux 3-étiquetages propres qui minimisent le nombre de fois où l'étiquette 3 est attribuée. Le choix d'étudier ces variantes est naturel. En effet, une version équilibrée de la Conjecture 1-2-3 est que presque tous les graphes G admettent un 3-étiquetage propre équilibré. En outre, la somme des étiquettes d'un tel étiquetage est au plus égale à 2|E(G)| et associe l'étiquette 3 à au plus un tiers des arêtes de G. Nous prouvons que les problèmes d'optimisation introduits sont NP-difficiles. Grâce à des résultats structurels et algorithmiques, nous sommes amenés à proposer de nouvelles conjectures pour ces problèmes, que nous vérifions sur quelques classes de graphes (complets, bipartis, réguliers, 3-chromatiques, etc.). Notre travail renforce l'idée que des variantes plus fortes de la Conjecture 1-2-3 pourraient être vraies. Nous terminons en considérant le problème consistant à trouver un plus grand sous-graphe induit d'un graphe donné qui admet un 1-étiquetage propre. Il est prouvé que ce problème est difficile à résoudre et qu'il n'est pas approximable à un facteur O(|V (G)|^(1-1/c)) près pour tout entier c. Néanmoins, nous fournissons des algorithmes paramétrés efficaces.La deuxième partie de la thèse introduit le jeu du plus grand sous-graphe connexe Maker-Breaker, joué par deux joueurs, Alice et Bob, sur un graphe G, initialement non coloré. Les joueurs colorent à tour de rôle les sommets de G, chacun avec sa couleur, jusqu'à ce que tous les sommets soient colorés. Alice est la gagnante si, à la fin, le plus grand sous-graphe connexe de G induit par sa couleur est d'ordre au moins k, un entier fixé. Sinon, Bob gagne le jeu. Nous considérons aussi une version Maker-Maker du même jeu, dans laquelle le gagnant est le joueur dont la couleur induit le plus grand sous-graphe connexe de G à la fin du jeu. Nous prouvons que décider de l'issue de ces deux jeux est PSPACE-difficile et nous fournissons des algorithmes efficaces pour le cas où le jeu se déroule dans certaines familles de graphes (chemins, cycles, cographes, (q, q-4)-graphes, etc.). En comparant ces deux jeux, la principale différence que nous observons est que Bob ne peut jamais gagner la version Maker-Maker (si Alice joue de manière optimale). Pour une valeur de k égale à la moitié de l'ordre de G, remarquons que si Alice peut gagner la version Maker-Breaker alors elle peut aussi construire un sous-graphe connexe du même ordre dans la version Maker-Maker ; de tels graphes sont nommés A-parfaits. Nous étudions les graphes réguliers qui sont A-parfaits et prouvons que tout graphe 3-régulier A-parfait a au plus 132 sommets. Nous terminons en fournissant des conditions suffisantes pour qu'un graphe soit A-parfait.

National audience; Déterminer les origines du SARS-CoV-2 est une des quêtes scientifiques parmi les plus fascinantes à l'heure actuelle. Habitué aux découvertes fracassantes de la physique (détection des ondes gravitationnelles, image d'un trou noir, boson de Higgs, etc.), le grand public n'a que rarement l'occasion d'être captivé par les découvertes de bio-informaticiens et autres spécialistes des sciences de l'évolution moléculaire.Or, enquêter sur l’origine de la COVID-19 repose en premier lieu sur une analyse minutieuse des génomes de souches virales collectées lors des premiers stades de ce qui n’était alors qu’une épidémie. Cette enquête met en jeu des outils bien connus dans le domaine de la bio-informatique avec, aux avant-postes, l’analyse phylogénétique. Cette dernière vise à retracer l’histoire évolutive de lignées virales en reconstituant, à partir de la modélisation mathématique, les évènements évolutifs qui ont abouti aux génomes des virus analysés. Nous verrons par la suite comment ce type d’analyse permet de répondre clairement à certaines questions liées aux origines du SARS-CoV-2.

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.

International audience; L’irruption du chemin de fer au cours du XIXe siècle en France a permis d’élargir l’horizon spatio-temporel en créant un choc d’accessibilité. Si l’infrastructure ferroviaire s’est largement diffusée dans sa phase de croissance dans l’ensemble du pays entre 1860 et 1930, la « révolution de la vitesse » permise par le train est loin d’être homogène. Cet article propose d’interroger ces deux dimensions du réseau ferroviaire français dans une perspective géohistorique et quantitative. Il s’agit de montrer la force des phénomènes de hiérarchisation et de sélection dans le façonnement du réseau, tant d’un point de vue spatial que temporel. Pour cela, nous utilisons le formalisme des graphes grâce à la base de données FRANcE (French RAilway NEtwork), qui renferment des informations sur l’extension spatiale du réseau ainsi que sur les vitesses moyennes de chacun des tronçons. Nous utilisons la théorie des graphes pour identifier des principes universels de la science des réseaux et étudier leur inscription dans les territoires traversés. Ces résultats permettent de dresser une « fresque » du développement du chemin de fer : l’accès précurseur des places urbaines les plus dynamiques, l’identification d’axes structurants du réseau dont l’itinéraire peut parfois paraître surprenant, et la mise en place progressive de sous-réseaux. Ce travail participe à la construction d’un instrument de recherche permettant d’explorer les mutations socio-économiques à toutes les échelles, dont les temporalités peuvent être adaptées.

International audience; L'arrivée de Bitcoin a entraîné le passage vers des écosystèmes décentralisés grâce à l'échange de transactions sans tiers de confiance. Cependant, parmi les principaux défis auxquels doivent faire face les blockchains non permissionnées figurent la scalabilité et la sécurité. C'est dans cette optique qu'a été créé Sycomore, un registre distribué orienté graphe dont la structure s'auto-adapte au débit de transactions soumises. Dans cet article, nous présentons et évaluons une extension de Sycomore, Sycomore ++ dont la principale caractéristique est l'auto-adaptation de son débit de création de blocs au débit de transactions soumises. Nous comparons ensuite ses performances à celles de Bitcoin et de Sycomore. En s'appuyant sur des simulations par agents, nous évaluons la capacité de ces registres distribués à relever les défis susmentionnés, dans différents contextes d'exécution. L'un des principaux enseignements tirés de ces simulations est la capacité de Sycomore ++ à réduire considérablement le temps de confirmation des transactions, à réagir rapidement à toute variation soudaine du débit de soumission des transactions et à minimiser le gaspillage d'énergie, en comparaison avec les autres registres distribués basés sur le Proof-of-Work précédemment cités.

International audience; Dans l'objectif de la lutte contre les Chevaux de Troie Matériels, nous proposons d'optimiser une méthode appelé Strong Logic Locking. La mesure de sécurité de cette méthode se base sur les cliques d'un graphe de relation, plus les cliques sont grandes et nombreuses, meilleure sera la sécurité. Nous proposons deux approches pour modéliser et résoudre ce problème.

Dans ce travail, nous proposons une nouvelle lecture du modèle input-output réconciliant la théorie des chaînes de Markov et la théorie de la dominance économique, dans le domaine des interactions interindustrielles. Une lecture plus approfondie de la table de Leontieff en terme de chaîne de Markov est donnée, exploitant les propriétés spectrales et le temps d'absorption pour caractériser les processus de production, puis les dualités local-global/dominance-analyse de sensibilité sont établies, permettant une meilleure compréhension de l'agencement des pôles économiques., In this work, we propose a new lecture of input-output model reconciliation Markov chain and the dominance theory, in the field of interindustrial poles interactions. A deeper lecture of Leontieff table in term of Markov chain is given, exploiting spectral properties and time to absorption to characterize production processes, then the dualities local-global/dominance-Sensitivity analysis are established, allowing a better understanding of economic poles arrangement.

Machine learning has become a popular research topic in recent years, thanks to the reintroduction of neural networks in the early 2010s. The abundance of data and computational power at that time allowed for very good performance in a variety of learning tasks using these neural networks. In recent years, the learning community has focused on generalizing these models to less structured data carried by graphs. Neural networks on graphs have been proposed and have recently met with some success, especially graph convolution networks; they are used in a wide variety of learning models related to graphs. Nevertheless, these networks have limitations, but they can be circumvented by integrating them into an adequate learning model.In this thesis, we have been able to work on some of these representation learning problems for assigned graphs, using these neural networks on graphs. In particular, we have extended CCA (Canonical Correlation Analysis) which is a classical multi-view representation method to attributed graphs, by obtaining interesting properties of robustness and adaptation to a large volume of data. We have also been interested in the issue of Euclidean representation of graphs. We have proposed a multi-scale representation method that can also handle a large volume of data and is inductive; being differentiable from end to end, this method can also be combined with other automatic learning approaches. The method also overcomes one of the limitations of convolution networks, which have difficulty in extracting global information from graphs. Finally, our work explored how to define a notion of distances between graphs and more particularly how to address the issue of metric learning for assigned data sets, by combining neural networks and optimal transport. The objective is then to propose a simple but efficient model for this metric learning task. [Translated with www.DeepL.com/Translator (free version)], L’apprentissage automatique est devenu un sujet populaire de recherche ces dernières années, grâce à la réintroduction des réseaux de neurones au début des années 2010. L’abondance des données et la puissance de calcul à cette période ont permis d’obtenir de très bonnes performances dans un nombre varié de tâches d’apprentissage grâce à ces réseaux de neurones. Ces dernières années la communauté de l’apprentissage s’est attachée à généraliser ces modèles aux données moins structurées qui sont portées par des graphes. Les réseaux de neurones sur graphes ont alors été proposés et ont connu récemment un certain succès, notamment les réseaux de convolution sur graphe ; ils sont utilisés dans une grande variété de modèles d’apprentissages liés aux graphes. Néanmoins ces réseaux ont des limites, mais elles peuvent être contournées notamment en les intégrant dans un modèle adéquat d’apprentissage. Dans cette thèse, nous avons pu travailler sur certaines de ces problématiques d’apprentissage de représentation pour des graphes attribués, en nous appuyant sur ces réseaux de neurones sur graphes. Nous avons notamment étendu la CCA (l'analyse des corrélations canoniques) qui est une méthode de représentation multi-vues classique à des graphes attribués, en obtenant des propriétés intéressantes de robustesses et d'adaptation à un grand volume de données. Nous nous sommes également intéressés à la question de la représentation euclidienne de graphes. On a ainsi proposé une méthode de représentation multi-échelle qui puisse également traiter un grand volume de données et soit inductive ; étant différentiable de bout en bout cette méthode peut aussi être combinée avec d’autres approches d’apprentissages automatiques. La méthode permet aussi de s’affranchir d’une des limitations des réseaux de convolutions qui ont du mal à extraire des informations globales sur les graphes. Enfin, nos travaux ont exploré comment définir une notion de distances entre graphe et plus particulièrement comment aborder la question d'apprentissage de métrique pour des jeux de données attribuées, en combinant des réseaux de neurones et du transport optimal. L'objectif est alors de proposer un modèle simple mais efficace pour cette tâche d'apprentissage de métrique.

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

To explain the biological function of a molecular assembly (MA), one has to know its structural description. It may be ascribed to two levels of resolution: low resolution (i.e. molecular interactions) and high resolution (i.e. relative position and orientation of each molecular subunit, called conformation). Our thesis aims to address the two problems from graph aspects.The first part focuses on low resolution problem. Assume that the composition (complexes) of a MA is known, we want to determine all interactions ofsubunits in the MA which satisfies some property. It can be modeled as a graph problem by representing a subunit as a vertex, then a subunit interaction is an edge, and a complex is an induced subgraph. In our work, we use the fact that a subunit has a bounded number of interactions. It leads to overlaying graph with bounded maximum degree. For a graph family F and a fixed integer k, given a hypergraph H = (V (H), E(H)) (whose edges are subsets of vertices) and an integer s, M AX (∆ ≤ k)-F -O VERLAY consists in deciding whether there exists a graph with degree at most k such that there are at least s hyperedges in which the subgraph induced by each hyperedge (complex) contains an element of F. When s = |E(H)|, it is called (∆ ≤ k)-F -O VERLAY . We present complexity dichotomy results (P vs. NP-complete) for MAX (∆ ≤ k)-F-OVERLAY and (∆ ≤ k)-F-OVERLAY depending on pairs (F, k).The second part presents our works motivated by high resolution problem. Assume that we are given a graph representing the interactions of subunits, a finite set of conformations for each subunit and a weight function assessing the quality of the contact between two subunits positioned in the assembly. Discrete Optimization of Multiple INteracting Objects (D OMINO ) aims to find conformations for the subunits maximizing a global utility function. We propose a new approach based on this problem in which the weight function is relaxed, CONFLICT COLORING . We present studies from both theoretical and experimental points of view. Regarding the theory, we provide a complexity dichotomy result and also algorithmic methods (approximation and fixed paramater tracktability). Regarding the experiments, we build instances of CONFLICT COLORING associated with Voronoi diagrams in the plane. The obtained statistics provide information on the dependencies of the existences of a solution, to parameters used in ourexperimental setup.; Pour comprendre les fonctions biologiques d’un assemblage moléculaire (AM), il est utile d’en avoir une représentation structurale. Celle-ci peut avoir deux niveaux de résolution : basse résolution (i.e. interactions moléculaires) et haute résolution (i.e. position relative et orientation de chaque sous-unité, appelée conformation). Cette thèse s’intéresse à trouver de telles représentations à l’aide de graphes.Dans la première partie, nous cherchons des représentations basse résolution. Etant donné la composition des complexes d’un AM, notre but est de déterminer les interactions entre ses différentes sous-unités. Nous modélisons l’AM à l’aide d’un graphe : les sous-unités sont les sommets, les interactions entre elles sont les arêtes et un complexe est un sous-graphe induit. Utilisant le fait qu’une sous-unité n’a qu’un nombre limité d’interactions, nous arrivons au problème suivant. Pour un graphe F et un entier k fixés, étant donné un hypergraphe H et un entier s, MAX (∆ ≤ k)-F-OVERLAY consiste à décider s’il existe un graphe de degré au plus k tel qu’au moins s hyperarêtes de H induisent un sous-graphe contenant F (en tant que sous-graphe). La restriction au cas s = |E(H)| est appelée (∆ ≤ k)-F-OVERLAY . Nous donnons une dichotomie de complexité (P vs. NP-complet) pour MAX (∆ ≤ k)-F-OVERLAY et (∆ ≤ k)-F-OVERLAY en fonction du couple (F, k).Dans la seconde partie, nous nous attaquons à la haute résolution. Nous sont donnés un graphe représentant les interactions entre sous-unités, un ensemble de conformations possibles pour chaque sous-unité et une fonction de poids représentant la qualité de contact entre les conformations de deux sous-unités interagissant dans l’assemblage. Le problème Discrete Optimization of Multiple INteracting Objects (D OMINO ) consiste alors à trouver les conformations pour les sous-unités qui maximise une fonction d’utilité globale. Nous proposons une nouvelle approche à ce problème en relâchant la fonction de poids, ce qui mène au problème de graphe CONFLICT COLORING . Nous donnons tout d’abord des résultats de complexité et des algorithmes (d’approximation et à paramètre fixé). Nous menons ensuite des expérimentations sur des instances de CONFLICT COLORING associées à des diagrammes de Voronoi dans le plan. Les statistiques obtenues nous informent sur comment les parmètres de notre montage expérimental influe sur l’existence d’une solution.

International audience

Ces transparents ont pour but de présenter de façon la plus complète possible l'existant du Dictionnaire Electronique de Synomynes (DES), outil du laboratoire CRISCO qui génère de 150.000 à 200.000 requêtes par jour.Les points abordés sont : l'historique du projet, les statistiques d'accès, la gestion de la maintenance, les éléments composants le DES et l'espace sémantique ( calcul des premiers synonymes, les cliques, la réduction de dimension, la féminisation, les liaisons litigieuses, le calcul des liens probables ...).

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.

For the last 25 years, complex networks have been an active field of research. The size of the networks studied imposes to model their structure in order to make it understandable. Many models have been put forward to do so, whether based on nodes’ degree, on a partition of the node into blocks, on an embeddeding in a latent space, etc. The estimation of those models’ parameters has shown how important it is to follow a rigourous statistical approach in order to avoid both overfitting and underfitting. In this thesis, we build on this previous work to develop two methodologies aiming at evaluating the relevance of a model with respect to a given graph. First, we study the geometric structure of the microcanonical ensemble and highlight the existence of a characteristic radius for various models. This allows us to suggest a statistical testing methodology inspired from the principles of the p-value to test a model. Then, to tackle the issue of the lack of observations compared with the number of parameters of the model, we focused on edge models. We suggest a methodology to evaluate a model, based on the minimum description length. Its main benefits are its rigorous statistical grounds, which allow for an interpretation of the results, and a common formulation for models of different nature (SBM and configuration model, for example) which allows to compare their performance on a graph. All along our work, we remained careful to follow a formal approach which allowed us to proove various properties about the methodologies described, particularly about the convergence of the estimators., Depuis vingt-cinq ans, l’étude de réseaux complexes est un domaine de recherche particulièrement actif. La taille des réseaux étudiés impose de modéliser leur structure pour la rendre compréhensible. De nombreux modèles ont été proposés pour cela, basés sur le degré des nœuds, une partition des nœuds en blocs, des plongements dans des espaces sous-jacents, etc. L’estimation des paramètres de ces modèles a mis en évidence la nécessité d’une approche statistique rigoureuse pour éviter le sur-apprentissage aussi bien que le sous-apprentissage. Dans cette thèse, nous nous appuyons sur ces résultats pour proposer deux méthodologies qui permettent d’évaluer la pertinence d’un modèle pour un graphe donné. Dans un premier temps, nous avons étudié la structure géométrique de l’ensemble microcanonique, mettant en évidence un rayon caractéristique pour plusieurs modèles. Cela nous a permis de proposer un test statistique s’inspirant des principes de la p-valeur pour tester un modèle. Dans un deuxième temps, pour pallier au problème du manque d’observation par rapport au nombre de paramètres des modèles considérés, nous nous sommes concentrés sur des modèles d’arêtes. Cela nous a permis de proposer une méthodologie pour évaluer un modèle, basée sur la longueur de description minimale. Ses avantages principaux sont d’une part des fondements statistiques rigoureux qui permettent une interprétation des résultats obtenus, et d’autre part une formulation commune pour des modèles de nature différente (SBM et configuration model, par exemple), qui permet de comparer leurs performances sur un même graphe. Tout au long de notre travail, nous nous sommes attachés à suivre une approche formelle qui nous a permis de prouver plusieurs résultats sur les méthodes proposées, en particulier concernant la convergence des estimateurs.

In this thesis, we study some graph coloring problems. We are interested intwo families of colorings.The first one consists in coloring graphs, called signed graphs, modeling social links. These signed graphs dispose of two types of edges: positive edges to represent friendship and negative edges for animosity. Coloring signed graphs is done through the notion of homomorphism: the chromatic number of a signed graph (G, σ) is the smallest order of a signed graph (H, π) to which (G, σ) admits a homomorphism. We study the complexity of homomorphisms of signed graphs when the target graph is fixed and when the input can be modified, giving P/NP-complete dichotomies and FPT/W[1]-hard dichotomies. We also present bounds on the chromatic number of signed graphs when the input graph has few cycles. Finally, we study the relationship between homomorphisms of signed graphs and the Cartesian product of signed graphs.The second family of colorings consists in coloring edges, instead of vertices, according to some constraints. We study four kinds of edge-colorings notions: packing edge-colorings, injective edge-colorings, AVD colorings and 1-2-3-labellings. Packing edge-coloring is a form of proper edge-coloring where each color has its own conflict rule, for example, color 1 may behave according to the rules of proper edge-colorings while color 2 behave according to the rules of strong edge-colorings. We study packing edge-coloring on subcubic graphs and provide bounds on the number of colors necessary to color the graphs. An injective edge-coloring is an edge-coloring where for any path of length 3, the two non-internal edges of the path receive different colors. We determine the complexity of injective edge-coloring for some classes of graphs. For AVD colorings, i.e. a proper edge-coloring where adjacent vertices are incident with different sets of colors, we obtain bounds on the number of colors required to color the graph when the graph has its maximum degree significantly greater than its maximum average degree and when the graph is planar and has maximum degree at least 12. Finally, we prove the Multiplicative 1-2-3 Conjecture, i.e. that every connected graph (which is not just an edge) can be edge-labelled with labels 1, 2 and 3 so that the coloring of G, obtained by associating with each vertex the product of the labels on edges incident with u, is proper., Dans cette thèse, nous étudions des problèmes de coloration de graphe. Nous nous intéressons à deux familles de colorations.La première consiste à colorer des graphes, appelés graphes signés, modélisant des relations sociales. Ceux-ci disposent de deux types d’arêtes : les arêtes positives pour représenter l’amitié et les arêtes négatives pour l’animosité. Nous pouvons colorer des graphes signés à travers la notion d’homomorphisme : le nombre chromatique d’un graphe signé (G, σ) est alors le nombre minimum de sommets d’un graphe signé (H, π) tel que (G, σ) admet un homomorphisme vers (H, π). Nous étudions la complexité des homomorphismes de graphes signés quand la cible est fixée et quand l’entrée peut être modifiée, et obtenons des dichotomies P/NP-complet et FPT/W[1]-difficile. Nous obtenons des bornes supérieures sur le nombre chromatique d’un graphe signé quand le graphe a peu de cycles. Enfin, nous étudions les relations entre les homomorphismes de graphes signés et le produit Cartésien des graphes signés.La deuxième famille de coloration consiste à colorer les arêtes au lieu des sommets en respectant différents critères. Nous étudions quatre types de colorations d’arêtes : la coloration d’arêtes « packing », la coloration d’arêtes injective, la coloration AVD et les 1-2-3-étiquetages. La coloration d’arêtes « packing » est une forme de coloration propre d’arêtes où chaque couleur a ses propres règles de conflits, par exemple, la couleur 1 pourrait obéir aux règles de la coloration propre d’arêtes tandis que la couleur 2 obéirait aux règles de la coloration forte d’arêtes. Nous étudions cette forme de coloration sur les graphes subcubiques en donnant des bornes supérieures sur le nombre de couleurs nécessaires pour colorer ces graphes. Une coloration d’arêtes injective est une coloration d’arêtes telle que pour chaque chemin de longueur 3, les deux arêtes aux extrémités du chemin n’ont pas la même couleur. Nous déterminons la complexité de la coloration d’arêtes injective sur plusieurs classes de graphes. Pour les colorations AVD, c’est-à-dire les colorations propres d’arêtes où les sommets adjacents sont incidents à des ensembles de couleurs différents, nous obtenons des bornes supérieures sur le nombre de couleurs requises pour colorer le graphe quand le degré maximum du graphe est significativement plus grand que son degré moyen maximum, ou quand le graphe est planaire et a un degré maximum supérieur ou égal à 12. Finalement, nous prouvons la 1-2-3 Conjecture multiplicative : pour tout graphe connexe (non réduit à une arête), on peut colorer ses arêtes avec les couleurs 1, 2 et 3 de telle manière que la coloration (de sommets) obtenue en associant à un sommet le produit des couleurs de ses arêtes incidentes est propre.

In this thesis we study the algorithmic complexity of optimization problems related to the study of social networks. A social network can be modeled by a graph in which the vertices represent the members and the edges their relations. We are interested in two different problems, graph anonymization and community detection.The anonymization of graphs has already been studied and many formalizations of the concept have been proposed in the form of properties. To satisfy them, it is often necessary to transform the initial graph. We will then be careful to provide algorithms that minimize its alteration during the anonymization process. In this thesis we measure the alteration by the number of elementary transformations performed on the graph. We propose to study the minimization of the number of edge rotations required on a graph in order for it to respect a given anonymization property in different cases. Empirical work has already been published and we have tried to pursue it on the complexity and approximation angle. The use of this new operator has allowed for more encouraging negative as well as positive theoretical results than with the previous ones.A community is a social group sharing a common space, goods or interests. This is reflected on the graph by strong connections between its individuals. There are many ways to characterize communities and we focus on definitions based on the optimization of a density function. More precisely, we study a problem of partitioning into dense subgraphs where we try to maximize a global density function. We continue the first works undertaken on this subject and propose more thorough results.For these two problems we have studied different classes including classes of sparse graphs, relatively similar to social networks., Dans cette thèse nous étudions la complexité algorithmique de problèmes d’optimisation liés à l’étude des réseaux sociaux. Un réseau social peut être modélisé par un graphe dans lequel les sommets représentent les membres et les arêtes, leurs relations. Nous nous intéressons à deux problématiques différentes, l’anonymisation de graphes et la détection de communautés. L’anonymisation de graphes a déjà été étudiée et de nombreuses formalisations du concept ont été proposées sous forme de propriétés. Pour les satisfaire, il faut souvent transformer le graphe initial. On sera alors attentif à fournir des algorithmes qui minimisent son altération lors du processus d’anonymisation. Dans cette thèse nous mesurons l’altération subie par le nombre de transformations élémentaires effectuées sur le graphe. Nous proposons d’étudier la minimisation du nombre de rotations d’arêtes nécessaires sur un graphe afin que celui-ci respecte une propriété d’anonymisation donnée dans différents cas de figure. Des travaux empiriques ont déjà été publiés et nous nous sommes attachés à les poursuivre sous l’angle de la complexité et de l’approximation. L’utilisation de ce nouvel opérateur a permis des résultats théoriques négatifs ainsi que positifs, l’ensemble étant plus encourageant que les résultats sur les précédents opérateurs. Une communauté est un groupe social partageant un espace, des biens ou des intérêts communs. Cela se reflète sur le graphe par des fortes connexions entre ses individus. Il existe de nombreuses manières de caractériser les communautés et nous nous sommes concentrés sur les définitions basées sur l’optimisation d’une fonction de densité. Plus précisément nous étudions un problème de partition en sous-graphes denses où l’on cherche à maximiser une fonction de densité globale. Nous poursuivons les premiers travaux entrepris sur ce sujet et proposons des résultats plus approfondis.

International audience; Les applications du traitement automatique des langues (TAL) nourrissent aujourd’hui une bonne partie des langues indo-européennes en raison des corpus linguistiques de qualité disponibles en grande quantité et variété. Les corpus de données open sources en langues africaines étant quasi inexistants, comment arrimer les avancées du TAL à ces langues peu dotées ? Dans cet article, nous examinons le problème de construction des ressources lexicographiques pour les langues peu dotées. Nous souhaitons introduire un modèle de construction des ressources lexicographiques en exploitant les compétences socio-linguistiques des communautés linguistiques locales. Au fil des sections, nous présenterons le nouveau modèle de codification des dictionnaires issue de cette modélisation orientée communauté.

In many scientific fields, studied data have an underlying graph or manifold structure, such as communication networks (whether social or technical), knowledge graphs or molecules. A graph is composed of nodes, also called vertices, connected together by edges. Recently, deep learning algorithms have become state-of-the-art models in many fields, and in particular in natural language processing and image analysis. It led the way to a great line of studies to generalize deep learning models to graphs. In particular, several formulations of convolutional neural networks were proposed and research is carried to develop new layers and network architectures to graphs. Those models aim at solving different tasks such as node classification, link prediction or graph classification. In this work, we study node, subgraph or graph embeddings produced by graph neural networks. These embeddings at different scales encode hierarchical representations of graphs. Based on these embedding techniques, we propose new deep learning architectures to tackle node classification or graph classification tasks. We study several applications of these new techniques. For example, we study the problem of having a graph embedding invariant by node permutation and the interpretability of graph neural networks., Les graphes sont présents dans de nombreux domaines de recherche, que ce soit pour représenter des molécules, des réseaux sociaux ou des réseaux de transport. Un graphe est un outil mathématique utilisé pour représenter des relations entre des objets. Il est composé de nœuds reliés entre eux par des liens, appelés arêtes. Récemment, les techniques d’apprentissage profond ont prouvé leur efficacité dans de nombreux domaines tels que le traitement de texte ou l’analyse d’images. Ce constat a motivé de nombreux travaux de recherche visant à généraliser les techniques d’apprentissage profond à l’analyse de graphes. Ainsi, des algorithmes se basant notamment sur des réseaux de neurones et des convolutions ont été développés afin de répondre à des problématiques de classification de nœuds et de graphes. Au cours de cette thèse, nous analysons les représentations vectorielles des nœuds, des communautés ou de l’ensemble du graphe qui émerge de ces modèles. Ces représentations, à différentes échelles, encodent des informations hierarchiques sur le graphe. En se basant sur ces vectorialisations de graphes, nous proposons de nouvelles architectures afin de répondre à des tâches de classification de nœuds et classification de graphes. Nous étudions plusieurs applications de ces nouvelles techniques, notamment le problème d’obtenir une représentation invariante par permutation des nœuds ou encore l’interprétabilité de ces algorithmes.

National audience; Si vous êtes passionnés de train, un touriste un peu fantaisiste, un Dr Sheldon Cooper en puissance ou simplement une personne ayant du temps (rayer les mentions inutiles), alors peut-être serez-vous curieux de passer au moins une fois par toutes les lignes de métro d’une ville, tout en empruntant le moins de stations possible ?

National audience; Le problème dit « des huit reines » est bien connu des informaticiens car il est souvent utilisé pour illustrer la récursivité ou les stratégies de backtracking (retour en arrière). Il ne s’agit pas d’organiser une réunion entre têtes couronnées mais d’étudier une situation simple. Si le problème se décrit en quelques phrases, il n’est pas si aisé que ça à résoudre...

National audience; Les robots mobiles oublieux ont été étudiés à la fois dans des espaces euclidiens continus et dans des espaces discrets (c'est-à-dire des graphes). Cependant, l'état de l'art actuel forme des ensembles de résultats distincts pour les deux modèles. À notre avis, le modèle continu reflète bien la physicalité des robots fonctionnant dans un environnement réel, tandis que le modèle discret reflète bien la nature numérique des robots autonomes, dont les capteurs et les capacités de calcul sont intrinsèquement finis. Nous explorons la possibilité de faire le pont entre les deux modèles. Notre approche est certifiée à l'aide de l'assistant de preuve Coq et du framework Pactole, que nous étendons au modèle asynchrone (le plus général) sans compromettre sa généricité. Notre cadre étendu est ensuite utilisé pour prouver formellement l'équivalence entre les mouvements atomiques dans un espace discret (le modèle classique des «robots sur les graphes») et les mouvements non atomiques dans un espace unidimensionnel continu lorsque les capteurs de vision du robot sont discrets (les robots se déplacent en ligne droite entre les positions, mais leurs observations ne se traduisent que par les positions de départ ou d'arrivée), quel que soit le problème résolu. Notre effort consolide l'intégration entre le modèle, la spécification du problème et sa preuve prônée par le framework Pactole.

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

La notion de «réseau arborescent» a suscité un regain d'intérêt ces dernières années, notamment en informatique et en biologie (réseau de neurones). Cependant, cette notion est habituellement interprétée de façon extrêmement restrictive : essentielle-ment liés au traitement des données, les «réseaux arborescents» d'aujourd'hui sont des topologies de réseaux hybrides dans lesquelles des réseaux en étoile sont généra-lement interconnectés via des réseaux de bus (voir Sosinsky (2009) ; Bradley (2016)). Ces réseaux sont, le plus souvent, hiérarchiques et réguliers (voir Kromer (2017)), et chacun de leurs noeuds peut avoir un nombre arbitraire de fils. Au départ, cependant, la notion de «réseau arborescent», introduite en 1936 par le scientifique belge Julien Pacotte, était assez différente : plus générale et, en même temps, plus contrainte, elle devait en outre servir un objectif ambitieux : la reconstruction des mathématiques à partir de structures empiriques concrètes. Ordinairement mal commentée et mal comprise (notamment des philosophes), elle n'a pas eu de véritable postérité. Dans cet article, nous essayons d'abord de clarifier cette notion de «réseau arborescent» au sens de Julien Pacotte, ce qui permet d'éliminer les mauvaises interprétations auxquelles cette notion a donné lieu (voir, par exemple, Deleuze et Guattari, 1980). Nous utilisons à cette fin le langage et les concepts de la théorie des graphes et for-malisons les principales propriétés de ces réseaux qui, contrairement à ce qu'on croit, ne sont pas, en général, des arbres. Dans une seconde partie, nous tentons ensuite de suivre et d'expliquer, pas à pas, comment Pacotte comptait, à l'aide de notions empruntées à la géométrie projective, reconstruire à partir d'un tel réseau l'ensemble des mathématiques. 1

Les technologies immersives ont fait leur apparition dans bon nombre d’outils de modélisation architecturale. Néanmoins, leur usage se limite bien souvent à des fins de visualisation, par exemple pour valider un design auprès d’un client muni d’un casque de réalité virtuelle. Notre travail vise à permettre une utilisation de ce medium immersif durant l’activité de conception architecturale elle-même. Nous présentons dès lors un outil de modélisation paramétrique en réalité virtuelle permettant de combiner, en immersion, l’édition de modèles Grasshopper et la visualisation des géométries générées. Nous validerons notre approche auprès d’architectes et d’étudiants formés à ce paradigme de conception.

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

International audience

In this PhD thesis, our aim is to establish a general methodology for performing the segmentation of a dataset constituted of similar images with only a few annotated images as training examples. This methodology is directly intended to be applied to images gathered in Earth observation or materials science applications, for which there is not enough annotated examples to train state-of-the-art deep learning based segmentation algorithms. The proposed methodology starts from a superpixel partition of the image and gradually merges the initial regions until anactual segmentation is obtained. The two main contributions described in this PhD thesis are the development of a new superpixel algorithm which makes use of the Eikonal equation, and the development of a superpixel merging algorithm steaming from the adaption of the Eikonal equation to the setting of graphs. The superpixels merging approach makes use of a region adjacency graph computed from the superpixel partition. The edges are weighted by a dissimilarity measure learned by a machine learning algorithm from low-level cues computed on the superpixels. In terms of application, our approach to image segmentation is finally evaluated on the SWIMSEG dataset, a dataset which contains sky cloud images. On this dataset, using only a limited amount of images for training our algorithm, we were able to obtain segmentation results similar to the ones obtained with state-of-the-art algorithms.; La présente thèse vise à développer une méthodologie générale basée sur des méthodes d’apprentissage pour effectuer la segmentation d’une base de données constituée d’images similaires, à partir d’un nombre limité d’exemples d’entraînement. Cette méthodologie est destinée à être appliquée à des images recueillies dans le cadre d’observations de la terre ou lors d’expériences menées en science des matériaux, pour lesquelles il n’y a pas suffisamment d’exemples d’entraînement pour appliquer des méthodes basées sur des techniques d’apprentissage profond. La méthodologie proposée commence par construire une partition de l’image en superpixels, avant de fusionner progressivement les différents superpixels obtenus jusqu’à l’obtention d’une segmentation valide. Les deux principales contributions de cette thèse sont le développement d’un nouvel algorithme de superpixel basé sur l’équation eikonale, et le développement d’un algorithme de fusion de superpixels basé sur une adaptation de l’équation eikonale au contexte des graphes. L’algorithme de fusion des superpixels s’appuie sur un graphe d’adjacence construit à partir de la partition en superpixels. Les arêtes de ce graphe sont valuées par une mesure de dissimilarité prédite par un algorithme d’apprentissage à partir des caractéristiques de bas niveau calculées sur les superpixels. A titre d’application, l’approche de segmentation est évaluée sur la base de données SWIMSEG, qui contient des images de nuages. Pour cette base de données, avec un nombre limité d’images d’entraînement, nous obtenons des résultats de segmentation similaires à ceux de l’état de l’art.

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.