Un origami, ou encore une surface à petits carreaux, est l'exemple le plus simple d'une surface de translation. Il s'obtient en collant entre eux un nombre fini de carreaux identiques. Le point le plus intéressant est l'étude du flot linéaire sur un origami, qui est un système dynamique continu lié à la dynamique des billards ou encore celle des échanges d'intervalles. Nous pouvons aussi nous intéresser au stabilisateur de l'action naturelle du groupe spécial linéaire sur les origamis, que nous appelons groupe de Veech de l'origami. Le but de cette thèse est l'étude de ces deux notions sur des exemples d'origamis infinis, obtenus en collant une infinité dénombrable de carreaux entre eux. Ces exemples sont obtenus comme revêtement galoisiens d'origamis finis, avec comme groupe de Galois des groupes abéliens, nilpotents ou plus compliqués. / An origami, or a square-tiled surface, is the simplest example of translation surface. An origami can be viewed as a finite collection of identical squares, glued together along their edges. We can study the linear flow on this origami, which is the geodesic flow for this kind of surfaces. This dynamical system is related to the dynamical system of billiard, or interval exchange transformations. We can also study the Veech group of an origami. The special linear group acts on the space of translation surface, and the Veech group of an origami is the stabilizer of this origami under this action. We know in particular that the Veech group is a fuchsian group. In this thesis, we work on some example of infinite origamis. These origamis are constructed as Galois covering of finite origamis. In these examples, the deck group will be an abelian group, a niltpotent group or something more difficult.

La sécurité des transmissions et du stockage des données est devenue un enjeu majeur de ces dernières années et la cryptologie, qui traite de la protection algorithmique de l'information, est un sujet de recherche extrêmement actif. Elle englobe la conception d'algorithmes cryptographiques, appelée cryptographie, et l'analyse de leur sécurité, appelée cryptanalyse.Dans cette thèse, nous nous concentrons uniquement sur la cryptanalyse, et en particulier celle des algorithmes de chiffrement symétrique, qui reposent sur le partage d'un même secret entre l'entité qui chiffre l'information et celle qui la déchiffre. Dans ce manuscrit, trois attaques contre des algorithmes de chiffrement symétriques sont présentées. Les deux premières portent sur deux candidats de l'actuelle compétition cryptographique CAESAR, les algorithmes AEZ et NORX, tandis que la dernière porte sur l'algorithme Kravatte, une instance de la construction Farfalle qui utilise la permutation de la fonction de hachage décrite dans le standard SHA-3. Les trois algorithmes étudiés présentent une stratégie de conception similaire, qui consiste à intégrer dans une construction nouvelle une primitive, i.e. une fonction cryptographique élémentaire, déjà existante ou directement inspirée de travaux précédents.La compétition CAESAR, qui a débuté en 2015, a pour but de définir un portefeuille d'algorithmes recommandés pour le chiffrement authentifié. Les deux candidats étudiés, AEZ et NORX, sont deux algorithmes qui ont atteint le troisième tour de cette compétition. Les deux attaques présentées ici ont contribué à l'effort de cryptanalyse nécessaire dans une telle compétition. Cet effort n'a, en l'occurrence, pas permis d'établir une confiance suffisante pour justifier la présence des algorithmes AEZ et NORX parmi les finalistes.AEZ est une construction reposant sur la primitive AES, dont l'un des principaux objectifs est d'offrir une résistance optimale à des scénarios d'attaque plus permissifs que ceux généralement considérés pour les algorithmes de chiffrement authentifié. Nous montrons ici que dans de tels scénarios il est possible, avec une probabilité anormalement élevée, de retrouver l'ensemble des secrets utilisés dans l'algorithme.NORX est un algorithme de chiffrement authentifié qui repose sur une variante de la construction dite en éponge employée par exemple dans la fonction de hachage Keccak. Sa permutation interne est inspirée de celles utilisées dans BLAKE et ChaCha. Nous montrons qu'il est possible d'exploiter une propriété structurelle de cette permutation afin de récupérer la clé secrète utilisée. Pour cela, nous tirons parti du choix des concepteurs de réduire les marges de sécurité dans le dimensionnement de la construction en éponge.Enfin, la dernière cryptanalyse remet en cause la robustesse de l'algorithme Kravatte, une fonction pseudo-aléatoire qui autorise des entrées et sorties de taille variable. Dérivée de la permutation Keccak-p de SHA-3 au moyen de la construction Farfalle, Kravatte est efficace et parallélisable. Ici, nous exploitons le faible degré algébrique de la permutation interne pour mettre au jour trois attaques par recouvrement de clé : une attaque différentielle d'ordre supérieur, une attaque algébrique "par le milieu" et une attaque inspirée de la cryptanalyse de certains algorithmes de chiffrement à flot. / Nowadays, cryptology is heavily used to protect stored and transmitted data against malicious attacks, by means of security algorithms. Cryptology comprises cryptography, the design of these algorithms, and cryptanalysis, the analysis of their security.In this thesis, we focus on the cryptanalysis of symmetric encryption algorithms, that is cryptographic algorithms that rely on a secret value shared beforehand between two parties to ensure both encryption and decryption. We present three attacks against symmetric encryption algorithms. The first two cryptanalyses target two high profile candidates of the CAESAR cryptographic competition, the AEZ and NORX algorithms, while the last one targets the Kravatte algorithm, an instance of the Farfalle construction based on the Keccak permutation. Farfalle is multipurpose a pseudo-random function (PRF) developed by the same designers' team as the permutation Keccak used in the SHA-3 hash function.The CAESAR competition, that began in 2015, aims at selecting a portfolio of algorithms recommended for authenticated encryption. The two candidates analysed, AEZ and NORX, reached the third round of the CAESAR competition but were not selected to be part of the finalists. These two results contributed to the cryptanalysis effort required in such a competition. This effort did not establish enough confidence to justify that AEZ and NORX accede to the final round of the competition.AEZ is a construction based on the AES primitive, that aims at offering an optimal resistance against more permissive attack scenarios than those usually considered for authenticated encryption algorithms. We show here that one can recover all the secret material used in AEZ with an abnormal success probability.NORX is an authenticated encryption algorithm based on a variant of the so-called sponge construction used for instance in the SHA-3 hash function. The internal permutation is inspired from the one of BLAKE and ChaCha. We show that one can leverage a strong structural property of this permutation to recover the secret key, thanks to the designers' non-conservative choice of reducing the security margin in the sponge construction.Finally, the last cryptanalysis reconsiders the robustness of the Kravatte algorithm. Kravatte is an efficient and parallelizable PRF with input and output of variable length. In this analysis, we exploit the low algebraic degree of the permutation Keccak used in Kravatte to mount three key-recovery attacks targeting different parts of the construction: a higher order differential attack, an algebraic meet-in-the-middle attack and an attack based on a linear recurrence distinguisher.

