TD No1

Exercice 1: recherche du nombre d'occurence d'un élément dans un tableau

Proposez un algorithme permettant de trouver le nombre d'occurences d'un élément dans un tableau. Vous devrez prouver que votre algorithme termine et fournit le bon résultat. Déterminez la complexité de votre algorithme.

Exercice 2: recherche du second plus grand élément d'un tableau

Proposez un algorithme qui recherche le second plus grand élément d'un tableau. Déterminez la complexité de votre algorithme..

Exercice 3: calcul de

On propose l'algorithme suivant de calcul de :

si n=0 alors 1

si n est pair alors retourner

si n est impair alors retourner

Ecrire la fonction C correspondante et déterminer la complexité de cet algorithme.

Exercice 4: calcul des sommes partielles

Soit T un tableau d'entiers. On note S(i,j) la somme des éléments de T d'indices compris entre i et j:

Ecrire un algorithme calculant la plus grandes de ces sommes partielles (les calculer toutes et garder la plus grande)

Quelle relation y a-t-il entre S(i,j) et S(i,j+1) ? Déduisez en un algorithme optimisé.

Comparez la complexité de vos deux algorithmes.

Exercice 5: inversion des éléments d'un tableau

Ecrire un algorithme qui inverse les éléments d'un tableau: le premier devient le dernier, le second devient l'avant-dernier, ...

Exercice 6: positifs puis négatifs dans un tableau

Proposez un algorithme permettant d'obtenir à partir d'un tableau T un tableau T' tel que

T' contient tous les éléments de T

Dans T', les nombres négatifs sont avant les nombres positifs

On souhaite maintenant modifier directement le tableau T sans utiliser de tableau auxiliaire. Proposez l'algorithme correspondant

Vous calculerez la complexité de vos algorithmes.

Exercice 7: n-uplets de 0 et de 1

Proposez un algorithme permettant d'afficher tous les n-uplets composés de 0 et de 1. Ainsi, si n vaut 2, on souhaite obtenir les n-uplets suivants: 00 01 10 11 (dans l'ordre de votre choix). Déterminez la complexité de votre algorithme.

TD No1: éléments de correction

Exercice 1: recherche du nombre d'occurence d'un élément dans un tableau

Proposez un algorithme permettant de trouver le nombre d'occurences d'un élément dans un tableau. Vous devrez prouver que votre algorithme termine et fournit le bon résultat. Déterminez la complexité de votre algorithme.

Algorithme:

// recherche du nombre d'occurences de l'élément X dans le tableau t

// nbElem: nombre d'élément de t. nbElem >= 0

// dans le cas où le tableau est vide, on retourne 0

int nbOccurence(Element x, tableau t, int nbElem){

int cb, cmpt;

assert(nbElem>=0);

cmpt=0;

for (cb=0; cb < nbElem; cb ++)

if (t[cb]==x)

cmpt++;

return cmpt;

}

C'est un algorithme classique que de chercher le nombre d'éléments d'une structure vérifiant une propriété. Il s'écrit de façon générale de la façon suivante en utilisant une variable initialisée à 0 qui va être incrémentée à chaque découverte d'un élément vérifiant la propriété :

cmpt=0;

parcours de la structure

si l'élément courant vérifie la propriété

elors cmpt = cmpt + 1;

return cmpt;

Correction :

La terminaison ne pose pas problème car l'algorithme est constitué d'une boucle for simple dont le nombre d'itérations (nbElem) ne change pas lors de l'exécution de la boucle.

Posons l'invariant de boucle suivant: « x apparaît exactement cmpt fois dans la partie de tableau d'indices compris entre zéro et cb-1 ».

Initialisation : cet invariant de boucle est valable au début de la première boucle (la partie de tableau est vide car cb==0)

Conservation: si l'invariant de boucle est vrai à la ième itération et s'il y a une (i+1)ème itération:

lors de la ième itération, cb vaut i-1

si t[cb]==x alors cmpt est incrémenté. Or, le nombre d'occurences de x dans partie de t d'indices compris entre 0 et cb est égalà 1+ « le nombre d'occurences de x dans la partie du tableau d'indice compris entre 0 et cb-1 »=la valeur actuelle de cmpt.

Si t[cb] != x alors la valeur de cmpt ne change pas. Or, le nombre d'occurences de x dans partie de t d'indices compris entre 0 et cb est égal au « nombre d'occurences de x dans la partie du tableau d'indice compris entre 0 et cb-1 « =la valeur actuelle de cmpt.

À la fin de la ième boucle et donc au début de la (i+1)ème, l'invariant de boucle est donc vérifié dans les deux cas.

La valeur de l'invariant de boucle lors de la dernière itération (cb==nbElem) nous permet de conclure sur la correction de l'algorithme car dans ce cas, la partie de tableau dont parle l'invariant de boucle correspond à tout le tableau.

Complexité:

Détermination des opérations fondamentales: au pif comme d'habitude. Si on se trompe d'opérations fondamentales, on énonce un résultat juste (l'algo nécessite tant de telles opérations) mais sans intérêt pratique car ce nombre d'opérations n'est pas alors pas proportionnel au temps d'exécution.

On choisit la comparaison d'éléments comme opération fondamentale. Ne pas confondre avec les comparaison d'entiers comme celles que l'on trouve dans « cb < nbElem ». L'une des raisons et notamment que, dans la vraie vie, les éléments sont des choses complexes dont la comparaison nécessite beaucoup plus de temps que la comparaison de deux entiers.

Il y a une comparaison dans la boucle for. La complexité en nombre de comparaisons d'éléments est donc égale à

Exercice 2: recherche du second plus grand élément d'un tableau

Proposez un algorithme qui recherche le second plus grand élément d'un tableau. Déterminez la complexité de votre algorithme..

Correction:

L'énonce de l'exercice est imprécis. Exemple: Si le tableau contient les nombres suivants : 1;5;4;3;7;1;10;6;8;10;7. Le second plus grand élément du tableau est-il 10 (qui apparaît 2 fois donc une fois en première place et une fois en seconde) ou bien 8 (qui est la seconde plus grande valeur du tableau). Dit plus rigoureusement, laquelle des deux affirmations suivantes est-elle la bonne :

on trie les éléments du tableau dans l'ordre décroissant (10,10,8,7,7,6,5,4,3,1,1) et on prend le deuxième éléments. Dans ce cas, on retourne 10. Tout ceci suppose qu'il y a au moins 2 éléments dans le tableau.

on détermine la plus grande valeur, on ôte toutes ses occurences (1;5;4;3;7;1;6;8;7 )et on prend le plus grand élément. Dans ce cas, on retourne 8. Tout ceci suppose qu'il y a au moins deux valeurs distinctes dans le tableau.

C'est au rédacteur de l'exercice de la préciser. :-) Comme on ne sait pas ce qu'il en est, on fera les deux.

// fonction vue en cours

void echange(int * a, int * b){

int tmp;

tmp=*a;

*a=*b;

*b=tmp;

}

// retourne le second plus grand élément du tableau t,

// c'est à dire le second élément d'une version triée de t

// t doit avoir au moins 2 éléments (nbElem >=2)

// nbElem: nombre d'éléments du tableau.

int max2_m1(tableau t, int nbElem)

{

int i, max, max2,tmp;

assert(nbElem >= 2);

max=t[0];

max2=t[1];

if (max2 > max)

echange(&max, &max2);

for (i=2; i< nbElem; i++){

tmp=t[i];

if (tmp > max2){

max2=tmp;

if (max2 > max)

echange (&max, &max2);

}

}

return max2;

}

