Lorsque l'on affiche un objet 3D sur un écran d'ordinateur, on transforme cet objet en une image, c.a.d en un ensemble de pixels colorés. On appelle Rendu la discipline qui consiste à trouver la couleur à associer à ces pixels. Calculer la couleur d'un pixel revient à intégrer la quantité de lumière arrivant de toutes les directions que la surface renvoie dans la direction du plan image, le tout pondéré par une fonction binaire déterminant si un point est visible ou non. Malheureusement, l'ordinateur ne sait pas calculer des intégrales on a donc deux méthodes possibles : Trouver une expression analytique qui permet de supprimer l'intégrale de l'équation (approche basée statistique). Approximer numériquement l'équation en tirant des échantillons aléatoires dans le domaine d'intégration et en en déduisant la valeur de l'intégrale via des méthodes dites de Monte Carlo. Nous nous sommes ici intéressés à l'intégration numérique et à la théorie de l'échantillonnage. L'échantillonnage est au cœur des problématiques d'intégration numérique. En informatique graphique, il est capital qu'un échantillonneur génère des points uniformément dans le domaine d’échantillonnage pour garantir que l'intégration ne sera pas biaisée. Il faut également que le groupe de points généré ne présente aucune régularité structurelle visible, au risque de voir apparaître des artefacts dit d'aliassage dans l'image résultante. De plus, les groupes de points générés doivent minimiser la variance lors de l'intégration pour converger au plus vite vers le résultat. Il existe de nombreux types d'échantillonneurs que nous classeront ici grossièrement en 2 grandes familles : Les échantillonneurs bruit bleu, qui ont une faible la variance lors de l'intégration tout en générant de groupes de points non structurés. Le défaut de ces échantillonneurs est qu'ils sont extrêmement lents pour générer les points. Les échantillonneurs basse discrépance, qui minimisent la variance lors de l'intégration, génèrent des points extrêmement vite, mais qui présentent une forte structure, générant énormément d'aliassage. Notre travail a été de développer des échantillonneurs hybrides, combinant à la fois bruit bleu et basse discrépance / When you display a 3D object on a computer screen, we transform this 3D scene into a 2D image, which is a set of organized colored pixels. We call Rendering all the process that aims at finding the correct color to give those pixels. This is done by integrating all the light rays coming for every directions that the object's surface reflects back to the pixel, the whole being ponderated by a visibility function. Unfortunately, a computer can not compute an integrand. We therefore have two possibilities to solve this issue: We find an analytical expression to remove the integrand (statistic based strategy). Numerically approximate the equation by taking random samples in the integration domain and approximating the integrand value using Monte Carlo methods. Here we focused on numerical integration and sampling theory. Sampling is a fundamental part of numerical integration. A good sampler should generate points that cover the domain uniformly to prevent bias in the integration and, when used in Computer Graphics, the point set should not present any visible structure, otherwise this structure will appear as artifacts in the resulting image. Furthermore, a stochastic sampler should minimize the variance in integration to converge to a correct approximation using as few samples as possible. There exists many different samplers that we will regroup into two families: Blue Noise samplers, that have a low integration variance while generating unstructured point sets. The issue with those samplers is that they are often slow to generate a pointset. Low Discrepancy samplers, that minimize the variance in integration and are able to generate and enrich a point set very quickly. However, they present a lot of structural artifacts when used in Rendering. Our work aimed at developing hybriod samplers, that are both Blue Noise and Low Discrepancy

Cette recherche s'insère dans le contexte général de la calibration, en vue d'applications industrielles. Son objectif est d'évaluer la qualité d'une base de données, représentant la manière dont celle-ci occupe, au mieux des objectifs recherchés, son domaine de variation. Le travail réalisé ici fournit une synthèse des outils mathématiques et algorithmiques permettant de réaliser une telle opération. Nous proposons en outre des techniques de sélection ou d'importation de nouvelles observations permettant d'améliorer la qualité globale des bases de données. Les méthodes élaborées permettent entre autres d'identifier des défauts dans la structure des données. Leurs applications sont illustrées dans le cadre de l'évaluation de paramètres fonctionnels, dans un contexte d'estimation par fonctions orthogonales.

