Les images panoramiques sont des vues en largeur d'un espace physique. Ces larges images, en plus d'être intéressantes par leur aspect esthétique, sont un support essentiel pour de nombreuses applications comme par exemple l'orientation automatique d'un robot dans son environnement ou la création de cartes satellites. Pour obtenir un panorama, deux approches sont possibles : une approche matérielle et une approche logicielle. Dans l'approche logicielle, il y a deux problématiques : le recalage des images entre elles et le mélange des valeurs radiométriques des sections se recoupant. Ce mémoire s'intéresse à la problématique de mélange. En effet, les images à regrouper peuvent présenter des différences d'intensité pour diverses raisons. Il faut alors effectuer un mélange afin de faire disparaître ces différences et pouvoir ainsi produire un panorama sans transition visible. Plus précisément, nous travaillons sur l'amélioration de l'algorithme de construction panoramique par recalage à l'aide du flux optique présenté par Rebière et Toffa. Cette méthode de positionnement très efficace repose sur le recalage de chaque pixel, à l'aide du flux optique. Malheureusement l'algorithme de Rebière et Toffa ne gère pas les différences d'intensité qui peuvent exister entre les images. Dans ces conditions, les panoramas produits ne sont pas de qualité satisfaisante. Pour régler ce problème, nous intégrons donc la méthode de mélange multibande présentée par Brown et Lowe. Nous adaptons ainsi le mélange multibande à l'algorithme de recalage par flux optique afin de le rendre robuste aux différences d'intensité.

L’émergence d’internet et l’amélioration des infrastructures de com- munication ont considérablement encouragé l’explosion des flux d’in- formations au niveau mondial. Cette évolution a été accompagnée par l’apparition de nouveaux besoins et de nouvelles attentes de la part des consommateurs. Communiquer avec ses proches ou ses collaborateurs, stocker des documents de travail, des fichiers mul- timédia, utiliser des services innovants traitant nos documents per- sonnels, tout cela se traduit immanquablement par le partage, avec des tiers, d’informations potentiellement sensibles. Ces tiers, s’ils ne sont pas de confiance, peuvent réutiliser à notre insu les données sensibles que l’on leur a confiées. Dans ce contexte, le chiffrement homomorphe apporte une bonne solution. Il permet de cacher aux yeux des tiers les données qu’ils sont en train de manipuler. Cependant, à l’heure actuelle, le chif- frement homomorphe reste complexe. Pour faire des opérations sur des données de quelques bits (données en clair), il est nécessaire de manipuler des opérandes sur quelques millions de bits (données chiffrées). Ainsi, une opération normalement simple devient longue en termes de temps de calcul. Dans cette étude, nous avons cherché à rendre le chiffrement ho- momorphe plus pratique en concevant un accélérateur spécifique. Nous nous sommes basés sur une approche de type co-conception logicielle/matérielle utilisant l’algorithme de Karatsuba. En particulier, notre approche est compatible avec le batching, qui permet de sto- cker plusieurs bits d’informations dans un même chiffré. Notre étude démontre que le batching peut être implémenté sans surcoût important comparé à l’approche sans batching, et permet à la fois de réduire les temps de calcul (calculs effectués en parallèle) et de réduire le rapport entre la taille des données chiffrées et des données en clair. / The emergence of internet and the improvement of communica- tion infrastructures have considerably increased the information flow around the world. This development has come with the emergence of new needs and new expectations from consumers. Communicate with family or colleagues, store documents or multimedia files, using innovative services which processes our personal data, all of this im- plies sharing with third parties some potentially sensitive data. If third parties are untrusted, they can manipulate without our agreement data we share with them. In this context, homomorphic encryption can be a good solution. Ho- momorphic encryption can hide to the third parties the data they are processing. However, at this point, homomorphic encryption is still complex. To process a few bits of clear data (cleartext), one needs to manage a few million bits of encrypted data (ciphertext). Thus, a computation which is usually simple becomes very costly in terms of computation time. In this work, we have improved the practicability of homomorphic en- cryption by implementing a specific accelerator. We have followed a software/hardware co-design approach with the help of Karatsuba algorithm. In particular, our approach is compatible with batching, a technique that “packs" several messages into one ciphertext. Our work demonstrates that the batching can be implemented at no important additional cost compared to non-batching approaches, and allows both reducing computation time (operations are processed in parallel) and the ciphertext/cleartext ratio.

