République Algérienne Démocratique et Populaire

Ministère de l’enseignement supérieur et de la recherche scientifique

Université Abdelhamid Mehri – Constantine2
Faculté des nouvelles technologies de l’information et de la communication

Algorithmique et structures de données

Pr. Amer Draa

Support de TD pour la matière ASD – 2ème année Informatique

Année universitaire : 2020 – 2021

TABLE DES MATIÈRES

Table des matières

Table des figures 1

Liste de tableaux 1

Préface 1

1 Fonctions, procédures et récursivité 2

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Série d’exercices corrigés No 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Exercice 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Exercice 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Exercice 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Exercice 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Exercice 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Exercice 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Exercice 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3 Exercices supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Exercice 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Exercice 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Exercice 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Exercice 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Exercice 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Exercice 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2 Complexité algorithmique 29
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2 Série d’exercices du TD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Exercice 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Exercice 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

1
TABLE DES MATIÈRES TABLE DES MATIÈRES

Exercice 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Exercice 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Exercice 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.3 Complexité théorique et temps d’exécution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3 Types abstraits de données, TAD 44

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2 Série d’exercices du TD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Exercice 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Exercice 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Exercice 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Exercice 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Exercice 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.3 Exercices supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Exercice 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Exercice 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.4 Le TAD ARBRE et son implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

4 Structures de données linéaires : liste, pile et file 67

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2 Série de TD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
Exercice 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
Exercice 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Exercice 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
Exercice 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
Exercice 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
Exercice 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
Exercice 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Exercice 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

Annexe A Programmation en langage C des exercice du chapitre 1 93

A.1 Implémentation de la solution de l’exercice 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
Implémentation de la solution de l’exercice 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

2
TABLE DES MATIÈRES TABLE DES MATIÈRES

A.2 Implémentation de la solution de l’exercice 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

Implémentation de la solution de l’exercice 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
A.3 Implémentation de la solution de l’exercice 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
Implémentation de la solution de l’exercice 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
A.4 Implémentation de la solution de l’exercice 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
Implémentation de la solution de l’exercice 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
A.5 Implémentation de la solution de l’exercice 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Implémentation de la solution de l’exercice 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
A.6 Implémentation de la solution de l’exercice 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Implémentation de la solution de l’exercice 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
A.7 Implémentation de la solution de l’exercice 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
Implémentation de la solution de l’exercice 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

Bibliographie 104

3
Préface

L’objectif de ce document est de fournir aux étudiants un support sur lequel ils peuvent s’appuyer pour assimiler
les concepts liés à l’algorithmique avancée. Plus particulièrement, on vise faire apprendre aux étudiants la
meilleure façon d’écrire un algorithme commençant par le choix de la structure de données la plus appropriée à
la résolution d’un problème donné et arrivant à l’écriture des instructions de l’algorithme.
L’un des défis à relever dans ce support est de faire habituer l’apprenant à donner l’intérêt nécessaire à
la phase de choix des structures de données pour la représentation des données à utiliser avant de passer à la
conception de l’algorithme. Ceci est bien détaillé dans les chapitres 3 et4.
Ce support est organisé en quatre chapitres, qui s’articule autours du programme officiel des universités
algériennes pour la deuxième année du tronc commun Mathématique et Informatique (MI). Ces chapitres sont :
– Chapitre 1 : Fonctions procédures et passage des paramètres
– Chapitre 2 : Complexité algorithmique
– Chapitre 3 : Types abstraits de données
– Chapitre 4 : Structures de données linéaires : liste, pile et file
La notion des arbres est présentée dans deux chapitres différents :
– Dans le troisième chapitre, comme TAD à définir, où on détaille la signature de son TAD et on implémente
les opération de base sur les arbres.
– Dans le quatrième chapitre, on présente là le cas particulier de l’arbre binaire à implémenter par des
structures linéaires.
Finalement, il est à noter que les solutions proposées dans ce support sont construite autour des solutions
types faites et proposées par l’équipe de formation du module, supervisée par Pr. F. Belala. Ces solutions ont
été enrichies, détaillées et illustrées par l’auteur. Ainsi, pour reconnaitre l’effort fourni par les collègues, on
mentionne localement la source de l’information.
Un remerciement spécial va aux collègues enseignants du module ASD qui ont contribué à la correction
des solutions proposées dans ce manuscrit, en particulier Dr. Hichem Talbi.

1
 Chapitre
1
Fonctions, procédures et récursivité

1.1 Introduction

Ce chapitre traite les concepts liés aux sous-programmes, fonctions et procédures avec plus d’intérêt donné à la
notion de récursivité. De plus, on s’intéresse à faire apprendre à l’étudiant les trois modes principaux de passage
des paramètres : ‘Donnée’, ‘Résultat’ et ‘Donnée/Résultat’.

1.2 Série d’exercices corrigés No 1

On présente dans cette section des solutions possibles pour les exercices contenus dans la série du TD 12 .

Exercice 1

1. Écrire un sous-algorithme (procédure ou fonction) qui calcule la somme des éléments positifs d’un tableau
d’entiers de taille N. Préciser le nombre et le type des paramètres considérés.
2. Dérouler la fonction ou la procédure pour des données de votre choix
3. Écrire un algorithme principal qui permet de :
– Créer un tableau T contenant 200 éléments de type entiers
– Faire la somme des éléments positifs de T (utiliser le sous-algorithme donné dans 1).
– Afficher la somme calculée.

Solution :

1. Écrire un sous-algorithme (procédure ou fonction) qui calcule la somme des éléments positifs
d’un tableau d’entiers de taille N. Préciser le nombre et le type des paramètres considérés.

Le sous-programme à proposer peut être soit une fonction ou bien une procédure. Pour chaque cas, on

1
Ce manuscrit est mis à jours périodiquement ; les exercices omis de la série de TD de l’année en cours seront insérés dans la partie
dédiée aux résultats supplémentaires.
2
Presque tous les énoncés sont proposés par Pr. F. Belala

2
 Chapitre 1 : Fonctions, procédures et récursivité

commence par déterminer le nombre et le type des paramètres à passer à cette routine3 4 . Il est important de
rappeler que, dans la majorité des cas, si une tâche est faite par une fonction elle peut être aussi accomplie par
une procédure, et vice versa. La seule différence réside dans la façon de passer les données au sous-programme
et la façon de retourner le résultat vers le programme appelant 5 . En effet, l’idée clé est que la fonction retourne
le résultat calculé dans son nom.

• Cas d’une fonction :

Par définition, une fonction doit retourner au moins un résultat. Cependant, certains langages de programmation,
tels que Python et Matlab, permettent de retourner plusieurs résultats par l’instruction ‘Retourner’. Même
pour les langages permettant de retourner un seul résultat, il est possible de retourner plus qu’un résultat en
procédant comme suit : un résultat est passé directement dans le nom de la fonction, alors que les autres, s’il y
en a, sont passés par le biais de variables en mode de passage de paramètres ‘par résultat’.

Passant à la fonction demandée dans la question de l’exercice, SommePositifs ; il est bien clair qu’il y a un
seul résultat à retourner par cette fonction : la somme des éléments positifs du tableau. En ce qui concerne la
définition des paramètres à passer à la fonction, on se pose deux questions :
1. Que doit le programme appelant passer au programme appelé comme donnée(s) pour que ce dernier puisse
accomplir la tâche ?
2. Est il permis au programme appelé de changer les valeurs des données qui sont lui passées ?
La réponse à la première question permet de décider le nombre et le type des paramètres à passer
au programme secondaire, tandis que la réponse à la deuxième question détermine le mode de passage des
paramètres. Dans l’exemple de la question :
1. On doit passer le tableau Tab des entiers comme premier paramètre et la taille N de ce tableau comme
deuxième paramètre. Ce deuxième paramètre est essentiel pour la compilation et l’exécution du sous-
programme. Vu que la taille N du tableau T ab sera utilisée dans un test ou une boucle, elle doit être passée
comme paramètre séparément de la déclaration du tableau. Il est évident que N est la taille de T ab, mais
on doit fournir cette taille à la machine pour qu’elle puisse faire le traitement en question.
2. Le programme appelé utilisera le contenu du tableau pour calculer la somme des nombres positifs, il n’aura
pas besoin de changer son contenu et de garder des changements dedans. Donc, le mode de passage le plus
approprié est le passage par ‘Donnée’. La taille N du tableau T ab est aussi passée par ‘Donnée’.
Ainsi, la signature6 de cette fonction est comme suit :
Fonction sommePositifs (Donnée Tableau Tab de N entiers, Donnée N : entier) : entier
Pour le corps de la fonction, on parcourt le tableau et on compare chacun des élément avec le zéro. Si
l’élément courant est supérieur à zéro, on rajoute la valeur de l’élément à la somme. Une fois on termine le
parcours du tableau, on retourne le résultat. La fonction sommePositifs est déclarée comme suit :

3
routine = sous-programme, sous-algorithme
4
Dans ce manuscrit les termes ‘algorithme’, ‘routine’, ‘code’ at ‘programme’ sont interchangeables.
5
Le programme appelant n’est pas forcement le programme principal ; il peut lui même être un sous-programme.
6
La signature d’un sous-algorithme est composée de son nom, ses paramètres formels et leurs types, et le type de retour dans le cas
d’une fonction.

3
 Chapitre 1 : Fonctions, procédures et récursivité

Fonction sommePositifs(Donnée Tab : Tableau de N entiers, Donnée N : entier) : entier

Som : entier
i : entier
Début
Som←0
Pour i ← 1 à N :
Si (Tab(i) ≥ 0) :
Som←Som+Tab(i)
FSi
FPour
a
Retourner Som

Fin

a
On peut écrire également : somPositifs ← Som

• Cas d’une procédure :

Comme déjà mentionné, tout traitement accomplis par une fonction pourrait être traduit en procédure et vice
versa 7 . Pour ce faire on procède comme suit :
1. De la fonction vers la procédure :
– Le résultat retourné par l’instruction ‘Retourner’ deviendra un paramètre à passer par ‘Résultat’.
– IL n’y a pas un type de retour.
– Les autres paramètres garderont leur mode de passage.
2. De la procédure vers la fonction :
– L’un des paramères passés par ‘Résultat’ (ou ‘Donnée/Résultat’8 ) est choisi pour être retourné par
l’instruction ‘Retourner’9 .
– Le type de retour de la fonction est le type de ce paramètre retourné par la fonction.
– Les autres paramètres garderont leur mode de passage.
On applique donc cette méthode pour convertir la fonction sommePositifs en procédure. Le résultat
retourné par l’instruction ‘Retourner’ est la variable Som, donc cette variable sera passée comme paramète en
mode ‘Résultat’. De plus, l’instruction ‘Retourner’ ainsi que le type de retour de la fonction ne doivent pas
figurer dans la procédure. On obtient la procédure suivante :

7
IL est parfois inutile de convertir une procédure en fonction si la procédure ne fait pas de calcul ; mais ça reste possible dans
certains langages de programmation comme Java qui retourne un type ‘void’ comme type de retourne vide.
8
Voir ce détail dans la partie cours publiée sur la plateforme e-learning de l’université Abdelhamid Mehri - Constantine 2.
9
S’il y a plusieurs paramètres passés par résultats (ou ‘Donnée/Résultat’), on choisira celui qui répond au rôle principal de la
fonction.

4
 Chapitre 1 : Fonctions, procédures et récursivité

Procédure sommePositifs(Donnée Tab : Tableau de N entiers, Résultat Som : entier, Donnée N : entier)
Début
Som←0
Pour i ← 1 à N :
Si (T ab(i) ≥ 0) :
Som←Som+T ab(i)
FSi
FPour

Fin

2. Dérouler la fonction ou la procédure pour des données de votre choix

On introduit ici le résultat d’exécution du code (programme) équivalent à la fonction/procédure somPositifs sur
le tableau, TabEff, suivant :

15 -3 -2 0 6

Le résultat de déroulement est comme suit 10 :

i TabEff(i) Som
1 15 15
2 -3 15
3 -2 15
4 0 15
5 6 21
6 / 21

3. Écrire un algorithme principal qui permet de :

– Créer un tableau T contenant 200 éléments de type entier.
– Faire la somme des éléments positifs de T (utiliser le sous-algorithme donné dans la
question 1).
– Afficher la somme calculée.
On introduit ici deux versions de cet algorithme ; la première utilise une fonction comme sous-algorithme
et la deuxième utilise une procédure. Le pseudo-code des sous-algorithmes est abrégé ici, on l’a déjà détaillé
dans les question précédentes.

10
Il est à remarquer que la valeur de i est égale à 6 à ma sortie de la boucle.

5
 Chapitre 1 : Fonctions, procédures et récursivité

Algorithme Exercice 01_VersionFonction

Déclarations :
TabEff : Tableau de N entiers
i : entier
Fonction sommePositifs(Donnée Tab : Tableau de N entiers, Donnée N : entier) : entier
···
Fin
Début
Pour i ← 1 à 200 :
Lire(TabEff(i))
FPour
Ecrire(sommePositifs(TabEff, 200))
Fin

Algorithme Exercice 01_VersionProcédure

Déclarations :
TabEff : Tableau de N entiers
i : entier
Res : entier
Procédure sommePositifs(Donnée Tab : Tableau de N entiers, Résultat Som : entier, Donnée N : entier)
···
Fin
Début
Pour i ← 1 à 200 :
Lire(TabEff(i))
FPour
sommePositifs(TabEff, Res, 200)
Ecrire(Res)
Fin

Exercice 2

Un nombre entier est dit équilibré si l’ordre des chiffres qui le constituent reste le même qu’on le lise de gauche
à droite ou de droite à gauche, comme par exemple : 123321, 6578756 sont des nombres équilibrés. Ecrire la
fonction itérative Equilibre (. . . ) qui teste si un nombre entier donné est équilibré.

Solution :

L’idée de base de la solution proposée ici est de passer le nombre testé dans un tableau à la fonction ‘Equilibre’.
Aussi, il est essentiel de passer la taille de ce tableau, qui indique le nombre de chiffre de cet entier, comme
paramètre. Les deux paramètres sont passés par ‘Donnée’, vu qu’on ne doit garder aucun changement appliqué
par le sous-programme sur leurs valeurs. La solution proposée est la suivante :

6
 Chapitre 1 : Fonctions, procédures et récursivité

Fonction Equilibre(Donnée Tab : Tableau de N entiers, Donnée N : entier) : booléen

B : booléen
i : entier
Début
B←vrai
Pour i ← 1 à N Div 2 :
Si (Tab(i) 6= Tab(N-i+1)) :
B←faux
FSi
FPour
Retourner B
Fin

Exercice 3

Le nombre Dn de dérangements de n éléments vérifie l’étonnante récurrence suivante :

D1 = 0
Dn = n ∗ Dn−1 + (−1)n

1. Écrire une fonction récursive Dérangement( ?) qui calcule Dn .

2. Écrire une fonction itérative qui calcule Dn .
3. Dérouler la fonction récursive Dérangement pour N = 4.

Solution :

1. Écrire une fonction récursive Dérangement( ?) qui calcule Dn :

Par définition, une fonction récursive est une fonction qui fait un appel dedans de la même fonction, mais
avec d’autres valeurs de ses paramètres. La structure générale d’une fonction récursive est comme suit :

Fonction F(ParsForm) : typeRes

Déclarations
···
Début
Si (cas trivial) :
Retourner valeur équivalente au cas trivial
Sinon
Retourner F(ParsEff2)
FSi
Fin

Dans cette structure, on distingue entre les paramètres formels ParsForm, donnés dans la signature de la
fonction, et les paramètres effectifs ParsEff2, utilisés par la fonction si la condition d’arret des appels, cas trivial,
n’est pas vérifiées. Les valeurs des paramètres effectifs ParsEff2 sont également différentes de leaurs valeurs dans
l’appel initial ParsEff1 (fait dans le programme appelant). Le cas trivial représente le point de sortie des appels
récursifs.

On applique maintenant cette façon de raisonnement à notre exercice. Le cas trivial de la formule
‘Dérangement’ est D1 , donc la valeur de n=1. Si la valeur d’entrée est égale à 1, la fonction ‘Dérangement’ retourne

7
 Chapitre 1 : Fonctions, procédures et récursivité

comme résultat la valeur 0, sinon, elle applique la deuxième équation de la formule : Dn = n ∗ Dn−1 + (−1)n .
De cette formule, on peut facilement déduire que dans le bloc ‘Sinon’ l’instruction ‘Retourner’ s’applique sur la
valeur n ∗ Dn−1 + (−1)n . Par conséquent, l’appel interne de la fonction Dérangement prend comme paramètre
la valeur n − 1. Remplissant maintenant la structure précédente de la fonction récursive, on obtient :

