La programmation linéaire en nombres entiers est une approche robuste qui permet de résoudre rapidement de grandes instances de problèmes d'optimisation discrète. Toutefois, les problèmes gagnent constamment en complexité et imposent parfois de fortes limites sur le temps de calcul. Il devient alors nécessaire de développer des méthodes spécialisées afin de résoudre approximativement ces problèmes, tout en calculant des bornes sur leurs valeurs optimales afin de prouver la qualité des solutions obtenues. Nous proposons d'explorer une approche de reformulation en nombres entiers guidée par la relaxation lagrangienne. Après l'identification d'une forte relaxation lagrangienne, un processus systématique permet d'obtenir une seconde formulation en nombres entiers. Cette reformulation, plus compacte que celle de Dantzig et Wolfe, comporte exactement les mêmes solutions entières que la formulation initiale, mais en améliore la borne linéaire: elle devient égale à la borne lagrangienne. L'approche de reformulation permet d'unifier et de généraliser des formulations et des méthodes de borne connues. De plus, elle offre une manière simple d'obtenir des reformulations de moins grandes tailles en contrepartie de bornes plus faibles. Ces reformulations demeurent de grandes tailles. C'est pourquoi nous décrivons aussi des méthodes spécialisées pour en résoudre les relaxations linéaires. Finalement, nous appliquons l'approche de reformulation à deux problèmes de localisation. Cela nous mène à de nouvelles formulations pour ces problèmes; certaines sont de très grandes tailles, mais nos méthodes de résolution spécialisées les rendent pratiques. / Integer linear programming is a robust and efficient approach to solve large-scale instances of combinatorial problems. However, problems constantly gain in complexity and sometimes impose strong constraints on computation times. We must then develop specialised methods to compute heuristic primal solutions to the problem and derive lower bounds on the optimal value, and thus prove the quality of our primal solutions. We propose to guide a reformulation approach for mixed integer programs with Lagrangian relaxations. After the identification of a strong relaxation, a mechanical process leads to a second integer formulation. This reformulation is equivalent to the initial one, but its linear relaxation is equivalent to the strong Lagrangian dual. We will show that the reformulation approach unifies and generalises prior formulations and lower bounding approaches, and that it exposes a simple mechanism to reduce the size of reformulations in return for weaker bounds. Nevertheless, our reformulations are large. We address this issue by solving their linear relaxations with specialised methods. Finally, we apply the reformulation approach to two location problems. This yields novel formulations for both problems; some are very large but, thanks to the aforementioned specialised methods, still practical.

