Centrale Informatique commune MP 2016

Thème de l'épreuve Prévention des collisions aériennes
Principaux outils utilisés programmation, complexité, 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


Informatique
MP, PC. PSI. TSI

Calculatrices autorisées

2016

3 heures

Prévention des collisions aériennes

Ce problème s'intéresse à différents aspects relatifs à la sécurité aérienne et 
plus précisément au risque de
collision entre deux appareils. Dans la première partie nous abordons 
l'enregistrement des plans de vol des
différentes compagnies aériennes. La deuxième partie explique la manière 
d'attribuer à chaque vol un couloir
aérien répondant au mieux aux souhaits des compagnies aériennes. Enfin, la 
troisième partie s'intéresse à la
procédure de détection d'un risque de collision entre deux avions se croisant à 
des altitudes proches.

Une liste d'opérations et de fonctions qui peuvent être utilisées dans les 
fonctions Python figure en fin d'énoncé.
Les candidats peuvent coder toute fonction complémentaire qui leur semble 
utile. Ils devront dans ce cas préciser
le rôle de cette fonction, la signification de ses paramètres et la nature de 
la valeur renvoyée.

I Plan de vol

Afin d'éviter les collisions entre avions, les altitudes de vol en croisière 
sont normalisées. Dans la majorité des

pays, les avions volent a une altitude multiple de 1000 pieds (un pied vaut 
30,48 cm) au--dessus de la surface

isobare à 1013,25 hPa. L'espace aérien est ainsi découpé en tranches 
horizontales appelées niveaux de vol et

désignées par les lettres « FL » (flight level) suivies de l'altitude en 
centaines de pieds : « FL310 » désigne une

altitude de croisière de 31000 pieds au--dessus de la surface isobare de 
référence.

EUROCONTROL est l'organisation européenne chargée de la navigation aérienne, 
elle gère plusieurs dizaines de

milliers de vol par jour. Toute compagnie qui souhaite faire traverser le ciel 
européen à un de ses avions doit

soumettre à cet organisme un plan de vol comprenant un certain nombre 
d'informations : trajet, heure de départ,

niveau de vol souhaité, etc. Muni de ces informations, EUROCONTROL peut prévoir 
les secteurs aériens qui vont

être surchargés et prendre des mesures en conséquence pour les désengorger : 
retard au décollage, modification

de la route à suivre, etc.

Nous modélisons (de manière très simplifiée) les plans de vol gérés par 
EUROCONTROL sous la forme d'une base

de données comportant deux tables :

-- la table vol qui répertorie les plans de vol déposés par les compagnies 
aériennes ; elle contient les colonnes
. id_vol : numéro du vol (chaîne de caractères) ;

depart : code de l'aéroport de départ (chaine de caractères) ;

arrivee : code de l'aéroport d'arrivée (chaine de caractères) ;

jour : jour du vol (de type date, affiché au format aaaa--mm--j j) ;

heure : heure de décollage souhaitée (de type time, affiché au format hh:mi) ;

niveau : niveau de vol souhaité (entier).

id_vol depart arrivee jour heure niveau
AF1204 CDG FCO 2016--05--02 07:35 300
AF1205 FCO CDG 2016--05--02 10:25 300
AF1504 CDG FCO 2016--05--02 10:05 310
AF1505 FCO CDG 2016--05--02 13:00 310

Figure 1 Extrait de la table vol : vols de la compagnie Air France entre les 
aéroports Charles--de--
Gaule (Paris) et Léonard--de--Vinci à Fiumicino (Rome)

. id_aero : code de l'aéroport (chaine de caractères) ;
. ville : principale ville desservie (chaine de caractères) ;
. pays : pays dans lequel se situe l'aéroport (chaine de caractères).

2016--03-13 14:33:27

-- la table aeroport qui répertorie les aéroports européens ; elle contient les 
colonnes

id_aero ville pays
CD G Paris France
ORY Paris France
MRS Marseille France
FCO Rome Italie

Figure 2 Extrait de la table aeroport

Page 1/7

(cc)--

Les types SQL date et time permettent de mémoriser respectivement un jour du 
calendrier grégorien et une
heure du jour. Deux valeurs de type date ou de type time peuvent être comparées 
avec les opérateurs habituels
(=, <, <=, etc.). La comparaison s'effectue suivant l'ordre chronologique. Ces 
valeurs peuvent également être
comparées à une chaine de caractères correspondant a leur représentation 
externe ( 'aaaa--mm-- j j ' ou 'hh:mi ' ).

I .A = Écrire une requête SQL qui fournit le nombre de vols qui doivent 
décoller dans la journée du 2 mai 2016
avant midi.

I.B = Écrire une requête SQL qui fournit la liste des numéros de vols au départ 
d'un aéroport desservant
Paris le 2 mai 2016.

I. C = Que fait la requête suivante '?

SELECT id_vol
FROM vol
JOIN aeroport AS d DN d.id_aero = depart
JOIN aeroport AS a ON a.id_aero = arrivee
WHERE
d.pays = 'France' AND
a.pays = 'France' AND
jour = '2016--05--02'

