Aller au contenu

Option Sciences du Numérique
Filière MPI


Concours EPITA - IPSA - ESME⚓︎

Avertissement

Ce document n'est pas un corrigé du sujet officiel. D'ailleurs les parties de programmation se feront toutes en Python, et non en OCaml et C comme demandé.

I. Mots de Dyck1 et arbres binaires⚓︎

De façon informelle, un mot de Dyck sur un langage \(D_k\) est un mot bien parenthésé sur un alphabet à \(k\) paires de délimiteurs.

Quelques mots
  • () est un mot de \(D_1\)
  • (()(){}){} est un mot de \(D_2\)
  • (() n'est pas un mot de Dyck (il manque une parenthèse fermante)
  • {}(()[])[) n'est pas un mot de Dyck (le dernier crochet est fermé par une parenthèse)

Sur les sites de la communauté e-nsi on trouve des exercices relatifs à ces mots de Dyck et arbres binaires ou des annales de BAC :

Dans le sujet, on s'intéresse à \(D_1\) sur l'alphabet \({a, b}\) (\(a\) joue le rôle d'un délimiteur ouvrant, \(b\) est le fermant correspondant). Le mot vide est noté \(\varepsilon\).

Question 1⚓︎

Reconnaître un mot de \(D_1\)

Parmi les mots ci-dessous, lesquels sont des mots de Dyck ?

  • \(\varepsilon\)
  • \(aabbbaab\)
  • \(aaab\)
  • \(abab\)
  • \(aaabbb\)

Parmi les mots ci-dessous, lesquels sont des mots de Dyck ?

  • \(\varepsilon\), le mot vide est bien un mot de Dyck
  • aabbbaab, le préfixe \(aabbb\) comporte plus de \(b\) que de \(a\)
  • aaab, il y a plus de \(a\) que de \(b\)
  • \(abab\)
  • \(aaabbb\)

Question 2⚓︎

Vérifier un mot de Dyck

Écrire une fonction booléenne verifie_dyck qui prend un mot \(w\) en paramètre et renvoie True si \(w\in D_1\) et False sinon.

Le principe est simple : on parcourt le mot de gauche à droite et pour chaque caractère rencontré, on compte \(+1\) s'il s'agit d'un \(a\) et \(-1\) si c'est un \(b\). Si on rencontre un autre caractère on renvoie False. Si à un moment du parcours le décompte devient négatif, on renvoie False (cela signifie qu'on a trouvé un préfixe qui comporte plus de \(b\) que de \(a\)). À la fin, si notre décompte est à \(0\), le mot est bien un mot de Dyck, sinon ce n'en est pas un.

def verifie_dyck(mot):
    decompte = 0
    for lettre in mot:
        if lettre == 'a':
            decompte += 1
        elif lettre == 'b':
            decompte -= 1
        else:
            return False
        if decompte < 0:
            return False
    return decompte == 0

Question 3⚓︎

Décomposition

Tout mot \(m\) non vide de \(D_1\) se décompose de façon unique sous la forme \(aubv\)\(u\) et \(v\) sont des mots de \(D_1\). On admet la propriété suivante : \(aub\) est le plus petit préfixe non vide de \(m\) comportant autant de \(a\) que de \(b\).

Décomposer un mot de Dyck

Donner sans démonstration la décomposition des mots suivants : \(ab\), \(aababb\), \(ababab\), \(aabbab\)

  • \(ab = a\varepsilon b\varepsilon\), \(u\) et \(v\) sont le mot vide
  • \(aababb = a(abab)b\varepsilon\), \(u = abab\) et \(v\) est vide
  • \(ababab = a\varepsilon b(abab)\), \(u\) est vide et \(v = abab\)
  • \(aabbab = a(ab)b(ab)\), \(u = v = ab\)

Question 4⚓︎

Une fonction pour décomposer

Écrire une fonction decompo_dyck qui prend un mot \(m\) de \(D_1\) non vide (on ne vérifiera pas que \(m\in D_1\)) et qui renvoie le couple \((u, v)\) de la décomposition \(aubv\) de \(m\).

La méthode consiste à parcourir le mot en partant de la gauche pour découvrir le premier préfixe comportant autant de \(a\) que de \(b\). On renvoie alors ce préfixe privé de ses extrémités et le suffixe du mot. Pour ce faire, on part de la première lettre et, comme pour la vérification, on compte les \(a\) et les \(b\). Tant que le nombre de \(a\) est différent du nombre de \(b\) on avance.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def decompo_dyck(mot):
    nb_a, nb_b = 0, 0
    i = 0
    while i < len(mot) and (nb_a == 0 or nb_a != nb_b):
        if mot[i] == 'a':
            nb_a += 1
        elif mot[i] == 'b':
            nb_b += 1
        i += 1
    return mot[1:i-1], mot[i:]
Application

On retrouve les résultats de la question 3 :

>>> decompo_dyck('ab')
('', '')
>>> decompo_dyck('aababb')
('abab', '')
>>> decompo_dyck('ababab')
('', 'abab')
>>> decompo_dyck('aabbab')
('ab', 'ab')

Question 5⚓︎

Dans les dernières questions, il s'agit de représenter les mots de \(D_1\) par des arbres binaires stricts (non vide et qui possède \(0\) ou \(2\) sous-arbres). Il existe une bijection naturelle entre les deux ensembles :

  • au mot vide on associe l'arbre réduit à une feuille ;
  • à un mot non vide qui se décompose en \(aubv\) on associe l'arbre dont le sous-arbre à gauche est celui de \(u\) et le sous-arbre à droite est celui de \(v\).

Pour reproduire les quelques codes présents dans cette partie, et notamment voir les arbres dessinés, vous pouvez télécharger le script suivant.

Faire tourner les exemples

Pour manipuler et visualiser les arbres de ce sujet, vous pouvez télécharger et utiliser (dans un notebook jupyter) le script suivant :

bin_tree.py

Ce script nécessite un module maison et les notebooks jupyter. Voici les pré-requis :

Attention : il existe d'autres petits modules aux noms proches : simple-graph, pygraph.

Dessiner un arbre de Dyck

Dessiner l'arbre associé au mot \(aababb\).

Réponse

L'arbre brut :

q5 brut

Les feuilles sont colorées en bleu, elles représentent le mot vide \(\varepsilon\).

q5

Pour dessiner cet arbre nous avons du coder la fonction mot_a_arbre de la question suivante, que nous ne dévoilons pas tout de suite. Cette fonction construit un ArbreBin, défini dans le script bin_tree.py, à partir d'un mot de Dyck.

Puis nous créons un objet de visualisation (ArbreViz qui s'appuie sur les graphes du module simple-pygraph) qui prend en premier paramètre un arbre binaire et en second un coefficient qui gère l'écartement des branches de l'arbre (\(1\) est la valeur par défaut).

>>> M1 = 'aababb'
>>> A1 = mot_a_arbre(M1)
>>> AV1 = ArbreViz(A1, 0.3)
>>> AV1.vue  # pour voir l'arbre dans le notebook

On obtient alors la version brute. On peut supprimer les étiquettes \(\varepsilon\), colorier ces mêmes feuilles et réduire un peu la taille :

>>> AV1.small()
>>> AV1.colore_feuille('𝜀')
>>> AV1.zoom(0.4)
>>> AV1.vue 

Questions 6 et 7⚓︎

Il s'agit d'écrire les fonctions qui permettent de passer d'un mot à son arbre binaire et vice-versa. On s'appuie sur la structure récursive.

D'un mot à l'arbre binaire

Écrire une fonction mot_a_arbre qui renvoie l'arbre binaire strict associé à un mot de \(D_1\) (on né vérifiera pas que le mot est bien un mot de Dyck).

Réponse
def mot_a_arbre(mot):
    if mot == '':
        return ArbreBin('𝜀')
    else:
        u, v = decompo_dyck(mot)
        arbre_u = mot_a_arbre(u)
        arbre_v = mot_a_arbre(v)
        return ArbreBin('', arbre_u, arbre_v)
Application

Nous avons déjà vu une application sur le mot M1 = 'aababb'. Voyons sur un autre mot :

>>> M2 = 'aabbab'
>>> A2 = mot_a_arbre(M2)
>>> AV2 = ArbreViz(A2, 0.35)
>>> AV2.small()
>>> AV2.colore_feuille('𝜀')
>>> AV2.zoom(0.4)
>>> AV2.vue

q5b

Reconstruire le mot à partir de son arbre

Écrire une fonction arbre_a_mot qui réalise l'opération inverse de la fonction précédente.

Réponse
def arbre_a_mot(arbre):
    if arbre.feuille():
        return ''
    else:
        u = arbre_a_mot(arbre.gauche)
        v = arbre_a_mot(arbre.droite)
        return 'a' + u + 'b' + v
Applications

À partir des arbres A1 et A2 nous retrouvons nos mots de Dyck :

>>> arbre_a_mot(A1)
'aababb'
>>> arbre_a_mot(A2)
'aabbab'

Conclusion⚓︎

Ce premier exercice d'un concours d'entrée en école d'ingénieur est tout à fait abordable en Terminal NSI sur des notions qui peuvent être évaluées au BAC. C'est rassurant de pouvoir montrer de tels exemples aux élèves.


  1. Langages de Dyck par Wikipédia