Дисертації з теми "Logique aléatoire"

La théorie de l'aléa effective étudie l'absence de structure qui caractérise l'aléa. La complexité de Kolmogorov est un outil fondamental de cette théorie et nous étudions les propriétés caractéristiques de cette fonctions. Dans un second temps noùs nous intéressons à la possibilité d'étendre l'étude de l'aléa aux suites de bits biaisés en nous demandant si la connaissance précise du biais ou non modifie la qualité de l'aléa que nous décrivons. Nous nous intéressons ensuite à la puissance logique de l'aléa: que peut on déduire du fait (non prouvable) qu'une suite est dénué de structure ? Enfin on s'intéresse a la possibilité de calculer une complétion de l'arithmétique à partir d'un algorithme utilisant de l'aléa
Theory of algorithmic randomness theory studies the Jack of structure that characterizes random objects Kolmogorov complexity is a fimdamental tool of this theory and we study the characteristic properties of this fonction. In a second step we investigate the possibility of extending the study of the biased random bit sequences wondering if precise knowledge of using or not changes the quality of randomness we describe, We then focus on the logic power of the random object: What can be inferred from the fact (non provable) that a sequence has no structure? Finally we look a the possibility of calculating a completion of arithmetic from an randomized algorithm

Par l’intermédiaire d’Esther Duflo et de son laboratoire le J-PAL, les expérimentations aléatoires ont connu un essor remarquable depuis les années 2000 en économie et sont présentées par leurs promoteurs comme une méthode particulièrement robuste dans l’évaluation d’impact. Combinant méthodologies quantitatives et qualitatives, cette thèse examine la construction sociale de la preuve expérimentale et apporte une contribution à une épistémologie sociale et historique des expérimentations aléatoires, ainsi qu’à la socio-économie de la quantification. Dans une première partie, nous développons une socio-histoire de cette méthode. Les origines des expérimentations aléatoires sont pluridisciplinaires et antérieures à leur utilisation massive en médecine depuis les années 1940, puis en économie depuis la fin des années 1960. Nous en tirons des enseignements méthodologiques éclairant la pratique actuelle des expérimentations aléatoires. Dans un second temps, nous nous intéressons aux acteurs de cette méthode, en nous penchant sur les chercheurs du J-PAL. En procédant à une analyse prosopographique, complétée par une analyse de réseau, nous montrons que les capitaux académiques élevés de ces chercheurs et l’existence de leaders permettent de contrôler et promouvoir la diffusion de la méthode. Dans une dernière partie, nous interrogeons la production de la preuve par les expérimentations aléatoires. En nous attachant à saisir les pratiques expérimentales, nous montrons que les validités interne et externe sont souvent problématiques. Enfin, nous analysons les liens contrariés entre expérimentations aléatoires et politique(s)
With Esther Duflo and her lab (the J-PAL), randomized controlled trials (RCTs) became trendy from the the 2000’s onward in economics and are presented by their advocates as the most robust method for impact evaluation. Relying on mixed methods, this thesis investigates the social construction of experimental evidence and contributes to a social and historical epistemology of RCTs and to the socio-economy of quantification.The first part develops a socio-history of this method. The origins of RCTs are multidisciplinary and precede their extensive use in medicine from the 1940s and in economics from the 1960s onward. This allows us to gain a deeper undestanding of the current use of RCTs.In the second part, we examine the stakeholders of this method, chiefly J-PAL researchers. Our prosopographical analysis, supplemented by a network analysis, demonstrates that their high level of academic capital and the presence of leaders allow for the control and the diffusion of RCTs.In the last part, we scrutinize the production of experimental evidence. By examining RCTs in operation, we show that both their internal and external validity are in many cases compromized. Finally, we explore the convoluted links between RCTs, policy and politics

La prise en compte d'événements en temps réel dans le raisonnement d'un système expert en ligne peut être résolue en utilisant un système PROLOG modifié travaillant sur une base de faits temps réel. On ajoute deux mécanismes essentiels au système déductif : d'une part, le backtracking dirigé par les événements qui est chargé de corriger les preuves, quand des événements se produisent et d'autre part, la gestion en parallèle des preuves logiquement indépendantes entre elles qui structure les raisonnements et optimise la correction des preuves. La cohérence logique entre les preuves et la base de faits s'appuie sur la représentation des connaissances de l'application.

