#+TITLE : Prise de notes TD 4I500 ALGAV

Raphaël Monat (raphael.monat@lip6.fr)

TD 1 : 26/09/2019

TD 1

Exercice 1.1

Question 1.1.1

On rappelle la formule du binôme de Newton :

La première égalité suit du binôme de Newton, en posant a = b = 1

La deuxième égalité suit de la définition des suites géométriques, et de la somme des séries :

Deux manière de redémontrer ce résultat.

Par somme téléscopique, pourvu qu’on connaisse l’astuce qui consiste à multiplier les deux quantités par x - 1 :

Question 1.1.2

Définitions de Landau :

Question 1.1.3

On suppose f ∈ O(g)

Question 1.1.4

On se propose de montrer O(f + g) = O(max(f,g))

[à faire plus tard] [Notre démonstration repose sur un lemme encore non validé]

Question 1.1.5

[à reprendre au propre] [Tout pris en feuilles volantes]

Exercice 1.2

Question 1.2.1

Oui. Exemple du tri à bulle.

Question 1.2.2

Oui : f ∈ O(n^2) est une espèce de borne supérieure. On pourrait parfaitement avoir aussi f ∈ O(n).

Question 1.2.3

Oui, j’imagine : exemple du tri à bulle sur des données non-triées en n^2, mais en n sur des données n^2.

Question 1.2.4

A priori non : On a $f ∈ Θ(n^2)$, donc on a $n^2 ∈ Θ(f)$, donc on a $n^2 ∈ O(f)$.

Or $n^2 ∉ O(n)$. Donc $O(f) ⊄ O(n)$.

Ce qui revient à dire qu’il n’est pas possible qu’il soit en O(n) sur toutes les données.

Exercice 3

Question 1.3.1

Dans l’ordre croissant :

f14

f3 f11

f6

f10

f1 f9 f13 f15

f16

f8

f4

f2

f12

f5

f7

On se propose de redémontrer un certain nombre de dominations qui ne seraient pas évidentes.

On rappelle quand même un certain nombre d’ordres de grandeur qu’on suppose connus de soi.

Résultats annexes

Il est un ensemble de résultats d’analyse qu’on souhaiterait avérés, et utilisables sans redémonstration.

Deux résultats en particulier, un faible, l’autre plus fort (le faible suivant du fort, et suffisant en lui-même pour nos besoins)

TD 2 : 03/10/2019

TD 2

Exercice 2.1

Les choses qu’il fallait deviner :

l’opération Dépiler(S) consiste en le dépilage d’une “unité” (on va dire un octet) : cette opération est réputée coûter 1.
l’opération Empiler(S,x) consiste en l’empilage d’un objet x de taille d’une unité (un octet) : cette opération est réputée coûter 1.
l’opération MultiDépiler(S,k) consiste en :

MultiDépiler(P,k) tant que P ≠ ∅ et k>0 faire Dépiler(P) k = k-1

On rappelle quand même le principe de deux manières de donner un coût amorti :

Méthode par agrégat : On prend une suite de n opérations, on borne son coût, et on divise par n
Méthode du potentiel : On créé une fonction de potentiel Φ dont la différence entre Φ(D_i) et Φ(D_0) est positive ou nulle pour tout i un entier entre 0 et n.

Question 2.1.1

Coût amorti : on se place dans le cas d’une suite de n opérations (soit Empiler, soit Dépiler, soit MultiDépiler) faites sur une pile initialement vide. A la suite d’une séquence de n opérations :