Ce manuscrit est structuré en deux parties. La première partie composée des chapitres 2à 4 aborde le problème d'estimation du nombre de classes dans une population avec une application en écologie. La deuxième partie, correspondant au chapitre 5,concerne la mise en oeuvre de méthodes statistiques pour analyser des données de pêche. Dans la première partie, nous considérons une population hétérogène subdiviséeen plusieurs classes. À partir d'un échantillon, les effectifs d'individus observés parclasse, encore appelés abondances, sont utilisés pour estimer le nombre total declasses dans la population. Dans la littérature consacrée à l'estimation du nombrede classes, les méthodes basées sur un mélange de distributions de Poisson semblentêtre les plus performantes (voir par exemple les travaux de Chao and Bunge (2002)dans le cadre paramétrique et celui de Wang and Lindsay (2005) dans un cadrenon paramétrique). La mise en oeuvre de ces approches sur des données réellesmet en évidence que la distribution des abondances peut être approchée par unedistribution convexe. Nous proposons une approche non paramétrique pour estimerla distribution des abondances sous contrainte de convexité. Cette contrainte définitun cadre théorique d'estimation d'une densité discrète. Le problème d'estimation dunombre de classes est donc abordé en deux volets. Nous montrons d'une part l'existenceet l'unicité d'un estimateur d'une densité discrète sous la contrainte de convexité.Sous cette contrainte, nous démontrons qu'une densité discrète s'écrit comme un mélange de densités triangulaires. À partir de l'algorithme de réduction du supportproposé par Groeneboom et al. (2008), nous proposons un algorithme exact pourestimer les proportions dans le mélange. D'autre part, la procédure d'estimationd'une densité discrète convexe nous sert de cadre pour l'estimation de la distributiontronquée en zéro des observations d'abondance. L'estimation de la loi tronquée obtenue est ensuite prolongée en zéro pour estimer la probabilité qu'une classe ne soit pasobservée. Ce prolongement en zéro est fait de façon à annuler la proportion dela première composante dans le mélange de densités triangulaires. Nousaboutissons à une estimation du nombre de classes à l'aide d'un modèle binomial ensupposant que chaque classe apparaît dans un échantillon par une épreuve deBernoulli. Nous montrons la convergence en loi de l'estimateur proposé. Sur le plan pratique, une application aux données réelles en écologie est présentée. La méthode est ensuite comparée à d'autres méthodes concurrentes à l'aide de simulations. La seconde partie présente l'analyse des données de pêche collectées dans le fleuveOuémé au Bénin. Nous proposons une démarche statistique permettant de regrouperles espèces selon leur profil temporel d'abondances, d'estimer le stock d'une espèceainsi que leur capturabilité par les engins de pêche artisanale. / This manuscript is structured in two parts. The #rst part composed of Chapters 2to 4 deals with the problem of estimating the number of classes in a population withan application in ecology. The second part, corresponding to Chapter 5, concernsthe application of statistical methods to analyze fisheries data.In the first part, we consider a heterogeneous population split into several classes.From a sample, the numbers of observed individuals per class, also called abun-dances, are used to estimate the total number of classes in the population. In theliterature devoted to the number of classes estimation, methods based on a mix-ture of Poisson distributions seem to be the most effcient (see for example the workof Chao and Bunge (2002) in the parametric framework and that of Wang and Lind-say (2005) in a non-parametric framework). Applications of these approaches to realdata show that the distribution of abundances can be approximated by a convexdistribution. We propose a non-parametric approach to estimate the distribution ofabundances under the constraint of convexity. This constraint defines a theoreticalframework for estimating a discrete density. The problem of estimating the numberof classes is then tackled in two steps.We show on the one hand the existence and uniqueness of an estimator of adiscrete density under the constraint of convexity. Under this constraint, we provethat a discrete density can be written as a mixture of triangular distributions. Usingthe support reduction algorithm proposed by Groeneboom et al. (2008), we proposean exact algorithm to estimate the proportions in the mixture.On the other hand, the estimation procedure of a discrete convex density is usedto estimate the zero-truncated distribution of the observed abundance data. Thezero-truncated distribution estimate is then extended at zero to derive an estimateof the probability that a class is not observed. This extension is made so as tocancel the first component in the mixture of triangular distributions. An estimateof the total number of classes is obtained through a binomial model assuming thateach class appears in a sample by a Bernoulli trial. We show the convergence inlaw of the proposed estimator. On practical view, an application to real ecologicaldata is presented. The method is then compared to other concurrent methods usingsimulations.The second part presents the analysis of fisheries data collected on the Ouémériver in Benin. We propose a statistical approach for grouping species accordingto their temporal abundance profile, to estimate the stock of a species and theircatchability by artisanal fishing gears.

La simulation numérique est largement utilisée pour évaluer les performances aérodynamiques des aéronefs ainsi qu'en optimisation de forme. Ainsi l'objectif de ces simulations est souvent le calcul de fonctions aérodynamiques. L'objet de cette thèse est d'étudier des méthodes d'adaptation de maillages basées sur la dérivée totale de ces fonctions par rapport aux coordonnées du maillage (notée dJ/dX). Celle-ci pouvant être calculée par la méthode adjointe discrète. La première partie de cette étude concerne l'application de méthodes d'adaptation de maillages appliquées à des écoulements de fluides parfaits. Le senseur qui détecte les zones de maillage à raffiner s'appuie sur la norme de cette dérivée pour adapter des maillages pour le calcul d'une fonction J. La seconde partie du travail est la construction et l'étude de critères plus fiables basés sur dJ/dX pour d'une part adapter des maillages et d'autre part estimer si un maillage est bien adapté ou non pour le calcul de la fonction J. De plus une méthode de remaillage plus efficace basée sur une EDP elliptique est aussi présentée. Cette nouvelle méthode est appliquée pour des écoulements bidimensionnels de fluides parfaits ainsi que pour un écoulement décrit par les équations RANS. La dernière partie de l'étude est consacrée à l'application de la méthode proposée à des cas tridimensionnels d'écoulement RANS sur des géométries d'intérêt industriel. / Numerical simulation is widely used for the assessment of aircraft aerodynamic performances and shape optimizations. Hence the objective of these simulations is often to compute aerodynamic outputs. The purpose of this thesis is to study mesh adaptation methods based on the total derivative of the outputs with respect to mesh coordinates (denoted dJ/dX). This derivative can be computed using the discrete adjoint method. The first part of this study is about the application of mesh adaptation methods applied for Eulerian flows. The mesh locations to refine are detected using a sensor based on the norm of the derivative dJ/dX. This study confirmed that this derivative is relevant in order to adapt a mesh for the computation of the output J. The second part of this work is the construction and the study of reliable criteria based on dJ/dX for both mesh adaptation and the quality assessment of a given mesh for the computation of the output J. Moreover a more efficient remeshing method based on an elliptic PDE is presented too. This new method is applied for both two-dimensional Eulerian flows and a flow described by the RANS equations. The last part of the study is devoted to the application of the proposed method to three-dimensional RANS flows on geometries of industrial interest.

