Université Abdelhamid Mehri – Constantine 2

2022-2023. Semestre 3

Algorithmique et Structures de Données (ASD)

Chargée de Cours : Mme Dj.Hammoud

Objectifs du cours
 Présenter les etapes de résolution d’un problème algorithmique ;
 Rappeler la conception modulaire en introduisant les concepts de
fonctions et procédures ;
 Réviser les modes de passage de paramètres ;
 Définir le concept de la récursivité dans les fonctions et procédures ;
 Présenter les etapes d’une résolution récursive.

1
 1. Introduction
Un algorithme est une suite finie d’opérations ou d’instructions permettant de résoudre un problème.
La resolution d’un problème en algorithmique est souvent formulée comme la transformation
d’un ensemble de valeurs, d’entrée ( Les données), en un nouvel ensemble de valeurs, de sortie
( les résultats).
Un algorithme peut être spécifié (defini ou decrit) de différentes manières :
 en langage naturel,
 graphiquement,
 en pseudo-code (c’est le cas au niveau de l’ASD),
 par un programme écrit dans un langage informatique ...
La seule condition est que la description soit précise.

En ASD, nous étudieons les algorithmes corrects. Un algorithme est (totalement) correct
lorsque pour chaque instance (chaque déroulement), il se termine en produisant la bonne
sortie. Il existe aussi des algorithmes partiellement corrects dont la terminaison n’est pas assurée
mais qui fournissent la bonne sortie lorsqu’ils se terminent. Il existe également des
algorithmes approximatifs qui fournissent une sortie inexacte mais proche de l’optimum (domaine
de l’intelligence artificielle).

1.1. Etapes de Résolution d’un Problème en Algorithmique

Pour une résolution méthodique d’un problème en algorithmique, vous avez à suivre les étapes
suivantes (qui deviendront des réflexes avec le temps) :