Cette thèse se concentre sur l'apport du calcul en temps infini à la logique mathématique. Le calcul en temps infini est une variante de la traditionnelle définition du calcul comme suite finie d'étapes, chaque étape étant définie à partir des précédentes, et aboutissant à un état final. Dans le cas de cette thèse, nous considérons le cas où le nombre d'étapes n'est pas forcément fini, mais peut continuer le long des ordinaux, une extension des entiers. Il existe plusieurs manières d'implémenter cette idée, nous en utilisons trois : la calculabilité d'ordre supérieur, les machines de Turing à temps infini et l'α-récursion.Une part de ce travail concerne les mathématiques à rebours, et plus particulièrement le théorème de Hindman. Les mathématiques à rebours sont un programme mathématique consistant en l'étude des théorèmes et axiomes mathématiques du point de vue de leur "puissance", et établissant une hiérarchie sur celle-ci. En particulier la détermination des briques de bases, aussi appelées axiomes, qui sont nécessaires dans une preuve est centrale. Nous étudions au travers de ce prisme le théorème de Hindman, un théorème combinatoire de la théorie de Ramsey qui dit que pour tout partitionnement des entiers en un nombre fini d'ensembles, appelés couleurs, il doit exister une ensemble infini S d'entiers dont toute les sommes d'éléments issus de S ont la même couleur. Dans cette thèse, nous progressons dans la résolution de la question du système d'axiomes minimal pour prouver ce théorème, en montrant que l'existence d'objets combinatoires intermédiaires est prouvable dans un système d'axiome faible.La réduction de Weihrauch est une méthode récente de comparaison de puissance de théorème, qui les considère comme des problèmes à résoudre, puis compare leur difficulté. Cette réduction a été moins étudiée, et en particulier certains des principes les plus importants des mathématiques à rebours ne sont pas bien compris dans ce cadre. L'un d'eux est le principe ATR de Récursion Arithmétique Transfinie, un principe très lié au calcul en temps infini et plus particulièrement à la calculabilité d'ordre supérieur. Nous continuons l'étude de ce principe en montrant ses liens avec un type particulier d'axiome du choix, et l'utilisons pour séparer les versions dépendantes et indépendantes de ces axiomes.Un autre domaine de la logique mathématiques qui tire parti de la théorie de la calculabilité est l'aléatoire algorithmique. Ce domaine étudie les réels "aléatoires", c'est à dire ceux dont il paraît raisonnable qu'ils aient été obtenus de façon purement aléatoire. Une manière d'étudier cela est de considérer, étant donné un réel, la plus petite complexité algorithmique d'un ensemble de mesure 0 le contenant. Ce domaine est très riche et a déjà été étendu à certains types de calcul en temps infini, modifiant ainsi les classes de complexité considérées. Cependant, il a seulement très récemment été étendu aux machines de Turing à temps infini (ITTMs) et à l'α-récursion. Dans cette thèse, nous contribuons à l'étude des notions d'aléatoire pour ITTMs et α-récursion les plus naturelles. Nous montrons que deux classes importantes, le Σ-aléatoire et l'ITTM-aléatoire, ne sont pas automatiquement distinctes ; en particulier leurs équivalents catégoriques sont confondus
This thesis focuses on the gains of infinite time computations to mathematical logic. Infinite time computations is a variant of the traditional definition of computations as a finite sequence of stages, each stage being defined from the previous ones, and finally reaching a halting state. In this thesis, we consider the case where the number of stages is not necessarily finite, but can continue along ordinals, an extension of the integers. There exists several ways to implement this idea, we will use three of them: higher recursion, infinite time Turing machines and α-recursion.Part of this works concerns the domain of reverse mathematics, and especially Hindman's theorem. Reverse mathematics is a program consisting in the study of theorems and axioms from the point of view of their "strength", and establishing a hierarchy on these. In particular the question of which axioms are needed in a proof of a given statement is central. We study Hindman's theorem under this lens, a combinatorial result from Ramsey's theory stating that for every partitioning of the integers into finitely many colors, there must exists an infinite set such that any sum of elements taken from it has a fixed color. In this thesis, we make some progress in the question of the minimal axiomatic system needed to show this result, by showing that the existence of some intermediate combinatorial objects is provable in a weak system.Weihrauch reduction is a way to compare the strength of theorems, that has been introduced in reverse mathematics recently. It sees theorems as problems to solve, and then compare their difficulties. This reduction is still less studied in this context, in particular few of the most important principles of reverse mathematics are not yet well comprehended. One of these is the Arithmetical Transfinite Recursion principle, an axiomatic system with strong links with infinite time computations and especially higher recursion. We continue the study of this principle by showing its links with a particular type of axiom of choice, and use it to separate the dependent and independent version of this choice.Yet another field of mathematical logic that benefits from computability theory is the one of algorithmic randomness. It studies "random" reals, those that it would seem reasonable to think that they arise from a process picking a real uniformly in some interval. A way to study this is to considerate, for a given real, the smallest algorithmic complexity of a null set containing it. This domain has proven very rich and has already been extended to certain type of infinite time computation, thereby modifying the complexity class considered. However, it has been extended to infinite time Turing machine and α-recursion only recently, by Carl and Schlicht. In this thesis, we contribute to the study of the most natural randomness classes for ITTMs and α-recursion. We show that two important classes, Σ-randomness and ITTM-randomness, are not automatically different; in particular their categorical equivalent are in fact the same classes

Cette thèse propose l'étude des propriétés locales satisfaites par le modèle d'Ising défini sur un graphe torique d-dimensionnel. Lorsque la taille n du graphe tend vers l'infini, une limite pour leur probabilité d'apparition est obtenue en fonction des potentiels de surface a=a(n) et de paire b=b(n). En mettant en évidence un phénomème de seuil, nous déterminons le moment d'apparition dans le graphe d'une propriété locale donnée. Puis, en se plaçant à sa fonction seuil, nous démontrons une approximation poissonnienne pour sa probabilité d'apparition. Enfin, deux applications sont proposées : une estimation des potentiels a et b ainsi qu'un algorithme de débruitage d'images en niveaux de gris.

A travers ma thèse, j'étudie des systèmes propositionnels d'un point de vue probabilité/complexité. Je commence par deux distributions de probabilité sur les fonctions Booléennes, induites par des expressions Booléennes construites avec le connecteur Implication. On donne la structure de la plupart des expressions représentant une fonction donnée, quand le nombre de variables tend vers l'infini. On obtient ainsi l'équivalent asymptotique de la probabilité de la fonction, dépendant de sa complexité. Via la fonction Vrai, on compare quantitativement les logiques classique et intuitionniste de l'implication. Cette comparaison met en évidence certaines propriétés d'une classe d'expressions, qui se retrouvent dans le système propositionnel complet : on compare alors les deux logiques dans ce système. Enfin on étudie les expressions équilibrées des deux systèmes, de l'implication et des deux connecteurs Et et Ou. Dans les deux cas, on exhibe la distribution de probabilité sur les fonctions
In this thesis, I am interested in propositional systems from a probability/complexity point of view. I begin with two probability distributions on Boolean functions, induced by the Boolean expressions built with the Implication connective. I obtain the structure of most of the expressions representing a given function, when the number of variables tends to infinity. This gives the asymptotic equivalent of the probability of the function, depending on its complexity. Via the function True, we compare quantitatively the intuitionistic and classical logics of implication. This comparison highlights some properties of a class of expressions, that are found also in the full propositional system, and we can compare the two logics in this system. Finally we study balanced expressions in the two systems built on implication, or on the two connectors And and Or. In both cases, we exhibit the probability distribution of the functions

