ALGORITHMIQUE II

El Maati CHABBAR
Département d’Informatique
Faculté des Science –Rabat-

FSR Dé[Link]. 15
1
 PLAN DU COURS
2

OBJECTIF: Conception des algorithmes corrects et efficaces

PLAN
RAPPELS : NOTATIONS ALGORITHMIQUES
COMPLEXITE
ALGORITHMES ITERATIFS DE TRIS
RECURSIVITE
DIVISER POUR RESOUDRE
PREUVE D’ALGORITHMES

FSR Dé[Link]. 15
 Notations algorithmiques

Un type est un ensemble de valeurs sur lesquelles on définit

des opérations.
• Types de base :
✓Entier : Opérateurs arithmétiques +, -, *, div, mod
✓ Réel : Opérateurs arithmétiques +, -, *, /
✓ Booléen : Opérateurs logiques et, ou, non
✓ Caractère : constante (lettre imprimable) entre
apostrophe.
- Les opérateurs relationnels permettant de faire des
comparaisons: <, ≤, =, >, ≥, ≠
Le Résultat de la comparaison est une valeur booléenne.
FSR Dé[Link]. 15
 Notations algorithmiques

Une variable possède :

- un nom
- une valeur
- un type
(la valeur d’une variable peut changer au cours de
l’exécution)
Déclaration : <variable> : <type>

Une expression, pour un type, est soit une constante,

soit une variable, soit constituée à l’aide de constantes,
de variables, de parenthèses et des opérateurs

FSR Dé[Link]. 15
 Notations algorithmiques

INSTRUCTIONS
Affectation : <variable> := <expression>

Condition : si <condition> alors

action
fsi
ou :
si <condition> alors
action1
sinon
action 2
fsi
( condition est une expression à valeur booléenne;
action est une instruction ou un bloc d’instructions séparées par ;)
FSR Dé[Link]. 15
 Notations algorithmiques

Itération
• boucle Pour

pour <variable> := <initiale> à <final> faire

action
fpour

(Où initiale et finale sont des expressions de même type que celui de
la variable contrôlant la boucle, le type peut être entier, caractère
ou énuméré)

Remarque: la boucle pour affecte la valeur de initiale à variable et

compare cette valeur à celle de finale avant d’exécuter action.

FSR Dé[Link]. 15
 Notations algorithmiques

Exemple: calcul de 1+2+…+n (n entier≥ 1 en C

fixé)
Programme somme_des_n_premiersTermes
// partie déclaration main ( ) {
n : entier; s : entier; i : entier; (ou n, i, s : entier) // déclaration des variables
Début
int i, n, s;
// Lecture des données // lecture des données
Écrire (" n = ? " ); lire(n); prinf(" n = ? "); scanf(" %d" , &n);
// calcul de la somme
// calcul de la somme
s := 0; s = 0;
pour i := 1 à n faire for(i = 1; i <=n; i++) s = s + i;
s := s + i;
// affichage
fpour; printf(" 1+2+…+ %d = %d \n" , n, s)
// affichage du résultat }
écrire("1+ 2 + … + n = ", s);
fin

FSR Dé[Link]. 15
 Notations algorithmiques

Itération
• boucle tantque • boucle répéter

tantque < condition> faire répéter

action action
ftantque jusque < condition>

Remarques:
- Condition est une expression à valeur booléenne, cette expression
doit être modifiée dans le corps de la boucle (dans action).
- La boucle pour peut être traduite en boucle tantque (ou en répéter)
mais l’inverse n’est pas toujours vrai.

FSR Dé[Link]. 15
 Notations algorithmiques

