: 👈 gratuite pour tous les corrigés si tu crées un compte 👈 l'accès aux indications de tous les corrigés ne coûte que 1 €⬅ clique ici 👈 gratuite pour tous les corrigés si tu crées un compte - - - - - - - - - - - - - - - - - 👈 gratuite pour ce corrigé si tu crées un compte - - - - - - - - - - - - - - -
Énoncé obtenu par reconnaissance optique des caractères
SESSION 2025
PSI5IN
ÉPREUVE MUTUALISÉE AVEC E3A-POLYTECH
ÉPREUVE SPÉCIFIQUE - FILIÈRE PSI
____________________
INFORMATIQUE
Durée : 3 heures
____________________
N.B. : le candidat attachera la plus grande importance à la clarté, à la
précision et à la concision de la rédaction.
Si un candidat est amené à repérer ce qui peut lui sembler être une erreur
d'énoncé, il le signalera sur sa copie
et devra poursuivre sa composition en expliquant les raisons des initiatives
qu'il a été amené à prendre.
RAPPEL DES CONSIGNES
·
·
·
Utiliser uniquement un stylo noir ou bleu foncé non effaçable pour la rédaction
de votre composition ; d'autres
couleurs, excepté le vert, bleu clair ou turquoise, peuvent être utilisées,
mais exclusivement pour les schémas
et la mise en évidence des résultats.
Ne pas utiliser de correcteur.
Écrire le mot FIN à la fin de votre composition.
______________________________________________________________________________
Les calculatrices sont interdites.
Le sujet est composé de trois parties.
L'épreuve est à traiter en langage Python sauf pour les bases de données.
Les différents algorithmes doivent être rendus dans leur forme définitive sur
le Document
Réponse dans l'espace réservé à cet effet en respectant les éléments de syntaxe
du langage (les brouillons ne sont pas acceptés).
La réponse ne doit pas se limiter à la rédaction de l'algorithme sans
explication, les programmes doivent être expliqués et commentés de manière
raisonnable.
Énoncé et Annexe : 16 pages
Document Réponse (DR) : 11 pages
Seul le Document Réponse (DR) doit être rendu dans son intégralité (le QR Code
doit
être collé sur la première page du DR.
1/16
A
Gestion de Randonnées
Les fonctions seront définies avec leur signature dans le sujet :
ma_fonction(arg1:type1, arg2:type2) -> type3.
Cette notation permet de définir une fonction qui se nomme ma_fonction qui
prend deux
arguments en entrée, arg1 de type type1 et arg2 de type type2. Cette fonction
renvoie une
valeur de type type3.
Il ne faut pas recopier les signatures des fonctions dans le DR, il faut écrire
directement :
def ma_fonction ( arg1 , arg2 ) :
# liste d ' instructions
Introduction
Lors d'une randonnée, des applications disponibles sur smartphones permettent
d'enregistrer l'itinéraire parcouru. L'utilisation de ces données peut
permettre d'analyser a posteriori
le parcours effectué (distance, durée, dénivelés...) ou de planifier de
nouvelles sorties.
L'objectif du travail proposé est de découvrir différentes facettes de ces
applications.
Le sujet abordera les points suivants :
- l'organisation des différents parcours dans une base de données,
- différentes stratégies pour obtenir des informations sur le dénivelé effectué,
- la planification de randonnées en utilisant des algorithmes de type Dijkstra.
Les données recueillies lors d'une randonnée sont généralement stockées dans un
fichier au
format GPX (pour GPS eXchange Format). Ce fichier est appelé trace GPX de la
randonnée.
2/16
Partie I - Gestion des randonnées dans une base de données
Les applications de randonnées permettent à un utilisateur de stocker les
données de ses
randonnées effectuées ou d'avoir accès à celles effectuées par d'autres
utilisateurs. Ces
données sont stockées dans une base contenant notamment les tables suivantes.
La table Randonnee contenant :
Id
Titre
Type
Lieu
Distance
DenP
DenN
Duree
Niveau
IdAuteur
Trace
entier, identifiant de la randonnée
chaîne de caractères, titre de la randonnée
chaîne de caractères du type de l'activité : "Pied", "VTT", "Cheval"
chaîne de caractères, coordonnées GPS du point de départ
flottant, longueur en kilomètres de la randonnée
entier, dénivelé positif en mètres
entier, dénivelé négatif en mètres
entier, durée en minutes de la randonnée
entier compris entre 1 et 5 (1 : facile à 5 : extrême), difficulté
entier, identifiant de l'auteur de la randonnée
chaîne de caractères, lien internet vers la trace GPX.
La table Auteur contenant :
Id
Nom
Prenom
Pseudo
Mail
entier, identifiant de l'auteur (le randonneur)
chaîne de caractères, nom de l'auteur
chaîne de caractères, prénom de l'auteur
chaîne de caractères, pseudo de l'auteur
chaîne de caractères, mail de l'auteur.
Q1. Expliquer en quoi l'attribut Titre ne peut probablement pas être une clé
primaire pour
la table Randonnee. Proposer un attribut de la table Randonnee qui puisse être
une clé
primaire.
Q2. Identifier un attribut qui soit une clé étrangère de la table Randonnee.
Q3. Écrire une requête SQL dont l'évaluation renvoie le titre, les coordonnées
GPS du
point de départ et la longueur des randonnées à pied.
Q4. Écrire une requête SQL dont l'évaluation renvoie l'identifiant de l'auteur
et son nombre
d'activités à pied de niveau 3, classées par ordre décroissant du nombre
d'activités
de chaque auteur.
Q5. Écrire une requête SQL dont l'évaluation renvoie le Pseudo de l'auteur et
le Titre des
randonnées stockées dans la base.
Q6. Écrire une requête SQL dont l'évaluation renvoie les nom et prénom d'un des
auteurs
ayant posté le plus de randonnées à cheval.
3/16
Partie II - Quelques calculs de dénivelés
Nous allons maintenant nous intéresser plus particulièrement aux données
enregistrées par
l'application lors d'une randonnée. En pratique, une application enregistre
régulièrement les
données fournies par le GPS du téléphone portable comme la latitude et la
longitude exprimées en degrés ainsi que l'altitude (élévation) exprimée en
mètres. La figure 1 présente un
extrait du fichier trace GPX.
Randonne Marche 261267.20001220703125 267.79998779296875 268.399993896484375
Figure 1 - Exemple de fichier trace GPX
Le module gpxpy de Python permet de lire et extraire simplement les données de
ce type de
fichier.
Q7. Écrire une ligne de code permettant l'importation du module gpxpy.
Un parcours (ou une randonnée) est alors une succession de points. Après
lecture et traitement du fichier à l'aide du module gpxpy, l'itinéraire d'une
randonnée est représenté par
une liste de points où chacun de ces points est un triplet de trois flottants
correspondant
respectivement à la latitude, la longitude et l'altitude. Le premier point d'un
itinéraire sera le
point de départ et le dernier le point d'arrivée.
Pour améliorer la lisibilité de la signature de nos fonctions, nous utiliserons
le type trpt
(pour track point ou point de la trace) pour représenter les triplets de points
ainsi que le
type itineraire pour les listes de points. Ainsi, à partir du fichier de la
figure 1 on pourra
introduire les variables p0, p1, p2, p3 qui sont de type trpt et la variable
iti qui est de type
itineraire :
p0 = (43.331146 , -1.627655 , 2 6 1 . 0 0 )
p1 = (43.331055 , -1.627895 , 2 6 7 . 2 0 )
p2 = (43.331047 , -1.627927 , 2 6 7 . 7 9 )
p3 = (43.331040 , -1.627966 , 2 6 8 . 3 9 )
i t i = [ p0 , p1 , p2 , p3 ] # i t i n e r a i r e
#
#
#
#
point
point
point
point
4/16
de d e p a r t
intermediaire
intermediaire
d arrivee
Rappelons (figure 2) qu'un point de la surface terrestre est défini par :
- sa latitude, notée , qui est la mesure angulaire entre l'équateur et ce
point. Elle est
représentée par un angle compris entre -90 et +90
- sa longitude, notée , qui est la mesure angulaire entre le méridien de
référence (méridien de Greenwich) et ce point. Elle est représentée par un
angle compris entre -180
et +180
- son altitude qui exprime la hauteur entre le niveau de la mer et le niveau du
point. Elle
est représentée par un réel et s'exprime en mètres.
Figure 2 - Repérage, sur la surface du globe, d'un point A de latitude A et de
longitude A
La syntaxe pour extraire les éléments d'un tuple est identique à celle utilisée
pour les éléments d'une liste mais les tuples ne sont pas modifiables (ou
mutables).
>>> p0 = (43.331146 , -1.627655 , 2 6 1 . 0 0 ) # p o i n t de d e p a r t
>>> p0 [ 0 ]
43.331146
>>> ( a , b , c ) = p0
>>> a
43.331146
On considère la fonction mystere, dont l'argument iti est non vide :
1 def mystere ( i t i : i t i n e r a i r e ) -> f l o a t :
2
s = 0
3
f o r i i n range ( len ( i t i ) ) :
4
( l a t , long , a l t ) = i t i [ i ]
5
s = s + alt
6
r e t u r n ( s / len ( i t i ) )
Q8. Donner la valeur numérique que renvoie le code suivant. Donner la
signification de
cette valeur dans le contexte du sujet.
1
2
3
4
5
6
>>> p0 = ( 4 7 . 8 7 4 1 , 1.8758 ,
>>> p1 = ( 4 7 . 8 7 4 4 , 1.8759 ,
>>> p2 = ( 4 7 . 8 7 4 8 , 1.8761 ,
>>> p3 = ( 4 7 . 8 7 5 0 , 1.8759 ,
>>> I 1 = [ p0 , p1 , p2 , p3 ]
>>> mystere ( I 1 )
100)
102)
110)
108)
5/16
Q9. Donner la complexité temporelle de la fonction mystere en fonction de la
taille n de la
liste passée en argument.
Q10. Écrire une fonction altitude_maximale(iti:itineraire) -> float qui, étant
donné
une liste non vide iti de points, renvoie l'altitude maximale de l'itinéraire
en mètres.
Le dénivelé global d'une randonnée est la différence entre l'altitude maximale
et l'altitude du
point de départ.
Q11. En
utilisant
la
fonction
altitude_maximale,
écrire
une
fonction
denivele_global(iti:itineraire) -> float qui, étant donné une liste iti de
points, renvoie le dénivelé global de la randonnée.
II.1 - Premier calcul de dénivelé positif
Le dénivelé entre deux points successifs p1 et p2 d'un itinéraire est dit
positif si la différence
entre l'altitude de p2 et l'altitude de p1 est positive. On appelle alors
dénivelé positif la différence entre ces deux altitudes. Le dénivelé positif
cumulé d'une randonnée est la somme de
tous les dénivelés positifs entre les points successifs du parcours.
Q12. Écrire une fonction denivele_positif_cumule(iti:itineraire) -> float qui,
étant
donné une liste iti de points, renvoie le dénivelé positif cumulé de la
randonnée.
La méthode de mesure de l'altitude par le GPS est relativement imprécise due à
la présence
éventuelle d'une couverture nuageuse, d'un parcours sous des arbres... Or, lors
du calcul du
dénivelé positif cumulé, de faibles erreurs répétées peuvent induire une erreur
conséquente
sur le calcul cumulé.
Par exemple, si le randonneur effectue une randonnée en bord de mer sur une
plage d'altitude constante mais que le GPS effectue des mesures erronées pour
donner une liste d'altitudes égale à [0, -2, 2, -2, 2, -2, 2, -2, 2], le
dénivelé positif cumulé calculé par la
fonction précédente est égal à 16 mètres alors qu'il devrait être nul.
Nous allons envisager deux méthodes pour pallier ces imprécisions : le lissage
des altitudes
et l'utilisation d'altitudes de référence.
II.2 - Lissage des altitudes
Le lissage d'une liste de longueur n des altitudes par moyenne glissante de pas
p consiste à
remplacer l'altitude au point numéroté i par la moyenne des altitudes des
points numérotés
i, i + 1,..., i + j où j = min{p - 1, n - i - 1}.
Par exemple, lorsque p = 2, la liste précédente sera remplacée par :
liste de départ
0
-2
2
-2
2
-2
2
-2
2
calcul
0-2
2
-2+2
2
2-2
2
-2+2
2
2-2
2
-2+2
2
2-2
2
-2+2
2
2
liste lissée
-1
0
0
0
0
0
0
0
2
6/16
Le dénivelé positif est alors de 3 mètres, ce qui est plus proche de la réalité
de l'itinéraire.
Q13. Écrire une fonction alt_glissante(liste_alt:list, p:int) -> list qui étant
donné une liste d'altitudes et un entier p, crée une nouvelle liste contenant
la moyenne
glissante des altitudes avec un pas p. On pourra utiliser la fonction min qui
prend deux
nombres flottants en entrée et renvoie le plus petit des deux.
Q14. Évaluer la complexité de la fonction alt_glissante en fonction de la
taille n de la liste
d'altitudes passée en argument et du pas p.
II.3 - Utilisation d'altitudes de référence
Une autre stratégie pour améliorer la précision sur les altitudes, une fois la
randonnée effectuée et une connexion internet plus stable trouvée, consiste à
se connecter à une base de
référence qui, étant donné un point du globe, renvoie son altitude. Bien sûr,
tous les points
ne sont pas stockés dans la base. Nous supposerons que la surface du globe est
quadrillée
par une liste de latitudes et une liste de longitudes et qu'en chaque point de
cette grille l'altitude a été mesurée précisément. Ces altitudes sont stockées
dans un dictionnaire nommé
dem (Digital Elevation Model) dont les clés sont des couples latitude /
longitude et les valeurs
sont les altitudes correspondantes.
On considère le code suivant :
1
2
3
4
5
lat_ref = []
long_ref = [ ]
f o r ( l a t , l o n g ) i n dem :
l a t _ r e f . append ( l a t )
l o n g _ r e f . append ( l o n g )
On supposera dans la suite que les valeurs -90 et 90 sont dans lat_ref et que
les valeurs
-180 et 180 sont dans long_ref.
Q15. Indiquer le type des variables lat_ref et long_ref. Expliquer quel est le
contenu de
ces variables dans le contexte de ce sujet.
7/16
On considère le code suivant :
1 def a u x i l i a i r e ( x , y ) :
2
i f x == [ ] : r e t u r n y
3
i f y == [ ] : r e t u r n x
4
i f x [ len ( x ) -1] < y [ len ( y ) -1] : 5 v a l = y . pop ( ) 6 else : 7 v a l = x . pop ( ) 8 z = auxiliaire (x ,y) 9 z . append ( v a l ) 10 return z 11 12 def p r i n c i p a l ( x ) : 13 i f len ( x ) <= 1 : 14 return x 15 else : 16 m = len ( x ) / / 2 17 x1 = p r i n c i p a l ( x [ 0 :m] ) 18 y1 = p r i n c i p a l ( x [m : len ( x ) ] ) 19 z = a u x i l i a i r e ( x1 , y1 ) 20 return z Q16. Précisez la signature des fonctions auxiliaire et principal. La réponse doit être justifiée. Q17. Sur le DR, cocher la (les) cases qui correspond(ent) au(x) type(s) de programmation utilisé(s) pour coder la fonction principal. Q18. Justifier brièvement que, étant donné une liste x, l'appel principal(x) termine. Q19. L'appel principal(x) permet de renvoyer une liste triée par ordre croissant. Proposer un nom qui décrit le type de tri utilisé en justifiant brièvement votre choix. Par la suite, on suppose que les listes lat_ref et long_ref sont triées. Il faut maintenant déterminer le point du dictionnaire dem le plus proche d'un point donné. 8/16 On donne une implémentation partielle de la fonction ref(valeur, liste_ref) qui, étant donné un flottant valeur et une liste non vide de flottants triés par ordre croissant liste_ref tels que valeur est strictement compris entre le premier et le dernier élément de liste_ref, renvoie la valeur de la liste liste_ref la plus proche de valeur. 1 def r e f ( v a l e u r : f l o a t , l i s t e _ r e f : l i s t ) -> f l o
a t :
2
# on dé t e r m i n e ind_deb e t i n d _ f i n t e l s que
3
# l i s t e _ r e f [ ind_deb ] < v a l e u r <= l i s t e _ r e f [ i n d _ f i n ] 4 # avec une mé thode par d i c h o t o m i e 5 ind_deb = . . . . . . 6 ind_fin = . . . . . . 7 while ind_deb < i n d _ f i n - 1 : 8 k = ..... 9 i f v a l e u r <= l i s t e _ r e f [ k ] : 10 ind_fin = . . . . . 11 else : 12 ..... 13 # on dé t e r m i n e l e p l u s proche 14 i f l i s t e _ r e f [ i n d _ f i n ] - v a l e u r < v a l e u r - l i s t e _ r e f [ ind_deb ] : 15 return . . . . . 16 else : 17 return . . . . . Q20. Compléter les lignes 5, 6, 8, 10, 12, 15 et 17 de la fonction ref. Q21. Utiliser les données précédentes pour écrire une fonction standardise(liste_parcours:itineraire) -> itineraire qui, étant donné
un itinéraire, renvoie un nouvel itinéraire où l'altitude de chaque point a été
remplacée
par l'altitude issue du dictionnaire dem.
Pour chaque point de l'itinéraire, on cherchera la latitude r de référence la
plus proche
de sa latitude, la longitude r de référence la plus proche de sa longitude et
on remplacera son altitude par l'altitude du point de référence de coordonnées
(r , r ).
Les variables lat_ref, long_ref et dem sont définies globalement en dehors de la
fonction et peuvent être utilisées directement.
9/16
Partie III - Organisation d'un Trek
Un randonneur souhaite effectuer un long Trek, c'est-à-dire une série de
randonnées sur
plusieurs jours. Il organise son parcours à partir d'un site qui propose
différentes randonnées
d'une journée. Chaque randonnée est définie par un niveau de difficulté allant
de 1 (facile)
à 5 (extrême). L'ensemble des données permet au randonneur d'établir un graphe
où :
- les sommets représentent les points de départ / arrivée des randonnées,
- les arêtes représentent les randonnées possibles avec comme poids le niveau
de la
randonnée.
On suppose qu'il y a une unique randonnée qui relie 2 sommets du graphe.
On suppose que les randonnées peuvent être effectuées du point de départ vers
le point
d'arrivée ou du point d'arrivée vers le point de départ sans que la difficulité
ne soit modifiée.
Le graphe représentant les différentes randonnées sera donc non orienté.
5
e
1
1
2
c
b
2
3
4
a
4
d
4
f
Figure 3 - Graphe G
Le graphe G de la figure 3 est représenté par le dictionnaire G défini de la
manière suivante :
G = dict ( )
G[ ' a ' ] = { ' b ' :3 ,
G[ ' b ' ] = { ' a ' :3 ,
G[ ' c ' ] = { ' a ' :2 ,
G[ ' d ' ] = { ' a ' :4 ,
G[ ' e ' ] = { ' b ' :5 ,
G[ ' f ' ] = { ' d ' :4 ,
' c ' :2 ,
' d ' :2 ,
' d ' :4}
' b ' :2 ,
' d ' :1 ,
' e ' :1}
' d ' :4}
' e ' :5}
' c ' :4 , ' e ' :1 , ' f ' :4}
' f ' :1}
Le randonneur souhaite aller du point a au point f. Cependant, comme il n'est
pas entraîné,
il choisit de trouver le chemin dont la somme des difficultés des randonnées
est la plus petite,
quel que soit le nombre d'étapes.
Afin d'utiliser le vocabulaire habituellement employé dans les algorithmes de
parcours de
graphes, on utilisera le terme "distance" au lieu du terme "difficulté" et on
cherchera donc à
minimiser la "distance" (au sens de "difficulté" du trek).
10/16
III.1 - Première idée : algorithme intuitif
Pour trouver son chemin, le randonneur exécute la fonction mystere2 suivante.
1 def mystere2 ( graph : d i c t , Sd : s t r , Sf : s t r ) -> t u p l e :
2
" " " graph : graphe r e p r é s e n t a n t l e s randonnées d i s p o n i b l
e s
3
Sd : sommet de dé p a r t dans l e graphe
4
Sf : sommet d ' a r r i v ée dans l e graphe
5
Renvoie une l i s t e de randonnées p e r m e t t a n t de r e l i e r Sd à Sf
a i n s i
que l a somme des d i f f i c u l t és d ' un t e l chemin . " " "
6
d e j a V i s i t e s = [ ] # L i s t e des sommets dé j à v i s i t és
7
s T r a i t e = Sd # I n i t i a l i s a t i o n du sommet à t r a i t e r
8
chemin = [ s T r a i t e ] # Chemin c h o i s i i n i t i a l i s é
9
d i f f C h e m i n = 0 # D i f f i c u l t é du chemin c h o i s i
10
# C o n s t r u c t i o n i t e r a t i v e du chemin
11
while s T r a i t e ! = Sf :
12
d e j a V i s i t e s . append ( s T r a i t e )
13
d =float ( ' i n f ' ) #valeur représentant l ' i n f i n i
14
sInter = sTraite
15
f o r sommet i n graph [ s T r a i t e ] :
16
i f sommet not i n d e j a V i s i t e s :
17
i f graph [ s T r a i t e ] [ sommet ] < d : 18 s I n t e r = sommet 19 d = graph [ s T r a i t e ] [ sommet ] 20 diffChemin = diffChemin + d 21 chemin . append ( s I n t e r ) 22 sTraite = sInter 23 r e t u r n chemin , d i f f C h e m i n Q22. Expliquer le fonctionnement de la boucle itérative comprise entre les lignes 15 à 19 et en déduire le nom du type d'algorithme utilisé. Q23. Donner ce que renvoie l'instruction mystere2(G, "a", "f"). On ne demande pas d'indiquer toutes les étapes de l'algorithme. Q24. Justifier si ce programme permet au randonneur de trouver le chemin de difficulté cumulée minimale. III.2 - Deuxième idée : l'algorithme de Dijkstra Pour résoudre son problème, le randonneur décide d'appliquer l'algorithme de Dijkstra. Il réalise ainsi une fonction dijkstra qui prend en arguments : - la représentation du graphe sous forme de dictionnaire de dictionnaires - le sommet de départ sous forme d'une chaîne de caractères - le sommet d'arrivée sous forme d'une chaîne de caractères et renvoie un dictionnaire dont les clés sont les sommets du graphe et les valeurs sont des couples dont : - la première composante est la distance totale minimale du point de départ au sommet clé - la seconde composante est le sommet précédent dans le graphe qui permet de réaliser la distance minimale entre le point de départ et le sommet clé. 11/16 L'implémentation rappelée ci-dessous de l'algorithme de Dijkstra utilise les quatre variables : - aVisiter : liste des sommets qui doivent être visités - dejaVisites : liste des sommets déjà visités - distance : le dictionnaire qui sera renvoyé par la fonction - sTraite : sommet dont on étudie les voisins pour mettre à jour les distances au point de départ. La méthode L.remove(elt) permet de supprimer la première apparition de elt dans la liste L. 1 def cherche_min ( d i c o : d i c t , l i s t e : l i s t ) -> s t r :
2
d =float ( " i n f " ) # I n i t i a l i s a t i o n
3
f o r s i n l i s t e : # p a r c o u r s des elements de l a l i s t e
4
i f s i n d i c o and d i c o [ s ] [ 0 ] < d : # recherche de l a v a l e u r minimale 5 d = dico [ s ] [ 0 ] 6 sTraite = s 7 return s T r a i t e 8 9 def unpas ( graph : d i c t , s : s t r , d i s t a n c e : d i c t , d e j a V i s i t e s : l i s t , a v i s i t e r : l i s t ) -> None :
10
a v i s i t e r . remove ( s ) # Mise a j o u r des sommets a v i s i t e r
11
d e j a V i s i t e s . append ( s ) # Mise a j o u r des sommets dé j à v i s
i t és
12
f o r v i n graph [ s ] : # Mise a j o u r des d i s t a n c e s au p o i n t
de d e p a r t
13
i f v not i n d e j a V i s i t e s :
14
i f v not i n a v i s i t e r :
15
a v i s i t e r . append ( v )
16
n d i s t a n c e = d i s t a n c e [ s ] [ 0 ] + graph [ s ] [ v ]
17
i f v not i n d i s t a n c e or n d i s t a n c e < d i s t a n c e [ v ] [ 0 ] : 18 distance [ v ] = ( ndistance , s ) 19 20 def d i j k s t r a ( graph : d i c t , Sd : s t r , Sf : s t r ) -> d i c t
:
21
a V i s i t e r = [ Sd ] # L i s t e des sommets à v i s i t e r
22
d e j a V i s i t e s = [ ] # L i s t e des sommets dé j à v i s i t és
23
d i s t a n c e = { Sd : ( 0 , Sd ) } # D i c t i o n n a i r e des d i s t a n
c e s
24
s T r a i t e = Sd # Premier sommet a v i s i t e r
25
while s T r a i t e ! = Sf :
26
s T r a i t e = cherche_min ( d i s t a n c e , a V i s i t e r )
27
unpas ( graph , s T r a i t e , d i s t a n c e , d e j a V i s i t e s , a V i
s i t e r )
28
return distance
Q25. On effectue l'appel dijkstra(G, "a", "f") où le graphe G est défini dans
la figure 3.
Dans le tableau du DR est représenté le contenu de certaines variables de
l'algorithme
dijkstra en fonction de l'étape de l'itération (comme si un print était
effectué après
la ligne 27). À partir des cases déjà remplies, compléter les cases vides du
tableau.
Lorsque la clé n'est pas définie dans le dictionnaire, la case du tableau
contient un X.
12/16
# On a p p l i q u e l ' a l g o r i t h m e de D i j k s t r a
s I n i t , sFin = " a " , " f "
d i s t a n c e = d i j k s t r a (G, s I n i t , s F i n )
:
# On c o n s t r u i t l a l i s t e du chemin en p a r t a n t de l a f i n
s = sFin
chemin = [ s ]
while . . . . . . . . :
..........
..........
# On remet l e chemin dans l ' o r d r e du dé b u t v e r s l a f i n
chemin . r e v e r s e ( )
p r i n t ( " Un chemin de " , s I n i t , " à " , sFin , " e s t : " , chemin )
p r i n t ( " La d i f f i c u l t é minimale e s t de : " , . . . . . . . . .
. . . . . )
Q26. Indiquer le contenu des lignes 8, 9, 10 et 15 du code précédent.
Q27. Expliquer comment pourrait être diminué le nombre de tests d'appartenance
à une
liste, notamment des lignes 14 et 15, de l'algorithme de Dijkstra.
Pour la fin de la sous-partie III.2, on considère le graphe de la figure 4 où,
pour simplifier,
toutes les randonnées sont supposées de difficulté 1. On suppose qu'une
représentation de
ce graphe par un dictionnaire est fournie dans une variable globale G1 et que
la liste des
voisins est triée par ordre alphabétique.
1
e1
b1 1
f1
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Pour reconstruire un chemin qui réalise la distance optimale entre le point de
départ "a" et
le point d'arrivée "f", on utilise le code suivant. On rappelle que la variable
globale G a été
définie précédemment.
a1 1
c1
1
g1 1
j1
1
d1 1 h1
1
i1
Figure 4 - Graphe G1
Q28. Lister les sommets visités par l'appel dijkstra(G1, "a1", "j1"), puis par
l'appel
dijkstra(G1, "j1", "a1").
13/16
III.3 - Troisième idée : l'algorithme de Dijkstra bidirectionnel
On constate à l'aide des deux questions précédentes (Q27 et Q28) que, en
fonction de la
structure du graphe, il est parfois préférable de chercher un chemin qui part
du sommet d'arrivée vers le sommet de départ plutôt qu'un chemin qui part du
sommet de départ vers le
sommet d'arrivée.
L'algorithme de Dijkstra bidirectionnel combine ces deux stratégies : au cours
de l'algorithme,
on va effectuer successivement soit une recherche depuis le point de départ
(appelée étape
forward) soit une recherche depuis le point d'arrivée (appelée étape backward).
À chaque
étape, on choisit ainsi un sommet qui réalise le minimum de la distance soit au
sommet de
départ, soit au sommet d'arrivée et on y applique l'algorithme de Dijkstra
classique.
Précisons l'algorithme. Notons S l'ensemble des sommets du graphe. Pour tout
sommet
i S, on note dF(i) (respectivement dB(i)) la distance minimale actuellement
calculée entre
le sommet de départ (respectivement d'arrivée) et le sommet i. Ces distances
sont actualisées au cours de l'algorithme et valent initialement l'infini. Nous
allons maintenir, c'est-à-dire
mettre à jour pendant l'exécution de l'algorithme, plusieurs variables :
- aVisiterF, dejaVisitesF : associées à l'algorithme de Dijkstra partant du
point de
départ (partie Forward),
- aVisiterB, dejaVisitesB : associées à l'algorithme de Dijkstra partant du
point d'arrivée (partie Backward),
- Fmin = min{dF(i), i aVisiterF} : distance minimale du sommet de départ à un
sommet
non encore visité par l'algorithme forward,
- Bmin = min{dB(i), i aVisiterB} : distance minimale du sommet d'arrivée à un
sommet
non encore visité par l'algorithme backward,
- BFmin = min{dF(i) + dB(i), i S} : longueur minimale d'un chemin reliant le
sommet de
départ au sommet d'arrivée,
- distanceF (respectivement distanceB) : dictionnaire dont les clés sont les
sommets et
les valeurs sont des couples dont la première composante est la plus petite
distance
d'un chemin qui relie le sommet depuis le point de départ (respectivement
depuis le
point d'arrivée) et la seconde est le sommet précédent dans un chemin qui
réalise cette
distance.
À chaque étape :
- Si BFmin Fmin + Bmin, l'algorithme termine : tout chemin qui réalise le
minimum BFmin
est un chemin optimal.
- Sinon,
- si Fmin < Bmin, on choisit un sommet qui réalise Fmin et on applique une étape forward de Dijkstra depuis ce sommet, c'est-à-dire qu'on appelle la fonction unpas avec les variables forward en mettant à jour les variables dejaVisitesF, aVisiterF et distanceF, - si Bmin < Fmin, on choisit un sommet qui réalise Bmin et on applique une itération de l'algorithme de Dijkstra backward depuis ce sommet, c'est-à-dire qu'on appelle la fonction unpas avec les variables backward en mettant à jour les variables dejaVisitesB, aVisiterB et distanceB, - si Bmin = Fmin, on choisit un sommet qui réalise ce minimum dans l'ensemble qui contient le moins d'éléments parmi aVisiterF et aVisiterB et on réalise une étape de Dijkstra à partir de ce sommet. Dans le cas où les deux ensembles contiennent le même nombre d'éléments, on préférera une recherche forward. 14/16 - On actualise Fmin,Bmin et BFmin en parcourant l'ensemble des sommets pour lesquels un chemin entre ce sommet et les sommets d'arrivée et de départ a déjà été calculé. Q29. Compléter la dernière ligne des tableaux du DR qui recense les étapes successives de l'algorithme de Dijkstra bidirectionnel sur le graphe G de la figure 3 avec a comme sommet de départ et f comme sommet d'arrivée. À chaque étape, on précise si le sommet est visité par la recherche forward (F) ou par la recherche backward (B). Dans chaque case sont précisées les valeurs de distanceF et distanceB. Pour simplifier la lisibilité, le tableau est découpé en deux parties. Q30. Justifier si renvoyer la quantité BFmin dès qu'un sommet a été atteint par les recherches forward et backward permet de trouver le chemin de longueur minimale. On donne une implémentation partielle de la fonction dijkstra_bidirectionnel qui, étant donné un graphe graph, un sommet de départ Sd et un sommet final Sf, renvoie la distance minimale reliant Sd à Sf en utilisant l'algorithme de Dijkstra bidirectionnel. 1 def d i j k s t r a _ b i d i r e c t i o n n e l ( graph : d i c t , Sd : s t r , Sf : s t r ) -> f l o a t :
2
a V i s i t e r F = [ Sd ] # L i s t e des sommets à v i s i t e r Forward
3
d e j a V i s i t e s F = [ ] # L i s t e des sommets dé j à v i s i t és
Forward
4
a V i s i t e r B = . . . # L i s t e des sommets à v i s i t e r Backward
5
d e j a V i s i t e s B = . . . # L i s t e des sommets dé j à v i s i t és
Backward
6
# D i c t i o n n a i r e des d i s t a n c e s Forward
7
d i s t a n c e F = { s : ( f l o a t ( ' i n f ' ) ,Sd ) f o r s i n graph }
8
# D i c t i o n n a i r e des d i s t a n c e s Backward
9
di s t a n ce B = { s : ( f l o a t ( ' i n f ' ) , Sf ) f o r s i n graph }
10
d i s t a n c e F [ Sd ] = ( 0 , Sd )
11
di s t a n ce B [ Sf ] = ( 0 , Sf )
12
Fmin , Bmin , BFmin = 0 , 0 , f l o a t ( " i n f " )
13
while . . . . . . . . . . . . . . . . . . . . :
14
i f Fmin < Bmin or \ 15 ( Fmin == Bmin and len ( a V i s i t e r F ) <= len ( a V i s i t e r B ) ) : 16 s T r a i t e = cherche_min ( distanceF , a V i s i t e r F ) 17 unpas ( graph , s T r a i t e , distanceF , d e j a V i s i t e s F , a V i s i t e r F ) 18 else : 19 s T r a i t e = cherche_min ( distanceB , a V i s i t e r B ) 20 unpas ( graph , s T r a i t e , distanceB , d e j a V i s i t e s B , a V i s i t e r B ) 21 Fmin = min ( [ . . . . . . . [ v ] [ 0 ] f o r v i n a V i s i t e r F i f v i n d i s t a n c e F ] ) 22 Bmin = min ( [ . . . . . . . [ v ] [ 0 ] f o r v i n a V i s i t e r B i f v i n d i s t a n c e B ] ) 23 L = [ . . . . . . . . . . . . . . . . . . . . for v in distanceB i f v in distanceF ] 24 i f L == [ ] : 25 BFmin = f l o a t ( " i n f " ) 26 else : 27 BFmin = min ( L ) 28 r e t u r n BFmin Q31. Compléter la fonction dijkstra_bidirectionnel qui, étant donné un graphe graph, un sommet de départ Sd et un sommet final Sf, renvoie la distance minimale reliant Sd à Sf en utilisant l'algorithme de Dijkstra bidirectionnel. Indiquer précisément le contenu des lignes 4, 5, 13, 21, 22 et 23. La fonction min(L:list) renvoie l'élément minimal d'une liste L. 15/16 Pour tout couple de sommets a et b du graphe, on note d(a, b) la distance minimale d'un chemin qui relie a à b. On admet que l'algorithme de Dijkstra classique est correct et que, à chaque étape, pour tous les sommets s de dejaVisites, la valeur d(a, s) est égale à la distance calculée distance[s][0]. De plus, tous les sommets non visités sont à une distance de a supérieure à la plus grande des distances déjà calculées. On s'intéresse maintenant à la correction partielle de l'algorithme de Dijkstra bidirectionnel. Supposons alors par l'absurde que l'algorithme de Dijsktra bidirectionnel a terminé mais que la distance BFmin ne soit pas la plus petite distance reliant le sommet de départ s au sommet d'arrivée t. Alors, il existe un chemin s = s0 , s1 , ..., sn = t qui est de distance d strictement inférieure à BFmin. Soit si un sommet de ce chemin. Q32. Montrer que si appartient soit à dejaVisitesF soit à dejaVisitesB. Q33. En déduire qu'il existe un indice i0 tel que si0 a été visité par la recherche forward et si0 +1 l'a été par la recherche backward. Q34. En déduire la correction partielle de l'algorithme de Dijkstra bidirectionnel. 16/16 I M P R I M E R I E N A T I O N A L E 25 1059 D'après documents fournis FIN Numéro d'inscription Nom : ____________________________________ Numéro de table Prénom : _________________________________ Né(e) le QR Code Emplacement Filière : Session : 2025 PSI Épreuve de : Consignes INFORMATIQUE · Remplir soigneusement l'en-tête de chaque feuille avant de commencer à composer · Rédiger avec un stylo non effaçable bleu ou noir · Ne rien écrire dans les marges (gauche et droite) · Numéroter chaque page (cadre en bas à droite) · Placer les feuilles A3 ouvertes, dans le même sens et dans l'ordre PSI5IN Document Réponse Ce Document Réponse doit être rendu dans son intégralité. Q1 - Explication de pourquoi l'attribut Titre ne peut probablement pas être une clé primaire pour la table Randonnee. Proposition d'un attribut de la table Randonnee qui puisse être une clé primaire Q2 - Identification d'un attribut qui puisse être une clé étrangère de la table Randonnee Q3 - Requête SQL dont l'évaluation renvoie le titre, les coordonnées GPS du point de départ et la longueur des randonnées à pied NE RIEN ÉCRIRE DANS CE CADRE Q4 - Requête SQL dont l'évaluation renvoie l'identifiant de l'auteur et son nombre d'activités à pied de niveau 3, classées par ordre décroissant du nombre d'activités de chaque auteur Q5 - Requête SQL dont l'évaluation renvoie le Pseudo de l'auteur et le Titre des randonnées stockées dans la base Q6 - Requête SQL dont l'évaluation renvoie les nom et prénom d'un des auteurs ayant posté le plus de randonnées à cheval Q7 - Instruction pour l'importation du module gpxpy Q8 - Valeur numérique renvoyée par mystere(I1). Signification de cette valeur Q9 - Complexité temporelle de mystere en fonction de la taille n de la liste passée en argument Q10 - Fonction altitude_maximale(iti:itineraire) -> float
Q11 - Fonction denivele_global(iti:itineraire) -> float
Q12 - Fonction denivele_positif_cumule(iti:itineraire) -> float
Q13 - Fonction alt_glissante(liste_alt:list, p:int) -> list
Q14 - Complexité de la fonction alt_glissante(liste_alt:list, p:int) -> list
Numéro
d'inscription
Nom : ____________________________________
Numéro
de table
Prénom : _________________________________
Né(e) le
QR Code
Emplacement
Filière :
Session : 2025
PSI
Épreuve de :
Consignes
INFORMATIQUE
· Remplir soigneusement l'en-tête de chaque feuille avant de commencer à
composer
· Rédiger avec un stylo non effaçable bleu ou noir
· Ne rien écrire dans les marges (gauche et droite)
· Numéroter chaque page (cadre en bas à droite)
· Placer les feuilles A3 ouvertes, dans le même sens et dans l'ordre
PSI5IN
Q15 - Type des variables lat_ref et long_ref. Explication du contenu de ces
variables dans
le contexte de ce sujet
Q16 - Signature des fonctions auxiliaire et principal. Justifier
Q17 - Type(s) de programmation utilisé(s) pour coder la fonction principal
Itératif
Récursif
k plus proches voisins
Algorithme glouton
Programmation dynamique
Diviser pour régner
NE RIEN ÉCRIRE DANS CE CADRE
Q18 - Justification de la terminaison de la fonction principal
Q19 - Nom décrivant le type de tri utilisé. Justification de votre choix
Q20 - Compléter les lignes 5, 6, 8, 10, 12, 15 et 17 de la fonction ref
Ligne 5 :
Ligne 6 :
Ligne 8 :
Ligne 10 :
Ligne 12 :
Ligne 15 :
Ligne 17 :
Q21 - Fonction standardise(liste_parcours:itineraire) -> itineraire
Q22 - Explication des lignes 15 à 19 de la fonction mystere2. Nom du type
d'algorithme utilisé
Q23 - Résultat de l'intruction mystere2(G, "a", "f")
Q24 - Ce programme permet-il au randonneur de trouver le chemin de difficulté
cumulée
minimale ? Vous justifierez votre réponse.
Q25 - Tableau ci-dessous à compléter
Étape
Initialisation
1
2
3
4
5
sTraite
a
c
b
a
0, a
0, a
0, a
0, a
0, a
0, a
b
X
3, a
3, a
3, a
3, a
3, a
distance
c
d
X
X
2, a 4, a
2, a 4, a
2, a 4, a
2, a
2, a
e
X
X
X
8, b
f
X
X
X
X
aVisiter
["a"]
["b", "c", "d"]
["b", "d"]
["d", "e"]
Q26 - Compléter les lignes 8, 9, 10 et 15 du code
Ligne 8 :
Ligne 9 :
Ligne 10 :
Ligne 15 :
Q27 - Proposition pour diminuer le nombre de tests d'appartenance à une liste
de l'algorithme de Dijkstra
Numéro
d'inscription
Nom : ____________________________________
Numéro
de table
Prénom : _________________________________
Né(e) le
Emplacement
Filière :
Épreuve de :
QR Code
Session : 2025
PSI
INFORMATIQUE
Consignes
· Remplir soigneusement l'en-tête de chaque feuille avant de commencer à
composer
· Rédiger avec un stylo non effaçable bleu ou noir
· Ne rien écrire dans les marges (gauche et droite)
· Numéroter chaque page (cadre en bas à droite)
· Placer les feuilles A3 ouvertes, dans le même sens et dans l'ordre
PSI5IN
Q28 - Liste des sommets visités :
- par l'appel dijkstra(G1, "a1", "j1")
- par l'appel dijkstra(G1, "j1", "a1")
Q29 - Dernière ligne de chacun des tableaux ci-dessous à compléter.
Étape
Init.
1
2
3
4
Traité
a, F
f, B
e, B
Étape
Init.
1
2
3
4
a
0, a | , f
0, a | , f
0, a | , f
0, a | , f
|
Fmin
0
2
2
2
b
, a | , f
3, a | , f
3, a | , f
3, a | 6, e
|
Bmin
0
0
1
2
BFmin
8
6
distanceF | distanceB
c
d
, a | , f , a | , f
2, a | , f 4, a | , f
2, a | , f 4, a | 4, f
2, a | , f 4, a | 2, e
|
|
aVisiterF
["a"]
["b", "c", "d"]
["b", "c", "d"]
["b", "c", "d"]
e
, a | , f
, a | , f
, a | 1, f
, a | 1, f
|
aVisiterB
["f"]
["f"]
["d", "e"]
["d", "b"]
f
, a | 0, f
, a | 0, f
, a | 0, f
, a | 0, f
|
NE RIEN ÉCRIRE DANS CE CADRE
Q30 - Justification de la proposition pour trouver le chemin de longueur
minimale
Q31 - Compléter les lignes 4, 5, 13, 21, 22 et 23 de la fonction
dijkstra_bidirectionnel
Ligne 4 :
Ligne 5 :
Ligne 13 :
Ligne 21 :
Ligne 22 :
Ligne 23 :
Q32 - Démonstration que si appartient à dejaVisitesF ou dejaVisitesB
Q33 - Existence de i0 tel que si0 a été visité à une étape forward et si0 +1 à
une étape backward
Q34 - Correction partielle de l'algorithme de Dijstra bidirectionnel
FIN