Final Flashcards Preview

NF16 > Final > Flashcards

Flashcards in Final Deck (29)
Loading flashcards...
1

∑q^i

s=(q^(n+1)-1) / (q-1)

(tip: s=... qs=... s-qs=...)

2

Insertion dans une pile ordonnée

Insérer(P,x)
Si pilevide(P) ou x < P[sommet[P]]
alors empiler(P,x)
sinon y:=depiler(P); insérer(P,x); empiler(P,y)

3

File, vide ? pleine ?

Vide : Tete[F] = Queue[F]
Pleine : Tete[F] = (Queue[F] + 1) % longueur[F]

4

Parcours infixe (dans l'ordre)

Parcours_infixe(x)
Si x <> nil alors
Parcours_infixe(gauche[x])
Imprimer clé[x]
Parcours_infixe(droit[x])

5

Nombre de noeuds internes (arbre binaire complet de hauteur h)

2^h -1

6

∑i, ∑k.i

∑k.i = k∑ = k.n(n+1)/2
(tip: # of terms, 2s=...)

7

ABR : Rechercher(x, k)

Si x=nil ou k=cle[x] retourner x
sinon si k < cle[x] alors retourner Rechercher(gauche[x], k)
Sinon retourner Rechercher(droit[x], k)

8

ABR : Minimum(x)

Tant que gauche[x] <> nil x=gauche[x]
Retourner x

9

ABR : Successeur(x)

Si droit[x]<>nil retourner Minimum(droit[x])
y = pere[x]
Tant que y <> nil et x=droit(y)
x=y; y=pere[y]
Retourner y

10

ABR : Insérer(T,z)

y=nil; x=racine[T]
Tant que x <> nil
y = x
si clé[z] < clé[x] x=gauche[x]
sinon x=droit[x]
pere[z] = y
Si y=nil racine[T] = z
sinon si clé[z] < cle[y] alors gauche[y] = z
sinon droit[y] = z

11

ABR : Suppression

Si aucun fils, supprimer.
Si 1 fils, raccorder.
Si 2 fils, remplacer par le minimum de droit[x] puis supprimer ce minimum

12

H-équilibré

Si pour tout x, |equilibre[x]| <= 1
equilibre(x) = hauteur(droit(x)) - hauteur(gauche(x))
(hauteur(x) = 1, hauteur(nil) = -1

13

ABR : Rotd(A, x)

Si x<>nil et gauche[x]<>nil alors
y = gauche[x]
c = droit[y]
pere[y] = pere[x]
Si pere[x] <> nil alors
si x=gauche[pere[x]] alors gauche[pere[x]] = y
sinon droit[pere[x]] = y
Sinon racine[A] = y
droit[y] = x
pere[x] = y
gauche[x] = c
Si c<>nil alors pere[c] = x

14

ABR : enraciner(racine, e)

Si cle[racine] = e alors retourner racine
Si clé[racine] > e alors
enraciner(gauche[racine], e)
retourner Rotd(racine)
Si clé[racine] < e alors
enraciner(droit[racine], e)
retourner Rotg(racine)
Complexité O(h) = O(n)

15

max(A,B) + C
C - max(A,B)
max(A,B)

= max(A+C, B+C)
= - max(A-C,B-C)
= - min(-A,-B)

16

Rotation gauche-droite

x/y-E/B-z/C-D puis x/z-E/y-D/B-C puis z/y-x/B-C-D-E

17

Propriétés tas

T[1] racine. Fils de T[i] : T[2i] et T[2i+1]
T[i] <= ses fils, père de T[i] = T[i/2]
Arbre binaire parfait de taille n. Si 2*i = n alors i n'a qu'un fils. Tous les éléments i > n/2 sont des feuilles.

18

Tas : entasser(A,i)

Gauche et droit sont des tas.
l = gauche(i)
r = droit(i)
Si l<=taille[A] et A[l] > A[i] alors max = l
sinon max = l
Si r <= taille[A] et A[r] > A[max] alors max = r
Si max ≠ i alors
échanger(A[i], A[max])
entasser(A, max)

19

Tas : construire_tas(A)

taille[A] = longueur[A]
Pour i de longueur[A]/2 à 1 faire
entasser(A,i)
Complexité O(n) !

20

Tas : trier_tas(A)

Construire_tas(A)
Pour i de longueur[A] à 2 faire
échange(A[1], A[i])
taille[A] = taille[A] - 1
entasser(A,1)
Complexité O(n.log(n))

21

Tas : extraire_max(A)

Si taille[A] < 1 erreur
max = A[1]
A[1] = A[taille[A]]
taille[A] = taille[A] - 1
entasser(A,1)
Retourner max
Complexité O(log(n))

22

Nb min-max de sommets dans un tas de hauteur h

2^h min, 2^(h+1) -1 max (donc h ~ log(n))

23

Tas : insérer_tas(A, cle)

taille[A] = taille[A] + 1
i = taille[A]
Tant que i > 1 et A[Pere[i]] < clé faire
A[i] = A[pere[i]]
i = pere[i]
A[i] = clé
Complexité O(log(n))

24

Complexité tri comparatif

O(n.log(n))

25

Tri par insertion

Stable si <=, O(n^2) ou O(n) si trié (par décalage ou permutation, on place chaque élément par comparaison avec les éléments suivants)

Tri_insertion(T)
n = taille[T]
Pour i de 2 à n faire
X = T[i]; j = i-1
Tant que j >= 1 et T[j] < X faire
T[j+1] = T[j]
j = j -1
T[j+1] = X

26

Tri par bulles

À chaque parcours, plus grand élément mis à sa place, n parcours, O(n^2) ou O(n) si trié
Tri_bulle(T)
ok = 1
j = taille[T]
Tant que OK
Ok = 0
Pour i de 1 à j-1 faire
Si T[i]>T[i+1] échanger(T[i], T[i+1]); Ok = 1
j = j-1

27

Tri par sélection

à chaque itération on place le minimum au début (O(n^2))

Tri selection(T)
Pour i de 1 à taille(T)-1
min = i
Pour j allant de i+1 à taille(T)
Si T[j] inf t[min] min=j
Si min not i échanger(t[i],t[min])

28

Tri rapide

O(n^2) mais moyenne O(n.log(n))
Tri_rapide(A,p,r)
Si p < r alors
Q = partitionner(A,r,p)
Tri-rapide(A,p,q)
Tri-rapide(A,q+1,r)

Partitionner(A,p,r)
x=A[p], i=p-1, j=r+1
Tant que vrai faire
Répéter j=j-1 jusqu'à A[j]<=x
Répéter i=i+1 jusqu'à A[i]>=x
Si i inf j échanger(a[i],a[j])
Sinon retourner j

29

Tri par dénombrement

O(k) exact, k nombre max (ensemble dénombrable)

Tri_denombrement(A,B,k)
Pour i = 1 à k faire C[i] = 0
Pour j = 1 à longueur[A] faire
C[A[j]] = C[A[j]] + 1
Pour i = 2 à k faire
C[i] = C[i] = C[i-1]
Pour j = longueur[A] à 1 faire (sinon perte stabilité)
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]] -1