Centrale Informatique optionnelle MP 2018

Thème de l'épreuve Étude du jeu Ricochet Robots
Principaux outils utilisés recherche dichotomique, tri par insertion, graphes, calcul de complexité en moyenne, programmation
Mots clefs dichotomie, table de hachage, file, graphe, parcours en largeur

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


t % Option informatique 00

"a , 1--l

_/ MP @

cnncuuns EENÏHHLE--SUPËLEE 4 heures Calculatrices autorisées N
Étude du jeu Ricochet Robots

À travers l'étude d'un jeu de société, ce sujet s'intéresse aux mouvements de 
robots, qui possèdent des capacités
limitées de localisation. Avec le développement de la robotique, plusieurs 
problèmes de ce type font l'objet
de nombreuses recherches: parcours minimum pour examiner une surface donnée, 
stratégies collectives avec
plusieurs robots en interaction proche, nombre de robots nécessaires pour que 
tous les points d'une surface avec
obstacles soient accessibles, etc.

Ce sujet porte sur la résolution de la situation pratique du jeu « Ricochet 
Robots » (Rasende Roboter pour la
première édition en allemand) créé par Alex Randolph en 1999. Ce jeu se déroule 
sur un plateau de 16 >< 16
cases, avec 4 robots et des murs. À chaque mouvement, un des robots se déplace, 
dans une des quatre directions,
jusqu'à ce qu'il rencontre un obstacle (un mur ou autre robot). Le but est de 
trouver le nombre de coups minimal
pour déplacer un robot particulier de son point de départ jusqu'à une case 
précise du plateau. Un exemple en
8 coups est donné figure 1.

Figure 1 Le jeu des robots : le but est d'amener le robot 1 sur la case 
hachurée. À gauche : deux
déplacements des robots 2 et 4 ; à droite : six déplacements du robot 1. Le jeu 
est résolu en 8 mouvements
(solution optimale)

On rappelle la définition des fonctions suivantes, disponibles dans la 
bibliothèque standard de Caml :

'-- copy_vect : 'a vect --> 'a vect telle que l'appel copy_vect v renvoie un 
nouveau tableau contenant
les valeurs contenues dans V ;

--- make_vect : int --> 'a --> 'a vect telle que l'appel make_vect n x renvoie 
un nouveau tableau de lon--
gueur n initialisé avec des éléments égaux à X ;

-- make_matrix : int --> int --> 'a --> 'a vect vect telle que l'appel 
make_matrix p q x renvoie une
nouvelle matrice a p lignes et q colonnes initialisée avec des éléments égaux à 
x.

I Déplacement d'un robot dans une grille

On considère pour le moment une grille sans robots du jeu Ricochet Robots. 
Notons N le nombre de cases par
ligne et colonne de la grille (16 dans le jeu originel). Dans les fonctions 
demandées, on supposem que N est une
variable globale. On numérote chaque case par un couple (a, b) de [[0, N -- 
1]]2, correspondant a la ligne a et a
la colonne b. On numérote également les lignes horizontales et verticales 
séparant les cases à l'aide d'un entier
de [[0, N ], de sorte que la case (a, b) est délimitée par les lignes 
horizontales a (au dessus) et a + 1 (en dessous),
de même que par les lignes verticales b (à gauche) et b + 1 (à droite) (figure 
2).

2018-03--02 09:00:32 Page 1/6 @c BY--NC-SA

2 3 4 5 6 7 8 9101112131415 0 1 2 3 4 5 6 7 8 910111213141516

0
0

1
1

2
2

3
3

4
4

5
5

6
6

7
7

8
8
9 9

10
10

11
11

12
12

13
13

14
14
15 15

16

Figure 2 A gauche : numérotation des cases par ligne/ colonne ; a droite : 
numérotation des lignes
horizontales et vertica_es

Pour représenter en Caml la grille avec ses obstacles, on se donne deux 
tableaux (vecteurs) de taille N. Le premier
contient les obstacles verticaux sur chacune des lignes, le second contient les 
obstacles horizontaux sur chacune
des colonnes. Un obstacle est donné par le numéro de la ligne (verticale ou 
horizontale) auquel il appartient.
Les obstacles sur une ligne (ou colonne) sont donnés sous la forme d'un tableau 
ordonné dans l'ordre croissant.
Par exemple, la représentation du plateau de la figure 1 est donnée figure 3.

let obstacles_lignes = [| [|O; 4; 10; 16|]; UC; 14; 16|]; [|O; 6; 16|];
EIO; 9; 16l]; Elo; 3; 15; 16l]; Elo; 7; 16l]; Elo; 1; 12; 16l1; Elo; 7; 9; 16l];
Elo; 7; 9; 16l]; Elo; 4; 13; 16l]; Elo; 6; 16l]; Elo; 10; 16l]; Elo; 8; 16l];
Elo; 2; 15; 16I1; Elo; 4; 10; 16I1; Elo; 5; 12; 16I1 I];;