On ne peut pas avoir appelé Dépiler (soit directement, soit via MultiDépiler) plus de fois qu’on a appelé Empiler (on ne dépile pas une pile vide). Le nombre total d’appel à la fonction Dépiler est inférieure ou égale à n, soit ∈ Θ(n). Le nombre d’appels restants (n - #Dépiler) correspond aux nombres d’appels de Empiler.

La complexité au pire cas de la séquence des n opérations est un élément de Θ(n).

Le coût amorti de MultiDépiler est donc de Θ(n)/n soit dans Θ(1).

Question 2.1.2

La seule condition qui doit porter sur la fonction Φ, c’est que ∀ i, Φ(D_i) - Φ(D_0) \geq 0 (D_i étant la structure de donnée que l’on considère, à l’état i) : le coût amorti selon cette définition doit toujours être un majorant du coût réel (inconnu).

Si on définit le potentiel de la pile comme simplement le nombre d’éléments de la pile, on a bien la condition respectée (si on admet qu’on commence avec une pile vide) : Φ(D_0) = 0 et ∀ i, Φ(D_i) \geq 0.

Empiler : Coût réel = 1. Différence du potentiel = 1. Coût amorti : 2 Dépiler : Coût réel = 1. Différence du potentiel = -1. Coût amorti : 0 MultiDépiler : Coût réel = k’ le minimum de k le paramètre et s la taille de la pile. Différence du potentiel = k’ le nombre d’éléments effectivement dépilés. Coût amorti = 0

Le coût amorti d’une séquence quelconque de n opérations est bien dans Θ(n) : le coût amorti d’une de ses opérations prise dans la série est donc de Θ(n)/n soit dans Θ(1).

Exercice 2.2

MultiEmpiler, deux cas distincts.

Coût réel d’une opération : k le nombre de paramètres effectivement empilés. Différence du potentiel : k le nombre de paramètres effectivement empilés.

Le coût amorti est donc effectivement de 2k dans le cas général.

On peut avoir k borné par c, ou k borné par s la taille de la pile au moment de l’opération.

Si k est borné par c, le coût amorti d’une séquence quelconque est de 2cn au plus, soit dans Θ(n) Si k est borné par s, dans le pire des cas :

Empilage puis MultiEmpilage, puis MultiEmpilage, etc… 2 + 2 + 2 * 2 + 2 * 4 + 2 * 8 + 2 * 16

2 + 2 * 2^0 + 2 * 2^1 + 2 * 2^2 + 2 * 2^3

2 + \Sum_i=0^n-1 (2*2^i)

2 + \Sum_i=0^n-1 (2ⁱ⁺¹)

2 + \Sum_i=1ⁿ (2ⁱ)

1 + \Sum_i=0ⁿ (2ⁱ)

Ce qui donne 2ⁿ⁺¹

Donc la pire séquence de 1 opération d’Empilage suivie de (n-1) opérations de MultiEmpilage est de complexité 2ⁿ⁺¹.

Soit le coût amorti un Θ(2ⁿ⁺¹/n)

Exercice 2.3

On se place dans le cas d’une séquence de n opérations. La ième opération coûte i si i est une puissance de i, et 1 sinon.

Question 2.3.1

Soit n opérations : 1 2 3 4 5 6 7 8 0 + 1 + 1 + 2 + 1 + 1 + 1 + 3

n opérations dont :

ceil(log_2(n)) opérations au plus valent i
n - ceil(log_2(n)) opérations valent 1

On a donc une complexité d’une suite de n opérations :

$i * ceil(log_2(n)) + 1 * (n - log_2(n))$

Soit d’une opération :

$\frac{i * ceil(log_2(n)) + 1 * (n - log_2(n))}{n}$

L’opération est donc dans O(1 + 1), donc dans O(1).

Question 2.3.2

a

Soit i pas une puissance de 2 :

Le coût réel est de 1, la différence de potentiel est de 1 : le coût amorti est de 2

Soit i une puissance de 2 : Le coût réel est de i, la différence de potentiel est de - Φ(i-1) : le coût amorti est de i - Φ(i-1), majoré par 0 à partir d’un certain rang.

[Tu compte les entiers de 8 non compris à 16 non compris, c’est plus que 4 : et ça va de pire en pire]

Donc 2 * (n - ceil(log_2(n))) + (i - Φ(i-1)) * ceil(log_2(n))

Qui est borné par 2 * (n - ceil(log_2(n)))

Donc O(2n), donc O(n). En effet O(2n) = O(n+n) = O(max(n,n)) = O(n)

Donc O(1) pour le coût amorti d’une opération.

Ma foi, le résultat est tout à fait satisfaisant : on obtient O(1), de même que la méthode par agrégat.

b

On obtiendra à mon avis la même chose.

La différence i - Φ(i-1) sera toujours bien négative à partir d’un certain rang.

Le coût amorti des opérations peu coûteuses sera de 3 au lieu de 2.

On aura donc le coût amorti de la suite de n opérations en O(3n) qui vaut bien toujours O(n).

Question 2.3.3

On peut prendre l’exemple de l’incrémentation d’un nombre sur le plus petit nombre de bits possibles.

Si l’incrémentation à i ne requiert pas d’augmenter le nombre de bits alloués, l’opération coûte 1 (ou un peu plus si on doit changer plus que 1 bit)

Si l’incrémentation à i requiert d’augmenter le nombre de bits alloués, il faut copier log_2(i) bits dans une nouvelle zone qui a un bit en plus.

Exercice 3.1

Question 3.1.1

Montrer l’équivalence entre les deux définitions.

Définition 1 = Définition 2

Initialisation : Vrai au rang 0

Récurrence : On suppose B_k selon Déf 1 = B_k selon Déf 2 au rang k fixé.

Si j’ai deux arbres B_k et B_k et que je mets l’un comme le fils le plus à gauche de l’autres, j’ai bien B_k+1 un arbre dont la racine à k fils : B_k que je viens de mettre, puis B_k-1, … les anciens fils de l’arbre que j’ai choisi comme frère de l’autre.

Inversement, si j’ai B_k+1 dont le noeud racine a k + 1 fils B_k, B_k-1, …, B_0, je peux bien prendre le fils le plus à gauche, j’aurais bien en main deux arbres binomiaux B_k

Donc B_k selon la première définition est équivalent à B_k selon la deuxième définition.

Question 3.1.2

a

En se servant de la définition 1, puis par induction faible :

Vrai aux rangs 0 et 1 : 1 puis 2 noeuds.
On suppose vrai au rang k fixé : B_k a bien 2^k noeuds.

On dédouble cet arbre, et on le met comme fils gauche de son frère. Le nouvel arbre a 2*2^k noeuds, soit 2^k+1

D’après le principe de récurrence, on a bien 2^k noeuds à B_k

CQFD

b

La hauteur de B_k est k. on définit la hauteur comme le nombre d’arêtes à traverser pour accéder au descendant le plus à gauche.

En se servant de n’importe quelle définition, par induction faible :

Vrai aux rangs 0 et 1 : hauteur 0 puis 1.
On suppose la chose vraie au rang k fixé : B_k est bien de hauteur k.

Soit B_k+1 : pour accéder à son descendant le plus à gauche, on doit d’abord traverser une arête pour aller à son fils le plus à gauche, qui est B_k (évident par la définition 1 et la définition 2). De là, par hypothèse de récurrence, il faut traverser k arêtes pour accéder au descendant le plus à gauche. En tout, on a donc dû traverser k+1 arêtes.

D’après le principe de récurrence, on a bien B_k de hauteur k

CQFD

c

La chose la moins triviale à prouver.

Par construction (en prenant la définition 2), le nombre de noeuds à profondeur i de B_k+1 est égal au nombre de noeuds à profondeur i de B_k (l’arbre B_k qu’on a fait le père de l’autre) plus le nombre de noeuds à profondeur i-1 de B_k (l’arbre B_k qu’on a fait le fils le plus à gauche de l’autre).

Si on donne n_k,i le nombre de noeuds de profondeur i de l’arbre B_k, alors la traduction formelle de la précédente intuition est donnée par : $n_{k + 1,i} = n_k,i + n_k,i-1$

A partir de ça, on peut démontrer ce résultat par récurrence. Initialisation (à 1) : ${1\choose 0} = {1\choose 1} = 1$. On a bien un noeud de profondeur 0 et un de profondeur 1. On suppose l’égalité vérifiée au rang n, soit $n_k,i = {k\choose i}$. On doit montrer $n_k+1,i = {k+1\choose i}$, ce qui revient à montrer, par application de la formule de Pascal $n_k+1,i = {k\choose i} + {k\choose i-1}$.

Or, par application de la précédente intuition, on voit immédiatement le résultat à démontrer.

d

Par degré, on entend arité, soit nombre de fils.

On va se servir ici de la définition 2 :

La racine de B_k a k fils, B_k-1, …, B_0.

CQFD

Conclusion

Les arbres binomiaux ont une taille exponentielle en leur degré : si leur degré est k, alors leur taille est 2^k

Les arbres binomiaux ont une hauteur, et un degré, logarithmique en leur taille : si leur taille vaut n, alors leur hauteur et leur degré valent log_2(n).

Exercice 3.2

Les files binômiales relâchées.

Question 3.2.1

Par file binomiale de taille n, on entend une file binômiale avec en tout n noeuds dedans.

L’arbre binomial en tête de file sera de degré ou de hauteur k_1 = ⌊ log_2(n) ⌋, et donc de taille 2^k_1.

Le suivant sera de degré k_2 = ⌊ log_2(n - 2^k_1) ⌋ et donc de taille 2^k_2

et ainsi de suite, jusqu’à un éventuel arbre de hauteur 0 avec un unique élément dedans (seulement si n est impair, soit dit en passant)

Exemple :

Soit n = 143

log_2(143) = 7 et des poussières.

On a donc B_7 en premier arbre binomial de la file, avec 2^7 éléments dedans (128)

143 - 128 = 15

log_2(15) = 3.9 et des poussières

On a donc B_3 en deuxième arbre binomial de la file, avec 2^3 élements dedans (8)

15 - 8 = 7

log_2(7) = 2.8 et des poussières

On a donc B_2 en troisième arbre binomial de la file avec 2^2 éléments dedans (4)

7 - 4 = 3

log_2(3) = 1 plus qqch

On a donc B_1 en quatrième arbre binomial de la file avec 2^1 éléments dedans (2)

3 - 2 = 1

On met le dernier élément dans B_0.

On a donc :

FB₁₄₃ = < AB_7, AB_3, AB_2, AB_1, AB_0 >

143 a besoin de l’arbre binomial 7, ce qui revient à dire qu’il a besoin de 8 bits pour être écrit en binaire. Et en fait, il s’écrit :

7	6	5	4	3	2	1	0
1	0	0	0	1	1	1	1

Ce qui correspond exactement aux degrés des arbres binomiaux nécessaires.

Question 3.2.2

Je viens de démontrer ce résultat dans la question précédente.

Question 3.2.3

On appelle file binomiale relâchée de n une suite de tournois binomiaux de tailles quelconques mais dont la somme des noeuds est quand même égale à n.

On a défini D(n) comme le degré maximal d’une file binomiale n.

On ne saurait avoir un arbre binomial de degré (D(n) + 1) dans une file binomiale : par définition, on aurait strictement plus de n éléments dans la file binomiale. Or c’est une file binomiale n !

La file binomiale relâchée n contient quand même toujours n éléments. Si j’admets un arbre binomial de degré (D(n) + 1), j’aurais toujours strictement plus de n éléments, ce qui sera toujours aussi absurde.

Le degré maximal d’un noeud d’une file binomiale relâchée est donc toujours de D(n).

Question 3.2.4

On dispose d’un ensemble de primitives bien choisies, et on demande d’écrire deux procédures plus complexes, et de calculer leur complexité.

a

ConcatenerFBR : c’est archi débile, on a juste besoin de faire une nouvelle file binomiale relâchée avec les éléments de la file binomiale relâchée 1 puis de la file binomiale relâchée 2.

La complexité est en O(1)

b

InsererFBR : c’est aussi giga débile, il suffit juste de rajouter un tournoi binomial B_0 avec v comme étiquette sur son unique noeud dans la file binomiale relâchée existante : la nouvelle chose est bien aussi une file binomiale relâchée.

Là encore, la complexité est en O(1)

En fait, on bouge toute la complexité dans la partie consolidation qui arrive.

Question 3.2.5

a

Le revers de la simplicité de plus haut.

On doit quand même avoir les éléments de la file binomiale en sortie des tournois binomiaux, qui respectent la croissance stricte dans tous leurs chemins descendants possibles.

On suppose n la taille de la file binomiale connu (au pire on le recalcule, c’est la somme des puissances de 2 des degrés ou hauteurs des tournois qui composent la file)

Je réarrange mes éléments.

Si j’ai deux tournois binomiaux de même taille k, je mets celui dont la racine est la plus grande comme fils de l’autre pour obtenir un tournoi binomial de taille k+1.

Si je n’ai qu’un seul tournoi binomial de taille k, je le laisse tranquille.

Au bout d’un certain nombre d’itérations, je me retrouve forcément avec au plus un exemplaire de tournoi binomial de taille k.

Je les réarrange en taille décroissante :

J’ai bien une file binomiale.

b

Soit a(H) le nombre de tournois d’une file binomiale relâchée H.

On part du principe que la seule opération qui coûte 1, c’est la comparaison des racines et des tailles (supposées accessibles).

La greffe d’un tournoi sous un autre ne coûte rien (après qu’on a compté la comparaison des racines, bien entendu), et le réordonnancement final non plus.

Mq le coût de la procédure qu’on vient d’écrire appliquée à une file H de taille n est borné par α * (a(H) + D(n))

Je prends le premier élément, je compare sa taille à celle des autres éléments : au pire a(H) - 1 comparaisons. Si j’en trouve aucun, je passe au deuxième élément.

TD 3 : 10/10/2019

TD 3

Question 1.1.1

Le père d’un 4-noeud ne peut pas être un 4-noeud dans le cas d’un éclatement systématique à la descente.

Question 1.1.2

8

3,8

2,3,8

Eclatement ! On garde un pointeur avant 8

	3
2		8

On reprend la recherche avant 8

	3
2		4,8
	3
1,2		4,8
	3
1,2		4,8,15

Eclatement ! On garde un pointeur avant 15

	3,8
1,2	4	15

On reprend la recherche avant 15

	3,8
1,2	4	10,15
	3,8
1,2	4	9,10,15

Eclatement ! On garde un pointeur avant 10

	3,8,10
1,2	4	9	15

On reprend la recherche avant 15

	3,8,10
1,2	4	9	11,15

Eclatement ! On garde un pointeur avant 8

			8
	3				10
1,2		4,7		9		11,15

On reprend la recherche avant 8

			8
	3				10
1,2		4,6,7		9		11,15
			8
	3				10
1,2		4,6,7		9		11,13,15

Eclatement ! On garde un pointeur avant 13

			8
	3				10,13
1,2		4,6,7		9	11	15

On reprend la recherche avant 13.

			8
	3				10,13
1,2		4,6,7		9	11,12	15

Eclatement ! On garde un pointeur avant 6.

			8
	3,6				10,13
1,2	4	7		9	11,12	15

On reprend la recherche avant 6.

			8
	3,6				10,13
1,2	4,5	7		9	11,12	15
			8
	3,6				10,13
1,2	4,5	7		9	11,12	14,15
			8
	3,6				10,13
1,2	4,5	7		9	11,12	14,15,16

Eclatement ! On garde un pointeur après 16.

			8
	3,6				10,13,15
1,2	4,5	7		9	11,12	14	16

On reprend la recherche avant 16.

			8
	3,6				10,13,15
1,2	4,5	7		9	11,12	14	16,17

Question 1.2.1

Arbre bicolore what ?

Remarque : on remplacera blanc par noir (la littérature parle de red-black tree, soit arbre rouge-noir)

Illustrer le principe énoncé.

Question 1.2.2

							8
		3										13
	2				6,r				10,r					15,r
1,r				5		7		9		11			14		16
			4,r								12,r					17,r

Question 1.2.3

On se propose de formaliser l’algorithme écrit plus haut.

On part de la racine :

soit il est vide : on en fait une feuille blanche.
soit c’est un 2-noeud : on le transforme en noeud blanc
soit c’est un 3-noeud : on choisit une des deux clés, on en fait le père ou le fils de l’autre, c’est au choix : par contre, on place le fils du bon côté (c’est facile, il n’y en a qu’un seul), et on met le fils en rouge, et le père en blanc. Les trois sous-arbres de l’ancien noeud sont plaçables de manière unique comme sous-arbres du fils et du père (2 sous-arbres pour le fils, 1 sous-arbre pour le père)
Soit c’est un 4-noeud : les deux clés extrêmes sont faits fils gauche (le + petit) et droit (le + grand) de la clé centrale : une manière unique de les placer, on les met en rouge, on met le père en blanc. Les 4 sous arbres du noeud qu’on vient de transformer sont plaçables de manière unique comme les sous-arbres du fils de gauche et de droite.

On définit le truc de manière récursive : on transforme les sous-arbres en premier dans le corps de la fonction.

Question 1.2.4

Est-ce que la résultante est bien un arbre bicolore ?

La racine est bien blanche : quelle qu’était la taille du noeud qu’on a cassé pour en faire la racine, on a fait ce noeud le père de zéro, un ou deux autres noeuds
Les noeuds vides sont bien blancs
Le père de tous les noeuds rouges est bien un noeud blanc : les seuls noeuds rouges qu’on a créé sont des fils de noeuds blancs créés en même temps.

Induction forte pour la quatrième propriété :

Vrai à hauteur 1 de la racine : qu’on soit rouge ou blanc, on a une seule arête à prendre, et elle débouche forcément sur une feuille (contruction)

On se place à hauteur k de la racine, et on suppose la chose vraie.

On remonte d’un noeud : soit on est rouge, on traverse autant de noeuds blancs qu’avant. Soit on est blanc, on traverse un noeud blanc de plus qu’avant dans tous les cas de manière uniforme.

On peut encadrer la hauteur de l’arbre bicolore comme ça :

(meilleur cas : on ne casse jamais) h₂₃₄ \leq b_bic \leq 2 * h₂₃₄ (pire cas : on casse à chaque fois)

Si on part du principe qu’on ne compte pas les feuilles (ou qu’on les compte) de la même manière dans les deux cas.

Question 1.3.1

Transformation inverse :

On part de la racine
On prend tous les fils rouges (il y en a au plus 2) : si il y en a 2, on les prend pour faire un 4-noeud, si il y en a 1, on le prend pour faire un 3-noeud, si il n’y en a pas, on laisse le noeud tel quel.
Les sous arbres des noeuds rouges absorbés sont les sous-arbres du nouveau {2,3,4}-noeud : si on a 2 fils rouges, on créé un 4-noeud et on a bien 4 sous-arbres. si on a fils rouge, on créé un 3-noeud, et on a bien 3 arbres (les deux du fils, plus l’ancien non-rouge du père), si on a 0 fils rouge, on ne fait rien.

Fini. (récursivité, blabla)

Question 1.3.2

Même question que la précédente (on ne s’embêtera pas à écrire du pseudo-langage).

Question 1.4.1

RotationDroite(T) :

Soit un arbre A = < q, < p, U, V >, W > avec U l’arbre de hauteur supérieure de 1 à V.

La hauteur de U est supérieure de 2 celle de W (placé plus bas, plus hauteur plus élevée)

On a V inférieur à q, et V supérieur à p.

RD(A) = < p, U, < q, V, W > >

On remonte la racine du sous-arbre fautif tout en haut.

On met U l’arbre trop grand comme ssa gauche de p la nouvelle racine. q est le sous-neoud droit, a V comme sous-arbre droit et W comme sous-arbre gauche.

RotationGaucheDroite(T) :

Soit A = < q, < p, < U, < r, V1, V2 > >, W > avec V1 l’arbre de hauteur supérieure de 1 à V2.

On a un déséquilibre entre V1 et W (2 de hauteur de différence).

On fait remonter la racine du sous-arbre fautif tout en haut. On remet les noeuds p et q à leur place (une seule). On met les sous-arbres U, V1, V2, et W à leur place (il n’y en a qu’une pour chacun de ces arbres.)

RGD(A) = < r, < p, U, V₁ >, < q, V₂, W > >

La différence de hauteur maximale est entre U, V1 et W d’une part, et V2 d’autre part, et est au maximum de 1.

Question 1.5.1

Transposer dans un arbre bicolore les différents cas d’insertion d’une clé dans une feuille d’un arbre 2-3-4.

On se met dans le cas de l’éclatement systématique en descente.

On fait la recherche de manière classique : on ne s’arrête que si on est arrivé en bas. Si on rencontre un noeud dont les deux fils sont rouges, on doit éclater (on sait que ce noeud est noir) :

On colorie ce noeud en rouge (équivalent de renvoyer l’élément central un noeud plus haut)
On colorie ses deux fils en noir (équivalent de les mettre dans des noeuds où ils sont seuls)

On reprend la recherche au noeud rouge qu’on a colorié en noir et on va jusqu’en bas, à la place unique à laquelle on peut aller.

Des fois, on doit quand même faire des rotations.

On a juste soit RD, RG, RGD, RDG et des intervertissements de couleur. (sachant qu’on doit avoir la racine toujours blanches)

Question 1.5.2

On a déjà répondu à la question.

Question 1.5.3

							8
		3										13
	2				6,r				10,r					15,r
1,r				5		7		9		11			14		16
			4,r								12,r					17,r

-> Eclatement, on rencontre un père à deux fils rouges pendant la descente.

							8
		3										13,r
	2				6,r				10					15
1,r				5		7		9		11			14		16
			4,r								12,r					17,r

-> On reprend la recherche à 13

							8
		3										13,r
	2				6,r				10						15
1,r				5		7		9		11				14		16
			4,r								12,r		13.1,r				17,r
							8
		3										13,r
	2				6,r				10							15
1,r				5		7		9		11				13.3			16
			4,r								12,r		13.1,r		14			17,r
							8
		3											13,r
	2				6,r				10								15
1,r				5		7		9			12				13.3			16
			4,r							11,r		12.5,r		13.1,r		14			17,r

-> Eclatement, on rencontre un père avec deux fils rouges pendant la descente.

							8
		3											13,r
	2				6,r				10								15
1,r				5		7		9			12,r				13.3			16
			4,r							11		12.5		13.1,r		14			17,r

-> On reprend la recherche à 12

							8
		3												13,r
	2				6,r				10									15
1,r				5		7		9			12,r					13.3			16
			4,r							11		12.5			13.1,r		14			17,r
													12.8,r

-> Fini, on a bien un arbre rouge-noir

Question 1.5.4

Déjà écrit.

insertion(A, cle)
{
	  if (!un_des_sous_arbres_est_vide(A)) {
		  if (Sous_noeud_gauche_rouge(A) && Sous_noeud_droit_rouge(A)) {
			  eclatement(A);
		  }

		  if (cle < clef(A)) {
			  insertion(sous_noeud_gauche(A), cle);
		  } else {
			  insertion(sous_noeud_droit(A), cle);
		  }
	  }

	  insertion_feuille(A, cle);
	  return;
}

Très très moche. On part du principe que toutes les sous-fonctions sont bien écrites. Et récursif en plus.

Question 1.5.5

Analysons l’algorithme du Cormen :

Pour insérer une nouvelle valeur v dans un arbre binaire de recherche, on utilise la routine arbre-inserer de l’énoncé.

Cette routine prend l’arbre T dans lequel on veut insérer la valeur, et un noeud z dont la clé est v, et dont les pointeurs respectifs vers l’élément droite et l’élément gauche sont à NULL. Le but est de modifier T et certains des attributs de z de manière à insérer z à sa position appropriée.

L’algorithme commence à la racine de l’arbre. Le pointeur x trace un simple chemin binaire vers le bas. Le pointeur y garde le parent de x (très important).

La boucle while fait descendre x et y vers le bas et s’arrête quand x est le pointeur NULL.

Quand x est le pointeur NULL, on vérifie que y ne l’est pas non plus. S’il l’est, alors c’est que l’arbre T était vide, et on peut se contenter de mettre le noeud z à la racine de T.

Si x est le pointeur NULL et que donc y est le pointeur vers son père, on sait par les propriétés de l’arbre binaire de recherche que y.left = NULL et y.right = NULL (les deux fils sont vides).

On compare donc v à la clé de y : si cette clé est inférieure, on met le noeud z à gauche, sinon à droite.

La routine left-rotate prend en paramètre l’arbre sur lequel appliquer la rotation (T), ainsi que le noeud à demote par rotation gauche (x). On disposerait apparemment d’un pointeur vers le parent p.

On enregistre dans y le pointeur vers le fils droit de x. On met le sous-arbre gauche de y (β) comme sous-arbre droit de x.

Si le sous arbre gauche de y n’est pas l’arbre nul, on fait pointer le pointeur de père de ce sous-arbre vers x.

On attribue au pointeur vers le parent de y le parent de x.

Si le parent de x (et donc maintenant, le parent de y aussi) est nul, alors la racine de l’arbre est y.

sinon, et si le sous-arbre-gauche du père de x est x (si x est à gauche de son père), on dit que ce sous-arbre-gauche du père de x est maintenant y.

Sinon (càd si le sous-arbre-droit du père de x est x, on plus simplement si x est à droite de son père), on met y comme sous-arbre-droit du père de x.

On met x à la gauche de y, et y devient le père de x.

Tout cet algorithme suppose quand même que chaque noeud a un pointeur vers son père, ce qui est coûteux.

Rotations

TD 4 : 17/10/2019

TD 2, suite

Question 2.1.1

Arbre binaire de recherche :

A

S

E

X

C

R

H

G

I

N

M

P

L

Question 2.1.2

L

A

S

E

R

X

C

H

N

G

I

M

P

Question 2.1.3

La structure de l’arbre lexicographique ne dépend pas de l’ordre d’insertion. La structure de l’arbre digital dépend de la structure. La structure de l’arbre binaire de recherche dépend de la structure.

Question 2.1.4

[non prioritaire, à refaire en révisions pour s’entraîner]

Question 2.2.1

[non prioritaire, à refaire en révisions pour s’entraîner]

Question 2.2.2

[Fait au tableau] [non prioritaire, à refaire en révisions pour s’entraîner]

Question 2.2.3

Arbre de la Briandais :

Inventé par René de la Briandais (le pionnier des structures de type tries) dans un article de 1959.

Chaque noeud est une structure qui contient un caractère et deux pointeurs. Le premier pointeur pointe vers un fils éventuel, le deuxième pointeur pointe vers un frère éventuel.

Le tableau de taille R qui constitue un noeud dans le R-trie est remplacé par une liste chaînée triée (chaînée via le deuxième pointeur) des éléments de ce tableau.

Le premier pointeur est le pointeur vers la liste chaînée triée du prochain caractère.

On doit créer un caractère supplémentaire (genre ‘\0’) qui indique qu’on est à la fin d’un mot. Par convention, ce caractère est trié avant tous les autres.

Cette structure de données est avantageuse si on a un grand alphabet : la taille du stockage d’un mot ne dépend pas de la taille de l’alphabet, mais uniquement de la taille du mot.

Là où les Patricia-tries sont très mauvais, par exemple pour stocker des mots très longs qui n’ont pas ou peu de préfixes communs, l’arbre de la briandais ne paie que deux pointeurs par caractère.

A,.,.		C,.,.	T,.,0
A,.,.	T,.,0	G,.,0	A,.,0
T,.,0	\0,0,0	G,.,0	C,.,0
\0,0,0		A,.,0	\0,0,.	G,.,0
		\0,0,0		\0,0,0

Question 2.2.4

Cette question dépend un peu trop de l’implémentation choisie. Pour notre implémentation des deux questions suivantes, on a défini les primitives suivantes :

tete, qui rend le premier caractère d’une chaine.
queue, qui rend la chaine privée de tete.
place_fratrie_ou_cree, qui rend un pointeur vers un noeud correspondant à la bonne place dans la liste chainée des frères, créé et rend s’il ne trouve pas.
place_fratrie_ou_echec, qui rend un pointeur vers un noeud correspondant à la bonne place dans la liste chaînée des frères, rend un pointeur nul s’il ne trouve pas.

Question 2.2.5

struct noeud {
	  char lettre;
	  struct noeud *frere;
	  struct noeud *fils;
};

char tete(char *chaine)
{
	  return *chaine;
}

char *queue(char *chaine)
{
	  return chaine + 1;
}

struct noeud *place_fratrie_ou_cree(struct noeud *grand_frere, char caractere)
{
	  struct noeud *cur = grand_frere;
	  for (; cur != NULL; cur = cur->frere) {
		  if (caractere == cur->lettre) return cur;

		  if (caractere > cur->frere->lettre) {
			  struct noeud *nouv = malloc(sizeof(struct noeud));
			  nouv->lettre = caractere;
			  nouv->frere = cur->frere;
			  nouv->fils = malloc(sizeof(struct noeud));

			  nouv->fils->lettre = '\0';
			  nouv->fils->fils = NULL;
			  nouv->fils->frere = NULL;

			  cur->frere = nouv;

			  return nouv;
		  }
	  }

	  cur = malloc(sizeof(struct noeud));
	  cur->frere = NULL;
	  cur->lettre = caractere;
	  cur->fils = malloc(sizeof(struct noeud));

	  cur->fils->lettre = '\0';
	  cur->fils->fils = NULL;
	  cur->fils->frere = NULL;

	  return cur;
	  }

struct noeud *place_fratrie_ou_echec(struct noeud *grand_frere, char caractere)
{
	  struct noeud *cur = grand_frere;

	  for (; cur != NULL; cur = cur->frere) {
		  if (caractere == cur->lettre) return cur;
		  if (caractere > cur->frere->lettre) return NULL;
	  }

	  return NULL;
}

struct noeud *insertion(struct noeud *racine, char *chaine)
{
	  struct noeud *cur = racine;

	  while (*chaine != '\0') {
		  cur = place_fratrie_ou_cree(cur, *chaine);
		  cur = cur->fils;
		  chaine = queue(chaine);
	  }

	  return racine;
}

struct noeud *suppression(struct noeud *racine, char *chaine)
{
}

L’implantation de la suppression est un peu complexe, surtout si on se refuse à implémenter une fonction de suppression récursive. La difficulté vient de l’absence de pointeur montant. On voudrait aussi essayer de ne descendre qu’une fois la table.

On a une idée assez élégante, mais un peu longue à implémenter : au fur et à mesure qu’on descent, on rajoute un pointeur vers le noeud qu’on vient de quitter en tête d’une liste chaînée de pointeurs qu’on aura pris la peine de créer. Si à un moment, on s’aperçoit qu’on n’a pas le mot, on peut d’arrêter, dépop tous les éléments de la liste chaînée et rendre un pointeur nul. Si on trouve le mot, on nettoie l’arbre en remontant dans la liste chaînée (et en dépopant la liste chainée au passage).

La liste chaînée de pointeurs est excellente, parce qu’on met les pointeurs dans la liste dans le sens inverse exact dans lequel on va les en enlever (LIFO). Les opérations d’ajout et de suppression dans cette liste chaînée seront en O(1), on n’a pas besoin de faire quelque hypothèse que ce soit sur la hauteur de l’arbre de la Briandais.

La complexité au pire cas de la suppression est donc de O(h) dans notre implémentation, avec h la hauteur de l’arbre.

On implémentera ça si on a le temps et l’envie.

Question 2.3.1

0,0,0,0,TACG\0
0,AAT\0,0,0,TACG\0
	0,A,0,0,TACG\0
0,AT\0,0,0,T\0
	0,A,CGGA\0,0,TACG\0
0,AT\0,0,0,T\0
	0,A,CGGA\0,0,TAC
0,AT\0,0,0,T\0		\0,0,0,G\0,0

Les chaines très longues et avec peu de radicaux communs sont très mauvaises en Patricia tries. Le patricia trie est aussi de plus en plus mauvais en la taille de l’alphabet (augmente le nombre d’éléments du tableau qui représente chaque noeud). Il faut soit faire des hypothèses sur la taille maximale des chaines de caractères à inclure, soit mettre dans les tableaux des pointeurs vers des chaînes de caractères allouées dynamiquement (mauvais pour le cache).

Néanmoins, permet un random access à tous les éléments d’un noeud, indépendemment de leur place dans l’alphabet, contrairement au Briandais, qui traite les mots de pire en pire selon qu’ils ont beaucoup de lettres de fin d’alphabet.

Question 2.3.2

Cette question ne veut rien dire de toute façon, on a probablement plein de manière de choisir nos primitives.

On va écrire une primitive qui donne le plus grand radical commun de deux chaines de caractère. (avec une règle en plus : si un des deux paramètres est la chaine vide, c’est l’autre qui est rendu).

Question 2.3.3

Un patricia trie est un tableau de chaines de caractères, dont le nombre d’éléments est donné par le nombre de lettres de notre alphabet.

En fait, un patricia trie est un R-trie : il doit donc disposer, en plus de son tableau, de R pointeurs vers chacun des R sous-noeuds

On se restreint au cas considéré, un alphabet de 4 caractères.

L’idée est la suivante :

Je suis à la racine, je compare la chaine à celle du tableau de la racine (avec la primitive décrit plus haut).

Si la racine est vide ou que la chaine de caractère du tableau est vide, je créé le noeud et je mets la chaine à sa place, ou je mets seulement la chaine à sa place.

Si le prefixe est non réduit à l’élément nul (il est au moins réduit à la première lettre par construction), et ne correspond pas à la chaine dans le tableau, il faut réduire la chaine dans le tableau au préfixe commun, et renvoyer le reste plus bas (revient à insérer dans l’arbre le reste en question, peut-être fait en utilisant la fonction courante en passant le sous-noeud et le reste en paramètre, mais ouvre une sous-chaine de récursivité).

Si le préfixe est non réduit à l’élément nul (il est au moins réduit à la première lettre par construction), et correspond bien à la chaine dans le tableau, je recommence la procédure au sous-noeud correspondant, avec en input la chaine privée de son premier élément.

Si le préfixe est non réduit à l’élément nul et qu’il est égal à la chaine que je veux insérer (caractère de terminaison compris, bien entendu), alors l’élément est déjà dans la structure et je m’arrête.

Question 2.3.4

La suppression est plus simple :

On cherche le préfixe maximal entre la chaine avec son caractère de terminaison d’une part et la chaine à la bonne place d’autre part.

Si le préfixe maximal est la chaine réduite à l’élément nul, c’est que la chaine qu’on cherche n’est pas dans la structure, on s’arrête donc.

Si le préfixe maximal est la chaîne qu’on cherche avec son caractère de fin, on supprime le champ. Si le noeud devient vide par-là, on le free.

Dans tous les autres cas, on reprend la recherche au sous-noeud idoine, avec en input la chaine de caractère privée de son préfixe commun avec le champ idoine du noeud qu’on vient de quitter.

(Dans cette vision, le caractère de terminaison fait partie intégrante de la chaine)

On a forcément une condition d’arrêt parmi les deux définies plus haut : algorithme fini et valable.

Question 2.3.5

Pas facile.

On peut vider un Patricia trie dans l’autre, en vidant les noeuds de manière systématique, en commençant par ceux du bas à gauche, par exemple.

On remonte au fur et à mesure qu’on depop les noeuds après avoir mis leur contenu dans l’autre.

Un peu violent et coûteux, mais fonctionne.

Si on connaît les tailles des deux patricia tries, on s’arrange pour vider le plus petit dans le plus grand (merci captain obvious).

Si n la taille du plus petit des deux patricia tries, alors la fusion coute n recherches plus n insertions.

Annexes

Supports de TD :

TD1 TD2

Files

TD.org

Latest commit

History

TD.org

File metadata and controls

TD 1 : 26/09/2019

TD 1

Exercice 1.1

Question 1.1.1

Question 1.1.2

Question 1.1.3

Question 1.1.4

Question 1.1.5

Exercice 1.2

Question 1.2.1

Question 1.2.2

Question 1.2.3

Question 1.2.4

Exercice 3

Question 1.3.1

Résultats annexes

TD 2 : 03/10/2019

TD 2

Exercice 2.1

Question 2.1.1

Question 2.1.2

Exercice 2.2

Exercice 2.3

Question 2.3.1

Question 2.3.2

a

b

Question 2.3.3

Exercice 3.1

Question 3.1.1

Question 3.1.2

a

b

c

d

Conclusion

Exercice 3.2

Question 3.2.1

Question 3.2.2

Question 3.2.3

Question 3.2.4

a

b

Question 3.2.5

a

b

TD 3 : 10/10/2019

TD 3

Question 1.1.1

Question 1.1.2

Question 1.2.1

Question 1.2.2

Question 1.2.3

Question 1.2.4

Question 1.3.1

Question 1.3.2

Question 1.4.1

RotationDroite(T) :

RotationGaucheDroite(T) :

Question 1.5.1

Question 1.5.2

Question 1.5.3

Question 1.5.4

Question 1.5.5

TD 4 : 17/10/2019

TD 2, suite

Question 2.1.1

Question 2.1.2

Question 2.1.3

Question 2.1.4

Question 2.2.1

Question 2.2.2

Question 2.2.3

Question 2.2.4