Pour expliquer l'algo ci-dessus, j'explique que max1 contient le plus grand élément de la partie de tableau déjà examinée et max2 contient le deuxième. Je fais remarquer que cette remarque naturelle revient à définir un invariant de boucle. Comme quoi les invariants de boucle font partie de la vie courante même si on en a pas concience. :-) Un problème classique est de savoir quoi prendre comme valeurs initiales pour nos variables (ici max1 et max2). Dans le premier algo, on peut simplement prendre t[0] et t[1] (le plus grand des deux dans max1 et l'autre dans max2). Dans le second algo (ci-dessous), ce n'est plus possible car il faut que max1 != max2. On va donc rechercher la première valeur v différente de t[0]. On mettra v et t[0] dans max1 (la plus grande) et dans max2 (l'autre).

La seconde valeur du tableau:

// retourne la seconde plus grande valeur de t : le max du

// tableau obtenu en enlevant son max à t

// t doit contenir au moins deux valeurs différentes

// nbElem: nombre d'éléments du tableau

int max2_m2(tableau t)

{

int i, max, max2,tmp;

max=t[0];

// on cherche une valeur != max dans t :

i=1;

while ((i<nbElem) && (t[i]==max))

i++;

assert(i < nbElem); // equivaut à l'existence de 2

// valeurs != dans le tableau

max2=t[i];

if (max2 > max)

echange(&max, &max2);

// arrivé là, max contient la plus grande valeur des celules d'indice <= i

// max2 contient la seconde plus grande valeur (!= max) des celules

// d'indice <= i

// il reste à traiter le reste du tableau

for (;i< nbElem; i++){ // on garde la valeur précédente de cb

tmp=t[i];

if ((tmp > max2) && (tmp != max)){

max2=tmp;

if (max2 > max)

echange (&max, &max2);

}

}

return max2;

}

Exercice 3: calcul de

On propose l'algorithme suivant de calcul de :

si n=0 alors 1

si n est pair alors retourner

si n est impair alors retourner

Ecrire la fonction C correspondante et déterminer la complexité de cet algorithme.

Corrigé:

// calcul de x^n

// n entier positif ou nul

// x entier

int puissance(int x, int n){

assert(n>=0);

if (n%2==0)

return carre(puissance(x,n/2));

else return x*puissance(x,n-1));

}

// détermine le carré d'un entier

// (pour éviter de calculer deux fois puissance(x, n/2) dans puissance)

int carre(int a){

return a*a;

}

Complexité: opération fondamentales: opération arithmétique (/, -)

On note c(n) la complexité de puissance(x,n).

si n est pair,

si n est impair, car n-1 est pair

En admettant que c(n) est une fonction croissante de n, on en déduit si

Soit k tel que soit On en déduit que k est le plus petit k tel que et

De la définition de k, on déduit que k=partie entière de . On a donc affaire à une complexité qui est au plus logarithmique (O(log n)).

Exercice 4: calcul des sommes partielles

Soit T un tableau d'entiers. On note S(i,j) la somme des éléments de T d'indices compris entre i et j:

Ecrire un algorithme calculant la plus grandes de ces sommes partielles (les calculer toutes et garder la plus grande)

Quelle relation y a-t-il entre S(i,j) et S(i,j+1) ? Déduisez en un algorithme optimisé.

Comparez la complexité de vos deux algorithmes.

Correction:

Remarque: le problème n'a d'intérêt que si le tableau contient des nombres négatifs et des nombres positifs.

L'algorithme qui calcule la somme des éléments d'une structure est un algorithme classique qui peut s'écrire schématiquement de la façon suivante en utilisant une variable s dans laquelle vont venir d'accumuler les valeurs des éléments de la structure:

s=0;

on parcourt tous les éléments de la structure

s=s+élément courant

On va appliquer cet algorithme pour calculer la somme des éléments d'indice compris entre a et a de notre tableau:

// retourne la somme des éléments du tableau d'indices compris entre a et b

// inclus.

// on suppose que a et b sont des indices valides et que a < b :

// - a positif ou nul

// - b strictement inférieur au nombre d'élément du tableaux

// - a < b

int somme(int a, int b, tableau t, int nbElem){

int res;

assert(a >= 0);

assert(b < nbElem);

assert(a < b);

res=0;

for (cb=a; cb <= b; cb++)

res=res+t[cb];

return res;

}

On peut maintenant utiliser la fonction somme pour répondre au problème posé :

Le calcul de la plus grande des valeurs d'un ensemble d'objet est un algorithme classique qui peut s'écrire de la façon suivante :

m=valeur initiale plus petite que le max des éléments de l'ensemble

on parcourt l'ensemble

si la valeur courante est supérieure à m

alors m = valeur courante

on retourne m

Le seul problème consiste à trouver une valeur initiale intelligente inférieure à la plus grande valeur de l'ensemble. Exemple: pour déterminer la plus grande valeur stockée dans un tableau, on prendra la première valeur t[0] comme valeur initiale car le max est forcément supérieur ou égal à t[0].

Appliquons tout ça à notre problème :

// calcul de la plus grande somme partielle

// des éléments d'un ensemble

// le tableau ne doit pas être vide (ça se discute mais on prend ça pour

// éviter de parler de somme des éléments d'un tableau vide

int plusGrandeSomme(tableau t, int nbElem){

int i,j,res,tmp;

assert(nbElem >0);

s=somme(0,0,t, nbelem);

for(i=0; i< nbElem; i++)

for(j=i; j < nbElem; j++){

tmp=somme(i,j,t,nbElem); // pour éviter de calculer 2 fois la somme

if (s<tmp)

s=tmp;

}

return s;

}

Alog optimisé:

// calcul de la plus grande somme partielle

// des éléments d'un ensemble

// le tableau ne doit pas être vide (ça se discute mais on prend ça pour

// éviter de parler de somme des éléments d'un tableau vide

int plusGrandeSomme(tableau t, int nbElem){

int i,j,res,tmp;

assert(nbElem >0);

s=t[0];

for(i=0; i< nbElem; i++){

tmp=0;

for(j=i; j < nbElem; j++){

tmp=tmp+t[j];

if (s<tmp)

s=tmp;

}

return s;

}

Complexite: on admet que On peut alors montrer que le premier algo est un tandis que le second est un O(n²).

Exercice 5: inversion des éléments d'un tableau

Ecrire un algorithme qui inverse les éléments d'un tableau: le premier devient le dernier, le second devient l'avant-dernier, ...

Correction:

Les erreurs à ne pas faire :

Avant d'écraser une valeur (t[i] ici), il faut être sur de ne plus en avoir besoin :

for (i=0, i < nbElem; i++)

t[i]=t[nbElem-i-1];

Le tableau {1,5,3,4}devient {4,3,3,4}

Autre erreur classique: erreur de borne

for (i=0, i < nbElem; i++)

echange(&(t[i]), &(t[nbElem-i-1]));

Il fallait se limiter à (i < nbElem/2).

Une solution (pédagogiquement intéressante parce qu'elle utilise deux « mémorisateurs de position »: i et j):

i=0;j=nbElem-1;

while (i < j){

echange(&(t[i]), &(t[j]));

i++;

j--;

}

Exercice 6: positifs puis négatifs dans un tableau

Proposez un algorithme permettant d'obtenir à partir d'un tableau T un tableau T' tel que

T' contient tous les éléments de T

Dans T', les nombres strictement négatifs sont avant les nombres positifs ou nuls

On souhaite maintenant modifier directement le tableau T sans utiliser de tableau auxiliaire. Proposez l'algorithme correspondant

Vous calculerez la complexité de vos algorithmes.

Correction:

Premier algo :

tableau posneg(tableau t, int nbElem){

int i,j,cb;

tableau res;

assert(nbElem >= 0);

i=0;

j=nbElem-1;

for (cb=0; cb < nbElem; cb++)

if (t[cb]<0) {

res[i]=t[cb];

i++;

} else {

res[j]=t[cb];

j--;

}

return res;

}

Algo sur place :

comme je n'ai pas envie de parler de passage de tableaux en paramètres, je ne présente pas l'algo sous la forme d'une fonction.

int i,j,cb;

assert(nbElem >= 0);

i=0;

j=nbElem-1;

while (i<j){

// on cherche un positif trop à gauche

while ((i<j) && (t[i]<0))

i++;

// on cherche un négatif trop à droite

while ((i<j) && (t[j]<0))

j--;

// si i<j, on les échange et on repart pour un tour

if (i<j)

echange(&(t[i]), &(t[j]));

}

}

Dans les deux cas, complexité linéaire en nombre de comparaisons.

Exercice 7: n-uplets de 0 et de 1

Proposez un algorithme permettant de d'afficher tous les n-uplets composés de 0 et de 1. Ainsi, si n vaut 2, on souhaite obtenir les n-uplets suivants: 00 01 10 11 (dans l'ordre de votre choix). Déterminez la complexité de votre algorithme.

Correction:

En le faisant au tableau à la main, on voit que l'on est obligé d'utiliser la ligne du dessus pour savoir où l'on en est. Appliquer un algorithme similaire nécessitera un tableau pour mémoriser l'état courant.

#define NMAX 200

typedef struct ttableau {

int tab [NAMX];

int taille;

} tableau;

void affiche(tableau t){

int cb;

assert(t.taille >=0);

for(cb=0; cb<t.taille; cb++)

printf("%d",t.tab[cb]);

printf("\n");

}

void nuplets(int n, tableau * pt){

if (n == 0)

affiche(*pt);

else {

pt->tab[n]=0;

nuplets(n-1,pt);

pt->tab[n]=1;

nuplets(n-1,pt);

}

}

complexité en nombre d'affectations au tableau: C(n)=2+2C(n-1)=2+2(2+2C(n-2))=2+2^2+2^4+ ...+2^n (de tête, à vérifier)

TD No2

Exercice 1 ensembles représentés par des tableaux

Nous allons représenter les ensembles par des tableaux. On rappelle le TAD ensemble vu en cours :

Sorte Ensemble

Utilise: Booléen, Element

Opérations:

ensemble_vide: -> Ensemble

ajouter: Element x Ensemble -> Ensemble

retirer: Element x Ensemble -> Ensemble

appartient: Element x Ensemble -> Booléen

Propriétés:

Tout ensemble non vide peut être construit en ajoutant ses éléments à l'ensemble vide. Un ensemble est donc soit vide, soit de la forme ajouter(e, E).

appartient(e, ensemble_vide) = Faux

appartient(e, ajouter(e, E)) = Vrai // l'élément ajouté appartient à l'ensemble

si e != e', appartient(e, ajouter(e', E))= appartient(e, E) // pour les autres éléments, l'ajout ne change pas leur situation.

appartient(e, supprimer(e, E)) = Faux // un élément supprimé n'est plus dans l'ensemble

si e != e', appartient(e, supprimer(e', E))=appartient(e,E) // pour les autres éléments, la suppression ne change pas leur situation

Question 1 : union d'ensembles

Ajoutez l'opération union au type abstrait ensemble. L'union de deux ensembles A et B est un ensemble contenant tous les éléments de A et de B.

Question 2 : union d'ensembles: implantation à l'aide tableaux non triés

On représente les ensembles par des tableaus non triés. Proposer un algorithme permettant de réaliser l'union de deux ensembles et l'implantation en C correspondante . Vous déterminerez sa complexité au pire en nombre de comparaisons d'éléments et en nombre d'affectations d'éléments.

On pourra utiliser l'algorithme, vu en cours, testant l'appartenance d'un élément à un ensemble représenté par un tableau non trié :

typedef struct ttableau {

int tailleMax;

int taille;

int * tab;

} tableau;