let obstacles_colonnes = [| [|O; 5; 11; 16l]; [IO; 6; 13; 16|]; flo; 4; 16l];
[|O;15;16|]; [|0;10;16|]; [|0;8;16|]; [|0;10;16|]; flo; 6; 7; 9; 12; 16|];
Elo; 7; 9; 16I]; El0; 3; 12; 16I]; EI0; 14; 16I1; El0; 16I1; El0; 7; 16I];

[|o; 2; 10; 16l]; Elo; 4; 13; 16l]; Elo; 2; 12; 16l] I];;

Figure 3 Exemple de représentation en Caml

Notez que les bordures de la grille sont considérées comme des obstacles. 
Ainsi, les entiers () et N sont présents
dans les tableaux associés à chaque ligne / colonne.

Q 1. Écrire une fonction dichotomie a t de signature int --> int vect --> int 
telle que si t est un
tableau d'entiers strictement croissants et a un élément supérieur ou égal au 
premier élément du tableau et
strictement inférieur au dernier, la fonction renvoie l'unique indice 1 tel que 
t.(i) < a < t.(i + 1). La fonction
doit avoir une complexité logarithmique en la taille du tableau.

On considère un robot positionné en (a, b), avec 0 g a, b < N. Il peut se 
déplacer dans les quatre directions
cardinales ouest / est / nord / sud représentées sur la figure 4.

nord
A

ouest 4 ......... O ........ ., est

%
sud

Figure 4 Déplacements cardinaux

Q 2. Écrire une fonction deplacements_gtille (a,b) de signature int * int --> 
(int * int) vect
fournissant les 4 cases atteintes par les déplacements en question, sous forme 
d'un tableau a 4 éléments

