Séminaire ALGO : Marin Gohard (CREM, Univ. Caen) « Les règles de vote multi gagnants : Une proximité axiomatique est-elle liée à des résultats similaires ? »
Les règles de votes multi gagnants ont de multiples applications (1er tour d'élection, concours de différentes sortes, choix de produits à promouvoir pour une entreprise...). Elles sont cependant moins étudiées que les règles qui n'élisent qu'un gagnant. En partant de l'étude axiomatique de certaines de ces règles, nous nous sommes interrogés sur la similarité des … Continue reading Séminaire ALGO : Marin Gohard (CREM, Univ. Caen) « Les règles de vote multi gagnants : Une proximité axiomatique est-elle liée à des résultats similaires ? »
Séminaire ALGO : Ionona Ranaivoson (GREYC) « Isomorphisme de sous-graphes (SubIso) des graphes séries-parallèles (SP-graphes) et couvertures par trous »
Sciences 3- S3 351On s’intéresse au problème SubIso: étant donnés deux graphes non orientés G et H, déterminer si G contient un sous-graphe qui est isomorphe à H. Le problème SubIso est NP-complet en général. Mais des algorithmes polynomiaux de SubIso existent pour les graphes extra-planaires biconnexes (en O(n3) par ) et pour les SP-graphes biconnexes (en O(n6.5) … Continue reading Séminaire ALGO : Ionona Ranaivoson (GREYC) « Isomorphisme de sous-graphes (SubIso) des graphes séries-parallèles (SP-graphes) et couvertures par trous »
Séminaire Algo Victor Luftalla (GREYC, Université de Caen), « Les pavages de Penrose par losanges »
Sciences 3- S3 351Les pavages de Penrose sont une famille de pavages par losanges qui a été définie en 1974 par Roger Penrose. Je vais présenter les propriétés de cette famille et expliquer pourquoi 50 ans après on travaille toujours sur cette famille de pavages et ses généralisations. Au menu : apériodicité, symétries, substitution, règles locales, plans discrets … Continue reading Séminaire Algo Victor Luftalla (GREYC, Université de Caen), « Les pavages de Penrose par losanges »
Séminaire Algo : Rémi Pallen (ENS Paris Saclay) « Comment le lambda-calcul typé peut-il nous assurer que nos données personnelles ne fuiront pas ? »
Sciences 3- S3 351De nos jours, de nombreuses études publient des données sur des bases de données sensibles, mais comment s'assurer qu'elles ne dévoilent pas d'informations sur des individus pris séparément ? Nous allons voir comment nous pouvons concevoir un lambda-calcul dont les fonctions bien typées ne dévoilent aucune information (ou très peu) sur un individu en particulier.
Séminaire Algo : Corentin Jeudy (Orange Labs, Rennes) « Vers la Difficulté de « Module Learning With Errors » avec Distributions Courtes »
Sciences 3- S3 351Le problème "Module Learning With Errors" (M-LWE) est une hypothèse calculatoire fondamentale en cryptographie sur les réseaux Euclidiens qui offre un compromis intéressant entre efficacité et sécurité des cryptosystèmes qui en résultent. Ce problème est paramétré par une distribution de secret ainsi qu'une distribution d'erreur. Il y a encore aujourd'hui un fossé entre le choix … Continue reading Séminaire Algo : Corentin Jeudy (Orange Labs, Rennes) « Vers la Difficulté de « Module Learning With Errors » avec Distributions Courtes »
Séminaire Algo : Brigitte Vallée (GREYC, Caen) « Variations autour du modèle des VLMC (= Variable Length Markov Chains) »
Sciences 3- S3 351Je commencerai par quelques rappels sur les processus généraux qui produisent des mots, appelés sources, leurs séries génératrices, leur entropie et leur poids de Shannon. Je mentionnerai les sources simples (les sources sans mémoire, les chaînes de Markov). Puis, j’introduirai le modèle des VLMC (= Variable Length Markov Chains) qui se situe juste « au-dessus … Continue reading Séminaire Algo : Brigitte Vallée (GREYC, Caen) « Variations autour du modèle des VLMC (= Variable Length Markov Chains) »
SÉMINAIRE ALGO : Justine Reynaud (GREYC, Caen) « Analyse de Concepts Formels et découverte de Redescriptions – une application au web des données »
Sciences 3- S3 351Dans un premier temps, je présenterai l'Analyse de Concepts Formels (FCA -- Formal Concept Analysis) qui est le cadre théorique sur lequel je m'appuie pour faire de la fouille de données. Intuitivement, il s'agit de considérer un ensemble d'objets G, un ensemble d'attributs M, et une relation binaire I ⊆ G×M où gIm s'interprète comme "l'objet g … Continue reading SÉMINAIRE ALGO : Justine Reynaud (GREYC, Caen) « Analyse de Concepts Formels et découverte de Redescriptions – une application au web des données »
SÉMINAIRE ALGO : Daria Pchelina (LIPN, Univ. Paris 13) « Densité des empilements de sphères : des pièces de monnaie aux oranges »
Sciences 3- S3 351Comment empiler un nombre infini d’oranges pour maximiser la proportion de l’espace couvert ? Kepler a conjecturé que l’empilement des “balles de canon” est optimal. 400 ans se sont écoulés avant que cette conjecture soit démontrée par Hales et Ferguson dont la preuve comporte 6 papiers et plus de 50000 lignes de code. Comment arranger … Continue reading SÉMINAIRE ALGO : Daria Pchelina (LIPN, Univ. Paris 13) « Densité des empilements de sphères : des pièces de monnaie aux oranges »
Séminaire Algo : Adeline Roux-Langlois (GREYC, Caen) « Introduction to lattice based cryptography »
Sciences 3- S3 351The goal of cryptography is to safely communicate, and it is widely used when connecting to a website or during a banking transaction for example. But some cryptographic constructions used today could be attacked given a powerful enough quantum computer. Even if such a computer does not exist yet, it is important to anticipate its … Continue reading Séminaire Algo : Adeline Roux-Langlois (GREYC, Caen) « Introduction to lattice based cryptography »
Séminaire Algo : Théo Grente (FEM: France Energies Marines) « Étude de propriété des automates cellulaires en utilisant les bases de Groebner »
Sciences 3- S3 351Dans cet exposé je présenterai une méthode utilisant les bases de Groebner pour rechercher des automates cellulaires (AC) ayant une propriété donnée. Cette méthode a d’abord été conçue pour concevoir des équations différentielles partielles (PDE) intéressantes à partir d’AC. Pour faire le lien entre le comportement discret des AC et le comportement continu des PDE, … Continue reading Séminaire Algo : Théo Grente (FEM: France Energies Marines) « Étude de propriété des automates cellulaires en utilisant les bases de Groebner »
Séminaire Algo : Andrea Lesavourey (IRISA, Rennes) « Recherche d’éléments courts dans les réseaux idéaux »
Sciences 3- S3 351Dans la recherche actuelle de primitives pouvant résister à l’utilisation d’un ordinateur quantique, une des pistes majeure se base sur les réseaux euclidiens, et, en particulier, sur le problème Learning With Errors (LWE). En effet, il existe une réduction pire cas - moyen cas vers le problème classique de réseaux qu’est le Shortest Vector Problem … Continue reading Séminaire Algo : Andrea Lesavourey (IRISA, Rennes) « Recherche d’éléments courts dans les réseaux idéaux »
Séminaire Algorithmique : Florent Koechlin (LORIA, Nancy) « Two new criteria to prove the inherent ambiguity of bounded context-free languages »
Sciences 3- S3 351A context-free language is inherently ambiguous if any grammar that recognizes it is ambiguous, i.e. there exists a word that is generated in two different ways. Deciding the inherent ambiguity of a context-free language is a difficult problem, undecidable in general. The first examples of inherently ambiguous languages were discovered in the 1960s, using iteration … Continue reading Séminaire Algorithmique : Florent Koechlin (LORIA, Nancy) « Two new criteria to prove the inherent ambiguity of bounded context-free languages »