CCP Informatique PSI 2017

Thème de l'épreuve Étude de la capacité et de la congestion de l'autoroute A7
Principaux outils utilisés SQL, algorithmique, intégration numérique, automates cellulaires
Mots clefs trafic routier, bouchons, schéma d'intégration

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


SESSION 2017

PSIIN07

.

!

!
!

EPREUVE SPECIFIQUE - FILIERE PSI!
!!!!!!!!!!!!!!!!!!!!"
!

INFORMATIQUE
Vendredi 5 mai : 8 h - 11 h!
!!!!!!!!!!!!!!!!!!!!"
N.B. : le candidat attachera la plus grande importance à la clarté, à la 
précision et à la concision de la
!"#$%&'()*+,'+-)+%$)#'#$&+./&+$0.)"+1+!.2"!.!+%.+3-'+2.-&+4-'+/.054.!+6&!.+-).+.!!.-!+#7")()%"8+'4+4.+
/'9)$4.!$+/-!+/$+%(2'.+.&+#.:!$+2(-!/-':!.+/$+%(02(/'&'()+.)+.;24'3-$)&+4./+!$'/()/+#./+')'&'$&':./+3-7'4+
a été amené à prendre.!

!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"
!
!
!
!
Les calculatrices sont interdites
!
!
! Le sujet comporte 15 pages dont :
!
­ 13 pages de texte de presentation et enonce du sujet ;
!
­ 2 pages d'annexes.
!
!
Toute documentation autre que celle fournie est interdite.
!
!
!
!
REMARQUES PRELIMINAIRES
!
!
!
! L'epreuve doit etre traitee en langage Python. Les syntaxes sont rappelees en 
annexe 2.
! Les differents algorithmes doivent etre rendus dans leur forme definitive sur 
la copie a rendre (les
! brouillons ne seront pas acceptes).
!
Il est demande au candidat de bien vouloir rediger ses reponses en precisant 
bien le numero de la
!
question traitee et, si possible, dans l'ordre des questions. La reponse ne 
doit pas se cantonner a la
!
redaction de l'algorithme sans explication ; les programmes doivent etre 
expliques et commentes.
!
!
!
!

1/15

!

Etude de la capacite et de la congestion de l'autoroute A7
I

Objectifs et demarche d'etude

Il existe plusieurs formes de congestions routieres, selon leur
cause : la congestion recurrente, la congestion  previsible 
(travaux, manifestations, meteo) et la congestion due aux
incidents et accidents, par definition imprevisibles. On
s'interesse ici au niveau de congestion recurrente qui peut
etre defini comme le surplus de demande qui amene la
congestion.
Cette etude se focalise sur la congestion routiere de l'autoroute A7 en France. 
La section etudiee ne comporte ni entree
ni sortie. La longueur de l'axe est de 8,5 km et comporte 3
voies sauf au niveau de la derniere station (non etudiee ici).
Un seul sens de circulation est etudie.
La cartographie presentee sur la figure 1 donne l'implantation des differentes 
stations de mesure, de la station M8A a
M8P, et des controles de sanction automatique (CSA). Ces
stations de mesure font partie du systeme de recueil automa- Figure 1 ­ 
Cartographie de la zone
d'etude
tique des donnees (RAD) present sur les autoroutes.
Pour realiser les mesures, la chaussee est equipee de boucles 
electromagnetiques connectees aux
stations qui remontent l'information vers un systeme central. Ces boucles 
permettent de compter le
nombre de vehicules qui passent sur les routes et, dans le cadre de cette 
etude, il s'agit de boucles
doubles qui permettent aussi d'estimer les vitesses.
La connaissance et le suivi du niveau de congestion recurrente permettent 
ensuite d'envisager des
actions de regulation et d'amenagement de voirie. La simulation numerique est 
alors employee pour
etudier differentes solutions d'amenagement ou proposer des solutions de 
regulation dynamique du
trafic.
Objectifs
Le premier objectif est d'etablir le diagramme fondamental (trace du debit en 
fonction de la concentration) caracteristique du troncon etudie a partir de 
l'historique de donnees de comptage.
Le deuxieme objectif est de mettre en place une simulation numerique adaptee au 
troncon etudie a
partir de deux modeles afin de tester deux approches numeriques differentes.

II

Traitement des donnees experimentales

La methodologie choisie ici pour estimer la capacite d'une route est celle 
utilisee notamment par les
centres d'etudes techniques de l'equipement. Elle consiste a representer un 
diagramme fondamental,
c'est-a-dire le debit q, nombre de vehicules par unite de temps, en fonction de 
la concentration c,
nombre de vehicules par unite de longueur. Ce diagramme permet alors de 
determiner les parametres
caracteristiques de la route.
2/15

II.1

Exploitation des donnees de mesure

II.1.1 Selection des mesures
L'ensemble des donnees produites par le reseau est archive dans une base de 
donnees. Les variables d'interet moyennees par tranche de temps de 6 min pour 
chaque point de mesure sont le
debit q exp, representatif du nombre de vehicules par unite de temps et la 
vitesse moyenne v exp des
vehicules en ce point. On peut egalement acceder a la concentration, c exp, par 
calcul etant donne que
c exp = q exp/v exp.
Une version simplifiee de cette base de donnees est reduite a deux tables.
La table STATIONS repertorie les stations de mesures ; elle
STATIONS
COMPTAGES
contient les attributs :
­ id station (cle primaire), entier identifiant chaque staid_comptage
id_station
id_station
nom
tion ;
date
nombre_voies
voie
­ nom, chaine de caracteres designant le nom de la staq_exp
tion ;
v_exp
­ nombre voies, entier donnant le nombre de voies de la
section d'autoroute.
La table COMPTAGES repertorie les differents enregistrements de donnees 
realises au cours du
temps par les stations de comptage. Elle contient les attributs :
­
­
­
­
­
­

