Mines Informatique MP-PC-PSI 2017

A2017 ­ INFO

ÉCOLE DES PONTS PARISTECH,
ISAE-SUPAERO, ENSTA PARISTECH,
TELECOM PARISTECH, MINES PARISTECH,
MINES SAINT-ÉTIENNE, MINES NANCY,
IMT Atlantique (ex Télécom Bretagne),
ENSAE PARISTECH.
Concours Centrale-Supelec (Cycle International),
Concours Mines-Télécom, Concours Commun TPE/EIVP.
CONCOURS 2017
ÉPREUVE D'INFORMATIQUE COMMUNE
Durée de l'épreuve : 1 heure 30 minutes
L'usage de la calculatrice et de tout dispositif électronique est interdit.

Cette épreuve est commune aux candidats des filières MP, PC et PSI
Les candidats sont priés de mentionner de façon apparente
sur la première page de la copie :

INFORMATIQUE COMMUNE
L'énoncé de cette épreuve comporte 7 pages de texte.

Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur
d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant 
les
raisons des initiatives qu'il est amené à prendre.

Etude de trafic routier

Ce sujet concerne la conception d'un logiciel d'etude de trafic routier. On 
modelise le deplacement d'un ensemble de voitures sur des files a sens unique 
(voir Figure 1(a) et 1(b)). C'est un
schema simple qui peut permettre de comprendre l'apparition d'embouteillages et 
de concevoir des
solutions pour fluidifier le trafic.
Le sujet comporte des questions de programmation. Le langage a utiliser est 
Python.
Notations
Soit L une liste,
· on note len(L) sa longueur ;
· pour i entier, 0  i < len(L), l'element de la liste d'indice i est note L[i] ; · pour i et j entiers, 0  i < j  len(L), L[i : j] est la sous-liste composee des elements L[i], . . ., L[j - 1] ; · p  L, avec p entier, est la liste obtenue en concatenant p copies de L. Par exemple, 3  [0] est la liste [0, 0, 0]. (a) Representation d'une file de longueur onze comprenant quatre voitures, situees respectivement sur les cases d'indices 0, 2, 3 et 10. (b) Configuration representant deux files de circulation a sens unique se croisant en une case. Les voitures sont representees par un carre noir. Figure 1 ­ Files de circulation Partie I. Preliminaires Dans un premier temps, on considere le cas d'une seule file, illustre par la Figure 1(a). Une file de longueur n est representee par n cases. Une case peut contenir au plus une voiture. Les voitures presentes dans une file circulent toutes dans la meme direction (sens des indices croissants, designe par les fleches sur la Figure 1(a)) et sont indifferenciees. Q1 ­ Expliquer comment representer une file de voitures a l'aide d'une liste de booleens. Q2 ­ Donner une ou plusieurs instructions Python permettant de definir une liste A representant la file de voitures illustree par la Figure 1(a). Q3 ­ Soit L une liste representant une file de longueur n et i un entier tel que 0  i < n. Definir en Python la fonction occupe(L, i) qui renvoie True lorsque la case d'indice i de la file est occupee par une voiture et False sinon. Q4 ­ Combien existe-t-il de files differentes de longueur n ? Justifier votre reponse. 1 Q5 ­ Ecrire une fonction egal(L1, L2) retournant un booleen permettant de savoir si deux listes L1 et L2 sont egales. Q6 ­ Que peut-on dire de la complexite de cette fonction ? Q7 ­ Preciser le type de retour de cette fonction. Partie II. Deplacement de voitures dans la file On identifie desormais une file de voitures a une liste. On considere les schemas de la Figure 2 representant des exemples de files. Une etape de simulation pour une file consiste a deplacer les voitures de la file, a tour de role, en commencant par la voiture la plus a droite, d'apres les regles suivantes : · une voiture se trouvant sur la case la plus a droite de la file sort de la file ; · une voiture peut avancer d'une case vers la droite si elle arrive sur une case inoccupee ; · une case liberee par une voiture devient inoccupee ; · la case la plus a gauche peut devenir occupee ou non, selon le cas considere. On suppose avoir ecrit en Python la fonction avancer prenant en parametres une liste de depart, un booleen indiquant si la case la plus a gauche doit devenir occupee lors de l'etape de simulation, et renvoyant la liste obtenue par une etape de simulation. Par exemple, l'application de cette fonction a la liste illustree par la Figure 2(a) permet d'obtenir soit la liste illustree par la Figure 2(b) lorsque l'on considere qu'aucune voiture nouvelle n'est introduite, soit la liste illustree par la Figure 2(c) lorsque l'on considere qu'une voiture nouvelle est introduite. (a) Liste initiale A (b) B = avancer(A, False) (c) C = avancer(A, True) Figure 2 ­ Etape de simulation Q8 ­ Etant donnee A la liste definie a la question 2, que renvoie avancer(avancer(A, False), True) ? Q9 ­ On considere L une liste et m l'indice d'une case de cette liste (0  m < len(L)). On s'interesse a une etape partielle ou seules les voitures situees sur la case d'indice m ou a droite de cette case peuvent avancer normalement, les autres voitures ne se deplacant pas. Par exemple, la file devient m m Definir en Python la fonction avancer_fin(L, m) qui realise cette etape partielle de deplacement et renvoie le resultat dans une nouvelle liste sans modifier L. Q10 ­ Soient L une liste, b un booleen et m l'indice d'une case inoccupee de cette liste. On considere une etape partielle ou seules les voitures situees a gauche de la case d'indice m se deplacent, les autres voitures ne se deplacent pas. Le booleen b indique si une nouvelle voiture est introduite sur la case la plus a gauche. Par exemple, la file devient lorsque aucune m m nouvelle voiture n'est introduite. Definir en Python la fonction avancer_debut(L, b, m) qui realise cette etape partielle de deplacement et renvoie le resultat dans une nouvelle liste sans modifier L. 2 Q11 ­ On considere une liste L dont la case d'indice m > 0 est temporairement 
inaccessible et
bloque l'avancee des voitures. Une voiture situee immediatement a gauche de la 
case d'indice m ne
peut pas avancer. Les voitures situees sur les cases plus a gauche peuvent 
avancer, a moins d'etre
bloquees par une case occupee, les autres voitures ne se deplacent pas. Un 
booleen b indique si une
nouvelle voiture est introduite lorsque cela est possible.
Par exemple, la file
devient
lorsque aucune
m
m
nouvelle voiture n'est introduite.
Definir en Python la fonction avancer_debut_bloque(L, b, m) qui realise cette 
etape partielle de
deplacement et renvoie le resultat dans une nouvelle liste.
On considere dorenavant deux files L1 et L2 de meme longueur impaire se 
croisant en leur
milieu ; on note m l'indice de la case du milieu. La file L1 est toujours 
prioritaire sur la file L2. Les
voitures ne peuvent pas quitter leur file et la case de croisement ne peut etre 
occupee que par une
seule voiture. Les voitures de la file L2 ne peuvent acceder au croisement que 
si une voiture de la
file L1 ne s'apprete pas a y acceder. Une etape de simulation a deux files se 
deroule en deux temps.
Dans un premier temps, on deplace toutes les voitures situees sur le croisement 
ou apres. Dans un
second temps, les voitures situees avant le croisement sont deplacees en 
respectant la priorite. Par
exemple, partant d'une configuration donnee par la Figure 3(a), les 
configurations successives sont
donnees par les Figures 3(b), 3(c), 3(d), 3(e) et 3(f) en considerant qu'aucune 
nouvelle voiture n'est
introduite.
L2

