En analyse de risques, les arbres d’attaque sont utilisés pour évaluer les menaces sur un système. Les méthodes formelles permettent leur analyse quantitative et leur synthèse, mais les propriétés exprimant la qualité des arbres d’attaque par rapport au système n’ont pas été formalisées. Dans ce document, nous définissons un nouveau cadre formel pour les arbres d’attaque prenant en compte un modèle opérationnel du système, et dotant les arbres d’une sémantique de chemins. Nous définissons les propriétés de correction des raffinements, et étudions leurs complexités. A partir d’une attaque optimale dans un modèle de système quantitatif, nous guidons la conception d’un arbre d’attaque, en indiquant ses feuilles qui contribuent à l’attaque optimale considérée. / In risk analysis, attack trees are used to assess threats to a system. Formal methods allow for their quantitative analysis and synthesis, but the properties expressing the quality of the attack trees with respect to the system have not been formalized. In this document, we define a new formal framework for attack trees that takes an operational model of the system into account, and provides the trees with a path semantics. We define the correctness properties of refinements, and study their computational complexity. Given an optimal attack in a quantitative system model, we guide the design of a attack tree, indicating its leaves that contribute to considered the optimal attack.

Malgré son importance économique, culturelle et historique, l’histoire évolutive du pommier cultivé (Malus domestica) ainsi que celle de ses apparentés sauvages supposés, restaient encore très peu connues. En s’appuyant sur les nouvelles approches de génétique des populations (approximate Bayesian computation) avec l’utilisation de marqueurs microsatellites et de séquences nucléaires, cette thèse a eu pour objectif d’étudier, à différentes échelles évolutives (phylogéographie, spéciation, domestication), les mécanismes de diversification naturelle et artificielle dans le genre Malus. Mes travaux ont porté sur quatre espèces de pommiers sauvages distribuées à travers l’Eurasie (Malus orientalis (Caucase), Malus sieversii (Asie Centrale), Malus sylvestris (Europe), et Malus baccata (Sibérie)) et sur la seule espèce domestiquée du genre, Malus domestica. Cette thèse s’est articulée en quatre parties visant respectivement à inférer : (i) l’histoire de la domestication du pommier cultivé depuis son centre d’origine en Asie Centrale, (ii) l’histoire de la recolonisation post-glaciaire du pommier sauvage Européen (M. sylvestris), (iii) les histoires de spéciation entre les cinq espèces de Malus, (iv) les hybridations interspécifiques et les capacités de dispersion des trois principaux contributeurs (M. sylvestris, M. sieversii et M. orientalis) au génome du pommier cultivé. L’étude des mécanismes de diversification artificielle montre que les processus de domestication sont originaux chez cet arbre fruitier, de par l'absence de goulet d’étranglement et l’existence d’introgressions post-domestication fréquentes par une autre espèce sauvage (M. sylvestris) que l’espèce ancestrale (M. sieversii). L’étude des processus de diversification naturelle (phylogéographie, spéciation et structure des populations) révèlent de grandes tailles de populations, de forts flux de gènes et de faibles structures génétiques spatiales chez chacune des espèces. Cette thèse a aussi révélé de forts taux d’hybridations interspécifiques, en particulier de fortes introgressions des espèces de pommiers sauvages par le pommier cultivé en Europe et en Asie Centrale. Cette étude a permis l'amélioration des connaissances de la structuration des populations de pommiers sauvages ayant contribué au génome du pommier cultivé ainsi que de l’étendue des hybridations du pommier cultivé avec les espèces sauvages. Ces travaux revêtent une grande importance autant pour la conservation des pommiers sauvages, pour le maintien de leur intégrité dans des habitats fragmentés que pour l'amélioration variétale du pommier domestiqué. / : Despite its economic, cultural and historical importance, few studies have investigated the evolutionary history of the domesticated apple (Malus domestica) as well as those of its wild relatives. Using new population genetic approaches (approximate Bayesian computation) with microsatellites and nuclear sequences, this thesis aimed at unravelling, at different evolutionary scales (phylogeography, speciation, domestication), the natural and artificial diversification processes at play in the Malus genus. My research focused on the four wild apple species distributed across Eurasia (Malus orientalis (Caucasus), Malus sieversii (Central Asia), Malus sylvestris (Europe), and Malus baccata (Siberia)) and on the single domesticated apple species in the genus, Malus domestica. This thesis was divided into four parts: (i) domestication history of the cultivated apple, from its origin in Central Asia to Europe, (ii) post-glacial recolonization history of the European crabapple (M. sylvestris), (iii) the history of speciation among the five Malus species, (iv) crop-to-wild gene flow and dispersal capacities of the closest wild relative species (M. sylvestris, M. sieversii and M. orientalis). By investigating artificial diversification, we evidenced unique processes of domestication in this fruit tree, with no bottleneck and with extensive post-domestication introgressions by another wild species (M. sylvestris) than the ancestral progenitor (M. sieversii). Natural diversification patterns (phylogeography, speciation and population structure) revealed large effective population sizes, high dispersal capacities and weak spatial genetic structures. This thesis also revealed high levels of interspecific hybridizations, particularly high level of crop-to-wild gene flow in Europe and Central Asia. This study extended our knowledge about population structures for wild species that contributed to the cultivated apple genome, as well as the extent of hybridization rates. This work is essential for the conservation of wild apple populations, the integrity maintenance of wild species facing fragmentation and future breeding programs concerning the domesticated apple.

