La mise en oeuvre des méthodes formelles déductives lors du développement de systèmes permet d'obtenir des garanties mathématiques quant à leur validité. Pour cette raison, leur utilisation est recommandée ou exigée par certains standards relatifs à la sûreté de fonctionnement ou à la sécurité, tels que l'IEC 61508 ou les Critères Communs. Il reste cependant légitime de s'interroger sur la portée exacte des bénéfices obtenus. Certains aspects d'un système peuvent en effet échapper à la formalisation, et il n'est pas toujours facile d'identifier ces limitations ou leurs conséquences. De même, si la validité d'une preuve vérifiée mécaniquement est difficilement contestable, son utilisation pour justifier d'une confiance réelle dans le système physique n'est pas toujours admise. De telles questions sont particulièrement pertinentes dans le domaine de la sécurité, lorsque les systèmes sont l'objet d'attaques de la part d'agents intelligents ; par rapport à la sûreté il y a un changement radical de point de vue, qui justifie de s'interroger quant à l'application de principes ou de pratiques bien connus. Nous identifions les bénéfice et évaluons la confiance résultant de l'application des méthodes formelles déductives lors de développements de systèmes de sécurité. Cette analyse aborde les éventuelles difficultés, déviations ou problèmes qui peuvent être rencontrés et les illustre par des exemples. Elle comporte également une étude détaillée du concept de raffinement, et présente un plongement profond visant à valider la logique de la méthode B en Coq. Ce plongement conduit par ailleurs à l'étude des représentations à la de Bruijn.

Le thème central de cette thèse est l'étude de plongements d'espaces métriques dans des espaces de Banach. La première étude concerne les plongements grossièrement Lipschitz entre les espaces de James Jp pour p≻1 et p fini. On obtient que, pour p,q différents, Jq ne se plonge pas grossièrement Lipschitz dans Jp. Nous avons également obtenu, dans le cas où q≺p, une majoration de l'exposant de compression de Jq dans Jp par q/p. La question naturelle qui se pose ensuite est de savoir si le résultat obtenu pour les espaces de James est vrai aussi en ce qui concerne leurs duaux. Nous obtenons que, pour p,q différents, Jp* ne se plonge pas grossièrement lipschitz dans Jq*. Suite à ce travail, on établit des résultats plus généraux sur la non-plongeabilité des espaces de Banach q-AUS dans les espaces de Banach p-AMUC pour p≺q. On en déduit aussi, à l'aide d'un théorème de renormage, un résultat sur les indices de Szlenk. Par ailleurs, on obtient un résultat sur la plongeabilité quasi-Lipschitz dont la définition diffère légèrement de la plongeabilité presque Lipschitz : pour deux espaces de Banach X et Y, si, pour C≻1, X est C-finiment crûment représentable dans tout sous-espace vectoriel de codimension finie de Y, alors tout sous-espace propre M de X se plonge quasi-Lipschitz dans Y. Pour conclure, on obtient le corollaire suivant : soient X et Y deux espaces de Banach tels que X est localement minimal et Y est finiment crûment représentable dans X. Alors, pour M sous-espace propre de Y, M se plonge quasi-Lipschitz dans X. / The central theme of this thesis is the study of embeddings of metric spaces into Banach spaces.The first study focuses on the coarse Lipschitz embeddings between James Spaces Jp for p≻1 and p finite. We obtain that, for p,q different, Jq does not coarse Lipschitz embed into Jp. We also obtain, in the case where q≺p, that the compression exponent of Jq in Jp is lower or equal to q/p. Another natural question is to know whether we have similar results for the dual spaces of James spaces. We obtain that, for p,q different, Jp* does not coarse Lipschitz embed into Jq*. Further to this work, we establish a more general result about the coarse Lipschitz embeddability of a Banach space which has a q-AUS norm into a Banach space which has a p-AMUC norm for p≺q. With the help of a renorming theorem, we deduce also a result about the Szlenk index. Moreover, after defining the quasi-Lipschitz embeddability, which is slightly different to the almost Lipschitz embeddability, we obtain the following result: For two Banach spaces X, if X is crudely finitely representable with constant C (where C≻1) in any subspace of Y of finite codimension, then every proper subset M of X quasi-Lipschitz embeds into Y. To conclude, we obtain the following corollary: Let X be a locally minimal Banach space, and Y be a Banach space which is crudely finitely representable in X. Then, for M a proper subspace of Y, M quasi-Lipschitz embeds into X.