int appartient(int e, tableau t){

int cb;

for (cb=0; cb < t.taille; cb ++){

if (t.tab[cb]==e)

return 1;

return 0;

}

Question 3 : union d'ensembles (cas trié)

On représente maintenant les ensembles par des tableaux triés. Que faut-il modifier dans l'algorithme de la question 2 pour le rendre compatible avec notre nouvelle représentation des ensembles ? Quelle influence cette modification a-t-elle sur la complexité de l'algorithme ?

Question 4 : union d'ensembles (cas trié)

Plutôt que d'ajouter les éléments un à un, nous nous proposons de tirer partie de la remarque suivante:

soient A et B deux ensembles représentés par des tableaux triés

soient minA le plus petit élément de l'ensemble A, soit minB, le plus petit élément de l'ensemble B

Où se trouve minA dans le tableau représentant A ? Où se trouve minB dans le tableau représentant B ?

soit minUnion le plus petit élément de A U B. Où se trouve-t-il dans l'ensemble représentant A U B ?

peut-on exprimer minUnion en fonction de minA et de minB ?

Proposez un algorithme tirant partie de ces remarques. Vous déterminerez un majorant de sa complexité en nombre de comparaisons d'éléments et en nombre d'affectations d'éléments de façon à prouver qu'elles sont d'un ordre de grandeur inférieur à celles de l'algorithme de la question 3.

Exercice 2 pile d'entiers

Nous allons représenter les piles d'entiers par des listes chaînées. On rappelle le type abstrait de données vu en cours :

Sorte: Pile

Utilise: Booléen, Element

Opérations:

pile_vide: -> Pile

empiler: Pile x Element -> Pile

dépiler: Pile -> Pile

sommet: Pile -> Element

est_vide: Pile -> Booléen

Propriétés:

dépiler(p) est défini si est_vide(p) == Faux

sommet(p) est défini si est_vide(p) == Faux

dépiler(empiler(p,e))= p (rem; toute pile p' non vide pouvant se mettre sous la forme p'=empiler(p,e), cette propriété permet de déterminer ce que vaut dépiler(p') pour toute pile p' non vide.

sommet(empiler(p,e))=e

est_vide(pile_vide()) == Vrai

si p=empiler(p', e) alors est_vide(p)=Faux

Question 1:

En C, on représentera une pile par une liste chaînée de la façon suivante:

typedef struct telement{

int valeur;

struct telement * suivant;

} element;

typedef element * pile;

Implanter les opérations sur les piles.

Exercice 3 type abstrait de données : file d'entiers

Nous allons représenter les piles d'entiers par des listes chaînées. On rappelle le type abstrait de données vu en cours :

Sorte: File

Utilise : Element, Booléen

Opérations:

file_vide: ->File

ajouter: File x Element -> File

supprimer : File -> File

premier: File -> Element

est_vide: File -> Booléen

Propriétés:

ajouter(f,e) est définie si est_pleine(f) vaut Faux

supprimer(f) est définie si est_vide(f) vaut Faux

premier(f) est définie si est_vide(f) vaut Faux

si est_vide(f) == Vrai alors premier(ajouter(f,e))==e

si est_vide(f) == faux alors premier(ajouter(f,e))==premier(f)

si est_vide(f) == Vrai alors supprimer(ajouter(f,e))==file_vide

si est_vide(f) == faux alors supprimer(ajouter(f,e))==ajouter(supprimer(f),e)

Question 1:

Dans un premier temps, on envisage de représenter les file par des listes chaînées. Proposez les algorithmes correspondants et évaluez leur complexité en nombre de parcours d'éléments (on utilisera l'affectation d'une adresse comme opération fondamentale).

Question 2

On se propose de maintenir un pointeur qui désignera le dernier élément de la liste. Une file sera donc représentée par un élément du type suivant :

typedef struct tfile {

liste premier; // premier élément

liste dernier; // dernier élément

} file;

Expliquez en quoi cette représentation permettra d'améliorer la complexité des opérations sur les file et écrire l'implantation correspondante des opérations sur les files.

TD No2

Exercice 1 ensembles représentés par des tableaux

Nous allons représenter les ensembles par des tableaux. On rappelle le TAD ensemble vu en cours :

Sorte Ensemble

Utilise: Booléen, Element

Opérations:

ensemble_vide: -> Ensemble

ajouter: Element x Ensemble -> Ensemble

retirer: Element x Ensemble -> Ensemble

appartient: Element x Ensemble -> Booléen

Propriétés:

Tout ensemble non vide peut être construit en ajoutant ses éléments à l'ensemble vide. Un ensemble est donc soit vide, soit de la forme ajouter(e, E).

appartient(e, ensemble_vide) = Faux

appartient(e, ajouter(e, E)) = Vrai // l'élément ajouté appartient à l'ensemble

si e != e', appartient(e, ajouter(e', E))= appartient(e, E) // pour les autres éléments, l'ajout ne change pas leur situation.

appartient(e, supprimer(e, E)) = Faux // un élément supprimé n'est plus dans l'ensemble

si e != e', appartient(e, supprimer(e', E))=appartient(e,E) // pour les autres éléments, la suppression ne change pas leur situation

Question 1 : union d'ensembles

Ajoutez l'opération union au type abstrait ensemble. L'union de deux ensembles A et B est un ensemble contenant tous les éléments de A et de B.

Eléments de correction :

Union: Ensemble x Ensemble -> Ensemble

Propriétés:

appartient(e, union(A,B))=appartient(e,A) ou appartient(e,B)

On peut le dire autrement:

les éléments de A U B sont les éléments de A et les éléments de B

On peut aussi le dire de la façon suivante :

A U ensemble_vide = A

A U ajouter(e,B)=ajouter(e, A U B)

Cette dernière façon de définir les propriétés nous donne quasimment un algorithme implantable (mais pas forcémment eficace) pour calculer l'union de deux ensembles. Si on suppose définie la fonction premier qui retourne l'un des éléments de l'ensemble, la fonction reste qui retourne l'ensemble privé de l'élément retourné par premier et la fonction copie qui retourne un nouvel ensemble copie de l'ensemble passé en argument :

ensemble union(ensemble A, ensemble B){

if (estVide(B))

return copie(A);

else {

element e=premier A;

ensemble res= union(reste(A), B);

ajouter(e, &res);

return res;

}

}

Un algorithme classique proche consiste à ajouter successivement les éléments de A puis ceux de B à un ensemble initialement vide :

ensemble union(ensemble A, ensemble B){

ensemble res;

while(! EstVide(A)){

ajouter(premier(A), &res);

A=reste(A);

}

while(! EstVide(B)){

ajouter(premier(B), &res);

B=reste(B);

}

return res;

}

Cette algorithme sera valable quelque soit la représentation des ensembles. On peut même le généraliser à autre chose que des ensembles: il sera valable pour tout type de structure de données à partir du moment où l'on souhaite obtenir une structure de données contenant les éléments de A et ceux de B. C'est la fonction ajouter qui garantit que le résultat est une structure de données viable (ici, un ensemble).

Question 2 : union d'ensembles: implantation à l'aide tableaux non triés

On représente les ensembles par des tableaus non triés. Proposer un algorithme permettant de réaliser l'union de deux ensembles et l'implantation en C correspondante . Vous déterminerez sa complexité au pire en nombre de comparaisons d'éléments et en nombre d'affectations d'éléments.

On pourra utiliser l'algorithme, vu en cours, testant l'appartenance d'un élément à un ensemble représenté par un tableau non trié :

typedef struct ttableau {

int tailleMax;

int taille;

int * tab;

} tableau;