Dans ce travail de thèse , je présente comment extraire les géométries discrètes de l'espace-temps de la formulation covariante de la gravitaté quantique à boucles, qui est appelé le formalisme de la mousse de spin. LQG est une théorie quantique de la gravité qui non-perturbativement quantifie la relativité générale indépendante d'un fond fixe. Il prédit que la géométrie de l'espace est quantifiée, dans lequel l'aire et le volume ne peuvent prendre que la valeur discrète. L'espace de Hilbert cinématique est engendré par les fonctions du réseau de spin. L'excitation de la géométrie peut être parfaitement visualisée comme des polyèdres floue qui collées à travers leurs facettes. La mousse de spin définit la dynamique de la LQG par une amplitude de la mousse de spin sur un complexe cellulaire avec un état du réseau de spin comme la frontiére. Cette thèse présente deux résultats principaux. Premièrement, la limite semi-classique de l'amplitude de la mousse de spin sur un complexe simplicial arbitraire avec une frontière est complètement étudiée. La géométrie discrète classique de l'espace-temps est reconstruite et classée par les configurations critiques de l'amplitude de la mousse de spin. Deuxièmement, la fonction de trois-point de LQG est calculé. Il coïncide avec le résultat de la gravité discrète. Troisièmement, la description des géométries discrètes de hypersurfaces nulles est explorée dans le cadre de la LQG. En particulier, la géométrie nulle est décrit par une structure singulière euclidienne sur la surface de type espace à deux dimensions définie par un feuilletage de l'espace-temps par hypersurfaces nulles. / In this thesis, I will present how to extract discrete geometries of space-time fromthe covariant formulation of loop quantum gravity (LQG), which is called the spinfoam formalism. LQG is a quantum theory of gravity that non-perturbative quantizesgeneral relativity independent from a fix background. It predicts that the geometryof space is quantized, in which area and volume can only take discrete value. Thekinematical Hilbert space is spanned by Penrose's spin network functions. The excita-tion of geometry can be neatly visualized as fuzzy polyhedra that glued through theirfacets. The spin foam defines the dynamics of LQG by a spin foam amplitude on acellular complex, bounded by the spin network states. There are three main results inthis thesis. First, the semiclassical limit of the spin foam amplitude on an arbitrarysimplicial cellular complex with boundary is studied completely. The classical discretegeometry of space-time is reconstructed and classified by the critical configurations ofthe spin foam amplitude. Second, the three-point function from LQG is calculated.It coincides with the results from discrete gravity. Third, the description of discretegeometries of null hypersurfaces is explored in the context of LQG. In particular, thenull geometry is described by a Euclidean singular structure on the two-dimensionalspacelike surface defined by a foliation of space-time by null hypersurfaces. Its quan-tization is U(1) spin network states which are embedded nontrivially in the unitaryirreducible representations of the Lorentz group.