L'augmentation considérable de la quantité des données textuelles rend aujourd’hui difficile leur analyse sans l’assistance d’outils. Or, un texte rédigé en langue naturelle est une donnée non-structurée, c’est-à-dire qu’elle n’est pas interprétable par un programme informatique spécialisé, sans lequel les informations des textes restent largement sous-exploitées. Parmi les outils d’extraction automatique d’information, nous nous intéressons aux méthodes d’interprétation automatique de texte pour la tâche de normalisation d’entité qui consiste en la mise en correspondance automatique des mentions d’entités de textes avec des concepts d’un référentiel. Pour réaliser cette tâche, nous proposons une nouvelle approche par alignement de deux types de représentations vectorielles d’entités capturant une partie de leur sens : les plongements lexicaux pour les mentions textuelles et des “plongements ontologiques” pour les concepts, conçus spécifiquement pour ce travail. L’alignement entre les deux se fait par apprentissage supervisé. Les méthodes développées ont été évaluées avec un jeu de données de référence du domaine biologique et elles représentent aujourd’hui l’état de l’art pour ce jeu de données. Ces méthodes sont intégrées dans une suite logicielle de traitement automatique des langues et les codes sont partagés librement. / The impressive increase in the quantity of textual data makes it difficult today to analyze them without the assistance of tools. However, a text written in natural language is unstructured data, i.e. it cannot be interpreted by a specialized computer program, without which the information in the texts remains largely under-exploited. Among the tools for automatic extraction of information from text, we are interested in automatic text interpretation methods for the entity normalization task that consists in automatically matching text entitiy mentions to concepts in a reference terminology. To accomplish this task, we propose a new approach by aligning two types of vector representations of entities that capture part of their meanings: word embeddings for text mentions and concept embeddings for concepts, designed specifically for this work. The alignment between the two is done through supervised learning. The developed methods have been evaluated on a reference dataset from the biological domain and they now represent the state of the art for this dataset. These methods are integrated into a natural language processing software suite and the codes are freely shared.

Durant cette thèse, nous avons introduit les problèmes de Bin Covering avec Contrainte de Distance (BCCD) et de Bin Packing avec Contrainte de Distance (BPCD), qui trouvent leur application dans les réseaux de grande échelle, tel Internet. L'étude de ces problèmes que nous effectuons dans des espaces métriques quelconques montre qu'il est impossible de travailler dans un tel cadre sans avoir recours à de l'augmentation de ressources, un procédé qui permet d'élaborer des algorithmes construisant des solutions moins contraintes que la solution optimale à laquelle elles sont comparées. En plus de résultats d'approximation intéressants, nous prouvons la difficulté de ces problèmes si ce procédé n'est pas utilisé. Par ailleurs, de nombreux outils ont pour objectif de plonger les grands réseaux qui nous intéressent dans des espaces métriques bien décrits. Nous avons alors étudié nos problèmes dans les espaces métriques générés par certains de ces outils, comme Vivaldi et Sequoia.

