Exercice 3 - Graphes · Bac Numérique et Sciences Informatiques Polynésie 2025 (jour 2)

Exercice 3 (8 points)

Dans cet exercice il est question de tableaux, de dictionnaires, de recherche de chemins dans un graphe, de piles, de files et de POO.

On considère une liste de mots de quatre lettres. Par exemple gars, grue, mars, mors, ours, purs, durs...

Deux mots sont voisins s'ils ne diffèrent que d'une seule lettre sans se soucier de l'ordre des lettres dans les mots. Par exemple:

mars et mors sont voisins (on change le a en o);

mors et ours sont voisins (on change le m en u);

grue et ours ne sont pas voisins (il faudrait changer g en o et e en s).

L'exercice consiste à partir d'un mot de départ (par exemple mars) pour atteindre un mot de destination (par exemple ours) en passant de voisins en voisins et en empruntant le moins de voisins possible.

Les mots utilisés, du mot de départ au mot de destination, forment alors le chemin emprunté. Par exemple mars, mors, ours est le chemin qui relie le mot mars au mot ours.

On considère qu'il est toujours possible de trouver un tel chemin.

Partie A: Modélisation par un graphe

3.

Expliquer pourquoi un graphe non orienté est adapté à la situation.

4.

Dessiner le graphe si la liste de mots est: gars, mars, mors, ours et purs.

Partie B: Calcul des distances et des voisins

La distance entre deux mots est le nombre minimum de lettres qu'il faut modifier pour passer de l'un à l'autre. Par exemple, la distance entre mars et mors est 1 tandis que la distance entre grue et ours est 2.

Deux mots sont voisins si et seulement si la distance entre eux vaut 1.

Dans toute cette partie, on dispose d'une variable globale TAB_MOTS, un tableau (type list en Python) dont les éléments sont des chaînes de quatre caractères qui correspondent à des mots.

5.

Recopier et compléter la fonction chaine_vers_tab(mot) ci-dessous. Cette fonction prend en paramètre une chaîne de quatre caractères et renvoie un tableau (type list en Python) dont les éléments sont les caractères de cette chaîne.

6.

Expliquer pourquoi la fonction ci-dessous renvoie effectivement la distance entre les deux mots mot1 et mot2, deux chaînes de quatre caractères:

def distance(mot1, mot2):

tab = chaine_vers_tab(mot1)

for lettre in mot2:

if lettre in tab:

tab.remove(lettre)

return len(tab)

7.

Recopier et compléter la fonction renvoie_voisins(mot) qui renvoie un tableau dont les éléments sont les mots de TAB_MOTS qui sont voisins de mot, une chaîne de quatre caractères, passé en paramètre.

Partie C: Recherche du plus court chemin

On dispose d'une classe File (méthodes est_vide(), defiler(), enfiler(element)) et d'une classe Pile (méthodes est_vide(), depiler(), empiler(element)).

La fonction dic_parent(mot_depart, mot_final) ci-dessous renvoie le chemin sous la forme d'un dictionnaire {sommet parcouru: sommet précédent}:

def dic_parent(mot_depart, mot_final):

file_voisins = File()

parent = {mot_depart: None}

mot = mot_depart

file_voisins.enfiler(mot)

while not file_voisins.est_vide() and not mot == mot_final:

mot = file_voisins.defiler()

for voisin in renvoie_voisins(mot):

if not voisin in parent:

parent[voisin] = mot

file_voisins.enfiler(voisin)

return parent

8.

Poursuivre le déroulement de la fonction pas à pas (avec 'mars' pour mot de départ et 'ours' pour mot final) en détaillant chaque tour de boucle jusqu'à l'issue de la fonction.

9.

Recopier et compléter la fonction renvoie_pile(parent, mot_final) qui renvoie une pile dont le premier élément empilé est le mot final et dont le sommet est le mot de départ.

10.

Recopier et compléter la fonction construit_chemin(ma_pile) qui prend en paramètre une pile de mots et renvoie un tableau contenant les mots du chemin dans le bon ordre.

11.

Coder, en utilisant les fonctions précédentes, la fonction chercher_chemin(mot_depart, mot_final) qui renvoie un tableau constitué des mots du chemin du mot de départ au mot final.