Le ballast est la couche granulaire, formée de grains rocheux irréguliers de taille centimétrique, qui supporte la voie ferrée par l'intermédiaire des traverses. Son rôle est crucial dans la transmission des efforts statiques et dynamiques imposés par la circulation des trains vers le sol supportant la voie. Pour comprendre le phénomène de tassement du ballast, qui croît fortement avec la vitesse des trains, et qui entraîne de coûteuses opérations de maintenance, il est important de bien connaître l’influence de la morphologie des grains sur le comportement mécanique du ballast. C’est l’objectif de cette thèse, dans laquelle est développée une technique innovante de caractérisation morphologique fondée sur la décomposition orthogonale aux valeurs propres (« POD »). Cette technique, appliquée à des données expérimentales détaillées (scans 3D) permet d’identifier un choix optimal de fonctions de forme. Il est alors possible de générer numériquement des assemblages granulaires représentatifs du ballast avec différents degrés de raffinement selon le nombre de fonctions de base retenu. Pour passer aux applications mécaniques, les grains, ainsi modélisés par un nombre limité de coefficients, doivent ensuite par une opération de maillage être assimilés à des polyèdres convexes dont le comportement mécanique est simulé par la méthode des éléments discrets (dynamique des contacts, avec le logiciel LMGC90). On détermine alors des caractéristiques de base comme l'angle de frottement interne et la compacité dans l'état critique de cisaillement quasi-statique maintenu. Ces propriétés sont stabilisées à partir d’un nombre assez faible de fonctions de forme (de l’ordre de 10). Dans le domaine de la description morphologique, l’approche fondée sur la POD ouvre d’intéressantes perspectives pour améliorer les caractérisations usuelles. Elle permet de différencier les ballasts selon leur degré d’usure ou la carrière dont ils proviennent. Elle conduit également à une méthode d’identification des faces et des courbures des grains / The ballast is the granular layer formed of irregular centimeter-sized rock grains, which supports the railway through the sleepers. Its role is crucial in the transmission of static and dynamic forces imposed by the movement of trains towards the ground supporting the track. To understand the phenomenon of ballast settlement, which increases significantly with the speed of the trains, and which requires costly maintenance operations, it is important to understand the influence of the grain morphology on the mechanical behavior of the ballast. Such is the objective of this thesis. First, an innovative method for particle shape characterization is developed, based on the Proper Orthogonal Decomposition (POD). When applied to highly accurate experimental data (3D scans of ballast grains), this technique enables the identification of an optimal set of shape functions, such that the shape information is condensed in a minimum number of coefficients. It becomes then possible to numerically generate granular assemblies that are representative of the morphology of ballast grains with different degrees of refinement according to the number of retained shape functions. In order to investigate their mechanical properties, the grains modeled by a limited number of coefficients have to be subjected to a meshing procedure and turned into convex polyhedra, suitable for numerical simulations of mechanical behaviours via the discrete element method (contact dynamics, using the LMGC90 software). We determine some fundamental characteristics such as the internal friction angle and the solid fraction in the critical state of quasistatic steady shear flow. These properties are stabilized after including a rather small number of shape functions in to the model (on the order of 10).The method also opens promising avenues for morphological characterization applications. It proves able to distinguish ballast grains with varying degrees of wear, or produced in different quarries. It also leads to a procedure for identifying faces and curvatures

L’objet de cette thèse est l’étude du modèle plat, l’ingrédient principal du programme de quantification de la gravité par les mousses de spins, avec un accent particulier sur ses divergences. Outre une introduction personnelle au problème de la gravité quantique, le manuscrit se compose de deux parties. Dans la première, nous obtenons une formule exacte pour le comptage de puissances des divergences de bulles dans le modèle plat, notamment grâce à des outils de théorie de jauge discrète et de cohomologie tordue. Dans la seconde partie, nous considérons le problème de la limite continue des mousses de spins, tant du point de vue des théories de jauge sur réseau que du point de vue de la group field theory. Nous avançons en particulier une nouvelle preuve de la sommabilité de Borel du modèle de Boulatov-Freidel-Louapre, permettant un contrôle accru du comportement d’échelle dans la limite de grands spins. Nous concluons par une discussion prospective du programme de renormalisation pour les mousses de spins. / In this thesis we study the flat model, the main buidling block for the spinfoam ap- proach to quantum gravity, with an emphasis on its divergences. Besides a personal introduction to the problem of quantum gravity, the manuscript consists in two part. In the first one, we establish an exact powercounting formula for the bubble divergences of the flat model, using tools from discrete gauge theory and twisted cohomology. In the second one, we address the issue of spinfoam continuum limit, both from the lattice field theory and the group field theory perspectives. In particular, we put forward a new proof of the Borel summability of the Boulatov-Freidel-Louapre model, with an improved control over the large-spin scaling behaviour. We conclude with an outlook of the renormalization program in spinfoam quantum gravity.

