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)
                       

Rapport du jury

(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 commune MP 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).