Les générateurs de nombres aléatoires sont des blocs destinés à produire des quantités numériques qui doivent être indépendantes et uniformément distribuées. Ces RNG sont utilisés dans des contextes sécuritaires où l'utilisation de nombres aléatoires est requise (génération de clefs cryptographiques, nonces des protocoles cryptographiques, marqueurs anti-rejeu, contre-mesures face aux attaques par canaux cachés) et où leur qualité est primordiale. Tous les composants électroniques ayant une fonction sécuritaire, comme par exemple les cartes à puces, incluent un ou plusieurs générateurs aléatoires (basés sur des principes physiques). En conséquence, le RNG est une brique centrale des applications sécuritaires et sa défaillance, totale ou partielle met donc en péril la fonctionnalité dans son ensemble. Ce travail de thèse porte sur l'étude des RNG physiques (PTRNG) et la modélisation de l'aléa à partir des caractérisations électroniques et mathématiques du circuit. Cette étude se place essentiellement dans le contexte de la norme AIS 31 du BSI* qui fait référence dans de nombreux pays européens. Cette norme est l‘une des rares qui impose des caractérisations sur les PTRNG, incluant notamment un modèle stochastique de ce dernier. Dans ce contexte, il est crucial de pouvoir valider la méthodologie d'évaluation proposée par ces normes et c'est sur ce point que j'ai focalisé mon travail de thèse.*Bundesamt für Sicherheit in der Informationstechnik, agence fédérale allemande chargée de la sécurité des technologies de l'information
Random number generators (RNG) are primitives that produce independent and uniformly distributed digital values, RNG are used in secure environments where the use of random numbers is required (generation of cryptographic keys, nonces in cryptographic protocols, padding values, countermeasures against side-channel attacks) and where the quality of the randomness is essential. All electronic components with a security function, such as smart cards, include one or more random generators (based on physical principles). Consequently, the RNG is an essential primitive for security applications. A flaw in security of the random number generation process directly impacts the security of the cryptographic system. This thesis focuses on the study of physical RNG (PTRNG), the modeling of its randomness and an electronic characterizations of the circuit. This study is in the context of the AIS-31 standard which is published by the BSI* and followed by many European countries. This standard is one of the few that require a characterizations of the PTRNG and a stochastic model. In this context, it is crucial to validate the evaluation methodology proposed by these standards and l focused on them during my thesis.*Bundesamt fiir Sicherheit in der Informationstechnik, federal agency German responsible for the security of information technology

Depuis leur introduction en 2006, les systèmes de spins artificiels ont suscité un large intérêt autant pour leur similarité avec des systèmes frustrés tels que la glace d'eau ou certains pyrochlores. Ces réseaux de nano-aimants sont observables par des techniques de microscopie simples et modifiables à volonté. Dans ce travail, nous avons étudié des modifications de géométries classiques pour l’étude de l’évolution des interactions et pour l’élaboration d’un dispositif. Dans un premier temps, nous avons étudié la modification des interactions par la rotation des éléments d’un système carré. Pour un système dans l’état brut de croissance, l’état de fondamental évolue d’ordre antiferromagnétique à ferromagnétique suivant les prédictions de calculs dipolaires. En considérant les interactions longue portée dans nos simulations Monte Carlo, nous avons décrit l’énergie dipolaire totale ainsi que les populations de vertex de notre système. Cette description a mené à une étude de la thermodynamique du système et la détermination d’une température effective unique. Ensuite, nous nous sommes intéressés à la possibilité de « tailler sur mesure » ces systèmes de spins artificiels pour des applications de calcul. Nous avons commencé par montrer que ces systèmes sont plus adaptés en exploitant de la propagation de paroi plutôt que le couplage. Nous avons ensuite établi que le défi dans de grandes structures connectées est le compromis entre champ de nucléation et champ de piégeage du haut de la structure. Par une optimisation fine de sa forme, nous avons observé la propagation d’une paroi injectée à un endroit choisi. Cette propagation a été caractérisée en termes de champs de propagation, de types de renversements et a montré que notre système optimisé permet des propagations en majorité unidimensionnelles qui sont stochastiques. Ce comportement aléatoire a pu être décrit par un poids moyen décrivant l’ensemble des choix réalisés, ces derniers ne présentant aucune corrélation entre eux. Notre étude a démontré que les systèmes de spins peuvent être utilisés pour de la génération de nombres aléatoires au même titre qu’une planche de Galton. Cette thèse a donc montré la versatilité des systèmes de spins artificiels en qualité de glace de spin pour la compréhension de la modification des interactions dans leur thermodynamique. Ce travail a aussi démontré leur versatilité pour des applications de génération de nombres aléatoires grâce à une optimisation de leur géométrie
Since their introduction in 2006, artificial spin ice systems have sparked an interest for their similarity with frustrated systems such as water ice or some pyrochlores. These networks of interacting nanomagnets can be observed using simple microscopy techniques and be tailored at will. In this work, we have studied customised geometries in order to observe the evolution of dipolar interactions and develop a device. First, we have studied the tuning of the dipolar interactions induced by rotation of the elements of the square geometry. For an as-grown system that the ground state evolution from antiferromagnetic to ferromagnetic orders observed is consistent with dipolar computations. Taking into account the long-range interactions in our Monte Carlo simulations, we have described the total dipolar energy along with the vertex populations of our system with all its tilted networks. This has led to a study of the thermodynamics of our system and a unique effective could be ascribed. Secondly, we have taken an interest into the possibility of tailoring these artificial spin systems for applications in random number generation. We have seen that these systems are a better fit exploiting domain wall propagation rather than reversals by coupling. We have then established that the main challenge to overcome in large connected structures is the trade-off between nucleation field from the outputs and depinning field of the upper part of the nanostructure. Indeed, it is necessary to ensure than the domain wall propagating in the structure is indeed the injected one and that no parasitic nucleation occurs which is overcome this issue. The domain wall propagation has been characterised in terms of propagation fields and types of reversals. We have shown that our optimised system exhibits reversal induced by the injected domain wall mainly in unidimensional fashion with clear stochastic behaviour. The characterisation of this behaviour has shown that a mean weight value describes the choices observed which do not exhibit any correlation. Our artificial spin system therefore behaves as a Galton board, the prime device for random number generation. This PhD work has shown the versatility of artificial spin systems as spin ice for understanding the influence of tuned interactions in their thermodynamics. This work has also demonstrated their versatility for an application with the characterisation of their stochastic behaviour through an optimisation of the geometry