2018-03--02 09:00:32 Page 2/6 (cc BY--NC-SA

(Ouest / est /nord/ sud). Si le robot ne peux pas bouger dans une direction 
donnée (car il est contre un obs--
tacle), on considérera que le résultat du déplacement dans cette direction est 
la case (a, b) elle--même. Les deux
tableaux obstacles_lignes et obstacles_colonnes sont des variables globales.

Q 3. Écrire une fonction matrice_deplacements (), de type unit --> (int * int) 
vect vect vect pro--
duisant une matrice m telle que m. (a) . (b) contienne le vecteur des 
déplacements possibles pour un robot depuis
la case (a, b), et ce pour tous 0 < a, b < N. Donner la complexité de création 
de la matrice.

On cherche maintenant à intégrer les positions d'autres robots dans le 
déplacement d'un robot. On utilise la
fonction précédente pour créer une matrice mat_deplacements que l'on 
considérera comme globale.

Q 4. Écrire une fonction modif t (a,b) (c,d) de signature
(int * int) vect --> int * int --> int * int --> unit

telle que si t est le tableau de taille 4 donnant les déplacements ouest /est / 
nord/ sud d'un robot placé en (a, b)
dans la grille ne contenant pas d'autres robots, et (c, d) la position d'un 
autre robot, alors la fonction modifie
si nécessaire le tableau t en prenant en compte le robot en (c, d).

On s'intéresse maintenant au déplacement d'un robot situé en (a, b) dans la 
grille, avec d'autres robots éven--
tuellement présents, dont les positions sont stockées dans une liste.

Q 5. Déduire des questions précédentes une fonction deplacements_robots (a,b) q 
de signature
int * int --> (int * int) list --> (int * int) vect

donnant les déplacements ouest / est / nord / sud d'un robot situé en (a, b) 
dans la grille, les positions des autres
robots étant stockées dans la liste q. On ne modifiera pas la matrice 
mat_deplacements : on souhaite une copie
modifiée de mat_deplacements . (a) . (b).

Q 6. Si on suppose que la solution optimale demande au plus k mouvements, une 
solution possible pour
résoudre le jeu Ricochet Robots consiste à générer toutes les suites possibles 
de [{ déplacements. Avec 4 robots
en tout, estimer la complexité d'une telle approche (on utilisera la notation 
0).

La suite du problème a pour objet de proposer une solution plus efficace pour 
la résolution du jeu Ricochet
Robots.

II Quelques fonctions utilitaires

II.A -- Une fonction de tri

Q 7. Ecrire une fonction insertion x q de signature 'a --> 'a list --> 'a list 
prenant en entrée un
élément x et une liste q triée dans l'ordre croissant, et renvoyant une liste 
triée dans l'ordre croissant, constituée
des éléments de q et x.

Q 8. En déduire une fonction tri_insertion q de signature 'a list --> 'a list 
permettant de trier une
liste dans l'ordre croissant.

Q 9. Rappeler la complexité de ce tri dans le pire et le meilleur cas. Que 
peut--on dire de la complexité si
dans la liste q, tous les éléments excepté peut--être un sont dans l'ordre 
croissant '?

II.B * Quelques fonctions sur les listes

Q 10. Écrire une fonction mem1 x q de signature 'a --> ('a * 'b) list --> bool 
testant l'appartenance
d'un couple dont le premier élément est x dans la liste q.

Q 11. Écrire une fonction assoc x qde signature 'a --> ('a * 'b) list --> 'b 
renvoyant, s'il existe, l'élé--
ment y du premier couple (x.y) appartenant à la liste q.

II.C * Implantation d'une structure de file

On rappelle que l'on peut facilement implanter une structure de file a l'aide 
de deux listes : une des listes est
utilisée pour rajouter des éléments, l'autre pour enlever des éléments. On 
définit ainsi le type

type 'a file = {mutable entree: 'a list; mutable sortie: 'a list};;
Lorsqu'on veut retirer un élément de la file alors que la deuxième liste est 
vide, on remplace celle--ci par la

première, renversée.

On pourra utiliser les fonctions suivantes, qui permettent de manipuler une 
file ainsi définie :

creer_file_vide : unit --> 'a file crée une file vide

est_vide_file : 'a file --> bool teste si une file est vide

enfiler : 'a file --> 'a --> unit ajoute un élément a une file

defiler : 'a file --> 'a supprime l'élément en tête de file et le renvoie

On pourra supposer dans la suite que ces fonctions sont écrites de sorte que 
toute suite de p opérations
enfiler/defiler a partir d'une file vide (ne produisant pas d'erreur) se fait 
en complexité O(p).

2018-03--02 09:00:32 Page 3/6 (CC) BY--NC-SA

III Tables de hachage

Dans l'optique de résoudre le problème du jeu des robots, nous allons 
travailler sur un graphe dont les sommets
seront étiquetés par les positions des robots. Le nombre de sommets possibles 
étant élevé, il est nécessaire
d'utiliser une structure de données adaptée pour travailler sur ce graphe. Nous 
allons donc réaliser une structure
de dictionnaire permettant, en particulier, de tester facilement si un sommet a 
déjà été vu ou non et d'associer
un sommet a chaque sommet découvert.

Une structure de dictionnaire est un ensemble de couples (clé,élément), les 
clés (nécessairement distinctes)
appartenant à un même ensemble K, les éléments à un ensemble E. La structure 
doit garantir les opérations
suivantes :

-- recherche d'un élément connaissant sa clé ;
* ajout d'un couple (clé,élément) ;
-- suppression d'un couple connaissant sa clé.

Une structure de dictionnaire peut--être réalisée à l'aide d'une table de 
hachage. Cette table est implantée dans
un tableau de w listes (appelées alvéoles) de couples (clé, élément). Ce 
tableau est organisé de façon a ce que la
liste d'indice i contienne tous les couples (k, 6) tels que h...(k) : i où h... 
: K --> [[0, w -- 1]] s'appelle fonction de
hachage. On appelle w la largeur de la table de hachage et h...(k) le haché de 
la clé k.

Ainsi pour rechercher ou supprimer l'élément de clé k, on commence par calculer 
son haché qui détermine
l'alvéole adéquate et on est alors ramené à une action sur la liste 
correspondante. De même pour ajouter un
nouvel élément au dictionnaire on l'ajoute à l'alvéole indiquée par le haché de 
sa clé.

III.A * Une famille de fonctions h...

Nous commençons par nous doter d'une famille de fonctions h... pour les listes 
de couples de [[0, N -- 1]]2. Un
hachage naturel d'une liste comportant les couples (a- b')0gi