id comptage, entier identifiant chaque comptage ;
id station, entier identifiant la station concernee ;
date, entier datant la mesure ;
voie, entier numerotant la voie sur laquelle a ete effectuee la mesure ;
q exp, flottant donnant le debit mesure pendant 6 minutes ;
v exp, flottant donnant la vitesse moyenne mesuree pendant 6 minutes.

Q1. L'etude se focalise uniquement sur les mesures de l'une des stations, la 
M8B. Ecrire une
requete SQL qui renvoie les donnees de comptage (id comptage, date, voie, q 
exp, v exp)
mesurees a la station de comptage de nom M8B.
Le resultat de la requete precedente est stocke dans une nouvelle table 
COMPTAGES M8B a cinq
colonnes (id comptage, date, voie, q exp, v exp).
On fait l'hypothese que les mesures sur les differentes voies d'une meme 
station sont enregistrees
de facon synchronisee. Lors d'un enregistrement pour une station a trois voies, 
on ecrit donc trois
lignes dans la table COMPTAGES avec trois dates identiques. Pour chacun des 
enregistrements de
la station M8B, trois lignes avec trois dates identiques sont donc presentes 
dans la nouvelle table
COMPTAGES M8B. Pour la suite de l'etude, les resultats experimentaux de chacune 
des trois voies
doivent etre agreges pour se ramener a une voie unique.
Q2. Ecrire une requete SQL qui renvoie, pour chaque date des donnees de 
COMPTAGES M8B,
le debit correspondant a la somme des debits de chaque voie.
De la meme facon, une requete SQL permet d'obtenir la moyenne des vitesses sur 
l'ensemble des
trois voies pour chaque date des donnees de COMPTAGES M8B. Il n'est pas demande 
d'ecrire
cette requete. Ainsi, dans la suite de l'etude, la portion d'autoroute sera 
simplifiee en ne considerant
qu'une seule voie.

3/15

5-6)&*+,-.)$/0%*1*.4

On veut tracer le diagramme fondamental du troncon
d'autoroute etudie (figure 2). Suite au traitement de la
base de donnees, on dispose a present du tableau a une
dimension (aussi appele vecteur) des debits q exp (en
vehicules par heure) et du vecteur des vitesses v exp
(en kilometres par heure). Ces deux vecteurs possedent
nbmesures composantes avec nbmesures le nombre de points
de mesure a tracer. Pour chaque composante i, la relation
c exp[i] = q exp[i]/v exp[i] permet d'obtenir la concentration. L'utilisation 
des tableaux a une dimension (ou vecteurs)
est rappelee en annexe 2.

7***************:777*************;777*************<777**************=777*

II.1.2 Diagramme fondamental

7

87

977

987

:77

!"#$%#&'(&)"#*+,-.)$/0%*1*234

Figure 2 ­ Points de mesure
M8B : diagramme fondamental
(c exp,q exp)

Q3. Ecrire une fonction trace(q exp , v exp) qui prend en arguments q exp et v 
exp et qui permet
d'afficher le nuage de points du diagramme fondamental. On considerera que les 
bibliotheques
sont importees et on pourra utiliser la fonction  plot  donnee en annexe 2.

II.2

Estimation de l'etat de congestion

