ch2: Paradigmes classiques et
techniques de conception
d’algorithmes
Classe : M1SIAD
Dr. Hana RABBOUCH
Plan
I. Algorithme: Rappel
II. Paradigmes classiques et techniques de conception d’algorithmes
1. Récursivité ( Simple, Multiple, Mutuelle, Imbriquée)
2. Récursivité terminale et non terminale
3. Dérécursivation
4. Diviser pour régner
2
1
Algorithmique
Rappel
Un peu d’histoire
Al-Khawarizmi
né vers 783 à Ouzbékistan, et
783
décédé vers 850 à Bagdad, est un
mathématicien, géographe,
astrologue et astronome perse,
membre des Maisons de la sagesse
dont les écrits, rédigés en langue
arabe, ont permis l’introduction de
l’algèbre en Europe. Il est à
l’origine des mots «algorithme » et
« algèbre » ou encore de
l’utilisation des chiffres arabes.
source: [Link]
4
Algorithme
Définition:
Un algorithme est une suite ordonnée d’instructions qui indique la
démarche à suivre pour résoudre un problème.
Instruction 1
Instruction 2
Donnée en entrée Instruction 3 Donnée en sortie
Instruction 4
……….
5
La représentation d’un algorithme
Il existe deux façons pour représenter un algorithme:
1. Organigrame:
- Représentation graphique avec des symboles
(carrés, losanges, etc.)
- Offre une vue d’ensemble de l’algorithme
- Représentation quasiment abandonnée
aujourd’hui.
Organigramme pour faire bouillir de l’eau
6
La représentation d’un algorithme
Il existe deux façons pour représenter un algorithme:
2. Pseudo-Code:
- Représentation textuelle avec une série de conventions ressemblant à un
langage de programmation.
- Plus pratique pour écrire un algorithme.
- Représentation largement utilisée.
7
Les étapes d’un algorithme
Préparation du traitement
• données nécessaires à la résolution du problème
Traitement
• résolution pas à pas,
• après décomposition en sous-problèmes si nécessaire
Edition des résultats
• impression à l’écran,
8
Les étapes d’un algorithme
Exemple:
Algorithme Calcul_Carré
Variables A,C : Entier
Début
Ecrire("Veuillez saisir la valeur de A: ")
Lire(A)
C ← A*A
Ecrire("le carré de ", A, "est :", C)
Fin
9
Les éléments d’un algorithme
Les variables:
La déclaration de variables est effectuée par la forme suivante :
Variables liste_identificateurs : type
Exemple:
Variables i, j, k : entier
x, y : réel
ok : booléen
ch1, ch2 : chaîne de caractères
10
Les éléments d’un algorithme
Les constantes:
La déclaration des constantes est effectuée par la forme suivante :
Constante nom_identificateur=valeur : type
Exemple:
Constantes
PI=3.14 : réel
MAXI=32 : entier
(par convention, les noms de constantes sont en majuscules)
11
Les éléments d’un algorithme
Les opérations:
• Affectation: variable ⟵ valeur
• Elévation à la puissance : ^
• Opérateurs de calcul:
Entiers : + , – , * , div , mod
Réels : + , – , * , /
Booléens : and ; or ; not
• Opérateurs de comparaison (le résultat est un booléen)
Entiers, réels, caractères : = ; <= ; < ; >= ; > ; <>
Booléens : = ; <>
12
Les éléments d’un algorithme
Instructions conditionnelles
• Instructions conditionnelles: Si Alors Sinon
• Syntaxe:
SI < condition >
ALORS < action _alors >
SINON < action _SINON >
FINSI
13
Les éléments d’un algorithme
Instructions itératives
• Boucle: Pour
• Exemple:
Algorithme CompteJusqueCent
Variable i : entier
Début
Pour i ← 1 à 100 faire
Écrire(i)
Fin Pour
Fin
14
Les éléments d’un algorithme
Instructions itératives
• Boucle: Tant que
• Exemple:
Algorithme CompteJusqueCentVersionTQ
Variable i : entier
Début
i←1
Tant que (i ≤ 100) faire
Écrire(i)
i ← i+1
Fin tant que
Fin
15
Les éléments d’un algorithme
Instructions itératives
• Boucle: Répéter
• Exemple:
Algorithme CompteJusqueCentVersionRepeter
Variable i : entier
Début
i←1
Répéter
Écrire(i)
i ← i+1
Jusqu'à (i < 100)
Fin
16
Les éléments d’un algorithme
Structure à choix multiple
• La structure SELONQUE
• Exemple:
Algorithme MentionSelonNote
Variable note : réel
Début
SELONQUE
note ≥ 16 : ECRIRE (‘'TB’’)
note ≥ 14 : ECRIRE (‘'B’’)
note ≥ 12 : ECRIRE (‘'AB’’)
note ≥ 10 : ECRIRE (‘'Passable’’)
SINON : ECRIRE (‘'ajourné’’)
FINSELONQUE
Fin
17
Les éléments d’un algorithme
Fonctions
• Syntaxe:
Fonction <nom_fonction> ( <liste des paramètres> ) : <type de résultat>
< déclaration des objets locaux à la fonction>
Début
{ corps de la fonction}
RETOURNER (résultat)
Fin
18
Les éléments d’un algorithme
Fonctions
• Exemple:
Fonction perimetre_rectangle (largeur, longueur : Entier) : Entier
Debut
Retourner (2*(largeur+longueur))
Fin
19
2
Paradigmes classiques et techniques
de conception d’algorithmes
Récursivité
La récursivité
Définition
• Un algorithme est dit récursif lorsqu’il est défini en fonction de lui-même.
Principe:
• Une fonction récursive est une fonction qui s'appelle elle-même jusqu’à
Trouver une condition d’arrêt.
21
La récursivité
Exemple:
Algorithme de la fonction factorielle
Algorithme Fact (n : entier)
Début:
Si n = 0 ou n=1 retourner 1
SINON retourner n * Fact(n-1)
Fin
22
La récursivité
Exemple: Algorithme de la fonction factorielle
23
Les types de la récursivité
Il y a différents types de récursivité:
Récursivité simple
Récursivité multiple
Récursivité mutuelle
Récursivité imbriquée
24
La récursivité simple
Principe
La récursivité simple est basé sur un seul appel de la fonction récursive.
1푠 �=0
Exemple
La fonction puissance définie comme suit : � n =
� × ��_1
l’algorithme correspondant s’écrit:
PUISSANCE (x, n)
Sinon renvoyer � ×PUISSANCE(x, n−1)
Si n = 0 alors renvoyer 1
Exécution: Calcul de 43
4 ×PUISSANCE(4, 2)-> 4×4 ×PUISSANCE(4, 1) -> 4×4×4×PUISSANCE(4, 0)-> 4×4×4×1
25
La récursivité multiple
Principe
Une définition récursive peut contenir plus d’un appel récursif
Exemple
Le calcul des combinaisons en se servant de la relation de Pascal :
l’algorithme correspondant s’écrit:
COMBINAISON (n, p)
Si p = 0 ou p = n alors renvoyer 1
sinon renvoyer COMBINAISON (n−1, p) + COMBINAISON (n−1, p−1)
26
La récursivité mutuelle
Principe
Des définitions sont dites mutuellement récursives si elles dépendent les unes
des autres. Ça peut être le cas pour la définition de la parité :
Les algorithmes correspondants s’écrivent:
PAIR (n) IMPAIR (n)
Si n = 0 alors renvoyer vrai Si n = 0 alors renvoyer faux
sinon renvoyer IMPAIR (n−1) sinon renvoyer PAIR (n−1)
27
La récursivité imbriquée
Principe
Une récursivité imbriquée consiste à faire l’appel de la fonction récursive à
l’intérieur d’un autre appel récursif.
Exemple:
La fonction d’Ackermann
L’algorithme correspondant s’écrit:
ACKERMANN(m, n)
si m = 0 alors n+1
sinon si n = 0 alors ACKERMANN(m−1, 1)
sinon ACKERMANN(m−1, ACKERMANN(m, n−1))
28
La récursivité terminale
Principe
Un module récursif est dit terminal si aucun traitement n'est effectué à la
remontée d’un appel récursif (sauf le retour du module).
Exemple: reste de la division entière de a par b ( a mod b=(a-b) mod b)
L’algorithme correspondant s’écrit:
Reste (a,b: entier): entier
si a<b alors retourner (a)
Sinon retourner Reste (a-b, b)
29
La récursivité non terminale
Principe
Un module récursif est dit non terminal si le résultat de l'appel récursif est
utilisé pour réaliser un traitement (en plus du retour du module).
Exemple:
Algorithme de la fonction factorielle
30
Dérécursivation
Définition
Dérécursiver, c’est transformer un algorithme récursif en un algorithme
équivalent ne contenant pas d’appels récursifs.
Exemple: Algorithme de la fonction factorielle:
Version récursive Version itérative
Algorithme FactRecursif Algorithme FactIteratif
Variable n : entier Factorielle (Variables n : entier): entier
Début: Déclaration F, i: entier
Si n = 0 retourner 1 Début:
SINON retourner n * Fact(n-1) F← 1
Fin Pour i allant de 1 à n faire
F←F*i
Retourner F
Fin
31
Récursif vs Itératif
Une mise au point
Les programmes itératifs sont souvent plus efficaces, mais les
programmes récursifs sont plus faciles à écrire. Les compilateurs savent, la
plupart du temps, reconnaître les appels récursifs terminaux, et ceux-ci
n’engendrent pas de surcoût par rapport à la version itérative du même
programme. Il est toujours possible de dérécursiver un algorithme récursif.
32
“ Exercice:
1. Ecrivez un algorithme récursif terminal pour la
fonction factorielle
33
Solution
Algorithme FactorielleTerminale
resultat ⟵1
Procédure Facto ( n: entier, Var resultat: entier)
Si (n<=1) retourner resultat
Sinon retourner Facto (n-1, n * resultat);
Fin
Exécution:
Fact(4,1)➝Fact(3,4∗1) ➝ Fact(2, 3 ∗ 4) ➝ Fact(1, 2 ∗12) ➝ Fact(1, 24)
34
2
Paradigmes classiques et techniques
de conception d’algorithmes
Diviser pour Régner
Le paradigme "Diviser pour régner"
Principe
Diviser pour régner est une méthode algorithmique basée sur le
principe suivant :
• On divise un problème qui est généralement complexe à résoudre en
une multitude de "petits problèmes"
• Les "petits problèmes" seront plus simples à résoudre que le problème
original.
• Une fois les petits problèmes résolus, on recombine les
"petits problèmes résolus" afin d'obtenir la solution du problème de
départ.
36
Le paradigme "Diviser pour régner"
Etapes
Le paradigme "diviser pour régner" repose donc sur 3 étapes :
DIVISER : le problème d'origine est divisé en un certain nombre de
sous-problèmes
RÉGNER : on résout les sous-problèmes (les sous-problèmes sont plus
faciles à résoudre que le problème d'origine)
COMBINER : les solutions des sous-problèmes sont combinées afin
d'obtenir la solution du problème d'origine.
37
"Diviser pour régner": Tri par fusion
9 7 1 4 3 8
9 7 1 4 3 8
9 7 1 4 3 8
9 7 4 3
7 9 1 3 4 8
1 7 9 3 4 8
1 3 4 7 8 9
38
Le paradigme "Diviser pour régner"
Algorithme
fonction triFusion(T, debut, fin):
Si debut < fin alors faire
# Trouvez le point milieu pour diviser le tableau en deux moitiés
milieu = (debut+fin)/2
# Appelez triFusion pour la première moitié du tableau:
triFusion(T, debut, milieu)
# Appelez triFusion pour la deuxième moitié du tableau:
triFusion(T, milieu+1, fin)
# Fusionnez les deux moitiés triées
fusion(T, debut, milieu, fin)
39
Le paradigme "Diviser pour régner"
Algorithme
fonction triFusion(T, debut, fin):
Si debut < fin alors faire
# Trouvez le point milieu pour diviser le tableau en deux moitiés
milieu = (debut+fin)/2
# Appelez triFusion pour la première moitié du tableau:
triFusion(T, debut, milieu)
# Appelez triFusion pour la deuxième moitié du tableau:
triFusion(T, milieu+1, fin)
# Fusionnez les deux moitiés triées
fusion(T, debut, milieu, fin)
40
