Epreuve d'Informatique et Modélisation de Systèmes Physiques

L'usage de calculatrices est interdit.

AVERTISSEMENT

CONSIGNES:

• Composer lisiblement sur les copies avec un stylo à bille à encre foncée : bleue ou noire.
• L'usage de stylo à friction, stylo plume, stylo feutre, liquide de correction et dérouleur de ruban correcteur est strictement interdit. Les surveillants et surveillantes se réservent le droit de les confisquer.
• Remplir sur chaque copie en MAJUSCULES toutes vos informations d'identification : nom, prénom, numéro inscription, date de naissance, le libellé du concours, le libellé de l'épreuve et la session.
• Une feuille, dont l'entête n'a pas été intégralement renseigné, ne sera pas prise en compte.
• Il est interdit aux candidats de signer leur composition ou d'y mettre un signe quelconque pouvant indiquer sa provenance. La présence d'une information d'identification en dehors du cartouche donnera lieu à un point de pénalité et la page concernée pourra être soustraite de la correction.
  " Les applications numériques sont attendues avec un (voire deux) chiffres significatifs. Le jury prendra pleinement en compte le fait que l'épreuve est sans calculatrice et de ce fait sera tout à fait tolérant sur la précision des résultats numériques, l'essentiel étant l'ordre de grandeur ".

Présentation de la problématique AUTOUR DE LA GÉOLOCALISATION PAR SATELLITES

1. Fonctionnement

1. une constellation de satellites, suffisamment nombreux pour que plusieurs d'entre eux soient en permanence visibles en tout point de la surface de la Terre et qui émettent en permanence des signaux radio contenant des repères temporels et des informations sur leurs localisations;
2. des stations de contrôle au sol, qui suivent les satellites, identifient les erreurs dans les messages qu'ils envoient (sur les positions, vitesses et temps), les corrigent et leur envoient des rectificatifs;
3. un récepteur par utilisateur, qui capte les signaux des satellites et les utilise pour se localiser.

Figure 1 - Constituants d'un GNSS et informations transmises

Figure 2 - Exemple de trilatération dans le plan

2. Travail demandé

1. la modélisation des satellites : il s'agit de prévoir leurs mouvements et de modéliser la propagation des signaux en direction de la Terre;
2. la simulation du décodage des signaux, qui présente une partie du traitement du signal effectué par le récepteur pour identifier les satellites émetteurs ainsi que la distance le séparant de chacun d'eux ;
3. la simulation d'une recherche d'itinéraires qui est une application courante des GNSS, avec la recherche d'un plus court chemin et la mise en œuvre de statistiques sur des temps de trajet.

Première partie MODÉLISATION DES SATELLITES

A. Mouvements et trajectoires

Figure 3 - Repérage en coordonnées polaires dans le plan du mouvement

1. Sans démonstration, écrire l'expression de la force vectorielle subie par le satellite et calculer la valeur numérique de sa norme. Toujours sans démonstration, donner l'expression du champ de gravitation créé par la Terre au point en fonction de et . On pourra utiliser l'aide numérique suivante : .
2. En considérant la Terre comme sphérique et de masse volumique uniforme, justifier le fait que son champ de gravitation en un point extérieur à la Terre est le même que celui d'un point matériel situé en son centre affecté de toute la masse de la Terre.
3. En utilisant la deuxième loi de Newton, justifier :

• la relation , où est la vitesse du satellite;
• que le mouvement circulaire est nécessairement uniforme.

4. En utilisant la question précédente, retrouver la troisième loi de Kepler dans le cas circulaire.
5. Calculer la période de révolution des satellites GPS en secondes (rappel : ). Comparer cette valeur avec la période d'un satellite géostationnaire.
   On donne ci-dessous la projection sur la surface terrestre de la trajectoire d'un satellite GPS ainsi que quelques valeurs de latitudes et longitudes.

Figure 4 - Projection de la trajectoire d'un satellite gps

6. Evaluer approximativement, à près, l'inclinaison du plan de l'orbite de ce satellite par rapport au plan équatorial.
7. On admet que le sens de la révolution du satellite est le même que celui de la rotation propre de la Terre. Sur la figure 4, ce sens est-il vers la droite ou vers la gauche (une justification, même succinte, est attendue) ? Quelle est la période du phénomène «le satellite se retrouve à la verticale d'un même point de la Terre»?

B. Propagation du signal