La problématique de la classification de données spatiales se pose par exemple lorsqu'on segmente une image en régions homogènes ou lorsqu'on cartographie des données multidimensionnelles localisées telles que des relevés physico-chimiques du sol. Dans ce travail, les méthodes proposées s'appuient sur des distributions de probabilité afin de modéliser les mécanismes engendrant la partition non observée et les observations. S'il s'agit d'effectuer les regroupements en se basant uniquement sur les valeurs observées, on rappelle que les modèles de mélange, la vraisemblance classifiante et l'algorithme EM procurent des solutions flexibles et relativement simples à mettre en œuvre. Afin d'intégrer en outre une hypothèse d'homogénéité spatiale de la partition, on se propose de conduire des raisonnements similaires dans le cadre des modèles utilisant un champ de Markov caché. D'une part, on démontre qu'en appliquant l'algorithme EM au cas des champs de potts cachés avec une approximation de champ moyen, on effectue les mêmes calculs que l'optimisation alternée d'une vraisemblance classifiante floue. Ce constat permet d'améliorer sur certains points une méthode de classification spatiale floue itérative récemment proposée. Sur des données simulées et réelles, la méthode obtenue fournit des résultats comparables aux techniques utilisant des simulations de Monte-Carlo pour un cout algorithmique moindre. D'autre part, on adapte l'approche précédente à des types particuliers de données spatiales. Pour un problème d'écologie numérique, on construit ainsi une méthode visant à classifier des indicateurs de présence/absence localisés. On propose selon une démarche analogue un algorithme de classification peu sensible aux valeurs atypiques. Enfin, pour traiter des données spatiales incomplètes, on propose d'optimiser une vraisemblance classifiante dont le modèle statistique sous-jacent intègre la notion de valeurs manquantes.

La théorie des modèles finis est devenue un enjeu important de l'informatique. Les probabilités y jouent un rôle central, comme objet d'étude et comme méthode de preuve. En effet, elles conduisent aux notions de loi 0-1 et de convergence et autorisent des preuves d'existence particulièrement concises. Nous répondons à une question de Kolaitis et Vardi en donnant deux preuves finitistes de la loi 0-1 pour les énoncés de Bernays-Schönfinkel et Ackermann quantifiés existentiellement au second ordre. Nous établissons aussi la conjecture de ces auteurs sur l'incomparabilité du pouvoir d'expression de ces deux langages. Nous montrons que le problème de la frontière des lois 0-1 dans la logique du second ordre est intéressant. Nous formulons une conjecture donnant la position de cette frontière, et la prouvons en partie pour le deuxième niveau de la hiérarchie du second ordre. Nous fournissons aussi le tableau complet des lois 0-1 et de convergence de l'ensemble des propriétés monotones dans les graphes aléatoires pour la classe des probabilités d'arêtes la plus étudiée d'un point de vue logique. Nos résultats montrent que ces propriétés sont sensibles au double saut découvert par Erdös et Rényi, mais insensibles à la curieuse dichotomie rationnel / irrationnel obtenue par Shelah et Spencer pour la logique du premier ordre. Nous ouvrons ainsi l'étude des phénomènes de convergence de langages préservés par extension, comme DATALOG, pour des structures aléatoires peu denses, susceptibles de rendre compte de situations concrètes en informatique.

Avec l'accroissement des traitements de l'information à bord des véhicules spatiaux et l'utilisation de technologies de plus en plus intégrées, le phénomène d'upset (modification non destructive du contenu d'un point mémoire suite à la collision d'un ion lourd) devient critique. L'objectif de cette thèse est d'étudier la possibilité de durcir face aux upsets un circuit VLSI, tel un processeur, à partir d'une technologie standard. Pour cela, deux points mémoire statiques CMOS (appelés HIT), capables de restituer l'information modifiée par l'impact d'une particule, ont été conçus. Une étude comparative portant sur les cellules HIT, deux cellules mémoire durcies proposées par la NASA et IBM, et le point mémoire statique non durci, a été entreprise. Un premier volet de cette étude, réalisée par simulation Spice, montre que les performances électriques statiques et dynamiques (consommation de puissance statique, temps de propagation et de lecture) sont comparables ou meilleures que celles des cellules mémoire durcies proposées dans la littérature. Un aspect important du durcissement à la conception est la surface silicium additionnelle. L'implantation des cellules à l'aide d'un process HS13 de THOMSON-TCS (épitaxial 1,2 micron) a permis de mettre en évidence que les cellules HIT consomment moins de surface silicium. Le deuxième volet d'étude a concerné la sensibilité aux upsets des cellules : - les charges collectées ont été évaluées à l'aide des simulations Spice, montrant qu'elles sont suffisamment élevées pour tolérer les upsets simples induits par les ions lourds couvrant un large spectre d'énergie, - la sensibilité aux upsets multiples a été évaluée à l'aide d'un modèle Markovien, montrant que les cellules HIT présentent une meilleure tolérance. Pour obtenir ce résultat, l'introduction des chaînes de Markov a conduit à calculer le facteur de défaillance à partir de tous les états critiques susceptibles d'engendrer un aléa logique. Un prototype implémentant cinq bancs de registres constitués de deux solutions proposées dans cette thèse, de deux cellules durcies proposées dans la littérature et de la cellule non durcie, a été conçu et réalisé. Les tests aux ions lourds de ce prototype, à l'aide d'équipements adéquats pour simuler l'environnement radiatif (accélérateurs de particules) permettra de corréler les résultats théoriques avec les données expérimentales