Cette thèse porte sur les irrégularités de distribution de suites à une ou plusieurs dimensions et sur leurs applications a l'intégration numérique. Elle comprend trois parties. La première partie est consacrée aux suites unidimensionnelles : estimations de la diaphonie de la suite de Van der Corput à partir de l'étude des sommes exponentielles et étude des suites (n). La deuxième partie porte sur quelques suites classiques en dimension plus grande que une (suites de Fame, suites de Halton). La troisième partie, consacrée aux applications à l'intégration contient de nombreux résultats numériques, permettant de comparer l'efficacité de suites.

Cette thèse porte sur l'analyse d'algorithmes stochastiques et leur application en Finance notamment et est composée de deux parties. Dans la première partie, nous présentons un résultat de convergence pour des algorithmes stochastiques où les innovations vérifient une hypothèse de moyennisation avec une certaine vitesse. Nous l'appliquons ensuite à différents types d'innovations (suites i.i.d., suites à discrépance faible, chaînes de Markov homogènes, fonctionnelles de processus \alpha-mélangeant) et nous l'illustrons à l'aide d'exemples motivés principalement par la Finance. Nous établissons ensuite un résultat de vitesse ''universelle'' de convergence dans le cadre d'innovations équiréparties dans [0,1]^q et nous confrontons nos résultats à ceux obtenus dans le cadre i.i.d.. La seconde partie est consacrée aux applications. Nous présentons d'abord un problème d'allocation optimale appliqué au cas d'un nouveau type de place de trading: les {\em dark pools}. Ces places proposent un prix d'achat (ou de vente) certain, mais n'assurent pas le volume délivré. Le but est alors d'exécuter le maximum de la quantité souhaitée sur ces places. Ceci mène à la construction d'un algorithme stochastique sous contraintes à l'aide du Lagrangien que nous étudions dans les cadres d'innovations i.i.d. et moyennisantes. Le chapitre suivant présente un algorithme d'optimisation pour trouver la meilleure distance de placement d'ordres limites: il s'agit de minimiser le coût d'exécution d'une quantité donnée. Ceci mène à la construction d'un algorithme stochastique sous contraintes avec projection. Pour assurer l'existence et l'unicité de l'équilibre, des critères suffisants sur certains paramètres du modèle sont obtenus à l'aide d'un principe de monotonie opposée pour les diffusions unidimensionnelles. Le chapitre suivant porte sur l'implicitation et la calibration de paramètres dans des modèles financiers. La première technique mène à un algorithme de recherche de zéro et la seconde à une méthode de gradient stochastique. Nous illustrons ces deux techniques par des exemples d'applications sur 3 modèles: le modèle de Black-Scholes, le modèle de Merton et le modèle pseudo-CEV. Enfin le dernier chapitre porte sur l'application des algorithmes stochastiques dans le cadre de modèles d'urnes aléatoires utilisés en essais cliniques. A l'aide des méthodes de l'EDO et de l'EDS, nous retrouvons les résultats de consistance (convergence p.s.) et de normalité asymptotique (TCL) de Bai et Hu mais sous des hypothèses plus faibles sur les matrices génératrices. Nous étudions aussi un modèle ''multi-bras'' pour lequel nous retrouvons le résultat de convergence p.s. et nous montrons un nouveau résultat de normalité asymptotique par simple application du TCL pour les algorithmes stochastiques.