int appartient(int e, tableau t){

int cb;

for (cb=0; cb < t.taille; cb ++){

if (t.tab[cb]==e)

return 1;

return 0;

}

Eléments de correction :

Pour construire unon(t1, t2), on va :

recopier t1 dans un tableau résultat (pour éviter le test d'appartenance présent dans la fonction ajouter et qui est inutile ici car on sait que les éléments ne sont pas encore dans le tableau cible vu que t1 est un ensemble (tableau non trié sans redondance).

insérer un à un les éléments de t2 dans le tableau résultat à l'aide d'une fonction sachant ajouter un élément à un ensemble et garantissant le fait qu'un élément n'apparaît pas deux fois. Tester l'appartenance est utile car un élément de t2 peut aussi appartenir à t1.

// recopie le tableau s dans le tableau dest

// le contenu initial du tableau destination est détruit

// le tableau destination doit être suffisamment grand :

// dest->tailleMax >= s.taille

void copie(tableau s, tableau * dest){

int cb;

assert(dest->tailleMax >= s.taille);

for (cb=0; cb < s.taille, cb ++)

dest->tab[cb]=s.tab[cb];

dest->taille=s.taille;

}

// indique si un tableau est plein :

// t.taille==t.tailleMax

// ajoute un élément à un tableau (à la fin)

// si l'élément est déjà dans le tableau, on ne fait rien

// dans le cas où l'élément n'est pas dans le tableau,

// le tableau ne doit pas être plein

void ajouter(int e, tableau * pt){

if (! appartient(e, *pt)){ // si l'élément n'est dans le tableau

assert(! Est Plein(*pt));

pt->tab[pt->taille]=e;

pt->taille++;

}

}

// retourne un nouveau tableau contenant l'union de t1 et de t2.

// on choisit taille.t1+taille.t2 comme taille pour le tableau résultat ce qui

// est discutable car 1) dans certains cas, c'est trop et 2) dans d'autres,

// ça ne laisse aucune marge pour ajouter des éléments au tableau.

// la bonne solution consiste à profiter du fait que nos tableaux sont

// alloués dynamiquement pour les redimentionner si ils sont pleins

// (ou trop vide). Ceci dit, on sort du cadre de ce TD.

tableau union(tableau t1, tableau t2){

tableau res;

int cb;

res=creeTableau(t1.taille+t2.taille);

copie(t1, &res); // aucune comparaisons; t1.taille affectations d'éléments

for (cb=0; cb< t2.taille; cb ++)

ajouter(t2.tab[cb], &res); // de 1 à res.taille comparaisons;

// 0 ou 1 affectation

return res;

}

Complexité: dans la fonction ajouter(t2.tab[cb], &res), on a de 1 à res.taille comparaisons et de 0 à 1 affectations suivant que l'on ajoute ou non l'élément. L'un des pires cas est celui où aucun élément du second ensemble n'est dans le premier car :

chaque élément est compaté avec tous ceux de res (qui en contient t1.taille, puis t1.taille+1, ..., t1.taille+t2.taille-1) au total: t1.taille*t2.taille+(1+2+3+...+t2.taille-1)=t1.taille*t2.taille+t2.taille * (t2.taille+1)/2-1=Θ(n²) si t1.taille et t2.taille valent n tous les deux.

Chaque élément est ajouté à res (1 affectation).

Dans ce pire cas, on a :

t1.taille + t2.taille affectations (t1.taille dans copie puis t2.taille dans ajouter)

Question 3 : union d'ensembles (cas trié)

On représente maintenant les ensembles par des tableaux triés. Que faut-il modifier dans l'algorithme de la question 2 pour le rendre compatible avec notre nouvelle représentation des ensembles ? Quelle influence cette modification a-t-elle sur la complexité de l'algorithme ?

Elements de correction: la solution la plus simple consiste à modifier la fonction ajouter en y remplaçant l'ajout à la fin par un ajout à la bonne place après un décalage des éléments situés à sa droite.

On peut optimiser un peu les choses en remplaçant l'appel à appartient par un appel à une fonction renvoyant la place que l'élément devrait avoir dans le tableau. Il suffit ensuite de voir s'il y est vraiment pour éviter de l'y ajouter dans ce cas. La fonction place peut utiliser une recherche dichotomique dont la complexité est en log n (non vu encore, sera vu lors du prochain cours). Ici, on se contentera de la recherche séquencielle utilisée ci-dessus pour le cas non trié.

L'algorithme devient :

void ajouter(int e, tableau * pt){

int p, cb;

p=place(e, *pt);

if (! (pt->tab[p] == e)){ // si l'élément n'y est pas

// on décale, noter le sens de parcours (cb --)

for (cb = pt->taille; cb > p; cb --)

pt->tab[cb]=pt->tab[cb-1];

pt->tab[p]=e;

pt->taille ++;

}

}

D'un point de vue complexité, on passe en n² pour le nombre d'affectations (cas où le second tableau a tous ses éléments strictement plus petits que ceux du premier et où l'ajout se fait toujours avant les éléments de t1 que l'on est donc obligé de décaler).

Aucun changement pour le nombre de comparaisons (ou passage en nlog(n) si recherche dichotomique.

Question 4 : union d'ensembles (cas trié)

Plutôt que d'ajouter les éléments un à un, nous nous proposons de tirer partie de la remarque suivante:

soient A et B deux ensembles représentés par des tableaux triés

soient minA le plus petit élément de l'ensemble A, soit minB, le plus petit élément de l'ensemble B

Où se trouve minA dans le tableau représentant A ? Où se trouve minB dans le tableau représentant B ?

soit minUnion le plus petit élément de A U B. Où se trouve-t-il dans l'ensemble représentant A U B ?

peut-on exprimer minUnion en fonction de minA et de minB ?

Proposez un algorithme tirant partie de ces remarques. Vous déterminerez un majorant de sa complexité en nombre de comparaisons d'éléments et en nombre d'affectations d'éléments de façon à prouver qu'elles sont d'un ordre de grandeur inférieur à celles de l'algorithme de la question 2.

Eléments de correction:

nos tableaux sont triés. Les plus petits éléments sont donc en début de tableau. Le plus petit élément de l'union est donc soit le plus petit élément de A, soit le plus petit élément de B.

Exemple: A={2,3,5,8,11}, B={1,4,5,8,11}, le plus petit élément de l'union est 1=min(1,2)

Cela nous conduit à l'algorithme suivant où on suppose que res est un tableau suffisamment grand pour contenir l'union des deux ensembles:

cbA=0;cbB=0;cbres=0;

while ((cbA < A.taille) && (cbB < b.taille)){

if (A.tab[cbA]== B.taille[cbB])

cbB++;

else if ((A.tab[cbA] < B.taille[cbB]){ // le min est dans A

res.tab[cbres]=A.tab[cbA];

cbres++;

cbA++;

} else { // le min est dans B

res.tab[cbres]=B.tab[cbB];

cbres++;

cbB++;

}

// on recopie ce qui reste dans l'éventuel tableau non fini

while (cbA<A.taille){

res.tab[cbres]=A.tab[cbA];

cbA++;

cbres++;

}

while (cbB<B.taille){

res.tab[cbres]=B.tab[cbB];

cbB++;

cbres++;

}

res.taille=cbres;

// maintenantres = A U B

D'un point de vue complexité, on fait au plus une ou deux comparaison pour chaque élément de A et de B et une affectation au plus pour chaque élément de A et de B. La complexité est donc en O(n) tant en nombre de comparaisons qu'en nombre d'affectations.

Exercice 2 pile d'entiers

Nous allons représenter les piles d'entiers par des listes chaînées. On rappelle le type abstrait de données vu en cours :

Sorte: Pile

Utilise: Booléen, Element

Opérations:

pile_vide: -> Pile

empiler: Pile x Element -> Pile

dépiler: Pile -> Pile

sommet: Pile -> Element

est_vide: Pile -> Booléen

Propriétés:

dépiler(p) est défini si est_vide(p) == Faux

sommet(p) est défini si est_vide(p) == Faux

dépiler(empiler(p,e))= p (rem; toute pile p' non vide pouvant se mettre sous la forme p'=empiler(p,e), cette propriété permet de déterminer ce que vaut dépiler(p') pour toute pile p' non vide.

sommet(empiler(p,e))=e

est_vide(pile_vide()) == Vrai

si p=empiler(p', e) alors est_vide(p)=Faux

Question 1:

En C, on représentera une pile par une liste chaînée de la façon suivante:

typedef struct telement{

int valeur;

struct telement * suivant;

} element;

typedef element * pile;

Implanter les opérations sur les piles.

Eléments de correction: deux solutions s'offrent à nous :

on ajoute les valeurs en fin de liste: d'un point de vue complexité, cela obligera à aller en fin de liste (et donc à parcourir la liste du début à la fin) pour les opérations empiler, dépiler et sommet

on ajoute les valeurs en début de liste: d'un point de vue complexité, les opérations empiler, dépiler et sommet se font en temps constant puisqu'il suffit de travailler sur le début de la liste. C'est donc la solution que nous allons adopter.

Exercice 3 type abstrait de données : file d'entiers

Nous allons représenter les piles d'entiers par des listes chaînées. On rappelle le type abstrait de données vu en cours :

Sorte: File

Utilise : Element, Booléen

Opérations:

file_vide: ->File

ajouter: File x Element -> File

supprimer : File -> File

premier: File -> Element

est_vide: File -> Booléen

Propriétés:

enfiler(f,e) est définie si est_pleine(f) vaut Faux

défiler(f) est définie si est_vide(f) vaut Faux

premier(f) est définie si est_vide(f) vaut Faux

si est_vide(f) == Vrai alors premier(enfiler(f,e))==e

si est_vide(f) == faux alors premier(enfiler(f,e))==premier(f)

si est_vide(f) == Vrai alors défiler(enfiler(f,e))==file_vide

si est_vide(f) == faux alors défiler(enfiler(f,e))==enfiler(defiler(f),e)

Question 1:

Dans un premier temps, on envisage de représenter les file par des listes chaînées. Proposez les algorithmes correspondants et évaluez leur complexité en nombre de parcours d'éléments (on utilisera l'affectation d'une adresse comme opération fondamentale).

Eléments de correction:

l'ajout et la suppression se font à des bouts différents. Quelque soit la solution choisie, l'une de ces opérations nécessitera d'aller en fin de liste ce qui nécessite de parcourir toute la liste.

Question 2

On se propose de maintenir un pointeur qui désignera le dernier élément de la liste. Une file sera donc représentée par un élément du type suivant :

typedef struct tfile {

liste premier; // premier élément

liste dernier; // dernier élément

} file;

Expliquez en quoi cette représentation permettra d'améliorer la complexité des opérations sur les file et écrire l'implantation correspondante des opérations sur les files.

Eléments de correction:

pour éviter de parcourir toute la liste quand on a besoin d'agir en fin de liste, on mémorise l'adresse de la fin de liste. 2 solutions:

on supprime en fin de liste et on ajoute en début de liste: c'est une mauvaise solution car la suppression suppose de modifier le champ suivant de l'élément précédent l'élément à supprimer. Là, on a simplement l'adresse du dernier élément. Trouver l'adresse de l'élément précédent suppose de parcourir la liste (ou d'utiliser des listes doublement chaînées ce qui ne présente aucun avantage par rapport à la solution décrite ci-dessous). L'ajout en début de liste ne pose pas de problème.

on ajoute en fin de liste et on retire en début de liste: c'est la bonne solution car l'ajout nécessite de simplement modifier le champ suivant de l'élément de f in de liste. La suppression consistera à supprimer le premier élément (remplacer premier par premier->suivant et désallouer l'ancien premier élément)

On opte donc pour la seconde solution :

ajout: en fin de liste, on remplace dernier->suivant par l'adresse du nouvel élément. Si la file est vide (dernier->suivant n'a alors pas de sens), on crée simplement un élément vers lequel pointeront premier et dernier.

Suppression: on supprime l'élément de tête désigné par premier ce qui est maintenant de la routine.

D'un point de vue complexité, toutes les opérations sont en temps constant (Θ(1)).

Lorsque l'on supprime le dernier élément, on se retrouve avec une file vide. L'algorithme de suppression implique que dans ce cas, on aura premier==NULL. On peut se demander s'il est utile de faire en sorte que dernier soit aussi NULL. La réponse est NON car la fonction qui teste si une file est vide regarde simplement si premier == NULL.

TD No3

Exercice 1 arbres binaires

Question 1 : recherche

Ecrire un algorithme de recherche retournant l'adresse du noeud contenant une valeur e passée en argument et l'arbre vide dans le cas où l'élément n'est pas dans l'arbre.

Question 2 plus petit élément d'un arbre binaire

Ecrire un algorithme retournant l'adresse du noeud contenant la plus petite valeur d'un arbre binaire non vide.

Exercice 2 arbres binaires de recherche

Question 1 : exemples d'arbres binaires de recherche

Donnez tous les arbres binaires de recherche pouvant contenir les valeurs suivantes : 3; 6; 2; 7

Question 2 : exemple d'arbre binaire de recherche

Dessinez l'arbre binaire de recherche obtenu par ajout successif aux feuilles des éléments suivants: 10;12;7;14;16;15;4;9;8;5;3;2

Supprimez les éléments 15; 9 et 7 en utilisant l'algorithme vu en cours.

Ajoutez 9 à la racine de l'arbre obtenu.

Question 3 : appartenance/ajout

Ecrivez une version itérative de l'algorithme indiquant si une valeur e appartient à un arbre binaire de recherche a. Faire de même pour l'algorithme ajout un élément e aux feuilles d'un arbre a.

Question 4 : plus petit élément d'un arbre binaire de recherche non vide

Ecrire une version récursive et une version itérative d'un algorithme retournant l'adresse du noeud contenant la plus petite valeur d'un arbre binaire de recherche non vide.

Question 5 : successeur d'un élément donné

Le successeur d'un élément est la plus petite valeur qui lui est immédiatement supérieure. Ainsi, le successeur de 10 dans l'arbre de la question 2 est 12. Un parcours infixe d'un arbre binaire de recherche permet d'obtenir les éléments dans l'ordre croissant. En utilisant cette propriété, écrire un algorithme permettant d'obtenir l'adresse du noeud contenant le successeur d'un élément donné de l'arbre et arbreVide si l'élément n'a pas de successeur. Quelle est la complexité au pire de votre algorithme en nombre de comparaisons d'éléments ?

Question 6 : successeur d'un élément donné

Dans cette question (et seulement dans cette question), on suppose que le type noeud contient aussi un lien vers le père d'un noeud qui vaudra arbreVide() pour la racine de l'arbre.

Ajoutez ces liens sur le dessin d'arbre de la question 2

Définisssez les types noeuds et arbre correspondants

adaptez l'algorithme d'ajout aux feuilles à cette nouvelle définition des types.

Proposez un algorithme permettant de déterminer l'adresse du noeud contenant le successeur d'un élément de l'arbre plus efficace que celui proposé en question 5. On pourra envisager deux cas de figures illustrés par le successeur de 7 et celui de 9 dans l'arbre donné en question 2. Quelle est la complexité au pire (en nombre de comparaisons d'éléments) de votre algorithme.

Question 7 : code positionnel d'un élément dans l'arbre

A tout élément de l'arbre, on peut associer une chaîne de 0 et de 1 indiquant le chemin de la racine à l'élément dans l'arbre de la façon suivante :

la chaîne se lit de gauche à droite

si on rencontre un 0, on va sur le sous-arbre droit

si on rencontre un 1, on va sur le sous-arbre gauche

quand la chaîne est vide, on doit être arrivé à l'élément

Ainsi, dans l'arbre de la question 2, le code positionnel de 8 est 010.

Donnez le code positionnel de 5 dans l'arbre de la question 2.

Ecrire un algorithme permettant de trouver le code positionnel d'un élément donné. Inversement, écrire un algorithme retournant l'adresse du noeud désigné par un code positionnel donné.

Question 8 : successeur d'un élément donné

Proposez un algorithme tirant partie de la question 7 et permettant de déterminer l'adresse du noeud contenant le successeur d'un élément donné dans le cas où les noeuds ne contiennent pas de lien vers leur père. Quelle est sa complexité au pire en nombre de comparaisons d'éléments ?

TD No3

Exercice 1 arbres binaires

Question 1 : recherche

Ecrire un algorithme de recherche retournant l'adresse du noeud contenant une valeur e passée en argument et l'arbre vide dans le cas où l'élément n'est pas dans l'arbre.

Eléments de correction:

sans ordre sur les éléments de l'arbre, il n'est pas possible de prévoir à l'avance le sous-arbre où chercher l'élément. Ainsi, si l'on ne le trouve pas dans l'un des sous-arbres, il faut aller voir s'il n'est pas dans l'autre.

arbre recherche(int e, arbre a){

if (estVide(a))

return arbreVide();

else if (a->valeur == e)

return a

else {

arbre atmp=recherche(e, a->gauche);

if (estVide(atmp))

atmp=recherche(e, a->droit);

return atmp;

}

}

Question 2 plus petit élément d'un arbre binaire

Ecrire un algorithme retournant l'adresse du noeud contenant la plus petites valeur d'un arbre binaire non vide.

Eléments de correction:

Même problème que pour la recherche: il faut regarder dans le sous-arbre gauche et dans le sous-abre droit. L'algorithme compare la valeur de la racine avec le min du sag,avec le min du sad et retourne la plus petite des trois valeurs.

D'un point de vue programmation, écrire une expression de la forme « a->qqc » suppose que a ne soit pas nul. A chaque fois que l'on écrit une telle expression, il faut se demander si a peut être nul.

arbre min(arbre a){

int m,tmp;

assert(! EstVide(a));

m = a-> valeur;

if (! estVide(a->gauche)){

tmp=min(a->gauche);

if (tmp < m)

m=tmp;

}

if (! estVide(a->droit)){

tmp=min(a->droit);

if (tmp < m)

m=tmp;

}

return m;

}

Exercice 2 arbres binaires de recherche

Question 1 : exemples d'arbres binaires de recherche

Donnez tous les arbres binaires de recherche pouvant contenir les valeurs suivantes : 3; 6; 2; 7

Eléments de correction:

Racine 2: 5 arbres

Racine 3: 2 arbres

Racine 6: 2 arbres

Racine 7: 5 arbres

Question 2 : exemple d'arbre binaire de recherche

Dessinez l'arbre binaire de recherche obtenu par ajout successif aux feuilles des éléments suivants: 10;12;7;14;16;15;4;9;8;5;3;2

Supprimez les éléments 15; 9 et 7 en utilisant l'algorithme vu en cours.

Elément de correction:

on a à supprimer :

une feuille (15)

un noeud interne au sens large ayant un seul fils

un noeud interne ayant deux sous-arbres (dans ce cas, on échange la valeur avec celle du min de son sad ou celle du max de son sag)

Ajoutez 9 à la racine de l'arbre obtenu.

Eléments de correction:

on applique l'algorithme de coupure sur cet exemple.

Question 3 : appartenance/ajout

Ecrivez une version itérative de l'algorithme indiquant si une valeur e appartient à un arbre binaire de recherche a. Faire de même pour l'algorithme ajout un élément e aux feuilles d'un arbre a.

Eléments de correction:

int appartientIter(int e, arbre a)

{

while ((!estVide(a)) && (e != a->valeur)){

if (e <a->valeur)

a=a->gauche;

else

a=a->droit;

}

// 2 cas de sortie: soit a est vide, soit on a trouvé e

if (estVide(a))

return 0;

else return 1;

}

Question 4 : plus petit élément d'un arbre binaire de recherche non vide

Ecrire une version récursive et une version itérative d'un algorithme retournant la plus petite valeur d'un arbre binaire de recherche non vide.

Eléments de correction:

l'ordre sur les éléments nous dispense de chercher dans les deux sous-arbres. En fait, on a même mieux, l'ordre sur les éléments nous permet de trouver le plus petit élément sans aucune comparaison d'éléments: le plus petit élément, c'est celui qui est le plus à gauche.

int min(arbre a)

{

assert( ! estVide(a));

if (estVide(a->gauche))

return a->valeur;

else return min(a->gauche);

}

// version itérative

int minIter(arbre a)

{

assert( ! estVide(a));

while ( ! estVide(a->gauche))

a=a->gauche;

return a->valeur;

}

Question 5 : successeur d'un élément donné

Le successeur d'un élément est la plus petite valeur qui lui est immédiatement supérieure. Ainsi, le successeur de 10 dans l'arbre de la question 1 est 12. Un parcours infixe d'un arbre binaire de recherche permet d'obtenir les éléments dans l'ordre croissant. En utilisant cette propriété, écrire un algorithme permettant d'obtenir l'adresse du noeud contenant le successeur d'un élément donné de l'arbre et arbreVide si l'élément n'a pas de successeur. Quelle est la complexité au pire de votre algorithme en nombre de comparaisons d'éléments ?

Eléments de correction:

Il faut parcourir l'arbre et s'arrêter juste après avoir rencontré l'élément e. Pour cela, on va déterminer une valeur « trouve » qui vaudra: 0 quand on n'a pas encore rencontré e, 1 quand on vient de recontrer e et 2 quand on a trouvé le successeur de e.

D'un point de vue complexité, c'est celle d'un parcours infixe qui s'arrête dès que l'élément cherché est trouvé. La complexité au pire est donc celle du parcours infixe : complexité linéaire par rapport au nombre d'éléments de l'arbre.

//////////////////////////////////////////////////////////////////////////////

// Nom : successeurParcoursInfixeAux

//

// Arguments : un element e, un arbre a

//

//

// retourne : res le successeur de e dans a (passé par valeur)

// trouve qui vaut :

// + 2 si on a déjà trouvé le successeur

// + 1: si l'élément précédemment vu est e

// + 0: dans les autres cas

//

void successeurParcoursInfixeAux(int e, arbre a, int * res, int * trouve){

if (! estVide(a)){

if (! estVide(a->gauche))

successeurParcoursInfixeAux(e, a->gauche, res, trouve);

if (*trouve == 1){

*res = a-> valeur;

*trouve=2;

}else if (a->valeur == e)

*trouve = 1;

if ((*trouve != 2) && (! estVide(a->droit)))

successeurParcoursInfixeAux(e, a->droit, res, trouve);

}

}

//////////////////////////////////////////////////////////////////////////////

// Nom : successeurParcoursInfixe

//

// Arguments : un element e et un arbre a

//

// retourne : le successeur de e dans a

//

// l'élément e doit appartenir à a et y avoir un successeur

int successeurParcoursInfixe(int e, arbre a){

int res=-1, t=0;

successeurParcoursInfixeAux(e,a,&res, &t);

assert(t == 2);

return res;

}

Question 6 : successeur d'un élément donné

Dans cette question (et seulement dans cette question), on suppose que le type noeud contient aussi un lien vers le père d'un noeud qui vaudra arbreVide() pour la racine de l'arbre.

Ajoutez ces liens sur le dessin d'arbre de la question 1

Définisssez les types noeuds et arbre correspondants

adaptez l'algorithme d'ajout aux feuilles à cette nouvelle définition des types.

Proposez un algorithme permettant de déterminer l'adresse du noeud contenant le successeur d'un élément de l'arbre plus efficace que celui proposé en question 2. On pourra envisager deux cas de figures illustrés par le successeur de 7 et celui de 9 dans l'arbre donné en question 1. Quelle est la complexité au pire (en nombre de comparaisons d'éléments) de votre algorithme.

Eléments de correction:

Pour permettre les parcours d'un noeud jusqu'à la racine, on prendra comme convention que la racine de l'arbre a l'arbre vide comme père. On pourra écrire des choses de la forme:

while (! estVide(a->pere)){

traitement sur le noeud;

a=a->pere;

}

La contrepartie est que cette propriété ne sera pas valable pour un sous-arbre car son champ père n'est pas nul. On pourra remplacer ce critère d'arrêt par une comparaison avec la racine de l'arbre (qu'il aura alors fallu préserver):

// a désigne l'adresse du noeud courant

// racine désigne l'adresse de la racine de l'arbre

while (a != racine){

traitement sur le noeud;

a=a->pere;

}

Pour tenir compte de la modification de structure, on va

modifier la fonction cree_noeud de façon à ce qu'elle aie un argument supplémentaire contenant le père du noeud à créer

faire en sorte que la fonction d'ajout aux feuille aie le père du noeud courant comme argument : cette fonction sera une fonction auxiliaire qui fera le travail

la fonction ajoute_feuille appellera la fonction ajoute_feuilleAux avec les paramètres ad hoc (notamment le père de la racine de l'arbre).

Algo d'ajout aux feuilles:

arbre cree_noeud(int e, arbre fg, arbre, arbre p)

{

arbre a=malloc(sizeof(noeud));

assert(a != NULL);

a->valeur=e;

a->gauche=fg;

a->droit=fd;

a->pere=p;

return a;

}

arbre ajoute_feuilleAux(int e, arbre a, arbre p)

{

if (estVide(a))

a=cree_noeud(e,NULL, NULL,p);

else

if (e<a->valeur)

a->gauche=ajoute_feuilleAux(e,a->gauche,p);

else if (e> a->valeur)

a->droit=ajoute_feuilleAux(e,a->droit,p);

return a;

}

arbre ajoute_feuille(int e, arbre a){

if (estVide(a))

return ajoute_feuilleAux(e, a, arbreVide());

else return ajoute_feuilleAux(e, a, a->pere);

}

Successeur: nous allons tirer partie du fait que l'on a affaire à des arbres binaires de recherche. On peut montrer que les éléments plus grands que la valeur v d'un noeud se définissent récursivement de la façon suivante :

les éléments de son sous-arbre droit

en remontant vers la racine: la valeur anc du premier noeud où l'on remonte par la gauche (i.e.: v appartient au sous-arbre gauche de anc) et toutes les valeurs supérieurs à anc.

anc

sad

...

v

sag sad

Les valeurs du sous arbre droit de v sont inférieures à anc car elles sont dans le sous-arbre gauche de anc. Le successeur de v est donc :

si le noeud a un sous-arbre droit, le successeur est le min de ce sous-arbre.

Si le noeud n'a pas de sous-arbre droit, on remonte jusqu'à trouver un noeud où on arrive par la gauche. Le successeur est la valeur de ce noeud.

L'algorithme suivant utilise cette propriété:

(ràf: rédaction à finir)

Question 7 : code positionnel d'un élément dans l'arbre

A tout élément de l'arbre, on peut associer une chaîne de 0 et de 1 indiquant le chemin de la racine à l'élément dans l'arbre de la façon suivante :

la chaîne se lit de gauche à droite

la racine a 1 comme code

si on rencontre un 0, on va sur le sous-arbre droit

si on rencontre un 1, on va sur le sous-arbre gauche

quand la chaîne est vide, on doit être arrivé à l'élément

Ainsi, dans l'arbre de la question 1, le code positionnel de 8 est 1010.

Donnez le code positionnel de 5 dans l'arbre de la question 1.

Ecrire un algorithme permettant de trouver le code positionnel d'un élément donné. Inversement, écrire un algorithme retournant l'adresse du noeud désigné par un code positionnel donné.

Elément de correction:

Pour stocker le code d'un élément, nous allons supposer que nous disposons d'une structure de données linéaire permettant un ajout et une suppression à la fin, un affichage des éléments du début à la fin.

Ràf: donner le TAD correspondant

le code C correspondant :

//////////////////////////////////////////////////////////////////////////////

// Nom : construitCode

//

// Arguments : une valeur e, un arbre a

//

// retourne : un tableau t (passé par adresse) qui contiendra le code de

// l'élément dans a

// si l'élément n'est pas dans a, le code est celui qu'il

// aurait après insertion aux feuilles

void construitCode(int e, arbre a, tableau * t){

if ( ! estVide(a)){

if (e < a-> valeur){

tableau_ajouterFin(0,t);

construitCode(e, a->gauche, t);

}

else if (a->valeur < e){

tableau_ajouterFin(1,t);

construitCode(e, a->droit, t);

}

}

}

//////////////////////////////////////////////////////////////////////////////

// Nom : afficheCode

//

// Arguments : un tableau t contenant le code d'un élément

//

// Fait: affiche le contenu de t du début à la fin

// rien si t est vide

// l'affichage est suivi d'un saut de ligne

void afficheCode(tableau t){

int cb;

printf("1"); // la racine

for (cb=0; cb < tableau_taille(t); cb++)

printf("%i",tableau_ieme(cb,t));

printf("\n");

}

//////////////////////////////////////////////////////////////////////////////

// Nom : NoeudCode

//

// Arguments : un arbre a, un tableau t contenant le code d'un élément de l'arbre

//

// retourne : l'adresse du noeud de l'arbre ayant t comme code

// si aucun élément n'a t comme code, retourne l'arbre vide.

arbre noeudCode(arbre a, tableau t){

int cb=0;

while ((! estVide(a)) && (cb <tableau_taille(t))){

if (tableau_ieme(cb,t)==0)

a=a->gauche;

else a=a->droit;

cb ++;

}

return a;

}

//////////////////////////////////////////////////////////////////////////////

// Nom : valeurCode

//

// Arguments : un arbre a, un tableau t contenant le code d'un élément de

// l'arbre

//

// retourne : la valeur de l'élément de a ayant t comme code

//

// pre-condition: il doit y avoir un élément ayant le code t

int valeurCode(arbre a, tableau t){

arbre n=noeudCode(a,t);

assert( ! estVide(n));

return n->valeur;

}

Question 8 : successeur d'un élément donné

Proposez un algorithme tirant partie de la question 7 et permettant de déterminer l'adresse du noeud contenant le successeur d'un élément donné dans le cas où les noeuds ne contiennent pas de lien vers leur père. Quelle est sa complexité au pire en nombre de comparaisons d'éléments ?

Eléments de correction:

La complexité est en O(h) car on fait un parcours pour trouver le code de l'élément et, suivant le cas:

soit on trouve le min du sag (ce qui revient à finir la hauteur de l'arbre commencée en cherchant le code de l'élément),

soit on parcourt le code jusqu'à trouver un 1 (remontée par la gauche, cf question 6) puis le code résultant par la droite pour trouver l'élément correspondant de l'arbre. Au pire, on fait 3 * hauteur(a) parcours

Dans tous les cas, on est en O(h).

Dans le second cas, il est possible de mémoriser le dernier élément situé en haut d'un sous arbre gauche ce qui éviterait le parcours du code et la recherche de l'élément correspondant. Cela suppose de ne pas utiliser construitCode mais de faire un travail adapté dans successeur. Cette amélioration qui ne change pas l'ordre de grandeur de la complexité est laissé en exercice.

int successeur(int e, arbre a){

tableau t=tableau_tableauVide();

arbre ae;

construitCode(e, a, &t);

ae=noeudCode(a, t);

assert(! estVide(ae));

if (! estVide(ae->droit))

return min(ae->droit);

else {

while((! tableau_estVide(t)) && (tableau_ieme(tableau_taille(t)-1, t)==1))

tableau_supprimerFin(&t);;

if (tableau_taille(t) >0)

tableau_supprimerFin(&t);

return valeurCode(a,t);

}

}

TD No4

Exercice 1 tri fusion

Question 1 : exemple

Appliquez l'algorithme du tri fusion vu en cours sur la liste linéaire suivante: 56,4,6,2,7,8,3,1,7,12

Question 2 couper une liste en deux

Dans la suite de cet exercice, les listes linéaires seront représentées par des listes chaînées. Ecrire une fonction C permettant de répartir les éléments d'une liste l dans deux listes l1 et l2 dont la taille diffère d'au plus 1.

Question 3 fusion de listes triées

Ecrire une fonction ayant deux listes triées l1 et l2 comme arguments et retournant la liste obtenue en fusionnant l1 et l2. Votre fonction doit faire la fusion sur place en utilisant directement les éléments de l1 et de l2.

Question 4 tri fusion

Ecrire le fonction triFusion qui applique l'algorithme du tri fusion à une liste.

Exercice 2 Listes de priorité

Question 1 : liste de priorités

Une liste de priorité est une structure de données contenant des objets ayant un champ priorité (un entier) et sur laquelle on peut réaliser efficacement les opérations suivantes :

Inserer(e, l): insére un élément dans la liste de priorité

max(l): Liste -> element: retourne l'élément qui a la plus grande priorité

extraireMax(l): supprime l'élément qui a la plus grande priorité et retourne sa valeur

Proposer une structure de donnée pour représenter les listes de priorité.

Question 2 : implantation

Implanter les opérations sur les listes de priorité en C.

Exercice 3 Tri rapide

Question 1 : algorithme

Le tri rapide est un algorithme dont le principe de fonctionnement est le suivant :

on choisit un élément appelé pivot dans la liste

on réorganise la liste de façon à ce que les éléments inférieurs au pivot soient avant le pivot et que ceux qui lui sont supérieurs soient après lui dans la liste.

On applique l'algorithme au deux partie de la liste (ceux avant et ceux après le pivot).

Quelle propriété vérifie la liste obtenue à la fin de l'algorithme ?

Question 2 : partition

Dans la suite de cet exercice, on suppose que les listes sont représentées par des tableaux. Ecrire une fonction partition ayant comme argument la partie de liste à traîter et le pivot et qui réorganise la liste en mettre les éléments plus petits que le pivot avant lui et les éléments plus grands après lui.

Question 3 : tri rapide

Ecrire le reste des fonctions nécessaires à l'implantation de cet algorithme.

Question 4 : complexité au pire

Déterminez la complexité au pire de cet algorithme.

Question 5 : tri rapide sur les listes chaînées

Cet algorithme est-il implantable efficacement sur les listes chaînées ?

Question 6 : choix du pivot

Si l'on connaît des informations sur les données, il est possible de choisir le pivot en fonction de ces informations. Dans chacun cas des cas suivants, indiquez le pivot que vous choisiriez en sachant que la liste à trier est déjà quasiment triée.

TD No4 (éléments de correction)

Exercice 1 tri fusion

Question 1 : exemple

Appliquez l'algorithme du tri fusion vu en cours sur la liste linéaire suivante: 56,4,6,2,7,8,3,1,7,12

Question 2 couper une liste en deux

Dans la suite de cet exercice, les listes linéaires seront représentées par des listes chaînées. Ecrire une fonction C permettant de répartir les éléments d'une liste l dans deux listes l1 et l2 dont la taille diffère d'au plus 1.

Eléments de correction:

On a plusieurs tactiques possibles. La plus simple consiste à déterminer la taille t de la liste et à mettre les t/2 premiers élément dans l1 et les éléments restants dans l2.

Voici l'algorithme correspondant:

int taille(liste l){

if (estVide(l))

return 0;

else return 1+taille(l->suivant);

}

void coupeEnDeux(liste l, liste * l1, liste * l2){

int t=taille(l), cb;

if ((estVide(l)) || (estVide(l->suivant))){ // 0 ou 1 élément

*l2=listeVide();

*l1=l;

} else{

liste ltmp=l;

*l1=l;

for (cb=0; cb < t/2-1; cb++)

ltmp=ltmp->suivant;

*l2=ltmp->suivant;

ltmp->suivant=listeVide();

}

}

Une alternative consiste à remarquer que l'on n'est pas obligé de couper la liste en son milieu mais que l'on peut répartir les éléments en parcourrant la liste : un élément dans l1, le suivant dans l2 et ainsi de suite. Si l=3;5;4;6;2;8 alors l1=3;4;2 et l2=5;6;8. Voici l'algorithme correspondant :

void coupeEnDeux(liste l, liste * l1, liste * l2){

if ((estVide(l))|| (estVide(l->suivant))) { // 0 ou 1 élément

*l2=listeVide();

*l1=l;

} else {

*l1=l;

l=l->suivant;

*l2=l;

l=l->suivant;

coupeEnDeux(l,&((*l1)->suivant), &((*l2)->suivant));

}

}

Question 3 fusion de listes triées

Ecrire une fonction ayant deux listes triées l1 et l2 comme arguments et retournant la liste obtenue en fusionnant l1 et l2. Votre fonction doit faire la fusion sur place en utilisant directement les éléments de l1 et de l2.

Éléments de correction: la fusion de liste triées est un algorithme classique vu en cours: pour déterminer le premier élément de la liste résultat, il suffit de comparer les premiers éléments de chacune des listes et de prendre le plus petit. Une implantation possible :

liste fusion(liste l1, liste l2){

if (estVide(l1))

return l2;

else if (estVide(l2))

return l1;

else {

if (l1->valeur < l2->valeur){

l1->suivant=fusion(l1->suivant, l2);

return l1;

} else {

l2->suivant=fusion(l1, l2->suivant);

return l2;

}

}

}

Dans la prochaine version de ce corrigé, il faudra inclure une version itérative (ràf).

Question 4 tri fusion

Ecrire le fonction triFusion qui applique l'algorithme du tri fusion à une liste.

Éléments de correction:

liste triFusion(liste l){

if ((estVide(l)) || (estVide(l->suivant)))

return l;

else {

liste l1, l2;

coupeEnDeux(l, &l1, &l2);

l1=triFusion(l1);

l2=triFusion(l2);

return fusion(l1, l2);

}

}

Exercice 2 Listes de priorité

Question 1 : liste de priorités

Une liste de priorité est une structure de données contenant des objets ayant un champ priorité (un entier) et sur laquelle on peut réaliser efficacement les opérations suivantes :

Inserer(e, l): insére un élément dans la liste de priorité

max(l): Liste -> element: retourne l'élément qui a la plus grande priorité

extraireMax(l): supprime l'élément qui a la plus grande priorité et retourne sa valeur

Proposer une structure de donnée pour représenter les listes de priorité.

Il nous faut étudier la complexité des opérations proposées sur les structures de données connues :

tableau non triés:

inserer: O(1) en nb d'affectations (affectation à la fin)

max: O(n) en nombre de comparaisons car il faut parcourir tout le tableau pour détermine le max

extraireMax: on trouve l'indice du max et on échange le contenu de la cellule avec la dernière du tableau: O(n) en nb de comparaisons, O(1) en nb d'affectations.

Tableaux triés:

inserer: au pire O(n) en nb d'affectations (il faut décaler les éléments situés après le point d'insertion) et O(log n) de comparaisons (recherche dichotomique)

max: O(1) car le max est à la fin

extraireMax: O(1) en nombre de comparaisons car le max est à la fin, idem pour les nombre d'affectations.

Arbres binaires de recherche équilibrés (AVL ou ~)

inserer: au pire O(long n) en nb de comparaisons si ajout au feuilles, 0(1) en nombre d'affectations.

max: O(long n) en parcours d'éléments car le max est tout à droite. Pas de comparaisons ou d'affectations.

extraireMax: O(long n) en nombre de parcours d'éléments, O(1) en nombre d'affectations car le noeud qui héberge le max n'a pas de fils droit.

Tas

inserer: au pire O(long n) comparaisons et affectations : on insère et on remonte en vérifiants à chaque fois si la propriété des tas est vérifiées. On va au pire jusqu'à la racine.

max: O(1): on retourne la valeur de la racine du tas;

extraireMax: O(long n) au pire en nombre de comparaisons et d'affectations: on échange la racine avec le dernier éléments et on vérifie que la propriété du tas est vérifiée en descendant.

Le tas est la structure de données choisie.

Question 2 : implantation

Implanter les opérations sur les listes de priorité en C.

éléments de correction :

// attention: le premier élément a l'indice 0 (et pas 1 comme dans le cours)

int pere(int n){

return (n+1)/2-1;

}

int filsg(int n){

return 2*(n+1)-1;

}

int filsd(int n){

return 2*(n+1);

}

int estNoeudTas(int n, tableau t){

return n < t.taille;

}

int indiceDuMax(int a, int b, tableau t){

if (t.tab[a]>t.tab[b])

return a;

else return b;

}

void ordonner (tableau * pt, int noeud){

int m=noeud;

if (estNoeudTas(filsg(noeud), *pt)){

m=indiceDuMax(m, filsg(noeud), *pt);

if (estNoeudTas(filsd(noeud), *pt))

m=indiceDuMax(m, filsd(noeud),*pt);

}

if (m != noeud){

echangeElemTab(pt, m, noeud);

ordonner(pt, m);

}

}

void ajouteElementTas(tableau * pt, int e){

int cb=pt->taille;

pt->tab[pt->taille]=e;

pt->taille++;

while (estNoeudTas(cb,*pt) && (pt->tab[cb]>pt->tab[pere(cb)])){

echangeElemTab(pt, cb, pere(cb));

cb=pere(cb);

}

}

Exercice 3 Tri rapide

Question 1 : algorithme

Le tri rapide est un algorithme dont le principe de fonctionnement est le suivant :

on choisit un élément appelé pivot dans la liste

on réorganise la liste de façon à ce que les éléments inférieurs au pivot soient avant le pivot et que ceux qui lui sont supérieurs soient après lui dans la liste.

On applique l'algorithme au deux partie de la liste (ceux avant et ceux après le pivot).

Quelle propriété vérifie la liste obtenue à la fin de l'algorithme ?

Elément de correction

Elle est triée. :-)

Question 2 : partition

Dans la suite de cet exercice, on suppose que les listes sont représentées par des tableaux. Ecrire une fonction partition ayant comme argument la partie de liste à traîter et le pivot et qui réorganise la liste en mettre les éléments plus petits que le pivot avant lui et les éléments plus grands après lui.

Éléments de correction:

/* */

/* placer : */

/* arguments : l'adresse du tableau, les indices des bornes du */

/* sous-tableau sur lequel on travaille. */

/* le pivot est le premier élément du sous-tableau */

int placer(tableau * t, int debut, int fin){

int i, s;

i=debut + 1;

s=fin;

while (i <= s) {

while (t->tab[s] > t->tab[debut]) s--;

while ((t->tab[i] <= t->tab[debut]) && (i <= t->taille)) i++;

if (i<s) {

echangeElemTab(t,i,s);

i+=1;

s-=1;

}

}

echangeElemTab(t,debut,s);

return s;

}

Question 3 : tri rapide

Ecrire le reste des fonctions nécessaires à l'implantation de cet algorithme.

Éléments de correction:

/* */

/* Le tri rapide */

/* */

/* */

void trirapideAux(tableau * t, int debut, int fin){

int indice_pivot;

if (debut < fin) {

indice_pivot=placer(t,debut,fin);

trirapideAux(t,debut,indice_pivot-1);

trirapideAux(t,indice_pivot+1,fin);

}

}

void triRapide(tableau * pt){

trirapideAux(pt, 0, pt->taille-1);

}

Question 4 : complexité au pire

Déterminez la complexité au pire de cet algorithme en nombre de comparaisons

éléments de correction:

Cas d'une liste déjà triée: complexité en n².

Question 5 : tri rapide sur les listes chaînées

Cet algorithme est-il implantable efficacement sur les listes chaînées ?

Éléments de correction:

ràf

Question 6 : choix du pivot

Si l'on connaît des informations sur les données, il est possible de choisir le pivot en fonction de ces informations. Indiquez le pivot que vous choisiriez en sachant que la liste à trier est déjà quasiment triée.

Éléments de correction: on prend l'élément qui est au milieu du tableau (indice taille/2).

TD No5: tas binomiaux

Exercice 1 arbres binomiaux

Un arbre binomial Bk est soit l'arbre vide, soit construit à partir de deux arbres de la forme Bk-1 en reliant la racine de Bk-1 à celle de l'autre arbre de la forme Bk-1 de la façon suivante:

Bk-1

Bk-1

Question 1 : exemples

Construisez B0, B1, B2, B3, B4 et indiquez le nombre d'élément de chacun de ces arbres. Donnez un exemple d'arbre binomial pouvant contenir exactement 32 éléments. Faites de même avec un arbre binomial pouvant contenir exactement 7 éléments.

Question 2 Propriétés de Bk

Montrez que l'arbre binomial Bk vérifie les propriétés suivantes :

il a 2k éléments

sa hauteur est k

la racine a k fils et c'est le seul sommet qui vérifie cette propriété

si l'on numérote les fils de la racine de droite à gauche, le premier est B0, le second est B1, le second est B2, ..., le dernier est Bk-1.

Question 3 fusion de deux arbres binomiaux

On représente les arbres binomiaux sous la forme d'un arbre binaire fils/freres de la façon suivante:

typedef noeud * arbreBinomial ;

typedef struct tnoeud {

arbreBinomial fils;

arbreBinomial frere;

arbreBinomial pere;

int valeur;

int degre;

} noeud;

Représentez graphiquement un arbre B4 en vous appuyant sur cette définition.

Ecrire une fonction qui fusionne deux arbre binomiaux h et b de même taille. La racine de h deviendra la racine de l'arbre obtenu. Votre fonction modifierea sur place les champs de h et de b. Elle ne modifiera pas le père de h.

Question 4 suppression d'un noeud d'un arbre binomial

Ecrire une fonction ayant l'adresse d'un noeud d'un arbre binomial comme argument qui supprime ce noeud de l'arbre auquel il appartient.

Exercice 2 Tas binomial

Un tas binomial est une forêt d'arbres binomiaux vérifiant les propriétés suivantes :

La valeur de chaque noeud de chaque arbre binomial est inférieure à la valeur de ses fils.

Les arbres binomiaux du tas sont tous d'ordre de taille différente

les arbres binomiaux sont triés par taille croissante.

On souhaite pour réaliser efficacement les opérations suivantes sur nos tas :

créer un tas vide

insérer un élément dans un tas

obtenir le minimum d'un tas

obtenir et supprimer le minimum d'un tas

réaliser l'union de deux tas

diminuer la valeur d'un élément d'un tas

supprimer un élément d'un tas

Question 1 : Exemples

Donnez des exemples de tas binomiaux à 8, 10 et 7 éléments. Montrez qu'un tas binomial a n éléments contient au plus E(log2n) arbres binomiaux.

Question 2 : implantation

On vous demande de proposer une représentation des tas binomiaux, de proposer les algorithmes permettant de réaliser les opérations suivantes et d'évaluer leur complexité:

création d'un tas binomial vide

obtention de la clef minimale

union de deux tas

ajout d'une clef

suppression de la clef minimale

diminution de la valeur d'une clef

suppression d'une clef

Question 3 : comparaison avec d'autres SD

Comparez la complexité de ces opérations avec celles sur les tas binaires vu dans le cadre du tri par tas.

TD No5: tas binomiaux (éléments de correction)

Exercice 1 arbres binomiaux

Un arbre binomial Bk est soit l'arbre vide, soit construit à partir de deux arbres de la forme Bk-1 en reliant la racine de Bk-1 à celle de l'autre arbre de la forme Bk-1 de la façon suivante:

Bk-1

Bk-1

Question 1 : exemples

Construisez B0, B1, B2, B3, B4 et indiquez le nombre d'élément de chacun de ces arbres. Donnez un exemple d'arbre binomial pouvant contenir exactement 32 éléments. Faites de même avec un arbre binomial pouvant contenir exactement 7 éléments.

Éléments de correction:

Un arbre binomial contient 2k éléments. Il ne peut donc exister d'arbres à 7 éléments. :-)

Question 2 Propriétés de Bk

Montrez que l'arbre binomial Bk vérifie les propriétés suivantes :

il a 2k éléments

sa hauteur est k

la racine a k fils

si l'on numérote les fils de la racine de droite à gauche, le premier est B0, le second est B1, le second est B2, ..., le dernier est Bk-1.

Éléments de correction:

ces propriétés se démontrent facilement par récurrence en s'appuyant sur la définitions des arbres binomiaux.

Question 3 fusion de deux arbres binomiaux

On représente les arbres binomiaux sous la forme d'un arbre binaire fils/freres de la façon suivante:

typedef noeud * arbreBinomial ;

typedef struct tnoeud {

arbreBinomial fils;

arbreBinomial frere;

arbreBinomial pere;

int valeur;

int degre;

} noeud;

Représentez graphiquement un arbre B4 en vous appuyant sur cette définition.

Ecrire une fonction qui fusionne deux arbre binomiaux h et b de même taille. La racine de h deviendra la racine de l'arbre obtenu. Votre fonction modifierea sur place les champs de h et de b. Elle ne modifiera pas le père de h.

Question 4 suppression d'un noeud d'un arbre binomial

Ecrire une fonction ayant l'adresse d'un noeud d'un arbre binomial comme argument qui supprime ce noeud de l'arbre auquel il appartient.

Exercice 2 Tas binomial

Un tas binomial est une forêt d'arbres binomiaux vérifiant les propriétés suivantes :

La valeur de chaque noeud de chaque arbre binomial est inférieure à la valeur de ses fils.

Les arbres binomiaux du tas sont tous d'ordre de taille différente

les arbres binomiaux sont triés par taille croissante.

On souhaite pour réaliser efficacement les opérations suivantes sur nos tas :

créer un tas vide

insérer un élément dans un tas

obtenir le minimum d'un tas

obtenir et supprimer le minimum d'un tas

réaliser l'union de deux tas

diminuer la valeur d'un élément d'un tas

supprimer un élément d'un tas

Question 1 : Exemples

Donnez des exemples de tas binomiaux à 8, 10 et 7 éléments. Montrez qu'un tas binomial a n éléments contient au plus E(log2n) arbres binomiaux.

Éléments de correction:

On peut faire un parallèle entre les arbres binomiaux composant un tas et la décomposition en base 2 du nombre d'éléments du tas. Ainsi:

8 = 23 donc le tas à 8 éléments est constitué du seul arbre B3

10 = 23 + 21 + 20 donc le tas à 10 éléments est constitué des arbres B0;B1;B3;

7 = 22 + 21 + 20 donc le tas à 7 éléments est constitué des arbres B0;B1;B2;

Si t= Bi, ..., Bk-1. Le nombre d'éléments n de t est supérieur au nombre d'éléments de Bk-1. On en déduit que 2k-1 ≤n et donc que log 2k-1 ≤ log n et donc que k-1≤ log n.

Comme on travaille avec des entiers, on en déduit: k < log n

Question 2 : implantation

On vous demande de proposer une représentation des tas binomiaux, de proposer les algorithmes permettant de réaliser les opérations suivantes et d'évaluer leur complexité:

création d'un tas binomial vide

obtention de la clef minimale

union de deux tas

ajout d'une clef

suppression de la clef minimale

diminution de la valeur d'une clef

suppression d'une clef

éléments de correction:

cf leicerson.

Question 3 : comparaison avec d'autres SD

Comparez la complexité de ces opérations avec celles sur les tas binaires vu dans le cadre du tri par tas.

TD No6: tables de hachage

Exercice 1 table de hachage: gestion des collisions par chaînage

Rappel de cours: dans une table de hachage, un élément e ayant une clef c est stocké à l'indice h(c). h est appelée fonction de hachage. Si la fonction h était injective (à deux éléments différents ont toujours des indices différents), l'accès à un élément se ferait en temps constant: le calcul de h(c).

En pratique, il n'est pas possible d'éviter que deux éléments aient le même indice. On parle alors de collision. L'une des méthode de gestion de collision appelée « gestion des collisions par chaînage » consiste à stocker dans le tableau des listes d'éléments plutôt que les éléments eux-même. Ainsi, dans la cellule numéro 4, on aura la liste des éléments dont l'indice (h(c)) vaut 4.

La complexité devient alors proportionnelle à la taille des listes.

Question 1 exemple

On considère la fonction de hachage: h(c) = m mod m avec m =11. Représentez l'état de la table de hachage après

l'ajout des clefs: 22;4;39;88;15;17;59;16

la suppression de 15

Simulez la recherche de 59 dans la table.

Question 2

Ecrire les algorithmes permettant d'ajouter, rechercher ou supprimer un élément dans une table de hachage en respectant les étapes suivantes :

donner les prototypes des fonctions travaillant sur les tables de hachage

donner les prototypes des fonctions utiles travaillant sur les listes chaînées

écrire les fonctions travaillant sur les tables de hachage

écrire les fonctions travaillant sur les listes chaînées

On utilisera les types suivants pour représenter les listes et les tables de hachage :

typedef struct telement {

int clef;

struct telement * suivant;

} element;

typedef element * liste;

typedef struct ttable {

int taille;

liste * tab;

}table;

Exercice 2 table de hachage: gestion des collisions par adresage ouvert

Une autre méthode de gestion des collisions utilisée lorsque l'on n'a pas la possibilité de gérer des listes chaînées consiste à stocker les éléments en collision ailleurs dans le tableau. On utilise alors une fonction h à deux arguments: h(c,i) avec i=nombre d'essais de placement déjà effectués. Ajouter un élément de clef c à la table revient alors à regarder sur la cellule d'indice h(c,0) est vide. Si c'est le cas, on y met l'élément. Dans le cas contraire, on essaie la cellule d'indice h(c,1), puis h(c,2), ...

Question 1 exemple

On considère la fonction de hachage: h(c,i) = (h'(c)+ i) mod m avec h'(c)= m mod m avec m =11. On vous demande de :

Représentez l'état de la table de hachage après l'ajout des clefs: 22;4;39;88;16;15;17;59;

Simuler la recherche de 59

Représentez l'état de la table de hachage après la suppression de 15

Simulez la recherche de 59

représentez l'état de la table après l'ajout de 27

Question 2

Ecrire les algorithmes permettant d'ajouter, rechercher ou supprimer un élément dans une table de hachage.

On utilisera les types suivants pour représenter les tables de hachage :

#define VIDE 0

#define PLEIN 1

#define DEJAOCCUPE 2

typedef struct telem{

int clef;

int statut; // vide, plein ou libre mais déjà occupé

typedef struct ttable {

int taille;

liste * tab;

}table;

Exercice 3 B-arbres

Question 1

Insérez les éléments suivants dans un arbre 2-3-4 (un arbre 2-3-4 est un B-arbre de degré minimal 2):

6, 30, 20; 15; 3; 35; 40; 42

IUP2-Miage-ASR	Structures de données	2004-2005

Pascal PETIT

2004-08-01T15:20:30

Pascal PETIT