Techniques

algorithmiques et
Structures de données
Techniques algorithmiques
Notion de modularité
Introduction
• Nous avons montré comment développer des algorithmes
grâce à des procédures d’affinement des instructions
jusqu’à ce que l’algorithme soit exprimé de manière telle
que le processeur prévu peut l’interpréter.
• Certaines parties de l’algorithme sont souvent totalement
indépendantes de l’algorithme principal. De tels éléments
peuvent être conçus par quelqu’un d’autre que le
concepteur de l’algorithme principal et peuvent également
être utilisés comme éléments d’un autre algorithme. Ils
peuvent être considérés comme des éléments
multifonctionnels et intégrables à tout algorithme auquel
ils seraient nécessaires.
Exemple
• Examinons la conception de certains algorithmes
destinés à être exécutés par un simple automate.
• La fonction de l’automate consiste à dessiner.
• Il est équipé de roulettes qui lui permettent des
déplacements sur la feuille de papier et d’un stylo
qui peut s’abaisser dès qu’il veut faire un trait.
 L’automate peut interpréter et
exécuter des commandes de la forme :
• Déplace (x) se déplace en avant de x cm
• Gauche (x) tourne de x degrés à gauche
• Droite (x) tourne de x degrés à droite
• Lèvestylo ôte le stylo du papier
• Baissestylo pose le stylo sur le papier.
Supposons que nous voulions que l’automate dessine deux carrés
concentriques comme le montre la figure suivante, sa position initiale
étant le point X, centre des carrés, stylo levé. Son orientation initiale
est vers le haut. On nomme A le point en haut à gauche du petit carré
et B le point en haut à gauche du grand carré.

B
A
On peut proposer l’algorithme
suivant:
Déplace en A
Dessine un carré de 10 cm de côté 1.1
Déplace en B
Dessine un carré de 20 cm de côté
• La seconde et la quatrième instruction de cet
algorithme impliquent le dessin d’un carré.
• C’est une procédure indépendante du reste de
l’algorithme,
• Ce qui implique que nous pouvons concevoir un
algorithme pour dessiner un carré sans référence
au contexte de l’algorithme qui l’utilise.
• Nous pouvons l’intégrer aux endroits prévus dans
l’algorithme 1.1 ou à tout autre algorithme pour
lequel le tracé d’un carré serait nécessaire.
Définitions
• Un algorithme qui peut être intégré à un autre
algorithme est un module (dans certains langages
de programmation, on parle de procédure ou
fonction).
• Si la procédure retourne une valeur résultante, on
l’appelle une fonction.
• La définition de l’abréviation est la déclaration de
procédure.
• Son utilisation au cours d’un algorithme est un
appel de procédure.
Notion de paramètre
• Pour que le module de conception du carré soit
globalement utilisable, il doit être en mesure d’effectuer
un tracé de n’importe quelle taille. Lorsque le module (la
procédure) est appelé, la taille spécifique requise doit être
indiquée. Pour l’algorithme 1.1, nous pouvons écrire :
Dessinercarré (10) et dessinercarré (20)
• Ce qui signifierait qu’un des carrés doit avoir un coté de
10cm et l’autre, un côté de 20cm.
Définition du module qui dessine un
carré d’une taille donnée
• Module dessinercarré (taille)
{dessine un carré dont le côté a une longueur "taille" en cm. Le carré est tracé dans le
sens inverse des aiguilles d’une montre en partant de la position actuelle de
l’automate. La première ligne est tracée selon l’orientation actuelle de l’automate.
L’automate revient à sa position et à son orientation initiale dès que le stylo est levé.}
Début
baissestylo
répéter 4 fois
déplacer (taille)
gauche (90)
lèvestylo
fin
Définitions : paramètre formel,
paramètre actuel
• La "taille" représente un paramètre formel
du module. Il est utilisé à l’intérieur du
module pour définir la taille du carré.
• Lorsque le module est appelé, le paramètre
actuel 10 (ou 20) donne une valeur spécifique
de la taille et détermine ainsi la grandeur du
carré.
Généralisation

Module nomdumodule (paramètres formels)

Corps du module

• On appelle un module de la manière suivante :