De nombreuses sources de variabilité impactent la fabrication des circuits intégrés analogiques et RF et peuvent conduire à une dégradation du rendement. Il est donc nécessaire de mesurer leur influence le plus tôt possible dans le processus de fabrications. Les méthodes de simulation statistiques permettent ainsi d'estimer le rendement paramétrique des circuits durant la phase de conception. Cependant, les méthodes traditionnelles telles que la méthode de Monte Carlo ne sont pas assez précises lorsqu'un faible nombre de circuits est simulé. Par conséquent, il est nécessaire de créer un estimateur précis du rendement paramétrique basé sur un faible nombre de simulations. Dans cette thèse, les méthodes statistiques existantes provenant à la fois de publications en électroniques et non-Électroniques sont d'abord décrites et leurs limites sont mises en avant. Ensuite, trois nouveaux estimateurs de rendement sont proposés: une méthode de type quasi-Monte Carlo avec tri automatique des dimensions, une méthode des variables de contrôle basée sur l'estimation par noyau, et une méthode par tirage d'importance. Les trois méthodes reposent sur un modèle mathématique de la métrique de performance du circuit qui est construit à partir d'un développement de Taylor à l'ordre un. Les résultats théoriques et expérimentaux obtenus démontrent la supériorité des méthodes proposées par rapport aux méthodes existantes, à la fois en terme de précision de l'estimateur et en terme de réduction du nombre de simulations de circuits. / Semiconductor device fabrication is a complex process which is subject to various sources of variability. These variations can impact the functionality and performance of analog integrated circuits, which leads to yield loss, potential chip modifications, delayed time to market and reduced profit. Statistical circuit simulation methods enable to estimate the parametric yield of the circuit early in the design stage so that corrections can be done before manufacturing. However, traditional methods such as Monte Carlo method and corner simulation have limitations. Therefore an accurate analog yield estimate based on a small number of circuit simulations is needed. In this thesis, existing statistical methods from electronics and non-Electronics publications are first described. However, these methods suffer from sever drawbacks such as the need of initial time-Consuming circuit simulations, or a poor scaling with the number of random variables. Second, three novel statistical methods are proposed to accurately estimate the parametric yield of analog/RF integrated circuits based on a moderate number of circuit simulations: An automatically sorted quasi-Monte Carlo method, a kernel-Based control variates method and an importance sampling method. The three methods rely on a mathematical model of the circuit performance metric which is constructed based on a truncated first-Order Taylor expansion. This modeling technique is selected as it requires a minimal number of SPICE-Like circuit simulations. Both theoretical and simulation results show that the proposed methods lead to significant speedup or improvement in accuracy compared to other existing methods.