Dans un contexte de besoins croissants de moyens de communication pour augmenter la sécurité des vols et répondre aux attentes des compagnies et des passagers, le monde de l'aviation civile cherche de nouveaux systémes de communication pouvant répondre à ces objectifs. Les réseaux ad-hoc aéronautiques, AANET (Aeronautical Ad hoc NETworks) représentent une approche innovante pour répondre à cette problématique. Il s'agit de réseaux auto-configurés, n'utilisant pas d'infrastructure fixe et dont la spécificité réside dans le fait que les nfiuds composant le réseau sont des avions commerciaux. Les AANET peuvent être vus comme un sous ensemble des VANET (Vehicular Ad-Hoc Networks) puisqu'ils partagent de nombreuses caractéristiques comme les contraintes imposées sur les trajectoires. Afin d'utiliser le plus eficacement ces réseaux mobiles tout en répondant aux besoins de nouvelles applications, telle que l'information météorologique temps réel sur des phénoménes dangereux, qui nécessitent des communications d'avion à avion, la proposition avancée dans cette thése est d'utiliser le paradigme du routage basé sur le contenu au dessus des AANET. Dans ce type de routage, ce n'est plus une adresse de destination qui est utilisée pour joindre le ou les correspondants, mais le contenu du message qui permet de décider des destinataires. Dans ce paradigme, un émetteur envoi un message possédant des attributs et le message est alors transmis par le réseau uniquement aux terminaux intéressés par le contenu du message. Appliqué à l'information météorologique, cette approche permet à un aéronef détectant un phénoméne dangereux tel qu'un orage de prévenir uniquement les avions intéressés par cet événement, c'est à dire ceux dont la trajectoire passe prés de l'orage dans le temps de vie du phénoméne. Dans cette thése, nous avons choisi de nous appuyer sur le paradigme populaire de publication/souscription (P/S) pour fournir un service de routage basé sur le contenu. Dans cette approche, des éditeurs publient des événements et des nfiuds envoient des abonnements pour déclarer les contenus qui les intéressent au systéme qui est alors en charge de leur faire suivre les événements répondant à leur demande. Aprés un état de l'art sur les systémes P/S existants, notamment ceux adaptés aux VANET, nous avons choisi de tester des solutions paraissant intéressantes dans un contexte AANET. Pour cela, nous avons développé sous Omnet++ un module de mobilité utilisant des reports de position réels afin de rejouer des journées complétes de trafic d'avions réels, ainsi que plusieurs applications aéronautiques s'appuyant sur un systéme P/S permettant de générer des données réalistes. Les résultats montrent que ces solutions ne sont pas complétement adaptées pour un contexte AANET. C'est pourquoi, dans un second temps, nous avons proposé un nouveau systéme P/S pour les AANET. Cette solution s'appuie sur une architecture recouvrante ("overlay network") construite à l'aide d'un algorithme original de regroupement à 1-saut (1-hop clusterisation) adapté aux AANET. Afin de favoriser la stabilité de l'architecture recouvrante, cet algorithme s'appuie sur le nombre de voisins et la mobilité relative entre les nfiuds voisins pour définir les groupes. Les tests réalisés montrent que le systéme P/S s'appuyant sur cette surcouche ofire de meilleurs résultats que les solutions testées précédemment, que ce soit en termes de charge réseau ou de pourcentage d'événements délivrés. / In a context of growing needs of communication means to increase ight safety and meet the expectations of companies and passengers, the world of civil aviation seeks new communication systems that can meet these objectives. The Aeronautical Ad-Hoc Networks, AANETs represent an innovative approach to address this problem. It is self-configured networks, using no fixed infrastructure where the nodes are commercial aircraft. The AANETs can be seen as a subset of the VANET (Vehicular Ad-Hoc Networks) since they share many features as the constraints imposed on the trajectories. In order to use these mobile networks more eficiently while meeting the needs of new applications, such as the transmission of weather information in real time, requiring air to air communications. , we propose in this thesis to use the paradigm of content based routing above AANET. In this kind of routing, it is not a destination address that is used to identify the recipients, but the message content itself. In this paradigm, a transmitter sends a message having attributes and the message is then transmitted by the network to nodes interested by the content of the message. Applied to weather information update, this approach allows an aircraft detecting a dangerous phenomenon such as a thunderstorm to only prevent interested nodes, ie those whose the trajectorycome close to the storm during the lifetime of the event. In this thesis, we have chosen to rely on the popular Publish / Subscribe (P/S) paradigm to provide a content based routing service. In this approach, publishers publish events. On the other side, nodes send subscriptions to declare their interest and the system is then in charge of forward events to nodes that match their needs. After a state of the art about existing P / S systems, particularly those adapted to VANETs, we choose to test the solutions seemed interesting in a AANET context. To accomplish this, we have developed as a Omnet ++ mobility model using real position reports to replay a full day of trafic of aircraft and several aeronautical applications based on a P / S system to generate realistic data. The results show that these solutions are not completely suitable for AANET context. Therefore, in a second step, we proposed a new P / S system which is more eficient on a AANET. This solution is based on an overlay network built thanks to a new of 1-hopping clustering algorithm suitable for AANET. In order to increase the stability of the overlay architecture, this algorithm is based on the number of neighbors and the relative mobility between the nodes to define groups. The tests show that the P/S system based on this overlay provides better results than the previously tested solutions, whether in terms of network load or percentage of transmitted events.