Nomdumodule (paramètres actuels)
Définition Algorithme modulaire
• Un algorithme construit autour d’un nombre
donné de modules est appelé un algorithme
modulaire.
• Chaque module est un composant en soi de
l’algorithme et agit comme un bloc dans la
construction de l’algorithme.
En utilisant le module dessinercarré comme nous l’avons
précédemment défini, nous pouvons affiner l’algorithme 1.1
de la manière suivante (algorithme 1.2):
Gauche (45)
Déplace (√50) {déplacer en A}
droite (135)
Dessinercarré (10) {dessiner le carré intérieur}
gauche (135)
Déplace (√50) {déplacer en B}
Droite (135)
Dessinercarré (20) {dessiner le carré extérieur}

• Il faut bien comprendre que le concepteur de l’algorithme 1.2 n’a pas

besoin de savoir comment le module dessinercarré travaille ; tout ce qu’il
doit connaître est l’effet de son exécution
Localisation

• Il arrive souvent que certaines variables ou certains objets (appelées

souvent variables auxiliaires) soient utilisées seulement dans une
suite donnée d’énoncés sans avoir la moindre signification en
dehors de ces énoncés.
• La procédure apparaît comme l’unité naturelle pour délimiter le
domaine de validité de ces objets locaux.
• Si un objet (une constante, une variable, une procédure, une
fonction ou un type) n’a de signification qu’à l’intérieur d’une
certaine partie du programme (procédure ou fonction), il est dit local.

• Les objets locaux sont alors déclarés dans l’en-tête de la procédure.

