cpge-paradise.
com
ECOLE POLYTECHNIQUE - ESPCI
ECOLES NORMALES SUPERIEURES
CONCOURS D'ADMISSION 2025
JEUDI 17 AVRIL 2025
16h30 - 18h30
FILIERES MP-PC-PSI
Epreuve n° 8
INFORMATIQUE B (XELSR)
Durée : 2 heures
L'utilisation des calculatrices n'est pas
autorisée pour cette épreuve
[Link]
Le jeu de Röckse
coInptés crs
Nx N des pénalités et des gains
On dispose sur les cases d'une grille vors L
débute à la case (0,0) et cherche un chemin
des péalités négatives. Le jen de Röckse du chernin, un nombre fni
case (N 1. N - 1) qui minimise les pénalités. A chaque étape une fois atteintes, des sast
Des cases bonus ajoutent,
de dépliacement:s (sauts) est autorisé. de grille et doss
figure ci-dessous donne 1n exemnple
possibles pour a suite du chemin. La (i, j + 1)
sauts autorisés slr la grille sont (i,i) ’
chemins possibBes, en supposant que les
1,j +1) ). On suppose par ailleurs une case bonus
(i. i) (i + 1.j - 1) ( ) et (i.j) ’ (i+ (i+1,i) (L):
ajoute aux sauts autorisés (,j) ’
en (1.2) (grisée ) qui, une fois atteinte, 3-4
1 2 1 2 3
1 2 DÉPART
DÉPART
DÉPART 2 4-6 0 2 -4 6
2 -4 -6
(4)
1 1 -2 3 1 1 -2 2 3
1 1
-3 4 2 -2 2 -3 4
-3 4 2 2 2
2 -2 2
3 -1 4 -3 7 3 -1 4 -3’ 7
3 -1 4 -3 7 |ARRIVÉE
ARRIVÉE
ARRIVÉE
(b) Chemin non-optimal (c) Chemin optimal
(a) Grille de jeu poids : -7
poids : -6
Considérons le chemin décrit en (c). On part de la case
de départ (0,0) et, en appliquant les
case bonus. A partir de cette case, le saut <
est
sauts successifs’, ’ , ’ , on arrive sur la d'arrivée (3.3).
désormais autorisé. On applique ensuite les sauts
J.J, ’ pour atteindre la case
Le chemin obtenu est décrit par la liste des cases
:
(2,2) , (3,2),(3,3)]
chenin = [(0,0) , (0, 1), (0, 2),(1,1),(1,2),
dans ces cases, soit -7. On peut montrer que
Son poids est la somme des pénalités contenues
optimal. Le chemin décrit en (b) est correct.
c'est un cheminde poids minimal on dit qu'il est
majs son pojds est de -6. Il n'est donc pas optimal.
Représentation des données. La grille de jeu Nx N est représent¿e par une liste de listes
représentatio
d'entiers T telle que T[i] Lj] est la pénalitéà la case (i,j). On suppoOse que cette exemple :
N. Sur notre
est bie formée, c'est-à-dire que toutes les listes ont la même taille
T = [[2 , -4, -6,0] ,[1, -2,2,3],(-2,2, -3,4],[-1,4, -3,7]]
d'entiers (oi, 8j). L'ensemble des
Uu saut (,j) ’ (i +oi,j + dj) est représenté par le couple l'ensemble des sauts possibles
sauts pOSsibles est ainsi une liste de couples. Sur notre exemple,
par déjaut (avant d'avoir atteint une case bonus) est :
sauts = [(0,1),(1,- 1),(1, 1)]
tel que
Les sauts activés par les cases bous soHt enregistrés dans un dictioumaire bonus
bonus [(i,j)] est la liste des sauts activés par lacase bonus (i,j) . Sur notre exemple :
bonus = { (1,2) : [(1,0)) }
[Link]
(addi
Complexité. La complexité d'une fonction F est le nombre d'opérations élémentaires
tion, multiplication, Lorsque cette com
affectation, test, etc.) nécessaires àl'exécution de F.
plexité dépend de plusieurs en O(ó(n, m))
paramètres n et m, ondira que F a une coInplexité ou égale
lorsqu'il existe trois constantes la complexitéde Fest inférieure
à A- o(n, m), pour tout n> n0 A,et nÍmet> mÍ
mo. telles que est
Lorsqu'il demandé de donner la conplexité d'un
programme, le candidat devra justifier sa réponse en utilisant le
code du programme.
PeIs Sur Python. L'utilisation de toute fonction Pvtho) sur les listes ou sur les alcto
naires autre que celles mentionnées dans ce paragraphe est interdite. Sur les listes, on autorise
les opérations suivantes, dont la complezité est en O(1):
len (1) renvoie la longueur de la liste 1.
1[(1]désigne l'élément d'indice i de la liste l. pour 0 <i< len(1).
-[Link](e) ajoute en place l'élément e à la fin de la liste 1.
Les opérations suivantes sont également autorisées et leur complerité est en O(p) :
concaténation des listes 1
1+ l2 renvoie une nouvelle liste (de longueur n) gui est la
et 12.
range (n) renvoie la liste [0,1, . . . n-1].
range (n-1,-1,-1) renvoie la liste [n-1, ].
e.
[Link](0) retire le premier élément e de la liste l (de longueur n) et renvoie
longueur n), et False sinon.
(e in 1) renvoie True si l'élément e est dans la liste 1 (de
1[:]renvoie une copie de la liste 1 (de longueur n).
On autorise également les constructions suivantes:
liste l du premier
La construction for e in l parcourt (itère sur) les éléments de la
O(len (1) ).
élément (d'indice 0), audernier élément (d'indice len (1) -1) avec la complexité
suivant, et avec la
La construction [f (e) for e in l] produit la même liste que le code
complexité len (1) fois la complexité de f :
result =
for e in l:
[Link] (f (e))
return result
Sur les dictionnaires, on autorise uniquement les opérations suivantes, dont la compleité est
en O(1) :
Le test (e in d) renvoie True sl e est une cle du dictionnaire d, et False sinon
D'accès dle] à l'élément associé à la clé e dans le dictionnaire d
On autorise égalernent les constructions suivantes sur les dictionnaires
ro construction for (k,v) in d parcourt les éléments du dictionnaire d.
la valeur v à la c]á l
La construction d [k] = v affecte
donnée une variable globale INFINI qui
Enfin, on supp0sera contient un entier supérieur ou égal
àtout entier utilisé dans les programmes de ce sujet.
Organisation. Les parties peuvent être traitées indé[Link] partie I porte sur
de base sur les
chemins et les sauts. Ensuite, la partie II les
fonctions
recherche exhaustive. La partie III utilise propose de trouver un chemin
avec une les
optimal
une méthode de recherche gloutonne. Enfin, la partie résultats de la partie II pour
construire IV étudie
problème par
programmation dynamique. On rappelle
que le code doit une résolution du
être commenté.
2
[Link]
Partie I:Sauts et chemins
Question 1Éerir unc fonction poids (T, chemin) qui, étant donné un platean de jeuT et un
cheminchemin. rnroic le poids de e chemin. Donner la complerité de cette fonction.
Question Ecrir une fonction appliquer sauts(1,j, sauts) qui, étant donné une case (i, j)
ef uncliste de sauts sauts, applique les sants dans l'ordre donné par la liste sauts, en partant
de la case (i.j) ct rnvoic la casc attcinte. On suppose que le chemin indiqué par sauts reste
dans la grille.
Question 3 Éerir une fonction sauts corrects (sauts , bonus,chemin) qui, étant donné
l'ensemble des sauts par défaut rrpréscnté par la liste sauts, les sauts associés anz cases bomus
bonus rt un chemin chemin, envoie True si les sants utilisés dans le chemin sont corrects et
False sinon. On suppose que le chemin reste dans la rille.
On dit qu'un ensemble de sauts Cest bien formé s'il ne peut pas mener à un cycle. Autrement
dit, sil n'existe pas de suite de sauts construite à partir des sauts de C qui, en partant de la case
(0.0)permettrait d'arriver sur une case (i. i) puis de revenir àcettecase. Une condition suffsante
est que chaque saut (Öi, Sj)de l'ensemble de sauts C soit strictement positif lexicographiquenent,
condition notée (8i, 6j) > 0 et définie par :
ôi >0ou bien (8i =0et 6j > 0) (*)
Une suite de sauts Q est positive lexicographiguement, propriété notée 8 >0, si chaque saut
(Si. 6j) de 6 satisfait (*).
Question 4 Ecrire une fonction sauts_bien formes (sauts, bonus) qui, étant donné la liste
chaque saut
des sauts par défaut sauts et les sauts associés auz cases bonus bonus, vérifie que
le cas et False sinon.
de ces listes satisfait la condition (. La fonction renvoie True si c'est
utilisés satisfont la condition (*).
Dans le reste du sujet, on suppose que les sauts
N
Partie II : Recherche exhaustive
première solution est de tester
On cherche maintenant à calculer un chemin optimal. Une
minimum. L'¿numération de tous les
tous les chemins corrects et de retenir le chemin de poids
récursive suivante:
chemins corrects se fera avec la fonction auxiliaire
trouve_complet_rec(T, sauts,bonus, sauts_max,i,j)
associés aux cases
Étant donnés une grille de jeu T, les sauts par défaut sauts, les sautS
case (i, i), la fonction ci-dessus calcule un
bonus bonus, une valeur entière sauts max et une
forcenuent à(N - 1,N - 1).
chemin p de poids mininum partant de (i,)et n'arrivant pas sauts_min)
(poids min,
Inais ayant au plus sautsmax+1 cases. La fonctioll renvoie le couple
pet sauts min est la liste des sauts pour construire p.
oç poids min est le poids de
La valeur sauts max est utilisée pour limiter la complexité de la recherche. Ainsi, la longueur
horizon. Si
du résultat sauts min sera inférieure ou égale àsauts max. Cette limite est appelée
I'horizo) est assez grand, la fonction renvoie un chenmin optial partant de (i, j).
Question 5 Quelle est la longueur marimaleL d'un chemin de (0,0) à(N - 1,N - 1) pour
r'imyorte gucl ensemble de sauts satisfuisant (") Donner wn exemple d'ensemble de sauts par
défaut pour lequel se réalise ce chenin de lonqueur L. (4,9
(o
[Link]
Rhestion- Écrire la fonction auriliaire trouve Complet rec (T, sauts, bonus , sauts max, i,j)
et ta fonction principale trouve_complet (T , sauts3, bonus, sauts max) qui renvoie le couple
(poids, sauts) où poids est le poids liste des sauts
du chemin
trouvé. Quelle est la complexité du chemin trouvé et sauts est la
de cette fonction ?
AnestieHLa fonction trouve_complet rec les Tnêmes cal
perd beaucoup de temps àefaire valeur fizée de
Cuts. On peut laméliorer en une
sauts max.
enrgistrant les résultats déjà calculés pouralors la complezité?
Erpliquer en quelques lignes comment;procéder. Quelle serait
La recherche exhaustive d'un chemin optimal est obtenue en appelant trouvecomplet (T,
sauts, bonus , L) avec L la longueur maxinale d'un chemin dans I.
Partie III: Recherche gloutonne
etape, o
On peut redure la complexité de la recherche evhaustive en limitant, à chaque
COurante. Dou
nartir de la case
1120 de la recerche, c'est-à-dire le nombre de sauts regardés à
I1dee de construire un algorithme olouton nor tro1Ver une solution. En partant de la Case (0, ):
on utiliSe la recherche exhaustive avec un e netit horizon » k pour déterminer la meuieure sue
minimal et d'au plus k sauts. On joue les sauts
loate de k SautS, C'est-à-dire la suite de poids
de la meilleure suite locale, puis on recommence sur la, case atteinte, jusqu'à la c£se d anve
une suite locale, alors
(N- 1, N-1). Si la recherche exhaustive avec 1'horizon k ne trouve pas
l'algorithme abandonne la recherche.
trouvé pour k=2? bst-u
Question 8 Sur l'exemple donné en introduction. guel est le chemin forcément un chemin de
obtient-on
optimal? Mêmes questions pour k =3. En auomentant k,
poids plus petit ?
Qfeston-0-Ecrire une fonction trouve_glouton(T,
sauts, bonus ,k) qui, étant donnés la
cases bonus bonus
défaut sauts, les sauts associés auz
grlle de jeu T, la liste des sauts par
et renvoie le couple (poids, sauts) où poids
et l'horizon k, effectue cette recherche gloutonne recherche
liste des sauts du chemin trouvé. Quand la
est le poids du chemin trouvéet sauts est la renvoie (INFINI, ]).
echaustive avec l'horizon k ne trouve pas de
suite locale, la fonction
programmation dynamique
Partie IV:Recherche par
dynamigue pour
une methode par programmation
On se propose maintenant de construire dépend des cases
chemin optimal. Comme la solution optimale en partant de (i,j)
trouver un bonus]
remplir un tableau poids_opt [i] [iLcode
bonus déiàrencontrées (dites activées), on va (i,j) et où la 3e dimension
optimal en partant de la case
gui contient le poids du chemin remplira un tablea
cases bonus aCtivees. En parallèle, on
(code bonus) encode l'ensernble des partant de la case (i s)
contient un Saut opima a jouer en
saut opt il[i [code bonus] qui optimal.
permettra de retrouver
un chemin
Ce tableau
activées
Encodagedes cases bonus
1) numérote les cases bonus de 0 à n-1.
nombre de cases
bonu. On On représente les
2 Soit n le liste de booléens (7nasque binaire)
bo,..,bh- où bk vaut True si
activées par une L'ensemble des cases
Cases bonus k est activée. bonus activées est encodé
la case bonus
...bo. où par
et seulenent si r e p r e s e n t a t i o n binaire est bn-l True=let False = 0. Ce code est noté
l'entier dont la exemple, le code asSocié au masque [False, False] est 0, le code associé au
(bo...bn-). Par
False] est 1, etc.
masque [True,
4 A (°)
oseUSant la orécuTTe uilnÉs une ulVante
Cases bonus
o-opt est [Link], sa b arille
[Link]
au
code associé
(masque_bonus)
qui renvoie le
Question 10 Écrire la fonction code_bonus
l'enmsemble des cases bonus
activées.
masque binaire masque bonus représentant
2) Récurrence valeurs
calculer les
récurrence pour
On va maintenant donner une
Cette récurrence
[j] [code bonus] Dour tout case (; i) et valeur de code _bonus.
[Link] [i]
sera utilisée dams la section suivante pour construire un [Link] temps. Si un chemin
cases bonus dans un
piner l'explication, ignorons les lui retirant (2,j) (en
case (2,j) a un poids minimal, alors le chemin obtenu en
e là calcule pOuT tous
un poids minimal. Une fois poids opt
e ce e là case suivante) a lui-même garder le plus petit et de lui ajouter le poids
les sueceSseurs possibles de la case (i. ). il suffit de
de la case T[i] [j]. On obtient ainsi poids -opt pour la case (2,J).
sauts supplémentaires
Avec les cases bonus, c'est le mÇme principe sauf qu'il faut gérer les
des cases bonus activées. Deux cas sont pOssibles :
i suffit de calculer
(i,j) n'est pas une Case bonus. Dans Ce Cas,
tous les Successeurs possibles (i.s,j_s)
poidsopt [i s] [j-s] [code_bonus] Dour
de la case (i, i) avec les sauts par défaut et les sauts associés à chaque case bonus
activée de code _bonus. Le poids_opt [i] [i] [code_bonus] est alors le minimum de ces
[Link] [i-s] [j-sl [code_bonus] auquel s'ajoute la pénalité T[i] [31 de la case (i,j).
(i,i) est une case bonus. Dans ce cas, c'est le même processus, sauf que : 1) parmi les
sauts possibles, on ajoute ceux activés par la case bonus et 2) on considère les successeurs
(is,j s) avec un nouveau code bonus code_bonus dans lequel la case bonus (i,j) est
activée:le minimum doit ainsi être calculé parmi les poids-opt [is] [j_s] [code_bonus].
Sicode_bonus = (bo... bn-1), en notant k le numéro de la case bonus (i, j), on changera
b7 àTrue pour obtenir code_bonus' = (bo...bg...bn-1), où b = True.
Ouestio t1 tcrire la définition de [Link] [i] [j1 [(bo... bn-1)]. On notera T l'ensemble
des sauts par défaut et A; l'ensemble des sauts associé à la k-ième case bonus.
3) Algorithme
On évalue itérativement les diftérentes cases po1ds_opt LiJ LjJ Lcode _bonus] de poidsopt
dn trois boucles imbriquées itérant respectivement sur i, jet le masque de
bomus (d'où
y tirora code bonus). La diffhiculte est de trouver un ordre d'évaluation correct. À Drtir de la
récurrence, on voit que poids_opt [i] L3] t([Link]-1)] doit être évalué après avoir ghten
poids des successeurs : [Link] [itoz] [j +oj] [(b6...b,_)1.
e (8; &i) >0(condition (*)), alors + 0u > i ou bien ßi = 0 et /
itérations sur iet jdoivent etre < à l'envers >, de N - 1 À 0
+ 8i >i, donc les
Cris 1H...._J est égal a |b0;** n-l| SOt (00**n- est obtenu
à partir de
b-len mettant un b7 a 1rue. d' autres terines, le choix de bous renromtA
l est inclus dans le choix e bonus represente par (bo,...,b,,_]. par
itérer par choi: de bonus La boucle sur
doit donc décroissant au sens de
les masques de bonus ll'inclusion.
ordre est le suivant :
Avec 3 cases bonus, un
[True,True, True], puis
[Link],TrueJ, LTrue, False, TrueJ, [True, True , Fal se) . t
rEelae. False,True], lFalse , True,Falsel, lTrue, False , Falsel. is
False]
[False,False ,
6
[Link]
Par contre, les
Noter que les choix rassemblés
sur une ligne ne sont pas classables entre [Link] de la ligne
choix d'une ligne sont strictement supérieurs au sens de l'inclusion àl'un des
suivante. comme
Un algorithme pour calculer l'ordre d'évaluation des masques de bonus peut procéder
construit la
suit. On commence par le choix total, dans notre exemple [True ,True, True]. On False. Par
True à
ligne suivante en insérant les choix obtenus en basculant une COordonnée
False]. On
itère
exemple, on insère [False, True,True], (True, False, True], [True,True,lorsqu'on atteint le
ensuite sur chaque choix obtenu pour construire la ligne d'après. On s'arrêteune file pour défiler
choix vide, dans notre exemple [False,False , False]. On pourra utiliser la ligne suivante.
les choix de bonus àtraiter et enfiler progressivement les choix de bonus de
nombre
qui, étant donné le
_bonus (nb _bonus)
Question 12 Écrire une fonction combinaisons bonus oTdonnée
de manière
total de cases bonus nb _bonus, renvoie la liste de masques
décroissante dans le sens de l'inchusion, en codant l'algorithme
ci-dessus.
couple
ranger bonus (bonus) qui renvoie un
On suppose quilexiste une fonction
(bonus_au rang, rang_du_bonus) tel que :
est K,
la case bonus dont le numéro
bonus_au rang [k] est la liste des sauts activés Dar
numéro de la case bonus (i.j) dans
un masque de bonus.
rang du_bonus[(i,j)]est le
la question suivante et pouT la
résultat de cette fonction est utilisé comme paramètre pour
Le
fonction ajouter_bonus décrite après.
Question 13 Ecrire une fonction
bonus_au_rang, masque_bonus)
trouver_sauts_possibles
(sauts,
bonus_au rang renvOyée par
par défaut sauts, la liste
gui. étant donnés les sauts renvoie l'ensemble des
et le masque des bonus activés masque_bonus,
ranger bonus (bonus)
sauts possibles.
suppose donnée
une fonction
On
rang_du_bonus,l,],bonus_actifs,
code_bonus actifs)
aiouter bonus (bonus ,
activées code_bonus actife
( , ) dans le code des cases bonus _bonus_actifs L'opemee.
aui active la case bonus renvoie code
case bonus, là tonction
Si (G i) n'est pas une par ranger-bonus (bonus) et
l'argument henyo
structure renvoyee
rang du bonus est la est code_bonus_actifs.
dont le code
masque des bonus actifs
est le
incomplet de la page suivante implémente la fonction
code Python
Question 14 Le (T, sauts, bonus) qu, étant ddonnés une grille de jeu T, la liste des sauts
trouve_dynamique
bonus bonus, calcule le
associés auz cases chemin optimal par
et les sauts
par défaut sauts utilisant la récurrence trouvée en question 11. Le résultat de la
dynamique en
sautsopt) où poids opt est le poids du
programmation
(poids-opt,
est le couple chemin chemin optimal
fonction des sauts de ce
sauts_opt est la liste
trouvé et par s
manquantes
indiquées dans le code.
Donner les sept parties
1. fonction
complerité de cette
2. Quelle est la
6
[Link]
):
trouve_dynamique
(T, sauts , bonus
def
N = len (T)
nb_bonus= len (bonus)
# A COMPLETER (1)
)]
(nb_code_bonus
nb_code_bonus = in range
bonus_code
for (N)]
poids_opt = [[[INFINI for i in range
for j in range (N) ] (nb_code_bOnus)]
range
,0) for bonus code in
saut_opt = [II(O,0
for i in range (N)]
for j in range (N)] (bonus)
ranger_bonus
, rang_du_ bonus) =
(bonus_au_rang (nb_bonus):
combinaisons_ bonus
for bonus_actifs in
(bonus_actifs)
code bonus
code bonus_ actifs = [ c o d e _ b o n u s _ a c t i f s ] = # A COMPLETER (2)
poids_opt [N-1] [N-1] # A COMPLETER (3)
sauts_possibles = # A COMPLETER (4)
for i in range (. ..): #A COMPLETER (5)
for j in range (. ..): rang_du_bonus,i,j,
code_bonus_ dest = ajouter_bonus (bonus , code_bous_actifs)
bonus_actif s ,
if (i,j) in bonus:
sauts_possibles final = sauts_possibles + bonus [ ( i , i ) ]
else :
sauts_possibles_final = sauts possibles
possibles final:
for (delta_i , delta_j) in Sauts
i_dest = i+delta i
j_dest = j+ delta_j
if (i_dest in range (N) and j _dest in range (N)) :
poids_opt_dest = poids_opt [i_dest] [j_dest] [code_ bonus_dest]
if (poids _opt[iJ[jJ[code_bonus_actifs] > poids_opt_dest):
poids_opt [i][j][code_bonus_ actifs] = .. # A COMPLETER (6)
saut_opt [i]Lj][code_bonus_actifs] = # A COMPLETER (7)
poids_opt [i[j] [code_bonus_actifs] += T[i][i]
return (poids_opt,saut_opt)
Question 15 Écriela fonction solution dynamique([Link], N) qui, étant donnés la struc
ture saut opt calculée dans la question précédente et a dimension N de la grille, renvoie le
chemin optimalcorrespondant. La fonction renvoie le chemin vide [] s'ln'eriste pas de chemin
entre la case de départ et celle d'arrivée.
F N
