Python
Python
Python
Tristan.Cazenave@dauphine.fr
Objectifs
● Notions de complexité
● Tris
● Structures de données :
– Tableaux
– Listes chaînées
– Piles et files
– Arbres
– Arbres binaires de recherche
Notions de complexité
● Notion de problème
● Notion d'algorithme
● Tri par sélection
● Analyse des algorithmes
● Tri par insertion
● Complexité des algorithmes
Notion de problème
● Un problème comprend des données en entrée
et spécifie une sortie désirée.
● Exemple de problème :
● Étant donnés un tableau de nombres et un
nombre, trouver si le nombre fait partie du
tableau de nombres.
Notion de problème
● Autre exemple :
● Trier une séquence finie de nombres
[a1, a2, ..., an ]
● Entrée : une séquence de nombres
[a1, a2, ..., an ]
● Sortie : une permutation de la séquence d'entrée
[a1', a2', ..., an' ] telle que a1' ≤ a2' ≤ ... ≤ an'
Notion de problème
● Un problème peut avoir des instances.
● Définition : L'instance d'un problème est
constituée des entrées satisfaisant les
contraintes imposées par l'énoncé du problème.
● Exemple : la séquence [10, 4, 2, 9, 8, 3] est une
instance du problème du tri.
● Un algorithme de tri appliqué à cette instance
donnera en sortie la séquence [2,3,4,8,9,10].
Notion de problème
● Une notion importante est la taille de l'instance.
● En général la taille de l'instance est le nombre
d'éléments de l'instance.
● La taille de l'instance précédente pour le
problème du tri est par exemple de 6.
Notion de problème
T : N -> R
n -> T(n)
Notations et propriétés
asymptotiques
● Notation Θ
● Définition : pour une fonction g(n), on note Θ(g(n))
l'ensemble des fonctions :
Θ(g) = {f |∃ c1, c2 ∈ N∗, ∃ n0 ∈ N, ∀n ≥ n0 ∈ N,
0 ≤ c1.g(n) ≤ f (n) ≤ c2.g(n)}
● f (n) ∈ Θ(g(n)) si f(n) peut être prise en sandwich entre
c1.g(n) et c2.g(n) à partir d'un certain rang pour n.
● Par abus de notation, on écrit f (n) = Θ(g(n)) pour dire
que f (n) ∈ Θ(g(n)) .
Notations et propriétés
asymptotiques
● Exercice : montrez que 3n2 − 10n = Θ(n2)
Notations et propriétés
asymptotiques
● Montrons que 3n2 − 10n = Θ(n2)
● On cherche à déterminer c1, c2 et n0 tels que :
● c1.n2 ≤ 3n2 − 10n ≤ c2.n2 ∀n ≥ n0
● comme n2 > 0 pour n > 1 on divise tout par n 2 :
● c1 ≤ 3 − 10/n ≤ c2 ∀n ≥ n0
Notations et propriétés
asymptotiques
● partie gauche : c1 ≤ 3 − 10/n
● Si on choisit c1=2, on a
● 2 ≤ 3 − 10/n
● 10/n ≤ 1
● n ≥ 10
● c'est donc vérifié avec c1=2 pour n0=10
Notations et propriétés
asymptotiques
● partie droite : 3 − 10/n ≤ c2
● Si on choisit c2=3, on a
● 3 − 10/n ≤ 3
● 10/n ≥ 0
● qui est vérifié pour n0=10
Notations et propriétés
asymptotiques
● Donc
∀n ≥ 10 2.n2 ≤ 3n2 − 10n ≤ 3.n2
● Remarque : il suffit d'exhiber un cas
Notations et propriétés
asymptotiques
● Exercice : Montrer que 6n3 = Θ(n2)
Notations et propriétés
asymptotiques
● Supposons que 6n3 = Θ(n2)
● on doit avoir 6n3 ≤ c2.n2 ∀n ≥ n0
● donc 6n2 ≤ c2.n
● or pour n arbitrairement grand c'est impossible
car c2 est une constante.
● => de tels c2 et n0 n'existent pas
● donc 6n3 est différent de Θ(n2 )
Notations et propriétés
asymptotiques
● Intuitivement, les termes d'ordre inférieur d'une
fonction positive asymptotiquement peuvent
être ignorés ainsi que le coefficient du terme
d'ordre max.
● Pour appliquer la définition, il suffit de choisir c1
un peu plus petit que le coefficient associé au
terme de plus grand ordre et pour c2 une valeur
légèrement plus grande.
Application au tri par insertion
● On a montré que dans le pire des cas, le temps
d'exécution du tri par insertion est
T (n) = a.n2 + b.n + c avec a, b et c constantes.
● Montrons que T (n) = Θ(n2)
● On dira que la complexité au pire des cas du tri
par insertion est en Θ(n2) .
Application au tri par insertion
● Pour cela montrons que :
● Soit p(x) un polynôme de degré k quelconque à
coefficients positifs, alors p(n) ∈ Θ(n k) .
● Il faut montrer ∃ c1, c2, n0 ∈ N ∗ tels que :
∀n ≥ n0 c1.nk ≤ p(n) ≤ c2.nk
Application au tri par insertion
● soit p(x) = Σ ai xi avec ai ≥ 0 et ak > 0
● posons c1 = ak
● de façon évidente on a :
● c1.nk ≤ p(n) ∀n ≥ 1
Application au tri par insertion
● posons c2 = Σ ai
● on a bien
● p(n) ≤ c2.nk ∀n ≥ 1
● cqfd.
Notation O
● Quand on dispose d'une borne supérieure
asymptotique, on utilise la notation O
● Définition : pour une fonction g(n), on note
O(g(n)) l'ensemble des fonctions :
● O(g) = {f |∃c ∈ N∗, ∃n0 ∈ N, ∀n ≥ n0 ∈ N,
0 ≤ f (n) ≤ c.g(n)}
Notation O
● La notation O vise à donner une borne sup à
une fonction, on écrit f (n) = O(g(n))
● Exemple graphique de f(n) et c.g(n)
● Remarque :
si f (n) = Θ(g(n)) alors f (n) = O(g(n))
Notation O
● Exemple : comme 3n2 − 10n = Θ(n2)
alors 3n2 − 10n = O(n2)
● Montrons que 10n = O(n2)
● 10n ≤ n2 pour n0 = 10
● La définition est vérifiée pour c=1 et n0 = 10 .
Utilisation en théorie de la
complexité
● Puisque la notation O décrit une borne sup,
quand on l'utilise pour borner le temps
d'exécution d'un algorithme dans le pire des
cas, on borne aussi le temps d'exécution pour
une entrée quelconque.
● Application : Pour le tri par insertion, la borne
en O(n2) obtenue pour le pire cas s'applique à
toute instance.
Notation Ω
● Cette notation fournit une borne asymptotique
inférieure.
● Définition : pour une fonction g(n), on note
Ω(g(n)) l'ensemble des fonctions :
● Ω(g) = {f |∃c ∈ N∗, ∃n0 ∈ N, ∀n ≥ n0 ∈ N,
0 ≤ c.g(n) ≤ f (n)}
Notation Ω
● Théorème : Pour deux fonctions f(n) et g(n) on a
f (n) = Θ(g(n)) ssi f (n) = O(g(n)) et f (n) = Ω(g(n)) .
● Application à la complexité : comme la notation Ω
décrit une borne inférieure quand on l'utilise pour
borner le temps d'exécution d'un algorithme dans
le meilleur des cas, on borne également le temps
d'exécution pour toute entrée.
Complexité d'un algorithme
● On cherche en général à déterminer la
complexité théorique d'un algorithme dans le
pire des cas.
● On utilise la notation O puisque c'est celle qui
donne une borne sup.
Ordres de grandeur de complexités
Complexité croissante type
● O(1) constante
● O(ln(n)) logarithmique
● O(n) linéaire
● O(n²) quadratique
● O(n³) cubique
● O(nk) polynomiale
● O(en) exponentielle
Méthodes de calcul de la complexité
● Consiste à déterminer un majorant du nombre
d'opérations élémentaires nécessaires à
l'exécution d'un algorithme.
● Les opérations arithmétiques de base, les
comparaisons ( >, <, =, = ) sont des opérations
élémentaires en O(1).
● La complexité d'une affectation est en O(1).
● La complexité d'une opération de lecture ou
d'écriture est en O(1)
Méthodes de calcul de la complexité
● La complexité d'une suite d'instructions
correspond à la complexité la plus forte parmi
toutes les instructions de la suite.
● Instruction conditionnelle :
Si condition alors I1 sinon I2.
La complexité est la somme de la complexité
de l'évaluation de la condition et de la
complexité la plus grande entre I1 et I2.
Méthodes de calcul de la complexité
● La complexité d'une boucle est la somme sur
toutes les itérations de la complexité des
instructions rencontrées dans le corps de la
boucle plus la complexité du test de sortie de la
boucle.
● Procédure récursive : pour déterminer sa
complexité, il faut lui associer une fonction de
complexité inconnue T(n) et cherche une
équation de récurrence qu'il faut alors résoudre.
Comparaison de l'efficacité de
différents algorithmes
● Problème : Soit p un polynôme de degré n, à
coefficients réels, dont on veut calculer la
valeur en un point réel.
● p(x) = a0 + a1 x + a2 x2 + ... + an xn
Comparaison de l'efficacité de
différents algorithmes
x=3
poly = [1,3,4,2] # 1 + 3x + 4x^2 + 2x^3
p=0
for i in range (len(poly)):
pi = 1
for j in range (i):
pi = pi * x
p = p + poly [i] * pi
print (p)
●
Complexité ?
Comparaison de l'efficacité de
différents algorithmes
x=3
poly = [1,3,4,2] # 1 + 3x + 4x^2 + 2x^3
p=0
for i in range (len(poly)):
pi = 1
for j in range (i):
pi = pi * x
p = p + poly [i] * pi
print (p)
●
Complexité en O(n2) si polynôme de degré n
Comparaison de l'efficacité de
différents algorithmes
x=3
poly = [1,3,4,2] # 1 + 3x + 4x^2 + 2x^3
p=0
q=1
for i in range (len(poly)):
p = p + poly [i] * q
q=q*x
print (p)
●
Complexité en O(n) si polynôme de degré n
Algorithme de Horner
● Principe :
● Effectuer les calculs en partant de a n
● Puis an ∗ x + an-1
● Puis (an ∗ x + an-1 ) ∗ x + an-2
● etc.
Comparaison de l'efficacité de
différents algorithmes
x=3
poly = [1,3,4,2] # 1 + 3x + 4x^2 + 2x^3
i = len (poly) - 1
p = poly [i]
while i > 0:
i=i-1
p = p * x + poly [i]
print (p)
● Par exemple :
● On la déclare par :
a = chercher (unpatient.numero)
print a.nom
Gestion à l'aide d'un tableau
def ajouter(patient):
if t [patient.numero] != None:
return False
else:
t [patient.numero] = patient
return True
p = Patient (65432)
p.nom = "Turing"
p.prenom = "Alan"
b = ajouter (p)
print (b)
print (t [65432].nom)
Gestion à l'aide d'un tableau
supprimer (65432)
print t [65432]
Gestion à l'aide d'un tableau
15
conduit à un tableau de 10 entrées (ce qui
dépasse la taille de la mémoire vive qui est de
9
l'ordre de 10 octets)
● Or on estime le nombre de numéros attribués à
108 .
● Il est nécessaire d'utiliser une structure qui
t = []
def ajouter(patient):
i = chercher (patient.numero)
if (i != -1):
return False
else:
t.append (patient)
return True
Gestion à l'aide d'un tableau
séquentiel
● Pour supprimer un élément de ce tableau :
a = chercher (65432)
print t[a].nom
supprimer (65432)
print sommet
Gestion à l'aide d'un tableau
séquentiel
Représentation de la liste :
[0,-]->[1,-]->[2,-]->…->[10,None]
courant = entete.suiv
while (courant != None):
print (courant.entier)
courant = courant.suiv
Liste chaînée pour l'annuaire
class Cellule (object):
def __init__(self, entier):
self.numero = entier
self.nom = None
self.prenom = None
self.suiv = None
ajouter (Cellule(1024))
[0,-]->[1,-]->[2,-]->[3,-]->None
[0,-]→[1024]→[1,-]→[2,-]→[3,-]→None
supprimer (2) :
[0,-]->[1,-]->[2,-]->[3,-]->None
| î
|_______|
Liste chaînée pour l'annuaire
p = Cellule(10)
p.nom = "Turing"
p.prenom = "Alan"
ajouter (p)
p1 = chercher(10)
print (p1.nom)
supprimer (10)
p1 = chercher (10)
if (p1 == None):
print ("None")
Structures de données
listes, piles, files
Principe :
Exemple :
[5, 3, 10, 4]
Sinon :
On sépare en deux tableaux,
On trie chaque tableau
On fusionne les tableaux triés
● Exercice
● Histogramme et Camembert
Pile
p=[1,3,9,5,4].
sommet(p) renvoie 4.
dépiler (p) donne p=[1,3,9,5].
empiler (6, p) donne p=[1,3,9,5,6].
Pile
p = []
empiler (1, p)
empiler (2, p)
depiler (p)
print (sommet (p))
Pile
[-,-]->[1,-]->[2,-]->[3,-]->None
[-,-]->[e,-]->[1,-]->[2,-]->[3,-]->None
Pile avec une liste chaînée
def depiler (p):
if p.suiv == None:
return False
else:
suite = p.suiv.suiv
p.suiv = suite
return True
[0,-]->[1,-]->[2,-]->[3,-]->None
| î
|_______|
[0,-]->[2,-]->[3,-]->None
Pile avec une liste chaînée
p = Cellule (0)
empiler (1, p)
empiler (2, p)
depiler (p)
print (sommet (p))
Pile pour calculer une expression
(4 + 3) * 5
Devient alors :
43+5*
Pile pour calculer une expression
f = File ()
enfiler (1, f)
enfiler (2, f)
enfiler (3, f)
defiler (f)
affiche (f)
Éxecution :
2
3
Pile et liste chaînée
On cherche une fonction qui prend en entrée une
pile d'entiers et qui fournit en sortie une liste
chaînée qui ne contient que les nombres multiples
de 3 contenus dans la pile.
chaînée
● Comparaison des mises en œuvre
● Le TDA Pile
● Le TDA File
TDA Ensemble
● Définition : Un type de données abstrait (TDA)
se dénit par un type de données et par les
opérations qui lui sont associées.
● Exemple : Pour le TDA ensemble d'entiers on
note les opérations :
- UNION (A,B)
- INTERSECTION(A,B)
- DIFFERENCE (A,B)
TDA Ensemble
● Les types élémentaires sont ceux définis dans le langage de
programmation :
entiers, réels, caractères, chaînes de caractères.
● Les TDA sont une généralisation des types élémentaires de
même que les procédures et fonctions sont des généralisations
des opérations élémentaires +, -, /, *.
● Lorsqu'on écrit un algorithme à l'aide d'un TDA, l'algorithme ne
change pas si on modifie la façon dont les procédures du TDA
sont programmées.
● On peut traiter un TDA comme un type élémentaire associé à
des primitives.
TDA Liste
● Si une liste est représentée par [a1,a2,a3,...,an], la
longueur de la liste est n et l'élément en position i est ai.
● On utilise un type position qui peut être un entier ou un
pointeur suivant que le TDA liste est mis en oeuvre par un
tableau ou une liste chaînée.
● On suppose l'existence d'une position qui suit
immédiatement le dernier élément de la liste.
● La fonction FIN(L) retourne la position suivant la nième
position de la liste L ayant n éléments.
● La position FIN(L) varie avec la liste L.
TDA Liste
● Pour construire le TDA, on définit des opérations
sur les objets de type liste appelées primitives.
● Pour toutes les primitives on notera :
- L une liste d'éléments
- x un élément
- p une position
● La position peut être un entier ou un pointeur.
TDA Liste
● INSERER (x, p, L)
- insère l'élément x à la position p dans la liste L.
- si L= [a1,a2,...an] elle devient
[a1,a2,...,ap-1,x,ap,...,an]
- si p = FIN (L) alors la liste devient [a1,a2,...,an,x],
● FIN (L) est la position qui permet d'insérer en fin de
liste.
TDA Liste
● LOCALISER (x, L) : position
- retourne la position de x dans L.
- si x apparaît plusieurs fois dans L, c'est la
première position de x qui est renvoyée.
- si x n'est pas dans L, c'est la position FIN (L)
qui est renvoyée.
TDA Liste
● ACCEDER (p, L) : élément
- retourne l'élément en position p dans L (sans
le retirer).
- l'opération est impossible si p = FIN (L) ou si
la liste n'a pas de position p.
TDA Liste
● SUPPRIMER (p, L)
- supprime l'élément en position p dans la liste
L.
- si la liste était L= [a1,a2,...,ap-1,ap,ap+1,...,an]
elle devient [a1,a2,...,ap-1,ap+1,...,an].
- l'opération est impossible si L n'a pas de
position p ou si p = FIN (L). Dans ce cas la liste
reste inchangée.
TDA Liste
● SUIVANT (p, L) : position
- retourne la position suivant la position p dans
la liste L.
- si p est la dernière position de L, SUIVANT (p,
L) retourne FIN (L).
- l'opération est impossible si L n'a pas de
position p ou si p = FIN (L).
TDA Liste
● PRECEDENT (p, L) : position
- retourne la position précédent la position p
dans la liste L.
- l'opération est impossible si L n'a pas de
position p ou si p est la première position de L.
TDA Liste
● PREMIER (L) : position
- retourne la première position de L.
- si L est vide, retourne FIN (L).
Utilisation du TDA Liste
● Sans connaître la structure de données utilisée pour
représenter une liste, on peut écrire l'algorithme qui
prend en entrée une liste L et qui élimine de L toutes
les répétitions.
● L'algorithme Simplifier fonctionnera indépendamment
de la manière dont les listes sont représentées.
● La complexité de Simplifier dépendra de la
complexité des primitives qui elles mêmes dépendent
de la mise en oeuvre retenue.
Utilisation du TDA Liste
def Simplifier (L):
p = PREMIER (L)
while (p != FIN (L)):
q = SUIVANT (p, L)
while (q != FIN (L)):
if (ACCEDER (p, L) == ACCEDER (q, L)):
SUPPRIMER (q, L)
else:
q = SUIVANT (q, L)
p = SUIVANT (p, L)
Mise en oeuvre du TDA Liste par un
tableau
● La classe Liste contient un enregistrement à deux champs :
- un tableau de taille suffisante pour contenir les plus grandes listes à traiter.
- un entier contenant la position du dernier élément de la liste.
● L'élément ai est placé dans la ième cellule du tableau.
- Le type d'une position est un entier (l'indice dans le tableau).
- la structure de données utilisée comprend un tableau et un entier :
class Liste (object):
def __init__(self, entier):
self.tableau = [0] * entier
self.taille = entier
self.sommet = 0
Mise en oeuvre du TDA Liste par un
tableau
INSERER (x, p, L)
Pour insérer un élément à la position p :
1) Il faut déplacer les éléments situés aux
positions p, p+1,..., L.sommet vers les positions
p+1, p+2,...,L.sommet+1. Il faut faire attention à
partir du dernier élément et à aller vers la position
p, sinon on écrase les valeurs qui n'ont pas encore
été déplacées.
2) Il faut alors insérer x en position p.
Mise en oeuvre du TDA Liste par un
tableau
def INSERER (x, p, L):
if L.sommet == L.taille + 1:
print ("insertion impossible")
else:
for q in range (L.sommet - p):
L.tableau [L.sommet - q] = L.tableau [L.sommet - q - 1]
L.tableau [p] = x;
L.sommet = L.sommet + 1
● Exercice :
Ecrire la primitive SUPPRIMER (p, L)
Mise en oeuvre du TDA Liste par
une liste chaînée
def SUPPRIMER (p, L):
if p != None and p.suiv != None:
p.suiv = p.suiv.suiv
if p.suiv == None:
L.dernier = p
Mise en oeuvre du TDA Liste par
une liste chaînée
def ACCEDER (p, L):
return p.suiv.entier
● Exercice :
Ecrire la primitive AFFICHER (L) à l'aide des
primitives déjà définies
Mise en oeuvre du TDA Liste par
une liste chaînée
def AFFICHER (L):
q = PREMIER (L)
while q != FIN (L):
print (ACCEDER (q,L))
q = SUIVANT (q, L)
Comparaison des mises en oeuvre
Primitive tableau liste chaînée
INSERER(x,p,L) O(n) O(1)
LOCALISER(X,L) O(n) O(n)
ACCEDER(p,L) O(1) O(1)
SUPPRIMER(p,L) O(n) O(1)
SUIVANT(p,L) O(1) O(1)
PRECEDENT(p,L) O(1) O(n)
PREMIER(p,L) O(1) O(1)
Le TDA Pile
● On peut définir le TDA Pile à l'aide du TDA
Liste :
SOMMET(P) = ACCEDER(PREMIER(P))
DEPILER(P) = SUPPRIMER(PREMIER(P), P)
EMPILER(x,P) = INSERER(x, PREMIER(P), P)
● En utilisant l'implémentation sous forme de listes
chaînées, toutes les opérations sont en O(1).
Le TDA File
● Exercice :
Définir le TDA File à l'aide du TDA Liste
Le TDA File
● TDA File à l'aide du TDA Liste :
ENFILER(x, F) = INSERER (x, FIN (F), F)
DEFILER (F) = SUPPRIMER (PREMIER (F), F)
TETE (F) = ACCEDER (PREMIER (F))
● ENFILER est en O(n) si on n'a pas de pointeur
sur le dernier élément, sinon il est en O(1)
Histogramme
import matplotlib.pyplot as plt
import random
l = []
for x in range (100000):
e=0
for i in range (30):
e = e + random.randint (0, 1)
l.append (e)
plt.hist(l, 20)
plt.show ()
Histogramme
Camembert
import matplotlib.pyplot as plt
import random
l = [0] * 10
for x in range (100000):
e=0
for i in range (9):
e = e + random.randint (0, 1)
l [e] = l [e] + 1
plt.pie (l)
plt.show ()
Camembert
Sinus
import matplotlib.pyplot as plt
import math
t = []
s = []
for i in range (200):
t.append (i / 100.0)
s.append (math.sin (2 * math.pi * i / 100.0))
plt.plot (t, s)
plt.show ()
Sinus
Partiel 2013
Somme de deux éléments d'un tableau
Comptage d'éléments d'un tableau
Comptage d'éléments d'une liste chaînée
Indice d'un élément dans une liste chaînée
Produit des éléments d'une liste chaînée
Transformer un tableau en liste chaînée
Tri à bulle d'une liste chaînée
Opérations sur les produits
Plus grand budget
Liste triée de produits
Somme de deux éléments d'un
tableau
Ecrire un algorithme qui trouve si un nombre
donné n est la somme de deux nombres éléments
d'un tableau T.
Par exemple pour l = [1, 50, 2, 20, -] → [2, 100, 10, 30,
-] → [3, 20, 1000, 15, -] → None, l'algorithme renverra
3.
Plus grand budget
p = l.suiv
id = p.identifiant
b = p.prix * p.nombre
while p != None:
if p.prix * p.nombre > b:
id = p.identifiant
b = p.prix * p.nombre
p = p.suiv
Liste triée de produits
b = p.prix * p.nombre
p1 = l
nonInsere = True
if p1.suiv == None:
p1.suiv = p
else:
Liste triée de produits
Définitions
Ordre sur les noeuds d'un arbre
Les arbres binaires
Parcours des arbres
Mise en œuvre des arbres
Définitions
● Un arbre est un ensemble d'éléments appelés
noeuds reliés par des arcs.
● Il existe une relation de parenté entre les noeuds.
● Un noeud père est situé au dessus de ses
noeuds fils.
● Un père est relié à ses fils par des arcs.
● Le noeud le plus haut placé dont dérivent tous les
autres noeuds est appelé la racine.
Définitions
Définitions
● La racine est le noeud 12.
● Le père est placé au dessus des fils.
● Le segment reliant un fils à son père est un arc.
Définitions
● Définition récursive d'un arbre :
● Un noeud unique est un arbre. Dans ce cas il est aussi la
racine de l'arbre.
● Si n est un noeud et A1, A2,..., Ak sont des arbres de
racines respectives n1, n2, ..., nk alors on peut construire
un arbre en associant comme père unique aux noeuds n1,
n2, ..., nk le noeud n. Dans ce nouvel arbre, n est la racine
et A1, A2, ..., Ak sont les sous arbres de cette racine.
● Les noeuds n1, n2, ..., nk sont appelés les fils du noeud n.
Définitions
● Définition : si n1, n2, ..., nj est une suite de
noeuds telle que ni est le père de ni+1 pour i
allant de 1 à j-1, alors cette suite est appelée
chemin entre le nœud n1 et le noeud nj.
● La longueur du chemin est le nombre de
noeuds - 1 (= nombre d'arcs).
Définitions
● S'il existe un chemin entre les noeuds a et b alors a
est dit ascendant de b (ou ancêtre), b est dit
descendant de a.
● Tout noeud est un de ses descendants et un de ses
ascendants.
● Tout ascendant ou descendant d'un noeud différent de
lui même est un ascendant ou descendant propre.
● Dans un arbre seule la racine n'a pas d'ascendant
propre.
Définitions
● Un noeud sans descendant propre est appelé
une feuille.
● Des noeuds ayant le même père sont appelés
frères.
● Un noeud qui n'est pas une feuille est un noeud
interne.
● Il est parfois utile de nommer l'arbre sans
noeuds noté A0.
Définitions
Définitions
● 12, 17, 19 est un chemin de longueur 2.
● 12, 17, 6 n'est pas un chemin.
● Les descendants propres de 5 sont 4, 3, 6.
● Les fils de 5 sont 4 et 6.
● Le père de 5 est 12.
● Les ascendants propres de 4 sont 5 et 12.
● Les feuilles de l'arbre sont 3, 6, 18, 21.
● 18 et 21 sont frères.
Définitions
● Définition : la hauteur d'un noeud dans un arbre est la
longueur du plus long chemin que l'on peut mener entre ce
noeud et une feuille de l'arbre.
● La hauteur d'un arbre est la hauteur de sa racine.
● La profondeur d'un noeud est la longueur du chemin entre la
racine et ce noeud.
● Dans l'exemple :
● La hauteur de 5 est 2.
● La profondeur de 5 est 1.
● La hauteur de l'arbre est 3.
Ordre sur les noeuds d'un arbre
● Les fils d'un noeud sont habituellement ordonnés de gauche à droite.
●
Les deux arbres ci dessous sont différents :
a a
/\ /\
bc c b
● L'ordre gauche-droite peut être prolongé pour comparer deux noeuds qui ne sont ni
ascendants ni descendants.
● Si b et c sont deux frères, que b est à gauche de c, tout descendant de b est à gauche de tout
descendant de c.
●
Dans l'exemple :
● 5 est à gauche de 17.
● 4 est à gauche de 19.
● 6 est à gauche de 18.
● 17 n'est ni à gauche ni à droite de 18.
Les arbres binaires
● Définition : Un arbre binaire est un arbre dont chaque noeud a au
maximum deux fils.
● Les arbres binaires distinguent le fils gauche du fils droit.
● Ces deux arbres binaires sont différents :
1 1
/ \
2 2
/ \ / \
3 4 3 4
\ \
5 5
Les arbres binaires
● Dans un arbre binaire dégénéré ou filiforme chaque noeud a un seul fils
● Un arbre binaire complet est un arbre binaire dont chaque noeud a deux fils ou
est une feuille.
● Exemples :
1 1 1
/ / \ / \
2 2 3 2 3
/ / \ \
3 4 5 4
\ / \
4 6 7
filiforme complet pas complet
Les arbres binaires
● Théorème 1 : pour un arbre binaire possédant
n noeuds et de hauteur h on a :
log2 (n) ≤ h ≤ n − 1
9
/ \
4 12
/ \ \
3 5 19
/ \
18 20
Recherche d'un élément
● Ecrire une fonction python récursive qui recherche un
élément dans un ABR.
● Le prototype est recherche (x, nœud).
● Un nœud est représenté par :
class ABR (object):
def __init__(self, entier):
self.entier = entier
self.gauche = None
self.droite = None
Recherche d'un élément
def recherche (x, nœud):
if nœud == None:
return None
if nœud.entier == x:
return nœud
if x < nœud.entier:
return recherche (x, nœud.gauche)
else:
return recherche (x, nœud.droit)
Recherche d'un élément
● Ecrire la fonction recherche (x, nœud) sans
utiliser la récursivité.
● Utiliser une boucle while.
Recherche d'un élément
On peut aussi l'écrire de façon itérative :
def recherche (x, n) :
while n != None:
if n.entier == x:
return n
if x < n.entier:
n = n.gauche
else:
n = n.droit
return None
Recherche du plus grand élément
● Le plus grand élément est toujours dans le fils
droit puisque le fils droit contient tous les
éléments plus grand que le noeud.
● S'il n'y a pas de fils droit, le plus grand élément
est l'entier du noeud racine.
● Pour chercher le plus grand élément on descend
donc toujours dans le fils droit tant que c'est
possible, lorsque ce n'est plus possible on
renvoie l'entier du noeud.
Recherche du plus grand élément
● Exemple : sur l'arbre suivant rechercher le plus grand élément :
9
/ \
4 12
/ \ \
3 5 19
/ \
18 20
Recherche du plus grand élément
Exercice :
9
/ \
4 12
/ \ \
3 5 19
/ \
18 20
Ajout aux feuilles
Exercice :
● Algorithme de recherche
● Algorithme d'ajout
● Algorithme de suppression
Somme (racine)
NombresSuperieurs (racine, x)
Hauteur (racine)
U0 = 1
U1 = 1
l2 = Cellule (0)
p2 = l2
p1 = l1.suiv
indice = 0
Indices de Fibonacci d’une liste
chaînée
while p1 != None:
if indice == U1:
p2.suiv = Cellule (p1.entier)
p2 = p2.suiv
U2 = U0 + U1
U0 = U1
U1 = U2
p1 = p1.suiv
indice = indice + 1
p2.suiv = None
Inversion de deux listes chaînées
● On souhaite qu’une liste chaînée l3 contienne les
éléments de deux listes chaînées l1 et l2 dans l’ordre
inverse.
● On suppose que l1 et l2 ont la même taille. Le premier
élément de l3 est le dernier élément de l2, suivi du
dernier élément de l1, suivi de l’avant dernier élément
de l2, suivi de l’avant dernier élément de l1, etc.
● Par exemple pour l1 = [1, 2, 3, 4] et l2 = [5, 6, 7, 8] on
aura l3 = [8, 4, 7, 3, 6, 2, 5, 1].
Inversion de deux listes
l3 = Cellule (0)
p1 = l1.suiv
p2 = l2.suiv
while p1 != None:
p = l3.suiv
l3.suiv = Cellule (p1.entier)
l3.suiv.suiv = p
p = l3.suiv
l3.suiv = Cellule (p2.entier)
l3.suiv.suiv = p
p1 = p1.suiv
p2 = p2.suiv
Séparation en deux listes chaînées
● Ecrire un algorithme qui permet de trouver
l’élément e d’une liste chaînée tel qu’il y ait
autant de valeurs supérieures à cet élément
que de valeurs inférieures à cet élément dans
la liste.
● Une fois cet élément trouvé séparer la liste en
deux listes. La liste des éléments plus grands
que e et la liste des éléments plus petits que e.
Séparation en deux listes
p = l.suiv
while p != None:
plusGrand = 0
plusPetit = 0
p1 = l.suiv
while p1 != None:
if p1.entier > p.entier:
plusGrand = plusGrand + 1
if p1.entier < p.entier:
plusPetit = plusPetit + 1
p1 = p1.suiv
if plusGrand == plusPetit:
e = p.entier
p = p.suiv
Séparation en deux listes
plusGrands = Cellule (0)
plusPetits = Cellule (0)
pg = plusGrands
pp = plusPetits
p = l.suiv
while p != None:
if p.entier > e:
pg.suiv = Cellule (p.entier)
pg = pg.suiv
if p.entier < e:
pp.suiv = Cellule (p.entier)
pp = pp.suiv
p = p.suiv
Création d’un arbre binaire de
recherche
● Représenter l’arbre binaire de recherche créé
en insérant dans cet ordre les nombres
suivants:
23, 12, 5, 36, 30, 7, 6, 27
● On ne représentera que les valeurs des noeuds
et les flèches entre les noeuds.
Sommes égales
● Ecrire un algorithme qui renvoie vrai si la
propriété suivante est vérifiée et faux sinon.
● Pour tous les noeuds d’un arbre binaire la
somme des éléments du sous arbre gauche est
égale à la somme des éléments du sous arbre
droit
Sommes égales
def somme (racine):
if racine == None:
return 0
s = racine.entier
s = s + somme (racine.gauche)
s = s + somme (racine.droit)
return s
Sommes égales
def sommesEgales (r):
if r == None:
return true
if somme (r.gauche) != somme (r.droit):
return false
return sommesEgales (r.gauche) and
sommesEgales (r.droit)
Vérification d’un tas
● Dans un arbre binaire qui représente un tas
chaque valeur d’un noeud est supérieure à
toutes les valeurs de tous ses descendants.
● Ecrire un algorithme qui renvoie vrai si cette
propriété est vérifiée et faux sinon.
Vérification d’un tas
def tas (racine):
if racine == None:
return true
if racine.gauche != None:
if racine.entier < racine.gauche.entier:
return false
if racine.droit != None:
if racine.entier < racine.droit.entier:
return false
return tas (racine.gauche) and tas (racine.droit)
Elément le plus profond
if p1 == -1
return p2
if p2 == -1
return p1
if p2 < p1:
return p2
else:
return p1
Valeur de la feuille la moins
profonde
● Ecrire un algorithme qui renvoie la valeur de la
feuille la moins profonde d’un arbre binaire de
recherche.
Valeur de la feuille la moins
profonde
def valeur (racine):
if racine.gauche == None and racine.droit == None:
return racine.entier
p1 = -1
if racine.gauche != None:
p1 = profondeur (racine.gauche, 0)
p2 = -1
if racine.droit != None:
p2 = profondeur (racine.droit, 0)
Valeur de la feuille la moins
profonde
if p2 == -1
return valeur (racine.gauche)
if p1 == -1
return valeur (racine.droit)
if p1 < p2
return valeur (racine.gauche)
else:
return valeur (racine.droit)
Liste d’étudiants
On souhaite modéliser une liste d'étudiants à
l’aide de la structure suivante :
class Etudiant (object):
def __init__(self, n, no):
self.nom = n
self.note = no
self.suiv = None
Amplitude des notes
● Ecrire une fonction amplitude (l) qui renvoie la
liste des deux étudiants ayant la meilleure et la
moins bonne note.
Amplitude des notes
def amplitude (l)
p = l.suiv
petit = Etudiant (p.nom, p.note)
grand = Etudiant (p.nom, p.note)
while p != None:
if p.note < petit.note:
petit.nom = p.nom
petit.note = p.note
Amplitude des notes
if p.note > grand.note:
grand.nom = p.nom
grand.note = p.note
p = p.suiv
l1 = Etudiant (0, 0)
l1.suiv = petit
petit.suiv = grand
return l1
Ordre alphabétique
● Ecrire une fonction tri (l) qui trie la liste l par
ordre alphabétique.
Ordre alphabétique
def tri (l)
change = true
while change == true:
change = false
p = l.suiv
while p.suiv != None:
if p.nom > p.suiv.nom:
change = true
nom = p.nom
note = p.note
p.nom = p.suiv.nom
p.note = p.suiv.note
p.suiv.nom = nom
p.suiv.note = note
p = p.suiv