Au cours des quinze dernières années, le développement de plateformes embarquées intelligentes et les progrès des protocoles de communication radio ont permis l'émergence de réseaux de capteurs sans-fils (WSN). D'autre part, la démocratisation d'Internet et du Web, ainsi que l'augmentation des débits ont contribué à l'essor d'un nouveau paradigme : le Cloud computing. L'Internet des Objets, (IoT) ou Internet des Objets réalise la convergence entre les réseaux de capteurs et le Cloud computing. De nombreux travaux adressant les problématiques de l'IoT ont étés menés ces dix dernières années, cependant ces propositions manquent ne tiennent pas suffisamment compte des problématiques de sécurité et de protection des données. D'après Gartner, 70 % des plateformes déployées ne disposent pas d'une solution de sécurité efficace, les rendant vulnérables aux attaques. Dans le domaine des monnaies numériques, Bitcoin propose en son sein une nouvelle structure de données authentifiée et trustless permettant la décentralisation de l'enregistrement de transactions en s'appuyant sur un protocole permettant d'obtenir un consensus : la blockchain. Cette thèse se focalise sur l'utilisation de cette nouvelle structure de données dans les WSN dans un contexte IoT, comme base pour la définition d'une architecture sécurisée et adaptative basée sur la blockchain. Le but de cette architecture est d'intégrer les solutions existantes pour l'organisation du réseau et l'accès aux services de manière innovante afin de réaliser l'intégration des WSN avec l'infrastructure web; mais aussi d'y adjoindre une solution répondant aux nouveaux besoins de sécurités et contraintes spécifiques des réseaux de capteurs. Nous proposons pour cela un framework nommé Network Service Loader (NSL) en charge de la gestion de services et d'agents mobiles, auquel s'adjoint notre solution Blockchain Authentication and Trust Module (BATM) en charge de l'authentification, du contrôle d'accès, ainsi que des évaluations de confiance via l'algorithme Maximum Likelihood Trust Estimator (MLTE). / During the last fifteen years, the rise of smart and wireless enabled embedded devices lead to the development of wireless sensor networks (WSN). In the same time, the emerging of Cloud computing with the development of the Internet and the Web as an everyday technology thanks to the rise of bandwidth and processing power leads to new network paradigms. The Internet of Things (IoT) primary goal is to bridge the gap between these technologies and bring WSN sensing and actuating abilities to Cloud applications. We count a significant amount of work targetting the IoT in the last decade, however they lack proper solutions to ensure data privacy and security. Gartner investigations shows that 70 % of connected and smart devices provide little or no security policies and solutions, making both user and devices vulnerable to attackers. In the field of digital currencies, Bitcoin proposed a new authenticated and trustless data structure dedicated to transactions logging in a decentralized network with the help of a consensus protocol : the blockchain. This thesis is focused on bringing the blockchain technology as a new solutions for security in decentralized WSN in the IoT, providing the basis for a secure and adaptative agent-based middleware and execution framework. This framework attempt to federate existing work regarding the architecture of the IoT, but also to tackle security issues regarding network access, agent execution and trust evaluation. To achieve this goal, we propose Network Service Loader (NSL), an agent-based middleware constructed of existing protocols in a new way, along with a new solution called Blockchain Authentication and Trust Module (BATM) dedicated to node and users authentication, access control policies, and trust evaluation through our new Maximum Likelihood Trust Estimator (MLTE) algorithm.