La simulation numérique est devenue une alternative à l’expérimentation réelle pour étudier des phénomènes physiques. Cependant, les phénomènes complexes requièrent en général un nombre important de simulations, chaque simulation étant très coûteuse en temps de calcul. Une approche basée sur la théorie des plans d’expériences est souvent utilisée en vue de réduire ce coût de calcul. Elle consiste à partir d’un nombre réduit de simulations, organisées selon un plan d’expériences numériques, à construire un modèle d’approximation souvent appelé métamodèle, alors beaucoup plus rapide à évaluer que le code lui-même. Traditionnellement, les plans utilisés sont des plans de type Space-Filling Design (SFD). La première partie de la thèse concerne la construction de plans d’expériences SFD à taille fixe adaptés à l’identification d’un modèle de krigeage car le krigeage est un des métamodèles les plus populaires. Nous étudions l’impact de la contrainte Hypercube Latin (qui est le type de plans les plus utilisés en pratique avec le modèle de krigeage) sur des plans maximin-optimaux. Nous montrons que cette contrainte largement utilisée en pratique est bénéfique quand le nombre de points est peu élevé car elle atténue les défauts de la configuration maximin-optimal (majorité des points du plan aux bords du domaine). Un critère d’uniformité appelé discrépance radiale est proposé dans le but d’étudier l’uniformité des points selon leur position par rapport aux bords du domaine. Ensuite, nous introduisons un proxy pour le plan minimax-optimal qui est le plan le plus proche du plan IMSE (plan adapté à la prédiction par krigeage) et qui est coûteux en temps de calcul, ce proxy est basé sur les plans maximin-optimaux. Enfin, nous présentons une procédure bien réglée de l’optimisation par recuit simulé pour trouver les plans maximin-optimaux. Il s’agit ici de réduire au plus la probabilité de tomber dans un optimum local. La deuxième partie de la thèse porte sur un problème légèrement différent. Si un plan est construit de sorte à être SFD pour N points, il n’y a aucune garantie qu’un sous-plan à n points (n 6 N) soit SFD. Or en pratique le plan peut être arrêté avant sa réalisation complète. La deuxième partie est donc dédiée au développement de méthodes de planification séquentielle pour bâtir un ensemble d’expériences de type SFD pour tout n compris entre 1 et N qui soient toutes adaptées à la prédiction par krigeage. Nous proposons une méthode pour générer des plans séquentiellement ou encore emboités (l’un est inclus dans l’autre) basée sur des critères d’information, notamment le critère d’Information Mutuelle qui mesure la réduction de l’incertitude de la prédiction en tout point du domaine entre avant et après l’observation de la réponse aux points du plan. Cette approche assure la qualité des plans obtenus pour toutes les valeurs de n, 1 6 n 6 N. La difficulté est le calcul du critère et notamment la génération de plans en grande dimension. Pour pallier ce problème une solution a été présentée. Cette solution propose une implémentation astucieuse de la méthode basée sur le découpage par blocs des matrices de covariances ce qui la rend numériquement efficace. / In recent years, computer simulation models are increasingly used to study complex phenomena. Such problems usually rely on very large sophisticated simulation codes that are very expensive in computing time. The exploitation of these codes becomes a problem, especially when the objective requires a significant number of evaluations of the code. In practice, the code is replaced by global approximation models, often called metamodels, most commonly a Gaussian Process (kriging) adjusted to a design of experiments, i.e. on observations of the model output obtained on a small number of simulations. Space-Filling-Designs which have the design points evenly spread over the entire feasible input region, are the most used designs. This thesis consists of two parts. The main focus of both parts is on construction of designs of experiments that are adapted to kriging, which is one of the most popular metamodels. Part I considers the construction of space-fillingdesigns of fixed size which are adapted to kriging prediction. This part was started by studying the effect of Latin Hypercube constraint (the most used design in practice with the kriging) on maximin-optimal designs. This study shows that when the design has a small number of points, the addition of the Latin Hypercube constraint will be useful because it mitigates the drawbacks of maximin-optimal configurations (the position of the majority of points at the boundary of the input space). Following this study, an uniformity criterion called Radial discrepancy has been proposed in order to measure the uniformity of the points of the design according to their distance to the boundary of the input space. Then we show that the minimax-optimal design is the closest design to IMSE design (design which is adapted to prediction by kriging) but is also very difficult to evaluate. We then introduce a proxy for the minimax-optimal design based on the maximin-optimal design. Finally, we present an optimised implementation of the simulated annealing algorithm in order to find maximin-optimal designs. Our aim here is to minimize the probability of falling in a local minimum configuration of the simulated annealing. The second part of the thesis concerns a slightly different problem. If XN is space-filling-design of N points, there is no guarantee that any n points of XN (1 6 n 6 N) constitute a space-filling-design. In practice, however, we may have to stop the simulations before the full realization of design. The aim of this part is therefore to propose a new methodology to construct sequential of space-filling-designs (nested designs) of experiments Xn for any n between 1 and N that are all adapted to kriging prediction. We introduce a method to generate nested designs based on information criteria, particularly the Mutual Information criterion. This method ensures a good quality forall the designs generated, 1 6 n 6 N. A key difficulty of this method is that the time needed to generate a MI-sequential design in the highdimension case is very larg. To address this issue a particular implementation, which calculates the determinant of a given matrix by partitioning it into blocks. This implementation allows a significant reduction of the computational cost of MI-sequential designs, has been proposed.

L'apprentissage statistique cherche à modéliser un lien fonctionnel entre deux variables X et Y à partir d'un échantillon aléatoire de réalisations de (X,Y ). Lorsque la variable Y prend un nombre binaire de valeurs, l'apprentissage s'appelle la classification (ou discrimination en français) et apprendre le lien fonctionnel s'apparente à apprendre la frontière d'une variété dans l'espace de la variable X. Dans cette thèse, nous nous plaçons dans le contexte de l'apprentissage actif, i.e. nous supposons que l'échantillon d'apprentissage n'est plus aléatoire et que nous pouvons, par l'intermédiaire d'un oracle, générer les points sur lesquels l'apprentissage de la variété va s'effectuer. Dans le cas où la variable Y est continue (régression), des travaux précédents montrent que le critère de la faible discrépance pour générer les premiers points d'apprentissage est adéquat. Nous montrons, de manière surprenante, que ces résultats ne peuvent pas être transférés à la classification. Dans ce manuscrit, nous proposons alors le critère de la dispersion pour la classification. Ce critère étant difficile à mettre en pratique, nous proposons un nouvel algorithme pour générer un plan d'expérience à faible dispersion dans le carré unité. Après une première approximation de la variété, des approximations successives peuvent être réalisées afin d'affiner la connaissance de celle-ci. Deux méthodes d'échantillonnage sont alors envisageables : le " selective sampling " qui choisit les points à présenter à un oracle parmi un ensemble fini de candidats et l'" adaptative sampling " qui permet de choisir n'importe quels points de l'espace de la variable X. Le deuxième échantillonnage peut être vu comme un passage à la limite du premier. Néanmoins, en pratique, il n'est pas raisonnable d'utiliser cette méthode. Nous proposons alors un nouvel algorithme basé sur le critère de dispersion, menant de front exploitation et exploration, pour approximer une variété.