• Comme les procédures elles-mêmes peuvent être définies de façon
locale, on peut emboîter des déclarations de procédures.
Exemple: Déclaration de procédure
avec une déclaration de variable
locale
Procédure P
Var t : entier ;
Début t ← r mod q ;
r ← q;
q ← t
Fin ;
Définitions
• À l’intérieur de la procédure, on utilise deux sortes d’objets : les objets
locaux (ici, t) et les objets non locaux.
• Ces derniers sont déclarés dans l’environnement de la déclaration de
procédure.
• S’ils sont définis dans le programme principal, ils sont dits globaux, et s’ils
sont définis dans le langage (càd dans le contexte dans lequel le
programme est inclus), ils sont dits standards.
• Le domaine de validité des objets locaux est le texte de la procédure tout
entier. Ceci implique qu’après l’achèvement du processus décrit par une
procédure, l’espace de mémoire utilisé par les variables locales devient à
nouveau disponible et peut servir pour d’autres variables.
• Évidemment, lors d’un prochain appel de la même procédure, les valeurs
de ces variables locales seront à nouveau non définies, comme au moment
du premier appel.
Conflit de noms
• Quand on identifie les objets locaux, il est essentiel que l’on
puisse choisir les noms librement, sans se préoccuper de
l’environnement.
• Mais il peut se produire que la situation où l’identificateur
(disons x) choisi pour une variable locale dans la procédure P
est identique à celui d’un objet de l’environnement de P.
• Naturellement, cette situation n’est possible que si le x non
local n’a pas de signification pour P.
• Nous adopterons la convention de base selon laquelle, en cas
de conflit de noms, x à l’intérieur de P désignera la variable
locale, et x à l’extérieur de P l’objet non local.
Exemple :
Programme démofonct
var x1 , x2 : entier ;
fonction quitteoudouble (nombre : entier) : entier ;
const deux = 2 ;
var x2 : entier ;
début
x2 ← 0 ;
écrire (« dans quitteoudouble x2 vaut : » , x2) ;
si nombre ≤ 0 alors quitteoudouble ← 0
sinon quitteoudouble ← deux * nombre
fin ;
début {programme principal}
x2 ← 1 ;
écrire (« x2 = » , x2) ;
x1 ← quitteoudouble (10) ;
écrire (« x1 = », x1, « x2 = » , x2) ;
x1 ← quitteoudouble (-3) ;
écrire (« x1 = », x1 , « x2 = », x2)
fin.
• L’exécution de ce programme donne :
• x2 = 1
• Dans quitteoudouble x2 vaut : 0
• x1 = 20 x2 = 1
• La variable x2 n’est pas la même suivant qu’on se place ou non dans la
fonction.
• Il est commode de considérer le programme principal comme une
procédure sans nom. Son environnement est le langage de
programmation, et c’est là que sont définis tous les objets standards. Cette
idée explique aussi pourquoi l’on peut choisir des identificateurs sans
s’occuper des noms standards déjà définis. Aussi longtemps qu’un objet
standard n’est pas utilisé dans le programme, l’usage soit accidentel, soit
intentionnel de son identificateur comme nom d’objet local, n’a pas le
moindre effet défavorable.
Paramètres de procédure :
• Les paramètres formels ne sont qu’à l’intérieur du corps de
procédure et lui sont locaux. On précise les types des
paramètres dans l’en-tête de procédure. Le type du paramètre
actuel ou effectif est déterminé par le type du paramètre formel.
• En plus de l’indication du type de paramètre, il faut aussi
préciser la sorte de substitution désirée, car l’on peut substituer
soit la valeur actuelle soit l’identité de la variable ou de
l’expression effectives.
Substitution de paramètres
• On distingue trois sortes de substitution de paramètres :
On évalue le paramètre effectif, et on substitue la valeur résultante au
paramètre formel correspondant. C’est la substitution de valeur, et
c’est la plus connue.
Le paramètre effectif est une variable. On évalue les indices éventuels
et on substitue la variable ainsi identifiée à son correspondant formel.
C’est la substitution de variable ou par référence. Elle sert si le
paramètre représente un résultat de la procédure.
On substitue littéralement le paramètre effectif, sans faire d’évaluation.
C’est la substitution de nom qui n’apparaît que rarement dans les
applications pratiques.
Ex : L’algorithme suivant sert à montrer l’effet des trois sortes de
substitution de paramètres. Nous examinons les conséquences
de l’appel de procédure P ( T [ i ] ).
Algorithme Test
Var i : entier ;
T : tableau [1 .. 2] de entier ;
Procédure P ( x : entier ) ;
Début i ← i+1; x ← x+2
(1
Fin ;
)
Début {programme principal}
T [ 1 ] ← 10 ; T [ 2 ] ← 20 ; i ← 1 ;
P (T [ i ] )
Fin.
• 1er cas : substitution de valeur
x est une variable dont la valeur initiale est 10 ; la valeur finale de T est
(10, 20).
• 2ème cas : substitution de variable
x ≡T[1]
L’énoncé x ← x + 2 signifie maintenant T[1] ← T[1]+2
La valeur finale de T est (12, 20).
• 3ème cas : substitution de nom
x ≡T[i]
L’énoncé x ← x + 2 signifie maintenant T[i] ← T[i]+2
La valeur finale de T est (10, 22).
Distinction des différentes sortes de
substitution
• Pour distinguer les différentes sortes de substitution, nous
posons les différentes règles de notation suivantes :
La substitution de valeur est la forme la plus fréquente ; elle
est choisie à défaut d’indication explicite.
La substitution de variable est indiquée par le symbole var
en tête du ou des paramètres formels.
Une procédure ou une fonction sert de paramètre à une
procédure ou une fonction.
• Dans le cas de la substitution de valeur, le paramètre formel
représente une variable locale qui prend initialement comme
valeur le résultat de l’évaluation du paramètre effectif
correspondant.
• Après cette affectation initiale, cependant, il n’existe plus
aucune « connexion » entre les objets effectif et formel.
=> Deux règles générales
• qui gouvernent le choix des substitutions :
• si un paramètre est un argument mais non pas un résultat de la
procédure (ou de la fonction), c’est la substitution de valeur qui est
(d’ordinaire) appropriée.
• si un paramètre joue le rôle de résultat de la procédure, la substitution
de variable est nécessaire.
Pièges propres à la méthode de
substitution de variable
• Ils sont dus au fait que la même variable peut être rendue
accessible sous plus d’une identité. Cela est particulièrement
dangereux dans le cas de variables structurées telles que les
tableaux.
• Dans ces cas-là, le programmeur doit absolument se
conformer à la discipline de programmation énoncée par
l’importante règle suivante :
Tout paramètre variable doit être disjoint de tous les
autres paramètres !
• L’exemple suivant montre les dangers potentiels de la violation
de cette règle, sur une procédure simple de multiplication de
matrices.
Exemple
Type matrice = tableau [ 1 .. 2 , 1 .. 2 ] de entier ;
Procédure mult (var x , y , z : matrice) ;
Début
z [ 1, 1 ] ← x [ 1, 1 ] * y [ 1, 1 ] + x [ 1, 2 ] * y [ 2, 1 ] ;
z [ 1, 2 ] ← x [ 1, 1 ] * y [ 1, 2 ] + x [ 1, 2 ] * y [ 2, 2 ] ;
z [ 2, 1 ] ← x [ 2, 1 ] * y [ 1, 1 ] + x [ 2, 2 ] * y [ 2, 1 ] ;
z [ 2, 2 ] ← x [ 2, 1 ] * y [ 1, 2 ] + x [ 2, 2 ] * y [ 2, 2 ] ;
fin ;
• Etant données les matrices :

