TD.

Enoncé :

Réaliser les exercices suivants en faisant éventuellement les hypothèses supplémentaires qui vous paraîtrons pertinentes en les justifiant.

- Concevoir un algo qui permet d'éliminer toutes les répétitions dans une liste- Concevoir un algo qui permet de fusionner deux listes triées dans l'ordre croissant- Concevoir un algo pour déplacer des entiers contenus dans une pile p1 vers une pile p2 de façon à avoir tous les nombres pairs au dessus des nombres impairs- Concevoir un algo pour trier une file f1 dans une file f2. Créer les opérations intermédiaires qui vous paraîtrons nécessaires pour une bonne lisibilité

ConseilsTentez de mettre votre démarche de conception algorithmique en évidencehypothèse: un énoncé "doit" être interprété pour être traduit en algorithme.

Correction :

Fonction liste répétition (L)E/S

L : ListeDéclaration

i,j : entierDébut

Si longueur (L) = 0 ou longueur (L) = 1 alorsRetourner (L)

Sinoni1Tant que i < longueur (L) faire

ji+1Tant que j<= longueur (L)

Si Ième (L,j) = Ième (L,i) alorsLRetire_elmt (L,j)

Sinonjj+1

FinSiFinTqii+1

FinTqRetourner (L)

FinSiFin

Complexité de l’algo = 3+1+n*(1+2+n*(1+2)+2) = 4+n*(5+3n) = 4+5n+3n²

Perso :

Procedure Fusion (L1,L2,L3)E

L1,L2 : listeS

L3 : listeDeclaration

i,j,k : entireDébut

i1j1k1Tant que i<=longueur(L1) et j<=Longueur(L2) faire

Si Ième (L1,i) = Ième (L2,j) alorsL3[k]L1[i]L3[k+1]L2[j]jj+1ii+1kk+2

SinonSi Ième(L1,i) < Ième(L2,j) alors

L3[k]L1[i]ii+1

SinonL3[k]L2[j]jj+1

Finsikk+1

FinsiFintq

Gérer cas ou il reste des elements dans L1 ou L2.

Correction du TD :

Réaliser les exercices suivants en faisant éventuellement les hypothèses supplémentaires qui vous paraîtrons pertinentes en les justifiant.

- Concevoir un algo qui permet d'éliminer toutes les répétitions dans une liste- Concevoir un algo qui permet de fusionner deux listes triées dans l'ordre croissant- Concevoir un algo pour déplacer des entiers contenus dans une pile p1 vers une pile p2 de façon à avoir tous les nombres pairs au dessus des nombres impairs- Concevoir un algo pour trier une file f1 dans une file f2. Créer les opérations intermédiaires qui vous paraîtrons nécessaires pour une bonne lisibilité.

ConseilsTentez de mettre votre démarche de conception algorithmique en évidencehypothèse: un énoncé "doit" être interprété pour être traduit en algorithme.

**************************************************************************

Suggestion de correction

Pour l'ensemble des problèmes posés, l'exercice algorithmique consiste à savoir ou décider des "outils" qui seront utilisés pour résoudre le problème en fonction des contraintes que l'on voudra s'imposer pour celle qui ne sont pas explicitement posées dans l'énoncé (choix ou non d'une implémentation particulière, résolution à partir d'un jeu de primitives "fourni" pour le modèle de données, etc.). Ce sont, en général des critères de lisibilité et/ou de calcul de complexité qui permettent de prendre les décisions avant de réaliser l'écriture de l'algorithme proprement dit.

Des exemples variés de "solutions" ci-dessous

***************************************************************************

- Concevoir un algo qui permet d'éliminer toutes les répétitions dans une liste

Question 1: Est-il nécessaire de se préoccuper de l'implémentation ?

Les considérations d'implémentation ne sont ici importantes que si l'on considère que l'on peut mieux faire qu'une résolution quadratique. Ceci semble possible si l'on peut réaliser un tri entre les éléments de la liste. Or rien, dans l'énoncé ne précise que les éléments contenus dans la liste sont triables. Nous considèrerons donc de nous contenter d'une résolution algorithmique utilisant les primitives classiques vues en cours: ième, longueur, insérer, supprimer,

Remarque: on supposera également que l'on dispose d'une primitive qui permet de comparer deux éléments

compare(type_element e1, type_element e2)

Voici une suggestion en français d'un algorithme récursif pour résoudre le problème

Conception récursive:

Eliminer tous les doublons dans une liste c'est:si la liste est vide ou composée d'un seul élément

renvoyer la listesinon

renvoyer une liste dans laquelle on insèrera en tête l'élément plac2 en tête dans la liste en argument dans une liste résultat de l'appel récursif sur une liste dans laquelle on aura enlevé tous les 2léments identiques à l'élément placé en tête

Ce qui nécessite de pouvoir enlever un élément dans une liste

Enlever un élément e dans une liste c'est:si la liste est vide

renvoyer la listesinon

Si l'élément placé en tête est identique à l'élément e

renvoyer la liste résultat de l'appel récursif sur la liste privée de son premier élément

Sinonrenvoyer une liste dans laquelle on insèrera en tête