Nous étudions le problème de maintenir une distribution donnée de graphes aléatoires après une séquence arbitraire d’insertions et de suppressions de sommets. Dans l’objectif de modéliser l’évolution de réseaux logiques dynamiques,nous travaillons dans un modèle local où l’accès à la liste des sommets est restreint. À la place, nous faisons l’hypothèse d’un accès à une primitive globale qui retourne un sommet aléatoire, choisi uniformément dans l’ensemble total des sommets. Le problème de maintenance a été exploré sur plusieurs modèles simples de graphes aléatoires (graphes d’Erdos–Rényi, graphes basés sur le modèle par paires, graphes k-sortants uniformes). Pour chacun des modèles, un ou plusieurs algorithmes pour la tâche de maintenance ont été décris et analysés ; les plus élaborés de ces algorithmes sont asymptotiquement optimaux. Le problème de maintenance soulève plusieurs problèmes de simulation liés à notre contexte distribué. Nous nous sommes intéressé en particulier à la maintenabilité de distributions de graphes et à la simulabilité de familles de distributions de probabilité sur les entiers, dans le modèle d’aléa présenté.Une attention particulière a été portée sur la simulation efficace de lois spécifiques nous intéressant (certaines lois binomiales). Cette dernière a pu être obtenue en exploitant les propriétés d’un nouvel arbre de génération pour les permutations, que nous avons introduit
We study the problem of maintaining a given distribution of randomgraphs under an arbitrary sequence of vertex insertions and deletions. Keeping inmind our objective to model the evolution of dynamic logical networks, we work ina local model where we do not have direct access to the list of all vertices. Instead,we assume access to a global primitive that returns a random vertex, chosen uniformlyfrom the whole vertex set. The maintenance problem has been explored onseveral simple random graph models (Erdos–Rényi random graphs, pairing modelbased random graphs, uniform k-out graphs). For each model, one or several updatealgorithms for the maintenance task have been described and analyzed ; the mostelaborate of them are asymptically optimal. The maintenance task rise several simulationissues linked to our distributed context. In particular, we have focused onmaintenability of random graph distributions and simulability of families of probabilitydistributions over integers in our local random model. Special attention hasbeen paid to efficient simulation of particular distributions we were interested in(certain binomial distributions). The latter has been obtained through the use ofproperties of a new generation tree for permutations, which has been introducedalong the way

Comment un robot peut-il estimer si une tâche est réalisable ou pas dans un envi ronnement donné ? De nombreux travaux en robotique s'appuient pour répondre sur les affordances de la psychologie écologique. Apprendre quelles sont les actions permises nécessite selon nous d'apprendre les relations de dépendances locales et globales entre capteurs et effecteurs au cours de l'action.
Pour cela nous assimilons le robot à un réseau sensorimoteur aléatoire, et pour représenter son activité nous introduisons des mesures de dépendance probabilist es et statistiques. Celles-ci nous permettent de construire des matrices, graphes et complexes simpliciaux aléatoires dont nous étudions les propriétés spectrales, topologiques et homologiques.
Puis nous vérifions expérimentalement l'intérêt des outils proposés à l'aide d'un robot mobile simulé, autour de la capacité de pousser les objets de l'environnement, dans le cadre de tâches de classification supervisée et non supervisée.

L'utilisation des memoires sram dans les applications avioniques pose le probleme de leur sensibilite aux radiations. Parmi l'ensemble des rayonnements presents dans l'environnement aerospatial, les particules non ionisantes, comme les neutrons, sont susceptibles de provoquer des reactions nucleaires dans les composants micro-electronique et d'induire des defaillances de type single event upset (seu). L'evaluation des risques lies aux neutrons atmospheriques constitue l'objet principal de ce travail. Les mecanismes d'interaction neutron matiere, la caracterisation des aleas logiques dans les memoires et la determination des particules ionisantes produites par l'environnement neutronique ont permis d'etablir une base de donnees universelle. Cette base contient toutes les courbes de probabilite relatives a la gamme d'energie correspondant aux neutrons atmospheriques, de 1 mev a 1 gev. Les moyens utilises pour sa mise en uvre, l'energie des neutrons incidents, ainsi que son utilisation sont presentes dans ce memoire.

La jonction tunnel magnétique (JTM) commutée par la couple de transfert de spin (STT) a été considérée comme un candidat prometteur pour la prochaine génération de mémoires non-volatiles et de circuits logiques, car elle fournit une solution pour surmonter le goulet d'étranglement de l'augmentation de puissance statique causée par la mise à l'échelle de la technologie CMOS. Cependant, sa commercialisation est limitée par la fiabilité faible, qui se détériore gravement avec la réduction de la taille du dispositif. Cette thèse porte sur l'étude de la fiabilité des circuits basés sur JTM. Tout d'abord, un modèle compact de JTM incluant les problèmes principaux de fiabilité est proposé et validé par la comparaison avec des données expérimentales. Sur la base de ce modèle précis, la fiabilité des circuits typiques est analysée et une méthodologie d'optimisation de la fiabilité est proposée. Enfin, le comportement de commutation stochastique est utilisé dans certaines nouvelles conceptions d'applications classiques
Spin transfer torque magnetic tunnel junction (STT-MTJ) has been considered as a promising candidate for next generation of non-volatile memories and logic circuits, because it provides a perfect solution to overcome the bottleneck of increasing static power caused by CMOS technology scaling. However, its commercialization is limited by the poor reliability, which deteriorates severely with device scaling down. This thesis focuses on the reliability investigation of MTJ based non-volatile circuits. Firstly, a compact model of MTJ including main reliability issues is proposed and validated by the comparison with experimental data. Based on this accurate model, the reliability of typical circuits is analyzed and reliability optimization methodology is proposed. Finally, the stochastic switching behavior is utilized in some new designs of conventional applications

La jonction tunnel magnétique (JTM) commutée par la couple de transfert de spin (STT) a été considérée comme un candidat prometteur pour la prochaine génération de mémoires non-volatiles et de circuits logiques, car elle fournit une solution pour surmonter le goulet d'étranglement de l'augmentation de puissance statique causée par la mise à l'échelle de la technologie CMOS. Cependant, sa commercialisation est limitée par la fiabilité faible, qui se détériore gravement avec la réduction de la taille du dispositif. Cette thèse porte sur l'étude de la fiabilité des circuits basés sur JTM. Tout d'abord, un modèle compact de JTM incluant les problèmes principaux de fiabilité est proposé et validé par la comparaison avec des données expérimentales. Sur la base de ce modèle précis, la fiabilité des circuits typiques est analysée et une méthodologie d'optimisation de la fiabilité est proposée. Enfin, le comportement de commutation stochastique est utilisé dans certaines nouvelles conceptions d'applications classiques
Spin transfer torque magnetic tunnel junction (STT-MTJ) has been considered as a promising candidate for next generation of non-volatile memories and logic circuits, because it provides a perfect solution to overcome the bottleneck of increasing static power caused by CMOS technology scaling. However, its commercialization is limited by the poor reliability, which deteriorates severely with device scaling down. This thesis focuses on the reliability investigation of MTJ based non-volatile circuits. Firstly, a compact model of MTJ including main reliability issues is proposed and validated by the comparison with experimental data. Based on this accurate model, the reliability of typical circuits is analyzed and reliability optimization methodology is proposed. Finally, the stochastic switching behavior is utilized in some new designs of conventional applications