Programme somme_des_n_premiersTermes en C
// partie déclaration
n : entier; s : entier; i : entier; (ou n, i, s : entier) main ( ) {
Début // déclaration des variables
// Lecture des données int i, n, s;
Écrire (" n = ? " ); lire(n); // lecture des données
// calcul de la somme prinf(" n = ? "); scanf(" %d" , &n);
s := 0; // calcul de la somme
i := 1; s = 0;
tantque i <= n faire i = 1;
s := s + i; while (i <= n) {
i := i + 1; s = s + i;
ftantque; i = i + 1;
// affichage du résultat }
écrire("1+ 2 + … + n = ", s); // affichage
fin printf(" 1+2+…+ %d = %d \n" , n, s)
}

FSR Dé[Link]. 15
 Notations algorithmiques

10

Algorithme

algorithme

Cheminement à suivre :
analyse codification
Problème Algorithme programme
FSR Dé[Link]. 15
 Notations algorithmiques

11

Conception structurée des algorithmes

Fonctions
- Une fonction est un sous algorithme (sous programme) qui, à partir
de données, retourne un seul type de résultat.
- Une fonction
• possède un nom
• communique avec l’extérieur par le biais des paramètres
• retourne un résultat par l’instruction retourner(expression)

FSR Dé[Link]. 15
 Notations algorithmiques

12

Schéma d’une fonction :

fonction <nom de la fonction>(Liste des paramètres) : <type du résultat>
// déclaration des variables locales
début
// corps de la fonction qui contient l’instruction retourner
fin

o Les paramètres de la définition d’une fonction (appelés formels) sont :

• typés
• séparés par ‘,’ s’il y en a plusieurs
o Les paramètres formels sont utilisés pour ne pas lire les données dans une
fonction.
o Les variables déclarées dans une fonctions (y compris les paramètres formels)
sont appelées variables locales.

FSR Dé[Link]. 15
 Notations algorithmiques

13

Exemple: factoriel n en n! en C :
pseudo code:
Fonction fact(n : entier) : entier unsigned int fact (unsigned int n) {
m, i : entier; unsigned int i, m;
début m = 1;
m := 1; for (i = 2; i<= n; i++)
pour i :=2 à n faire m = m * i;
m := m * i; return m;
fpour }
retourner(m);
fin
FSR Dé[Link]. 15
 Notations algorithmiques

14

o L’appel d’une fonction est utilisé dans une instruction sous la forme :
<nom de la fonction> (liste des paramètres effectifs)
Les paramètres formels et effectifs doivent correspondre en nombre
et en type
Lors d’un appel :
• les paramètres formels reçoivent les valeurs des paramètres
effectifs correspondant
• le corps de la fonction est exécuté jusqu’au premier retourner
rencontré
• l’exécution se poursuit (à l’dresse de retour) dans la fonction
appelante.
o Remarque: le type de retour d’une fonction peut être vide, et dans
ce cas on écrit retourner() ou pas d’instruction retourner;

FSR Dé[Link]. 15
 Notations algorithmiques

15

Exemple: calcul de 1+2+…+n (n Fonction pour calculer la somme

entier≥ 1 fixé) 1+2+…+m
Programme somme_des_n_premiersTermes
// partie déclaration Fonction sommeArith ( m : entier) : entier
n : entier; r : entier; (ou n, r : entier) i, s : entier;
Début début
// Lecture des données s := 0;
Écrire (" n = ? " ); lire(n); pour i := 1 à m faire
// appel et utilisation de la fonction s := s + i;
sommeArith fpour;
r := sommeArith(n); retourner(s);
// affichage du résultat fin
écrire("1+ 2 + … + n = ", r);
fin

FSR Dé[Link]. 15
 Notations algorithmiques

16

o Deux types de passages des paramètres :

• Passage par valeur: la fonction travaille sur une copie du

paramètre effectif transmis; i.e. la valeur du paramètre effectif
n’est pas modifiée après l’appel de la fonction.

• Passage par adresse (ou par référence):

- l’identificateur du paramètre formel est précédé par le mot ref.
- la fonction travaille directement sur l’identificateur du paramètre
effectif; i.e. toute modification sur le formel entraine la même
modification sur le paramètre effectif correspondant.

FSR Dé[Link]. 15
 Notations algorithmiques

17

Passage par valeur Passage par réference

Fonction échnger(x: réel, y : réel) : vide Fonction echnger(ref x: réel, ref y : réel) : vide
z : réel; z : réel;
début début
z := x; z := x;
x := y; x := y;
y := z; y := z;
fin fin

Fonction appelante() Fonction appelante()

a, b : réel; a, b : réel;
début début
a := 2; b:= 7; a := 2; b:= 7;
échanger(a,b); échanger(a,b);
écrire( a = , a); écrire( a = , a);
écrire( b = , b); écrire( b = , b);
fin fin
Les résultas affichés par la fonction appelante : Les résultas affichés par la fonction appelante :
a=2 b=7 a=7 b=2

FSR Dé[Link]. 15
 Notations algorithmiques

18

Un algorithme se comporte comme une fonction sauf

que l’on ne s’occupe pas des déclarations des variables
ni de leurs types.
Schéma d’un algorithme :
Algorithme <nom de l’algorithme>
Données : // les variables qui sont des données de l’algo.
<nom de l’algorithme>(Liste des paramètres) Résultat(s): // variable(s) contenant le(s) résultat(s)

début début
//bloc d’instructions Ou //bloc d’instructions
fin //ne contenant pas retourner
fin

On omet la partie déclaration des variables locales en adoptant la

règle: les variables simples sont en minuscule et les tableaux en
majuscule.

FSR Dé[Link]. 15
 Notations algorithmiques

19

Algorithme pour calculer n!

factoriel(n)
// n ≥ 0
début
m := 1; i := 1;
tantque i < n faire
i := i + 1;
m := m * i;
ftantque
retourner(m);
fin

FSR Dé[Link]. 15
 TABLEAUX STATIQUES
20

TABLEAUX
Un tableau est utilisé pour représenter une suite d’éléments de même type
( T = (t1,t2,…,tn)).
Déclaration d’un tableau (à un dimension):
<nom du tableau> : tableau [1 .. max] de <type des éléments>
(exemple T : tableau [1..20] de réel)
où : - max est une constante entière (positive)
- le type des éléments est quelconque (de base ou déclaré).

• La taille (ou longueur) d’un tableau est le nombre d’éléments du tableau;

elle est toujours inférieure ou égale à max.

• les tableaux, en algorithmique, commencent à l’indice 1(en C et en java,

ils commencent à l’indice 0)

FSR Dé[Link]. 15
 TABLEAUX STATIQUES
21

Opérations (de base) sur les tableaux:

Accès à un élément du tableau :
<nom du tableau> [<indice>]
(indice est une expression de type entier)
Parcours : (on utilise un indice et une boucle pour ou tant que)
(exemple :
pour i=1 à n faire //n est le nombre d’éléments du tableau T
traiter( T[i]) // traiter() est une fonction ou algorithme à définir
fpour;
Recherche d’un élément dans un tableau
Insertion d’un élément
Suppression d’un élément

FSR Dé[Link]. 15
 TABLEAUX STATIQUES
22

o Exemple : recherche de la position d’un élément dans un tableau de réels.

fonction localiser(T: tableau[1..max]de réel, n : entier, val :réel) : entier

i : entier;
trouve : booléen;
début
i := 1; trouve := faux;
tantque (i ≤ n) et (non trouve) faire
si (T[i] = val) alors
trouve := vrai;
sinon i := i + 1;
fsi;
ftantque;
si (trouve) alors retourner(i)
sinon retourner(0);
fsi
fin

FSR Dé[Link]. 15
 [Link]

23

insertion d’élément x dans un tableau T à n éléments à la position p.

Fonction inserer(T : tableau[1..max] de réel, ref n : entier, x : réel, p : entier) : vide
// 1 ≤p ≤ n
i : entier;
début
i := n;
tantque i ≥ p faire
T[i+1] := T[i];
i := i – 1;
ftantque
T[p] := x;
n := n + 1;
fin

FSR Dé[Link]. 15
 [Link]

24

Suppression d’une valeur d’un tableau T, qui se trouve à la position

p.
Fonction supprimer(T : tableau[1.. max] de réel, ref n : entier, p : entier) : vide
i : entier;
début
i := p;
tantque i < n faire
T[i] := T[i+1];
i := i + 1;
ftantque;
n := n – 1;
fin

FSR Dé[Link]. 15
 [Link]

25

o Remarques :
Le nom du tableau, dans une liste de paramètres
formels, est une référence.
(en C, l’adresse de T[i], notée T + i, est calculée:
adresse(T[i]) = adresse(T[0]) + sizeof(<type des éléments>) * i)

L’insertion (resp. suppression) d’un élément à un

indice i, nécessite un décalage des (n- i +1)
derniers éléments d’une position à droite (resp. à
gauche)
FSR Dé[Link]. 15
 STRUCTURE (ENREGISTREMENT)
26

Structures (ou enregistrements)

Le type structure est utilisé pour représenter une suite d’éléments pas
nécessairement de même type, chaque élément est appelé champs.
Déclaration d’un type structure:
<nom de type structure> = structure
<variable_champs1> : <type_champs1>;
<variable_champs2> : <type_champs2>;
.
.
fstructure

Déclaration d’une variable de type structure:

<variable_structure> : <nom de type structure>

FSR Dé[Link]. 15
 STRUCTURE (ENREGISTREMENT)
27

Par analogie au type struct de C:

Déclaration :
struct <nom de la structure> {
<type_champs1> <variable_champs1>
<type_champs2> <variable_champs2>
.
.
}
Déclaration d’une variable de type structure:
struct <nom de la structure> <variable>

• Ou avec la définition de type : typedef

typedef struct <nom de la structure> <type_structure>;
Déclaration d’une variable :
<type_structure> <variable>

FSR Dé[Link]. 15
 STRUCTURE (ENREGISTREMENT)
28

Exemples : En C :
Adresse = structure struct adresse {
numero_rue : entier; int numero_rue;
nom_rue : tableau[1..20] de caractère; char[20] nom_rue;
code_postal : entier; int code_postal;
fstructure }
typedef struct adresse Adresse;
Point = structure
abscisse : réel; typedef struct point {
ordonnee : réel; float abscisse, ordonnee;
fstructure }Point;

Déclaration des variables: //Déclaration des variables:

adr : Adresse; Adresse adr;
p : Point Point p;

FSR Dé[Link]. 15
 STRUCTURE (ENREGISTREMENT)
29

Opération sur les structures :

Accès à un champs :
<variable de type structure>. <variable_champs>
(ex: [Link] désigne l’abscisse du poin p)
Affectation :
<variable_type_structure> := <variable_type_structure>
(L’affectation se fait champs par champs)

Exemple : manipulation des complexes

FSR Dé[Link]. 15
 STRUCTURE (ENREGISTREMENT)
30

Déclaration de type complexe: Déclaration de type complexe en C:

Complexe = structure typedef struct complexe {
p_reel, p_imag : réel; double p_reel, p_imag ;
fstructure } Complexe;

fonction plus(z1 : Complexe, z2 : Complexe) : Complexe Complexe plus(Complexe z1,Complexe z2){

z : Complexe; Complexe z;
debut z.p_reel = z1.p_reel + z2.p_reel;
z.p_reel := z1.p_reel + z2.p_reel; z.p_imag = z1.p_imag + z2.p_imag;
z.p_imag := z1.p_imag + z2.p_imag; retun z;
retourner(z); }
fin

FSR Dé[Link]. 15
 ALGORITHMIQUE II

NOTION DE COMPLEXITE

1 SMI AlgoII
 Complexité

Comment choisir entre différents algorithmes pour

résoudre un même problème?

Plusieurs critères de choix :

Exactitude
Simplicité
Efficacité (but de ce chapitre)

SMI AlgoII
 Complexité

L’évaluation de la complexité d’un algorithme se fait

par l’analyse relative à deux ressources de l’ordinateur:
o Le temps de calcul

o L’espace mémoire, utilisé par un programme, pour

transformer les données du problème en un ensemble
de résultats.
L’analyse de la complexité consiste à mesurer ces deux
grandeurs pour choisir l’algorithme le mieux adapté
pour résoudre un problème.(le plus rapide, le moins
gourment en place mémoire)
On ne s’intéresse, ici, qu’à la complexité temporelle c.à d. qu’au temps de calcul
(par opposition à la complexité spatiale) SMI AlgoII
 Complexité

Le temps d’exécution est difficile à prévoir, il peut

être affecté par plusieurs facteurs:
la machine
la traduction (interprétation, compilation)
l’environnement (partagé ou non)
L’habileté du programmeur
Structures de données utilisées

SMI AlgoII
 Complexité

Pour pallier à ces problèmes, une notion de

complexité plus simple, mais efficace, a été définie
pour un modèle de machine . Elle consiste à
compter les instructions de base exécutées par
l’algorithme. Elle est exprimée en fonction de la
taille du problème à résoudre.
Une instruction de base (ou élémentaire) est soit:
une affectation, un test, une addition, une
multiplication, modulo, ou partie entière.

SMI AlgoII
 Complexité

La complexité dépend de la taille des données de l’algorithme.

Exemples :
Recherche d’une valeur dans un tableau
→ taille (= nombre d’éléments) du tableau)
Produit de deux matrices
→ dimension des matrices
Recherche d’un mot dans un texte
→ longueur du mot et celle du texte
On note généralement:
n la taille de données, T(n) le temps (ou le cout) de l’algorithme.
T(n) est une fonction de IN dans IR+

SMI AlgoII
 Complexité

Dans certains cas, la complexité ne dépend pas

seulement de la taille de la donnée du problème
mais aussi de la donnée elle-même.
Toutes les données de même taille ne génèrent
pas nécessairement le même temps d’exécution.
→ (Ex. la recherche d’une valeur dans un tableau
dépend de la position de cette valeur dans le
tableau)

SMI AlgoII
 Complexité

Une donnée particulière d’un algorithme est appelée instance

du problème.
On distingue trois mesures de complexité:
1. Complexité dans le meilleur cas
TMin (n) = min {T(d) ; d une donnée de taille n }
2. Complexité dans le pire cas
TMx (n) = max {T(d) ; d une donnée de taille n }
3. dans la cas moyen
TMOY (n) = ∑ p(d).T (d)
d de taille n
p(d) : probabilité d'avoir la donnée d

TMIN (n) ≤ TMOY (n) ≤ TMAX (n)

SMI AlgoII
 Complexité

Exemple. Complexité de la Cas le plus favorable. x est le

recherche d’un élément x dans un premier élément du tableau:
tableau A à n valeurs.
Tmin(n) = 1a + 3t
i := 1
tantque (i ≤n) et (A[i] ≠x) faire Pire des cas. x n’est pas dans le
i := i+1; tableau:
ftantque Tmax(n) = (n+1)a +(2n+2)t +nd
si i >n alors retourner(faux);
sinon retourner(vrai);
fsi; En moyenne :
On note par:
a : le cout d’une affectation
t : cout d’un test
d : cout d’une addition

SMI AlgoII
 Complexité

10

Complexité en moyenne:
On note par :
Di (1 ≤i≤ n) : ensemble de données (de taille n) où x est
présent à la ieme position
Dn+1 : ensemble de données où x n’est pas présent
On suppose que la probabilité de présence de x dans une
donnée est q. De plus, dans le cas où x est présent, on
suppose que sa probabilité de présence dans l’une des
positions est de 1/n
On a :
p(Di) = q/n , T(Di) = i a +(2i+1)t + (i-1)d ; (1 ≤i≤ n)
p( Dn+1) = 1 – q , T(Dn+1)=Tmax = (n+1)a+(2n+2)t+nd

SMI AlgoII
 Complexité
11

p(Di) = q/n , T(Di) = i a +(2i+1)t + (i-1)d ; (1 ≤i≤ n)

p( Dn+1) = 1 – q , T(Dn+1)=Tmax(n) = (n+1)a+(2n+2)t+nd

TMOY (n) = ∑ p(d).T (d)

d de taille n
p(d) : probabilité d'avoir la donnée d

Cas où q=1, i.e. x est toujours présent:

On remarque que la complexité de cet algo. est
de la forme: αn + β, αet βson des constates SMI AlgoII
 Complexité asymptotique
12
Comportement de T(n)
Pour mesurer la complexité d’un algorithme, il ne s’agit pas de faire un décompte exact du
nombre d’opérations T(n), mais plutôt de donner un ordre de grandeur de ce nombre pour n
assez grand.
Notation de Landau
"grand O"
T(n) = O(f(n)) ssi
∃ c > 0 ∃ n0 > 0 ∀ n > n0 T(n) ≤ c.f(n)
"grand oméga"
T(n) = Ω (f(n)) ssi
∃ c > 0 ∃ n0 > 0 ∀ n > n0 T(n) ≥ c.f(n)
"grand théta"
T(n) = Θ(f(n)) ssi
∃ c1 > 0 ∃ c2 > 0 ∃ n0 > 0 ∀ n > n0 c1f(n)≤ T(n)≤ c2f(n)

Remarque: les constantes c, c1, c2 et n0 sont indépendantes de n

SMI AlgoII
 Complexité

13

D’une manière générale, f : IR → IR

f(x) = O(g(x)) s’il existe un voisinage V de x0 et une constante k>0 tels
que |f(x)|≤ k|g(x)| , (x ∈ V)
- Si la fonction g ne s’annule pas, il revient au même de dire que le
rapport est borné pour x ∈ V.
-Exemple: au voisinage de 0, on a:
x2 = O(x), ln(1+x) = O(x)
- Au voisinage de l’infini (comme pour le cas de la complexité), il
existe a>0 (V = ]a, + ∞ [) et k>0 t.q
|f(x)|≤ k|g(x)| , ∀x > a
et on dit que f est dominée asymptotiquement par g.
(Au voisinage de +∞ , on a: x = O(x2), ln x = O(x))

SMI AlgoII
 Complexité

14

Remarques
1. f = O(g) ⇔ le quotient est bornée au voisinage
de l’infini.
2.

3. si a = 1, on écrit f ∼ g et on a f = Θ(g).
4. f = Θ(g) ne signifie pas que le quotient f(x)/g(x)
tend vers une limite (1 en particulier).
Exemple. f(x) = x(2+sin x). On a x ≤ f(x) ≤ 3x
∀x>0, donc f(x) = Θ(x). En revanche, le quotient
f(x)/x ne tend vers aucune limite lorsque x → +∞

SMI AlgoII
 Complexité

15

Abus de notation:
On a par définition:
O(f) = {g: IN → IR / ∃ c > 0 ∃ n0 > 0 g(n) ≤ c.f(n) , ∀ n > n0}
Ω(f) = {g: IN → IR / ∃ c > 0 ∃ n0 > 0 g(n) ≥ c.f(n) , ∀ n > n0}
Θ (f) = O(f) ∩ Ω(f)

La difficulté, dans la familiarisation avec ces concepts, provient de la convention

de notation (de Landau) qui veut que l’on écrive :
g = O(f), ou encore g(n) = O(f(n)) au lieu de g ∈ O(f)
De manière analogue, on écrit O(f) = O(g) lorsque O(f)⊂ O(g)

(il en est de même pour les notations Ω ou Θ)

SMI AlgoII
 Complexité

16

Exemple. Soit la fonction T(n) = ½ n2 + 3n

T(n) = Ω(n) ( n0 = 1, c = ½)
T(n) = Θ(n2) (n0 = 1, c1 = ½, c2 = 4)
T(n) = O(n3) (n0 = 1, c = 4)
T(n) ≠ O(n)
Supposons que T(n) = O(n)
∃ c >0, ∃n0>0 : ½ n2 +3n ≤ cn ∀n ≥n0
donc c ≥ ½ n , contradiction. (la constante c ne peut dépendre de n)
Remarques
1. Si T(n) est un polynôme de degré k alors T(n) = Θ(nk)
2. O(nk) ⊂ O(nk+1) ∀ K ≥ 0 (idem pour Θ)
3. Θ(f(n)) ⊂ O(f(n)) pour toute fonction f positive
4. O(1) utilisé pour signifier « en temps constant »

SMI AlgoII
 Complexité

17

Remarques pratiques:
Le cas le plus défavorable est souvent utilisé pour
analyser un algorithme.
La notation O donne une borne supérieure de la
complexité pour toutes les données de même
taille(suffisamment grande). Elle est utilisée pour évaluer un
algorithme dans le cas le plus défavorable.
T(n) ≤ cf(n) signifie que le nombre d’opérations ne peut
dépasser cf(n) itérations, pour n’importe quelle donnée de
longueur n.
Pour évaluer la complexité d’un algorithme, on cherche un
majorant du nombre d’opérations les plus dominantes.
Dans les notations asymptotiques, on ignore les constantes.
L’algorithme de recherche dans un tableau à n éléments, cité précédemment, est en O(n)
SMI AlgoII
 Complexité

18

Ordre de grandeur courant

O(1) : complexité constante

O(log(n)) : complexité logarithmique
O(n) : complexité linéaire
O(n2) : complexité quadratique
O(n3) : complexité cubique
O(2n) : complexité exponentielle

SMI AlgoII
 Complexité

19

Exemples de temps d’exécution en fonction de la

taille de la donnée et de la complexité de
l’algorithme.
On suppose que l’ordinateur utilisé peut effectuer
106 opérations à la seconde (une opération est de
l’ordre de la µs)

SMI AlgoII
 Complexité

20

. \T(n)
n log n n n log n n2 2n

10 3 µs 10 µs 30 µs 100 µs 1000µs

100 7 µs 100 µs 700 µs 1/100 s 1014

siècles
1000 10 µs 1000µs 1/100µs 1 s astrono
mique
10000 13 µs 1/100µs 1/7 s 1,7 mn astrono
mique
100000 17 µs 1/10 s 2s 2,8 h astrono
SMI AlgoII mique
 Complexité

21

Un algorithme est dit polynomial si sa complexité est en O(np ).

Un algorithme est dit praticable s’il est polynomial (p ≤ 3).
Les algorithmes polynomiaux où p > 3 sont considérés comme très lents
(un algorithme polynomial de l’ordre de n5 prendrait environ 30 ans pour n=1000)
Un algorithme est dit exponentiel si sa complexité est supérieure à tout polynôme.

Deux grandes classes de la complexité :

- ℙ classe des algorithmes polynomiaux
- ℵ ℙ classe des algorithmes « Non déterministe polynomiale »
On a :

(O(log n) ⊂ O(n) ⊂ O(n log n) ⊂ O(n2) ⊂ O(n3) ⊂ O(2n) ⊂ O(en) ⊂ O(n!)

SMI AlgoII
 Complexité

22

Propriétés
En utilisant la notation de Landau (pour les fonctions de IN dans IR+ ), on a :
1. f + O(g) = {f + h / h ∈ O(g)}
(h = f + O(g) ⇔ h – f ∈ O(g).
f O(g) = {f h / h ∈ O(g)}
2. f = O(f)
3. f = O(g), g = O(h) ⇒ f = O(h)
4. c O(f) = O(c f) = O(f) ( c>0)
5. O(f) + O(g) = O(f + g) = O(max(f, g))
6. O(f) + O(f) = O(f)
7. O(f) O(g) = O(fg)
8. f = O(g) ⇔ g = Ω (f)

SMI AlgoII
 Complexité

23

Calcul de la complexité: règles pratiques

1. la complexité d’une suite d’instructions est la
somme des complexités de chacune d’elles.
2. Les opérations élémentaires telle que l’affectation,
test, accès à un tableau, opérations logiques et
arithmétiques, lecture ou écriture d’une variable
simple ... etc, sont en O(1).
3. T(si C alors A1 sinon A2) = max(T(C),max(T(A1),T(A2)))

SMI AlgoII
 Complexité

24

4. T(pour i:=e1 à e2 faire Ai fpour) =

( si Ai ne contient pas de boucle dépendante de i
et si Ai est de complexité O(m) alors la complexité
de cette boucle « pour » est O((e2 – e1 + 1)m). )
5. La difficulté, pour la boucle tantque, est de
déterminer le nombre d’itération Nb_iter (ou
donner une borne supérieure de ce nombre)
T(tantque C faire A ftantque) = O(Nb_iter x (T(C) + T(A))

SMI AlgoII
 Complexité

25

Exemples
1. Calcul de la somme 1+2+…+n
S:=0; //O( 1)
Pour i:=1 à n faire
s:= s + i; // O(1)
O(1) + O(n) = O(n)
O(n)

fpour;

T(n) = O(n)
SMI AlgoII
 Complexité

26

2. Calcul de :
pour i := 1 à n faire
s := 0; // O(1)
pour j := 1 à i faire
s := s + j; // O(1) O(i) O(1)+O(i)+O(1)=O(i)

fpour; = O(n2)

T[i] := s; //O(1)
fpour;
T(n) = O(n2)
SMI AlgoII
 Complexité

27

3. Analyse de l’algo. Suivant : cpt = 1 + le nombre d’itérations

Le nombre d’itérations = nombre
Donnée n; (n>0) de division de n par 2.
Résultat cpt; Soit p ce nombre.
- si n est une puissance de 2, i.e.
n = 2p alors p=log2(n).
début
- p vérifie: 2p ≤ n < 2 p+1
cpt := 1;
p ≤ log2(n)< p+1 ⇒p=E(log2(n))
tantque n ≥ 2 faire
cpt = 1 + E(log2(n)), cette
n := n div 2; expression de cpt correspond au
cpt := cpt +1; nombre de bits nécessaires pour
ftantque représenter l’entier n.
fin T(n) = O(log(n))
Que calcule cet algo?
Quelle est sa complexité?

SMI AlgoII
ALGORITHMIQUE II
TRIS ITERATIFS

SMI ALGOII 1
2

Le problème:
Etant donnée une suite de n nombres (a1,a2,…, an), on
cherche une permutation (arrangement) des éléments
de cette suite (a’1,a’2,…, a’n) telle que a’1≤a’2≤…≤a’n.
♦ A partir de la suite (7,1,2,6), un algorithme de tri
donne comme résultat la suite (1,2,6,7).
On se limite aux nombres entiers rangés dans un
tableau A à n éléments.
Dans le cas où les éléments sont des collections de
données (enregistrement), on trie le tableau suivant une
clé (champ de l’enregistrement).

SMI ALGOII
3

Tri par sélection:

Algorithme:
pour i=1 à n-1 faire
-chercher le 1ème minimum, Ak , de {Ai+1,…,An}
(K est l’indice de min{Ai+1,…,An} dans le tableau A)
- échanger Ai et Ak
L’algorithme fonctionne selon le schéma suivant:
échange
A
trié
1 i SMI ALGOII k n
• Exemple

3 2 9 5 4
7

3 7 9 5 4
2

3 7 9 5 4
2

3 4 9 5 7
2

3 4 5 9 7
2

3 4 5 7 9
2

SMI ALGOII 4
 Analyse du tri par sélection
5

Algorithme: La boucle j détermine le iè minimum;

Tri_selection(A,n) elle tourne n-i fois (au maximum) pour
faire (n-i) tests d’éléments.
début
Les échanges de A[k] et A[i]
pour i := 1 à n-1 faire
demandent 3 opérations.
//Recherche de min{Ai, …, An} = Ak
La complexité du corps de la boucle j
k := i; est de la forme
pour j:=i+1 à n faire
a(n-i)+b, donc en O(n-i) ( i=1, …, n-1).
si A[j] < A[k] alors k:=j;
La complexité de l’algorithme est de
fsi;
l’ordre de:
fpour
// échange de Ak et Ai
temp := A[k];
A[k] := A[i];
A[i] := temp;
fpour;
fin

T(n) = O(n2)
SMI ALGOII
 TRI par ISERTION
6

Algorithme:
Pour i := 2 à n faire
- on insère A[i], à sa place, dans le sous-tableau
A[1..i-1]
(On cherche le 1er élément ≤ A[i] parmi {A[i-1],…,A[1]} en
décalant d’une position à droite)
L’algorithme fonctionne selon le schéma suivant:

A[i]
A
triétrié
1 i-1 i SMI ALGOII
 3
• exemple
>
7 3 2 5

7 7 2 5
i=2

3 7 2 5

3 7 2 5

3 7 7 5

i=3
3 3 7 5

2 3 7 5

2 3 7 5

i=4
2 3 SMI ALGOII 5 7 7
 Analyse du tri par insertion
8

Algorithme: La boucle j tourne, dans le

Tri_Insersion(A,n) pire des cas, (i-1) fois
début (i-1 comparaisons et i-1
pour i := 2 à n faire décalages)
cle := A[i]; La complexité du corps de la
boucle i est de la forme
j := i-1;
Tantque (j≥1) et (cle<A[j]) faire a(i-1)+b, pour i=2,…,n.
A[j+1] := A[j]; La complexité de l’algorithme:
j := j-1;
ftantque
A[j+1] = cle;
fpour T(n) = O(n2)
fin

SMI ALGOII
 Tri à Bulles
9

On dit qu’on a une inversion s’il existe (i,j) tels que i<j et
ai > aj
(a1,…,ai , ai+1,…,an) (a1,…,ai+1,ai,…,an)
Un tableau est trié s’il n’a aucune inversion. La complexité du
tri est proportionnelle au nombre d’inversions qui est de
l’ordre de (nombre de couple(i,j) tels que i<j).
L’algorithme consiste à parcourir le tableau à trier en
examinant si chaque couple d’éléments consécutifs (ai, ai+1)
est dans le bon ordre ou non, si ce couple n’est pas dans le
bon ordre on échange ses éléments et ce processus est
répété tant qu’il reste des inversions à faire.

SMI ALGOII
 Tri à Bulles
10

Algorithme1: On remarque que les transpositions successives

Bulles1(A,n) font pousser le maximum à la dernière position
du tableau si on fait un balayage de gauche à
Début droite et le minimum à la 1ère position si on fait
un balayage de droite à gauche.
fini := faux;
Algorithme2:
Tant que non fini faire
Bulles2(A,n)
i:=1;
Début i := 1;
tant que (i < n) et (A[i] ≤ A[i+1] ) faire
i := i + 1 ; tantque i ≤ n-1 faire der_ech := n;
ftantque; pour j := n à i+1 pas -1 faire
si i < n alors si A[j-1] > A[j] alors
échanger (A[i], A[i+1]) ; échanger(A[j], A[j-1]); der_ech := j;
fini := faux ; } fsi;
sinon fpour; i := der_ech;
fini := vrai ; ftantque;
fsi; Fin
ftantque; Le nombre de comparaison d’éléments de A ≤
fin Le nombre d’échanges ≤

T(n) = O(n2)
SMI ALGOII
 • Exemple
3 7 5 2

3 7 2 5

i=1

3 2 7 5

Der_ech=2 3 7 5
2

I=2 3 5 7
2
Der_ech=4

2 3 5 7
i=4
SMI ALGOII 11
 ALGORITHMIQUE II

Récurrence et Récursivité

SMI AlgoII
Récurrence
Suite récurrente: la définition d’une suite est la donnée
• d’un terme général défini en fonction du (ou des) terme(s) précédant(s)
• D’un terme initial qui permet d’initialiser le calcul
Principe de récurrence :
Soit P un prédicat (ou propriété) sur IN qui peut être soit vrai soit faux (on écrira
souvent P(n) à la place de P(n) = vrai).
On suppose que
P(0) vrai
∀n ∈ IN, P(n) ⇒ P(n+1)
Alors , pour tout n ∈ IN, P(n) est vrai.
Si on considère le prédicat suivant
P(n) : je sais résoudre le problème pour n
alors le principe de récurrence nous dit que si je sais résoudre le Pb pour n=0
et que si je sais exprimer la solution pour n en fonction de la solution pour n+1
alors je sais résoudre le Pb pour n’importe quel n.

SMI AlgoII
 Récursivité
Examples:
1. Puissance
a0 = 1 Ou bien
a0 = 1
an+1 = a an an = a an-1 n>0

2. Factoriel
0! = 1
n! = n (n-1)! , n ≥1

3. Suite de Fibonacci
F0 = F1 = 1
Fn = Fn-1 + Fn-2 , n≥2

SMI AlgoII
 Récursivité
Un algorithme (ou fonction) est dit récursif s’il est défini en fonction de lui-même.
Exemples
Fonction puissance(x : réel, n : entier) : réel
début
si n = 0 alors retourner 1
sinon retourner (x * puissance(x , n-1))
fin

Factoriel (n)
début
si n = 0 alors retourner(1)
sinon retourner (n*factoriel(n-1))
fin

SMI AlgoII
 Récursivité
fact (n) Le déroulement de l’appel de fact(3):
début 3*fact(2)
si n = 0 alors retourner(1) Fact(3) 3*2=6 2*fact(1)
sinon retourner(n*fact(n-1)) 6 2*1=2 1*fact(0)
fsi
1*1=1
fin La condition n = 0 est appelée test
d’arrêt de la récursivité.
Il est impératif de prévoir un test d’arrêt
dans une fonction récursive, sinon
l’exécution ne s’arrêtera jamais.
L’appel récursif est traité comme n’importe
appel de fonction.

SMI AlgoII
 Récursivité
L’appel d’une fonction (récursive ou non) se fait dans un
contexte d’exécution propre (pile d’exécution), qui
contient :
L’adresse mémoire de l’instruction qui a appelé la fonction
(adresse de retour)
Les valeurs des paramètres et des variables locales à la
fonction.
L’exécution d’une fonction récursive se fait par des
appels successifs à la fonction jusqu’à ce que la
condition d’arrêt soit vérifiée, et à chaque appel, les
valeurs des paramètres et l’adresse de retour sont mis
(empilés) dans la pile d’exécution.

SMI AlgoII
 Récursivité
L’ordre des instructions par rapport à un appel récursif est important.
Exemple:
afficher(n)
début
si n > 0 alors
١
afficher(n div 10) écrire(n mod 10)
٢
fsi
fin
L’algorithme récursif afficher(n) permet d’afficher les chiffres d’un entier, strictement positif, selon la
disposition de l’instruction écrie(n mod 10):
- Si l’instruction est placée en ١ , les chiffres sont affichés dans l’ordre inverse
- Si elle est placée en ٢, alors les chiffres seront affichés dans le bon ordre
Pour n = 123, on a :
١ → 3 2 1
٢ → 1 2 3

SMI AlgoII
Type de récursivité
Récursivité simple: Une fonction récursive contient un
seul appel récursif.
Récursivité multiple: une fonction récursive contient
plus d’un appel récursif (exemple suite de
Fibonacci).
Récursivité mutuelle( ou croisée): Consiste à écrire
des fonctions qui s’appellent l’une l’autre.
Exemple

SMI AlgoII
Récursivité mutuelle
Pair(n) Impair(n)
début début
si n = 0 alors si n = 0 alors
retourner vrai retourner (faux)
sinon sinon
retourner (impair(n-1)) retourner (pair(n-1))
fsi fsi
fin fin

SMI AlgoII
Un peu de Structures de Données
Notion de pile.
Une pile est une structure pour représenter une suite
d’éléments avec la contrainte qu’on ne peut ajouter,
ou enlever, un élément que d’un même côté de la
pile (dit sommet de la pile). ajouter enlever
Exemple pile d’assiettes. som
4
Une pile peut être représentée
par un tableau et un indice de sommet
P

SMI AlgoII
Notion de Pile
Opérations définies sur les piles:
initialiser(p : Pile) //Crée une pile vide.
sommet(p : Pile) : élément// Renvoie l’élément au
sommet de la pile p, sous la condition que p soit non
vide.
empiler(x : élément, p : Pile) // ajoute x au sommet
de la pile p.
dépiler(p : Pile) // supprime l’élément au sommet de la
pile p, sous la condition que p soit non vide.
pileVide(p : Pile) : booléen // retourne vrai si p est
vide.
SMI AlgoII
Notion de Pile
Exemple.
Une expression e est dite bien parenthésée (on se limite au ‘(‘ et ‘)’) si :
1. Le nombre de parenthèses ouvrantes (|e|() est égal au nombre de
parenthèses fermantes (|e|)) dans e.
2. Tout préfixe (partie gauche) u de e vérifie: |u|( - |u|( ≥ 0.

Algorithme: on parcourt l’expression e (de gauche à droite). A chaque

rencontre d’une parenthèse ouvrante on l’empile, et à chaque rencontre
d’une parenthèse fermente on dépile.
Si on arrive à la fin de e avec une pile vide, l’expression e est bien
parenthésée sinon e n’est pas bien parenthésée.

- l’expression (()())() est bien parenthée.

- l’expression ())( n’est pas bien parenthésée.

SMI AlgoII
Transformation du récursif en itératif :
« Dérécursivation »
Schéma d’un algorithme récursif:
algoR(X)
début
A
si C(X) alors
B;
algoR(ϕ(X));
D;
sinon Où :
E; X : liste de paramètres
fsi; C : condition d’arrêt portant sur X
A, B, D, E : bloc d’instructions (éventuellement vide)
fin ϕ(X) : transformation des paramètres

SMI AlgoII
Transformation du récursif en itératif :
« Dérécursivation »
Algorithme itératif équivalent.
algoR(X) algoI(X)
p : Pile
Début début
A initialiser(p);
si C(X) alors A;
tantque C(X) faire
B;
B;
ϕ
algoR(ϕ(X)); empiler(X, p);
D; X := ϕ (X);
A;
sinon
ftantque;
E; E;
fsi; tantque (non pileVide(p)) faire
X := sommet(p);
fin
dépiler(p);
D;
ftantque
fin

SMI AlgoII
Dérécusivation
Exemple. afficherI(n)
p : Pile;
Début
initialiser(p);
afficherR(n) tanque n > 0 faire
début empiler(n, p);
si n > 0 alors n := n div 10;
ftantque
afficher(n div 10)
tantque (non pileVide(p)) faire
écrire(n mod 10); n := sommet(p);
fsi dépiler(p);
fin écrire(n mod 10);
ftanque
fin
A=B=E=∅

SMI AlgoII
Transformation du récursif en itératif :
« Dérécursivation »
Récursivité terminale:
La récursivité est dite terminale si la dernière instruction
exécutée est un appel récursive; (Cas où D = ∅). Il est
claire, dans ce cas, d’éliminer la pile dans la version
itérative. (On dépile pour ne rien faire dans la 2ème
boucle).
La récursivité d’une fonction F(X) est aussi dite terminale
lorsqu’elle se termine par l’instruction retourner(F(ϕ(X))).
On ajoute, dans ce cas, un paramètre à la liste X pour
contenir le résultat de retour d’un appel récursive,
comme le montre l’exemple suivant:
SMI AlgoII
Exemple
fonction FACR(n) ; fonction FACR'(n, r)
début début
si n=0 alors retourner (1) si n=0 alors retourner (r)
sinon retourner (n* FACR(n-1)) ; sinon retourner (FACR'(n-1, n*r)) ;
fin. fin.
RÉCURSIVE RÉCURSIVITÉ TERMINALE

fonction FACI(n) ; fonction FACI'(n, r) ;

début début
r: = 1 ; tant que n > 0 faire
tant que n > 0 faire { r : = n* r ; n : = n-1 ; }
{ r := n* r ; n := n-1 ; } retourner (r) ;
retourner (r) ; fin.
fin.
ITÉRATIVE

SMI AlgoII
Complexité des algorithmes récursifs
La complexité des algorithmes récursifs est souvent exprimée
par une équation de récurrence.

Exemple1. Complexité de l’algorithme récursif pour

calculer n! (l’opération dominante est la multiplication)
Soit T(n) le coût de FACR(n). T(n) vérifie l’équation:
T(0) = 0
T(n) = T(n-1) + 1
la solution de cette équation est :
T(n) = n = 1 + 1 + … + 1 (n fois)
SMI AlgoII
Complexité des algorithmes récursifs
Exemple2.
Tri par sélection
sel_rec(T,n)
début
si n > 1 alors
k← max {i ∈{1,2,…,n} / T[i] ≥ T[j] , j=1,2,…,n et j ≠ i}
échanger(T[k],T[n])
sel_rec(T,n-1)
fsi;
fin
Complexité : T(n) vérifie :
T(1) = 0
T(n) = T(n-1) + n
T(n) = n+T(n-1) = n+(n-1)+T(n-2) =…= n+(n-1)+…+2 +C(1) =
T(n) = O(n2)
SMI AlgoII
 On ouvre une parenthèse
Encore un peu de structures de données
Notion d’arbre binaire
On introduit cette notion pour savoir interpréter les arbres d’appels
dans le cas d’une récursivité double(où il y a deux appels récursifs).
- Les arbres sont utilisés pour représenter une suite d’éléments.
- un arbre est un ensemble de nœuds, chaque nœud représente un
élément de la suite.
Définition récursive d’un arbre binaire:
arbre de racine r
un arbre binaire est: r
Soit vide
Soit formé :
D’un nœud (appelé racine) SAG SAD
D’un sous-arbre gauche , noté SAG, qui est un arbre binaire)
D’un sous-arbre droit, noté SAD, qui est aussi un arbre binaire
(les deux sou-arbres gauche et droit sont disjoints).

SMI AlgoII
Arbre binaire: terminologie
Soit A un arbre binaire de racine r. .
La racine du SAG (resp. SAD) de A
est appelé fils gauche (resp. fils
droit) de r et r est appelé père. 10

Un nœud qui n’ a pas de fils est

appelé feuille. 5
50

un chemin de l’arbre est une suite

de nœuds n1,n2,…nk où ni+1 est un fils
(gauche ou droit) de ni , 1≤i≤k-1. 9 60
30
Longueur d’un chemin = nombre de
nœuds, constituant le chemin, - 1
Une branche est un chemin de la 20 40
racine à une feuille.
La hauteur d’un arbre est la longueur Branche:
de la plus longue branche de feuilles 35 Branche plus longue:
l’arbre.
-1 si A = ∅ Hauteur = 4
h(A) =
1 + max(h(SAG(A), h(SAD(A))
SMI AlgoII
 Arbre binaire
Résultat (utile pour la complexité sur les arbres
binaires de recherche):

la hauteur h d’un arbre binaire de taille n (n est le nombre de nœuds de l’arbre)

vérifie: 1 + log2n ≤ h ≤ n
- la hauteur est, en moyenne, un O(log n) et
un O(n) dans le pire des cas.

Les algorithmes sur les arbres binaires se ramènent

souvent aux algorithmes de parcours de ces arbres.

SMI AlgoII
 Algorithmes de parcours
puis on ferme la parenthèse
Parcours(a : Arbre) .
10
début
si a ≠ ∅ alors
50
١ 5

parcours(SAG(a));
٢ Traiter(racine(a))
parcours(SAD(a)); ∅ 9
30
60

٣
fsi;
20 40
fin
Selon la disposition de l’instruction
traiter(racine(a)), on distingue 3 types de
parcours: 35

١ : parcours préfixe. On passe 3 fois sur un nœud .

٢ : parcours infixe. Parcours préfixe: on traite un nœud lorsqu’on le rencontre pour la 1er fois.
10-5-9-50-30-20-40-35-
٣ : parcours postfixe.
Parcours infixe: ‘’ ‘’ ‘’ ‘‘ la 2è fois.
5-9-10-20-30-35-40-50-60
Parcours posfixe: ‘’ ‘’ ‘’ le quitte pour la dernière fois.
SMI AlgoII 9-5-20-35-40-30-60-50-
 Récursivité double
&
Arbre des appels récursifs

Exemple1: calcul de la hauteur Un arbre est donné par sa racine

d’un arbre binaire. appel de h(1):
h(a : arbre)
1 h(1)=3
début
si a = ∅ alors retourner -1 2 h(2)=2
4 h(4)=0

sinon
h1 := h(SAG(a)); h(3)=1
∅ -1 3
∅ -1 ∅ -1
h2 : h(SAD(a));
retourner(1+max(h1,h2)); 5 h(5)=0
∅ -1
fsi;
fin -1 ∅ ∅ -1

SMI AlgoII
 Récursivité double
&
Arbre des appels récursifs
.
Exemple2 : tours de Hanoï (Occupation des moines de Hanoï)
Le jeu consiste à faire passer les
disques de la tour T1 à la tours
T2, en ne déplaçant qu’un seul
disque à la fois, et en utilisant la
tour intermédiaire T3 de telle T1 T2 T3
sorte qu’à aucun moment un
disque ne soit empilé sur un
disque de plus petite dimension.
La solution semble difficile, et pourtant une solution récursive existe.
Soit n le nombre de disques à déplacer. Si n=1 la solution est triviale.
Si on sait transférer n-1 disques alors on sait en transférer n.
Il suffit de transférer les n-1 disques supérieurs de la tours T1 vers la tours T3,
de déplacer le disque le plus grand de T1 vers T2, puis de transférer les n-1 disques
de T3 vers T2. Ceci se traduit par l’algorithme récursif suivant:
SMI AlgoII
Tours de Hanoï

H(n,T1,T2,T3)
début
si n = 1 alors écrire(T1, ‘→’,T2)
sinon
H(n-1,T1,T3,T2);
écrire(T1,’→’,T2)
H(n-1,T3,T2,T1);
fsi
fin

SMI AlgoII
H(n,T1,T2,T3)
début
si n = 1 alors écrire(T1, ‘→’,T2)
sinon
H(n-1,T1,T3,T2);
écrire(T1,’→’,T2)
H(n-1,T3,T2,T1);
fsi
fin Arbre des appels de H(3,a,b,c)
H (3, a, b, c)
.
H (2, a, c, b) a→b H(2,c,b,a)

H(1,a,b,c) a→c H(1,b,c,a) c→b H(1,a,b,c)

H(1,c,a,b)

a→b b→c c→a a→b

SMI AlgoII
Tours de Hanoï : Complexité
Soit T(n) le temps pour déplacer les n disques. T(n) vérifie l’équation :
T(1) = 1
T(n) = 2 T(n-1) +1

On a :
T(2) = 2 + 1
T(3) = 2(2 +1) + 1 = 22 + 2 + 1
On montre, par récurrence, que
T(n) = 1 + 2 + … + 2n-1 = 2n – 1
Sachant que T(10) = 210 – 1 = 1023 et une année ≅ 0.3 x108 secondes, il
faudrait, pour les moines, 1010 siècles pour pouvoir déplacer 64 disques!

SMI AlgoII
1 Méthode « Diviser pour Résoudre »
E. CHABBAR

SMI-ALGOII
 DVR
2

Les algorithmes sont regroupés en familles selon

certains concepts t. q. Division pour Résoudre,
Glouton, Programmation dynamique.
- L’aspect DVR consiste à diviser le problème initial
(de taille n) en sous-problèmes similaires de tailles
plus petites (en général de taille n/2, n/3,…).
- Ces sous-problèmes sont résolus récursivement.
- On peut combiner ces solutions récursives pour
avoir la solution du problème initial.
SMI-ALGOII
 DVR
3
Exemples
1. Calcul de xn (n ≥ 1)
Le nombre de multiplications par la méthode classique ( xn = x xn-1) est de l’ordre
de n.
La méthode DVR exploite la définition suivante:
1 si n=1
xn = xp . xp si n= 2p
x . xp . xp si n = 2p+1
- pour calculer xn on fait appel (récursif) au calcul xp ou p = E(n/2). (algo. Slide
suivant)
- si T(n) est le nombre de multiplications pour calculer xn alors T(n) = T(n/2) + 1 si n
est pair ou T(n) = T(n/2) + 2 si n est impair. On a, dans tous les cas, T(n) = T(n/2) +
O(1).
Comme il y a log2n divisions euclidiennes successives (avant d’avoir 1 comme
quotient) , donc T(n) = O(log(n)). (pour s’en convaincre prendre n une puissance de
2)
(T(n)=O(1)+O(1)+…+O(1) log2n fois)

SMI-ALGOII
 DVR
4
Exemples
1. Calcul de xn (n ≥ 1)
puissBin(x,n)
Début
si n = 1 alors retourner x
sinon
si n mod 2 = 0 alors
y := puissBin(x,n/2)
retourner (y*y)
sinon
y := puissBin(x,n/2)
retourner (x*y*y)
fsi;
fsi;
Fin.

SMI-ALGOII
 DVR
5
Exemples
2. RECHERCHE DICHOTOMIQUE
La recherche séquentielle d’un élément x dans un
tableau A à n éléments est de l’ordre de n.
La recherche dichotomique exige que le tableau
soit trié. Elle consiste à:
- comparer x à l’élément du milieu
- si c’est différent, x peut se trouver soit dans la
moitié gauche soit dans la moitié droite du
tableau A, selon que x < A[milieu] ou x> A[milieu].
SMI-ALGOII
 DVR
6
Exemples
2. Recherche dichotomique

rechDicho(A,inf,sup,x)
début
si inf ≤ sup alors
m := (inf + sup)/2
si x = A[m] retourner m;
si x < A[m] alors retourner rechDicho(A,inf,m-1,x);
sinon retourner rechDicho(A,m+1,sup,x);
fsi;
fsi;
sinon retourner 0;
fsi;
fin

SMI-ALGOII
 DVR
7
Exemples
2. Recherche dichotomique
Complexité de la recherche dichotomique
Dans le pire des cas (i.e. x n’est pas dans le tableau)
le nombre de comparaisons T(n), pour chercher x dans
un tableau A[1..n] à n éléments, vérifie:
T(1) = 1
T(n) = T(n/2) + 1 , n>1
- la solution de cette équation dépend du nombre
d’itérations (nombre de divisions par 2)

SMI-ALGOII
 DVR
8
Exemples
Itération Nbre d’élts du ss tableau
0 n
1 n/2
2 n/4
3 n/8
. .
. .
p n/2p
L’algorithme utilise p itérations(et aussi p comparaisons) et s’arrête
lorsque n/2p =1, c.à d. p = log2n.
par conséquent, la recherche dichotomique est en O(log2n), i.e.
T(n) = O(log2n)

SMI-ALGOII
9

3. Tri par fusion

Fusion de deux tableaux triés.
Etant donnés deux tableaux triés T1[1..n1] et
T2[1..n2]. La fusion consiste à construire un tableau
T[1..n1+n2] contenant tous les éléments de T1 et
T2 dans l’ordre croissant.
T1 T2

2 3 5 4 6 9
Fusion

T
SMI-ALGOII
2 3 4 5 6 9
 Fusion
10

Fusion(T1,n1,T2,n2)
// T est un tableau qui contient le résultat de la fusion
i1:=1; i2:= 1; k:=1;
tantque (i1≤n1) et (i2≤n2) faire
si T1[i1] ≤ T2[i2] alors
T[k] := T1[i1]; copier(A,d,f,B,j)
k:=k+1; i1 := i1 +1; début
sinon pour i:=d à f faire
T[k] := T2[i2]; B[j] := A[i]
k:=k+1; i2 := i2 + 1; j := j+1;
fsi; fpour;
ftantque; retourner(B);
// on recopie les élts restants dans l’un des //tableaux Ti dans le tableau T fin
si i1 ≤ n1 alors copier(T1,i1,n1,T,k)
sinon copier(T2,i2,n2,T,k)
fsi;
retourner (T);

SMI-ALGOII la complexité de la fusion est en O(n1+n2)

 TriFusion
11

Le tri par fusion est un exemple typique de la

stratégie diviser pour résoudre, à savoir:
1. Diviser le tableau T[1..n] en deux sous-tableaux
T[1..E(n/2)] et T[E(n/2)+1..n]
2. Trier (récursivement) les deux sous-tableaux (2
appels récursifs à la même fonction TriFusion).
3. Fusionner les deux sous-tableaux;
Ceci est schématisé par l’exemple suivant:

SMI-ALGOII
 TriFusion
12

.
5 3 2 9 4 6
Diviser

5 3 2 9 4 6

Résoudre récursivement Tri récursif

2 3 5 4 6 9

Combiner
2 3 4 5 6 9
SMI-ALGOII
 TriFusion
13

TriFusion(T, n)
// T1, T2 : des tableaux (locaux) de longueurs variables à chaque appel
début
si n > 1 alors
copier(T, 1, n/2, T1,1);
copier(T, n/2 +1, n, T2, 1);
T1 := TriFusion(T1, n/2);
T2 := TriFusion(T2, n – n/2);
T := Fusion(T1, n/2, T2, n – n/2);
fsi;
retourner(T);
fin Retourner(Fusion(TriFusion(T1,n/2),n/2,TriFusion(T2,n-n/2),n-n/2)

SMI-ALGOII
 TriFusion: exemple d’exécution
Tableau à trier:
14

TF(1..8) 1 2 3 4 5 6 8 9

1 3 6 9 TF(1..4) 2 4 5 8 TF(5..8) F(1..4,5..8)

3 9 1 6 5 2 4 8 1 2 3 4 5 6 8 9

2 5 4 8
3 9 TF(1..2) 1 6 TF(3..4) F(1..2,3..4) TF(5..6) TF(7..8) F(5..6,7..8)
3 9 1 6 1 3 6 9 5 2 4 8 2 4 5 8

TF(1..1) TF(2..2) F(1..2) TF(3..3) TF(4..4) F(3..4) TF(5..5) TF(6..6) F(5..6) TF(7..7) TF(8..8) F(7..8)

3 9 3 9 1 6 1 6 5 2 2 5 4 8 4 8

---------------------------------------------------------------------------------------------------
Recopie de ss-tableau Tableau (vert)retourné Fusion des 2 ss-tableaux(rouges)
à l’appel récursif résultats des appels récursifs
SMI-ALGOII
 DVR: Compléxité
15

La complexité T(n) pour trier un tableau de n

éléments par l’algorithme TriFusion vérifie:

T(1) = 0
T(n) = 2 T(n/2) + O(n) , n > 1

(Il y a 2 appels récursifs, chacun porte sur la moitié du

tableau. O(n) pour recopier les 2 ss-tableaus en
2xO(n/2) + leur fusion en O(n))).

SMI-ALGOII
 Equation de récurrence des [Link]
16

La récurrence, utilisée par les algorithmes type DVR, est

souvent de la forme:
O(1) pour n=1
T(n) =
a T(n/b) + O(nd) , n > 1

a : est le nombre de divisions du problème initial en sous-problème

(nombre d’appels récursifs)

n/b : la taille de chaque sous-problème (b≥2)

O(nd) : le temps nécessaire pour décomposer le problème en sous-

problème + le temps pour combiner les solutions des ss-problèmes
pour avoir la solution du problème initial.

SMI-ALGOII
 DVR: Résultat de Complexité
17

Théorème:
Soit T : IN IR+ une fonction croissante à partir d’un certain rang, telle qu’il
existe des entiers n0 ≥1, b≥2 et des réels d≥0, a>0 pour lesquels

Alors on a :
O( ) si a < bd

O( ) si a = bd
T(n) =

O( ) si a > bd
SMI-ALGOII
 DVR: Résultat de Complexité
18

On montre par récurrence sur p (p≥1), que :

SMI-ALGOII
 DVR: Résultat de Complexité
19

D’une manière générale. Si

T(1) = O(1)
T(n) = a T( ) + O( ) (n>1, a > 0, b > 1, d ≥ 0)

Alors

O( ) si a < bd

T(n) = O( ) si a = bd

O( ) si a > bd

SMI-ALGOII
 DVR
20

Applications
1. Pour la recherche dichotomique et le calcul de la
puissance on a : T(n) = T(n/2) + O(1)
donc T(n) = O(log n) (a=1 , b=2, d=0)
2. Pour le TriFusion on a : T(n) = 2 T(n/2) + O(n)
Alors T(n) = O(n log2n) (a=2, b=2, d=1)
3. T(1) = 1
T(n) = 2t(n/2) + O(n2)
a pour solution T(n) = O(n2) (a=b=d=2)

SMI-ALGOII
 DVR : tri rapide (quickSort)
21

Soit à trier le tableau T[g..d] (au départ g=1 et d=n)

Le principe de l’algorithme réside dans une procédure,
appelée partition, qui réorganise les éléments de T
autour d’un pivot (élément du tableau choisi au hasard)
de sorte que :
1) Il existe un indice p (g≤ p ≤d) tel que p est la
position définitive du pivot (T[p] = pivot).
2) tous les éléments T[g], …, T[p-1] sont inférieurs ou
égaux à T[p].
3) tous les éléments T[p+1], …T[d] sont supérieurs ou
égaux à T[p].

SMI-ALGOII
 DVR : tri rapide
22

Le travail de la fonction partition consiste à:

o Choisir un élément du tableau comme pivot(par exemple le premier
T[g])
o Parcourir le tableau depuis la gauche(de gauche à droite) jusqu’à
rencontrer un élément ≥ T[g]
o Parcourir le tableau depuis la droite (de droite à gauche) jusqu’à
rencontrer un élément ≤ T[g]
o Echanger ces deux éléments dans le tableau
o Continuer ce processus jusqu’à ce que les deux indices (de gauche et
de droite) se croisent.
o Finalement, échanger le pivot T[g] et l’élément indiqué par l’indice
de droite. ≤ pivot Non encore analysé ≥ pivot

SMI-ALGOII
g i j d
 DVR : Tri Rapide
23

//T[n+1] = + ∝ Exemple
Partition(T, g, d)
(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13)
début
3 1 4 1 5 9 2 6 5 3 5 8 9 i j
pivot := T[g];
i := g; j := d+1; 3 1 4 1 5 9 2 6 5 3 5 8 9 3 10
tantque i < j faire
i := i +1; 3 1 3 1 5 9 2 6 5 4 5 8 9 3 10
tantque T[i] < pivot faire i:=i+1;
3 1 3 1 5 9 2 6 5 4 5 8 9 5 7
ftantque
j := j -1; 3 1 3 1 2 9 5 6 5 4 5 8 9 5 7
tantque T[j] > pivot faire j:=j-1;
ftantque 3 1 3 1 2 9 5 6 5 4 5 8 9 6 5
si i < j alors échanger(T, i, j); fsi
ftantque 2 1 3 1 3 9 5 6 5 4 5 8 9 5
échanger(T, g, j);
retourner(j) 2 1 3 1 3 9 5 6 5 4 5 8 9
fin

SMI-ALGOII
 DVR : Tri Rapide
24

La fonction partition, appliquée à un tableau T,

produit trois sous-tableaux:
o Un sous-tableau réduit à un seul élément T[p] qui
garde sa place définitive dans le tri de T, et
o Deux sous-tableaux T[g .. p-1], T[p+1 .. d].
Pour trier T, il suffit d’appliquer récursivement le
même algorithme sur les deux sous-tableaux.

SMI-ALGOII
 DVR : Tri Rapide
25

quickSort(T, inf, sup)

début
si inf < sup alors
p := partition(T, inf, sup);
quickSort(T, inf, p-1);
quickSort(T, p+1, sup);
fsi
fin

SMI-ALGOII
 Complexité du Tri rapide
26

La complexité de la fonction partition, appliquée à

T[1..n], est en O(n).
- Cas le plus défavorable :
Cas où le pivot sort, à chaque fois, en premier
(ou en dernier) élément (T: tableau trié).
La partition coupe le tableau en un morceau de un
élément et un morceau de n-1 éléments, dans ce
cas on a :
C(n) = C(n-1) + O(n)
(O(n) est le coût de la partition)
On en déduit que C(n) est en O(n2)

SMI-ALGOII
 Complexité du Tri rapide
27

- Cas le plus favorable :

cas où le pivot est l’élément médiane de T.
La partition coupe T en deux morceaux de
taille n/2
C(n) = 2 C(n/2) + O(n)
ce qui donne: C(n) = O(n log n)

La complexité moyenne est aussi de l’ordre de n log n

SMI-ALGOII
 Complexité du Tri rapide
28

- Complexité moyenne du tri rapide

La formule de récurrence donnant le nombre de
comparaisons effectuées par le tri rapide pour une
permutation aléatoire de n éléments vérifie :
C0 = C1 = 0 et

1 n-1
Cn = n – 1 + ∑ (Ci + C n-i-1) pour n ≥2
n
i=0
Le terme générique Cn peut s’écrire :
2 n-1
Cn = n – 1 + ∑ Ci
n
i=0
SMI-ALGOII
 .Complexité moyenne du tri rapide
29
n-1
2
. Cn = n−1+ n i=0
∑ Ci

2 n-2
Cn = n – 1 + + 2 ∑ Ci
n Cn-1 n i=0
2 n-1 n-2 (n-1) (n-2)
Cn = n – 1 + Cn-1 + (n – 2 + 2 ∑ Ci ) -
n n n-1 i=0 n

2 n-1 2n-2
Cn = n Cn-1 + n Cn-1 +
n
n+1 2(n-1)
Cn = n Cn-1 + n
Cn 2 - 2
En posant Dn = On aura la récurrence : Dn = Dn-1 +
n+1 n+1 n(n+1)

En négligeant le dernier terme de Dn on a: Dn ≃ log n

1 +…+ 1
Du fat que : 1 + ≃ Ln(n) d’où Cn est en O(n log n)
2 n SMI-ALGOII
 Preuve de programmes

Notions de Logique
E. CHABBAR

1 SMI-ALGOII
 Logique
2

La logique a joué un rôle décisif dans le

développement de l’informatique, notamment en
informatique théorique:
- Définition d’un modèle théorique des premiers
ordinateurs (Machine de Turing)
- Calcul booléen pour la conception et l’étude des
circuits.
- La récursivité pour définir la calculabilité.
- la décidabilité et la complexité pour étudier la limite
de la machine.
- La programmation fonctionnelle.

SMI-ALGOII
 Logique
3

Actuellement l’informatique a envahi tous les

domaines de la vie. Le problème le plus important
qui se pose dans la conception d’une application
informatique est de prouver qu’elle est exempte
d’erreurs et qu’elle résout le problème pour
laquelle elle a été conçue. Pour cela, on définit une
tache par une formule de logique et on montre
qu’elle est satisfaite par un modèle de cette
application. Ce type de preuve est appelé «
Vérification Formelle ».

SMI-ALGOII
 Logique
4

Une logique, par définition, est un ensemble de formules.

Une formule est construite, sur un alphabet, suivant certaines
règles (Syntaxe).
La sémantique d’une formule est une valuation (ou
interprétation dans un modèle) qui détermine la valeur de
vérité de la formule.
Il y a plusieurs types de logiques:
- Logique des propositions (d’ordre 0)
- Logique du premier ordre (les prédicats en font partie)
- logique du second ordre et logique d’ordre supérieur.

SMI-ALGOII
 Logique des propositions
5

- On note P = {p, q, …} l’ensemble des propositions

atomiques. Chaque proposition atomique est une
variable qui ne peut prendre que « vrai » ou « faux ».
- {¬ , ∧, ∨, ⇒, ⇔} l’ensemble des connecteurs (ou
opérateurs) logique plus les parenthèses.
- On note F(P) l’ensemble des formules déduit de P.
F(P) est le plus petit ensemble qui contient P et qui est
stable par les connecteurs.
En d’autres termes:
Une formule est une suite de symboles de P ∪ {¬ , ∧,
∨, ⇒, ⇔, (, )} construite selon les règles suivantes:

SMI-ALGOII
 Logique des propositions
6

- Toute proposition atomique est une formule.

- si f est une formule alors ¬f est aussi une formule.
- si f1 et f2 sont des formules alors :
- f1 ∧ f2 est une formule
- f1 ∨ f2 « « «
- f1 ⇒ f2
- f1 ⇔ f2 « « «
Exemple: (¬p ⇒ q) ∨ (p ∧ q) est une formule.

SMI-ALGOII
 Logique des propositions
7

La sémantique des opérateurs logiques est donnée

par des tables de vérité.

p q ¬p ¬q p∨q p∧q p⇒q (¬p∨q)

0 0 1 1 0 0 1
0 1 1 0 1 0 1
1 0 0 1 1 0 0
1 1 0 0 1 1 1

SMI-ALGOII
 Prédicats
8

Les prédicats sont construits avec :

- les constantes (0,1,2,….)
- les variables (x, y, ….)
- les fonctions (f, g, +, *, …)
- des connecteurs logiques (¬ , ∧, ∨, ⇒, ⇔)
- des parenthèses
- des quantificateurs (∀, ∃)
Un prédicat atomique est un prédicat qui ne contient ni
connecteur ni quantificateur.
- Exemples: x < y ; pair(2 x) ;

SMI-ALGOII
 Prédicats
9

Règles de formations des formules de prédicats:

- Tout prédicat atomique est une formule
- si f1 et f2 sont des formules alors
¬ f1, f1 ∨ f2, f1 ∧ f2, f1 ⇒ f2, f1⇔ f2
sont des formules.
- si f est une formule alors
∀ x f est une formule
∃ x f est une formule

SMI-ALGOII
 Prédicats
10

Exemples:
1) ∀x pair(x + x)
2) ∃x premier(x) ∧ x < succ(succ(0))
3) ∀x (oiseau(x) ⇒ vole(x)) (tous les oiseaux volent)
4) ∃x (oiseau(x) ∧ ¬ vole(x)) (4 ≡ ¬ 3)
5) ∀i ∀j (1≤i ≤j≤n ⇒ T[i] ≤ T[j]) (spécification d’un tableau trié)
Remarques
¬ (∀x P) ≡ ∃x ¬P
¬ (∃x P) ≡ ∀x ¬P
SMI-ALGOII
 Déduction logique
