Centrale Informatique MP-PC-PSI 2017

Thème de l'épreuve Mars Exploration Rovers: mission d'exploration martienne
Principaux outils utilisés algorithmique, recherche de minimum, listes, SQL
Mots clefs numpy, calcul de distances, minimisation, algorithme génétique, algorithme du plus proche voisin, jointure, robot, Mars

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


 

ç, % ln ormatique "
"a « "'
__/ MP, PC, PSI, TSI @

UNEUURSEENTHHLE-SUPËLEE 3 heures Calculatrices autorisées N

Mars Eæploration Rovers
Mission d'eoeploration martienne

Mars Eæploration Rovers (MER) est une mission de la NASA qui cherche à étudier 
le rôle joué par l'eau dans
l'histoire de la planète Mars. Deux robots géologues, Spirit et Opportunity 
(figure 1), se sont posés sur cette
planète, sur deux sites opposés, en janvier 2004. Leur mission est de 
rechercher et d'analyser différents types de
roches et de sols qui peuvent contenir des indices sur la présence d'eau. Ils 
sont équipés de six roues et d'une
suspension spécialement conçue pour leur permettre de se déplacer quelle que 
soit la nature du terrain rencontré
Leur cahier des charges prévoyait une durée de vie de 90 jours martiens (le 
jour martien est environ 40 minutes
plus long que le jour terrestre). Spirit a cessé d'émettre le 22 mars 2010, 
soit 2210 jours martiens après son
arrivée sur la planète. Début 2017, Opportunity est toujours en activité et il 
a parcouru plus de 44 km sur Mars

Figure 1 Vue d'artiste d'un robot géologue de la mission Mars Exploration 
Rovers (NASA/JPL -- Cal--
tech / Cornell)

Chaque robot est équipé de plusieurs instruments d'analyse (caméra, microscope, 
spectromètres) et d'un bras
qui permet d'amener les instruments au plus près des roches et sols dignes 
d'intérêt. À partir de photographies de
la surface de la planète, prises à plusieurs longueurs d'ondes par différents 
satellites et par le robot lui--même, les
scientifiques de la NASA définissent une liste d'emplacements (points d'intérêt 
ou PI) où effectuer des analyses
Cette liste est transmise au robot qui doit se rendre a chaque emplacement 
indiqué et y effectuer les analyses
prévues. Chaque robot est capable d'effectuer un certain nombre de types 
d'analyses géologiques correspondant
aux difiérents instruments dont il dispose. Une fois tous les points d'intérêts 
visités et les résultats des analyses

2017--03.27 20:13:45 Page 1/8 E': 'BY'NC'SA

transmis à la Terre, le robot reçoit une nouvelle liste de points d'intérêts et 
démarre une nouvelle exploration.

Compte--tenu des contraintes de transmission entre la Terre et les robots 
(latence, périodes d'ombre, faible débit,

etc.) il est prévu que les robots travaillent en autonomie pour planifier le 
parcours de chaque exploration. Ainsi,

une fois la liste des points d'intérêt reçue, le robot analyse le terrain afin 
de détecter d'éventuels obstacles et

détermine le meilleur chemin lui permettant de visiter l'ensemble de ces points 
en dépensant le moins d'énergie

possible.

Après s'être intéressé à l'enregistrement des explorations, des points 
d'intérêts correspondants et des analyses

à y mener, ce sujet aborde trois algorithmes qui peuvent être utilisés par le 
robot pour déterminer le meilleur

parcours lui permettant de visiter chaque point d'intérêt une et une seule 
fois. Pour cela nous faisons quelques

hypothèses simplificatrices.

-- La zone d'exploration est dépourvue d'obstacle : le robot peut rejoindre 
directement en ligne droite n'importe
quel point d'intérêt.

-- Le sol est horizontal et de nature constante : l'énergie utilisé pour se 
déplacer entre deux points ne dépend
que de leur distance, autrement dit le meilleur chemin est le plus court.

-- La courbure de la planète est négligée compte tenu de la dimension réduite 
de la zone d'exploration : nous
travaillerons en géométrie euclidienne et les points d'intérêts seront repérés 
par leurs coordonnées cartésiennes
a l'intérieur de la zone d'exploration.

Les seuls langages de programmation autorisés dans cette épreuve sont Python et 
SQL. Toutes les questions

sont indépendantes. Néanmoins, il est possible de faire appel a des fonctions 
ou procédures créées dans d'autres

questions. Dans tout le sujet on suppose que les bibliothèques math, numpy et 
random ont été importées grâce

aux instructions

import math
import numpy as np
import random

Si les candidats font appel a des fonctions d'autres bibliothèques ils doivent 
préciser les instructions d'importa--
tion correspondantes.

Ce sujet utilise la syntaxe des annotations pour préciser le types des 
arguments et du résultat des fonctions à
écrire. Ainsi

def maFonction(n:int, x:float, d:str) --> np.ndarray:

signifie que la fonction maFonction prend trois arguments, le premier est un 
entier, le deuxième un nombre a
virgule flottante et le troisième une chaine de caractères et qu'elle renvoie 
un tableau numpy.
Une liste de fonctions utiles est donnée a la fin du sujet.