Les travaux effectués durant cette thèse portent sur l’appariement de formes planes basé sur une squelettisation hiérarchique. Dans un premier temps, nous avons abordé la création d’un squelette de forme grâce à un algorithme associant des outils de la géométrie discrète et des filtres. Cette association permet d’acquérir un squelette regroupant les propriétés désirées dans le cadre de l’appariement. Néanmoins, le squelette obtenu reste une représentation de la forme ne différenciant pas les branches représentant l’allure générale de celles représentant un détail de la forme. Or, lors de l’appariement, il semble plus intéressant d’associer des branches ayant le même ordre d’importance, mais aussi de donner plus de poids aux associations décrivant un aspect global des formes. Notre deuxième contribution porte sur la résolution de ce problème. Elle concerne donc la hiérarchisation des branches du squelette, précédemment créé, en leur attribuant une pondération reflétant leur importance dans la forme. À cet effet, nous lissons progressivement une forme et étudions la persistance des branches pour leur attribuer un poids. L’ultime étape consiste donc à apparier les formes grâce à leur squelette hiérarchique modélisé par un hypergraphe. En d’autres termes, nous associons les branches deux à deux pour déterminer une mesure de dissimilarité entre deux formes. Pour ce faire, nous prenons en compte la géométrie des formes, la position relative des différentes parties des formes ainsi que de leur importance. / The works performed during this thesis focuses on the matching of planar shapes based on a hierarchical skeletonisation. First, we approached the creation of a shape skeleton using an algorithm combining the tools of discrete geometry and filters. This combination allows to acquire a skeleton gathering the desired properties in the context of matching. Nevertheless, the resulting skeleton remains a representation of the shape, which does not differentiate branches representing the general shape of those coming from a detail of the shape. But when matching, it seems more interesting to pair branches of the same order of importance, but also to give more weight to associations describing an overall appearance of shapes. Our second contribution focuses on solving this problem. It concerns the prioritization of skeletal branches, previously created by assigning a weight reflecting their importance in shape. To this end, we gradually smooth a shape and study the persistence of branches to assign a weight. The final step is to match the shapes with their hierarchical skeleton modeled as a hypergraph. In other words, we associate the branches two by two to determine a dissimilarity measure between two shapes. To do this, we take into account the geometry of the shapes, the relative position of different parts of the shapes and their importance.

L'étude non destructive du bois à partir de scanners à rayons X nécessite d’imaginer de nouvelles solutions adaptées à l'analyse des images. Préoccupation à la fois de la recherche agronomique et du milieu industriel des scieries, la segmentation des nœuds de bois est un défi majeur en termes de robustesse aux spécificités de chaque espèce et aux conditions d'acquisition des images. Les travaux menés dans cette thèse permettent de proposer un processus de segmentation en deux phases. Il isole d'abord chaque nœud dans une zone réduite puis segmente le nœud unique de chaque zone. Les solutions proposées pour chaque phase permettent d'intégrer les connaissances sur l'organisation interne du tronc et les mécanismes inhérents à sa croissance, à travers des outils classiques du traitement et de l'analyse d'image. La première phase repose en grande partie sur un principe de détection du mouvement emprunté à l'analyse vidéo et revisité. Deux approches de segmentation sont ensuite proposées, considérant pour l'une les coupes tomographiques initiales, et pour l'autre de nouvelles coupes ré-échantillonnées pour chaque nœud, orthogonalement à sa trajectoire. L'intégralité du processus a été implémenté dans un logiciel dédié aussi bien à l'expérimentation et la validation de l'approche qu'aux échanges interdisciplinaires. Le support applicatif du bois souligne la capacité de spécialisation des algorithmes génériques du traitement et de l'analyse d'image, et la pertinence de l'intégration de connaissances a priori dans cette optique / The non-destructive study of wood from X-Ray CT scanners requires to imagine new solutions adapted to analysis of images. Relating both agronomic research and industrial sector of sawmills, segmentation of wood knots is a major challenge in terms of robustness to specificities of each species and to image acquisition conditions. The works carried out in this thesis allow to propose a segmentation process in two phases. It first isolates each knot in a reduced area then it segments the unique knot of each area. Proposed solutions for each phase allow to integrate knowledges about internal organization of trunk and mechanisms inherent to its growth, through classical tools of image analysis and processing. The first phase is essentially based on a movement detection principle borrowed from video analysis and revisited. Two segmentation approaches are then proposed, considering for one the initial CT slices and for the other news slices resampled for each knot orthogonally to its trajectory. The complete process has been implemented in a software dedicated both for experimentation and validation of approach, and to interdisciplinary dialogs. The applicative support of wood emphasizes the specialization abilities of generic image analysis and processing algorithms, and the relevance to integrate priori knowledges in this perspective

