[[{"text":"
"}],[{"text":"
![\"graphe1.png](\"https://sciencesappliquees.com/images/nsi/graphe1.png\")
","title":"Définitions"},{"edit":"
"}],[{"text":"
![\"graphe1.png](\"https://sciencesappliquees.com/images/nsi/graphe2.png\")
![\"graphe1.png](\"https://sciencesappliquees.com/images/nsi/graphe3.png\")
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
![\"graphe1.png](\"https://sciencesappliquees.com/images/nsi/graphe5.png\")
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
![\"graphe1.png](\"https://sciencesappliquees.com/images/nsi/graphe4.png\")
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
"}],[{"text":"
","title":"Exemples de graphes"},{"edit":"
"}],[{"text":"![](\"https://sciencesappliquees.com/images/snt/itineraire.png\")
Un navigateur GPS implémente un algorithme de recherche de chemin dans un tel graphe. Il prend en compte des informations supplémentaires, telles que la longueur des routes, la vitesse maximale autorisée, la présence de péages, etc pour calculer des chemins qui minimisent la distance totale, le temps de trajet, etc. La recherche d'un tel chemin minimal n'est pas au programme de terminale.
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"![\"Labyrinthe\"](\"https://omnilogie.fr/images/O/0e6e1fcc31f8281e7d1445bd64714aa2.jpg\")
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"![\"graphe1.png](\"https://sciencesappliquees.com/images/nsi/arbre1.png\")
","title":""},{"edit":"
"}],[{"text":"
","title":"Représentation d'un graphe en Python"},{"edit":"
"}],[{"text":"
![\"graphe1.png](\"https://sciencesappliquees.com/images/nsi/graphe6.png\")
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":"Exemple d'algorithme sur les graphes"},{"edit":"
"}],[{"text":"
","title":"Conclusion"},{"edit":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"![\"graphe1.png](\"https://sciencesappliquees.com/images/nsi/graphe7.png\")
"}],[{"text":"
"},{"solution":"![\"graphe1.png](\"https://sciencesappliquees.com/images/nsi/graphe8.png\")
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice","tagtitle":"h1"},{"edit":"
"},{"solution":"
"}],[{"text":"
Tester avec:
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
Tester avec:
","title":"Exercice","tagtitle":"h1"},{"edit":"
"},{"solution":"
"}],[{"text":"
Tester avec:
","title":"Exercice"},{"edit":"
"},{"solution":"
"}]]
Alice est sur Wikipedia, en train de lire la page Algorithme du lièvre et de la tortue. Trois clics plus tard, elle se surprend à lire la page Cathédrale Saint-Étienne de Metz et se demande soudain comment elle en est arrivée là.
D'autres questions se précipitent alors dans sa tête.
Est-il possible de revenir à la page Algorithme du lièvre et de la tortue en suivant uniquement des liens entre articles de Wikipedia?
Combien de clics seraient nécessaires
pour cela?
Certains article de Wikipedia sont-ils tout simplement inatteignables à partir de cette page?
Immédiatement, Alice comprend qu'il lui faudra écrire un programme si elle veut répondre à de telles questions, car tenter d'y répondre par une exploration manuelle lui prendrait bien trop de temps.
Mais Alice sait également qu'il y a plus de deux millions de pages sur fr.wikipedia.org, et des dizaines de liens dans chaque page, alors elle se demande légitimement si un tel programme a simplement une chance de répondre dans un délai raisonnable.
En cherchant à écrire des programmes pour répondre à ces questions, Alice découvre la théorie des graphes, inventée il y a presque 300 ans par le mathématicien Leonhard Euler, et qu'elle peut effectivement déterminer s'il existe un chemin d'une page à une autre dans Wikipedia avec un algorithme qui s'écrit en seulement cinq lignes de code.
","title":"S.D. : Graphes","tagtitle":"h1","posi":0},{"edit":"Nous allons commencer par fixer les notions et le vocabulaire de base de
la théorie des graphes.
Sommets, arcs, orientation
Un graphe est un ensemble de sommets reliés entre eux par des arcs.
Dans l'exemple de Wikipedia chaque page forme un sommet, et les liens permettant de naviguer d'une page à l'autre constituent les arcs.
Graphe orienté
Voici un exemple plus petit de graphe possédant quatre sommets, notés A, B, C et D, et six arcs, dessinés par des flèches.
Dans ce graphe il y à un arc du sommet A vers le sommet B, ce que l'on note A—>B , mais pas du sommet B vers le sommet A.
On parle de graphe orienté lorsque l'on distingue ainsi un sens pour les arcs.
En particulier, il y a un arc du sommet B vers le sommet D et un autre du sommet D vers le sommet B.
Mettre le résultat ici (code et figure).
Graphe non orienté
Lorsqu'en revanche le sens des arcs n'est pas significatif, c'est-à-dire que l'on s'intéresse uniquement à la présence d'un arc entre deux sommets, on parle de graphe non orienté.
On dessine alors les arcs non pas comme des flèches mais comme de simples traits reliant les sommets.
Sur cet exemple, on a toujours quatre sommets mais seulement cinq arcs maintenant.
La figure ci-dessous représente un graphe où les sommets sont les dix-huit régions françaises et où on a relié entre elles les régions limitrophes (par la terre).
Figure 1 : Le graphe des régions françaises.
C'est un autre exemple de graphe non orienté.
Mettre le résultat ici (code et figure).
Voisinage
Lorsqu'il y a un arc d'un sommet s vers un sommet t, on dit que t est adjacent à s.
Les sommets adjacents à s sont également appelés les voisins de s.
Dans les exemples précédents, le voisinage de A est l'ensemble {B,D} et le voisinage de D est le singleton {B} dans le cas orienté et l'ensemble {A,B, C} dans le cas non orienté.
Dans tout cette séquence, on se limite à des graphes simples, dans lesquels il y a au plus un arc entre deux sommets (pas d'arcs multiples) et pas d'arc reliant un sommet à lui-même (pas de boucles).
Mettre le résultat ici (code et figure).
Dessins
Il est important de comprendre que c'est l'ensemble des sommets et la relation d'adjacence, c'est-à-dire l'ensemble des arcs, qui définissent le graphe, et non pas la façon dont on le dessine.
Ainsi, les trois graphes suivants sont identiques, bien que dessinés différemment.
Notons qu'un graphe n'est pas nécessairement fini. Il peut contenir une
infinité de sommets et, dans ce cas, possiblement une infinité d'arcs. Ainsi, on peut considérer le graphe dont les sommets sont les entiers naturels et où il y a un arc n — m dès lors que m est un diviseur strict de n.
Mettre le résultat ici (code et figure).
Chemin dans un graphe
Dans notre exemple de Wikipedia, Alice a visité plusieurs pages l'une après l'autre, navigant de l'une à la suivante à l'aide de liens.
On appelle ceci un chemin.
Chemin
Dans un graphe donné, un chemin reliant un sommet u à un sommet v est une séquence finie de sommets reliés deux à deux par des arcs et menant de u à v.
Ainsi, dans le graphe
il existe un chemin reliant A à C, à savoir A —> B —> C. Mais il y en a d'autres, comme par exemple A —> D —> B —> C ou encore A —> B -> C —> D —> B ->C.
En fait, il y a ici une infinité de chemins reliant A à C, car on peut emprunter le chemin D —> B —> C —> D ou encore B —> D —> B autant de fois que l'on veut.
Pour un graphe non orienté, on à un chemin reliant u à v si et seulement
si on à un chemin reliant v à u. Mais pour un graphe orienté, on peut avoir
un chemin reliant u à v mais pas de chemin reliant v à u.
Ainsi, dans le graphe ci-dessus, il n'y a pas de chemin reliant C à A.
Mettre le résultat ici (code et figure).
Cycle
Un chemin est dit simple s'il n'emprunte pas deux fois le même arc, et élémentaire s'il ne passe pas deux fois par le même sommet.
Ainsi, dans le graphe précédent il n'y a que trois chemins simples reliant A à C, et seulement deux chemins élémentaires.
Un chemin simple reliant un sommet à lui-même et contenant au moins un arc est appelé un cycle.
C'est le cas par exemple de D—>B->C->D ici.
Notez que, dans le cas d'un graphe non orienté, la restriction imposant aux cycles d'être des chemins simples empêche de revenir sur ses pas.
Ainsi dans le graphe
le chemin A->B—>A n'est pas simple et n'est donc pas un cycle.
Mettre le résultat ici (code et figure).
Distance
La longueur d'un chemin est définie comme le nombre d'arcs qui constituent ce chemin.
La distance entre deux sommets est la longueur du plus court chemin reliant ces deux sommets, le cas échéant.
Ainsi, dans l'exemple ci-dessus, le chemin A->D->B->C a pour longueur 3, mais la distance entre A et C est 2, obtenue pour le chemin plus court A->B->C.
La distance d'un sommet s à lui-même est 0, obtenue pour le chemin allant de s à s en n'empruntant aucun arc.
La distance entre deux sommets n'est pas définie s'il n'existe aucun chemin entre les deux sommets.
Mettre le résultat ici (code et figure).
Connexité
On dit qu'un graphe non orienté est connexe si, pour toute paire u,v de sommets, il existe un chemin de u à v.
Pour un graphe orienté, on dit qu'il est connexe si le graphe non orienté obtenu en oubliant le sens des arcs est connexe.
On dit qu'un graphe orienté est fortement connexe lorsqu'il existe un chemin de u à v et un chemin de v à u pour toute paire u,v de sommets.
Ainsi, le graphe
est connexe mais pas fortement connexe. En effet, il existe un chemin reliant A à B mais pas de chemin reliant B à A.
Le graphe
n'est pas connexe, car il n'y a pas de chemin reliant C à E une fois qu'on
a oublié le sens des arcs.
On dit qu'il possède deux composantes conneres, l'une formée des sommets A, B, C et D et l'autre formée des sommets E et F.
De même, le graphe des régions de la figure 11.1 n'est pas connexe. Il contient sept composantes connexes, dont six sont réduites à un unique sommet.
Dans la séquence suivant, nous verrons des algorithmes pour déterminer si un graphe est connexe et plus généralement pour déterminer s'il existe un chemin entre deux sommets.
Mettre le résultat ici (code et figure).
Vocabulaire
Le vocabulaire des graphes varie selon le contexte et notamment selon le caractère orienté ou non des graphes.
Ainsi, on parle parfois de nœuds et d'arêtes plutôt que de sommets et d'arcs pour les graphes non orientés.
De même, on parle parfois de chaîne plutôt que de chemins dans les graphes non orientés.
Mettre le résultat ici (code et figure).
Autres caractérisations des chemins
Un chemin peut également être caractérisé par la succession des arcs qu'il emprunte.
C'est notamment pertinent lorsque l'on ne considère pas un graphe simple, et que plusieurs arcs peuvent aller d'un sommet s à un sommet t.
Cette caractérisation peut cependant également comporter une ambiguïté dans le cas des graphes non orientés.
Dans ce cas, on peut aller jusqu'à une description complète donnant la succession des sommets et des arcs.
Étiquetage
Il est fréquent d'associer une information à chaque sommet et/ou à chaque arc d'un graphe. On parle alors de graphe étiqueté.
Pour ce qui est des sommets, on peut confondre un sommet et son étiquette dès lors que celle-ci est unique.
Ainsi, dans nos exemples précédents, on
peut dire « le sommet «A» ou «le sommet étiqueté par A».
Pour ce qui est des arcs, on peut adopter la notation u -e-> v pour indiquer
que l'arc entre les sommets u et v porte l'étiquette e.
Si la nature de cette étiquette est numérique, alors on peut définir une notion de coût pour un chemin, comme la somme des étiquettes des arcs constituant ce chemin.
On peut alors parler de plus court chemin au sens de ce coût plutôt qu'au sens du nombre d'arcs.
","title":""},{"edit":"Mettre le résultat ici (code et figure).
Maintenant que nous savons ce qu'est un graphe, on peut en donner de nombreux exemples.
Sur tous ces exemples, on peut se poser des questions comme :
- le graphe est-il connexe?
- existe-t-il un chemin entre le
sommet A et le sommet B?
- ou encore : quelle est la distance entre les sommets A et B?
Réseau
Un réseau routier est naturellement un graphe. Ce peut être par exemple un réseau routier à grande échelle, avec des sommets qui sont des villes, reliés par des arcs qui représentent des routes entre ces villes.
Si toutes les routes sont à double sens, le graphe sera naturellement non orienté.
Mais on peut également imaginer un réseau routier à l'intérieur d'une même ville, où les sommets sont plutôt les intersections entre les rues ct les
arcs des portions de rues reliant une intersection à une autre.
Dans ce cas, le graphe sera naturellement orienté dès lors que certaines rues sont à sens unique.
Un navigateur GPS implémente un algorithme de recherche de chemin dans un tel graphe. Il prend en compte des informations supplémentaires, telles que la longueur des routes, la vitesse maximale autorisée, la présence de péages, etc pour calculer des chemins qui minimisent la distance totale, le temps de trajet, etc. La recherche d'un tel chemin minimal n'est pas au programme de terminale.
Un réseau n'est pas nécessairement un réseau routier. On peut ainsi considérer un réseau informatique, où des machines sont reliées entre elles, ou encore un réseau social, où des personnes sont reliées entre elles, par exemple par leurs contacts respectifs.
Dans ce domaine, les mathématiciens ont défini le nombre d'Erdös d'un mathématicien X comme la distance entre le mathématicien Paul Erdös et le mathématicien X dans un graphe non orienté où les arcs relient entre eux les mathématiciens qui sont coauteurs d'un même article.
Toujours dans le domaine des réseaux sociaux, la propriété de «petit monde» énonce que la distance entre deux personnes est très petite (logarithmique, pour être précis) comparativement au nombre d'individus.
Mettre le résultat ici (code et figure).
Carte
Le graphe des régions françaises de la figure 1 est une façon de concevoir la carte des régions. On pourrait faire la même chose avec les départements, les pays du monde, etc.
Un très célèbre théorème de mathématiques, le théorème des quatre couleurs, énonce que les pays d'une carte
planaire peuvent toujours être coloriés avec quatre couleurs seulement sans que deux pays limitrophes aient la même couleur.
Ce théorème s'énonce en termes de graphes en disant que tout graphe qui peut être dessiné dans le plan (i.e., sans que deux arcs ne se croisent) peut voir ses sommets coloriés avec quatre couleurs au plus sans que deux sommets reliés par un are n'aient la même couleur.
Mettre le résultat ici (code et figure).
Labyrinthe
Source : https://omnilogie.fr/O/Labyrinthe
Un labyrinthe constitué de salles reliées entre elles par des portes peut être vu comme un graphe non orienté.
Les sommets sont les salles du labyrinthe et deux sommets sont reliés par un arc s'il existe une porte entre ces deux salles.
Dans la séquence suivant, nous étudierons un algorithme efficace pour déterminer s'il existe un chemin entre deux sommets donnés d'un graphe et même le construire, le cas échéant.
On peut en particulier se servir d'un tel algorithme pour trouver un chemin qui mène de l'entrée à la sortie d'un labyrinthe.
Mettre le résultat ici (code et figure).
Jeu![](\"https://www.lapouleapois.fr/24976-thickbox_default/jeu-de-dames-pliant-jeujura.jpg\")
Source:https://www.lapouleapois.fr/jeux-traditionnels/8490-jeu-de-dames-pliant-jeujura-3225280813103.html?gclid=CjwKCAiAtK79BRAIEiwA4OskBo1Rmxf0xpVrd0RXq8lOrdTi5JBVE0xvO4Wh081AX_qOdZxG8NzBGxoCkG4QAvD_BwE
De nombreux jeux consistent à modifier une configuration donnée, typiquement en déplacement des pièces, jusqu'à obtenir une configuration particulière.
Dans cette catégorie, on peut citer des jeux à un joueur de type casse-tête, comme l'âne rouge, le solitaire où encore le taquin, mais aussi à plusieurs joueurs, comme les échecs ou les dames.
Pour un tel jeu, on peut concevoir un graphe où les sommets sont les configurations possibles du jeu et les arcs les coups valides qui permettent de passer d'une configuration à une autre.
Un tel graphe est typiquement gigantesque, voire infini, et de
multiples chemins peuvent mener d'une configuration à une autre. Nous verrons que cela n'empêche pas néanmoins de chercher des chemins et en particulier des chemins menant à une configuration gagnante.
Mettre le résultat ici (code et figure).
Arbre
Un arbre peut être naturellement vu comme un graphe où chaque nœud constitue un sommet et est relié aux racines de ses sons-arbres, le cas échéant. On peut le voir au choix comme un graphe non orienté ou comme un graphe orienté, deux solutions étant alors envisageables (arcs dirigés «vers le haut» ou «vers le bas»).
Il existe de multiples façons de représenter un graphe en machine, selon la nature du graphe mais aussi selon la nature des opérations et des algorithmes
à effectuer sur ce graphe.
Quelle que soit la représentation, on souhaite proposer des opérations de deux sortes :
- d'une part des opérations de construction de graphes, comme l'obtention d'un graphe vide, l'ajout de sommets ou d'arcs, etc. ;
- d'autre part des opérations de parcours d'un graphe, comme parcourir tous les sommets, tous les arcs, ou encore tous les arcs issus d'un
sommet donné.
À priori, on ne souhaite pas fixer le type des sommets d'un graphe.
Ce pourrait être des entiers, des chaînes de caractères ou encore des objets.
Cependant, nous allons commencer par une représentation où les sommets sont des entiers, avant de proposer une représentation plus souple où les sommets peuvent être d'un type quelconque.
On se focalise pour l'instant sur des graphes orientés et on expliquera, à la fin de cette section, comment représenter des graphes non orientés.
Mettre le résultat ici (code et figure).
Matrice d'adjacence
Dans cette première représentation, les sommets du graphe sont supposés être les entiers 0,1,...,N — 1 pour un certain entier N, qui se trouve donc être le nombre total de sommets.
On peut alors représenter le graphe par une matrice adj de booléens de taille NxN, c'est-à-dire un tableau de N tableaux de booléens de taille N, où le booléen adj[i][j] indique la présence d'un arc entre les sommets i et j.
On appelle cela une matrice d'adjacence.
Pour construire un certain graphe, on peut commencer par construire une telle matrice où tous les booléens sont initialisés à False, par exemple de la manière suivante :
adj = [[False] * N for _ in range(N)]
Ensuite, on peut ajouter des arcs au graphe, en donnant la valeur True à certains éléments de cette matrice.
Ainsi, on peut ajouter un arc entre les
sommets 2 et 7 avec une simple affectation :
adj[2][7] = True
Et ainsi de suite.
Une telle représentation à le mérite d'être relativement simple. En particulier, on peut parcourir tous les sommets du graphe avec une simple boucle:
for s in range(N):
Programme 36 — Graphe représenté par une matrice d'adjacence
class Graphe:
l'un graphe représenté par une matrice d''adjacence, où les sommets sont les entiers 0,1,...,n-1\"\"\"
def __init__(self, n):
self.n=n
self.adj = [(False] * n for _ in range(n)]
def ajouter arc(self, si, 82):
self.adj{sii[s?2] = True
def arc(self, s1, 52):
return self.adj[s1] [s2]
def voisins(self, s):
v =
for i in range(self.n):
if self.adjfs]lil:
v.append(i)
return v
De même, on peut parcourir tous les voisins du sommet s avec une boucle for et un test :
for v in range(N):
if adj[s][v]:
...
Le programme ci-dessous encapsule une telle matrice d'adjacence dans une classe Graphe.
class Graphe1:
\"\"\"un graphe représenté par une matrice d'adjacence,
où les sommets sont les entiers 0,1,...,n-1\"\"\"
def __init__(self, n):
self.n = n
self.adj = [[False] * n for _ in range(n)]
def ajouter_arc(self, s1, s2):
self.adj[s1][s2] = True
def arc(self, s1, s2):
return self.adj[s1][s2]
def voisins(self, s):
v = []
for i in range(self.n):
if self.adj[s][i]:
v.append(i)
return v
def afficher_matrice(self) :
for l in self.adj:
print(l)
Le constructeur de cette classe prend en argument le nombre de sommets et alloue la matrice.
Une méthode ajouter_arc permet d'ajouter un arc au graphe. Ainsi, on peut écrire
g1 = Graphe1(4)
g1.afficher_matrice()
print(\"Ajout des arcs:\")
g1.ajouter_arc(0,1)
g1.ajouter_arc(0,3)
g1.ajouter_arc(1,2)
g1.ajouter_arc(3,1)
print(g1.voisins(0))
print(g1.voisins(1))
g1.afficher_matrice()
pour construire le graphe représenté ci-dessous:
Une méthode arc permet de tester la présence d'un arc entre deux sommets et une méthode voisins renvoie l'ensemble des voisins d'un sommet donné, sous forme d'un tableau.
Efficacité
La matrice d'adjacence est indéniablement simple à mettre en œuvre, mais elle a néanmoins quelques défauts.
D'une part, elle occupe un espace mémoire proportionnel à N x N. Ainsi, un graphe de mille sommets nécessite une matrice d'un million de booléens, ce qui représente déjà quelques mégaoctets, et ce, même si le graphe contient très peu d'arcs.
D'autre part, parcourir tous les voisins d'un sommet donné exige de parcourir toute une ligne de la matrice, c'est-à-dire N booléens, alors même qu'il peut y avoir très peu de voisins.
Enfin, elle limite les sommets à des entiers, qui plus est consécutifs et d'un nombre connu à l'avance. Dans la section suivante, nous présentons une autre façon de représenter un graphe, qui s'affranchit de tous ces défauts.
Mettre le résultat ici (code et figure).
Dictionnaire d'adjacence
Dans cette nouvelle représentation, un graphe est un dictionnaire, qui associe à chaque sommet l'ensemble de ses voisins. On appelle cela un dictionnaire d'adjacence.
La première conséquence est que les sommets ne sont pas limités à des entiers et qu'il n'est pas nécessaire de les connaître tous a priori.
En effet, il suffit d'ajouter une nouvelle entrée dans le dictionnaire
pour ajouter uu nouveau sommet au graphe.
L'ensemble des sommets du graphe est exactement l'ensemble des clés du dictionnaire.
En particulier, on peut parcourir tous les sommets d'un graphe stocké dans la variable graphe avec la boucle suivante :
for s in graphe:
Les voisins du sommet s sont donnés par l'ensemble graphe[s]. On peut donc les parcourir avec la boucle suivante :
for v in graphe[s]:
La deuxième conséquence de cette nouvelle représentation est que ce parcours est maintenant d'une complexité directement proportionnelle au nombre de voisins de s, indépendamment du nombre total de sommets du graphe.
Le programme ci-dessous encapsule un tel dictionnaire d'adjacence dans une classe Graphe.
Programme — Graphe représenté par un dictionnaire d'adjacence
class Graphe2:
\"\"\"un graphe comme un dictionnaire d'adjacence\"\"\"
def __init__(self):
self.adj = {}
def ajouter_sommet(self, s):
if s not in self.adj:
self.adj[s] = set()
def ajouter_arc(self, s1, s2):
self.ajouter_sommet(s1)
self.ajouter_sommet(s2)
self.adj[s1].add(s2)
def arc(self, s1, s2):
return s2 in self.adj[s1]
def sommets(self):
return list (self.adj)
def voisins(self, s):
return self.adj[s]
Le constructeur de cette classe alloue un dictionnaire vide.
Une méthode ajouter_sommet permet d'ajouter un nouveau sommet et une
méthode ajouter_arc permet d'ajouter un arc.
Ainsi, on peut écrire
g2 = Graphe2()
g2.ajouter_arc(0,1)
g2.ajouter_arc(0,3)
g2.ajouter_arc(1,2)
g2.ajouter_arc(3,1)
print(g2.voisins(0))
print(g2.voisins(1))
pour construire le graphe représenté ci-dessous.
On note que le constructeur ne prend pas d'argument (contrairement à la matrice d'adjacence, où on avait passé le nombre de sommet, 4, en argument).
On note également qu'on n'a pas pris la peine d'ajouter les quatre sommets au graphe, parce que la méthode ajouter_arc le fait déjà.
Mais si un sommet n'est relié à aucun autre, alors il faut le rajouter explicitement au graphe, avec la méthode
aïouter_sommet.
On n'est nas censé annuler la méthode arc aver un sam-met si qui ne serait pas dans le graphe, sans quoi l'accès au dictionnaire adj avec la clé s1 provoquerait l'exception KeyError.
Efficacité
En ce qui concerne le coût des opérations, le dictionnaire d'adjacence est optimal:
ajouter un sommet, ajouter un arc ou tester la présence d'un arc se fait en temps constant (les dictionnaires et les ensembles de Python étant réalisés par des tables de hachage) et parcourir les voisins d'un sommet donné sc fait en un temps proportionnel au nombre de ces voisins.
Le seul intérêt de la matrice d'adjacence peut résider dans l'espace mémoire qu'elle occupe, qui peut être inférieur à celui d'un dictionnaire d'adjacence dans certains cas.
Ainsi, un graphe de 400 sommets qui contient presque tous les arcs possibles occupe dix fois moins d'espace quand il est représenté par une matrice d'adjacence que lorsqu'il est représenté par un dictionnaire d'adjacence. Mais s'il contient au contraire très peu d'arcs, alors c'est le dictionnaire d'adjacence qui occupe moins de mémoire, jusqu'à 13 fois moins.
Ën pratique, on suggère de privilégier le dictionnaire d'adjacence, car il permet des sommets d'un type quelconque, et de ne retenir la matrice d'adjacence que dans le cas extrême d'un graphe dont le dictionnaire d'adjacence ne tiendrait pas en mémoire.
Mettre le résultat ici (code et figure).
Autres représentations
Dans la littérature, on rencontre souvent une autre représentation des graphes, dite de liste d'adjacence, où chaque sommet est associé à une liste ordonnée de ses voisins.
En Python, une telle liste pourrait être réalisée par une liste chaînée ou
encore un tableau.
Cependant, une telle représentation n'offre aucun avantage sur la solution à base d'ensembles que nous avons proposée.
En effet, pour déterminer s'il existe un arc entre les sommets s1 et s2, il faudrait parcourir linéairement la liste des voisins de s1, là où l'ensemble
d'adjacence offre une réponse en temps constant.
De même, on rencontre souvent des représentations des graphes utilisant
non pas un dictionnaire mais un tableau. Cela impose cependant que les sommets soient les entiers 0,1...,N — 1.
Là encore, notre solution utilisant un dictionnaire est meilleure:
elle est plus souple quant à la nature des sommets et fournit des opérations tout aussi efficaces (un dictionnaire, comme un tableau, offre des opérations en temps constant).
On aura compris qu'il y a de multiples façons de représeuter un graphe. Ainsi, on peut imaginer d'autres combinaisons, comme un tableau d'ensembles ou encore un dictionnaire de listes. Dans tous les cas, la représentation est relativement secondaire, dès lors que lon peut accéder à tous les sommets du graphe et à tous les voisins d'un sommet donné d'une façon ou d'une autre.
Représenter un graphe non orienté
La façon la plus simple de représenter un graphe non orienté consiste à le représenter exactement comme un graphe orienté, avec l'une ou l'autre des deux solutions que nous venons de présenter, et d'assurer en permanence l'invariant suivant :
- il y a un arc reliant le sommet u au sommet v si et seulement si il y à un arc reliant le sommet v au sommet u.
Dit autrement, on a systématiquement un double arc, orienté dans les deux sens.
Pour maintenir cet invariant, il suffit que les opérations ajouter_arc et supprimer_arc ajoutent et enlèvent systématiquement la paire d'arcs.
Ainsi, pour une matrice d'adjacence, on modifie la méthode ajouter_arc comme ceci:
self.adj[s1][s2] = True
self.adj[s2][s1] = True
Et pour un dictionnaire d'adjacence, on la modifie comme ceci:
self.ajouter_sommet(si)
self.ajouter_sommet(s2)
self.adj[s1].add(s2)
self.adj[s2].add(s1)
Avec ce choix de représentation des graphes non orientés, les algorithmes de
parcours de graphe que nous étudions à la séquence suivante s'écrivent exactement de la même façon que les graphes soient ou non orientés.
La seule subtilité est éventuellement le décompte des arcs, où l'on peut vouloir diviser par deux le nombre d'arcs obtenu au total.
En modifiant la classe Graphe2 on obtient la classe suivante pour les graphes non orientés:
class Graphe3:
\"\"\"un graphe non orienté comme un dictionnaire d'adjacence\"\"\"
def __init__(self):
self.adj = {}
def ajouter_sommet(self, s):
if s not in self.adj:
self.adj[s] = set()
def ajouter_arc(self, s1, s2):
self.ajouter_sommet(s1)
self.ajouter_sommet(s2)
self.adj[s1].add(s2)
self.adj[s2].add(s1)
def arc(self, s1, s2):
return s2 in self.adj[s1]
def sommets(self):
return list (self.adj)
def voisins(self, s):
return self.adj[s]
Donc le graphe ci-dessous;
est représenté de la manière suivante :
g3 = Graphe3()
g3.ajouter_arc(\"A\",\"B\")
g3.ajouter_arc(\"A\",\"D\")
g3.ajouter_arc(\"B\",\"C\")
g3.ajouter_arc(\"D\",\"C\")
g3.ajouter_arc(\"B\",\"D\")
print(g3.voisins(\"B\"))
Tester le code et conclure.
Mettre le résultat ici (code et figure).
Représenter un graphe infini
Si un graphe est infini, il reste néanmoins possible de le représenter en machine. En effet, beaucoup d'algorithmes ont uniquement besoin d'une fonction voisins qui énumère les voisins d'un sommet donné (sous la forme d'un tableau, d'un ensemble, etc.).
C'est le cas notamment des algorithmes de recherche de chemin que nous détaillons dans la séquence suivante. Ainsi, même si le graphe est infini, il suffit que les voisins d'un sommet donné soient en nombre fini pour que la fonction voisins puisse être réalisée.
Mettre le résultat ici (code et figure).
L'algorithme étudié va colorie un graphe à l'aide d'un algorithme glouton.
Colorier un graphe veut dire associer
une couleur à chacun de ses sommets, de façon à ce que deux sommets reliés par un arc n'aient pas la même couleur.
Colorier un graphe avec un minimum de couleurs est un problème difficile, mais si on accepte l'idée d'utiliser éventuellement plus de couleurs que nécessaire, alors on peut colorier un graphe efficacement.
Le principe d'un coloriage glouton est simple. On parcourt les sommets dans un ordre arbitraire et, pour chaque sommet, on lui attribue la première couleur qui n'est pas utilisée par ses voisins.
Le programme ci-dessous réalise cet algorithme. Il est décomposé en deux fonctions.
La fonction principale, coloriage, reçoit un graphe g en argument et renvoie un couple constituée d'un coloriage et du nombre total de couleurs utilisées.
Le coloriage est représenté par un dictionnaire, couleur, qui associe à tout sommet une couleur.
Une couleur est ici un entier naturel.
La variable n maintient le nombre total de couleurs utilisées.
Pour attribuer une couleur à un sommet, on utilise une seconde fonction, appelée mex (pour minimum exclus), qui reçoit en arguments l'ensemble des voisins du sommet et le coloriage courant couleur.
Cette fonction cherche la plus petite couleur qui n'est pas encore utilisée par les voisins.
Pour cela, elle utilise un tableau dispo qui indique, pour chaque couleur, si elle est encore disponible.
La taille de ce tableau est n+1 où n est le nombre de voisins.
On sera en effet assuré de trouver au moins une couleur disponible parmi les n+1 premiers entiers.
Une première boucle commence par marquer
toutes les couleurs utilisées.
IL faut être soigneux ici, en ne considérant que les sommets déjà coloriés d'une part et uniquement ceux pour lesquels la couleur est inférieure ou égale à n d'autre part, sans quoi on accéderait au tableau dispo en dehors de ses bornes.
Ensuite, une seconde boucle parcourt le tableau dispo à la recherche d'une couleur disponible. Il y en a forcément une et par conséquent la toute dernière ligne de la fonction est inatteignable, ce que l'on manifeste avec l'instruction assert False.
On pourrait se contenter de ne rien faire, mais une programmation défensive est une bonne pratique.
Cet algorithme est efficace, car il parcourt chaque sommet une seule fois et, pour chaque sommet, il parcourt l'ensemble de ses voisins une seule fois.
Dit autrement, le temps de calcul de cet algorithme est directement proportionnel à la taille du graphe, c'est-à-dire à la somme du nombre de ses sommets et de ses arcs.
Programme — Coloriage glouton d'un graphe
def mex(voisins, couleur):
\"\"\"la plus petite couleur non utilisée par les voisins\"\"\"
n = len(voisins)
dispo = [True] * (n + 1)
for v in voisins:
if v in couleur and couleur[v] <= n:
dispo[couleur[v]] = False
for c in range(n + 1):
if dispo[c]:
return c
assert False # on n'arrivera jamais ici
def coloriage(g):
\"\"\"colorie graphe g avec un algorithme glouton\"\"\"
couleur = {}
n = 0
for s in g.sommets():
c = mex(g.voisins(s), couleur)
couleur[s] = c
n = max(n, c + 1)
return couleur, n
On ne peut pas faire mieux, car il faut examiner tout sommet pour lui donner une couleur et il faut examiner tout arc pour prendre en compte toutes les contraintes.
Créons le graphe des régions:
regions = Graphe3() #non orienté
regions.ajouter_sommet(\"Guadeloupe\")
regions.ajouter_sommet(\"Martinique\")
regions.ajouter_sommet(\"Guyane\")
regions.ajouter_sommet(\"Corse\")
regions.ajouter_sommet(\"Mayotte\")
regions.ajouter_sommet(\"La Reunion\")
regions.ajouter_arc(\"Hauts-de-France\",\"Normandie\")
regions.ajouter_arc(\"Hauts-de-France\",\"Ile-de-France\")
regions.ajouter_arc(\"Hauts-de-France\",\"Grand Est\")
regions.ajouter_arc(\"Ile-de-France\",\"Grand Est\")
regions.ajouter_arc(\"Ile-de-France\",\"Hauts-de-France\")
regions.ajouter_arc(\"Pays de la Loire\",\"Bretagne\")
regions.ajouter_arc(\"Normandie\",\"Bretagne\")
regions.ajouter_arc(\"Normandie\",\"Pays de la Loire\")
regions.ajouter_arc(\"Pays de la Loire\",\"Centre-Val de Loire\")
regions.ajouter_arc(\"Centre-Val de Loire\",\"Normandie\")
regions.ajouter_arc(\"Pays de la Loire\",\"Nouvelie-Aquitaine\")
regions.ajouter_arc(\"Nouvelie-Aquitaine\",\"Centre-Val de Loire\")
regions.ajouter_arc(\"Ile-de-France\",\"Centre-Val de Loire\")
regions.ajouter_arc(\"Bourgogne-Franche Comte\",\"Centre-Val de Loire\")
regions.ajouter_arc(\"Bourgogne-Franche Comte\",\"Grand Est\")
regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Centre-Val de Loire\")
regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Bourgogne-Franche Comte\")
regions.ajouter_arc(\"Ile-de-France\",\"Bourgogne-Franche Comte\")
regions.ajouter_arc(\"Ile-de-France\",\"Normandie\")
regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Occitanie\")
regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Provence-Alpes-Cote d'Azur\")
regions.ajouter_arc(\"Occitanie\",\"Provence-Alpes-Cote d'Azur\")
regions.ajouter_arc(\"Occitanie\",\"Nouvelie-Aquitaine\")
regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Nouvelie-Aquitaine\")
print(\"Voisins Bretagne\",regions.voisins(\"Bretagne\"))
print(\"Voisins Ile-de-France\",regions.voisins(\"Ile-de-France\"))
Faisons tourner cet algorithme sur le graphe des régions.
print(coloriage(regions))
Tester et mettre le résultat ci-dessous.
On obtient combien de couleurs pour le graphe. Ceci correspond-il au théorème des quatres couleurs?
Avec notre algorithme glouton, au moment d'affecter une couleur à la Normandie, ses cinq voisins utilisaient déjà quatre couleurs différentes.
D'une manière plus générale, le coloriage obtenu dépend de l'ordre dans lequel les sommets ont été parcourus, qui est ici fixé par ce que nous donne la méthode sommets.
Comme on le voit, le programme est indépendant de la façon dont le graphe est représenté.
Il a uniquement besoin des deux méthodes sommets et voisins. On peut en particulier l'utiliser sans changement avec les deux représentations étudiées dans la section précédente.
Mais on pourrait également l'utiliser avec d'autres représentations encore, dès lors que ces deux méthodes sont fournies. C'est là une application du principe de modularité.
Mettre le résultat ici (code et figure).
Un graphe est un ensemble de sommets reliés entre eux par des arcs.
Un graphe peut être orienté ou non orienté, selon que les arcs sont ou non considérés comme symétriques.
Un graphe peut être représenté en machine par une matrice d'adjacence ou par un
dictionnaire d'adjacence.
Exercice 93 Dessiner tous les graphes non orientés ayant exactement trois sommets. Solution page 469 D
Mettre le résultat ici (code et figure).
Il y en a 8 au total :
Exercice 94 Combien y a-t-il de graphes orientés ayant exactement trois sommets ?
On ne demande pas de les dessiner tous, mais seulement de les dénombrer.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
Il y a six arcs possibles (0—>1, 1—>0, 1—>2, 2—>1,2—>0, 0—>2), chacun pouvant être présent ou absent, soit 26=64 possibilités au total.
class Graphe1:
\"\"\"un graphe représenté par une matrice d'adjacence,
où les sommets sont les entiers 0,1,...,n-1\"\"\"
def __init__(self, n):
self.n = n
self.adj = [[False] * n for _ in range(n)]
def ajouter_arc(self, s1, s2):
self.adj[s1][s2] = True
def arc(self, s1, s2):
return self.adj[s1][s2]
def voisins(self, s):
v = []
for i in range(self.n):
if self.adj[s][i]:
v.append(i)
return v
Ajouter à cette classe Graphe (matrice d'adjacence) une méthode afficher pour afficher le graphe sous la forme suivante :
0 -> 1 3
1 -> 2
2 -> 3
3 -> 1
c'est-à-dire une ligne par sommet, avec pour chacun la liste de ses voisins.
Tester avec:
g1 = Graphe1(4)
g1.ajouter_arc(0,1)
g1.ajouter_arc(0,3)
g1.ajouter_arc(1,2)
g1.ajouter_arc(2,3)
g1.ajouter_arc(3,1)
g1.afficher()
Mettre le résultat ici (code et figure).
def afficher(self) :
for s in range(self.n):
print(s, \"->\", end=\"\")
for v in range(self.n):
if self.adj[s][v]:
print(\"\", v, end=\"\")
print()
class Graphe2:
\"\"\"un graphe comme un dictionnaire d'adjacence\"\"\"
def __init__(self):
self.adj = {}
def ajouter_sommet(self, s):
if s not in self.adj:
self.adj[s] = set()
def ajouter_arc(self, s1, s2):
self.ajouter_sommet(s1)
self.ajouter_sommet(s2)
self.adj[s1].add(s2)
def arc(self, s1, s2):
return s2 in self.adj[s1]
def sommets(self):
return list (self.adj)
def voisins(self, s):
return self.adj[s]
Ajouter à la classe Graphe (dictionnaire d'adjacence) une méthode afficher pour afficher le graphe sous la forme suivante:
0 {1, 3}
1 {2}
3 {1}
2 {3}
c'est-à-dire une ligne par sommet, avec pour chacun l'ensemble de ses voisins.
L'ordre des sommets n'est pas important. L'ensemble des voisins peut être affiché directement avec print.
Tester avec :
g2 = Graphe2()
g2.ajouter_arc(0,1)
g2.ajouter_arc(0,3)
g2.ajouter_arc(1,2)
g2.ajouter_arc(2,3)
g2.ajouter_arc(3,1)
g2.afficher()
Mettre le résultat ici (code et figure).
On fait un cas particulier pour ’ensemble vide, histoire qu’il ne soit pas affiché comme set() mais comme {}.
def afficher(self):
for s in self.adj:
if len(self.adj[s]) == 0:
print(s, \"{}\")
else:
print(s, self.adj[s])
Ajouter à la classe Graphe2 une méthode
nb_sommets() qui donne le nombre de sommets du graphe.
Tester avec :
g2 = Graphe2()
g2.ajouter_arc(0,1)
g2.ajouter_arc(0,3)
g2.ajouter_arc(1,2)
g2.ajouter_arc(2,3)
g2.ajouter_arc(3,1)
print(g2.nb_sommets())
Résultat:
4
Mettre le résultat ici (code et figure).
Le nombre de sommets est égal au nombre d’entrées
dans le dictionnaire :
def nb_sommets(self):
return len(self.adj)
Ajouter à la classe Graphe1 une méthode
degre(s) qui donne le nombre d'arcs issus du sommet s.
On appelle cela le degré du sommet s.
Tester avec:
g1 = Graphe1(4)
g1.ajouter_arc(0,1)
g1.ajouter_arc(0,3)
g1.ajouter_arc(1,2)
g1.ajouter_arc(2,3)
g1.ajouter_arc(3,1)
print(g1.degre(0))
Résultat:
2
Mettre le résultat ici (code et figure).
Le code est très semblable à celui de la méthode voisins:
def degre(self, s):
d=0
for i in range(self.n):
if self.adj[s][i]:
d += 1
return d
En utilisant l'exercice précédent, ajouter à la classe Graphe1 une méthode nb_arcs() qui donne le nombre total d'arcs du graphe.
Tester avec:
g1 = Graphe1(4)
g1.ajouter_arc(0,1)
g1.ajouter_arc(0,3)
g1.ajouter_arc(1,2)
g1.ajouter_arc(2,3)
g1.ajouter_arc(3,1)
print(g1.nb_arcs())
Résultat:
5
Mettre le résultat ici (code et figure).
Il suffit de faire la somme de tous les degrés.
def nb_arcs(self):
n=0
for s in range(self.n):
n += self.degre(s)
return n
Ajouter à la classe Graphe2 une méthode degre(s) qui donne le nombre d'arcs issus du sommet s.
On appelle cela le degré du sommet s.
Tester avec:
g2 = Graphe2()
g2.ajouter_arc(0,1)
g2.ajouter_arc(0,3)
g2.ajouter_arc(1,2)
g2.ajouter_arc(2,3)
g2.ajouter_arc(3,1)
print(g2.degre(0))
Résultat :
2
Mettre le résultat ici (code et figure).
C’est exactement le cardinal de l’ensemble adj [s] :
def degre(self, s):
return len(self.adj[s])
En utilisant l'exercice précédent, ajouter à la classe Graphe2 une méthode nb_arcs() qui donne le nombre total d'arcs du graphe.
Tester avec:
g2 = Graphe2()
g2.ajouter_arc(0,1)
g2.ajouter_arc(0,3)
g2.ajouter_arc(1,2)
g2.ajouter_arc(2,3)
g2.ajouter_arc(3,1)
print(g2.nb_arcs())
Résultat:
5
Mettre le résultat ici (code et figure).
Comme dans l'exercice 99, on fait la somme de tous
les degrés.
def nb_arcs(self):
n=0
for s in self.adj:
n += self.degre(s)
return n
Ajouter à la classes Graphe1 une méthode supprimer_arc(s1,s2) pour supprimer l'arc entre les sommets s1 et s2.
S'il n'y a pas d'arc entre ces sommets, la méthode n'a aucun effet.
Tester avec:
g1.ajouter_arc(0,1)
g1.ajouter_arc(0,3)
g1.ajouter_arc(1,2)
g1.ajouter_arc(2,3)
g1.ajouter_arc(3,1)
g1.afficher()
print(\"Suprime arc 1->2\")
g1.supprimer_arc(1,2)
g1.afficher()
Résultat:
0 -> 1 3
1 -> 2
2 -> 3
3 -> 1
Suprime arc 1->2
0 -> 1 3
1 ->
2 -> 3
3 -> 1
Mettre le résultat ici (code et figure).
Pour la matrice d’adjacence, on affecte le booléen à False dans la matrice:
def supprimer_arc(self,s1,s2):
self.adj[s1][s2] = False
Ajouter à la classes Graphe2 une méthode supprimer_arc(s1,s2) pour supprimer l'arc entre les sommets s1 et s2.
S'il n'y a pas d'arc entre ces sommets, la méthode n'a aucun effet.
On supprime un élément d'un ensemble avec sa méthode remove.
Tester avec:
g2 = Graphe2()
g2.ajouter_arc(0,1)
g2.ajouter_arc(0,3)
g2.ajouter_arc(1,2)
g2.ajouter_arc(2,3)
g2.ajouter_arc(3,1)
g2.afficher()
print(\"Suprime arc 1->2\")
g2.supprimer_arc(1,2)
g2.afficher()
Résultat:
0 {1, 3}
1 {2}
3 {1}
2 {3}
Suprime arc 1->2
0 {1, 3}
1 {}
3 {1}
2 {3}
Mettre le résultat ici (code et figure).
Pour le dictionnaire d’adjacence, on supprime s2 de l’ensemble des voisins
de s1:
def supprimer_arc(self, s1, s2):
self.adj[s1].remove(s2)
- Détails
- Écrit par : Richard GAUTHIER
- Clics : 1501
[[{"text":"
","title":"S.D. - Autres structures arborescentes","tagtitle":"h1","posi":0},{"edit":"
"}],[{"text":"
"}],[{"text":"
"}],[{"text":"
","title":"Représentation en Python"},{"edit":"
"}],[{"text":"![\"pile_file1.png](\"https://sciencesappliquees.com/images/nsi/restapi1.png\")
","title":"Exemples de structures arborescentes","tagtitle":"h1"},{"edit":"
"}],[{"text":"
![\"pile_file1.png](\"https://sciencesappliquees.com/images/nsi/arbo.png\")
","title":"Documents XML","tagtitle":"h1"},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
![\"pile_file1.png](\"https://sciencesappliquees.com/images/nsi/arbo2.png\")
","title":"Python et XML","tagtitle":"h1"},{"edit":"
"}],[{"text":"Il existe aussi un autre module pour gerer les xml. Le module xml.etree.ElementTree qui permet de gérer les documents xml. La documentation de celle-ci se trouve ici:
"}],[{"text":"
","title":"Le format JSON"},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":"Conclusion"},{"edit":"
"}],[{"text":"
","title":"Exercice","tagtitle":"h1"},{"edit":"
"},{"solution":"
"}],[{"text":"
affiche(\"\",repertoires(\"C:\\Users\\\"))
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
"},{"solution":"
"}],[{"text":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice","tagtitle":"h1"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"A l'aide du module ETREE, écrire un programme Python qui convertit le fichier xml fichier.xml au format json et le copier dans le fichier.json.
"},{"solution":"
"}],[{"text":"
","title":"Exercice","tagtitle":"h1"},{"edit":"
"},{"solution":"
"}],[{"text":"Vous allez compléter un programme pour réaliser une connexion entre le client (Front end) et le serveur (Back e,d) :
","title":"Exercice"},{"edit":"
"},{"solution":""}]]
Les arbres binaires, vus dans les deux séquences précédentes, se “généralisent” en des structures arborescentes constituées de nœuds toujours organisés par des notions de racine et de sous-arbres.
Ces structures arborescentes sont omniprésentes en informatique et prennent des formes concrètes très variées.
Elles permettent de structurer l'information, notamment pour la stocker, la parcourir, y faire des recherches, etc.
Dans cette séquence, on commence par définir ce qu'est une arborescence et
par montrer comment la représenter en Python.
Puis on donnera des exemples significatifs de structures arborescentes.
Mettre le résultat ici (code et figure).
Une arborescence est un ensemble non vide de nœuds qui sont organisés de la façon suivante :
- un nœud particulier constitue la racine de l'arborescence;
- les autres nœuds sont partagés en n sous-ensembles distincts, qui forment autant d'arborescences;
- le nœud racine est relié aux n racines de ses arborescences, qu'on appelle ses fils.
C'est donc là une définition récursive, comme pour les arbres binaires. À la
différence de ces derniers. cependant, il n'y a pas de notion d'arborescence vide qui ne contiendrait aucun nœud.
Le cas de base de cette définition récursive est une arborescence qui contient un seul nœud.
Voici un exemple d'arborescence contenant huit nœuds, chacun étant étiqueté par une chaîne de caractères:
____\"A\"____
/ \\
\"B\". __\"C\"___
| / | \\
\"D\". \"E\" \"F\" \"G\"
|
\"H\"
La racine est le nœud étiqueté par \"A\", qui possède deux fils, respectivernent
étiquetés par \"B\" et \"C\".
Certains nœuds possèdent un seul fils, comme \"B\" et \"F\", le nœud \"C\" possède trois fils, et enfin les nœuds \"D\", \"E\", \"H\" et ‘G\" ne possède aucun fils.
Ces derniers sont appelés des feuilles.
Souvent, on se contente de parler d'arbre plutôt que d'arborescence. Cependant, il y a alors un petit risque de confusion entre arbre et arbre binaire.
Certains auteurs utilisent parfois le vocabulaire d'arbre n-aire mais il est là encore source de confusion, certains l'interprétant comme «le nombre de sous-arbres est borné par n». C'est pourquoi
nous avons choisi le terme d'arborescence.
","title":"Arborescence"},{"edit":"Mettre le résultat ici (code et figure).
Arbres binaires et arborescences
Un arbre binaire (séquence précédentes) n'est pas un cas particulier d'arborescence où chaque nœud n'aurait qu'au plus deux fils.
En effet, les arbres binaires font la distinction entre le sous-arbre gauche et le sous-arbre droit.
Ainsi, les deux arbres binaires
__O__ __O__
/ \\ et / \\
_O_ _O_
/ \\ / \\
sont distincts.
On parle d'arbres positionnels pour les arbres binaires.
Une arborescence contenant deux nœuds, c'est-à-dire une racine reliée à un unique fils, ne peut faire la distinction entre ces deux cas.
Certaines notions définies sur les arbres binaires s'appliquent également aux arborescences. Ainsi, on définit la taille d'une arborescence comme son nombre de nœuds et sa hauteur comme le plus grand nombre de nœuds rencontrés en descendant de la racine jusqu'à une feuille.
","title":""},{"edit":"Pour représenter une arborescence en Python, on va utiliser des objets, comme on l'a fait pour les arbres binaires. Le programme ci-dessous contient la définition d'une classe Noeud pour représenter un nœud d'une arborescence.
Programme — Nœud d'une arborescence
class Noeud:
\"\"\"un noeud d'une arborescence\"\"\"
def __init__(self, v, f):
self.valeur = v
self.fils = f
Un objet de cette classe contient deux attributs :
- un attribut valeur dans lequel on stocke une valeur quelconque qui étiquette le nœud;
- et un attribut fils dans lequel on stocke les fils sous la forme d'un tableau.
Avec cette classe, on peut construire l'arbre donné en exemple plus haut de la manière suivante :
a1 = Noeud(\"A\", [Noeud(\"B\", [Noeud(\"D\", [])]), \\
Noeud(\"C\", [Noeud(\"E\", []), \\
Noeud(\"F\", [Noeud(\"H\", [])]), \\
Noeud(\"G\", [])
]) \\
])
On peut ensuite programmer des opérations sur les arborescences d'une façon analogue à ce que nous avons fait avec les arbres binaires, à deux différences près. La première tient dans le traitement d'un tableau de fils plutôt que dans celui de deux sous-arbres.
La seconde différence tient dans le cas de base, qui n'est plus celui d'un arbre vide.
Ainsi, pour calculer la taille d'une arborescence, on peut écrire la fonction récursive suivante:
def taille(a):
t = 1 # Le noeud a lui-même
for f in a.fils:
t += taille(f)
return t
print(taille(a1))
Tester les instruction ci-dessus et conclure.
Un tel calcul se termine bien, car les feuilles ont un attribut fils qui contient un tableau vide. Dans ce cas, la boucle for ne provoque aucun appel récursif et la fonction renvoie le nombre d'élèments de l'arborescence.
De même, on peut écrire un fonction qui réalise un parcours d'arborescence analogue au parcours d'un arbre binaire. Il n'y a pas vraiment d'analogue au parcours infixe (où le sous-arbre gauche était visité avant le nœud, lui-même avant le sous-arbre droit) mais en revanche on peut tout à fait réaliser un parcours préfixe d'une arborescence.
En voici un exemple :
def parcours_prefixe(a):
\"\"\"affiche les éléments de a dans un parcours préfixe\"\"\"
print(a.valeur)
for f in a.fils:
parcours_prefixe(f)
parcours_prefixe(a1)
Cette fonction affiche les éléments de l'arborescence a1 selon un parcours
préfixe, c'est-à-dire en affichant la valeur contenue dans la racine avant de
parcourir récursivement les arborescences de chacun des fils.
Tester le code et conclure.
Mettre le résultat ici (code et figure).
Dans cette section, on détaille deux exemples de structures arborescentes
qui sont aujourd'hui omniprésentes en informatique :
- XML
- JSON.
Les arborescences sont des structures particulièrement adaptées à la représentation de documents.
Considérons un livre. C'est un document structuré :
il contient des chapitres et des paragraphes.
Si c'est un ouvrage technique, il contient aussi des figures, des tables, des sections et des sous-sections.
Une table des matières ou un index peuvent aussi être présents.
On se retrouve donc dans une situation hybride entre des documents à la structure rigide (comme des fichiers CSV avec un nombre fixe de colonnes par exemple) et des documents dépourvus de structure (comme un simple
fichier texte).
Par exemple, on peut vouloir arranger le document de façon à ce que chaque chapitre commence par un titre, puis soit suivi d'une liste non vide de paragraphes.
En revanche, au sein d'un paragraphe, on souhaite simplement mettre des suites arbitraires de caractères.
On appelle ce type de documents des documents semi-structurés.
Le format XML (pour l'anglais eXtensible Markup Language, langage de balises extensibles) est un format de fichier, standardisé par le W3C (pour World Wide Web Consortium).
Ce format est proche du format HTML utilisé pour la représentation des pages web.
Nous présentons ce format, sans rentrer dans les détails de la spécification.
Par exemple, si on souhaite décrire une recette de cuisine, on pourra utiliser le document donné ci-dessous:
<recette difficulté=\"facile\">
<titre>Crêpes sucrées</titre>
<temps>1h</temps>
<note>pour 10 crêpes</note>
<ingredients>
<i q=\"200g\">farine</i>
<i q=\"40g\">sucre</i>
<i q=\"2\">œufs</i>
<i q=\"40cl\">lait</i>
</ingredients>
<etapes>
<e>mélanger les ingrédients solides</e>
<e>ajouter le lait</e>
<e>laisser reposer</e>
<e>cuire sur une poêle beurrée</e>
</etapes>
</recette>
Figure 1 - Un document XML.
Dans ce document, et comme dans les documents HTML, le texte entre chevrons , par exemple, <temps>, </e> ou <i g=\"200g\"> s'appelle une balise (Tag en anglais).
Une balise commençant par </ est appelée balise fermante.
Les autres balises sont appelées balises ouvrantes.
Le texte tel que temps, e où i est le nom de la balise.
Les suites de caractères telles que q=\"200g\" se trouvant dans les balises ouvrantes sont appelés des attributs.
Ici, q est le nom de l'attribut et
200g est sa valeur.
Les documents XML doivent respecter un certain nombre de contraintes de bonne formation. dont voici les principales :
- les balises doivent être bien parenthésées, c'est-à-dire qu'à chaque balise ouvrante doit correspondre une balise fermante avec le même nom de
balise;
- les noms de balises sont sensibles à la casse (temps, TEMPS et Temps
sont trois noms de balise différents);
- tout le contenu du document doit être entouré par une unique paire de balise ouvrante et fermante appelée balise racine;
- les valeurs d'attributs sont toujours présentes et délimitées par des guillemets doubles ou simples;
- il ne peut pas y avoir deux attributs avec le même nom au sein d'une même balise;
- les caractères «<», «>», «&», «'» et «\"» doivent être «échappés» respectivement par « < », « > », « & », « " » et
« ' »;
- n'importe quel caractère Unicode peut être échappé avec la notation « &#n; » où n est le code du caractère, en base 10.
Par exemple, le caractère « ⇔ » peut être saisi comme « ⇔ ».
La spécification du format XML ne fixe pas les noms des balises et des attributs.
Tout un chacun est libre de choisir les noms qu'il souhaite pour pouvoir représenter de l'information.
Une observation importante est qu'à chaque document XML correspond une arborescence, où toute portion complète du document correspond à un nœud.
Par exemple, le document de la figure 1 correspond à l'arbre donné à la figure ci-dessous :
Figure 2 — Arborescence du document de la figure 1.
Mettre le résultat ici (code et figure).
Le W3C ne se limite pas à spécifier le format des fichiers XML. Il définit
aussi le modèle d'arborescence correspondant aux documents.
En quelques mots, ce modèle impose la présence d'un nœud document. Ce dernier est un nœud fictif, ne correspondant à aucune balise, et défini comme parent du
nœud correspondant à la balise racine.
Tous les autres fragments du document XML sont représentés. Les balises correspondent à des nœuds internes de l'arborescence, On appelle de tels nœuds des éléments de l'arborescence XML.
Les attributs sont associés au nœud de la balise dans laquelle ils sont.
Les caractères sont naturellement les feuilles de l'arborescence.
Le W3C définit aussi la façon dont de tels arbres sont représentés dans des langages orientés objets.
C'est le standard DOM (pour Document Object Model où modèle objet de document). Ce standard du W3C définit les noms de classes, de méthodes, d'attributs ou les constantes qui permettent de manipuler un document XML.
L'intérêt d'un tel standard est que les noms des concepts seront les mêmes, quels que soit le langage de programmation utilisé. Dans le modèle DOM, les nœuds de l'arbre possèdent les attributs suivants: :
type : le type de nœud considéré (élément, texte, nœud document, etc.)
nom : le nom du nœud. Les éléments ont pour nom le nom de la balise associée (ingrédients , étapes etc ). Le noeud document a pour nom la chaîne constante #document. Les nœuds texte ont pour nom la chaîne constante #text.
valeur : les nœuds texte ont comme valeur la chaîne de caractères correspondant à ce nœud dans le document initial (par exemple pour 10 crêpes).
fils : chaque nœud a une liste de fils (qui peut être vide dans le cas de feuilles).
parent : chaque nœud a un nœud parent, excepté le nœud document.
En Python, les fonctions et classes permettant de manipuler un document XML se trouvent dans le module xml.dom.minidom. Il est usuel de
donner à ce module un alias plus court :
import xml.dom.minidom as dom
Ce module contient une implémentation «minimale» de la spécification DOM du W3C (d'où son nom).
Nous faisons un bref tour d'horizon, forcément partiel, de cette vaste bibliothèque et montrons comme elle permet de manipuler des documents XML comme de simples arborescences.
Les fonctions dom.parse et dom.parseString permettent de charger un document XML à partir d'un fichier ou d'une chaîne de caractères, comme le montre l'exemple ci-dessous :
import xml.dom.minidom as dom
#Méthode 1
doc1 = dom.parse(\"fichier.xml\")
print(doc1)
#Méthode 2
f = open (\"fichier.xml\")
doc2 = dom.parse(f)
print(doc2)
#Mé‡thode 3
doc3 = dom.parseString(\"<a>mon joli <b>document</b></a>\")
print(doc3)
Télécharger le fichier xml fichier.xml et le mettre dans le même dossier que votre programme.
Tester le programme et conclure.
Une fois chargé, un document XML est un objet de la classe dom.Node.
Il possède les méthodes et attributs que nous listons dans la table suivante :
Attributs pour tous les types de noeuds
| nom | description |
| .nodeType | Entier représentant le type du nœud. Les constantes de type de nœud sont des attributs de la classe Node : dom.Node.ELEMENT_NODE, dom.Node .TEXT dom.Node .DOCUMENT_NODE, etc. |
| .nodeName | Chaîne de caractères représentant le nom du nœud |
| .nodeValue | Chaîne de caractères représentant la valeur du nœud pour les nœuds de type texte et attribut. None pour les autres types de nœuds. |
| .childNodes | Liste contenant les nœuds fils du nœud courant. |
| .attributes | Dictionnaire associant les noms des attributs du nœud à des nœuds attributs. |
Méthodes pour le nœud document
| nom | description |
| .createElemant(n) | Crée un nouveau nœud élément dont le nom est donné par la chaîne de caractères n. |
| createTextNode(t) | Crée un nouveau nœud texte dont la valeur don. née par la chaîne de caractères t. |
| .toxml() | Renvoic le document comme une chaîne de carac- tères afin de le sauver dans un fichier. Méthode utilitaire Python, ne faisant pas partie de DOM. |
Méthodes pour le nœud document ou les nœuds éléments
| nom | description |
| .appendChild(n) | Ajoute le nœud n comme dernier fils du nœud courant. |
| .insertBefore(c, n) | Ajoute le nœud n juste avant le nœud c, qui doit être un fils du nœud courant. |
| .removeChild(n) | Supprime le nœud n, qui doit être un fils du nœud courant. |
Méthodes pour les nœud
| nom | description |
| .setAttribute(n,v) | Ajoute ou modifie l'attribut de nom n pour lui donner la valeur v. |
| .basAttribute(n) | Teste si le nœud courrant possède un attribut n. |
| removeAttribute(n) | Retire l'attribut de nom n du nœud courrant. |
Ainsi, en utilisant ces attributs, on peut définir par exemple une fonction
tailleDOM(d) semblable à la fonction récursive taille de la section précédente:
def tailleDOM(d):
t=1
for c in d.childNodes:
t += tailleDOM(c)
return t
print(\"doc1\",tailleDOM(doc1))
print(\"doc2\",tailleDOM(doc2))
print(\"doc3\",tailleDOM(doc3))
Tester le code et conclure.
Le modèle DOM impose des invariants lors de la création et ajout de nœuds pour garantir que l'objet résultant représente toujours une arborescence.
On illustre ce comportement avec un exemple:
Nous créons un document avec uniquement une racine :
doc4 = dom.parseString(\"<a></a>\")
a = doc4.childNodes[0] # doc est le nœud #document, son seul
# fils est la balise racine
b = doc4.createElement(\"b\") # on crée un nouveau nœud
c = doc4.createElement(\"c\") # on crée un nouveau nœud
a.appendChild(b) # on ajoute b comme fils de a
a.appendChild(c) # on ajoute c comme fils de a
Le code précédent crée, à partir d'une chaîne de caractères, un document minimal.
Attention, ce document possède deux nœuds, celui correspondant au nœud fictif #document et celui correspondant à la balise racine.
On utilise le nœud document pour créer deux nouveaux nœuds, b et c. Ces nœuds sont pour l'instant détachés et n'apparaissent pas dans l'arborescence.
On peut les accrocher en utilisant la méthode .appendChild du nœud auquel on veut les ajouter, ici la racine a.
À la fin de l'exécution de ce code, on obtient en mémoire une arborescence correspondant au document
<a><b></b><c></c></a>.
Si on effectue de nouveau l'ajout d'un nœud se trouvant déjà dans la structure, alors la bibliothèque va déplacer ce nœud, si c'est possible :
a.appendChild(b)
Cet appel de méthode a pour effet de détacher le nœud b de l'arbre et de le
rajouter à la fin des fils de a.
Lorsque ce déplacement n'est pas possible, la méthode de déplacement lève
une erreur, comme le montre les exemples suivants :
doc = dom.parseString(\"<a></a>\")
a = doc.childNodes[0]
b = doc.createElement(\"b\")
doc.appendChild(b)
Ici, on crée un nouveau nœud b et on essaye de l'ajouter avant (ie., comme
frère précédent) le nœud a.
Ceci lève une erreur :
xml.dom.HierarchyRequestErr: two document elements disallowed
Le standard XML va bien au-delà de cette simple présentation.
Cette dernière permet cependant d'utiliser des documents XML, par exemple pour en extraire de l'information, ou d'utiliser un document XML comme format
d'échange entre deux programmes.
Un aspect important du format XML est
la notion de schéma ou de type associé à un document.
En effet, il est possible de spécifier précisément la structure que doit avoir un document (balises autorisées, forme de leur contenu, etc.).
Ces schémas permettent de définir une notion de documents valides et peuvent être vérifiés automatiquement lors du chargement du fichier.
Cette notion est particulièrement cruciale car elle réduit de façon importante le volume de code que le programmeur doit écrire.
Ainsi, le programmeur n'a pas besoin de tester explicitement que la racine s'appelle recette, qu'elle a bien un attribut difficulté, qu'elle a une liste non vide d'ingrédients, etc.
Elle permet aussi de forcer certains
invariants (par exemple, que tel élément contient toujours une date et non
pas des caractères arbitraires), ce qui est important dans un contexte de manipulation de données.
Mettre le résultat ici (code et figure).
https://docs.python.org/3.4/library/xml.etree.elementtree.html
Lisez la documentattion de etree.
","title":""},{"edit":"Les fonctions etree.parse et etree.XML permettent de charger un document XML à partir d'un fichier ou d'une chaîne de caractères, comme le montre l'exemple ci-dessous :
#Méthode 1
doc1 = ET.parse(\"fichier.xml\")
root1 = doc1.getroot()
print(root1)
#Méthode 2
f = open (\"fichier.xml\")
doc2 = ET.parse(f)
root2 = doc2.getroot()
print(root2)
#Mé‡thode 3
doc3 = ET.XML(\"<a>mon joli <b>document</b></a>\")
print(doc3)
Télécharger le fichier xml fichier.xml et le mettre dans le même dossier que votre programme.
Tester le programme et conclure.
A partir de la documentation ETREE, on peut définir par une fonction
tailleETREE(d) semblable à la fonction récursive taille et tailleDOM:
def tailleETREE(d):
t=1
for c in d:
t += tailleETREE(c)
return t
print(\"doc1\",tailleETREE(root1))
print(\"doc2\",tailleETREE(root2))
print(\"doc3\",tailleETREE(doc3))
Tester la fonction tailleETREE et la comparer à tailleDOM.
Si nous voulons maintenant créer un document xml de la forme suivante avec ETREE:
__\"a\"__
/ \\
\"b\" \"c\"
|
\"d\"
Avec ETREE, il faudra utiliser le code suivant :a = ET.Element('a')
b = ET.SubElement(a, 'b')
c = ET.SubElement(a, 'c')
d = ET.SubElement(c, 'd')
#affiche arborescence de a
ET.dump(a)
Mettre le résultat ici (code et figure).
Bien que le format XML remplisse son rôle de format standard pour les données semi-structurées, il souffre de plusieurs défauts.
En premier lieu, la spécification est très longue, contenant de nombreux documents annexes remplis de détails subtils.
En second lieu, il est considéré comme verbeux.
Bien que l'un des buts du W3C ait été de proposer un format de fichiers lisible par un humain, l'abondance de balises et de séquences d'échappement rend les documents peu lisibles en pratique.
Enfin, le modèle DOM qui impose les noms d'attributs et de méthodes se trouve fortement inspiré par la bibliothèque standard du langage Java et son utilisation pousse les prograinmeurs des autres langages (Python, JavaScript, etc.) à écrire du code souvent non idiomatique.
Avec l'avènement du Web, et en particulier de la programmation «côté
client» en JavaScript, le besoin s'est fait sentir de disposer d'un format flexible et compact permettant l'échange de données entre le client. (le navigateur web) et le serveur web.
Cela a donné lieu à l'introduction du format JSON (JavaScript Object Notation ou notation objet JavaScript) au début des années 2000. Ce format à été ensuite standardisé par différents organismes internationaux tels que l'ECMA (référence ECMA-404) ou l'ISO (référence 180 21778 :2017).
Le nom est tiré du fait que le format utilise la même syntaxe que celle des objets dans le langage JavaScript.
En JavaScript, un «objet» correspond plus ou moins à un dictionnaire Python, tout du moins du point de vue syntaxique.
Un exemple de fichier JSON, contenant la même recette que le fichier XML donné en exemple dans la section précédente, est donné à la figure 3.
{
\"titre\" : \"Crêpes sucrées\",
\"difficulté\" : \"facile\",
\"temps\" : { \"unité\" : \"h\", \"valeur\" : 1 },
\"note\" : \"pour 10 crêpes\",
\"ingredients\" : [
{ \"nom\" : \"farine\", \"q\" : { \"unité\" : \"g\", \"valeur\" : 200 } },
{ \"nom\" : \"sucre\", \"q\" : { \"unité\" : \"g\", \"valeur\" : 200 } },
{ \"nom\" : \"œufs\", \"q\" : { \"unité\" : \"\", \"valeur\" : 2 }},
{ \"nom\" : \"lait\", \"q\" : { \"unité\" : \"cl\", \"valeur\" : 40 }}
],
\"étapes\" : [
\"mélanger les ingrédients solides\",
\"ajouter le lait\",
\"laisser reposer\",
\"cuire sur une poële beurrée\" ]
}
Figure 3 - Un fichier JSON de la recette des crêpes
À l'inverse des fichiers XML, la syntaxe
JSON est plus simple d'approche pour un programmeur Python. Les valeurs JSON peuvent être de six types différents. II y à quatre types simples :
null : une constante spéciale indiquant une absence de voleur similaire à la constante None de Python;
booléens : représentés par les deux constantes true et false (en minuscule);
nombres : peuvent être entiers ou flottants {dans ce deuxième cas, la notation scientifique standard est utilisée, c'est-à-dire une mantisse et
éventuellement un E ou e suivi d'un entier représentant une puissance de 10, comme -1.2E23 qui représente —1.2 x 10^23;
chaînes de caractères : délimitées par des guillemets doubles « \" » obligatoirement et encodées en UTF-8.
Par exemple, true, 6.022e23, \"Bonjour 1es amis!\" et null sont des valeurs JSON valides.
À ces quatre types simples s'ajoutent deux types structurés :
tableaux : identiques aux tableaux Python. Les tableaux sont délimités
par des crochets et les éléments sont séparés par des virgules. Un tableau contient une suite de valeurs JSON (qui peuvent être de types différents).
objets : similaires aux dictionnaires Python. Les objets JSON sont délimités par des accolades. Ils contiennent des associations clés-valeurs. Les clés sont obligatoirement des chaînes de caractères au format décrit ci-dessus.
Les valeurs peuvent être n'importe quelles valeurs JSON.
Les clés sont séparées des valeurs par le caractère « : ».
Les différentes associations sont séparées par des virgules.
Cette proximité de syntaxe et de types fait que l'utilisation de données JSON en Python est très simple.
Les fonctions nécessaires se trouvent dans le module json.
En premier lieu, on peut lire une valeur JSON, soit en la chargeant depuis un fichier ouvert avec la fonction open, soit à partir d'une chaîne de caractères.
Ces opérations sont offertes par les fonctions json.load et json.loads respectivement :
import json
f = open(\"recette.json\") # ouverture du fichier en lecture
recette = json.load(f) # chargement du fichier
f.close()
print(recette[\"titre\"]) # affiche Crêpes sucrées
print(recette[\"ingredients\"][2][\"nom\"]) # affiche œufs
d = json.loads('{ \"nom\" : \"Sérudier\" , \"prénom\" : \"Paul\"}')
print(d[\"nom\"]) # affiche Knuth
Télécharger le recette json recette.json et le mettre dans le même dossier que votre programme.
Tester le programme et conclure.
Comme on le voit, utilisation est très simple. Une fois le fichier ou la chaîne
de caractères chargés, les valeurs JSON sont traduites automatiquement en
valeur Python. Il est ensuite possible de les manipuler comme on le souhaite.
Attention, comme dans le cas des documents XML, manipuler la structure de
données en mémoire n'a aucun impact sur le fichier. Si on souhaite modifier
le fichier, il faut écrire l'objet modifié dans un fichier, ou le sérialiser sous
forme d'une chaîne de caractères qui pourra être écrite dans un fichier. C'est
le rôle des fonction json.dump ct json.dumps :
#modifie le titre
recette['titre'] = \"La soupe aux choux\"
f2 = open(\"recette_mod.json\", \"w+\") # ouverture en écriture
# et création si besoin
json.dump(recette, f2)
f2.close()
d = { 'a' : None, 'b' : False }
print(json.dumps(d))
Tester le code et ouvrir le fichier recette_mod.json et conclure.
Comme on le voit, les fonctions json.dump et json.dumps effectuent une traduction inverse, des valeurs Python vers les valeurs JSON.
Cette traduction n'est pas toujours possible. Dans ce cas, la fonction lève une exception :
d = { 'b' : b\"1234\" }
json.dumps (d)
TypeËrror: Qbject of type bytes is not JSON serializabled= {tx :1}
d{\"y\"] = à
json.dumps (4)
ValueError: Circular reference detected
Bien que les valeurs JSON soient des structures arborescentes, elles possèdent quelques différences notables avec les arbres et les arborescences décrites jusqu'à présent.
En premier lieu, elles ne possèdent pas de nœud «racine». En effet, une arborescence JSON est soit un type de base, soit un tableau, soit un dictionnaire.
Ensuite, lorsque lon parcourt une structure JSON, on est dépendant de l'ordre de parcours des clés dans un dictionnaire. Cette ordre peut être influencé par de nombreux facteurs (numéro de version de Python, ordre d'insertion, type exact du dictionnaire, etc.).
Mettre le résultat ici (code et figure).
Une arborescence, souvent désignée simplement comme un arbre, est un ensemble de nœuds structurés avec une racine reliée à des nœuds fils, eux-mêmes racines d'autres arborescences.
De telles arborescences sont utilisées pour organiser l'information.
Les formats XML et JSON en sont deux exemples, omniprésents dans l'informatique d'aujourd'hui.
Mettre le résultat ici (code et figure).
Écrire une fonction affiche(a) qui affiche une arborescence
sous la forme
A
B
D
C
E
F
H
G
c'est-à-dire qui affiche les nœuds selon un parcours préfixe, avec un nœud
par ligne et une marge qui est proportionnelle à la profondeur du nœud
dans l'arbre.
Indication : écrire une fonction récursive, qui prend comme paramètre supplémentaire une chaîne de caractères, constituée d'espaces, à afficher avant la valeur du noeud.
Tester avec :
a1 = Noeud(\"A\", [Noeud(\"B\", [Noeud(\"D\", [])]), \\
Noeud(\"C\", [Noeud(\"E\", []), \\
Noeud(\"F\", [Noeud(\"H\", [])]), \\
Noeud(\"G\", [])
]) \\
])
affiche(\"\",a1)
Mettre le résultat ici (code et figure).
La chaîne p est la marge, qu’on augmente de deux espaces pour l'affichage des sous-arbres.
def affiche(p, a):
print(p + str(a.valeur))
for f in a.fils:
affiche(p +\" \", f)
Le système de fichiers d'un ordinateur, et en particulier les répertoires qui le composent, peut être considéré comme une arborescence en première approximation.
Dans cet exercice, on se propose d'écrire une fonction Python repertoires qui reçoit en argument un nom de répertoire
et renvoie une arborescence, au sens du programme 35, qui décrit la structure
récursive de ses sous-répertoires.
Pour cela, on pourra se servir des fonctions suivantes fournies par la bibliothèque os :
- La fonction os.listdir(r) renvoie un tableau de tous les fichiers contenus dans le répertoire r, dont les sous-dossiers de r.
- La fonction os.path.join(r, f) permet de concaténer le nom du répertoire x au nom d'un fichier f qu'il contient pour construire le nom complet de ce fichier.
- La fonction os.path.isdir(f) permet de tester si le nom de fichier f désigne un répertoire.
Tester le résultat de cette fonction repertoires en l'affichant avec la fonction de l'exercice précédent.
affiche(\"\",repertoires(\"C:\\Users\\\"))
Attention changer le nom du répertoire racine C:\\Users\\
Mettre le résultat ici (code et figure).
import os
def repertoires(racine):
assert os.path.isdir(racine)
n = Noeud(racine, [])
for f in os.listdir(racine):
p = os.path.join(racine, f)
if os.path.isdir(p):
n.fils.append(repertoires(p))
return n
Pour chacun des petits documents XML ci-dessous, dire s'il est
bien formé.
Si ce n'est pas le cas, indiquer l'erreur.
1. <a></a>
2. <a>
<b></b>
<b></b>
</a>
3. <a>
<b></B> 7 | <bid=\"45\" ia=\"agr></b>
</a> </a>
4. <a>
<b>
</a>
5. <a></a>
<a></a>
6. <a>
<b id=\"45\" v='45'></b>
</a>
7. <a>
<b id=\"45\" id=\"48\"></b>
</a>
8.
<a>
<b id=\"45\"></b>
<b id=\"45\"></b>
</a>
Mettre le résultat ici (code et figure).
1. Correct.
2. Correct.
3. Incorrect, la balise fermante n’est utilise une majuscule.
4. Incorrect, il manque une balise fermante.
5. Incorrect, il y a deux balises racines.
6. Correct.
7. Incorrect, il y a deux attributs avec la même valeur.
8. Correct.
A l'aide du module DOM, écrire une fonction récursive compte_balise(d, n) qui prend en argument un nœud DOM d et un nom de balise n et qui renvoie le nombre de nœuds ayant ce nom dans le document.
Tester avec :
import xml.dom.minidom as dom
doc1 = dom.parse(\"fichier.xml\")
print(\"nb balises :\",compte_balise(doc1,\"libelle\"))
Résultat :
25
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
On utilise une variante de la fonction tailleDOM.
def compte_balise(d,n):
if d.nodeName == n :
t = 1
else:
t = 0
for c in d.childNodes:
t += compte_balise(c, n)
return t
A l'aide du module DOM, écrire une fonction récursive stat_xml(d) qui prend en argument un nœud DOM d et renvoie le triplet (e,a,t) constitué du nombre e d'éléments, a d'attributs et t de textes.
Tester avec :
import xml.dom.minidom as dom
doc1 = dom.parse(\"fichier.xml\")
print(stat_xml(doc1,(0,0,0)))
Résultat :
(146, 90, 291)
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
def stat_xml(d,n):
if d.nodeType == dom.Node.TEXT_NODE:
t=1
else:
t = 0
if d.nodeType == dom.Node.ELEMENT_NODE:
e= 1
a = len(d.attributes)
else:
e = 0
a = 0
for c in d.childNodes:
(ne, na, nt) = stat_xml(c,(e,a,t))
e += ne
a += na
t += nt
return (e, a, t)
Attention, lors des tests, les espaces et retours à la lignes ajoutés pour in-
denter le document XML sont aussi des nœuds texte.
A l'aide du module DOM, écrire une fonction gen_doc(n) qui prend en argument un entier n et génère un document XML de Ia forme :
<a><b>0</b><b>1</b>...<b>n — 1</b></a>
et sauve ce document dans un fichier docn.xml.
Tester avec :
import xml.dom.minidom as dom
gen_doc(100)
Une fois la fonction exécuter, ouvrir le fichier doc100.xml et vérifier que la structure est correcte.
Mettre le résultat ici (code et figure).
def gen_doc(n):
doc = dom.parseString(\"<a></a>\")
a = doc.childNodes[0]
for i in range(n):
b = doc.createElement(\"b\")
t = doc.createTextNode(str(i))
b.appendChild(t)
a.appendChild(b)
with open(\"doc\" + str(n) + \".xml\", \"w\") as f:
f.write(doc.toxml())
A l'aide du module ETREE, écrire une fonction gen_doc2(n) qui prend en argument un entier n et génère un document XML de Ia forme :
<a><b>0</b><b>1</b>...<b>n — 1</b></a>
et sauve ce document dans un fichier docn1.xml.
Indication : Il faut utiliser les méthodes suivantes pour copier le fichier xml:
tree = ET.ElementTree(a)
tree.write('doc'+str(n)+'1.xml', xml_declaration=True, encoding=\"utf-8\")
Tester avec :
import xml.etree.ElementTree as ET
gen_doc2(100)
Une fois la fonction exécuter, ouvrir le fichier doc1001.xml et vérifier que la structure est correcte.
Mettre le résultat ici (code et figure).
def gen_doc2(n):
a = ET.Element('a')
for i in range(n):
b = ET.SubElement(a, 'b')
b.text = str(i)
tree = ET.ElementTree(a)
tree.write('doc'+str(n)+'1.xml', xml_declaration=True, encoding=\"utf-8\")
gen_doc2(100)
Écrire un programme hello_json.py qui charge un fichier JSON config.json contenant un dictionnaire à deux entrées. Une entrée \"mode\" contenant la chaîne \"bonjour\" et une entrée \"nom\" contenant un nom de personne (par exemple \"Toto\").
Le programme affiche ensuite «bonjour Toto».
Attention, le fichier config.xml doit contenir les éléments suivants :
{\"mode\":\"bonjour\",\"nom\":\"Toto\"}
Tester avec :
import json
print(config[\"mode\"], config[\"nom\"])
Résultat :
bonjour Toto
Mettre le résultat ici (code et figure).
with open(\"config.json\") as f:
config = json.load(f)
Indications : Regarder la structure de fichier.xml pour l'analyser et choisir ses attributs en conséquences.
Mettre les différents éléments dans un dictionnaire.
Comparer la taille du fichier.xml et du fichier.json. Conclure sur l'avantage du format JSON par rapport au XML.
","title":"Exercice","tagtitle":"h1"},{"edit":"Mettre le résultat ici (code et figure).
import xml.etree.ElementTree as ET
import json
#charger le fichier xml
doc = ET.parse(\"fichier.xml\")
root = doc.getroot()
dic = {}
for c in root:
if c.tag != 'question' :
dic[c.tag] = c.text
else :
sousdic = {}
tabRep = []
tabSol = []
for sc in c :
if sc.tag == \"libelle\" :
sousdic[sc.tag] = sc.text
else :
tabRep.append(sc.text)
sol = sc.attrib
tabSol.append(sol['sol'])
sousdic['reponse'] = tabRep
sousdic['sol'] = tabSol
quest = dic.get(\"question\")
if quest is None :
dic['question'] = []
dic['question'].append(sousdic)
else :
dic['question'].append(sousdic)
with open('fichier.json', 'w') as f:
json.dump(dic, f)
Le fichier.json contient un quizz sur Python.
A l'aide de ce fichier, écrire un programme qui réaliser le quizz.Indications :
Etape 1 : Charger le fichier.json
Etape 2 : Initialiser les variables bonnes_reponses et questions.
Etape 3 : Afficher les questions une à une.
Etape 4 : Afficher le libéllé.
Etape 5 : Afficher les réponses
Etape 6 : Traiter la réponse donnée par l'utilisateur.
Mettre le résultat ici (code et figure).
import json
#Charger le quizz au format json
with open(\"fichier.json\") as f:
quizz = json.load(f)
questions = quizz['question']
bonnes_reponses = 0
#Affichage des questions
for question in questions :
#Affichage du libéllé
print(question['libelle'])
i = 1
#affichage des réponses
for reponse in question['reponse'] :
print(i ,reponse )
i+=1
#traitement de la réponse
myrep = int(input(\"Answer the question ? \"))
solution = question['sol']
if solution[myrep-1] == 'true':
bonnes_reponses +=1
print(\"Yes\")
else :
print(\"No\")
print(\"Your score is : \",bonnes_reponses,\"/25\")
Dans cette api, l'utilisateur rentrera un nom de pays (Exemple France) et le programme ira chercher dans la base de donnée world.sql (Télécharger ici) les informations suivantes :
- Capitale
- Population
- Continent
- Surface du pays
- Espérance de vie
pour les afficher sur la page web.
Ces données sont transmise entre le serveur (serveur.py) et le client (index.html) au format json.
Vous utiliserons les 2 fichiers ci-dessous pour réaliser cette api :
index.html
<!DOCTYPE html>
<html>
<head>
<title>Front End</title>
<meta charset=\"utf-8\"/>
<script>
function miseAJourPage() {
//déclaration de l'objet contenant les données à envoyer.
var data = [];
var param1 = document.getElementById('param1').value;
var param2 = document.getElementById('param2').value;
data.push({
'param1' : param1,
'param2' : param2
})
data = JSON.stringify(data[0]);
//alert(data);
//declaration de l'objet pour la requete
var maRequete = new XMLHttpRequest();
//url du serveur
var url = \"cgi\";
//gestion de la reponse du serveur
maRequete.onreadystatechange = function () {
if (maRequete.readyState == 4) {
//affiche la réponse du serveur
//alert(maRequete.responseText);
//convertis la reponse du serveur en dictionnaire
var tabkeyvalue = JSON.parse(maRequete.responseText);
//remplis les id dans le body
for(var key in tabkeyvalue) {
//alert(key);
document.getElementById(key).innerHTML = tabkeyvalue[key];
}
}
}
//Choisir le type de requete
maRequete.open(\"POST\", url, true);
//Entête de la requete pour la méthode POST
maRequete.setRequestHeader(\"Content-Type\", \"application/json\");
//envoyer la requete au serveur
maRequete.send(data);
}
</script>
</head>
<body>
<div>
<label>Paramètre 1 : </label><input id=\"param1\" type=\"text\">
</div>
<div>
<label>Paramètre 2 : </label><input id=\"param2\" type=\"text\">
</div>
<div><input type=\"button\" value=\" Envoyer \" onclick=\"miseAJourPage()\"></div>
<!-- Ajouter les clés du json ici-->
<div>Capital : <span id=\"capital\"></span></div>
</body>
</html>
et serveur.py
import socketserver
import http.server
import logging
import urllib
import json
import mysql.connector as sgbd
#Entrer l'adresse IP du serveur ou le nom de domaine
HOST = \"217.182.207.90\" # ou \"domaine.com\"
#Le nom de la base de données
DATABASE = \"\" #changer le ? par le numero donnée par le professeur
#Le nom de l'utilisateur de la DB
USER = \"\"
# Le mot de passe de l'utilisateur
PASSWORD = \"\"
def requeteSQL(dic):
# Rentrer votre code ici
#connection à la SGDB
cnx = sgbd.connect(host=HOST, database=DATABASE, user=USER, password=PASSWORD)
print(\"Connecté à:\", cnx.get_server_info())
#recuperation du paramètre 1 du client
param1 = dic['param1']
#creation de la requete
c = cnx.cursor()
#A modifier
requete = \"\"\" SELECT city.name,countryinfo.population FROM country JOIN city , countryinfo
WHERE country.code = city.code
AND country.code = countryinfo.code
AND country.capital = city.ID
AND country.name = %s
\"\"\"
#Exécution de la requete
c.execute( requete , [ param1 ])
#Récupéaration du résultat dans un tableau
tab = c.fetchall()
print('tab=',tab)
#Récupération de la 1ère valeur du tab
tup = tab[0]
print(tup[0],tup[1])
cnx.close()
#retour du fichier json avec les éléments recherchés
#A modifier
return {'capital' : tup[0]}
####################################################
# Ne pas modifier
####################################################
PORT = 8000
class ServerHandler(http.server.SimpleHTTPRequestHandler):
def _set_headers(self):
self.send_response(200)
self.send_header('Content-type', 'application/json')
self.end_headers()
def do_GET(self):
logging.error(self.headers)
http.server.SimpleHTTPRequestHandler.do_GET(self)
def do_POST(self):
\"\"\" response for a POST \"\"\"
#traite le message du client
length = int(self.headers['content-length'])
messageRecu = json.loads(self.rfile.read(length))
print(\"message reçu :\",messageRecu)
messageEnvoyer = requeteSQL(messageRecu)
print(\"message envoyé :\",messageEnvoyer)
#renvoie un message json au client
self._set_headers()
self.wfile.write(bytes(json.dumps(messageEnvoyer),'utf-8'))
Handler = ServerHandler
httpd = socketserver.TCPServer((\"\", PORT), Handler)
print(\"Adresse : http://localhost:\"+str(PORT))
httpd.serve_forever()
Pour réaliser cette api, suivrez les étapes suivantes :
Etape 1 : Copier les 2 fichiers dans le même répertoire.
Etape 2 : Lancer serveur.py
Etape 3 : Analyser le code des 2 pages.
Etape 4 : Aller à l'adresse internet indiqué par le programme.
Etape 5 ; Rentrer dans paramètre 1: France et cliquer sur envoyer.
Etape 6 ; Compléter le code coté serveur pour mettre en forme (json) les informations demandées sur le pays.
Etape 7 : Compléter index.html pour afficher les informations envoyé par le serveur.
Format de la table countryinfo :
Table countryinfo |
` ( code, le code du pays indepyear, date indépendance pays region, la région ou se situe le pays continent, le continent ou se situe le pays surfaceArea, la surface du pays `governmentForm, le régime du pays `population lifeExpectancy, l'espérance de vie du pays |
Mettre le résultat ici (code et figure).
- Détails
- Écrit par : Richard GAUTHIER
- Clics : 1618
[[{"text":"
"}],[{"text":"
","title":"Notion"},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":"Recherche dans un ABR"},{"edit":"
"}],[{"text":"
__3__
"}],[{"text":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
"}],[{"text":"
![\"arbre9.png](\"https://sciencesappliquees.com/images/nsi/arbre9.png\")
![\"arbre9.png](\"https://sciencesappliquees.com/images/nsi/arbre10.png\")
","title":"Encapsulation dans un objet"},{"edit":"
"}],[{"text":"
"}],[{"text":"
","title":"Conclusion"},{"edit":"
"}],[{"text":"
"},{"solution":"Parce qu’il y a 26x26x26 = 263 = 17576 mots de trois lettres."}],[{"text":"
"},{"solution":"
"}],[{"text":"
"},{"solution":"
"}],[{"text":"
"},{"solution":"
"}],[{"text":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice","tagtitle":"h1"},{"edit":"
"},{"solution":"
"}],[{"text":"
"},{"solution":"
"},{"solution":""}],[{"text":"Ajouter la méthode supprimer(self,x) à la classe a qui supprime l'élément x de l'arbre.","title":"Exercice"},{"edit":"
"},{"solution":""}]]
Imaginons une bibliothèque qui contienne vraiment beaucoup de livres l, répartis dans 17 576 salles reliées les unes aux autres par des portes.
Chaque salle contient une porte d'entrée et, possiblement, deux portes de sorties vers deux autres salles.
Pour retrouver facilement l'emplacement d'un livre, les bibliothécaires astucieux ont eu l'idée suivante. Dans la toute première salle, dans laquelle on entre par la porte d'entrée de la bibliothèque, ils ont mis tous les ouvrages dont le titre commence par MDB.
Si en revanche le titre commence par trois lettres venant avant MDB dans l'ordre alphabétique, alors il faut prendre la porte de sortie de gauche. Sinon, il faut prendre la porte
de sortie de droite.
On continue alors la recherche dans la salle suivante.
Si on est allé dans la salle de gauche, par exemple, on y trouve tous les ouvrages dont le titre commence par GBN. Là, de même, si le titre commence par trois lettres venant avant GBN dans l'ordre alphabétique, alors il faut prendre la porte de sortie de gauche, sinon la porte de droite. Et ainsi de
suite jusqu'à ce qu'on parvienne à la salle contenant tous les livres dont les trois premières lettres du titre sont celles du titre qui nous intéresse.
Une telle organisation est incroyablement efficace. En effet, avec la répartition choisie par les bibliothécaires, il ne faut jamais traverser plus de 15 salles pour trouver un ouvrage, alors qu'il y à, rappelons-le, 17576 salles au total.
******
Lu LHABIUS 7e PULIED WING UE IEUNIGIUIIS
On peut visualiser les salles de cette bibliothèque comme un arbre binaire, où chaque nœud correspond à une salle.
Un nœud est étiqueté par un mot de trois lettres et ses deux sous-arbres correspondent aux salles adjacentes.
Dans l'exemple ci-dessus, le haut de cet arbre ressemble à ceci :
___MDB____
/ \\
_GEN_ _SEP_
/ \\ / \\
... _JOH_ ... ...
/ \\
... ...
Comme on l'a compris, quand on se dirige du côté gauche, on trouve des mots plus petits dans l'ordre alphabétique et quand on se dirige du côté droit, on trouve des mots plus grands. Et cette propriété n'est pas vraie seulement pour la racine.
Elle est valable pour tous les nœuds de l'arbre.
Ainsi, dans le sous-arbre droit du nœud marqué JCH, on trouvera des mots plus grands que JCH et plus petits que MDB (car on reste à gauche de la racine).
De même, dans le sous-arbre gauche du nœud marqué SEP, on trouvera des mots plus petits que SEP mais plus grands que MDB (car on reste à droite de la racine).Et ainsi de suite.
On appelle cela un arbre binaire de recherche.
","title":"Arbres binaires de recherche","tagtitle":"h1"},{"edit":"D'une manière générale, un arbre binaire de recherche (abrégé en ABR ou en anglais BST Binary Search Tree) est un arbre binaire dont les nœuds contiennent des valeurs qui peuvent être comparées entre elles, comme des entiers ou des chaînes de caractères par exemple, et tel que, pour tout nœud de l'arbre, toutes les valeurs situées dans le sous-arbre gauche (resp. droit) sont plus petites (resp. plus grandes) que la valeur située dans le nœud.
Ainsi, les deux arbres de gauche sont des ABR, mais celui de droite n'en est pas un:
___3___ / \\ _1_ _4_ / \\ / \\ _2_ / \\ | ___3___ / \\ _2_ _4_ / \\ / \\ _1_ / \\ | ___3___ / \\ _2_ _4_ / \\ / \\ _1_ / \\ |
Pour l'arbre de droite, la propriété est bien vérifiée pour la racine, mais
elle ne l'est pas pour le nœud étiqueté par 2, qui contient 1 dans son sous-
arbre droit.
Comme l'illustrent les deux arbres de gauche, les mêmes valeurs peuvent être stockées dans plusieurs ABR différents.
Représentation en Python
Un ABR étant un arbre binaire, on le représente en Python exactement comme à la séquence précédente avec notre classe Noeud.
On nc fait qu'ajouter deux
contraintes :
- les valeurs contenues dans les nœuds peuvent être comparées avec les opérations <, >=, etc., de Python (c'est le cas des entiers et des chaînes de caractère notamment);
- les arbres vérifient la propriété d'ABR.
Ces deux contraintes ne sont pas encodées en Python.
Elles sont uniquement supposées ou garanties, selon le cas, par les fonctions que nous allons écrire dans les sections suivantes.
class Noeud:
\"\"\"un noeud d'un arbre binaire\"\"\"
def __init__(self, g, v, d):
self.gauche = g
self.valeur = v
self.droit = d
def __eq__(self, n):
return n is not None \\
and self.gauche == n.gauche \\
and self.valeur == n.valeur \\
and self.droit == n.droit
Opérations
Les fonctions définies à la séquence précédent sur les arbres binaires, à savoir taille, hauteur et parcours_infixe restent valables pour des ABR.
En particulier, le parcours infixe d'un ABR affiche les valeurs contenues dans
l'ABR par ordre croissant.
En effet, il commence par afficher les valeurs du sous-arbre gauche, puis affiche la racine, et affiche enfin les valeurs du sous-arbre droit.
Dans ce qui suit, nous allons maintenant programmer des opérations qui sont spécifiques aux ABR.
Comme on l'a compris avec l'exemple introductif, la propriété d'ABR
tire tout son intérêt de l'efficacité de la recherche qu'elle permet.
En effet, pour chercher une valeur dans un ABR, il suffit de la comparer à la valeur à la racine puis, si elle est différente, de se diriger vers un seul des deux sous-arbres.
On élimine ainsi complètement la recherche dans l'autre sous-arbre.
Écrivons une fonction
def appartient(x, a):
qui détermine si la valeur x apparaît dans l'ABR a.
On commence par le cas d'un arbre vide, pour lequel la réponse est évidente.
if a is None:
return False
Dans le cas contraire, cela veut dire que l'arbre contient au moins un nœud.
On peut donc comparer la valeur x avec la valeur située à la racine de l'arbre, c'est-à-dire a.valeur.
Si la valeur x est plus petite, il faut continuer la recherche dans le sous-arbre gauche, ce que l'on fait récursivement.
if x < a.valeur:
return appartient(x, a.gauche)
(Ne pas oublier le return, pour renvoyer le résultat de l'appel récursif.)
Si la valeur x est en revanche plus grande que a.valeur, alors on procède de même à une recherche dans le sous-arbre droit.
elif x > a.valeur:
return appartient(x, a.droit)
Enfin, si elle n'est ni plus petite ni plus grande, c'est que les deux valeurs
sont égales.
Autrement dit, la valeur x apparaît à la racine de l'arbre, ce que l'on signale en renvoyant True.
else:
return True
Le code complet est le suivant :
Programme — Recherche dans un ABR
def appartient(x, a):
\"\"\"détermine si x apparaît dans l'ABR a\"\"\"
if a is None:
return False
if x < a.valeur:
return appartient(x, a.gauche)
elif x > a.valeur:
return appartient(x, a.droit)
else:
return True
Tester le programme appartient avec les instructions suivantes et conclure:
a5 = Noeud(Noeud(Noeud(None,2,None),4,Noeud(None,5,None)), \\
8, \\
Noeud(Noeud(None,10,None),12,Noeud(None,14,None) ))
print(appartient(2,a5))
print(appartient(15,a5))
Efficacité
Quelle est l'efficacité de la fonction appartient, en terme du nombre d'opérations effectuées pour rechercher une valeur x dans un arbre à qui contient N éléments?
Si les éléments sont répartis à peu près équitablement entre les deux sous-arbres, la fonction appartient élimine la moitié des éléments à chaque étape.
Cela fait écho à la recherche dichotomique dans un tableau trié, où chaque étape divise par deux le nombre d'éléments à examiner.
Comme on l'a vu, c'est extrêmement efficace. Ainsi, il ne faut pas plus de 20 étapes pour chercher parmi un million de valeurs.
D'autre part, il n'y aucun risque de provoquer l'erreur RecursionError dans
ce cas.
Cela étant, rien ne garantit que les éléments sont équitablement répartis, à chaque étape, entre les deux sous-arbres.
En particulier, l'arbre a peut tout à fait être un peigne, comme les deux arbres suivants :
__O_ __O__
/ \\ / \\
__O__ __O__
/ \\ / \\
__O__ __O__ / \\ / \\
ou plus généralement un arbre complètement filiforme dont la hauteur est égale au nombre de nœuds.
Dans ce cas, la recherche est au contraire peu efficace, car elle est susceptible de parcourir l'arbre tout entier, par exemple dans le cas
d'une recherche infructueuse.
À cet égard, un ABR linéaire n'est pas meilleur qu'une liste chaînée.
D'une manière générale, le coût de la recherche dans un ABR est majoré par sa hauteur. En effet, chaque étape de la recherche descend dans l'un des deux sous-arbres. Du coup, on ne peut répéter cela un nombre de fois plus grand que la hauteur de l'arbre, par définition.
La hauteur d'un ABR dépend directement de la façon dont il a été construit, ce qui est discuté dans les deux sections suivantes.
Mettre le résultat ici (code et figure).
Nous allons écrire une fonction ajoute(x, a) qui ajoute un nouvel élément x dans l'ABR a.
Ainsi, nous pourrons construire des ABR par ajouts successifs d'éléments avec la fonction ajoute, en partant d'un arbre vide.
Dans le principe, ajouter un nouvel élément dans un ABR n'est pas plus compliqué que de le chercher :
- s'il est plus petit, on va à gauche; - s'il est plus grand, on va à droite.
Et quand on arrive à un arbre vide, on ajoute un nouveau nœud.
Si par exemple il s'agit d'ajouter l'élément 2 dans l'arbre
___3___
/ \\
_1_ _4_
/ \\ / \\
alors on commence par aller à gauche, car 2 est plus petit que 3, puis on va à droite, car 2 est plus grand que 1, puis enfin on ajoute un nouveau nœud contenant 2 car on est arrivé sur un arbre vide.
On obtient donc cet arbre :
___3___
/ \\
_1_ _4_
/ \\ / \\
_2_
/ \\
En pratique, cependant, il n'est pas si facile de mettre en œuvre cette idée.
Naïvement, on pourrait penser que la fonction ajoute ne renvoie rien et se contente de modifier l'arbre reçu en argument, pour lui greffer un nouveau nœud.
Mais si l'arbre est vide, c'est-à-dire vaut None, une telle modification n'est pas possible. [l faudrait faire alors un cas particulier pour l'insertion dans un arbre vide, en dehors de notre fonction ajoute, ce qui est extrêmement déplaisant.
Par ailleurs, il faudrait faire également des cas particuliers dans la fonction ajoute elle-même, lorsqu'elle s'apprête à se rappele récursivement sur un sous-arbre vide.
Pour cette raison, nous allons adopter la même approche qu'avec les listes chaînées, à savoir ne pas modifier les arbres reçus en arguments mais en renvoyer de nouveaux.
Dit autrement, nous choisissons d'utiliser nos objets de classe Noeud de façon immuable, comme nous l'avions fait avec les objets de la classe Cellule.
Écrivons donc une fonction ajoute qui renvoie un nouvel arbre contenant x et tous les éléments de a.
def ajoute(x, a):
Comme pour la recherche, on procède récursivement.
Le cas de base est celui de l'ajout dans un arbre vide. Dans ce cas, il convient de renvoyer un arbre contenant un unique nœud, dont la valeur est x.
iF a is None:
return Noeud(None, x, None)
Si en revanche l'arbre a n'est pas vide, on compare x et a.valeur. Si x est plus petit, on doit l'ajouter dans le sous-arbre gauche.
L'appel récursif ajoute(x, a.gauche) nous renvoie, par définition, un arbre qui contient x et tous les éléments de a.gauche.
C'est le sous-arbre gauche de notre résultat, par dessus lequel nous réinstallons une racine de même valeur a.valeur et un sous-arbre droit a.droit inchangé.
if x < a.valeur:
return Noeud(ajoute(x, a.gauche), a.valeur, a.droit)
Si en revanche x est supérieur ou égal à a.valeur, on doit l'ajouter au sous-
arbre droit.
On procède de façon similaire, avec cette fois un appel récursif ajoute(x,a.droit).
else:
return Noeud(a.gauche, a.valeur, ajoute(x, a.droit))
On note qu'on ne fait pas ici de traitement particulier dans le cas où x est égal à a.valeur.
Ceci est discuté un tout petit peu plus loin.
Ceci achève donc notre fonction ajoute. Le code complet est le suivant :
Programme — Ajout dans un ABR
def ajoute(x, a):
\"\"\"ajoute x à l'arbre a, renvoie un nouvel arbre\"\"\"
if a is None:
return Noeud(None, x, None)
if x < a.valeur:
return Noeud(ajoute(x, a.gauche), a.valeur, a.droit)
else:
return Noeud(a.gauche, a.valeur, ajoute(x, a.droit))
Tester le programme avec les instructions suivantes et conclure :
a1 = ajoute(8,None)
a1 = ajoute(4,a1)
a1 = ajoute(2,a1)
a1 = ajoute(5,a1)
a1 = ajoute(12,a1)
a1 = ajoute(10,a1)
a1 = ajoute(14,a1)
affiche1(a1)
print()
Efficacité
La complexité de notre fonction ajoute n'est pas différente de celle de la fonction appartient. En effet, on prend exactement les mêmes décisions quant à la descente dans l'arbre et, comme pour la fonction appartient, on fait un nombre borné d'opérations à chaque étape.
La conclusion est donc la même :
la complexité dépend de la forme de l'arbre et elle est, dans le pire des cas, majorée par sa hauteur.
En ce qui concerne l'utilisation de la
mémoire, la fonction ajoute construit autant de nœuds qu'elle fait d'appels
récursifs. Sa complexité en espace est donc comparable à sa complexité en temps.
Exactement comme pour la concaténation des listes chaînées, certaines parties de l'arbre a sont réutilisées dans le résultat renvoyé par ajoute(x, a) et d'autres parties sont en revanche «dupliquées».
Plus précisément, tous les nœuds le long de la descente sont dupliqués et
tous les sous-arbres dans lesquels on ne descend pas sont partagés. Re-
prenons l'exemple ci-dessus où on ajoute successivement les éléments 3, 1
et 4, dans cet ordre, dans un arbre initialement vide. Quand on exécute
a = ajoute(3, None), on obtient un arbre réduit à un seul nœud, qui vient
d'être créé :
_3_
/. \\
Quand ensuite on exécute a = ajoute(1,a), ce nœud contenant 3 est dupliqué, par le return Noeud(...) qui encadre l'appel récursif pour insérer 1 dans le sous-arbre gauche. Puis un nouveau nœud contenant 1 est créé et on obtient au final un arbre qui ne partage rien avec le précédent :
_3_
/ \\
_1_
/ \\
En revanche, les choses deviennent plus subtiles quand on poursuit avec a = ajoute(4,a) car cette fois le sous-arbre gauche est partagé entre l'argument et le résultat. La racine contenant 3 est de nouveau dupliquée et bien sûr un nouveau nœud contenant 4 est construit. On peut l'illustrer ainsi, avec à gauche l'arbre passé en argument et à droite l'arbre renvoyé en résultat :
*****
Comme pour les listes, il n'y a pas de danger à réaliser un tel partage, tant
qu'on ne modifie pas (par des affectations) les sous-arbres ainsi partagés. Vu que notre fonction ajoute ne fait aucune affectation, il n'y a aucun risque tant qu'on se limite à cette fonction.
En première approximation, on n'a pas vraiment besoin de se soucier de ce partage. On peut tout à fait l'ignorer. En particulier, on peut continuer à dessiner le résultat précédent comme nous le faisions auparavant,
__3__
/ \\
_1_ _4_
/ \\ / \\
c'est-à-dire sans expliciter que le sous-arbre gauche est commun avec un autre arbre.
Seules des considérations d'occupation mémoire pourraient éventuellement faire une différence, si tous ces arbres cohabitaient en mémoire. Mais le plus souvent, ce n'est pas le cas. Ainsi, lorsqu'on exécute une séquence d'instructions telle que
a = ajoute(3, None)
a = ajoute(1, a)
a = ajoute(4, a)
seul le dernier arbre construit est stocké dans la variable a. Tous les sous-
arbres qui ne participent pas au résultat final sont récupérés par le GC de Python. Une fois que c'est fait, il n'y a plus de partage.
","title":"Ajout dans un ABR","tagtitle":"h1"},{"edit":"Mettre le résultat ici (code et figure).
Doublons
Telle que nous l'avons écrite, notre fonction ajoute a la propriété de toujours ajouter un nouveau nœud à l'arbre.
En particulier, si l'élément x apparaît déjà dans l'arbre, un nouveau nœud contenant une nouvelle occurrence de x va être ajouté.
Plus précisément, lorsque x est égal à la racine a.valeur, on poursuit notre insertion dans le sous-arbre droit. Ainsi, si on insère 3 dans l'arbre donné en exemple plus haut qui contient déjà 1,2,3,4, alors on va obtenir l'arbre suivant :
____3____
/ \\
_1_ _4_
/ \\ / \\
_2_ _3_
/ \\ / \\
En effet, on commence par comparer l'élément à ajouter, 3, avec la racine, qui vaut 3 également. Dès lors, on se déplace vers le sous-arbre droit.
On pourrait tout à fait préférer insérer à gauche plutôt qu'à droite en cas d'égalité. Pour cela, il suffirait de remplacer la comparaison stricte < par une comparaison large <= dans le code de la fonction ajoute.
Nos ABR réalisent donc des multi-ensembles, c'est-à-dire des ensembles où un même élément peut paraître plusieurs fois. Si on veut en revanche réaliser des ensembles, où chaque élément apparaît exactement une fois, il ne faut pas ajouter de nouvelle occurrence de l'élément x lorsqu'il se trouve déjà
dans l'arbre.
Pour cela, il y a deux solutions. La première consiste à d'abord tester si x apparaît dans a, avec notre fonction appartient, et n'appeler la fonction ajouter qu'en cas de réponse négative.
La deuxième consiste à écrire une variante de la fonction ajoute qui n'ajoute pas de nouvelle occurrence de l'élément x s'il est déjà dans l'arbre a, mais renvoie un arbre identique à a.
","title":""},{"edit":"Alternatives
Comme nous l'avons évoqué plus haut, il n'est pas impossible de réaliser une modification en place d'un arbre pour lui ajouter un nouvel élément.
Voici à quoi pourrait ressembler une fonction ajoute qui modifie l'arbre a reçu en argument et ne renvoie rien.
def ajoute(x,a):
if x < a.valeur:
if a.gauche is None:
a.gauche = Noeud(None, x, None)
else:
ajoute(x,a.gauche)
elif x > a.valeur:
if a.droit is None:
a.droit = Noeud(None, x, None)
else:
ajoute(x,a.droit)
On a illustré ici le cas d'une insertion dans le sous-arbre gauche.
On teste si ce sous-arbre est vide. Le cas échéant, on greffe le nouveau nœud.
Sinon, on procède récursivement.
On fait de même pour une insertion dans le sous-arbre droit.
Comme on le voit, le code est devenu plus
complexe. Mais surtout, il ne traite pas le cas de l'insertion dans un arbre vide, c'est-à-dire lorsque a vaut None.
On serait obligé de le traiter dans le code englobant, c'est-à-dire dans le code qui appelle ajoute initialement.
Tester la fonction ajoute avec les instructions suivantes :
a6 = Noeud(None,8,None)
ajoute(4,a6)
ajoute(12,a6)
ajoute(2,a6)
ajoute(6,a6)
ajoute(10,a6)
ajoute(14,a6)
ajoute(1,a6)
ajoute(3,a6)
ajoute(5,a6)
ajoute(7,a6)
ajoute(9,a6)
ajoute(11,a6)
ajoute(13,a6)
ajoute(15,a6)
affiche1(a6)
Comparer avec le la fonction précédente ajoute et conclure.
Il y a d'autres manières de procéder pour réaliser une insertion en place, mais elles sont toutes complexes, d'une façon ou d'une autre.
Au final, le premier programme ajout est plus simple simple qui soit. Par ailleurs, son efficacité est comparable à celle de toute autre solution, y compris les solutions qui modifient l'arbre.
En effet, le nombre d'opérations est dans tous les cas défini par la descente dans l'arbre jusqu'au point d'insertion, quelle que soit la méthode choisie.
Enfin, dans la dernière section, nous allons encapsuler un ABR dans un objet
pour lui donner notamment une interface impérative, où la méthode d'ajout ne renvoie rien. Ainsi, nous aurons réconcilié la simplicité des arbres immuables avec une utilisation impérative idiomatique en Python.
Mettre le résultat ici (code et figure).
Pour supprmer un élément dans un ABR, on applique toujours le même principe, en procédant récursivement soit à gauche, soit à droite, selon le résultat de la comparaison.
Le cas de base, cependant, est plus délicat, car il s'agit de supprimer le nœud à la racine de l'arbre.
Pour conserver une structure d'arbre, il faut donner une racine à l'arbre renvoyé.
Pour cela, on peut prendre par exemple le plus petit élément du sous-arbre droit, pour en faire la racine, et le supprimer du sous-arbre droit. On est donc ramené à la suppression du plus petit élément d'un arbre, qui s'avère plus facile que la
suppression d'un élément quelconque.
En premier lieu, on suppose avoir écrit une fonction plus_petit(a) qui renvoie le plus petit élément de l'arbre a, c'est-à-dire l'élément se trouvant tout en bas à gauche de a en supposant l'arbre a non vide.
On écrit ensuite une fonction supprime_minimum(a) qui renvoie un arbre
contenant les mêmes éléments que a, à l'exclusion du plus petit élément de a.
Cela revient donc à supprimer l'élément situé tout en bas à gauche de a.
On suppose que l'arbre a est non vide. Cette fonction procède récursivement, avec un cas de
base et un cas récursif.
Le cas de base est celui d'un arbre dont le sous-arbre gauche est vide. Dans ce cas, le minimum est la racine et il suffit de renvoyer le sons-arbre droit. Sinon, on procède récursivement, en supprimant le minimum dans le sous-arbre gauche.
On peut enfin écrire une fonction supprime(x, a) qui supprime une occurrence de x dans a.
On rappelle en effet qu'on à potentiellement des doublons dans nos arbres et donc potentiellement plusieurs occurrences de x dans a.
Ici, on choisit de n'en supprimer qu'une.
Par ailleurs, on n'impose pas que l'élément x apparaisse dans a. S'il n'apparaît pas, la fonction supprime renvoie un arbre identique à a.
Le code de la fonction supprime est le suivant :
def plus_petit(a):
if a is None:
return None
if a.gauche is None:
return a.valeur
else:
return plus_petit(a.gauche)
def supprime_minimum(a) :
\"\"\"itisupprime Le plus petit élément de a
suppose a non vide\"\"\"
assert a is not None
if a.gauche is None:
# la racine est Le minimum
return a.droit
return Noeud(supprime_minimum(a.gauche) ,a.valeur,a.droit)
def supprime(x, a):
\"\"\"supprime une occurrence de x dans a\"\"\"
if a is None:
return None
if x < a.valeur:
return Noeud(supprime(x,a.gauche) ,a.valeur,a.droit)
elif x > a.valeur:
return Noeud(a.gauche,a.valeur,supprime(x,a.droit))
#il faut supprimer la racine
elif a.droit is None:
return a.gauche
else:
return Noeud(a.gauche, plus_petit(a.droit), \\
supprime_minimum(a.droit))
Tester le avec les instructions suivantes:
a6 = Noeud(None,8,None)
ajoute(4,a6)
ajoute(12,a6)
ajoute(2,a6)
ajoute(6,a6)
ajoute(10,a6)
ajoute(14,a6)
ajoute(1,a6)
ajoute(3,a6)
ajoute(5,a6)
ajoute(7,a6)
ajoute(9,a6)
ajoute(11,a6)
ajoute(13,a6)
ajoute(15,a6)
affiche1(a6)
print()
a7 = supprime(4,a6)
affiche1(a7)
Et conclure sur la fonction supprime.
Le cas d'un arbre vide est traité en premier lieu. Il suffit de renvoyer un arbre vide.
On traite ensuite le cas d'une valeur x située dans le sous-arbre gauche ou dans le sous-arbre droit, avec un appel récursif. Il reste enfin le cas où la valeur x est égale à a.valeur, c'est-à-dire le cas où l'on souhaite supprimer la racine de l'arbre. C'est 1à qu'on emploie les deux fonctions minimum et supprime_minimum, pour faire du plus petit élément de a.droit la nouvelle racine de l'arbre.
Bien entendu, on aurait pu utiliser tout autant le maximum du sous-arbre gauche, d'une façon totalement symétrique.
","title":"Suppression dans un ABR"},{"edit":"Mettre le résultat ici (code et figure).
Comme nous l'avons fait pour les listes chaînées, nous pouvons maintenant encapsuler nos arbres binaires de recherche dans une classe, ici appelée ABR.
Le code de cette classe est le suivant:
Programme — Encapsulation d'un ABR dans un objet
class Noeud:
\"\"\"un noeud d'un arbre binaire\"\"\"
def __init__(self, g, v, d):
self.gauche = g
self.valeur = v
self.droit = d
def __eq__(self, n):
return n is not None \\
and self.gauche == n.gauche \\
and self.valeur == n.valeur \\
and self.droit == n.droit
class ABR:
\"\"\"arbre binaire de recherche\"\"\"
def __init__(self):
self.racine = None
def ajouter(self, x):
if self.racine is None :
self.racine = Noeud(None,x,None)
else :
self.__ajoute__(x,self.racine)
def contient(self, x):
return self.__appartient__(x, self.racine)
def affiche(self):
self.__afficher__(self.racine)
print(\"\\n\")
def __afficher__(self,a):
if a is None:
return
print (\"(\", end=\"\")
self.__afficher__(a.gauche)
print(a.valeur, end=\"\")
self.__afficher__(a.droit)
print(\")\", end=\"\")
def __ajoute__(self,x,a):
if x < a.valeur:
if a.gauche is None:
a.gauche = Noeud(None, x, None)
else:
self.__ajoute__(x,a.gauche)
elif x > a.valeur:
if a.droit is None:
a.droit = Noeud(None, x, None)
else:
self.__ajoute__(x,a.droit)
def __appartient__(self,x, a):
\"\"\"détermine si x apparaît dans l'ABR\"\"\"
if a is None:
return False
if x < a.valeur:
return self.__appartient__(x, a.gauche)
elif x > a.valeur:
return self.__appartient__(x, a.droit)
else:
return True
Tester avec :
a8 = ABR()
a8.ajouter(8)
a8.ajouter(4)
a8.ajouter(12)
a8.ajouter(2)
a8.ajouter(6)
a8.ajouter(10)
a8.ajouter(14)
a8.ajouter(1)
a8.ajouter(3)
a8.ajouter(5)
a8.ajouter(7)
a8.ajouter(9)
a8.ajouter(11)
a8.ajouter(13)
a8.ajouter(15)
a8.affiche()
print(\"a8 contient 15? \",a8.contient(15))
print(\"a8 contient 17? \",a8.contient(17))
Et conclure.
Chaque objet de la classe ABR contient un unique attribut, racine, qui est l'arbre binaire de recherche qu'il représente. Le constructeur de la classe ABR renvoie un arbre vide, avec donc la valeur None dans l'attribut racine.
Ainsi, si on construit un arbre vide, que l'on stocke dans une variable a, on a la
situation suivante:
a = ABR()
La classe ABR fournit deux méthodes, ajouter et contient, correspondant aux deux fonctions ajoute et appartient des deux sections précédentes.
Ainsi, on peut construire un arbre contenant les éléments 1, 2, 3, 4 en les
ajoutant avec la méthode ajouter. I! faut comprendre que chaque appel à la méthode ajouter remplace l'attribut racine par un nouvel arbre, à savoir celui qui est renvoyé par la fonction ajoute.
L'arbre qui était précédemment dans l'attribut racine est perdu et sera récupéré par le GC de Python, à sa discrétion.
En pratique, il faudrait ajouter d'autres méthodes à la classe ABR, correspondant à d'autres fonctions comme taille, hauteur, parcours_infixe, suprimer, etc.
a = ABR()
a.ajouter(3)
a.ajouter(1)
a.ajouter(4)
a.ajouter(2)
Figure : Construction d'un ABR contenant quatre éléments.
Mettre le résultat ici (code et figure).
Comme on l'a expliqué plus précédemment, le coût de la recherche ou de l'ajout dans un ABR dépend de sa structure. Il est borné par la hauteur de l'ABR.
Dans le pire des cas, l'arbre peut être complètement linéaire et le coût peut
donc être proportionnel au nombre d'éléments, ce qui en fait une structure
de peu d'intérêt. Autant mettre tous les éléments dans un tableau ou une liste chaînée si c'est pour faire une recherche linéaire.
Néanmoins, il est possible de s'assurer, pendant leur construction, que la hauteur des ABR « ne sera pas trop grande ».
Pour cela, on réorganise la structure de l'ABR lorsque c'est nécessaire, tout en maintenant la propriété d'arbre binaire de recherche.
Il existe de multiples façons de procéder. Parmi les plus connues, on peut citer les arbres AVL ou encore les arbres rouges et noirs.
Le détail de ces méthodes dépasse largement le cadre du programme de terminale.
On peut se contenter de dire que l'idée est, pour chaque sous-arbre, de mettre approximativement la moitié des nœuds dans le sous-arbre gauche et l'autre moitié dans le sous-arbre droit.
Ainsi, on divise par deux le nombre de nœuds à considérer à chaque descente dans l'arbre, comme dans le cas de la recherche dichotomique dans un tableau trié. Dit autrement, ces méthodes d'équilibrage des arbres permettent de garantir une hauteur logarithmique, c'est-à-dire l'existence d'une constante C telle que
h ≤ C.log2(N)
où h désigne la hauteur et N la taille d'un ABR.
Par exemple, pour les arbres AVL, on a C=1,44. On parle d'arbres équilibrés lorsqu'on à une telle inégalité. Les opérations de recherche ou d'ajout sur les arbres équilibrés ont une complexité logarithmique, ce qui en fait des opérations très efficaces en pratique.
Par ailleurs, il n'y a plus aucun risque de provoquer l'erreur RecursionError lorsque les arbres sont équilibrés.
","title":"Arbre équilibré "},{"edit":"Un arbre binaire de recherche est un arbre binaire contenant des valeurs ordonnées, avec la propriété que tout nœud contient une valeur plus grande (resp. plus petite ou égale) que les valeurs contenues dans son sous-arbre gauche (resp. droit). Cette organisation permet de procéder par dichotomie, en n'ayant à considérer qu'un seul des
deux sous-arbres pendant une opération. Lorsqu'ils sont équilibrés, les arbres binaires de recherche constituent une méthode très efficace pour stocker et rechercher de l'information.
Pourquoi la bibliothèque donnée en exemple au début de ce
chapitre contient-elle 17576 salles ?
","title":"Exercice","tagtitle":"h1"},{"edit":"Mettre le résultat ici (code et figure).
Donner tous les ABR formés de trois nœuds et contenant les entiers 1, 2 et 3.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
_3_ / \\ _2_ / \\ _1_ / \\ | _3_ / \\ _1_ / \\ _2_ / \\ | __2__ / \\ _1_ _3_ / \\ / \\ |
_1_ / \\ _2_ / \\ _3_ / \\ | _1_ / \\ _3_ / \\ _2_ / \\ |
Dans un ABR, où se trouve le plus petit élément ? En déduire
unc fonction minimum(a) qui renvoie le plus petit élément de l'ABR a. Si
l'arbre à est vide, alors cette fonction renvoie None.
Tester avec :
a5 = Noeud(Noeud(Noeud(None,2,None),4,Noeud(None,5,None)), \\
8, \\
Noeud(Noeud(None,10,None),12,Noeud(None,14,None) ))
print(minimum(a5))
Résultat :
2
","title":"Exercice","tagtitle":"h1"},{"edit":"Mettre le résultat ici (code et figure).
Par définition d’un ARB, le plus petit élément se trouve en bas à gauche de l’arbre.
def minimum(a):
if a is None:
return None
if a.gauche is None:
return a.valeur
else:
return minimum(a.gauche)
def ajoute(x, a):
#ajoute x à l'arbre a, renvoie un nouvel arbre
if a is None:
return Noeud(None, x, None)
if x < a.valeur:
return Noeud(ajoute(x, a.gauche), a.valeur, a.droit)
else:
return Noeud(a.gauche, a.valeur, ajoute(x, a.droit))
Modifier la fonction ajoute qui n'ajoute pas l'élément x à l'arbre a s'il est déjà dedans.
Tester avec :
a5 = Noeud(Noeud(Noeud(None,2,None),4,Noeud(None,5,None)), \\
8, \\
Noeud(Noeud(None,10,None),12,Noeud(None,14,None) ))
a5 = ajoute(1,a5)
a5 = ajoute(15,a5)
a5 = ajoute(14,a5)
affiche1(a5)
Résultat :
(((1)2)4(5))8((10)12(14(15))))
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
def ajoute(x, a):
#ajoute x à l'arbre a, renvoie un nouvel arbre
if a is None:
return Noeud(None, x, None)
if x < a.valeur:
return Noeud(ajoute(x, a.gauche), a.valeur, a.droit)
elif x > a.valeur:
return Noeud(a.gauche, a.valeur, ajoute(x, a.droit))
else :
return a # x est dans a
Écrire une fonction compte(x, a) qui renvoie le nombre d'occurrences de x dans l'ABR. a. On ne suppose pas que l'arbre a à été construit à partir de la fonction ajoute, mais seulement qu'il s'agit d'un ABR.
Cela veut dire qu'une valeur égale à la racine peut se trouver encore dans le sous-arbre gauche autant que dans le sous-arbre droit.
Cela étant, on s'attachera à ne pas descendre dans les sous-arbres dans lesquels on est certain que la
valeur x ne peut apparaître.
Tester avec :
a5 = Noeud(Noeud(Noeud(None,2,None),4,Noeud(None,5,None)), \\
8, \\
Noeud(Noeud(None,10,None),12,Noeud(None,14,None) ))
print(compte(4,a5))
print(compte(14,a5))
print(compte(1,a5))
Résultat :
1
1
0
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
Lorsque x est strictement plus petit ou strictement plus grand que a.valeur, il suffit d’aller d’un seul côté. En cas d'égalité, en
revanche, il faut continuer à compter des deux côtés.
def compte(x, a):
if a is None:
return 0
if x < a.valeur:
return compte(x, a.gauche)
elif x > a.valeur:
return compte(x, a.droit)
else:
return 1 + compte(x, a.gauche) + compte(x, a.droit)
Écrire une fonction remplir(a, t) qui ajoute tous les éléments de l'arbre a dans le tableau t, dans l'ordre infixe. Chaque élément x est ajouté au tableau t avec t.append(x).
Ajouter ensuite une méthode lister(self)
à la classe ABR qui renvoie un nouveau tableau contenant tous les éléments de l'ABR self par ordre croissant.
Tester avec :
a5 = Noeud(Noeud(Noeud(None,2,None),4,Noeud(None,5,None)), \\
8, \\
Noeud(Noeud(None,10,None),12,Noeud(None,14,None) ))
t1 = []
remplir(a5,t1)
print(t1)
Pour la classe ABR :
a6 = ABR()
a6.ajouter(8)
a6.ajouter(4)
a6.ajouter(2)
a6.ajouter(5)
a6.ajouter(12)
a6.ajouter(14)
a6.ajouter(10)
t2 = a6.lister()
print(t2)
Résultat :
[2, 4, 5, 8, 10, 12, 14]
Mettre le résultat ici (code et figure).
C'est un cas particulier de parcours infixe (pro-
gramme 30 page 154) :
def remplir(a, t):
if a is None:
return
remplir(a.gauche, t)
t.append(a.valeur)
remplir(a.droit, t)
Pour la méthode lister dans la classe ABR, on crée un nouveau tableau, que l’on remplit avec la fonction remplir.
def lister(self):
t = []
remplir(self.racine, t)
return t
En utilisant l'exercice précédent, écrire une fonction trier(t) qui reçoit en argument un tableau d'entiers et renvoie un tableau trié contenant les mêmes éléments.
Quelle est l'efficacité de ce tri?
Tester avec :
t2 = [5,2,4,0,9,10,3,12,7]
t3 = trier(t2)
print(t3)
Résultat :
[0, 2, 3, 4, 5, 7, 9, 10, 12]
","title":"Exercice","tagtitle":"h1"},{"edit":"Mettre le résultat ici (code et figure).
L'idée est d'ajouter tous les éléments du tableau t dans un ABR, puis d'utiliser la méthode lister de l'exercice précédent.
def trier(t):
a = ABR()
for x in t :
a.ajouter(x)
return a.lister()
L'efficacité de ce tri dépend fortement de la répartition des éléments dans le tableau initial. Si par exemple les éléments sont déjà triés dans le tableau
initial, alors l’arbre sera un peigne et le coût de la construction de l'ABR sera donc quadratique.
"}],[{"text":"Ajouter la méthode hauteur(self) à la classe a qui renvoie la hauteur de l'arbre.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
Mettre le résultat ici (code et figure).
- Détails
- Écrit par : Richard GAUTHIER
- Clics : 1564
[[{"text":"
"}],[{"text":"
","title":"Structures arborescentes"},{"edit":"
"}],[{"text":"
![\"preview\"](\"https://sciencesappliquees.com/images/nsi/arbre2.png\")
![\"preview\"](\"https://sciencesappliquees.com/images/nsi/arbre4.png\")
","title":"Définition et propriétés des arbres binaires"},{"edit":"
"}],[{"text":"
![\"preview\"](\"https://sciencesappliquees.com/images/arbre5.png\")
![\"preview\"](\"https://sciencesappliquees.com/images/arbre6.png\")
","title":"Hauteur","tagtitle":"h1"},{"edit":"
"}],[{"text":"
![\"preview\"](\"https://sciencesappliquees.com/images/arbre7.png\")
","title":"De l'information dans les arbres","tagtitle":"h1"},{"edit":""}],[{"text":"
","title":"De nombreuses variantes","tagtitle":"h1"},{"edit":"
"}],[{"text":"
![\"preview\"](\"https://sciencesappliquees.com/images/nsi/arbre8.png\")
","title":"Représentation en Python","tagtitle":"h1"},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":"Algorithmique des arbres binaires"},{"edit":"
"}],[{"text":"
","title":"Parcours d'un arbre binaire"},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":"Conclusion"},{"edit":"
"}],[{"text":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"},{"solution":"
"}],[{"text":"
"},{"solution":"
"},{"solution":"
"}],[{"text":"
"},{"solution":"
"}],[{"text":"
"},{"solution":"
"}]]
La notion de liste chaînée explorée dans les deux chapitres précédents est parfaite pour structurer un ensemble d'éléments destiné à être énuméré séquentiellement.
Comme on l'a vu avec la réalisation de piles et de files, cette structure permet également un accès simple au début de la séquence et éventuellement à certaines autres positions choisies.
Elle n'est en revanche pas adaptée aux accès ponctuels à des positions arbitraires dans la séquence, puisqu'il faut pour cela à chaque nouvel accès parcourir tous les maillons depuis la tête de la liste jusqu'à la position cherchée, ce qui prend en moyenne
un temps proportionnel au nombre d'éléments stockés dans la structure.
","title":"S.D. - Arbres binaires","tagtitle":"h1"},{"edit":"Les structures arborescentes forment une autre famille de structures chaînées, dans lesquelles le nombre de sauts à effectuer pour aller depuis le point de départ jusqu'à une position souhaitée est potentiellement bien moindre.
Ces structures sont omniprésentes en informatique et nous en avons déjà observé une :
l'arborescence des fichiers d'un ordinateur.
administrator@vps:/$ tree /home/
/home/
├── administrator
│ ├── 11.0
│ ├── odoo_install.sh
│ ├── www
│ └── documents
├── user1
│ └── documents
├── invite
└── ubuntu
Cette organisation des fichiers permet notamment, partant du répertoire racine et voyageant de répertoire en sous-répertoire, d'accéder en un petit nombre d'étapes à n'importe quel fichier choisi parmi des dizaines de milliers, pour peu qu'on aille dans la bonne direction.
Ce principe d'un point de départ unique à partir duquel une structure chaînée se scinde à chaque étape en plusieurs branches donne l'idée générale de la structure d'arbre en informatique, qui est à la base d'innombrables structures de données.
Cette structure permet en outre une organisation hiérarchique de l'information, qui la rend utile pour représenter des programmes, des formules de logique, le contenu de pages web, etc.
Mettre le résultat ici (code et figure).
Un arbre binaire est un cas particulier de structure arborescente où chaque position ouvre sur exactement deux branches.
Plus précisément, un arbre binaire est un ensemble fini de nœuds correspondant à l'un des deux cas suivants.
- Soit l'arbre est vide, c'est-à-dire qu'il ne contient aucun nœud.
- Soit l'arbre n'est pas vide, et ses nœuds sont structurés de la façon suivante :
- un nœud est appelé la racine de l'arbre:
- les nœuds restant sont séparés en deux sous-ensembles, qui forment récursivement deux sous-arbres appelés respectivement sous-arbre gauche et sous-arbre droit ;
- la racine est reliée à ses deux sous-arbres gauche et droit, et plus précisément à la racine de chacun de ses sous-arbres (lorsqu'ils ne sont pas vides).
On peut rapprocher la notion de nœud d'un arbre binaire de la notion de cellule d'une liste chaînée.
L'arbre vide est alors similaire à la liste vide qui est noté par le symbole L.
La racine d'un arbre non vide est l'équivalent de la tête d'une liste non vide et les liens vers les deux sous-arbres correspondent à deux chaînages « suivants » menant à deux suites disjointes.
De même que la taille d'une liste était définie comme son nombre de cellules, la faille d'un arbre binaire est ainsi définie comme son nombre de nœuds.
Voici un exemple d'arbre binaire contenant quatre nœuds.
La racine de arbre cst représentée en haut — en informatique, les arbres poussent vers le bas.
Ici, le sous-arbre gauche contient deux nœuds et le sous-arbre droit un nœud.
Comme on le voit, chaque nœud est relié à ses deux sous-arbres, et plus précisément à la racine de chaque sous-arbre, le cas échéant.
On a également représenté les liaisons entre les nœuds et leurs sous-arbres vides, le cas échéant. Ainsi, on explicite le fait qu'un nœud possède toujours deux
sous-arbres, même si l'un ou l'autre ou les deux peuvent être vides.
Lorsqu'un nœud à deux sous-arbres vides, c'est-à-dire qu'il est de la forme
on parle de feuille, Il est important de ne pas confondre une feuille, qui contient un nœud, et un arbre vide, qui n'en contient pas.
On définit la hauteur d'un arbre comme le plus grand nombre de nœuds rencontrés en descendant de la racine jusqu'à une feuille (ou, de façon équivalente, jusqu'à un arbre vide).
Tous les nœuds le long de cette descente sont comptés, y compris la racine et la feuille.
Ainsi, l'arbre
a une hauteur 3.
De façon équivalente, on peut définir la hauteur récursivement sur la structure de l'arbre de la manière suivante :
- l'arbre vide a pour hauteur 0:
- un arbre non vide a pour hauteur le maximum des hauteurs de ses deux sous-arbres, auquel on ajoute 1.
Si N désigne la taille d'un arbre binaire, c'est-à-dire son nombre de nœuds, et si k désigne sa hauteur, alors ces deux quantités sont contraintes par les inégalités suivantes:
h ≤ N ≤ 2h - 1
L'inégalité de gauche s'interprète facilement comme le fait qu'un arbre de hauteur } possède au moins À nœuds, par définition de la hauteur. L'égalité
est possible lorsque l'arbre est complètement linéaire, avec un seul nœud à chaque profondeur.
Voici trois exemples d'arbres de taille de hauteur 4 :
Les arbres comme celui de gauche on celui de droite, où le sous-arbre non
vide est systématiquement du même côté, sont appelés des peignes, car leur
forme évoque celle d'un peigne. On note qu'un peigne n'est pas différent, par sa structure, d'une liste chaînée.
De l'autre côté, la limite 2% — 1 sur la taille de l'arbre est atteinte pour
un arbre binaire parfait où toutes les feuilles sont exactement à la même
est un arbre binaire parfait de hauteur 3 et sa taille est 2? —1=7.
La hauteur est une notion importante. Elle joue notamment un grand
rôle lorsque la complexité des algorithmes dépend directement de la hauteur
des arbres. Le chapitre suivant en donne plusieurs exemples.
Mettre le résultat ici (code et figure).
Comme nous le verrons dans la séquence suivant, l'intérêt des arbres est d'y
stocker de l'information.
Pour cela, on va attacher une ou plusieurs valeurs à chaque nœud. Voici par exemple un arbre où chacun des quatre nœuds
contient une chaîne de caractères :
Les arbres vides, en revanche, ne contiennent pas d'information.
Dans la pratique, il existe de nombreuses
variantes des arbres binaires que nous venons de présenter.
Ainsi, il arrive que les feuilles contiennent une information d'une nature différente, ou encore que seules les feuilles contiennent une information.
Nous nous en tiendrons à la version la plus simple, qui est celle que nous avons présentée.
Il y a de nombreuses façons de représenter un arbre binaire en Python.
Une manière traditionnelle consiste à représenter chaque nœud par un objet d'une classe, qu'on appellera ici Noeud.
Programme — Nœud d'un arbre binaire
class Noeud:
\"\"\"un noeud d'un arbre binaire\"\"\"
def __init__(self, g, v, d):
self.gauche = g
self.valeur = v
self.droit = d
Comme on le voit, un objet de cette classe contient trois attributs :
- un attribut gauche pour le sous-arbre gauche;
- un attribut valeur pour la valeur contenue dans le nœud;
- et un attribut droit pour le sous-arbre droit.
Par ailleurs, l'arbre vide est représenté par la valeur None.
Pour construire un arbre, il suffit d'appliquer le constructeur de la classe
Noeud autant de fois qu'il y a de nœuds dans l'arbre. Ainsi, arbre
est construit et stocké dans la variable a avec cette instruction :
a = Noeud(Noeud(None, \"B\", Noeud(None, \"C\", None)),
\"A\",
Noeud(None, \"D\", None))
On a ici créé quatre objets de la classe Noeud, qui sont illustrés dans la figure ci-dessous.
La valeur contenue dans la variable a est l'adresse mémoire de l'objet contenant la valeur \"A\", qui constitue la racine de l'arbre.
Ce nœud contient lui-même dans son attribut gauche l'adresse mémoire de l'objet contenant la valeur \"B\" et dans son attribut droit l'adresse mémoire de
l'objet contenant la valeur \"D\", et ainsi de suite.
Certains des attributs gauche ou droit ont une valeur None, lorsque le sous-arbre correspondant est vide.
Dans la séquence suivant, nous expliquerons comment un arbre peut être
encapsulé dans un objet, exactement comme nous l'avons fait pour les listes
Représentations alternatives
Exactement comme pour les listes chaînées, d'autres représentations sont possibles.
Plutôt qu'un objet de la classe Noeud, on pourrait utiliser un triplet, et dans ce
cas écrire
a = ((None,\"B\", (None, \"C\",None)) , \"A\", (None, \"D\" ,None))
,un dictionnaire, ou encore un tableau à trois éléments.
Cependant, l'utitisation d'une valeur structurée avec des champs nommés (ici les attributs gauche, valeur et droit) est idiomatique, y compris dans un langage comme Python.
Orientation des arbres
Comme avec les listes doublement chaînées, il est tout à fait envisageable d'avoir un chaînage bidirectionnel dans les arbres, où chaque nœud qui n'est pas la racine est également relié à son
nœud parent.
Pour cela, il suffit d'ajouter un quatrième attribut à la classe Noeud, appelé parent, qui contient None pour un nœud racine et un objet de la classe Noeud sinon.
Homogénéité
Exactement comme les listes chaînées, les les arbres peuvent contenir des valeurs de n'importe quel type et nous recommandons une utilisation homogène des arbres, où les valeurs contenues dans les nœuds d'un même arbre sont toutes du même type.
Mettre le résultat ici (code et figure).
La définition d'arbre binaire étant récursive, il est naturel d'écrire des
opérations sur les arbres binaires sous la forme de fonctions récursives.
L'exemple le plus simple est celui d'une fonction taille qui calcule la taille
d'un arbre.
def taille(a):
\"\"\"Le nombre de noeuds de l'arbre a\"\"\"
On commence par considérer le cas de base où l'arbre a est vide.
Dans ce cas, il convient de renvoyer 0, car il n'y à aucun nœud dans l'arbre.
if a is None:
return 0
Dans le cas contraire, l'arbre contient au moins un nœud (la racine de l'arbre), auquel on va ajouter la taille des sous-arbres gauche et droit, calculées récursivement.
else:
return 1 + taille(a.gauche) + taille(a.droit)
Il est important de noter que les expressions a.gauche et a.droite ne provoqueront pas d'erreur, car l'arbre a n'est pas vide.
Le code complet est le suivant:
Programme — Calcul de la taille et de la hauteur
def taille(a):
\"\"\"le nombre de noeuds de L'arbre a\"\"\"
if a is None:
return 0
else:
return 1 + taille(a.gauche) + taille(a.droit)
Ensuite, nous pouvons créer une fonction qui calcule la hauteur d'un arbre.Sa structure est très similaire à la fonction taille :
def hauteur(a):
\"\"\"la hauteur de l'arbre a\"\"\"
if a is None:
return 0
else:
return 1 + max(hauteur(a.gauche), hauteur(a.droit))
Efficacité. Il est clair que les deux fonctions taille et hauteur ont une
complexité directement proportionnelle au nombre de nœuds de l'arbre.
En effet, ces deux fonctions font un nombre d'opérations borné sur chaque nœud
(addition, maximum) et parcourent une fois et une seule chaque nœud.
Tester avec :
print(\"taille de a\",taille(a))
print(\"hauteur de a\",hauteur(a))
et conclure.
Mettre le résultat ici (code et figure).
Les deux fonctions que nous venons d'écrire, à savoir taille et hauteur, parcourent tous les nœuds de l'arbre.
L'ordre dans lequel ce parcours est
effectué n'est pas important. Que ce soit pour calculer la taille ou la hauteur, peu importe si on commence le calcul par le sous-arbre gauche ou droit.
Écrivons maintenant une autre fonction, qui affiche les valeurs contenues dans tous les nœuds de l'arbre, par exemple une par ligne.
L'ordre dans lequel le parcours des nœuds est effectué devient important. On peut
par exemple parcourir le sous-arbre gauche, puis afficher la valeur de la racine, puis enfin parcourir le sous-arbre droit.
On appelle cela un parcours infixe.
Le programme suivant contient le code d'une fonction parcours_infixe qui imprime les valeurs des nœuds d'un arbre dans un parcours infixe.
Programme — Parcours infixe d'un arbre binaire
def parcours_infixe(a):
\"\"\"affiche les éléments de a dans un parcours infite\"\"\"
if a is None:
return
parcours_infixe(a.gauche)
print (a.valeur)
parcours_infixe(a.droit)
Tester avec :
parcours_infixe(a)
Efficacité. La fonction parcours_infixe a une complexité directement proportionnelle au nombre de nœuds de l'arbre. Comme les fonctions taille et hauteur, elle fait un nombre d'opérations borné sur chaque nœud (ici, l'affichage de la valeur) et parcourt une fois et une seule chaque nœud.
Mettre le résultat ici (code et figure).
D'autres parcours
Le parcours infixe n'est pas la seule façon de parcourir
les nœuds d'un arbre. On pourrait afficher la valeur avant de parcourir les
sous-arbres (on parle alors de parcours préfixe) ou après (on parle alors de
parcours postfixe).
Si on ajoute la possibilité de parcourir le sous-arbre droit avant le sous-arbre gauche, cela fait encore trois autres solutions, même si elles sont peu utilisées en pratique et ne portent du coup pas de nom.
Attention au partage
Rien ne nous empêche de réutiliser plusieurs fois un même sous-arbre dans une construction d'arbre. Ainsi, on peut
écrire le code Python à gauche et obtenir (en mémoire) l'arbre à droite :
f = Noeud(None, 1, None)
r = Noeud( f , 2, f )
Il s'agit là d'un arbre de taille 3, avec un sous-arbre gauche contenant un nœud et un sous-arbre droit contenant également un nœud.
Le fait que ces deux nœuds sont en réalité un même nœud en mémoire n'est
pas observable en première approximation.
En particulier, un appel à taille(r) renvoie la valeur 3, car la fonction taille parcourt d'abord le sous-arbre gauche, puis le sous-arbre droit.
On peut tout à faire réaliser un tel partage intentionnellement, par exemple pour économiser de la mémoire.
Maïs il faut bien avoir conscience que le partage est difficilement compatible avec des modifications de la structure de l'arbre ou des valeurs contenues dans les
nœuds.
Un arbre binaire est un ensemble fini de nœuds, qui est soit vide, soit structuré à partir d'un nœud particulier, appelé la racine de l'arbre, et de deux sous-ensembles de nœuds formant récursivement
un sous-arbre gauche et un sous-arbre droit.
Un arbre peut être matérialisé en Python avec un objet par nœud, d'une classe qui à trois attributs : le sous-arbre gauche, le sous-arbre droit et une valeur stockée
dans le nœud,
La valeur None est utilisée pour représenter l'arbre vide.
Dessiner tous les arbres binaires ayant respectivement 3 et 4 nœuds.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
Il y a 5 arbres binaires possédant 3 nœuds :
_1_ _1_ _1_
/ \\ / \\ / \\
_2_ _3_ _2_ _2_
/ \\ / \\ / \\ / \\
_3_ _3_
/ \\ / \\
_1_ _1_
/ \\ / \\ / \\
_2_ _2_
/ \\ / \\
_3_ _3_
/ \\ / \\
Il y a 14 arbres binaires possédant 4 nœuds :
__1__ / \\ _2_ _3_ / \\ / \\ _4_ / \\ | __1__ / \\ _2_ _3_ / \\ / \\ _4_ / \\ | __1__ / \\ _2_ _3_ / \\ / \\ _4_ / \\ |
__1__ / \\ _2_ _3_ / \\ /. \\ _4_ / \\ | __1__ / \\ __2__ / \\ _3_ _4_ /. \\ / \\ | __1__ / \\ __2__ / \\ _3_ /. \\ _4_ /. \\ |
__1__ / \\ __2__ / \\ _3_ /. \\ _4_ / \\ | __1__ / \\ _2_ / \\ _3_ / \\ _4_ / \\ | __1__ / \\ _2_ / \\ _3_ / \\ _4_ / \\ |
| __1__ / \\ __2__ / \\ _3_ _4_ /. \\ / \\ | __1__ / \\ __2__ / \\ _3_ /. \\ _4_ /. \\ | __1__ / \\ __2__ / \\ _3_ /. \\ _4_ /. \\ |
| __1__ / \\ __2__ / \\ _3_ /. \\ _4_ /. \\ | __1__ / \\ __2__ / \\ _3_ /. \\ _4_ / \\ |
Sachant qu'il y à 1 arbre binaire vide, 1 arbre binaire contenant 1 nœud, 2 arbres binaires contenant 2 nœuds, 5 arbres binaires contenant 3
nœuds et 14 arbres binaires contenant 4 nœuds, calculer le nombre d'arbres binaires contenant 5 nœuds.
On ne cherchera pas à les construire tous, mais seulement à les dénombrer.
Mettre le résultat ici (code et figure).
Pour les dénombrer, on considère le nœud à la racine puis on répartit les quatre nœuds restants entre le sous-arbre gauche et le sous-arbre droit.
Par exemple, on peut mettre un nœud dans le sous-arbre gauche et trois dans le sous-arbre droit.
Au total, il y a cinq façons différentes
de répartir les nœuds (0+4, 1+3 , 2+2, 3+1, 4+0).
Pour chacune, on connaît le nombre de sous-arbres possibles, ce qui donne la somme
1x14 + 1x5 + 2x2 + 5x1 + 14x1
soit un total de 42 arbres binaires possédant 5 nœuds.
"}],[{"text":"Écrire une fonction affiche1(a) qui imprime un arbre sous la forme suivante :
- pour un arbre vide, on n'imprime rien;
- pour un nœud, ou sa valeur, son sous-arbre droit (récursivement), puis enfin une parenthèse fermante.
Ainsi, pour l'arbre :
on doit afficher ((B(C))A(D)).
Tester avec :
a1 = Noeud(Noeud(None,\"B\",Noeud(None,\"C\",None)),\"A\",Noeud(None,\"D\",None))
affiche1(a1)
Résultat :
((B(C))A(D))
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
def affiche1(a):
if a is None:
return
print (\"(\", end=\"\")
affiche1(a.gauche)
print(a.valeur, end=\"\")
affiche1(a.droit)
print(\")\", end=\"\")
Dessiner l'arbre binaire sur lequel la fonction affiche1 de l'exercice précédent produit la sortie :
(1((2)3)).
D'une manière générale, expliquer comment retrouver l'arbre dont l'affichage est donné.
Mettre le résultat ici (code et figure).
Pour la sortie (1((2)3)), l'arbre est le suivant :
__1__
/ \\
_3_
/ \\
_2_
/ \\
D'une manière générale, on distingue deux cas : si l'affichage est vide, l’arbre
est vide; sinon, il y a une paire de parenthèses qui encadre la chaîne toute
entière. On cherche alors la valeur qui est contenue dans cette paire de parenthèses et qui n’est contenue dans aucune autre.
C’est la valeur que l'on place à la racine.
À gauche (resp. droite) de cette valeur, on trouve la sous-chaîne qui nous permet de reconstruire (récursivement) le sous-arbre gauche (resp. droit).
"}],[{"text":"Ajouter à la classe Noeud une méthode __eq__ permettant de tester l'égalité entre deux arbres binaires à l'aide de l'opération ==.
Tester avec :
a = Noeud(None,\"C\",None)
b = Noeud(None,\"B\",None)
c = Noeud(a,\"A\",b)
d = Noeud(a,\"A\",b)
e = Noeud(a,\"A\",a)
print(c==d)
print(c==e)
Résultat :
True
False
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
Les sous-arbres étant également des nœuds, pour lesquels on est justement en train de définir une méthode __eq_., il suffit de les comparer récursivement avec ==. Il faut en revanche bien vérifier avant cela que n n’est pas l'arbre vide et il ne faut surtout pas le faire avec == car cela provoquerait un appel récursif.
Comme il arrive parfois dans les fonctions récursives, le piège est au niveau du cas de base.
En revanche la vérification pour self est inutile : la méthode n’aurait pas pu être appelée sur un arbre égal à None.
class Noeud:
\"\"\"un noeud d'un arbre binaire\"\"\"
def __init__(self, g, v, d):
self.gauche = g
self.valeur = v
self.droit = d
def __eq__(self, n):
return n is not None \\
and self.gauche == n.gauche \\
and self.valeur == n.valeur \\
and self.droit == n.droit
Écrire une fonction parfait(h) qui reçoit en argument un entier h supérieur ou égal à zéro et renvoie un arbre binaire parfait de hauteur h.
Tester avec :
a2 = parfait(4)
affiche1(a2)
Résultat :
((((1)2(1))3((1)2(1)))4(((1)2(1))3((1)2(1))))
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
On procède récursivement :
def parfait(h):
\"\"\"construit un arbre binaire parfait de hauteur h\"\"\"
if h == 0:
return None
return Noeud(parfait(h-1), h, parfait(h-1))
On ne factorise pas l’appel récursif parfait(h-1) pour ne pas introduire de partage.
On a choisi ici de stocker la hauteur comme valeur dans chaque nœud.
"}],[{"text":"Écrire une fonction peigne_gauche(h) qui reçoit en argument un entier h supérieur ou égal à zéro et renvoie un peigne de hauteur h où chaque nœud à un sous-arbre droit qui est vide.
Tester avec :
a3 = peigne_gauche(4)
affiche1(a3)
Résultat :
((((4)3)2)1)
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
On peut le faire au choix avec une fonction récursive
(comme dans l’exercice précédent) ou avec une boucle. On choisit ici la
seconde solution :
def peigne_gauche(h) :
\"\"\"construit un peigne gauche de hauteur h\"\"\"
a = None
while h > 0:
a = Noeud(a, h, None)
h -= 1
return a
Il est intéressant de noter que les nœuds de l’arbre sont ici construits de bas
en haut. C’est ce qui nous permet notamment de l'écrire facilement avec une
boucle.
Écrire une fonction est_peigne_gauche(a) qui renvoie True si et seulement a est un peigne à gauche.
Tester avec :
a3 = peigne_gauche(4)
print(est_peigne_gauche(a3))
a4 = parfait(4)
print(est_peigne_gauche(a4))
Résultat :
True
False
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
On l'écrit ici comme une fonction récursive :
def est_peigne_gauche(a):
if a is None:
return True
if not a.droit is None:
return False
return est_peigne_gauche(a.gauche)
Mais on pourrait le faire tout aussi bien avec une boucle (cinq lignes de code
également).
Donner cinq arbres de taille 3, différents, dont les nœuds contiennent les valeurs 1, 2, 3 et pour lesquels la fonction parcours_infixe affiche à chaque fois
1
2
3
dans cet ordre.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
On reprend les cinq arbres de l’exercice sur le dessin des arbres et on les étiquette correctement à chaque fois:
_3_ / \\ _2_ / \\ _1_ / \\ | _3_ / \\ _1_ / \\ _2_ / \\ | __2__ / \\ _1_ _3_ / \\ / \\ |
_1_ / \\ _2_ / \\ _3_ / \\ | _1_ / \\ _3_ / \\ _2_ / \\ |
- Détails
- Écrit par : Richard GAUTHIER
- Clics : 1914
[[{"text":"
![\"pile_file.png](\"https://sciencesappliquees.com/images/nsi/pile_file.png\")
![\"pile_file1.png](\"https://sciencesappliquees.com/images/nsi/pile_file1.png\")
","title":"Piles et files","posi":19},{"edit":"
"}],[{"text":"
","title":"Interface et utilisation d'une pile"},{"edit":"
"}],[{"text":"
","title":"Utilisation d'une pile : bouton de retour en arrière","tagtitle":"h1"},{"edit":"
"}],[{"text":"
","title":"Pile d'appels"},{"edit":"
"}],[{"text":"
","title":"Interface et utilisation d'une file"},{"edit":"
"}],[{"text":"
","title":"Utilisation d'une file : jouer à la bataille"},{"edit":"
"}],[{"text":"
","title":"Réaliser une pile avec une liste chaînée","tagtitle":"h1"},{"edit":"
"}],[{"text":"
","title":"Piles et tableaux Python"},{"edit":"
"}],[{"text":"
","title":"Réaliser une file avec une liste chaînée mutable"},{"edit":"
"}],[{"text":"
"}],[{"text":"
","title":"Réaliser une file avec deux piles"},{"edit":"
"}],[{"text":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice","tagtitle":"h1"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice","tagtitle":"h1"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice","tagtitle":"h1"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice","tagtitle":"h1"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"Pour afficher la valeur de la carte, on utilise 2 tableau :
"}]]
Les structures de pile et de file permettent toutes deux de stocker des ensembles d'objets et fournissent des opérations permettant d'ajouter ou de retirer des objets un à un.
Les éléments retirés ne sont cependant, ni dans une structure ni dans l'autre, retirés dans un ordre arbitraire, et chacune de ces structures à sa règle.
Dans une pile (en anglais stack), chaque opération de retrait retire l'élément arrivé le plus récemment.
On associe cette structure à l'image d'une pile d'assiettes, dans laquelle chaque nouvelle assiette est ajoutée au-dessus des précédentes, et où l'assiette retirée est systématiquement celle du sommet.
Cette discipline est nommée dernier entré, premier sorti (DEPS), ou plus couramment en anglais LIFO (last in, first out).
Dans une structure de file en revanche (en anglais queue), chaque opération de retrait retire l'élément qui avait été ajouté le premier.
On associe cette structure à l'image d'une file d'attente, dans laquelle des personnes arrivent à tour de rôle, patientent, et sont servies dans leur ordre d'arrivée.
Cette discipline est nommée premier entré, premier sorti (PEPS), ou plus couramment en anglais FIFO (first in, first out).
Classiquement, chacune de ces deux structures à une interface proposant au minimum les quatre opérations suivantes :
- créer une structure initialement vide,
- tester si une structure est vide,
- ajouter un élément à une structure,
- retirer et obtenir un élément d'une structure.
De même qu'on la déjà préconisé pour les tableaux et les listes chaînées, on s'attend à ce que les piles ct les files soient des structures homogènes, c'est-à-dire que tous les éléments stockés aient le même type.
Et évidemment, l'opération de retrait suit la discipline correspondant à la structure concernée.
Le plus souvent, les structures de pile et de file sont également considérées mutables : chaque opération
d'ajout ou de retrait d'un élément modifie la pile ou la file à laquelle elle s'applique.
Enfin, sauf mention contraire explicite, il n'y a pas de limite de principe au nombre d'éléments qui peuvent être accueillis dans une pile ou une file :
il est toujours possible d'en ajouter un nouveau.
En plus des opérations minimales déjà citées, les interfaces des piles ou des files ajoutent souvent d'autres opérations facilitant leur manipulation.
Par exemple :
- connaître le nombre d'éléments contenus dans une structure,
- vider une structure,
- consulter un élément d'une structure (celui qu'on aurait obtenu avec l'opération de retrait) sans le retirer,
- etc.
Dans ce chapitre, nous allons voir dans un premier temps les interfaces des structures de pile et de file et des exemples d'utilisation.
Ensuite, nous détaillerons plusieurs manières de réaliser ces structures.
Pour exprimer l'interface des piles, nous notons Pile[T] le type des piles contenant des éléments de type T.
L'opération est_vide, qui prend en paramètre une pile et renvoie un booléen indiquant la vacuité de la pile, a
donc le type suivant.
est_vide(Pile[T]) -> bool
À l'inverse, l'opération creer_pile de création d'une pile vide ne prend aucun paramètre et renvoie une nouvelle pile.
creer_pile() -> Pile[T]
On remarque que le type T des éléments de la pile ainsi créée ne peut pas être déduit des paramètres inexistants. Il faut simplement comprendre de cette définition que l'opération de création peut fournir une pile accueillant des éléments de n'importe quel type T.
Notez que cela ne signifie pas que chaque élément puisse avoir n'importe quel type.
En effet, ce type T, bien qu'arbitraire, reste valable pour toute la pile.
L'opération d'ajout d'un élément au sommet d'une pile est traditionnellement appelée empiler (ou push en anglais).
Elle prend en paramètres une pile et l'élément à ajouter, d'un type homogène avec celui des éléments de la pile.
Cette opération ne produit pas de résultat.
empiler(PilefTi, T) -> None
Inversement, l'opération de retrait de l'élément au sommet d'une pile est appelée depiler (ou pop en anglais). Elle prend en paramètre la pile et renvoie l'élément qui en a été retiré.
depiler(Pile[T}) -> T
Cette dernière opération suppose que la pile est non vide et lèvera une exception dans le cas contraire.
| fonction | description |
| Pile[T] "}\" style=\"border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; padding: 2px 3px; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">creer_pile() -> Pile[T] | crée une pile vide |
| bool "}\" style=\"border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; padding: 2px 3px; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">est_vide(p: Pile[T]) -> bool | renvoie True si p est vide et False sinon |
| None"}\" style=\"border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; padding: 2px 3px; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">empiler(p: Pile[T], e: T) -> None | ajoute e au sommet de p |
| T "}\" style=\"border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; padding: 2px 3px; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">depiler(p: Pile[T]) ->T | retire et renvoie l'élément au sommet de p |
Notez que dans la suite nous montrerons des utilisations de cette interface où les opérations sont réalisées par des fonctions ordinaires, mais aussi des
utilisations supposant que la structure de pile est réalisée par une classe dont les opérations est_vide, empiler et depiler sont des méthodes.
L'ajout de l'élément e au sommet de la pile p s'écrira donc empiler(p, e) dans le premier cas et p.empiler(e) dans le second.
Mettre le résultat ici (code et figure).
Considérons un navigateur web dans lequel on s'intéresse à deux opérations : aller à une nouvelle page et revenir à la page précédente.
On veut que le bouton de retour en arrière permette de remonter une à une les pages précédentes, et ce jusqu'au début de la navigation.
En plus de l'adresse courante, qui peut être stockée dans une variable à part, il nous faut donc conserver l'ensemble des pages précédentes auxquelles il est possible de revenir.
Puisque le retour en arrière se fait vers la dernière
page qui a été quittée, la discipline « dernier entré, premier sorti » des piles est exactement ce dont nous avons besoin pour cet ensemble.
adresse_courante = “\"
adresses_precedentes = creer_pile()
Ainsi, lorsque l'on navigue vers une nouvelle page, l'adresse de la page courante peut être ajoutée au sommet de la pile des pages précédentes avec l'opération empiler.
l'adresse cible donnée en paramètre peut alors être
enregistrée comme nouvelle adresse courante.
def aller_a(adresse_ cible):
empiler(adresses_precedentes , adresse_courante)
adresse_courante = adresse_cible
Lorsque l'on veut revenir en arrière, il suffit alors de revenir à la dernière page enregistrée sur la pile.
Ici, en outre, on vérifie au préalable qu'il existe bien une page précédente et on ne fait rien si ce n'est pas le cas.
def retour():
if not est_vide(adresses_precedentes):
adresse_courante = depiler(adresses_precedentes)
Le programme ci-dessous redonne l'ensemble de cet exemple, en utilisant cette fois la notation des classes et des appels de méthodes.
Attention, il faut importer le module modPile.py et le mettre où se trouve votre programme.
Programme — Navigation
from modPile import Pile
class Navigation:
\"\"\"Gere la navigation du navigateur\"\"\"
def __init__(self):
self.adresse_courante = \"\"
self.adresses_precedentes = Pile()
def aller_a(self,adresse_cible):
self.adresses_precedentes.empiler(self.adresse_courante)
self.adresse_courante = adresse_cible
def retour(self):
if not self.adresses_precedentes.est_vide():
self.adresse_courante = self.adresses_precedentes.depiler()
def naviguer(self):
while True :
adresse = input(\"Adresse ou < :\")
if adresse == \"<\" :
self.retour()
else :
self.aller_a(adresse)
print(\"Page :\",self.adresse_courante)
Tester avec :
#Lancer la navigation
nav = Navigation()
#lancer la navigation
nav.naviguer()
On a parlé dans certaines séquences d'une « pile d'appels » existant à tout moment de l'exécution d'un programme et contenant, à chaque instant, les informations relatives à tous les appels de fonctions emboîtés en cours d'exécution.
Ce nom correspond bien à la structure d'une pile au sens que nous décrivons dans cette séquence.
En effet, lorsqu'une exécution d'une fonction f déclenche elle-même un appel à une autre fonction g (ou récursivement à la même fonction), la progression dans le code de f est suspendue jusqu'à obtention du
résultat de l'appel à g.
L'appel à f ne peut donc se conclure et disparaître
de la pile d'appels qu'après que l'appel à g est lui-même terminé. Dit autrement, le premier appel à quitter la pile d'appels est le dernier qui y est entré.
Ceci tient à la propriété des appels de fonctions d'être bien emboîtés.
Pour exprimer l'interface des files, nous notons File[T] le type des files contenant des éléments de type T.
Ceci étant fixé, l'interface des files, donnée par l'interface 2, est similaire à celle des piles.
L'opération d'ajout sera simplement appelée ajouter (elle est parfois appelée enfiler, ou en anglais enqueue) et l'opération de retrait retirer (parfois défiler, ou en anglais dequeue).
Interface 3 — File d'étéments de type T
| fonction | description |
| Pile[T] "}\" style=\"padding: 2px 3px; border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">creer_file() -> File[T] | crée une file vide |
| bool "}\" style=\"padding: 2px 3px; border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">est_vide(f: File[T]) -> bool | renvoie True si f est vide et False sinon |
| None"}\" style=\"padding: 2px 3px; border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">ajouter(f: File[T], e: T) -> None | ajoute e à l'arrière de f |
| T "}\" style=\"padding: 2px 3px; border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">retirer(f: File[T]) ->T | retire et renvoie l'élément à l'avant de f |
Considérons le jeu de cartes de la bataille. Chaque joueur possède un paquet de cartes et pose à chaque manche la carte prise sur le dessus du paquet.
Le vainqueur de la manche récupère alors les cartes posées, pour les placer au-dessous de son paquet.
En plus des cartes posées au centre de la table, dont on discutera le traitement plus bas, nous avons besoin de conserver en mémoire le paquet de cartes de chaque joueur. Puisque les cartes sont remises dans un paquet à une extrémité et prélevées à l'autre, la discipline « premier entré, premier sorti » des files est exactement ce dont nous avons besoin pour chacun de
ces ensembles.
En supposant que les joueurs s'appellent Alice et Basile, nous pouvons donc créer ainsi deux paquets de cartes.
paquet_alice = File()
paquet_basile = File()
Une opération de distribution des cartes peut ensuite placer dans ces deux paquets les cartes de départ de chacun des joueurs.
#crée le jeu de 52 cartes
cartes = [i for i in range(0,52)]
#melange les cartes
random.shuffle(cartes)
#distribue les cartes aux 2 joueurs
for i in range(len(cartes)//2) :
paquet_alice.ajouter(cartes.pop())
paquet_basile.ajouter(cartes.pop())
Regardons maintenant quelques aspects de la réalisation d'un tour de jeu. Au moment de démarrer un tour, un joueur perd s'il n'a plus de cartes dans son paquet.
def tour():
global en_cours
if paquet_alice.est_vide():
print(\"Alice perd\")
en_cours = False
elif paquet_basile.est_vide():
print(\"Basile perd\")
en_cours = False
else :
tirer()
Si Ia partie n'est pas terminée, le jeu demande alors à chaque joueur de tirer sa première carte. Il s'agit de prélever la première carte du paquet de chaque joueur, avec l'opération defiler.
def joue():
a = paquet_alice.retirer()
b = paquet_basile.retirer()
valeura = a%13
valeurb = b%13
Remarque : modulo 13 (%13), car il y 13 cartes par couleur (pique, carreau, trèfle, coeur).
Si l'un des joueurs gagne ce tour, on peut alors remettre ces deux cartes au fond de son paquet, c'est-à-dire à l'arrière de sa file de carte, avec l'opération
enfiler.
print(\"Alice\",valeura,valeurb,\"Basile\")
#le programme ne gere pas l'égalité
if valeura > valeurb :
paquet_alice.ajouter(a)
paquet_alice.ajouter(b)
elif valeura < valeurb :
paquet_basile.ajouter(b)
paquet_basile.ajouter(a)
Sans présumer de la manière dont sont représentées les cartes, on suppose ici disposer d'une fonction valeur permettant une comparaison.
Vous terminerez en exercice ce jeu. Vous aurez à gérer d'une part la valeur des cartes et d'autre part les cas d'égalités.
Le programme partiel du jeu de bataille est le suivant :
from modFile import File
import random
paquet_alice = File()
paquet_basile = File()
#crée le jeu de 52 cartes
cartes = [i for i in range(0,52)]
#melange les cartes
random.shuffle(cartes)
#distribue les cartes aux 2 joueurs
for i in range(len(cartes)//2) :
paquet_alice.ajouter(cartes.pop())
paquet_basile.ajouter(cartes.pop())
#Gestion d'un tour de jeu
def tour():
global en_cours
if paquet_alice.est_vide():
print(\"Alice perd\")
en_cours = False
elif paquet_basile.est_vide():
print(\"Basile perd\")
en_cours = False
else :
tirer()
#Si la partie n'est pas terminée, tirage d'une carte
def tirer():
a = paquet_alice.retirer()
b = paquet_basile.retirer()
valeura = a%13
valeurb = b%13
print(\"Alice\",valeura,valeurb,\"Basile\")
#le programme ne gere pas l'égalité
if valeura > valeurb :
paquet_alice.ajouter(a)
paquet_alice.ajouter(b)
elif valeura < valeurb :
paquet_basile.ajouter(b)
paquet_basile.ajouter(a)
#démarrage du jeu
en_cours = True
nb_tours = 0
while en_cours :#not paquet_alice.est_vide() and not paquet_basile.est_vide() :
tour()
nb_tours+=1
print(\"Partie en \",nb_tours,\" tours\")
Importer le module modFile.py :
https://sciencesappliquees.com/images/nsi/modFile.py
et tester le jeu de carte de la bataille.
Conclure sur le role de la classe File.
Mettre le résultat ici.
La structure de liste chaînée donne une manière élémentaire de réaliser une pile.
Empiler un nouvel élément revient à ajouter une nouvelle cellule en tête de liste, tandis que dépiler un élément revient à supprimer la cellule de tête.
Où peut ainsi construire une classe Pile définie par un unique attribut contenu associé à l'ensemble des éléments de la pile, stockés sous la forme d'une liste chaînée.
class Pile:
Le constructeur Pile(), défini par la méthode __init__ (self), construit une pile vide en définissant contenu comme la liste vide.
On rappelle que la liste chaînée vide est simplement représentée par la valeur None.
def __init__(self):
self.contenu = None
Ainsi, tester la vacuité d'une pile revient simplement à tester si son contenu
est la liste vide.
def est_vide(self):
return self.contenu is None
On empile un nouvel élément en ajoutant une nouvelle cellule devant celles que contient déjà notre liste chaînée. On peut réaliser cela en construisant
une nouvelle liste chaînée dont la première cellule contient :
- comme valeur l'élément que l'on souhaite empiler,
- comme cellule suivante la première cellule de la liste d'origine, c'est-à- dire self.contenu.
On écrit donc :
def empiler(self, v):
c = Cellule(v, self.contenu)
Ne reste alors qu'à définir cette nouvelle liste chaînée comme le nouveau contenu de notre pile.
self.contenu = c
Récupérer la valeur au sommet de la pile consiste alors à consulter la valeur de la première cellule, en supposant que cette première cellule existe, autrement dit en supposant que la pile n'est pas vide.
def depiler(self):
if self.est_vide():
raise IndexError(\"depiler sur une pile vide\")
v = self.contenu.valeur
On complète l'opération de dépilement en retirant le premier élément, c'est-à-dire en redéfinissant le contenu de notre pile comme la liste d'origine
privée de sa première cellule. Autrement dit, la nouvelle cellule de tête est la cellule suivante de la cellule supprimée.
Après cette mise à jour, on peut renvoyer la valeur qui avait été prélevée dans la cellule de tête d'origine.
self.contenu = self.contenu.suivante
return v
Le programme ci-dessous regroupe tous ces éléments pour donner une mise en œuvre complète de la structure de pile à l'aide d'une liste chaînée.
Programme — Réalisation d'une pile avec une liste chaînée
class Cellule:
\"\"\"une cellule d'une liste chaînée\"\"\"
def __init__(self, v, s):
self.valeur = v
self.suivante = s
class Pile:
\"\"\"structure de pite\"\"\"
def __init__(self):
self.contenu = None
def est_vide(self):
return self.contenu is None
def empiler(self, v):
self.contenu = Cellule(v, self.contenu)
def depiler(self):
if self.est_vide():
raise IndexError(\"depiler sur une pile vide\")
v = self.contenu.valeur
self.contenu = self.contenu.suivante
return v
def creer_pile():
return Pile()
Tester la création d'une pile avec les instructions suivantes :
p = Pile()
#ou p = creer_pile()
print(\"p est vide?\",p.est_vide())
p.empiler(1)
p.empiler(2)
p.empiler(3)
p.empiler(4)
print(\"p est vide ?\",p.est_vide())
print(\"retire le 1er element :\",p.depiler())
Décrire les instructions ci-dessous et dessiner la pile à la fin des instructions.
Mettre le résultat ici (code et figure).
. Les tableaux de Python réalisent également
directement une structure de pile, avec leurs opérations append et pop.
On pourrait donc donner une définition en apparence très simple à une autre version de la classe Pile.
class PileTab:
\"\"\"structure de pile avec tableau\"\"\"
def __init__(self):
self.contenu = []
def est_vide(self):
return len(self.contenu) == 0
def empiler(self, v):
self.contenu.append(v)
def depiler(self):
if self.est_vide():
raise IndexError(\"depiler sur une pile vide\")
return self.contenu.pop()
Dans le cadre d'un programme Python, cette réalisation est raisonnable et efficace, les opérations append et pop s'exécutant en moyenne en temps constant. Cette solution, cependant, ne s'exporte pas directement
à n'importe quel autre langage, puisqu'elle cache la richesse de la structure de tableau redimensionnable utilisée par les tableaux de Python.
Tester PileTab avec les instruction suivante et conclure par rapport au Pile précédent :
p = PileTab()
print(\"p est vide?\",p.est_vide())
p.empiler(1)
p.empiler(2)
p.empiler(3)
p.empiler(4)
print(\"p est vide ?\",p.est_vide())
print(\"affiche 1er element :\",p.depiler())
Mettre le résultat ici (code et figure).
La structure de liste chaînée donne également une manière de réaliser une file, à condition de considérer la variante des listes chaînées mutables.
Comme dans la réalisation d'une pile, on peut retirer l'élément de tête en retirant la cellule de tête.
En revanche, l'ajout d'un nouvel élément à l'arrière de la file revient à ajouter une nouvelle cellule en queue de liste.
Une mutation intervient à cet endroit :
alors que la cellule qui était la dernière de la liste chaînée avant l'ajout n'avait pas de suivante définie, elle a comme suivante après l'ajout la nouvelle cellule créée pour le nouvel élément.
Autre différence avec la réalisation d'une pile, nous avons maintenant besoin de savoir accéder à la dernière cellule et plus seulement à la première. Il est possible, mais pas raisonnable, de trouver la dernière cellule en parcourant toute la liste chaînée à partir de la première cellule.
Il est plus intéressant de conserver dans notre structure
de données un attribut permettant d'accéder directement à cette dernière cellule.
On peut ainsi construire une classe File dont le constructeur définit deux attributs, l'un appelé tete et l'autre appelé queue, et désignant respectivement la première cellule et la dernière cellule de la liste chaînée utilisée pour stocker les éléments.
class File:
def __init__(self):
self.tete = None
self.queue = None
La file vide est caractérisée par le fait qu'elle ne contient aucune cellule.
En conséquence, sa tête et sa queue sont indéfinies.
En outre, l'une comme l'autre ne peut valoir None que dans ce cas. Pour tester la vacuité de la file, il suffit donc de consulter l'un des deux attributs.
def est_vide(self):
return self.tete îs None
L'ajout d'un nouvel élément à l'arrière de la file demande de créer une nouvelle cellule. Cette cellule prend la dernière place, et n'a donc pas de cellule
suivante :
def ajouter(self, x):
c = Cellule(x, None)
Cette cellule est alors définie comme suivant la cellule de queue actuelle. On a cependant besoin de traiter le cas particulier où il n'existe pas de cellule de queue, qui correspond à une file initialement vide.
Dans ce cas la nouvelle cellule devient l'unique cellule de la file, et donc sa cellule de tête.
if self.est_vide():
self.tete = c
else:
self.queue.suivante = c
Dans tous les cas, notre nouvelle cellule devient en outre la nouvelle cellule de queue de la file .
self.queue = c
Pour retirer un élément il s'agit de supprimer la première cellule de la file, exactement comme il avait été fait lors de l'utilisation d'une liste chaînée pour réaliser une pile.
Cependant, si la cellule retirée est la dernière, on doit également redéfinir l'attribut self.queue à None, afin de maintenir notre invariant qu'une file vide à ses deux attributs qui valent None.
Le programme ci-dessous montre l'intégralité du code de la classe File que nous venons de décrire.
Programme — Réalisation d'une file avec une tiste chaînée mutable
class File:
\"\"\"structure de file\"\"\"
def __init__(self):
self.tete = None
self.queue = None
def est_vide(self):
return self.tete is None
def ajouter(self, x):
c = Cellule(x, None)
if self.est_vide():
self.tete = c
else:
self.queue.suivante = c
self.queue = c
def retirer(self):
if self.est_vide():
raise IndexError(\"retirer sur une file vide\")
v = self.tete.valeur
self.tete = self.tete.suivante
if self.tete is None:
self.queue = None
return v
Tester la création d'une file avec les instructions suivantes :
f = File()
print(\"f est vide?\",f.est_vide())
f.ajouter(1)
f.ajouter(2)
f.ajouter(3)
f.ajouter(4)
print(\"f est vide ?\",f.est_vide())
print(\"retire 1er element :\",f.retirer())
Décrire les instructions ci-dessous et dessiner la file à la fin des instructions.
Mettre le résultat ici (code et figure).
La réalisation d'une file donnée par le programme précédent impose une représentation unique de la file
vide, où les deux attributs se1f.tete et self .queue valent None.
Cela peut simplifier la réflexion sur la structure, mais impose de prendre des précautions en programmant, notamment en incluant les deux lignes
if self.tete fs None:
self.queue = None
dans la fonction retirer pour s'assurer que lorsque l'on rend la file vide, les deux attributs sont bien annulés.
On peut cependant s'autoriser un peu plus de souplesse, et décider que n'importe quelle file dont l'attribut self.tete vaut None est une file vide, sans tenir compte de la valeur de self.queue.
Cela simplifie l'écriture de toute fonction susceptible de vider la file, et on pourra par exemple simplifier le code de retirer de la manière suivante.
def retirer(self):
if self.est_vide():
raise IndexError(\"retirer sur une file vide\")
v = self.tete.valeur
self.tete = self.tete.suivante
return v
En revanche cela pose aussi de nouvelles contraintes :
le test de vacuité
ne doit être fait qu'en fonction de l'attribut self.tete, et surtout il ne faut jamais travailler avec l'attribut self.queue d'une file dont la tête vaudrait None, car la valeur de la queue n'a aucune signification dans ce cas.
","title":"Représentation plus souple de la file vide"},{"edit":"Une réalisation radicalement différente de cette même structure de file consiste à utiliser deux piles, ou directement deux listes chaînées immuables.
On prend pour cela modèle sur un jeu de cartes où l'on disposerait d'une pioche, au sommet de laquelle on prend des cartes (disposées face cachée), et d'une défausse, au sommet de laquelle on en repose (disposées face visible)
Chacun de ces deux paquets de cartes est une pile, et ces deux paquets forment ensemble la réserve de cartes.
On a ensuite la discipline suivante :
- toute carte prise dans la réserve est retirée dans l'une de ces piles (la pioche),
- toute carte remise dans la réserve est ajoutée à l'autre pile (la défausse)
S'ajoute un mécanisme liant les deux paquets : une fois la pioche vide on retourne la défausse pour en faire une nouvelle pioche, laissant à la place une défausse vide.
Cette gestion des cartes correspond à une structure de file : une fois la pioche initiale vidée, les cartes seront piochées précisément dans l'ordre dans lequel elles ont été défaussées.
La première défaussée sera la première piochée (FIFO).
On peut donc définir une nouvelle version de la classe File utilisant ce principe.
Une file réalisée ainsi est caractérisée par deux attributs entree et sortie, le premier contenant une pile dans laquelle on ajoute les nouveaux éléments et le second une pile d'où l'on prend les éléments retirés.
class File:
def __init__ (self):
self.entree = creer _pile()
self.sortie = creer _pile()
Une file est vide lorsque ces deux piles sont toutes deux vides.
def est_vide(self):
return self.entree.est_vide() \\
and self.sortie.est_vide()
Ajouter un nouvel élément consiste simplement à empiler cet élément sur la pile d'entrée.
def ajouter(self, x):
self .entree .empiler(x)
Retirer un élément est l'opération la plus délicate. Dans le cas simple où la pile de sortie n'est pas vide, il suffit de dépiler son premier élément.
Dans le cas où la pile de sortie est vide, en revanche, il faut au préalable retourner la pile d'entrée pour la mettre à la place de la pile de sortie.
On peut réaliser cette opération intermédiaire en transférant un à un tous les éléments de la pile d'entrée sur la pile de sortie.
En effet, le premier élément prélevé sur la pile d'entrée est le dernier entrant (discipline FIFO de la pile utilisée), c'est-à-dire celui qui devra sortir de la file après tous les autres (discipline FIFO de la file que l'on veut réaliser}, et il sortira bien le dernier puisqu'il sera
ajouté le premier sur la pile de sortie (discipline FIFO de la pile utilisée).
def retirer(self):
if self .sortie.est_vide():
while not self.entree.est_vide():
self.sortie.empiler(self.entree.depiler())
On peut alors maintenant dépiler le premier élément de la nouvelle pile de sortie, qui, s'il y a eu retournement, était auparavant le dernier élément de la pile d'entrée, à moins que cette pile soit encore vide (ce qui signifierait
que les deux piles étaient vide, et donc la file également).
if self.sortie.est_vide():
raise IndexError(\"retirer sur une file vide\")
return self.sortie.depiler()
Le programme ci-dessous contient l'intégralité de cette nouvelle réalisation des fles.
Programme — Réalisation d'une file avec deux piles
class File2Piles:
\"\"\"structure de fite\"\"\"
def __init__(self):
self.entree = creer_pile()
self.sortie = creer_pile()
def est_vide(self):
return self.entree.est_vide() \\
and self.sortie.est_vide()
def ajouter(self, x):
self.entree.empiler(x)
def retirer(self):
if self.sortie.est_vide():
while not self.entree.est_vide():
self.sortie.empiler(self.entree.depiler())
if self.sortie.est_vide():
raise IndexError(\"retirer sur une file vide\")
return self.sortie.depiler()
Tester la création d'une file avec les instructions suivantes :
f = File2Piles()
print(\"f est vide?\",f.est_vide())
f.ajouter(1)
f.ajouter(2)
f.ajouter(3)
f.ajouter(4)
print(\"f est vide ?\",f.est_vide())
print(\"retire 1er element :\",f.retirer())
Décrire les instructions ci-dessous et dessiner la file à la fin des instructions.
Mettre le résultat ici (code et figure).
La pile est une structure de données de type « dernier entré, premier sorti ». Elle peut être réalisée avec une
liste chaînée ou avec un tableau Python.
La file est une structure de données de type « premier entré, premier sorti ». Elle peut être réalisée avec une liste chaînée mutable ou encore avec deux piles.
","title":"Conclusion","tagtitle":"h1"},{"edit":"Compléter la classe Pile avec les trois méthodes suivantes :
- consulter : retourne la valeur de l'élement en haut de la pile;
- taille : donne le nombre d'éléments dans la pile.
- vider : vide la pilz.
class Cellule:
\"\"\"une cellule d'une liste chaînée\"\"\"
def __init__(self, v, s):
self.valeur = v
self.suivante = s
class Pile:
\"\"\"structure de pite\"\"\"
def __init__(self):
self.contenu = None
def est_vide(self):
return self.contenu is None
def empiler(self, v):
self.contenu = Cellule(v, self.contenu)
def depiler(self):
if self.est_vide():
raise IndexError(\"depiler sur une pile vide\")
v = self.contenu.valeur
self.contenu = self.contenu.suivante
return v
Quel est l'ordre de grandeur du nombre d'opérations effectuées par la fonction taille ?
Tester avec :
p = Pile()
p.empiler(1)
p.empiler(2)
print(p.consulter())
p.empiler(3)
p.empiler(4)
p.empiler(5)
p.empiler(6)
print(p.taille())
p.vider()
print(p.consulter())
print(p.taille())
Résultat :
2
6
La pile est vide
0
Mettre le résultat ici (code et figure).
La consultation de l’élément au sommet est similaire
à l'opération depiler, mais ne modifie pas le contenu.
def consulter(self):
if self.est_vide():
return \"La pile est vide\"
#raise IndexError(\"consulter sur une pile vide\")
return self.contenu.valeur
On peut vider la pile en redéfinissant le contenu comme la liste vide.
def vider(self):
self.contenu = None
Le calcul de la taille peut se faire à l’aide d’une fonction calculant la longueur d’une liste.
Le coût de cette opération est proportionnel à la longueur de la liste, c’est-à-dire ici au nombre d'éléments que contient la pile.
def taille(self):
return self.longueur(self.contenu)
def longueur(self,liste) :
if liste is None :
return 0
elif liste.suivante is None :
return 1
else :
return 1 + self.longueur(liste.suivante)
On souhaite compléter le programme navigation pour avoir également une fonction retour_avant dont le comportement est le suivant :
- chaque appel à la fonction retour place la page quittée au sommet d'une deuxième pile adresses_suivantes,
- un appel à la fonction retour_avant amène à la page enregistrée au sommet de la pile adresses_suivantes, et met à jour les deux piles de manière adaptée,
- toute nouvelle navigation avec aller_a annule les adresses suivantes.
Programme — Navigation
class Navigation:
\"\"\"Gere la navigation du navigateur\"\"\"
def __init__(self):
self.adresse_courante = \"\"
self.adresses_precedentes = Pile()
def aller_a(self,adresse_cible):
self.adresses_precedentes.empiler(self.adresse_courante)
self.adresse_courante = adresse_cible
def retour(self):
if not self.adresses_precedentes.est_vide():
self.adresse_courante = self.adresses_precedentes.depiler()
def naviguer(self):
while True :
adresse = input(\"Adresse ou < :\")
if adresse == \"<\" :
self.retour()
else :
self.aller_a(adresse)
print(\"Page :\",self.adresse_courante)
#Lancer la navigation
nav = Navigation()
#lancer la navigation
nav.naviguer()
Modifier et compléter le programme pour définir cette nouvelle fonction.
Remarque : On utilisera la touche \">\" pour naviquer vers l'avant.
","title":"Exercice","tagtitle":"h1"},{"edit":"Mettre le résultat ici (code et figure).
L'initialisation demande de créer une nouvelle pile, vide à l’origine.
def __init__(self):
self.adresse_courante = \"\"
self.adresses_precedentes = Pile()
self.adresses_suivantes = Pile()
La fonction de navigation principale annule les adresses suivantes en vidant la pile correspondante.
def aller_a(self,adresse_cible):
self.adresses_suivantes.vider()
self.adresses_precedentes.empiler(self.adresse_courante)
self.adresse_courante = adresse_cible
Chaque retour en arrière ajoute l’adresse courante à la pile des adresses suivantes, avant de revenir effectivement à la dernière adresse précédente connue.
def retour(self):
if not self.adresses_precedentes.est_vide():
self.adresses_suivantes.empiler(self.adresse_courante)
self.adresse_courante = self.adresses_precedentes.depiler()
Symétriquement, retour_avant va à la première adresse suivante, après avoir remis la page courante sur la pile des adresses précédentes.
def retour_avant(self):
if not self.adresses_suivantes.est_vide():
self.adresses_precedentes.empiler(self.adresse_courante)
self.adresse_courante = self.adresses_suivantes.depiler()
def naviguer(self):
while True :
adresse = input(\"Adresse , < ou > :\")
if adresse == \"<\" :
self.retour()
elif adresse == \">\" :
self.retour_avant()
else :
self.aller_a(adresse)
print(\"Page :\",self.adresse_courante)
Pour éviter le problème du calcul de taille à l'exercice sur la pile, on propose de revisiter la classe Pile en lui ajoutant un attribut taille, indiquant à tout moment la taille de la pile.
Quelles méthodes doivent être modifiées, et comment?
Programme - La classe pile
class Pile:
\"\"\"structure de pite\"\"\"
def __init__(self):
self.contenu = None
def est_vide(self):
return self.contenu is None
def empiler(self, v):
self.contenu = Cellule(v, self.contenu)
def depiler(self):
if self.est_vide():
raise IndexError(\"depiler sur une pile vide\")
v = self.contenu.valeur
self.contenu = self.contenu.suivante
return v
def consulter(self):
if self.est_vide():
return \"La pile est vide\"
#raise IndexError(\"consulter sur une pile vide\")
return self.contenu.valeur
def vider(self):
self.contenu = None
def taille(self):
return self.longueur(self.contenu)
def longueur(self,liste) :
if liste is None :
return 0
elif liste.suivante is None :
return 1
else :
return 1 + self.longueur(liste.suivante)
Tester avec :
p = Pile()
p.empiler(1)
p.empiler(2)
print(p.consulter())
p.empiler(3)
p.empiler(4)
p.empiler(5)
p.empiler(6)
print(p.taille)
p.vider()
print(p.consulter())
print(p.taille)
Résultat :
2
6
La pile est vide
0
Mettre le résultat ici (code et figure).
On modifie le constructeur pour initialiser ce nouvel
attribut _taille à zéro, puis les deux opérations empiler et depiler pour que chacune mette à jour cet attribut en lui ajoutant ou retirant un.
Ainsi la valeur reste en permanence à jour
class Pile:
\"\"\"structure de pite\"\"\"
def __init__(self):
self.contenu = None
self.taille = 0
def est_vide(self):
return self.contenu is None
def empiler(self, v):
self.contenu = Cellule(v, self.contenu)
self.taille += 1
def depiler(self):
if self.est_vide():
raise IndexError(\"depiler sur une pile vide\")
v = self.contenu.valeur
self.contenu = self.contenu.suivante
self.taille -= 1
return v
def consulter(self):
if self.est_vide():
return \"La pile est vide\"
#raise IndexError(\"consulter sur une pile vide\")
return self.contenu.valeur
def vider(self):
self.contenu = None
self.taille = 0
On pourrait également modifier la définition de est_vide pour utiliser une comparaison entre taille et 0, mais cela n’apporterait rien de particulier.
Calculatrice polonaise inverse à pile L'écriture polonaise inverse des expressions arithmétiques place l'opérateur après ses opérandes.
Cette notation ne nécessite aucune parenthèse ni aucune règle de priorité.
Ains l'expression polonaise inverse décrite par la chaîne de caractères
'1 2 3 x + 4 x'
désigne l'expression traditionnellement notée
(1+2 x 3) x 4.
La valeur d'une telle expression peut être calculée facilement en utilisant une pile pour stocker les résultats intermédiaires.
Pour cela, on observe un à un les éléments de l'expression et on effectue les actions suivantes :
- si on voit un nombre, on le place sur la pile:
- si on voit un opérateur binaire, on récupère les deux nombres au sommet de la pile, on leur applique l'opérateur, et on replace le résultat sur la pile.
Si l'expression était bien écrite, il y a bien toujours deux nombres sur la pile lorsque l'on voit un opérateur, et à la fin du processus il reste exactement un nombre sur la pile, qui est le résultat.
Écrire une fonction prenant en paramètre une chaîne de caractères représentant une expression en notation polonaise inverse composée d'additions et de multiplications de nombres entiers et renvoyant la valeur de cette expression.
On supposera que les éléments de lexpression sont séparés par des espaces.
Attention : cette fonction ne doit pas renvoyer de résultat si l'expression est mal écrite.
Tester avec :
exp_polo = '1 2 3 x + 4 x'
res_calcul = eval_polonaise_inverse(exp_polo)
print(res_calcul)
Résultat :
28
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
On itère sur les éléments obtenus en découpant la
chaîne au niveau des espaces. On isole d’abord les cas des opérateurs qui
sont les plus faciles à identifier et on suppose que tout ce qui n’est pas \"+\"
où \"*' est un entier (cette branche échouera si on trouve encore autre chose
dans l’expression). À la fin, on dépile le dernier élément et on vérifie que la
pile est bien vide avant de renvoyer ce résultat. Si à un moment il n’était
pas possible de dépiler, le programme échoue de toute façon.
def eval_polonaise_inverse(s):
pile = Pile()
for e in s.split(\" \"):
if e == \"+\" or e == \"x\":
x = pile.depiler()
y = pile.depiler()
if e == \"+\" :
z=x+y
else :
z = x * y
pile.empiler (z)
else:
pile.empiler(int(e))
res = pile.depiler()
assert pile.est_vide()
return res
exp_polo = '1 2 3 x + 4 x'
res_calcul = eval_polonaise_inverse(exp_polo)
print(res_calcul)
Parenthèse associée
On dit qu'une chaîne de caractères comprenant, entre autres choses, des parenthèses ( et ) est bien parenthésée lorsque chaque parenthèse ouvrante est associée à une unique fermante, et réciproquement.
Écrire une fonction prenant en paramètres une chaîne bien parenthésée s , et qui renvoie l'indice de la parenthèse ouvrante associée.
Tester avec :
exp = \"(2*(2+4*(3+1)))\"
print(ouvrante_associee(exp))
exp = \"(2*(2+4*(3+1))\"
print(ouvrante_associee(exp))
exp = \"(2*(2+4*(3+1))))\"
print(ouvrante_associee(exp))
Résultat :
0
1
Index error
Mettre le résultat ici (code et figure).
La première parenthèse fermée est la dernière qui a été ouverte. On utilise donc une pile pour suivre les associations. En l’occurrence, notre pile va enregistrer les indices des parenthèses ouvrantes qui n’ont pas encore été associées à des parenthèses fermantes.
def ouvrante_associee(s):
pile = Pile()
for c in s:
if c == \"(\":
pile.empiler(\"(\")
elif c == \")\":
pile.depiler()
return pile.taille
Chaînes bien parenthésées
On considère une chaîne de carac-
tères incluant à la fois des parenthèses rondes ( et ) et des parenthèses
carrées [ et 1. La chaîne est bien parenthésée si chaque ouvrante est asso-
ciée à une unique fermante de même forme, et réciproquement.
Écrire une fonction prenant en paramètre une chaîne de caractères conte-
nant, entre autres, les parenthèses décrites et qui renvoie True si la chaîne
est bien parenthésée et False sinon.
Mettre le résultat ici (code et figure).
On utilise une pile pour stocker toutes les parenthèses ouvrantes qui n’ont pas encore trouvé de fermante associée. Chaque fermante étant censée être associée à la dernière ouvrante non encore associée, on vérifie à chaque fermentante rencontrée que la parenthèse ouvrante associé est la bonne forme.
On échoue si l’ouvrante associée n’a pas la bonne forme, ou s’il n’y a pas d’ouvrante associée, ou encore si la pile n’est pas vide à la fin du processus (ce qui signifierait qu’au moins une ouvrante n’a pas été fermée).
def bonnes_parentheses(s):
assoc = { \")\": \"(\" , \"]\": \"[\" }
pile = Pile()
for c in s :
if c == \"(\" or c == \"[\":
pile.empiler(c)
elif c == \")\" or c == \"]\":
if pile.est_vide() or pile.depiler() != assoc[c]:
return False
return pile.est_vide()
Pile bornée
Une pile bornée est une pile dotée à sa création d'une capacité maximale. On propose l'interface suivante :
| fonction | description |
| creer_pile(p). | crée et renvoie une pile bornée de capacité c |
| est_vide(p) | renvoie True si p est vide et False sinon |
| est_pleine(p) | renvoie True si la pile est pleine et False sinon |
| empiler(f, e) | ajoute e au sommet de p si p n'est pas pleine, et lève une exception IndexError sinon |
| depiler(f) | retire et renvoie l'élément au sommet de p si p n'est pas vide, et lève une exception IndexError sinon |
On propose de réaliser une telle pile bornée à l'aide d'un tableau dont la taille est fixée à la création et correspond à la capacité c.
Les éléments de la pile sont stockés consécutivement à partir de l'indice 0 (qui contient l'élément du fond de la pile).
On se donne également un entier enregistrant le nombre d'éléments dans la pile, qui permet donc également de désigner l'indice de la prochaine case libre.
Ainsi dans le schéma ci-dessous, les éléments sont ajoutés et retirés du côté droit de la pile.
0 nb
| |
| a | b | .... | z | None | ... | None |
Réaliser une telle structure à l'aide d'une classe ayant pour attributs le
tableau fixe et le nombre d'éléments dans la pile bornée.
Tester avec :
p = PileBornee(5)
print(p.est_vide())
p.empiler(1)
p.empiler(2)
p.empiler(3)
p.empiler(4)
p.empiler(5)
print(p.est_pleine())
print(p.depiler())
print(p.depiler())
print(p.est_vide())
print(p.est_pleine())
Résultat :
True
True
5
4
False
False
Mettre le résultat ici (code et figure).
À la création d’une pile bornée on définit son contenu comme un tableau de taille donnée par la capacité passée en paramètre, dont toutes cases contiennent None. La pile vide est caractérisée par un nombre d’éléments nb nul et la pile pleine par un nombre d'éléments égal à
la capacité.
class PileBornee:
\"\"\"pile à capacité bornée\"\"\"
def __init__(self, cap):
self.contenu = [None] * cap
self.nb = 0
def est_vide(self):
return self.nb == 0
def est_pleine(self):
return self.nb == len(self.contenu)
Les méthodes empiler et depiler vérifient l’une et l’autre qu’elles sont applicables, et mettent à jour le nombre d’éléments nb. Lorsque dépiler retire un élément, on a choisi de remplacer cet élément dans le tableau par
None.
La pile est aussi bien réalisée avec ou sans ce détail, puisque tous les éventuels éléments aux indices nb et suivants sont inaccessibles en utilisant
linterface de la pile. Cependant un élément présent dans le tableau, même
à un indice normalement inaccessible, ne pourrait plus être désalloué par le gestionnaire de mémoire. On évite donc en les supprimant d'éventuelles fuites de mémoire.
def empiler(self, v):
if self.est_pleine():
raise IndexError(\"empiler sur une pile pleine\")
self.contenu[self.nb] = v
self.nb += 1
def depiler(self):
if self.est_vide():
raise IndexError(\"depiler sur une pile vide\")
self.nb -= 1
v = self.contenu[self.nb]
self.contenu[self.nb] = None
return v
File bornée
Une file bornée est unc file dotée à sa création d'une capacité maximale.
On propose l'interface suivante.
| fonction | description |
| creer_file(f). | crée et renvoie une file bornée de capacité c |
| est_vide(f) | renvoie True si f est vide et False sinon |
| est_pleine(f) | renvoie True si la file est pleine et False sinon |
| ajouter(f, e) | ajoute e à l'arrière de f si f n'est pas pleine, et lève une exception IndexError sinon |
| retirer(f) | retire et renvoie l'élément à l'avant de f si f n'est pas vide, et lève une exception IndexError sinon |
Comme pour la pile bornée, on propose dc réaliser une telle file bornée à l'aide d'un tableau dont la taille est fixée à la création et correspond à la capacité.
Les éléments de la file sont stockés consécutivement à partir d'un indice premier correspondant à l'avant de la file, et le tableau est considéré comme circulaire :
après la dernière case, les éléments reviennent à la première.
Dans les schémas ci-dessous, un élément retiré l'est au niveau de l'indice premier, et un élément ajouté l'est à l'autre extrémité.
premier premier+nb
| |
| None | ... | None | a | b | .... | z | None | ... | None |
(premier+nb)%cap premier
| |
| k | l | .... | z | None | ... | None | a | .... | j |
Réaliser une telle structure à l'aide d'une classe ayant pour attributs le tableau fixe, le nombre d'éléments dans la file bornée et l'indice du premier élément.
Tester avec :
f = FileBornee(5)
print(f.est_vide())
f.ajouter(1)
f.ajouter(2)
f.ajouter(3)
f.ajouter(4)
f.ajouter(5)
print(f.est_pleine())
print(f.retirer())
print(f.retirer())
print(f.est_vide())
print(f.est_pleine())
Résultat:
True
True
1
2
False
False
Mettre le résultat ici (code et figure).
L'initialisation est comme celle des piles bornées, et ajoute un attribut premier a la valeur 0 :
à l’origine, les éléments sont placés au début du tableau.
class FileBornee:
\"\"\"UWfile à capacité bornée\"\"\"
def __init__(self, cap):
self.contenu = [None] * cap
self.premier = 0
self.nb = 0
# invariant O <= premier < len(contenu)
# invariant O <= nb <= len(contenu)
def est_vide(self):
return self.nb == 0
def est_pleine(self):
return self.nb == len(self.contenu)
Les éléments sont ajoutés à la fin de la file. L'opération incrémente nb.
def ajouter(self, v):
if self.est_pleine():
raise IndexError(\"ajouter sur une file pleine\")
i = (self.premier + self.nb) % len(self.contenu)
self.contenu[i] = v
self.nb += 1
def retirer(self):
if self.est_vide():
raise IndexError(\"retirer sur une file vide\")
v = self.contenu[self.premier]
self.contenu[self.premier] = None
self.nb -= 1
self.premier = (self.premier + 1) % len(self.contenu)
return v
On a pris soin d’écrire None à la place de v (pour ne pas conserver inutilement
un pointeur vers v à l’intérieur de la structure, ce qui empêcherait le GC de
Python de la récupérer lorsqu'elle ne sera plus accessible par ailleurs).
Dans cet exercice, on se propose d'évaluer le temps d'attente de clients à des guichets, en comparant la solution d'une unique file d'attente et la solution d'une file d'attente par guichet.
Pour cela, on modélise le temps par une variable globale, qui est incrémenté à chaque tour de boucle.
Lorsqu'un nouveau client arrive, il est placé dans une file sous la forme d'un entier égal à la valeur de l'horloge, c'est-à-dire égal à son heure d'arrivée.
Lorsqu'un client est servi, c'est-à-dire lorsqu'il sort de sa file d'attente, on obtient son temps d'attente en faisant la soustraction de la valeur courante de l'horloge et de la valeur qui vient d'être retirée de la file.
L'idée est de faire tourner une telle simulation relativement longtemps, tout en totalisant le nombre de clients servis et le temps d'attente cumulé sur tous les clients.
Le rapport de ces deux quantités nous donne le temps d'attente moyen. On peut alors comparer plusieurs stratégies (une ou plusieurs files, choix d'une file au hasard quand il y en à plusieurs, choix de la file où il y a le moins de clients, ete.).
On se donne un nombre N de guichets (par exemple, N=5). Pour simuler la disponibilité d'un guichet, on peut se donner un tableau d'entiers dispo de taille N.
La valeur de dispo[i] indique le nombre de tours d'horloge où le guichet i sera occupé.
En particulier, lorsque cette valeur vaut 0, cela veut dire que le guichet est libre et peut donc servir un nouveau client.
Lorsqu'un client est servi par le guichet à, on choisit un temps de traitement pour ce client, au hasard entre 0 et N, et on l'affecte à dispo[i].
À chaque tour d'horloge, on réalise deux opérations :
- on fait apparaître un nouveau client ;
- pour chaque guichet i,
- s'il est disponible, il sert un nouveau client (pris dans sa propre file ou dans l'unique file, selon le modèle}, le cas échéant ;
- sinon, on décrémente dispo[i].
Écrire un programme qui effectue une telle simulation, sur 100000 tours d'horloge, et affiche au final le temps d'attente moyen.
Comparer avec différentes stratégies.
Mettre le résultat ici (code et figure).
On se donne quelques variables globales :
from random import randint
ng = 5 # nb de guichets
tick = 0 # horloge
dispo = [0] * ng
unique = File()
total = 0 # temps d’attente total
servis = 0 # nb de clients servis
On suppose ici une unique file, réalisée ici avec le programme 27. Lorsqu'un
nouveau client arrive, on ajoute son heure d’arrivée dans la file.
def nouveau_client():
unique.ajouter(tick)
On définit une fonction servir pour que le guichet g serve un client.
def servir(g):
global total, servis
if not unique.est_vide():
t = unique.retirer()
total += tick - t
servis += 1
dispo[g] = randint(0, ng)
Enfin, le programme principal est constitué de la boucle suivante.
or __ in range(100000):
tick += 1
nouveau_client()
for g in range(ng):
if dispo[g] == 0:
servir(g)
else:
dispo[g] -= 1
print(total / servis)
Avec ce code, on obtient un temps d’attente moyen quasi nul (0,017). Mais
si on modélise maintenant une file par guichet, en modifiant les fonctions
nouveau_client et servir en conséquence, alors ce temps moyen passe à
1,92 si un nouveau client choisit systématiquement la file contenant le moins de clients et à 3.88 si un client choisit une file au hasard.
Compléter le programme ci-dessous du jeu de la bataille.
Vous aurez à gérer d'une part la valeur des cartes et d'autre part les cas d'égalités.
Indice : il faut créer une file égalité.
Le programme partiel du jeu de bataille :
from modFile import File
import random
paquet_alice = File()
paquet_basile = File()
#crée le jeu de 52 cartes
cartes = [i for i in range(0,52)]
#melange les cartes
random.shuffle(cartes)
#distribue les cartes aux 2 joueurs
for i in range(len(cartes)//2) :
paquet_alice.ajouter(cartes.pop())
paquet_basile.ajouter(cartes.pop())
#Gestion d'un tour de jeu
def tour():
global en_cours
if paquet_alice.est_vide():
print(\"Alice perd\")
en_cours = False
elif paquet_basile.est_vide():
print(\"Basile perd\")
en_cours = False
else :
tirer()
#Si la partie n'est pas terminée, tirage d'une carte
def tirer():
a = paquet_alice.retirer()
b = paquet_basile.retirer()
valeura = a%13
valeurb = b%13
print(\"Alice\",valeura,valeurb,\"Basile\")
#le programme ne gere pas l'égalité
if valeura > valeurb :
paquet_alice.ajouter(a)
paquet_alice.ajouter(b)
elif valeura < valeurb :
paquet_basile.ajouter(b)
paquet_basile.ajouter(a)
#démarrage du jeu
en_cours = True
nb_tours = 0
while en_cours :#not paquet_alice.est_vide() and not paquet_basile.est_vide() :
tour()
nb_tours+=1
print(\"Partie en \",nb_tours,\" tours\")
Importer le module modFile.py :
https://sciencesappliquees.com/images/nsi/modFile.py
et tester le jeu de carte de la bataille.
Une fois terminé les modifications, vous transformerez le programme bataille en classe Bataille avec toutes les fonctions encapsulé dans cette-ci.
Mettre le résultat ici (code et figure).
def affiche(valeur) :
couleur = [\"Ca\",\"Pi\",\"Co\",\"Tr\"]
numero = [\"2\",\"3\",\"4\",\"5\",\"6\",\"7\",\"8\",\"9\",\"10\",\"Va\",\"Da\",\"Ro\",\"1\"]
return (couleur[valeur//13],numero[valeur%13])
Le programme de la bataille modifié :
from modFile import File
import random
paquet_alice = File()
paquet_basile = File()
paquet_egalite = File()
#crée le jeu de 52 cartes
cartes = [i for i in range(0,52)]
#melange les cartes
random.shuffle(cartes)
#distribue les cartes aux 2 joueurs
for i in range(len(cartes)//2) :
paquet_alice.ajouter(cartes.pop())
paquet_basile.ajouter(cartes.pop())
#Gestion d'un tour de jeu
def tour():
global en_cours
if paquet_alice.est_vide():
print(\"Alice perd\")
en_cours = False
elif paquet_basile.est_vide():
print(\"Basile perd\")
en_cours = False
else :
tirer()
def affiche(valeur) :
couleur = [\"Ca\",\"Pi\",\"Co\",\"Tr\"]
numero = [\"2\",\"3\",\"4\",\"5\",\"6\",\"7\",\"8\",\"9\",\"10\",\"Va\",\"Da\",\"Ro\",\"1\"]
return (couleur[valeur//13],numero[valeur%13])
def tirer():
a = paquet_alice.retirer()
b = paquet_basile.retirer()
valeura = a%13
valeurb = b%13
print(\"Alice\",affiche(a),affiche(b),\"Basile\")
#le programme ne gere pas l'égalité
if valeura > valeurb :
paquet_alice.ajouter(a)
paquet_alice.ajouter(b)
while not paquet_egalite.est_vide() :
paquet_alice.ajouter(paquet_egalite.retirer())
elif valeura < valeurb :
paquet_basile.ajouter(b)
paquet_basile.ajouter(a)
while not paquet_egalite.est_vide() :
paquet_alice.ajouter(paquet_egalite.retirer())
else : #gerer l'egalité
print(\"Egalité\")
paquet_egalite.ajouter(b)
paquet_egalite.ajouter(a)
#carte à l'envers
if not paquet_alice.est_vide() :
paquet_egalite.ajouter(paquet_alice.retirer())
if not paquet_basile.est_vide() :
paquet_egalite.ajouter(paquet_basile.retirer())
#démarrage du jeu
en_cours = True
nb_tours = 0
while en_cours :#not paquet_alice.est_vide() and not paquet_basile.est_vide() :
tour()
nb_tours+=1
print(\"Partie en \",nb_tours,\" tours\")
- Détails
- Écrit par : Richard GAUTHIER
- Clics : 1867