Au niveau d'une station de mesure, la situation est dite congestionnee lorsque 
les vitesses prises par
les vehicules restent inferieures a 40 km/h et la situation est dite fluide 
lorsque les vitesses restent
superieures a 80 km/h.
Q4. La fonction congestion(v exp), qui prend en argument v exp et renvoie la 
valeur mediane du
tableau de valeurs v exp est definie ci-dessous. La recherche de la mediane est 
basee sur un algorithme de tri. Choisir une des 4 propositions donnees pour 
completer les 2 lignes manquantes
(indiquees par  ligne a completer ). Donner le nom, puis la complexite de 
l'algorithme de
tri employe, dans le meilleur et le pire des cas. Analyser la pertinence de ce 
choix.
def congestion(v_exp):
nbmesures=len(v_exp)
for i in range(nbmesures):
v=v_exp[i]
j = i
while 0 < j and v < v_exp[j-1]:
ligne a completer
ligne a completer
v_exp[j] = v
return v_exp[nbmesures//2]

Propositions pour les lignes manquantes :
1. v_exp[j-1]
j = j-1
2. v_exp[j] =
j = j-1
3. v_exp[j+1]
j = j+1
4. v_exp[j] =
j = j+1

= v_exp[j]
v_exp[j-1]
= v_exp[j]
v_exp[j+1]

Q5. A partir de la base de donnees de la station M8B, on obtient le vecteur v 
exp. On execute
la fonction congestion(v exp), la valeur retournee par la fonction etant 30, 
quelle conclusion
peut-on tirer de ce resultat?

4/15

III

Elaboration d'une premiere simulation du trafic routier par
la mecanique des fluides

Il est rappele ici que dans toute la suite de l'etude, l'autoroute est 
assimilee a une seule voie. Le modele
continu revient a negliger le caractere discret de la matiere. Pour le modele 
routier, cela revient donc
a regarder l'evolution du trafic sur des distances grandes devant la taille des 
vehicules, notee L0. On
appelle c(t,x), en vehicules par metre, la concentration de vehicules par unite 
de longueur de route a
1
l'instant t et a la position x. Sur une longeur L0, il y a, au plus, un seul 
vehicule, soit c  c max =
.
L0
On appelle q(t,x), en vehicules par seconde, le debit de vehicules, 
c'est-a-dire le nombre de vehicules
par unite de temps traversant la section de la route situee a la position x. La 
vitesse v(t,x), en metres
par seconde, ne represente pas la vitesse de chacun des vehicules mais la 
vitesse moyenne du trafic a
la position x. On considere que les vehicules se deplacent selon l'axe x dans 
le sens des x croissants.
On rappelle la relation q(t,x) = c(t,x) × v(t,x). Desormais, q, v et c 
representent les grandeurs simulees et non plus des donnees experimentales. On 
travaille dans la suite avec les unites du systeme
international.
En considerant une portion d'autoroute dx pendant une duree dt et en supposant 
qu'il n'y a ni perte,
ni creation de vehicule, il est possible de montrer que q(t,x) et c(t,x) 
verifient l'equation aux derivees
partielles suivante :
q(t,x) c(t,x)
+
= 0.
(1)
x
t

III.1

Discretisation

Afin de resoudre numeriquement cette
equation aux derivees partielles, nous avons
besoin de la discretiser. On choisit les
parametres suivants :
­ longueur de l'autoroute : La
­ duree de simulation : T emps
­ pas d'espace (en metres) : dx
­ pas de temps (en secondes) : dt

Discrétisation en temps (indice i)
Sens des temps croissants

Pour comprendre comment evoluent la concentration, la vitesse moyenne ou le 
debit de vehicules
au cours du temps le long de l'autoroute, il convient donc de resoudre cette 
equation aux derivees
partielles a partir de la situation initiale.
Discrétisation en espace (indice j)
Sens des positions croissantes
!"#$,%#$

!"#$,%

!"#$,%&$

!",%#$

!",%

!",%&$

!"&$,%#$

!"&$,%

!"&$,%&$

Figure 3 ­ Representation de la discretisation
Q6. Soit C le tableau de valeurs contenant les concentrations en tous les 
points x et a tous les instants t discretises, comme represente sur la figure 
3. L'approximation numerique de la concentration au temps ti et a la position x 
j sera notee Ci, j avec i designant l'indice de temps et j
designant l'indice d'espace. Quelles sont les dimensions de C ?

5/15

III.2

Un modele de diagramme fondamental

L'equation (1) possede deux inconnues. Il faut donc ajouter une deuxieme 
equation pour pouvoir la
resoudre. On propose tout d'abord de relier la vitesse et la concentration par 
le modele de Greenshield
etabli a partir des analyses suivantes :
­ lorsque la concentration en vehicules tend vers 0, les conducteurs peuvent 
rouler a la vitesse
maximale autorisee, v max en metres par seconde ;
­ lorsque les vehicules sont pare-choc contre pare-choc, la concentration est 
egale a c max en
vehicules par metre : ils n'avancent plus.
Une relation lineaire entre vitesse et concentration est choisie dans le modele 
de Greenshield, qui est
ainsi defini par la relation suivante :
v(t,x) = v max(1 - c(t,x)/c max).

(2)

On souhaite concevoir une fonction diagramme permettant de realiser le trace du 
diagramme fondamental pour un instant donne ti (soit pour une ligne de C). 
Cette fonction fait appel a une fonction
debit permettant de calculer les valeurs de debit a un instant ti en utilisant 
la relation de Greenshield
(2). Ces valeurs sont stockees dans un vecteur Q. Le trace du diagramme 
fondamental est realise et le
tableau Q est retourne.
Q7. Ecrire une fonction debit(v max , c max , C ligne) qui prend en arguments 
la vitesse maximale
(v max), la concentration maximale (c max) et un tableau contenant les 
concentrations a un
instant donne (soit les elements d'une ligne du tableau C) nomme ici C ligne et 
qui renvoie un
tableau de valeurs contenant les debits (en vehicules par seconde) aux 
differentes positions a
ce meme instant.
Q8. Specifier les arguments d'entree (et leur type) de la fonction diagramme. 
L'ecriture du code
de la fonction n'est pas demandee. Preciser les unites des differents termes. 
Tracer l'allure du
diagramme fondamental obtenu. L'allure du diagramme depend-elle du temps ti 
auquel on se
place (soit du choix de la ligne de C)?

Resolution de l'equation

III.3.1

Situation initiale

On considere une situation de depart (t = 0),
comme indique sur la figure 4. On se place
dans une configuration ou l'on a un profil de
concentration dont on veut etudier l'evolution.
La concentration c1 la plus faible passe a c2, plus
forte, a la distance d1 et revient a c1 en d2.
Chacune des distances sera discretisee.
L'approximation numerique d'une distance
correspondra a la division entiere de la distance
par le pas.

c2

Concentration

III.3

c1

0

d1

d2

La

!"#$%$"&'#()'*+,(%")"(%-

Figure 4 ­ Configuration initiale

Q9. Concevoir une fonction C depart qui permet d'initialiser la premiere ligne 
du tableau C (correspondant a t = 0). L'ecriture du code correspondant n'est 
pas demandee ; en revanche, on
precisera toutes les valeurs de j pour lesquelles C0, j sera egale a c1 et 
toutes les valeurs pour
lesquelles C0, j sera egale a c2. L'en-tete ou specification de la fonction 
devra etre precise(e) (et
comporter les arguments d'entree et leur type), ainsi que le resultat renvoye 
par la fonction.
6/15

III.3.2

Resolution

Le tableau C contient des zeros, exceptee la premiere ligne qui a ete remplie 
de valeurs grace a la mise
en oeuvre de la fonction C depart. On souhaite a present ecrire la fonction
resolution(C , dt , dx , c max , v max) permettant de resoudre l'equation et de 
remplir completement
le tableau C.
Connaissant pour tout indice j les valeurs de Ci, j , on cherche a determiner 
Ci+1, j .
Dans le schema d'Euler  avant , la derivee d'une fonction f par rapport a la 
variable x, au point x j ,
f j+1 - f j
df
(x j ), est approximee (en utilisant ce point et le point situe  devant  lui) 
par
.
dx
dx
Q est un vecteur contenant les valeurs de debits Q j aux differentes positions 
x j et a l'instant ti (l'approximation du debit au temps ti et a la position x 
j sera donc notee Q j .). A chaque instant ti , Q devra
etre recalcule.
Q10. A partir de l'equation (1) et en utilisant des schemas d'Euler  avant  
pour l'ecriture des
derivees, montrer que la relation de recurrence donnant Ci+1, j en fonction de 
Ci, j , Q j+1 , Q j , dx
et dt est donnee par l'une des propositions ci-dessous. Le numero de la reponse 
correcte sera
clairement indique sur la copie.
Q j - Q j+1
1. Ci+1, j = Ci, j -
.dt
dx
Q j+1 - Q j
.dt
2. Ci+1, j = Ci, j -
dx
Q j+1 - Q j
.dx
3. Ci+1, j = Ci, j -
dt
Q j - Q j-1
.dt
4. Ci+1, j = Ci, j -
dx
Pour que le nombre de voitures soit constant sur la longueur de la route, il 
faut se fixer des conditions
aux limites periodiques. Ainsi, quand un vehicule arrive en bout d'autoroute, 
il est replace au debut
de celle-ci. On considere donc que le vehicule situe en x = La, se deplacant 
vers la droite, a pour
voisin de droite le vehicule situe en x = 0.
Q11. L'initialisation a ete effectuee avec la fonction C depart(dx , d1 , d2 , 
c1 , c2 , C). Ecrire une
fonction resolution(C , dt , dx , c max , v max) qui prend en arguments le 
tableau C, les pas
dt et dx, la concentration maximale c max et la valeur de la vitesse maximale v 
max et qui
renvoie le tableau C rempli au cours de la resolution. On pourra faire appel a 
la fonction
debit(v max , c max , C ligne) definie a la question Q7.

III.4 Etude des solutions trouvees et modification du schema
On etudie deux situations de depart basees sur le meme profil que celui propose 
a la situation initiale
(figure 4). Dans le cas 1, on choisit c1 et c2, respectivement notees c1b et 
c2b, correspondant a
des concentrations faibles. On peut montrer que, pour ces concentrations, le 
creneau se deplace vers
la droite (dans le sens des x croissants) au cours du temps. Cette 
demonstration n'est pas demandee.
Dans le cas 2, on choisit c1 et c2, respectivement notees c1h et c2h, 
correspondant a des concentrations
fortes. On peut montrer que, pour ces concentrations, le creneau se deplace 
vers la gauche (dans le
sens des x decroissants) au cours du temps. Cette demonstration n'est pas 
demandee.

7/15

On applique la fonction resolution a ces deux situations de depart et on 
represente la concentration
en fonction de la position a differents instants (figure 5). La situation 
initiale est en traits interrompus
(- -), les situations intermediaires en traits continus (-) et la situation 
finale en pointilles (:).
!

%&'()'&*+,/&+)-.
+*+,0.1023.+'2.
4)0,-),3*-('&*+,
5&6.07.

!"%

!

%&'()'&*+,/&+)-.

