X/ENS Informatique A MP 2020

Thème de l'épreuve Constructions et explorations de labyrinthes
Principaux outils utilisés preuve d'algorithmes, algorithmes de graphes, parcours de graphes, probabilités, programmation OCaml, file, plus court chemin
Mots clefs labyrinthe, graphe, parcours, parfait, mélange de Knuth, profondeur, largeur, aléatoire, classes disjointes, algorithme d'Eller, Eller, monstre, distance

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                                            

Rapport du jury

(télécharger le PDF)
           

Énoncé obtenu par reconnaissance optique des caractères


ECOLE POLYTECHNIQUE - ECOLES NORMALES SUPERIEURES

CONCOURS D'ADMISSION 2020

!

MARDI 21 AVRIL 2020 - 14h00 ­ 18h00
FILIERE MP (Spécialité Informatique)
Epreuve n° 4
INFORMATIQUE A
(XULCR)

Durée : 4 heures
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve
Cette composition ne concerne qu'une partie des candidats de la filière MP,
les autres candidats effectuant simultanément la composition de Physique et
Sciences de l'Ingénieur.
Pour la filière MP, il y a donc deux enveloppes de Sujets pour cette séance.!

0
0

1

···

0

-1

×
{0, 1, . . . , × - 1}
·

( + 1)

0

< -1 · ( + ) 0 < ( - 1) × 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 0 >0
{0, 1, . . . , - 1}

{0, 1, . . . , - 1}

0

-1

0

-1

( , )

( , )

A
A
0 , · · · , r-1

A

O(f (0 , · · · , r-1 ))

0 , · · · , r-1

C > 0

0 , · · · , r-1
C f (0 , · · · , r-1 )

0

< = x 0 x Pr(x = ) = 1 . x 0 < < 0 < x = Pr(x = ) = 1 < 0 < {0, 1, . . . , - 1} = = = = = {0, 2, 5, 6} {1} 5 1 {3, 4} 3 {0, 1, . . . , - 1} 0 < = = {0, 2, 5, 6} {1} 0, 2, 4, 6 {0, 1, . . . , - 1} 0 , < 2k k k k 0 = {0, 1, . . . , - 1} =0 {3, 4} {0, 1, . . . , - 1} O(log ) {0, 1, . . . , - 1} X X X × {0, 1, . . . , × - 1} ( + 1) +1 1/2 +1 + + -1 + 0 < 0 -1- =7 =2 =4 =7 =5 =4 m -1 = -1 · (m, ) m · (m, ) (m, ) m (m1 , 1 ) < (m2 , 2 ) m1 < m2 (1, ) (1, ) (2, ) m1 = m2 (1, ) 1 < 2 (m, ) (-1, -1) · · (0, 0) · (1, 0) (m, ) = = (m, ) (m,  + 1) (-1, -1) · (m,  + 1) · (m + 1,  + 1) =0 =8 0 1 2 3 4 5 0  (0, 0) 1  (0, 1) 3  (1, 1) 2  (0, 2) 4  (1, 2) 5  (1, 3) 6 7 6  (1, 2) 7  (2, 3) 8  (1, 4) 8 =0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 = 11

Extrait du corrigé obtenu par reconnaissance optique des caractères



