Spelling suggestions: "subject:"cartesian""
81 |
Recherche de motifs fréquents dans une base de cartes combinatoires / Frequent pattern discovery in combinatorial maps databasesGosselin, Stéphane 24 October 2011 (has links)
Une carte combinatoire est un modèle topologique qui permet de représenter les subdivisions de l’espace en cellules et les relations d’adjacences et d’incidences entre ces cellules en n dimensions. Cette structure de données est de plus en plus utilisée en traitement d’images, mais elle manque encore d’outils pour les analyser. Notre but est de définir de nouveaux outils pour les cartes combinatoires nD. Nous nous intéressons plus particulièrement à l’extraction de sous-cartes fréquentes dans une base de cartes. Nous proposons deux signatures qui sont également des formes canoniques de cartes combinatoires. Ces signatures ont chacune leurs avantages et leurs inconvénients. La première permet de décider de l’isomorphisme entre deux cartes en temps linéaire, en contrepartie le coût de stockage en mémoire est quadratique en la taille de la carte. La seconde signature a un coût de stockage en mémoire linéaire en la taille de la carte, cependant le temps de calcul de l’isomorphisme est quadratique. Elles sont utilisables à la fois pour des cartes connexes, non connexes, valuées ou non valuées. Ces signatures permettent de représenter une base de cartes combinatoires et de rechercher un élément de manière efficace. De plus, le temps de recherche ne dépend pas du nombre de cartes présent dans la base. Ensuite, nous formalisons le problème de recherche de sous-cartes fréquentes dans une base de cartes combinatoires nD. Nous implémentons deux algorithmes pour résoudre ce problème. Le premier algorithme extrait les sous-cartes fréquentes par une approche en largeur tandis que le second utilise une approche en profondeur. Nous comparons les performances de ces deux algorithmes sur des bases de cartes synthétiques. Enfin, nous proposons d’utiliser les motifs fréquents dans une application de classification d’images. Chaque image est décrite par une carte qui est transformée en un vecteur représentant le nombre d’occurrences des motifs fréquents. À partir de ces vecteurs, nous utilisons des techniques classiques de classification définies sur les espaces vectoriels. Nous proposons des expérimentations en classification supervisée et non supervisée sur deux bases d’images. / A combinatorial map is a topological model that can represent the subdivisions of space into cells and their adjacency relations in n dimensions. This data structure is increasingly used in image processing, but it still lacks tools for analysis. Our goal is to define new tools for combinatorial maps nD. We are particularly interested in the extraction of submaps in a database of maps. We define two combinatorial map signatures : the first one has a quadratic space complexity and may be used to decide of isomorphism with a new map in linear time whereas the second one has a linear space complexity and may be used to decide of isomorphism in quadratic time. They can be used for connected maps, non connected maps, labbeled maps or non labelled maps. These signatures can be used to efficiently search for a map in a database.Moreover, the search time does not depend on the number of maps in the database. Then, we formalize the problem of finding frequent submaps in a database of combinatorial nD maps. We implement two algorithms for solving this problem. The first algorithm extracts the submaps with a breadth-first search approach and the second uses a depth-first search approach. We compare the performance of these two algorithms on synthetic database of maps. Finally, we propose to use the frequent patterns in an image classification application. Each image is described by a map that is transformed into a vector representing the number of occurrences of frequent patterns. From these vectors, we use standard techniques of classification defined on vector spaces. We propose experiments in supervised and unsupervised classification on two images databases.
|
82 |
The role of lysosome alterations in bladder cancer progression / Rôle des altérations lysosomales dans la progression du cancer de la vessieDe Barros Santos, Camilla 28 September 2017 (has links)
Le cancer est une maladie multifactorielle définie par un développement rapide de cellules anormales. Les cellules malignes acquièrent des avantages compétitifs qui permettent une croissance et prolifération anormales, grâce à un large spectre de changements génétiques et épigénétiques conduisant à des changements majeurs dans les profils de transcriptome et protéome et ainsi des modifications dans des voies de signalisation, le trafic intracellulaire et le métabolisme. Des nombreuses voies cellulaires ont été étudiées dans le contexte du cancer, y compris la signalisation, la migration, la perte de la polarité cellulaire apico-basale et l'adhésion cellulaire, cependant très peu est connu sur les altérations au niveau des organelles. Cette thèse a comme objectif d'identifier des altérations dans les compartiments intracellulaires et d'étudier leurs corrélations avec la progression du cancer. Dans la culture cellulaire classique, l'étude systématique de l'organisation du positionnement relatif des organelles est difficile en raison des fortes hétérogénéités morphologiques des cellules. Pour contourner ce problème, nous avons utilisé l’innovante technique des micro-patrons combinée à des cartes de densité des organelles. Après une analyse systématique de différentes lignées cellulaires représentant différents grades du cancer de la vessie, nous avons identifié des changements dans le positionnement de plusieurs organelles. Le changement de position le plus important a été observé pour les lysosomes, dont la distribution était plus périphérique dans les cellules représentant des grades plus avancées du cancer de la vessie. Ceci suggère que le positionnement des lysosomes pourrait être potentiellement important dans la progression du cancer. Par conséquent, nous avons cherché à caractériser l'impact de l’altération des lysosomes sur le comportement des cellules transformées. Nous avons constaté que les changements dans le positionnement des lysosomes jouent un rôle dans l'invasion des cellules cancéreuses de la vessie. En effet, le transport antérograde des lysosomes est en corrélation avec l’invasion 3D, contrairement au transport rétrograde qui corrèle avec une diminution de l’invasion cellulaire. Enfin, nous avons étudié les mécanismes moléculaires par lesquels les altérations du lysosome ont un impact sur l'invasion cellulaire. / Cancer is a multifactorial disease defined by a rapid development of abnormal cells. Malignant cells acquire competitive advantages for growth and proliferation through a big spectrum of genetic and epigenetic changes leading to major changes in the transcriptome and proteome profiles and thus to alterations in multiple signaling pathways, intracellular trafficking and metabolism. Although many cellular pathways have been studied in the context of cancer, including signaling, migration, loss of apical-basal cell-polarity and cell adhesion, little is known about cancer-related alterations on the sub-cellular, organelle level. This PhD thesis aimed to identify alterations in intracellular compartments and to study how these changes correlate with cancer progression. In classical culture, the systematic study on the organization and relative positioning of organelles is challenging because of the strong morphological cell-to-cell variations. To overcome this problem, we used innovative micro-patterning technique in combination with quantitative, probabilistic mapping of cell organelles. Using a systematic analysis of different cell lines representing different stages of bladder cancer, we identified several changes in the positioning of organelles. The most striking phenotype was revealed by lysosomes, whose distribution was more peripheral in cells representing higher grades of bladder cancer. This suggested that lysosome positioning could be potentially relevant in cancer progression. Therefore, we aimed to characterize the impact of lysosome alteration on cell behavior in transformed cells. We found that changes in lysosome positioning played a role on bladder cancer cell invasion. Indeed, anterograde transport of lysosomes correlate with 3D invasion behavior, contrary to retrograde transport that correlated with decreased cell invasion. Finally, we studied about the molecular mechanisms by which lysosome alterations impact cell invasion.
|
83 |
Lobes de cosinus et visibilité pour la simulation d'éclairage / Cosine lobes and visibility for lighting simulationPerrot, Romuald 07 December 2012 (has links)
La simulation des réflexions lumineuses multiples à l'intérieur d'un environnement nécessite de résoudre une intégrale de premier ordre, récursive infinie, pour laquelle il n'existe pas de solution analytique dans le cas général. Certaines méthodes permettent de donner une solution théorique exacte, mais avec des temps de calcul trop important pour espérer produire plusieurs images par seconde dans un avenir proche. De nombreuses méthodes permettent de réaliser ces calculs de manière plus rapide, mais elles reposent sur des approximations dont les effets sont souvent visibles sur les images produites. Notre objectif est de proposer des solutions permettant de réduire les erreurs de calculs en exploitant deux approches complémentaires : (i) une homogénéisation des termes de l'équation de manière à la résoudre seulement à l'aide de quelques opérateurs simples ; (ii) la prise en compte précise des informations de visibilité pour réduire le biais des méthodes reposant sur une estimation de densité. A terme, notre objectif est de diminuer le coût des requêtes de visibilité de nos deux contributions. Pour cela nous envisageons notamment d'introduire des calculs hiérarchiques de visibilité de façon à amortir le coût global des requêtes. / Simulating light transfer within a virtual environment requires to solve a first order, infinite recursive integral, that unfortunately doesn't have any solution in general cases. Though theoretically exact solutions exist, their computing time is not adapted to real-time rendering in a near future. Many methods have been proposed for accelerating these computations, but they rely on approximations that often produce visible artifacts on the resulting images. Our goal is to propose some new solutions that can reduce biases with two complementary approaches : (i) a new homogeneous representation of each term of the equation can be used to resolve it using only simple operators ; (ii) considering precise visibility information in order to reduce bias of methods that rely on density estimation. On the long range, we aim at reducing visibility requests costs of each contribution. For that purpose, we particularly plan to introduce hierarchical visibility computations so as to amortize queries cost.
|
84 |
Analysis of the chemical space of antimalarial compounds by generative topographie mapping / Analyse de l'espace chimique des composés antipaludiques par la méthode GTMSidorov, Pavel 25 September 2017 (has links)
Cette thèse est consacrée à l’analyse de l’espace chimique des composés antipaludiques. L’analyse est faite à l’aide de la méthode des cartes topographiques génératrices (GTM). Un nouveau concept des cartes universelles est introduit et discuté en détail dans cette thèse : ce sont des cartes qui sont capables d’accommoder plusieurs jeux de données et les propriétés associées simultanément. Trois types des cartes sont construits et analysés : les cartes locales, globales et universelles. Elles sont toutes compétentes à la prédiction des composés actifs contre le parasite, ainsi qu’à l’analyse de l’espace chimique. Elles nous permettent d’étudier le recouvrement des données issues des sources différentes, de détecter des terra incognita de l’espace chimique, identifier des zones correspondantes aux différents mécanismes d’action, et révéler des incohérences d’annotations des données. / This thesis is dedicated to the concept of the analysis of chemical space, and the application of thatconcept to antimalarial compounds. The analysis of the chemical space of antimalarial compoundshere is done with the aid of the Generative Topographic Mapping (GTM) method. A concept ofUniversal GTM maps is developed and discussed in detail in this thesis: these are maps that areable to accommodate different datasets and associated properties. Three types of maps are builtand analyzed: local, global, and universal. All these maps perform well in predicting compoundsactive against the parasite, as well as in the analysis of chemical space: they help us to study theoverlap of data coming from different sources, detect terra incognita of the antimalarial space,delineate zones corresponding to various mechanisms of action, as well as highlight theinconsistencies in data annotations.
|
85 |
Real-time 2D manipulation of plausible 3D appearance using shading and geometry buffers / Manipulation 2D en temps réel d'une apparence 3D plausible en utilisant les buffer d'ombrage et de géométrieZubiaga Pena, Carlos Jorge 07 November 2016 (has links)
Les artistes traditionnels peignent directement sur une toile et créent des apparences plausibles de scènes qui ressemblent au monde réel. A l’opposé, les artistes en informatique graphique définissent des objets dans une scène virtuelle (maillages 3D, matériaux et sources de lumière), et utilisent des algorithmes complexes (rendu) pour reproduire leur apparence. D’un côté, les techniques de peinture permettent de librement définir l’apparence. D’un autre côté, les techniques de rendu permettent de modifier séparément et dynamiquement les différents éléments qui définissent l’apparence. Dans cette thèse, nous présentons une approche intermédiaire pour manipuler l’apparence, qui permettent certaines manipulations en 3D en travaillant dans l’espace 2D. Mous étudions d’abord l’impact sur l’ombrage des matériaux, tenant en compte des matériaux comme des filtres passe-bande d’éclairage. Nous présentons ensuite un petit ensemble de relations statistiques locales entre les matériaux / l’éclairage et l’ombrage. Ces relations sont utilisées pour imiter les modifications sur le matériaux ou l’éclairage d’une image d’une sphère créée par un artiste. Les techniques connues sons le nom de LitSpheres / MatCaps utilisent ce genre d’images pour transférer leur apparence `a des objets de forme quelconque. Notre technique prouve la possibilité d’imiter les modifications 3D de la lumière et de matériaux à partir d’une image en 2D. Nous présentons une technique différente pour modifier le troisième élément impliqué dans l’aspect visuel d’un objet, sa géométrie. Dans ce cas, on utilise des rendus comme images d’entrée avec des images auxiliaires qui contiennent des informations 3D de la scène. Nous récupérons un ombrage indépendant de la géométrie pour chaque surface, ce qui nous demande de supposer qu’il n’y a pas de variations spatiales d’éclairage pour chaque surface. L’ombrage récupéré peut être utilisé pour modifier arbitrairement la forme locale de l’objet de manière interactive sans la nécessité de rendre `a nouveau la scène. / Traditional artists paint directly on a canvas and create plausible appearances of real-world scenes. In contrast, Computer Graphics artists define objects on a virtual scene (3D meshes, materials and light sources), and use complex algorithms (rendering) to reproduce their appearance. On the one hand, painting techniques permit to freely define appearance. On the other hand, rendering techniques permit to modify separately and dynamically the different elements that compose the scene. In this thesis we present a middle-ground approach to manipulate appearance. We offer 3D-like manipulation abilities while working on the 2D space. We first study the impact on shading of materials as band-pass filters of lighting. We present a small set of local statistical relationships between material/lighting and shading. These relationships are used to mimic modifications on material or lighting from an artist-created image of a sphere. Techniques known as LitSpheres/MatCaps use these kinds of images to transfer their appearance to arbitrary-shaped objects. Our technique proves the possibility to mimic 3D-like modifications of light and material from an input artwork in 2D. We present a different technique to modify the third element involved on the visual appearance of an object: its geometry. In this case we use as input rendered images alongside with 3D information of the scene output in so-called auxiliary buffers. We are able to recover geometry-independent shading for each object surface, assuming no spatial variations for each recovered surface. The recovered shading can be used to modify arbitrarily the local shape of the object interactively without the need to re-render the scene.
|
86 |
Naissance des oscillations dans les instruments de type clarinette à paramètre de contrôle variable. / Birth of oscillation in clarinet-like interments with variable control parameter.Bergeot, Baptiste 10 October 2013 (has links)
Ce travail de recherche est une contribution à l'étude des transitoires d'attaque dans les instruments de type clarinette. L'objectif est d'analyser le comportement de l'instrument en réponse à une variation lente et linéaire de la pression dans la bouche du musicien.Dans des simulations numériques ou des expériences in vitro, lorsque la pression dans la bouche du musicien varie lentement et linéairement dans le temps, on observe en général l'apparition du son lorsque la pression dans la bouche atteint une valeur, appelée seuil d’oscillation dynamique, supérieure au seuil d'oscillation statique. L'apport principal de ce travail est d'interpréter ce phénomène par la présence d'un retard à la bifurcation.L'approche analytique est privilégiée. La contribution majeure de ce doctorat est de comprendre les fondements de la théorie de la bifurcation dynamique afin d’étudier le retard à la bifurcation dans le modèle de clarinette dit "de Raman". Les propriétés du seuil dynamique d’oscillation sont ainsi reliées aux caractéristiques de la variation temporelle de la pression dans la bouche (sa valeur initiale et sa pente). L'une des caractéristiques notoires du retard à la bifurcation est sa grande dépendance au bruit, même s’il provient des erreurs d’arrondi de l’ordinateur. Les propriétés du seuil dynamique changent selon que le bruit peut être ignoré ou non.Nous montrons ensuite expérimentalement à l'aide d’une bouche artificielle et d'une clarinette de laboratoire que le retard à la bifurcation n'est pas qu'un phénomène numérique. Il est ainsi mis en évidence expérimentalement et ses propriétés sont également étudiés et comparées avec celles obtenues dans le cas numérique. / This research is a contribution to the study of attack transients in clarinet-like instruments. The main objective is to understand the behavior of the instrument when the mouth pressure is increased slowly through time at a constant rate.Although previous research proves that oscillations can appear at a value of the static oscillation threshold, numerical simulations and in vitro experiments show that for gradual increases of the mouth pressure, the audible sound generally appears when mouth pressure reaches a much higher value, called the dynamic oscillation threshold. This phenomenon is referred to as bifurcation delay in this work.A major part of this work follows an analytical approach, using the foundations of dynamic bifurcation theory to study the bifurcation delay in the simple "Raman" clarinet model. The properties of the dynamic oscillation threshold are related to indicators of the time variation of the mouth pressure such as its initial value and its slope. One of the remarkable features of the bifurcation delay is its strong dependence on noise, including that arising from round-off errors of the computer. The properties of the dynamic threshold are different according to whether the noise can be ignored or not.Additionally, an artificial mouth is used on a clarinet-like instrument to show that the bifurcation delay is not only a numerical phenomenon. Experimental observations performed on a clarinet-like instrument blown by an artificial mouth prove that bifurcation delay exists also on real-life systems. These observations show that the properties of the bifurcation delay observed in low-precision simulations are similar to experimental ones.
|
87 |
Enumerative and bijective aspects of combinatorial maps : generalization, unification and application / Aspects énumératifs et bijectifs des cartes combinatoires : généralisation, unification et applicationFang, Wenjie 11 October 2016 (has links)
Le sujet de cette thèse est l'étude énumérative des cartes combinatoires et ses applications à l'énumération des autres objet s combinatoires.Les cartes combinatoires, aussi appelées simplement « cartes », sont un modèle combinatoire riche. Elles sont définies d'une manière intuitive et géométrique, mais elles sont aussi liées à des structures algébriques plus complexes. Par exemple, l'étude d'une famille de cartes appelées des « constellations » donne un cadre unifié à plusieurs problèmes d'énumération des factorisations dans le groupe symétrique. À la croisée des différents domaines, les cartes peuvent être analysées par une grande variété de méthodes, et leur énumération peut aussi nous aider à compter des autres objets combinatoires. Cette thèse présente un ensemble de résultats et de connexions très riches dans le domaine de l'énumération des cartes. Cette thèse se divise en quatre grandes parties. La première partie, qui correspond aux chapitres 1 et 2, est une introduction à l'étude énumérative des cartes. La deuxième partie, qui correspond aux chapitres 3 et 4, contient mes travaux sur l'énumération des constellations, qui sont des cartes particulières présentant un modèle unifié de certains types de factorisation de l'identité dans le groupe symétrique. La troisième partie, qui correspond aux chapitres 5 et 6, présente ma recherche sur le lien énumératif entre les cartes et des autres objets combinatoires, par exemple les généralisations du treillis de Tamari et les graphes aléatoires qui peuvent être plongés dans une surface donnée. La dernière partie correspond au chapitre 7, dé ns lequel je conclus cette thèse avec des perspectives et des directions de recherche dans l'étude énumérative des cartes. / This thesis deals with the enumerative study of combinatorial maps, and its application to the enumeration of other combinatorial objects. Combinatorial maps, or simply maps, form a rich combinatorial model. They have an intuitive and geometric definition, but are also related to some deep algebraic structures. For instance, a special type of maps called \emph{constellations} provides a unifying framework for some enumeration problems concerning factorizations in the symmetric group. Standing on a position where many domains meet, maps can be studied using a large variety of methods, and their enumeration can also help us count other combinatorial objects. This thesis is a sampling from the rich results and connections in the enumeration of maps.This thesis is structured into four major parts. The first part, including Chapter 1 and 2, consist of an introduction to the enumerative study of maps. The second part, Chapter 3 and 4, contains my work in the enumeration of constellations, which are a special type of maps that can serve as a unifying model of some factorizations of die identity in the symmetric group: The third part, composed by Chapter 5 and 6, shows my research on the enumerative link from maps to other combinatori al objects, such as generalizations of the Tamari lattice and random graphs embeddable onto surfaces. The last part is the closing chapter, in which the thesis concludes with some perspectives and future directions in the enumerative study of maps.
|
88 |
Cartes aléatoires et serpent brownien / Random maps and Brownian snakeAbraham, Céline 11 December 2015 (has links)
La première partie de cette thèse s’inscrit dans le domaine des cartes aléatoires, qui est un sujet à la frontière des probabilités, de la combinatoire et de la physique statistique. Nos travaux complètent une série de résultats de convergence de différents modèles de cartes aléatoires vers la carte brownienne, qui est un espace métrique compact aléatoire. Plus précisément, on montre que la limite d’échelle d’une carte de loi uniforme sur l’ensemble des cartes biparties enracinées à n arêtes, munie de la distance de graphe renormalisée par (2n)^(−1/4), est, au sens de Gromov–Hausdorff, la carte brownienne. Pour prouver ce résultat, les arguments importants sont d’une part l’utilisation d’une bijection combinatoire entre cartes biparties et arbres multitypes, et d’autre part des théorèmes de convergence pour les arbres de Galton–Watson multitypes étiquetés. Dans un deuxième temps, le but est de présenter une théorie des excursions pour le mouvement brownien indexé par l’arbre brownien. De manière analogue à la théorie d’Itô des excursions pour le mouvement brownien, chaque excursion correspond à une composante connexe du complémentaire des zéros du mouvement brownien indexé par l’arbre, et l’excursion est définie comme un processus indexé par un arbre continu. On explique comment mesurer la longueur de la frontière de ces excursions, de sorte que la famille de ces longueurs coïncide avec les sauts d’un processus de branchement à temps continu de mécanisme de branchement stable d’indice 3/2. De plus, conditionnellement aux longueurs des frontières, les excursions sont indépendantes et leur loi conditionnelle est déterminée à l’aide d’une mesure d’excursion explicite que l’on introduit et décrit. Dans ce travail, le serpent brownien apparaît comme un outil particulièrement important. / The first part of this thesis concerns the area of random maps, which is a topic in between probability theory, combinatorics and statistical physics. Our work complements several results of convergence of various classes of random maps to the Brownian map, which is a random compact metric space. More precisely, we prove that the scaling limit of a map which is uniformly distributed over the class of rooted planar maps with n edges, equipped with the graph distance rescaled by (2n)^(−1/4), is, in the Gromov-Hausdorff sense, the Brownian map. To establish this result, the main arguments are the use of a combinatorial bijection between bipartite maps and multitype trees, together with convergence theorems for Galton-Watson multitype trees. We then aim to develop an excursion theory for Brownian motion indexed by the Brownian tree. Analogous to the Itô excursion theory for Brownian motion, each excursion corresponds to a connected component of the complement of the zero set of the tree-indexed Brownian motion, and the excursion is defined as a process indexed by a continuous tree. We explain how to measure the length of the boundary of these excursions, in a way that the collection of these lengths coincides with the collection of jumps of a continuous-state branching process with a 3/2-stable branching mechanism. Moreover, conditionally on the boundary lengths, the excursions are independent and their conditional distribution is determined in terms of an excursion measure that we introduce and study. In this work, the Brownian snake appears as a particularly important tool.
|
89 |
Analyse forensique de la mémoire des cartes à puce / Memory carving of smart cards memoriesGougeon, Thomas 04 October 2017 (has links)
Dans notre monde toujours plus connecté, les cartes à puce sont impliquées quotidiennementdans nos activités, que ce soit pour le paiement, le transport, le contrôle d’accès ou encore la santé.Ces cartes contiennent des informations personnelles liées aux faits et gestes de leur possesseur.Le besoin d’interpréter les données contenues dans les mémoires de ces cartes n’a jamais été aussiimportant. Cependant, sans les spécifications de l’application, il est difficile de connaître quellesinformations sont stockées dans la carte, leur emplacement précis, ou encore l’encodage utilisé.L’objectif de cette thèse est de proposer une méthode qui retrouve les informations stockéesdans les mémoires non volatile des cartes à puce. Ces informations peuvent être des dates (e.g.,date de naissance, date d’un événement) ou des informations textuelles (e.g., nom, adresse). Pourretrouver ces informations, un décodage exhaustif des données à l’aide de différentes fonctions dedécodage est possible. Malheureusement, cette technique génère de nombreux faux positifs. Unfaux positif apparaı̂t lorsqu’une fonction de décodage est appliquée sur des données qui ont étéencodées avec une fonction différente. Cette thèse s’appuie alors sur trois contributions exploitantles spécificités des cartes à puce pour éliminer ces faux positifs. La première contribution identifie lesobjets cryptographiques dans les mémoires non volatiles des cartes à puce afin de ne pas effectuer ledécodage sur ces données. Les deux autres contributions retrouvent respectivement des informationstextuelles et des dates dans ces mémoires. Afin de valider ces méthodes, elles sont chacune appliquéessur 371 mémoires de cartes à puce de la vie réelle. / In our increasingly connected world, smart cards are involved in any everyday activity, and theygather and record plenty of personal data. The need to interpret the raw data of smart card memoryhas never been stronger. However, without the knowledge of the specifications, it is difficult toretrieve what are the information stored, their location, and the encoding used to store them.The objective of this thesis is to propose a method retrieving the stored information in thenon-volatile memory of smart cards. This information include dates (e.g., birth date or event date)and textual information (e.g., name, address). In order to retrieve these information, it is possibleto perform an exhaustive decoding of the data with several decoding functions. Unfortunately,this technique generates a lot of false positives. Indeed, a false positive occurs when a decodingfunction is applied to data that have been encoded with another function. This thesis proposesthree contributions exploiting smart cards specificities to eliminate the false positives. The firstcontribution identifies cryptographic material in these non-volatile memories in order to preventthe false positives generated by the decoding of these cryptographic objects. The two otherscontributions retrieve respectively textual information and dates in these memories. In order tovalidate these methods, they are applied on 371 memory dumps of real-life smart cards.
|
90 |
Une promenade aléatoire entre combinatoire et mécanique statistique / A random hike between combinatorics and statistical mechanicsHuynh, Cong Bang 27 June 2019 (has links)
Cette thèse se situe à l'interface entre combinatoire et probabilités,et contribue à l'étude de différents modèles issus de la mécanique statistique : polymères, marches aléatoires inter-agissantes ou en milieu aléatoire, cartes aléatoires. Le premier modèle que nous étudions est une famille de mesures de probabilités sur les chemins auto-évitants de longueur infinie sur un réseau régulier, construites à partir de marches aléatoires biaisées sur l'arbre des chemins auto-évitants finis. Ces mesures, introduites par Beretti et Sokal, existent pour tout biais strictement supérieur à l'inverse de la constante de connectivité, et leur limite en ce biais critique serait l'un des définitions naturelles de la marche aléatoire uniforme en longueur infinie. Le but de ce travail, en collaboration avec Vincent Beffara, est de comprendre le lien entre cette limite, si elle existe, et d'autres chemins aléatoires notamment la mesure de Kesten (qui est la limite faible de la marche auto-évitante uniforme dans le demi-plan) et les interfaces de percolation de Bernoulli critique; d'une certaine façon le modèle constitue une interpolation entre les deux. Dans une deuxième partie, nous considérons des marches aléatoires en conductances aléatoires sur un arbre quelconque, dans le cas où la loi des conductances est à queue lourde. L’objectif de notre travail, en collaboration avec Andrea Collevecchio et Daniel Kious, est de montrer une transition de phase par rapport au paramètre de la queue; on exprime le paramètre critique comme une fonction explicite de l'arbre sous-jacent. Parallèlement, nous étudions des modèles de marches aléatoires excitées sur des arbres et leurs transitions de phase. En particulier, nous étendons une conjecture de Volkov et généralisons des résultats de Bas devant et Singh. Enfin, une troisième partie en collaboration avec Vincent Beffara et Benjamin Lévêque porte sur les cartes aléatoires en genre supérieur : nous montrons l'existence de limites d'échelle, le long de sous-suites, pour les triangulations simples uniformes sur le tore, étendant à ce cas les résultats d'Adario-Berri et Albenque (sur les triangulations simples de la sphère) et de Bettinelli (sur les quadrangulations du tore). La question de l'unicité de la limite et de son universalité restent ouvertes, mais nous obtenons des résultats partiels dans ce sens. / This thesis is at the interface between combinatorics and probability,and contributes to the study of a few models stemming from statisticalmechanics: polymers, self-interacting random walks and random walks inrandom environment, random maps.bigskipThe first model that we investigate is a one-parameter family ofprobability measures on self-avoiding paths of infinite length on aregular lattice, constructed from biased random walks on the tree offinite self-avoiding paths. These measures, initially introduced byBeretti and Sokal, exist for every bias larger than the inverseconnectivity constant, and their limit at the critical bias would beaamong the natural definitions of the uniform self-avoiding walk ofinfinite length. The aim of our work, in collaboration with VincentBeffara, is to understand the link between this limit, if it indeedexists, and other random infinite paths such as Kesten's measure(which is the weak limit of uniformly random finite self-avoidingwalks in the half-plane) and critical Bernoulli percolationinterfaces; the model can be seen as an interpolation between thesetwo.In a second part, we consider random walks with random conductances ona tree, in the case when the law of the conductances has heavy tail.Our aim, in collabration with Andrea Collevecchio and Daniel Kious, isto show a phase transition in the tail parameter; we express thecritical point as an explicit function of the underlying tree.In parallel, we study excited random walks on trees and their phasetransitions: we extend a conjecture of Volkov's and generalize resultsby Basdevant and Singh.Finally, a third part in collaboration with Vincent Beffara andBenjamin Lévêque contributes to the study of random maps of highergenus: we show the existence of subsequential scaling limits foruniformly random simple triangulations of the torus, extending to thatsetup fromer results by Adario-Berri and Albenque (on simpletriangulations of the sphere) and by Bettinelli (on quadrangulationsof the torus). The question of uniqueness and universality of thelimit remain open, but we obtain partial results in that direction.
|
Page generated in 0.0295 seconds