La prise de décision stratégique concernant des ressources de valeur devrait tenir compte du degré d'aversion au risque. D'ailleurs, de nombreux domaines d'application mettent le risque au cœur de la prise de décision. Toutefois, ce n'est pas le cas de l'apprentissage automatique. Ainsi, il semble essentiel de devoir fournir des indicateurs et des algorithmes dotant l'apprentissage automatique de la possibilité de prendre en considération le risque dans la prise de décision. En particulier, nous souhaiterions pouvoir estimer ce dernier sur de courtes séquences dépendantes générées à partir de la classe la plus générale possible de processus stochastiques en utilisant des outils théoriques d'inférence statistique et d'aversion au risque dans la prise de décision séquentielle. Cette thèse étudie ces deux problèmes en fournissant des méthodes algorithmiques prenant en considération le risque dans le cadre de la prise de décision en apprentissage automatique. Un algorithme avec des performances de pointe est proposé pour une estimation précise des statistiques de risque avec la classe la plus générale de processus ergodiques et stochastiques. De plus, la notion d'aversion au risque est introduite dans la prise de décision séquentielle (apprentissage en ligne) à la fois dans les jeux de bandits stochastiques et dans l'apprentissage séquentiel antagoniste. / Strategic decision-making over valuable resources should consider risk-averse objectives. Many practical areas of application consider risk as central to decision-making. However, machine learning does not. As a result, research should provide insights and algorithms that endow machine learning with the ability to consider decision-theoretic risk. In particular, in estimating decision-theoretic risk on short dependent sequences generated from the most general possible class of processes for statistical inference and through decision-theoretic risk objectives in sequential decision-making. This thesis studies these two problems to provide principled algorithmic methods for considering decision-theoretic risk in machine learning. An algorithm with state-of-the-art performance is introduced for accurate estimation of risk statistics on the most general class of stationary--ergodic processes and risk-averse objectives are introduced in sequential decision-making (online learning) in both the stochastic multi-arm bandit setting and the adversarial full-information setting.

