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.