I .D = Certains vols peuvent engendrer des conflits potentiels : c'est par 
exemple le cas lorsque deux avions

suivent un même trajet, en sens inverse, le même jour et à un même niveau. 
Écrire une requête SQL qui fournit
la liste des couples (ld1, ld2) des identifiants des vols dans cette situation.

II Allocation des niveaux de vol

Lors du dépôt d'un plan de vol, la compagnie aérienne doit préciser à quel 
niveau de vol elle souhaite faire
évoluer son avion lors de la phase de croisière. Ce niveau de vol souhaité, le 
RFL pour requested flight level,
correspond le plus souvent à l'altitude a laquelle la consommation de carburant 
sera minimale. Cette altitude
dépend du type d'avion, de sa charge, de la distance à parcourir, des 
conditions météorologiques, etc.
Cependant, du fait des similitudes entre les différents avions qui équipent les 
compagnies aériennes, certains
niveaux de vols sont très demandés ce qui engendre des conflits potentiels, 
deux avions risquant de se croiser
à des altitudes proches. Les contrôleurs aériens de la région concernée par un 
conflit doivent alors gérer le
croisement de ces deux avions.

Pour alléger le travail des contrôleurs et diminuer les risques, le système de 
régulation s'autorise a faire voler
un avion a un niveau difiérent de son RFL. Cependant, cela engendre 
généralement une augmentation de la

consommation de carburant. C'est pourquoi on limite le choix aux niveaux 
immédiatement supérieur et inférieur
au RFL.

Ce problème de régulation est modélisé par un graphe dans lequel chaque vol est 
représenté par trois sommets. Le
sommet 0 correspond à l'attribution du RFL, le sommet + au niveau supérieur et 
le sommet -- au niveau inférieur.
Chaque conflit potentiel entre deux vols sera représenté par une arête reliant 
les deux sommets concernés. Le
cout d'un conflit potentiel (plus ou moins important en fonction de sa durée, 
de la distance minimale entre les
avions, etc.) sera représenté par une valuation sur l'arête correspondante.

Figure 3 Exemple de conflits potentiels entre
trois vols

Dans l'exemple de la figure 3, faire voler les trois avions à leur RFL engendre 
un cout de régulation entre A et
B de 100 et un cout de régulation entre B et C de 400, soit un cout total de la 
régulation de 500 (il n'y a pas de

2016--03-13 14:33:27 Page 2/7 @@ BY--NC-SA

conflit entre A et C). Faire voler l'avion A a son RFL et les avions B et C 
au--dessus de leur RFL engendre un
conflit potentiel de cout 100 entre A et B et 150 entre A et C, soit un cout 
total de 250 (il n'y a plus de conflit
entre B et C).

On peut observer que cet exemple possède des solutions de cout nul, par exemple 
faire voler A et C a leur RFL
et B au--dessous de son RFL. Mais en général le nombre d'avions en vol est tel 
que des conflits potentiels sont
inévitables. Le but de la régulation est d'imposer des plans de vol qui 
réduisent le plus possible le cout total de
la résolution des conflits.

II.A = Implantation du problème

Chaque vol étant représenté par trois sommets, le graphe des conflits associé à 
n vols v0,v1, ..., v,,11 possède 3n
sommets que nous numéroterons de 0 à 371 -- 1. Nous conviendrons que pour 0 < 
[<: < n :

-- le sommet 31EUR représente le vol uk à son RFL ;

-- le sommet 3k --- 1 représente le vol 'Uk au--dessus de son RFL ;

-- le sommet 3k ---- 2 représente le vol Uk au--dessous de son RFL ;

Le cout de chaque conflit potentiel est stocké dans une liste de 3n listes de 
311 entiers (tableau 3n >< 3n) accessible
grâce a la variable globale conflit : si i et j désignent deux sommets du 
graphe, alors conflit [i] [j] est égal
au cout du conflit potentiel (s'il existe) entre les plans de vol représentés 
par les sommets i et j . S'il n'y a pas de
conflit entre ces deux sommets, conflit [i] [j] vaut 0. On convient que conflit 
[i] [j] vaut 0 si les sommets
i et j correspondent au même vol (figure 4).

On notera que pour tout couple de sommets (i, j), conflit [i] [j] et conflit 
[j] [i], représentent un seul et

même conflit et donc conflit [i] [j] == conflit [j] [i].
conflit = [ [ O, 0, 0, 100, 100, 0, 0, 150, O],
[ O, 0, O, O, O, 50, O, O, O],
[ O, 0, O, O, 200, O, 0, 300, 50],
[100, O, O, 0, O, 0, 400, O, O],
[100, 0, 200, O, O, 0, 200, 0, 100],
[ O, 50, O, O, O, O, O, O, O],
[ O, 0, O, 400, 200, O, 0, O, O],
[150, O, 300, O, O, O, O, O, O],
[ o, o, 50, o, 100, o, o, o, o] ]

Figure 4 Tableau des couts des conflits associé au graphe représenté figure 3

II.A.1) Écrire en Python une fonction nb_conflits() sans paramètre qui renvoie 
le nombre de conflits po--
tentiels, c'est--à--dire le nombre d'arêtes de valuation non nulle du graphe.

II.A.2) Exprimer en fonction de n la complexité de cette fonction.