L1

L2

L1

L2

L1

(a)

(b)

(c)

L2

L2

L2

L1

L1

(d)

L1

(e)

(f)

Figure 3 ­ Etapes de simulation a deux files
Partie III. Une etape de simulation a deux files
L'objectif de cette partie est de definir en Python l'algorithme permettant 
d'effectuer une etape
de simulation pour ce systeme a deux files.
3

 Q12 ­ En utilisant le langage Python, definir la fonction avancer_files(L1, 
b1, L2, b2) qui
renvoie le resultat d'une etape de simulation sous la forme d'une liste de deux 
elements notee
[R1, R2] sans changer les listes L1 et L2. Les booleens b1 et b2 indiquent 
respectivement si une
nouvelle voiture est introduite dans les files L1 et L2. Les listes R1 et R2 
correspondent aux listes
apres deplacement.
 Q13 ­ On considere les listes
D = [ False, True, False, True, False],

E = [False, True, True, False, False]

Que renvoie l'appel avancer files(D, False, E, False) ?
Partie IV. Transitions
 Q14 ­ En considerant que de nouvelles voitures peuvent etre introduites sur 
les premieres cases
des files lors d'une etape de simulation, decrire une situation ou une voiture 
de la file L2 serait
indefiniment bloquee.
L2

L2