La présence de spécularité sur un objet est un problème récurrent qui limite l'application de nombreuses méthodes de segmentation. En effet, les spécularités sont des zones ayant une intensité très élevée et perturbent énormément la détection dès lors que l'on utilise la notion de gradient de l'image. Les travaux menés dans cette thèse permettent de proposer une nouvelle méthode de détection d'un objet tubulaire métallique dans une image. La méthode s'affranchit de la notion de gradient en utilisant la notion de profil d'intensité. Nous proposons dans ce manuscrit, un processus qui parcourt des zones rectangulaires prédéfinies de l'image, par balayage d'un segment discret à la recherche d'un profil d'intensité référence. Ces travaux s'inscrivent dans une collaboration avec Numalliance, une entreprise qui fabrique des machines-outils. Cette collaboration permet de mettre en pratique cette méthode dans le cadre d'un système de contrôle qualité automatique et temps-réel des pièces manufacturées par les machines-outils. Pour cela, la méthode présentée doit être rapide, robuste aux spécularités et à l'environnement industriel tout en étant suffisamment précise pour permettre de conclure sur la conformité ou non de la pièce / The presence of specularity on an object is a recurring problem that limits the application of many segmentation methods. Indeed, specularities are areas with a very high intensity and greatly disturb the detection when the notion of gradient of the image is used. The work carried out in this thesis makes it possible to propose a new detection method for a metallic tubular object in an image. The method avoids the notion of gradient by using the notion of intensity profile. We propose in this manuscript a process which traverses predefined rectangular areas of the image by scanning a discrete segment in search of a reference intensity profile. This work is part of a collaboration with Numalliance, a company that manufactures machine tools. This collaboration enables this method to be put into a real industrial application as part of an automatic and real-time quality control system for parts manufactured by machine tools. To this end, the method presented must be fast, robust to the specularities and to the industrial environment while being sufficiently precise to make it possible to conclude on the conformity or not of the part

La cryptographie à base de réseaux euclidiens a généré un vif intérêt durant les deux dernièresdécennies grâce à des propriétés intéressantes, incluant une conjecture de résistance àl’ordinateur quantique, de fortes garanties de sécurité provenant d’hypothèses de difficulté sur lepire cas et la construction de schémas de chiffrement pleinement homomorphes. Cela dit, bienqu’elle soit cruciale à bon nombre de schémas à base de réseaux euclidiens, la génération debruit gaussien reste peu étudiée et continue de limiter l’efficacité de cette cryptographie nouvelle.Cette thèse s’attelle dans un premier temps à améliorer l’efficacité des générateurs de bruitgaussien pour les signatures hache-puis-signe à base de réseaux euclidiens. Nous proposons unnouvel algorithme non-centré, avec un compromis temps-mémoire flexible, aussi rapide que savariante centrée pour des tables pré-calculées de tailles acceptables en pratique. Nousemployons également la divergence de Rényi afin de réduire la précision nécessaire à la doubleprécision standard. Notre second propos tient à construire Falcon, un nouveau schéma designature hache-puis-signe, basé sur la méthode théorique de Gentry, Peikert et Vaikuntanathanpour les signatures à base de réseaux euclidiens. Nous instancions cette méthode sur les réseauxNTRU avec un nouvel algorithme de génération de trappes. / Lattice-based cryptography has generated considerable interest in the last two decades due toattractive features, including conjectured security against quantum attacks, strong securityguarantees from worst-case hardness assumptions and constructions of fully homomorphicencryption schemes. On the other hand, even though it is a crucial part of many lattice-basedschemes, Gaussian sampling is still lagging and continues to limit the effectiveness of this newcryptography. The first goal of this thesis is to improve the efficiency of Gaussian sampling forlattice-based hash-and-sign signature schemes. We propose a non-centered algorithm, with aflexible time-memory tradeoff, as fast as its centered variant for practicable size of precomputedtables. We also use the Rényi divergence to bound the precision requirement to the standarddouble precision. Our second objective is to construct Falcon, a new hash-and-sign signaturescheme, based on the theoretical framework of Gentry, Peikert and Vaikuntanathan for latticebasedsignatures. We instantiate that framework over NTRU lattices with a new trapdoor sampler.