Grâce à une analyse statistique de l’équation de la Mesure des Interféromètres Radio, un schéma de pondération adaptatif est dérivé,basé sur la qualité de calibration des données d’un instrument interférométrique. Ce schéma est utilisé sur une observation d’un champ extragalactique, l’ExtendedGroth Strip, observation qui contient une source radio-vive (3C295) dans son champ de vue. Cette source est résolue avec LOFAR-VLBI ; un modèle de source est créé afin de calibrer les stations LOFAR internationales. Cela permettra d’imager le champ a une résolution comparable à celle du Hubble Space Telescope, dont des données sont disponibles pour ce champ extragalactique. / By performing a statistical analysis ofthe Radio Interferometer’s MeasurementEquation, we derive adaptivequality-based weighting schemes.These are deployed on an observationof the Extended Groth Strip,which includes a bright 3C sourcein the field of view. This source,which is resolved for LOFAR-VLBI,is modeled and used as a calibratorsource for the Extended Groth Strip.This will allow the field to be imagedwith a resolution matching the HubbleSpace Telescope’s, of which dataare available for this field.

La cryptographie à base de réseaux euclidiens est un domaine prometteur pour la construction de primitives cryptographiques post-quantiques. Un problème fondamental, lié aux réseaux, est le problème du plus court vecteur (ou SVP, pour Shortest Vector Problem). Ce problème est supposé être difficile à résoudre même avec un ordinateur quantique. Afin d’améliorer l’efficacité des protocoles cryptographiques, on peut utiliser des réseaux structurés, comme par exemple des réseaux idéaux ou des réseaux modules (qui sont une généralisation des réseaux idéaux). La sécurité de la plupart des schémas utilisant des réseaux structurés dépend de la difficulté du problème SVP dans des réseaux modules, mais un petit nombre de schémas peuvent également être impactés par SVP dans des réseaux idéaux. La principale construction pouvant être impactée par SVP dans des réseaux idéaux est la fonction multilinéaire GGH13. Cette fonction multilinéaire est principalement utilisée aujourd’hui pour construire des obfuscateurs de programmes, c’est-à-dire des fonctions qui prennent en entrée le code d’un programme et renvoie le code d’un programme équivalent (calculant la même fonction), mais qui doit cacher la façon dont le programme fonctionne.Dans cette thèse, nous nous intéressons dans un premier temps au problème SVP dans les réseaux idéaux et modules. Nous présentons un premier algorithme qui, après un pre-calcul exponentiel, permet de trouver des vecteurs courts dans des réseaux idéaux plus rapidement que le meilleur algorithme connu pour des réseaux arbitraires. Nous présentons ensuite un algorithme pour les réseaux modules de rang 2, également plus efficace que le meilleur algorithme connu pour des réseaux arbitraires, à condition d’avoir accès à un oracle résolvant le problème du plus proche vecteur dans un réseau fixé. Le pré-calcul exponentiel et l’oracle pour le problème du plus proche vecteurs rendent ces deux algorithmes inutilisables en pratique.Dans un second temps, nous nous intéressons à la fonction GGH13 ainsi qu’aux obfuscateurs qui l’utilisent. Nous étudions d’abord l’impact des attaques statistiques sur la fonction GGH13 et ses variantes. Nous nous intéressons ensuite à la sécurité des obfuscateurs utilisant la fonction GGH13 et proposons une attaque quantique contre plusieurs de ces obfuscateurs. Cette attaque quantique utilise entre autres un algorithme calculant un vecteur court dans un réseau idéal dépendant d’un paramètre secret de la fonction GGH13. / Lattice-based cryptography is a promising area for constructing cryptographic primitives that are plausibly secure even in the presence of quantum computers. A fundamental problem related to lattices is the shortest vector problem (or SVP), which asks to find a shortest non-zero vector in a lattice. This problem is believed to be intractable, even quantumly. Structured lattices, for example ideal lattices or module lattices (the latter being a generalization of the former), are often used to improve the efficiency of lattice-based primitives. The security of most of the schemes based on structured lattices is related to SVP in module lattices, and a very small number of schemes can also be impacted by SVP in ideal lattices.In this thesis, we first focus on the problem of finding short vectors in ideal and module lattices.We propose an algorithm which, after some exponential pre-computation, performs better on ideal lattices than the best known algorithm for arbitrary lattices. We also present an algorithm to find short vectors in rank 2 modules, provided that we have access to some oracle solving the closest vector problem in a fixed lattice. The exponential pre-processing time and the oracle call make these two algorithms unusable in practice.The main scheme whose security might be impacted by SVP in ideal lattices is the GGH13multilinear map. This protocol is mainly used today to construct program obfuscators, which should render the code of a program unintelligible, while preserving its functionality. In a second part of this thesis, we focus on the GGH13 map and its application to obfuscation. We first study the impact of statistical attacks on the GGH13 map and on its variants. We then study the security of obfuscators based on the GGH13 map and propose a quantum attack against multiple such obfuscators. This quantum attack uses as a subroutine an algorithm to find a short vector in an ideal lattice related to a secret element of the GGH13 map.