maxentier = . . . /*Se fait dans le programme appelant

Type entierpositif = [1 .. maxentier] /*Se fait dans le programme appelant

Fonction Dérangement(Donnée N : entierpositif) : entier

Déclarations
i : entier
Début
i←1
Si (N=1) :
Retourner 0 ; /*Cas trivial
Sinon
Si (N mod 2 =0 a ) :
Retourner N * Dérangement(N–1) + 1 ; /*Appel Recursif
Sinon
Retourner N * Dérangement(N–1) – 1 ;
FSi

a
Ce test permet de définir la valeur de (−1)n
FSi
Fin

2. Écrire une fonction itérative qui calcule Dn :

Fonction Dérangement(donnée N : entierpositif) : entier

Déclarations
dn, i : entiers
Début
dn←0
Pour i ← 2 à N :
Si (i mod 2 =0 a ) :
dn←i*dn+1
Sinon
dn←i*dn-1
FSi

a
Ce test permet de définir la valeur de (−1)n
FPour
Retourner dn
Fin

3. Dérouler la fonction récursive Dérangement pour N = 4 :

Exercice 4

Reprendre les exercices 1 et 2 en utilisant des fonctions récursives

8
 Chapitre 1 : Fonctions, procédures et récursivité

Solution :

On reprend l’exercice 1 en utilisant une fonction récursive :

Le rôle de la fonction est de calculer la somme des éléments positifs dans un tableau Tab de N entiers. En
plus de son rôle dans la boucle ‘Pour’ (Voir solution exercice 1), la variable N, passée comme paramètre à la
fonction récursive, a un rôle important dans la solution suivante. Elle permet la réalisation des appels récursifs.
Dans la solution itérative donnée précédemment, on a parcouru le tableau du début à la fin d’une façon
séquentielle pour chercher les éléments positifs. On pourra faire la même chose dans la solution récursive, on
aura besoin dans ce cas de passer comme paramètre pour les appels récursifs : le tableau Tab, un indice de
départ (1, puis 2, puis 3, ...), et la taille du tableau à utiliser dans la boucle ‘Pour’. La fonction récursive dans
ce cas est comme suit :

Fonction sommePosRec(Donnée T :Tableau de N entiers, Données i :entier, Donnée N : entier) : entier

Si (i>N) :
Retourner 0 ; /*Cas trivial
Sinon
Si (T(i)≥0) :
Retourner T(i)+sommePositifsRec(T,i+1,N)
Sinon
Retourner sommePositifsRec(T,i+1,N) ;
FSi
FSi
Fin

Soit l’exemple du tableau Tab_Exemple suivant :

15 -3 -2 10 6

On suppose qu’un programme appelant contient l’instruction :

Écrire(sommePosRec(Tab_Exemple,1,N)).

L’exécution de cette instruction se déroule comme suit. La valeur de sommePosRec(Tab_Exemple,1,N)

est calculée puis affichée. Le calcul de cette valeur se fait par deux étapes : (1) le passage des paramètres du
programme appelant au programme appelé, (2) l’exécution du corps de la fonction sommePosRec.

Étape 1 : passage des paramètres : Les trois paramètres sont passés par ‘Donnée’, la machine dans
ce cas crée dans l’espace réservé au sous-algorithme des copies des variables correspondantes utilisées dans
l’appel et les nomme comme défini dans l’algorithme appelé. La figure 1.1 donne une illustration de ce qui se
passe en mémoire lors du passage des paramètres.

9
 Chapitre 1 : Fonctions, procédures et récursivité

…
N5
Ecrire(sommePosRec(Tab_Exemple,1,N))
…

Espace réservé au programme appelant

Tab_Exemple

N 5

Espace réservé au programme appelé sommePosRec

Tab

N 5 i 1

Figure 1.1: Passage de paramètres pour l’appel Ecrire(sommePosRec(Tab_Exemple,1,N))

Étape 2 : l’exécution du corps de la fonction sommePosRec : La particularité de l’exécution

d’une fonction récursive réside dans le fait que le sous-programme fait appel à lui même. On peut simplifier ceci
par imaginer que le sous-programme appelle un autre sous-programme ayant le même nom, et ce dernier appelle
un autre sous-programme ayant le même nom et ainsi de suite, jusqu’à aboutir au cas trivial. Une fois le cas
trivial est obtenu, la chaine des retours des résultats d’appels récursifs commencera, l’appel qui a abouti au
cas trivial sera le premier à retourner un résultat au sous-programme qui a fait le dernier appel, et ce dernier
programme retourne la valeur au sous-programme qui l’a appelé et ainsi de suite, jusqu’à retourner la valeur au
premier appel, au programme appelant dans ce cas. Les figures 1.2 et 1.3 illustrent le processus d’évaluation de
l’appel sommePosRec(Tab_Exemple,1,N).

Une autre façon de traiter ce problème d’une manière récursive est d’exploiter uniquement la taille du
tableau qui change de N à N-1, N-2 · · · , 1. Dans ce cas, les éléments du tableau sont parcouru dans l’ordre
inverse, si l’élément courant est positif on retourne sa valeur plus le résultat d’appel de la fonction pour les
éléments qui restent, sinon on retourne le résultat d’appel de la fonction pour le reste des éléments. La fonction
sommePosRec2 implémente cette idée.

Fonction sommePosRec2(Donnée T : Tableau de N entiers, Donnée N : entier) : entier

Si (N<1) :
Retourner 0 ; /*Cas trivial
Sinon
Si (T(N)≥0) :
Retourner T(N)+sommePositifsRec2(T,N-1)
Sinon
Retourner sommePositifsRec2(T,N-1)
FSi
FSi
Fin

10
 Chapitre 1 : Fonctions, procédures et récursivité

Affiche la valeur
31 à l’écran Ecrire(sommePosRec(Tab_Exemple,1,N))

Espace réservé au programme appelant

Tab_Exemple
5 N

Espace réservé au programme appelé sommePosRec

31
T

5 N
i 1

i>N Faux

T(i)≥0 Vrai

Retourner(T(i)+sommePositifsRec(T,i+1,N))

16 Espace réservé au programme appelé sommePosRec

5 N
i 2

i>N Faux

T(i)≥0 Faux

Retourner(sommePositifsRec(T,i+1,N))
Espace réservé au programme appelé sommePosRec

16
T

5 N
i 3

i>N Faux

    T(i)≥0 Faux    
       
       

Figure 1.2: Déroulement de l’instruction Ecrire(sommePosRec(Tab_Exemple,1,N)), Partie 1

11
 Chapitre 1 : Fonctions, procédures et récursivité

     

Retourner(sommePositifsRec(T,i+1,N))
Espace réservé au programme appelé sommePosRec

5 N
i 4

16 i>N Faux

T(i)≥0 Faux

Retourner(sommePositifsRec(T,i+1,N))
Espace réservé au programme appelé sommePosRec

i 5
6 5 N

i>N Faux

T(i)≥0 Vrai

Retourner(T(i)+sommePositifsRec(T,i+1,N))
Espace réservé au programme appelé sommePosRec

5 N
i 6

i>N Vrai

0
Retourner(0) /*Cas trivial

Figure 1.3: Déroulement de l’instruction Ecrire(sommePosRec(Tab_Exemple,1,N)), Partie 2

12
 Chapitre 1 : Fonctions, procédures et récursivité

L’avantage de cette solution par rapport à la précédente est qu’elle utilise deux paramètres au lieu de trois,
chose qui peut créer la différence au moment d’exécution en termes de l’espace de stockage et même le temps
d’exécution 11 . La réponse à la troisième question de l’exercice 1 en utilisant la fonction récursive devient ainsi :

Algo Exercice 01_VersionRecursion

Déclarations :
TabEff : Tableau de N entiers
i : entier
Fonction sommePosRec(Donnée Tab : Tableau de N entiers, Donnée i :entier, Donnée N : entier) : entier
· · · /*voir solution détaille sur la page 9.
Fin
Début
Pour i ← 1 à 200 :
Lire(TabEff(i))
FPour
Ecrire(sommePosRec(TabEff,1,200))
Fin

On reprend l’exercice 2 en utilisant une fonction récursive :

On doit fournir une fonction récursive qui vérifie si un nombre est équilibré ou nom. Une solution possible
est de confronter les deux extrémités du tableau contenant le nombre à tester. Les figures 1.4 et 1.5 illustre la
façon d’implémenter l’idée.

52125

534435

Figure 1.4: Exemples de nombres équilibrés, test par symétrie récursive

53145

Figure 1.5: Exemples d’un nombre non-équilibrés, test par symétrie récursive

Comme peut être vu des deux figures, on réitère la comparaison de l’élément en cours (à la position i du
tableau) jusqu’à aboutir à l’une des deux configurations suivantes :

11
À cause du temps nécessaire pour le passage des paramètres et la gestion de la mémoire.

13
 Chapitre 1 : Fonctions, procédures et récursivité

1. On n’a qu’un seul élément ou zéro élément dans le tableau, on retourne ‘vrai’ dans ce cas.
2. L’élément courant, i, et celui en symétrie avec lui, à la position N-i+1, ne sont pas similaire ; on retourne
‘faux’ dans ce cas.
En utilisant une solution algorithmique, on ne va pas supprimer les éléments du tableau en les ecrasant de
la mémoire, on enlève pas des espaces de stockage. Le tableau restera le même lors de tous les appels récursifs,
comme vu dans les figures 1.1, 1.2 et 1.3. La non-considération d’un élément du tableau est implémentée à
travers la manipulation des paramètres. Par exemple, le tableau dans l’exemple de somePosRec est composé de
deux éléments : l’espace de stockage T et le nombre d’éléments à considérer dans cet espace. Donc, le tableau
lors du premier appel, fait par le programme appelant, est l’union des deux éléments : (T,5) ; il devient lors
du deuxième appel équivalent) l’union (T,4), ..., (T,1). D’une façon pareille, dans la fonction EquilibreRec,
proposée dans la suite, on traite le tableau comme un triplet : (T,i,N) : (T,1,5) lors du premier appel, et puis
(T,2,4), T(3,3). La condition ‘le nombre d’éléments est égal à 1 ou 0’ est exprimée par : i=(N+1) div 2 12 . La
solution sera donc :

Fonction EquilibreRec(Donnée T :Tableau de N entiers, Donnée i :entier, Donnée N : entier) : entier

Si (i=(N+1) div 2) :
Retourner Vrai ; /*Cas trivial
Sinon
Si (T(i) = T(N-i+1)) :
Retourner EquilibreRec(T,i+1,N)
Sinon
Retourner Faux
FSi
FSi
Fin

L’appel de cette fonction se fera initialement comme suit : ‘x←EquilbreRec(T,1,N)’, i=1 dans ce cas, il
change à chaque appel récursif, mais N est fixé à 5. Une autre solution possible utilisant deux indices pour
parcourir le tableau. En plus de i, on utilise j qui représente l’indice obtenu par symétrie. La solution est la
suivante :

Fonction EquilibreRec2(Donnée T :Tableau de N entiers, Donnée i :entier, Donnée j : entier) : entier

Si (i≥j a ) :
Retourner Vrai ; /*Cas trivial
Sinon
Si (T(i) = T(j)) :
Retourner EquilibreRec(T,i+1,j-1)
Sinon
Retourner Faux
FSi

a
Cette deuxième condition indique qu’on a plus d’éléments dans le tableau, par contre la première est pour le cas ou on a a
un seul élément dans le tableau.
FSi
Fin

12
L’opérateur div est pour la division naturelle

14
 Chapitre 1 : Fonctions, procédures et récursivité

La deuxième condition utilisée dans le cas trivial indique que tous les éléments sont parcourus. L’appel
initial affect 1 à i et N à j. Contrairement à la version précédente, j change sa valeur ici d’une façon décrémentale.

Exercice 5

1. Écrire une fonction récursive permettant de déterminer le maximum de deux entiers positifs donnés (sans
utiliser l’opération de comparaison).
2. Dérouler la fonction pour les deux nombres 3 et 7.

Solution :

1. Ecrire une fonction récursive permettant de déterminer le maximum de deux entiers positifs
donnés (sans utiliser l’opération de comparaison).

Une solution possible est de soustraire récursivement ‘un’, 1, des deux éléments et d’appeler à nouveau
la fonction Maximum en lui passant les résultats de cette soustraction jusqu’à aboutir à l’annulation de l’un
des deux. L’autre nombre, en lui ajoutant des uns avec le même nombre d’appels récursifs, est le résultat de
la comparaison, voir l’exemple de déroulement donnée dans la réponse à la question 2. La fonction récursive
résultant est la suivante :

Fonction Maximum(Donnée N1 : entier, Donnée N2 : entier) : entier

Si (N1=0) :
Retourner N2
Sinon
Si (N2=0) :
Retourner N1
Sinon
Retourner Maximum(N1–1, N2–1)+1
FSi
FSi
Fin

2. Dérouler la fonction pour les deux nombres 3 et 7.

Le déroulement de cet appel est illustré dans la figure 1.6.

15
 Chapitre 1 : Fonctions, procédures et récursivité

Figure 1.6: Déroulement de l’appel Maximum(3,7)

Exercice 6

Le nombre de partitions d’un entier naturel p (6=0) en q (6=0) parties est défini par :
Si p>q, NP(p, q) = NP(p-1, q-1) + NP(p-q, q)
Si p < q, NP(p, q)= 0
NP(p, p)= NP(p, 1)= 1
Par exemple, les partitions de 5 en 3 parties sont : 3+1+1, 2+2+1.
1. Ecrire une fonction récursive NP ( ? ?) qui calcule le nombre de partitions d’un entier naturel p en q parties.
2. Dérouler la fonction récursive NP pour p=5 et q=3

Solution :

1. Ecrire une fonction récursive NP ( ? ?) qui calcule le nombre de partitions d’un entier naturel
p en q parties.
La formule décrivant le problème pourra être directement utilisée pour définir le (les) cas trivial (triviaux) et les
paramètres des appels récursifs.

• Cas triviaux :

Selon la définition donnée, on arrête les appels récursif dans l’un des trois cas suivants :
– Si p<q, on retourne 0.
– Si p=q, on retourne 1.
– Si q=1, on retourne 1.

16
 Chapitre 1 : Fonctions, procédures et récursivité

• Paramètres des appels récursifs :

Tant qu’aucun cas trivial n’est atteint, on appelle la fonction ‘NP’ comme donnée par la formule : nbrPart(p,
q) = nbrPart(p-1, q-1) + nbrPart(p-q, q)

En considérant ces deux points, on définit la fonction calculant le nombre de partitions de p en q partitions
comme suit :

Fonction nbrPart(Donnée p : entier, Donnée q : entier) : entier

Si (q=1) :
Retourner 1
Sinon
Si (p<q) :
Retourner 0
Sinon
Si (p=q) :
Retourner 1
Sinon
Retourner (nbrPart(p-1, q-1) + nbrPart(p-q, q))
FSi
FSi
FSi
Fin

2. Dérouler la fonction récursive NP pour p=5 et q=3

La figure 1.7 montre le déroulement de la fonction nbrPart pour p=5 et q=3.

NP(5, 3) NP(4, 2) NP(2, 3)

P=5 p=4 p q
q=3 q=2 0

2+0 NP(3, 1) NP(2,2)

1+1 p=3 p=q=2
2 q=1
2 1 1

Figure 1.7: Déroulement de la fonction nbrPart pour p=5 et q=3 (Proposée par Pr. F. Belala)

Exercice 7 (Énoncé proposé par Dr. Dj. Hammoud)

1. Écrire une fonction récursive Maximum (T, · · · ) qui détermine le maximum d’un tableau T de N réels.
2. Soit une suite S numérique de N nombres. On suppose l’existence des fonctions suivantes :
– Reste (S) : qui retourne le reste des éléments de la suite S sans son premier élément.
– Elem (S) : qui retourne le premier élément de S.
– Vide ?(S) : qui teste si la suite S ne contient aucun élément.

17
 Chapitre 1 : Fonctions, procédures et récursivité

– Proposez une fonction récursive Maximum (S) qui retourne le nombre maximal de cette suite en utilisant
ces fonctions.
3. Donnez l’implémentation des 3 fonctions précédentes avec une représentation interne de la suite par un
tableau de N entiers. Commenter les résultats.

Solution :

1. Écrire une fonction récursive Maximum(T, · · · ) qui détermine le maximum d’un tableau T de
N réels.

Fonction Maximum(Donnée T : Tableau[N] de réels ; Donnée N : entier) : réel

Si (N=1) :
Retourner T(1)
Sinon
Si (T(N)> Maximum(T, N-1)) :
Retourner T(N)
Sinon
Retourner Maximum(T, N-1)
FSi
FSi
Fin

2. Soit une suite S numérique de N nombres. On suppose l’existence des fonctions suivantes :
– Reste(S) : qui retourne le reste des éléments de la suite S sans son premier élément.
– Elem(S) : qui retourne le premier élément de S.
– Vide ?(S) : qui teste si la suite S ne contient aucun élément.
Proposez une fonction récursive Maximum (S) qui retourne le nombre maximal de cette suite
en utilisant ces fonctions.
L’implémentation, des 3 fonctions déclarées, dépend de la représentation interne de la suite numérique,
ainsi à la question 2, nous avons donné uniquement les entêtes de ces 3 fonctions. Maintenant, avec une
représentation interne de la suite numérique par un tableau de N entiers nous pouvons les implémenter comme
suit :
Pour la structure de données :
Type : suite-numérique = Tableau de N entier
ou bien :
Type : suite-numérique = enregistrement
(
N : entier
Tab : Tableau de N entiers
Fin
Pour les fonctions :

18
 Chapitre 1 : Fonctions, procédures et récursivité

Fonction vide ? (Donnée S : suite-numérique ) : booléen

Si (S.N = 0) :
Retourner Vrai
Sinon
Retourner Faux
FSi
Fin

Fonction Reste(Donnée S : suite-numérique ) : suite-numérique

S.N ← S.N-1 a
Retourner S
Fin

a
On suppose que les éléments sont stockés dans l’ordre inverse. Reste élimine le dernier élément de la suite.

Fonction Elem(Donnée S : suite-numérique ) : entier

Retourner [Link](N)
Fin

3. Donnez l’implémentation des 3 fonctions précédentes avec une représentation interne de la

suite par un tableau de N entiers. Commenter les résultats.
Si on remplace la représentation interne de la suite numérique, déjà définie par un enregistrement, par un
tableau, les fonctions précédentes seront adaptée comme suit.

Fonction vide ? (Donnée S : suite-numérique ) : booléen

Si (Taille(S) = 0 a ) :
Retourner Vrai
Sinon
Retourner Faux
FSi

a
La fonction Taille est supposée prédéfinie. Elle restourne le nombre d’éléments d’un tableau.
Fin

ab
Fonction Reste(Donnée S : suite-numérique, Donnée DebSuite : entier ) : suite-numérique, entier
DebSuite ← DebSuite+1
Retourner S, DebSuite
Fin

a
Le paramètre DebSuite indique le début de la suite dans le tableau contenant ses éléments.
b
La suite est l’ensemble du tableau plus la position du premier élément dans ce tableau.

Fonction Elem(Donnée S : suite-numérique ) : entier

Retourner S(1)
Fin

19
 Chapitre 1 : Fonctions, procédures et récursivité

Fonction Maximum(Donnée S : Suite-numérique, Donnée IndDEbSuite :entier) : nombre

/* nombre peut être entier ou réel ; suite-numérique est une suite de nombres */
Fonction Vide ?(Donnée S : Suite-numérique) : booléen
···
Fin
Fonction Reste(Donnée S : Suite-numérique, Donnée DebSuite) : Suite-numérique
···
Fin
Fonction Elem(Donnée S : Suite-numérique) : nombre
···
Fin
Si (vide ? (Reste(S)) = vrai) :
Retourner T(Elem(S))
Sinon
Si (Elem(S)>Maximum(Reste(S,IndDEbSuite))) :
Retourner Elem(S)
Sinon
Retourner Maximum(Reste(S))
FSi
FSi
Fin

La fonction Maximum (de la question 2) reste inchangée quelque soit l’implémentation de la suite
numérique, c’est une solution générale et générique ; seules les fonctions de base dépendent de l’implémentation.
Ainsi, cette fonction Maximum générique peut être réutilisée pour d’autres implémentations de la suite numérique
(e.g : une liste ou une pile chainées), alors que la fonction Maximum de la question 1 est complètement dépendante
de l’implémentation.

1.3 Exercices supplémentaires

Dans cette section, on présente quelques exercices supplémentaires dont leur résolution permet plus de maitrise
des concepts liées aux passages des paramètres et à la récursivité. Les solutions proposées dans ces sections ne
seront pas détaillées, en effet on ne vise pas donner des réponses type, on stresse le but de chaque exercice dans
sa solution.

Exercice 8

On considère, pour effectuer la recherche du plus grand élément dans un tableau de N éléments entiers, la
recherche séquentielle et la recherche dichotomique. La recherche dichotomique du plus grand élément d’un
tableau T qui contient n éléments se fait ainsi :
Si T contient un seul élément :
C’est fini ;
Sinon :
– Couper T en deux tableaux T1 et T2 de taille "presque" identiques
– Chercher m1, le max de T1
– Chercher m2, le max de T2
– Retourner le max de m1 et m2

20
 Chapitre 1 : Fonctions, procédures et récursivité

Solution :

L’idée de base de l’algorithme de recherche du maximum par dichotomie (A ne pas confondre avec le tri
dichotomique) est de subdiviser le tableau en deux à chaque fois et de comparer le maximum des deux parties.
Ce processus est répété jusqu’à obtenir un seul élément dans le tableau. La figure 1.8 résume ce principe.

98

56 6 8 98 54 -2 7

98
56

56 6 8 98 54 -2 7

56 8 98 7

56 6 8 98 54 -2 7
6 8 98 54 -2 7

6 8 98 54 -2 7

Figure 1.8: Principe de la recherche du maximum par dichotomie

Une manière simple de résoudre ce problème est de créer à chaque appel deux nouveaux tableaux vers
lesquels les parties gauche et droite sont recopiées respectivement. Cette solution n’est pas pratique pour deux
raisons :
• Si le tableau initial est assez grand, on aura besoin d’un grand espace mémoire pour permettre l’exécution
du programme.
• Le temps d’exécution aussi augmente considérablement.
On peut faire face à ces limites par la bonne utilisation des paramètres. En effet ; au lieu de créer à chaque
fois deux sous-tableaux, on utilise le même tableau lors de l’appel, mais avec deux paramètres indiquant où le
sous tableau est situé. La figure 1.9 illustre cette idée, où d est l’indice du début du tableau en cours, alors que
f représente l’indice de la fin.

21
 Chapitre 1 : Fonctions, procédures et récursivité

1
D=1
F=7
D=2
56 6 8 98 54 -2 7 F=2 56 6 8 98 54 -2 7

D=1 D=3
F=3 56 6 8 98 54 -2 7 F=3 56 6 8 98 54 -2 7

2
D=4 56 6 8 98 54 -2 7
F=7 D=4
56 6 8 98 54 -2 7
F=4

4
D=1 D=5
F=1 56 6 8 98 54 -2 7 F=5 56 6 8 98 54 -2 7

D=2 56 6 8 98 54 -2 7
F=3 D=6
F=6 56 6 8 98 54 -2 7
3
D=4
F=5 56 6 8 98 54 -2 7
D=7
F=7 56 6 8 98 54 -2 7
D=6 56 6 8 98 54 -2 7
F=7

Figure 1.9: Utilisation des paramètres pour délimiter les sous-tableaux

On peut passer comme paramètres à la fonction récursive rechMaxDicho, en plus du tableau T, deux
autres éléments marquant respectivement l’adresse du début et celle de la fin. Comme vu dans l’illustration de
la figure 1.9, tous les appels récursifs travaille sur des tableaux de même taille et de même contenu, mais la
subdivision se fait logiquement et pas physiquement. La fonction récursive devient ainsi :

Fonction rechMaxDicho(Donnée T : Tableau de N entiers, Données indDeb : entier, Donnée indFin : entier) : réel
Si (indDeb=indFin) :
Retourner T(indDeb)
Sinon
Si (rechMaxDicho(T, indDeb,(indDeb+indFin) div 2) > rechMaxDicho(T,((indDeb+indFin) div 2) + 1,
indFin)) :
Retourner rechMaxDicho(T, indDeb,(indDeb+indFin) div 2)
Sinon
Retourner rechMaxDicho(T, ((indDeb+indFin) div 2) + 1, indFin)
FSi
FSi
Fin

22
 Chapitre 1 : Fonctions, procédures et récursivité

Exercice 9

1. Écrire une fonction récursive nbrChiffres qui calcule le nombre de chiffres d’un nombre entier positif. Par
exemple, nbrChiffres(1203) = 4.
2. Donner l’image mémoire relative à l’exécution de nbrChiffres(1203).
3. Traduire cette fonction en C.

Solution :

Fonction nbrChiffres(Donnée N : entier) : entier

Si (N ≤ 9) :
Retourner (1)
Sinon
Retourner (1+nbrChiffres(N div 10))
FSi
Fin

N= 1203 N= 120 N= 12 N= 1
N= 1203
nbrChiffres=4 nbrChiffres=3 nbrChiffres=2 nbrChiffres=1
4
@retour 3 2 1
@retour 1 @retour 2 @retour 3
r

Programme nbrChiffres(1203) nbrChiffres(120) nbrChiffres(12) nbrChiffres(1)

principal

Figure 1.10: Image mémoire relative à l’exécution de nbrChiffres(1203)

Listing 1.1: Code C de la fonction qui calcule le nombre de chiffres d’un entier
1 #include <stdio.h>
2 #include <math.h>
3 #include <stdbool.h>
4
5 int nbrChiffres(int n)
6 {
7 if (n<=9)
8 return(1);
9 else
10 n=n/10;
11 return(1 + nbrChiffres(n));
12 }
13
14 int main() {

23
 Chapitre 1 : Fonctions, procédures et récursivité

15 int nt;
16 printf("Entrer le nombre n: ");
17 scanf("%d", &nt);
18 printf("Le nombre de chiffres de cet entier est: %d",nbrChiffres(nt));
19 return 0;
20 }

Exercice 10

1. Écrire une fonction itérative qui teste si un nombre est premier ou non.
2. Écrire une fonction récursive qui teste si un nombre est premier ou non.

Solution :

Solution adaptée du code fournie sur la page :

[Link]

Fonction estPremier(Donnée nbr : entier) : booléen

i : entier
TQ (i<=nbr/2) :
Si (nbr mod i=0) :
Retourner faux
Sinon
Retourner i ← i+1
FSi
FTQ
Retourner Vrai ;
Fin

Fonction estPremierRec(Donnée nbr : entier, Donnée i : entier) : entier

Si (i=0) :
Retourner Vrai
Sinon
Si (nbr mod i = 0) :
Retourner Faux
Sinon
Retourner (estPremierRec(nbr, i-1))
FSi
FSi
Fin

Exercice 11

Soit l’algorithme, dû à Euclide, qui détermine le PGCD de 2 nombres naturels A et B. Si un des nombres est
nul, l’autre est le PGCD, sinon il faut soustraire le plus petit du plus grand et laisser le plus petit inchangé.
Puis, recommencer ainsi avec la nouvelle paire jusqu’à ce que l’un des deux nombres soit nul. Dans ce cas,
l’autre nombre est le PGCD.

24
 Chapitre 1 : Fonctions, procédures et récursivité

Exemple : Si A vaut 32 et B vaut 14, on obtient successivement :

(32, 14) → (32-14=18, 14) → (18-14=4, 14) → (14-4=10, 4) → (10-4=6, 4) → (6-4=2, 4) → (4-2=2, 2) →
(2-2=0, 2)
Donc PGCD(32,14)=2.
1. Écrire une fonction itérative pour calculer le PGCD en utilisant l’algorithme d’Euclide.
2. Écrire une fonction récursive pour calculer le PGCD en utilisant l’algorithme d’Euclide.

Solution :

Fonction PGCD(Donnée A : entier, Donnée B : entier) : entier

TQ (A6=0 et B6=0) :
Si (A>B) :
A ← A–B
Sinon
B ← B–A
FSi
FTQ
Si (A=0) :
Retourner (B)
Sinon
Retourner (A)
FSi
Fin

Fonction PGCD_Rec(Donnée A : entier, Donnée B : entier) : entier

Si (B>A) :
Retourner PGCD_Rec(B,A)
Sinon
Si (A=0) :
Retourner B
Sinon
Retourner PGCD_Rec(A-B,B)
FSi
FSi
Fin

Exercice 12

1. Écrire une fonction récursive qui permet la conversion d’un entier du décimal en binaire.
2. Généraliser cette solution pour la conversion vers d’autres bases.

25
 Chapitre 1 : Fonctions, procédures et récursivité

Solution :

Fonction Binaire(Donnée N : entier) : entier

Si (N div 2 = 0) :
Retourner N
Sinon
Retourner ((N mod 2) + 10 * Binaire(N div 2))
FSi
Fin

Fonction Conversion(Donnée N : entier, Donnée B : entier) : entier

Si (N div B = 0) :
Retourner N
Sinon
Retourner ((N mod B) + 10 * Conversion(N div B))
FSi
Fin

Exercice 13

1. Écrire une fonction récursive qui reçoit un entier n et retourne la valeur A(n) selon la formule suivante :




 A(0) = 1


B(0) = 0





 A(n) = n − B(A(n − 1)), Sin > 0


B(n) = n − A(B(n − 1)), Sin > 0



NB : La fonction B doit aussi être récursive.

2. Faire le déroulement de l’appel A(3).
Solution :
1. Cet exercice illustre le cas de la récursivité mutuelle (des fois multiple). La conception de la solution
se fait d’une façon ordinaire avec la seule exception que lors des appels récursifs la fonction A fait appel à la
fonction B et vice versa ; bien sûr avec des valeurs de paramètres différents à chaque appel. On peut proposer
donc les deux fonctions récursives suivante :

Fonction A(Donnée N : entier) : entier

Si (N = 0) :
Retourner 1
Sinon
Retourner (n–B(A(n–1)))
FSi
Fin

26
 Chapitre 1 : Fonctions, procédures et récursivité

Fonction B(Donnée N : entier) : entier

Si (N = 0) :
Retourner 0
Sinon
Retourner (n–A(B(n–1)))
FSi
Fin