Les algorithmes Branch-and-Bound (B&B) font partie des méthodes exactes pour la résolution de problèmes d’optimisation combinatoire. Les calculs induits par un algorithme B&B sont extrêmement couteux surtout lorsque des instances de grande tailles sont considérées. Un algorithme B&B peut être vu comme une exploration implicite d’un espace représenté sous la forme d’un arbre qui a pour spécificité d’être hautement irrégulier. Pour accélérer l’exploration de cet espace, les calculs parallèles et distribués à très large échelle sont souvent utilisés. Cependant, atteindre des performances parallèles optimales est un objectif difficile et jalonné de plusieurs défis, qui découlent essentiellement de deux facteurs: (i) l’irrégularité des calculs inhérents à l’arbre B&B et (ii) l’hétérogénéité inhérente aux environnements de calcul large échelle. Dans cette thèse, nous nous intéressons spécifiquement à la résolution de ces deux défis. Nous nous concentrons sur la conception d’algorithmes distribués pour l’équilibrage de charge afin de garantir qu’aucune entité de calcul n’est surchargée ou sous-utilisée. Nous montrons comment résoudre l’irrégularité des calculs sur différents type d’environnements, et nous comparons les approches proposées par rapport aux approches de références existantes. En particulier, nous proposons un ensemble de protocoles spécifiques à des contextes homogènes, hétérogène en terme de puissance de calcul (muti-coeurs, CPU et GPU), et hétérogènes en terme de qualité des lien réseaux. Nous montrons à chaque fois la supériorité de nos protocoles à travers des études expérimentales extensives et rigoureuses. / Branch and Bound (B&B) algorithms are exact methods used to solve combinatorial optimization problems (COPs). The computation process of B&B is extremely time-intensive when solving large problem instances since the algorithm must explore a very large space which can be viewed as a highly irregular tree. Consequently, B&B algorithms are usually parallelized on large scale distributed computing environments in order to speedup their execution time. Large scale distributed computing environments, such as Grids and Clouds, can provide a huge amount of computing resources so that very large B&B instances can be tackled. However achieving high performance is very challenging mainly because of (i) the irregular characteristics of B&B workload and (ii) the heterogeneity exposed by large scale computing environments. This thesis addresses and deals with the above issues in order to design high performance parallel B&B on large scale heterogeneous computing environments. We focus on dynamic load balancing techniques which are to guarantee that no computing resources are underloaded or overloaded during execution time. We also show how to tackle the irregularity of B&B while running on different computing environments, and consider to compare our proposed solutions with the state-of-the-art algorithms. In particular, we propose several dynamic load balancing algorithms for homogeneous, node-heterogeneous and link-heterogeneous computing platforms. In each context, our approach is shown to perform much better than the state-of-the-art approaches.

Le sujet de cette thèse est la théorie des graphes. Formellement, un graphe est un ensemble de sommets et un ensemble d’arêtes, c’est à dire de paires de sommets, qui relient les sommets. Cette thèse traite de différents problèmes de décisions binaires ou de minimisations liés à la notion de graphe, et cherche, pour chacun de ces problèmes, à déterminer sa classe de complexité, ou à fournir un algorithme. Le premier chapitre concerne le problème de trouver le plus petit sous-graphe connexe tropical dans un graphe sommet-colorié, c’est à dire le plus petit sous-graphe connexe contenant toutes les couleurs. Le deuxième chapitre concerne les problèmes d’homomorphisme tropical, une généralisation des problèmes de coloriage de graphe. On y trouve un lien entre ces problèmes et plusieurs classes de problèmes d’homomorphismes, dont la classe des Problèmes de Satisfaction de Contraintes. Le troisième chapitre concerne deux variantes lointaines du problème de domination, nommément les problèmes d’alliances globales dans un graphe pondéré et le problème de l’ensemble sûr. Le quatrième chapitre concerne la recherche d’une décomposition arborescente étoilée, c’est à dire une décomposition arborescente dont le rayon des sacs est 1. Enfin, le cinquième chapitre concerne une variante du problème de décider du comportement asymptotique de l’itéré du graphe des bicliques. / This thesis is about graph theory. Formally, a graph is a set of vertices and a set of edges, which are pair of vertices, linking vertices. This thesis deals with various decision problem linked to the notion of graph, and, for each of these problem, try to find its complexity class, or to give an algorithm. The first chapter is about the problem of finding the smallest connected tropical subgraph of a vertex-colored graph, which is the smallest connecter subgraph containing every colors. The second chapter is about problems of tropical homomorphism, a generalization of coloring problem. A link between these problems and several other class of homomorphism problems can be found in this chapter, especially with the class of Constraint Satisfaction Problem. The third chapter is about two variant of the domination problem, namely the global alliance problems in a weighted graph and the safe set problem. The fourth chapter is about the problem of finding a star tree-decomposition, which is a tree-decomposition where the radius of bags is 1. Finally, the fifth chapter is about a variant of the problem of deciding the asymptotic behavior of the iterated biclique graph