2 1 3 -1
• A= B=
-1 3 1 2
Etudier l’effet des énoncés de
procédures qui suivent :
• mult (A , B , C)
• mult (A , B , A)
• mult (A , B , B)
 7 0
• mult (A , B , C) donne C=
0 7
7 -5
• mult (A , B , A) donne A =
0 6
7 0
• mult (A , B , B) donne B =
-4 6
• Notons que l’on peut obtenir dans les
trois cas les résultats corrects obtenus
par 1. (mult (A , B , C)), si x et y sont
des paramètres à substitution de valeur.
Procédures et fonctions en
paramètres
• Une procédure ou une fonction F sert de paramètre à une
procédure ou fonction G si F doit être évaluée pendant
l’exécution de G, et que F sert à représenter des procédures
ou fonctions différentes lors d’appels différents de G.
• Les algorithmes qui calculent l’intégrale G d’une fonction F sont
des exemples bien connus.
Ex : Intégrale de Simpson
• Pour trouver une valeur approchée de l’intégrale
S = ∫ f(x) dx
nous calculons la somme d’un nombre fini de valeurs échantillons fi .
Sk = h/3 (f0 + 4 f1 + 2 f2 + 4 f3 + 2 f4 + … + 4 fn-3 + 2 fn-2 + 4 fn-1 + fn)
où fi = f (a + i * h) , h = (b – a)/n , et n = 2k.
• Le nombre de points échantillons est n + 1, et h est la distance
entre deux de ces points adjacents. La suite S1, S2, S3, … donne
alors une valeur approchée de l’intégrale S, qui converge si la
fonction a un comportement suffisamment bon (lisse) et si
l’arithmétique est supposée exacte.
• A chaque pas le nombre de points échantillons double.
• Naturellement, un programme bien conçu évitera
d’évaluer la fonction 2k fois à chaque k-ième pas. Au
lieu de cela, il réutilisera les valeurs fi calculées dans
les pas précédents. La somme Sk est, par conséquent,
représentée par les trois termes :
Sk = Sk(1) + Sk(2) + Sk(4)
qui représentent les sommes des points échantillons
ayant respectivement les poids 1, 2 et 4.
On peut les définir grâce aux relations de récurrence
suivantes (avec k > 1, et avec les valeurs initiales
suivantes) :

Sk(1) = ½ Sk-1(2)
Sk(2) = ½ Sk-1(2) + ¼ Sk-1(4)
Sk(4) = 4h/3 ( f (a + h) + f ( a + 3h) + … + f ( a + (n –
1)h ) )

S1(1) = h/3 ( f(a) + f(b) )

