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 T de taille n vont de 1 à n, et ses éléments sont notés T[1], …, T[n]. 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 O(⋯).
Autres conventions. On note ℕ l'ensemble des entiers naturels et ℤ celui des entiers relatifs. On pose ℤ_∞ = ℤ ∪ {∞}. On convient que pour tout entier n, on a n < ∞ et n + ∞ = ∞ + n = ∞ + ∞ = ∞. 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 n × n à coefficients dans ℤ_∞ est noté M_n(ℤ_∞). On pourra représenter une telle matrice M = (m_(i, j))_(1 ⩽ i, j ⩽ n) par un tableau M bidimensionnel n × n, où M[i][j] représente m_(i, j).
Définitions et notations
Ce problème considère des graphes finis et orientés. Un graphe (fini, orienté) est un couple G = (S, A), où S est un ensemble fini non vide, et A ⊆ S × S. Un élément de S
est appelé un sommet, et un élément de A une arête de G. Si a = (s, t) ∈ A, on dit que t est successeur de s, on appelle s l'origine de l'arête a et t sa destination. Un chemin σ est une suite non vide, finie ou infinie de sommets (s_i)_(0 ⩽ i < m), avec m ∈ (ℕ∖{0}) ∪ {∞}, telle que (s_i, s_(i + 1)) ∈ A si 0 ⩽ i et i + 1 < m. On dit que s_(i + 1) est le successeur de s_i sur σ. Si m ≠ ∞, on dit que σ est fini de longueur m − 1. Un chemin trivial est un chemin de longueur nulle. Si m = ∞, σ est dit infini. L'origine de σ est s_0. Si σ est fini, sa destination est s_(m − 1), et on dit que σ est un chemin de s_0 a^‵s_(m − 1). On dit que σ visite un sommet s s'il existe i tel que 0 ⩽ i < m et s_i = s.
Étant donnés deux sommets s, t, on note P_(s ∼ t) l'ensemble des chemins de s à t. 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 σ = (s_0, s_1, …, s_(m − 1)) et τ = (t_0, t_1, …, t_(p − 1)) est définie, si s_(m − 1) = t_0, comme le chemin σ ∘ τ = (s_0, s_1, …, s_(m − 1), t_1, …, t_(p − 1)).
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 s et pointant vers un sommet t représente l'arête ( s, t ). On suppose que l'ensemble des sommets des graphes sur lesquels on travaille est S = {1, …, n}.
1 Chemins optimaux
Dans cette partie, on travaille sur un graphe G = (S, A). On se donne une fonction w : S × S → ℤ_∞ satisfaisant les conditions:
∀s ∈ S :, w(s, s) = 0; ∀(s, t) ∈ (S × S)∖A :, s ≠ t ⇒ w(s, t) = ∞
Le poids d'un chemin fini σ = (s_i)_(0 ⩽ i < m), que l'on notera encore w(σ), est ∑_(i = 1)^(m − 1)w(s_(i − 1), s_i), avec la convention que si le chemin est trivial ( m = 1 ), son poids vaut 0 . Sauf pour la question 1.10, on suppose que G n'a aucun cycle de poids strictement négatif.
1.1. Soient s, t tels que P_(s ∼ t) ≠ ∅. Montrer que min{w(σ)|σ ∈ P_(s ∼ t)} est bien défini.
On définit la matrice D^w de M_n(ℤ_∞) par D^w = (d^w(s, t))_(1 ⩽ s, t ⩽ n).
1.2. Calculer la matrice D^w pour le graphe G_1 de la figure 1 , où les valeurs de la fonction w sont données sur les arêtes (on a w(s, t) = x si x est l'entier indiqué sur la flèche allant de s à t ).
Le produit min-+ de deux matrices M, N ∈ M_n(ℤ_∞), noté M∗N, 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 M et N, ainsi que leur dimension commune n, et qui calcule leur produit min- + . Évaluer la complexité de la fonction.
Fig. 1 - Graphe G_1 et fonction w
Un chemin σ d'un sommet s à un sommet t est optimal si w(σ) = d^w(s, t).
1.4. Soit σ un chemin optimal. On suppose que σ = σ_1 ∘ τ ∘ σ_2. Montrer que τ est optimal.
1.5. Soit W = (W_(s, t))_(1 ⩽ s, t ⩽ n) ∈ M_n(ℤ_∞) définie par W_(s, t) = w(s, t). Exprimer D^w en fonction de W, en justifiant précisément.
1.6. Écrire en pseudo-code un algorithme de complexité O(n^3 logn) prenant en entrée la matrice W et sa dimension, et calculant D^w. Justifier la correction de l'algorithme ainsi que sa complexité.
L'ensemble. des sommets intermédiaires d'un chemin fini σ = (s_i)_(0 ⩽ i < m) est I(σ) = {s_i|1 ⩽ i < m − 1}. Pour u = 0, 1, …, n, on définit
d_u^w(s, t) = min{w(σ)|σ ∈ P_(s ∼ t, u)}, en convenant que min∅ = ∞.
1.7. Pour s, t ∈ S, calculer d_0^w(s, t) et exprimer d_u^w(s, t) en fonction de valeurs de d_(u − 1)^w, pour u ⩾ 1. Justifier précisément la relation obtenue.
1.8. Décrire un algorithme de complexité O(n^3) calculant la matrice D^w. Justifier la correction de l'algorithme et sa complexité.
1.9. Décrire un algorithme prenant en entrée la matrice W (définie en question 1.5) et sa dimension, ainsi que deux sommets s, t, et qui renvoie une liste de sommets représentant un chemin optimal de s à t dans G, 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é O(n^3) 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 ( G, S_0, S_1 ) est donnée par un graphe G = (S, A) dont tout sommet a un successeur, et deux sous-ensembles S_0, S_1 de S tels que S = S_0 ∪ S_1 et S_0 ∩ S_1 = ∅. Pour ℓ ∈ {0, 1}, on dit que S_ℓ 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 G, 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 s, le joueur à qui s appartient le déplace sur un successeur de s, et ainsi de suite. Une partie est le chemin infini traversé par le jeton.
Formellement, un jeu est un 4-uplet ( G, S_0, S_1, W ). où
( G, S_0, S_1 ) est une arène, avec G = (S, A);
W est un ensemble de chemins infinis dans G, appelé condition de gain.
Une partie depuis un sommet initial s_(init) est un chemin infini (s_i)_(i ⩾ 0) dans G d'origine s_0 = s_(init). Une partie (s_i)_(i ⩾ 0) est gagnée par le joueur 0 si elle appartient à l'ensemble W, et gagnée par le joueur 1 sinon.
Pour ℓ ∈ {0, 1}, une stratégie pour le joueur ℓ est une application f : S_ℓ → S telle que pour tout s ∈ S_ℓ, on a (s, f(s)) ∈ A. Une partie (s_i)_(i ⩾ 0) est une f-partie si pour tout i tel que s_i ∈ S_ℓ, on a s_(i + 1) = f(s_i). Une stratégie f pour le joueur ℓ est gagnante depuis un ensemble X ⊆ S si toute f-partie depuis un sommet initial appartenant à X est gagnée par le joueur ℓ.
Un jeu est positionnel s'il existe R_0, R_1 ⊆ S avec S = R_0 ∪ R_1, et pour ℓ = 0, 1, une stratégie f_ℓ pour le joueur ℓ qui est gagnante depuis R_ℓ. On remarquera que R_0 peut contenir à la fois des sommets de S_0 et des sommets de S_1 (et de même pour R_1 ).
2.1. On considère l'arène de la figure 2 , où S_0 = {1} et S_1 = {0, 2} (les sommets de S_0 sont représentés par des cercles, ceux de S_1 par des carrés).
Fig. 2 - Une arène ( G, S_0, S_1 )
2.1.1. On suppose que W est l'ensemble des chemins ne visitant pas le sommet 0 . Le jeu est-il positionnel? Si oui, donner les ensembles R_0, R_1, et les stratégies f_0, f_1 correspondantes. Sinon, justifier.
2.1.2. Même question si W est l'ensemble des chemins (s_i)_(i ⩾ 0) pour lesquels les ensembles {j ∈ ℕ|s_j = 0} et {j ∈ ℕ|s_j = 2} sont tous deux infinis.
2.2. Montrer que si un jeu est positionnel, les ensembles R_0 et R_1 sont disjoints.
2.1 Jeux d'accessibilité
Dans les questions 2.3 à 2.7 , on suppose qu'il existe T ⊆ S tel qu'un chemin infini est dans W si et seulement s'il visite un sommet de T. On suppose S_1 = ∅ dans les questions 2.3 à 2.5.
2.3. Soit X_0 l'ensemble des sommets s tels qu'il existe une stratégie pour le joueur 0 gagnante depuis {s}. Montrer qu'il existe une stratégie pour le joueur 0 gagnante depuis X_0.
2.4. On appelle matrice d'adjacence de G la matrice V_G = (v_(s, t))_(1 ⩽ s, t ⩽ n) définie par
v_(s, t) = {1, si (s, t) ∈ A; 0, sinon
Écrire en pseudo-code un algorithme de complexité O(n^2) calculant une stratégie pour le joueur 0 , gagnante depuis X_0. On suppose données une liste des éléments de T et la matrice d'adjacence de G. La stratégie f pourra être représentée comme un tableau F de taille n, avec F[s] = t si f(s) = t. Justifier la correction de l'algorithme et sa complexité.
2.5. On suppose maintenant le graphe G donné par un tableau Succ à n cases, où Succ [s] est une liste des successeurs du sommet s. Une liste des éléments de T est encore donnée. Écrire en pseudo-code un algorithme de complexité O(m), où m est le nombre d'arêtes de G, calculant une stratégie pour le joueur 0 , gagnante depuis X_0.
On suppose à présent que S_1 ≠ ∅. Pour X ⊆ S, on définit pour tout i ∈ ℕ l'ensemble Attr_i(X) ⊆ S inductivement par
Attr_0(X) =, X; Attr_(i + 1)(X) =, Attr_i(X); ∪ {s ∈ S_0|∃(s, t) ∈ A et t ∈ Attr_i(X)}; ∪ {s ∈ S_1|∀(s, t) ∈ A, t ∈ Attr_i(X)}
Soit enfin Attr(X) = ⋃_(i ⩾ 0)Attr_i(X), appelé attracteur de X.
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 R_0 = Attr(T), l'attracteur de T.
2.6.2. Montrer que le joueur 1 a une stratégie gagnante depuis R_1 = S∖Attr(T).
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 T.
2.8. Étant donnés deux entiers a, b > 0, on considère le jeu ( G_(a, b), S_0, S_1, W ) suivant. L'arène est G_(a, b) = (S, A) avec S = {(x, y, z) ∈ ℕ^3|0 < x ⩽ a, 0 < y ⩽ b, z ∈ {0, 1}}, S_0 = S ∩ (ℕ^2 × {0}) et S_1 = S ∩ (ℕ^2 × {1}) et les arêtes sont tous les couples suivants, où 0 < x ⩽ a, 0 < y ⩽ b et z ∈ {0, 1} :
((x, y, z), (x − ky, y, 1 − z)) où k et x − ky sont des entiers strictement positifs.
((x, y, z), (x, y − ℓx, 1 − z)) où ℓ et y − ℓx sont des entiers strictement positifs.
((x, x, z), (x, x, z)).
Une partie (s_i)_(i ⩾ 0) est dans W si et seulement si l'ensemble {j ⩾ 0|s_j ∈ S_0} est fini.
Soit γ(x, y) = ⌊|x/y − y/x|⌋, où ⌊α⌋ désigne le plus grand entier inférieur ou égal à α.
Vérifier que ( G_(a, b), S_0, S_1, W ) est un jeu bien défini, et montrer que:
2.8.1. si γ(x, y) ≠ 0, le sommet ( x, y, z ) a un successeur ( x^′, y^′, 1 − z ) tel que γ(x^′, y^′) = 0 ;
2.8.2. si γ(x, y) = 0, tout successeur (x^′, y^′, 1 − z) de (x, y, z) est tel que γ(x^′, y^′) ≠ 0;
2.8.3. le joueur 0 a une stratégie gagnante depuis les sommets ( x, y, z ) tels que z = 0 et γ(x, y) ≠ 0, ou z = 1 et γ(x, y) = 0, et uniquement depuis ces sommets.
2.2 Jeux d'accessibilité répétée
Dans les questions 2.9 à 2.13, on suppose donné T ⊆ S tel qu'un chemin infini (s_i)_(i ⩾ 0) est dans W si et seulement si l'ensemble {j ∈ ℕ|s_j ∈ T} est infini. Les parties gagnées par le joueur 0 sont ainsi celles qui visitent infiniment souvent un sommet de T.
2.9. On suppose S_1 = ∅. On suppose données une liste des éléments de l'ensemble T, la matrice d'adjacence V_G et la matrice D^w définie en question 1.1, pour la fonction w telle que w(s, t) = 1 si s ≠ t et (s, t) ∈ A. Décrire un algorithme de complexité O(n|T|) calculant l'ensemble X_0 des sommets s tels qu'il existe une stratégie pour le joueur 0 gagnante depuis {s}.
2.10. On suppose à nouveau S_1 = ∅. On suppose le graphe G donné comme en question 2.5 par un tableau de listes de successeurs, et T par une liste de ses éléments. Décrire un algorithme de complexité O(m|T|) calculant l'ensemble X_0 de la question 2.9.
Pour X ⊆ S, on définit Attr^+(X) = ⋃_(i ⩾ 0)Attr_i^+(X), où
Attr_0^+(X) =, ∅; Attr_(i + 1)^+(X) =, Attr_i^+(X); ∪ {s ∈ S_0|∃(s, t) ∈ A et t ∈ Attr_i^+(X) ∪ X}; ∪ {s ∈ S_1|∀(s, t) ∈ A, t ∈ Attr_i^+(X) ∪ X}
2.11. Si X ⊆ S, montrer que
2.11.1. tout sommet de Attr^+(X) ∩ S_0 a un successeur dans Attr(X),
2.11.2. tout sommet de Attr^+(X) ∩ S_1 a tous ses successeurs dans Attr(X).
On définit W_0(T) = T, et pour tout i ∈ ℕ, W_(i + 1)(T) = Attr^+(W_i(T)) ∩ T. On pose W(T) = ⋂_(i ⩾ 0)W_i(T).
2.12. Déduire de la question précédente une stratégie pour le joueur 0 gagnante depuis Attr(W(T)). On pourra définir cette stratégie par ses restrictions sur les ensembles W(T) et Attr(W(T))∖W(T).
2.13. Montrer que le joueur 1 a une stratégie gagnante depuis S∖Attr(W(T)).
2.3 Jeux de parité
Une arène coloriée ( G, S_0, S_1, c ) est donnée par une arène ( G, S_0, S_1 ), où G = (S, A), et une fonction c : S → ℕ. Pour s ∈ S, l'entier c(s) est appelé la couleur du sommet s. Si σ = (s_i)_(i ⩾ 0) est une partie dans ( G, S_0, S_1 ), on note v(σ) = lim_(n → + ∞)sup_(i ⩾ n)c(s_i). Jusqu'à la fin du problème, une partie σ est dans l'ensemble W des parties gagnées par le joueur 0 si et seulement si v(σ) est pair. Un tel jeu est appelé jeu de parité.
2.14. Sur l'arène coloriée suivante, les sommets de S_0 sont représentés par des cercles, ceux de S_1 par des carrés. Les couleurs sont indiquées sur les sommets. Pour quels sommets s le joueur 0 a-t-il une stratégie gagnante depuis {s} ? Montrer qu'il a une stratégie gagnante depuis l'ensemble de ces sommets. Mêmes questions pour le joueur 1.
2.15. Soit ( G, S_0, S_1, c ) une arène coloriée, et X_0 = {s_1, …, s_p} l'ensemble des sommets s tels que le joueur 0 a une stratégie gagnante depuis {s}. Pour 1 ⩽ i ⩽ p, soit f_i une stratégie pour le joueur 0 , gagnante depuis {s_i}. Soit F_i l'ensemble des sommets de S_0 visités par au moins une f_i-partie de sommet initial s_i. Définir à partir des stratégies f_i et des ensembles F_i une stratégie pour le joueur 0, gagnante depuis X_0.
Soit k = max{c(s)|s ∈ S}. On veut montrer par induction sur k que tout jeu de parité est positionnel.
2.16. Vérifier le résultat pour k = 0.
On suppose maintenant que k > 0, et que tout jeu de parité tel que c(s) < k pour tout s ∈ S est positionnel.
2.17. Soit U_1 l'ensemble des sommets depuis lesquels le joueur 1 admet une stratégie gagnante, et soit U_0 = S∖U_1. Soit H le graphe (U_0, A ∩ (U_0 × U_0)). Montrer que ( H, S_0 ∩ U_0, S_1 ∩ U_0 ) est une arène si U_0 ≠ ∅.
2.18. On suppose que k est pair. Montrer que dans ( G, S_0, S_1, c ), le joueur 0 a une stratégie gagnante depuis U_0. On pourra commencer par traiter le cas où U_0 ne contient aucun sommet de couleur maximale k.
2.19. Déduire des questions précédentes que tout jeu de parité est positionnel.
2.20. Décrire un algorithme de complexité 2^(θ(n)), où θ(n) = O(nlogn) pour calculer des ensembles R_0, R_1 tels que S = R_0 ∪ R_1, ainsi que deux stratégies f_0 et f_1 pour les joueurs 0 et 1 respectivement, telles que f_0 soit gagnante depuis R_0 et f_1 le soit depuis R_1.
Pas de description pour le moment
Commentaires• ENS Informatique MP PC 2007
Connectez-vous pour participer aux discussions
Partagez vos avis, posez des questions et échangez avec la communauté
Sujet proche avec corrigéX ENS Informatique C MPI 2025X-ENS · 2025Corrigé
Même année, XPolytechnique Informatique Commune MP PC 2007X · 2007Corrigé
Sujet proche avec corrigéCentrale Option Informatique MP 2024Centrale · 2024Corrigé
Même année, CCINPCCINP Option Informatique MP 2007CCINP · 2007Corrigé
