Activité "Progression dans un graphe dirigé."

DISPONIBLE

Découvrez un jeu amusant et captivant pour deux joueurs ! À tour de rôle, déplacez un pion sur un graphe dirigé. Le premier à atteindre le sommet d’arrivée remporte la partie. Imaginez une stratégie gagnante pour chaque graphe dirigé, concevez un algorithme capable de trouver automatiquement ces stratégies, et explorez comment représenter des jeux classiques sous forme de graphes dirigés. Devenez ainsi imbattable à de nombreux jeux !

illustration
Cliquer sur l'image pour zoomer
Type d'activité
Atelier
Nature
débranchée
Activité en ligne ?
Non
Notions abordées
Stratégie gagnante, position perdante ou gagnante, graphes des positions, quantificateurs logiques ``quel que soit'', ``il existe'', algorithme, modélisation de problèmes.
Thématiques
Algorithmes, Algorithmes dans les graphes, Jeux combinatoires
Niveau scolaire
cycle 3, cycle 4, lycée
Audience grand public
adultes et enfants
Lieu d'utilisation
intérieur
Contexte d'utilisation
tout contexte
Peut être empruntée ?
Oui
Localisation ou lieu d'emprunt
TerraNumerica@Sophia
Effectif
non précisé
Durée
entre 30 et None minutes
Effectif encadrement minimum
1
Ressources nécessaires
chaise(s), table(s)
Peut être déplacée ?
Oui
Temps d'installation
5m
Objectifs pédagogiques
  • S'initier aux stratégies gagnantes au travers d'un jeu et ainsi aux algorithmes et à la preuve.
  • Comprendre comment de nombreux jeux peuvent se modéliser à l'aide d'un graphe dirigé.
  • Découvrir puis maîtriser un algorithme générique pour trouver et démontrer une stratégie gagnante à ces jeux.
    • Méthodologie
    On fait jouer les participants jouent, afin qu'ils trouvent une stratégie gagnante pour chacun des graphes dirigés proposés. Il leur est ensuite demander d'explicaiter clairement leurs stratégies. On essaie ensuite de leur faire découvrir une manière automatique (c'est-à-dire un algorithme) pour trouver la stratégie gagnante sur n’importe quel graphe dirigé acyclique. Enfin on leur demande ou explique comment modéliser d'autres jeux tels que Jeu des bâtonnets, L'abeille et le miel, ou le Le roi buté comme des cas particuliers de ce jeu sur certains graphes dirigés.
    Groupe de travail
    GT-03 - Jeux
    Contacts
    Frédéric HAVET (frederic<dot>havet@i3s<dot>unice<dot>fr)
    Nicolas NISSE (nicolas<dot>nisse@inria<dot>fr)
    Incluse dans les parcours
    Galejade
    PN Th. 3 Algorithmes : Inititation
    Passeport Numérique
    Documents joints
    Fiche pédagogique
    Plateaux de jeu imprimables.
    Plateaux de jeu imprimables avec positions perdantes.
    Retour liste