S1(2) = 0
S1(4) = 4h/3 f ( ( a + b)/2 )
Fonction Simpson ( a, b : réel ; fonction f : réel ) : réel ;
Const Epsilon = 0,01
Var i, n : entier ;
S, SS, S1, S2, S4, h : réel ;
{f(x) est une fonction à valeur réelle avec un unique paramètre à valeur réelle. La fonction doit être
bien définie dans l’intervalle a ≤ x ≤ b}
début n ← 2 ; h ← (b – a) * 0,5 ;
S 1 ← h * ( f(a) + f(b) ) ; S 2 ← 0 ;
S 4 ← 4 * h * f ( a + h ) ; S ← S 1 + S2 + S4 ;
Répéter SS ← S ; n ← 2 * n ; h ← h/2 ;
S 1 ← 0,5 * S 2 ; S2 ← 0,5 * S2 + 0,25 * S 4 ;
S4 ← 0 ; i ← 1 ;
Répéter S4 ← S4 + f( a + i * h) ; i ← i + 2 ;
Jusqu’à i > n;
S4 ← 4 * h * S 4 ; S ← S1 + S2 + S4
Jusqu’à abs ( S – SS ) < epsilon ;
Simpson ← S/3
Fin;
•
• Cependant, seul un identificateur de fonction peut apparaître comme
troisième paramètre effectif. Par exemple, pour calculer :

u = ∫ dx / ( a2 cos2 x + b2 sin2 x ) ½

à l’aide de la fonction Simpson, il faut déclarer explicitement une autre

fonction F :

fonction F ( x : réel ) : réel ;

début
F ← 1 / SQRT ( SQR ( a * cos (x)) + SQR ( b * sin (x)))
fin ;
C’est seulement que l’on peut exprimer ceci :
u ← Simpson ( 0 , Pi /2 , F )
La récursivité (ou
récursion)
Définition et exemple
• Calcul de la factorielle de N
Programme Factorielle ;
Var I, N, P : entier ;
Début
lire (N) ; P ← 1 ;
Si N = 0 alors écrire (P) ;
Sinon pour I ← 1 à N faire
P ← P * I
FinPour
Ecrire (P)
Fin.
• Une approche différente consiste à utiliser le fait que la
factorielle de N est simplement le produit de N par la factorielle
de (N – 1)
Càd,
Factorielle (N) = N * factorielle (N – 1)
• Cela est vrai pour tout N plus grand que 1.
• De plus, factorielle (0) = 1.
Fonction factorielle ( n : 0 .. 32767) : entier ;
Début
Si n = 0 alors factorielle ← 1
Sinon factorielle ← n * factorielle ( n – 1 )
Fin ;
 La dernière ligne du programme (sinon …) pré suppose que le programme
doit être exécuté à nouveau, mais avec le paramètre actuel moins 1. La
figure suivante illustre l’exécution du programme lorsque N = 3.

• Factorielle (3)
Si 3 = 0 alors …
sinon fact ← 3 * fact (2)
si 2 = 0 alors …
sinon fact ← 2 * fact (1)
si 1 = 0 alors …
sinon fact ←1 *fact(0)
si 0 = 0 alors fact ← 1
• L’algorithme utilisé pour calculer la factorielle de N est
exprimé en terme d’un algorithme pour calculer la
factorielle de (N – 1). C’est pourquoi on peut
considérer que l’algorithme est exprimé en référence à
lui-même, son entrée N devant être remplacée par (N –
1).
• Le terme utilisé pour cette forme d’expression est la
récursion : un algorithme récursif est un algorithme qui
s’appelle lui-même.
• On évite le mouvement apparent de retour sur soi-même de la
récursion en s’assurant que l’entrée des appels récursifs
successifs devient progressivement plus « simple ». On doit
alors rencontrer un cas limite dans lequel l’entrée est si
« simple » que le traitement peut-être effectué sans qu’il n’ait
plus à s’appeler lui-même.
• Le cas limite peut être considéré comme une issue de secours
qui assure en tout état de cause la fin de l’exécution. Tout
algorithme récursif doit comporter une issue de secours et
l’entrée doit être simplifiée progressivement jusqu’à pouvoir
atteindre cette issue de secours.
La récursivité en arbre
• Un autre modèle courant de calcul est appelé récursivité en
arbre. Prenons pour exemple la suite de Fibonacci où chaque
nombre est la somme des deux précédents :
• 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21, …
• En général les nombres de Fibonacci peuvent être définis par
la règle suivante :

0 si n = 0
Fib (n) = 1 si n = 1
Fib (n – 1) + Fib (n – 2) autrement
• Fonction fib (n : 0 .. 32 767) : entier ;
Début
Si n = 0 alors fib ← 0
Sinon
si n = 1 alors fib ← 1
Sinon fib ← fib (n – 1) + fib (n – 2)
Fin;