11

Démonstrations logiques

Un séquent est un couple de la forme (ℐ ,f), où f

est une formule et ℐ un ensemble fini de
formules . L’ensemble ℐ est l’ensemble
des prémisses du séquent, la formule f sa
conclusion.

SMI-ALGOII
12

• Séquents prouvables
• Un séquent (ℐ,f) est prouvable, ce que l’on notera
ℐ ├ f, s’il peut être construit en utilisant un nombre fini
de fois les 6 règles suivantes :
1. si f∈ℐ, alors ℐ├f (Hypothèse)

2. si g ∉ ℐ et ℐ ├ f, alors ℐ, g├ f
3. si ℐ ├ (f ⇒ f’) et ℐ ├ f, alors ℐ ├ f’ (Modus Ponens)
4. si ℐ , f├ f’, alors ℐ ├(f ⇒ f’) (Synthèse)
5. ℐ ├ f ssi ℐ ├ ¬¬f
6. si ℐ ,f├ f’ ℐ,f├ ¬f’ alors ℐ├¬f (Raisonnement par l’absurde)
(Contradiction)
SMI-ALGOII
13

• Démonstrations logiques
• Une démonstration d’un séquent prouvable ℐ ├ f est
une suite finie de séquents prouvables ℐi├ fi,
i = 1,...,n, telle que :
• ℐn = ℐ et fn = f
• chaque séquent de la suite est obtenu à partir des
séquents qui le précède en appliquant l’une des 6 règles
• Remarque : le premier séquent de la suite est
nécessairement obtenu par utilisation d’une hypothèse