I Création d'une exploration et gestion des points d'intérêt

Une exploration est un ensemble de points d'intérêts à l'intérieur d'une zone 
géographique limitée, une série
d'analyses étant associée à chaque point d'intérêt. Chaque type d'analyse que 
le robot peut effectuer est codifié
et référencé par un nombre entier. Un point d'intérêt est repéré par deux 
entiers, positifs ou nuls, correspondant
a ses coordonnées cartésiennes en millimètres à l'intérieur de la zone 
d'exploration. L'ensemble des points
d'intérêts d'une exploration qui en contient 71 est représenté par un objet de 
type numpy.ndarray, à éléments
entiers, à 2 colonnes et n lignes, l'élément d'indice i , 0 correspondant a 
l'abscisse du point d'intérêt i et l'élément
d'indice i , 1 a son ordonnée.

% y
0 345 635
1 1076 415
2 38 859
3 121 582

Figure 2 Exemple d'exploration avec
quatre points d'intérêt

I.A * Génération d'une empl0mtion d'essai
I.A.1) Choix de points au hasard

a ) Afin de disposer de données pour tester les différents algorithmes de 
calcul de chemin qui seront développés
plus tard, écrire une fonction qui construit une exploration au hasard. Cette 
fonction d'entête

def générer_Pl(n:int, cmax:int) --> np.ndarrayz

20174)a27 20:13:45 Page 2/8 (cc) BY--NC-SA

prend en paramètres le nombre de points d'intérêts à générer et la largeur de 
la zone d'exploration (supposée
carrée) et renvoie un objet de type numpy.ndarray contenant les coordonnées de 
n points deux à deux
distincts choisis au hasard dans la zone d'exploration (figure 2).

b) Quelles contraintes doivent vérifier les arguments de la fonction générer_Pl 
'?

I.A.2) Calcul des distances
On dispose de la fonction d'entête

def position_robot() --> tuple:

qui renvoie un couple donnant les coordonnées actuelles du robot dans le 
système de coordonnées de l'exploration
à planifier. Ainsi l'instruction x, y = position_robot () permet de récupérer 
les coordonnées courantes du
robot.

Afin de faciliter l'application des différents algorithmes de recherche de 
chemin, on souhaite construire un tableau
des distances entre les différents points d'intérêt d'une exploration et entre 
ceux--ci et la position courante du
robot au moment du calcul. Ecrire une fonction d'entête

def calculer_distances(PI:np.ndarray) --> np.ndarray:

qui prend en paramètre un tableau de 71 points d'intérêt tel que décrit 
précédemment et renvoie un tableau de
nombres flottants, de dimension (n + 1) >< (n + 1), tel que l'élément d'indice 
i, j fournit la distance entre les
points d'intérêt i et ], l'indice n désignant le point de départ du robot.

I. B = Traitement d "image

On dispose de photographies d'une zone d'exploration effectuées à différentes 
longueur d'onde. Chaque photo--
graphie a été mises à l'échelle de la zone d'exploration puis stockée dans un 
tableau numpy (np.ndarray) a
deux dimensions. Les dimensions correspondent aux coordonnées géographiques du 
point photographié, chaque
élément est un entier, compris entre 0 et 255, donnant l'intensité du point 
considéré sur l'image. Ainsi l'élément
d'indice x , y contient un entier, compris entre 0 et 255, correspondant à 
l'intensité sur la photographie considérée
du point de coordonnées (a:, y). A partir de ces photographies, les géologues 
déterminent les endroits à analyser
en filtrant ceux qui ont un profil d'émission caractéristique de certaines 
roches intéressantes.

I.B.l) Analyse d'une image

La fonction F1 ci--dessous prend en paramètre une photographie représentée 
comme décrit plus haut. Expliquer
ce que fait cette fonction et décrire son résultat.

1 def F1(photo:np.ndarray) --> np.ndarray:
2 n = photo.min()

3 b = photo.max()

4 h = np.zeros(b -- n + 1, np.int64)

5 for p in photo.f1at:

6 h[p -- n] += 1

7 return h

I.B.2) Sélection de points d'intérêts

Écrire une fonction d'entête
def sélectionner_PI (photo :np.ndarray, imin: int , imax: int) --> np.ndarray:

où photo est un tableau représentant une photographie. Le résultat de la 
fonction sélectionner_PI est un
tableau a deux dimensions, de structure similaire a celui décrit figure 2, 
contenant les coordonnées des points
dont l'intensité sur la photographie est comprise entre imin et imax.

1.0 = Base de données

Afin d'assurer son autonomie opérationnelle, le robot dispose localement des 
informations nécessaires à son
fonctionnement quotidien. Ainsi, il enregistre la durée d'utilisation de ses 
différents instruments embarqués. ll
connait également les différents types d'analyses qu'il peut effectuer et, pour 
chacun de ces types, les instruments
à utiliser. Il enregistre la prochaine exploration, c'est--à--dire les 
différents points d'intérêts qu'il doit visiter et
pour chacun la ou les analyses qu'il doit effectuer. D'autre part, il conserve 
les résultats d'analyses effectuées
lors de ses explorations passées. Ces résultats ne sont effacés qu'après 
confirmation de leur bonne transmission
sur Terre.