La facilité compte parmi les notions les plus fines de l'indéfini en lambda-calcul. Un terme est dit facile s'il peut être identifié à tout autre terme clos arbitraire sans soulever de contradiction. Introduite en 1975 par Jacopini, elle fait depuis l'objet de recherches qui visent à caractériser la forme des termes faciles. Aujourd'hui, de tous les travaux entrepris il se dégage qu'un tel terme doit posséder une périodicité. Être périodique, c'est être équivalent à un sous-terme propre de l'un de ses réduits. Ici, la périodicité apparaîtra sous les traits de l'auto-similarité. Sont auto-similaires les termes dont l'arbre de Berarducci réapparaît comme sous-arbre propre à lui-même. La facilité de tels termes demeure un mystère. À ce jour, nous n'en connaissons que peu d'exemples. Le terme "Y omega_3" constitue un exemple typique dont la question de la facilité reste ouverte. Dans cette thèse, nous étendrons la connaissance de l'ensemble des termes m identiables à Y Omega_3. Nous montrerons que dans un cas critique où lambda-beta +{Y Omega_3 = m} implique m = delta_3, sous certaines hypothèses, m est lui-même auto-similaire. Ils s'en suit une description possible de toutes les équations dérivées de {Y Omega_3= m} sous la forme de classes confinantes.

Ce travail de thèse traite du maintien dynamique de représentations géométriques de graphes. Le manuscrit met en avant des connexions fortes entre trois types de représentation de graphes : les décompositions de graphes, les modèles géométriques et les représentations arborescentes à degrés de liberté (PQ-arbres, PC-arbres et autres structures du même type). De nouvelles relations entre ces objets sont mises en évidence et d'autres déjà connues sont approfondies. Notamment, il est établi une équivalence mathématique et algorithmique entre la décomposition modulaire des graphes d'intervalles et le PQ-arbre de leurs cliques maximales.<br /><br />Les connexions entre les trois types de représentation précités sont exploitées pour la conception d'algorithmes de reconnaissance entièrement dynamiques pour les cographes orientés, les graphes de permutation et les graphes d'intervalles. Pour les cographes orientés, l'algorithme présenté est de complexité optimale, il traite les modifications de sommet en temps O(d), où d est le degré du sommet en question, et les modifications d'arête en temps constant. Les algorithmes pour les graphes de permutation et les graphes d'intervalles ont la même complexité : les modifications d'arête et de sommet sont traitées en temps O(n), où n est le nombre de sommets du graphe. Une des contributions du mémoire est de mettre en lumière des similarités très fortes entre les opérations d'ajout d'un sommet dans un graphe de permutation et dans un graphe d'intervalles. <br />L'approche mise en oeuvre dans ce mémoire est assez générale pour laisser entrevoir les mêmes possibilités algorithmiques pour d'autres classes de graphes définies géométriquement.