Ce mémoire traite des structures affines et de leur rapport à la géométrie de l'information. Nous y introduisons la notion de T-plongement. Il permet de montrer que l'ensemble des structures affines complètes du tore T^2 est une courbe projective de RP^2. En substituant à la contrainte topologique (compacité) une contrainte dynamique (action canonique de Aff_0(1) dans le démi-plan de Poincaré H^2)on démontre que l'ensemble S des structures Aff_0(1)-invariantes dans H^2 est une surface projective connexe dans RP^5 ne contenant aucun point complet. Un de mes résultats remarquables concerne la classification des éléments de S pour la relation d'isomorphisme.Nous exploitons un outil récent: la KV-cohomologie. Outre le rôle fondamental joué par la KV-cohomologie dans l'étude des points rigides dans certains modules des structures affines, elle nous a permis d'aborder avec succès une problématique qui est au centre de la géométrie de l'information. Cette problématique concerne la détermination des structures affines invariantes dans les variétés modèles statistiques qui sont invariantes par toute transformation non singulière de l'espace des paramètres. Celles-ci ont une signification pertinente en statistique. / This dissertation deals with modules of affinely flat structure and with their relationships between these structures and the information geometry. The so-called T-embedding is used to prove that the set of complete locally flat structures is an irreducible projective curve in RP^2. In the same way we prove that the set S of Aff_0(1)-invariant locally flat structure in H^2 is a connected projective surface in RP^5, which does not contain any complete point. We also give the classification up to isomorphism of S. We use the KV-cohomology to study the rigidity problem for locally flat structures. The main concern of information geometry is the study of geometrical invariants in statistical models. We perform the KV-cohomology to bring in control this problem.

Dans cette thèse, nous nous intéressons à plusieurs problèmes liés à la conception de réseaux géométriques et aux plongements isométriques dans le plan.Nous commençons par étudier la généralisation du problème du réseau de Manhattan classique aux plans normés. Étant donné un ensemble de terminaux, nous recherchons le réseau de longueur totale minimum qui connecte chaque paire de terminaux par un plus court chemin dans la métrique définie par la norme. Nous proposons un algorithme d'approximation facteur 2.5 pour ce problème en temps O(mn^3) avec n le nombre de terminaux et m le nombre de directions de la boule unitaire. Le deuxième problème étudié est une version orientée des réseaux de Manhattan dont le but est de construire un réseau orienté de taille minimum dans lequel pour chaque paire de terminaux u, v est relié par un plus court chemin rectilinéaire de u vers v et un autre de v vers u. Nous proposons un algorithme d'approximation facteur 2 pour ce problème en temps O(n^3) où n est le nombre de terminaux.Nous nous intéressons ensuite à la recherche d'un spanner (un sous-graphe approximant les distances) planaire pour les graphes de disques unitaires (UDG) qui modélise les réseaux ad hoc sans fils. Nous présentons un algorithme qui construit un spanner planaire avec un facteur d'étirement constant en terme de distance de graphe pour UDG. Cet algorithme utilise uniquement des propriétés locales et peut donc être implémenté de manière distribuée.Finalement nous étudions le problème de la reconnaissance des espaces plongeables isométriquement dans le plan l_1 pour lequel nous proposons un algorithme en temps optimal O(n^2) pour sa résolution, ainsi que la généralisation de ce problème aux plans normés dont la boule unitaire est un polygone convexe central symétrique. / In this thesis, we study several problems related to the design of geometric networks and isometric embeddings into the plane.We start by considering the generalization of the classical Minimum Manhattan Network problem to all normed planes. We search the minimum network that connects each pair of terminals by a shortest path in this norm. We propose a factor 2.5 approximation algorithm in time O(mn^3), where n is the number of terminals and m is the number of directions of the unit ball.The second problem presented is an oriented version of the minumum Manhattan Network problem, we want to obtain a minimum oriented network such that for each pair u, v of terminals, there is a shortest rectilinear path from u to v and another path from v to u.We describe a factor 2 approximation algorithm with complexity O(n^3) where n is the number of terminals for this problem.Then we study the problem of finding a planar spanner (a subgraph which approximates the distances) of the Unit Disk Graph (UDG) which is used to modelize wireless ad hoc networks. We present an algorithm for computing a constant hop stretch factor planar spanner for all UDG. This algorithm uses only local properties and it can be implemented in distributed manner.Finally, we study the problem of recognizing metric spaces that can be isometrically embbed into the rectilinear plane and we provide an optimal time O(n^2) algorithm to solve this problem. We also study the generalization of this problem to all normed planes whose unit ball is a centrally symmetric convex polygon.

