Mines Informatique MP-PC-PSI 2017

Thème de l'épreuve Étude du trafic routier
Principaux outils utilisés simulation, booléens, listes, tri, complexité
Mots clefs trafic routier, bases de données

Corrigé

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

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                       

Énoncé obtenu par reconnaissance optique des caractères


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

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



Mines Informatique PC 2017 -- Corrigé
Ce corrigé est proposé par Virgile Andreani (ENS Ulm) ; il a été relu par Cyril
Ravat (Professeur en CPGE) et Julien Dumont (Professeur en CPGE).

Ce sujet aborde la modélisation d'un croisement routier, représenté par deux 
files
de voitures qui s'intersectent.
· Dans la première partie, il pose les bases de la modélisation avec le cas 
d'une
file unique.
· Dans la deuxième, il invite à programmer la dynamique de la file en présence
ou non d'un obstacle sur la voie, à l'aide d'une opération élémentaire, fournie
par une fonction déjà écrite, qui consiste à faire avancer toute la file d'un 
coup.
· Dans une troisième partie qui ne comporte que deux questions, on s'intéresse
enfin au cas du croisement, en simulant conjointement deux files couplées par
une case commune.
· La quatrième partie, courte elle aussi, prépare la suivante en introduisant la
notion de transition entre configurations non immédiatement successives.
· L'avant-dernière partie, la moins facile de l'épreuve, est consacrée au codage
d'un algorithme de recherche en largeur sur les états du système ce qui permet
de déterminer si une configuration est atteignable depuis une autre.
· Enfin, l'épreuve se termine par trois questions utilisant les bases de 
données.
La difficulté de ce problème est progressive, avec de nombreuses questions très 
accessibles en début et milieu d'épreuve, suivies d'autres plus délicates en 
fin d'épreuve,
notamment dans la cinquième partie. Il est accessible dès la première année 
(sauf la
question 18). L'ensemble du programme est couvert à l'exception de la simulation
numérique.

Indications
Partie II
9 La fonction avancer peut servir d'opération élémentaire dans la fonction 
demandée, il faut s'en servir. On peut faire appel à la concaténation de listes 
au moyen
de l'opérateur +.
10 Noter que la case m est inoccupée. Que cela implique-t-il sur les voitures à 
gauche
de m ?
11 Étant donné que les voitures immédiatement à gauche de m sont bloquées, où 
sont
les voitures qui ont la possibilité d'avancer ?
Partie III
12 Bien réfléchir à l'ordre dans lequel appeler les trois fonctions 
précédemment définies avancer_debut, avancer_debut_bloque et avancer_fin.
Partie V
17 Noter que la liste est triée : il suffit donc de comparer chaque valeur à la 
précédente
pour déterminer si elle est nouvelle ou non.
20 Chercher dans le code où apparaissent les variables en question et les 
opérations
dans lesquelles elles sont impliquées pour déterminer leur type.
21 Quel est le principal critère de choix d'un algorithme ?
24 Démontrer que le nombre d'éléments uniques contenus dans la liste espace est
croissant et borné.

I. Préliminaires
1 Soit une case est vide, soit elle contient une voiture. On peut donc encoder 
ces
deux états au moyen d'une variable binaire qui vaut True si une voiture est 
présente
à cet endroit et False sinon. Pour représenter n cases, on utilise une liste de 
n de
ces booléens.
2 On commence par créer une liste vide, puis on remplit les cases qui doivent 
l'être :
A = 11*[False]
A[0] = True
A[2] = True
A[3] = True
A[10] = True
Il vaut mieux éviter ici de construire la liste directement avec A = [True,
False, True, True, etc.] pour réduire les risques d'erreur.
3 Vu la manière dont on a encodé les états des cases, la fonction occupe ne 
renvoie
rien d'autre que la valeur booléenne de la case demandée :
def occupe(L, i):
return L[i]
Il faut prendre soin à partir d'ici d'utiliser uniquement cette fonction pour
vérifier l'état des cases et éviter d'indexer directement les listes. En effet,
si on décidait un jour de changer de représentation pour les états des cases,
il suffirait d'adapter cette fonction une fois au lieu de chercher dans le code
tous les endroits où l'on indexe une liste.
4 Chaque case pouvant être dans deux états différents, et ce de manière 
indépendante des autres cases,
Le nombre de files différentes est le produit du nombre
d'états possibles pour chacune des cases soit 2n
.
5 Deux listes sont égales si et seulement si elles ont la même longueur et 
chacune
de leurs cases égales deux à deux. Par conséquent :
def egal(L1, L2):
if len(L1) != len(L2):
return False
for i in range(len(L1)):
if L1[i] != L2[i]:
return False
return True
On fait le test de longueur en premier pour s'assurer que les indices seront
valides dans la boucle. À l'intérieur de celle-ci, on peut retourner False dès
la première paire de valeurs différentes, inutile de poursuivre.
Python permet de comparer directement deux listes avec l'opérateur ==,
mais écrire L1 == L2 ici annule l'intérêt de la question et ne fait pas 
apparaître explicitement la complexité.

6 Si les listes sont de longueur différente, il n'y a pas de boucle et la 
fonction
s'achève en temps constant. Le pire cas correspond à la situation où l'on itère 
la
boucle un maximum de fois, c'est-à-dire quand les listes sont de même taille et 
que
tous leurs éléments sont égaux deux à deux (sauf éventuellement les deux 
derniers).
Dans ce cas,
La complexité est linéaire en la longueur commune des listes
7 Comme il était demandé à la question 5, cette fonction retourne un booléen.

II. Déplacement de voitures dans la file
8 Cette évolution consiste à faire avancer la file deux fois, d'abord sans 
ajouter de
voiture au début, puis en en ajoutant une. On obtient donc [True, False, True,
False, True, True, False, False, False, False, False].
9 Cette étape partielle consiste à faire avancer la deuxième partie de la liste 
et à
laisser la première inchangée. On peut réutiliser la fonction avancer pour la 
deuxième
partie et recoller le résultat avec la première partie de la liste au moyen de 
l'opérateur
de concaténation +.
def avancer_fin(L, m):
return L[:m] + avancer(L[m:], False)
Pour cette question comme pour les suivantes, l'énoncé incite à réutiliser
la fonction avancer, qu'il définit mais n'utilise pas ailleurs. Une réponse
acceptable sans utiliser cette fonction aurait pu être
def avancer_fin(L, m):
return L[:m] + [False] + L[m:-1]
ou encore, sans concaténation :
def avancer_fin(L, m):
L1 = L[:m]
L1.append(False)
for i in range(m, len(L)-1):
L1.append(L[i])
return L1
10 La case m étant inoccupée, les voitures à gauche de m ne sont pas bloquées et
peuvent toutes avancer. On peut donc là aussi réutiliser la fonction avancer 
sur la
première partie de la liste et recoller le résultat avec la seconde partie.
def avancer_debut(L, b, m):
return avancer(L[:m+1], b) + L[m+1:]
11 Les voitures bloquées immédiatement à la gauche de m ne bougent pas, de la
même manière que les voitures à la droite de m. Toutes les voitures à la droite 
de la
première case inoccupée à la gauche de m (si elle existe) voient donc leur 
position
inchangée par avancer_debut_bloque, seules les voitures à la gauche de cette 
case
pouvant avancer librement. Si toutes les cases à la gauche de m sont occupées, 
alors
aucune voiture ne peut avancer. Par conséquent, il nous faut trouver l'indice l 
de
la première case inoccupée à la gauche de m et appeler avancer_debut(L, b, l).