La facilité compte parmi les notions les plus fines de l'indéfini en λ-calcul. Un terme est dit facile s'il peut être identifié à tout autre terme clos arbitraire sans soulever de contradiction. Introduite en 1975 par Jacopini, elle fait depuis l'objet de recherches qui visent à caractériser la forme des termes faciles. Aujourd'hui, de tous les travaux entrepris il se dégage qu'un tel terme doit posséder une périodicité i.e être β-équivalent à un sous-terme propre de l'un de ses réduits. Ici, la périodicité apparaîtra sous les traits de l'auto-similarité. Sont auto-similaires les termes dont l'arbre de Berarducci réapparaît comme sous-arbre propre à lui-même. La facilité de tels termes demeure un mystère et à ce jour, nous n'en connaissons que peu d'exemples. Le terme Yt Ω3 constitue un exemple typique dont la question de la facilité reste ouverte. Dans cette thèse, nous élargirons la connaissance de l'ensemble des termes m identifiables à Yt Ω3. Nous montrerons que dans un cas critique où λβ +{Yt Ω3 = m} |- m = δ3, sous certaines hypothèses, m est lui-même auto-similaire. Ils s'en suit une description possible de toutes les équations dérivées de {Yt Ω3 = m} sous la forme de classes confinantes.

Développement d'une notation algorithmique adaptée à une démarche de programmation systématique et validation de l'emploi de méthodes précises d'analyse et de techniques de programmation au travers d'une expérience significative. La première partie de la thèse propose une réflexion sur les concepts sous-jacents à la maitrise des diverses constructions algorithmiques de base. Tandis que la deuxième partie aborde la spécification des divers composants d'un environnement de programmation

Nous présentons dans cette thèse une étude sur des<br />algorithmes distribués asynchrones et déterministes de<br />contröle. Un système distribué consiste en un réseau<br />de sites (processeurs, ordinateurs ou réseaux locaux). Dans cette<br />thèse, nous ne considérons que des réseaux de sites<br />communicants n'ayant ni mémoire partagée ni horloge globale.<br />De nombreux problèmes de l'algorithmique distribuée sont<br />réductibles à la construction d'un Arbre Couvrant qui est la<br />structure de contrôle qui nous intéresse.<br /><br />Nous étudions deux types d'algorithmes~: ceux utilisant<br />la notion de phase logique et les autres qui ne considèrent aucun<br />mécanisme de synchronisation. Ces derniers ont des comportements<br />imprévisibles améliorant la tolérance aux fautes. Nous<br />présentons un nouvel algorithme de ce type associé à une<br />élection qui n'est pas une recherche d'extremum contrairement<br />à l'usage. Cet algorithme est comparable au meilleur<br />algorithme connu qui utilise des jetons et des phases logiques<br />induisant un comportement plus "séquentiel".<br /><br />D'autres algorithmes, construisant des AC contraints, sont<br />considérés. En particulier l'AC de Diamètre Minimum qui<br />est, à notre connaissance, un problème qui n'a jamais<br />été étudié dans ce domaine. Le diamètre d'un<br />graphe est la somme des poids des arêtes du plus long des plus<br />courts chemins. Si nous considérons la complexité temporelle,<br />cette contrainte est d'un intérêt &vident. Nous proposons<br />différents algorithmes suivant que la tolérance aux fautes est<br />nécessaire ou non.<br /><br />Finalement, l'étude pratique des algorithmes distribués sur<br />des réseaux de grande taille nous a conduit à la construction<br />d'un simulateur. Il permet l'exécution d'un même code source<br />sur des machines séquentielles ou parallèles.

