Première année, S2
ISITCOM H-S
Département Informatique
Mohamed EL OUNI
TD—Algorithmique
et structure de
données et complexité
Classe : 1LM
Février 2021
1
Première année, S2
PREFACE
Ce fascicule des travaux dirigés d’algorithmique et structures de données et complexité est à l’intention
des étudiants de la première année en Licence (1LM + 1IOT).
Il aborde brièvement les thèmes les plus classiques et les plus utilisés en informatique : la récursivité,
les listes chainées, les piles, les files et les arbres binaires de recherche.
Le fascicule comporte 4 TD qui sont réparties comme suit :
TD1 : La récursivité
TD2 : Les pointeurs et Les listes chainées
TD3 : Les piles et les files
TD4 : Les arbres binaires de recherche
2
Première année, S2
Table des matières
TD n°1—La récursivité ………………………...................................................4
TD n°2-- Les pointeurs et Les listes chainées.............................................6
TD n°3 -- Les piles et les files ……………………………………………………7
TD n°4-- Arbre binaire de recherche.................................................................8
BIBLIOGRAPHIE ........................................................................................... 9
3
Première année, S2
TD1—La récursivité
Objectifs
- Résoudre des programmes récursifs.
- Comprendre la démarche de transformation d’un programme itérative en un programme
récursive.
- Savoir les avantages de l’utilisation de la récursivité pour résoudre les problèmes.
EXERCICE 1
1. On souhaite écrire une fonction récursive qui calcule le carré d'un entier. Pour trouver un lien entre
carre(n) et carre(n-1), on utilise la formule donnée en énoncé : (n + 1)2 = n2 + 2n + 1.
En changeant n en n -1.
2. On veut écrire une fonction récursive qui calcule la somme de 1 à un entier n : 1+2+3+ +(n -1) + n.
EXERCICE 2
On rappelle que les nombres de Fibonacci sont définis de la façon suivante :
F0=F1=1
Fn = Fn -1 + Fn -2 pour n≥2
1. On applique la définition :
F2= ? F3= ?, F4= ?, F5= ?.
2. Pour écrire une fonction récursive qui calcule le nième nombre de Fibonacci, il suffit d'utiliser
directement les formules de l'énoncé.
3. Comment écrire une fonction itérative (c'est-‡-dire sans appel récursif) qui calcule la même
chose ? On remarque que pour calculer Fn, il faut connaître Fn- 1 et Fn- 2. Mais pour avoir Fn- 2,
il faut connaître Fn -3 et Fn- 4 …
EXERCICE 3
On définit la fonction suivante :
Fonction McCarthy(n : Entier) : Entier
Debut
Si (n>100)
Alors Renvoyer(n-10)
Sinon Renvoyer(McCarthy(McCarthy(n+11)))
FinSi
Fin
1.Pour n > 100, McCarthy(n) ?
2.McCarthy(98) ?
3.En déduire la valeur de McCarthy(n) pour n ≤ 100. Expliquer.
4
Première année, S2
TD2—La récursivité
EXERCICE 4
Soit la fonction récursive suivante :
Fonction mystère (n, p : entier) : entier
Début
Si (p < 1) alors mystère <-- 0
Sinon mystère <-- n + mystère (n, p-1)
Finsi
Fin
1. Exécutez à la main la fonction mystère en laissant sur votre copie la trace de l’exécution pour les valeurs
respectives 5, 4 pour n et p.
2. Dites ce que fait l’algorithme de cette fonction.
3. Est-ce que la fonction peut être utilisée pour un entier positif et un entier négatif ?
4. Est-ce que la fonction peut être utilisée pour deux entiers négatifs ?
5. Proposez une solution itérative.
5
Première année, S2
TD2-- Les pointeurs et les listes chainées
Objectifs :
- Savoir déclarer, construire des listes chainées.
- Manipuler, traiter et apprendre à utiliser des listes chainées.
- Distinguer entre les différents types de listes chainées.
QUESTIONS DE COURS
1. Qu’est-ce qu’un pointeur ?
2. Quelle est la différence entre une structure de données statique et une structure de données dynamique ?
EXERCICE 1
Soit une liste d’entiers L, écrire les actions paramétrées suivantes permettant :
1- Le calcul du nombre d’éléments, et la détermination du maximum et du minimum ;
2- L’insertion d’une valeur val donnée dans une liste triée ;
3- La suppression des doublons (éléments identiques) ;
4- La création de la liste miroir de L (avec ensuite sans création d’une nouvelle liste) ;
5- La duplication d’une liste au début / à la fin;
6- La fusion de deux listes triées d’entiers L1 et L2 en une liste triée L3 ;
EXERCICE 2
Soit T un tableau de 26 listes de chaînes de caractères. La liste 1 contient des mots commençant par la lettre
‘A’, la liste 2 contient des mots commençant par la lettre ‘B’…etc.
Déclarer T et écrire une Fonction permettant de vérifier l’existence d’un mot M dans la structure.
EXERCICE 3
Soient deux listes L1 et L2 de valeurs entières positives :
Ecrire une action paramétrée permettant de déplacer (sans allocation ni libération) les valeurs paires de L1
vers L2, et de déplacer les valeurs impaires de L2 vers L1 ;
EXERCICE 4
1. Écrire la procédure AjouterTete qui permet d’ajouter au début d’une liste circulaire L un entier e.
2. Écrire la procédure AjouterFin qui permet d’ajouter à la fin d’une liste circulaire L un entier e.
3. Écrire une procédure Affiche qui affiche la liste circulaire qui lui est passée en argument.
6
Première année, S2
TD5-- Les piles et les files
Objectifs :
- Définir et manipuler une pile et une file
- Savoir différencier entre la structure d’une pile et la structure de celle d’une file.
QUESTIONS DE COURS
1. Rappeler la définition d’une pile et donner les contraintes d’accès à cette dernière.
2. Rappeler la déclaration d’une pile est ces modules de manipulation.
3. Qu’est-ce qu’une file. Présenter un graphe illustrant l’accès à cette derrière.
4. Rappeler la déclaration d’une file est ces modules de manipulation.
EXERCICE 1
Copie d’une pile Ecrire une fonction pile_copy(s) recevant une pile (s) comme argument et renvoyant une copie s2
de s. Attention, la pile s doit (bien sûr) être conservée ! Evaluer le coût en mémoire et le nombre d’opérations de la
fonction.
EXERCICE 2
Ecrire une fonction pile_reverse recevant une pile (s) comme argument et renvoyant une copie inversée rs de s.
Attention, la pile s doit être conservée ! Evaluer le coût en mémoire et le nombre d’opérations de la fonction.
EXERCICE 3
Permutations circulaires (acte 1) Ecrire une fonction pile_circperm qui reçoit en argument une pile s et un entier n et
effectue sur la pile n permutations circulaires successives. Dans cet exercice, c’est la pile s elle-même qui sera
modifiée.
Exemple avec n=2 : 7 - 11 – 98 – 2 -103 donnera 97- 2- 103 -7 -11 Evaluer le coût en mémoire et le nombre
d’opérations de la fonction.
EXERCICE 4
Permutations circulaires Reprendre les exercices 1 et 3 de la partie « Piles » mais en traitant cette fois le cas d’une
file.
7
Première année, S2
TD6-- Arbre binaire de recherche
Objectifs :
- Définir, créer et manipuler un arbre binaire de recherche.
- Savoir comment parcourir un arbre binaire de recherche ?
- Trouver un élément dans un arbre.
- Savoir passer d’une structure dynamique d’un arbre vers une structure statique représentée par un
vecteur.
- Savoir fusionner deux arbres.
- Connaitre les différents types d’arbres : dégénéré, complet ou parfait.
QUESTIONS DE COURS
1. Qu’est-ce qu’un arbre binaire de recherche ?
2. Quel est le nombre minimal des nœuds que peut avoir un arbre binaire de recherche à 5 niveaux ?
3. Combien y a-t-il de formes d’arbres binaire différents à (respectivement) 1, 2, 3, 4 nœuds.
EXERCICE 1
Considérer l’ensemble des clés 1, 4, 5, 10, 16, 17, 21.
1. Dessiner des arbres binaires de recherche de cet ensemble de clés avec une hauteur de 2, puis 4, et ensuite 6.
2. Donner les différents types de parcours en profondeur vues en cours (pour l’arbre binaire de recherche de hauteur
2.
3. Ecrire une fonction qui calcule le nombre de nœuds internes d’un arbre binaire.
EXERCICE 2
1. Écrire une fonction qui calcule la taille d’un arbre binaire.
2. Écrire une fonction qui calcule la hauteur d’un arbre binaire.
3. Écrire une fonction qui calcule le nombre de nœuds externes (feuilles) d’un arbre binaire.
4. Écrire une fonction qui calcule le nombre de nœuds internes d’un arbre binaire.
5. Écrire une fonction qui calcule la longueur de cheminement externe d’un arbre binaire.
EXERCICE 3
Écrire une procédure qui permet de copier un arbre binaire A dans un deuxième arbre B.
EXERCICE 4
Écrire une procédure qui permet de fusionner deux arbres binaires A et B, et de renvoyer un arbre C qui contient les
deux arbres. Discuter les différents cas possibles.
8
Première année, S2
BIBLIOGRAPHIE
S. ROHAUT : Algorithmique et Techniques fondamentale de programmation, Edition Eni 2007.
LIGNELET P., Algorithmique. Méthodes et modèles, Paris : Masson, 1985.
www.intelligentedu.com/blogs/post/free_computer_books/3760/the-algorithm-designmanual/fr/