!"&
%&'()'&*+
&+&'&)-.

%&'()'&*+,&+&'&)-.

!$&

!$%
!
#

!

"$ ""
8)3,$

#$

"$ ""
8)3,"

#

#$

Figure 5 ­ Resultats pour le cas 1 et pour le cas 2 avec Euler  avant  pour 
l'espace et  avant  pour
le temps
On remarque qu'avec la situation de depart du cas 1, la solution diverge. Avec 
la situation de depart
du cas 2, le creneau initial semble se deplacer vers la gauche.
Une modification est alors apportee a la fonction resolution. Dans la 
discretisation en espace (c'est-adire lors de l'ecriture des derivees par 
rapport a la variable d'espace), le schema d'Euler  avant  en
espace est remplace par un schema d'Euler  arriere  en espace. Dans ce schema, 
la derivee d'une
df
fonction f par rapport a la variable x au point x j ,
(x j ) est approximee (en utilisant ce point et le
dx
f j - f j-1
point situe  derriere  lui) par
. On obtient alors les resultats presentes figure 6.
dx
!

%&'()'&*+,&+&'&)-.
%&'()'&*+,/&+)-.

!
!"&

%&'()'&*+,
/&+)-.
+*+,
0.1023.+'2.
4)0,-),3*-('&*+,
5&6.07.

!"%
%&'()'&*+
&+&'&)-.

!$&
!$%

!

!
#

"$ ""
8)3,$

#$

#

"$ ""
8)3,"

#$

