[[{"text":"
","title":"Diviser pour régner","tagtitle":"h1"},{"edit":"
"}],[{"text":"
","title":"Retour sur la recherche dichotomique","tagtitle":"h1"},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":"Tri fusion","tagtitle":"h1"},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":"Conclusion","tagtitle":"h1"},{"edit":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice","tagtitle":"h1"},{"edit":"
"},{"solution":"
"}],[{"text":"![](\"https://sciencesappliquees.com/images/nsi/diviser1.png\")
","title":"Exercice","tagtitle":"h1"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice","tagtitle":"h1"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice","tagtitle":"h1"},{"edit":"
"},{"solution":"
"}],[{"text":"
![](\"https://sciencesappliquees.com/images/nsi/diviser2.png\")
![](\"https://sciencesappliquees.com/images/nsi/diviser3.png\")
![](\"https://sciencesappliquees.com/images/nsi/image1.png\")
![](\"https://sciencesappliquees.com/images/nsi/rotation.png\")
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}]]
Alice se décide à ranger ses bandes dessinées par ordre alphabétique de titre.
Le travail est fastidieux car elle en possède une bonne centaine.
Elle appelle son frère Basile à la rescousse. Ils se partagent les bandes dessinées et chacun d'eux trie sa moitié, sous la forme d'une pile de bande dessinées.
Ensuite, les bandes dessinées sont rangées dans la bibliothèque en fusionnant les deux piles, c'est-à-dire en prenant à chaque fois celle des deux bandes dessinées au sommet des deux piles qui vient avant l'autre dans l'ordre alphabétique.
Si la fratrie est plus grande, on peut même imaginer décomposer le travail plus encore.
Ainsi, la pile d'Alice ou de Basile pourrait être triée en étant elle-même décomposée.
Dans un contexte informatique, cette façon de procéder suggère que plusieurs ordinateurs ou plusieurs programmes pourraient collaborer pour effectuer une tâche telle qu'un tri.
C'est effectivement le cas. Mais d'une façon très surprenante, il s'avère que même un unique programme peut tirer avantage à ainsi décomposer un problème en sous-problèmes plus petits, ou plus
simples, qu'il va lui-même résoudre successivement.
Ainsi, même si Alice est seule pour trier ses bandes dessinées, elle peut tout à fait partager les bandes dessinées en deux tas égaux, les trier puis les fusionner.
Et pour trier chacun des deux tas, elle peut recommencer ainsi avec la même idée, jusqu'à ce que chaque tas soit suffisamment petit pour pouvoir être trié sans effort.
Alice vient ainsi d'inventer le tri fusion, une méthode extrêmement efficace pour trier.
C'est là une instance du principe «diviser pour régner».
D'une manière générale, ce principe consiste à décomposer un problème à résoudre en sous-problèmes, plus petits, puis à les résoudre, éventuellement en appliquant le même principe autant de fois que nécessaire, puis enfin à combiner les résultats des sous-problèmes pour en déduire le résultat du
problème initial.
L'idée de se ramener à la résolution de sous-problèmes plus petits a déjà été explorée dans la séquence consacré à la récursivité.
En effet, quand on calcule la factorielle de n récursivement, on se ramène au calcul de la factorielle de n — 1, un problème identique mais «plus petit».
De même, le principe «diviser pour régner» invite à penser la solution
d'un problème récursivement.
Cependant, les sous-problèmes «plus petits» traités récursivement seront généralement plus nombreux ou nettement plus petits.
Dans cette séquence, nous détaillons deux exemples d'application du principe «diviser pour régner».
La première application est la recherche dichotomique dans un tableau trié, déjà étudiée en classe de première, mais reformulée ici à l'aide de récursion.
La seconde application est celle du tri fusion, suggérée ci-dessus avec l'exemple des bandes dessinées.
Les exercices proposés contiennent d'autres applications, dont un algorithme pour effectuer la rotation d'une image de 90 degrés.
On rappelle qu'il s'agit de déterminer si un entier v apparaît dans un tableau t, ce dernier étant supposé trié par ordre croissant.
Plus précisément, on cherche à écrire une fonction qui renvoie un indice où la valeur v apparaît dans t, en choisissant arbitrairement s'il y a plusieurs réponses possibles, et None si la valeur v n'apparaît pas dans t.
L'idée principale de la recherche dichotomique consiste à délimiter une portion du tableau dans laquelle la valeur v peut encore se trouver, avec deux indices g et d.
On peut illustrer ainsi la situation à chaque étape:
0 g. d
t
| éléments < v | ... | éléments > v |
On compare alors la valeur au centre de cet intervalle avec la valeur v et, selon le cas, on signale qu'on a trouvé la valeur v ou on se déplace vers la moitié gauche ou la moitié droite.
Il s'agit bien là d'une instance de l'idée «diviser pour régner», car on réduit le problème de la recherche dans
l'intervalle g ... d à celui de la recherche dans un intervalle plus petit.
Dans le programme de première, nous avions écrit la recherche dichotomique sous la forme d'une boucle while, en modifiant la valeur de g ou de d à chaque étape.
Cette fois, nous allons l'écrire sous la forme d'une fonction récursive, ce qui illustre encore mieux le principe «diviser pour régner».
En effet, l'appel récursif va directement exprimer la résolution d'un problème identique mais nlus petit.
Nous écrivons done une fonction récursive qui prend quatre arguments:
- le tableau,
- la valeur recherchée
- et les deux indices délimitant la portion dans laquelle se fait la recherche:
def recherche(t, v, g, d):
On commence par traiter le cas d'un intervalle qui ne contient aucune valeur, c'est-à-dire lorsque la borne gauche g est plus grande que la borne droite d.
Dans ce cas, on renvoie None pour signaler l'échec de la recherche.
if g > d:
return None
Si l'intervalle n'est pas vide, on calcule la position centrale de cet intervalle, en faisant la moyenne de g et d.
Ensuite, on compare la valeur v à la valeur t[m].
Si elle est plus grande, cela veut dire qu'il faut poursuivre la recherche dans la moitié droite, délimitée par les indices m+1 et d.
On rappelle donc récursivement la fonction recherche sur cet intervalle.
if tm] < v:
return recherche(t, v, m + 1, d)
Attention à ne pas oublier le return devant l'appel à recherche, car il s'agit de renvoyer le résultat de l'appel récursif.
C'est justement là qu'on exprime l'idée que la solution de notre problème est ramenée à la solution d'un problème plus petit.
D'une façon symétrique, on rappelle récursivement la fonction sur la moitié gauche de l'intervalle, délimitée par les indices g et m-1, si la valeur v est plus petite que la valeur t[m]:
elif t[ml > v:
return recherche(t, v, g, m - 1)
Enfin, il ne reste que le cas où la valeur v vient d'être trouvée à la position m que l'on renvoie alors.
else:
return m
Le programme complet de la recherche dichotomique s'en déduit en appelant la fonction recherche sur l'intégralité du tableau.
def recherche _dichotomique(t, v):
return recherche(t, v, 0, len(t) - 1)
Le code complet est le suivant:
Programme — Recherche dichotomique dans un tableau trié
def recherche(t, v, g, d):
\"\"\"renvoie une position de v dans t[g..d],
supposé trié, et None si elle ne s'y trouve pas\"\"\"
if g > d:
return None
m = (g + d) // 2
if t[m] < v:
return recherche(t, v, m + 1, d)
elif t[m] > v:
return recherche(t, v, g, m - 1)
else:
return m
def recherche_dichotomique(t, v):
\"\"\"renvoie une position de v dans le tableau t,
supposé trié, et None si elle ne s'y trouve pas\"\"\"
return recherche(t, v, 0, len(t) - 1)
Tester le cpde avec les instructions suivantes:
t1 = [randint(0,10000) for _ in range(10000)]
t1.sort()
v1 = randint(0,10000)
print(recherche_dichotomique(t1,v1))
Mettre le résultat ici (code et figure).
Correction et efficacité
Il est important de se persuader que ce programme ce termine toujours.
L'argument n'est pas différent de celui utilisé en première avec la boucle while:
la quantité d - g est un variant de notre fonction récursive. En effet, il s'agit d'une quantité entière qui décroît strictement à chaque appel récursif, tout en restant positive ou nulle.
On peut également se persuader qu'il n'y a pas de risque d'obtenir l'erreur RecursionError à cause d'un trop grand nombre d'appels récursifs. En effet, la taille de l'intervalle étant divisée par deux à chaque étape, il faudrait un tableau de plus de 21000 éléments pour que la fonction recherche soit appelée récursivement plus de 1000 fois. Or, la mémoire d'un ordinateur n'autorise aujourd'hui que des tableaux de quelques
milliards d'éléments, c'est-à-dire de l'ordre de 230. Il n'y a donc aucun risque de provoquer l'erreur RecursionError.
Mettre le résultat ici (code et figure).
Supposons que l'on veuille trier une liste chaînée contenant des entiers par ordre croissant. Plus précisément, on cherche à écrire une fonction qui reçoit en argument une liste chaînée et renvoie une nouvelle liste contenant les mêmes éléments mais triés par ordre croissant.
On pourrait tout à fait utiliser le tri par sélection ou le tri par insertion vus
au programme de première.
Cependant, le principe «diviser pour régner» peut être avantageusement utilisé pour concevoir un algorithme de tri plus efficace encore, appelé tri fusion.
L'idée a été évoquée dans l'introduction.
Elle consiste à séparer les éléments de la liste en deux listes de même taille, à un élément près.
Ensuite, on trie chacune des deux listes avec le tri fusion, récursivement.
Enfin, on fusionne les deux listes triées, ce qui est facile car il suffit d'examiner uniquement le premier élément de chaque liste.
Il s'agit bien là d'une application du principe «diviser pour régner» car on ramène le problème du tri d'une liste aux sous-problèmes du tri de deux listes plus petites, jusqu'à parvenir à des listes d'au plus un élément, pour lesquelles il n'y a rien à faire.
Le code Python qui traduit cette idée est le suivant:
def tri_fusion(lst):
if 1st is None or lst.suivante is None:
return lst
l1, l2 = coupe(lst)
return fusion(tri_fusion(l1), tri_fusion(l2))
Bien entendu, il reste à réaliser les fonctions coupe et fusion mais le principe «diviser pour régner» est capturé entièrement par la fonction tri fusion et c'est pour cela que nous la donnons tout de suite.
Écrivons maintenant la fonction coupe qui sépare les éléments d'une liste donnée dans deux listes de même taille, à un près, qui sont renvoyées sous la forme d'un couple de listes.
Il y a plusieurs façons de procéder. On pourrait par exemple commencer par calculer la longueur n de la liste, puis mettre les n/2 premiers éléments dans la première liste et le reste dans la seconde.
Üne autre solution consiste à considérer les éléments deux par deux, en en mettant un dans chaque liste.
Pour éviter de faire un cas particulier pour un éventuel dernier élément, dans le cas d'un nombre impair d'éléments, on peut adopter une troisième approche:
on considère les éléments un par un, en les mettant alternativement dans la première et dans la seconde liste,
Une façon élégante de réaliser cela consiste à échanger à chaque étape le rôle des deux listes. C'est cette dernière approche que nous adoptons.
Le code de la fonction coupe est donné dans le programme ci-dessous.
Enfin, il nous reste à écrire la fonction fusion qui reçoit deux listes triées en arguments et renvoie une liste triée contenant les éléments de ces deux listes.
Nous allons l'écrire comme une fonction récursive, car c'est là le plus simple.
La fonction fusion reçoit en argument deux listes l1 et l2, supposées triées par ordre croissant.
def fusion(l1, l2):
Elle doit renvoyer une liste contenant les mêmes éléments que l1 et l2, triée par ordre croissant.
On commence par le cas où l'une des deux listes est vide => il suffit alors de renvoyer l'autre.
if l1 is None:
return l2
if l2 is None:
return l1
Sinon, cela veut dire que les deux listes sont non vides.
On peut donc sans risque examiner maintenant le premier élément de chaque liste.
Le plus petit des deux sera le premier élément du résultat, car les deux listes sont triées.
On compare donc les deux éléments l1.valeur et l2.valeur.
Si le plus petit provient de la première liste, on le place en tête du résultat et le reste de la liste est construit en fusionnant récursivement le reste de l1 avec l2.
if l1.valeur <= l2.valeur:
return Cellule(l1.valeur, fusion(l1.suivante, l2))
Dans le cas contraire, c'est l'inverse:
le premier élément de l2 est placé en tête du résultat et le reste de la liste est construit en fusionnant l1 avec le reste de l2.
else:
return Cellule(l2.valeur, fusion(l1, l2.suivante))
Ceci achève le code de la fonction fusion.
Le code complet du tri fusion est le suivant:
Programme — Tri fusion d'une liste chaînée
def coupe(lst):
\"\"\"sépare une liste en deux listes ayant le même nombre
d'éléménts, à un près\"\"\"
l1, l2 = None, None
while lst is not None:
l1, l2 = Cellule(lst.valeur, l2), l1
lst = lst.suivante
return l1, l2
def fusion(l1, l2):
\"\"\"fusionne deux listes triées\"\"\"
if l1 is None:
return l2
if l2 is None:
return l1
if l1.valeur <= l2.valeur:
return Cellule(l1.valeur, fusion(l1.suivante, l2))
else:
return Cellule(l2.valeur, fusion(l1, l2.suivante))
def tri_fusion(lst):
\"\"\"trie une liste avec le tri fusion\"\"\"
if lst is None or lst.suivante is None:
return lst
l1, l2 = coupe(lst)
return fusion(tri_fusion(l1), tri_fusion(l2))
Tester avec:
def creer_lst_hasard(n,maxhasard):
\"\"\"Creer une liste chainée de nombres aux hasards\"\"\"
lst = None
while n>0 :
lst = Cellule(randint(0,maxhasard),lst)
n -= 1
return lst
def affiche_lst(lst):
\"\"\"affiche le contenue d'une liste chainée\"\"\"
print(lst.valeur,end=\" \")
c = lst.suivante
while c.suivante is not None:
print(c.valeur,end=\" \")
c = c.suivante
print()
#Création de la liste chainée
lst1 = creer_lst_hasard(500,5000)
affiche_lst(lst1)
#Tri de la liste
lst2 = tri_fusion(lst1)
affiche_lst(lst2)
Tester avec 1000 éléments dans la liste lst1 et conclure.
Mettre le résultat ici (code et figure).
Limites de la récursion
Si on cherche à trier une liste de plus de mille éléments avec notre fonction
tri_fusion, on obtient l'erreur RecursionError, qui signifie qu'on a fait un trop grand nombre d'appels récursifs imbriqués.
Plus précisément, c'est la fonction fusion qui est responsable de cette erreur.
Une solution consiste à augmenter le nombre maximal d'appels, avec setrecursionlimit. Une autre solution consiste À réécrire la fonc-
tion fusion avec une boucle while, ce que propose lexercice 112. C'est
cependant un peu plus délicat à écrire que la version récursive.
La fonction tri_fusion, bien que récursive, ne conduira en revanche
jamais à l'erreur RecursionError. En effet, la taille de la liste étant divisée par deux à chaque fois, il faudrait une liste de plus de 21000 éléments pour conduire à une erreur.
La mémoire de notre machine ne nous permet pas de construire une liste aussi grande.
Et quand bien même nous le pourrions, le tout premier appel à la fonction coupe ne termincrait pas avant très longtemps.
Mettre le résultat ici (code et figure).
Efficacité
Il est intéressant de se demander si le tri fusion constitue une bonne méthode de tri. En particulier, on peut chercher à le comparer aux tris par sélection et par insertion du programme de première.
Par exemple. nous avions observé que le tri par sélection nous permettait de trier 16 000 valeurs en un peu moins de 7 secondes (sur notre machine).
Avec notre tri fusion, il ne faut que 0,28 secondes pour trier autant de valeurs.
Plus généralement, voici un tableau comparatif, à gauche, et un tracé des performances du tri fusion, à droite.
| taille | sélection | fusion |
| 1000 | 0,06s | 0,01s |
| 2000 | ||
| 4000 | ||
| 8000 | ||
| 16000 | ||
| 32000 | ||
| 64000 |
Comme on le constate, la courbe n'est pas tout à fait linéaire.
Néanmoins, les performances sont bien meilleures qu'avec le tri par sélection et il en serait de même si l'on comparait avec le tri par insertion.
Pour être précis, rappelons que, dans le pire des cas, les tris par sélection
et par insertion peuvent prendre un temps quadratique, c'est-à-dire proportionnel à N2 où N désigne le nombre d'éléments à trier.
Ainsi, chaque fois que le nombre d'éléments à trier double, le temps est multiplié par quatre.
Le tri fusion, en revanche, demande un temps qui est proportionnel à N.log2N, où
log2 désigne la fonction logarithme.
Le logarithme est une fonction qui croît
relativement lentement.
Ainsi, log2(1030) < 30.
Ccla veut dire que lorsque le nombre d'éléments à trier double, le coût du tri fusion fait un peu plus que doubler, mais pas beaucoup plus.
On peut l'observer empiriquement dans le tableau ci-dessus.
Pour être complet, mentionnons qu'une telle complexité en N.log2N est optimale pour le problème du tri par comparaison.
En effet, la théorie nous dit que, dès lors qu'on ne connaît rien quant aux valeurs à trier, notamment leur distribution, et qu'on peut seulement les comparer deux à deux, alors il faut au moins N.log2N comparaisons, dans le pire des cas, pour trier N valeurs, et donc un temps au moins proportionnel à N.log2N.
Le tri fusion est donc optimal.
Mettre le résultat ici (code et figure).
Remarque : Trier un tableau
Il est possible d'utiliser le tri fusion pour trier un tableau.
Cependant, c'est assez délicat à mettre en œuvre, car réaliser la fusion en place dans le tableau est extrêmement difficile.
Du coup, on utilise un second tableau comme espace de travail temporaire pour
réaliser la fusion et le code s'en trouve tout de suite un peu compliqué.
Il existe un autre algorithme de tri mettant en œuvre le principe «diviser
pour régner» qui s'adapte mieux au cas d'un tableau.
Il s'agit du tri rapide. H consiste à choisir une valeur arbitraire apparaissant dans le tableau et s'en servir comme “pivot”, c'est-à-dire déplacer les éléments dans le tableau pour mettre à gauche les éléments plus petits que le pivot et à droite les éléments plus grands que le pivot, et enfin à trier récursivement les deux moitiés.
Il reste cependant difficile à mettre en
œuvre efficacement. Le tri rapide n'est pas au programme de terminale.
Le principe «diviser pour régner» consiste à décomposer un problème en un ou plusieurs sous-problèmes de même nature, mais plus petits:
- résoudre ces sous-problèmes, éventuellement en les décomposant à leur tour récursivement en problèmes plus petits encore;
- déduire des solutions des sous-problèmes la solution du problème initial.
Le tri fusion est un algorithme de tri efficace qui met en œuvre la technique «diviser pour régner».
Mettre le résultat ici (code et figure).
Donner la séquence des appels à la fonction recherche pendant l'évaluation des deux appels suivants :
recherche_dichotomique([0,1,1,2,3,5,8,13,21], 13)
recherche_dichotomique([0,1,1,2,8,5,8,13,21], 12)
Mettre le résultat ici (code et figure).
recherche(t, 13, O0, 8)
recherche(t, 13, 5, 8)
recherche(t, 13, 7, 8)
À ce moment-là, on obtient m = 7, position à laquelle on trouve la valeur 13.
recherche(t, 12, O0, 8)
recherche(t, 12, 5, 8)
recherche(t, 12, 7, 8)
recherche(t, 12, 7, 6)
À ce moment-là, on a g > d et la recherche termine avec le résultat None.
Quelles sont les deux listes renvoyées par la fonction coupe() lorsqu'on lui passe la liste 8 1 3 0 1 2 5?
L'ordre relatif des éléments est-il préservé?
Est-ce important?
","title":"Exercice","tagtitle":"h1"},{"edit":"Mettre le résultat ici (code et figure).
La première liste est 5 1 3 8
et la seconde 2 0 1.
On constate que l’ordre relatif est inversé, car les premiers éléments de la
liste l sont ajoutés en premier dans les deux listes l1 et l2.
Ce n’est pas important, car les deux listes vont être triées avant d’être fusionnées.
Réécrire La fonction fusion à l'aide d'une boucle while plutôt que comme une fonction récursive.
Indication : Construire le résultat en
ordre décroissant, puis le renverser avec une seconde boucle while.
Tester avec:
def creer_lst_hasard(n,maxhasard):
\"\"\"Creer une liste chainée de nombres aux hasards\"\"\"
lst = None
while n>0 :
lst = Cellule(randint(0,maxhasard),lst)
n -= 1
return lst
def affiche_lst(lst):
\"\"\"affiche le contenue d'une liste chainée\"\"\"
print(lst.valeur,end=\" \")
c = lst.suivante
while c.suivante is not None:
print(c.valeur,end=\" \")
c = c.suivante
print()
#Création de la liste chainée
lst1 = lsthasard(1000,5000)
affiche_lst(lst1)
#Tri de la liste
lst2 = tri_fusion(lst1)
affiche_lst(lst2)
Mettre le résultat ici (code et figure).
def coupe(lst):
\"\"\"sépare une liste en deux listes ayant le même nombre
d'éléménts, à un près\"\"\"
l1, l2 = None, None
while lst is not None:
l1, l2 = Cellule(lst.valeur, l2), l1
lst = lst.suivante
return l1, l2
def fusion(l1, l2):
lst = None
while l1 is not None or l2 is not None:
if l1 is not None and \\
(l2 is None or l1.valeur <= l2.valeur):
lst, l1 = Cellule(l1.valeur, lst), l1.suivante
else:
lst, l2 = Cellule(l2.valeur, lst), l2.suivante
# puis on renverse lst
r = None
while lst is not None:
r, lst = Cellule(lst.valeur, r), lst.suivante
return r
def tri_fusion(lst):
\"\"\"trie une liste avec le tri fusion\"\"\"
if lst is None or lst.suivante is None:
return lst
l1, l2 = coupe(lst)
return fusion(tri_fusion(l1), tri_fusion(l2))
Le problème des tours de Hanoï est un jeu célèbre constitué de trois tiges verticales sur lesquelles sont empilés des disques de diamètres différents.
Il s'agit de déplacer tous les disques de la première tige (dessin de gauche) vers la dernière tige (dessin de droite) en respectant deux contraintes:
- d'une part, on ne peut déplacer qu'un seul disque à la fois;
- d'autre part, on ne peut pas poser un disque sur un disque de diamètre plus petit.
Sur l'exemple ci-dessus, avec quatre disques, il ne faut pas moins de 15 déplacements pour y parvenir.
Écrire une fonction hanoiï(n) qui affiche la solution du problème des tours de Hanoï pour n disques, sous la forme de déplacements élémentaires désignant les trois tiges par les entiers 1, 2 et 3, de la manière suivante:
déplace de 1 vers 3
déplace de 1 vers 2
Indication: Commencer par une fonction récursive deplace(a, b, c, k) qui résout le problème plus général du déplacement de k disques de la tige a vers la tige b en se servant de la tige c comme stockage intermédiaire.
Tester avec:
hanoi(4)
Résultat:
déplace de 1 vers 2
déplace de 1 vers 3
déplace de 2 vers 3
déplace de 1 vers 2
déplace de 3 vers 1
déplace de 3 vers 2
déplace de 1 vers 2
déplace de 1 vers 3
déplace de 2 vers 3
déplace de 2 vers 1
déplace de 3 vers 1
déplace de 2 vers 3
déplace de 1 vers 2
déplace de 1 vers 3
déplace de 2 vers 3
Mettre le résultat ici (code et figure).
On suit l'indication. Il n’est pas nécessaire de faire un cas particulier pour k = 1, c’est-à-dire un seul disque.
Il suffit de ne rien faire lorsque k = 0.
def deplace(a, b, c, k):
\"\"\"déplace k disques de La tour a vers la tour b,
en se servant de la tour c comme intermédiaire\"\"\"
if k > 0:
deplace(a, c, b, k - 1)
print(\"déplace de\", a, \"vers\", b)
deplace(c, b, a, k - 1)
#La solution s’en déduit facilement :
def hanoi(n):
deplace(1, 3, 2, n)
Dans le problème des tours de Hanoï (exercice précédent), combien faut-il de déplacements élémentaires au total pour déplacer les N disques de la tour de départ à la tour d'arrivée?
Indication : Regarder les 3 vidéos pour vous aider.
Mettre le résultat ici (code et figure).
Pour déplacer 1 disque, il suffit d’un seul mouvement.
Pour déplacer 2 disques, il faut 1 + 1 + 1 = 3 déplacements.
Pour déplacer 3 disques, il faut 3 + 1 + 3 = 7 déplacements (on en déplace deux,
puis le grand, puis on en déplace deux de nouveau).
En continuant ainsi, on trouve ensuite les valeurs 15, 31, 63, ...,
c’est-à-dire les nombres de la forme :
2N - 1.
On peut le prouver à l’aide d’une récurrence.
En effet, c’est bien le cas pour N = 1, car 21 - 1 = 1 et s’il faut 2N-1 - 1 déplacements pour N — 1 tours, alors on aura au total (2N-1 -1)+ 1 +(2N-1 -1) = 2N - 1 déplacements pour N tours.
Reprendre l'exercice sur les tours de Hanoï en utilisant trois piles, chacune contenant des entiers qui représentent les tailles des disques que cette pile contient.
Mettre le résultat ici (code et figure).
Les trois arguments a, b, c ne sont plus des entiers mais des piles. Dans le code de la fonction deplace, il suffit de remplacer la ligne
print (\"déplace de\", a, \"vers\", b)
par la ligne
b.empiler(a.depiler())
Dans le code de la fonction hanoi, il faut construire les trois piles, la première contenant les n disques.
def deplace2(a, b, c, k, posi):
\"\"\"déplace k disques de La tour a vers la tour b,
en se servant de la tour c comme intermédiaire\"\"\"
if k > 0:
deplace2(a, c, b, k - 1,[posi[0],posi[2],posi[1]])
b.empiler(a.depiler())
#affichage contenu pile
for i in range(3):
if posi[i] == 0 :
tab = afficher_pile(a)
print(tab)
elif posi[i] == 1 :
tab = afficher_pile(b)
print(tab)
else :
tab = afficher_pile(c)
print(tab)
print()
deplace2(c, b, a, k - 1,[posi[2],posi[1],posi[0]])
def hanoi2(n):
a = Pile()
for i in range(1,n+1):
a.empiler(i)
print(afficher_pile(a))
deplace2(a, Pile(), Pile(), n,[0,1,2])
def afficher_pile(pile:Pile):
if pile.contenu is None:
return []
tab = [pile.contenu.valeur]
c = pile.contenu.suivante
while c is not None:
tab.append(c.valeur)
c = c.suivante
return tab
On a pris soin d’empiler les diamètres en partant du plus grand. Suggestion :
ajouter un affichage du contenu des trois piles après chaque déplacement.
Dans cet exercice, on cherche à écrire une fonction qui effectue la rotation d'une image de 90 degrés en utilisant le principe «diviser pour régner».
Pour manipuler une image en Python, on peut utiliser par exemple la bibliothèque PIL (Python Image Library) et plus précisément son module Image.
Avec les quatre lignes suivantes:
from PIL import Image
im = Jmage.open(\"image.png\")
largeur, hauteur = im.size
px = im.load()
on charge l'image contenue dans le fichier image.png, on obtient ses dimensions dans les variables largeur et hauteur, et la variable px est la matrice
des pixels constituant l'image.
Pour 0 < x < largeur et 0 < y < hauteur, la couleur du pixel (x, y) est donnée par px[x, y].
Une couleur est un triplet donnant les composantes rouge, vert et bleu, sous la forme d'entiers entre 0 et 255.
On peut modifier la couleur d'un pixel avec une affectation de la forme px[x,y]=c où c est une couleur.
Dans cet exercice, on suppose que l'image est carrée et que sa dimension est une puissance de deux, par exemple 256 x 256.
Notre idée consiste à découper l'image en quatre, à effectuer la rotation de 90 degrés de chacun des quatre morceaux, puis à les déplacer vers leur position finale.
On peut illustrer les deux étapes ainsi:
Afin de pouvoir procéder récursivement, on va définir une fonction rotation_aux(px, x, y, t) qui effectue la rotation de la portion carrée
de l'image comprise entre les pixels (x,y) et (x+t,y+t).
Cette fonction ne renvoie rien. Elle modifie le tableau px pour effectuer la rotation de cette portion de l'image, au même endroit.
On suppose que t est une puissance de 2.
Écrire le code de la fonction rotation_aux.
En déduire une fonction rotation(px, taille) qui effectue une rotation de l'image toute entière, sa dimension étant donnée par le paramètre taille.
Une fois la rotation effectuée, on pourra sauvegarder le résultat dans un autre fichier avec la commande im.save(\"rotation.png\").
Tester avec:
from PIL import Image
im = Image.open(\"image1.png\")
largeur, hauteur = im.size
px = im.load()
rotation(px, largeur)
im.save(\"rotation.png\")
et l'image suivante (Clique droit enregistrer sous):
Résultat en ouvrant rotation.png:
Mettre le résultat ici (code et figure).
On commence par traiter le cas d’une région réduite
à un unique pixel. Dans ce cas, il n’y a strictement rien à faire :
def rotation_aux(px, x0, y0, t):
if t == 1:
return
#Sinon, on peut découper la région en quatre sous-régions, de dimension deux
#fois plus petite, dont on effectue la rotation récursivement :
t //=2
rotation_aux(px, x0 , y0 , t)
rotation_aux(px, x0+t , y0 , t)
rotation_aux(px, x0 , y0+t , t)
rotation_aux(px, x0+t , y0+t , t)
#Il faut ensuite déplacer chacune des quatre régions, ce que l’on peut faire
#élégamment avec une double boucle et une affectation simultanée des quatre
#pixels qui échangent leur position :
for x in range(x0, x0+t):
for y in range(y0, y0+t):
px[x,y+t],px[x+t,y+t],px[x+t,y],px[x,y] \\
= px[x,y], px[x,y+t], px[x+t,y+t], px[x+t,y]
La rotation de l’image toute entière est obtenue avec une région qui couvre
toute l’image:
def rotation(px, taille):
rotation_aux(px, 0, 0, taille)
Dans cet exercice, on se propose d'appliquer le principe «diviser pour régner» pour multiplier deux entiers, avec la méthode de Karatsuba.
Le principe est le suivant. Supposons deux entiers x et y ayant chacun 2n chiffres en base 2.
On peut les écrire sous la forme
x = a2n+b
y = c2n+d
avec 0 < a,b,c,d < 2n, c'est-à-dire avec quatre entiers a, b, c, d qui s'écrivent
chacun sur n chiffres en base 2.
Dès lors, on peut calculer le produit de x et y de la façon suivante:
xy = (a2n + b)(c2n + d)
= ac22n + (ad + bc)2n + bd
= ac2n + (ac + bd — (a — b)(c — d))2n + bd
Cette dernière forme, d'apparence inutilement compliquée, fait apparaître
seulement trois produits, à savoir ac, bd et (a — b}(c — d).
Ainsi, on a ramené la multiplication de deux entiers de 2n chiffres à trois multiplications d'entiers de n chiffres.
Pour faire chacune de ces trois multiplications, on peut appliquer le même principe, et ainsi de suite jusqu'à obtenir de petits entiers dont la multiplication est immédiate.
Au final, cela permet d'effectuer la multiplication en un temps proportionnel à n1,58 (environ) au lieu de n2, ce qui est un gain significatif lorsque le nombre de chiffres n est grand.
1. Écrire une fonction taille(x) qui renvoie le nombre de chiffres de l'entier x lorsqu'il est écrit en base 2.
2. Écrire une fonction karatsuba(x, y, n) qui calcule le produit de x et y par la méthode de Karatsuba, en supposant que x et y s'écrivent sur n chiffres en base 2.
Indication : On peut calculer 2n en Python avec l'expression 1 << n.
On peut décomposer x sous la forme a2n+b
avec a, b = x>>n, x % (1 << n).
3. En déduire une fonction mult(x, y) qui calcule le produit de x et y.
Remarque : Il n'est pas nécessaire d'utiliser la base 2. On pourrait tout aussi bien utiliser la base 10 par exemple. Mais les opérations liées à la base deux (multiplication, division ou reste par une puissance de deux sont faciles à réaliser pour la machine).
Tester avec:
print(mult(31478987896658567686786785446,2311675667575656756575765757554))
Mettre le résultat ici (code et figure).
Pour la fonction taille, il suffit de diviser x par deux jusqu’à obtenir zéro.
def taille(x):
n=1
while x > 0:
x //= 2
n += 1
return n
Pour la fonction karatsuba, on suit l’algorithme proposé, en s’arrêtant lorsqu'il ne reste qu’un seul chiffre.
def karatsuba(x, y, n):
\"\"\"multiplie x et y par La méthode de Karatsuba\"\"\"
if n <= 1:
return x * y
n //=2
m = 1<<n
a , b = x >> n , x % m
c , d = y >> n , y % m
ac = karatsuba(a, c, n)
bd = karatsuba(b, d, n)
abcd = karatsuba(a - b, c - d, n)
return (ac << ( 2 * n ) ) + ((ac + bd - abcd) << n ) + bd
Enfin, la fonction mult calcule la valeur de n comme le maximum des deux tailles (l'algorithme reste correct si l’un des deux entiers a moins que n chiffres).
def mult(x, y):
n = max(taille(abs(x)), taille(abs(y)))
return karatsuba(x, y, n)
- Détails
- Écrit par : Richard GAUTHIER
- Clics : 2484
[[{"text":"
![\"graphe10.png](\"https://sciencesappliquees.com/images/nsi/graphe9.png\")
","title":"S.D. : Parcours en profondeur et en largeur un graphe","tagtitle":"h1"},{"edit":"
"}],[{"text":"
#Test si il existe un chemin
","title":"Parcours en profondeur","tagtitle":"h1"},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
![](\"https://sciencesappliquees.com/images/nsi/graphe10.png\")
","title":"Détecter la présence d'un cycle dans un graphe orienté"},{"edit":"
"}],[{"text":"
![](\"https://sciencesappliquees.com/images/nsi/graphe3.png\")
","title":"Parcours en largeur"},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"![\"pile_file1.png](\"https://sciencesappliquees.com/images/nsi/pile_file1.png\")
![](\"https://sciencesappliquees.com/images/nsi/graphe20.png\")
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":""},{"edit":"
"}],[{"text":"
","title":"Conclusion","tagtitle":"h1"},{"edit":"
"}],[{"text":"
![](\"https://sciencesappliquees.com/images/nsi/graphe11.png\")
"},{"solution":"
"}],[{"text":"
","title":"Exercice","tagtitle":"h1"},{"edit":"
"},{"solution":"
"}],[{"text":"
![](\"https://sciencesappliquees.com/images/nsi/graphe13.png\")
![](\"https://sciencesappliquees.com/images/nsi/graphe12.png\")
","title":"Exercice","tagtitle":"h1"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"
","title":"Exercice"},{"edit":"
"},{"solution":"
"}],[{"text":"![](\"https://sciencesappliquees.com/images/nsi/graphe14.png\")
","title":"Exercice","tagtitle":"h1"},{"edit":"
"},{"solution":"
"}],[{"text":"
Nous avons le labyrinthe suivant:![](\"https://sciencesappliquees.com/images/nsi/graphe18.png\")
![](\"https://sciencesappliquees.com/images/nsi/graphe19.png\")
","title":"Exercice","tagtitle":"h1"},{"edit":"
"},{"solution":"
"}]]
On a coutume de dire que pour sortir d'un labyrinthe il suffit de toujours suivre le mur situé sur notre droite.
En particulier, on emprunte ainsi toujours la première porte que l'on rencontre sur notre droite et, si on arrive à un cul de sac, cela a pour effet de nous faire faire un demi-tour.
Ceux qui ont un peu réfléchi à cette idée, voire qui ont essayé de la mettre
en pratique, savent plusieurs choses.
D'une part, cette méthode peut échouer
dans certains cas, où on se retrouve à « tourner en rond » autour d'un bloc.
Pour y remédier, ü suffit de marquer au sol les endroits par lesquels on est déjà passé.
Dès lors, quand on revient sur un embranchement qui est marqué, on procède comme s'il s'agissait d'un cul de sac.
D'autre part, on peut tout aussi bien suivre le mur sur la gauche plutôt que sur la droite.
On peut même changer d'avis à chaque nouvelle salle et emprunter à sa guise
n'importe laquelle des portes qui la quittent.
Ces deux idées combinées, à savoir emprunter les embranchernents de façon arbitraire et marquer les endroits par lesquels on est déjà passé, constituent un algorithme fondamental appelé parcours en profondeur. Il s'applique à n'importe quel graphe et permet de déterminer tous les sommets
| sommet visité | action |
A .B ..C ...E ....B ...E ..C ...F ..C .B A .D ..E .D A | marquer A, emprunter arc A—>B marquer B, emprunter arc B—>C marquer C, emprunter arc C—>E marquer E, emprunter arc E—>B déjà vu, terminé pas d'autre arc, terminé emprunter arc C—>F marquer F, aucun arc, terminé pas d'autre arc, terminé pas d'autre arc, terminé emprunter arc A—>D marquer D, emprunter arc D—>E déjà vu, terminé pas d'autre arc, terminé pas d'autre arc, terminé |
Figure 1 — Parcours en profondeur, à partir du sommet A.
Avant de programmer le parcours en profondeur en Python, illustrons
son fonctionnement en détail sur un exemple. La figure 1 détaille les
différentes étapes du parcours en profondeur du graphe à partir du sommet A.
La première chose que l'on fait est de marquer le sommet A comme déjà vu. En effet, il pourrait y avoir un cycle qui nous ramènerait sur le sommet A (ce n'est pas le cas ici, mais on ne peut pas le
savoir a priori) et avoir marqué le sommet A nous permettra d'interrompre
le parcours et de revenir en arrière.
On considère ensuite les arcs sortants du
sommet A. Il y en a deux, à savoir A—>B et A—>D. Comme on l'a expliqué dans l'introduction, on choisit de façon arbitraire un arc à considérer en premier.
Choisissons par exemple d'emprunter l'arc A—>B. On se retrouve donc maintenant à visiter le sommet B. On commence par le marquer puis on examine ses arcs.
Ici, il n'y en a qu'un seul, à savoir B—>C. On l'emprunte donc et on se retrouve à visiter le sommet C, que l'on commence par marquer.
Il y a 2 arcs sortants du sommet C et là encore on choisit arbitrairement celui qui est considéré en premier.
Ici, on choisit l'arc C—>E, ce qui nous
conduit à marquer E puis à considérer l'unique arc E—>B issu de E.
On se retrouve alors dans une situation nouvelle, où pour la première fois on retombe sur un sommet déjà marqué, à savoir B. On revient donc en arrière, pour se retrouver sur le sommet E.
Comme il n'y avait pas d'autre arc issu
de E, on revient une fois de plus en arrière, pour se retrouver sur le sommet C.
Là, on avait considéré l'arc C—>E mais il y a également l'arc C—>F, que l'on emprunte donc maintenant.
On visite donc le sommet F, que l'on marque.
Comme il n'y a aucun arc sortant du sommet F, on a terminé et on revient
au sommet C.
Cette fois, tous les arcs issus de C ont été examinés, et on a donc terminé la visite de C.
On revient donc au sommet B, donc la visite est également terminée.
On revient donc au sommet A.
Là, il y avait encore l'arc A->D à considérer.
On visite donc le sommet D, que l'on marque avant de considérer l'arc D—>E.
On retombe alors sur le sommet E, déjà visité.
On revient donc en arrière, sur le sommet D, puis encore en arrière, sur le sommet A.
Là, il n'y a plus d'arc à considérer et la visite de A est terminée, ce qui achève notre parcours en profondeur.
Une fois le parcours terminé, tous les sommets atteignables à partir de A
ont été marqués, à savoir A, B, C, D,E et F.
Inversement, le sommet G, qui n'est pas atteignable à partir de A, n'a pas été marqué. C'est là une propriété fondamentale du parcours en profondeur.
Venons-en à la programmation du parcours en profondeur. Le code, ci-dessous repose sur deux ingrédients. Le premier est l'utilisation d'un ensemble pour le marquage des sommets, que l'on appelle vus. Le second ingrédient est l'utilisation d'une fonction récursive pour réaliser le parcours proprement dit.
Cette fonction appelée parcours reçoit en arguments le graphe g, l'ensemble vus et un sommet s à partir duquel réaliser le parcours.
En quatre lignes seulement, elle s'écrit comme elle s'énonce :
«si le sommet s n'est pas dans vus, l'y ajouter et parcourir récursivement tous ses voisins».
Programme — Parcours en profondeur
def parcours(g, vus, s):
\"\"\"parcours en profondeur depuis le sommet s\"\"\"
if s not in vus:
vus.add(s)
for v in g.voisins(s):
parcours(g, vus, v)
def existe_chemin(g, u, v):
\"\"\"existe-t-il un chemin de u à v?\"\"\"
vus = set()
parcours(g, vus, u)
return v in vus
Tester le programme existe_chemin sur le graphe suivant:
#réalisation du graphe
g2 = Graphe2()
g2.ajouter_arc(\"A\",\"B\")
g2.ajouter_arc(\"B\",\"C\")
g2.ajouter_arc(\"A\",\"D\")
g2.ajouter_arc(\"D\",\"E\")
g2.ajouter_arc(\"E\",\"B\")
g2.ajouter_arc(\"C\",\"E\")
g2.ajouter_arc(\"C\",\"F\")
g2.ajouter_arc(\"G\",\"C\")
g2.afficher()
print(\"A->F?\",existe_chemin(g2,\"A\",\"F\"))
print(\"A->G?\",existe_chemin(g2,\"A\",\"G\"))
print(\"D->F?\",existe_chemin(g2,\"D\",\"F\"))
Mettre le résultat ici (code et figure).
Déterminer l'existence d'un chemin entre deux sommets
Une application immédiate du parcours en profondeur consiste à déterminer s'il existe un chemin entre deux sommets u et v. En effet, il suffit de lancer un parcours en profondeur à partir du sommet u puis, une fois qu'il est terminé, de regarder si le sommet v fait partie de l'ensemble des sommets marqués.
Le progrannne contient une fonction existe_chemin qui réalise cette idée.
Elle crée un nouvel ensemble vus, appelle la fonction parcours à partir du sommet u puis vérifie enfin si le sommet v à été visité pendant le parcours.
Bien entendu, on pourrait interrompre le parcours en profondeur dès que le sommet v est atteint. Mais il faudrait modifier pour cela la fonction parcours.
Construire le chemin
Si on veut construire le chemin, il faut se fatiguer un peu plus.
Au lieu d'un ensemble vus, on prend un dictionnaire, qui associe à chaque sommet le sommet qui à permis de l'atteindre (la
première fois) pendant le parcours en profondeur.
Pour le sommet de départ u, on lui associe None dans ce dictionnaire.
Une fois le parcours en profondeur terminé, on ne se contente pas de regarder si le sommet d'arrivée v est dans vus, mais on «remonte» le dictionnaire, en partant de v, jusqu'à arriver à u.
Vous réaliserez ce programme dans les exercices.
Mettre le résultat ici (code et figure).
Utilisation
Illustrons l'utilisation de notre parcours en profondeur sur le graphe des régions de la figure ci-dessous:
On a la variable regions qui contient une représentation de ce graphe.
******
On peut tester la présence de chemins, par exemple comme ceci :
assert existe_chemin(regions, \"Bretagne\", \"Occitanie\")
assert not existe_chemin(regions, \"Bretagne\", \"Mayotte\")
Ici, où vérifie l'existence d'un chemin entre la région Bretagne et la région
Occitanie et l'absence d'un chemin entre la région Bretagne et la région Mayotte.
Mettre le résultat ici (code et figure).
Efficacité
Le parcours en profondeur est un algorithme très efficace, dont
******
pendant ce parcours.
En effet, l'arc u—>v est examiné au plus une fois, à savoir la première fois que la fonction parcours est appelée sur le sommet u.
En effet, si la fonction parcours est rappelée plus tard sur ce même sommet u, alors il sera trouvé dans l'ensemble vus et la fonction se terminera immédiatement, sans rien faire.
Dans le pire des cas, tous les sommets sont atteignables et tout le graphe est donc parcouru.
Le coût est moindre lorsque certains sommets ne sont pas atteignables depuis le sommet de départ.
Le coût en mémoire est celui de l'ensemble vus, qui contient au final tous les sommets atteignables.
Mettre le résultat ici (code et figure).
Limites de la récursion
La fonction parcours étant récursive, il y a un risque de provoquer RecursionError si le graphe contient beaucoup de sommets.
Ainsi, un parcours en profondeur à partir du sommet 1 sur le graphe
1 -> 2 ... <> 2000
va provoquer cette erreur, car on va dépasser le nombre maximal d'appels récursifs imbriqués (1000 par défaut).
Comme expliqué dans la séquence sur les fonctions récursives, on peut modifier cette limite avec la fonction setrecursionlimit.
Une autre solution consiste à réécrire la fonction parcours avec une boucle while.
Pour cela, on utilise une pile dans laquelle on stocke les sommets qu'il faut parcourir.
Le programme ci-dessous donne le code de cette nouvelle fonction parcours.
On n'a pas besoin de savoir ici comment la pile est réalisée.
C'est un exemple de modularité. La fonction existe_chemin reste inchangée.
Programme — Parcours en profondeur avec une pile
from modPile import *
def parcours2(g, vus, s):
\"\"\"parcours en profondeur depuis le sommet s\"\"\"
pile = Pile()
pile.empiler(s)
while not pile.est_vide():
s = pile.depiler()
if s in vus:
continue
vus.add(s)
for v in g.voisins(s):
pile.empiler(v)
def existe_chemin2(g, u, v):
\"\"\"existe-t-il un chemin de u à v?\"\"\"
vus = set()
parcours2(g, vus, u)
return v in vus
Tester avec :
g2 = Graphe2()
g2.ajouter_arc(\"A\",\"B\")
g2.ajouter_arc(\"B\",\"C\")
g2.ajouter_arc(\"A\",\"D\")
g2.ajouter_arc(\"D\",\"E\")
g2.ajouter_arc(\"E\",\"B\")
g2.ajouter_arc(\"C\",\"E\")
g2.ajouter_arc(\"C\",\"F\")
g2.ajouter_arc(\"G\",\"C\")
g2.afficher()
print(\"A->F?\",existe_chemin2(g2,\"A\",\"F\"))
print(\"A->G?\",existe_chemin2(g2,\"A\",\"G\"))
print(\"D->F?\",existe_chemin2(g2,\"D\",\"F\"))
Conclure sur k'avantage de l'utilisation d'une pile par rapport à une fonction récursive.
Mettre le résultat ici (code et figure).
Le parcours en profondeur permet également de détecter la présence d'un
cycle dans un graphe orienté.
En effet, puisque l'on marque les sommets
avant de considérer leurs voisins, pour justement éviter de tourner en rond dans un cycle, alors on doit pouvoir être à même de détecter la présence d'un cycle.
Il y a cependant une petite subtilité, car lorsqu'on retombe sur un sommet déjà marqué, on ne sait pas pour autant si on vient de découvrir un cycle.
Considérons par exemple le parcours en profondeur des deux graphes suivants, à partir du sommet A à chaque fois:
Dans le graphe de gauche, on retombe sur le sommet C.
Il n'y a pas de cycle pour autant, mais seulement un chemin parallèle.
Dans le graphe de droite, on retombe sur le sommet B, cette fois à cause d'un cycle.
Tel qu'il est écrit, notre parcours en profondeur ne nous permet pas de distinguer ces deux situations.
Dans les deux cas, on constate que le sommet est déjà dans l'ensemble vus, sans pouvoir en tirer de conclusion quant à l'existence d'un cycle.
Pour y remédier, on va distinguer dans l'ensemble vus deux sortes de sommets:
ceux pour lesquels le parcours en profondeur n'est pas encore terminé et ceux pour lesquels il est au contraire terminé.
On pourrait utiliser pour cela deux ensembles, ou encore un dictionnaire qui associe à chaque sommet déjà rencontré un booléen indiquant si son parcours en profondeur est terminé.
Mais traditionnellement on utilise un marquage à trois couleurs:
- on marque en blane les sommets non encore atteints par le parcours en profondeur,
- en gris les sommets déjà atteints dont le parcours en profondeur est en cours
- et enfin en noir les sommets atteints dont le parcours est terminé.
Dans l'exemple de gauche ci-dessus, le sommet C sera colorié en noir quand on retombera dessus la deuxième fois.
Dans l'exemple de droite, en revanche, il sera encore gris quand on retombera dessus et on en déduira la présence d'un cycle.
Nous adoptons ici cette solution utilisant trois couleurs.
Le parcours en profondeur est modifié de la façon suivante.
Lorsque l'on visite un sommet s, on procède ainsi :
- s'il est gris, c'est qu'on vient de découvrir un cycle;
- s'il est noir, on ne fait rien;
- sinon, c'est qu'il est blanc, et on procède ainsi:
- on colore le sommet s en gris;
- on visite tous ses voisins, récursivement;
- enfin, on colore le sommet s en noir.
Comme on le voit, les voisins du sommet s sont examinés après le moment où s est colorié en gris et avant le moment où s est colorié en noir.
Ainsi, s'il existe un cycle nous ramenant sur s, on le trouvera comme étant gris et
le cycle sera signalé.
Le programme ci-dessous contient une fonction cycle qui réalise cette détection de cycle. Il s'agit 1à d'une modification du parcours en profondeur où un dictionnaire couleur remplace l'ensemble vus.
Programme — Détecter la présence d'un cycle dans un graphe
BLANC, GRIS, NOIR = 1, 2, 3
def parcours_cy(g, couleur, s):
\"\"\"parcours en profondeur depuis le sommet s\"\"\"
if couleur[s] == GRIS:
return True
if couleur[s] == NOIR:
return False
couleur[s] = GRIS
for v in g.voisins(s):
if parcours_cy(g, couleur, v):
return True
couleur[s] = NOIR
return False
def cycle(g):
couleur = {}
for s in g.sommets():
couleur[s] = BLANC
for s in g.sommets():
if parcours_cy(g, couleur, s):
return True
return False
La fonction parcours est toujours une fonction récursive, mais elle renvoie désormais un résultat, à savoir un booléen indiquant la présence d'un cycle.
Enfin, la fonction cycle colorie tous les sommets en blanc puis lance un parcours en profondeur à partir de tous les sommets du graphe.
Si l'un de ces parcours renvoie True, on transmet re résultat. Sinon. on renvoie False.
Dans cette version, on cherche à détecter la présence d'un cycle n'importe où dans le graphe. C'est pourquoi on lance un parcours en profondeur à partir de tous les sommets du graphe,
Pour beauconp de ces sommets, le parcours est passé par là, car ils étaient accessibles depuis des sommets déjà parcourus, et la fonction parcours se termine immédiatement sans rien faire.
Le temps total passé dans la détection de cycle reste proportionnel à la taille du graphe. Si on lance un parcours en profondeur à partir d'un seul sommet s, alors on détecte uniquement la présence d'un cycle atteignable à partir de s.
Tester avec les graphes suivants:
g1 = Graphe2()
g1.ajouter_arc(\"A\",\"B\")
g1.ajouter_arc(\"B\",\"C\")
g1.ajouter_arc(\"A\",\"D\")
g1.ajouter_arc(\"D\",\"C\")
g1.afficher()
print(cycle(g1))
g2 = Graphe2()
g2.ajouter_arc(\"A\",\"B\")
g2.ajouter_arc(\"B\",\"C\")
g2.ajouter_arc(\"D\",\"B\")
g2.ajouter_arc(\"C\",\"D\")
g2.afficher()
print(cycle(g2))
Conclure sur les résultats donnés par la fonction cycle.
Mettre le résultat ici (code et figure).
Le parcours en profondeur nous permet de déterminer l'existence d'un chemin entre deux sommets, et même d'en construire un, mais il ne détermine pas pour autant la distance entre deux sommets, c'est-à-dire la longueur minimale d'un chemin entre ces deux sommets.
Si on considère par exemple le graphe des régions et que l'on cherche un chemin entre la région Bretagne et la région Grand Est avec notre parcours en profondeur, alors on trouve le chemin suivant :
Bretagne—>Normandie—>Hauts-de-France—>Île-de-France—>Bourgogne-Franche-Comté —> Grand Est
Ce chemin à la longueur 5, alors qu'il existe un chemin de longueur 3, à savoir
Bretagne—>Normandie—>Île-de-France—>Grand Est
Le fait est que le parcours en profondeur détermine un chemin arbitraire parmi tous les chemins possibles (sans répétitions), car il emprunte les arcs dans un ordre arbitraire.
Si on veut en revanche déterminer la distance entre deux sommets, c'est-à-dire un plus court chemin entre ces deux sommets, alors il faut utiliser un autre algorithme, à savoir le parcours en largeur.
Comme pour le parcours en profondeur, on se donne un sommet de départ, pour initier le parcours. On l'appelle la source.
Et comme pour le parcours en profondeur, on va déterminer peu à peu tous les sommets atteignables à partir de ce sommet de départ.
Ce qui diffère, c'est l'ordre dans lequel ces sommets vont être visités.
Dans le parcours en largeur, on explore le graphe «en cercles concentriques» à partir de la source, c'est-à-dire qu'on visite d'abord tous les sommets à distance 1 de la source, puis tous les sommets à distance 2 de la source, et ainsi de suite, jusqu'à ce que tous les sommets atteignables depuis la source aient été visités.
Mettre le résultat ici (code et figure).
Si on reprend l'exemple du graphe ci-dessus et qu'on effectue un parcours en largeur à partir du sommet A,
- alors on va examiner d'abord les sommets B et D, situés à distance 1 de A,
- puis les sommets C et E, situés à distance 2,
- puis enfin le sommet F, situé à distance 3.
Comme pour le parcours en profondeur, le sommet G n'est pas visité, car il n'est pas atteignable depuis A.
Pour mettre en œuvre le parcours en largeur, et l'idée de cercles concentriques, on peut se servir de deux ensembles.
Le premier, appelé courant, contient des sommets situés à distance d de la source.
C'est notamment dans cet ensemble qu'on pioche le prochain sommet à examiner.
Le second ensemble, appelé suivant, contient des sommets situés à distance d de la source, que l'on examinera après ceux de l'ensemble courant.
À côté de ces deux ensembles, on utilise également un dictionnaire, appelé dist, qui associe à chaque sommet déjà atteint sa distance à la source.
Le parcours en largeur procède ainsi :
- initialement, la source est placée dans l'ensemble courant et sa distance est fixée à D:
- tant que l'ensemble courant n'est pas vide,
(a) on en retire un sommets,
(b) pour chaque voisin v de s qui n'est pas encore dans dist
* on ajoute v à l'ensemble suivant,
* on fixe dist[v] à dist[s]+1
(c) si l'ensemble courant est vide, on l'échange avec l'ensemble
suivant.
Mettre le résultat ici (code et figure).
La figure 2 détaille les différentes étapes de cet algorithme sur l'exemple
du graphe
en partant du sommet A. La figure illustre le contenu des deux ensembles, ainsi que les différentes affectations effectuées dans le dictionnaire dist.
| courant | suivant | action |
| A | initialisation, dist[A]=0 | |
| B,D | on retire le sommet A, dist|B]=1. dist[D]=1 | |
| B,D | l'ensemble suivant est vide => échange | |
| D | C | on retire le sommet B, dist|C]=2 |
| C,E | on retire le sommet D, dist[E]=2 | |
| C,E | l'ensemble suivant est vide => échange | |
| E | on retire le sommet C, dist[F]=3 | |
| F | on retire le sommet E | |
| on retire le sommet F terminé |
Figure 2 — Parcours en largeur, à partir du sommet A.
On prendra le temps de bien comprendre cet algorithme.
Le programme ci-dessous réalise cet algorithme en Python. La fonction parcours_largeur réalise un parcours en largeur en partant du sommet
source, à l'aide d'une boucle while.
Programme — Parcours en largeur
def parcours_largeur(g, source):
\"\"\"parcours en largeur depuis le sommet source\"\"\"
dist = {source: 0}
courant = {source}
suivant = set()
while len(courant) > 0:
s = courant.pop()
for v in g.voisins(s):
if v not in dist:
suivant.add(v)
dist[v] = dist[s] + 1
if len(courant) == 0:
courant, suivant = suivant, set()
return dist
def distance(g, u, v):
\"\"\"distance de u à v (et None si pas de chemin)\"\"\"
dist = parcours_largeur(g, u)
return dist[v] if v in dist else None
Les deux ensembles courant et suivant sont des variables locales à la fonction parcours. Une fois le parcours terminé, la fonction parcours renvoie le dictionnaire dist.
Une seconde fonction distance renvoie la distance entre deux sommets u et v, en lançant un parcours en largeur à partir de u puis en consultant la valeur de dist[v].
Si v n'a pas été atteint, on renvoie None.
Tester le programme avec les instructions suivantes :
g2 = Graphe2()
g2.ajouter_arc(\"A\",\"B\")
g2.ajouter_arc(\"B\",\"C\")
g2.ajouter_arc(\"A\",\"D\")
g2.ajouter_arc(\"D\",\"E\")
g2.ajouter_arc(\"E\",\"B\")
g2.ajouter_arc(\"C\",\"E\")
g2.ajouter_arc(\"C\",\"F\")
g2.ajouter_arc(\"G\",\"C\")
g2.afficher()
print(\"distance A F\",distance(g2,\"A\",\"F\"))
print(\"distance A F\",distance(g2,\"A\",\"G\"))
justifier les résultats.
Mettre le résultat ici (code et figure).
Une file, pour quoi faire une file?
Le parcours en largeur est traditionnellement réalisé avec une file, dans laquelle on ajoute à la fin les nouveaux sommets (ceux que notre code met dans l'ensemble suivant) et dans laquelle on retire au début le prochain sommet à examiner (celui que notre code retire de l'ensemble courant).
Dans cette file, des sommets à la distance d de la source précède des sommets à distance d + 1, ce que l'on peut visualiser ainsi :
L'ordre des sommets situés à une même distance de la source important peu, notre solution avec deux ensembles convient tout aussi bien. Mais surtout, elle explicite la raison pour laquelle notre parcours en largeur est correct, ce que ne montre absolument pas la file.
En terme d'efficacité, il n'y à absolument aucune différence.
Utilisation
Illustrons l'utilisation de notre parcours en largeur sur le graphe des régions.
Nous avons la variable regions qui contienne la représentation de ce graphe:
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\")
On peut vérifier la distance entre des régions:
assert distance(regions, \"Bretagne\", \"Occitanie\") == 3
assert distance(regions, \"Bretagne\", \"Bretagne\") == 0
assert distance(regions, \"Bretagne\", \"Mayotte\") == None
Ici, on vérifie que la distance d'une région a elle-même est bien 0 et que la fonction distance renvoie bien None pour deux régions entre lesquelles il n'existe pas de chemin.
Tester les codes et conclure sur les résultats.
Mettre le résultat ici (code et figure).
Efficacité
Comme pour le parcours en profondeur, le parcours en largeur a un coût directement proportionnel à la taille de la partie du graphe qui a été explorée. En effet, chaque sommet est placé au plus une fois dans l'ensemble suivant, la première fois qu'il est rencontré, c'est-à-dire lorsqu'il n'est pas encore dans le dictionnaire dist.
À ce moment-là, on fixe sa distance, ce qui fait qu'il ne sera pas considéré de nouveau.
De même, chaque arc s —> v est examiné au plus une fois, lorsque le sommet s est retiré de l'ensemble courant.
Le coût en mémoire est celui des deux ensembles et du dictionnaire, au pire proportionnel au nombre total de sommets du graphe.
Mettre le résultat ici (code et figure).
Étant donnés un graphe et un sommet dans ce graphe, le parcours eu profondeur et le parcours en largeur sont deux algorithimes fondamentaux pour explorer le graphe en partant de ce sommet.
Ces deux parcours déterminent l'ensemble des sommets accessibles depuis le sommet de départ.
Le parcours en profondeur permet de détecter la présence d'un cycle dans un graphe orienté.
Le parcours en largeur permet de déterminer la distance entre le sommet de départ et tout sommet accessible, c'est-à-dire le plus petit nombre d'arcs pour
relier ces deux sommets.
Mettre le résultat ici (code et figure).
Dérouler à la main le parcours en profondeur sur le graphe
suivant
pour différentes valeurs du sommet de départ.
Donner à chaque fois la valeur finale de l'ensemble vus, c'est-à-dire l'ensemble des sommets atteints par le parcours.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
sommet | valeur finale
de départ de vus
0 {0,1,3,2}
1 {1,2}
2 C2}
3 {3,1,2}
Dérouler à la main le parcours en largeur sur le graphe suivant
pour différentes valeurs du sommet de départ.
Donner à chaque fois la valeur finale du dictionnaire dist, c'est-à-dire la distance à la source de chaque sommet atteint par le parcours.
Mettre le résultat ici (code et figure).
sommet valeur finale
de départ de dist
0 {0H0,1H1,38m1,2r 2}
1 {1H0,2H 1}
2 {25 0}
3 {3-0,1H1,2r 2}
On peut se servir d'un parcours en profondeur pour déterminer si un graphe non orienté est connexe, c'est-à-dire si tous ses sommets sont reliés entre eux par des chemins.
Pour cela, il suffit de faire un parcours en profondeur à partir d'un sommet quelconque, puis de vérifier que tous les sommets ont été atteints par ce parcours.
Écrire une fonction est_connexe() qui réalise cet algorithme.
On pourra se servir de la méthode sommets() de la classe Graphe et de la fonction parcours.
Tester avec les 2 graphes suivants :
g1 :
g2:
print(\"g1 connexe?\",est_connexe(g1))
print(\"g2 connexe?\",est_connexe(g2))
Résultat :
True
False
Mettre le résultat ici (code et figure).
g1 = Graphe3()
g1.ajouter_arc(\"A\",\"B\")
g1.ajouter_arc(\"B\",\"C\")
g1.ajouter_arc(\"A\",\"D\")
g1.ajouter_arc(\"D\",\"C\")
g2 = Graphe3()
g3.ajouter_arc(\"A\",\"B\")
g3.ajouter_arc(\"B\",\"C\")
g3.ajouter_arc(\"A\",\"D\")
g3.ajouter_arc(\"D\",\"C\")
g2.ajouter_arc(\"E\",\"F\")
On suit l’algorithme proposé, en faisant uniquement attention au cas d’un graphe qui ne contiendrait aucun
sommet.
def est_connexe(g):
\"\"\"le graphe est-il connexe?
(uniquement pour un graphe non orienté)\"\"\"
ts = g.sommets()
if len(ts) == 0:
return True
s = ts.pop()
vus = set()
parcours(g, vus, s)
for s in ts:
if s not in vus:
return False
return True
Dans cet exercice, on se propose d'utiliser le parcours en profondeur pour construire un chemin entre deux sommets, lorsque c'est possible.
On le fait avec deux fonctions, comme dans le programme parcours en profobdeur.
def parcours_ch(g, vus, org, s):
\"\"\"parcours depuis Le sommet s, en venant de org\"\"\"
...
def chemin(g, u, v):
\"\"\"un chemin de u à v, Le cas échéant, None sinon\"\"\"
...
L'idée est que l'attribut vus n'est plus un ensemble mais un dictionnaire, qui associe à chaque sommet visité le sommet qui a permis de l'atteindre pendant le parcours en profondeur.
La fonction parcours_ch prend un argument supplémentaire, org (pour origine), qui est justement le sommet qui a permis d'atteindre s, en empruntant l'arc org —>s.
Écrire le code de la fonction parcours_ch.
Il est très semblable à celui de la fonction parcours du programme parcours en profondeur.
Écrire ensuite le code de la fonction chemin qui renvoie un chemin entre les sommets u et v, le cas échéant, None s'il n'existe pas de chemin entre ces deux sommets.
Pour cela, lancer un parcours en profondeur à partir du sommet u, en donnant à org la valeur None, puis, si
le sommet v a été atteint, construire le chemin dans un tableau en «remontant» le dictionnaire vus de v jusqu'à u.
Tester avec le graphe suivant:
print(\"A->F?\",chemin(g2, \"A\", \"F\"))
print(\"A->G?\",chemin(g2, \"A\", \"G\"))
Résultat:
A->F? ['A', 'D', 'E', 'B', 'C', 'F']
A->G? None
Mettre le résultat ici (code et figure).
Pour parcours_ch, l'ajout dans un ensemble de-
vient un ajout dans un dictionnaire.
def parcours_ch(g, vus, org, s):
\"\"\"parcours depuis le sommet s, en venant de org\"\"\"
if s not in vus:
vus[s] = org
for v in g.voisins(s):
parcours_ch(g, vus, s, v)
Pour chemin, on prend soin de tester si v a été atteint par le parcours. Dans
le cas contraire, on renvoie None. Sinon, on construit le chemin avec une
boucle while.
def chemin(g, u, v):
\"\"\"chemin de u à v, le cas échéant, None sinon\"\"\"
vus = {}
parcours_ch(g, vus, None, u)
if v not in vus:
return None
ch = []
s=v
while s is not None:
ch.append(s)
s = vus[s]
ch.reverse()
return ch
De fait, le chemin est construit à l'envers. On prend soin de le renverser avec
la méthode reverse avant de le renvoyer.
Dans cet exercice, on se propose d'utiliser le parcours en largeur pour construire un chemin de longueur minimale entre deux sommets.
On le fait avec deux fonctions, comme dans le programme parcours en largeur.
def parcours_largeur_ch(g, source):
\"\"\"parcours depuis le sommet source\"\"\"
...
def chemin(g, u, v):
\"\"\"un chemin de u à v, le cas échéant, None sinon\"\"\"
L'idée est qu'un dictionnaire vus remplace le dictionnaire dist.
Ce dictionnaire vus associe à chaque sommet visité le sommet qui à permis de l'atteindre pendant le parcours en largeur.
Écrire le code de la fonction parcours_largeur_ch.
Il est très semblable à celui de la fonction parcours_largeur du programme parcours en largeur.
Pour le sommet source, on lui associe la valeur None dans le dictionnaire vus.
Écrire ensuite le code de la fonction chemin qui renvoie un chemin réalisant la distance entre les sommets u et v, le cas échéant, et None s'il n'existe pas de chemin entre ces deux sommets.
Pour cela, lancer un parcours en largeur à partir du sommet u puis, si le sommet v a été atteint, construire le chemin dans un tableau en «remontant» le dictionnaire vus de v jusqu'à u.
Tester avec le graphe suivant:
print(\"A->F?\",chemin(g2, \"A\", \"F\"))
print(\"A->G?\",chemin(g2, \"A\", \"G\"))
Résultat:
A->F? ['A', 'B', 'C', 'F']
A->G? None
Mettre le résultat ici (code et figure).
On garde la structure du programme 42, le diction-
naire vus prenant la place du dictionnaire dist.
def parcours_largeur_ch(g, source):
\"\"\"parcours depuis Le sommet source\"\"\"
vus = {source: None}
courant = {source}
suivant = set()
while len(courant)>0:
s = courant.pop()
for v in g.voisins(s):
if v not in vus:
suivant.add(v)
vus[v] = s
if len(courant) == 0:
courant, suivant = suivant, set()
return vus
La seconde partie, à savoir la reconstruction du chemin, n’est pas différente
de celle effectuée dans l’exercice précédent pour un parcours en profondeur.
def chemin(g, u, v):
\"\"\"chemin de u à v, Le cas échéant, None sinon\"\"\"
vus = parcours_largeur_ch(g, u)
if v not in vus:
return None
ch = []
s=v
while s is not None:
ch.append(s)
s = vus[s]
ch.reverse()
return ch
Les nœuds d'un arbre binaire peuvent être vus comme les sommets d'un graphe non orienté.
En particulier, on peut donc parcourir les nœuds d'un arbre avec un parcours en profondeur ou en largeur.
Pour le parcours en profondeur, il s'agit d'un parcours que nous avons déjà présenté, à savoir le parcours préfixe.
Dans cet exercice, on se propose de parcourir les nœuds d'un arbre binaire avec un parcours en largeur.
Écrire une fonction largeur(a) qui reçoit un arbre binaire a en argument et imprime les valeurs de ses différents nœuds dans un ordre donné par un parcours en largeur, c'est-à-dire la valeur contenue dans la racine, puis les valeurs contenues dans les nœuds immédiatement en-dessous (niveau 1), puis celles contenues dans les nœuds encore en-dessous (niveau 2), etc.
Tester le programme avec l'arbre ci-dessus et le code suivant:
largeur(a1)
Résultat:
8
4
12
2
6
10
14
1
3
7
9
13
15
Indication : Il faut utiliser les classes suivantes pour construire l'arbre a1:
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
Mettre le résultat ici (code et figure).
On crée l'arbre a1:
a1 = ABR()
a1.ajouter(8)
a1.ajouter(4)
a1.ajouter(12)
a1.ajouter(2)
a1.ajouter(6)
a1.ajouter(10)
a1.ajouter(14)
a1.ajouter(1)
a1.ajouter(3)
a1.ajouter(7)
a1.ajouter(9)
a1.ajouter(13)
a1.ajouter(15)
a1.affiche()
a1.affiche()
a1.affiche()
Le programme en largeur est le suivant:
def largeur(a):
h = hauteur(a.racine)
for i in range(1, h+1):
affiche_niveau(a.racine, i)
print()
def affiche_niveau(Noeud, niveau):
if Noeud is None:
return
if niveau == 1:
print(Noeud.valeur)
elif niveau > 1:
affiche_niveau(Noeud.gauche, niveau-1)
affiche_niveau(Noeud.droit, niveau-1)
def hauteur(Noeud):
if Noeud is None:
return 0
else:
lheight = hauteur(Noeud.gauche)
rheight = hauteur(Noeud.droit)
return 1+max(lheight, rheight)
Il est représenté part un liste à 2 dimensions en Python
grid = [[1, 0, 1, 1, 1, 1, 1 ,1],
[1, 0, 0, 0, 0, 0, 1 ,1],
[1, 1, 1, 0, 0, 0, 1 ,1],
[1, 0, 0, 0, 1, 0, 0 ,1],
[1, 0, 1, 1, 0, 0, 1 ,1],
[1, 0, 1, 0, 0, 1, 0 ,1],
[1, 0, 1, 0, 0, 0, 0 ,1],
[1, 1, 1, 1, 1, 1, 0 ,1]]
Avec :
- O pour un passage;
- 1 pour un mur;
- l'entrée est en haut à gauche en (1,0);
- la sortie est en bas à droite en (len(grid[0])-2,len(grid)-1).
En le modélisant par un graphe et en le parcourant en largeur à l'aide de la fonction chemin, on détermine le moyen pour en sortir:
Vous allez donc écrire une fonction generer_graphe qui a comme argument une grille de labyrinthe et qui retourne son graphe non orienté (Graphe3).
En effet, grace au graphe du labyrinthe et à la fonction chemin, vu précédemment, nous pourrons déterminer le chemin pour en sortir.
Indications : Pour déterminer le graphe, il faut parcourir le labyrinthe et pour chacune des cases ajouter ou non des arcs.
Par exemple :
on ajoute pour cette cellule l'arc correspondant :
glaby.ajouter_arc((x,y),(x+1,y))
et pas :
glaby.ajouter_arc((x,y),(x,y+1))
car il y a un mur.
Tester avec le code suivant :
graphe_laby = generer_graphe(grid)
itineraire = chemin(graphe_laby,(1,0),(len(grid[0])-2,len(grid)-1))
print(itineraire)
Pour notre grille le résultat est le suivant:
[(1, 0), (1, 1), (2, 1), (3, 1), (3, 2), (4, 2), (5, 2), (5, 3), (5, 4), (4, 4), (4, 5), (4, 6), (5, 6), (6, 6), (6, 7)]
Donc avec les fonctions generer_graphe et chemin, nous pouvons déterminer les parcours pour des labyrinthe plus complexes:
","title":"Exercice","tagtitle":"h1"},{"edit":"
Mettre le résultat ici (code et figure).
def generer_graphe(grille):
glaby = Graphe3()
for i in range(0,len(grille)-1):
for j in range(0,len(grille[0])-1):
if grille[i][j] == 0 and grille[i][j+1]==0:
glaby.ajouter_arc((j,i),(j+1,i))
if grille[i][j] == 0 and grille[i+1][j]==0:
glaby.ajouter_arc((j,i),(j,i+1))
j+=1
if grille[i][j]==0 and grille[i+1][j]==0:
glaby.ajouter_arc((j,i),(j,i+1))
i+=1
for j in range(0,len(grille[0])-1):
if grille[i][j] == 0 and grille[i][j+1]==0:
glaby.ajouter_arc((j,i),(j+1,i))
return glaby
- Détails
- Écrit par : Richard GAUTHIER
- Clics : 1932
[[{"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\")
","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 : 1738
[[{"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 : 1903
[[{"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 : 1794