Les nombres aléatoires sont indispensables dans de nombreuses applications notamment en cryptographie où l’aléa est utilisé dans les protocoles de sécurité. Les générateurs de nombres aléatoires, plus connus sous le nom de RNG comme “Random Number Generator” se déclinent en deux familles, les PRNG (Pseudo RNG) qui sont des générateurs de nombres aléatoires ayant des séquences déterministes et les TRNG (True RNG) qui sont des générateurs d’aléa “vrai”, donc non prédictibles. Les applications cryptographiques utilisent à la fois les TRNG et les PRNG. Un PRNG nécessite une valeur initiale, ou graine, qui peut être la sortie d’un TRNG. Les TRNG tirent profit de l’aléa des phénomènes physiques. Les TRNGs dans les technologies numériques comme les FPGAs font appel à des oscillateurs qui présentent l’inconvénient de pouvoir être attaqués par couplage harmonique. De façon à évaluer la qualité entropique d’un TRNG, des standards basés sur des tests statistiques ont été élaborés par des organismes de certification comme le NIST ou la BSI. Cependant, il est recommandé de formaliser, par le biais d’un modèle, le caractère stochastique de la génération d’aléa. Dans cette thèse, nous étudions une architecture de TRNG, peu coûteuse et robuste face aux attaques harmoniques car elle n’utilise pas d’oscillateurs. Ce TRNG extrait une variable aléatoire en exploitant à la fois les états métastables des bascules et les fluctuations temporelles (ou gigue) des signaux échantillonnés. Nous proposons par la suite un modèle stochastique qui nous permet de décrire le comportement aléatoire du TRNG indépendamment de la technologie ciblée. Les caractérisations et évaluations sur des circuits prototypes en technologies FPGA et ASIC montrent que l’architecture TRNG proposée génère de l’aléa de qualité et est robuste face aux variations environnementales
Random numbers are required in numerous applications namely in cryptography where randomness is used in security protocols. There are two main classes of Random Number Generators (RNG) : The Pseudo RNG (PRNG) which have a deterministic sequence, and the True RNG (TRNG) which generates unpredictable random numbers. Cryptographic applications use both TRNG and PRNG. The PRNG needs an initial value, or seed, which can be the output of a TRNG. In digital technologies, like FPGAs, TRNG are commonly based on oscillators which have the drawback of being biased by harmonic coupling. In order to assess the entropic quality of TRNGs, standards based on statistical tests have been elaborated by certification organisms namely the NIST and the BSI. However, it is recommended to formalize the stochastic behaviour of the randomness generation process. In this Ph.D, we address the design and quality evaluation of TRNGs in digital circuits. We study of a low-cost digital TRNG without oscillators, hence robust against harmonics attacks. The proposed TRNG exploits both the metastability phenomenon and the jitter noise in CMOS digital flip-flops to generate the random numbers. A stochastic model of this TRNG has been formalized. This model describes the random generation process regardless of the targeted technology. The characterization and evaluation on a prototype circuit, in FPGA and ASIC technologies, has shown that the proposed TRNG architecture generates randomness of good quality and is robust against environmental variations

Cette thèse adresse le sujet de la génération de suites binaires aléatoires dans les circuits logiques programmables FPGA et plus particulièrement les suites dont l'origine aléatoire est de nature physique et non algorithmique. De telles suites trouvent une utilisation abondante dans la plupart des protocoles cryptographiques. Un état de l'art portant sur les différentes méthodes de génération de vrai aléa dans les circuits logiques programmables est présenté sous forme d'analyse critique d'articles scientifiques. Une synthèse des différentes tendances dans l'extraction et la génération d'aléa est également présentée. Une campagne d'expériences et de mesures est présentée visant à caractériser les différentes sources de signaux aléatoires disponibles à l'intérieur du FPGA. Des phénomènes intéressants tel le verrouillage de plusieurs oscillateurs en anneau, la dépendance de la source d'aléa vis-à-vis de la logique environnante et la méthodologie de mesure du jitter sont analysés. Plusieurs méthodes nouvelles de génération de suites binaires aléatoires sont décrites. Finalement une méthodologie nouvelle de simulation en VHDL de générateurs complets ainsi qu'un modèle mathématique d'un oscillateur en anneau en tant que source d'aléa sont présentés

L’objectif de ce travail est de concevoir un système de communication et de localisation destiné à des métros automatiques guidés afin d’améliorer leur exploitation et d’accroître la sécurité. La principale application du RADAR est de réduire le temps de perte d’exploitation causé par un métro en panne, en permettant au train suivant de connaître en temps réel la distance le séparant de celui qui est immobilisé. Le capteur est du type radar coopératif constitué de deux couples d’interrogateurs–répondeurs équipant l’avant et l’arrière de chaque train et formant ainsi une boucle complète. Le choix du capteur s’est orienté vers le radar à corrélation, car il maximise le rapport signal à bruit en sortie. Des techniques de multiplexage originales à étalement de spectre ont été développées afin de combiner la fonction de localisation et l’établissement d’une communication avec le même capteur. Une des caractéristiques de ce système est qu’il est amené à fonctionner en tunnel et en espace libre. D’où le choix des têtes hyperfréquences proposées. La chaîne de transmission/réception a ensuite été simulée dans son intégralité et dans son environnement de fonctionnement afin de valider les choix techniques opérées. Finalement, nous avons présenté des solutions d’implémentation des algorithmes de traitement sur une plateforme de développement de type FPGA. Un prototype a été réalisé et les premiers tests ont été menés en espace libre. Les résultats obtenus montrent qu’une portée de l’ordre de 700 m peut être atteinte. Les techniques de multiplexage que nous avons proposées permettent d’établir une communication avec des débits variables suivant la technique de multiplexage. Ils peuvent prendre les valeurs (97kb/s,1,6Mb/S, 5,4Mb/s et 11,27Mb/s)
The aim of this work is to design a localization and communication system dedicated to guided automatic trains in order to enhance their exploitation and to increase their reliability. The principal function of this radar is to reduce the lost exploitation time caused by a broken-down train to allow the following train to estimate in real time the distance between them. The sensor is a cooperative radar composed by two couples of interrogators– transponders which equip the front and the rear of each train following a complete loop. The choice of the sensor type is directed towards the correlation radar, because it maximizes the output signal to noise ratio. Some original multiplexing techniques based on spreading spectrum have been developed to combine the localization and the communication functions inside the same device. This system must be able to work on open area and also in tunnel. The choice of Hyperfrequency front-ends has been done following this important characteristic. The whole system (Transmitter/Receiver) have been simulated in real conditions in order to validate the selected technical choices. Finally, we present some solutions to implement the computing algorithms on a FPGA devices. A mock-up has been realized and the first tests have been carried out on open area. The obtained results show that a range of about 700m could be reached. The proposed multiplexing techniques allow the system to establish a communication with different data rates among (97kb/s, 1. 6Mb/S, 5. 4Mb/s and 11. 27Mb/s)