L’apprentissage statistique cherche à modéliser un lien fonctionnel entre deux variables X et Y à partir d’un échantillon aléatoire de réalisations de (X,Y ). Lorsque la variable Y prend un nombre binaire de valeurs, l’apprentissage s’appelle la classification (ou discrimination en français) et apprendre le lien fonctionnel s’apparente à apprendre la frontière d’une variété dans l’espace de la variable X. Dans cette thèse, nous nous plaçons dans le contexte de l’apprentissage actif, i.e. nous supposons que l’échantillon d’apprentissage n’est plus aléatoire et que nous pouvons, par l’intermédiaire d’un oracle, générer les points sur lesquels l’apprentissage de la variété va s’effectuer. Dans le cas où la variable Y est continue (régression), des travaux précédents montrent que le critère de la faible discrépance pour générer les premiers points d’apprentissage est adéquat. Nous montrons, de manière surprenante, que ces résultats ne peuvent pas être transférés à la classification. Dans ce manuscrit, nous proposons alors le critère de la dispersion pour la classification. Ce critère étant difficile à mettre en pratique, nous proposons un nouvel algorithme pour générer un plan d’expérience à faible dispersion dans le carré unité. Après une première approximation de la variété, des approximations successives peuvent être réalisées afin d’affiner la connaissance de celle-ci. Deux méthodes d’échantillonnage sont alors envisageables : le « selective sampling » qui choisit les points à présenter à un oracle parmi un ensemble fini de candidats et l’« adaptative sampling » qui permet de choisir n’importe quels points de l’espace de la variable X. Le deuxième échantillonnage peut être vu comme un passage à la limite du premier. Néanmoins, en pratique, il n’est pas raisonnable d’utiliser cette méthode. Nous proposons alors un nouvel algorithme basé sur le critère de dispersion, menant de front exploitation et exploration, pour approximer une variété. / Statistical learning aims to modelize a functional link between two variables X and Y thanks to a random sample of realizations of the couple (X,Y ). When the variable Y takes a binary number of values, learning is named classification and learn the functional link is equivalent to learn the boundary of a manifold in the feature space of the variable X. In this PhD thesis, we are placed in the context of active learning, i.e. we suppose that learning sample is not random and that we can, thanks to an oracle, generate points for learning the manifold. In the case where the variable Y is continue (regression), previous works show that criterion of low discrepacy to generate learning points is adequat. We show that, surprisingly, this result cannot be transfered to classification talks. In this PhD thesis, we propose the criterion of dispersion for classification problems. This criterion being difficult to realize, we propose a new algorithm to generate low dispersion samples in the unit cube. After a first approximation of the manifold, successive approximations can be realized in order to refine its knowledge. Two methods of sampling are possible : the « selective sampling » which selects points to present to the oracle in a finite set of candidate points, and the « adaptative sampling » which allows to select any point in the feature space of the variable X. The second sampling can be viewed as the infinite limit of the first. Nevertheless, in practice, it is not reasonable to use this method. Then, we propose a new algorithm, based on dispersion criterion, leading both exploration and exploitation to approximate a manifold.