Les données du monde réel ont manifestement une composante géométrique importante et suggère les patterns géométriques signifiants. Les méthodes qui utilisent la nature géométrique des données sont activement développés dans plusieurs domaines scientifiques, comme, par exemple, la géométrie algorithmique, la géométrie discrète, la synthèse d'images, la vision par ordinateur. Dans le travail présent, nous utilisons les structures géométriques afin de modéliser des algorithmes efficaces pour deux domaines, celui de synthèse d'images et de l'optimisation combinatoire. Dans la première partie il s'agit de la structure de données géométriques, appelé une décomposition bien-séparée, et son application pour un des problèmes les plus difficiles dans la synthèse d'images, un efficace rendu photo-réalistique. Une solution consiste à appliquer toute une famille de méthodes de many-lights qui fait une approximation d'illumination globale par calcule individuelle d'illumination avec un grand nombre de VPLs (virtual point light) répartis sur les surfaces. L'application individuelle de chacun VPL résulte dans un grand nombre des calculs. Une des stratégies de la réussite pour réduire les computations est de faire les clusteurs considérés qui sont consideré comme une seul émetteur. Nous utilisons la décomposition bien-séparée de points comme le fondement de la structure des données susceptible de procéder à un calcul préliminaire et de conserver d'une façon compacte un grand nombre des clusterisations individuels potentiels ce qui montre que la clusterisation des VPL plus correspondante peut être extraite de cette structure de données d'une manière efficace. Nous montrons qu'au lieu de regroupper les points et/ou VPL indépendemment il vaut mieux produire les clusteurs sur l'espace de produit du nombre des points à nuancer et un groupe de VPL à la base de l'illumination des paires induite. En plus, nous proposons une technique adaptive afin d'échantillonner pour réduire le nombre des demandes de vérifications de visibilité pour chaque clusteur de l'espace de produit. Notre méthode consiste à détenir chaque émetteur qui peut être rapproché par VPL, matériaux spéculaire et à performer les méthodes précédents réconnus les meilleurs jusqu'au présent. La deuxième partie est consacrée au développement de nouveaux algorithmes d'approximation pour un problème fondamental de NP complet dans la géométrie algorithmique, précisément le problème du hitting set, avec une précision pour le cas d'un groupe de points et d'un groupe de disques, nous souhaiterons calculer les plus petits nombre du points qui touche tous les disques. Il arrive que les algorithmes efficaces à détecter le hitting set repose sur une structure géométrique clée, appelée epsilon-net. Nous donnons un algorithme utilisant uniquement les triangulisations de Delaunay pour construire les epsilon-nets de taille 13.4/epsilon. Nous donnons une implémentation pratique de la technique à calculer les hitting sets dans le temps quasi-linéaire en utilisant des epsilon-nets de petites tailles. Nos résultats aboutissent à une approximation de 13.4 pour le problème de hitting set par un algorithme qui fonctionne même pour les grands ensembles de données. Pour les ensembles de taille plus petite, nous proposons une implémentation de la technique de recherche locale avec une approximation bornes supérieures, avec le résultat obtenu d'approximation de (8 + epsilon) dans le temps O(n^{2.34}) / Real-world data has a large geometric component, showing significant geometric patterns. How to use the geometric nature of data to design efficient methods has became a very important topic in several scientific fields, e.g., computational geometry, discrete geometry, computer graphics, computer vision. In this thesis we use geometric structures to design efficient algorithms for problems in two domains, computer graphics and combinatorial optimization. Part I focuses on a geometric data structure called well-separated pair decomposition and its usage for one of the most challenging problems in computer graphics, namely efficient photo-realistic rendering. One solution is the family of many-lights methods that approximate global illumination by individually computing illumination from a large number of virtual point lights (VPLs) placed on surfaces. Considering each VPL individually results in a vast number of calculations. One successful strategy the reduce computations is to group the VPLs into a small number of clusters that are treated as individual lights with respect to each point to be shaded. We use the well-separated pair decomposition of points as a basis for a data structure for pre-computing and compactly storing a set of view independent candidate VPL clusterings showing that a suitable clustering of the VPLs can be efficiently extracted from this data structure. We show that instead of clustering points and/or VPLs independently what is required is to cluster the product-space of the set of points to be shaded and the set of VPLs based on the induced pairwise illumination. Additionally we propose an adaptive sampling technique to reduce the number of visibility queries for each product-space cluster. Our method handles any light source that can be approximated with virtual point lights (VPLs), highly glossy materials and outperforms previous state-of-the-art methods. Part II focuses on developing new approximation algorithms for a fundamental NP-complete problem in computational geometry, namely the minimum hitting set problem with particular focus on the case where given a set of points and a set of disks, we wish to compute the minimum-sized subset of the points that hits all disks. It turns out that efficient algorithms for geometric hitting set rely on a key geometric structure, called epsilon-net. We give an algorithm that uses only Delaunay triangulations to construct epsilon-nets of size 13.4/epsilon and we provide a practical implementation of a technique to calculate hitting sets in near-linear time using small sized epsilon-nets. Our results yield a 13.4 approximation for the hitting set problem with an algorithm that runs efficiently even on large data sets. For smaller datasets, we present an implementation of the local search technique along with tight approximation bounds for its approximation factor, yielding an (8 + epsilon)-approximation algorithm with running time O(n^{2.34})