1. Etudier et Analyser votre problème (lire et relire l’énoncé du problème (Ex : l’énoncé du TD ou
TP) ;
2. Trouver une solution (une idée) qui résoud le problème (ici Travail de reflexion pour poser
une solution globale qui peut être narrative, graphique ou une formule), une fois l’idée trouvée
(même mentalement) :
2.1. Choisissez les structures de données adaptées aux entrées (données) de votre
solution ;
2.2. Entammez l’écriture de votre algorithme qui décrit la solution trouvée en pseudo
code tout en choisissant les structures de contrôle adaptées (et écrivez votre Algo) ;
2.3. Verifiez que votre algorithme est correcte en le déroulant avec plusieurs jeu de
tests (se termine et bonne sortie) ;
2.4. Analyser la complexité de votre algorithme (thème du chapitre 2) ;
2.5. Penser toujours à optimiser vos algorithmes.

2. Conception Modulaire : Rappel sur les Fonctions et Procédures

La conception modulaire en algorithmique consiste à construire des algorithmes constitués
de plusieurs sous algorithmes (ou modules). Chaque sous algorithme résoud un sous problème;
il reçoit des données et transmet des résultats. Ceci permet l’utilisation répétitive d’un même
module en différents points de l’algorithme. L e module peut etre une fonction ou une procédure.

2.1. Fonctions
Une fonction est un ensemble d’actions effectuant un calcul sur des paramètres dont les
valeurs lui sont ‘passées’. La fonction se sert alors de ces paramètres pour calculer un résultat
qu’elle renvoie explicitement en fin de traitement ; il existe deux types de fonctions:
1-fonctions prédéfinies par le langague exemple: sin, cos, sqrt, etc
2- fonctions définies par l’utilisateur selon les besoins du problème à traiter.

2
2.1.1. Déclaration de fonction
La déclaration d’une fonction se fait de différentes façons suivant le langage de
programmation utilisé. Dans notre langage de description algorithmique, nous adoptons la syntaxe
suivante:

Fonction nom-de-la-fonction (mode-de-passage X1: Type1 , ..., mode-de-passage Xn: Typen): Type-de-
la-fonction

Déclaration
... /*déclaration de variables locales à cette fonction*/
Début
... /* une séquence d’actions constituant le corps de la fonction*/
retourner (expression)
ffoncfonction*/
/*C’est la dernière action pour retourner le résultat à l’algorithme appelant*/
Fin

X1,X2,....,Xn: sont appelés paramètres formels, ce sont les noms donnés aux entrées futures de la
fonction. Ils servent à désigner, dans le corps de la fonction, les variables mises en oeuvre par ses
actions.

2.1.2. Appel d’une fonction :

Une fonction s’utilise (est appelée), quelque soit le langage de programmation, en insérant:
Nom-de-la-fonction (V1, ... , Vn)
1. dans une expression à droite d’une affectation.
2. ou dans une action d’écriture.
3. ou comme paramètre d’une autre fonction ou procédure (un appel trés important).
4. ou dans un test.

V1, ... , Vn : sont appelés paramètres effectifs.

Chaque paramètre effectif Vi doit être de même type que le paramètre formel associé. Ainsi, le
nombre de paramètres effectifs doit être le même que le nombre de paramètres formels.

Exemple 1: Ecrire une fonction (déclaration) qui calcule le minimum de deux nombres entiers.

Fonction minimum (donnée a , b : entier) : entier

Déclaration
m :entier
Début
si a < b alors m ← a sinon m ← b Ou bien Si a< b alors retourner a sinon retourner b
finsi retourner m
fin

2.2. Procédures
A la différence des fonctions, les procédures ne calculent pas un résultat; elles permettent de
modifier l’état du corps de l’algorithme appellant (modification de variables). Pour le calcul d’un
résultat, on préfère les fonctions. Néanmoins, il est toujours possible de remplacer une fonction
par une procédure équivalente. La procédure reprend tous les paramètres de la fonction et en
rajoute un pour le résultat.

2.2.1. Déclaration d’une procédure

3
La syntaxe de la déclaration d’une procédure est la suivante:

Procédure nom-de-la-procedure (mode-de-passage X1: Type1 , ..., mode-de-passage Xn: Typen)

Déclaration
... /*déclaration de variables locales à cette procédure*/
Début
... /* une séquence d’actions constituant le corps de la procédure*/
fin

2.2.2. Appel d’une procédure

L’appel d’une procédure se fait, à partir d’un autre algorithme en écrivant le nom de la
procédure appelée, suivi d’une liste de paramètres effectifs au même nombre et de même types que
les paramètres formels. Ainsi à l’appel d’une procédure, nous insérons :
nom-de-la-procédure (V1, ... , Vn)

Exemple 2:
Procédure double (données/résultat x : entier)

début
x ← 2*x;
fin
Algorithme Exemple2
déclarations
a : entier
début
…….
a ← 4;
écrire(a);
double(a);
écrire(a);
...
fin
La procédure double a un effet de bord: la modification de la variable a de l’algorithme Exemple2.

3. Modes de Passage des Arguments

Les paramètres formels et effectifs sont mis en correspondance deux à deux d’après l’ordre
qu’ils occupent dans leur liste respective. En général, cette correspondance se fait selon les trois
modes de passage suivants.

3.1. Mode de Passage par Donnée

Le paramètre formel en mode donnée est considéré comme une variable locale dans le corps
du sous algorithme. A l’appel, il est initialisé par la valeur du paramètre effectif. Ce mode est aussi
dit passage par valeur.

Exemple 3 (mode donnée)

Procédure affichage-date (donnée x : date)

Début
écrire(x.jour, ”/”);
écrire(x.mois, ”/”);
écrire(x.année);
fin /* x n’a pas été modifié */

Algorithme Exemple3
Déclarations
d : date
début
d ← (14, 9, 2022);

4
affichage-date(d);
fin
A l’appel de la procédure affichage-date(d): la valeur de d (14, 9, 2022) est transmise à x, qui est ainsi
initialisée est utilisé dans la procédure sans être modifiée. Donc la variable d a la même valeur avant
et après l’appel de la procédure affichage-date(d) a cause du mode de passage par donnée.

Noter que tous les paramètres des fonctions sont généralement en mode donnée.

3.2. Mode de Passage par résultat

Un argument en mode résultat est considéré comme une variable non initialisée dans le
corps du sous algorithme. A la fin de l’exécution de ce dernier, la valeur calculée pour cet argument
est alors affectée au paramétre effectif. Ce mode est présent dans le langage Algol W mais pas dans
JAVA !

Exemple 4 (mode résultat)

Procédure lecture-date (résultat x : date)
Début
écrire(”jour=”);
lire(x.jour);
écrire(”mois=”);
lire(x.mois);
écrire(”annee=”);
lire(x.annee);
fin

Algorithme Exemple4
Déclarations
d : date; /* non initialisée */
Début
/* jusqu’ici dans d il n’y a rien /
lecture-date(d);
/* ici d contient les valeurs saisies dans la procédure */
fin

A l’appel de la procedure lecture-date(d), la valeur de d n’est pas prise en compte, x n’est pas
initialisée, x est calculée ( ici une saisie) dans la procédure, la valeur finale de x est transmise à d.

3.3. Mode de Passage par donnée/résultat

A l’appel, la valeur du paramètre effectif sert à initialiser le paramètre formel. A la fin
de l’exécution du sous algorithme la valeur calculée pour l’argument formel en mode
donnée/résultat est retournée dans le paramètre effectif. Ce mode est aussi appeler par variable et
aussi par adresse (le cas du langage C).

Exemple 5 : (mode donnée/résultat)

Procédure incrémenter (donnée/résultat x : entier)
Début
x← x + 1
fin

Algorithme Exemple5
Déclarations
a :entier
Début
a ← 3 ...
/* jusqu’ici a = 3 */
incrémenter(a)
/* maintenant a = 4 */
Fin

Après l’appel de la procedure incrémenter(a), la valeur de a est transmise à x, qui est ainsi initialisé.

5
x est modifiée dans la procédure et la valeur finale de x est transmise à a.

Exemple 6 (comparaison entre les trois modes)

Algorithme Exemple6
Déclarations
Procédure Echange ( ???? x, y : entier)
Déclarations
t :entier
Début
t← x
x← y
y← t

fin
a,b : entier /* variables de l’algo Exemple6
Début
a ←1
b ← 2 ...
Echange (a, b);
écrire(a,b)
fin

Si le mode de passage par donnée est utilisé, a=1 et b=2,

Si le mode de passage par résultat est utilisé, a=? et b=?,
Si le mode de passage par donnée/résultat est utilisé, a=2 et b=1.

NB : Les vidéos 2, 3 et 4 (plateforme elearining) expliquent cette première partie.

4. Récursivité
En algorithmique, la récursivité permet une écriture élégante et compréhensible
e t c o n c i s e des algorithmes. Dans certains cas, le sous-problème est une illustration
du problème initial, mais pour un cas ”plus simple”. Par conséquent, la solution du problème
s’exprime par rapport à elle-même. On appelle ce phénomène récursivité.

Exemple 7: Le calcul de la somme des n premiers nombres est donné par:

n
S1 = 1 + 2 + 3.. + (n − 1) + n = ∑ i
i=1
Or, S1=S2 + n sachant que :
n-1
S2 = 1 + 2 + 3.. + (n − 1) = ∑ i
i=1
.Donc, il nous suffit de savoir calculer S2 pour pouvoir calculer la valeur de S1. Le sous-problème
du calcul de S2 est le même que le problème initial (S1), mais pour un cas ”plus simple”, car
(n − 1 < n.

Le problème a été réduit à lui-même, mais pour un cas plus simple. En algorithmique, le sous-
algorithme récursif traitant un problème donné, fait un appel à lui-même pour traiter un cas plus
simple, ce qui correspond à un appel avec des paramètres différents (”plus réduits”).
Un appel récursif produit lui-même un autre appel récursif, ...,etc
Ceci produira une suite infinie d’appels, il faut donc arrêter cette suite au moment où le sous-
problème peut être résolu directement: condition d’arrêt. La fonction s’énonce ainsi:

6
Fonction Somme ( Donnée n : entier) : entier
Déclarations
result : entier;
Début
Si n= 1 /* test d’arrêt
Alors result  1
Sinon result  n+ Somme (n-1) /*Appel récursif
Finsi
Retourner (result)
Fin

4.1. Evaluation d’un appel récursif

• Comment est-il possible d’appeler un sous-programme pendant que celui-ci est en
train de s’exécuter?
• Comment se fait-il que les données gérées par ces différents appels du même sous-
programme ne se ”mélangent” pas?
Pour répondre à ces questions, il faut d’abord comprendre le modèle de
mémoire utilisé dans l’exécution des sous- programmes.

4.1.1. Modèle de mémoire

Chaque sous-programme (le programme principal aussi) utilise une zone de mémoire pour stocker:

1. ses arguments (paramètres) et ses variables locales.

2. une place pour l’adresse de retour au programme appelant (le programme principal
n’a pas besoin de cette adresse).
3. dans le cas d’une fonction, elle réserve de plus, une place pour le résultat
retourné.
L’allocation de cette zone de mémoire se fait au moment de l’appel du sous programme, dans une
zone de mémoire spéciale associé au programme, appelée la pile d’exécution.

Les zones de mémoire de tous les sous-programmes appelés sont empilées suivant l’ordre
de leur appels, puis dépilées un à un, dès que le sous-programme correspondant se termine. Par
conséquent, une zone de mémoire d’un sous-programme n’existe physiquement que pendant
l’exécution de celui ci.

Exemple 8 : Soit l’exemple de la fonction suivante:

Fonction Fonc1 (donnée X: entier; donnée Y: réel) : booléen
Déclarations
T: tableau[3] d’entier;
C: caractère;
Début
...
Fin

On représentera la zône de mémoire occupée par cette fonction de la manière suivante:

t

X Y

T C
@ de
retour
résultat

zone de mémoire de7 Fonc1

4.2. Déroulement des appels récursifs

Exemple 9: Considérons la fonction récursive qui calcule le factoriel d’une valeur entière positive
n (donné par: n! = 1 x 2 x 3.. x (n − 1) x n = (n − 1)! x n.
Fonction factoriel ( Donnée N : entier) : entier
Déclarations
fact: entier;
Début
si N=1 alors fact ← 1 /* condition d’arrêt */
sinon fact ← N* factoriel (N-1) /* appel récursif */
finsi
retourner fact;
fin

Dans le cas des programmes récursifs, la pile est remplie par des appels du même sous
programme. L’enchaînement des appels et des calculs dans l’exemple du factoriel est illustré par le
schéma ci-dessous :

Factoriel(3)
Factoriel(3)
Factoriel(3) Factoriel(2)
Factoriel(2)
Factoriel(2) Factoriel(1)
Factoriel(1)

N N N
Pgm 3 2 1
principal
fact fact
fact 1
résultat résultat
résultat 1

@ de @ de @ de
retour retour retour

NB : C’est l’exemple de la somme qui a été déroulé en Présentiel (en Amphi), nous traitons des
exos en amphi en plus de ceux du support de cours et des vidéos.

4.3. Récursivité et itération

Par l’appel répété d’un même sous-programme, la récursivité permet de réaliser des
traitements répétitifs. Or, jusqu’ici, pour réaliser des répétitions nous avons utilisé les boucles
(itération). Suivant le type de problème, la solution s’exprime plus naturellement par la
récursivité ou par itération. Souvent, il est aussi simple d’exprimer les deux types de solutions.

Exemple 10: Calcul du nombre d’occurrences n d’un caractère c dans une chaîne S : nb-
occurrences ( ?, ?)

Solution récursive:
• Décomposition récursive:
. Elément de récursivité : la chaîne s, dont la taille diminue. Un cas plus simple est la chaîne sans
son premier caractère (nous l’obtenons avec la fonction Premier(s) ). La sous chaîne est
obtenue par la fonction Reste(s)

 Donc si Premier(s) = c la soluion est 1 + nb-occurrences(c, reste(s)) sinon

 c’est nb-occurrences(c, reste(s))

Condition d’arrêt :
Si s = ”” (la chaîne vide) alors n = 0 sinon c’est les appels récursif avec les conditions du pbm, voici la fonction
associée :

8
fonction nb-occurrences (Donnée c: caractère; Donnée s: chaine) : entier
Déclarations
/*ici declarer les fonc reste(s) et premier(s)
Début
si s = ””
alors retourner 0
sinon si premier(s) = c
alors retourner (1 + nb-occurrences(c, reste(s)))
sinon retourner (nb-occurrences(c, reste(s)))
finsi
finsi
Fin

Solution itérative:
fonction nb-occurrences (Donnée c: caractère; Donnée s: chaîne) : entier
Déclarations
occ: entier
/*declarer reste(s)
Début
occu ← 0;
tantque s≠” “ faire
si premier(s)=c
alors occu ← occu + 1
finsi;
s←reste(s)
fintantque
retourner occu;
fin

En principe tout programme récursif peut être écrit à l’aide d’actions itératives
(boucles), sans récursivité. Inversement, chaque type d’action itérative (répéter, tantque, pour)
peut être simulé par récursivité. Il s’agit en fait de deux manières différentes de programmation.
Utiliser l’une ou l’autre est souvent une question de ”goût” et de style de programmation.
Cependant chacune peut s’avèrer mieux adaptée que l’autre à certaines classes de problèmes.

L’avantage essentiel de l’itération est l’efficacité (exécution rapide). Un programme qui

utilise des actions itératives décrit précisément chaque action à réaliser. Ce style de programmation
est appelé impératif ou procédural. Le code compilé d’un tel programme est une image assez
fidèle des actions décrites par le programme, traduites en code machine. Les choses sont différentes
pour un programme récursif.
L’avantage de la récursivité est qu’elle se situe à un niveau d’abstraction supérieur par
rapport à l’itération. Une solution récursive décrit comment aboutir à la solution à partir d’un
cas plus simple. Ce style de programmation est appelé déclaratif. Au lieu de préciser chaque
action à réaliser, on décrit ce qu’on veut obtenir, c’est ensuite, au système de réaliser les actions
nécessaires pour obtenir le résultat demandé. Souvent la solution récursive d’un problème est plus
intuitive que l’itérative et le programme à écrire est plus court et plus lisible. Néanmoins, elle
correspond à un type de raisonnement particulier. De plus, le style déclaratif associé, produit souvent
du code moins efficace (car entre le programme descriptif et le code compilé, il y a un espace
d’interprétation rempli par le système, difficile à optimiser).

Dans les langages (comme C, Java) qui offrent à la fois l’itération et la récursivité, nous préférons
utiliser la récursivité surtout dans les situations :
 Manipulation des structures de données récursives (listes, piles et files et surtout arbres

9
 pour lequels la solution itérative est difficile à obtenir)
 Le raisonnement lui même est récursif.
 A la conception, le critère à favoriser est la réutilisation avec des solutions génériques

Exercice (Résolvez cet exercice puis voir Discussion de la solution vidéo 7)

Le nombre Dn de dérangements de n éléments vérifie l’étonnante récurrence suivante :
D1= 0
n
Dn= n*Dn-1 + (-1) , (n>=2)
1. Ecrire une fonction récursive Dérangement(??) qui calcule Dn.
2. Ecrire une fonction itérative qui calcule Dn.
3. Dérouler la fonction récursive Dérangement pour n=4.

4.4. Etapes de résolution Récursive

Nous récaputilons la résolution récursive ( lors de la conception d’une solution récursive) avec
les etapes suivantes extraites des vidéos 5 et 7. Et nous terminons ce chapitre avec la résolution (en
amphi) du dernier exercice de la serie de TD1 qui englobent toutes les notions présentées dans ce
chapitre avec des solutions génériques et réutilisables, l’un des objectifs de l’ASD.

10