(int * int) list --> int calculant la quantité précédente. III.B * Tables de hachage de largeur fimée Dans cette sous--section, en fixe une largeur de hachage w. Un bon choix pour w serait par exemple un nombre premier ni trop petit, ni trop grand, comme 997. Pour les listes, on considérerait alors la fonction de hachage h997 donnée en Caml par hachage_liste 997. On définit en toute généralité le type suivant : type ('a, 'b) table_hachage = { hache: 'a --> int; donnees: ('a * 'b) list vect; largeur: int};; III.B.1) Implantation de la structure de dictionnaire Q 13. Écrire une fonction creer_table h wde signature ('a --> int) --> int --> ('a, 'b) table_hachage telle que creer_table h w renvoie une nouvelle table de hachage vide de largeur w munie de la fonction de hachage h. Q 14. Écrire une fonction recherche t kde signature ('a, 'b) table_hachage --> 'a --> bool renvoyant un booléen indiquant si la clé k est présente dans la table t. On pourra utiliser les fonctions de la partie H. Q 15. Écrire une fonction element t k de signature ('a, 'b) table_hachage --> 'a --> 'b renvoyant l'élément e associé à la clé [EUR dans la table t, si cette clé est bien présente dans la table. Q 16. Écrire une fonction ajout t k ede signature ('a, 'b) table_hachage --> 'a --> 'b --> unit ajou-- tant l'entrée (k, e) a la table de hachage t. On n'effectuera aucun changement si la clé est déjà présente. Q 17. Écrire enfin une fonction suppression t k de signature ('a, 'b) table_hachage --> 'a --> unit supprimant l'entrée de la clé k dans la table 15. On n'effectuera aucun changement si la clé n'est pas présente. III.B.2) Étude de la complexité de la recherche d'un élément Nous étudions ici la complexité de la recherche d'une clé dans une table de hachage. Dans le pire cas, toutes les clés sont hachées vers la même alvéole, ainsi la complexité de la recherche d'une clé dans une table de hachage n'est pas meilleure que la recherche dans une liste. Cependant, si la fonction de hachage hw est bien choisie, on 2018-03--02 09:00:32 Page 4/6 GC) BY--NC-SA peut espérer que les clés vont se répartir de façon apparemment aléatoire dans les alvéoles, ce qui donnera une complexité bien meilleure. Nous faisons donc ici l'hypothèse de hachage uniforme simple : pour une clé donnée, la probabilité d'être hachée dans l'alvéole i est 1/w, indépendante des autres clés. On note n le nombre de clés stockées dans la table et on appelle oz : n/w le facteur de remplissage de la table. On suppose de plus, que le calcul du haché d'une clé se fait en temps constant. Q 18. On se donne une clé k non présente dans la table. Montrer que l'espérance de la complexité de la recherche de [EUR dans la table est un O(1 + oz). Q 19. On prend au hasard une clé présente dans la table ; toutes les clés sont équiprobables. Montrer qu'alors la recherche de la clé se fait en O(1 + 04), en moyenne sur toutes les clés présentes. 111.0 + Tables de hachage dynamique Les deux questions précédentes montrent que l'on peut assurer une complexité moyenne constante pour la recherche dans une table de hachage, sous réserve que le facteur de remplissage oz soit borné. Il en va de même des opérations d'insertion et de suppression, pour peu que les clés a ajouter / supprimer vérifient des hypothèses d'indépendance. Bien souvent, et cela va être le cas dans notre problème, on ne sait pas a l'avance quel sera le nombre de clés à stocker dans la table, et on préfère ne pas surestimer ce nombre pour garder un espace mémoire linéaire en le nombre de clés stockées. Ainsi, il est utile de faire varier la largeur U) de la table de hachage : si le facteur de remplissage devient trop important, on réarrange la table sur une largeur plus grande (de même, on peut réduire la largeur de la table lorsque le facteur de remplissage devient petit). On parle alors de tables de hachage dynamiques pour ces tables à largeur variable. À une table de hachage dynamique est associée une famille de fonctions de hachage (h...). Par exemple, pour les listes de couples de [[O, N -- 1]]2, la fonction hachage_liste précédemment écrite fournit une telle famille. On définit en toute généralité le type suivant : type ('a, 'b) table_dyn = { hache: int --> 'a --> int; mutable taille: int; mutable donnees: ('a * 'b) list vect; mutable largeur: int};; On notera trois différences par rapport au type précédent : + la fonction hache possède un paramètre supplémentaire qui est la largeur de hachage, elle correspond main-- tenant a la famille de fonctions de hachage (hw) ; + on a rendu les champs donnees et largeur modifiables ; -- un champ taille (modifiable) est rajouté, il doit a tout moment contenir le nombre de clés présentes dans la table. Q 20. Écrire une fonction creer_table_dyn h permettant de créer une table de hachage dynamique initia-- lement vide, avec la famille de fonctions de hachage h et la largeur initiale 1. On admet avoir écrit deux fonctions recherche_dyn t k et element_dyn t k, variantes des fonctions recherche et element précédentes, basées sur le même principe. On va maintenant développer une stratégie pour maintenir à tout moment un facteur de remplissage borné. Q 21. Écrire une fonction rearrange_dyn 1: W2 prenant en entrée une table de hachage dynamique et une nouvelle largeur de hachage w2, qui réarrange la table sur une largeur w2. En supposant que le calcul des valeurs de hachage se fasse en temps constant, la complexité doit être en O(n + 0; + tu?) où n est le nombre de clés présentes dans la table (sa taille), il; est l'ancienne largeur de la table, 1112 la nouvelle. Une stratégie heuristique simple pour garantir que le facteur de remplissage reste borné, tout en garantissant une bonne répartition des clés dans le cas des listes de couples à valeurs dans [[0, N -- 1]] avec N : 16, est d'utiliser les puissances de 3 comme largeurs de hachage. Après ajout d'un élément à la table, si celle--ci est de taille strictement supérieure a trois fois sa largeur w, on la réarrange sur une largeur w' : 310. Q 22. Écrire une fonction aj out_dyn t k e ajoutant le couple (k, e) a la table de hachage (si la clé k n'est pas présente), en réarrangeant si nécessaire la table, en suivant le principe ci--dessus. Dans l'hypothèse que chaque ajout se fait en temps O(1 + oz), où oz est le facteur de remplissage de la table, on peut montrer qu'une série de p ajouts dans une table initialement vide prend un temps O(p). On pourrait écrire de même une fonction de suppression dynamique, de sorte de maintenir un facteur de remplissage de la table borné, et qu'une série de p opérations licites d'insertion/suppression dans la table prenne un temps O(p). 2018-03--02 09:00:32 Page 5/6 GC) BY--NC-SA IV Résolution du jeu des robots IV.A * Graphe orienté associé au jeu des robots La résolution du jeu des robots peut se faire en traduisant le problème sous forme d'un graphe dans lequel chaque sommet représente une position des robots sur le plateau de jeu. On distingue le « robot principal » (celui que l'on veut amener sur une case donnée) et les autres robots. Ainsi, un sommet est représenté par le type suivant : type sommet = {robot: int * int; autres_robots: (int * int) list};; Pour chaque sommet, on impose que la liste autres_robots soit triée dans l'ordre croissant en suivant l'ordre lexicographique (l'ordre naturel pour les couples en Caml). Cet ordre est défini par (a, b) < (of, b') si a < a' ou si a : a' et b { b'. Par exemple, Caml évalue l'expression (2,3) < (3,0) en true. Les arcs dans le graphe (orienté) sont définis naturellement : un sommet s est relié a un sommet s' si on peut passer de s a s' par un mouvement licite d'un des robots. Q 23. Avec p robots en tout sur un plateau de taille N >< N, quel est le nombre possible de sommets '? Donner le nombre exact pour p : 4 et N : 16. Q 24. Écrire une fonction sommets_accessibles s de type sommet --> sommet list prenant en entrée un sommet et renvoyant la liste des sommets accessibles via s a partir du déplacement d'un des robots. S'il y a p robots en tout, la fonction renverra une liste de 4p sommets, certains sommets pouvant être égaux au sommet s : ils correspondent au mouvement d'un robot dans une direction où il est bloqué. I V.B * Parcours en largeur : étude théorique On se donne un graphe G = (S, A) orienté, S dénote l'ensemble des sommets et A l'ensemble des arcs. On se donne un sommet 50 EUR S du graphe et on considère l'algorithme 1 (parcours en largeur). Entrées : un arbre G = (S, A), orienté, un sommet de départ 50 Sortie : un tableau de booléens, un tableau de prédecesseurs F <-- creer_file_vide( ) ; Enfiler 50 dans F ; bs0 % vrai ; bs <-- faux pour tout 5 EUR S ; (* un tableau de booléens pour chaque sommet, tous faux >k) 7rs <-- 5 pour tout 5 E S ; ("< un tableau de prédecesseurs pour chaque sommet, initialement als] : s >'<) tant que F est non vide faire 5 <-- defiler(F) ; pour tout s' voisin de 5 tel que bs, est faux faire bS, % vrai ; 7rS, <-- 5 ; enfiler s' dans F; fin pour fin tant que renvoyer b, 7r Algorithme 1 Parcours en largeur Q 25. Montrer que l'algorithme termine. Q 26. Montrer que l'algorithme visite tous les sommets s du graphe pour lesquels il existe un chemin de s() a 5. Q 27. Pour un sommet s visité par l'algorithme (c'est--à--dire tel que b5 soit Vrai a la fin de l'algorithme), expliquer à partir de 7r comment retrouver un chemin de so a 5. Q 28. Montrer que ce chemin est un plus court chemin de s() a 5. Q 29. On suppose que les voisins sont implantés par liste d'adjacence, la complexité est linéaire en le nombre de voisins pour les parcourir. Les opérations de file et les opérations sur les tableaux 7r et b s'effectuent en temps constant, donner la complexité de l'algorithme en fonction de |S | et |A|. Un parcours en largeur du graphe associé au jeu permet donc de trouver une solution qui nécessite le minimum de déplacements des robots. La difl'iculté dans l'implantation de cet algorithme réside dans le grand nombre de sommets du graphe. Pour pallier cette difiîculté, on remplace les tableauoe b et 7r par un dictionnaire implanté dans une table de hachage dynamique. Les clés et les éléments du dictionnaires sont tous les deurr des sommets du graphe tels que l'élément associé à la clé 5 soit 7rs. On remplace ainsi le test de bs, par l'emistence de la clé 5] dans le dictionnaire. oooFlNooo 2018--03--02 09:00:32 Page 6/6 («à BY--NC-SA

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



Centrale Informatique optionnelle MP 2018
Corrigé
Ce corrigé est proposé par Hugo Menet (ENS Lyon) ; il a été relu par Martin Guy
(ENS Lyon) et Guillaume Batog (professeur en CPGE).

L'épreuve propose de travailler sur le déplacement de robots placés sur une 
grille
parsemée d'obstacles via la résolution d'un jeu de société intitulé « Ricochet 
Robot ».
À cette occasion, le sujet fait appel à différentes facettes de 
l'algorithmique. On demande d'abord de concevoir quelques fonctions (en Caml) 
manipulant des tableaux
et des listes avant d'introduire une nouvelle structure de données, les tables 
de hachage. La dernière partie est consacrée à l'étude de graphes, notamment au 
parcours
en largeur. Le sujet comporte également quelques calculs de complexité (dont 
l'un
fait intervenir des probabilités) et des études du tri par insertion et de 
l'algorithme
de parcours en largeur d'un graphe.
· La première partie est consacrée à la construction de fonctions manipulant des
tableaux qui modélisent les déplacements des robots sur la grille.
· La deuxième partie s'intéresse aux listes. On implémente le tri par insertion
et des tests d'appartenance à des listes de couples. Cette partie assez proche
du cours permet de vérifier que l'on a bien compris la manipulation de listes
en Caml.
· La troisième partie présente les tables de hachage, une structure de données
implémentant un « dictionnaire » qui est souvent utilisée en pratique : là où
une liste indexe des valeurs par des entiers 0, 1, 2, . . . , n - 1, un 
dictionnaire
associe des valeurs à des clés quelconques, par exemple des chaînes de 
caractères.
On travaille d'abord sur des tables de largeur fixée avant de se tourner vers
des tables dynamiques. La partie se termine par deux calculs de complexité
en moyenne.
· Pour la dernière partie, on introduit une modélisation du problème par un
graphe. On revient à cette occasion aux fonctions écrites dans la première 
partie
pour déterminer les voisins d'un sommet dans ce modèle. Pour finir, le sujet
propose une étude théorique de l'algorithme de parcours en largeur, avec des
questions sur la terminaison, la correction et la complexité.
Le sujet est très bien écrit et propose de travailler sur de nombreux aspects
du programme d'informatique optionnelle (tri, graphe, calcul de complexité, 
preuve
d'algorithme) et propose de nombreuses fonctions à programmer manipulant listes 
et
tableaux, ce qui en fait un exercice très formateur.
Dans le corrigé, les codes sont écrits en OCaml plutôt qu'en Caml Light, comme
le demandait pourtant l'énoncé, car c'est le langage qui deviendra obligatoire 
aux
concours à partir de la session 2019.

Indications
Partie I
1 Commencer par comparer a à l'élément placé au milieu du tableau et 
déterminer, à partir de cette comparaison, dans quelle moitié du tableau il faut
continuer la recherche.
2 Utiliser une seule fois la fonction dichotomie pour trouver les déplacements
dans deux directions opposées.
4 Écrire une condition pour que le robot en position (c, d) bloque l'autre robot
dans son déplacement de (a, b) vers (a , b ).
5 Écrire une fonction récursive qui parcourt la liste q pour mettre à jour la 
copie
de la matrice de déplacements robot par robot.
6 Dénombrer les suites de longueur k de couples (R, d) où R a 4 valeurs 
possibles,
l'indice d'un des 4 robots, et d a 4 valeurs possibles, ouest, est, nord, sud.
Partie II
7 Écrire une fonction récursive pour parcourir la liste q.
8 Partir de la liste vide et la garder triée en ajoutant un à un les éléments 
de q.
9 Un meilleur cas est donné par une liste déjà triée, un pire cas par une liste
triée dans l'ordre décroissant.
10 On cherche un élément de la forme (x,y) avec y quelconque dans une liste q
de couples.
11 Utiliser la même structure de fonction récursive que pour la question 10.
Partie III
12 Remarquer que si P =

p
P

i X2i alors P = 0 + X2 Q où Q =

i=0

p-1
P

i+1 X2i .

i=0

14 Utiliser la fonction mem1 de la question 10.
15 Adapter la fonction de la question 14 en utilisant cette fois la fonction 
assoc
de la question 11.
16 Utiliser la fonction mem1 de la question 10 pour séparer les deux cas.
17 Construire une fonction del1 sur le modèle de la fonction mem1 de la 
question 10 qui supprime un élément. Puis adapter la fonction de la question 16.
18 L'hypothèse de hachage uniforme simple implique que la clé k est choisie de
sorte que toutes les alvéoles sont équiprobables pour son haché hw (k). 
Exprimer alors le coût de la recherche de cette clé dans cette alvéole en 
fonction de
la longueur de celle-ci.
19 Les clés de la table sont également choisies de manière aléatoire dans cette
question. Utiliser la formule des probabilités totales pour en déduire la 
probabilité qu'une clé choisie uniformément parmi les clés de la table soit 
hachée
dans une alvéole fixée.
20 Adapter la réponse de la question 13.
21 Utiliser une fonction auxiliaire pour parcourir une liste afin de parcourir 
chacune des listes de la table donnees initiale. Pour chaque élément rencontré,
calculer son haché avec la nouvelle fonction de hachage et le placer dans la 
liste
correspondante dans une nouvelle table de données préalablement construite.
Pour la complexité, remarquer qu'on rencontre une seule fois chacun des n
éléments de la table.

22 Commencer par ajouter l'élément comme en question 16 en utilisant à nouveau
la fonction mem1 de la question 10 puis utiliser la fonction rearrange si 
besoin.
Partie IV
24 Utiliser la fonction deplacements_robots de la question 5. On pourra 
également utiliser la fonction insertion de la question 7. Il pourra être utile 
de
construire une fonction suppr pour supprimer un élément d'une liste.
25 Montrer qu'un sommet du graphe ne peut pas être ajouté deux fois dans la
file F.
26 Pour un sommet s quelconque accessible depuis s0 , montrer par récurrence que
tous les sommets d'un chemin de s0 à s sont ajoutés à F pendant l'exécution
de l'algorithme.
27 Remarquer qu'un chemin de s0 à s est un chemin de s0 à s auquel on ajoute
le parcours de l'arête entre s et s.
28 Considérer le lemme suivant : « Il existe un nombre qn de tours de boucle 
tant
que tel que la file F contient exactement l'ensemble des sommets à distance n
de s0 ». L'adapter, par exemple, en s'intéressant aux sommets qui n'ont pas
encore été enfilés dans F, afin de pouvoir le démontrer par récurrence.
29 Raisonner comme en question 21 et remarquer que
P
|V(s)| = 2 |A|
sS

où V(s) est l'ensemble des voisins du sommet s.

1 Appliquons le principe de la dichotomie pour rechercher un élément a dans un
tableau trié t. Après avoir comparé a avec l'élément b situé au milieu du 
tableau t,
la recherche continue de manière récursive dans la première ou la seconde 
moitié du
tableau, selon que a est inférieur ou supérieur à b.
Utilisons pour ce faire une fonction récursive recherche_sous_tableau de type
int -> int array -> int -> int -> int. Elle prend en argument l'élément a, le
tableau t et deux indices pour marquer le début et la fin d'un sous-tableau qui 
vérifie
l'invariant
t.(debut) 6 a < t.(fin)
Elle renvoie l'unique indice i du sous-tableau tel que
t.(i) 6 a < t.(i + 1)
Cette définition n'est valable que pour un tableau de taille au moins deux.
Comme on suppose le tableau de taille au moins deux, le cas de base de la 
fonction
récursive correspond au cas où le sous-tableau contient deux éléments, 
l'invariant
donne donc l'élément à renvoyer.
Pour un sous-tableau de longueur strictement supérieure à deux, une comparaison
entre a et l'élément b au milieu du sous-tableau permet de conserver soit le 
soustableau à gauche, dans le cas où a < b, soit le sous-tableau à droite. Pour 
conserver
l'invariant, on garde l'élément milieu dans chacun des sous-tableaux. Cela 
permet
également d'éviter de se retrouver à traiter un sous-tableau de taille 1 pour 
lequel la
fonction n'est pas définie (ce qui arriverait en coupant un tableau de taille 
trois en
deux sous-tableaux disjoints). De plus initialement on a bien
t.(0) 6 a < t.(n - 1)
où n est la taille du tableau t puisqu'on suppose que l'élément a en entrée est 
strictement inférieur au plus grand élément de t.
La quantité fin - debut décroît bien strictement à chaque appel récursif si
le cas terminal est celui d'un tableau de taille deux, et ce même si on garde
la quantité milieu et pas milieu - 1 comme on le fait habituellement pour
une recherche dichotomique.
let dichotomie a t =
let rec recherche_sous_tableau a t debut fin =
let milieu = (debut + fin)/2 in (* t.(debut) <= a < t.(fin) *)
if (debut + 1) = fin then debut
else
if a < t.(milieu) then
recherche_sous_tableau a t debut milieu
else
recherche_sous_tableau a t milieu fin
in recherche_sous_tableau a t 0 (Array.length(t)-1);;
On remarque que la fonction a bien une complexité logarithmique en la taille du
tableau comme demandé.
Du fait du changement de langage au programme, les fonctions sur les vect
de Caml Light sont remplacées par des fonctions sur les Array de OCaml.