Le graphe est un concept puissant pour la représentation des relations entre des paires d'entités. Les données ayant une structure de graphes sous-jacente peuvent être trouvées dans de nombreuses disciplines, décrivant des composés chimiques, des surfaces des modèles tridimensionnels, des interactions sociales ou des bases de connaissance, pour n'en nommer que quelques-unes. L'apprentissage profond (DL) a accompli des avancées significatives dans une variété de tâches d'apprentissage automatique au cours des dernières années, particulièrement lorsque les données sont structurées sur une grille, comme dans la compréhension du texte, de la parole ou des images. Cependant, étonnamment peu de choses ont été faites pour explorer l'applicabilité de DL directement sur des données structurées sous forme des graphes. L'objectif de cette thèse est d'étudier des architectures de DL sur des graphes et de rechercher comment transférer, adapter ou généraliser à ce domaine des concepts qui fonctionnent bien sur des données séquentielles et des images. Nous nous concentrons sur deux primitives importantes : le plongement de graphes ou leurs nœuds dans une représentation de l'espace vectorielle continue (codage) et, inversement, la génération des graphes à partir de ces vecteurs (décodage). Nous faisons les contributions suivantes. Tout d'abord, nous introduisons Edge-Conditioned Convolutions (ECC), une opération de type convolution sur les graphes réalisés dans le domaine spatial où les filtres sont générés dynamiquement en fonction des attributs des arêtes. La méthode est utilisée pour coder des graphes avec une structure arbitraire et variable. Deuxièmement, nous proposons SuperPoint Graph, une représentation intermédiaire de nuages de points avec de riches attributs des arêtes codant la relation contextuelle entre des parties des objets. Sur la base de cette représentation, l'ECC est utilisé pour segmenter les nuages de points à grande échelle sans sacrifier les détails les plus fins. Troisièmement, nous présentons GraphVAE, un générateur de graphes permettant de décoder des graphes avec un nombre de nœuds variable mais limité en haut, en utilisant la correspondance approximative des graphes pour aligner les prédictions d'un auto-encodeur avec ses entrées. La méthode est appliquée à génération de molécules / Graph is a powerful concept for representation of relations between pairs of entities. Data with underlying graph structure can be found across many disciplines, describing chemical compounds, surfaces of three-dimensional models, social interactions, or knowledge bases, to name only a few. There is a natural desire for understanding such data better. Deep learning (DL) has achieved significant breakthroughs in a variety of machine learning tasks in recent years, especially where data is structured on a grid, such as in text, speech, or image understanding. However, surprisingly little has been done to explore the applicability of DL on graph-structured data directly.The goal of this thesis is to investigate architectures for DL on graphs and study how to transfer, adapt or generalize concepts working well on sequential and image data to this domain. We concentrate on two important primitives: embedding graphs or their nodes into a continuous vector space representation (encoding) and, conversely, generating graphs from such vectors back (decoding). To that end, we make the following contributions.First, we introduce Edge-Conditioned Convolutions (ECC), a convolution-like operation on graphs performed in the spatial domain where filters are dynamically generated based on edge attributes. The method is used to encode graphs with arbitrary and varying structure.Second, we propose SuperPoint Graph, an intermediate point cloud representation with rich edge attributes encoding the contextual relationship between object parts. Based on this representation, ECC is employed to segment large-scale point clouds without major sacrifice in fine details.Third, we present GraphVAE, a graph generator allowing to decode graphs with variable but upper-bounded number of nodes making use of approximate graph matching for aligning the predictions of an autoencoder with its inputs. The method is applied to the task of molecule generation

