Filière MP (groupes MPI et I)
Épreuve commune aux ENS de Paris, Lyon et Cachan
Filière PC (groupe I)Épreuve commune aux ENS de Paris et Lyon
INFORMATIQUE
Durée : 4 heures
L'usage de calculatrice est interdit
Graphes et jeux à deux joueurs
Ce problème s'intéresse au calcul de chemins optimaux dans un graphe fini et orienté, puis aux stratégies dans un jeu à information parfaite, joué par deux joueurs antagonistes déplaçant sur un tel graphe un jeton de sommet en sommet, suivant les arêtes. Les sections 1 et 2 sont largement indépendantes l'une de l'autre. Il en est de même pour les sections 2.2 et 2.3 .
Préliminaires
Structures de données et algorithmes. Pour les questions demandant l'écriture d'un algorithme en pseudo-code, on utilisera un langage ou pseudo-langage au choix, avec les structures de données (tableaux uni- et multi-dimensionnels, listes, etc.) et de contrôle (si, tant que, pour, etc.) usuelles. Les indices d'un tableau de taille vont de 1 à , et ses éléments sont notés . On pourra si nécessaire allouer des tableaux dont la taille est une variable, sans se soucier de la désallocation. Les questions demandant la description d'un algorithme n'imposent pas d'écrire du pseudo-code, mais simplement de décrire l'algorithme en français. Dans les deux cas, la qualité de la rédaction ainsi que les justifications (correction de l'algorithme, complexité) seront des éléments d'appréciation.
Complexité. La complexité d'un algorithme est le nombre d'opérations élémentaires qu'il effectue dans le cas le pire: lecture ou écriture dans une variable, opérations arithmétiques sur les entiers (comparaisons, addition, soustraction, multiplication, division entière), tests, ajout ou suppression en tête de liste, empilement ou dépilement dans une pile, etc. On ne cherchera pas à estimer les complexités exactement. On en donnera un ordre de grandeur, en utilisant la notation asymptotique .
Autres conventions. On note l'ensemble des entiers naturels et celui des entiers relatifs. On pose . On convient que pour tout entier , on a et . On s'autorisera à utiliser dans les algorithmes ou les programmes en pseudo-code le symbole pour représenter une valeur infinie, ainsi que les comparaisons et additions faisant intervenir cette valeur. L'ensemble des matrices à coefficients dans est noté . On pourra représenter une telle matrice par un tableau bidimensionnel , où représente .
Définitions et notations
Ce problème considère des graphes finis et orientés. Un graphe (fini, orienté) est un couple , où est un ensemble fini non vide, et . Un élément de
est appelé un sommet, et un élément de une arête de . Si , on dit que est successeur de , on appelle l'origine de l'arête et sa destination. Un chemin est une suite non vide, finie ou infinie de sommets , avec , telle que si et . On dit que est le successeur de sur . Si , on dit que est fini de longueur . Un chemin trivial est un chemin de longueur nulle. Si est dit infini. L'origine de est . Si est fini, sa destination est , et on dit que est un chemin de . On dit que visite un sommet s'il existe tel que et .
Étant donnés deux sommets , on note l'ensemble des chemins de à . Un cycle est un chemin dont l'origine et la destination sont égales. Un graphe est acyclique s'il n'a pas de cycle non trivial. La concaténation de deux chemins finis et est définie, si , comme le chemin .
Dans les figures, les sommets des graphes seront représentés par des cercles ou des carrés, reliés entre eux par des flèches représentant les arêtes: une flèche partant d'un sommet et pointant vers un sommet représente l'arête ( ). On suppose que l'ensemble des sommets des graphes sur lesquels on travaille est .
1 Chemins optimaux
Dans cette partie, on travaille sur un graphe . On se donne une fonction satisfaisant les conditions:
Le poids d'un chemin fini , que l'on notera encore , est , avec la convention que si le chemin est trivial ( ), son poids vaut 0 . Sauf pour la question 1.10, on suppose que n'a aucun cycle de poids strictement négatif.
1.1. Soient tels que . Montrer que est bien défini.
On définit par:
On définit la matrice de par .
1.2. Calculer la matrice pour le graphe de la figure 1 , où les valeurs de la fonction sont données sur les arêtes (on a si est l'entier indiqué sur la flèche allant de à ).
Le produit min-+ de deux matrices , noté , est défini par
1.3. Écrire en pseudo-code une fonction prenant en argument deux tableaux bidimensionnels M et N représentant les matrices et , ainsi que leur dimension commune n, et qui calcule leur produit min- + . Évaluer la complexité de la fonction.
Fig. 1 - Graphe et fonction
Un chemin d'un sommet à un sommet est optimal si .
1.4. Soit un chemin optimal. On suppose que . Montrer que est optimal.
1.5. Soit définie par . Exprimer en fonction de , en justifiant précisément.
1.6. Écrire en pseudo-code un algorithme de complexité prenant en entrée la matrice et sa dimension, et calculant . Justifier la correction de l'algorithme ainsi que sa complexité.
L'ensemble. des sommets intermédiaires d'un chemin fini est . Pour , on définit
.
, en convenant que .
1.7. Pour , calculer et exprimer en fonction de valeurs de , pour . Justifier précisément la relation obtenue.
1.8. Décrire un algorithme de complexité calculant la matrice . Justifier la correction de l'algorithme et sa complexité.
1.9. Décrire un algorithme prenant en entrée la matrice (définie en question 1.5) et sa dimension, ainsi que deux sommets , et qui renvoie une liste de sommets représentant un chemin optimal de à dans , ou la liste vide si un tel chemin n'existe pas. Indiquer sa complexité.
1.10. On supprime dans cette question l'hypothèse qu'il n'existe aucun cycle de poids strictement négatif. Décrire un algorithme de complexité testant si un graphe possède un cycle de poids strictement négatif.
2 Jeux sur une arène
On considère des jeux joués sur une arène par deux joueurs antagonistes, appelés 0 et 1 . Une arène ( ) est donnée par un graphe dont tout sommet a un successeur, et deux sous-ensembles de tels que et . Pour , on dit que est l'ensemble des sommets appartenant au joueur .
Informellement, une partie se déroule comme suit: un jeton est placé sur un sommet du graphe , et déplacé par les joueurs de sommet en sommet, par une succession de mouvements. Un mouvement consiste à déplacer le jeton en suivant une arête: lorsque le jeton est sur un sommet , le joueur à qui appartient le déplace sur un successeur de , et ainsi de suite. Une partie est le chemin infini traversé par le jeton.
Formellement, un jeu est un 4-uplet ( ). où
( ) est une arène, avec ;
est un ensemble de chemins infinis dans , appelé condition de gain.
Une partie depuis un sommet initial est un chemin infini dans d'origine . Une partie est gagnée par le joueur 0 si elle appartient à l'ensemble , et gagnée par le joueur 1 sinon.
Pour , une stratégie pour le joueur est une application telle que pour tout , on a . Une partie est une -partie si pour tout tel que , on a . Une stratégie pour le joueur est gagnante depuis un ensemble si toute -partie depuis un sommet initial appartenant à est gagnée par le joueur .
Un jeu est positionnel s'il existe avec , et pour , une stratégie pour le joueur qui est gagnante depuis . On remarquera que peut contenir à la fois des sommets de et des sommets de (et de même pour ).
2.1. On considère l'arène de la figure 2 , où et (les sommets de sont représentés par des cercles, ceux de par des carrés).
Fig. 2 - Une arène ( )
2.1.1. On suppose que est l'ensemble des chemins ne visitant pas le sommet 0 . Le jeu est-il positionnel? Si oui, donner les ensembles , et les stratégies correspondantes. Sinon, justifier.
2.1.2. Même question si est l'ensemble des chemins pour lesquels les ensembles et sont tous deux infinis.
2.2. Montrer que si un jeu est positionnel, les ensembles et sont disjoints.
2.1 Jeux d'accessibilité
Dans les questions 2.3 à 2.7 , on suppose qu'il existe tel qu'un chemin infini est dans si et seulement s'il visite un sommet de . On suppose dans les questions 2.3 à 2.5.
2.3. Soit l'ensemble des sommets tels qu'il existe une stratégie pour le joueur 0 gagnante depuis . Montrer qu'il existe une stratégie pour le joueur 0 gagnante depuis .
2.4. On appelle matrice d'adjacence de la matrice définie par
Écrire en pseudo-code un algorithme de complexité calculant une stratégie pour le joueur 0 , gagnante depuis . On suppose données une liste des éléments de et la matrice d'adjacence de . La stratégie pourra être représentée comme un tableau de taille , avec si . Justifier la correction de l'algorithme et sa complexité.
2.5. On suppose maintenant le graphe donné par un tableau Succ à cases, où Succ est une liste des successeurs du sommet . Une liste des éléments de est encore donnée. Écrire en pseudo-code un algorithme de complexité , où est le nombre d'arêtes de , calculant une stratégie pour le joueur 0 , gagnante depuis .
On suppose à présent que . Pour , on définit pour tout l'ensemble inductivement par
Soit enfin , appelé attracteur de .
2.6. Montrer que le jeu est positionnel, plus précisément:
2.6.1. Montrer que le joueur 0 a une stratégie gagnante depuis , l'attracteur de .
2.6.2. Montrer que le joueur 1 a une stratégie gagnante depuis .
2.7. On suppose le graphe donné comme en question 2.5. Décrire un algorithme calculant une stratégie pour le joueur 0 gagnante depuis l'attracteur de .
2.8. Étant donnés deux entiers , on considère le jeu ( ) suivant. L'arène est avec , et et les arêtes sont tous les couples suivants, où et :
où et sont des entiers strictement positifs.
où et sont des entiers strictement positifs.
.
Une partie est dans si et seulement si l'ensemble est fini.
Soit , où désigne le plus grand entier inférieur ou égal à .
Vérifier que ( ) est un jeu bien défini, et montrer que:
2.8.1. si , le sommet ( ) a un successeur ( ) tel que 0 ;
2.8.2. si , tout successeur de est tel que ;
2.8.3. le joueur 0 a une stratégie gagnante depuis les sommets ( ) tels que et , ou et , et uniquement depuis ces sommets.
2.2 Jeux d'accessibilité répétée
Dans les questions 2.9 à 2.13, on suppose donné tel qu'un chemin infini est dans si et seulement si l'ensemble est infini. Les parties gagnées par le joueur 0 sont ainsi celles qui visitent infiniment souvent un sommet de .
2.9. On suppose . On suppose données une liste des éléments de l'ensemble , la matrice d'adjacence et la matrice définie en question 1.1, pour la fonction telle que si et . Décrire un algorithme de complexité calculant l'ensemble des sommets tels qu'il existe une stratégie pour le joueur 0 gagnante depuis .
2.10. On suppose à nouveau . On suppose le graphe donné comme en question 2.5 par un tableau de listes de successeurs, et par une liste de ses éléments. Décrire un algorithme de complexité calculant l'ensemble de la question 2.9.
Pour , on définit , où
2.11. Si , montrer que
2.11.1. tout sommet de a un successeur dans ,
2.11.2. tout sommet de a tous ses successeurs dans .
On définit , et pour tout . On pose .
2.12. Déduire de la question précédente une stratégie pour le joueur 0 gagnante depuis . On pourra définir cette stratégie par ses restrictions sur les ensembles et .
2.13. Montrer que le joueur 1 a une stratégie gagnante depuis .
2.3 Jeux de parité
Une arène coloriée ( ) est donnée par une arène ( ), où , et une fonction . Pour , l'entier est appelé la couleur du sommet . Si est une partie dans ( ), on note . Jusqu'à la fin du problème, une partie est dans l'ensemble des parties gagnées par le joueur 0 si et seulement si est pair. Un tel jeu est appelé jeu de parité.
2.14. Sur l'arène coloriée suivante, les sommets de sont représentés par des cercles, ceux de par des carrés. Les couleurs sont indiquées sur les sommets. Pour quels sommets le joueur 0 a-t-il une stratégie gagnante depuis ? Montrer qu'il a une stratégie gagnante depuis l'ensemble de ces sommets. Mêmes questions pour le joueur 1.
2.15. Soit ( ) une arène coloriée, et l'ensemble des sommets tels que le joueur 0 a une stratégie gagnante depuis . Pour , soit une stratégie pour le joueur 0 , gagnante depuis . Soit l'ensemble des sommets de visités par au moins une -partie de sommet initial . Définir à partir des stratégies et des ensembles une stratégie pour le joueur 0, gagnante depuis .
Soit . On veut montrer par induction sur que tout jeu de parité est positionnel.
2.16. Vérifier le résultat pour .
On suppose maintenant que , et que tout jeu de parité tel que pour tout est positionnel.
2.17. Soit l'ensemble des sommets depuis lesquels le joueur 1 admet une stratégie gagnante, et soit . Soit le graphe . Montrer que ( ) est une arène si .
2.18. On suppose que est pair. Montrer que dans ( ), le joueur 0 a une stratégie gagnante depuis . On pourra commencer par traiter le cas où ne contient aucun sommet de couleur maximale .
2.19. Déduire des questions précédentes que tout jeu de parité est positionnel.
2.20. Décrire un algorithme de complexité , où pour calculer des ensembles tels que , ainsi que deux stratégies et pour les joueurs 0 et 1 respectivement, telles que soit gagnante depuis et le soit depuis .
ENS Informatique MP PC 2007 - Version Web LaTeX | WikiPrépa | WikiPrépa