L1

L1

(a)

L2

L1

(b)

(c)

Figure 4 ­ Etude de configurations
 Q15 ­ Etant donnees les configurations illustrees par la Figure 4, combien 
d'etapes sont necessaires (on demande le nombre minimum) pour passer de la 
configuration 4(a) a la configuration 4(b) ? Justifier votre reponse.
 Q16 ­ Peut-on passer de la configuration 4(a) a la configuration 4(c) ? 
Justifier votre reponse.
Partie V. Atteignabilite
Certaines configurations peuvent etre nefastes pour la fluidite du trafic. Une 
fois ces configurations identifiees, il est interessant de savoir si elles 
peuvent apparaitre. Lorsque c'est le cas, on dit
qu'une telle configuration est atteignable.
Pour savoir si une configuration est atteignable a partir d'une configuration 
initiale, on a ecrit
le code incomplet donne en annexe.
Le langage Python sait comparer deux listes de booleens a l'aide de l'operateur 
usuel <, on peut ainsi utiliser la methode sort pour trier une liste de listes de booleens. Q17 ­ Ecrire en langage Python une fonction elim_double(L) non recursive, de complexite lineaire en la taille de L, qui elimine les elements apparaissant plusieurs fois dans une liste triee L et renvoie la liste triee obtenue. Par exemple elim_double([1, 1, 3, 3, 3, 7]) doit renvoyer la liste [1, 3, 7]. On dispose de la fonction suivante : 4 1 2 3 4 5 6 7 8 def doublons(liste): if len(liste)>1:
if liste[0] != liste[1]:
return [liste[0]] + doublons(liste[1:])
del liste[1]
return doublons(liste)
else:
return liste

 Q18 ­ Que retourne l'appel suivant ?
doublons([1, 1, 2, 2, 3, 3, 3, 5])
 Q19 ­ Cette fonction est-elle utilisable pour eliminer les elements 
apparaissant plusieurs fois
dans une liste non triee ? Justifier.
 Q20 ­ La fonction recherche donnee en annexe permet d'etablir si la 
configuration correspondant a but est atteignable en partant de l'etat init. 
Preciser le type de retour de la fonction recherche, le type des variables but 
et espace, ainsi que le type de retour de la fonction
successeurs.
 Q21 ­ Afin d'ameliorer l'efficacite du test if but in espace, ligne 10 de 
l'annexe, on propose
de le remplacer par if in1(but, espace) ou bien par if in2(but, espace), avec 
in1 et in2
deux fonctions definies ci-dessous. On considere que le parametre liste est une 
liste triee par ordre
croissant.
Quel est le meilleur choix ? Justifier.
1
2
3
4
5
6
7
8
9

def in1(element,liste):
a = 0
b = len(liste)-1
while a <= b and element >= liste[a]:
if element == liste[a]:
return True
else:
a = a + 1
return False