Ces différentes informations sont stockées dans une base de données 
relationnelle dont le modèle physique est
schématisé figure 3.

2017--03--27 20:13:45 Page 3/8 @@ BY--NC-SA

EXPLÛ PI ANALY
EX_NUM integer <-- EX_NUM integer <-- EX_NUM integer
EX_CHG real PI_NUM integer <-- PI_NUM integer
EX_DEB real PI_X integer TY_NUM integer
EX_FIN real PI_Y integer AN_DAT real
EX_LAT real PI_ARR real AN_DTR real
EX_LON real PI_DEP real AN_RES blob

INSTR INTYP TYANA

IN_NUM integer TY_NUM integer _. TY_NUM integer «_
IN_FCT real \ IN_NUM integer TY_DES varchar(80)

IN_DER real IT_DUR real

IN_NUM varchar(80)

Figure 3 Structure physique de la base de données d'un robot

Cette base comporte les six tables suivantes :

-- la table EXPLO des explorations, avec les colonnes

EX_NUM numéro (entier) de l'exploration (clef primaire)

EX_CHG date de transmission des points d'intérêts de cette exploration

EX_DEB date de début de l'exploration (NULL si l'exploration n'est pas encore 
commencée)
EX_FIN date de fin de l'exploration (NULL si l'exploration n'est pas encore 
terminée)

EX_LAT latitude (en degrés décimaux) du point de coordonnées (0,0) de la zone 
d'exploration
EX_LON longitude (en degrés décimaux) du point de coordonnées (0,0) de la zone 
d'exploration

-- la table PI des points d'intérêts, de clef primaire (EX_NUM, PI_NUM), avec 
les colonnes

EX_NUM numéro de l'exploration a laquelle appartient le point d'intérêt

PI_NUM numéro du point d'intérêt dans l'exploration (au sein d'une exploration 
les Pl sont numérotés en
séquence en commençant à 0, ce numéro n'a pas de rapport avec l'ordre dans 
lequel les PI sont explorés
par le robot)

PI_X l'abscisse du point d'intérêt dans la zone d'exploration (entier positif 
en millimètres)

PI_Y l'ordonnée du point d'intérêt dans la zone d'exploration (entier positif 
en millimètres)

PI_ARR date d'arrivée du robot au point d'intérêt (NULL si ce point n'a pas 
encore été visité)

PI_DEP date a laquelle le robot a quitté le point d'intérêt (NULL si ce point 
n'a pas encore été exploré ou
si la visite est en cours)

* la table INSTR des instruments embarqués, avec les colonnes

IN_NUM le numéro (entier) de l'instrument (clef primaire)

IN_FCT la durée pendant lequel l'instrument a déjà été utilisé depuis l'arrivée 
sur la planète (nombre
décimal : fraction de jour martien)

IN_DER la date de la dernière utilisation de l'instrument

IN_NUM nom de l'instrument

* la table TYANA des types d'analyses à effectuer, avec les colonnes

TY_NUM le numéro de référence (entier) du type d'analyse (clef primaire)
TY_DES le nom du type d'analyse

-- la table INTYP des instruments utilisés pour un type d'analyse, de clef 
primaire (TY_NUM, IN_NUM), avec les
colonnes

TY_NUM le numéro de référence (entier) du type d'analyse

IN_NUM le numéro (entier) de l'instrument

IT_DUR la durée standard d'utilisation de l'instrument dans ce type d'analyse 
(nombre décimal : fraction
de jour martien)

* la table ANALY indiquant pour chaque point d'intérêt les types d'analyses a 
effectuer ou effectuées, de clef
primaire (EX_NUM, PI_NUM, TY_NUM) et avec les colonnes

EX_NUM numéro de l'exploration a laquelle appartient le point d'intérêt
PI_NUM numéro du point d'intérêt dans l'exploration
TY_NUM type de l'analyse

2017--03--27 20:13:45 Page 4/8 (CC) BY--NC-SA

. AN_DAT date de l'analyse (NULL si l'analyse n'a pas été effectuée)
. AN_DTR date de transmission sur Terre des résultats de l'analyse (NULL si 
l'analyse n'a pas été transmise)
. AN_RES résultat de l'analyse (donnée opaque dont la signification dépend du 
type d'analyse)

Toutes les dates sont stockées sous forme d'un nombre décimal correspondant au 
nombre de jours martiens
depuis l'arrivée du robot sur la planète.

I.C.1) Écrire une requête SQL qui donne le numéro de l'exploration en cours, 
s'il y en a une.
I.C.2) Écrire une requête SQL qui donne, pour une exploration dont on connait 
le numéro, la liste des points
d'intérêts de cette exploration avec leurs coordonnées.

I.C.3) Écrire une requête SQL qui donne la surface, en mètres carrés, de chaque 
zone déjà explorée par le
robot. La zone d'exploration est définie comme le plus petit rectangle qui 
englobe l'ensemble des points d'intérêts
de l'exploration et dont les bords sont parallèles aux axes de référence (axes 
des abscisse et des ordonnées).