9. Faire un schéma où figurent le satellite , le récepteur ainsi que la base directe ( ). Quels sont les direction, sens de propagation et la polarisation relativement à ce système d'axes?
10. Vérifier que cette onde est bien solution de l'équation de propagation à une condition près à préciser reliant et . Calculer numériquement et la longueur d'onde associés.
11. Exprimer le champ associé à la propagation de l'onde.
12. Exprimer le vecteur de Poynting et en déduire l'expression de la puissance moyenne par unité de surface associée à la propagation de l'onde.
13. Au niveau du récepteur, l'amplitude du champ électrique est . Calculer numériquement la puissance moyenne par unité de surface à cet endroit. On pourra utiliser l'aide numérique suivante: .
14. On considère que le satellite émet de manière isotrope. Calculer la puissance émise par le satellite dans cette hypothèse (rappel ). Peut-on supposer que la puissance réelle est supérieure ou inférieure à celle-ci?

C. Décalage dû à la traversée de la troposphère

Figure 6 - Repérage de l'altitude

15. En considérant l'air comme un gaz parfait, donner l'expression de sa masse volumique en fonction de (masse molaire de l'air), (pression), (constante des gaz parfaits) et (température). On donne et . Calculer numériquement la masse volumique de l'air au niveau du sol où on prendra bar et .
16. La loi de Gladstone donne une relation entre l'indice de réfraction d'un gaz et sa masse volumique étant une constante :
    Montrer que, pour un gaz parfait, on peut écrire . On prendra dans la suite SI. Quelle est l'unité de ?
17. Montrer que l'expression de la pression en fonction de l'altitude dans le modèle de l'atmosphère isotherme s'écrit et préciser l'expression de .
18. On prendra et . Calculer numériquement ainsi que la pression à l'altitude de . Aide numérique :
19. On s'intéresse à la variation de l'indice de réfraction de l'air en fonction de l'altitude . Montrer que l'on peut écrire, à partir des résultats précédents :

21. En déduire l'expression littérale du temps nécessaire pour traverser verticalement les de la troposphère en fonction de et .
22. En déduire le temps de propagation supplémentaire lors de la traversée de la troposphère par rapport à la même distance parcourue dans le vide. Faire l'application numérique. A quelle erreur sur l'estimation de la distance entre le satellite émetteur et le récepteur cela conduit-il? Aide numérique :

D. Identification du satellite et estimation de la distance

1. le message de navigation, transmis à 50 bit/s, qui donne notamment la position des satellites;
2. le code , pour Coarse/Acquisition code («code grossier et d'acquisition» en français), transmis à 1,023 Mbit.s , qui permet d'identifier le satellite émetteur ainsi que la durée de propagation depuis celui-ci jusqu'au récepteur.

D.1. Les codes : définitions

D.2. Trois propriétés des codes C/A

1. l'autocorrélation d'un code, c'est-à-dire sa corrélation avec lui-même, vaut 1 ;
2. la corrélation d'un code avec le même code retardé d'un nombre non nul est quasi-nulle;
3. la corrélation entre deux codes émis par deux satellites différents est quasi-nulle, et cela vaut aussi si l'un des deux codes (ou les deux) est retardé.

• construit une liste code1 contenant le code correspondant à et ;
• construit une liste code2 contenant le code correspondant à et ;
• construit une liste de listes nommée codes1 telle que pour tout i allant de 0 à 1022, codes1 [i] corresponde à code1 retardé de i;
• construit une liste nommée correls11 telle que correls11[i] soit la corrélation de codes1[i] et de code1;
• construit une liste nommée correls12 telle que correls11[i] soit la corrélation de codes1[i] et de code2.
  On pourra, sans obligation, utiliser des constructions de listes par compréhension.
  Le tracé des listes correls11 et correls12 en fonction de l'indice est représenté figure 8.

Figure 8 - Corrélation du code 1 retardé avec les codes 1 et 2

D.3. L'acquisition

E. Affinage de la mesure : la boucle à verrouillage de retard

• de «suivre» le satellite émetteur, c'est-à-dire de décoder son signal sans interruption malgré les variations de la distance satellite-récepteur et donc du retard de propagation;
• de mesurer cette distance récepteur-satellite avec une précision permettant la localisation.

1. estimer le décalage du signal reçu vis-à-vis du code local;
2. intégrer par rapport au temps, ou plus simplement sommer, les décalages estimés;
3. retarder le code local d'un délai proportionnel à la sortie de l'intégrateur; le code retardé est renvoyé à l'estimateur de décalage, formant un système bouclé.

Figure 9 - Fonctionnement de la boucle à verrouillage de retard

E.1. Modélisation S.L.C.I. rudimentaire

• représente le retard de propagation inconnu que l'on souhaite reproduire;
• représente le retard du code «d'entrée» obtenu lors de l'acquisition;
• représente le retard du code «de sortie» recalé par l'algorithme.

Figure 10 - Modèle rudimentaire de la boucle à verrouillage de retard

E.2. Simulation du fonctionnement

• le code «de référence» reçu par le récepteur;
• le code «de sortie» généré localement et retardé par l'algorithme.

• : prend une liste a et un entier relatif k , et renvoie une liste correspondant à a retardé de k . Si k est négatif, cela revient à avancer a ;
• : renvoie la liste de longueur 1023 contenant le code C/A (sans suréchantillonnage) généré à partir des entiers p et q ;
• : prend une liste a et un entier positif k , et renvoie la liste «suréchantillonnée», c'est-à-dire constituée des éléments de a présents k fois consécutives.

36. Proposer une fonction decal qui prend pour arguments deux listes et de même longueur (on ne demande pas de le vérifier) contenant respectivement le code de sortie et le code de référence, et renvoyant un flottant égal à l'estimateur de décalage défini ci-dessus. On appellera les fonctions corr et retarde.

import matplotlib.pyplot as pp
c = codeCA(1,5) # correspond au satellite 1
cc = surech(c,100)
cr = list(retarde(cc,k) for k in range(-100,101))
d = list(-0.01*k for k in range(-100,101)) # signe moins pour avoir l'avance
e = list(decal(cr[i],cc) for i in range(len(cr)))
pp.plot(d,e)
pp.xlabel("Avance sortie sur ref (rapportée à la durée d'un bit)")
pp.ylabel("Sortie de l'estimateur de décalage")

37. Pour chacune des variables cr, d et e, indiquer s'il s'agit d'une liste «simple» ou d'une liste de listes et préciser à quoi correspond son i-ème élément.

Figure 11 - Relation entrée/sortie de l'estimateur de décalage

• ref : liste contenant le code de référence (choisi constant tout au long de la simulation);
• entree : liste contenant le code C/A d'entrée;
• imax : durée de la simulation exprimée en nombre de périodes du code (entier);
  — K : « gain » de l'《intégrateur » (flottant).
  def simu(ref, entree, imax, K):
  retard
  sortie = entree[:]
  sorties, retards = [sortie],[retard]
  # boucle répétée à chaque période du code
  for i in range(imax-1):
  # 1. on estime le décalage
  ecart LIGNE À COMPLÉTER NUMÉRO 1
  # 2. on "intègre" (somme) les écarts avec un facteur
  retard = # LIGNE À COMPLÉTER NUMÉRO 2
  # 3. on retarde l'entrée pour obtenir la sortie
  sortie LIGNE À COMPLÉTER NUMÉRO 3
  # écriture des résultats de la simulation
  sorties.append(sortie)
  retards.append(retard)
  return sorties, retards

• à gauche, l'évolution du retard en sortie de l'intégrateur (qui doit tendre vers 20 pour aligner la sortie sur la référence),
• à droite, la corrélation de la sortie avec la référence (qui tend vers 1 si la sortie s'aligne parfaitement avec la référence).

Figure 12 - Simulation de la boucle à verrouillage de retard pour trois valeurs de

Troisième partie EXPLOITATION DE LA LOCALISATION

F. Transmission de la localisation : les trames NMEA

• $GPGGA : type de trame ;
• 064036.289: heure d'envoi au format 'HHMMSS.SSS' (ici );
• 4836.5375 : latitude en valeur absolue (ici 48 degrés 36,5375 minutes);
• N : sens de la latitude ( N pour Nord, S pour Sud);
• 00740 . 9373 : longitude en valeur absolue (ici 7 degrés 40,9373 minutes);
• E : sens de la longitude (E pour Est, W pour Ouest);
• 1 : type de positionnement (non abordé ici);
• 04 : nombre de satellites utilisés pour la localisation;
• 3.2 : indicateur de précision (non abordé ici);
• 200.2 : altitude (ici 200,2);
• M : unité de l'altitude (ici, des mètres) ;
• , , , , 0000: champs non utilisés (d'autres informations peuvent y être inscrites);
• *: séparateur entre les champs et la somme de contrôle;
• OE: somme de contrôle.

• Les trois caractères situés entre le et le sont ', ', ' et ' 1 ';
  - Leurs codes ASCII respectifs sont 48, 44 et 49 (en décimal);
  - L'instruction 48^44~49 renvoie l'entier 45, dont l'écriture hexadécimale est '2D';
  - Cela correspond bien aux deux caractères situés après le * : la trame est donc valide.

• si s est une chaîne, s.find('a') recherche la première apparition du caractère 'a' dans s et renvoie son indice (ou-1 s'il n'est pas trouvé) ;
• si c est un caractère (c'est-à-dire une chaîne de longueur 1), ord(c) renvoie le code ASCII de , qui est un entier compris entre 0 et 127 ;
• le OU exclusif bit à bit est commutatif ( ) et associatif ( );
• le calcul du OU exclusif bit à bit peut être initialisé à zéro car quel que soit l'entier i, 0^i est toujours égal à i;
• si s est une chaîne contenant la représentation hexadécimale d'un entier (dont les chiffres vont de 0 à F ), l'instruction int( ) permet d'obtenir l'entier correspondant.

43. Écrire une fonction controle qui prend pour argument la chaîne trame et renvoie True si la somme de contrôle correspond bien au résultat du calcul précédent, et False sinon.

G. Calcul du plus court chemin

Figure 13 - Exemple de graphe pondéré

44. Le graphe (exemple ci-dessus) sera codé par un dictionnaire d'adjacence dont on donne ci-dessous les 3 premières lignes :

{0 : [(1,5), (2,6)],
    1:[(0,5),(3,8),(4,3)],
    2:[(0,6),(4,1),(5,9)],
    ...
    ...
    ...
    }

Description de l'algorithme :

• On utilise une liste de taille appelée distances dont les éléments représentent les distances entre le sommet de départ et chacun des sommets. Cette distance est initialisée à 0 pour le sommet de départ et à -1 (qui représente l'infini) pour les autres;
• On va visiter les différents sommets du graphe, et il faut savoir lesquels ont déjà été visités ou non. On utilise une liste deja_visites de taille de booléens initialement tous à False;
• On itère avec une boucle while, la condition d'arrêt étant le fait que la liste deja_visites ne contient que des True. Pour chaque itération :
• On cherche parmi les sommets pas encore visités celui qui est à la plus petite distance du sommet de départ. On l'appelle en_cours pour la suite;
• On visite ce sommet en_cours :
• On met ce sommet à True dans la liste deja_visites;
• On parcourt ses voisins et pour chacun d'entre eux qui n'a pas encore été visité (appelé voisin) on actualise dans la liste distance la valeur le concernant : on la remplace par le minimum entre l'ancienne distance et la distance entre le sommet de départ et en_cours à laquelle on ajoute la distance entre en_cours et voisin.

45. Donner les états successifs de la liste distances au cours de l'exécution de l'algorithme sur l'exemple de la figure 13, le sommet de départ étant le sommet 0 .
46. Écrire une fonction sommet_min(dist,deja_visites) qui prend en argument une liste dist d'entiers positifs ou égaux à -1 et une liste deja_visites de booléens et qui renvoie l'indice du minimum de dist parmi ceux dont la valeur dans la liste deja_visites correspond à False et qui n'ont pas pour valeur -1 . Si aucun indice dans la liste ne convient, cela signifie que l'algorithme est terminé, on renverra None.
47. Écrire une fonction actualiser(k,dist,deja_visites,g) qui prend en entrée un graphe g sous forme d'un dictionnaire d'adjacence, deux listes dist et deja_visites de taille et un entier k compris entre 0 et (où est la taille du graphe), et qui met à jour les listes dist et deja_visites.
48. En utilisant les fonctions précédentes, écrire une fonction dijkstra(g,depart) prenant en entrée un graphe g sous forme de dictionnaire d'adjacence et un sommet depart et renvoyant la liste des distances minimales au sommet depart.

H. Statistiques sur les durées des trajets

1. noeuds, qui décrit chaque nœud (ou sommet) par les attributs suivants :

• id (entier) : identifiant du nœud (clé primaire) ;
• num (entier) : numéro de la voie de l'adresse;
• voie (chaîne) : type (rue, avenue...) et nom de la voie de l'adresse;
• code (entier) : code postal de l'adresse;
• ville (chaîne) : ville de l'adresse.

2. trajets, qui décrit chaque trajet enregistré par les attributs suivants :

• id_from (entier) : identifiant du nœud de départ ;
• id_to (entier) : identifiant du nœud d'arrivée;
• date (chaîne) : date de départ du trajet au format "AAAA-MM-JJ";
• heure (chaîne) : heure de départ du trajet au format "HH:MM:SS" sur 24 heures;
• durée (entier) : durée du trajet en secondes.

49. Écrire une requête renvoyant les heures de départ et les durées des trajets ayant débuté le avril 2025 et allant du nœud 123 au nœud 456 (les numéros sont les identifiants).
50. Écrire une requête renvoyant la date de départ, l'heure de départ et la durée des trois trajets les plus courts (c'est-à-dire dont les durées sont les plus petites) allant du nœud 123 au nœud 456, ordonnés par durées croissantes.
51. Écrire une requête renvoyant le nombre de trajets enregistrés qui partent du numéro 7 de la voie nommée « rue des Plantes » située dans la ville de Paris.
52. On considère les trajets vers la ville de Lyon ayant débuté le avril 2025. Écrire une requête renvoyant, pour chaque ville de départ pour laquelle au moins dix trajets de ce type existent, le nom de la ville suivi des durées minimale, moyenne et maximale des trajets.