II. B = Régulation

Pour un vol vk on appelle niveau relatif l'entier T'k valant 0, 1 ou 2 tel que :

-- rk : 0 représente le vol vk a son RFL ;

-- 7'k : 1 représente le vol Uk au--dessus de son RFL ;

-- 7'k : 2 représente le vol "U,, au--dessous son RFL.

On appelle régulation la liste (r0,r1, ..., rn_1). Par exemple, la régulation 
(0,0, ..., 0) représente la situation dans
laquelle chaque avion se voit attribuer son RFL. Une régulation sera implantée 
en Python par une liste d'entiers.

Il pourra être utile d'observer que les sommets du graphe des conflits choisis 
par la régulation r portent les
numéros 31% + rk pour 0 EUR [EUR < n. On remarque également qu'au sommet s du 
graphe correspond le niveau
relatif rk : smod3 et le vol Uk tel que k : Ls/3l.

II.B.1) Écrire en Python une fonction nb_vol_par_niveau_relatif (regulation) 
qui prend en paramètre
une régulation (liste de n entiers) et qui renvoie une liste de 3 entiers [a, b 
, c] dans laquelle a est le nombre de
vols à leurs niveaux RFL, b le nombre de vols au--dessus de leurs niveaux RFL 
et c le nombre de vols au--dessous
de leurs niveaux RFL.

II.B.2) Cout d'une régulation
On appelle cout d'une régulation la somme des couts des conflits potentiels que 
cette régulation engendre.

(1) Écrire en Python une fonction cout_regulation (regulation) qui prend en 
paramètre une liste représentant
une régulation et qui renvoie le cout de celle--ci.

b) Évaluer en fonction de n, la complexité de cette fonction.

c) Déduire de la question a) une fonction cout_RFL() qui renvoie le cout de la 
régulation pour laquelle chaque
avion vole a son RFL.

II.B.3) Combien existe--t--il de régulations possibles pour n vols '?
Est--il envisageable de calculer les couts de toutes les régulations possibles 
pour trouver celle de cout minimal?

2016--03-13 14:33:27 Page 3/7 @@ BY--NC-SA

II.C -- L'algorithme Minimal

On définit le cout d'un sommet comme la somme des couts des conflits potentiels 
dans lesquels ce sommet

intervient. Par exemple, le cout du sommet correspondant au niveau RFL de 
l'avion A dans le graphe de la
figure 3 est égal à 100 + 100 + 150 = 350.

L'algorithme Minimal consiste à sélectionner le sommet du graphe de cout 
minimal ; une fois ce dernier trouvé,
les deux autres niveaux possibles de ce vol sont supprimés du graphe et on 
recommence avec ce nouveau graphe
jusqu'à avoir attribué un niveau a chaque vol.

Dans la pratique, plutôt que de supprimer effectivement des sommets du graphe, 
on utilise une liste etat_sommet
de 3n entiers tels que :

-- etat_sommet [s] vaut 0 lorsque le sommet s a été supprimé du graphe ;

-- etat_sommet [5] vaut 1 lorsque le sommet s a été choisi dans la régulation ;

-- etat_sommet [5] vaut 2 dans les autres cas.

II.C.1)

a) Écrire en Python une fonction cout_du_sommet(s, etat_sommet) qui prend en 
paramètres un numéro de
sommet s (n'ayant pas été supprimé) ainsi que la liste etat_sommet et qui 
renvoie le cout du sommet s dans le
graphe défini par la variable globale conflit et le paramètre etat_sommet.

b) Exprimer en fonction de n la complexité de la fonction cout_du_sommet.
II.C.2)

a) Ecrire en Python une fonction sommet_de_cout_min(etat_sommet) qui, parmi les 
sommets qui n'ont pas
encore été choisis ou supprimés, renvoie le numéro du sommet de cout minimal.

b) Exprimer en fonction de n la complexité de la fonction sommet_de_cout_min.
II.C.3)

a ) En déduire une fonction minimal () qui renvoie la régulation résultant de 
l'application de l'algorithme Mini--
mal.

b ) Quelle est sa complexité '? Commenter.

II.D * Recuit simulé

L'algorithme de recuit simulé part d'une régulation initiale quelconque (par 
exemple la régulation pour laquelle
chacun des avions vole a son RFL) et d'une valeur positive T choisie 
empiriquement. Il réalise un nombre fini
d'étapes se déroulant ainsi :
-- un vol uk est tiré au hasard ;
-- on modifie rk en tirant au hasard parmi les deux autres valeurs possibles ;

c si cette modification diminue le cout de la régulation, cette modification 
est conservée ;

0 sinon, cette modification n'est conservée qu'avec une probabilité p : 
exp(--Ac/T), où Ac est l'augmen--

tation de cout liée à la modification de la régulation ;

-- le paramètre T est diminué d'une certaine quantité.

Écrire en Python une fonction recuit (regulation) qui modifie la liste 
regulation passée en paramètre en
appliquant l'algorithme du recuit simulé. On fera débuter l'algorithme avec la 
valeur T = 1000 et à chaque
étape la valeur de T sera diminuée de 1%. L'algorithme se terminera lorsque T < 
1.