Cette thèse a pour objet l’étude de l'apport de l’introduction des technologies de l'information et de la communication pour l'enseignement (TICE) dans le processus enseignement-apprentissage de l'algorithmique chez les apprenants débutants, en particulier une application de simulation d'algorithmes (AlgoBox). L'utilisation de cet artefact computationnel a pour objectif de proposer une contribution afin de juguler le problème du fort taux d'échec constaté par les responsables administratifs et pédagogiques depuis plusieurs années dans l'enseignement de l'algorithmique et de la programmation à l'Ecole Normale Supérieure de l’Enseignement Technique (ENSET) de Libreville. Ainsi, la mise en place d'un dispositif expérimental conformément aux hypothèses émises et faisant suite à une première expérimentation d'identification et d'analyse de certains indicateurs, a permis de faire l'étude de l'apport du logiciel de simulation d'algorithme. Au terme de cette recherche, il est établi une légère augmentation des performances des apprenants vraisemblablement due non seulement à l’apport de l’artefact, mais aussi à la réactivation des connaissances liées aux savoirs implicites portées par la tâche prescrite. Il convient donc de préconiser d’accompagner l’usage de cette application par la mise en œuvre d’une nouvelle approche afin de permettre la construction d’une pédagogie adaptée (Ginestié, 2008). / This thesis has for object to study of the contribution of the introduction of the TICE's in the teaching-learning process of the algorithmics to the novice learners, in particular an application of simulation of algorithmics (AlgoBox). The use of this computational artifact aims at proposing a contribution in order to solvat the problem of the high rate of failure noticed by the administratives and pedagogicals responsibles for several years in the teaching of the algorithmics and programmations at Ecole Normale Supérieure de l'Enseignement Technique (ENSET) of Libreville.Thereby the implementation of an experimental device according to the emitted hypotheses and following upon a first experiment of identification and analysis of certain indicators, has allowed making the study of the contribution of the simulation software of algorithm. At the end of this research, it is therefore note a slight increase in the performances of the learners most probably due not only to the contribution of the artifact, but also to the reactivation of implicit knowledge carried out by the prescribed task. It is thus advisable to foresee to accompany the use of this application by the implementation a new approach so as to allow the construction of an adapted pedagogy (Ginestie, 2008).