Nous étudions dans ce travail les mouvements de foule intervenant dans les situa- tions d’urgence. Nous proposons un modèle macroscopique (la foule est représentée par une densité de personnes) obéissant à deux principes très simples. Tout d’abord, chaque personne possède une vitesse souhaitée (typiquement celle qui la mène vers la sortie), qu’elle adopterait en l’absence des autres. Ensuite, la foule doit respecter une contrainte de congestion, et la densité de personnes doit rester inférieure à une valeur fixée. Cette contrainte impose une vitesse de déplacement différente de la vitesse souhaitée. Nous choisissons de prendre comme vitesse réelle celle qui est la plus proche, au sens des moindres carrés, de la vitesse souhaitée, parmi les champs de vitesses admissibles, au sens où ils respectent la contrainte de densité maximale. Le modèle obtenu s’écrit sous la forme d’une équation de transport impliquant une vitesse peu régulière a priori, et qui ne peut être étudiée par des méthodes classiques. Nous démontrons un résultat d’existence grâce à la théorie du transport optimal, tout d’abord dans le cas d’une vitesse donnée comme le gradient d’une fonction, puis dans le cas général. Nous mettons également en œuvre un schéma numérique de type catching-up : à chaque pas de temps, la densité est déplacée selon le champ de vitesse souhaitée, puis est projetée sur l’ensemble des densités admissibles. Les résultats obtenus fournissent des temps d’évacuation dont l’ordre de grandeur est proche de la réalité. / In this work, we aim at modelling crowd motion in emergency situations. We propose a macroscopic model (where people are represented as a density) following two basic principles. First, each individual has a spontaneous velocity (typically, the one which leads to the nearest exit) which would be fulfilled in the absence of other people. On the other hand, the crowd has to respect a congestion constraint, and its density must remain underneath a critical density. This constraint prevents people from following their desired velocity. The actual velocity we consider is the closest, in a mean square sense, to the desired one, among the velocities which respect the maximal density constraint.The mathematical formulation writes as a transport equation which cannot be studied with classical methods, since the real velocity field has no a priori regularity, even if the desired velocity is smooth. Thanks to the optimal transport theory, we prove an existence result, first in the case where the desired velocity is the gradient of a given function, and then in the general framework. We also propose a numerical scheme which follows the catching-up principle: at each time step, we move the density according to the spontaneous velocity, and then project it onto the space of admissible densities. The numerical results we obtain reproduce qualitatively the experimental observations