Face à la révolution numérique qui parcourt l’aube de ce nouveau siècle, des mutations s’engagent, soulevant de nouvelles questions pour l’humanité. Les postulats humanistes et les propositions des Lumières vont venir éclairer le questionnement autour de l’augmentation de l’Homme porté par le transhumanisme.Nous allons explorer en quoi ces thèses ont enclenché depuis plusieurs siècles une réification de l’Homme et de son monde. La révolution technique entreprise par Turing et celle philosophique, portée par la cybernétique, vont venir proposer une vision algorithmique de l’Homme et de sa réalité. Ce que nous avons appelé le Monde de Turing en est l’aboutissement, faisant de l’homme informationnel, le cybernanthrope, son esclave. Face au totalitarisme libéral de la techné, nous avons identifié un postulat éthique porté par ce que nous avons appelé le delta de Turing. Dès lors, il est possible et nécessaire de faire une critique de la raison artificielle donnant naissance à une éthique pratique de la vertu partagée. Ensuite, nous pourrons analyser comment l’intelligence artificielle peut nous aider à créer une éthique pragmatique des valeurs partagées entre Homme et Machine. / Doctorat en Philosophie / info:eu-repo/semantics/nonPublished

Cette thèse étudie la détection de communautés dans le contexte 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 représentent les relations entre les membres. En particulier, j'étudie quatre différentes définitions de communauté. D'abord, une structure en communautés peut être définie par une partition des sommets telle que tout sommet a une plus grande proportion de voisins dans sa partie que dans toute autre partie. Cette définition peut être adaptée pour l'étude d'une seule communauté. Ensuite, une communauté peut être vue comme un sous graphe tel que tout couple de sommets sont à distance 2 dans ce sous graphe. Enfin, dans le contexte des sites de rencontre, je propose d'étudier une définition de communauté potentielle dans le sens où les membres de la communauté ne se connaissent pas, mais sont liés par des connaissances communes. Pour ces trois définitions, j'étudie la complexité computationnelle et l'approximation de problèmes liés à l'existence ou la recherche de telles communautés dans les graphes. / This thesis deals with community detection in the context of social networks. A social network can be modeled by a graph in which vertices represent members, and edges represent relationships. In particular, I study four different definitions of a community. First, a community structure can be defined as a partition of the vertices such that each vertex has a greater proportion of neighbors in its part than in any other part. This definition can be adapted in order to study only one community. Then, a community can be viewed as a subgraph in which every two vertices are at distance 2 in this subgraph. Finally, in the context of online meetup services, I investigate a definition for potential communities in which members do not know each other but are related by their common neighbors. In regard to these proposed definitions, I study computational complexity and approximation within problems that either relate to the existence of such communities or to finding them in graphs.

