Séminaire ALGO : Sergej Scheck (GREYC), Knowledge Compilation for Action Languages
Sciences 3- S3 351Abstract : Computational efficiency of a planner in automated planning depends among other things on the formal representation of actions. This motivates the study of the relative succinctness and complexity of queries for languages that can be used to represent actions. We are going to investigate variants of two most common representations, namely the boolean … Continue reading Séminaire ALGO : Sergej Scheck (GREYC), Knowledge Compilation for Action Languages
Séminaire ALGO, Antonin Callard : « Entropies et entropies de surfaces des sous-shifts 2D »
Les sous-shifts 2D sont les ensembles de coloriages du plan $Z^2$, par un nombre fini de couleurs, et qui sont définis par des familles de motifs interdits. Les sous-shifts sont une classe de systèmes dynamiques qui profitent d'un lien étroit avec la calculabilité : d'abord un obstacle (indécidabilité du problème du domino), la calculabilité est … Continue reading Séminaire ALGO, Antonin Callard : « Entropies et entropies de surfaces des sous-shifts 2D »
Séminaire ALGO : Romain Lecoq
Sciences 3- S3 351A remplir.
Séminaire ALGO, Julien David : « Une nouvelle approche pour l’analyse d’algorithme. »
Résumé: L'étude théorique des algorithmes est très souvent limitée à l'analyse de la complexité dans le pire des cas. Il existe pourtant de nombreuses notions de complexité qui apportent des informations essentielles à la bonne compréhension de l'efficacité des algorithmes. Parmi celles-ci, la complexité en moyenne consiste à supposer une distribution de probabilité sur les … Continue reading Séminaire ALGO, Julien David : « Une nouvelle approche pour l’analyse d’algorithme. »
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 ».