Figure 6 ­ Resultats pour le cas 1 et pour le cas 2 avec Euler  arriere  pour 
l'espace et  avant 
pour le temps
Cette fois-ci, avec la situation de depart du cas 1, le creneau initial se 
deplace vers la droite et avec la
situation de depart du cas 2, la solution diverge.
Q12. On se place a l'iteration i + 1 ; les calculs des iterations precedentes 
ont deja ete realises.
Le calcul des termes de Q (vecteur des debits a l'instant ti ) est fait par la 
fonction debit, Q j
etant determine a partir de la valeur de Ci, j . Sur la grille de 
discretisation donnee figure 3 (qui
sera reproduite sur la copie), tracer des fleches partant des points deja 
calcules aux iterations
precedentes et allant vers le point a calculer Ci+1, j (au pas d'espace j et a 
l'iteration i + 1) dans
le cas du schema d'Euler  avant  pour la discretisation en espace. Proceder de 
meme dans le
cas du schema d'Euler  arriere  pour la discretisation en espace.
8/15

Q13. En deduire un argument permettant de choisir le schema d'Euler adapte a la 
situation de depart.
On cherche maintenant un schema fonctionnel pour les deux situations. On 
propose celui de LaxFriedriechs qui :
­ utilise un schema centre pour l'approximation des derivees par rapport a la 
variable d'espace.
df
Dans ce schema, la derivee d'une fonction f par rapport a la variable x au 
point x j ,
(x j ) est
dx
f j+1 - f j-1
approximee (a partir du point precedent et du point suivant) par
;
2dx
­ approxime les derivees par rapport a la variable de temps en remplacant la 
valeur Ci, j par la
moyenne de la valeur prise au point precedent Ci, j-1 et de la valeur prise au 
point suivant Ci, j+1 .
Q14. Proposer les modifications de la fonction resolution (definie a la 
question Q11) necessaires
pour utiliser le schema de Lax-Friedriechs.
La mise en oeuvre de la
fonction resolution permet,
ensuite, d'effectuer le trace
des solutions obtenues dont
le resultat est donne figure
7. Les instructions permettant de realiser le trace ne
sont pas demandees.
Figure 7 ­ Les deux situations de depart resolues avec le schema de
Lax-Friedriechs

III.5

Amelioration du programme : retour sur le choix du diagramme fondamental

Afin de s'assurer de la stabilite de la solution trouvee, il convient, une fois 
le schema d'approximation
determine, de definir les valeurs des parametres tels que les pas de temps et 
d'espace. On suppose
ici que ce travail a ete realise. Cependant, cela ne signifie pas que l'on peut 
simuler fidelement des
phenomenes reels. En effet, le diagramme fondamental utilise et trace a la 
question Q8 est assez
different du nuage de points experimentaux represente figure 2.
La nouvelle approximation choisie pour obtenir les parametres caracteristiques 
du diagramme fondamental q en fonction de c est une regression d'ordre 3 : q = 
a3  c3 + a2  c2 + a1  c + a0 , ai etant les
constantes d'ajustement de la courbe sur le nuage de n points. La fonction 
regression(q exp , c exp),
qui prend en arguments les vecteurs q exp et c exp obtenus experimentalement 
(ayant servi a tracer le
nuage de points de la figure 2) et qui renvoie les coefficients a0 ,a1 ,a2 ,a3 
, a ete realisee (on ne demande
pas d'ecrire cette fonction).
Q15. Expliquer en quelques phrases ce qu'il faut modifier dans la fonction 
resolution definie a
la question Q11 pour resoudre l'equation (1) en prenant en compte ce nouveau 
diagramme
fondamental base sur l'experimentation.
La simulation que nous avons mise en place permet ainsi de determiner les 
caracteristiques d'evolution
d'un embouteillage. On peut notamment en deduire la vitesse de propagation de 
l'embouteillage, ou
sa vitesse de resorption. Cependant, on aimerait a present mettre en place une 
simulation permettant
de modeliser les comportements individuels des conducteurs.
9/15

IV Deuxieme simulation du trafic routier :
simulation de Nagel et Schreckenberg (NaSch)
L'objectif est de simuler la formation d'embouteillages dits  embouteillages 
fantomes . Ils sont le
resultat d'une perturbation qui apparait localement sur la voie et s'amplifie 
peu a peu jusqu'a former
un embouteillage.

IV.1

Initialisation

Afin de modeliser le comportement de chacun des vehicules, l'espace, le temps 
ainsi que la vitesse
des vehicules sont discretises. La dynamique de chaque element est modelisee de 
facon tres simple,
l'objectif etant d'obtenir un bon comportement a l'echelle macroscopique. On 
etudie, comme dans les
parties precedentes, une autoroute de longueur La = 8 500 (en metres) pour 
laquelle on ne considere
qu'un seul sens et qu'une seule voie. La vitesse est limitee a 130 km/h et on 
considere une duree
totale d'etude T emps.
Soit Xn la position du vehicule n, vn  [[0,1,...,v max]] sa vitesse entiere et 
dn la distance intervehiculaire (par rapport au vehicule precedent). On choisit 
de decouper la route en nb cellules cellules
de tailles identiques valant pas x = 7,5 (en metres). La duree d'etude est 
decoupee en nb temps pas
de temps valant pas t = 1,2 (en secondes) qui peut s'interpreter comme le temps 
de reaction du
conducteur. Une probabilite donnee par le flottant p est utilisee dans 
l'algorithme.
Q16. Justifier le choix de la valeur du pas d'espace. En deduire ce que vaut la 
vitesse v max imposee
de 130 km/h en cellules par pas de temps. On arrondira au nombre entier 
superieur.
Comme precedemment, la portion d'autoroute consideree est sans entree ni 
sortie. Les conditions limites seront periodiques, c'est-a-dire qu'un vehicule 
sortant de l'autoroute se retrouve instantanement
a l'entree de celle-ci (avec la meme vitesse).
On considere que les donnees du probleme pas x, pas t, T emps, La, v max, p 
sont, a present, renseignees dans le programme. On cherche, pour une densite 
donnee, a determiner les vitesses a chaque
position au cours du temps, ainsi que l'occupation ou non de chacune des 
cellules. On met en place
une structure de stockage constituee :
­ d'un tableau Route de dimension nb temps × nb cellules qui contient des 
nombres binaires. Si,
au pas de temps 10, la cellule 23 est occupee par un vehicule, alors 
Route[10,23] = 1, sinon
Route[10,23] = 0 ;
­ d'un tableau Vitesses de dimension nb temps × nb cellules qui contient des 
entiers. Si, au pas
de temps 10, la cellule 23 est occupee par un vehicule et que sa vitesse est de 
3 cellules par pas
de temps, alors Vitesses[10,23] = 3. Si la cellule n'est pas occupee, alors 
Vitesses[10,23] = 0 ;
­ d'un tableau Vitesses suivantes de dimension 1 × nb cellules qui contient des 
entiers. Il permettra de stocker les vitesses au temps i + 1 avant de deplacer 
les vehicules.
On peut desormais definir la situation initiale. On considere une route ou les 
ecarts entre tous les
vehicules sont identiques. On cree ainsi une route avec une repartition 
homogene des vehicules. La
route a ete initialisee en placant des 1 dans les cellules possedant un 
vehicule dans la premiere ligne
de Route pour une concentration fixee c0 en vehicules par kilometre. Toutes les 
autres cellules de
Route sont initialisees avec la valeur 0. Les cellules de Vitesses sont 
egalement initialisees avec des
zeros. Cette etape d'initialisation est consideree comme deja realisee dans la 
suite.

10/15

IV.2

Mise en oeuvre de l'algorithme

Le modele NaSch, dont le pseudo-code est donne en annexe 1, est le pionnier des 
modeles cellulaires
permettant de simuler un trafic routier. L'algorithme est constitue de quatre 
etapes qui sont toutes
realisees l'une apres l'autre a chaque pas de temps.
Les etapes 1, 2 et 3 correspondent au calcul des futures vitesses. L'etape 4 
permet d'inscrire chaque
vitesse au lieu ou se trouve le vehicule au pas suivant. Le comportement 
correspondant est illustre
figure 8. Dans cet algorithme, on effectue la mise a jour des positions de tous 
les vehicules de facon
simultanee.
Au niveau des etapes 2 et 4, des comparaisons et calculs sont effectues entre 
dn et vn ou entre Xn et vn .
En effet, les vitesses sont exprimees en cellules par pas de temps. Sur un pas 
de temps, vn correspond
donc a une distance parcourue en nombre de cellules.
On cherche a ecrire la fonction ma j qui permet d'appliquer les etapes 1, 2 et 
3 de l'algorithme de
NaSch pour toutes les valeurs de Vitesses[i, :]. On utilisera la fonction 
distance(Route , i , j) qui
prend en arguments le tableau Route, l'indice de temps i et l'indice de 
position j du vehicule n et qui
renvoie la distance dn entre les vehicules n + 1 et n, a l'instant i. Seules 
les cellules comprenant un
vehicule doivent etre traitees ; les autres auront une vitesse nulle.
Sens de parcours
Configuration à linstant t
!"$

!"%

!"%

!"&

!"$

!"$

!"%

!"$

!"&

!"%

!"&

!"%

Etape 1 : Accélération
!"#

Etape 2 : Décélération
!"%

Mise à jour
des vitesses

Etape 3 : Facteur aléatoire
!"&

!"$

Etape 4 : Déplacement (Configuration à linstant t+1)
!"&

!"$

!"&

!"%

Figure 8 ­ Illustration du schema sur un exemple
Q17. En utilisant l'annexe 1, ecrire une fonction ma j(Route , Vitesses , p , 
vmax , i) qui prend en
arguments les tableaux Route et Vitesses, le parametre aleatoire p, la vitesse 
maximale
v max (en cellules par pas de temps) et l'indice de temps i et qui renvoie le 
tableau
Vitesses suivantes.

11/15

Q18. Ecrire une fonction deplacement(Vitesses , Route , Vitesses suivantes , i) 
qui permet de
determiner les valeurs de Vitesses[i + 1, :] et de Route[i + 1, :]. La fonction 
deplacement
renvoie les tableaux Route et Vitesses mis a jour avec la ligne i + 1 
completee. Les vitesses
calculees doivent etre placees dans les cellules ou se trouvent les voitures 
correspondantes une
fois deplacees. Penser a integrer la prise en compte des conditions aux limites.

IV.3

Simulation et analyse des resultats

Apres nb temps iterations sur le temps, on obtient l'evolution de l'etat de 
Route au cours du temps
representee figure 9. Les points noirs correspondent aux valeurs 1 du tableau 
(le reste etant a 0).

Figure 9 ­ Affichage de Route (indice i de temps en ordonnee, indice j des 
positions en abscisse)

12/15

Un zoom est realise figure 10 sur les premieres valeurs en temps et en espace 
pour mieux visualiser
la formation d'embouteillages.

Figure 10 ­ Zoom sur l'affichage de Route (indice i des temps en ordonnee, 
indice j des positions en
abscisse)
Q19. Expliquer en quelques phrases en quoi les figures presentees montrent que 
la formation d'un
embouteillage a ete simulee. Sur quels parametres peut-on agir pour que le 
resultat de la simulation se rapproche des resultats experimentaux?

13/15

Annexes
Annexe 1 - Algorithme de NaSch
Les operations suivantes sont realisees a chaque pas de temps.
­ Etape 1 - Acceleration
Le vehicule n accelere d'une unite s'il n'a pas encore atteint la vitesse 
maximum.
vn (t + 1)  min (vn (t) + 1,v max)
­ Etape 2 - Deceleration
Le vehicule n decelere si la distance dn = Xn+1 - Xn par rapport au vehicule 
precedent ne permet
pas de maintenir la vitesse vn .
vn (t + 1)  min (vn (t + 1),dn - 1)
­ Etape 3 - Facteur aleatoire
Pour caracteriser le comportement aleatoire de chacun des conducteurs, le 
vehicule n decelere
avec une probabilite p, mais la vitesse n'est pas modifiee si vn (t+1) = 0 (pas 
de marche arriere).
On utilise pour cela la fonction rand() qui renvoit une valeur aleatoire  
[0..1].
Si rand() < p

