S10 – Structures arborescentes et parcours en profondeur
| Élément | Détail |
|---|---|
| Niveau | BTS SIO option SISR, 2e année – complément : pour aller plus loin |
| Séance | S10 (séance 10 sur 19) – Phase 2 |
| Durée | 4 heures |
| Parcours | Cœur – Arbres et parcours : prérequis de S11 et S16. Voir le parcours cœur et complément. |
| Chapitre du programme | Récursivité – arbres, parcours |
| Prérequis | S08 ; S09 |
| Outils | Papier, calculatrice, éditeur Python intégré au site |
Note
Question qui guide la séance : « Comment parcourir un dossier contenant des sous-dossiers, ou un graphe, sans se perdre ? »
Objectifs
À la fin de la séance, l'étudiant est capable de :
- Représenter une arborescence en Python
- Parcourir récursivement une arborescence
- Calculer taille et profondeur
- Écrire un parcours en profondeur de graphe
- Éviter les cycles
Contenu de la séance
| Document | Rôle |
|---|---|
| Cours | Cours |
| Exercices | Exercices |
| TP Python | TP (éditeur Python intégré) |
| Aide-mémoire | Aide-mémoire |
Déroulé conseillé (4 h)
| Durée | Activité | Format |
|---|---|---|
| 0 h 00 – 0 h 15 | Rappel : récursivité sur listes et chaînes, dichotomie (S08, S09) ; graphes de la 1re année | Oral |
| 0 h 15 – 1 h 15 | Cours : arborescence en dictionnaires imbriqués, parcours récursif, parcours en profondeur d'un graphe | Cours et questions |
| 1 h 15 – 2 h 15 | Exercices | Individuel |
| 2 h 15 – 3 h 45 | TP Python | Individuel |
| 3 h 45 – 4 h 00 | Auto-évaluation | Individuel |
Durées indicatives : la séance dure 4 h ; l'enseignant ajuste selon le rythme du groupe.
Application en informatique
Calculer la taille d'un dossier, lister les fichiers d'une arborescence, savoir quelles machines sont atteignables dans un réseau.
Évaluation
- Feuille d'exercices et scripts du TP validés dans l'éditeur.
- Auto-évaluation « Je sais faire » en fin d'exercices.
Notes pour l'enseignant
- Exemples chiffrés recalculés par programme ; scripts du TP validés (solution réussie, squelette en échec).