l'élément placé en tête dans la liste en argument dans la liste résultat de l'appel récursif sur la liste privée de son premier élément

En conclusion, pour faciliter la lisibilité, il est judicieux de créer les outils suivants à partir des primitives

inserer_en_tete(l,e) équivalent à insérer(l,e,1)supprimer_en_tete(l) equivalent ) supprimer(l,1) (attention, une précondition pour utiliser cette opération est que la liste doit être non vide)supprimer_element (description ci-dessus)

Les solutions qui utilisent une implémentation particulière conduisent à l'écriture d'une nouvelle primitive pour ce type d'implémentation. Dans ces cas là, on conclura en donnant la complexité de l'algorithme fourni.

**************************************************************************

- Concevoir un algo qui permet de fusionner deux listes triées dans l'ordre croissant

Mon interprétation de l'énoncé me conduit à décider que le problème consiste à créer une liste résultat à partir de deux listes fournies en argument. En effet, prendre la décision d'écraser une des listes fournie ne me paraît pas une solution pertinente au seul regard de devoir choisir arbitrairement laquelle.

Conditions dans lesquelles la solution est immédiate...Si une des deux listes est vide alors la solution consiste à renvoyer l'autre liste (même si elle est vide)Dans le cas général (aucune des deux listes n'est vide): renvoyer une liste dans laquelle on insère en tête le plus petit des deux éléments figurant en tête dans les deux listes fournies en argument dans une liste résultat de l'appel récursif sur les deux listes dont l'une aura été privée de l'élément placé en tête dans la liste résultat

complexité linéaire!

***************************************************************************

- Concevoir un algo pour déplacer des entiers contenus dans une pile p1 vers une pile p2 de façon à avoir tous les nombres pairs au dessus des nombres impairs

Nous considèrerons que nous disposons des primitives suivantes concernant les piles: creer_pile_vide,empiler,dépiler,sommet,pile_videet d'une fonction de test de parité: est_pairet d'une fonction booléenne de négation: non

Le plus simple semble ici d'utiliser une troisième pile p3 pour "faire le tri".On "vide" la pile p1 en plaçant l'entier au sommet dans p2 s'il est impair et dans p3 s'il est pair tant que celle-ci n'est pas vide... puis on "vide p3 dans p2".

Algo:

p3 <- creer_pile_vide()TantQue (non(pile_vide(p1))

Si est_pair(sommet(p1))empiler(p3,sommet(p1))

Sinonempiler(p2,sommet(p1))

depiler(p1)FinTantQueTantQue(non(pile_vide(p3))

empiler(p2,sommet(p3))depiler(p3)

FinTantQue

On pourra utiliser une variable locale pour éviter d'évaluer deux fois le sommet de p1. Notons toutefois que cela ne change pas la complexité de l'algorithme... qui est linéaire.À la fin de l'exécution de cette procédure, la pile p2 contient l'ensemble des entiers préalablement contenus dans p1 avec les nombres pairs "au dessus"

exemple d'exécution: si p1 contient (en partant du sommet): 9,8,7,6,5,4,3,2,1 et que p2 est vide au débutp2 contiendra à la fin de l'exécution (en partant du sommet): 8,6,4,2,1,3,5,7,9

**********************************************************************************

- Concevoir un algo pour trier une file f1 dans une file f2. Créer les opérations intermédiaires qui vous paraîtrons nécessaires pour une bonne lisibilité

Nous considèrerons que nous disposons des primitives suivantes concernant les files: creerFileVide,enfiler,défiler,premier,fileVide

et

d'une fonction defilerEnfiler qui prend deux files f1 et f2 en arguments et qui défile le premier élément de la première file et l'ajoute à la deuxième filed'une fonction qui permet de comparer le premier de deux files f1 et f2 et renvoie vrai si le premier de f1 est plus grand (ou égal) et faux sinon: compared'une fonction qui permet de permuter le contenu d'une file f1 dans une file f2: permuteFileet d'une fonction booléenne de négation: non

On s'adjoindra une file f3

Algo:

f3 <- creerFileVide()TantQue non(fileVide(f1))

TantQue non(fileVide(f2)) et que comparer(f1,f2)defilerEnfiler(f2,f3)

FinTantQuedefilerEnfiler(f1,f3)TantQue non(fileVide(f2))

defilerEnfiler(f2,f3)FinTantQuepermuteFile(f3,f2)

FinTantQue

Cours 5 – 17 Mars 2009.

Tri avec meilleur complexité : tri fusion.

Modèle de données non linéaires : Arbre

(Miss un bout)

Exemple et terminologie.- Chaque elmt d’un arbre est un nœud.- Les nœuds sont reliés les uns aux autres par une relation d’ordre

(hiérarchie).- Un nœud a un père (au plus).- Un nœud qui a au moins un fils est un nœud interne.

Exemple d’arbre :

RacineNœud interne Nœud interne Feuille

Feuille Feuille Nœud interneFeuille

L’arité d’un arbre est caractérisée par le nombre maximum de fils pour un nœud.On parle d’arbre n-aire.L’arité n’impose pas de nb minimum de fils (un nœud d’un arbre ternaire aura 0,1,2 ou 3 fils).Le degré d’un nœud est le nb de fils que possède ce nœud.

(miss un bout).

Usages :Arbre de décisionAnalyse syntaxiqueSystème de gestion de fichiersClassificationEtc …

Passage d’un arbre n-aire à un arbre binaire. Ex = arbre généalogique. Typer diférement les liens entre nœuds.

Ex = Fleche est ouest : 1er enfant Fleche ouest est : frère/sœur.

Taille d’un arbre : nb de nœuds internes (ou nœuds en général selon l’usage) qui le compose.Profondeur d’un nœud : la distance en termes de nœuds par rapport à la racine.Le nœud racine est de profondeur nulle par convention.

Hauteur d’un arbre : profondeur maximum de ces nœuds.C’est aussi le maximum de la hauteur de ses fils.La hauteur est un critère de « performance » pour un arbre.

Arbre localement complet : arbre dont chaque nœud a 0 ou 2 fils. Les nœuds internes auront dons tous 2 fils.Ex : Racine OKRacine Nœud Int Feuille OK

Feuille Feuille

Arbre dégénéré : un arbre dont les nœuds ne possèdent qu’un seul fils.Ex : ABCD

On appellera un arbre binaire complet un arbre qui est localement complet et dont toutes les feuilles on la même profondeur.On peut calculer la taille exacte d’un tel arbre en fonction de sa hauteur.

Ex = Racine Nœud int feuille feuille

Nœud int feuille feuille

H = hauteur de l’arbre. [Ici 2].Taille = ∑ (i=0 h) 2^i = 2^(h+1) - 1.La hauteur d’un arbre complet “est en “ lg n.

Un arbre est dit parfait si tous les niveaux sont remplis sauf éventuellement le dernier. Dans ce cas les feuilles doivent être groupées à « gauche ».

Si on appelle le fils gauche d’un arbre binaire le sous arbre gauche et réciproquement le fils droit d’un arbre binaire le sous-arbre droit, alors on pourra noter un arbre sous la forme suivante :

Arbre_vide Ou

<Nœud, sous-arbre gauche, sous-arbre droit>

Sorte : ArbreUtilise : Valeur NœudOpérations :

Arbre_vide : Arbre<-,-,-> : Nœud x Arbre x Arbre ArbreRacine : Arbre NœudGauche : Arbre ArbreDroit : Arbre ArbreContenu : Nœud Valeur

Avec A et B de sorte arbre et n de sorte nœud.Pré conditions :

Racine(A) est définie ssi A n’est pas videGauche (A) est défini ssi 1 n’est pas videDroit (A) est défini ssi A n’est pas vide

Axiomes :Racine (<n,A,B>) = nGauche (<n,A,B>) = ADroit (<n,A,B>) = B

Implémentation : dans un tableau ou avec une structure nœud. Le choix se fera svt en fonction de propriétés supplémentaires associées à des arbres.

TD (structure de données et primitives associés) : exemple du tas (ou file de priorité ou heap).

Un tas est un modèle de données qui permet de gérer une file d’attente … avec des priorités. Le modèle de données utilisé n’est pas linéaire et correspond à un arbre binaire ayant les propriétés suivantes :

Un tas nécessite qu’il existe un ordre sur les valeurs contenues dans la hiérarchie.

La valeur de chaque nœud est supérieure ou égale à celle de ses fils.C’est un arbre parfait.

Opérations supplémentaire pour tas :Insertion : Tas x Valeur TasSuppression : Tas Tas

Cf feuille pour exemples d’insertion et de supression.

Soit i la position d’un nœud. i rapport au niveau (racine niveau 0, ses fils niveau 1, petits fils niveau 2 rapport au 2^0 elmts au niveau 0, 2^1 au niveau 1, 2² au niveau 2, …)

Fils gauche : 2*iFils droit : (2*i)+1Père : i/2.

Structure pour un tas

Type_elmt tableau [MAXSIZE]

Struct tas {Int taille ;Type_elmt * tableau ;Int taille_max ; // correspond a la taille allouée au tableau.

}

Typedef struct tas * tas_p ; // def d’un type qui est un pointeur sur un tas.

Implémenté algo pour entasser, pour retirer le max.

Version perso :

Void Entasser (tas_p t, type_elmt e){

Int i,j ;Type_elmt Temp ;If (ttaille < ttaille_max){

(ttaille) ++ ;i = ttaille ;(ttableau[i]) = e ;j = i division euclidienne par 2 ;While ((ttableau[i]) > (ttableau[j]) && j > 0 )

‘ {Temp = (ttableau[j]);(ttableau[j]) = e;(ttableau[i]) = Temp ;i = j ;j = i division euclidienne par 2 ;

}}

}

Correction Mathon :

Préconditions : traitement de taille_max.Soit pos une variable pour la position d’insertion de l’élément e.Incrémentez la taille du tas.Initialisez pos à la taille du tas.Tant que l’élément à insérer e est supérieur à la valeur de son père [pos / 2] (s’il en existe un) : la valeur du père est placée à la position pos. La position pos devient celle du père.Fin Tant que.L’élément e est placé à la position pos..