On donne le code équivalent en langage C :

Listing 1.2: Code C définissant et utilisant la récursivité mutuelle

1 #include <stdio.h>
2 #include <math.h>
3
4 int A(int n);
5 int B(int n);
6
7 int B(int n)
8 {
9 printf("\n Fonction B N=%d", n);
10 if (n==0)
11 return (0);
12 else
13 return (n-A(B(n-1)));
14 }
15
16 int A(int n)
17 {
18 printf("\n Fonction A N=%d", n);
19 if (n==0)
20 return (1);
21 else
22 return (n-B(A(n-1)));
23 }
24
25 int main() {
26 int nt;
27 printf("Entrer le nombre n: ");
28 scanf("%d", &nt);
29 printf("\n Appel initial de la fonction A N=%d", nt);
30 printf("\n\n A(N)= %d",A(nt));
31 return 0;
32 }

Le déroulement de ce code pour la valeur N=3 est donnée dans la figure 1.11.

27
 Chapitre 1 : Fonctions, procédures et récursivité

Figure 1.11: Exécution du programme de la récursion mutuelle des fonctions A et B

1.4 Conclusion

Dans ce chapitre, on a traité les fonction, les procédures, le passage des paramètres et la récursivité à travers la
résolution de treize exercices. Les solutions proposées ont été détaillée, mais pour augmenter le bénéfice des
étudiants, on présente la traduction de ces solutions en langages de programmation (C, python, etc.) dans
l’annexe 1.

28
 Chapitre
2
Complexité algorithmique

2.1 Introduction

Ce chapitre traite la notion de complexité temporelle des algorithme. L’analyse d’algorithmes est détaillée à
travers cinq exercice qui présentent les cas souvent rencontrés. Les trois notation O, T heta et Ω sont aussi
expliquées dans l’un des exercice où la complexité au pire des cas est abordée.
En plus, une section a été dédiée à la comparaison du temps théorique (ordre de grandeur de la complexité)
au temps réel pour deux algorithmes implémentés en langage de programmation Matlab.

2.2 Série d’exercices du TD

Les exercices proposés dans cette section ont été proposés initialement par Pr. F. Belala. Les tableaux résumant
les solutions on été donnés par Pr. F. Belala, tandi que l’organisation, les explications et les illustrations
présentée ici sont celles de l’auteur.

Exercice 1

Analysez la portion de code suivante pour calculer sa complexité :

Algorithme exComp1
Déclarations :
···
Début
I1 i←1
I2 TQ (i≤N) :
I3 j←1
I4 TQ (j<i) :
I5 j←j+1
FTQ
I6 i←i+1
FTQ
Fin

29
 Chapitre 2 : Complexité algorithmique

Table 2.1: Complexité calculée de l’algorithme exComp1

Instruction/Bloc Nombre de fois d’exécution Coût

I1 1 θ(1)
I2 N+1 (N+1)*θ(1)
I3 N N*θ(1)
I4 N*(N+1)/2 (N*(N+1)/2)*θ(1)
I5 N*N*(N-1)/2 (N*(N-1)/2)*θ(1)
I6 N N*θ(1)
CoûtexComp1 (N ) = θ(1) ∗ [1 + (N + 1) + N + (N ∗ (N + 1)/2) + (N ∗ (N − 1)/2) + N ]
= θ(1) ∗ (N 2 + 3N + 1) ' O(N 2 )

Solution :

D’une façon similaire à l’exercice précédent, on commence par donner une table (Table 2.1) qui résume le calcul
de la complexité de l’algorithme exComp2 ; et puis on détaille ces calculs.

Complexité de l’instruction I1 :

L’instruction I1 s’exécute une seule fois, son coût est égale à θ(1). Il est important de distinguer entre les
notations θ et O. La première représente une estimation ; par exemple θ(1) représente une estimation du temps
nécessaire pour une seule opération élémentaire et θ(n) est une estimation du temps nécessaire pour effectuer n
opérations élémentaires. D’autre part, O exprime l’ordre de grandeur, O(1) représente donc toute complexité
constante et O(n) représente une complexité d’ordre polynomial. Par conséquent, on utilise dans ce support
la notation θ quand on calcule le nombre (approximatif) d’instructions de l’algorithme et on fait appel à la
notation O quand on passe à l’analyse de l’ordre de grandeur d’une portion de code.

Complexité du bloc d’instructions I2 :

La complexité de la boucle I2 (TQ · · · FTQ) est le résultat de la somme de la complexité du test i≤N et
la complexité des instructions internes ( I3 , I4 (son test + I5 ) et I6 ). Pour calculer la complexité d’un
algorithme, on commence par le calcul du nombre d’instructions et on passe ensuite à mesurer l’ordre de
grandeur.
→ Nombre de test dans la boucle TQ i≤N :
Le test de la boucle s’exécute N+1 fois. On observe que i prend la valeur initiale 1, s’incrément par 1 à
chaque itération et sa valeur finale est fixée à N+1. Il est important à noter qu’on doit bien savoir comment la
variable de contrôle de la boucle change ses valeurs, il n’y a pas donc une formule universelle pour calculer la
complexité d’une boucle. Le nombre d’opérations dans la clause de test est donc égal à (N+1) opérations.
→ Nombre de fois d’entrée dans la boucle TQ · · · FTQ :
Pour la boucle TQ, le nombre de fois d’exécutions du bloc interne est une fois moins le nombre d’exécution du
test. Si le test s’exécute K fois, on rentre dans la boucle K-1 fois. Dans cette première boucle, le test s’exécute
(N+1) fois, donc le bloc interne s’exécute N fois. Attention, juste multiplier la complexité des instructions
internes par N ne donne pas toujours le bon résultat, car N entrées dans la boucle n’implique pas forcément une
multiplication par N (voir exemple de l’exercice 2).

30
 Chapitre 2 : Complexité algorithmique

Complexité de l’instruction I3 :

L’instruction I3 fait une seule opération élémentaire, elle se répète dans la boucle N fois ; donc elle fait
globalement N opérations élémentaire.

Complexité du bloc d’instructions I4 , et de l’instruction I5 :

De la même façon du traitement du bloc d’instructions I2 , la complexité du bloc d’instructions I4 est le

résultat de la somme du nombre d’opérations dans la clause de test et le nombre d’opérations dans la boucle,
i.e. le nombre de fois d’exécution de l’instruction I5 .
A chaque fois l’algorithme rentre dans la boucle I2 , l’indice j s’initialise à 1 et s’incrémente régulièrement
(dans l’instruction I5 ) jusqu’à la valeur actuelle de i. Cette dernière elle-même change de 1 jusqu’à N. Donc,
on obtient les différentes valeurs de i et j comme suit :
Pour i=1, j prend la valeur 1, le test j<i est ‘faux’. Donc, on obtient 1 test et 0 exécution de l’instruction I5 .
Pour i=2, j prend les valeurs 1 et 2. Donc, on obtient 2 tests et 1 exécution de l’instruction I5 .
Pour i=3, j prend les valeurs 1, 2 et 3. Donc, on obtient 3 tests et 2 exécutions de l’instruction I5 .
···
Pour i=N, j prend les valeurs 1, 2, · · · N. Donc, on obtient N tests et N-1 exécutions de l’instruction I5 .
Pour i=N+1, on rentre pas dans la boucle I2 .
On peut donc calculer le nombre d’opérations du test pour les différentes valeurs de i, il s’agit de
(1+2+3+· · · +N) tests. Ce nombre n’est plus que la somme des éléments d’uns suite arithmétique avec base
égale à 1, le premier élément est 1 et le dernier est N. On obtient ainsi N*(N+1)/2 opérations de test.
Le nombre de fois d’entrée à la boucle I4 peut être calculé de la même façon. Pour les différentes valeurs
de i, on a 0+1+· · · +(N-1) exécutions. Donc on a N*(0+N-1)/2= N*(N-1)/2 exécutions de l’instruction I5 .
Cette valeur peut être directement déduit, comme déjà cité, de la relation : ‘Le nombre de fois d’entrée à la
boucle est égal au nombre de fois de test -1’.
On aura donc, la complexité du bloc composé de I4 et I5 est égale à [N*(N+1)/2 + N*(N-1)/2]
opérations élémentaires.

Complexité de l’instruction I6 :

L’instruction I6 exécute une opération élémentaire et s’exécute dans la boucle I2 qui s’exécute N fois.

Complexité de l’algorithme exComp1 :

Le coût de l’algorithme exComp1 est la somme des complexité des différentes instructions qui le composent. On
a donc :
CoûtexComp1 (N ) = θ(1)∗[1+(N +1)+N +(N ∗(N +1)/2)+(N ∗(N −1)/2)+N ] = θ(1)∗(N 2 +3N +1) ' O(N 2 ).

On dit que la complexité de cet algorithme est de l’ordre de N.

Exercice 2

Analysez la portion de code suivante pour calculer sa complexité :

31
 Chapitre 2 : Complexité algorithmique

Algorithme exComp2
Déclarations :
···
Début
I1 i←1
I2 TQ (i≤N) :
I3 j←1
I4 TQ (j≤M) :
I5 j←j*2
FTQ
I6 i←i+1
FTQ
Fin

Solution :

La table 2.2 résume le processus de calcul de complexité pour cet algorithme. Comme vu dans la table, il y a
une variable additionnelle k. Cette variable est utilisée pour exprimer le nombre de fois d’exécution du test du
bloc de la boucle I2, ainsi que le nombre de fois on rentre dans la boucle. On détaille dans la suite le processus
de calcul du coût de l’algorithme exComp2.

Table 2.2: Complexité calculée de l’algorithme exComp1

Instruction/Bloc Nombre de fois d’exécution Coût

I1 1 θ(1)
I2 N+1 (N+1)*θ(1)
I3 N N*θ(1)
I4 N*(k+1) N*(k+1)*θ(1)
I5 N*k N*k*θ(1)
I6 N N*θ(1)
CoûtexComp2 (M, N ) = 2 ∗ θ(1) + 4N θ(1) + 2N kθ(1)
= (2 + 4N + 2N (1 + log(M )))θ(1)
' O(N blog2 M c)

Complexité de l’instruction I1 :

L’instruction I1 s’exécute une seule fois. donc sa complexité est θ(1).

Complexité du bloc d’instructions I2 :

La variable i s’incrémente régulièrement de 1 à N+1. Donc, le bloc d’instructions I2 fait N+1 tests et rentre
dans la boucle N fois. Le code délimité par cette boucle s’exécute N fois. Mais il faut faire attention que le fait
d’exécuter un code N fois n’implique pas une opération de multiplication simple sera suffisante pour calculer sa
complexité. On garde dans la tête ici que le bloc I2 consiste en N+1 tests et N entrée à la boucle.

Complexité de l’instruction I3 :

Cette instruction contient une seule opération élémentaire et s’exécute N fois. Sa complexité est donc θ(1) ∗ N .

32
 Chapitre 2 : Complexité algorithmique

Complexité du bloc d’instructions I4 et de l’instruction I5 :

la variable j prend la valeur initiale 1. A chaque entrée à la boucle (quand le test est ‘vrai’), la valeur de j sera
doublée. Donc, la variable j prend les valeurs 1, 2, 4, · · · , bSup. La valeur bSup est la première puissance de 2
strictement supérieure à M.
Par exemple : si M=17 ; j prend les valeurs : 1,2, 4, 8, 16, 32.
Donc, il est claire que le nombre de fois de tests et d’entrée dans cette boucle n’est pas M+1 ou M comme la
boucle du bloc I2 .
Nombres de fois de tests et d’entrée à la boucle du bloc I4 :
A l’itération 1, → j=1
A l’itération 2, → j= 1*2
A l’itération 3, → j= 1*2*2
A l’itération k, → j= 1*2k-1
...
A la dernière itération,→ j= M ; d’où : M = 2( k − 1) k = 1 + Log2 (M ).
Pour être plus précis k = 1 + P artieEntière(Log2 (M )).
La fonction PartieEntère (symbolisée par bc) donne la valeur entière d’un nombre réel.
On a k+1 tests (car obn a un test en plus après la dernière itération) et K entrée à la boucle et le traitement
fait dans l’instruction I5 est le même. Tout ce bloc s’exécute N fois dans le bloc de la boucle externe ( I2 ).
Donc, Il y a : N ∗ (1 + bLog2 M c + 1) opérations de test (dans I4 ) et N ∗ (1 + bLog2 M c) opérations dans
le code interne (dans I5 ).

Complexité de l’instruction I6 :

Cette opération élémentaire est exécutée N fois.

Complexité de l’algorithme exComp2 :

Le coût de l’algorithme exComp2 est la somme des complexité des différentes instructions qui le composent. On
a donc :
CoûtexComp2 (M, N ) = θ(1) ∗ (2 + 6N + 2N bLog2 M c) ' O(N blog2 M c)

Exercice 3

On considère l’algorithme exComp3 suivant, sachant que l’ordre de grandeur du temps d’exécution de la
procédure Action est O(N ), déterminer celui de exComp3.

33
 Chapitre 2 : Complexité algorithmique

Algorithme exComp3
Déclarations :
Procédure Action (Données a, b : entier, Résultat p : entier)
i, j , p, M, N : entier
Début
I1 Pour i ← 1 à N :
I2 Pour j ← 1 à M :
I3 Action(i,j,p)
I4 Ecrire (p)
FPour
FPour
Fin

Solution :

La complexité de l’algorithme exComp3 est la somme des complexités des instructions et blocs d’instructions
qui le composent. Donc, Coût_exComp3(N,M)=Coût( I1 )+Coût( I2 )+Coût( I3 )+Coût( I4 ).
La table 2.3 résume le processus de calcul de complexité pour cet algorithme. On détaille dans la suite ce
calcul.

Table 2.3: Complexité calculée de l’algorithme exComp1

Instruction/Bloc Coût
I1 (N+1)* θ(1)
I2 N*(M+1)*θ(1)
I3 N*M*θ(N)
I4 N*M*θ(1)
CoûtexComp3 (M, N ) ' O(N 2 ∗ M )

Complexité du bloc d’instructions I1 :

La boucle pour s’exécute d’une manière similaire à une boucle TQ, avec la simple différence que le test est
l’incrémentation de la variable de contrôle i de la condition d’arrêt se fait dans la clause de test. Dans cette
clause, on a une application itérative d’un test de condition, une entrée à la boucle, suivi par une incrémentation
de l’indice i, jusqu’à aboutir à la valeur N+1. Donc, comme conventionné dans le cours de ce module, le test de
cette boucle exécute N+1 opérations. On a donc N entrées à la boucle.

Complexité du bloc d’instructions I2 :

D’une façon pareille, ce bloc d’instructions fait (M+1) opérations de test, et vu que le même bloc s’exécute de
la même manière à chaque itération de la boucle externe, on obtient donc : N*(M+1) opérations de test.

Complexité du bloc d’instructions I3 :

Cette instruction contient un appel à la procédure Action qui reçoit les variable i, j et p comme paramètres. Il
est donné par l’énoncé que la complexité de cette procédure est O(N ). Une question qui se pose donc est : ‘Si
la complexité d’une portion de code s’exprime en terme de la taille des entrées, devrons-nous exprimer cette
complexité en terme de i, j ou p ?’.

34
 Chapitre 2 : Complexité algorithmique

Il est à rappeler que le N est supposé représenter la taille des entrées et non pas les valeurs des entrées
elles-mêmes. Dans les algorithmes des exercices précédents, la taille de la donnée était elle-même sa valeur, mais
rien n’empêche que ça ne soit pas vrai. Par exemple, N dans notre exemple peut représenter la taille de p, qui
pourrait être un tableau, une matrice, etc.
La complexité de cette instruction isolée est O(N ). Puisque I3 se répète M fois dans le bloc I2 qui se
répète lui-même N fois dans le bloc I1 ; on obtient : Coût( I3 )=N*M*θ(N).

Complexité du bloc d’instructions I4 :

Cette instruction est une opération élémentaire. Elle se répète M fois dans le bloc I2 qui se répète lui-même N
fois dans le bloc I1 ; on obtient : Coût( I3 )=N*M*θ(1).

Complexité de l’algorithme exComp3 :

Le coût de l’algorithme exComp3 est la somme des complexité des différentes instructions qui le composent. On
a donc :
CoûtexComp3 (M, N ) = θ(1) ∗ ((N + 1) + N ∗ (M + 1) + (N ∗ M ∗ N ) + N ∗ M ) ' O(N 2 ∗ M )' O(N 3 )

Exercice 4

Evaluez la complexité maximale (au pire des cas : T[i] > Mem toujours vérifiée) du morceau de code suivant :

Algorithme exComp4
Déclarations :
···
Début
I1 Pour k ← 2 à N-1 :
I2 Mem=T[k]
I3 i←k-1
I4 TQ (i ≥1 et T[i] > Mem ) :
I5 T[i+1]←T[i]
I6 i←i-1
FTQ
I7 T[i+1]←Mem
FPour
Fin

Solution :

La complexité de l’algorithme exComp4 est la somme des complexités des instructions et blocs d’instructions
qui le composent.
La table 2.4 résume le processus de calcul de complexité pour cet algorithme. On détaille dans la suite ce
calcul.

35
 Chapitre 2 : Complexité algorithmique

Table 2.4: Complexité calculée de l’algorithme exComp1

Instruction/Bloc Coût
I1 (N-1)* θ(1)
I2 (N-2)*θ(1)
I3 (N-2)*θ(N)
I4 (N+1)(N-2)/2*θ(1)
I5 (N-1)(N-2)/2*θ(1)
I6 (N-1)(N-2)/2*θ(1)
I7 (N-2)*θ(1)
CoûtexComp3 (M, N ) = θ(1) ∗ (3N 2 /2 − N/2 − 6) ' O(N 2 )

Complexité du bloc d’instructions I1 :

Cette boucle fait (N-1) opérations élémentaires. Sa complexité est donc (N-1)θ(1). Le nombre de fois d’entrée à
la boucle est donc (N-2).

Complexité de l’instruction I2 :

Cette instruction exécute une opération élémentaire à chaque entrée à la boucle, donc, sa complexité est égale à
(N-2)θ(1).

Complexité de l’instruction I3 :

Il s’agit d’une incrémentation qui est estimée par une opération élémentaire. La complexité de cette instruction
est égale à (N-2)θ(1).

Complexité du bloc d’instructions I4 :

Avant de discuter la complexité de cette instruction, il est utile de rappeler la différence entre les trois annotation
rencontrées dans le domaine de calcul de complexité algorithmique : O, Ω et Θ. On résume la différence/relation
entre ces notations dans ce qui suit : 1
– f (n) est O(g(n)) ssi ∃ c ∈ R ∃ n0 ∈ N, f (n) ≤ cf (n) pour tout n ≥ n0 .
– f (n) est Ω(g(n)) ssi ∃ c ∈ R ∃ n0 ∈ N, f (n) ≥ cf (n) pour tout n ≥ n0 .
– f (n) est Θ(g(n)) ssi f (n) est O(g(n)) et f (n) est Ω(g(n)).
Pour simplifier, on peut dire que :
– f (n) est O(g(n)) signifie que g(n) décrit la borne supérieure de f (n).
– f (n) est Ω(g(n)) signifie que g(n) décrit la borne inférieure de f (n).
– f (n) est Θ(g(n)) signifie que g(n) décrit la borne exacte / l’approximation de f (n).

1
https ://[Link]/data-structures-and-algorithms/content/analysis/[Link]
https ://[Link]/data-structures/aysmptotic-notations, https ://[Link]/big-o-omega-theta/
https ://[Link]/dsa/asymptotic-notations

36
 Chapitre 2 : Complexité algorithmique

Projetant ces définitions sur les notions vues dans le cours et le TD du module ASD, on peut dire que : O
représente la complexité au pire des cas, Ω représente la compléxité au méilleur des cas et Θ est la complexité
approximative. Dans la plupart des cas, il serait plus utile à comparer les algorithmes à la base de la complexité
au pire.
Revenant à notre exercice, on trouve qu’il est supposé que la condition T[i] > Mem est toujours vrai, donc
le test ‘i ≥ 1 etT[i] > Mem’ sera équivalent à la condition ‘i ≥ 1’. Il s’agit donc de calculer la complexité au pire,
c’est ce qu’on a fait tout au long ce chapitre.

Complexité de I4 :

La variable i reçoit comme valeur initiale k-1 et est décrémentée jusqu’à arriver à la valeur 0 d’une façon
régulière. Donc, on a (k+1) tests et K entrées à la boucle. Il est à noter que la valeur de k change de 2 à (N-1).
On analyse selon ces valeurs le nombre de fois de test et le nombre de fois d’entrée à la boucle :
Pour k=2, i prend les valeurs 1, et 0. Donc, on obtient 2 tests et 1 exécution des instructions I5 et I6 .
Pour k=3, i prend les valeurs 2, 1, et 0. Donc, on obtient 3 tests et 2 exécutions des instructions I5 et I6 .
Pour k=4, i prend les valeurs 3, 2, 1, et 0. Donc, on obtient 4 tests et 3 exécutions des instructions I5 et I6 .
···
Pour k=N-1, i prend les valeurs (N-1), (N-2), · · · 0. Donc, on obtient ()N-1) tests et (N-2) exécutions des
instructions I5 et I6 .
On a donc [2+3+· · · (N-1)] tests et [1+2+3+· · · (N-2)] entrées à la boucle. La complexité de la clause de test,
I4 , est donc : θ(1)*((N-2)*(N+1)/2).

Complexité des instructions I5 et I6 :

Les instructions I5 et I6 s’exécutent ((N-2)*(N-1)/2) fois. La comlexité de chacune est donc ((N-2)*(N-
1)/2)*θ(1).

Complexité de l’instruction I7 :

Le nombre de fois d’exécution de cette instructions est égal à (N-2). Sa complexité est égale à (N-2)*θ(1).

Complexité de l’algorithme exComp4 :

Le coût de l’algorithme exComp3 est la somme des complexité des différentes instructions qui le composent. On
a donc :
CoûtexComp4 (M, N ) = θ(1) ∗ ((N − 1) + (N − 2) + (N − 2) + (N + 1)(N − 2)/2 + (N − 1)(N − 2)/2 + (N −
1)(N − 2)/2 + (N − 2)) = θ(1) ∗ (3N 2 /2 − N/2 − 6)' O(N 2 )

Exercice 5

On considère, pour effectuer la recherche du plus grand élément dans un tableau de N éléments entiers,
la recherche séquentielle et la recherche dichotomique. On s’intéresse à déterminer la complexité des deux
algorithmes.

37
 Chapitre 2 : Complexité algorithmique

NB : Le principe de la recherche du maximum d’un tableau par dichotomie est déjà expliqué dans l’énoncé de
l’exercice 8 du chapitre 1 (page 20).

Solution :

On commence par analyser la complexité temporelle de la recherche séquentielle du maximum dans un tableau.
La fonction rechSeq, donnée ici, représente la version la plus simple de cette recherche.

Fonction rechSeq(Donnée T : Tableau de N entiers, Données N : entier) : réel

max : réel
i : entier
I1 max ← -∞
I2 Pour i ← 1 à N :
I3 Si (T[i]>max) :
I4 max←T[i]
FSi
FPour
Retourner (max)
Fin

Dans cette fonction on trouve que :

– L’instruction I1 a une complexité égale à θ(1)
– L’instruction I2 a une complexité égale à (N+1)*θ(1)
– L’instruction I3 a une complexité égale à N*θ(1)
– L’instruction I4 a une complexité égale à N*θ(1)
Le coût de la fonction rechSeq est :
CoûtrechSeq (N ) = θ(1) ∗ (1 + (N + 1) + N + N ) = θ(1) ∗ (3N + 2)' O(N )