Remarque. Dans la pratique, l'algorithme de recuit simulé est appliqué 
plusieurs fois de suite en partant à
chaque fois de la régulation obtenue à l'étape précédente, jusqu'à ne plus 
trouver d'amélioration notable.

III Système d'alerte de trafic et d'évitement de collision

L'optimisation globale des niveaux de vol d'un système d'avions étudiée 
précédemment est complétée par une
surveillance locale dans l'objectif de maintenir à tout instant une séparation 
suffisante avec tout autre avion.
La règlementation actuelle impose aux avions de ligne d'être équipé d'un 
système embarqué d'évitement de
collision en vol, ou TCAS pour trafic collision avoidance system.

Nous nous intéressons au fonctionnement du T CAS vu d'un avion particulier que 
nous appelons avion propre.
Les avions qui volent a proximité de l'avion propre sont qualifiés d'intrus.

Le système TCAS surveille l'environnement autour de l'avion propre (typiquement 
dans un rayon d'un soixan--
taine de kilomètres) pour identifier les intrus et déterminer s'ils présentent 
un risque de collision. Pour cela, le
TCAS évalue, pour chaque intrus, le point où sa distance avec l'avion propre 
sera minimale. Ce point est appelé
CPA, pour closest point of approach. Le fonctionnement global (simplifié) du 
système TCAS est décrit par la
fonction TCAS donnée figure 5.

Cette fonction maintient une liste des CPA des avions situés dans son périmètre 
de surveillance (variable CPAS).
Cette liste est limitée à un nombre restreint d'intrus (intrus_max) dont 
l'instant du CPA est proche (dans
moins de suivi_max) de façon à garantir la détection et le traitement d'un 
éventuel danger dans un temps
suffisamment court.

2016--03-13 14:33:27 Page 4/7 ("à BY--NC-SA

def TCAS():
"""Fonction principale du système TCAS."""
intrus_max = 30 # nombre maximum d'avions suivis
suivi_max = 100 # délai maximum pour le CPA (en secondes)
CPAS = [] # liste des CPA des avions suivis
while (TCAS_actif())z
intrus = acquerir_intrus()
enregistrer_CPA(inttus, CPAS, intrus_max, suivi_max)
traiter_CPAs(CPAs)

Figure 5

La fonction TCAS_actif renvoie la position de l'interrupteur principal du 
système.

La fonction acquerir_intrus détermine la position et la vitesse d'un intrus 
particulier. A chaque appel, elle
s'intéresse à un avion différent dans le périmètre de surveillance du TCAS. 
Lorsque tous les intrus ont été
examinés, l'appel suivant revient au premier intrus qui est toujours dans le 
périmètre.

La fonction enregistrer_CPA intègre dans la liste CPA de nouvelles informations 
telles que fournies par la
fonction acquerir_intrus.

Enfin la fonction traiter_CPAs examine les CPA des intrus les plus dangereux 
pour décider si l'un d'eux
présente un risque de collision. Si c'est le cas, cette fonction détermine la 
manoeuvre a effectuer (monter ou
descendre) en coordination avec le système TCAS de l'intrus concerné et génère 
une alarme et une consigne a
destination du pilote.

III.A = Acquisition et stockage des données

Chaque avion est équipé d'un émetteur radio spécialisé, appelé transpondeur, 
qui fournit automatiquement, en
réponse à l'interrogation d'une station au sol ou d'un autre avion, des 
informations sur l'avion dans lequel il
est installé. La fonction acquerir_intrus utilise les données du système de 
navigation de l'avion propre, les
données fournies par le transpondeur de l'intrus, le relèvement de son émission 
et les informations fournies par
le système de contrôle aérien au sol.

III.A.1) Les transpondeurs utilisent tous la même fréquence radio. Afin 
d'éviter la saturation de cette fréquence,
en particulier dans les zones à fort trafic, chaque émission ne doit pas durer 
plus de 128 ps. Le débit binaire
utilisé est de 106 bits par seconde ; chaque message commence par une marque de 
début de 6 bits et se termine
par 4 bits de contrôle et une marque de fin de 6 bits.

ddddddææoe...rflæoe eeee ffffff

__ _,-- _,_/ __
début données contrôle fin

Déterminer le nombre maximum de bits de données dans une émission de 
transpondeur.

III.A.2) Le système TCAS souhaite récupérer l'altitude et la vitesse 
ascensionnelle de chaque intrus en inter--
rogeant son transpondeur. La réponse du transpondeur contient systématiquement 
un numéro d'identification
de l'avion sur 24 bits. Les autres informations sont des entiers codés en 
binaire qui peuvent varier dans les
intervalles suivants :

-- altitude de 2000 à 66 000 pieds ;

-- vitesse ascensionnelle de --5000 a 5000 pieds par minute.

La taille d'un message de trans ondeur est--elle suffisante our obtenir ces 
informations en une seule fois '?
o p p

