Centrale Informatique MP-PC-PSI 2018

Thème de l'épreuve Simulation de la cinétique d'un gaz parfait
Principaux outils utilisés algorithmique, programmation, complexité, représentation des nombres, bases de données
Mots clefs simulation, gaz, particules, choc, aléatoire, probabilités, histogramme, insertion, erreur

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


î, % Informatique

00
"a , 1--|
__/ MP, PC, PSI, TSI @

N

EÜNE[IUHS EENTHHLE-SUPÊLEE 3 heures Calculatrices autorisées

Simulation de la cinétique d'un gaz parfait

La théorie cinétique des gaz vise a expliquer le comportement macroscopique 
d'un gaz à partir des mouvements
des particules qui le composent. Depuis la naissance de l'informatique, de 
nombreuses simulations numériques
ont permis de retrouver les lois de comportement de difiérents modèles de gaz 
comme celui du gaz parfait.

Ce sujet s'intéresse à un gaz parfait monoatomique. Nous considérerons que le 
gaz étudié est constitué de N
particules sphériques, toutes identiques, de masse m et de rayon R, confinées 
dans un récipient rigide. Les
simulations seront réalisées dans un espace à une, deux ou trois dimensions ; 
le récipient contenant le gaz sera,
suivant le cas, un segment de longueur L, un carré de côté L ou un cube d'arête 
L.

Dans le modèle du gaz parfait, les particules ne subissent aucune force (leur 
poids est négligé) ni aucune autre
action à distance. Elle n'interagissent que par l'intermédiaire de chocs, avec 
une autre particule ou avec la paroi
du récipient. Ces chocs sont toujours élastiques, c'est--à--dire que l'énergie 
cinétique totale est conservée.

Les seuls langages de programmation autorisés dans cette épreuve sont Python et 
SQL. Pour répondre à une
question il est possible de faire appel aux fonctions définies dans les 
questions précédentes. Dans tout le sujet
on suppose que les bibliothèques math, numpy et random ont été importées grâce 
aux instructions

import math
import numpy as np
import random

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

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

def maFonction(nzint, x:float, 1:[str]) --> (int, np.ndarray)z

signifie que la fonction maFonction prend trois arguments, le premier est un 
entier, le deuxième un nombre à
virgule flottante et le troisième une liste de chaines de caractères et qu'elle 
renvoie un couple dont le premier
élément est un entier et le deuxième un tableau numpy. Il n'est pas demandé aux 
candidats de recopier les
entêtes avec annotations telles qu'elles sont fournies dans ce sujet, ils 
peuvent utiliser des entêtes classiques. Ils
veilleront cependant à décrire précisément le rôle des fonctions qu'ils 
définiraient eux--mêmes.

Une liste de fonctions utiles est donnée a la fin du sujet.
Représentation en Python

Chaque particule est représentée par une liste de deux éléments, le premier 
correspond a la position de son
centre, la deuxième à sa vitesse. Chacun de ces éléments (position et vitesse) 
est représenté par un vecteur
(np.ndarray) dont le nombre de composantes correspond a la dimension de 
l'espace de simulation.

Les positions et vitesses sont exprimées sous forme de coordonnées cartésiennes 
dans un repère orthonormé
dont l'origine est placée dans un coin du récipient contenant le gaz et dont 
les axes sont parallèles aux côtés
du récipient issus de ce coin de façon à ce que tout point situé a l'intérieur 
du récipient ait ses coordonnées
comprises entre 0 et L.

Les positions sont exprimées en mètres et les vitesses en mns--1. La figure 1 
propose des exemples de particules
dans des espaces de diverses dimensions.

pl = [np.array([5.3]), np.array([4l2.3])] # 1D
p2 = [np.array([3.l, 4.8]), np.array([24l, --91.4])] # 2D
p3 = [np.array([5.2, 3.2, 2.31), np.array([--lBO.1, 320, 260.2])] # 3D

Figure 1 Exemples de particules

2018-02-27 14:14:38 Page 1/8 £cc BY--NC-SA

I Initialisation

Pour pouvoir réaliser une simulation, il convient de disposer d'une situation 
initiale, c'est--à--dire d'un ensemble
de particules réparties dans le récipient et dotées d'une vitesse initiale 
connue. Cette partie s'intéresse au
positionnement aléatoire d'un ensemble de particules. L'attribution de vitesses 
initiales a ces particules ne sera
pas abordé ici.

I.A -- Placement en dimension 1

Nous cherchons d'abord comment placer N particules (sphères de rayon R) le long 
d'un segment de longueur L
sans qu'elles se chevauchent ni qu'elles sortent du segment. La figure 2 montre 
quelques exemples de placements

possibles avec N = 5, R = 0,5 et L = 10.

O: ::::10 0::::: 10

( > < > ( > ( >< ) , /\ F\ /'\ . ,
0 10 0 V O V O U 10
Figure 2 Exemples de placement de 5 particules de rayon 0,5 sur un segment de 
longueur 10

La fonction placementlD construit aléatoirement, a partir des paramètres 
géométriques du problème (nombre
et rayon des particules, taille du récipient), une liste de coordonnées 
correspondant à la position initiale du
centre de chaque particule.

1 def placementlD(N:int, R:float, L:float) --> [np.ndarray]z

2 def possible(c:np.ndarray) --> bool:
3 if CEO] < R or CEO] > L -- R: return False
4 for p in res:
5 if abs(c[0] -- p[O]) < 2*R: return False
6 return True
? res = []
8 while 1en(res) < N:
p = L * np.random.rand(l)
10 if possible(p): res.append(p)
11 return res

Q 1. Détailler l'action de la ligne 9.

Q 2. Quelle est la signification du paramètre c de la fonction possible (ligne 
2) '?
Q 3. Expliquer le rôle de la ligne 3.

Q 4. Expliquer le rôle des lignes 4 et 5.

Q 5. Donner en une phrase le rôle de la fonction possible.

Q 6. Proposer une nouvelle version de la ligne 9 permettant d'éviter certains 
rejets de la part de la fonction
possible.

Q 7. On considère l'appel placementlD(4, 0.5, 5) et on suppose que les trois 
premières particules ont

été placées aux points d'abscisses 1, 2,5 et 4 (figure 3). Quelle sera la suite 
du déroulement de la fonction

placementlD '?
0 5

Figure 3
Q 8. Quelle est la complexité temporelle de la fonction placement1D dans le cas 
où N << Nmax, nombre
maximal de particules de rayon R pouvant être placées sur un segment de 
longueur L ?
Q 9. Pour remédier de manière simple (mais non optimale) à la situation de la 
question 7, on décide

de recommencer à zéro le placement des particules dès qu'une particule est 
rejetée par la fonction possible.
Réécrire les lignes 7 à 11 de la fonction placementlD pour mettre en oeuvre 
cette décision.

I.B -- Optimisation du placement en dimension 1

Pour placer aléatoirement N particules le long d'un segment, nous envisageons 
une approche plus efficace que
celle étudiée dans la sous--partie LA.

L'idée est de calculer l'espace laissé libre sur le segment cible par N 
particules puis de répartir aléatoirement cet
espace libre entre les particules. Afin de conserver une répartition uniforme 
des particules dans tout le segment,
nous utilisons l'algorithme suivant :
1. déterminer EUR, espace laissé libre par les N particules dans le segment [O, 
L[ ;
2. placer aléatoirement dans le segment [O,Ë[, N particules virtuelles 
ponctuelles (R = O) ; a cette étape, deux
particules peuvent parfaitement occuper la même abscisse : il n'y a pas de 
conflit ;
3. remplacer chaque particule virtuelle par une particule réelle de rayon R en 
décalant toutes les particules
(réelles et virtuelles) situées plus a droite de façon à dégager l'espace 
nécessaire.
Q 10. Écrire la fonction d'entête
def placementlDrapide (N: int, R:float, L:float) --> [np.ndarray] :

qui implante cet algorithme et renvoie la liste des coordonnées des centres de 
N particules de rayon R réparties
aléatoirement le long d'un segment situé entre les abscisses () et L. On 
précise que l'ordre de la liste résultat
n'est pas important.

Q 11. Quelle est la complexité de la fonction placement 1Drapide ? Commenter.

I.C' -- Analyse statistique

Afin de vérifier que la fonction placementlDrapide produit une répartition de 
particules uniformément répartie
sur le segment cible, on l'appelle un grand nombre de fois et on comptabilise 
pour chaque résultat obtenu la
position initiale de chaque particule. Le résultat final est présenté sous 
forme d'un histogramme dont l'axe
horizontal correspond a l'abscisse du centre de la particule dans l'intervalle 
[O, L] et l'axe vertical au nombre
total de particules placées à cette abscisse au cours des différentes 
exécutions de la fonction.

Q 12. Tracer et justifier l'allure des histogrammes pour N = 1, N = 2 et N = 5 
dans le cas où R = 1 et
L = 10.

I. D -- Dimension quelconque

L'algorithme optimisé pour un segment, n'est pas utilisable pour des espaces de 
dimensions supérieures. Nous
allons donc généraliser la fonction placement 1D pour la transformer en une 
fonction utilisable dans un espace
de dimension 1, 2 ou 3.

Q 13. En s'inspirant de la fonction placementlD, écrire la fonction d'entête
def placement (Dzint, N:int, R:float, L:float) --> [np.ndarray]z

qui renvoie la liste des coordonnées des centres de N particules sphériques de 
rayon R placées aléatoirement dans
un récipient de côté L dans un espace a D dimensions. Les modifications prévues 
aux questions 6 et 9 seront
prises en compte dans cette fonction.

II Mouvement des particules
On suppose que l'on dispose désormais d'une fonction d'entête
def situationInitiale(D:int, N:int, R:float, L:float) --> [[np.ndarray, 
np.ndarray]]z

qui renvoie une liste de N particules de rayon R, représentées chacune par une 
liste a deux éléments (position et
vitesse, cf. figure 1), placées aléatoirement a l'intérieur d'un récipient de 
taille L dans un espace a D dimensions.
À partir de cette situation initiale, les positions et vitesses des particules 
vont évoluer au gré du déplacement
des particules, des différents chocs entre elles et des rebonds sur les parois. 
On appelle évènement chaque choc
ou rebond.

II.A -- Analyse physique
Q 14. Comment évolue une particule entre deux évènements '?

Flacons--nous dans un espace à une dimension et considérons deux particules de 
masses ml et m2 qui entrent
en collision avec les vitesses initiales 51 et 62. Les vitesses Ül' et 52' des 
deux particules après le choc sont données
par

% m -- m à 2m %
Ul, : 1 2 "1 __ 2 'U2
...1 " m2 m1 " m2
2m % m -- m à
,02/ = 1 Ul __ 2 1 02
ml __ 7712 m1 _- 7712
Q 15. Que deviennent ces formules lorsque m1 : m2 '? Commenter.

Q 16. Que deviennent ces formules lorsque ml << m2 '? À quelle situation ce cas 
correspond--t--il dans le
problème qui nous occupe '?

II.B -- Évolution des particules

Q 17. Écrire la fonction d'entête
def vol(p: [np.ndarray, np.ndarray] , t:float) --> None:

qui met a jour l'état de la particule p (position et vitesse dans un espace de 
dimension quelconque) au bout
d'un vol de 1: secondes sans choc ni rebond.

Q 18. Écrire la fonction d'entête
def rebond (p: [np.ndarray, np.ndarray] , d: int) --> None:

qui met a jour la vitesse de la particule p suite a un rebond sur une paroi 
perpendiculaire à la dimension d'indice
d, c'est--à--dire l'axe des abscisses si d vaut 0, l'axe des ordonnées si d 
vaut 1 et l'axe des cotes si d vaut 2.

Par généralisation du résultat obtenu dans un espace a une dimension, on 
supposera que le rebond d'une
particule sur une paroi ne modifie pas la composante de la vitesse parallèle à 
la paroi et change le signe de sa
composante normale à la paroi (rebond parfait). La fonction rebond n'est pas 
chargée de vérifier que la particule
se trouve au contact d'une paroi.

Q 19. On revient dans un espace à une dimension. Écrire la fonction d'entête
def choc (pl: [np.ndarray, np.ndarray] , p2: [np.ndarray, np.ndarray]) --> None:

qui modifie les vitesses des deux particules, pl et p2, suite au choc de l'une 
contre l'autre. La fonction choc
n'est pas chargée de vérifier que les deux particules sont en contact.

On supposera dans la toute la suite que l'on dispose d'une version de la 
fonction choc également opérationnelle
dans un espace a deux et trois dimensions.

III Inventaire des évènements

Chaque évènement sera représenté par une liste de cinq éléments avec la 
signification suivante :

0. un booléen indiquant si l'évènement est valide ou pas ;

l. un flottant donnant le nombre de secondes, à partir de l'instant courant, au 
bout duquel l'évènement aura
lieu ;

2. un entier compris entre 0 et N -- 1 donnant l'indice dans la liste des N 
particules de la première (ou seule)
particule concernée par l'évènement ;

3. un entier compris entre 0 et N -- 1 donnant l'indice de la deuxième 
particule concernée par l'évènement ou
None s'il n'y a pas de deuxième particule concernée (l'évènement est un rebond 
sur une paroi) ;

4. un entier compris entre 0 et D -- 1 donnant l'indice de la dimension 
perpendiculaire à la paroi concernée par
l'évènement ou None s'il n'y a pas de paroi concernée (l'évènement est un choc 
entre deux particules).

On supposera, sans avoir besoin de le vérifier, qu'on a toujours une et une 
seule valeur None parmi les deux
derniers éléments de tout évènement.

Ainsi [True , 0.4, 34, 57, None] désigne le choc entre les particules d'indice 
34 et 57 qui aura lieu dans 0,4 8.
Et [True, 1.7, 34, None, 1] désigne le rebond de la particule d'indice 34 sur 
une paroi perpendiculaire à la
dimension d'indice 1 (axe des ordonnées) qui aura lieu dans 1,7 s.

III.A -- Prochains évènements dans un espace à une dimension

Q 20. Écrire, pour un espace à une dimension, la fonction d'entête
def tr (p: [np.ndarray, np.ndarray] , R:float, L:float) --> None or (float, 
int) :

qui détermine dans combien de temps la particule p, de rayon R, rencontrera une 
paroi du récipient de taille L,
en faisant abstraction de toute autre particule qui pourrait se trouver sur son 
chemin. Cette fonction renvoie
None si la particule ne rencontre jamais de paroi, sinon elle renvoie un couple 
dont le premier élément est la
durée (en secondes) avant le rebond et le deuxième la direction de la paroi 
désignée par l'indice de sa dimension
perpendiculaire.

Q 21. Toujours dans un espace à une dimension, écrire la fonction d'entête
def tc(p1: [np.ndarray, np.ndarray] , p2: [np.ndarray, np.ndarray] , R:float) 
--> None or float:

qui détermine si les deux particules pl et p2, de rayon R, vont se rencontrer, 
en faisant abstraction de la
présence des autres particules et des parois, autrement dit en considérant que 
ces deux particules sont seules
dans un espace infini. Cette fonction renvoie None si les deux particules ne se 
rencontrent jamais, sinon elle
renvoie le temps (en secondes) au bout duquel les particules entrent en 
collision.

On supposera dans la toute la suite que l'on dispose d'une version des fonction 
tr et tc également opérationnelles
dans un espace a deux et trois dimensions.

III.B -- Catalogue d'évènements

Afin d'alimenter l'algorithme de la partie suivante, on souhaite construire un 
catalogue des évènements qui
pourraient se produire prochainement. Ce catalogue sera représenté par une 
liste dans laquelle les évènements,
représentés par la liste de cinq éléments décrite au début de cette partie, 
sont ordonnés par date décroissante :
le plus lointain en début de liste, le plus proche en fin de liste.

Q 22. Écrire la fonction d'entête

def ajoutEv(catalogue: [[bool, float, int, int or None, int or None]] ,
e: [bool, float, int, int or None, int or None]) --> None:

qui ajoute au bon endroit dans la liste catalogue l'évènement e. La liste 
catalogue contient des évènements
ordonnés par temps décroissant.

Q 23. Écrire la fonction d'entête

def ajoutlp(catalogue:[[bool, float, int, int or None, int or None]], i:int,
R:float, L:float, particules:[[np.ndarray, np.ndarray]]) --> None:

qui ajoute, dans la liste ordonnée d'évènements catalogue, les prochains 
évènements potentiels concernant la
particule d'indice i de la liste particules qui contient toutes les particules 
présentes dans le récipient. Le
paramètre R donne le rayon d'une particule et L la taille du récipient. Les 
évènements à prendre en compte
sont le prochain rebond contre une paroi et le prochain choc avec chacune des 
autres particules (cf HLA). Les
prochains évènements seront supposés valides et la fonction veillera à 
maintenir ordonnée la liste catalogue.

Q 24. Écrire la fonction d'entête

def initCat(particules:[[np.ndarray, np.ndarray]], R:float,
L:float) --> [[bool, float, int, int or None, int or None]]:

qui utilise la fonction ajout1p et qui renvoie la liste, ordonnée par temps 
décroissant, des prochains évènements
potentiels concernant une liste de particules particules de rayon R dans un 
récipient de taille L.

Q 25. Expliquer pourquoi la liste renvoyée par la fonction initCat contient 
certains éléments qui corres--
pondent en fait au même évènement.

Q 26. Déterminer la complexité temporelle de la fonction initCat pour un espace 
a une dimension.

Q 27. Quelle est la fonction à optimiser en priorité afin d'améliorer la 
complexité de la fonction initCat '?
Quel algorithme classique peut être utilisé pour optimiser cette fonction '?

IV Simulation

Nous disposons désormais des éléments de base pour simuler l'évolution d'un 
ensemble de particules identiques
enfermées dans un récipient. En partant d'une situation initiale, nous pouvons 
déterminer les prochains évène--
ments possibles, le plus proche de ces évènements va forcément avoir lieu. Nous 
pouvons alors établir un nouvel
état de l'ensemble des particules juste après cet évènement, puis déterminer 
une nouvelle liste des prochains évè--
nements possibles à partir de cette nouvelle situation. En répétant ce 
traitement, il est théoriquement possible
de déterminer la position et la vitesse de chacune des particules a un instant 
quelconque dans le futur.

Q 28. Montrer que la liste des prochains évènements possibles ne peut jamais 
être vide, sauf si toutes les
particules sont initialement à l'arrêt.

Dans toute la suite, nous considèrerons qu'au moins une particule est en 
mouvement.
Q 29. Ecrire la fonction d'entête

def etape (particules: [[np.ndarray, np.ndarray]] ,
e:[bool, float, int, int or None, int or None]) --> None:

qui, partant d'une liste de particules particules représentant la situation a 
l'instant courant, modifie l'état de
chaque particule pour refléter la situation des particules juste après 
l'évènement e (supposé valide), en supposant
qu'aucun autre évènement n'arrive avant celui--ci.

Disposant de la fonction etape, il suffirait de la combiner avec la fonction 
initCat pour implanter l'algorithme
de simulation décrit plus haut. Cependant, étant donné la complexité de 
initCat, il semble intéressant d'opti--
miser cette phase de l'algorithme. Pour cela, remarquons que les évènements qui 
ne concernent par les particules
impliquées dans l'évènement traité par la fonction etape restent valides, a un 
décalage temporel près. Les seuls
nouveaux prochains évènements possibles concernent les particules impliquées 
dans l'évènement traité.

Q 30. Écrire la fonction d'entête

def majCat(catalogue: [[bool, float, int, int or None, int or None",
particules: [[np.ndarray, np.ndarray]] ,
e: [bool, float, int, int or None, int or None], R:float, L:float) --> None:

qui met a jour son paramètre catalogue, liste ordonnée des prochains évènements 
potentiels, en supposant que
particules représente la situation juste après l'évènement e, supposé valide et 
déjà retiré de catalogue. Les
paramètres R et L désignent respectivement le rayon d'une particule et la 
taille du récipient. Afin de limiter les

manipulations de listes, les évènements qui n'ont plus cours seront conservés 
dans le catalogue et simplement
marqués non valides.

On dispose de la fonction d'entête

def enregistrer(bdd, t:float, e:[bool, float, int, int or None, int or None],
particules: [[np.ndarray, np.ndarray]]) --> None:

qui enregistre dans la base de données bdd des informations à propos de 
l'évènement e survenu au temps t de
la simulation. Le temps de la simulation est exprimé en secondes, le début de 
la simulation étant pris comme
origine. Le paramètre particules donne la situation (position, vitesse) des 
particules au temps t considéré,
juste après la survenue de l'évènement e.

Q 31. Écrire la fonction d'entête
def simulation(bdd, d:int, N:int, R:float, L:float, T:float) --> int:

qui simule l'évolution de N particules identiques de rayon R dans un récipient 
de côté L dans un espace à d
dimensions pendant la durée T (exprimée en secondes). Cette fonction utilise 
une situation initiale générée
aléatoirement par l'intermédiaire de la fonction situationInitiale (partie H) 
et renvoie le nombre d'évène--
ments ayant eu lieu pendant toute la simulation. D'autre part, elle enregistre 
chaque évènement dans la base
de données bdd.

Q 32. Comment sont gérés les doublons repérés a la question 25 '?

Q 33. Dans la représentation choisie pour les évènements, le temps auquel cet 
évènement peut survenir est
donné par rapport a un instant courant (qui correspond à l'instant de 
l'évènement précédent dans l'implantation
choisie) ce qui oblige à recaler chaque évènement au fur et à mesure que le 
temps de la simulation s'écoule. Une
autre possibilité aurait été d'indiquer le temps de chaque évènement par 
rapport a une référence fixe (le début
de la simulation). Discuter des avantages et des inconvénients de chaque 
représentation en terme de précision
du résultat et de complexité de l'algorithme. La représentation retenue ici 
est--elle la mieux adaptée des deux
pour traiter le problème posé '?

V Exploitation des résultats

On dispose d'une version plus générale de la fonction simulation pour laquelle 
toutes les particules ne sont plus
nécessairement identiques. Cette fonction enregistre ses résultats dans une 
base de données dont la structure
est donnée figure 4.

SIMULATIÜN REBÜND PARTICULE
SI_NUM <-- SI_NUM integer PA_NUM integer
SI_DEB RE_NUM integer / PA_NÜM varchar(100)
SI_DUR PA_NUM integer PA_M real
SI_DIM RE_T float PA_R real
SI_N RE_DIR integer
SI_L RE_VIT real

RE_VP real

Figure 4 Structure physique de la base de données des résultats de simulation

Cette base comporte les trois tables suivantes :

-- la table SIMULATION, de clef primaire SI_NUM, donne les caractéristiques de 
chaque simulation effectuée. Elle
contient les colonnes

. SI_NUM numéro d'ordre de la simulation (clef primaire)
. SI_DEB date et heure du lancement du programme de simulation

. SI_DUR durée (en secondes) de la simulation (il ne s'agit pas du temps 
d'exécution du programme, mais
du temps simulé)

. SI_DIM nombre de dimensions de l'espace de simulation
. SI_N nombre de particules pour cette simulation
. SI_L (en mètres) taille du récipient utilisé pour la simulation
-- la table PARTICULE, de clef primaire PA_NUM7 des types de particules 
considérées. Elle contient les colonnes
. PA_NUM numéro (entier) identifiant le type de particule (clef primaire)
. PA_NOM nom de ce type de particule
. PA_M masse de la particule (en grammes)
. PA_R rayon (en mètres) de la particule

-- la table REBÛND, de clef primaire (SI_NUM, RE_NUM), liste les chocs des 
particules avec les parois du récipient.
Elle contient les colonnes

. SI_NUM numéro d'ordre de la simulation ayant généré ce rebond

. RE_NUM numéro d'ordre du rebond au sein de cette simulation

. PA_NUM numéro du type de particule concernée par ce rebond

. RE_T temps de simulation (en secondes) auquel ce rebond est arrivé

. RE_DIR paroi concernée: entier non nul de l'intervalle [--SI_DIM, SI_DIM] 
donnant la direction de la
normale à la paroi. Ainsi --2 désigne la paroi située en y = 0 alors que 1 
désigne la paroi située en :c = L

. RE_VIT norme de la vitesse de la particule qui rebondit (en m-s_1)
. RE_VP valeur absolue de la composante de la vitesse normale à la paroi (en 
m-s"1)

Q 34. Écrire une requête SQL qui donne le nombre de simulations effectuées pour 
chaque nombre de dimen--
sions de l'espace de simulation.

Q 35. Écrire une requête SQL qui donne, pour chaque simulation, le nombre de 
rebonds enregistrés et la
vitesse moyenne des particules qui frappent une paroi.

Q 36. Écrire une requête SQL qui, pour une simulation n donnée, calcule, pour 
chaque paroi, la variation
de quantité de mouvement due aux chocs des particules sur cette paroi tout au 
long de la simulation. On se
rappellera que lors du rebond d'une particule sur une paroi la composante de sa 
vitesse normale à la paroi est
inversée, ce qui correspond a une variation de quantité de mouvement de 2m|v,l 
où m désigne la masse de la
particule et @L la composante de sa vitesse normale à la paroi.

Opérations et fonctions Python disponibles

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

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

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

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

Opérations sur les listes
-- 1en (u) donne le nombre d'éléments de la liste u :
1en([1, 2, 3]) --> 3 ; len([[1,2] , [3,Æl]) --> 2
-- u + v construit une liste constituée de la concaténation des listes u et v :
[1, 2] + [3, 4, 5] --> [1, 2, 3, 4, 5]
-- n * u construit une liste constitué de la liste 11 concaténée 11 fois avec 
elle--même :
3 * [1, 2] --> [1, 2, 1, 2, 1, 2]
-- e in 11 et e not in 11 déterminent si l'objet e figure dans la liste u
2 in [1, 2, 3] -->True;2 not in [1, 2, 3] --> False
-- u.append(e) ajoute l'élément e à la fin de la liste 11 (similaire a u = u + 
[e])
-- u.pop() renvoie le dernier élément de la liste u (u [--1]) et le supprime 
(del u[--1])
-- del u[i] supprime de la liste u son élément d'indice i
-- del u [i : j] supprime de la liste u tous ses éléments dont les indices sont 
compris dans l'intervalle [i, j[

-- u . remove (e) supprime de la liste 11 le premier élément qui a pour valeur 
e, déclenche l'exception ValueError
si e ne figure pas dans u

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

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

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

Opérations sur les tableaua: (np.ndarray)

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

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

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

-- np . random. rand (n), np.random.rand (n, m) crée un tableau de la forme 
indiquée (11 lignes, m colonnes) en
initialisant chaque élément avec une valeur aléatoire issue d'une distribution 
uniforme sur [O, 1[

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

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

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

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

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

-- np . concatenate ( (al , a2)) construit un nouveau tableau en concaténant 
deux tableaux ; al et a2 doivent
avoir le même nombre de dimensions et la même taille à l'exception de leur 
taille dans la première dimension
(deux matrices doivent avoir le même nombre de colonnes pour pouvoir être 
concaténées)

-- a. sort (d) trie le tableau a en place suivant sa dimension d'indice (1 (par 
défaut, la dernière du tableau) :
a.sort(0) trie les éléments du vecteur a ou les lignes de la matrice a ; 
a.sort(1) trie les colonnes de la
matrice a

-- np.sort(a, d) renvoie une copie triée du tableau a suivant sa dimension 
d'indice d (voir a. sort (d) pour
la signification exacte du paramètre d)

oooFlNooo

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



Centrale Informatique MP-PC-PSI 2018 -- Corrigé
Ce corrigé est proposé par Cyril Ravat (professeur en CPGE) ; il a été relu par
Jean-Julien Fleck (professeur en CPGE) et Guillaume Batog (professeur en CPGE).

Ce sujet d'informatique a pour objectif la simulation microscopique d'un gaz
parfait. Le mouvement particulaire d'un tel gaz, abordé en physique en première
année de prépa, permet de s'appuyer sur un modèle simple et accessible. L'étude 
est
divisée en cinq parties de tailles sensiblement équivalentes.
· La première aborde l'initialisation de la simulation, c'est-à-dire le 
placement originel et aléatoire des particules dans l'espace. Si les premières 
questions, faciles,
permettaient à tous les candidats d'engranger quelques points, les dernières 
sont
beaucoup plus difficiles à cause d'un cahier des charges complexe ; elles 
donnaient l'occasion aux meilleurs candidats de se mettre en valeur. On notera 
une
question 12 très difficile et relativement mal posée.
· On traite ensuite l'aspect physique du mouvement des particules, dans un 
modèle simplifié à une dimension. Les fonctions demandées sont, tout comme leur
support physique, assez élémentaires.
· Dans la troisième partie, le problème de la gestion des différents événements
pour un système de N particules est posé. Une solution intéressante est fournie
et étudiée en détail, notamment au niveau de la complexité des algorithmes
mis en jeu. Ces questions, intéressantes, demandent du temps et de l'attention
pour être traitées correctement.
· La quatrième partie rassemble les résultats des questions précédentes pour 
établir les fonctions globales permettant la réalisation de la simulation. Elle 
demande d'avoir bien compris les différents modèles et outils utilisés 
précédemment et favorisait donc les candidats ayant pris le temps de réfléchir 
sur l'ensemble du sujet.
· Enfin, on exploite une base de données pour enregistrer une partie des 
informations liées à des simulations. Il s'agit de la partie la moins bien 
écrite du sujet.
Les bases de données sont assez mal formées, très partielles pour les 
informations stockées et avec un formalisme éloigné des canons du domaine. Bien 
qu'il
n'y ait que trois questions, elles sont répétitives.
Ce sujet est progressif et intéressant (la courte partie 5 exceptée). Le 
contexte
utilisé est assez familier et la physique sous-jacente suffisamment simple pour 
ne pas
poser de problème à la plupart des candidats. Les données sont représentées par 
des
tableaux numpy car ils permettent l'addition et la multiplication par des 
scalaires.
Il est donc nécessaire de savoir manipuler ces opérations. Il s'agit, pour les 
quatre
premières parties, d'un bon entraînement accessible dès la fin de la première 
année.
Les notions d'ingénierie numérique n'apparaissent pas, mais des questions 
associées
à la représentation des nombres flottants sont présentes.

Indications
Partie I
1 Ne pas confondre la multiplication par un scalaire d'une liste Python ou d'un
tableau np.array.
10 Il peut être profitable de commencer par un schéma d'une situation 
quelconque,
sans hésiter à créer des positions proches ou éloignées les unes des autres. 
Puis dérouler l'algorithme en déplaçant les particules sur le schéma. Ne pas 
oublier de
mettre en forme le retour comme une liste de tableaux np.array.
12 Le terme « histogramme » est très mal choisi. L'énoncé souhaite que l'on 
trace la
fonction de densité de probabilité. Pour les cas N = 1 et N = 5, la réponse est
intuitive. Mais pour le cas N = 2, il faut multiplier des probabilités 
conditionnelles.
Partie II
17 Les tableaux np.array permettent l'utilisation de l'addition et de la 
multiplication de façon naturelle. La réponse attendue est très courte.
Partie III
20 Il s'agit bien d'une question en une dimension, ce qui simplifie largement 
l'étude.
Trois cas sont possibles en fonction de la valeur précédente de la vitesse.
21 Comme à la question précédente, l'étude est en une dimension. Les deux 
particules
ne se choqueront que si elles sont en train de se rapprocher, c'est-à-dire si 
leur
distance diminue en valeur absolue.
22 Une fois trouvé l'endroit où insérer l'événement dans le catalogue, la 
méthode
insert, dont l'énoncé donne l'aide en annexe, est incontournable.
23 La fonction demandée utilise les trois fonctions écrites précédemment. Les 
fonctions tr et tc ont un comportement similaire pour leur retour, notamment 
lorsqu'il n'y a pas d'événement associé. Ce retour est à tester avant la 
fabrication de
l'événement.
26 Il faut bien compter toutes les complexités dans le pire des cas où chaque 
particule
est capable de rencontrer toutes les autres. Le résultat peut être exprimé sous 
la
forme d'une somme d'entiers consécutifs qui se simplifie.
27 Ne surtout pas aller chercher un algorithme trop compliqué ou éloigné du 
cours.
Partie IV
29 Mettre à jour les positions pour toutes les particules. Ensuite, ne mettre à 
jour
que les vitesses des particules ayant interagi. Toutes les fonctions 
nécessaires ont
déjà été écrites.
30 L'invalidation des événements doit se faire à la main, selon un test 
d'appartenance
long à écrire, mais simple à concevoir.
31 On ne sait pas à l'avance combien d'itérations seront réalisées. À chaque 
itération,
il faut commencer par supprimer les événements invalides en fin de catalogue.
33 L'erreur numérique associée à la représentation des valeurs flottantes est 
surtout
proportionnelle à la valeur représentée.
Partie V
34 Il s'agit d'une requête d'agrégation selon un critère à définir.
35 Cette question est très proche de la précédente. La jointure n'est pas 
nécessaire.
36 La requête est plus longue à écrire, mais il suffit de traduire ce que dit 
l'énoncé.

I. Initialisation
Pour la seconde fois, le concours Centrale-Supélec utilise la syntaxe des 
définitions de fonctions appelée « annotations ». Elle rend le code plus 
explicite
en précisant les types des arguments et des retours des fonctions. Il est 
probable que cela devienne une habitude dans ce concours et c'est une bonne
idée dont pourraient s'inspirer les autres.
1 La ligne 9 du code proposé crée un tableau np.array d'une unique valeur, 
générée
aléatoirement entre 0 inclus et L exclu.
Il fallait bien lire la documentation de la fonction np.random.rand, qui
ne fait pas partie des fonctions à connaître.
Attention à ne pas confondre le comportement de la multiplication sur les
listes et sur les objets np.array. La multiplication d'une liste par un entier
provoque une concaténation multiple de cette liste, comme il est rappelé dans
l'annexe de l'énoncé, tandis que pour un np.array cela multiplie chaque
élément du tableau par l'entier ou le flottant multiplicateur. Ce détail aurait
pu être rappelé dans l'annexe.
2 L'argument c de la fonction possible peut être interprété à partir de l'appel 
à
la fonction à la ligne 10. Il s'agit d'un tableau np.array à une dimension, 
contenant
la position d'une nouvelle particule à placer parmi celles déjà présentes dans 
res.
3 La ligne 3 évacue les deux cas où le placement de la particule est impossible
car trop près des bords de l'espace disponible. Elle conduit la fonction 
possible à
renvoyer False s'il faut générer une nouvelle position.
4 Les lignes 4 et 5 testent pour chaque particule déjà présente si la nouvelle 
particule
à insérer est trop proche. Elles ont la même conclusion que la ligne 3.
5 La fonction possible teste la possibilité de placement de la nouvelle 
particule.
Elle renvoie True si c'est possible et False s'il faut générer une nouvelle 
position.
6 Le rejet réalisé à la ligne 3 peut être évité en générant une valeur comprise 
entre R
et L - R, en remplaçant la ligne 9 par
p = R + (L-2*R) * np.random.rand(1)
7 Dans la configuration proposée, chaque particule est espacée de 0,5 des deux
particules adjacentes ou du bord. Il n'y a donc pas de place pour positionner 
une
quatrième particule, et la boucle while devient une « boucle infinie ». Ainsi,
La suite de l'appel à placement1D ne termine pas.
8 Dans le cas où N  Nmax , on peut supposer que presqu'aucun échec de placement 
de particule ne survient. Le contenu de la boucle while est alors répété N fois
et contient des instructions de complexité constante ainsi qu'un appel à la 
fonction possible. Cette fonction est de complexité linéaire en le nombre 
d'éléments
déjà dans res. Puisque O(1 + 2 + 3 + · · · + N) = O(N2 ),
La complexité de la fonction placement est quadratique.
La somme des diamètres des particules à placer à la question 7 est pourtant
inférieure à la longueur totale du segment. Cela signifie que le nombre Nmax
est certainement inférieur au rapport L/(2 R). Si l'on souhaite éviter la boucle
infinie, il ne faut pas arriver pour autant à la situation où N - 1 particules
sont écartées l'une de l'autre et du bord d'une distance légèrement inférieure
à 2 R. À la limite de ce raisonnement, la configuration est

Alors

Nmax =

L+2R
4R

9 Pour recommencer à zéro le placement des particules dès qu'une nouvelle 
position
est impossible, il suffit d'ajouter ce comportement lorsque possible(p) vaut 
False.
res = []
while len(res) < N:
p = L * np.random.rand(1)
if possible(p): res.append(p)
else: res = []
return res
10 L'énoncé demande une fonction en trois étapes. La troisième est une étape
de déplacements successifs des particules, de l'espace [ 0 ;  ] vers l'espace [ 
0 ; L ].
Par exemple, ces déplacements peuvent être représentés par le schéma suivant :
1

3 5

L

6

2 4

6

2 4

6

2

4

1

6

2

4

1

6

2

4

1

3 5

6

2

4

1

3

placement aléatoire
remplacement de la particule 1
remplacement de la particule 2
remplacement de la particule 3
remplacement de la particule 4
remplacement de la particule 5
remplacement de la particule 6

6

1

2

3 5
3 5
3 5

4

1

5
3

5

Le placement rapide de N particules peut donc se faire ainsi :
def placement1Drapide(N, R, L):
# Étape 1 : calcul de l'espace libre final
l = L-2*R*N
# Étape 2 : placement aléatoire des N particules sur [0; l]
positions = l * np.random.rand(N)
# Étape 3 : déplacement des particules
for i in range(N):
for j in range(N): # Déplacement des particules à droite
if positions[j] > positions[i]:
positions[j] = positions[j]+2*R
# Transformation en particule réelle
positions[i] = positions[i]+R