CPGE Mohammedia 2020-2021
2TSI3 - INFORMATIQUE - Programmation Python [Link]
Devoir surveillé n◦ 1
Trimestre 1
PROBLÉME 1 : Les Arbres Généalogiques
Le but de ce problème est de modéliser (et programmer quelques fonctionnalités sous Python)
une structure élémentaire représentant un arbre généalogique. On commence par représenter
l’arbre sous forme d’un graphe : en haut de l’arbre se situe l’ancêtre commun à tous les
membres de l’arbre généalogique, et chaque membre de l’arbre est relié à chacun de ses en-
fants. Par souci de simplicité, les conjoints ne sont pas représentés dans l’arbre. On suppose
également qu’il s’agit d’un arbre descendant où on représente sur quelques générations la
descendance issue d’un unique ancêtre commun. Ainsi, chaque membre de l’arbre est relié
vers le haut à une unique personne (qu’on appellera simplement son père, sans se préoccuper
du sexe des différents membres de l’arbre), à l’exception de l’ancêtre commun tout en haut
de l’arbre qui n’a pas de père, et vers le bas à tous ses enfants (dont le nombre est un entier
pouvant évidemment être nul, et pour lequel on ne fixera pas de borne supérieure). Prenons
un exemple pour plus de clarté :
L’ancêtre commun sera toujours numéroté 0, le reste de la numérotation peut par contre être
faite dans n’importe quel ordre (mais doit utiliser les entiers entre 0 et n − 1, où n’est le
nombre total de membres dans l’arbre). Ici, cet ancêtre a deux enfants (numérotés 3 et 8). Le
membre 3 n’a pas d’enfants, mais 8 en a trois (numérotés 6, 1 et 5) etc. On a ici fait un arbre
sur trois générations (on considère que l’ancêtre appartient à la génération 0, ses enfants à la
1
génération 1, etc). La structure de l’arbre généalogique est “ entièrement déterminée par la
donnée du père de chacun de ses membres (on décrète par convention que l’ancêtre 0 a pour
père le numero − 1qui ne correspond à personne dans l’arbre). Ainsi, on peut représenter
l’arbre précédent par le tableau à double entrée suivant :
Membre 0 1 2 3 4 5 6 7 8
père -1 8 1 ? ? ? ? ? ?
En Python, on représentera l’arbre sous forme d’une liste d’entiers contenant simplement la
deuxième ligne du tableau précédent (autrement dit la liste des pères des membres de l’arbre,
par ordre de numéro de membre). Ainsi, la liste Python représentant notre arbre exemple
sera la liste :
arbre=[-1,8,1, ?, ?, ?, ?, ?, ?].
Question1 : Compléter le tableau précédent et donner la liste arbre
complète.
Question2 : Tracer l’arbre généalogique correspondant à la liste arbre2=[-
1,2,8,2,5,1,1,8,0]. Combien de générations sont présentes sur cet arbre ?
Commençons par préciser un peu de vocabulaire sur nos arbres généalogiques : nous avons
déjà défini les termes d’ancêtre (l’élément en haut de l’arbre), de père et d’enfant, et de
génération. Plus généralement, un élément a de l’arbre est un descendant d’un autre élément
b si on peut passer de a à b par un chemin entièrement descendant dans l’arbre (autrement
dit, b est un enfant de a, ou un enfant d’un des enfants de a, etc). On convient qu’un élément
est toujours son propre descendant.
Question3 : Écrire une fonction Python pere(l,a) déterminant le père de
l’élément a dans la liste l (qui sera supposée représenter un arbre généalogique).
Exemple : pere(arbre,5) doit retourner la valeur 8.
Question4 : Écrire une fonction Python enfants(l,a) déterminant la
liste des enfants de l’élément a dans la liste l.
Exemple : enfants(arbre,8) doit retourner la liste [1,5,6].
Question5 : Écrire une fonction Python generation(l,a) déterminant à
quelle génération appartient l’élément a dans la liste l
Exemple : generation(arbre,6) doit retourner la valeur 2.
Question6 :Écrire une fonction Python nbredescendants(l,a) déterminant
le nombre de descendants de l’élément a dans la liste l (on pourra commencer
par écrire une fonction descendant(l,i,j) déterminant si j est un descendant
de i dans la liste l ).
Question 7 : Écrire une fonction Python nbregenerations(l) déterminant
2
le nombre de générations présentes dans l’arbre représenté par la liste l.
Exemple : nbregenerations(arbre) doit retourner la valeur 3.
Continuons avec le vocabulaire : si a et b sont deux membres d’un arbre
généalogique, leur plus proche ancêtre est l’élément de l’arbre appartenant
à la génération la plus grande ayant pour descendants à la fois a et b (un
tel plus proche ancêtre existe toujours, et il est même unique). On définit la
distance de a à b comme étant la longueur du plus court chemin menant de
a à b dans l’arbre généalogique. Ce chemin est toujours celui partant de a et
remontant jusqu’au plus proche ancêtre commun, puis redescendant jusqu’à b
(ainsi, deux éléments qui sont les fils d’une même personne seront à distance
2).
Question 8 :Écrire une fonction Python plusprocheancetre(l,a,b) déterminant
le plus proche ancêtre commun de a et b dans la liste l (on pourra commencer
par traiter le cas où a et b sont de la même génération).
Exemple : plusprocheancetre(arbre,6,4) doit retourner la valeur 8.
Question 9 : Écrire une fonction Python distance(l,a,b) déterminant la
distance entre a et b dans la liste l.
Exemple : distance(arbre,3,7) doit retourner la valeur 4.
Question 10 : Écrire une fonction Python genealogique(l) qui détermine
si une liste d’entiers en Python (quelconque) est une liste représentant un
arbre généalogique ou non.
Exemple : genealogique([-1,3,4,4,1,0]) doit retourner la valeur False.
Exercice : Implémentation d’une file d’attente
Le type abstrait de données ”files d’attente” est une structure linéaire de
stockage munie des primitives suivantes :
— est f ile vide(f ) : renvoie Vrai si la file f est vide, Faux sinon ;
— f ile vide() : renvoie la file vide ;
— ajouter(x, f ) : ajoute le client x à la fin de la file ;
— suivant(f ) : renvoie le client en tête de la file non vide f et le supprime
3
de f.
Question 1 :
1. Proposer une implémentation des fonctions ci-dessus, en Python, où la
file est stockée dans une simple liste.
2. Évaluer la complexité des fonctions ajouter et suivant.
Pour obtenir une complexité en temps constant (ou temps constant amorti)
des deux fonctions ajouter et suivant, on se propose de stocker une file à l’aide
de deux piles :
— la première contient le début de la file, le premier client à servir se
trouvant au sommet ;
— la deuxième contient la fin de la file, le dernier client entré se trouvant
au sommet.
Question 2 :
1. Mettre en œuvre ce principe en Python ; concrètement, la file f pourra
être définie comme une liste de deux piles [p0,p1] ;
2. Expliquer son intérêt du point de vue de la complexité.
3. Écrire une fonction python affiche file(f ) qui permet l’affichage du
contenu de la file passée en paramètre.