En quelques dizaines d'années, l'informatique a vu naître et se développer des machines fonctionnant avec plusieurs processeurs. Les difficultés techniques rencontrées pour la conception de ces ordinateurs ont été surmontées et l'un des défis majeur d'aujourd'hui est de fournir une plateforme pour la programmation parallèle. Ce travail de thèse s'inscrit dans le cadre du projet IMAG APACHE qui a pour but la conception d'un tel environnement. Le modèle de graphes que nous manipulons est un graphe de tâches orienté sans cycle. Le processus consistant à paralléliser une application est découpé en trois phases principales, avec l'ordonnancement et le placement des différentes parties de l'application comme étape centrale. Dans ce contexte, nous avons concentrés nos efforts sur la recherche de stratégies d'ordonnancement présentant de réelles qualités de robustesse et d'efficacité pour des graphes de différentes granularités, et pour des ensembles d'hypothèses d'exécution différents. A partir d'un algorithme produisant des ordonnancements optimaux dans le cas de graphes à structure arborescente formés de tàches de durées unitaires et de communications unitaires, nous avons montré qu'il était possible d'obtenir des ordonnancements, dont l'écart par rapport à l'optimal est borné, pour des arbres de granularité différente. Nous avons montré également que ce même algorithme permettait d'obtenir dans certains cas des ordonnancements optimaux pour un modèle d'exécution totalement différent de celui pour lequel il avait été originellement conçu. Cette étude sur deux processeurs a été mené pour un nombre supérieur de processeurs identiques et pour deux processeurs uniformes. Enfin, une partie de ce travail est dédiée à la recherche de stratégies d'ordonnancement pour des graphes générés par l'environnement Athapascan (projet APACHE) qui présentent la particularité de permettre l'adaptation de la granularité en fonction de la machine cible.

L'ARN, acide ribonucléique, est un des composants fondamentaux de la cellule. La majorité des ARN sont constitués d'une séquence orientée de nucléotides notés A,C,G et U. Une telle séquence se replie dans l'espace en formant des liaisons entre les nucléotides deux à deux. La fonction des ARN au sein de la cellule est liée à la conformation spatiale qu'ils adoptent. Ainsi, il est essentiel de pouvoir comparer deux ARN au niveau de leur conformation, par exemple pour déterminer si deux ARN ont la même fonction. On distingue trois niveaux dans la structure d'un ARN. La structure primaire correspond à la séquence de nucléotides, la structure secondaire est constistuée de la liste des liaisons formées entre les nucléotides tandis que la structure tertiaire consiste en la description exacte de la forme tridimensionnelle de la molécule (coordonnées de chaque nucléotide). Bien que la structure tertiaire soit celle qui décrit le mieux la forme spatiale de l'ARN, il est admis que deux ARN ayant une fonction moléculaire similaire ont une structure secondaire proche. Au niveau de la structure secondaire, une fois les liaisons nucléotidiques formées, on peut distinguer des éléments de structure secondaire telles que les hélices, les boucles multiples, les boucles terminales, les boucles internes et les renflements. Essentiellement deux formalismes ont été à ce jour proposés pour modéliser la structure secondaire des ARN. Les séquences annotées par des arcs permettent de représenter la séquence de l'ARN, les arcs codant alors pour les liaisons entre les lettres (nucléotides de la séquence). Les 2-intervalles, généralisation des séquences annotées, sont formés par deux intervalles disjoints. La structure secondaire peut alors être vue comme une famille de 2-intervalles. Enfin, les arbres racinés ordonnés offrent de nombreuses possibilités pour coder la structure secondaire, du niveau nucléotidique au niveau du réseau des boucles multiples. L'un des inconvénients de ces approches est qu'elles modélisent la structure secondaire de l'ARN selon un point de vue particulier (nucléotides, hélices etc). Nous proposons une nouvelle modélisation, appelée RNA-MiGaL, constituée de quatre arbres liés entre eux représentant la structure à différents niveaux de précision. Ainsi, le plus haut niveau code pour le réseau de boucles multiples considéré comme le squelette de la molécule. Le dernier niveau quant à lui détaille les nucléotides. Pour comparer de telles structures nous utilisons la notion de distance d'édition entre deux arbres. Cependant, au vu de certains limitations de celle-ci pour comparer des arbres représentant la structure secondaire à un haut niveau d'abstraction, nous avons introduit une nouvelle distance d'édition qui prend en compte deux nouvelles opérations d'édition: la fusion de noeud et la fusion d'arc. A l'aide de cette nouvelle distance, nous fournissons un algorithme permettant de comparer deux RNA-MiGaLs. Celui-ci est implémenté au sein d'un programme permettant la comparaison de deux structures secondaires d'ARN.