On passe maintenant à la version dichotomique de la recherhe du maxumum.

Fonction rechMaxDicho(Donnée T : Tableau de N entiers, Données indDeb : entier, Donnée indFin : entier) : réel
I1 Si (indDeb=indFin) :
I2 Retourner T(indDeb)
Sinon
I3 Si (rechMaxDicho(T, indDeb,(indDeb+indFin) div 2) > rechMaxDicho(T,((indDeb+indFin) div 2)+1, indFin))
:
I4 Retourner rechMaxDicho(T, indDeb,(indDeb+indFin) div 2)
Sinon
I5 Retourner rechMaxDicho(T, ((indDeb+indFin) div 2)+1, indFin)
FSi
FSi
Fin

Le calcul de la complexité d’une fonction récursive se fait de la même façon que celui d’une fonction
itérative. Il faut juste faire attention que lors d’exécution, on traite l’appel récursif comme étant un appel à un
sous-programme, comme déjà vu dans l’exercice 3 (l’appel à la procédure Action).
L’analyse de la fonction rechMaxDicho pour calculer sa complexité temporelle consiste en le calcule des
coûts des instruction et blocs d’instructions I1 – I5 . Il est naturel que l’analyse des instructions comprenant

38
 Chapitre 2 : Complexité algorithmique

l’appel récursif se fait récursivement jusquà obtenir une valeur de coût finale.
En plus des outils vus dans les exercices précédents, on pourra se faire aider par une illustration de calcul
de la complexité pour des tailles données des entrées, ce qui permettra de généraliser. Ensuite, on prouve la
formule trouvée, par récurrence par exemple.

Coût de la fonction rechMaxDicho pour différentes tailles du tableau T :

Pour un tableau d’un seul élément : la condition du cas trivial (’indDeb=indFin’) est vérifiée. Donc, en
plus de l’opération de test trouvée dans l’instruction I1 , l’algorithme exécute l’instruction I2 qui contient une
seule opération élémentaire. On obtient donc pour un tableau d’un seul élément une complexité égale 2*θ(1).
Pour un tableau de deux éléments : on comptabilise les opérations suivante :
– un test dans l’instruction I1 , qui donne une valeur égale à ‘faux’.
– un test dans l’instruction I3 . Ce test contient deux appels de rechMaxDicho pour deux tableaux
contenant chacun un seul élément. Ces deux appels nécessitent chacun un temps d’exécution égal àθ(1),
comme juste calculé. Ça donne donc (2+2+1) opérations, i.e. un coût égale à 5*θ(1).
– l’exécution de l’une des deux instructions I4 ou I5 . On suppose que la valeur calculée dans le test
reste stockée dans le cache, on ne comptabilise donc que l’opération retourner. Ceci donne θ(1) comme
coût pour I4 et le même coût pour I5 .
Le coût de la fonction rechMaxDicho pour un tableau à deux éléments est donc égal à (1+5+1)*θ(1)=7*θ(1).
Pour un tableau de trois éléments : on comptabilise les opérations suivante :
– un test dans l’instruction I1 , qui donne une valeur égale à ‘faux’.
– un test dans l’instruction I3 . Ce test contient deux appels de rechMaxDicho pour deux tableaux ayant
comme tailles 1 et 2. Ces deux appels nécessitent 2 et 7 opérations respectivement (2 pour un tableau de
taille 1 et 7 pour un tableau de taille 2). Ça donne donc (2+7+1) opérations, i.e. un coût égale à 10*θ(1).
– l’exécution de l’une des deux instructions I4 ou I5 . On suppose que la valeur calculée dans le test
reste stockée dans le cache, on ne comptabilise donc que l’opération retourner. Ceci donne θ(1) comme
coût pour I4 et le même coût pour I5 .
Le coût de la fonction rechMaxDicho pour un tableau à trois éléments est donc égal à (1+10+1)*θ(1)=12*θ(1).
Pour un tableau de quatre éléments : Le coût de la fonction rechMaxDicho pour un tableau à quatre
éléments est égal à (1+15+1)*θ(1)=17*θ(1).
On observe donc pour différentes tailles du tableau T, les coût de la fonction rechMaxDicho sont comme suit :
Pour Taille(T)=1 : la complexité de rechMaxDicho est 2 ∗ θ(1) = θ(1) ∗ (5 ∗ (1 − 1) + 2)
Pour Taille(T)=2 : la complexité de rechMaxDicho est 7 ∗ θ(1) = θ(1) ∗ (5 ∗ (2 − 1) + 2)
Pour Taille(T)=3 : la complexité de rechMaxDicho est 12 ∗ θ(1) = θ(1) ∗ (5 ∗ (3 − 1) + 2)
Pour Taille(T)=4 : la complexité de rechMaxDicho est 17 ∗ θ(1) = θ(1) ∗ (5 ∗ (4 − 1) + 2)
Une formule générale émerge :
Pour Taille(T)=N : la complexité de rechMaxDicho est θ(1) ∗ (5 ∗ (N − 1) + 2)
On doit ensuite prouver cette formule. On opte pour la preuve par récurrence :
1. La formule est vraie pour N=1.
2. On suppose la formule vraie pour N et on vérifie sa vérité pour N+1. Pour un tableau de taille égale à N+1,
on aura 5 opérations en plus par rapport au cas du tableau de taille N : le cas trivial sera temporisé par une

39
 Chapitre 2 : Complexité algorithmique

étape. On obtient donc :

Pour Taille(T)=N+1 on a une complexité égale à : θ(1) ∗ (lacomplexitéderechM axDicho) + 5 = θ(1) ∗
(5 ∗ (N − 1) + 2) + 5 = θ(1) ∗ (5 ∗ (N ) + 2) = θ(1) ∗ (5 ∗ ((N + 1) − 1) + 2).
La formule est donc vraie pour un tableau de taille égale à N+1.
On conclut donc que :
CoûtrechM axDicho (N ) = θ(1) ∗ (5 ∗ (N − 1) + 2) ' O(N )

Les deux fonctions rechSeq et rechMaxDicho, malgré qu’elles ont des complexités approximatives différentes,
ont le même ordre de grandeur de complexité, O(N ). Ceci est équivalent à dire que ‘Quand la taille du tableau
tend vers l’infini, les fonctions rechSeq et rechMaxDicho nécessitent presque le même temps pour être exécutées’.
Il est à noter que cette équivalence d’ordre de grandeur de complexité n’est pas toujours vraie.

2.3 Complexité théorique et temps d’exécution

Une illustration de l’influence de la complexité algorithmique sur le temps réel d’exécution est donnée dans
cette section. Soit les deux procédures A, B définies dans les deux pseudo-codes suivants :

Procédure A(Donnée tab : Tableau de N entiers, Données N : entier)

i : entier
Pour i ← 1 à N :
tab[i]←tab[i]+1
FPour
Fin

Procédure B(Donnée tab : Tableau de N entiers, Données N : entier)

i : entier
j : entier
Pour i ← 1 à N :
Pour j ← 1 à N :
tab[i]←tab[i]+1
FPour
FPour
Fin

1. Convertir ces pseudo-code en un codes dans un langage de programmation de votre choix.

2. Pour chaque procédure, exécuter le programme équivalent pour des tableaux d’entrée de tailles : N= 1, 2,
3, · · · , 100. Mesurer le temps d’exécution effectif pour chaque appel.
3. Tracer les courbes Y = tempsExA(N ) et Y = tempsExB(N ) pour les valeurs mesurées.
4. Comparer la complexité théorique à celle mesurée dans les trois cas.
Solution : On présente ici le code Matlab équivalent à ces deux procédures , ainsi que le code du programme
principal qui les appelle. Ce dernier fait des appels à ces procédures pour des valeurs différentes de N, calcule le
temps d’exécution et trace les courbes respectueuses. La table 2.5 illustre des extraits des temps d’exécution
obtenus pour les différentes tailles du tableau passé aux appels des procédures A et B, programmées en Matlab.
Les figures qui suivent représentent la comparaison entre le temps d’exécution effectif et la complexité théorique
dans les deux cas.

40
 Chapitre 2 : Complexité algorithmique

Listing 2.1: Code Matlab pour mesurer le temps des procédures A, B et C

1 function [mx] = A(tab,N)
2 for i=1:N
3 tab(i)=tab(i)+1;
4 end
5
6 function [mx] = B(tab,N)
7 for i=1:N
8 for j=1:N
9 tab(i)=tab(i)+1;
10 end
11 end
12
13 %%%%%%%%%%%% Programme principal %%%%%%%%%%%%
14 clear all
15 timeA=[];
16 timeB=[];
17 k=1;
18
19 for N=[Link]
20 T=randperm(N);
21 indices(k)=N;
22 tic
23 A(T,N);
24 timeA(k)=toc;
25 tic
26 B(T,N);
27 timeB(k)=toc;
28 k=k+1;
29 end
30
31 c=polyfit(indices,timeA,1);
32 y_est_A = polyval(c,indices);
33 figure
34 plot(timeA,‘*b’)
35 hold on
36 plot(y_est_A,‘-r’,‘Linewidth’,1.5)
37 xlabel(‘Taille du tableau’);
38 ylabel(‘Temps’);
39 legend(‘Reelle’,‘Theorique’);
40
41 fB=fit(indices’,timeB’,‘poly2’);
42 figure
43 plot(timeB,‘*b’);
44 hold on
45 plot(fB(indices),‘-r’,‘Linewidth’,1.5);

41
 Chapitre 2 : Complexité algorithmique

46 xlabel(‘Taille du tableau’);
47 ylabel(‘Temps’);
48 legend(‘Reelle’,‘Theorique’);

Table 2.5: temps d’exécution pour chaque taille du tableau pour les fonctions A,B et C en Matlab

Procédure A Procédure B
N tempsExe (mS) N tempsExe (mS)
1 1.21 1 1.25
1 ∗ 105 1.38 1 ∗ 102 0.88
5 2
2 ∗ 10 1.06 2 ∗ 10 0.77
5 2
3 ∗ 10 1.45 3 ∗ 10 0.86
4 ∗ 105 2.72 4 ∗ 102 1.95
5 2
5 ∗ 10 2.31 5 ∗ 10 2.11
5 2
6 ∗ 10 3.35 6 ∗ 10 2.98
7 ∗ 105 3.62 7 ∗ 102 4.09
5 2
8 ∗ 10 3.74 8 ∗ 10 3.20
5 2
9 ∗ 10 4.44 9 ∗ 10 1.75
10 ∗ 105 4.89 10 ∗ 102 2.14
5 2
11 ∗ 10 5.43 11 ∗ 10 2.71
5 2
12 ∗ 10 5.98 12 ∗ 10 3.21
5 2
13 ∗ 10 6.59 13 ∗ 10 3.71
14 ∗ 105 7.24 14 ∗ 102 4.56
5 2
15 ∗ 10 7.56 15 ∗ 10 4.93
5 2
16 ∗ 10 7.95 16 ∗ 10 5.50
17 ∗ 105 8.58 17 ∗ 102 6.35
5 2
18 ∗ 10 9.47 18 ∗ 10 7.48
5 2
19 ∗ 10 9.85 19 ∗ 10 8.08

0.01

0.009 Coût mésuré

Complexité Théorique

0.008

0.007
Temps d'exécution

0.006

0.005

0.004

0.003

0.002

0.001

0
0 2 4 6 8 10 12 14 16 18 20
Taille du tableau
Figure 2.1: Complexité théorique vs complexité réelle pour un programme de coût BigO(N )

42
 Chapitre 2 : Complexité algorithmique

Figure 2.2: Complexité théorique vs complexité réelle pour un programme de coût BigO(N 2 )

2.4 Conclusion

Ce chapitre a traité la notion de complexité algorithmique. On a opté pour la complexité dans le pire des cas O.
Les autres types d’analyse de complexité, Θ et Ω , ont été expliqués brièvement. En effet, c’est le premier type
qui nous intéresse dans la pratique : on analyse les algorithmes dans le cas général et on prévoit le pire des cas.

43
 Chapitre
3
Types abstraits de données, TAD

3.1 Introduction

L’objectif de ce chapitre est de faire apprendre à l’étudiant les éléments de base des types abstraits de données.
La maitrise de la notion de TAD nous permet de concevoir des algorithmes le plus indépendamment possible des
langages de programmation. On vise donc de créer des algorithmes génériques qui seront facilement extensibles
à plusieurs applications et à plusieurs langages de programmation.
La série des exercices 1 corrigée sera enrichie par un exemple de conception et d’implémentation du TAD
ARBRE dans la section 3.4.

3.2 Série d’exercices du TD

Exercice 1

Dans un plan cartésien, la structure de donnée cercle est définie par les coordonnées de son centre et son rayon.
1. Compléter le TAD CERCLE décrivant cette structure de donnée.

TAD CERCLE Variables :

Utilise : REEL u,v,r : réel, d : cercle
Sorte : · · · · · · · · · Préconditions :
Opérations : Pré(nouveau-cercle(u,v,r)) définie ssi · · · · · ·
Nouveau-cercle : réel, réel, réel → cercle Axiomes :
x-centre : cercle → réel Rayon(nouveau -cercle(u, v, r)) ≡ r
y-centre : · · · · · · · · · → réel x-centre(· · · · · · · · · )≡ u
rayon : cercle → · · · · · · · · · y-centre(nouveau -cercle(u, v, r))≡ V

2. Donner le type des opérations (internes constructeurs, internes non constructeurs, observateurs) de la signature
correspondante.

1
Proposée principalement par Pr. F. Belala

44
 Chapitre 3 : Types abstraits de données, TAD

3. Enrichir le TAD CERCLE par les opérations :

a. Surface : qui calcule la surface d’un cercle
b. _ _ appartient à_ : qui teste si un point de coordonnées x et y appartient à un cercle C.

Solution :

1. Compléter le TAD CERCLE décrivant cette structure de donnée.

TAD CERCLE Variables :

Utilise : REEL, BOOLEEN u,v,r : réel, d : cercle
Sorte : cercle Préconditions :
Opérations : Pré(nouveau-cercle(u,v,r)) définie ssi r>0
Nouveau-cercle : réel, réel, réel → cercle Axiomes :
x-centre : cercle → → réel Rayon(nouveau -cercle(u, v, r)) ≡ r
y-centre : cercle → réel x-centre(nouveau-cercle(u,v,r))≡ u
rayon : cercle → réel y-centre(nouveau -cercle(u, v, r))≡ V

2. Donner le type des opérations (internes constructeurs, internes non constructeurs, observateurs) de la signature
correspondante.
Il est utile de rappeler brièvement la définition de ces types d’opérations :
– Une opération est dite interne constructeur “si elle rend un résultat d’une sorte définie” en opérant sur
des données de sortes prédéfinies (déclarées dans la partie Ùtilise’). Ces opérations servent à construire
les valeurs d’une sorte.
– Une opération est dite interne non constructeur si elle rend un résultat d’une sorte définie mais ne
construit pas de nouvelles valeurs pour cette sorte. Ce type d’opérations ne crée pas des
données il fait juste l’association entre données déjà créées.
– Une opération est dite observateur sur une sorte définie si elle rend un résultat d’une sorte prédéfinie et
possède au moins un argument de sorte définie.
On peut donc classifier les opérations du TAD CERCLE comme suit :
→ Oprérations internes constructeur : nouveau-cercle
→ Oprérations internes non constructeur : /
→ Oprérations observateur : x-centre, y-centre, rayon
3. Enrichir le TAD CERCLE par les opérations :
a. surface : qui calcule la surface d’un cercle
b. _ _ appartient à_ : qui teste si un point de coordonnées x et y appartient à un cercle C.
Enrichir un TAD par une opération consiste en la donnée de deux éléments :
1. Définir le profile de cette opération : en plus de la syntaxe de l’opération, on doit spécifier les sortes de
ses entrées et son résultat.
2. Définir sa sémantique à travers un ensemble d’axiomes : c’est l’expression de l’opération en utilisant des
opérations basique ou plus simples de la sorte en cours ou des sortes qui figurent dans la partie ‘Utilise’
du TAD.
Profil de l’opération surface :
surface : cercle → réel

45
 Chapitre 3 : Types abstraits de données, TAD

Axiomes pour l’opération surface :

surface(d)≡rayon(d) * rayon(d) * 3.14
Comme bien vu, l’objectif de l’axiome est de donner une autre expression de l’opération en utilisant des
opérations plus simples. Ici, on a exprimé l’opération ‘surface’ à l’aide des opérations ‘rayon’ (du TAD cercle),
‘*’ (du TAD REEL) et en utilisant une donnée construite par le TAD REEL : ‘3.14’.
Profil de l’opération appartient :
_ _ appartient à _ : réel, réel → booléen
Axiomes pour l’opération appartient :
u v appartient à d ≡ (x-centre(d) − u)2 − (y-centre(d) − v)2 =rayon(d)2
Cet axiome simplifie la sémantique de l’opération appartient en l’exprimant en termes d’opération plus simple
des TAD CERCLE et REEL : ‘x-centre’, ‘y-centre’, ∧, − et ‘rayon’.
Il est aussi important d’enrichir la partie ‘Variables’, ‘Préconditions’ et même la partie ‘Utilise’ si nécessaire
quand on enrichie le TAD par des opérations.

Exercice 2

Soit le TAD suivant décrivant la structure de données graphe composée d’un ensemble de nœuds et un ensemble
d’arcs. Chaque arc relit deux nœuds

TAD GRAPHE
Variables :
Utilise : Nœud, ENTIER
a,b : arc, n1, n2 : nœud
Sortes : arc, graphe
Précondotions :
Opérations :
a•b définie ssi puit(a)=source(b)
1. < _, _ > : nœud, nœud → arc
Axiomes :
2. _ • _ : arc, arc → arc
1. source(<n1, n2>) ≡ n1
3. g-nœud : nœud → graphe
2. source(a•b)≡ source(a)
4. g-arc : arc → graphe
3. puit(<n1, n2>)≡ n2
5. source : arc → nœud
4. puit(a•b)≡ puit(b)
6. puit : arc → nœud

1. Donner le type des opérations (internes constructeurs, internes non constructeurs, observateurs) de la signature
correspondante.
On observe que le TAD GRAPHE définie deux types de sortes : arc et graphe. Donc, chaque opération qui
permet de construire des données de l’une de ces deux sortes, à partir de sortes prédéfinies, est une opération
interne constructeur. On obtient donc comme type d’opérations :
→ Opérations internes constructeur : < _, _ >, _ • _, g-nœud, g-arc
→ Opérations internes non constructeur : pas d’opérations de ce type
→ Opérations observateur : source, nœud
2. Indiquer parmi les données suivantes celles qui sont incorrectes syntaxiquement et corriger les. Préciser alors
la sorte de chacune de ces données.
(a) <A, C>•<D, E>•<E, F>
(b) Annaba, Médéa>•<Médéa, Ghardaïa>
(c) g-arc(<Annaba, Médéa>•<Médéa, Ghardaïa>)

46
 Chapitre 3 : Types abstraits de données, TAD

(d) source(<A, D>•<D, E>•<E, F>, A)

(e) puit(<A, C>•<C, E>•<E, F>)
3. Donner la notation (écriture) syntaxique correcte du graphe suivant selon cette signature :

12
45

32
27

Solution :

1. Donner le type des opérations (internes constructeurs, internes non constructeurs, observateurs) de la signature
correspondante.
On observe que le TAD GRAPHE définie deux types de sortes : arc et graphe. Donc, chaque opération qui
permet de construire des données de l’une de ces deux sortes, à partir de sortes prédéfinies, est une opération
interne constructeur. On obtient donc comme type d’opérations :
→ Oprérations internes constructeur : < _, _ >, _ • _, g-nœud, g-arc
→ Oprérations internes non constructeur : pas d’opérations de ce type
→ Oprérations observateur : source, nœud
2. Indiquer parmi les données suivantes celles qui sont incorrectes syntaxiquement et corriger les. Préciser alors
la sorte de chacune de ces données.
Pour qu’une donnée soit correcte syntaxiquement, elle doit respecter la syntaxe des opérations du TAD et
les préconditions. On analyse ces données selon la définition du TAD GRAPHE :
(a) <A, C>•<D, E>•<E, F> : Cette donnée n’est pas correcte syntaxiquement car la précondition indique
que l’opération a•b est définie ssi puit(a)=source(b), chose qui n’est pas vérifiée dans cette expression ; <A,
C>≡ C (selon les axiomes). Pour la corriger, on propose de remplaced la source de l’arc <D, E> par C ou le
puit de <A, C> par D ; on obtient donc : <A, C>•<C, E>•<E, F> ou <A, D>•<D, E>•<E, F>. La sorte
de cette donnée est ‘arc’, il s’agit de :
1. appliquer l’opération < _, _ > sur les noeuds A et C, qui donne un arc : <A, C>
2. appliquer l’opération < _, _ > sur les noeuds C et E, qui donne un arc : <C, E>
3. appliquer l’opération _ • _ sur les arcs <A, C> et <C, E>, qui donne l’arc <A, C>•<C, E>
4. appliquer l’opération _ • _ sur les arcs <A, C>•<C, E> et <E, F>, qui donne l’arc <A, C>•<C,
E>•<E, F>
(b) <Annaba, Médéa>•<Médéa, Ghardaïa> : Cette donnée est correcte syntaxiquement et nous donne
un élément de sorte ‘arc’.
(c) g-arc(<Annaba, Médéa>•<Médéa, Ghardaïa>) : Cette donnée est correcte syntaxiquement et nous
donne un élément de sorte ‘graphe’. L’opération ‘g-arc’, selon la signature du TAD GRAPHE, reçoit un arc,
appartir duquel un graphe est construit.
(d) source(<A, D>•<D, E>•<E, F>, A) : Cette donnée est correcte syntaxiquement et nous donne un

47
 Chapitre 3 : Types abstraits de données, TAD

élément de sorte ‘nœud’. L’opération ‘source’, selon la signature du TAD GRAPHE, reçoit un graphe, et nou
donne un élément de sorte ‘nœud’.
(e) puit(<A, C>•<C, E>•<E, F>) : Cette donnée est incorrecte syntaxiquement parceque l’opération
‘source’ s’applique sur un élément de sorte ‘graphe’ alors que l’expression “<A, C>•<C, E>•<E, F>, A” n’est
pas de type graphe. Sa correction se fait naturellement en supprimant la partie “, A”. On aura donc : source(<A,
C>•<C, E>•<E, F>). Cette données est de sorte nœud.
3. Donner la notation (écriture) syntaxique correcte du graphe suivant selon cette signature :

12
45

32
27

Selon la signature du TAD, pour construire (exprimer) une donnée de type graphe, il suffit d’appliquer l’une ou
un ensemble des opérations g-nœud (qui permet de construire un graphe à partir d’un nœud) et g-arc (qui crée
un graphe à partir d’un arc). Le graphe illustrée dans la figure est composé de l’union de deux sous-graphes qui
ne pourront pas être exprimés par une simple opération, ont construit ainsi notre graphe comme suit :
g-arc(<12, 27>)
g-arc(< 12, 45 > • < 45, 27 > • < 27, 32 > • < 32, 45 >)
Ces deux expressions ensembles définissent notre graphe.

Exercice 3

Soit le TAD suivant décrivant la structure de données LIVRE. La donnée livre étant définie par son auteur, son
contenu (texte) et son éditeur.

