Structures arborescentes

Arbre d'appel

Soit la fonction f dont on donne le code python ci-dessous :

def f(x):
    """int -> None"""
    if x <= 1:
        print("*")
    else:
        f(x - 1)
        print("*"*x)
        f(x - 1)

1. Pourquoi cette fonction peut-elle être qualifiée de récursive ? Justifier précisément votre réponse.

2. 1. Dresser l'arbre d'appel associé à l'exécution de l'instruction f(4).

   2. Quel affichage est réalisé lors de l'appel f(4) ?

3. Soit \(x\) un entier positif. On note \(h\) le nombre de "niveaux" de l'arbre d'appel associé à l'instruction f(x) et \(N\) le nombre de nœuds de cet arbre.

   1. Déterminer \(h\) et \(N\) lorsque \(x = 4\).

   2. Dans le cas général, exprimer \(h\) et \(N\) en fonction de \(x\). Comparer \(h\) et \(N\).

4. Reprendre les questions 2 et 3 avec la fonction g dont on donne le code ci-dessous :

   def g(x):
       """ int -> None """
       if x <= 1:
           print("*")
       else:
           print(g(x - 1)) 
           print(g(x - 2))
           print("*"*x)
   

HTML

On peut représenter le code source d'une page HTML à l'aide d'un arbre. On donne ci-dessous la structure arborescente correspondante au code source d'une page HTML.

On appelle "bloc" une chaîne de caractère du type <balise> ... </balise>.

<div>
  <p>une <em>mise en 
  valeur</em>de mots</p>
  <ul>
    <li>item 1</li>
    <li>item 2</li>
  </ul>
</div>

1. Proposer un code HTML dont la structure correspond à l'arbre ci-dessus.

   

2. 1. Quelle est la balise du nœud racine de cet arbre ?

   2. Quelles sont blocs de la page html qui ne contiennent aucune balise interne ?

   3. De combien de blocs est composée la page html au total ? Quels sont les blocs directement imbriqués dans le bloc article ?

   4. Quel est le nœud de l'arbre qui a le plus d'enfants ?

   5. Combien de paires de balises ouvrantes/fermantes entourent le bloc <h2> ... </h2> de votre code HTML ? Quelles sont-elles ?

   6. Au maximum, combien de balises sont-elles imbriquées les unes dans les autres ?

Arbre de syntaxe

Une phrase en français se fonde sur une structure hiérarchisée, donc non linéaire, et compte différents niveaux d'organisation (des mots, des groupes de mots, de la phrase). Ainsi, dans une première approximation, on peut dire :

• une phrase Ph est constituée d'un groupe nominal GN suivi d'un groupe verbal GV.

• un groupe verbal GV est constitué d'un verbe V puis d'un groupe nominal optionnel (GN) puis d'un groupe prépositionnel optionnel (GP).

• un groupe nominal GN est constitué d'un déterminant optionnel (D) suivi d'un nom N et d'un groupe prépositionnel optionnel (GP).

• un groupe prépositionnel GP est composé d'une préposition P suivie d'un groupe nominal GN.

On synthétise ces règles en (les éléments entre parenthèses sont optionnels) :

1. Ph = GN + GV
2. GV = V + (GN) + (GP)
3. GN = (D) + N + (GP)
4. GP = P + GN

La représentation en arbre permet de voir comment les mots et les groupes de mots s'articulent entre eux.

1. Indiquer sur chaque nœud interne de l'arbre ci-dessus le numéro de la règle de grammaire utilisée.

2. Déterminer les arbres de syntaxe des phrases suivantes :

   1. Son chien mange un os dans la cuisine.

   2. Le professeur de mathématiques corrige le contrôle avec ses élèves.

   Remarque. "son", "un", "la", "cette", "le", "ses" sont des déterminants. "dans", "à" "avec", "de", sont des prépositions.

3. On considère la phrase : John voit l'homme sur la montagne avec un télescope.

   1. Déterminer deux arbres de syntaxe distincts pour représenter cette phrase.

   2. Pourquoi peut-on dire que cette phrase est ambigüe ?

      Grammaticalement, à quoi cela est-il dû ?

Arbre d'expression arithmétique

On peut utiliser des arbres pour représenter et manipuler des expressions mathématiques.

Par exemple, l'expression \(\dfrac{1 + x^2}{1 - 2x}\) peut être représentée par l'arbre ci-contre.