L’aléatoire est un ingrédient clé en cryptographie. Par exemple, les nombres aléatoires sont utilisés pour générer des clés, pour le chiffrement et pour produire des nonces. Ces nombres sont générés par des générateurs pseudo-aléatoires et des fonctions pseudo-aléatoires dont les constructions sont basées sur des problèmes qui sont supposés difficiles. Dans cette thèse, nous étudions certaines mesures de complexité des fonctions pseudo-aléatoires de Naor-Reingold et Dodis-Yampolskiy et étudions la sécurité de certains générateurs pseudo-aléatoires (le générateur linéaire congruentiel et le générateur puissance basés sur les courbes elliptiques) et de certaines signatures à base de couplage basées sur le paradigme d’inversion. Nous montrons que la fonction pseudo-aléatoire de Dodis-Yampolskiy est uniformément distribué et qu’un polynôme multivarié de petit dégré ou de petit poids ne peut pas interpoler les fonctions pseudo-aléatoires de Naor-Reingold et de Dodis-Yampolskiy définies sur un corps fini ou une courbe elliptique. Le contraire serait désastreux car un tel polynôme casserait la sécurité de ces fonctions et des problèmes sur lesquels elles sont basées. Nous montrons aussi que le générateur linéaire congruentiel et le générateur puissance basés sur les courbes elliptiques sont prédictibles si trop de bits sont sortis à chaque itération. Les implémentations pratiques de cryptosystèmes souffrent souvent de fuites critiques d’informations à travers des attaques par canaux cachés. Ceci peut être le cas lors du calcul de l’exponentiation afin de calculer la sortie de la fonction pseudo-aléatoire de Dodis-Yampolskiy et plus généralement le calcul des signatures dans certains schémas de signatures bien connus à base de couplage (signatures de Sakai-Kasahara, Boneh-Boyen et Gentry) basées sur le paradigme d’inversion. Nous présentons des algorithmes (heuristiques) en temps polynomial à base des réseaux qui retrouvent le secret de celui qui signe le message dans ces trois schémas de signatures lorsque plusieurs messages sont signés sous l’hypothèse que des blocs consécutifs de bits des exposants sont connus de l’adversaire. / Randomness is a key ingredient in cryptography. For instance, random numbers are used to generate keys, for encryption and to produce nonces. They are generated by pseudo-random generators and pseudorandom functions whose constructions are based on problems which are assumed to be difficult. In this thesis, we study some complexity measures of the Naor-Reingold and Dodis-Yampolskiy pseudorandom functions and study the security of some pseudo-random generators (the linear congruential generator and the power generator on elliptic curves) and some pairing-based signatures based on exponentinversion framework. We show that the Dodis-Yampolskiy pseudo-random functions is uniformly distributed and that a lowdegree or low-weight multivariate polynomial cannot interpolate the Naor-Reingold and Dodis-Yampolskiy pseudo-random functions over finite fields and over elliptic curves. The contrary would be disastrous since it would break the security of these functions and of problems on which they are based. We also show that the linear congruential generator and the power generator on elliptic curves are insecure if too many bits are output at each iteration. Practical implementations of cryptosystems often suffer from critical information leakage through sidechannels. This can be the case when computing the exponentiation in order to compute the output of the Dodis-Yampolskiy pseudo-random function and more generally in well-known pairing-based signatures (Sakai-Kasahara signatures, Boneh-Boyen signatures and Gentry signatures) based on the exponent-inversion framework. We present lattice based polynomial-time (heuristic) algorithms that recover the signer’s secret in the pairing-based signatures when used to sign several messages under the assumption that blocks of consecutive bits of the exponents are known by the attacker.

Cette thèse contient quatre contributions indépendantes a la mécanique aléatoire: 1) une contribution aux suites à discrépance faible afin d'accélérer la convergence des algorithmes de type Monte-Carlo ; 2) l'homogénéisation des matériaux élastiques à microstructure aléatoire : on définit rigoureusement les tenseurs élastiques macroscopiques, on donne une méthode de simulation pour les calculer, enfin cette méthode est mise en oeuvre sur un matériau fictif ; 3) la fatigue à grand nombre de cycles des métaux polycristallins : on établit un nouveau critère d'endurance pour tous les chargements périodiques ; ce critère est susceptible de modéliser l'aspect aléatoire de la rupture ; 4) l'analyse de la simulation en calcul a 1 rupture probabiliste des structures discrètes : on montre notamment que l'approche par les vitesses est adaptée quand on a à effectuer une simulation et que l'algorithme du simplexe peut être utilisé.