I.C.4) Quelle est la surface maximale d'une zone d'exploration que peut stocker 
cette base de données '?

I.C.5) Écrire une requête SQL qui donne, pour l'exploration en cours, le nombre 
de fois où chaque instrument
doit être utilisé et sa durée d'utilisation théorique (en jours martiens) pour 
la totalité de l'exploration.

II Planification d'une exploration : première approche

Avant de démarrer une nouvelle exploration, le robot doit déterminer un chemin 
qui lui permet de passer par
tous les points d'intérêts une et une seule fois. L'enjeu de l'opération est de 
trouver le chemin le plus court
possible afin de limiter la dépense d'énergie et de limiter l'usure du robot.

Chaque point d'intérêt sera repéré par un entier positif ou nul correspondant a 
son indice dans le tableau des
points d'intérêt. Un chemin d'exploration sera représenté par un objet de type 
list donnant les indices des
points d'intérêt dans l'ordre de leur parcours.

II.A -- Quelques fonctions utilitaires
II.A.1) Longueur d'un chemin

Écrire une fonction d'entôte
def longueur_chemin(cheminzlist, d:np.ndarray) --> float:

qui prend en paramètre un chemin à parcourir et la matrice des distances entre 
points d'intérêt (telle que
renvoyée par la fonction calculer_distances) et renvoie la distance que doit 
effectuer le robot pour suivre
ce chemin en partant de sa position courante (correspondant à la dernière 
ligne/ colonne du tableau d) et en
visitant tous les points d'intérêt dans l'ordre indiqué.

II.A.2) Normalisation d'un chemin

Écrire une fonction d'entête
def normaliser_chemin(chemin:list, n:int) --> list:

qui prend en paramètre une liste d'entiers et renvoie une liste correspondant a 
un chemin valide, c'est--à--dire
contenant une seule fois tous les entiers entre 0 et n (exclu). Pour cela cette 
fonction commence par supprimer
les éventuels doublons (en ne conservant que la première occurrence) et les 
valeurs supérieures ou égales à 11,
sans modifier l'ordre relatif des éléments conservés, puis ajoute à la fin les 
éventuels éléments manquants en
ordre croissant de numéros.

II.B * Force brute

Pour rechercher le plus court chemin, on peut imaginer de considérer tous les 
chemins possibles et de calculer
leur longueur. On obtiendra ainsi a coup sûr le chemin le plus court.

II.B.1) Déterminer en fonction de n, nombre de points à visiter, le nombre de 
chemins possibles passant
exactement une fois par chacun des points.
II.B.2) Cet algorithme est--il utilisable pour une zone d'exploration contenant 
20 points d'intérêts '? Justifier.

II.C * Algorithme du plus proche voisin

Une idée simple pour obtenir un algorithme utilisable est de construire un 
chemin en choisissant systématique--
ment le point, non encore visité, le plus proche de la position courante.

II.C.1) Écrire une fonction d'entête
def plus_proche_voisin(d:np.ndarray) --> list:

qui prend en paramètre le tableau des distances résultat de la fonction 
calculer_distances (question l.A.2)
et fournit un chemin d'exploration en appliquant l'algorithme du plus proche 
voisin.

2017--03--27 20:13:45 Page 5/8 @@ BY--NC-SA

II.C.2) Quelle est la complexité temporelle de l'algorithme du plus proche 
voisin en considérant que cet
algorithme est constitué des deux fonctions calculer_distances et 
plus_proche_voisin '?

II.C.3) En considérant les trois points de coordonnées (0, 0), (0, 3000), (0, 
7000) et en choisissant un point de
départ adéquat pour le robot, montrer que l'algorithme du plus proche voisin ne 
fournit pas nécessairement le
plus court chemin.

Dans la pratique, on constate que, dès que le nombre de points d'intérêt 
devient important, l'algorithme du
plus proche voisin fournit un chemin qui peut être 50% plus long que le plus 
court chemin.

III Deuxième approche : algorithme génétique

Les algorithmes génétiques s'inspirent de la théorie de l'évolution en simulant 
l'évolution d'une population. Ils
font intervenir cinq traitements.

l. Initialisation
Il s'agit de créer une population d'origine composée de m individus (ici des 
chemins pour l'exploration à
planifier). Généralement la population de départ est produite aléatoirement.

2. Évaluation
Cette étape consiste à attribuer à chaque individu de la population courante 
une note correspondant a sa
capacité à répondre au problème posé. Ici la note sera simplement la longueur 
du chemin.

3. Sélection
Une fois tous les individus évalués, l'algorithme ne conserve que les « 
meilleurs » individus. Plusieurs mé--
thodes de sélection sont possibles : choix aléatoire, ceux qui ont obtenu la 
meilleure note, élimination par
tournoi, etc.

4. Croisement
Les individus sélectionnés sont croisés deux à deux pour produire de nouveaux 
individus et donc une nouvelle
population. La fonction de croisement (ou reproduction) dépend de la nature des 
individus.