Alors que l'on observe une disponibilité croissante de données décrivant des objets 3D, il semble essentiel de disposer de moyens de traitement efficaces de ces derniers. Ainsi, nous présentons dans ce mémoire un ensemble d'outils de manipulation de surfaces, qui exploitent à la fois leurs propriétés géométriques et topologiques. Après avoir décrit différents résultats classiques de topologie, et les structures et résultats fondamentaux de la topologie algorithmique, nous présentons les concepts de M-tuiles et M-pavages, offrant notamment une grande souplesse combinatoire, et permettant de décrire finement le résultat d'algorithmes de découpage topologique. En s'appuyant sur les possibilités de description de ce formalisme, nous présentons différents algorithmes de découpage de surface, prenant en compte non seulement la topologie et la géométrie des surfaces, mais également les propriétés des M-tuiles issues de ces découpages. Nous présentons également dans ce mémoire une généralisation des lacets par les n-cets, permettant notamment de décrire une approche originale de pavage de surfaces en cylindres puis en quadrangles. Enfin, deux applications de ces outils de découpage sont présentées. Dans un premier temps, nous déclinons ces algorithmes de découpage dans le contexte de l'infographie, en proposant un ensemble d'outils d'aide à la manipulation de surfaces. Puis nous présentons dans un second temps une chaîne complète de traitement de données issues de l'imagerie médicale, permettant la visualisation dynamique de données complexes sur des cartes planes de la surface du cerveau, en illustrant sa pertinence dans le contexte de la stimulation corticale. En conclusion de ces travaux, nous présentons les perspectives que laissent entrevoir ces développements originaux, notamment en exploitant les possibilités offertes par les n-cets et les M-pavages, qui semblent multiples. Nous soulignons également la richesse qu'assure une exploration des domaines applicatifs par des outils issus de la géométrie algorithmique.

Les problèmes étudiés dans cette thèse sont motivés par des questions issues de l'optimisation des réseaux de télécommunication. Nous avons abordé ces problèmes sous deux angles principaux. D'une part nous avons étudié leurs propriétés de complexité et d'inapproximabilité. D'autre part nous avons dans certains cas proposé des algorithmes exacts ou d'approximation ou encore des méthodes heuristiques que nous avons pu comparer à des formulations en programmes linéaires mixtes sur des instances particulières.<br /><br />Nous nous intéressons aussi bien aux réseaux de coeur qu'aux réseaux d'accès. Dans le premier chapitre, nous présentons brièvement les réseaux d'accès ainsi que les réseaux multiniveaux de type IP/WDM et l'architecture MPLS que nous considérons pour les réseaux de coeur. Ces réseaux sont composés d'un niveau physique sur lequel est routé un niveau virtuel. A leur tour les requêtes des utilisateurs sont routées sur le niveau virtuel. Nous abordons également la tolérance aux pannes dans les réseaux multiniveaux qui motive deux problèmes que nous avons étudiés.<br /><br />Le second chapitre est consacré à la conception de réseaux virtuels. Dans un premier temps nous modélisons un problème prenant en compte la tolérance aux pannes, puis nous en étudions un sous-problème, le groupage. Notre objectif est de minimiser le nombre de liens virtuels, ou tubes, à installer pour router un ensemble de requêtes quelconque lorsque le niveau physique est un chemin orienté.<br /><br />Le troisième chapitre traite des groupes de risque (SRRG) induits par l'empilement de niveaux au sein d'un réseau multiniveaux. Grâce à une modélisation par des graphes colorés, nous étudions la connexité et la vulnérabilité aux pannes de ces réseaux.<br /><br />L'objet du quatrième chapitre est le problème du placement d'instruments de mesure du trafic dans le réseau d'accès d'un opérateur. Nous considérons aussi bien les mesures passives qu'actives. La surveillance du trafic possède de nombreuses applications, en particulier la détection de pannes et l'évaluation des performances d'un réseau.