III.A.3) Après avoir récupéré les informations nécessaires, la fonction 
acquerir_intrus calcule la position et
la vitesse de l'intrus par rapport à l'avion propre et renvoie une liste de 
huit nombres :

{id, x, y, z, vx, vy, V2, 170]

-- id est le numéro d'identification de l'intrus ;

-- x, y, 2 les coordonnées (en mètres) de l'intrus dans un repère orthonormé 
330 lié à l'avion propre ;
-- vx, vy, vz la vitesse (en mètres par seconde) de l'intrus dans ce même 
repère ;

-- tO le moment de la mesure (en secondes depuis un instant de référence).

À des fins d'analyse une fois l'avion revenu au sol, la fonction 
acquerir_intrus conserve chaque résultat obtenu.
Chaque nombre est stocké sur 4 octets. En supposant que cette fonction est 
appelé au maximum 100 fois par

seconde, quel est le volume de mémoire nécessaire pour conserver les données de 
100 heures de fonctionnement
du TCAS '?

Ce volume de stockage représente--t--il une contrainte technique forte ?

2016--03-13 14:33:27 Page 5/7 @@ BY--NC-SA

III.B * Estimation du CPA

Le but de cette sous--partie III.B est d'estimer le CPA d'un avion intrus a 
partir des informations fournies par
la fonction acquerir_intrus. Pour cela on suppose que l'avion propre et l'avion 
intrus poursuivent leur route
sans changer de direction ni de vitesse. Vu les distances entre les deux 
avions, on néglige la courbure de la Terre,
on considère donc qu'ils suivent un mouvement rectiligne uniforme.

III.B.1) On se place dans le repère orthonormé 530 utilisé par la fonction 
acquerir_inttus. On note 0 l'origine
de ce repère (qui correspond à la position de l'avion propre), G(t) la position 
de l'intrus a l'instant t et V sa
vitesse dans 530 (supposée constante). La fonction acquerir_intrus fournit 
ainsi les coordonnées dans 530 des
vecteurs OE(tO) et V pour l'intrus id.

Exprimer le vecteur OG(t) en fonction des informations fournies par la fonction 
acquerir_intrus.

III.B.2) Déterminer l'expression du temps tc qui correspond a l'instant où les 
deux avions sont le plus proches
(instant du CPA).

III.B.3) Montrer qu'il n'y a pas de risque de collision si le produit scalaire 
OE(tO) - V est positif.

III.B.4) Écrire en Python une fonction calculer_CPA(intrus) qui prend en 
paramètre une liste de la forme
de celle produite par la fonction acquerir_intrus et qui renvoie :
-- None s'il n'y pas de risque de collision ;
-- ou une liste de 3 nombre [tCPA, dCPA, zCPA] où

. tCPA est l'instant prévu pour le CPA (tc) ;

. dCPA la distance en mètres entre les deux avions au moment du CPA ;

. zCPA la différence d'altitude en pieds entre les deux avions au moment du CPA 
(négative si l'intrus est

plus bas que l'avion propre).

Pour répondre a cette question, on considère que l'avion propre vole 
horizontalement (vol de croisière) et que
l'axe 5 du repère 580 est orienté verticalement vers le haut.

III.C * Mise à jour de la liste des CPA

Chaque élément de la liste CPAS (figure 5) est une liste de 4 nombres [id, 
tCPA, dCPA, zCPA] où id est
l'identifiant de l'intrus et les autres éléments ont la signification précisée 
a la question III.B.4. Un exemple de
liste CPAS est donné figure 6. Ainsi, CPAS [2] [3] indique la séparation 
verticale (800 pieds) au CPA pour le
troisième avion suivi, dont l'identifiant est 32675398 et dont le CPA aura lieu 
a l'instant 1462190455 (nombre
de secondes depuis l'instant de référence).

CPAS = [ [ 11305708, 1462190400, 2450, --1000] ,
[ 12416823, 1462190412, 2500, 500] ,
[ 32675398 , 1462190455 , 2000 , 800] ,
[ 18743283 , 1462190463 , 2100 , --200] ]

Figure 6 Exemple de liste de CPA

La fonction traiter_CPA attend une liste triée par ordre chronologique. La 
fonction enregistrer_CPA s'assurera

donc que la liste CPAS qu'elle produit est triée par ordre croissant des tCPA 
(CPAS [i--1] [1] <= CPAS [i] [1]

pour tout i compris entre 1 et len(CPAs)--1). La fonction traiter_CPAs ne 
modifie pas l'ordre de la liste CPAS,

enregistrer_CPA peut donc supposer que la liste qu'elle reçoit en paramètre est 
déjà triée.

III.C.1) Écrire en Python une fonction mettre_a_jour_CPAs(CPAs, id, nv_CPA, 
intrus_max, suivi_max)

qui prend en paramètre

-- CPAS : la liste actuelle des CPA au format décrit ci--dessus ;

-- id : l'identifiant d'un intrus ;

-- nv_CPA: les caractéristiques du CPA de l'intrus telles que renvoyées par la 
fonction calcu1_CPA (peut
éventuellement valoir None) ;

-- intrus_max : un entier indiquant le nombre maximum d'intrus à suivre ;