alors vn (t + 1)  max (vn (t + 1) - 1,0)

­ Etape 4 - Deplacement
Une fois les vitesses determinees, les positions des vehicules au pas de temps 
suivant sont
determinees de facon simultanee.
Xn (t + 1)  Xn (t) + vn (t + 1)

14/15

Annexe 2 - Rappels des syntaxes en Python
Remarque : sous Python, l'import du module numpy permet de realiser des 
operations pratiques sur
les tableaux : from numpy import *. Les indices de ces tableaux commencent a 0.
tableau a une dimension
acceder a un element
ajouter un element
tableau a deux dimensions (matrice)
acceder a un element
extraire une portion de tableau
(2 premieres colonnes)
tableau de 0 ( 2 lignes, 3 colonnes)
dimension d'un tableau T de taille (i, j)
sequence equirepartie quelconque de 0 a 10.1
(exclus) par pas de 0.1
definir une chaine de caracteres

Python
L=[1,2,3] (liste)
v=array([1,2,3]) (vecteur)
v[0] renvoie 1
L.append(5) uniquement sur les listes
M=array(([1,2,3],[3,4,5]))
M[1,2] ou M[1][2] donne 5
M[:,0:2]
zeros((2,3))
T.shape donne [i,j]
arange(0,10.1,0.1)
mot="Python"