Cette thèse porte en premier lieu sur l'analyse et le désassemblage de programmes malveillants utilisant certaines techniques d'obscurcissement telles que l'auto-modification et le chevauchement de code. Les programmes malveillants trouvés dans la pratique utilisent massivement l'auto-modification pour cacher leur code utile à un analyste. Nous proposons une technique d'analyse hybride qui utilise une trace d'exécution déterminée par analyse dynamique. Cette analyse découpe le programme auto-modifiant en plusieurs sous-parties non auto-modifiantes que nous pouvons alors étudier par analyse statique en utilisant la trace comme guide. Cette seconde analyse contourne d'autres techniques de protection comme le chevauchement de code afin de reconstruire le graphe de flot de contrôle du binaire analysé. Nous étudions également un détecteur de programmes malveillants, fonctionnant par analyse morphologique : il compare les graphes de flot de contrôle d'un programme à analyser à ceux de programmes connus comme malveillants. Nous proposons une formalisation de ce problème de comparaison de graphes, des algorithmes permettant de le résoudre efficacement et détaillons des cas concrets d'application à la détection de similarités logicielles / This dissertation explores tactics for analysis and disassembly of malwares using some obfuscation techniques such as self-modification and code overlapping. Most malwares found in the wild use self-modification in order to hide their payload from an analyst. We propose an hybrid analysis which uses an execution trace derived from a dynamic analysis. This analysis cuts the self-modifying binary into several non self-modifying parts that we can examine through a static analysis using the trace as a guide. This second analysis circumvents more protection techniques such as code overlapping in order to recover the control flow graph of the studied binary. Moreover we review a morphological malware detector which compares the control flow graph of the studied binary against those of known malwares. We provide a formalization of this graph comparison problem along with efficient algorithms that solve it and a use case in the software similarity field

Nous présentons dans ce manuscrit les méthodes développées et les résultats obtenus dans notre travail de thèse sur l'analyse du contenu dynamique de scène visuelle. Nous avons considéré la configuration la plus fréquente de vision par ordinateur, à savoir caméra monoculaire et vidéos naturelles de scène extérieure. Nous nous concentrons sur des problèmes importants généraux pour la vision par ordinateur et d'un intérêt particulier pour l'industrie cinématographique, dans le cadre de la post-production vidéo. Les problèmes abordés peuvent être regroupés en deux catégories principales, en fonction d'une interaction ou non avec les utilisateurs : l'analyse interactive du contenu vidéo et l'analyse vidéo entièrement automatique. Cette division est un peu schématique, mais elle est en fait liée aux façons dont les méthodes proposées sont utilisées en post-production vidéo. Ces deux grandes approches correspondent aux deux parties principales qui forment ce manuscrit, qui sont ensuite subdivisées en chapitres présentant les différentes méthodes que nous avons proposées. Néanmoins, un fil conducteur fort relie toutes nos contributions. Il s'agit d'une analyse hiérarchique compositionnelle du mouvement dans les scènes dynamiques. Nous motivons et expliquons nos travaux selon l'organisation du manuscrit résumée ci-dessous. Nous partons de l'hypothèse fondamentale de la présence d'une structure hiérarchique de mouvement dans la scène observée, avec un objectif de compréhension de la scène dynamique. Cette hypothèse s'inspire d'un grand nombre de recherches scientifiques sur la vision biologique et cognitive. Plus précisément, nous nous référons à la recherche sur la vision biologique qui a établi la présence d'unités sensorielles liées au mouvement dans le cortex visuel. La découverte de ces unités cérébrales spécialisées a motivé les chercheurs en vision cognitive à étudier comment la locomotion des animaux (évitement des obstacles, planification des chemins, localisation automatique) et d'autres tâches de niveau supérieur sont directement influencées par les perceptions liées aux mouvements. Fait intéressant, les réponses perceptuelles qui se déroulent dans le cortex visuel sont activées non seulement par le mouvement lui-même, mais par des occlusions, des désocclusions, une composition des mouvements et des contours mobiles. En outre, la vision cognitive a relié la capacité du cerveau à appréhender la nature compositionnelle du mouvement dans l'information visuelle à une compréhension de la scène de haut niveau, comme la segmentation et la reconnaissance d'objets. / The manuscript that is presented here contains all the findings and conclusions of the carried research in dynamic visual scene analysis. To be precise, we consider the ubiquitous monocular camera computer vision set-up, and the natural unconstrained videos that can be produced by it. In particular, we focus on important problems that are of general interest for the computer vision literature, and of special interest for the film industry, in the context of the video post-production pipeline. The tackled problems can be grouped in two main categories, according to the whether they are driven user interaction or not : user-assisted video processing tools and unsupervised tools for video analysis. This division is rather synthetic but it is in fact related to the ways the proposed methods are used inside the video post-production pipeline. These groups correspond to the main parts that form this manuscript, which are subsequently formed by chapters that explain our proposed methods. However, a single thread ties together all of our findings. This is, a hierarchical analysis of motion composition in dynamic scenes. We explain our exact contributions, together with our main motivations, and results in the following sections. We depart from a hypothesis that links the ability to consider a hierarchical structure of scene motion, with a deeper level of dynamic scene understanding. This hypothesis is inspired by plethora of scientific research in biological and psychological vision. More specifically, we refer to the biological vision research that established the presence of motion-related sensory units in the visual cortex. The discovery of these specialized brain units motivated psychological vision researchers to investigate how animal locomotion (obstacle avoidance, path planning, self-localization) and other higher-level tasks are directly influenced by motion-related percepts. Interestingly, the perceptual responses that take place in the visual cortex are activated not only by motion itself, but by occlusions, dis-occlusions, motion composition, and moving edges. Furthermore, psychological vision have linked the brain's ability to understand motion composition from visual information to high level scene understanding like object segmentation and recognition.

