Les lundis, à partir de 14h - UPEC CMC - Salle P2-131

20 avril 2020

TBA

Arnaud de Mesmay (LIGM)

TBA

23 mars 2020

TBA

Barnaby Martin (Durham)

TBA

2 mars 2020

Un algorithme stochastique pour résoudre les jeux stochastique simples

David Auger (Université de Versailles)

Après avoir présenté des généralités concernant les jeux stochastiques simples (qui sont des chaînes de Markov où deux adversaires peuvent contrôler certains sommets), nous feront en particulier l’état en ce qui concerne les algorithmes de résolution de ces jeux, en regardant en particulier les algorithmes d’itération de stratégies. Enfin, nous présenterons un algorithme stochastique, qui améliore l’état de l’art, ayant une complexité paramétrée par le nombre de nœuds aléatoires du graphe.

24 février 2020

Décider (ℝ,+,<,1) dans (ℝ,+,<,ℤ)

Alexis Bes (LACL - UPEC)

La structure (R,+,<,Z), où R désigne l’ensemble des réels et Z le prédicat unaire “être un entier”, admet l’élimination des quantificateurs et est décidable. Elle intervient notamment dans le domaine de la spécification et la vérification de systèmes hybrides. Elle peut être étudiée via les automates, en considérant des automates de Büchi qui lisent des réels représentés dans une base entière fixée. Boigelot et al. ont démontré en particulier que la classe des relations définissables dans (R,+,<,Z) coïncide avec celle des relations reconnaissables par automate en toute base. Une autre structure intéressante est (R,+,<,1), qui est moins expressive que (R,+,<,Z) mais définit les mêmes relations bornées. On présente une caractérisation topologique des relations définissables dans (R,+,<,Z) qui sont définissables dans (R,+,<,1), et on en déduit que le problème de savoir si une relation définissable dans (R,+,<,Z) est définissable dans (R,+,<,1) est décidable.
Travail en commun avec Christian Choffrut.

3 février 2020

Network Inference: Graph reconstruction and verification

Hang Zhou (LIX - Polytechnique)

How efficiently can we find an unknown graph using shortest path queries between its vertices? This is a natural theoretical question from the standpoint of recovery of hidden information. This question is related to discovering the topology of Internet networks, which is a crucial step for building accurate network models and designing efficient algorithms for Internet applications.

In this talk, I will introduce the problems of graph reconstruction and verification via oracles. I will investigate randomized algorithms based on a Voronoi cell decomposition. I will also analyze greedy algorithms, and prove that they are near-optimal.

The talk is based on joint work with Claire Mathieu and Sampath Kannan.