SMI-ALGOII
14

• Démonstrations logiques - Exemple

• Tous les hommes sont mortels, et
• les Grecs sont des hommes, donc les
Grecs sont mortels
h = « être un homme »
m= « être mortel »
g = « être Grec »
(h ⇒ m), (g ⇒ h)├ (g ⇒ m)
SMI-ALGOII
15

• Démonstrations Logiques - Exemple

• Tous les hommes sont mortels, et
• les Grecs sont des hommes, donc les Grecs
sont mortels
• 1. (h ⇒ m), (g ⇒ h), g├ g hypothèse
• 2. (h ⇒ m), (g ⇒ h), g├ (g ⇒ h) hypothèse
• 3. (h ⇒ m), (g ⇒ h), g├ h MP (1&2)
• 4. (h ⇒ m), (g ⇒ h), g├ (h ⇒ m) hypothèse
• 5. (h ⇒ m), (g ⇒ h), g├ m MP (3&4)
• 6. (h ⇒ m), (g ⇒ h)├ (g ⇒ m) synthèse
SMI-ALGOII
16 Preuve de programmes
Logique de Hoare

SMI-ALGOII
 Correction de programmes /
17
Spécification
un programme est correct s’il effectue la
tâche qui lui est confiée dans tous les cas
permis possibles

