Exercices

Reconnaitre avec une pile les mots de {a,b}* de la forme anbn La pile est utilisée pour "compter" les a du début du mots (elle contient autant d'éléments qu'on a lu de a) , puis décompter les b qui suivent : function AnBn(mot: String):booléen {mot est de la forme anbn} PileVide(Char; p) // création de la pile i=1 /* on lit et on compte (avec la pile) les a en tête du mot */ while (i<=length(mot) && mot[i]=='a') empiler('x',p); i++ endw /* on lit et on décompte les b qui suivent ; on arrête de décompter si la pile est vide */ while (i<=length(mot) && mot[i]=='b' && !pileEstVide(p)) depiler(p); i++ endw // /* le mot est de la forme anbn ssi on est maintenant à la fin du mot (on a tout lu) et si la pile est vide (on a décompté autant de b qu'il y avait de a) */ return pileEstVide(p) & i==length(mot)

Reconnaitre avec une pile les mots de {a,b}* ayant autant de a que de b La pile est utilisée pour "compter" l'excédent de a ou de b dans la lecture du mot : à tout instant soit la pile est vide (on a lu autant de a que de b), soit elle contient des a (les a en excédent) soit elle contient des b (les b en excédent). Après la lecture complète du mot, la pile doit être vide si on a lu autant de a que de b. function Autant(mot: String):booléen {le mot contient autant de a que de b} PileVide(Char; p) for (i; 1; length(mot) /* parcours complet du mot */ case (pileEstVide(p)) empiler(mot[i],p); /* puisqu'à cet instant on a lu autant de a que de b, mot[i] est une lettre en excédent */ (sommet(p)==mot[i]) empiler(mot[i],p); /* on lit une lettre déjà en excédent : une de plus */ sinon dépiler(p) /* un caractère en excédent de moins */ endcase endfor return pileEstVide(p)

Exercices - 2001/2002 - 1 -