-- suivi_max : un entier donnant le délai maximum (en secondes) avant un CPA 
pour s'intéresser à l'intrus
correspondant.

Cette fonction modifie la liste CPAS en appliquant les règles suivantes :

-- si l'avion id est déjà suivi et ne présente plus de risque de collision, ou 
si son CPA est prévu dans plus de
suivi_max secondes, il est supprimé de la liste ;

-- si l'avion id est déjà suivi et que son CPA est prévu dans moins de 
suivi_max secondes, la ligne correspon--
dante est mise a jour avec les nouvelles informations sur le CPA ;

-- si l'avion id n'est pas suivi et que son CPA est prévu dans moins de 
suivi_max secondes alors,
0 s'il reste de la place dans la liste il est ajouté à la fin,
0 si la liste est pleine (elle contient déjà intrus_max intrus) et si le tCPA 
du nouvel intrus est inférieur au

tCPA du dernier de la liste alors le nouvel intrus remplace le dernier intrus 
de la liste.

2016--03-13 14:33:27 Page 6/7 ("à BY--NC-SA

La fonction mettre_a_jour_CPAs renvoie :
-- None si l'avion id a été supprimé ou n'a pas été ajouté ;
-- ou un entier indiquant l'indice de la ligne de CPAS qui a été modifiée ou 
ajoutée.

III.C.2) Suite à un appel a la fonction mettre_a_j our_CPAs, il se peut que la 
liste CPAS ne soit plus triée par
ordre croissant des tCPA.

Écrire en Python une fonction replacer(ligne, CPAS) qui modifie la liste CPAS 
de façon à ce qu'elle soit
ordonnée par tCPA croissant, en sachant que la seule ligne qui n'est 
éventuellement pas a sa place est celle
d'indice ligne.

Autrement dit, la fonction replacer(ligne , CPAS) doit remettre la ligne CPAS 
[ligne] a sa place dans l'ordre
des tCPA croissants.

III.C.3) Écrire en Python la fonction enregistrer_CPA utilisée par la fonction 
TCAS (figure 5).

III.D * Évaluation des paramètres générauæ du système TCAS

III.D.1) Le système TCAS est capable de détecter un intrus a une distance 
d'environ 60 km. Un avion de ligne
vole typiquement a 900 km-hÿ'. Quel temps va--t--il s'écouler entre la première 
détection d'un intrus et son CPA
si celui--ci se situe a proximité de l'avion propre '?

Comparer ce résultat à la valeur standard du paramètre suivi_max (100 s) et 
commenter.

III.D.2) Afin de garantir le confort des passagers, les pilotes limitent 
généralement la vitesse ascensionnelle de
leur avion à 1500 pieds par minute.

Si deux avions volent l'un vers l'autre à la même altitude, combien de temps 
avant leur CPA doivent-ils com--
mencer à manoeuvrer afin de se croiser avec une différence d'altitude d'au 
moins 500 pieds '?

III.D.3) Le système TCAS émet une alarme dans le cockpit demandant au pilote de 
monter ou descendre s'il
détecte un intrus avec un zCPA inférieur à 500 pieds et un tCPA dans moins de 
25 secondes. Commenter cette
valeur.

La consigne de monter ou descendre est élaborée après concertation entre les 
systèmes TCAS des deux avions
concernés afin d'éviter de conseiller la même manoeuvre aux deux pilotes.

III.D.4) Les spécifications du système TCAS prévoient que la position de chaque 
intrus doit être vérifiée au
moins une fois par seconde. Elles limitent d'autre part le nombre d'intrus 
suivis à 30. En déduire le temps
maximum dont dispose la fonction TCAS pour exécuter une fois sa boucle.

III.D.5) Quel est le facteur limitant la vitesse d'exécution de la fonction 
TCAS ? En déduire un ordre de grandeur
du temps minimum d'exécution d'une boucle. Est--il compatible avec les 
spécifications du système TCAS '?

Opérations et fonctions Python disponibles

Fonctions

-- exp(x) calcule l'exponentielle du nombre oe

-- randint (n) (n entier) renvoie un entier aléatoire compris entre 0 et n--1 
inclus

-- random() renvoie un nombre flottant tiré aléatoirement dans {O., 1{ suivant 
une distribution uniforme
-- sqrt (x) calcule la racine carrée du nombre 95

-- time () renvoie l'heure sous la forme d'un nombre de secondes depuis un 
instant de référence

Opérations sur les listes

-- u + v construit une liste constituée de la concaténation des listes u et v :
E1, 2] + [3, 4, 5] --> [1, 2, 3, 4, 5]

-- n * u construit une liste constitué de la liste u concaténée n fois avec 
elle--même :
3 *[1, 2] --> [1, 2, 1, 2, 1, 2]

-- u. append(e) ajoute l'élément e a la fin de la liste u (équivalent à u

-- del(u [i]) supprime de la liste 11 son élément d'indice i

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

-- 1en(u) donne le nombre d'éléments de la liste u :
len([1, 2, 3]) --> 3,1en([[1,2], [3,4]]) --> 2

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

u + [e])

oooFlNooo

2016--03-13 14:33:27 Page 7/7 GQ BY--NC-SA

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