nécessité de disposer d’un langage de

spécification permettant de décrire
formellement la tâche confiée à un
programme.

SMI-ALGOII
 Correction de programmes /
18
Spécification
description des propriétés que doit
satisfaire un programme pour répondre au
problème posé
- relation entre les entrées et les sorties
du programme

Entrée E Programme Sortie S

Précondition : P(E) Postcondition : Q(E, S)

SMI-ALGOII
 Correction de programmes /
Spécification
19

Exemple
une spécification pour le problème du
calcul de la racine carrée entière par
défaut :
Données n : entier ;
Résultat r : entier ;

Pré condition : n ≥ 0
Algorithme: r := 0; tantque (n ≥(r +1)2) faire r := r + 1 ftantque

Post condition : (r2 ≤ n) ∧ (n < (r+1)2)

SMI-ALGOII
 Test vs Vérification
20

. Les couples (n, r) de l’ensemble suivant {(0, 0), (1, 1), (2, ), (3, 1), (4, 2), …}
sont des tests qui réussissent

• Hoare propose une exécution de l’algorithme sur une valeur

symbolique qui est un ensemble de valeurs défini par une expression
logique (ou prédicat).
• L’ensemble {(0, 0), (1, 1), (2, 1), (3, 1), (4, 2), …} est
défini par {(n,r) / n≥0 ∧ r ≥0 ∧ r2 ≤ n ∧ (n < (r+1)2}

• On note {n≥0 ∧ r ≥0 ∧ r2 ≤ n ∧ (n < (r+1)2} la valeur symbolique des

variables n et r.

• L’exécution d’un algorithme A sur une valeur symbolique de données

définies par l’expression { p} qui donne une valeur symbolique résultat
définie par l’expression { q} est notée {p} A {q} . {p} A {q} est appelé triplet
de Hoare (p : précondition, q : postcondition).
SMI-ALGOII
 Système formel
21

. Interpretation d’un triplet de Hoare

{p} A {q} signifie :
Si la propriété p est vraie avant l’exécution de A ET si l’exécution de A
se termine, ALORS la propriété q est vraie après l’exécution de A.
(Correction partielle)

• Un système formel est un triplet <L, Ax, R> où :

- L est un langage définissant un ensemble de formules,
- Ax est un sous-ensemble de L ; chaque formule de Ax est appelée axiome,
R est un ensemble de règles de déduction de formules à partir d’autres formules ;

SMI-ALGOII
 Langage algorithmique
22 Langage algorithmique
• Instructions :
- Affectation (:= symbole d’affectation et = pour la comparaison)
- Contrôle :
Si <cond> alors instruction fsi
ou Si <cond> alors instruction
sinon instruction fsi
- Boucle :
Tantque <cond> faire instruction ftantque

• Restriction :
- Pas de fonction (ou procédure)
- ni de variable pointeur
- pas de désignation de la forme t[i] où i fait référence à un autre
tableau.
SMI-ALGOII
 Logique de Hoare
23 Logique de Hoare
• Définition de la logique de Hoare : La logique de
HOARE est un triplet <L, Ax, R> avec :
- L est l’ensemble des formules { p} A { q} où p
et q sont des prédicats et A est un fragment
d’algorithme(ou de programme)
- Ax est l’ensemble des axiomes de la forme
suivante : { p[ x / e] } x := e { p(x)}
(p(x) est obtenu de p[x/e] en substituant toute
occurrence de e par x)
- R est l’ensemble de règles de déduction
suivant :
SMI-ALGOII
 Logique de hoare
24

(Séq) si {p} A1 {r} ; {r} A2 {q} alors

{p} A1 ; A2 {q}
(consg) si p ⇒ p’, {p’} A {q} alors
{p} A {q}
(consd) si {p} A {p’}, p’ ⇒ q alors
{p} A {q}
(cond1) si {p ∧ c} A {q} , (p ∧ ¬c) ⇒ q alors
{p} si c alors A fsi {q}
(cond2) si {p ∧ c} A1 {q} , {p ∧ ¬c} A2 {q} alors
{p} si c alors A1 sinon A2 fsi {q}
(tantque) si {I ∧ C} A {I} alors
{ I} tantque C faire A ftantque {I ∧ ¬C}

(I doit être un invariant de la boucle)

SMI-ALGOII
 Exemple : règles d’affectation
25
et conséquence
.
• { p[ x / e] } x := e { p(x)}
1. {n+1> 0} n:= n+1 {n>0} (x=n, e = n+1)
2. {k > 0} n :=0 {k > n} (x=n, e =0)
3. {x = 4} x := x+1 {x=5} en écrivant:
{(x+1) -1 =4} x := x+1 { x - 1 =4} ⇒ {x = 5}

4. {x ≥ 0} x := x + 1 {x ≥ 1}
{x ≥ 0} ⇒ {x + 1 ≥ 1}
x := x + 1
{x ≥ 1} SMI-ALGOII
 Exemple : règles de condition
26

5. {vrai}
si x ≥ 0 alors
{vrai ∧ x ≥ 0} ⇒ {x ≥ 0} ⇒{x+1≥1}
x := x + 1;
{x ≥ 1}
sinon
{vrai ∧ x < 0} ⇒ {x < 0} ⇒ {-x > 0}
x := - x;
{x > 0} ⇒ {x ≥ 1}
fsi
{x ≥ 1}

SMI-ALGOII
 Schéma de preuve d’un algorithme itératif
Tant que
27

Soit l’algorithme suivant:

début
{pré}
init;
{I}
tantque C faire
{I ∧ C}
A
{I}
ftantque
{I ∧ ¬ C} ⇒
{post}

SMI-ALGOII
 Exemple: calcul de la racine carrée
28
par défaut
Algorithme A:
donnée : n : entier;
résultat : r : entier;
début
r := 0;
tantque n ≥ (r + 1)2 faire
r := r + 1;
ftantque
fin

Spécification:
précondition : {n ≥ 0}
postcondition : { (r2 ≤ n ∧ n < (r + 1)2) }
invariant de la boucle: I = {r2 ≤ n} (évident, sinon on le déduit de la postcondition)

SMI-ALGOII
 Algorithme A annoté et prouvé
29

Algorithme A:
donnée : n : entier;
résultat : r : entier;
Début
{n ≥ 0} ⇒ {n ≥ 0*0}
r := 0;
{n ≥ r*r}
tantque n ≥ (r + 1)2 faire
{n ≥ r2 ∧ n ≥ (r + 1)2}
r := r + 1;
{n ≥ r2}
ftantque
{r2 ≤ n ∧ n < (r + 1)2}
fin

SMI-ALGOII
 Exemple: calcul de n!
30

Algorithme B:
donnée : n : entier
résultat : y : entier
début
x := n;
y := 1;
tantque x > 1 faire
y := y * x;
x := x – 1;
ftantque
fin

Spécification:
précondition : {n ≥ 0}
postcondition : {y = n!}
Invariant: I = { n! = y x! ∧ x ≥ 0}
SMI-ALGOII
 Algorithme B annoté et prouvé
31

Algorithme B:
donnée: n : entier;
résultat: y : entier;
début
{n ≥ 0}
x := n;
{x ≥ 0 ∧ x = n}
y := 1;
{n! = y x! ∧ x ≥ 0}
tantque x > 1 faire
{n! = y x! ∧ x ≥ 0 ∧ x > 1} ⇒ {n! = (y x)(x-1)! ∧ x > 1}
y := y * x;
{n! = y (x-1)! ∧ x-1 > 0}
x := x – 1;
{n! = y x! ∧ x > 0} ⇒ {n! = y x! ∧ x ≥ 0}
ftantque
{n! = y x! ∧ x ≥ 0 ∧ x ≤ 1} ⇒ { y = n!}

Exercice: Faites la preuve de l’algo. de n! en faisant une boucle qui va de 1 à n

SMI-ALGOII