In this thesis, we focus on "structural information" in computer graphics, that is the information concerning the structure of 3D objects or scenes. More specifically, we define structural information as a two-scale notion, namely the object and the scene levels and propose a way of structuring 3D Geometry at both levels using the information of symmetry and instancing. In the first part of this thesis, we propose an original method to structure the geometry at the object level based on the information of symmetry. Inspired by the work on principal component analysis, we introduce for this purpose the generalized moment functions of a 3D shape. From the symmetry information that we have computed on the objects of the scene, we present in the second part of this thesis an approach to represent an unstructured 3D scene as a hierarchy of instances adapted to common tasks such as rendering or geometry editing.

Les graphes dynamiques sont un outil de plus en plus utilisé dans des contextes variés où il s'avère nécessaire de modéliser des environnements changeants ou incertains. Les modèles aujourd'hui proposés sont dédiés à ces applications précises. Il n'existe pas de modèle général reprenant, hors de tout contexte applicatif, ces caractéristiques. D'autre part la résolution de problèmes liés à ces environnements dynamiques et incertains est problématique. Nous proposons, ici, la formalisation d'un modèle général de graphe dynamique. <br /><br />Nous étudions la résolution de problèmes dans ces graphes à l'aide de méthodes inspirées de mécanismes d'intelligence collective. <br /><br />Les modèles proposés sont validés dans le contexte applicatif des réseaux mobiles ad hoc. Une approche originale de construction et de maintien de chemins de communication sous plusieurs contraintes est proposée. Le problème de la construction et du maintien d'une forêt couvrante dans un réseau mobile ad hoc est également étudié.

Cette thèse est une contribution à l'étude des différentes notions effectives d'aléatoire pour les objets individuels (essentiellement les suites binaires finies ou finies). Dans le premier chapitre nous considérons les approches de l'aléatoire par la théorie des jeux (martingales et stratégies) que nous comparons à l'approche historique par les fréquences qui remonte au début du 20ème siècle avec les travaux de von Mises. Le résultat principal de ce chapitre est une relation explicite entre la vitesse de gain d'une martingale (ou stratégie) sur une suite binaire et le biais des sous-suites extraites. Le second chapitre porte sur les liens existant entre les différentes définitions de l'aléatoire pour les suites binaires infinies et la notion de complexité de Kolmogorov, définie comme étant la taille du plus court programme qui génère un objet donné. De nombreux résultats sont déjà connus dans ce domaine. Nous présentons une approche nouvelle, en utilisant non pas la complexité de Kolmogorov elle-même, mais ses bornes supérieures calculables. Cette approche est unificatrice, en ce sens qu'elle permet de caractériser précisément une grande variété de notions d'aléatoire, dont certaines pour qui la complexité de Kolmogorov échoue. Le troisième et dernier chapitre étudie l'extension des notions effectives d'aléatoire à des mesures de probabilité calculables quelconques, et plus particulièrement les relations d'équivalence qu'elles induisent sur ces mesures (où deux mesures sont équivalentes si elles ont les mêmes éléments aléatoires). Une preuve constructive (par les martingales) du théorème de Kakutani (qui caractérise l'équivalence entre les mesures de Bernoulli généralisées) y est notamment obtenue. Enfin, nous discutons en toute généralité (c'est-à-dire pour des mesures quelconques) les relations d'équivalence induites, dont nous donnons une classification complète.

Cette thèse a pour objet l'étude des systèmes de particules et collisions dans les automates cellulaires. En se basant sur des observations expérimentales, nous proposons des définitions formelles de ces objets et montrons qu'ils peuvent être mis en relation avec des coloriages réguliers du plan. À l'aide d'une représentation sous forme syntaxique de ces objets, nous introduisons une opération syntaxique d'assemblage: les schémas de ligature. Cette opération peut être interprétée en termes de coloriage et correspond à une opération intuitive utilisée dans l'étude algorithmique des automates cellulaires. Nous prouvons que, dans le cas d'assemblages finis, le lien entre l'opération syntaxique et l'interprétation peut être complètement caractérisé de façon algorithmique. Nous explorons ensuite des pistes d'extension de ces systèmes facilitant l'encodage et permettant de dépasser le cas fini. Enfin, nous étudions les applications de tels systèmes en lien avec l'universalité dans les automates cellulaires. En particulier, nous donnons une nouvelle preuve de l'universalité de l'automate cellulaire 110 et présentons la construction d'un automate cellulaire intrinsèquement universel de rayon 1 et à 4 états.