100, rue des maths 38610 Gières / GPS : 45.193055, 5.772076 / Directeur : Louis Funar

Jeu et complexité : une variante PSPACE-Dur du jeu de Nim.

Mercredi, 2 Octobre, 2013 - 16:30
Prénom de l'orateur : 
Simon
Nom de l'orateur : 
Schmidt
Résumé : 

Nous commencerons par présenter la notion de complexité pour les jeux combinatoires à deux joueurs. Quels sont les points communs et les divergences entre cette notion et celle, plus connue, de complexité pour les problèmes de décisions? Nous présenterons ensuite plusieurs version du jeu de Nim sur les graphes, et nous montrerons que dans la plus part des cas elles sont PSPACE-Dur. Cependant, en nous restreignant aux graphes bipartis, nous serons capables, en utilisant les couplages, de déterminer efficacement si une position et gagnante ou perdante.

Et toujours, la page du séminaire : http://www-fourier.ujf-grenoble.fr/~magotjm/seminaire_comprehensible/

Institution de l'orateur : 
Institut Fourier
Thème de recherche : 
Compréhensible
Salle : 
04
logo uga logo cnrs