Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Détermination (théorie des ensembles)
Résumé
La détermination est un sous-champ de la théorie des ensembles, une branche des mathématiques, qui s'intéresse aux conditions dans lesquelles un joueur peut avoir ou non une stratégie gagnante dans un jeu, à la complexité d'une telle stratégie quand elle existe, ainsi qu'aux conséquences de l'existence de telles stratégies.
Les jeux étudiés en théorie des ensembles sont généralement des jeux de Gale-Stewart, c'est-à-dire des jeux à deux joueurs à où les joueurs font une suite infinie de coups et où aucun match nul n'est possible. Le domaine de la théorie des jeux étudie des types de jeux plus généraux, comme les jeux avec match nul possible tels que le tic-tac-toe, les échecs ou , ainsi que les jeux à information imparfaite comme le poker.
Le premier jeu que nous allons considérer est le jeu à deux joueurs à information parfaite de longueur ω, dans lequel les joueurs jouent des entiers naturels. Ces jeux sont souvent appelés jeux de Gale–Stewart.
Dans ce jeu, il y a deux joueurs, souvent nommés I et II, qui choisissent à tour de rôle des entiers naturels, le joueur I commence. Ils jouent une infinité de fois chacun. Quand ils ont fini, ils ont obtenu une suite infinie d'entiers naturels. Une condition prédéterminée décide alors quel joueur a gagné en fonction de la suite ainsi obtenue.
Plus formellement, considérons un sous-ensemble A de l'ensemble des suites d'entiers naturels. On appelle GA le jeu suivant :
Le joueur I joue un entier naturel , puis II joue un entier naturel , I joue un entier naturel , et ainsi de suite. Le joueur I gagne le jeu si et seulement si la suite infinie appartient à A. Dans le cas contraire, le joueur II gagne.
L'ensemble A s'appelle alors l'ensemble de gain de GA. Le but du joueur I est donc de s'assurer que la suite créée par les deux joueurs appartienne à l'ensemble A et le but du joueur II est de l'en empêcher.
Le jeu est à information parfaite : chaque joueur connaît tous les mouvements qui précèdent chacun de ses mouvements et connaît également la condition de victoire.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Séances de cours associées (14)
Physique statistique : Isolement des systèmes
Explore les concepts de physique statistique dans des systèmes isolés, en se concentrant sur l'entropie et le désordre.
Optimisation convexe : Lemme de Farkas
Couvre le lemme de Farkas, explorant la relation entre les programmes linéaires et les conditions de sa validité.
Probabilité et statistiques pour les SIC
Déplacez-vous dans les probabilités, les statistiques, les expériences aléatoires et l'inférence statistique, avec des exemples pratiques et des idées.
Publications associées (15)
Personnes associées (1)
Concepts associés (9)
Axiome de détermination
L'axiome de détermination est un axiome alternatif de la théorie des ensembles affirmant que certains jeux (au sens de la théorie des jeux) infinis sont déterminés. Cet axiome n'est pas compatible avec l'axiome du choix mais implique l'axiome du choix dénombrable pour les familles d'ensembles de réels et implique également une forme faible de l'hypothèse du continu.
Axiom of projective determinacy
In mathematical logic, projective determinacy is the special case of the axiom of determinacy applying only to projective sets. The axiom of projective determinacy, abbreviated PD, states that for any two-player infinite game of perfect information of length ω in which the players play natural numbers, if the victory set (for either player, since the projective sets are closed under complementation) is projective, then one player or the other has a winning strategy.
Arithmétique du second ordre
En logique mathématique, l'arithmétique du second ordre est une théorie des entiers naturels et des ensembles d'entiers naturels. Elle a été introduite par David Hilbert et Paul Bernays dans leur livre Grundlagen der Mathematik. L'axiomatisation usuelle de l'arithmétique du second ordre est notée Z2. L'arithmétique de second ordre a pour conséquence les théorèmes de l'arithmétique de Peano (du premier ordre), mais elle est à la fois plus forte et plus expressive que celle-ci.