5. Mutation
Une proportion d'individus est choisie (généralement aléatoirement) pour subir 
une mutation, c'est--à--dire
une transformation aléatoire. Cette étape permet d'éviter à l'algorithme de 
rester bloqué sur un optimum
local.

En répétant les étapes de sélection, croisement et mutation, l'algorithme fait 
ainsi évoluer la population, jus--
qu'à trouver un individu qui réponde au problème initial. Cependant dans les 
cas pratiques d'utilisation des
algorithmes génétiques, il n'est pas possible de savoir simplement si le 
problème est résolu (le plus court che--
min figure--t--il dans ma population ?). On utilise donc des conditions d'arrêt 
heuristiques basées sur un critère
arbitraire.

Le but de cette partie est de construire un algorithme génétique pour 
rechercher un meilleur chemin d'exploration
que celui obtenu par l'algorithme du plus proche voisin.

III.A -- Initialisation et évaluation

Une population est représentée par une liste d'individus, chaque individu étant 
représenté par un couple (lon--
gueur, chemin} dans lequel

-- chemin désigne un chemin représenté comme précédemment par une liste 
d'entiers correspondant aux indices
des points d'intérêt dans le tableau des distances produit par la fonction 
calculer_distances ;

-- longueur est un entier correspondant a la longueur du chemin, en tenant 
compte de la position de départ du
robot.

Écrire une fonction d'entête
def créer_population(m:int, d:np.ndarray) --> list:

qui crée une population de m individus aléatoires. Cette fonction prend en 
paramètre le nombre d'individus a
engendrer et le tableau des distances entre points d'intérêt (et la position 
courante du robot) tel que produit par
la fonction calculer_distances. Elle renvoie une liste d'individus, 
c'est--à--dire de couples ( longueur, chemin )

III.B -- Sélection

Écrire une fonction d'entête
def réduire(pzlist) --> None:
qui réduit une population de moitié en ne conservant que les individus 
correspondant aux chemins les plus

courts. On rappelle que p est une liste de couples ( longueur, chemin ) La 
fonction réduire ne renvoie pas de
résultat mais modifie la liste passée en paramètre.

2017-03-27 20:13:45 Page 6/8 (66 BY--NC-SA

III.C * Mutation

III.C.1) Écrire une fonction d'entête

def muter_chemin(czlist) --> None:

qui prend en paramètre un chemin et le transforme en inversant aléatoirement 
deux de ses éléments.
III.C.2) Ecrire une fonction d'entête

def muter_population(pzlist, probazfloat, d:np.ndarray) --> None:

qui prend en paramètre une population dont elle fait muter un certain nombre 
d'individus. Le paramètre proba
(compris entre 0 et l) désigne la probabilité de mutation d'un individu. Le 
paramètre d est la matrice des
distances entre points d'intérêt.

III.D * Croisement
III.D.1) Écrire une fonction d'entête

def croiser(cl:list, c2:list) --> list:

qui crée un nouveau chemin a partir de deux chemins passés en paramètre. Ce 
nouveau chemin sera produit en
prenant la première moitié du premier chemin suivi de la deuxième moitié du 
deuxième puis en « normalisant »
le chemin ainsi obtenu.

III.D.2) Écrire une fonction d'entête

def nouvelle_génëration(p:list, d:np.ndarray) --> None:

qui fait grossir une population en croisant ses membres pour en doubler 
l'effectif. Pour cela, la fonction fait se
reproduire tous les couples d'individus qui se suivent dans la population (p 
[i] , p [i+1]) et (p [m--1] , p[O])
de façon à produire m nouveaux individus qui s'ajoutent aux m individus de la 
population de départ.

III.E * Algorithme complet

III.E.1) Écrire une fonction d'entête
def algo_génétique(Pl:np.ndarray, m:int, proba:float, g:int) --> float, list:

qui prend en paramètre un tableau de points d'intérêts (figure 2), la taille m 
de la population, la probabilité
de mutation proba et le nombre de générations g. Cette fonction implante un 
algorithme génétique a l'aide
des différentes fonctions écrites jusqu'à présent et renvoie la longueur du 
plus court chemin d'exploration et le
chemin lui--même obtenus au bout de g générations.

III.E.2) Est--il possible avec l'implantation réalisée, qu'une itération de 
l'algorithme dégrade le résultat : le
meilleur chemin obtenu à la génération n + 1 est plus long que celui de la 
génération n ?

Dans l'affirmative, comment modifier le programme pour que cette situation ne 
puisse plus arriver '?

III.E.3) Quelles autres conditions d'arrêt peut--on imaginer '? Établir un 
comparatif présentant les avantages
et inconvénients de chaque condition d'arrêt envisagée.

Opérations et fonctions Python disponibles

