Algorithmes et Programmation 2, année 2022

Exercice 1: Explorer un système de fichier

Vous pouvez télécharger ici un script qui génère une arborescence compliquée de fichiers qui contiennent des informations pas très intéressantes.

Vous pouvez regarder comment ça marche!

Pour lancer le script:

python3 TD_ref/genere_arbre.py arbre

il va alors créer dans le repertoire courant un dossier arbre et pleins de sous-dossier.

with open(“nom/du/fichier”) as f: x = f.read() # le contenu du fichier sous forme de chaîne de caractères

import os os.listdir(“chemin/vers/un/dossier”) # retourne la liste des noms de fichiers (chaine de caractères)

os.path.isdir(“chemin/vers/quelque/chose”) # retourne True si c’est un repertoire os.path.isfile(“chemin/vers/quelque/chose”) # retourne True si c’est un fichier

  1. Proposer un algorithme qui compte le nombre de fichiers dans l’arborescence

Attention à ne pas compter les dossiers. Vous pouvez utiliser la commande find chemin/vers/repertoire -type f | wc -l pour compter les fichier en ligne de commande (mais pas en Python!).

  1. Proposez un algorithme qui retourne la profondeur (le nombre maximal de dossier imbriqué) dans l’arborescence.

  2. Proposez un algorithme qui retourne une liste de liste où chaque liste contient les chemins vers fichiers ayant avec le même contenu.

  3. Faites des analyses de complexités de vos implémentations

Exercice 2: Jouer avec les références

On va regarder les objets Pythons \(\mathcal{T}\) définit récursivement ainsi:

D’une certaine manière, les éléments de \(\mathcal{T}\) représentent des arbres. Par exemple:

[[4, 5, 6], 10, [[11, 20, 30], 200, 440]] représente l’arbre suivant:

arbre

La liste des feuilles de l’arbre précédent est [4, 5, 6, 10, 11, 20, 30, 200, 440]

  1. Proposer un algorithme qui prends en entrée un élément de \(\mathcal{T}\) et retourne la liste de ses feuilles en respectant l’ordre.

Que ce passe t’il quand on execute votre code sur l’exemple suivant:

L = [[4, 5, 6], 10, [[11, 20, 30], 200, 440]]
L[2][0].append(L)
  1. Proposer un algorithme qui vérifie qu’un objet python construit uniquement avec des listes et des entiers est bien un objet de \(\mathcal{T}\). C’est-à dire qu’il ne contient de liste incluse dans elle même.

Vous pouvez utiliser la fonction id vu dans le cours


Compiled the: mer. 04 sept. 2024 12:49:46 CEST