CCINP Informatique PSI 2025

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 


261
2022 -08 -01 T07:37:39 .000Z


267.20001220703125 
2022 -08 -01 T07:37:52 .000Z


267.79998779296875 
2022 -08 -01 T07:37:54 .000Z


268.399993896484375 
2022 -08 -01 T07:37:57 .000Z


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