Les nombres aléatoires sont indispensables dans de nombreuses applications notamment en cryptographie où l’aléa est utilisé dans les protocoles de sécurité. Les générateurs de nombres aléatoires, plus connus sous le nom de RNG comme “Random Number Generator” se déclinent en deux familles, les PRNG (Pseudo RNG) qui sont des générateurs de nombres aléatoires ayant des séquences déterministes et les TRNG (True RNG) qui sont des générateurs d’aléa “vrai”, donc non prédictibles. Les applications cryptographiques utilisent à la fois les TRNG et les PRNG. Un PRNG nécessite une valeur initiale, ou graine, qui peut être la sortie d’un TRNG. Les TRNG tirent profit de l’aléa des phénomènes physiques. Les TRNGs dans les technologies numériques comme les FPGAs font appel à des oscillateurs qui présentent l’inconvénient de pouvoir être attaqués par couplage harmonique. De façon à évaluer la qualité entropique d’un TRNG, des standards basés sur des tests statistiques ont été élaborés par des organismes de certification comme le NIST ou la BSI. Cependant, il est recommandé de formaliser, par le biais d’un modèle, le caractère stochastique de la génération d’aléa. Dans cette thèse, nous étudions une architecture de TRNG, peu coûteuse et robuste face aux attaques harmoniques car elle n’utilise pas d’oscillateurs. Ce TRNG extrait une variable aléatoire en exploitant à la fois les états métastables des bascules et les fluctuations temporelles (ou gigue) des signaux échantillonnés. Nous proposons par la suite un modèle stochastique qui nous permet de décrire le comportement aléatoire du TRNG indépendamment de la technologie ciblée. Les caractérisations et évaluations sur des circuits prototypes en technologies FPGA et ASIC montrent que l’architecture TRNG proposée génère de l’aléa de qualité et est robuste face aux variations environnementales
Random numbers are required in numerous applications namely in cryptography where randomness is used in security protocols. There are two main classes of Random Number Generators (RNG) : The Pseudo RNG (PRNG) which have a deterministic sequence, and the True RNG (TRNG) which generates unpredictable random numbers. Cryptographic applications use both TRNG and PRNG. The PRNG needs an initial value, or seed, which can be the output of a TRNG. In digital technologies, like FPGAs, TRNG are commonly based on oscillators which have the drawback of being biased by harmonic coupling. In order to assess the entropic quality of TRNGs, standards based on statistical tests have been elaborated by certification organisms namely the NIST and the BSI. However, it is recommended to formalize the stochastic behaviour of the randomness generation process. In this Ph.D, we address the design and quality evaluation of TRNGs in digital circuits. We study of a low-cost digital TRNG without oscillators, hence robust against harmonics attacks. The proposed TRNG exploits both the metastability phenomenon and the jitter noise in CMOS digital flip-flops to generate the random numbers. A stochastic model of this TRNG has been formalized. This model describes the random generation process regardless of the targeted technology. The characterization and evaluation on a prototype circuit, in FPGA and ASIC technologies, has shown that the proposed TRNG architecture generates randomness of good quality and is robust against environmental variations

Les nombres aléatoires sont essentiels pour les systèmes cryptographiques modernes. Ils servent de clés cryptographiques, de nonces, de vecteurs d’initialisation et de masques aléatoires pour la protection contre les attaques par canaux cachés. Dans cette thèse, nous traitons des générateurs de nombres aléatoires dans les circuits logiques (FPGA et ASIC). Nous présentons les méthodes fondamentales de génération de nombres aléatoires dans des circuits logiques. Ensuite, nous discutons de différents types de TRNG en utilisant le jitter d’horloge comme source d’aléa. Nous faisons une évaluation rigoureuse de divers noyaux TRNG conformes à la norme AIS-20/31 et mis en œuvre dans trois familles de FPGA différentes: Intel Cyclone V, Xilinx Spartan-6 et Microsemi SmartFusion2. Puis, nous présentons l’implémentation des noyaux TRNG sélectionnés dans des ASIC et leur évaluation. Ensuite, nous étudions en profondeur PLL-TRNG afin de fournir une conception sécurisée de ce TRNG ainsi que des tests intégrés. Enfin, nous étudions les TRNG basés sur les oscillateurs. Nous comparons de différentes méthodes d'extraction d’aléa ainsi que de différents types d'oscillateurs et le comportement du jitter d'horloge à l'intérieur de chacun d'eux. Nous proposons également des méthodes de mesure du jitter intégrée pour le test en ligne des TRNG basés sur les oscillateurs
Random numbers are essential for modern cryptographic systems. They are used as cryptographic keys, nonces, initialization vectors and random masks for protection against side channel attacks. In this thesis, we deal with random number generators in logic devices (Field Programmable Gate Arrays – FPGAs and Application Specific Integrated Circuits – ASICs). We present fundamental methods of generation of random numbers in logic devices. Then, we discuss different types of TRNGs using clock jitter as a source of randomness. We provide a rigorous evaluation of various AIS-20/31 compliant TRNG cores implemented in three different FPGA families : Intel Cyclone V, Xilinx Spartan-6 and Microsemi SmartFusion2. We then present the implementation of selected TRNG cores in custom ASIC and we evaluate them. Next, we study PLL-TRNG in depth in order to provide a secure design of this TRNG together with embedded tests. Finally, we study oscillator based TRNGs. We compare different randomness extraction methods as well as different oscillator types and the behavior of the clock jitter inside each of them. We also propose methods of embedded jitter measurement for online testing of oscillator based TRNGs