TAD LIVRE
Variables :
Utilise : AUTEUR, TEXTE, EDITEUR, · · · · · ·
L1, L2 : livre, a : auteur, t : texte, e : éditeur
Sorte : livre
Précondotions :
Opérations :
fusion(L1, L2) définie ssi mêmeA(L1, L2) et mêmeE(L1, L2)
|_, _, _| : auteur, texte, éditeur → livre
Axiomes : 1. AL(|a, t, e|) ≡ a
_ • _ : texte, texte → texte
2. TL(|a, t, e|) ≡ t
AL : livre → auteur
3. EL(|a, t, e|) ≡ · · ·
TL : · · · · · · → texte
4. fusion(L1, L2) ≡ |AL(L1), TL(L1)•TL(L2), EL(L1)|
EL : livre → éditeur
5. mêmeA(L1, L2) ≡ si AL(L1) == AL(L2) alors
fusion : livre, livre → livre
vrai sinon faux
mêmeA : livre, livre → · · ·
6. mêmeE(L1, L2)≡ si · · · · · · alors vrai sinon faux
mêmeE : livre, livre → booléen

1. Compléter le TAD LIVRE : voir la figure

2. Donner le type des opérations (internes constructeurs, internes non constructeurs, observateurs) de la signature
correspondante.

48
 Chapitre 3 : Types abstraits de données, TAD

3. Réécrire l’axiome 4 d’une autre manière.

4. Proposer une implémentation pour les sortes de ce TAD ainsi que l’opération |_, _, _|

Solution :

1. Compléter le TAD LIVRE : voir la table 3.1

Table 3.1: TAD LIVRE

Variables :
TAD LIVRE
L1, L2 : livre, a : auteur, t : texte, e : éditeur
Utilise : AUTEUR, TEXTE, EDITEUR, booléen
Précondotions :
Sorte : livre
fusion(L1, L2) définie ssi mêmeA(L1, L2) et mêmeE(L1, L2)
Opérations :
Axiomes : 1. AL(|a, t, e|) ≡ a
|_, _, _| : auteur, texte, éditeur → livre
2. TL(|a, t, e|) ≡ t
_ • _ : texte, texte → texte
3. EL(|a, t, e|) ≡ e
AL : livre → auteur
4. fusion(L1, L2) ≡ |AL(L1), TL(L1)•TL(L2), EL(L1)|
TL : livre → texte
5. mêmeA(L1, L2) ≡ si AL(L1) == AL(L2) alors
EL : livre → éditeur
vrai sinon faux
fusion : livre, livre → livre
6. mêmeE(L1, L2)≡ si EL(L1) == EL(L2) alors
mêmeA : livre, livre → booléen
vrai sinon faux
mêmeE : livre, livre → booléen
alors vrai sinon faux

2. Donner le type des opérations (internes constructeurs, internes non constructeurs, observateurs) de la signature
correspondante.
→ Opérations internes constructeur : |_, _, _| ; cette opération permet de construire une livre ) en
combinant les informations d’un ‘auteur’, d’un ‘text’ et d’un ‘éditeur’. On remarque que le résultat obtenu,
de type ‘livre’, ne peut pas être généré autrement. C’est une opération constructeur de base.
→ Opérations internes non constructeur : fusion. Cette opération prend deux éléments de type livre
et les fusionne ; mais elle n’est pas constructeur car son résultat pourra être généré par des opération
constructeur de base (voir l’axiome 4).
→ Opérations observateur : AL, TL, EL, mêmeA, mêmeE. Toutes ces opérations donnent des résultats
de type sortes prédéfinies.
NB : l’opération •, malgré qu’elle est définie ici, concerne le TAD TEXTE et pas le TAD LIVRE.
On peut la voir comme un enrichissement du TAD TEXTE.
3. Réécrire l’axiome 4 d’une autre manière.
Cet axiome est exprimé en termes d’opérations de haut niveau : AL, TL et ELn qui sont des opération
observateur. Une manière possible pour le réécrire autrement est d’utiliser les opérations constructeur. On
commence par nous poser la question : ’Comment peut-t-on exprimer les données L1 et LE en utilisant les
opérations constructeur ?’
Si on suppose que le livre L1 est construit à partir des information de l’auteur a1, le texte t1 et l’éditeur
e1 ; et que le livre L2 est construit à partir des information de l’auteur a2, le texte t2 et l’éditeur e2. Donc
on peut réécrire les données L1 et L2 comme |a1,t1,e1| et |a2,t2,e2|, respectivement. D’autre part, on a la
précondition ‘fusion(L1, L2) définie ssi mêmeA(L1, L2) et mêmeE(L1, L2)’ qui doit être vérifiée ; alors : on doit
avoir a1=a2 et e1=e2. Si cette condition est vérifiée, il nous reste à décider comment exprimer la partie droite
de l’axiome à proposer. L’idée est simple, selon le même axiome, on fusionne la partie texte des deux livre en
utilisant l’opération •. On obtient ainsi :

49
 Chapitre 3 : Types abstraits de données, TAD

