TP Python – Arborescences et graphes en Python

BTS SIO SISR 2e année – Pour aller plus loin – S10

Note

Comment ce TP fonctionne. Chaque exercice a un éditeur Python intégré à la page (il s'exécute dans ton navigateur, rien à installer). Avant de lancer, écris sur ta feuille ce que tu anticipes (« J'anticipe »). Puis lance et compare. Le bouton Valider exécute des tests : un test réussi ne dispense pas de comprendre pourquoi.

Exercice A – Taille d'un dossier

Écris taille(a) qui renvoie la taille totale d'une arborescence (dictionnaires imbriqués ; un fichier est un entier). isinstance(a, int) teste si a est un fichier.

J'anticipe. Quelle taille attends-tu pour l'arborescence du cours (exercice 1) ?

###

assert taille({"docs": {"rapport.txt": 120, "notes.txt": 30, "archives": {"2023.zip": 500, "2024.zip": 650}}, "photo.png": 800, "config.ini": 5}) == 2105bksl-nlassert taille(120) == 120bksl-nlassert taille({}) == 0bksl-nlassert taille({"a": {"b": {"c": 7}}}) == 7bksl-nlbksl-nl ∞/∞

def taille(a):bksl-nl """Taille totale d'une arborescence (entier = fichier, dict = dossier)."""bksl-nl ...bksl-nlbksl-nl

Exercice B – Nombre de fichiers

Écris nb_fichiers(a) qui renvoie le nombre de fichiers (entiers) de l'arborescence.

###

assert nbpy-undfichiers({"docs": {"rapport.txt": 120, "notes.txt": 30, "archives": {"2023.zip": 500, "2024.zip": 650}}, "photo.png": 800, "config.ini": 5}) == 6bksl-nlassert nbpy-undfichiers(120) == 1bksl-nlassert nbpy-undfichiers({}) == 0bksl-nlassert nbpy-undfichiers({"a": {"b": 1, "c": 2}, "d": 3}) == 3bksl-nlbksl-nl ∞/∞

def nbpy-undfichiers(a):bksl-nl """Nombre de fichiers d'une arborescence."""bksl-nl ...bksl-nlbksl-nl

Exercice C – Profondeur

Écris profondeur(a) : 0 pour un fichier ; pour un dossier, 1 plus la plus grande profondeur de ses éléments (1 pour un dossier vide).

J'anticipe. Quelle profondeur attends-tu pour l'arborescence du cours (exercice 2) ?

###

assert profondeur({"docs": {"rapport.txt": 120, "notes.txt": 30, "archives": {"2023.zip": 500, "2024.zip": 650}}, "photo.png": 800, "config.ini": 5}) == 3bksl-nlassert profondeur(120) == 0bksl-nlassert profondeur({}) == 1bksl-nlassert profondeur({"a": 1}) == 1bksl-nlassert profondeur({"a": {"b": {"c": {}}}}) == 4bksl-nlbksl-nl ∞/∞

def profondeur(a):bksl-nl """0 pour un fichier ; 1 + max des profondeurs pour un dossier (1 si vide)."""bksl-nl ...bksl-nlbksl-nl

Je comprends. Quel est le variant de ta fonction ?

Exercice D – Liste des chemins

Écris chemins(a, prefixe="") qui renvoie la liste des chemins de tous les fichiers, sous la forme "docs/archives/2023.zip", dans l'ordre des clés.

J'anticipe. Écris la liste attendue pour l'arborescence du cours (exercice 3).

###

assert chemins({"docs": {"rapport.txt": 120, "notes.txt": 30, "archives": {"2023.zip": 500, "2024.zip": 650}}, "photo.png": 800, "config.ini": 5}) == ['docs/rapport.txt', 'docs/notes.txt', 'docs/archives/2023.zip', 'docs/archives/2024.zip', 'photo.png', 'config.ini']bksl-nlassert chemins({}) == []bksl-nlassert chemins({"a": 1}) == ['a']bksl-nlassert chemins({"d": {"e": {"f": 2}}}) == ['d/e/f']bksl-nlbksl-nl ∞/∞

def chemins(a, prefixe=""):bksl-nl """Liste des chemins de tous les fichiers d'un dossier a."""bksl-nl ...bksl-nlbksl-nl

Exercice E – Parcours en profondeur

Écris dfs(g, sommet, visites=None) qui renvoie la liste des sommets dans l'ordre de visite d'un parcours en profondeur depuis sommet. g associe chaque sommet à la liste de ses voisins. Ne repasse jamais par un sommet déjà visité.

J'anticipe. Écris l'ordre de visite attendu pour le graphe de l'exercice 4.

###

assert dfs({"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": ["A"]}, 'A') == ['A', 'B', 'D', 'C', 'E']bksl-nlassert dfs({"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": ["A"]}, 'B') == ['B', 'D']bksl-nlassert dfs({"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": ["A"]}, 'D') == ['D']bksl-nlassert dfs({'X': ['X']}, 'X') == ['X']bksl-nlassert dfs({'R1': ['R2', 'R3'], 'R2': ['R4'], 'R3': ['R4'], 'R4': [], 'R5': ['R1']}, 'R5') == ['R5', 'R1', 'R2', 'R4', 'R3']bksl-nlbksl-nl ∞/∞

def dfs(g, sommet, visites=None):bksl-nl """Sommets dans l'ordre d'un parcours en profondeur depuis sommet."""bksl-nl ...bksl-nlbksl-nl

Je comprends. Que se passerait-il sans le test sur visites ?

Exercice F – Machines atteignables

Écris atteignables(g, depart) qui renvoie la liste triée des sommets atteignables depuis depart (lui compris). Tu peux réécrire dfs dans l'éditeur.

J'anticipe. Quelles machines sont atteignables depuis R1 (exercice 6) ?

###

assert atteignables({'R1': ['R2', 'R3'], 'R2': ['R4'], 'R3': ['R4'], 'R4': [], 'R5': ['R1']}, 'R1') == ['R1', 'R2', 'R3', 'R4']bksl-nlassert atteignables({'R1': ['R2', 'R3'], 'R2': ['R4'], 'R3': ['R4'], 'R4': [], 'R5': ['R1']}, 'R5') == ['R1', 'R2', 'R3', 'R4', 'R5']bksl-nlassert atteignables({'A': []}, 'A') == ['A']bksl-nlassert atteignables({'A': ['B'], 'B': ['A']}, 'A') == ['A', 'B']bksl-nlbksl-nl ∞/∞

def dfs(g, sommet, visites=None):bksl-nl if visites is None:bksl-nl visites = []bksl-nl visites.append(sommet)bksl-nl for voisin in g[sommet]:bksl-nl if voisin not in visites:bksl-nl dfs(g, voisin, visites)bksl-nl return visitesbksl-nlbksl-nldef atteignables(g, depart):bksl-nl """Liste triee des sommets atteignables depuis depart."""bksl-nl ...bksl-nlbksl-nl