Reconnaitre avec une pile les mots de Dyck de {a,b}* Un mot de Dyck est un mot bien parenthesé : il a autant de a que de b, et tout préfixe possède au moins autant de a que de b. Un mot de Dyck restreint est une "expression" bien parenthesée : elle a autant de a que de b, et tout préfixe strict possède plus de a que de b. Variante du précédent. function Dyck(mot: String):booléen {le mot contient autant de a que de b} PileVide(Char; p) for (i; 1; length(mot) /* parcours du mot éventuellement interrompu par exit */ case (mot[i]=='a') empiler('a',p); /* il ne peut y avoir que des a en excédent */ (pileEstVide(p)) exit; /* puisqu'on a lu jusque là autant de a que de b, et qu'il y a maintenant un b, ce n'est pas un mot de Dyck */ sinon dépiler(p) /* un a excédentaire de moins */ endcase endfor return pileEstVide(p) & i=length(mot) /* on a pas utilisé exit */ function DyckRestreint(mot: String):booléen {le mot non vide contient autant de a que de b} PileVide(Char; p) i=1 Repeter case (mot[i]=='a') empiler('a',p); /* il ne peut y avoir que des a en excédent */ (pileEstVide(p)); /* on va arrêter */ sinon dépiler(p) /* un a excédentaire de moins */ endcase Jusque (pileEstVide(p) | i=length(mot)) /* on s'arrête quend la pile est vide ou qu'on a tout lu */ return pileEstVide(p) & i=length(mot) /* la pile ne doit être vide qu'à la fin */ Ou bien function DyckRestreint(mot: String):booléen {le mot non vide contient autant de a que de b} return mot[1]=="a" & mot[length(mot)]=="b" & Dyck(subString(mot,2,length(mot)-2))

Exercices - 2001/2002 - 2 -

Evaluer avec une pile une expression postfixée composée d'opérateurs binaires (pour simplifier). En exemple, l'expression infixée (2*3)+(5*((9*2)+(4*3))) est équivalente à l'expression préfixée + * 2 3 * 5 + * 9 2 * 4 3 . Dans cette dernière expression, les parenthèses ne sont pas nécessaires pour enlever l'ambiguïté. On peut la représenter par l'arbre : + * * 2 3

5

+ *

9 2

* 4 3

En inversant l'expression infixée, ou obtient l'expression préfixée 34*29*+5*32*+ On empile les opérandes : function EvalExpPost(exp: String): Decimal {valeur de l'expression à opérateurs binaire postfixée exp} PileVide(Decimal; p); c=1; while (c<=length(exp) while (exp[c]=' ') c++ endw /* on passe les espaces */ case /* de 3 choses l'une : */ (exp[c]='+') n=Pop(p)+Pop(p); empiler(n, p); c++ endif /* on additionne les deux derniers entiers lus et on empile le résultat */ (exp[c]='*') n=Pop(p)*Pop(p); empiler(n, p); c++ endif /* idem */ else /* on lit un opérande */ n=0; while (exp[c]>='0' & exp[c]<='9') n = 10*n + (ascii(exp[c])-ascii('0'); c++ endw; empiler(n, p) endcase endw retourn sommet(p)

Exercices - 2001/2002 - 3 -

Transformer avec une pile une expression infixée en expression postfixée. On suppose, pour simplifier, que l'expression est composée d'opérateurs binaires. Même exercice on supposant que les expressions infixées utilisent la préséance habituelle des opérateurs (^ puis */ puis +-) ; dans ces conditions par exemple, l'expression 2 + (3 ^2) * 4 est valide. function InfixToPostFix(exp: String): String PileVide(Char; p); String(e)="" /* expression calculée */ c=1; while (c<=length(mot) case (exp[c] in '0123456789') /* début d'opérande entier */ repeat e=e+exp[c]; c++ until (exp[c]<'0' | exp[c]>'9') e=e+' '; /* pour séparer les opérandes */ (exp[c] in '+-*/^') /* opérateur */ empiler(exp[c],p); c++; (exp[c]=')') e=e+pop(p); c++; /* on vient de lire ( opérande opérateur opérande +/ otherwise c++ /* en principe espace ou ( */ endcase endw if (!pileEstVide(p)) e=e+pop(p); retourn e

Avec la préséance function InfixToPostFix(exp: String): String PileVide(Char; p); String(e)="" /* expression calculée */ exp = exp + ')' empiler('(',p) c=1; while (c<=length(mot) case (exp[c] in '0123456789') /* début d'opérande entier */ repeat e=e+exp[c]; c++ until (exp[c]<'0' | exp[c]>'9') e=e+' '; /* pour séparer les opérandes */ (exp[c] in '+-*/^') /* opérateur */ while (!pileEstVide(p) && sommet(p)≥exp[c]) e=e+pop(p) endw /* on dépile les opérateurs de préséance supérieure */ empiler(exp[c],p); c++; (exp[c]='(') empiler('(',p); c++; /* pour noter le début de cet opérande */ (exp[c]=')') while !pileEstVide(p) && sommet(p)!='(' e=e+pop(p) endw otherwise c++ /* en principe espace */ endcase endw if (!pileEstVide(p)) e=e+pop(p); retourn e

Exercices - 2001/2002 - 4 -

Définir par une fonction elementPrésent l'opération qui teste si un élément de TypeElement appartient à une liste de TypeElement. Le principe est de faire un parcours partiel de la liste, en comparant l'élément visité à l'élément à trouver. Avec la constante placeNulle, cela donne : fonction elementPrésent (eltATrouver: T; l: Liste): Booléen {eltATrouver est présent dans la liste l} visiteur = premierePlace(l) /* si la liste est vide c'est placeNulle */ while (visiteur != placeNulle && contenu(visiteur) != eltATrouver) visiteur= placeSuivante(visiteur, l) /* c'est pas le bon contenu : on avance la visite */ endW return visiteur != placeNulle

Et sans : fonction elementPrésent (eltATrouver: T; l: Liste): Booléen {eltATrouver est présent dans la liste l} if (listeEstVide(l)) /* premierePlace n'est pas définie sur les listes vides */ return false else visiteur = premierePlace(l) repeat fin = (contenu(visiteur) == eltATrouver) | estDernierePlace(visiteur, l); if (!fin) visiteur= placeSuivante(visiteur, l) endif until (fin) return contenu(visiteur) == eltATrouver endif

On aurait aussi pu utiliser la fonction premiereOccurrence. Définir par une fonction premiereOccurrence l'opération qui retourne la première place contenant un élément de TypeElement dans une liste de TypeElement. Il faut envisager le cas où l'élément n'est pas dans la liste. Le principe est identique à celui de la recherche d'un élément dans une liste. Seul le resultat change. Avec la constante placeNulle, cela donne : fonction premièreOccurrence(eltATrouver: T; l: Liste): Place {la première place occupée par eltATrouver, ou placeNulle s'il n'est pas dans la liste} visiteur = premierePlace(l) while (visiteur != placeNulle && contenu(visiteur) != eltATrouver) visiteur= placeSuivante(visiteur, l) endW return visiteur Exercices - 2001/2002 - 5 -

Quand on ne dispose pas de placeNulle, on peut résoudre le cas où l'élément n'est pas dans la liste on construisant une procédure booléenne et en retournant dans un argument la place de la première occurrence : fonction premièreOccurrence(eltATrouver: T; l: Liste; p: Place): Booléen {si eltATrouver est dans la liste, p est la première place qu'il occupe, sinon la fonction retourne faux} if (listeEstVide(l)) return false /* pas de première occurrence */ else p = premierePlace(l) /* elle existe */ repeat fin = (contenu(p) == eltATrouver) | estDernierePlace(p,l); if (!fin) p = placeSuivante(p,l) endif until (fin) return contenu(p) == eltATrouver endif

Exercices - 2001/2002 - 6 -

Ecrire un algorithme pour purger une liste (on laisse dans la liste une seule occurrence de chaque élément) : a) en supposant que la liste est classée. Si la liste est classée, toutes les occurrences d'un même élément se suivent : procedure purgerListeClassee(l: liste) if (not estVide(l)) premOcc=premierPlace(l) /* visiteur qui se trouve successivement sur la première de tous les éléments présents dans la liste triée */ while (not estDernierePlace(premOcc,l)) /* il reste des elements non visités */ if (contenu(placeSuivante(premOcc,l),l)=contenu(premOcc,l)) supprimer(placeSuivante(premOcc,l),l) /* comme c'est écrit */ else /* il n'y a pas d'autres occurrence de l'élément visité par premOcc : on passe à la premiere occurrence suivante */ premOcc = pSuiv endif endw endif

b) en ne le supposant pas procedure purgerListeNonClassée(l: liste) if (not estVide(l)) premOcc=premierPlace(l) while (not estDernierePlace(premOcc,l)) /* on supprime les autres occurrences du contenu de premOcc (elles sont après */ posAvant = premOcc while (not estDernierePlace(posAvant,l)) if (contenu(placeSuivante(posAvant,l),l)=contenu(premOcc,l)) supprimer(placeSuivante(posAvant,l),l) else posAvant = placeSuivante(posAvant,l) endif endw /* on passe à l'élément suivant s'il existe */ if (not estDernierePlace(premOcc,l)) premOcc = placeSuivante(premOcc,l) endif endw endif

Exercices - 2001/2002 - 7 -

Définir les transformations utilitaires à l'aides des opérations primitives. fixerEtiquette(e, a) est équivalent à : a = consArbre(etiquette(racine(a)), sag(a), sag(a)) fixerSag(sa, a) est équivalent à : a = consArbre(etiquette(racine(a)), sa, sag(a)) arbreFeuille(e: TypeElement) est equivalent à : consArbre(e, arbreBinVide(TypeElement), arbreBinVide(TypeElement)) etiquette(a) est equivalent à etiquette(racine(a))

Egalité de deux arbres binaires étiquetés ; on supposera les étiquettes du même type, avec la fonction egalEtiq pour en tester l'égalité. On compare récursivement les étiquettes des racines, les sous-arbres gauches et droits, après avoir traité les cas particuliers : function egalArbre(a1, a2: ArbreBin): Bolean case (estVideArbre(a1)) return estVideArbre(a2) (estVideArbre(a2)) return false else return egal(etiquette(racine(a1)),etiquette(racine(a2))) && egalArbre(sag(a1), sag(a2)) && egalArbre(sad(a1), sad(a2)) endc

Un arbre complet de hauteur h possede 2h +1 -1 nœuds Le nombre de nœuds d'un arbre complet au niveau h est 2h (la démonstration par induction sur h est simple). Le nombre de nœuds est donc 1+2+…+2h = 2h+1-1 Montrer que si l’ordre hiérarchique d’un nœud n est i, le descendant direct gauche de n est d’ordre 2i et le descendant direct droit d’ordre 2i+1 • Un arbre complet de hauteur h possede 2h+1 -1 nœuds • Si n est au niveau h, son ordre i est égal au nombre de nœud d'un arbre complet de hauteur h-1 + le nombre r de nœuds à gauche de n au niveau h + 1 = 2h +r • De même l'ordre ig du successeur direct gauche ng de n s'écrit 2h+1+r' où r' nombre de nœuds à gauche de ng ; • comme r' vaut 2r on a ig = 2h+1 + 2r = 2*(2h +r) = 2i L'ordre id du successeur direct droit de n est 2h+1+r'+1=2*(2h+r)+1=2i+1

Exercices - 2001/2002 - 8 -

Montrer que la hauteur d'un arbre parfait de taille n est Ent(log2n) n est compris entre le nombre de nœuds de deux arbres complets de hauteur h-1 et h : 2h -1+1 ≤ n ≤ 2h+1-1 h ≤ log2 n < h+1 d'où la solution

Etablir une relation entre l'occurrence d'un nœud et son ordre hierarchique. Occurences d'un nœud. A chaque chaque nœud on associe son occurrence, occurrence un mot sur {0,1} qui décrit le chemin qui va de la racine au nœud : l'occurrence de la racine est le mot vide ; si m est l'occurrence de n, l'occurrence de son successeur direct gauche est m0, celle de son successeur direct droit est m1 Dans l'exemple n1

n2 n3

n6 n4

n7 n5

n9

n8

l'occurrence de n3 est 00, celle de n8 est 101. Soit h la hauteur de n, i son ordre hiérarchique et m son occurrence. Par définition i est égal au nombre de nœud d'un arbre complet de hauteur h-1 + le nombre r de nœuds à gauche de n au niveau h + 1= 2h +r Si on montre que le nombre représenté en base 2 par m est égal à r, on aura la relation : i = 2h + m Prouvons donc, par induction sur h, que m est égal à r : soit n un nœud au niveau h+1 • si ordre(n) est pair, c'est que n est le descendant direct gauche de p situé au niveau h, et on a donc par définition occurrence(n)=occurrence(p)0 , ce qui revient à multiplier occurrence(p) par 2 ; d'après l'hypothèse d'induction ( occurrence(p) = nombre de nœuds à gauche de p ), on a bien occurrence(n)=2*(nombre de nœuds à gauche de p)=nombre de nœuds à gauche de n ; • si ordre(n) est impair, on fait un raisonnement de même nature. On montre ailleurs que le niveau h d'un nœud d'ordre i est Ent(log2 i) ; on a donc la relation entre i et m : i = 2Ent(log2i) + m

Implémenter les opérations ajouterAuTas d'insertion et minEnleve de Exercices - 2001/2002 - 9 -

suppression dans un tas. ajouterAuTas(e: TypeElement; t: Tas) /* on insère e dans une nouvelle feuille */ n = feuilleAjoutée(e,t) /* on remonte le plus petit élément le long de la branche */ while(n != racine(t) && etiquette(ascendant(n)<etiquette(n)) echangerEtiquette(t,n,ascendant(n)); endw function minEnleve(t: Tas): TypeElement /* l'étiquette de la racine est un plus petit élément à retourner */ res = etiquette(t) /* on échange la racine et la dernière feuille */ echangerEtiquette(t,racine(t),dernièreFeuille(t)); /* on supprime cette dernière feuille */ supprimerDernièreFeuille(t) /* il faut maintenant descendre l'étiquette de la racine à sa place pour que t reste un tas */ if (not estVide(t)) n = racine(t) while (not estFeuille(n,t)) /* on cherche le plus petit successeur direct s */ if (succGauche(n,t)=dernierFeuille(t) || etiq(succGauche(n,t)) < etiq(succDroit(n,t)) s=succGauche(n,t) else s=succDroit(n,t) endif /* on échange s'il le faut */ if (etiquette(n)>etiquette(n)) echangerEtiquette(t,n,s) n = s else exit endif endw endif return res

Exercices - 2001/2002 - 10 -

Implémenter un tas de T avec un tableau de T. Il faut préciser : • comment on définit un nœud et ses successeurs • comment on définit les opérations sur les tas à l'aide de celles sur les tableaux. L'arbre binaire est organisé comme un tableau t de T. Un nœud est une ligne du tableau, représenté par son index ; l'étiquette du nœud i est t[i]. Les nœuds sont enregistrés dans le tableau selon leur ordre hiérarchique, et comme l'arbre est parfait, ils occupent les m premières lignes, m étant le nombre de nœuds du tas. Dans ces conditions, un tas est un tableau de T, plus un entier taille indiquant le nombre de nœuds. • TasVide(TypeElement, t) est donc défini (::) par TypeElement[tailleMax](t); taille=0 • arbreEstVide(t: Tas) :: taille == 0 • racine(t: Tas) :: 1 • etiquette(n: Nœud) :: t[n] • successeurGauche(n: Nœud) :: 2n • successeurDroit(n: Nœud) :: 2n+1 • estFeuille(n : Nœud) :: n > taille\2 • dernièreFeuille(t : Tas) :: taille • créerDernièreFeuille(e: TypeElement; t: Tas) :: taille++; t[taille] = e • supprimeDerniereFeuille(t: Tas) :: taille--

ajouterAuTas(e: TypeElement; t: Tas; taille: Integer) taille++; t[taille]=e /* on remonte le plus petit élément le long de la branche */ i=taille while(i>1 && t[i]
/* on échange s'il le faut */ if (t[n]>t[s]) echanger(t,n,s); n = s else exit endif endw return res

Montrer que si f est le nombre de feuilles d’un arbre et s le nombre de nœuds intérieurs, f ≤ s + 1 h=1 1 <= 0 +1 sinon a= (r, sag, sad) f=fg+fd s=sg+sd+1 mais comme la hauteur de fg et fd sont h-1 f=fg+fd<=sg+1+sd+1=s+1

Exercices - 2001/2002 - 12 -