Aperçu du sujet
EXERCICE 1 (6 points) Cet exercice porte sur les structures de données FILE et PILE, les graphes et les algorithmes de parcours. Partie A Une agence de voyages organise différentes excursions dans une région de France et propose la visite de certaines villes. Ces excursions peuvent être visualisées sur le
EXERCICE 1 (6 points) Cet exercice porte sur les structures de données FILE et PILE, les graphes et les algorithmes de parcours. Partie A Une agence de voyages organise différentes excursions dans une région de France et propose la visite de certaines villes. Ces excursions peuvent être visualisées sur le graphe ci-dessous : les sommets désignent les villes, les arêtes représentent les routes pouvant être empruntées pour relier deux villes et les poids des arêtes représentent des distances, exprimées en kilomètre. Figure 1. Graphe pondéré 1. Déterminer le plus court chemin allant du sommet Mp au sommet Nc et préciser la longueur, en kilomètres, de ce chemin. Aucune justification n’est attendue. On souhaite toujours se rendre du sommet Mp au sommet Nc mais en visitant le minimum de villes. 2. Déterminer les deux chemins possibles. 24-NSIJ2PO1 Page : 2 / 15 Partie B L’agence souhaite proposer un itinéraire permettant de visiter toutes les villes. On appelle G le graphe non pondéré ci-dessous. Figure 2. Graphe non pondéré On choisit d’implémenter un graphe par listes d’adjacence, à l’aide d’un dictionnaire, en langage Python, dont : • les clés sont les sommets du graphe ; • la valeur associée à une clé est la liste des voisins de ce sommet clé. Les sommets sont de type . str 3. Donner l’implémentation, en langage Python, du graphe de la figure 2. Le dictionnaire obtenu sera stocké dans une variable nommée . G Afin de faciliter la notation manuscrite ainsi que la lisibilité, écrire chaque couple clé/valeur sur une nouvelle ligne. On considère une file. 4. Indiquer la signification des lettres dans les acronymes LIFO et FIFO. 5. Indiquer l’acronyme utilisé pour désigner la structure de file. 24-NSIJ2PO1 Page : 3 / 15 Voici, en langage Python, les opérations pouvant être effectuées sur une telle file : • : renvoie une file vide ; creerFile() • : renvoie si la file est vide et sinon ; estVide(F) True F False • : ajoute l’élément dans la file ; enfiler(F, e) e F • : renvoie l’élément à la tête de la file en le retirant de la file . defiler(F) F F On donne la fonction ci-dessous. Cette fonction prend en paramètres un parcours dictionnaire représentant un graphe sous la forme de listes d’adjacence, et graphe une chaîne de caractères représentant un sommet du graphe. sommet 1 def parcours(graphe, sommet): 2 f = creerFile()