Les résultats obtenus dans cette thèse portent sur le dimensionnement de réseaux virtuels de télécommunications. Dans le chapitre 1, nous présentons brièvement la technologie des réseaux étudiés. Le chapitre 2 est consacré à la modélisation des réseaux de télécommunications à l'aide de la théorie des graphes. Les chapitres et traitent du problème du positionnement de chemins virtuels qui consiste à trouver un graphe ayant certaines propriétés tel que son plongement dans un graphe donné soit de congestion minimum. Pour les arbres, nous donnons des algorithmes polynomiaux permettant de trouver une solution optimale lorsque le nombre de sauts est fixé. Dans le chapitre 5 est introduit une extension optique de ce modèle. Le chapitre 6 est consacré au réseaux hiérarchiques en anneaux. Le problème de maximisation du nombre de sommets d'une telle structure ayant un diamètre donné est résolu. Dans le chapitre 7, nous étudions un problème d'optimisation lié à la tarification d'une boucle SDH.

Cette thèse donne une étude systématique des espaces de Sobolev, Besov et Triebel-Lizorkin sur le tore quantique. Ces espaces partagent beaucoup de propènes avec leurs analogues classiques. Nous prouvons le théorème de réduction pour tous ces espaces et une inégalité de Poincaré pour les espaces de Sobolev. Nous démontrons les inégalités de plongement pour eux, incluant le plongement d'espaces de Besov et d'espaces de Sobolev. Nous obtenons une caractérisation générale à la Littlewood-Paley pour les espaces de l3esov et Triebel-Lizorkin, qui implique des caractérisations concrètes par les semigroupes de Poisson et de chaleur ainsi par des différences. Certains d'entre elles sont nouvelles, même dans le cas commutatif; par exemple, celle d'espaces de Besov et Triebel-Lizorkin par le semigroupe de Poisson améliore le résultat classique. En conséquence de la caractérisation d'espaces de Besov par des différences, nous étendons les récents résultats de Bourgain-Brézis -Mironescu et Maz'ya-Shaposhnikova sur les limites de normes de Besov au cadre quantique. Nous étudions aussi l'interpolation de ces espaces, et en particulier, déterminons explicitement le K-fonctionnel du couple de l'espace Lp et l'espace de Sobolev, ce qui est l'analogue quantique du résultat classique de Johnen et Scherer. Enfin, nous montrons que les multiplicateurs de Fourier complètement bornés sur tous ces espaces coïncident avec ceux sur les espaces correspondants sur le tore usuel. Nous prouvons également que les multiplicateurs de Fourier sur les espaces de Besov sont complètement déterminés par ceux sur les sous-espaces Lp associés à leurs composantes dans la décomposition de Littlewood-Paley. / This thesis gives a systematic study of Sobolev, Besov and Triebel-Lizorkin spaces on a noncommutative d-torus. We prove, arnong other basic properties, the lifting theorem for all these spaces and a Poincaré type inequality for Sobolev spaces. We establish the embedding inequalities of all these spaces, including the l3esov and Sobolev embedding theorems. We obtain Littlewood-Paley type characterizations for Besov and 'friebel-Lizorki spaces in a general way, as well as the concrete ones internas of the Poisson, heat semigroups and differences. Some of them are new even in the commutative case, for instance, oui Poisson semigroup characterization of Besov and Triebel-Lizorkin spaces improves the classical ones. As a consequence of the characterization of the Besov spaces by differences, we extend to the quantum setting the recent results of Bourgain-Brézis -Mironescu and Maz'ya-Shaposhnikova on the limits of l3esov florins. We investigate the interpolation of all these spaces, in particular, deterrnine explicitly the K-functional of the couple of Lp space and Sobolev space, winch is the quantum analogue of a classical result due to Johnen and Scherer Finally, we show that the completely bounded Fourier multipliers on all these spaces coincide with those on the corresponding spaces on the usuel d-torus. We also give a quite simple description of (completely) bounded Fourier multipliers on the Besov spaces in ternis of their behavior on the Lp-components in the Littlevvood-Paley decomposition.