taille d'une chaine
extraire des caracteres

len(mot)
mot[2:7]

boucle For

for i in range(10):
print ( i )

condition If

if (i>3):
print (i)
else:
print("hello")

definir une fonction qui possede un argument et
renvoie 2 resultats

def fonction(param):
res1=param
res2=param*param
return res1,res2

trace de points (o) de coordonnees (x,y)

plot(x,y,"o")

FIN

15/15

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



CCP Informatique PSI 2017 -- Corrigé
Ce corrigé est proposé par Jean-Julien Fleck (professeur en CPGE) ; il a été 
relu
par Josselin Giet (ENS Ulm) et Julien Dumont (professeur en CPGE).

Ce sujet bien articulé et progressif étudie la circulation automobile et 
l'évolution
de bouchons aux heures de pointe sur l'autoroute, depuis l'étude expérimentale 
via le
suivi de la circulation jusqu'aux simulations numériques en utilisant soit la 
mécanique
des fluides, soit des automates cellulaires.
· La première partie se concentre sur les aspects « expérimentaux » en 
interrogeant une base de données (questions 1 et 2) qui stocke les informations 
autoroutières avant de les représenter graphiquement (question 3) et de les 
traiter
automatiquement pour détecter un ralentissement via un algorithme de tri par
insertion destiné à calculer la médiane des vitesses mesurées (questions 4 et 
5).
· Vient alors une première proposition de simulation (questions 6 à 15) qui 
traite
le trafic routier comme un flux hydrodynamique, ce qui revient à résoudre une
équation aux dérivées partielles par différentes méthodes afin d'analyser leurs
points forts ainsi que leurs motifs de divergence.
· Une seconde simulation à base d'automates cellulaires (questions 16 à 19) clôt
le sujet en se rapprochant légèrement du sujet d'informatique des Mines de la
même année, sans pour autant faire doublon avec lui. L'avantage est que l'on
peut très rapidement comprendre comment créer ses propres bouchons à partir
de coups de freins intempestifs de conducteurs peu attentifs.
Le sujet balaie une grande partie du programme de première année avec une brève
incursion en deuxième année concernant l'algorithme de tri présenté en question 
4.
Il permet de se familiariser avec une structure de données matricielle qui 
stocke
les évolutions temporelle et spatiale des objets considérés en une seule 
entité, ce qui
peut certainement être utilisé dans un TIPE lors de simulations similaires. 
D'ailleurs,
l'ensemble des codes permettant de reproduire certaines des figures de ce 
corrigé sont
disponibles à l'adresse
https://github.com/jjfPCSI1/codes_concours_CPGE
Pour ceux qui voudraient aller plus avant dans la partie physique, le sujet PSI
Centrale 2005, disponible sur Doc-Solus.fr, traite assez complètement de la 
modélisation physique abordée par ce sujet.

Indications
Partie II
1 La difficulté est dans la jointure.
2 Penser à l'instruction GROUP BY.
3 L'usage de Numpy trivialise quelque peu la fonction, mais on peut tout à fait
faire explicitement les boucles.
4 Se demander comment on fait pour trier « naturellement » ses cartes.
5 Que se passe-t-il pendant au moins la moitié du temps ?
Partie III
7 Là encore, Numpy simplifie les choses.
8 La dépendance temporelle n'influe que sur l'intervalle de concentrations 
explorées.
9 Penser à jeter un oeil en question 11 pour savoir les arguments a priori 
attendus
par le concepteur du sujet.
10 Il s'agit, comme d'habitude en physique, d'approximer les dérivées par leurs 
taux
d'accroissement, tantôt selon l'axe temporel, tantôt selon l'axe spatial, selon 
la
dérivée considérée.
11 Pour éviter de traîner de multiples vérifications à droite des listes, 
penser à utiliser
l'opération modulo (via l'opérateur %) pour mettre en place les conditions aux
limites périodiques.
13 Le schéma d'intégration est adapté pour un déplacement dans le sens des 
flèches
des représentations de la question 12.
14 L'introduction d'une fonction annexe pour la dérivation peut permettre de 
simplifier le code.
Partie IV
16 Se rappeler qu'on désire modéliser la réalité et que, dans celle-ci, une 
voiture a
une certaine longueur. Pour le calcul de la vitesse, ne pas oublier les 
changements
d'unités adéquats.
17 Traduire les trois premières étapes de l'algorithme proposé à chaque fois 
que l'on
croise une voiture dans une case.
18 Ne pas oublier qu'il ne faut prédire un déplacement que si une voiture est 
effectivement présente dans la case considérée.
19 Les bouchons correspondent aux agrégats noirs. Pour améliorer la simulation,
penser à tous les paramètres des autoroutes réelles que l'on a été amené à 
simplifier
dans cette étude.