X/ENS Informatique A MP 2020 -- Corrigé
Ce corrigé est proposé par Benjamin Monmege (enseignant-chercheur à 
l'université) ; il a été relu par Vincent Puyhaubert (professeur en CPGE).

Ce sujet est consacré aux labyrinthes bi-dimensionnels, qui sont successivement
construits et explorés dans deux parties indépendantes.
· La première partie étudie plusieurs méthodes de génération de labyrinthes.
Le sujet s'intéresse plus spécifiquement aux labyrinthes dit parfaits, dans 
lesquels deux emplacements du labyrinthe sont reliés par exactement un chemin.
De tels labyrinthes peuvent être représentés par des graphes connexes et sans
cycle. Pour éviter trop de régularité, la génération utilise des nombres 
pseudoaléatoires grâce au mélange de Knuth qui permet de permuter aléatoirement
les éléments d'un tableau : on réalise un parcours en profondeur aléatoire d'un
graphe connexe, et on en déduit un labyrinthe parfait. Une autre méthode de
génération fait appel à la structure de classes disjointes, très classique. Une
dernière méthode, l'algorithme d'Eller, est étudiée pour générer des labyrinthes
sur des grilles rectangulaires.
· La seconde partie s'intéresse à la résolution d'un labyrinthe, c'est-à-dire 
la recherche d'un chemin d'un point source à un point destination. Puisqu'on 
souhaite sortir le plus rapidement possible du labyrinthe, on recherche des plus
courts chemins. L'algorithme de parcours en largeur, implémenté avec une file
à deux bouts, est étudié en premier. L'énoncé incorpore ensuite des monstres
dans le labyrinthe : la tâche devient alors de trouver un plus court chemin 
parmi
ceux passant par un minimum de monstres. Après une première tentative ne
résolvant que partiellement le problème, un algorithme plus délicat utilisant
trois files est étudié.
Ce sujet d'apparence ludique est en fait très technique. Les questions de 
correction
d'algorithme à base d'invariants de boucles sont nombreuses et de difficulté 
croissante.
L'énoncé indique parfois les invariants à montrer (questions 2, 7 et 10), 
d'autres
fois il demande plus d'autonomie (questions 4, 11), en particulier pour 
dérouler une
preuve de correction vue en cours pour le parcours en largeur (question 15). La
question 19 demande des arguments de preuve très délicats. A contrario, les 
questions
de programmation en OCaml sont plutôt raisonnables et la complexité n'est 
abordée
que superficiellement (question 8). Ce sujet nécessite une bonne connaissance 
des
algorithmes de graphes du cours : parcours en profondeur et largeur, 
algorithmes de
recherche de plus court chemin dans des graphes orientés pondérés (pour la 
dernière
question).

Indications
1 Attention au paramètre donné à la fonction Random.int pour qu'elle tire bien 
un
entier aléatoire dans l'ensemble {0, 1, . . . , i}.
2 Il faut montrer que l'invariant donné en indication de l'énoncé est vraie 
avant de
rentrer dans la boucles (i = 0) puis qu'il reste vrai lorsqu'on fait une 
itération
supplémentaire.
4 Un labyrinthe est parfait s'il ne contient aucun cycle, c'est-à-dire une 
séquence
non vide d'arêtes consécutives reliant un sommet à lui-même.
5 Écrire une fonction récursive ou bien une boucle while.
6 Utiliser la fonction cd_trouve de la question 5. Ne pas oublier de mettre les 
rangs
à jour après la réunion des classes.
8 Utiliser l'invariant de la question 7 pour calculer le rang maximal d'une 
classe,
puis faire le lien avec la complexité d'un appel à la fonction cd_trouve.
9 Employer la fonction aretes fournie par l'énoncé au début pour extraire 
l'ensemble des arêtes du graphe.
10 On pourra montrer un invariant un peu plus fort à savoir que les composantes
connexes du graphe h correspondent aux classes d'équivalence et que, pour tout
classe d'équivalence X, le sous-graphe de h induit par X est un labyrinthe 
parfait
du sous-graphe de g induit par X.
11 Remarquer d'abord que l'algorithme d'Eller ne crée pas de cycle dans le 
labyrinthe
h en cours de création. Pour prouver la connexité, montrer que la boucle 1 
satisfait
l'invariant suivant : après i itérations, toutes les composantes connexes du 
sousgraphe induit de h par les i + 1 premières lignes contiennent au moins un 
sommet
sur la ligne i + 1.
12 En partant d'un labyrinthe parfait particulier, montrer par récurrence sur i 
qu'il
existe des choix probabilistes de l'algorithme d'Eller tels que le sous-graphe 
induit
par le labyrinthe sur les i premières lignes est identique au labyrinthe parfait
obtenu à la fin de l'exécution de l'algorithme.
13 Attention à modifier le début de la file de sorte que cela reste un entier 
de l'intervalle [[ 0 ; n - 1 ]] (où n est la capacité maximale).
15 Il s'agit d'une question de cours. Une façon de faire consiste à montrer que 
la
distance calculée par l'algorithme est supérieure à la distance réelle depuis la
source. Puis, on peut montrer qu'à tout moment, la file contient des sommets de
distance croissante toutes contenues dans un ensemble {`, ` + 1} à deux 
éléments.
Cela permet alors de prouver que la distance calculée est correcte.
19 Observer que le nombre de monstres de tous les sommets dans les files f et
sources_courantes est identique. S'inspirer des invariants utilisés dans la 
question 15 pour estimer les longueurs des sommets dans les trois files. 
L'objectif est
de montrer que les sommets sont bien extraits de la file f par ordre croissant 
de
distance (dans l'ordre lexicographique).
20 Le défi est de réussir à coder des couples ordonnés par l'ordre 
lexicographique
à l'aide d'entiers. Ceci est possible ici car l'on connait l'ensemble des 
couples
possibles, qu'on peut alors mettre en bijection avec un ensemble [[ 0 ; M ]] 
d'entiers.

Publié dans les Annales des Concours

I. Construire des labyrinthes
1 Implémentons le mélange de Knuth à l'aide d'une boucle sur les indices du 
tableau
donné en entrée : pour chaque indice i, on utilise l'appel Random.int (i+1) 
pour le
choix aléatoire d'un indice dans l'ensemble {0, 1, . . . , i}, puis on réalise 
l'échange du
contenu des deux cases avec une variable temporaire.
let melange_knuth a =
for i = 0 to Array.length a - 1
do let j = Random.int (i+1) in
if j < i then begin let tmp = a.(i) in a.(i) <- a.(j); a.(j) <- tmp end done;; On peut remplacer les instruction begin .. end par de simples parenthèses : if test then ( action1; action2; ); Attention toutefois à ne pas les oublier, puisqu'une syntaxe de la forme if test then action1; action2; est interprétée sous la forme (if test then action1); action2; ce qui signifie qu'action2 est exécutée quel que soit le résultat du test. 2 Montrons que la boucle for dans la fonction melange_knuth appliquée au tableau a de longueur n satisfait l'invariant de boucle suivant : à la fin de l'exécution de i  [[ 0 ; n ]] tours de boucle, 1. si i > 0, pour tous p  [[ 0 ; i - 1 ]] et q  [[ 0 ; i - 1 ]], P(xp = q) = 
1/i ;
2. pour tout p  [[ i ; n - 1 ]], xp = p.
Pour i = 0, c'est-à-dire avant même de rentrer dans la boucle, la propriété est
vraie puisqu'alors la propriété 1 est trivialement vérifiée et la propriété 2 
est vérifiée
par le tableau a initial, par définition.
Supposons ensuite que la propriété est vraie à la fin de l'exécution de i tours 
de
boucle (pour i  [[ 0 ; n - 1 ]]) et montrons qu'elle reste vraie après le i + 
1-ième tour.
Lors de celui-ci, la valeur de a.(i) est modifiée. Pour tout p  [[ 0 ; n ]], 
notons xp la
valeur courante de la p-ième case du tableau avant ce tour, et yp cette valeur 
après
ce tour. Alors, par définition, en notant j le résultat du tirage aléatoire 
uniforme de
l'entier entre 0 et i inclus, on a

/ {i, j}
xp si p 
yp = xj si p = i

xi si p = j

Par la propriété 2, xi = i. Notons que pour tout p  [[ i + 1 ; n - 1 ]], yp = 
xp = p,
d'après la propriété 2. Ainsi, la propriété 2 est toujours vraie après 
l'itération. Pour la
propriété 1, notons J la variable aléatoire décrivant la valeur aléatoire 
choisie entre 0
et i. Considérons tout d'abord la probabilité P(yi = q) pour q  [[ 0 ; i ]]. 
Deux cas
sont possibles :
· si q = i, alors l'événement [yi = i] coincide avec l'événement [J = i] 
puisqu'on
a xi = i au début de l'itération courante. Ainsi,
P(yi = i) = P(J = i) =

1
i+1

· si q < i, alors l'événement [yi = q] n'est possible que si le tirage aléatoire de j a donné un résultat différent de i. Puisque {[J = j] | 0 6 j 6 i} est un système complet d'événements, P(yi = q) = i X P(yi = q, J = j) = j=0 i-1 X P(yi = q, J = j) j=0 Pour j  [[ 0 ; i - 1 ]], on a P(yi = q, J = j) = P(xj = q, J = j) Par indépendance du tirage aléatoire de j, on obtient P(yi = q, J = j) = P(xj = q) P(J = j) Ainsi, par la propriété 1, i-1 X 1 1 1 P(yi = q) = = i i + 1 i + 1 j=0 Dans tous les cas, on déduit la propriété 1 pour yi . Passons ensuite à l'étude de la probabilité P(yp = q) pour p  [[ 0 ; i - 1 ]] et q  [[ 0 ; i ]]. Considérons à nouveau deux cas : · si q = i, alors l'événement [yp = i] coincide avec l'événement [J = p], d'où P(yp = i) = P(J = p) = 1 i+1 · si q < i, alors l'événement [yp = q] coincide avec l'événement [xp = q, J 6= p] (le tirage aléatoire de j a donné un résultat différent de p, auquel cas yp = xp ). Par la propriété 1 et par indépendance du tirage aléatoire de j, on obtient P(yp = q) = P(xp = q, J 6= p) = P(xp = q) P(J 6= p) = 1 i 1 = i i+1 i+1 On a prouvé la propriété 2 après l'itération. Les propriétés 1 et 2 sont donc des invariants de la boucle. Par principe de récurrence, elles sont encore vraies à la sortie de la boucle, c'est-à-dire lorsque i = n. En particulier, la propriété 1 assure alors que (p, q)  [[ 0 ; n - 1 ]]2 P(xp = q) = 1 n