Cette thèse présente trois principaux sujets de recherche, les deux premiers étant indépendants et le dernier indiquant la relation des deux premières problématiques dans un cas concret.Dans la première partie nous nous intéressons au problème de transport optimal martingale dans l’espace de Skorokhod, dont le premier but est d’étudier systématiquement la tension des plans de transport martingale. On s’intéresse tout d’abord à la semicontinuité supérieure du problème primal par rapport aux distributions marginales. En utilisant la S-topologie introduite par Jakubowski, on dérive la semicontinuité supérieure et on montre la première dualité. Nous donnons en outre deux problèmes duaux concernant la surcouverture robuste d’une option exotique, et nous établissons les dualités correspondantes, en adaptant le principe de la programmation dynamique et l’argument de discrétisation initie par Dolinsky et Soner.La deuxième partie de cette thèse traite le problème du plongement de Skorokhod optimal. On formule tout d’abord ce problème d’optimisation en termes de mesures de probabilité sur un espace élargi et ses problèmes duaux. En utilisant l’approche classique de la dualité; convexe et la théorie d’arrêt optimal, nous obtenons les résultats de dualité. Nous rapportons aussi ces résultats au transport optimal martingale dans l’espace des fonctions continues, d’où les dualités correspondantes sont dérivées pour une classe particulière de fonctions de paiement. Ensuite, on fournit une preuve alternative du principe de monotonie établi par Beiglbock, Cox et Huesmann, qui permet de caractériser les optimiseurs par leur support géométrique. Nous montrons à la fin un résultat de stabilité qui contient deux parties: la stabilité du problème d’optimisation par rapport aux marginales cibles et le lien avec un autre problème du plongement optimal.La dernière partie concerne l’application de contrôle stochastique au transport optimal martingale avec la fonction de paiement dépendant du temps local, et au plongement de Skorokhod. Pour le cas d’une marginale, nous retrouvons les optimiseurs pour les problèmes primaux et duaux via les solutions de Vallois, et montrons en conséquence l’optimalité des solutions de Vallois, ce qui regroupe le transport optimal martingale et le plongement de Skorokhod optimal. Quand au cas de deux marginales, on obtient une généralisation de la solution de Vallois. Enfin, un cas spécial de plusieurs marginales est étudié, où les temps d’arrêt donnés par Vallois sont bien ordonnés. / This PhD dissertation presents three research topics, the first two being independent and the last one relating the first two issues in a concrete case.In the first part we focus on the martingale optimal transport problem on the Skorokhod space, which aims at studying systematically the tightness of martingale transport plans. Using the S-topology introduced by Jakubowski, we obtain the desired tightness which yields the upper semicontinuity of the primal problem with respect to the marginal distributions, and further the first duality. Then, we provide also two dual formulations that are related to the robust superhedging in financial mathematics, and we establish the corresponding dualities by adapting the dynamic programming principle and the discretization argument initiated by Dolinsky and Soner.The second part of this dissertation addresses the optimal Skorokhod embedding problem under finitely-many marginal constraints. We formulate first this optimization problem by means of probability measures on an enlarged space as well as its dual problems. Using the classical convex duality approach together with the optimal stopping theory, we obtain the duality results. We also relate these results to the martingale optimal transport on the space of continuous functions, where the corresponding dualities are derived for a special class of reward functions. Next, We provide an alternative proof of the monotonicity principle established in Beiglbock, Cox and Huesmann, which characterizes the optimizers by their geometric support. Finally, we show a stability result that is twofold: the stability of the optimization problem with respect to target marginals and the relation with another optimal embedding problem.The last part concerns the application of stochastic control to the martingale optimal transport with a payoff depending on the local time, and the Skorokhod embedding problem. For the one-marginal case, we recover the optimizers for both primal and dual problems through Vallois' solutions, and show further the optimality of Vallois' solutions, which relates the martingale optimal transport and the optimal Skorokhod embedding. As for the two-marginal case, we obtain a generalization of Vallois' solution. Finally, a special multi-marginal case is studied, where the stopping times given by Vallois are well ordered.