Fonctions
-- range (n) renvoie la séquence des 11 premiers entiers (O --> n -- l)
-- list (range (n)) renvoie une liste contenant les 11 premiers entiers dans 
l'ordre croissant :
list(range(5)) _) [O, 1, 2, 3, 4]
-- random.randrange (a, b) renvoie un entier aléatoire compris entre a et b--1 
inclus (a et b entiers)
-- random . random() renvoie un nombre flottant tiré aléatoirement dans {D, Il 
suivant une distribution uniforme
-- random. shuffle (u) permute aléatoirement les éléments de la liste 11 
(modifie u)

-- random.sample(u, n) renvoie une liste de 11 éléments distincts de la liste 
11 choisis aléatoirement, si n >
len(u), déclenche l'exception ValueError

-- math. sqrt (x) calcule la racine carrée du nombre oe
-- math. ceil (x) renvoie le plus petit entier supérieur ou égal à x

2017-03-27 20:13:45 Page 7/8 @@ BY--NC-SA

math. floor(x) renvoie le plus grand entier inférieur ou égal à x

sorted(u) renvoie une nouvelle liste contenant les éléments de la liste u triés 
dans l'ordre « naturel » de ses
éléments (si les éléments de u sont des listes ou des tuples, l'ordre utilisé 
est l'ordre lexicographique)

Opérations sur les listes

1en(u) donne le nombre d'éléments de la liste u :

1en([1, 2, 3]) --> 3; len([[1,2] , [3,4]]) --> 2

u + v construit une liste constituée de la concaténation des listes u et v :

[l, 2] + [3, 4, 5] --> [1, 2, 3, 4, 5]

n * u construit une liste constitué de la liste u concaténée 11 fois avec 
elle--même :
3 *[1, 2] --> [1, 2, 1, 2, 1, 2]

e in 11 et e not in u déterminent si l'objet e figure dans la liste u, cette 
opération a une complexité
temporelle en O(len(u))

2 in [1, 2, 3] --> True ; 2 not in [1, 2, 3] --> False

u. append(e) ajoute l'élément e a la fin de la liste u (similaire a u = u + [e])

del u[i] supprimé de la liste 11 son élément d'indice i

del u [i : j] supprime de la liste u tous ses éléments dont les indices sont 
compris dans l'intervalle li, jl

u . remove (e) supprime de la liste u le premier élément qui a pour valeur e, 
déclenche l'exception ValueError
si e ne figure pas dans u, cette opération a une complexité temporelle en 
O(len(u))

u. insert (i , e) insère l'élément e a la position d'indice i dans la liste 11 
(en décalant les éléments suivants) ;
si 1 >= 1en(u), e est ajouté en fin de liste

u[i] , u[j] = u[j] , u[i] permute les éléments d'indice i et j dans la liste u

u. sort () trie la liste u en place, dans l'ordre « naturel » de ses éléments 
(si les éléments de u sont des listes
ou des tuples, l'ordre utilisé est l'ordre lexicographique)

Opérations sur les tableauæ (np.ndarray)

np . array(u) crée un nouveau tableau contenant les éléments de la liste u. La 
taille et le type des éléments
de ce tableau sont déduits du contenu de u

np.empty(n, dtype), np. empty( (n, m) , dtype) crée respectivement un vecteur à 
11 éléments ou une ma--
trice à 11 lignes et m colonnes dont les éléments, de valeurs indéterminées, 
sont de type dtype qui peut être
un type standard (bool, int, float, .) ou un type spécifique numpy (np.int16, 
np.float32, ..). Si le
paramètres dtype n'est pas précisé, il prend la valeur float par défaut

np.zeros(n, dtype), np.zeros((n, m) , dtype) fonctionne comme np.empty en 
initialisant chaque élé--
ment a la valeur zéro pour les types numériques ou False pour les types booléens

a.ndim nombre de dimensions du tableau a (1 pour un vecteur, 2 pour une 
matrice, etc.)
a. shape tuple donnant la taille du tableau a pour chacune de ses dimensions

1en(a) taille du tableau a dans sa première dimension (nombre d'éléments d'un 
vecteur, nombre de lignes
d'une matrice, etc.) équivalent à a. shape [0]

a. size nombre total d'éléments du tableau a
a. flat itérateur sur tous les éléments du tableau a

a.min(), a.max() renvoie la valeur du plus petit (respectivement plus grand) 
élément du tableau a; ces
opérations ont une complexité temporelle en O(a.size)

b in a détermine si b est un élément du tableau a ; si b est un scalaire, 
vérifie si b est un élément de a ; si
b est un vecteur ou une liste et a une matrice, détermine si b est une ligne de 
a

np . concatenate ( (al , a2)) construit un nouveau tableau en concaténant deux 
tableaux ; al et a2 doivent

avoir le même nombre de dimensions et la même taille à l'exception de leur 
taille dans la première dimension
(deux matrices doivent avoir le même nombre de colonnes pour pouvoir être 
concaténées)

oooFlNooo

2017--03--27 20:13:45 Page 8/8 (GQ BY--NC-SA

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



Centrale Informatique commune MP 2017 --
Corrigé
Ce corrigé est proposé par Cyril Ravat (professeur en CPGE) ; il a été relu par
Julien Dumont (professeur en CPGE) et Jean-Julien Fleck (professeur en CPGE).

Ce sujet d'informatique a pour contexte la mission martienne Mars Exploration
Rovers. Celle-ci conduit à une étude en trois parties des aspects robotiques de 
l'exploration, principalement le déplacement du système sur une carte : calculs 
de distances
parcourues et optimisation du chemin reliant tous les points suivant deux 
approches.
De nombreuses questions font intervenir des tableaux numpy, donc l'utilisation 
des
fonctions associées, alors que des listes de listes suffiraient la plupart du 
temps.
Un catalogue de ces fonctions est fourni en fin de sujet, avec des explications 
claires
et des exemples.
· La première partie est composée de trois sous-parties indépendantes et de 
difficultés inégales : la première permet de réaliser deux fonctions 
élémentaires de
génération de carte et de calcul de distance ; la deuxième traite très 
brièvement de traitement d'image ; la troisième étudie le fonctionnement de la 
base
de données des analyses à effectuer. On regrette la difficulté importante de la
première question, qui a dû décourager nombre de candidats, du moins ceux
qui ont correctement lu le sujet. Comparativement, les deux questions sur le
traitement d'image sont d'une simplicité déconcertante. Enfin, on note que les
requêtes SQL demandent l'utilisation d'une syntaxe (IS NULL) conceptuellement 
complexe et certainement peu enseignée.
· La deuxième partie aborde le problème très classique dit « du voyageur de
commerce » : il faut optimiser le passage du robot par tous les points d'une 
liste
une seule et unique fois. On met en place ici quelques fonctions élémentaires 
puis
on réalise l'algorithme glouton du plus proche voisin. L'ensemble est équilibré
et suffisamment progressif en termes de difficulté.
· La dernière partie continue le travail précédent en proposant pour le même
problème l'étude d'un autre type de solution, lui aussi classique : un 
algorithme
génétique. Les questions sont bien détaillées et se suivent parfaitement ; y 
répondre donne le plaisir de construire petit à petit un algorithme complexe et
utilisable sur un cas concret.
Ce sujet laisse au final deux impressions : celle d'un début mal maîtrisé et peu
progressif, suivie dans les deux dernières parties d'un sujet classique 
permettant
aux candidats de s'exprimer correctement. Il contient quelques questions de 
langage
SQL mais n'aborde pas la partie ingénierie numérique du programme et ne demande
aucune démonstration théorique.

Indications
Partie I
I.A.1.a Le plus simple est de continuer à générer des couples tant que le 
résultat n'en
contient pas n et d'enregistrer ces couples uniquement s'ils ne sont pas déjà
présents dans le résultat, à l'aide de l'opérateur not in.
I.A.2 Ce genre de matrices est symétrique, on évite de doubler les calculs. La 
distance entre deux points se calcule à l'aide du théorème de Pythagore.
I.B Il existe une fonction permettant d'obtenir les dimensions d'un tableau 
numpy.
I.C.1 Pour tester si un champ est égal à NULL, ce n'est pas l'opérateur = mais
l'opérateur IS qui est nécessaire : champ IS NULL ou champ IS NOT NULL.
I.C.3 Un seul résultat par exploration, pour plusieurs explorations, car il 
s'agit
d'une requête d'agrégation. Les champs à calculer et la sélection des 
explorations terminées se font sur deux tables, une jointure est donc 
nécessaire.
I.C.4 L'énoncé est incomplet, il ne dit pas comment sont stockés les entiers 
dans
la base. On peut imaginer qu'ils sont positifs et enregistrés sur 64 bits.
I.C.5 Il faut réaliser une jointure. Toutes les tables décrites dans l'énoncé 
ne sont
pas utiles. Les champs EX_NUM et TY_NUM sont présents et équivalents dans
trois tables.
Partie II
II.A.2 Générer une liste de n valeurs booléennes permet de savoir rapidement si 
un
point a déjà été visité, sans utiliser la syntaxe in.
II.C.1 Il s'agit d'une recherche classique de minimum, mais uniquement sur les
points encore disponibles à la ie itération. Comme en II.A.2, une liste de
valeurs booléennes peut aider. Faire attention à l'initialisation du critère 
minimal recherché.
II.C.3 Les points donnés sont alignés, faire un dessin au brouillon.
Partie III
III.A Pour générer une liste aléatoire d'entiers, le plus simple est d'utiliser 
la fonction de permutation donnée en fin d'énoncé, sur la liste complète.
III.B Pour trier les chemins, la méthode sort fonctionne immédiatement et il 
n'est
pas utile de la coder à la main. Attention, il faut supprimer directement
des éléments de la liste p, il est interdit d'écrire p = p[0 :len(p)//2] par
exemple.
III.C.1 La fonction random.sample permet d'obtenir plusieurs valeurs distinctes
prises aléatoirement au sein d'une liste.
III.C.2 Penser à utiliser les fonctions muter_chemin et longueur_chemin 
réalisées
aux questions précédentes.
III.D.1 On peut concaténer deux listes avec l'opérateur +.
III.E.1 Attention à la syntaxe des fonctions précédentes, notamment de celles 
qui ne
renvoient pas de valeur.
III.E.2 Où est le meilleur chemin dans une génération ? Est-il modifié ?
III.E.3 Classiquement, une série converge si sa valeur n'évolue plus beaucoup.

I. Création d'une exploration et
gestion des points d'intérêt
La syntaxe des définitions de fonctions choisie pour cet énoncé est une 
possibilité offerte par Python pour rendre le code plus explicite (les « 
annotations »).
Bien que peu d'élèves l'aient déjà vu, son emploi n'a pas dû être un problème.
I.A.1.a Dans la fonction générer_PI, on peut choisir de manipuler une liste et
d'utiliser la méthode append pour ajouter chaque point avant une transformation
finale en tableau numpy, puisque celle-ci est imposée par l'énoncé :
def générer_PI(n:int, cmax:int) -> np.ndarray:
PI = []
while len(PI) < n:
x = random.randrange(0,cmax+1)
y = random.randrange(0,cmax+1)
if [x,y] not in PI:
PI.append([x,y])
return np.array(PI)
La difficulté de cette question réside en grande partie dans le besoin
de ne garder que des points distincts. La réflexion pour obtenir une liste
de n points aléatoire est très courte, mais celle pour éliminer les doublons
l'est beaucoup moins, notamment parce qu'un grand nombre de possibilités
existent. Si l'on ajoute à cela le retour sous forme de tableau numpy exigé,
difficulté supplémentaire pour beaucoup de candidats, alors que la liste de
listes est suffisante, cette question est plutôt difficile pour un début 
d'épreuve.
Il est aussi possible d'utiliser un tableau numpy depuis le début de 
l'algorithme, en l'initialisant à un tableau de n zéros puis en le remplissant 
ligne
par ligne, en vérifiant que chaque couple tiré au sort n'est pas déjà présent :
def générer_PI(n:int, cmax:int) -> np.ndarray:
PI = np.zeros((n,2),int) # n lignes, 2 colonnes
i = 0
while i < n:
x = random.randrange(0,cmax+1)
y = random.randrange(0,cmax+1)
if [x,y] not in PI[0:i]:
PI[i] = [x,y]; i = i+1
return PI
Malheureusement, malgré ce qu'indique l'annexe de l'énoncé, la construction
en [x,y] in PI[0:i] ne donne pas le résultat prévu avec un tableau numpy :
>>> PI = np.array([[1,2],[3,4]])
>>> [1,2] in PI # Normal
True
>>> [1,5] in PI # Pas normal !
True
ce qui n'est pas vraiment le résultat escompté... À n'en pas douter, la fonction
proposée plus haut devrait être acceptée par les correcteurs, mais ce code ne
fonctionne pas en pratique. Une des possibilités pour résoudre ce problème,
très au-delà de ce que l'on peut attendre d'un candidat, est
any(np.equal([x,y],PI[0 :i]).all(1))

qui répond correctement sur notre exemple :
>>> any(np.equal([1,2],PI).all(1))
True
>>> any(np.equal([1,5],PI).all(1))
False
I.A.1.b Les deux nombres doivent être positifs et aussi permettre d'obtenir n
points distincts sur les cmax+1, c'est-à-dire
n 6 (cmax+1)2
Les coordonnées ainsi que cmax étant notées en millimètres, il est peu probable 
que n s'approche de cette valeur limite. On peut néanmoins noter dans
ce cas que l'algorithme donné à la question précédente devient très inefficace.
Il convient alors de le remplacer par un algorithme procédant par élimination
d'un nombre complémentaire de points, choisis aléatoirement.
I.A.2 La fonction demandée doit calculer pour chaque couple de points (i,j) la
distance, à l'aide du théorème de Pythagore. Le résultat est donc symétrique et 
il
faut recopier chaque valeur du triangle inférieur gauche vers le triangle 
supérieur
droit. On n'oublie pas d'ajouter la position actuelle en fin de ligne et de 
colonne.
def calculer_distances(PI:np.ndarray) -> np.ndarray:
n = len(PI)
pos = position_robot()
distances = np.zeros((n+1,n+1))
for i in range(n):
for j in range(i):
distances[i,j] = math.sqrt((PI[i,0]-PI[j,0])**2 \
+ (PI[i,1]-PI[j,1])**2)
distances[j,i] = distances[i,j]
distances[i,n] = math.sqrt((PI[i,0]-pos[0])**2 \
+ (PI[i,1]-pos[1])**2)
distances[n,i] = distances[i,n]
return distances
On peut éviter une des racines en ajoutant la position actuelle directement à 
la liste des points d'intérêt avant calcul, mais il faut pour cela être un
peu familier de la fonction np.concatenate, qui nécessite des listes ou des
tableaux numpy en argument. Les crochets ici sont essentiels, ce qui n'est pas
du tout évident...
def calculer_distances(PI:np.ndarray) -> np.ndarray:
points = np.concatenate((PI,[position_robot()]))
n = len(points)
distances = np.zeros((n,n))
for i in range(n):
for j in range(i):
distances[i,j] = math.sqrt(
\
(points[i,0]-points[j,0])**2 \
+ (points[i,1]-points[j,1])**2)
distances[j,i] = distances[i,j]
return distances