10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def in2(element,liste):
a = 0
b = len(liste)-1
while a < b: pivot = (a+b) // 2 # l'operateur // est la division entiere if liste[pivot] < element: a = pivot + 1 else: b = pivot if element == liste[a]: return True else: return False Q22 ­ Afin de comparer plus efficacement les files representees par des listes de booleens on remarque que ces listes representent un codage binaire ou True correspond a 1 et False a 0. Ecrire la fonction versEntier(L) prenant une liste de booleens en parametre et renvoyant l'entier correspondant. Par exemple, l'appel versEntier([True, False, False]) renverra 4. 5 Q23 ­ On veut ecrire la fonction inverse de versEntier, transformant un entier en une liste de booleens. Que doit etre au minimum la valeur de taille pour que le codage obtenu soit satisfaisant ? On suppose que la valeur de taille est suffisante. Quelle condition booleenne faut-il ecrire en ligne 4 du code ci-dessous ? 1 2 3 4 5 6 7 8 9 def versFile(n, taille): res = taille * [False] i = taille - 1 while ...: if (n % 2) != 0: # % est le reste de la division entiere res[i] = True n = n // 2 # // est la division entiere i = i - 1 return res Q24 ­ Montrer qu'un appel a la fonction recherche de l'annexe se termine toujours. Q25 ­ Completer la fonction recherche pour qu'elle indique le nombre minimum d'etapes a faire pour passer de init a but lorsque cela est possible. Justifier la reponse. Partie VI. Base de donnees On modelise ici un reseau routier par un ensemble de croisements et de voies reliant ces croisements. Les voies partent d'un croisement et arrivent a un autre croisement. Ainsi, pour modeliser une route a double sens, on utilise deux voies circulant en sens opposes. La base de donnees du reseau routier est constituee des relations suivantes : · Croisement(id, longitude, latitude) · Voie(id, longueur, id croisement debut, id croisement fin) Dans la suite on considere c l'identifiant (id) d'un croisement donne. Q26 ­ Ecrire la requete SQL qui renvoie les identifiants des croisements atteignables en utilisant une seule voie a partir du croisement ayant l'identifiant c. Q27 ­ Ecrire la requete SQL qui renvoie les longitudes et latitudes des croisements atteignables en utilisant une seule voie, a partir du croisement c. Q28 ­ Que renvoie la requete SQL suivante ? 1 2 3 4 5 SELECT FROM JOIN ON WHERE V2.id_croisement_fin Voie as V1 Voie as V2 V1.id_croisement_fin = V2.id_croisement_debut V1.id_croisement_debut = c 6 Annexe 1 2 3 4 5 6 7 8 9 10 11 12 def recherche(but, init): espace = [init] stop = False while not stop: ancien = espace espace = espace + successeurs(espace) espace.sort() # permet de trier espace par ordre croissant espace = elim_double(espace) stop = egal(ancien,espace) # fonction definie a la question 5 if but in espace: return True return False 13 14 15 16 17 18 19 20 21 22 23 24 def successeurs(L): res = [] for x in L: L1 = x[0] L2 = x[1] res.append( res.append( res.append( res.append( return res avancer_files(L1, avancer_files(L1, avancer_files(L1, avancer_files(L1, False, False, True, True, L2, L2, L2, L2, False) ) True) ) False) ) True) ) 25 26 27 28 29 # dans une liste triee, elim_double enleve les elements apparaissant plus d'une fois # exemple : elim_double([1, 1, 2, 3, 3]) renvoie [1, 2, 3] def elim_double(L): # code a completer 30 31 32 33 34 35 36 # exemple d'utilisation # debut et fin sont des listes composees de deux files de m^ eme longueur impaire, # la premiere etant prioritaire par rapport a la seconde debut = [5*[False], 5*[False]] fin = [3*[False]+2*[True], 3*[False]+2*[True]] print(recherche(fin,debut)) Fin de l'epreuve. 7