Info306 TD 2

INF306 : Algorithmique
Fiche de TD #2
Exercice 1 : Arbres binaires

1. Ecrire trois algorithmes de parcours d’un arbre et appliquer pour afficher les informations contenues
dans les nœuds de l’arbre ci-dessous
2. Cet arbre est - il un arbre binaire de recherche ? justifier
3. Ecrire des algorithmes suivants et donner leur complexité en temps, pour chaque algorithme
appliquer le sur l’arbre ci-dessus :
a. calculer le degré de l’arbre
b. Afficher le chemin d'un nœud partant de la racine
c. Calculer la hauteur ou profondeur d'un arbre
d. Calculer la taille d'un arbre
e. Calculer le nombre de feuilles d’un arbre binaire
f. Vérifier qu’un arbre n’est pas dégénéré
g. Recherche une valeur dans un arbre binaire
Exercice 2: arbre binaire de recherche

1. Ecrire la procédure d’insertion d’un élément dans un arbre binaire de recherche
2. On veut trier un tableau T :
a. Ecrire l’algorithme du tri par insertion
b. Proposer un autre algorithme en utilisant un arbre binaire de recherche
c. Comparer les deux algorithmes
Exercice 3 : file de priorité

Une file de priorité f est un objet contenant des éléments ayant chacun une priorité représentée par un
nombre entier positif. On veut pouvoir effectuer les deux opérations suivantes de manière efficace : insérer(f,
x) qui ajoute un nouvel élément de priorité x dans la file f et supprimer(f) qui renvoie et supprime de la file
l’élément ayant la plus grande priorité.
Ecrire les algorithmes pour :
1. Représenter une file de priorité avec un tableau
2. Représenter une file de priorité avec une liste
Exercice 4 : Pièces de monnaies + algorithme glouton

On considère le problème où l'on doit rendre la monnaie pour x euros avec le moins possible de pièces de
monnaies.
1. On a des pièces de 1, 2, 5, 10. Ecrire l'algorithme glouton qui donne une solution optimale
2. On dispose d'un ensemble de pièces c0; c1; c2; … ; ck pour c > 1, et k≥ 1. écrire l'algorithme glouton
qui donne la solution optimale.
3. Donner un ensemble de pièces tel que l'algorithme glouton ne retourne pas une solution optimale.
4. Donner un ensemble de pièces tel que l'algorithme glouton ne trouve pas de solution.
5. Donne un algorithme qui retourne une solution optimale pour n'importe quel ensemble de pièces.
Exercice 5 : codage de Huffman + algorithme glouton

Le codage d’une chaine de caractères par la méthode de Huffman peut être à longueur fixe ou à longueur
variable. Le principe repose sur la création d'un arbre composé de nœuds où les feuilles représentent les
caractères composant la chaine. Soit à coder la chaine CH = « RECOMPENSER LE TRAVAIL ».
1 sur 2
1. Pour le codage à longueur à fixe, l’arbre ne peut pas être construit. Il suffit de trouver une
configuration binaire pour chaque caractère. Ecrire un algorithme qui prend en entrée une chaine de
caractères et met en sortie le codage (Huffman) des caractères de cette chaine. Quels sont les codes
des caractères de CH ?
2. Pour le codage à longueur variable, il faut construire l’arbre de Huffman par une technique
gloutonne.
a. Ecrire une procédure qui prend en entrée une chaine de caractères, et construit l’arbre de
Huffman pour le codage de ses caractères. Appliquer cet algorithme pour construire l’arbre de
codage de la chaine CH.
NB : utiliser les opérations écrites pour la file de priorité
b. Ecrire une procédure qui prend en entrée un arbre de Huffman, et affiche le code de chaque
caractère. Donner le code de chaque caractère de CH.
c. Donner la formule permettant de calculer la taille de l’espace occupé par le code de Huffman
d’une chaine de caractères
d. Le codage de Huffman est préfixe, écrire l’algorithme qui permet faire l’inverse du codage (à
partir du code binaire de Huffman de la chaine et du code de chaque caractère)
3. Comparer les deux approches (à longueur fixe et à longueur variable) en temps de construction du
code et en espace mémoire.
Exercice 6
On donne une expression arithmétique, en notation préfixée rangée dans une chaine de caractères, et
terminée par le caractère #. L’expression est supposée syntaxiquement correcte. Donner un
algorithme permettant de construire l’arbre représentant une expression.
Ecrire une fonction qui recherche un élément dans un arbre et retourne le pointeur sur cet élément.
Supposer que l’arbre est ordonné.
Exercice 7
On peut construire un vecteur d’enregistrement pour représenter un ABR.
1. Proposer une structure de données.
Pour chacune des procédures à écrire, calculer la complexité.
2. Ecrire la procédure permettant de créer un arbre avec cette structure.
3. Ecrire la procédure permettant de vérifier si une valeur est dans l’arbre
4. Proposer une procédure permettant de parcourir l’arbre et afficher ses éléments triés.
Exercice 8
Proposer un algorithme de tri ayant une complexité en O(nlogn) permettant de trier un vecteur
d’éléments. Indication : Utiliser un ABR dans la procédure.
Exercice 9
Donner sous forme d’un tableau la complexité des opérations suivantes sur les listes simples
linéaires, listes circulaires, listes doublement chainées.
1. Insérer un élément dans une liste
2. Supprimer un élément dans une liste
3. Inverser une liste
4. Concaténer deux listes
2 sur 2

Info306 TD 2

Transféré par

Droits d'auteur :

Formats disponibles

Info306 TD 2

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Info306 TD 2

Transféré par

Droits d'auteur :

Formats disponibles

INF306 : Algorithmique

Exercice 1 : Arbres binaires

Exercice 2: arbre binaire de recherche

Exercice 3 : file de priorité

Exercice 4 : Pièces de monnaies + algorithme glouton

Exercice 5 : codage de Huffman + algorithme glouton

Vous aimerez peut-être aussi