Séminaire ALGO, Florian Bridoux (LIS, Université Aix-Marseille) : « Réseaux d’automates expansifs »
Sciences 3- S3 351Résumé : An Automata Network is a map f:Qn→Qn where Q is a finite alphabet. It can be viewed as a network of n entities, each holding a state from Q, and evolving according to a deterministic synchronous update rule in such a way that each entity only depends on its neighbors in the network's … Continue reading Séminaire ALGO, Florian Bridoux (LIS, Université Aix-Marseille) : « Réseaux d’automates expansifs »
Séminaire ALGO : Vincent Botbol (Nomadic labs.), Matthieu Dien (GREYC) et Ghiles Ziat (IRIF, Univ. Paris), « Génération de tests aléatoires pour des types numériques contraints ».
Sciences 3- S3 351Il est fréquent de manipuler des valeurs numériques avec des contraintes non explicitées par leur types. Par exemple, les intervalles sont des couples de nombres avec la contraintes que le premier (la borne inférieure) soit plus petit que le deuxième (borne supérieure). Nos travaux proposent de générer automatiquement des tests unitaires pour à partir de … Continue reading Séminaire ALGO : Vincent Botbol (Nomadic labs.), Matthieu Dien (GREYC) et Ghiles Ziat (IRIF, Univ. Paris), « Génération de tests aléatoires pour des types numériques contraints ».
Benoit Barbot (LACL, Univ. Paris Est Créteil) : « Sampling uniforme de langage d’automate temporisé »
Sciences 3- S3 351Résumé : In this work we develop Monte-Carlo model checking techniques to evaluate quantitative properties of timed languages. Our approach is based on uniform random sampling of behaviors, as opposed to isotropic sampling that chooses the next step uniformly at random. The uniformity is defined with respect to volume measure of timed languages previously studied … Continue reading Benoit Barbot (LACL, Univ. Paris Est Créteil) : « Sampling uniforme de langage d’automate temporisé »
Séminaire ALGO : Benjamin Hellouin (LRI, Univ. Paris Sud), « Comportement asymptotique de l’automate cyclique à 3 états »
Sciences 3- S3 351La dominance cyclique est un phénomène où différents états (espèces, stratégies...) sont dans une relation cyclique de proie à prédateur : A mange B mange C mange A. Il s'agit d'une situation classique dans des systèmes écologiques réels, en théorie évolutionnaire des jeux, etc. Simuler la dominance cyclique avec des modèles de type Lotka-Volterra fait … Continue reading Séminaire ALGO : Benjamin Hellouin (LRI, Univ. Paris Sud), « Comportement asymptotique de l’automate cyclique à 3 états »
Séminaire ALGO : Léo Pavlet Salomon (GREYC), « Groupe fondamental et pavages du plan: quelques constructions ».
Sciences 3- S3 351Résumé : On appelle sous-shift (ou sous-décalage) un ensemble de pavages ou de coloriages du plan respectant certaines contraintes locales. Historiquement introduits comme discrétisations de systèmes dynamiques continus, on se propose ici d'en étudier un invariant topologique, introduit par W.Geller et J.Propp, le Groupe Fondamental Projectif. A l'instar de la définition habituelle du groupe fondamental, … Continue reading Séminaire ALGO : Léo Pavlet Salomon (GREYC), « Groupe fondamental et pavages du plan: quelques constructions ».
Séminaire ALGO : Olivier Bournez (LIX, Ecole Polytechnique), « Computing with analog models. Computing with ordinary differential equations ».
Abstract : Differential equations is some universal language in many contexts, and in particular in experimental sciences. Motivated initially by analog models of computation, we will review various results demonstrating that it is possible to program with ordinary differential equations, or their discrete counterpart, discrete differences. We will show that several concepts from computability and … Continue reading Séminaire ALGO : Olivier Bournez (LIX, Ecole Polytechnique), « Computing with analog models. Computing with ordinary differential equations ».
Séminaire ALGO : Ionona Ranaivoson (GREYC) « Les graphes série-parallèles scrutés à travers des trous ».
Sciences 3- S3 351Résumé : Idée directrice : certains problèmes sur un graphe pourraient être facilités par la connaissance de relations d’adjacence entre des cycles de ce graphe. Mais, le nombre de cycle d’un graphe G étant, en général, exponentiel par rapport à sa taille, nous allons plutôt étudier des relations d’adjacence entre les éléments de bases particulières de … Continue reading Séminaire ALGO : Ionona Ranaivoson (GREYC) « Les graphes série-parallèles scrutés à travers des trous ».
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 »