Centrale Informatique commune MP 2016 --
Corrigé
Ce corrigé est proposé par Cyril Ravat (Professeur en CPGE) ; il a été relu
par Jean-Julien Fleck (Professeur en CPGE) et Benjamin Monmege 
(Enseignantchercheur à l'université).

Ce sujet d'informatique s'intéresse aux méthodes de prévention des collisions
aériennes. Il est découpé en trois parties indépendantes de longueurs très 
différentes.
· La première partie traite des plans de vol et de la gestion d'une base de 
données
contenant les indications de chaque vol. Toutes les questions portent sur les
bases de données ; leur difficulté est progressive. Cette partie donne un bon
aperçu des connaissances attendues dans ce domaine.
· La deuxième partie aborde le choix des niveaux de vol. Elle introduit pour
cela un graphe pondéré non orienté. Cette notion n'est pas explicitement au
programme, car elle ne figure que dans les activités facultatives de deuxième
année ; néanmoins, tout le vocabulaire associé (arête, sommet, valuation) est
rappelé par l'énoncé et la traduction du graphe sous forme de matrice 
d'adjacence est entièrement donnée. Remarquons cependant que les candidats en
MP option informatique avaient un net avantage sur les autres, puisque cette
notion est au programme de l'option.
L'objet de cette partie est l'écriture de fonctions élémentaires codant un 
algorithme de minimisation d'un coût global. Les questions de programmation
demandent du soin, notamment quand elles utilisent des listes de listes, mais ne
posent pas de difficulté conceptuelle majeure. Pour chaque fonction, l'énoncé
demande de calculer sa complexité. La partie s'achève avec l'algorithme du 
recuit simulé (un classique de l'optimisation), qui est entièrement décrit et 
qu'il
faut convertir en fonctions dans le langage Python.
· La troisième partie décrit les grandes lignes du système de prévention 
automatique de collisions TCAS. Cette partie est dans l'ensemble beaucoup moins
claire que la précédente. Le système est composé d'un certain nombre de boîtes
noires dont on ne comprend pas toujours l'intérêt. Les questions de la première
sous-partie, reliées à la représentation des nombres, sont plutôt simples. La
deuxième sous-partie consiste à calculer le temps avant collision et commence
par deux questions de mécanique élémentaire. La troisième sous-partie contient
à nouveau de la programmation Python. La dernière sous-partie, beaucoup
moins intéressante que le reste de l'épreuve, est faite de questions 
qualitatives,
simplistes ou mal posées, sur le temps d'exécution de l'algorithme global. On
ne sait pas trop ce qui est évalué dans ces questions.
Ce problème présente des questions d'intérêt inégal. De nombreuses questions de
programmation sont cependant intéressantes, notamment dans la deuxième partie.
Notons qu'il ne fait appel qu'au programme de première année et que les 
techniques
d'ingénierie numérique ne sont pas abordées.

Indications
Partie I
I.A La fonction comptant un nombre d'enregistrements est COUNT(*).
I.B La sélection exploite des informations présentes dans deux tables : il faut
réaliser une jointure.
I.D Il faut joindre deux fois la table vol : il est nécessaire de la renommer 
pour
distinguer chaque occurrence (on peut s'inspirer de la question précédente).
Partie II
II.A.1 Il s'agit d'une double itération, donc de deux boucles imbriquées. 
Attention
à ne pas tout compter en double...
II.B.2 La structure de l'algorithme est proche de celle de la question II.A.1, 
mais
avec des compteurs variant sur le nombre de vols. Penser à utiliser les 
indications de l'énoncé sur les liens entre s, rk et k.
II.C.1 Rechercher les sommets non supprimés et ajouter le coût correspondant. 
Que
leur état soit égal à 1 ou à 2 n'intervient pas.
II.C.2 Il s'agit d'une recherche de minimum, algorithme simple à connaître. 
Penser
à ne parcourir que les sommets ni supprimés ni déjà choisis.
II.C.3 Il faut se demander si l'on sait combien d'itérations l'algorithme doit 
effectuer.
La boucle doit être précédée de l'initialisation des variables (liste des états 
et
des régulations) ; son contenu est très bien décrit dans l'énoncé.
II.D La modification aléatoire de rk peut être longue à écrire : penser à une 
permutation circulaire d'une ou deux cases sur un total de trois peut permettre
d'obtenir un code plus simple.
Partie III
III.B.1 Le référentiel d'étude R0 est défini à la question III.A.3. Il est lié 
à l'avion
propre, qui y est donc immobile.
--
III.B.2 tc est l'instant où la norme de OG est minimale.
III.C.1 L'ensemble de l'algorithme est donné dans l'énoncé. Il faut commencer 
par
chercher l'avion intrus dans la liste et effectuer les traitements prévus 
lorsqu'on le trouve. Si chaque possibilité de traitement se conclue par un 
return,
la sortie de la boucle de recherche correspond à un avion absent de la liste.
III.C.2 Supprimer l'avion à traiter de la liste avant de la parcourir permet de 
simplifier et de systématiser le traitement.
III.C.3 Cette question ne présente aucune difficulté, si ce n'est de relire 
l'introduction
de cette partie (pages 4 et 5) et d'avoir bien compris ce que réalisent les
différentes fonctions écrites aux questions précédentes.

I. Plan de vol
I.A L'énoncé spécifie que l'on peut comparer une date et une heure avec une 
chaîne
de caractères équivalente. De plus, l'opérateur d'agrégation permettant de 
compter
le nombre d'enregistrements est COUNT(*). On peut ainsi écrire :
SELECT COUNT(*) FROM vol WHERE jour='2016-05-02' AND heure<'12:00'
I.B Les informations à utiliser sont contenues dans deux tables : on doit 
afficher
des identifiants de vol id_vol contenus dans la table vol et faire la sélection 
en
particulier sur ville, dans la table aeroport. Il faut donc réaliser une 
jointure, c'està-dire l'assemblage des lignes correspondantes dans les deux 
tables. La condition de
jointure est par conséquent depart=id_aero. On obtient :
SELECT id_vol FROM vol JOIN aeroport ON depart=id_aero
WHERE ville='Paris' AND jour='2016-05-02'
Dès que l'on utilise deux tables dans la même requête, il y a un risque de
nom identique pour deux colonnes. Ce n'est pas le cas ici, mais si les colonnes 
id_vol et id_aero s'appelaient toutes les deux id, alors le système
ne pourrait pas comprendre la requête si on ne précise pas de quel id il
s'agit. Il faudrait alors écrire respectivement vol.id et aeroport.id. Il est
par ailleurs possible d'écrire ici vol.id_vol, mais cela n'apporte rien.
I.C Cette requête réalise une double jointure entre la table vol et deux fois 
la table
aeroport, afin d'associer à chaque vol la ville et le pays des deux aéroports 
concernés.
Elle sélectionne ensuite les vols du 2 mai 2016 allant d'un aéroport français à 
un autre
aéroport français.
Cette requête liste les vols nationaux français du 2 mai 2016.
I.D Il est nécessaire d'utiliser deux fois la table vol. Comme dans l'exemple 
donné
à la question précédente, il faut renommer les tables. Les conditions de 
jointure et
de sélection sont ici exceptionnellement proches, au point que plusieurs 
solutions
sont possibles en déplaçant les conditions du ON vers le WHERE ou inversement. 
Par
exemple, en considérant que l'on joint les tables pour les vols ayant lieu le 
même jour
au même niveau, puis que l'on sélectionne les vols ayant les mêmes points de 
départ
et d'arrivée, on a
SELECT v1.id_vol AS id1, v2.id_vol AS id2
FROM vol AS v1 JOIN vol AS v2
ON v1.jour=v2.jour AND v1.niveau=v2.niveau
WHERE v1.depart=v2.arrivee AND v1.arrivee=v2.depart
AND v1.id_vol 0:
resultat = resultat
return resultat

N vaut 3n
Résultat initialisé à zéro
Autre possibilité : range(1,N)
Autre possibilité : range(i)
+ 1

Une autre possibilité est de parcourir l'ensemble de la grille, i et j allant
tous deux de 0 à N - 1. Bien sûr, le résultat sera le double de celui recherché,
il faudra donc penser à le diviser par deux. Une telle réponse ne devrait
normalement pas être pénalisée, car la complexité reste du même ordre que
celle de la fonction écrite ci-dessus.
Si on préfère rester sur le parcours d'une moitié de tableau, autant faire
attention à ne pas prendre en compte la diagonale : c'est pour cela que j
commence à i + 1 (ou s'arrête à i - 1 dans la variante). La diagonale ne
contient cependant que des zéros, les comptabiliser ne change pas le résultat.
II.A.2 Avant la première boucle, il y a deux opérations de complexité 
indépendante de la taille de conflit. À l'intérieur des deux boucles 
entièrement imbriquées, il n'y a aussi que des opérations de complexité 
constante. Le calcul de complexité revient donc à un calcul de nombre 
d'itérations de la deuxième boucle.
Lorsque i vaut 0, elle est exécutée N - 1 fois. Lorsque i vaut 1, elle est 
exécutée
N - 2 fois, et ainsi de suite : le nombre total d'opérations à effectuer peut 
s'écrire
k1 + k2 ((N - 1) + (N - 2) + · · · + 1 + 0) = k1 + k2 (N - 1)(N - 2)/2. Comme N 
= 3 n,
La complexité de la fonction nb_conflits est en O(n2 ).
On attend pour un calcul de complexité, et plus particulièrement pour le
premier calcul de ce genre dans une épreuve, qu'il soit précisément justifié. En
particulier, il ne faut pas se contenter de « Il y a deux boucles donc O(n2 ). 
» Le
calcul faisant apparaître la somme et sa transformation en produit doit être
présent. On pourra en revanche aller plus vite sur les justifications suivantes.
II.B.1 Pour réaliser cette fonction, on peut utiliser une liste abc, mise à 
jour à
chaque valeur r de regulation : si r vaut 0, il faut incrémenter abc[0], si r 
vaut 1,
il faut incrémenter abc[1], si r vaut 2, il faut incrémenter abc[2]. On obtient