L'objet de cette thèse est l'étude d'un problème d'ordonnancement, dont le critère d'optimisation est la minimisation du nombre total de changements d'outils sur une machine flexible. Différents problèmes liés à l'outillage et pouvant constituer un obstacle au fonctionnement d'un atelier flexible sont brièvement examinés, (de la gestion de l'inventaire aux changements d'outils). Nous nous concentrons ensuite sur le problème d'ordonnancement avec gestion d'outils sur une seule machine: ce problème est NP-complet. Un premier aspect qui est la gestion off-line des outils est étudié: différents modèles sont proposés pour la minimisation des changements en fonction d'une séquence des tâches donnée. Dans ce cas, le problème est polynomial. Nous revenons ensuite au problème d'ordonnancement proprement dit, pour lequel plusieurs types de méthodes heuristiques sont décrites et comparées. La seconde partie du travail est consacrée à la gestion on-line des changements d'outils; elle se compose de deux chapitres: dans le premier, le modèle que nous allons utiliser est décrit en détail. Il s'agit de la modélisation des problèmes de k-serveurs. Le principe peut être résumé comme suit: sur un réseau de n clients potentiels, on dispose de k serveurs mobiles, avec lesquels on doit répondre on-line aux demandes unitaires et successives des clients, tout en optimisant les déplacements des serveurs. Ce problème est en étroite relation avec la gestion des mémoires en informatique. Dans le dernier chapitre, le modèle des k-serveurs «classique» est généralisé aux problèmes avec service par blocs de demandes, ce qui permet d'adapter l'algorithme de partitionnement, (fortement compétitif pour le service unitaire), au cas plus général des demandes groupées. Cet algorithme dont nous étudions les propriétés et la compétitivité est applicable à la gestion on-line des changements d'outils. Il sert de base à la construction d'une heuristique d'ordonnancement avec gestion d'outils. Cette dernière méthode se révèle très efficace comparée aux précédentes

.

Le langage est conçu de manière à permettre une interprétation synchrone des suites. La nature du langage (dont la sémantique s'exprime simplement) permet des manipulations formelles sur les programmes dans le but de faire des vérifications et des preuves de correction. Des exemples illustrent l'utilisation du langage pour la programmation de systèmes temporisés pris dans différents domaines (temps réel classique, automatique, systolique, spécification et conception des circuits)

Introduction. Couvertures des graphes par des cycles. Couverture par des circuits d'un matroïde régulier qui admet un Z.5- flot non nul. Flots de Fulkerson. Flots de Petersen. Constructions locales. Annexe. Bibliographie

Les collisions d'ions lourds ultrarelativistes, dont le but est la formation et l'étude du plasma de quarks et de gluons, recouvrent un<br />vaste domaine de la physique nucléaire et des hautes énergies. Nombreuses sont les observables proposées comme signature de la<br />formation du plasma de quarks et de gluons. Dans mon travail de thèse, je me suis penchée sur deux d'entre elles: la suppression du <br />J/Psi et les effets collectifs ou de ``flot''. <br /><br />Dans cet exposé, je ne discuterai que du flot, ce dernier occupant la majeure partie de ma thèse. Après avoir présenté la problématique<br />de l'analyse de flot, je montrerai les limitations méthodes ``standard'' utilisées depuis 1985, notamment sur les données publiées en<br />1998 par la collaboration NA49 du CERN. J'exposerai alors une nouvelle méthode d'analyse se basant sur un développement en<br />cumulants des corrélations azimutales multiples. Cette méthode non seulement généralise la méthode standard mais également permet<br />des mesures de flot plus fines, là où les méthodes conventionnelles échouent. Je présenterai enfin mes résultats sur l'analyse des<br />nouvelles données de NA49.