fusion(|a,t1,e|, (|a,t2,e|) ≡|a, t1•t2, e|, où : a=a1=a2 et e=e1=e2.

4. Proposer une implémentation pour les sortes de ce TAD ainsi que l’opération |_, _, _|
Les sortes ‘auteur’, ‘texte’ et ‘éditeur’ peuvent être implémentées par “chaine de caractères", la sorte livre
par un “enregistrement" à trois champs :
Type : livre = enregistrement

 texte : chaine


auteur : chaine


 éditeur : chaine

Fin
L’opération |_, _, _| par la fonction ‘constLivre’ suivante :

Fonction constLivre(Données a, t, e : Chaine) : livre

L : livre
Début
[Link]= a
[Link]= t
L.éditeur= e
Retourner (L)
Fin
Fin

Exercice 4

Soit le TAD suivant décrivant la structure de données MAP formée d’une collection de paires de données.
Chaque paire de donnée est composée de clé/valeur.

TAD MAP
Utilise : KEY, VALUE, BOOLEEN Variables : k, k1 : key ; m : map
Sortes : pair, map Précondotions :
Opérations : get(k,m) est définie ssi containsKey(k,m)
< _, _ > : key, value → pair remove(k,m) est définie ssi containsKey(k,m)
_ • _ : pair, map → map Axiomes :
emptymap : → map containsKey(k, emptymap)≡ faux
containsKey : key, map → bool containsKey(k, <k1,v>•m) ≡ si k==k1 alors vrai sinon containsKey(k,m)
get : key, map → value get(k, <k1,v>•m) ≡ si k==k1 alors v sinon get(k,m)
remove : key, map → map remove(k, <k1,v>•m) ≡ si k==k1 alors m sinon <k1,v>• remove(k,m)
replace : key, value, map → map isEmpty(m) ≡ si m==emptymap alors vrai sinon faux
isEmpty : map → bool

1. Donner le type des opérations (internes constructeurs, internes non constructeurs, observateurs) de la signature
correspondante.
2. Donner la notation (écriture) syntaxique correcte de map1 et map2 selon cette signature.

clé id1
map1 :
valeur 5

<id1, 5>

50
 Chapitre 3 : Types abstraits de données, TAD

clé id1 id2 id3

map2 :
valeur 5 3.12 omar

3. Enrichir ce TAD par l’opération "replace" qui remplace une valeur dans une map donnée, connaissant sa clé.

Solution :

1. Donner le type des opérations (internes constructeurs, internes non constructeurs, observateurs) de la signature
correspondante.
→ Opérations internes constructeur : < _, _ >, _ • _, emptymap
→ Opérations internes non constructeur : remove, replace :
→ Opérations observateur : containsKey, get, isEmpty
2. Donner la notation (écriture) syntaxique correcte de map1 et map2 selon cette signature.

clé id1
map1 :
valeur 5

Cette donnée peut être exprimée comme suit :

<id1, 5> • emptymap

clé id1 id2 id3

map2 :
valeur 5 3.12 omar

Cette donnée peut être exprimée comme suit :

<id1, 5> • <id2, 3.12>• <id3, omar> • emptymap
3. Enrichir ce TAD par l’opération "replace" qui remplace une valeur dans une map donnée, connaissant sa clé.
Profil :
replaceValue : key, value, map → map
Variables :
v1 : value
Précondition :
replace(k,v,m) est définie ssi containsKey(k,m)
Axiome :
replace(k,v,<k1,v1> • m) ≡ si k=k1 alors <k,v>•m sinon <k1,v>•replace(k,v,m)

Exercice 5

On se propose de définir un robot et ses déplacements dans un plan à deux dimensions à l’aide d’un TAD. Le
robot est donc défini par deux valeurs : sa position dans le plan exprimée par les valeurs x et y et sa direction
exprimée par l’angle qu’il forme avec l’axe des X. Le robot peut se déplacer d’une seule unité vers l’avant ou
vers l’arrière, vers le haut ou vers le bas comme il peut aussi changer sa direction en tournant de plus ou de
moins 90◦ .

51
 Chapitre 3 : Types abstraits de données, TAD

1. Compléter ce TAD ROBOT, donné dans la figure 3.1.

Figure 3.1: TAD ROBOT complété

TAD ROBOT
Utilise Direction, …
Sorte robot
Opérations
Créer-robot : entier, entier, direction → …
Robot-x : robot → entier
Robot-y : …
Robot-direction : …
_se-déplace-avant : robot → robot
_se-déplace-arrière : …
_se-déplace-haut : …
_se-déplace-bas : …
_tourne-plus : …
_tourne-moins : …
Axiomes
Robot-x (créer-robot((x, y, d))  x
Robot-y (créer-robot((x, y, d))  …
Robot-direction (créer-robot((x, y, d))  …
Créer-robot(x, y, d)se-déplace-avant  créer-robot(x+1, y, d)
Créer-robot(x, y, d)se-déplace-arrière  …
Créer-robot(x, y, d)se-déplace-haut  …
Créer-robot(x, y, d)se-déplace-bas  créer-robot(x, y-1, d)
S tourne-plus  créer-robot(…, …, Robot-direction(S)+90°)
S tourne-moins  …
Variables
x, y : …, d : …, S : …

2. Donner le type de chaque opération définie dans la signature de ce TAD.

3. Indiquer parmi les données suivantes celles qui sont incorrectes syntaxiquement et corriger les.
(a) Créer-robot(2, 2, 3, 50◦ )
(b) Créer-robot(3, 5, 60◦ )se-déplace-avant
(c) Se-déplace-arrière(Créer-robot(3, 5, 65◦ ))
(d) Tourner-moins(Créer-robot(-3, 5, 60◦ ))
(e) ((Créer-robot(-3, 5, 60◦ ) tourne-plus) tourne-plus) se-déplace-haut
(f) ((Créer-robot(-3, 5, 60◦ ) se-déplace-haut) tourne-plus) tourne-plus
4. Indiquer parmi les données correctes précédentes celles qui sont équivalentes (ont le même sens) selon les
axiomes proposés.
5. Enrichir ce TAD par l’opération _est-dans-champ-vision_ qui teste si un robot S1 est dans le champ de
vision de S2 (le champ de vision d’un robot est de plus ou moins 45◦ ).
Solution :
1. Compléter ce TAD ROBOT ainsi écrit.
La version complétée du TAD ROBOT est donnée dans la figure 3.2.
2. Donner le type de chaque opération définie dans la signature de ce TAD.
→ Opérations internes constructeur : Créer-robot
→ Opérations internes non constructeur : _se-déplace-avant, _se-déplace-arrière, _se-déplace-haut,
_se-déplace-bas, _tourne-plus, _tourne-moins
→ Opérations observateur : Robot-x, Robot-y, Robot-direction

52
 Chapitre 3 : Types abstraits de données, TAD

Figure 3.2: TAD ROBOT complété

TAD ROBOT
Utilise Direction, Entier
Sorte robot
Opérations
Créer-robot : entier, entier, direction → robot
Robot-x : robot → entier
Robot-y : robot → entier
Robot-direction : robot → direction
_se-déplace-avant : robot → robot
_se-déplace-arrière : robot → robot
_se-déplace-haut : robot → robot
_se-déplace-bas : robot → robot
_tourne-plus : robot → robot
_tourne-moins : robot → robot
Axiomes
Robot-x (créer-robot((x, y, d))  x
Robot-y (créer-robot((x, y, d))  y
Robot-direction (créer-robot((x, y, d))  d
Créer-robot(x, y, d)se-déplace-avant  créer-robot(x+1, y, d)
Créer-robot(x, y, d)se-déplace-arrière  créer-robot(x-1, y, d)
Créer-robot(x, y, d)se-déplace-haut  créer-robot(x, y+1, d)
Créer-robot(x, y, d)se-déplace-bas  créer-robot(x, y-1, d)
S tourne-plus  créer-robot(Robot-x(S), Robot-y(S), Robot-direction(S)+90°)
S tourne-moins  créer-robot(Robot-x(S), Robot-y(S), Robot-direction(S)+90°)
Variables
x, y : entier, d : direction, S : robot

3. Indiquer parmi les données suivantes celles qui sont incorrectes syntaxiquement et corriger
les.
a. Créer-robot(2, 2, 3, 50◦ )
b. Créer-robot(3, 5, 60◦ )se-déplace-avant
c. Se-déplace-arrière(Créer-robot(3, 5, 65◦ ))
d. Tourner-moins(Créer-robot(-3, 5, 60◦ ))
e. ((Créer-robot(-3, 5, 60◦ ) tourne-plus) tourne-plus) se-déplace-haut
f. ((Créer-robot(-3, 5, 60◦ ) se-déplace-haut) tourne-plus) tourne-plus

4. Indiquer parmi les données correctes précédentes celles qui sont équivalentes (ont le même
sens) selon les axiomes proposés.
On commence par fournir la sémantique de chaque donnée, c’est à dire l’exprimer en termes des opérations
les plus simples possibles. Pour qu’on puisse donner la sémantique d’une donnée, il faut appliquer successivement

53
 Chapitre 3 : Types abstraits de données, TAD

les axiomes fournis dans la définition du TAD ; on peut pas juste faire l’évaluation (donner le sens) des données
par intuition. En appliquant l’ensemble des axiomes successivement, on trouve que les deux dernières données
sont équivalentes à : Créer-robot(-3, 6, 240◦ ). Elles sont équivalentes donc l’une à l’autre.
5. Enrichir ce TAD par l’opération _est-dans-champ-vision_ qui teste si un robot S1 est dans
le champ de vision de S2 (le champ de vision d’un robot est de plus ou moins 45◦ ).
Profil :
_est-dans-champs-vision_ : robot, robot → booléen
Axiome :
Une solution simplifée consiste en la proposition de l’axiome suivant :
S1 est-dans-champs-vision S2 ≡ |Robot-direction(S1)–Robot-direction (S2)|= 45◦ .
Mais, on trouve que cette solution ne considère que le cas où le robot s1 se trouve devant le robot s2
en termes de coordonnées, alors que l’axiome est supposé être correct pour tout type de robot, voir la figure
ci-après, où même si les deux robots ont la même direction, le robot s1 (x1, y1, d1) n’est pas dans le champ de
vision de s2 (x2, y2, d2) malgré qu’ils vérifie : |d1-d2|≤45◦ .
Donc, pour que s1 soit dans le champ de vision de s2, il faut que le point (x1,y1) vérifie l’équation
définissant le sous plan défini par x2, y2 et les vecteurs unitaires A et B (en vert dans la figure). On propose
ainsi l’axiome suivant :
s1 est_dans_champ_vision s2 ≡ position(s1) vérifie_equation_plan (x2,y2,d2)
s position et vérifie_equation_plan sont deux opérations pré-définies.
NB : On pourra développer ces opérations jusqu’à obtenir des instructions de base, il suffit que l’étudiant
sache faire une telle formulation qui reflète l’aspect abstrait de la chose, et c’est objectif du TAD : donner une
spécification du comportement sans s’étaler aux détails de l’implémentation.

12 52
53
13
6789
 53
42 43

54
 Chapitre 3 : Types abstraits de données, TAD

3.3 Exercices supplémentaires

Exercice 6

Soit le TAD donné dans la figure 3.3 spécifiant la structure de données ensemble d’éléments.

Figure 3.3: TAD ENSEMBLE

1. Donner le type des opérations de ce TAD (constructeurs, internes non constructeurs et observateurs).
2. Les données suivantes sont-elles correctes syntaxiquement ? Si oui donner le sens de chaque donnée en
appliquant les axiomes du TAD ensemble.
3. Enrichir ce TAD par l’opération Cardinalité qui retourne le nombre d’éléments contenu dans un ensemble.
Par exemple : Cardinalité(2, 4, 5, 4)=3.

Solution :

1. Donner le type des opérations de ce TAD (constructeurs, internes non constructeurs et observateurs).
Φ, ajouter : opérations internes constructeur
supprimer : opération interne non constructeurs
Choisir, appartient : observateurs
2. Les données suivantes sont-elles correctes syntaxiquement ? Si oui donner le sens de chaque donnée en
appliquant les axiomes du TAD ensemble.
a. ajouter(a, ajouter(b, ajouter(a, Φ)))
b. appartient(x, ajouter(b, ajouter(a,Φ)))
c. supprimer(2, ajouter(4, ajouter(5, ajouter(2, ajouter(4,Φ)))))

3. Enrichir ce TAD par l’opération Cardinalité qui retourne le nombre d’éléments contenu dans un ensemble.
Par exemple : Cardinalité(2, 4, 5, 4)=3.

55
 Chapitre 3 : Types abstraits de données, TAD

Profil : cardinalité : ensemble → entier

Axiomes :
cardinalité(Φ)≡0
cardinalité(ajouter(e,E))≡ Si appartient(e,E) alors cardinalité(E )
Sinon 1+cardinalité(E )
Variables : e : élément, E : ensemble

Exercice 7

Soit la signature suivante du TAD EXPRESSION spécifiant une expression mathématique simple.
TAD EXPRESSION
Utilise : VARIABLE, NATUREL, REEL
Sorte : expression
Opérations :
var : variable → expression
const : réel → expression
_ + _ : expression, expression → expression
_ ∗ _ : expression, expression → expression
_∧_ : variable, naturel → expression
1. Donner le type des opérations de ce TAD (constructeurs, internes non constructeurs et observateurs).
2. Les données suivantes sont elles correctes syntaxiquement ? sinon corriger ?
a. var(x)+const(2.4)*var(y)
b. x∧ 2+3.1*var(x)
c. var(x)*const(6.9)+var(y)*const(7.7)+z∧ 3
3. Enrichir ce TAD par l’opération Dérivée qui retourne la dérivée d’une expression.

Solution :

1. Donner le type des opérations de ce TAD (constructeurs, internes non constructeurs et observateurs).
Var, const, ∧ , + , * : opérations constructeurs ;
Toutes les opérations sont des opérations constructeurs, veuillez corriger l’information aux étudiants, car même
les opérations + et * ne peuvent pas être écrites en termes de constructeurs ni d’opérations plus simples. De

56
 Chapitre 3 : Types abstraits de données, TAD

plus, on est en train de faire le TAD qui génère des expressions et pas des nombres réels exprimés par ces
expressions.
2. Les données suivantes sont elles correctes syntaxiquement ? sinon corriger ?
a. var(x)+const(2.4)*var(y) : Oui
b. x∧ 2+3.1*var(x) : Non, x∧ 2+const(3.1)*var(x)
c. var(x)*const(6.9)+var(y)*const(7.7)+z∧ 3 :Oui
3. Enrichir ce TAD par l’opération Dérivée qui retourne la dérivée d’une expression.
Profil :
Dérivée : expression→expression
Axiomes :
dérivée(var(x))≡const(1)
dérivée(const(n))≡const(0)
dérivée(E1+E2)≡dérivée(E1) + dérivée(E2)
dérivée(E1*E2)≡dérivée(E1)*E2+dérivée(E2)*E1
dérivée(x◦ n) ≡ const(n)*x◦ (n-1)
Variables : x : variable n : entier E1, E2 : expression

3.4 Le TAD ARBRE et son implémentation

Dans cette section, on commence par définir le TAD ARBRE ; et puis on procède à son implémentation, dans
laquelle on définit ses structures et les fonctions et procédures équivalentes à ses opérations.
Un arbre est une structure de données hiérarchique formée par une collection d’informations homogènes
organisées en niveaux reliées entre eux par des branches sans boucles. Mathématiquement parlant, un arbre se
compose de deux ensembles N et A appelés respectivement l’ensemble des nœuds et l’ensemble des arcs
et d’un nœud particulier r appelé racine de l’arbre. Les éléments de A sont des paires (n1, n2) d’éléments de
N. Un arc (n1,n2) établit une relation entre n1, appelé nœud parent, et n2, appelé nœud enfant de n1. A doit
être tel que chaque nœud, sauf la racine, a exactement un parent. La racine n’a pas de parent 2 . La figure 3.4
illustre la notion d’arbre 3 .

Travail demandé

1. Prosper une définition (notation) récursive de la structure ‘Arbre’.

2. Proposer une signature pour le TAD ARBRE.
3. Implémenter les structures et opérations de ce TAD.

Solution :

1. Prosper une définition (notation) récursive de la structure ‘Arbre’.

2
Définition proposée par Pr. F. Belala
3
https ://[Link]/8-useful-tree-data-structures-worth-knowing-8532c7231e8c

57
 Chapitre 3 : Types abstraits de données, TAD

Figure 3.4: Structure de donnée ARBRE

Notation mathématique de l’arbre : Selon la définition mathématique de l’arbre, on doit donner trois
éléments : l’ensemble des nœuds N, l’ensemble des arcs A et la racine Racine. Si on considère l’exemple de la
figure 3.5, sa notation mathématique est comme suit :

Figure 3.5: Exemple d’un arbre

25

10 130 24

3 14 11 120 5

N=25, 10, 130, 24, 3, 14, 11, 120, 5

A= (25,10), (25,130), (25,24), (10,3), (10,14), (130,11), (130,120), (24,5)
Racine= 25
Définition récursive d’un arbre :
Un arbre est :
→ Soit vide
→ Soit formé d’un nœud particulier appelé racine et un ensemble fini de sous arbres.
Selon cette définition, on peut exprimer l’arbre de cet exemple comme suit :
Racine=25
Sous-arbre1
Racine= 10
Sous-arbre1.1

58
 Chapitre 3 : Types abstraits de données, TAD

Racine=3, sous-arbre1.1.1=vide, sous-arbre1.1.2=vide

Sous-arbre1.2
Racine=14, sous-arbre1.2.1=vide, sous-arbre1.2.2=vide
Sous-arbre2
Racine= 130
Sous-arbre2.1
Racine=11, sous-arbre2.1.1=vide, sous-arbre2.1.2=vide
Sous-arbre2.2
Racine=120, sous-arbre2.2.1=vide, sous-arbre2.2.2=vide
Sous-arbre3
Racine= 24
Sous-arbre3.1
Racine=5, sous-arbre3.1.1=vide, sous-arbre3.1.2=vide
2. Proposer une signature pour le TAD ARBRE
TAD ARBRE
Utilise : NŒUD, BOOLEEN, ENTIER, ENSEMBLENŒUDS, CHEMIN, BRANCHE, ELEMENT
Sortes : arbre, *****
Opérations :
arbreVide : → arbre
consArbreNœud : noeud → arbre
consArbreArbre : arbre, nœud, arbre → arbre
racine : arbre → nœud
contenu : nœud → élément
feuilles : arbre → ensemblenœuds
estfeuille : nœud, arbre → booléen
estNoeudInterne : nœud, arbre → booléen
ascendants : nœud, arbre → ensemblenœuds
descendants : nœud, arbre → ensemblenœuds
nœuds : arbre → ensemblenœuds
frères : nœud, arbre → ensemblenœuds
taille : arbre → entier
nombreFeuilles : arbre → entier
hauteurArbre : arbre → entier
hauteurNœud : nœud, arbre → entier
degréNœud : nœud, arbre → entier
degréArbre : arbre → entier
Variables :
b,sb,sb1,sb2, : arbre, n,n1,n2 :nœud, f :nœud
Précondotions :
racine(b) est définie ssi b 6= arbreVide
estFeuille(f,b) est définie ssi b 6= arbreVide
estNœudInterne(n,b) est définie ssi hauteurArbre(b) ≥ 3

59
 Chapitre 3 : Types abstraits de données, TAD

estNœudInterne(n,b) est définie ssi apperatient(n, b)=vrai

ascendants(n,b) est définie ssi apperatient(n, b)=vrai
déscendants(n,b) est définie ssi apperatient(n, b)=vrai
hauteurArbre(b) est définie ssi b 6= arbreVide
degréNœud(n,b) est définie ssi estFeuille(n,b)=faux
degréArbre(b) est définie ssi hauteurArbre(b) ≥ 2
Axiomes :
racine(consArbreNœud(n)) ≡ n
racine(consArbreArbre(sb,n,b)) ≡ racine(b)
nœuds(consArbreNœud(n)) ≡ ajouter(n ;Φ
nœuds(consArbreArbre(sb,n,b)) ≡ nœuds(sb) ∪ nœuds(b)
feuilles(consArbreNœud(n)) ≡ n
feuilles(consArbreArbre(sb,n,b)) ≡ feuilles(sb) ∪ feuilles(b) - ajouter(n,Φ)4
feuilles(arbreVide) ≡ Φ
estFeuille(n1, consArbreNœud(n)) ≡ n1=n
estFeuille(n1, consArbreArbre(sb,n,b)) ≡ estFeuille(n1,sb) ou estFeuille(n1,b) et n16=n
estNœudInterne(n,b) ≡ estFeuille(n1,b)= faux
ascendants(racine(b),b) ≡ Φ
ascendants(n,consArbreNœud(n2)) ≡ Φ
ascendants(n1,consArbreArbre(sb,n,b))≡ ascendants(n1,sb) ∪ ajouter(n,Φ) ∪ ascendants(n,sb)
descendants(n1,consArbreNœud(n)) ≡ Φ
descendants(n1,consArbreNœud(n2))≡ Φ
descendants(n1,consArbreArbre(sb,n,b)) ≡ si n=n1 alors noeuds(sb) ∪ descendants(n1,b)
sinon descendants(n1,sb) ∪ descendants(n1,b)
frère(racine(sb1),consArbreArbre(sb1,n1,consArbreArbre(sb2,n2,b)))≡ si n1=n2 alors
racine(sb2) ∪ frère(racine(sb1),b) sinon Φ
taille(arbreVide)≡ 0
taille(consArbreNœud(n)) ≡ 1
taille(consArbreArbre(sb,n,b)) ≡ taille(b)+taille(sb)
nombreFeuilles(arbreVide)≡0
nombreFeuilles(consArbreArbre(sb,n,b))≡ si estFeuille(n,b) alors
nombreFeuilles(sb)+ nombreFeuilles(b) -1 sinon nombreFeuilles(sb)+ nombreFeuilles(b)
hauteurArbre(consArbreNœud(n)) ≡ 0
hauteurArbre(consArbreArbre(sb1,n,(consArbreArbre(sb2,n,consArbreNœud(n))))) ≡
1+max(hauteurArbre(sb1),hauteurArbre(sb2))
hauteurNœud(racine(b),b)≡0
hauteurNœud(n1,consArbreArbre(sb,n,b))≡ si n1 ∈ descendants(racine(sb))
alors hauteurNœud(n1,sb)+ hauteurNœud(n,b) sinon hauteurNœud(n1,b)
degréNœud(n,consArbreNœud(n))≡0
degréNœud(n,consArbreArbre(sb,n,b)))≡ 1+degréNœud(n,b)
degréArbre(consArbreNœud(n)) ≡ 0
degréArbre(consArbreArbre(sb1,n,(consArbreArbre(sb2,n,b)))) ≡ max(degréArbre(sb1),degréArbre(sb2))

4
On suppose que l’opération ∪ est définie dans le TAD ENSEMBLE.

60
 Chapitre 3 : Types abstraits de données, TAD

3. Implémenter les structures et opérations de ce TAD.

La première étape pour implémenter le TAD ARBRE est le choix de la meilleure structure pour représenter
l’arbre et les éléments qui le composent. On propose de représenter un arbre par trois éléments :
Un arbre est :
N : l’ensemble des nœuds de l’arbre,
A : l’ensemble des arcs qui les relient, et
R : la racine de l’arbre
On peut ainsi représenter un arbre par un enregistrement :
Type : Arbre = enregistrement

 N : EnsembleNœuds


A : EnsembleArcs


 R : Noeud

Fin
Comme bien vu, la définition de cette structure doit passer par la définition des types : EnsembleNœuds,
EnsembleArcs et Nœud. Il n’y a pas une façon universelle pour décider la meilleure façon de représentation
de ces types ; tout dépend de la future utilisation du TAD ARBRE. Cette future application définit la nature
des nœuds et des arcs de l’arbre. Par exemple, dans un arbre qui représente la hiérarchie d’un staff dans une
entreprise, les nœuds sont des ‘personnes’, les arcs pourront représenter la relation ‘supérieur de’ et la racine est
le PDG. Dans un arbre qui représente un système de routage, les nœuds sont des machines, les arcs sont les
liens directs entre machines et la racine pourra être une machine client.
Pour illustrer l’utilité de la notion TAD et pour bien voir la généricité, on essaie dans ce qui suit
d’implémenter les opérations du TAD ARBRE, mais en gardant un certain niveau d’abstraction. Cette
abstraction, permet au maximum la réutilisation du TAD et de son implémentation.
Implémentation des opérations constructeur
arbreVide : → arbre

Fonction arbreVide() : arbre

b : arbre
b.Nœuds=Φ
[Link]=Φ
[Link]=Φ
Retourner (b)
Fin

consArbreNœud : noeud → arbre

Fonction consArbreNœud(Donnée n : Nœud) : arbre

b : arbre
b.Nœuds←b.Nœuds∪n
[Link]←Φ
[Link]←n
Retourner (b)
Fin

61
 Chapitre 3 : Types abstraits de données, TAD

consArbreArbre : arbre, nœud, arbre → arbre

Fonction consArbreArbre(Donnée sb : arbre, Donnée n : Nœud, Donnée b : arbre) : arbre

res : arbre
res.Nœuds← b.Nœuds ∪ sb.Nœuds
[Link]← [Link] ∪ [Link] ∪ (racine(sb),n)
[Link]← [Link]
Retourner (res)
Fin

Implémentation des opérations non constructeur

Fonction racine(Donnée b : arbre) : nœud

Retourner ([Link])
Fin

Fonction contenu(Donnée n : Nœud) : nœud

Retourner ([Link])a
Fin

a
On suppose que le TAD Nœud est implémenté par un enregistrement avec Elem comme champ du contenu

Fonction feuilles(Donnée b : arbre) : EnsembleNœuds

k, i, j : entier ; B :booléen
Si (Cardinalité(b.Nœuds)=1) :
Retourner (b.Nœuds)
Sinon
Feuilles←{}
k←0
Pour i ← 1 à Cardinalité(b.Nœuds) :
B ← vrai
TQ (j<=Cardinalité([Link]) et B) :
Si (b.Nœuds{i}=source(A{j})) :
B ← faux
FSi
FTQ
Si (B) :
k ← k+1 ;
Feuilles{k} ← [Link]{i}
FSi
FPour
FSi
Retourner (Feuilles)
Fin

Remarques :
a. Il est vrai qu’il n’existe pas de relation d’ordre entre les éléments d’un ensemble, mais quand on veut
l’implémenter dans les langages de programmation, on opte généralement pour des structures linéaires

62
 Chapitre 3 : Types abstraits de données, TAD

tels que les tableaux, les liste et les arraylists. Ces structures imposent une relation d’ordre entre leurs
éléments. Donc, la notation X{i} exprime le ieme élément dans l’ensemble X.
b. ‘Cardinalité’ est une opération observateur du TAD ENSEMBLE, voir page 55.
c. L’opération source est définie dans le TAD ARC, elle retourne la source d’un arc.

Fonction estFeuille(Donnée n : Nœud, Données b : arbre) : booléen

Retourner appartient(n,Feuilles(b))a
Fin

a
L’opération ‘appartient’ est définie dans le TAD ENSEMBLE

Fonction estNœudInterne(Donnée n : Nœud, Données b : arbre) : booléen

Retourner (estFeuille(n,b)=faux)
Fin

Fonction ascendants(Donnée n : Nœud, Données b : arbre) : EnsembleNœuds

asc : EnsembleNœuds
B : booléen
asc ← {}
B ← faux
Pour i ← 1 à Cardinalité([Link]) :
Si (puit([Link]{i})=n) :
B ← vrai
ajouter(source([Link]{i}), asc)
FSi
FPour
Si (B) :
Pour j ← 1 à Cardinalité(asc) :
asc=Union(asc, ascendants(asc{j},b))
FPour
FSi
Retourner (asc)
Fin

D’une façon récursive, la fonction ‘ascendants’ explore l’ensemble des arcs de l’arbre b pour chercher les
parents des nœuds passés comme paramètres aux différents appels.

63
 Chapitre 3 : Types abstraits de données, TAD

Fonction descendants(Donnée n : Nœud, Données b : arbre) : EnsembleNœuds

i, j : entier
dsc : EnsembleNœuds
B : booléen
dsc ← {}
B ← faux
Pour i ← 1 à Cardinalité([Link]) :
Si (source([Link]{i})=n) :
B ← vrai
ajouter(puit([Link]{i}), dsc)
FSi
FPour
Si (B) :
Pour j ← 1 à Cardinalité(dsc) :
dsc=Union(dsc, déscendants(dsc{j},b))
FPour
FSi
Retourner (dsc)
Fin

Fonction pere(Donnée n : Nœud, Données b : arbre) : EnsembleNœuds

i : entier
Pour i ← 1 à Cardinalité(b.Nœuds) :
Si (puit([Link]{i})=n) :
Retourner (source([Link]{i}))
FSi
FPour
Fin

Fonction frères(Donnée n : Nœud, Données b : arbre) : EnsembleNœuds

frs : EnsembleNœuds
i : entier
frs ← {}
Pour i ← 1 à Cardinalité(b.Nœuds) :
Si (pere([Link]{i},b)=pere(n,b)) :
ajouter([Link]{i}, frs)
FSi
FPour
Retourner (frs)
Fin

Fonction taille(Donnée b : arbre) : entier

Retourner Cardinalité([Link])
Fin

64
 Chapitre 3 : Types abstraits de données, TAD

Fonction nombreFeuilles(Donnée b : arbre) : entier

Retourner Cardinalité(Feuilles(b))
Fin

Fonction hauteurNœud(Donnée n : nœud, Donnée b : arbre) : entier

Si (n=racine(b)) :
Retourner (1)
Sinon
Retourner (1 + hauteurNœud(pere(n,b)))
FSi
Fin

Fonction hauteurArbre(Donnée b : arbre) : entier

i, h :entier
F : EnsembleNœuds
h←0
F← Feuilles(b)
Pour i ← 1 à Cardinalité(f) :
Si (hauteurNœud(F{i})>h) :
h ← hauteurNœud(F{i})
FSi
FPour
Retourner (h)
Fin

Fonction degréNoeud(Donnée n : Nœud, Données b : arbre) : entier

d : entier
d← 0
Pour i ← 1 à Cardinalité([Link]) :
Pour j ← 1 à Cardinalité([Link]) :
Si (source([Link]{i})=n) :
d← d+1
FSi
FPour
FPour
Retourner (d)
Fin

65
 Chapitre 3 : Types abstraits de données, TAD

Fonction degréArbre(Donnée b : arbre) : entier

i, d :entier
d←0
Pour i ← 1 à Cardinalité([Link]) :
Si (degréNœud(F{i})>d) :
d ← hauteurNœud(F{i})
FSi
FPour
Retourner (d)
Fin

3.5 Conclusion

Dans ce chapitre on a présenté quelques exercices de degrés de difficulté différents, on a proposé quelques
solutions types en se basant sur les notions du TAD vues dans le cours. Le TAD arbre présenté dans la fin du
chapitre vise l’illustration d’une définition d’un TAD le plus indépendamment possible de l’implémentation.
Le TAD arbre présenté dans ce chapitre est différent de ce qui est généralement donné dans d’autres
références. Premièrement, on a essayé de fournir une définition la plus générale possible des arbre, alors que la
majorité des référence ne donne que la définition du TAD ARBRE BINAIRE, ceci limite les possibilités des
opérations et des implémentations du TAD en question. Deuxièmement, on avait l’habitude d’implémenter les
arbres par des structures linéaires, telles que les listes, piles et files. Dans notre solution, on a insisté sur le fait
qu’un TAD peut être implémenté à base de n’importe quelle structure jugée appropriée, on a opté pour les
ensembles, les nœuds et les arcs dans notre solution.

66
 Chapitre
4
Structures de données linéaires : liste, pile et file

4.1 Introduction

Ce chapitre traite trois types de TAD représentant les trois structures linéaires : liste, pile et files. Les solutions
présentées sont basée principalement sur les TAD proposés dans le cours.
L’objectif du chapitre est de fournir de compléter ce qui est présenté en TD ; on présente des solutions les
plus complètes possible pour la totalité des exercices de la série de TD.

4.2 Série de TD

Exercice 1

Par réutilisation du type abstrait de données LISTE étudié en cours 1 :

1. Donner le rôle de l’opération suivante :
Profil :
chercherliste : élément, liste → booléen
Axiomes :
chercherliste(e, listeVide) ≡ faux
chercherliste(e, insérer(L, e’, i)) ≡ Si e==e’ alors vrai sinon chercherliste(e, L)
2. Proposez une fonction, donc une implémentation, pour l’opération chercherliste avec une représentation
contiguë de la liste L.
Solution :
Rôle de l’opération :
Cette opération cherche un élément dans une liste.
Implémentation de l’opération :

1
Voir cours sur : https ://[Link]/elearning/course/[Link] ?id=1076

67
 Chapitre 4 : Structures de données linéaires : liste, pile et file

Avant d’implémenter cette opération, on commence par implémenter la structure de la liste contiguë et par
l’implémentation d’autres opérations nécessaires pour l’accomplir.
On représente la liste contiguë par un enregistrement composé de deux champs : une table Tab contenant les
éléments de la liste et un entier N contenant le nombre des éléments de la liste.
(
Tab : tableau [N] : entier
N : entier

Une bonne façon de remplir les éléments de la liste est d’insérer les éléments dans l’ordre inverse dans le tableau
Tab. Cette représentation permet un accès rapide au premier élément de la liste et nous permet d’éviter les
opérations couteuses de décalage.

Fonction chercherListe(Donnée e : élément, Donnée L : liste) : entier

Si (L=listeVide()) :
Retourner (faux)
Sinon
Si (e=premier(L)) :
Retourner (vrai)
Sinon
Retourner (chercherListe(e, reste(L)))
FSi
FSi
Fin

Cette implémentation est basée sur l’axiome suivant ;

chercherliste(e, L) ≡ Si L=listeVide alors Faux
Sinon
Si e=premier(L) alors vrai
Sinon chercherliste(e, reste(L))
Cet axiome utilise deux autres opérations : ‘premier’ et ‘reste’, on les définit dans ce qui suit :
Profil :
premier : liste → élément
Axiomes :
reste : liste → liste
premier(insérer(L, e, i)) ≡ Si i=1 alors e sinon premier(L)
reste(insérer(L, e, i)) ≡ Si i=1 alors L sinon insérer(reste(L), e,i)

Fonction premier(Donnée L : liste) : entier

Retourner [Link](L.N)
Fin

Fonction reste(Donnée L : liste) : liste

L.N=(L.N)-1
Retourner (L)
Fin

68
 Chapitre 4 : Structures de données linéaires : liste, pile et file

Cette implémentation de la liste est des opération ‘reste’, ‘chercherliste’ et ‘reste’ utilise des opérations similaires
à celles proposées pour la structure pile ; en effet ‘reste’ est similaire à ‘dépiler’ et ‘premier’ est similaire à
‘sommet’.
NB : Il est également possible d’utiliser les opérations Accès et supprimer pour proposer une solution
similaire, voir la solution du prochain exercice qui exploite ces deux dernières opérations.

Exercice 2

1. Écrire un algorithme :
a. qui lit une suite de N nombres réels et construit une liste,
b. puis détermine le minimum de ces réels et l’imprime.
2. Laquelle des implémentations est favorable pour ce cas, contigüe ou chainée ?
Solution :
Cet exercice est très similaire à celui proposé dans l’exercice 7 du chapitre 1, voir page 17. La seule différence
réside dans le fait qu’on traite ici une liste au lieu d’une suite numérique et on cherche le minimum au lieu du
maximum.
Pour pouvoir écrire cet algorithme, on commence par implémenter le type élément, on le fait par
l’instruction :
Type élément : réel
On doit également définir l’opération minListe qui cherche la valeur minimale entre les éléments de la liste. On
donne le profil et l’axiome de cette opération :
Profil : minListe : liste → réel
Variables : L : liste, e : réel
Précondition : minListe(L) est définie ssi L 6= listeVide
Axiomes :
minListe(L)≡ Si (supprimer(L,1)= listeVide) Alors accès(L,1)
Sinon
Si (accès(L,1) < minListe(supprimer(L,1))) Alors accès(L,1)
Sinon minListe(supprimer(L,1))
Cet axiome nous aide à implémenter l’opération ‘minListe’ par une fonction récursive comme suit :

Fonction minListe(Donnée L : liste) : réel

Si (supprimer(L,1) = listeVide()) :
Retourner (accès(L,1))
Sinon
Si (accès(L,1)<minListe(supprimer(L,1))) :
Retourner (accès(L,1))
Sinon
Retourner (supprimer(L,1))
FSi
FSi
Fin

69
 Chapitre 4 : Structures de données linéaires : liste, pile et file

L’algorithme principal est donné ici :

Algorithme Exercice 01_Contigue

Déclarations :
L : liste
x : réel
i, N : entier
Type élément : réel
Fonction listeVide() : liste
Fonction insérer(Donnée L : liste, Donnée i : entier, Donnée e : réel) : liste
Fonction supprimer(Donnée L : liste, Donnée i : entier) : liste
Fonction accès(Donnée L : liste, Donnée i : entier) : réel
Fonction minListe(Donnée L : liste) : élément
Début
Lire(N)
L ← listeVide()
Pour i ← 1 à N :
Lire(x)
L ← insérer(L, x, i)
FPour
Écrire ("Le minimumde de ces nombres est :", minListe(L))
Fin

IL est à noter que l’axiome et l’implémentation donnés ici pour l’opération minListe sont appropriés à
l’implémentatuion contigue de la liste. Ils peuvent être adaptés au cas de la liste chainée comme suit :
minListe(L)≡ Si (supprimer(L,L)= listeVide) Alors accès(L,L)
Sinon
Si (accès(L,L) < minListe(supprimer(L,L))) Alors accès(L,L)
Sinon minListe(supprimer(L,L))
Aussi, nous adaptons l’appel (utilisation) de la fonction insérer comme suit : insérer(L, p, NB), p est de type
pointeur de cellule et nous pouvons ici insérer les nombres réels lus au début de la liste ; alors p = L (et
p=L=Null pour insérer dans la liste vide).
L’algorithme principal devient ainsi :

70
 Chapitre 4 : Structures de données linéaires : liste, pile et file

Algorithme Exercice 01_Chainée

Déclarations :
p, L : liste
x : réel
N : entier
Type élément : réel
Fonction listeVide() : liste
Fonction insérer(Donnée L : liste, Donnée p : liste, Donnée e : réel) : liste
Fonction supprimer(Donnée L : liste, Donnée p : liste) : liste
Fonction accès(Donnée L : liste, Donnée p : liste) : réel
Fonction minListe(Donnée L : liste) : élément
Début
Lire(N)
L ← listeVide()
Pour i ← 1 à N :
Lire(x)
L ← insérer(L, x, L)
FPour
Écrire ("Le minimumde de ces nombres est :", minListe(L))
Fin

2. Laquelle des implémentations est favorable pour ce cas, contigüe ou chainée ?

Pour le choix de l’implémentation favorable. Le critère est la complexité (donc la meilleure implémentation en
termes de temps réduit).
A. Si la liste contiguë est implémentée par une table ordinaire 2

La comparaison du code A, donné dans la figure 4.2, pour les 2 implémentations donne une complexité
équivalente pour les instructions 1 jusqu’à 5 . La différence réside dans l’instruction 6 et l’appel de la fonction
‘minListe’ :

En effet les instructions 1. et 2., pour chacune des 2 implémentations, sont équivalentes en complexité car
la fonction listeVide() est du même ordre pour les 2 implémentations (elle est constante). Les instructions 3. et
4. sont aussi équivalentes en complexité pour les deux implémentations. L’instruction 5. permet d’insérer un
nombre à la fin de la liste implémentée de façon contiguë (donc pas de décalage) et elle permet d’insérer un

2
Les éléments de la liste dans ce cas sont stockés dans la table dans l’ordre de leur lecture

71
 Chapitre 4 : Structures de données linéaires : liste, pile et file

nombre au début de la liste implémentée de façon chainée (pas de parcours). Ainsi elles sont presque équivalentes
en complexité.
L’instruction 6. contenant l’appel de la fonction minListe(L) nécessite plus de temps avec une
implémentation contiguë du fait qu’elle utilise la fonction supprimer(L, 1) nécessitant un décalage à gauche
de l’ordre O(N) (à chaque appel). Par contre, la fonction supprimer(L, L) (pour la liste implémentée de
façon chainée), supprimant le premier élément de la liste, est constante en complexité (avec 2 instructions
uniquement)3 .
Ainsi nous concluons que l’implémentation chainée de la liste (avec recherche du minimum) est plus
adéquate si l’implémentation contigue stocke les éléments dans le champ Tab dans le même ordre de leur lecture.
Il est évident, dans ce cas, que la deuxième implémentation (chainée) est la plus favorable ; l’accès aux
éléments de la liste, l’insertion et la suppression se font en début de liste, on n’a pas à parcourir tous les éléments.
Dans l’implémentation contigüe, les opérations de suppression et d’insertion nécessitent le décalage de tous les
éléments du tableau.
B. Si la liste contiguë est implémentée par une table dont l’ordre des éléments est inversé (comme
proposé dans l’exercice 1)
L’avantage de cette implémentation de la liste contiguë est qu’elle permet une insertion et une suppression
rapides du premier élément de la liste, donc elle va permettre de réduire la complexité de la solution de recherche
récursive du minimum de la liste, chose demandée dans cet exercice.
Ainsi, le stockage inverse des éléments dans le tableau de la liste permet une complexité équivalente à
celle offerte par l’implémentation chainée dans le contexte du code A. Cependant, si d’autres traitements sont
demandés, le même problème du décalage couteux peut émerger.

Exercice 3

1. Afin de disposer d’une boite à opérations (à utiliser selon le besoin), enrichir le type abstrait de données
LISTE (vu dans le cours 4 ) par les opérations suivantes :
(a) ajouterFin (L, e), permettant d’ajouter un élément e à la fin d’une liste L.
(b) queue (L), permettant de retourner le dernier élément d’une liste.
(c) Inverse(L), permettant d’inverser les éléments d’une liste.
(d) Som(L) qui calcule la somme des éléments d’une liste d’entiers
(e) égale(L1, L2) qui teste l’égalité de deux listes d’entiers.
2. Développez des fonctions implémentant les opérations précédentes.
3. Écrivez un algorithme, basé sur les fonctions précédentes, qui permet de :
(a) Créer une liste L1 contenant N entiers
(b) Afficher l’élément en queue de L1.

3
La fonction Supprimer peut poser une ambiguïté chez certains étudiants en pensant que les éléments de la liste sont détruits. La
réponse est que la liste initiale n’est pas touchée grâce au passage de paramètre par données, chaque fonction crée localement une
copie de la liste et travaille dessus sans toucher au paramètre réel qui a été envoyé. Exemple : Dans le code A (en rouge), à la fin de
la boucle la liste L est construite ; et à l’appel de la fonction minListe(L), cette dernière va créer une copie de L pour travailler et
idem pour la fonction supprimer(L,1) et chacune retournera son résultat. Après l’instruction 6., la liste reste intacte.
4
voir cours sur : https ://[Link]/elearning/course/[Link] ?id=1076

72
 Chapitre 4 : Structures de données linéaires : liste, pile et file

Solution :
(1) Enrichir le TAD LISTE et (2) Développez des fonctions implémentant les opérations précé-
dentes.
On propose pour chacune de ces opérations le profil, les axiomes et l’implémentation dans les deux cas de liste :
chainée et contiguë.
a) ajouterFin(L,e), permettant d’ajouter un élément e à la fin d’une liste L :
Le profil de l’opération ajouterFin dans les deux types de liste est donnée par :
Profil :
ajouterFin : liste, élément → liste
Ses propriétés sous forme d’axiomes sont données par :
Axiomes :
ajouterFin(L,e) ≡ insérer(L, longueur(L)+1, e) / * Si la liste est contigüe, i.e. Position = entier
ajouterFin (L,e) ≡ insérer(L, Null,e) / * Si la liste est chainée, i.e. Position = liste
Implémentation de la fonction ajouterFin dans le cas de la liste contiguë :

Fonction ajouterFin(Donnée L : liste, Donnée e : élément) : liste

Déclarations
Fonction longueur (D L : liste) : entier /* vue en cours
Fonction insérer (Donnée L : liste, Donnée i : entier, Donnée e : élément) : liste
/*Implémentation contigüe de la liste
Début
Retourner (insérer(L, longueur(L)+1, e))

Fin

Implémentation de la fonction ajouterFin dans le cas de la liste chainée

Fonction ajouterFin(Donnée L : liste, Donnée e : élément) : liste

Déclarations
Fonction insérer (Donnée L : liste, Donnée P : liste, Donnée e : élément) : liste
/*Implémentation chainée de la liste
Début
Retourner (insérer(L, Null, e))

Fin

Remarque : Cette fonction est meilleure dans le cas de l’implémentation contiguë. Dans la liste représentée
de manière chaînée, l’ajout à la fin se fait après avoir défilé tous les éléments de la liste, ce qui la rend plus
couteuse.
b) queue(L), permettant de retourner le dernier élément d’une liste :
Le profil de l’opération queue dans les deux types d’implémentation de la liste est donnée par :
Profil :
queue : liste→élément

73
 Chapitre 4 : Structures de données linéaires : liste, pile et file

Ses propriétés sous forme d’axiomes :

Axiomes :
queue (L) ≡ accès(L,longueur(L)) /* Contiguë
queue (L) ≡ Si suivant (L) = listeVide alors Accès (L,L) Sinon queue(suivant (L)) /* Chainnée

NB : queue ( listeVide ) est non définie

Pour l’implémentation de la fonction queue dans le cas de la liste contiguë :

Fonction queue(Donnée L : liste) : élément

Déclarations
Fonction longueur(Donnée L : liste) : entier
/* vue en cours
Fonction accès(Donnée L : liste, Donnée i : entier) : élément
/*Implémentation contigüe de la liste
Début
Retourner accès(longueur(L))
Fin

Pour l’implémentation de la fonction queue dans le cas de la liste chaînnée :

Fonction queue(Donnée L : liste) : élément

Déclarations
Fonction suivant(Donnée L : liste) : liste
/* vue en cours
Fonction accès(Donnée L : liste, Donnée L : liste) : élément
Début
Si (suivant(L)=Null) :
Retourner (accès(L,L))
Sinon
Retourner (queue(suivant(L)))
FSi
Fin

c) Inverse (L), permettant d’inverser les éléments d’une liste :

Profil :
Inverse : Liste→Liste
Axiomes :
Inverse(listeVide) ≡ listeVide
Inverse (L) ≡ ajouterFin(inverse(supprimer(L,1)),accès(L,1)) /* Implémentation contigüe
Inverse (L) ≡ ajouterFin(inverse(supprimer(L,L)),accès(L,L)) /* Implémentation chainée
En passant directement à la fonction, nous avons :
Pour l’implémentation contiguë de la liste :

74
 Chapitre 4 : Structures de données linéaires : liste, pile et file

Fonction Inverse(Donnée L : liste) : liste

Déclarations
Fonction ajouterFin(Donnée L : liste, Donnée e : élément) : Liste /* vue précédemment
Fonction supprimer(Donnée L : liste, Donnée i : entier) : liste
Fonction accès(Donnée L : liste, Donnée i : entier) : élément
Fonction listeVide() : liste /*Implémentation contigüe de la liste
Début
Si (L = listeVide()) :
Retourner (L)
Sinon
Retourner (ajouterFin(inverse(supprimer(L,1)),accès(L,1)))
FSi
Fin

Pour l’implémentation chainée de la liste :

Fonction Inverse(Donnée L : liste) : liste

Déclarations
Fonction ajouterFin(Donnée L : liste, Donnée e : élément) : liste /* vue précédemment
Fonction supprimer(Donnée L : liste, Donnée P : liste) : liste
Fonction accès(Donnée L : liste, Donnée P : liste) : élément
Fonction listeVide() : Liste
Début
Si (L = listeVide()) :
Retourner (L)
Sinon
Retourner (ajouterFin(inverse(supprimer(L,L)),accès(L,L)))
FSi
Fin

d) Som(L), qui calcule la somme des éléments d’une liste d’entiers

Une version récursive de cette opération peut être aisément donnée dans les deux implémentations de la liste ; il
est aussi utile de rappeler l’implémentation itérative pour quelques fonctions. On donne ici l’axiome récursif,
mais on donne les implémentations récursives et itératives de la fonction Som(L) dans les deux cas (contigu et
chainé).
Profil :
Som : liste → entier
Axiome por l’implémentation contiguë de la liste :
Som(L)≡ Si L = listeVide Alors
0
Sinon
accès(L,1)+Som(supprimer(L,1))
Axiome pour l’implémentation chainée de la liste :
Som(L)≡ Si L = listeVide Alors

75
 Chapitre 4 : Structures de données linéaires : liste, pile et file

0
Sinon
accès(L,L)+Som(supprimer(L,L))
Liste contigue / fonction récursive :

Fonction Som(Donnée L : liste) : entier

Déclarations
Fonction supprimer(Donnée L : liste, Donnée P : entier) : liste
Fonction accès(Donnée L : liste, Donnée P : entier) : élément
Fonction listeVide() : Liste
Début
Si (L = listeVide()) :
Retourner (0)
Sinon
Retourner (accès(L,1)+Som(supprimer(L,1)))
FSi

Fin

Liste chainée / fonction récursive :

Fonction Som(Donnée L : liste) : entier

Déclarations
Fonction supprimer(Donnée L : liste, Donnée P : liste) : liste
Fonction accès(Donnée L : liste, Donnée P : liste) : élément
Fonction listeVide() : Liste
Début
Si (L = listeVide()) :
Retourner (0)
Sinon
Retourner (accès(L,L)+Som(supprimer(L,L)))
FSi
Fin

NB : Veuillez faire aux étudiants la remarque qu’on peut remplacer “supprimer(L,L)” utilisée
dans le cas de la liste chainée par : “suivant(L)”, dans cet exercice et dans l’exercice 2 (Maximum
récursive).
Liste contiguë / fonction itérative :

76
 Chapitre 4 : Structures de données linéaires : liste, pile et file

Fonction Som(Donnée L : liste) : entier

Déclarations
Fonction supprimer(Donnée L : liste, Donnée P : entier) : liste
Fonction accès(Donnée L : liste, Donnée P : entier) : élément
Fonction listeVide() : Liste
Début
S←0
TQ (L6=listeVide()) :
S=S+accès(L,1)
L=supprimer(L,1)
FTQ
Retourner (S)
Fin

Liste chainée / fonction itérative :

Fonction Som(Donnée L : liste) : entier

Déclarations
Fonction supprimer(Donnée L : liste, Donnée P : liste) : liste
Fonction accès(Donnée L : liste, Donnée P : liste) : élément
Fonction listeVide() : Liste
Début
S=0
TQ (L6=listeVide()) :
S=S+accès(L,L)
L=supprimer(L,L)
FTQ
Retourner (S)
Fin

e) égale(L1,L2) qui teste l’égalité de deux listes d’entiers :

Profil :
égale : liste, liste → booléen
Précondition :
égale(L1,L2) est définie ssi longueur(L1)=longueur(L2)
Axiomes :
égale(listeVide,listeVide) ≡ vrai
égale(L1,L2) ≡ si accès(L1,1) = accès(L2,1) alors égale(supprimer(L1,1), supprimer(L2,1)) Sinon faux /* Liste
contiguë
égale(L1,L2) ≡ si accès(L1,L1) = accès(L2,L2) alors égale(supprimer(L1,L1), supprimer(L2,L2)) Sinon faux /*
Liste chainée
Implémentation de la fonction égale dans le cas de la liste contiguë :

77
 Chapitre 4 : Structures de données linéaires : liste, pile et file

Fonction égale_Contiguë(Donnée L1 : liste, L2 : liste) : booléen

Déclarations
Fonction supprimer(Donnée L : liste, Donnée i : entier) : liste
Fonction accès(Donnée L : liste, Donnée i : entier) : élément
Fonction listeVide() : liste /*Implémentation contigüe de la liste
Début
Si (L1 = listeVide()) :
Retourner (vrai)
Sinon
Si (accès(L1,1)=accès(L2,1)) :
Retourner (égale(supprimer(L1,1),supprimer(L2,1)))
Sinon
Retourner (faux)
FSi
FSi
Fin

Implémentation de la fonction égale dans le cas de liste chainée :

Fonction égale_Chainée(Donnée L1 : liste, L2 : liste) : booléen

Déclarations
Fonction supprimer(Donnée L : liste, Donnée p : liste) : liste
Fonction accès(Donnée L : liste, Donnée p : liste) : élément
Fonction listeVide() : liste /*Implémentation chainée de la liste
Début
Si (L1 = listeVide()) :
Retourner (vrai)
Sinon
Si (accès(L1,L1)=accès(L2,L2)) :
Retourner (égale(supprimer(L1,L1),supprimer(L2,L2)))
Sinon
Retourner (faux)
FSi
FSi
Fin

3. Écrivez un algorithme, basé sur les fonctions précédentes, qui permet de :

→ Créer une liste L contenant N éléments de type entiers :
→ Faire la somme des éléments de L :
→ Afficher la liste inversée de L :
Pour l’implémentation contiguë de la liste :

78
 Chapitre 4 : Structures de données linéaires : liste, pile et file

Algorithme : Exercice 3-3-Contiguë

Déclarations :
L, L1 : liste ; N, NB, i : entier
Fonction listeVide() : liste
Fonction supprimer(Donnée L : liste, Donnée i : entier) : liste
Fonction Inverse(Donnée L : liste) : liste
Fonction accès(Donnée L : liste, Donnée i : entier) : réel
Début
Lire (N)
L = listeVide()
Pour i ← 1 à N :
Lire(NB)
L=insérer(L,i,NB)
FPour
Écrire ("La somme des éléments de la liste est :", Som(L))
L1=inverse(L)
TQ (L16=listeVide()) :
Écrire(accès(L1,1))
L1=supprimer(L1,1)
FTQ
Fin

Pour l’implémentation chainée de la liste :

Algorithme : Exercice 3-3-Chainée

Déclarations :
L, L1 : liste ; N, NB, i : entier
Fonction listeVide() : liste
Fonction supprimer(Donnée L : liste, Donnée p : liste) : liste
Fonction Inverse(Donnée L : liste) : liste
Fonction accès(Donnée L : liste, Donnée p : liste) : réel
Début
Lire (N)
L = listeVide()
Pour i ← 1 à N :
Lire(NB)
L=insérer(L,Null,NB)
FPour
Écrire ("La somme des éléments de la liste est :", Som(L))
L1=inverse(L)
TQ (L16=listeVide()) :
Écrire(accès(L1,L1))
L1=supprimer(L1,L1)
FTQ
Fin

Exercice 4

Soit le TAD LISTE décrivant une liste de nombres réels.

1. Définir une opération produitListe qui construit à partir de deux listes L1 et L2 de tailles égales, la liste

79
 Chapitre 4 : Structures de données linéaires : liste, pile et file

des nombres produits dont les éléments sont obtenus en faisant le produit (la multiplication) des éléments de L1
par ceux de L2 (deux à deux).
2. Écrire un algorithme qui :
a. Construit deux listes de 500 nombres réels chacune.
b. Multiplie les éléments (deux à deux) des deux listes pour avoir une liste LPROD en utilisant l’opération
produitListe
c. Affiche les nombres de la liste LPROD obtenue.
Solution :
1. Définir l’opération produitListe
Profil :
produitListe : liste, liste→ liste
Précondition :
produitListe(L1,L2) est définie ssi longueur(L1)=longueur(L2)
Axiomes pour le cas de la liste contiguë :
produitListe(L1,L2,L3) ≡ Si (supprimer(L1,1)= listeVide) Alors insérer(L3, accès(L1,1)*accès(L2,1),1)
Sinon
insérer(produitListe(supprimer(L1, 1), supprimer(L2,1),L3), accès(L1, 1)*accès(L2, 1),1)
Axiomes pour le cas de la liste chainée :
produitListe(L1,L2,L3) ≡ Si (supprimer(L1,1)= listeVide) Alors insérer(L3, accès(L1,1)*accès(L2,1),L3)
Sinon
insérer(produitListe(supprimer(L1, 1), supprimer(L2,1),L3), accès(L1, 1)*accès(L2, 1), L3)

Implémentation de la fonction produitListe dans le cas de liste contiguë :

Fonction produitListe_Contiguë(Donnée L1, L2 : liste ; Donnée/Résultat L3 : liste) : liste

Déclarations
Fonction supprimer(Donnée L1, Donnée i : entier) : liste
Fonction accès(Donnée L : liste, Donnée i : entier) : élément
Fonction listeVide() : liste /*Implémentation contigüe de la liste
Début
Si (supprimer(L1,1)=listeVide()) :
Retourner (insérer(L3,accès(L1,1)*accès(L2,1),1)
Sinon
Retourner (inséréer(produitListe(supprimer(L1,1),supprimer(L2,1),L3),accès(L1,1)*accès(L2,1),1))
FSi
Fin

Implémentation de la fonction produitListe dans le cas de liste chainée :

80
 Chapitre 4 : Structures de données linéaires : liste, pile et file

Fonction produitListe_Chainée(Donnée L1, L2 : liste ; Donnée/Résultat L3 : liste) : liste

Déclarations
Fonction supprimer(Donnée L : liste, Donnée p : liste) : liste
Fonction accès(Donnée L : liste, Donnée p : liste) : élément
Fonction listeVide() : liste /*Implémentation chainée de la liste
Début
Si (supprimer(L1,L1)=listeVide()) :
Retourner (insérer(L3,accès(L1,L1)*accès(L2,L2),Null)
Sinon
Retourner (inséréer(produitListe(supprimer(L1,L1),supprimer(L2,L2),L3),accès(L1,L1)*accès(L2,L2),L3))
FSi
Fin

2. L’algorithme produitListe
Dans le cas de la liste contiguë :

Algorithme : algoProduitListes
Déclarations :
L1, L2, L3, Res : liste ; NB, i : entier
Fonction listeVide() : liste
Fonction supprimer(Donnée L : liste, Donnée i : liste) : liste
Fonction accès(Donnée L : liste, Donnée i : liste) : réel
Fonction insérer(Donnée L : liste, Donnée e : élément, Donnée i : entier) : réel
Fonction produitListe_Contiguë (Donnée L1, L2 : liste ; Donnée/Résultat L3 : liste) : liste
Début
L1 = listeVide()
L2 = listeVide()
L3 = listeVide()
Res = listeVide()
Pour i ← 1 à 500 :
Lire(NB1)
Lire(NB2)
L1=insérer(L1,i,NB1)
L2=insérer(L2,i,NB2)
FPour
Res=produitListe(L1,L2,L3)
TQ (Res6=listeVide) :
Écrire(accès(Res,1))
Res ← supprimer(Res,1)
FTQ
Fin

81
 Chapitre 4 : Structures de données linéaires : liste, pile et file

Dans le cas de la liste chainée :

Algorithme : algoProduitListes
Déclarations :
L1, L2, L3, Res : liste ; NB, i : entier
Fonction listeVide() : liste
Fonction supprimer(Donnée L : liste, Donnée i : liste) : liste
Fonction accès(Donnée L : liste, Donnée i : liste) : réel
Fonction insérer(Donnée L : liste, Donnée e : élément, Donnée i : entier) : réel
Fonction produitListe_Chainée (Donnée L1, L2 : liste ; Donnée/Résultat L3 : liste) : liste
Début
L1 = listeVide()
L2 = listeVide()
L3 = listeVide()
Res = listeVide()
Pour i ← 1 à 500 :
Lire(NB1)
Lire(NB2)
L1=insérer(L1,L1,NB1)
L2=insérer(L2,L2,NB2)
FPour
Res=produitListe(L1,L2,L3)
TQ (Res6=listeVide) :
Écrire(accès(Res,L3))
Res ← supprimer(Res,L3)
FTQ
Fin

Exercice 5

1. Enrichir le TAD FILE par l’opération "Identiques" qui teste l’égalité de deux files de caractères.
2. Donner les fonctions génériques récursive et itérative qui implémentent cette opération.
Solution :
Profil :
Identiques file, file → booléen
Précondition :
Identiques(f1,f2) est définie ssi longueur(f1)=longueur(f2)
Axiomes :
Identiques(fileVide,fileVide) ≡ vrai
Identiques(f1,f2) ≡ si tête(f1) = tête(f2) alors Identiques(défiler(f1), défiler(f2)) Sinon faux
2. Donner les fonctions génériques récursive et itérative qui implémentent cette opération.

82
 Chapitre 4 : Structures de données linéaires : liste, pile et file

Fonction récursive :

Fonction IdentiquesRec(Donnée f1 : file, f2 : file) : booléen

Déclarations
Fonction défiler(Donnée f : file) : file
Fonction tête(Donnée f : file) : élément
Fonction fileVide() : file
Début
Si (L1 = fileVide()) :
Retourner (vrai)
Sinon
Si (tête(f1)=tête(f2)) :
Retourner (IdentiquesRec(défiler(f1), défiler(f2)))
Sinon
Retourner (faux)
FSi
FSi
Fin

Fonction itérative :

Fonction IdentiquesIter(Donnée f1 : file, f2 : file) : booléen

Déclarations
B : booléen
Fonction défiler(Donnée f : file) : file
Fonction tête(Donnée f : file) : élément
Fonction fileVide() : file
Début
B ← vrai
TQ (f16=fileVide() et B) :
Si (tête(f1)=tête(f2)) :
f1 ← défiler(f1)
f2 ← défiler(f2)
Sinon
B ← faux
FSi
FTQ
Retourner (B)
Fin

Exercice 6

Soit le TAD PILE d’entiers compris entre 1 et N. On suppose l’existence d’une opération estPremier qui teste si
un entier est un nombre premier,
1. Enrichir le TAD par une opération pile-premier qui construit une sous pile formée de tous les éléments, de la
pile initiale, qui sont des nombres premiers.
2. Écrire la fonction récursive correspondante.
3. Donner la fonction itérative complète (entêtes et corps des différentes fonctions) pilePremiers sachant que la

83
 Chapitre 4 : Structures de données linéaires : liste, pile et file

pile est implémentée de manière chaînée.

NB : Pour la fonction premier donner uniquement son entête.
Solution :
1. Définir l’opération pilePremiers
Profil :
pilePremiers : pile → pile
Axiomes :
pilePremiers(pileVide) ≡ pileVide
pilePremiers(p) ≡ si estPremier(sommet(p)) alors empiler(pilePremiers(dépiler(p)), sommet(p))
sinon pilePremiers(dépiler(p))
2. Écrire la fonction récursive correspondante.

Fonction pilePremiersRec(Donnée p : pile) : entier

Déclarations
Fonction dépiler(Donnée p : pile) : pile
Fonction sommet(Donnée p : pile) : pile
Fonction pileVide() : pile
Début
Si (p=pileVide()) :
Retourner (pileVide())
Sinon
Si (estPremier(sommet(p))) :
Retourner (empiler(pilePremiersRec(dépiler(p)), sommet(p)))
Sinon
Retourner (pilePremiersRec(dépiler(p)))
FSi
FSi
Fin

3. Donner la fonction itérative complète (entêtes et corps des différentes fonctions) pilePremiers
sachant que la pile est implémentée de manière chaînée.

84
 Chapitre 4 : Structures de données linéaires : liste, pile et file

Fonction pilePremiersIter(Donnée p : pile) : entier

Déclarations
p2 : pile
Fonction estPremier(Donnée e : entier) : booléen
Fonction dépiler(Donnée p : pile) : pile
Retourner (suivant(p))
Fin
Fonction sommet(Donnée p : pile) : pile
Retourner ([Link])
Fin
Fonction pileVide(Donnée S : Suite-numérique) : pile
Retourner (Null)
Fin
Début
TQ (p neq pileVide) :
Si (estPremier(sommet(p))) :
p2 ← empiler(p2,sommet(p))
FSi
p ← dépiler(p)
FTQ
TQ (p2 neq pileVide) :
p ← empiler(p,sommet(p2))
p2 ← dépiler(p2)
FTQ
Fin

Exercice 7

1. Écrire les fonctions suivantes permettant de manipuler la structure de donnée FILE.

(a) a. chercherFile(F, e), permettant de vérifier si un élément e existe ou non dans une file F.
(b) ajouterDeb(F, e), permettant d’ajouter un élément e au début d’une file F.
(c) Inverse(f), permettant d’inverser les éléments d’une file.
2. Proposer l’implémentation la plus adéquate (Chainée ou contiguë) pour chacune de ces fonctions. Justifier
votre choix.
Solution :
1. Écrire les fonctions suivantes permettant de manipuler la structure de donnée FILE.
Profils :
chercherFile : file, élément → booléen
ajouterDeb : file, élément → file
Inverse : file → file
Axiomes :
chercherFile(f,e) ≡ Si f=fileVide alors faux
Sinon
Si tête(f)=e alors vrai

85
 Chapitre 4 : Structures de données linéaires : liste, pile et file

Sinon chercherFile(défiler(f),e)

ajouterDeb(f, e) ≡ Si f = fileVideAlors enfiler(f,e)

Sinon enfiler(ajouterDeb(suppQueue(f),e),queue(f))

Inverse(f) ≡ Si défiler(f) = fileVide ou f = fileVide alors f

Sinon enfiler(Inverse(défiler(f)), tête(f))

On ajoute la définition (profil, précondition et axiome) de l’opération suppQueue utilisée :

Profil : suppQueue : file → File
Précondition : suppQueue(f) est définie ssi f 6= fileVide()
Axiomes :
suppQueue(enfiler(f,e)) ≡ f
suppQueue(f, e) ≡ Si défiler(f) = fileVide Alors fileVide
Sinon ajouterDeb(suppQueue(défiler(f)), tête(f))

2- Proposer l’implémentation la plus adéquate (Chainée ou contigue) pour chacune de ces fonc-
tions. Justifier votre choix.

L’implémentation la plus appropriée est l’implémentation contiguë.

On définie les opérations d’une manière récursives comme suit :

Fonction Chercher-file(Donnée F : file, Donnée e : élément) : booléen

Déclarations
Fonction tête(Donnée F : file) : élément
Fonction défiler(Donnée F : file) : file
Fonction fileVide() : file
/* Leurs corps dépendent de l’implémentation considérée pour la file, chaînée ou contiguë (Voir cours)
Début
Si ( F = fileVide()) :
Retourner (Faux)
Sinon
Si (e = tête(f)) :
Retourner (Vrai)
Sinon
Retourner (Chercher-file (défiler(f), e)))
FSi
FSi
Fin

Avant de donner l’implémentation de la fonction ajouterDeb, on commence par donner le corps de la fonction
suppQueue, selon le premier axiome défini, ce dernier dépendra de l’implémentation de la file. L’implémentation
de la fonction suppQueue est premièrement donnée par exploitation de la structure adoptée de la file :

86
 Chapitre 4 : Structures de données linéaires : liste, pile et file

implémentation contiguë de la file.

Fonction suppQueue(Donnée F : file) : File

Déclarations
F1 : file
Début
F1.tête ← F.tête
[Link] ← [Link]
[Link] ← ([Link]  1) /* La fonction  est donnée en cours
[Link] ← Faux
Retourner (F1)
Fin

On a également proposé un axiome plus abstrait pour l’opération suppQueue, mais il utilise l’opération
ajouterDeb :
suppQueue(f, e) ≡ Si défiler(f) = fileVide Alors fileVide
Sinon ajouterDeb(suppQueue(défiler(f)), tête(f))

Comme déjà vu dans l’exercice 13 du chapitre 1 (page 26), il s’agit de l’appel récursif mutuel (Mutual Recursion)
entre deux fonctions : ajouterDeb et suppQueue ; ça s’exécute naturellement, car on arrive à un point où l’une
des deux fonction arrive au cas trivial et retourne une valeur qui sera utilisée par l’autre fonction pour retourner
une valeur à l’appel fait par la première et ainsi de suite.
L’implémentation de la fonction suppQueue est premièrement donnée par exploitation de la structure adoptée
de la file : implémentation contiguë de la file.

Fonction suppQueue(Donnée F : file) : File

Déclarations
F1 : file
Début
F1.tête ← F.tête
[Link] ← [Link]
[Link] ← ([Link]  1) /* La fonction  est donnée en cours
[Link] ← Faux
Retourner (F1)
Fin

On donne maintenant l’implémentation récursive de la fonction supp-queue qui fait appel à la fonction
ajouterDeb :

87
 Chapitre 4 : Structures de données linéaires : liste, pile et file

Fonction suppQueue(Donnée F : file) : File

Déclarations
Fonction fileVide() : file
Fonction défiler(Donnée F : file) : file
Fonction ajouterDeb(Donnée F : file, Donnée e : élément) : file
Fonction tête(Donnée f : file) : élément
Début
Si (défiler(f) = fileVide()) :
Retourner (fileVide())
Sinon
Retourner (ajouterDeb(suppQueue(défiler(f)),tête(f)))
FSi
Fin

Implémentation récursive de l’opération ajouterDeb :

Fonction ajouterDeb(Donnée f : file, Donnée e : élément) : File

Déclarations
Fonction fileVide() : file
Fonction enfiler(Donnée f : file, Donnée e : élément) : file
Fonction suppQueue(Donnée f : file) : file
Fonction queue(Donnée f : file) : élément
Début
Si (F = fileVide()) :
Retourner (enfiler(F,e))
Sinon
Retourner enfiler(ajouterDeb(suppQueue(f),e),queue(f))
FSi
Fin

Inverse :

Fonction Inverse(Donnée f : file) : File

Déclarations :
Fonction fileVide() : file
Fonction tête(Donnée f : file) : élément
Fonction défiler(Donnée f : file) : file
Fonction enfiler(Donnée f : file, Donnée e : élément) : file
Si (défiler(f) = fileVide() ou F = fileVide()) :
Retourner (f)
Sinon
Retourner (enfiler(Inverse(défiler(f))),tête(f))
FSi
Fin

On présente égélement à la version itérative des fonctions implémentant ces opérations (toujours
pour le cas de la file contiguë) :

88
 Chapitre 4 : Structures de données linéaires : liste, pile et file

Fonction Chercher-file(Donnée f : file, Donnée e : élément) : booléen

Déclarations
Fonction tête(Donnée f : file) : élément
Fonction défiler(Donnée f : file) : file
Fonction fileVide() : file
/* Leurs corps dépendent de l’implémentation considérée pour la file, chaînée ou contiguë (Voir cours)
Début
TQ (f 6= fileVide() et tête-f(f) 6= e ) :
F = défiler(f)
FTQ
Si (F = fileVide()) :
Retourner (Faux)
Sinon
Retourner (Vrai)
FSi
Fin

Fonction suppQueue(Donnée f : file, Donnée e : élément) : File

[Link] ← [Link]  1
[Link] ← Faux
Retourner(f)
Fin

Fonction ajouterDeb(Donnée f : file, Donnée e : élément) : File

F.tête = F.tête  1
[Link](F.tête) ← e
Si ( [Link] = F.tête) :
[Link] ← Vrai
FSi
Fin

89
 Chapitre 4 : Structures de données linéaires : liste, pile et file

Fonction Inverse(Donnée f : file) : File

Déclarations :
Fonction fileVide() : file
Fonction tête(Donnée f : file) : élément
Fonction défiler(Donnée f : file) : file
Fonction queue(Donnée f : file) : élément
Fonction Pile-vide() : Pile
Fonction Sommet(Donnée P :Pile) : élément
P : Pile
Début
P ← Pile-vide()
TQ (f 6= fileVide() ) :
P ← empiler(P,tête(f))
F←défiler(f)
FTQ
TQ (P 6= Pile-Vide() ) :
f ← enfiler(F,Sommet(P))
P← dépiler(P)
FTQ
Retourner (f)
Fin
Fin

Exercice 8

Etant donnée l’implémentation suivante de la sorte "élément" dans le TAD PILE d’éléments.
Type : élément : Etudiant
Type : Etudiant = enregistrement

 nom : chaine de caractères


prénom : chaine de caractères


 mat : entier

Fin
1. Donner l’implémentation chainée (types et fonctions de base) de la structure de données pile d’étudiants dans
ce cas.
2. Étant données la fonction : Mat(D E : étudiant) : entier, qui retourne le matricule d’un étudiant donné.
Écrire une fonction récursive (profile et axiome au préalable) qui retourne l’étudiant ayant le matricule 255 se
trouvant dans une pile d’étudiants.

Solution :
1. La création du TAD PILE_Etudiants consiste en :
(a) La définition ou la redéfinition des structures de données nécessaires
(b) L’adaptation des opérations du TAD PILE de base qui dépendent de l’implémentation
Redéfinition de la structure pile :
Type : pile= pointeur de cellule

90
 Chapitre 4 : Structures de données linéaires : liste, pile et file

Type : cellule= Enregistrement :

(
info : étudiant
suiv : pointeur de cellule
Fin
Comme dicté par l’énoncé, la structure étudiant est implémentée comme suit :
Type : élément : Etudiant
Type : Etudiant = enregistrement

 nom : chaine de caractères


prénom : chaine de caractères


 mat : entier

On donne et adapte, si l’y en a besoin, les fonctions de base :

Fonction pileVide( ) : pile
Retourner (null)
Fin

Fonction sommet(Donnée p :pile) : étudiant

Retourner ([Link])
Fin

Fonction dépiler(Donnée p :pile) : pile

Retourner ([Link])
Fin

Fonction empiler(Donnée p :pile, Donnée e :étudiant) : pile

T= allouer(cellule)
[Link] ← e
[Link] ← p
Retourner (T)
Fin

2. Définir l’opération chercher255

Profil : chercher255 : pile → étudiant
Variables : p :pile
Axiomes :
chercher255(p) ≡ Si Mat(sommet(p))==255 alors sommet(p) Sinon chercher255(dépiler(p))

Selon l’énoncé, l’élément recherché existe dans la pile ; on n’aura pas besoin de mettre une précondition liée à
son existence.

91
 Chapitre 4 : Structures de données linéaires : liste, pile et file

Implémentation de la fonction chercher255 :

Fonction chercher255(Donnée p : pile) : étudiant

Déclarations :
Fonction Mat(D E : étudiant) : entier
Fonction sommet(Donnée p : pile) : étudiant
Fonction dépiler(Donnée p : pile) : pile
Début
Si ((Mat(sommet(p))==255)) :
Retourner (sommet(p))
Sinon
Retourner chercher255 (dépiler(P))
FSi
Fin

4.3 Conclusion

Dans ce dernier chapitre, nous avons essayé de couvrir trois notions importantes dans le domaine de l’algorith-
mique : liste, pile et file. Les solutions et explications proposée stressent l’abstraction et le réutilisation par
l’adoption des TAD comme outil de définition et manipulation des structures de données.

92
 Annexe
A
Programmation en langage C des exercice du chapitre 1

A.1 Implémentation de la solution de l’exercice 1

Listing A.1: Code C définissant et utilisant la fonction sommePositifs

1 #include <stdio.h>
2 int sommePositifs(int *tab, unsigned n)
3 {
4 int som=0;
5 unsigned i;
6 for (i = 0; i <= n-1; i++)
7 {
8 printf("i= %d\n",i);
9 printf("tab[i]= %d\n",tab[i]);
10 if (tab[i] < 0)
11 som=som+tab[i];
12 }
13 return som;
14 }
15 int main(void)
16 {
17 int tabEff[5] = {15,-3,-2,0,6};
18 printf("%d",sommePositifs(tabEff,5));
19 return 0;
20 }
21 }

Listing A.2: Code C définissant et utilisant la procédure sommePositifs

1 #include <stdio.h>
2 void sommePositifs(int *tab, int *som,unsigned n)
3 {
4 *som=0;
5 unsigned i;

93
 Chapitre A : Programmation en langage C des exercice du chapitre 1

6 for (i = 0; i <= n; i++)

7 {
8 printf("i= %d\n",i);
9 printf("tab[i]= %d\n",tab[i]);
10 if (tab[i] >= 0)
11 *som=*som+tab[i];
12 }
13 return;
14 }
15 int main(void)
16 {
17 int res;
18 int tabAA[5] = {15,-3,-2,0,6};
19 sommePositifs(tabAA,&res,4);
20 printf("La somme des nombres positifs est : %d",res);
21 return 0;
22 }

Listing A.3: Code C pour une fonction qui admet un passage de paramètres ‘par résultat’
1 #include <stdio.h>
2 int sommePositifsNegatifs(int *tab, int *somNeg,unsigned n)
3 {
4 int somPos=0;
5 *somNeg=0;
6 unsigned i;
7 for (i = 0; i <= n-1; i++)
8 {
9 printf("i= %d\n",i);
10 printf("tab[i]= %d\n",tab[i]);
11 printf("somPos= %d\n",somPos);
12 printf("somNeg= %d\n",*somNeg);
13 if (tab[i] >= 0)
14 somPos=somPos+tab[i];
15 else
16 *somNeg=*somNeg+tab[i];
17 }
18 return somPos;
19 }
20 int main(void)
21 {
22 int resNeg;
23 int tabAA[5] = {15,-3,-2,0,6};
24 printf("La somme des nombre positifs est %d\n",sommePositifsNegatifs(tabAA,&resNeg,5));
25 printf("La somme des nombre negatifs est %d\n",resNeg);
26 return 0;
27 }

94
 Chapitre A : Programmation en langage C des exercice du chapitre 1

Listing A.4: Code Python définissant et utilisant une fonction qui retourne trois résultats
1 def test2():
2 return ’abc’, 100, [0, 1, 2]
3 a, b, c = test2()
4 print(a)
5 print(b)
6 print(c)

Listing A.5: Code Python définissant et utilisant une fonction qui retourne deux résultats
1 def sommePositifs(arr):
2 somPos = 0
3 somNeg = 0
4 for num in arr:
5 if num > 0:
6 somPos += num
7 else:
8 somNeg += num
9 return somPos,somNeg
10 print(sommePositifs([15,-3,-2,0,6]))

Figure A.1: Résultat d’exécution du code C de la fonction sommePositifs

Figure A.2: Résultat d’exécution du code C de la procédure sommePositifs

95
 Chapitre A : Programmation en langage C des exercice du chapitre 1

Figure A.3: Résultat d’exécution du code C de la fonction sommePositifsNegatifs

A.2 Implémentation de la solution de l’exercice 2

Listing A.6: Code C utilisant la fonction Equilibre – solution basée mod et div
1 #include <stdio.h>
2 #include <stdbool.h>
3 int reverse(int n)
4 {
5 printf("**** %d *****\n",n);
6 int rev;
7 int lastDigit;
8 rev = 0;
9 while (n> 0)
10 {
11 lastDigit = n % 10;
12 rev =(rev*10) +lastDigit;
13 n = div(n,10);
14 }
15 return rev;
16 }
17 bool Equilibre(int n)
18 {
19 if (reverse(n)==n)
20 {
21 return true;
22 }
23 else
24 {
25 return false;
26 }
27 }
28 int main() {
29 int nt;
30 printf("Entrer le nombre que vous voulez tester: \n");

96
 Chapitre A : Programmation en langage C des exercice du chapitre 1

31 scanf("%d", &nt);
32 printf(Equilibre(nt) ? "true\n" : "false\n");
33 return 0;
34 }

Listing A.7: Code Python pour fonction reverse – basée modulo et division naturelle
1 def reverseNumber():
2 reverse = 0
3 number = int(input("Please input a number to be reversed.\n"))
4 while (number > 0):
5 lastDigit = number % 10
6 reverse =(reverse*10) +lastDigit
7 number = number // 10
8 return reverse
9 print(reverseNumber())

Listing A.8: Code C définissant et utilisant la fonction Equilibre Récursive

1 #include <stdio.h>
2 #include <stdbool.h>
3 #include <math.h>
4 int reverse(int n)
5 {
6 if (n)
7 return ((n%10)*pow(10,(int)log10(n))+reverse(n/10)); 1
8 else
9 return 0;
10 }
11 bool Equilibre(int n)
12 {
13 if (reverse(n)==n)
14 {
15 return true;
16 }
17 else
18 {
19 return false;
20 }
21 }
22 int main() {
23 int nt;
24 printf("Entrer le nombre que vous voulez tester: \n");
25 scanf("%d", &nt);
26 printf(Equilibre(nt) ? "true\n" : "false\n");

1
[Link]

97
 Chapitre A : Programmation en langage C des exercice du chapitre 1

27 return 0;
28 }

A.3 Implémentation de la solution de l’exercice 3

Listing A.9: Code C définissant et utilisant la fonction Récursive DérangementRec

1 #include <stdio.h>
2 #include <math.h>
3 int main() {
4 int nt;
5 printf("Entrer le nombre n: ");
6 scanf("%d", &nt);
7 printf("%d",DerangementRec(nt));
8 return 0;
9 }
10 int DerangementRec(int n)
11 {
12 if (n==1)
13 return (0);
14 else
15 if (n%2==0)
16 return (n*DerangementRec(n-1)+1);
17 else
18 return (n*DerangementRec(n-1)-1);
19 }

Listing A.10: Code C définissant et utilisant la fonction Itérativee DérangementIt

1 #include <stdio.h>
2 #include <math.h>
3 int main() {
4 int nt;
5 printf("Entrer le nombre n: ");
6 scanf("%d", &nt);
7 printf("%d",DerangementIt(nt));
8 return 0;
9 }
10 int DerangementIt(int n)
11 {
12 int
13 }

A.4 Implémentation de la solution de l’exercice 4

Listing A.11: Code C pour la fonction récursive sommePosRec

98
 Chapitre A : Programmation en langage C des exercice du chapitre 1

1 #include <stdio.h>
2 //
3 double sommePosRec(double *T, int n)
4 {
5
6 if (n<0)
7 return 0;
8 else
9 printf("\n n=%d \t T[n]=%f",n,T[n]);
10 if (T[n] > 0)
11 return (T[n]+sommePosRec(T,n-1));
12 else
13 return (sommePosRec(T,n-1));
14 }
15
16 int main(void)
17 {
18 double tabEff[5] = {15,-3.5,-2,0,6};
19 printf("\n\n La somme des elements positifs dans ce tableau est: %Lf",sommePosRec(
,→ tabEff,5));
20 return 0;
21 }

Listing A.12: Code C pour la fonction récursive EquilibreRec

1 #include <stdio.h>
2 //
3 double sommePosRec(double *T, int n)
4 {
5
6 if (n<0)
7 return 0;
8 else
9 printf("\n n=%d \t T[n]=%f",n,T[n]);
10 if (T[n] > 0)
11 return (T[n]+sommePosRec(T,n-1));
12 else
13 return (sommePosRec(T,n-1));
14 }
15
16 int main(void)
17 {
18 double tabEff[5] = {15,-3.5,-2,0,6};
19 printf("\n\n La somme des elements positifs dans ce tableau est: %Lf",sommePosRec(
,→ tabEff,5));
20 return 0;
21 }

99
 Chapitre A : Programmation en langage C des exercice du chapitre 1

A.5 Implémentation de la solution de l’exercice 5

Listing A.13: Code C définissant et utilisant la fonction recursive Maximum

1 #include <stdio.h>
2 #include <math.h>
3 int Maximum(int n1, int n2)
4 {
5 if (n1==0)
6 return(n2);
7 else
8 if (n2==0)
9 return(n1);
10 else
11 return(Maximum(n1-1,n2-1)+1);
12 }
13 int main() {
14 int a,b;
15 printf("Entrer le premier nombre: \n");
16 scanf("%d", &a);
17 printf("Entrer le deuxieme nombre: \n");
18 scanf("%d", &b);
19 printf("Le plus grand nombre est: %d\n",Maximum(a,b));
20 return 0;
21 }

A.6 Implémentation de la solution de l’exercice 6

Listing A.14: Code C définissant et utilisant la fonction recursive nbrPart

1 #include <stdio.h>
2 #include <math.h>
3 int nbrPart(int p, int q)
4 {
5 if (q==1)
6 return(1);
7 else
8 if (p<q)
9 return(0);
10 else
11 if (p==q)
12 return(1);
13 else
14 return(nbrPart(p-1,q-1)+nbrPart(p-q,q));
15 }
16 int main() {
17 int a,b;
18 printf("Entrer le nombre a partitionner: \n");

100
 Chapitre A : Programmation en langage C des exercice du chapitre 1

19 scanf("%d", &a);
20 printf("Entrer le nombre de partitions: \n");
21 scanf("%d", &b);
22 printf("Le nombre de partiotions possibles de %d en %d partitions est: %d", a,b,nbrPart
,→ (a,b));
23 return 0;
24 }

A.7 Implémentation de la solution de l’exercice 7

Listing A.15: Code C définissant et utilisant la fonction recursive maxTabRec – Version1

1 #include <stdio.h>
2
3 double maxTabRec(double *T, int i,int n)
4 {
5 if (i==n-1)
6 return(T[n-1]);
7 else
8 {
9 if (T[i]>maxTabRec(T,i+1,n))
10 return(T[i]);
11 else
12 return(maxTabRec(T,i+1,n));
13 }
14 }
15 int main(void)
16 {
17 double tabEff[5] = {15,-3.5,-2,0,6};
18 printf("Le maximum du tableau est: %f",maxTabRec(tabEff,0,5));
19 return 0;
20 }

Listing A.16: Code C définissant et utilisant la fonction recursive maxTabRec – Version2

1 #include <stdio.h>
2 //
3 double maxTabRec(double *T, int n)
4 {
5 if (n-1==0)
6 return(T[n-1]);
7 else
8 {
9 printf("%d %f \t %f\n",n,T[n-1],maxTabRec(T,n-2));
10 if (T[n-1]>maxTabRec(T,n-2))
11 return(T[n-1]);
12 else
13 return(maxTabRec(T,n-2));

101
 Chapitre A : Programmation en langage C des exercice du chapitre 1

14 }
15 }
16 int main(void)
17 {
18 double tabEff[5] = {15,-3.5,-2,0,6};
19 printf("Le maximum du tableau est: %f",maxTabRec(tabEff,5));
20 return 0;
21 }

Listing A.17: Code C pour la suite numérique

1 #include <stdio.h>
2 #include <stdbool.h>
3 #include <math.h>
4 struct suiteNum
5 {
6 int n;
7 double tab[100];
8 };
9 bool estVide(struct suiteNum s)
10 {
11 if (s.n==0)
12 return(true);
13 else
14 return(false);
15 }
16 struct suiteNum reste(struct suiteNum s)
17 {
18 if (estVide(s)==false)
19 s.n=(s.n)-1;
20 return s;
21 }
22 double Elem(struct suiteNum s)
23 {
24 return [Link][s.n-1];
25 }
26 double maxSuiteNum(struct suiteNum s)
27 {
28 if (estVide(reste(s)))
29 return Elem(s);
30 else
31 if (Elem(s)>maxSuiteNum(reste(s)))
32 return Elem(s);
33 else
34 maxSuiteNum(reste(s));
35 }
36 int main()

102
 Chapitre A : Programmation en langage C des exercice du chapitre 1

37 {
38 struct suiteNum myS;
39 int nbr;
40 double tabEff[5];
41 printf("Donner le bombre d’elements de votre suite’: \n");
42 scanf("%d", &nbr);
43 myS.n=nbr;
44 printf("La taille actuelle de la suite est: %d",myS.n);
45 printf(estVide(myS) ? "\t Elle est vide\n" : "\t Elle n’est pas vide \n");
46 int i;
47 for(i=0;i<nbr;i++)
48 scanf("%Lf", &[Link][myS.n-i-1]);
49 printf("\n***********************\n");
50 printf("Le premier element de la suite est: %f \n", Elem(myS));
51 printf("\n***********************\n");
52 printf("\n***********************\n");
53 printf("Le maximum de cette suite numerique est: %f",maxSuiteNum(myS));
54 printf("\n***********************\n");
55 printf("\n***********************\n");
56 printf("Vider la suite:\n");
57 while (estVide(myS)==false)
58 {
59 printf("Taille actuelle: %d \t",myS.n);
60 printf("Tete de la suite: %f \n", Elem(myS));
61 myS=reste(myS);
62 }
63 printf("\n***********************\n");
64 printf("La taille actuelle de la suite est: %d",myS.n);
65 printf(estVide(myS) ? "\t La suite est vide \n" : "\t La suite n’est pas vide \n");
66 return 0;
67 }

103
 Chapitre A : Programmation en langage C des exercice du chapitre 1

Figure A.4: Résultat d’exécution du code C pour la suite numérique

104