II. Traitement des données expérimentales
1 La requête SQL demandée nécessite de faire une jointure avec la table des 
stations
pour trouver la station voulue.
SELECT id_comptage,date,voie,q_exp,v_exp
FROM COMPTAGES JOIN STATIONS
ON STATIONS.id_station = COMPTAGES.id_station
WHERE nom = 'M8B'
Notons que la table de provenance de l'attribut id_station doit être précisée
lors de la jointure puisqu'il porte le même nom dans les deux tables. En 
revanche,
il n'y a pas d'ambiguïté concernant les autres attributs, il n'est donc pas 
nécessaire
de les préciser.
2 La requête demandée nécessite maintenant de rassembler (à l'aide de 
l'instruction
GROUP BY) les mesures faites à un même instant sur toutes les voies pour sommer 
les
voitures qui y passent.
SELECT date,SUM(q_exp) FROM COMPTAGES_M8B GROUP BY date
3 Il s'agit là de calculer le vecteur des concentrations correspondant aux 
différentes
données en effectuant le rapport, à chaque fois, du débit par la vitesse. On 
peut
le faire de manière naturelle en itérant sur les différentes composantes des 
vecteurs
avant de faire le graphique.
On va ici procéder comme le suggère l'énoncé, c'est-à-dire importer numpy
et matplotlib.pyplot « à la sauvage » par les commandes from numpy
import * et from matplotlib.pyplot import *, mais il s'agit a priori d'un
mauvais réflexe en pratique puisque cela pollue l'espace des noms et peut mener 
à des conflits si les deux modules définissent une fonction de même nom.
Cela peut néanmoins se comprendre pour une épreuve écrite où le nombre
de fonctions disponibles est réduit et cela permet donc d'appeler zeros ou
plot sans préciser les habituels np.zeros ou plt.plot.
En outre, on utilise par la suite une autre forme de zeros que celle rappelée 
en annexe, à savoir zeros(n) pour créer un vecteur contenant n zéros.
Le rappel de l'annexe concerne la création de tableaux multidimensionnels
pour lesquels il faut spécifier la taille de chaque dimension et qui servirait
si on avait à initialiser le tableau C des concentrations, utilisé à partir de 
la
question 9, mais l'énoncé ne demande finalement jamais de le faire.
from numpy import *
from matplotlib.pyplot import *

# Imports présupposés par le sujet
# (mais mauvaise bonne idée en pratique)

def trace(q_exp,v_exp):
n = len(v_exp)
# Taille des vecteurs utilisés
c_exp = zeros(n)
# Initialisation du tableau des concentrations
for i in range(n):
# pour un calcul séquentiel.
c_exp[i] = q_exp[i] / v_exp[i]
plot(c_exp,q_exp,'o') # Tracé du graphe (Gare à l'ordre des arguments !)

Néanmoins, comme l'énoncé signale que les arguments sont des tableaux Numpy,
on peut aussi calculer c_exp « au vol » en utilisant les facilités de Numpy, 
qui s'occupe
tout seul de la boucle sous-jacente sur toutes les composantes des deux 
vecteurs. Ainsi,
l'écriture de la fonction s'en trouve grandement simplifiée :
def trace(q_exp,v_exp):
c_exp = q_exp / v_exp
plot(c_exp,q_exp,'o')

# Divisions composante par composante
# Tracé du graphe

Logiquement, une telle solution devrait être acceptée sans sourciller par le
correcteur, mais il peut être bon de rappeler dans sa copie que l'on sait que
Numpy s'occupe des boucles associées « derrière le rideau ».
4 Il s'agit ici d'un algorithme de tri par insertion. On prend un à un chaque
élément (de gauche à droite) et on le laisse « couler » dans la partie gauche 
de la liste
(qui est celle qui est triée à ce stade), jusqu'à ce qu'il trouve sa place, 
c'est-à-dire
jusqu'à ce qu'il ne soit plus le plus petit considéré jusqu'ici dans les 
comparaisons.
Pour qu'il fonctionne, il faut « faire de la place », donc décaler chaque 
élément (depuis
la position j-1) d'un cran vers la droite (donc vers la position j en utilisant 
l'instruction v_exp[j] = v_exp[j-1]) tout en continuant de déplacer l'élément v 
vers
la gauche via j = j-1. C'est donc la deuxième proposition qui est la bonne
et la fonction s'écrit totalement :
def congestion(v_exp):
nbmesures = len(v_exp)
for i in range(nbmesures):
# Pour chaque point de mesure,
v = v_exp[i]
# on note la valeur à classer
j = i
# et d'où l'on part.
# Tant qu'on n'arrive pas tout à gauche ou qu'on ne trouve
while 0