Les attaques en fautes (FA) et par canaux cachés (SCA), permettent de récupérer des données sensibles stockées dans des équipements cryptographiques, en exploitant une fuite d'information provenant de leur implémentation matérielle. Le but de cette thèse est donc de formuler un état de l'art des contre-mesures aux SCA adaptées aux FPGA, ainsi que d'implémenter celles qui seront retenues en minimisant les pertes de performance et de complexité. Le cas des algorithmes symétriques tel AES est spécialement étudié, révélant plusieurs faiblesses des contre-mesures habituelles (DPL et masquage) en terme de résistance et de coût. Trois nouvelles contre-mesures sont donc proposées: 1.Des stratégies de placement/routage équilibrés destinées à amélioré la résistance des DPL sur FPGA. 2.Un nouveau type de DPL appelée BCDL (Balanced Cell-based Dual-rail Logic) dont le but est de supprimer la plupart des vulnérabilités liées aux DPLs. BCDL est également résilient à la majeure partie des FA et optimisé pour les FPGA, ce qui induit des complexité et performance compétitives. 3. RSM (Rotating S-Box Masking), une nouvelle technique de masquage pour AES qui montre un haut niveau de performances et résistance pour une complexité réduite. Finalement, plusieurs nouvelles SCA sont présentées et évaluées. RC (Rank Corrector) est un algorithme permettant d'améliorer les autres SCA. La FPCA introduit un nouveau distingueur basée sur la PCA. Puis plusieurs combinaisons (distingueur et mesures) sont proposées et résultent en une diminution du nombre de trace nécessaire à l'attaque. / Side-Channel Analysis (SCA) and Fault Attacks (FA) are techniques to recover sensitive information in cryptographic systems by exploiting unintentional physical leakage, such as the power consumption. This thesis has two main goals: to draw a review of the state of the art of FPGA-compatible countermeasures against SCA and implement t the selected ones with the minimum area and performances overhead. Symmetrical algorithms, specially AES, are studied and several vulnerabilities of usual protections, namely Dual-rail with Precharge Logic (DPL) and masking are analysed, as well as the issue of performance and area overheads. In this context, three new countermeasures are considered: 1. Balance placement and routing (PAR) strategies aiming at enhancing existing DPLs robustness when implemented in modern FPGAs. 2. A new type of DPL called Balanced Cell-based Dual-railLogic (BCDL), to thwart most of the known DPL weaknesses. BCDL also possess a fault resilience mechanism and provides implementation optimisations on FPGA, achieving competitive performances and area overhead. 3. The Rotating S-Box Masking (RSM), a new masking technique for the AES that shows high leveles of robustness and performances while bringing a significant reduction of the area overhead. Finally, several new SCAs are presented and evaluated. Firstly the “Rank Corrector” a SCA enhancement algorithm. Secondly, The FPCA, introduces a novel SCA distinguisher based on the PCA. Then, combinations of either acquisition methods or SCA distinguishers are discussed and show significant decrease in the number of measurements required to perform a successful attack.

Les thèmes de recherche abordés dans ce manuscrit ont trait à la parallélisation d’algorithmes de classification non-supervisée (clustering) sur des plateformes de Cloud Computing. Le chapitre 2 propose un tour d’horizon de ces technologies. Nous y présentons d’une manière générale le Cloud Computing comme plateforme de calcul. Le chapitre 3 présente l’offre cloud de Microsoft : Windows Azure. Le chapitre suivant analyse certains enjeux techniques de la conception d’applications cloud et propose certains éléments d’architecture logicielle pour de telles applications. Le chapitre 5 propose une analyse du premier algorithme de classification étudié : le Batch K-Means. En particulier, nous approfondissons comment les versions réparties de cet algorithme doivent être adaptées à une architecture cloud. Nous y montrons l’impact des coûts de communication sur l’efficacité de cet algorithme lorsque celui-ci est implémenté sur une plateforme cloud. Les chapitres 6 et 7 présentent un travail de parallélisation d’un autre algorithme de classification : l’algorithme de Vector Quantization (VQ). Dans le chapitre 6 nous explorons quels schémas de parallélisation sont susceptibles de fournir des résultats satisfaisants en terme d’accélération de la convergence. Le chapitre 7 présente une implémentation de ces schémas de parallélisation. Les détails pratiques de l’implémentation soulignent un résultat de première importance : c’est le caractère en ligne du VQ qui permet de proposer une implémentation asynchrone de l’algorithme réparti, supprimant ainsi une partie des problèmes de communication rencontrés lors de la parallélisation du Batch K-Means. / He subjects addressed in this thesis are inspired from research problems faced by the Lokad company. These problems are related to the challenge of designing efficient parallelization techniques of clustering algorithms on a Cloud Computing platform. Chapter 2 provides an introduction to the Cloud Computing technologies, especially the ones devoted to intensivecomputations. Chapter 3 details more specifically Microsoft Cloud Computing offer : Windows Azure. The following chapter details technical aspects of cloud application development and provides some cloud design patterns. Chapter 5 is dedicated to the parallelization of a well-known clustering algorithm: the Batch K-Means. It provides insights on the challenges of a cloud implementation of distributed Batch K-Means, especially the impact of communication costs on the implementation efficiency. Chapters 6 and 7 are devoted to the parallelization of another clustering algorithm, the Vector Quantization (VQ). Chapter 6 provides an analysis of different parallelization schemes of VQ and presents the various speedups to convergence provided by them. Chapter 7 provides a cloud implementation of these schemes. It highlights that it is the online nature of the VQ technique that enables an asynchronous cloud implementation, which drastically reducesthe communication costs introduced in Chapter 5.