Les travaux de cette thèse s'inscrivent dans l'objectif général de fournir des recommandations sur la façon d'intégrer les effets du site dans l'évaluation probabiliste des risques sismiques, mieux connue sous le nom de PSHA, une méthodologie connue et utilisée à l'échelle mondiale pour estimer l'aléa et le risque sismiques à l'échelle régionale et locale. Nous passons donc en revue les méthodes disponibles dans la littérature pour obtenir la courbe d'aléa sismique en surface d'un site non-rocheux, en commençant par les méthodes les plus simples et plus génériques (partiellement probabiliste), jusqu'aux méthodes site-spécifiques (partiellement et entièrement probabilistes) qui nécessitent une caractérisation du site de plus en plus poussée, rarement disponible sauf cas exceptionnel comme par exemple le site test d'Euroseistest. C'est justement sur l'exemple de ce site que sont donc comparées un certain nombre de ces méthodes, ainsi qu'une nouvelle.La spécificité et la difficulté de ces études PSHA "site-spécifiques" vient du caractère non-linéaire de la réponse des sites peu rigides, ainsi que du fait que le rocher de référence contrôlant cette réponse est souvent très rigide. Les aspects "ajustement rocher dur" et "convolution" de l'aléa sismique au rocher avec la fonction d'amplification ou la fonction transfert (empirique ou numérique) d’un site font donc l'objet d'une attention particulière dans ces études comparatives. Un cadre général est présenté sur la façon de prendre en compte simultanément les caractéristiques spécifiques au site, la variabilité aléatoire complète ou réduite ("single station sigma"), les ajustements hôte-cible et le comportement linéaire / non linéaire d'un site, où nous expliquons toutes les étapes, corrections, avantages et difficultés que nous avons trouvés dans le processus et les différentes façons de les mettre en oeuvre.Cette étude comparative est divisée en deux parties: la première porte sur les méthodes non site-spécifiques et les méthodes hybrides site-spécifique (évaluation probabiliste de l'aléa au rocher et déterministe de la réponse de site), la seconde porte sur deux approches prenant en compte la convolution aléa rocher / réponse de site de façon probabiliste. Un des résultats majeurs de la première est l'augmentation de l'incertitude épistémique sur l'aléa en site meuble comparé à l'aléa au rocher, en raison du cumul des incertitudes associées à chaque étape. Un autre résultat majeur commun aux deux études est l'impact très important de la non-linéarité du sol dans les sites souples, ainsi que de la façon de les prendre en compte: la variabilité liée à l'utilisation de différents codes de simulation NL apparaît plus importante que la variabilité liée à différentes méthodes de convolution 100% probabilistes. Nous soulignons l'importance d'améliorer la manier d’inclure les effets du site dans les méthodes de l’estimation de l’aléa sismique probabiliste ou PSHA, et nous soulignons aussi l'importance d'instrumenter des sites actifs avec des sédiments meubles, comme l'Euroseistest, afin de tester et valider les modèles numériques.Finalement, on présente un résumé des résultats, des conclusions générales, de la discussion sur les principaux problèmes méthodologiques et des perspectives d'amélioration et de travail futur.Mots-clés: Effets du site, incertitude épistémique, PSHA, single station sigma, ajustements hôte-cible, effets linéaires et non linéaires, réponse de site
The overall goal of this research work is of provide recommendations on how to integrate site effects into Probabilistic Seismic Hazard Assessment, better known as PSHA, a well-known and widely used methodology. Globally used to estimate seismic hazard and risk at regional and local scales. We therefore review the methods available in the literature to obtain the seismic hazard curve at the surface of a soft soil site, starting with the simplest and most generic methods (partially probabilistic), up to the full site-specific methods (partially and fully probabilistic), requiring an excellent site-specific characterization, rarely available except exceptional cases such as the case of Euroseistest site. It is precisely on the example of this site that are compared a number of these methods, as well as a new one. And it is precisely at the Euroseistest that we performed an example of application of the different methods as well as a new one that we propose as a result of this work.The specificity and difficulty of these "site-specific" PSHA studies comes from the non-linear nature of the response of the soft sites, as well as from the fact that the reference rock controlling this response is often very rigid. The "rock to hard rock adjustment" and "convolution" aspects of the rock seismic hazard, together with the amplification function or the transfer function (empirical or numerical) of a site are therefore the subject of particular attention in these studies. comparative studies. A general framework is presented on how to simultaneously take into account the site-specific characteristics, such as the complete or reduced random variability ("single station sigma"), host-to -target adjustments and the linear / nonlinear behavior of a site, where we explain all the followed steps, the different corrections performed, the benefits and difficulties that we found in the process and the ways we sort them and discussing them when the answer was not straight forward.This comparative study is divided into two parts: the first deals with non-site-specific methods and site-specific hybrid methods (probabilistic evaluation of rock hazard and deterministic of the site response). The second deals with two approaches taking into account the convolution of rock hazard and the site response in a probabilistically way. One of the major results of the first is the increase of the epistemic uncertainty on the soft site hazard compared to the rock hazard, due to acumulation of uncertainties associated to each step. Another major common result to both studies is the very important impact of non-linearity on soft sites, as well as the complexity on how to account for them: the variability associated with the use of different non-linear simulation codes appears to be greater than the method-to-method variability associated with the two different full convolution probabilistic methods. We emphasize on the importance of improving the way in which the site effects are included into probabilistic seismic hazard methods, PSHA. And we also emphasize on the importance of instrumenting active sites with soft sediments, such as the Euroseistest, to test and validate numerical models.Finally, a summary of the results, the general conclusions, discussion of key methodological issues, and perspectives for improvement and future work are presented.Keywords: Site Effects, Epistemic Uncertainty, PSHA, single station sigma, host to target adjustments, linear and nonlinear site effects, soil site response