Centrale Informatique MP-PC-PSI 2016

Thème de l'épreuve Prévention des collisions aériennes
Principaux outils utilisés programmation, complexité, bases de données
Mots clefs vol, sql, graphe, régulation, optimisation, minimum, recuit simulé, système TCAS, collision aérienne

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 PSI 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