SESSION 2025 PC5IN ÉPREUVE MUTUALISÉE AVEC E3A-POLYTECH ÉPREUVE SPÉCIFIQUE - FILIÈRE PC ____________________ 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 lan- gage (les brouillons ne sont pas acceptés). La réponse ne doit pas se limiter à la rédaction de l’algorithme sans explication, les pro- grammes 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 -- 1 of 16 -- 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 ) : # l i s t e d ’ i n s t r u c t i o n s Introduction Lors d’une randonnée, des applications disponibles sur smartphones permettent d’enregis- trer 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 -- 2 of 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 entier, identifiant de la randonnée ; Titre chaîne de caractères, titre de la randonnée ; Type chaîne de caractères du type de l’activité : ”Pied”, ”VTT”, ”Cheval” ; Lieu chaîne de caractères, coordonnées GPS du point de départ ; Distance flottant, longueur en kilomètres de la randonnée ; DenP entier, dénivelé positif en mètres ; DenN entier, dénivelé négatif en mètres ; Duree entier, durée en minutes de la randonnée ; Niveau entier compris entre 1 et 5 (1 : facile à 5 : extrême), difficulté ; IdAuteur entier, identifiant de l’auteur de la randonnée ; Trace chaîne de caractères, lien internet vers la trace GPX. La table Auteur contenant : Id entier, identifiant de l’auteur (le randonneur) ; Nom chaîne de caractères, nom de l’auteur ; Prenom chaîne de caractères, prénom de l’auteur ; Pseudo chaîne de caractères, pseudo de l’auteur ; Mail 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 -- 3 of 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 expri- mé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 trai- tement 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 , 261.00) # p o i n t de d e p a r t p1 = (43.331055 , −1.627895 , 267.20) # p o i n t i n t e r m e d i a i r e p2 = (43.331047 , −1.627927 , 267.79) # p o i n t i n t e r m e d i a i r e p3 = (43.331040 , −1.627966 , 268.39) # p o i n t d a r r i v e e i t i = [ p0 , p1 , p2 , p3 ]# i t i n e r a i r e 4/16 -- 4 of 16 -- 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éri- dien 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 , 261.00) # 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 + a l t 6 re tu rn ( 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 >>> p0 = ( 4 7 . 8 7 4 1 , 1.8758 , 100) 2 >>> p1 = ( 4 7 . 8 7 4 4 , 1.8759 , 102) 3 >>> p2 = ( 4 7 . 8 7 4 8 , 1.8761 , 110) 4 >>> p3 = ( 4 7 . 8 7 5 0 , 1.8759 , 108) 5 >>> I 1 = [ p0 , p1 , p2 , p3 ] 6 >>> mystere ( I 1 ) 5/16 -- 5 of 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’alti- tude constante mais que le GPS effectue des mesures erronées pour donner une liste d’alti- tudes é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 -- 6 of 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 effec- tué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’al- titude 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 l a t _ r e f = [ ] 2 l o n g _ r e f = [ ] 3 f o r ( l a t , l ong ) i n dem : 4 l a t _ r e f . append ( l a t ) 5 l o n g _ r e f . append ( long ) 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 -- 7 of 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 == [ ] : return y 3 i f y == [ ] : return 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 = a u x i l i a i r e ( x , y ) 9 z . append ( v a l ) 10 re tu rn z 11 12 def p r i n c i p a l ( x ) : 13 i f len ( x ) <= 1 : 14 re turn 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 re turn 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 -- 8 of 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 i n d _ f i n = . . . . . . 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 i n d _ f i n = . . . . . 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 re turn . . . . . 16 else : 17 re turn . . . . . 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 rem- placera 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 -- 9 of 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é. a b e c d f 3 5 2 4 2 1 1 4 4 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 = d i c t ( ) G[ ’ a ’ ] = { ’ b ’ :3 , ’ c ’ :2 , ’ d ’ :4} G[ ’ b ’ ] = { ’ a ’ :3 , ’ d ’ :2 , ’ e ’ :5} G[ ’ c ’ ] = { ’ a ’ :2 , ’ d ’ :4} G[ ’ d ’ ] = { ’ a ’ :4 , ’ b ’ :2 , ’ c ’ :4 , ’ e ’ :1 , ’ f ’ :4} G[ ’ e ’ ] = { ’ b ’ :5 , ’ d ’ :1 , ’ f ’ :1} G[ ’ f ’ ] = { ’ d ’ :4 , ’ e ’ :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 -- 10 of 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 ) −> tuple : 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 = f l o a t ( ’ i n f ’ ) # v a l e u r r e p r é s e n t a n t l ’ i n f i n i 14 s I n t e r = s T r a i t e 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 d i f f C h e m i n = d i f f C h e m i n + d 21 chemin . append ( s I n t e r ) 22 s T r a i t e = s I n t e r 23 re tu rn 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’in- diquer 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éa- lise 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 -- 11 of 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 = f l o a t ( ” 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 : # parcours 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 = d i c o [ s ] [ 0 ] 6 s T r a i t e = s 7 re tu rn 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 d i s t a n c e [ 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 re tu rn d i s t a n c e 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 -- 12 of 16 -- 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. 1 # 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 : 2 s I n i t , s F i n = ” a ” , ” f ” 3 d i s t a n c e = d i j k s t r a (G, s I n i t , sFin ) 4 5 # 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 6 s = s F i n 7 chemin = [ s ] 8 while . . . . . . . . : 9 . . . . . . . . . . 10 . . . . . . . . . . 11 # On remet l e chemin dans l ’ o r d r e du dé but vers l a f i n 12 chemin . r e v e r s e ( ) 13 14 p r i n t ( ” Un chemin de ” , s I n i t , ” à ” , sFin , ” e s t : ” , chemin ) 15 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. a1 c1 g1 j1 b1 f1 e1 d1 h1 i1 1 1 1 1 1 1 1 1 1 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 -- 13 of 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’ar- rivé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 actuali- sé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’arri- vé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 ap- pelle 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 -- 14 of 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 re- cherches 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 distanceB = { 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 distanceB [ 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 distanceB ] ) 23 L = [ . . . . . . . . . . . . . . . . . . . . f o r v i n distanceB i f v i n d i s t a n c e F ] 24 i f L == [ ] : 25 BFmin = f l o a t ( ” i n f ” ) 26 else : 27 BFmin = min ( L ) 28 re tu rn 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 -- 15 of 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, ..., s n = t qui est de distance d strictement inférieure à BFmin. Soit si un sommet de ce chemin. Q32. Montrer que s i appartient soit à dejaVisitesF soit à dejaVisitesB. Q33. En déduire qu’il existe un indice i0 tel que s i0 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. FIN 16/16 I M P R I M E R I E N A T I O N A L E – 25 1051 – D’après documents fournis -- 16 of 16 --