Pour évaluer une expression représentée sous forme d'arbre, on applique l'algorithme suivant :

• si la racine de l'arbre est une feuille, on renvoie la valeur stockée à la racine ;

• sinon, la racine est un opérateur \(\square\) parmi \(+\), \(-\), \(\times\), \(\div\), \(\wedge\). On évalue récursivement le sous-arbre gauche en le nombre \(g\), puis on évalue récursivement le sous-arbre droite en le nombre \(d\). Le résultat de l'évaluation de l'arbre est le résultat de \(g \;\square\; d\).

1. 1. Évaluer les arbres \(\mathcal{A}_1\) et \(\mathcal{A}_2\). À quelle expression mathématique correspondent-ils ?

      

   2. À quelle expression mathématique correspond le troisième arbre ? Déterminer un arbre \(\mathcal{A}'_3\) dont le résultat de l'évaluation est le même que le résultat de l'évaluation de l'arbre \(\mathcal{A}_3\), pour toute valeur de \(a\), \(b\), \(c\), \(d\).

2. À quels arbres correspondent les expressions mathématiques suivantes :

   • \(1 - 3\times 8 + 7\)
   • \(1 - 3\times (8 + 7)\)
   • \((1 - 3)\times 8 + 7\)
   • \((1 - 3)\times( 8 + 7)\)

   Que constate-t-on ?

3. La notation polonaise inverse est un système d'écriture des expressions mathématiques qui utilise un système de pile.

   Pour évaluer une expression, on la parcourt de gauche à droite en plaçant les symboles dans la pile. Si le symbole est un nombre, on ne fait rien de plus. Si le symbole est un opérateur binaire \(\square\), on consomme les deux nombres précédents de la pile \(g\) et \(d\) et on place au sommet de la pile le résultat de \(g\; \square\; d\). À la fin du calcul le résultat de l'opération est le nombre au sommet de la pile.

   1. En précisant les états successifs de la pile à chaque étape du calcul, évaluer les expressions suivantes :

      1. 4 7 + 3 *
      2. 4 7 3 * +
      3. 4 7 3 + *
      4. 2 4 3 × + 7 -

   2. Déterminer une expression écrite en notation polonaise inverse pour chacun des arbres des arbres \(\mathcal{A}_1\), \(\mathcal{A}_2\), et \(\mathcal{A}_3\).

   3. Déterminer une notation polonaise inverse des expressions de la question 2..

   4. Quel est l'avantage de la notation polonaise inverse par rapport à la notation "usuelle" des calculs ?

4. 1. En utilisant le constructeur Arbre vu en TP, instancier trois variables a1, a2 et a3 représentant respectivement les arbres \(\mathcal{A}_1\), $ \mathcal{A}_2$, et \(\mathcal{A}_3\).

   2. À quel parcours d'arbre correspond l'écriture en notation polonaise inverse d'une expression arithmétique ?

   3. Écrire le code python d'une fonction affiche_npi qui étant donné un arbre a représentant une expression arithmétique en affiche la notation polonaise inverse correspondante.

   4. Écrire le code python d'une fonction affiche_infixe qui étant donné un arbre a représentant une expression arithmétique en affiche la représentation "usuelle" (avec des parenthèses).

Arborescence de fichiers

On considère une liste de dossiers et de fichiers ordonnés suivant l'arborescence ci-après.

• home

  • dossier1
    • dossier11
    • dossier12
  • dossier2
    • dossier21
      • fichier211
      • fichier212
    • dossier22

• Représenter cette arborescence sous forme d'arbre étiqueté.

• On souhaite afficher cette arborescence à l'aide d'un algorithme. Quel type de parcours d'arbre doit-on utiliser ?

• Proposer un code Python qui stocke l'arborescence dans une variable A de type Arbre, puis qui en réalise un affichage similaire à celui de l'énoncé. Exécuter votre algorithme à la main puis l'implémenter et le tester.

Arbre généalogique

1. Réaliser votre arbre généalogique jusqu'à la génération de vos grands-parents inclus.

2. On souhaite obtenir l'affichage ci-contre.

   Quel type de parcours d'arbre doit-on alors réaliser ?

   Moi : ... 
   Parent : ..., ... 
   Grand-parents : ..., ..., ..., ...
   

3. Proposer un code Python qui stocke votre arbre généalogique dans une variable de type Arbre puis qui en réalise un affichage similaire à celui demandé. Exécuter votre algoritme à la main puis l'implémenter et le tester.