Transparent Algo S 1

Algorithmique 1
Sylvain Daudé
HAI101I / HA8203I
Sylvain Daudé (UM - FDS) Algorithmique 1 1 / 118

Organisation
12h cours, 18h TD, 15h TP

Evaluation :
Un examen intermédiaire en amphi : 25%
Une note de TD-TP : 25%
Un examen final en amphi : 50% avec règle du max
Seconde session complète à 100%

Cadre du cours
Objet du cours
Ce cours porte sur les algorithmes récursifs et itératifs ainsi que leur efficacité
(complexité en temps). Deux sections sont dédiées aux algorithmes de
recherche et de tri. Une synthèse du cours est disponible en ligne sur Moodle.
Principale référence
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction à
l’algorithmique. Ed. Dunod.
Cet ouvrage de référence est disponible en ligne gratuitement. Il vous sera

utile pendant tout votre cursus.

Plan
1 Généralités
2 Structures linéaires
3 Arrêt d’un algorithme
4 Validité d’un algorithme
5 Complexité en temps d’un algorithme
6 Algorithmes de recherche dans un tableau
7 Algorithmes de tri

Plan
1 Généralités

Algorithme
Définition d’un algorithme
Algorithme : séquence de calcul bien définie, en réponse à un problème,
selon un nombre fini d’opérations.
S’il renvoie un résultat principal, c’est une fonction, sinon une procédure.
Les effets de l’algorithme autres que le résultat principal (affichages,
modification de l’environnement...) sont les effets de bord.
Remarques
Certains problèmes sont bien posés mais trop complexes pour un
algorithme ("indécidables" ou "incalculables"). Exemple : problème de
l’arrêt.
Certains algorithmes nécessiteraient trop de ressources pour être
concrètement utilisés. Exemple : le jeu d’échecs : 300 millions d’années
pour connaître les conséquences de chaque coup.
Dans ces deux cas, on adopte des méthodes approchées, les
heuristiques.
Vocabulaire sur un exemple en pseudo-code
Signature ou prototype
Catégorie Nom Paramètres Type du résultat principal
Fonction : facto (E n : entier) : entier
Spécifications : renvoie la factorielle d'un entier naturel n
Variables : produit : entier

spéciﬁcations : problème, contraintes
Début sur les paramètres, eﬀets de bord
produit ← 1
variables : emplacements nommés
de stockage
pour i de 1 à n faire
produit ← produit * i corps
finPour
Renvoyer produit
Fin

Algorithme itératif et récursif
Définitions
Algorithme itératif : contient au moins une boucle (pour, tant que).
Algorithme récursif : partiellement défini à partir de lui-même et d’un cas
de base.
Remarque
Un algorithme peut être ni itératif ni récursif, les deux à la fois ou seulement
un des deux : tout est possible.

Exemple d’algorithme itératif en pseudo-code
F ONCTION : FactIt (E n : entier) : entier
S PÉCIFICATIONS : n ∈ N. Renvoie n! = 1 × 2 × ... × n avec 0! = 1
Variable : res : entier
D ÉBUT
res ← 1
res ← res * i
fin pour;
Renvoyer res
F IN

Exemple d’algorithme récursif en pseudo-code
F ONCTION : FactRec (E n : entier) : entier
S PÉCIFICATIONS : n ∈ N. Renvoie n! = 1 × 2 × ... × n avec 0! = 1
D ÉBUT
si n = 0 alors
Renvoyer 1
sinon
Renvoyer n × FactRec(n − 1)
fin si;
F IN

Définitions
Type : catégorie d’une valeur : entier, nombre, booléen, tableau...

Constante : valeur invariable ayant un type : 5, ’c’, "Peachy".
Variable : triplet (nom, type, valeur). Nom et type définis à la déclaration,
valeur affectée dans un deuxième temps (par exemple dans le corps d’un
algorithme).
Environnement : ensemble de variables (notamment). Un environnement
peut contenir des sous-environnements.
Portée d’une variable : ensemble des environnements où elle existe.
Appel d’algorithme : nom de l’algorithme suivi de valeurs pour les
paramètres, les arguments, entre parenthèses. A pour valeur le résultat
principal de l’algorithme si c’est une fonction. Appel récursif : appel d’un
algorithme par lui-même.
Opération : application d’un opérateur à des opérandes : 3*8
Expression : formule contenant constantes, noms de variables,
paramètres, appels d’algorithmes et opérations. A pour valeur le résultat
de la formule.

A vous de jouer !
Trouver les types, constantes, variables, appels, opérations,

expressions
F ONCTION : PuisIt (E x : nombre,

F ONCTION : PuisRec (E x : nombre,
E n : entier) : nombre
E n : entier) : nombre
Variable : res : nombre
D ÉBUT
si n = 0 alors
D ÉBUT Renvoyer 1
res ← 1
sinon
pour i de 1 à n faire Renvoyer
res ← res * x
x × PuisRec(x, n − 1)
fin pour;
fin si;
Renvoyer res
F IN
F IN

A vous de jouer !
Correction
types : nombre, entier
constantes : 0, 1
variables : res
appels : PuisRec(n-1,x) (appel récursif)
opérations : res←1 (affectation), res*x, res←res*x, n=0, n-1, x ×
PuisRec(n-1,x)
expressions : tous les précédents sauf affectations, x, n (paramètres), i
(indice de boucle)
Attention !
L’indice de boucle et les paramètres ne sont pas des variables.

Opérateurs en pseudo-code et python
Opérateurs de calcul : + - * / ˆ (puissance) div (quotient) mod (reste)

Opérateurs de comparaison : = 6= < ≤ > ≥
Opérateurs logiques : non, et, ou. Evaluation paresseuse :
dans "a et b", si a est faux, b n’est pas évalué
dans "a ou b", si a est vrai, b n’est pas évalué.
Opérateur ternaire ou conditionnel : cond(a,b,c) : vaut b si a est vrai, c
si a est faux. b et c doivent être du même type. Utilise l’évaluation
paresseuse.
Affectation : variable ← expression. N’a pas de valeur.
En Python : ˆ devient **, div //, mod %, = ==, 6= ! =, ≤ <=, ≥
>=, non not, et and, ou or, cond(a,b,c) b if a else c, ← =

A vous de jouer !
Les expressions suivantes sont-elles correctes ?

Si oui, quel est leur type et leur valeur ?
1+5*2 entier, 11
1+5/2 nombre, 3.5
8 div 3 + 7 mod 5 entier, 4
5.0 mod 2 erreur
1=5*2 booléen, false
true et (true ou false) booléen, true
true ou 3 erreur
true ou (5/0=1) booléen, true
cond(5 mod 2 = 1, 8, 15) entier, 8
cond(5 div 2 = 1, true, 0) erreur
cond(5 div 2 = 2, cond(5 mod 2 = 0, 3, 8), 11) entier, 8

Structure conditionnelle
Définition
Une structure conditionnelle modifie le déroulement de l’algorithme selon
qu’une condition est vérifiée ou non.
Syntaxe
si a alors En Python :
instructions I if a :
sinon si b1 alors Instructions I
instructions SS1 elif b1 :
... Instructions SS1
sinon si bn alors (...)
instructions SSn elif bn :
sinon Instructions SSn
instructions S else :
fin si; Instructions S

A vous de jouer !
Qu’affichent les blocs d’instructions suivants ?

Variable : i : entier Variable : i : entier
D ÉBUT D ÉBUT
i←0 i←0
si i<3 alors si i<3 alors
i←5 i←5
sinon si i≥4 alors fin si;
i←7 si i≥4 alors
fin si; i←7
afficher i fin si;
F IN afficher i
F IN
Correction : 5
Correction : 7

Boucle tant que
Définition
Une boucle tant que répète un bloc d’instructions tant qu’une certaine
condition est vraie. On utilise une boucle tant que lorsque le nombre
d’itérations n’est pas connu à l’avance.
Syntaxe
tant que expression faire
instructions
fin tq;
En Python :
while expression :
instructions
Remarque
La boucle Tant que est plus générale que la boucle Pour.
A vous de jouer !
Que renvoient les blocs d’instruction suivants ?

Variable : i : entier Variable : i : entier
D ÉBUT D ÉBUT
i←0 i←5
tant que 2*i+1<10 faire tant que i 6= 0 faire
i ← i+1 i ← i-2
fin tq; fin tq;
Renvoyer i Renvoyer i
F IN F IN
Correction : 5 Correction : Rien ! (boucle infinie)

Boucle pour
Définition
Une boucle pour répète (ou itère) un bloc d’instructions. Les itérations sont
repérées par un indice de boucle. Il y a autant d’itérations que de valeurs de
l’indice. On l’utilise lorsque le nombre d’itérations est connu à l’avance.
Syntaxe
pour i de a à b [par pas de c] faire
instructions
fin pour;
# Par défaut, c=1 ;
# Pas d’itération si i dépasse strictement la valeur b.
En Python :
for i in range (a, B, c) :
Instructions
# Par défaut, a=0 et c=1 ;
# Pas d’itération si i dépasse ou prend la valeur B

A vous de jouer !
Qu’affichent les blocs d’instruction suivants ?

D ÉBUT D ÉBUT
pour i de 1 à 5 faire pour i de 1 à 5 faire
afficher 10 - 2*i pour j de 6 à 3 par
fin pour; pas de -2 faire
F IN afficher i*j
fin pour;
Correction : 8 6 4 2 0 fin pour;
F IN
Correction : 6 4 12 8 18 12 24 16 30
20

Plan
1 Généralités

Structures linéaires
Définition
Dans ce cours, les "structures linéaires" (tableaux 1D, listes, piles, files)
contiennent des données de même type "alignées" les unes derrière les
autres.
1 tableaux 1D
2 listes
3 piles
4 files

Tableaux 1D (statiques)
Définition
Un tableau 1D statique contient un nombre fixe d’éléments appelé taille du
tableau. Chaque élément du tableau est repéré par un entier naturel situé
entre 0 et la taille du tableau -1, appelé l’indice de l’élément. Un tableau ne
peut pas être vide.
Exemple de représentation
Si le tableau T contient les valeurs 1, 6 et 10 dans cet ordre, on peut le noter
T [i] 1 6 10
[1,6,10] et le représenter ainsi :
i 0 1 2
On a taille(T)=3, T[0]=1, T[1]=6, T[2]=10.

A vous de jouer !
Ecrire la valeur du tableau T après les étapes suivantes

Variable : T : tableau de 5 nombres [?,?,?,?,?]
T[0] ← 1 [1,?,?,?,?]
Pour i de 1 à 4 faire
T[i] ← 2*T[i-1]
finPour [1,2,4,8,16]
T[5] ← 32 Erreur

Utilisation des tableaux : exemple 1
P ROCÉDURE :
doubleTab (ES T : tableau d’entier)
S PÉCIFICATIONS :
Double les valeurs de T.
D ÉBUT
pour i de 0 à Taille(T)-1 faire
T[i] ← 2*T[i]
fin pour;
F IN

Utilisation des tableaux : exemple 2
F ONCTION : creeTabCarres
(E n : entier) : tableau d’entier
S PÉCIFICATIONS : Crée le
tableau des n premiers carrés (n ∈ N)
Variable : T : tableau de n entiers
D ÉBUT
pour i de 0 à Taille(T)-1 faire
T[i] ← i*i
fin pour;
Renvoyer T
F IN

A vous de jouer !
F ONCTION : compteEgaux(E e : entier,

E T : tableau d’entiers) : entier
S PÉCIFICATIONS : Calcule et renvoie

le nombre d’éléments de T égaux à e.
Variable : cpt : entier
D ÉBUT
cpt ← 0 ;
pour i de 0 à taille(T)-1 faire
si T[i]=e alors
cpt ← cpt + 1
fin si;
fin pour;
Renvoyer cpt
F IN

Tableaux en Python
Création : T=[4,6,17] ou T=[0]*3 ou T=[i*i for i in range(n)]

Accès à un élément : T[i]
Taille du tableau : len(T)

Listes
Définition
Une liste est soit vide, soit constituée d’un élément, sa tête, suivie d’une liste,
sa queue.
Constantes : la liste vide [ ]
Fonctions prédéfinies :
Tête d’une liste non vide : F ONCTION : tête(E liste) : élément
Queue d’une liste non vide : F ONCTION : queue(E liste) : liste
Construction avec tête et queue : F ONCTION : cons (E élément, E liste) :
liste
Test qu’une liste est vide : F ONCTION : estVide(E liste) : booléen
Exemple
L ← cons (1, cons (2, cons(3, [] ))) —–> L vaut [1, 2, 3], tête 1, queue [2,3]
A ← tête(queue(queue(L))) ——> A vaut 3
Test si L a au moins 2 éléments : non(estVide(L)) et non
estVide(queue(L))

A vous de jouer !
Ecrire la valeur de la liste L après les étapes suivantes

Variable : L : liste d’entiers ?
L ← cons(2,[]) [2]
L ← cons(tête(L),queue(L)) [2]
L ← cons(3,L) [3,2]
L ← cons(i,L)
finPour [5,4,3,2,1,3,2]
L ← queue(queue(L)) [3,2,1,3,2]
L ← cons(L[2], []) erreur : L[2] illégal
L ← cons([], 5) erreur : usage : cons(élément, liste)

Utilisation des listes : exemple itératif
F ONCTION :
longueur (E L : liste d’entier) : entier
S PÉCIFICATIONS :
Renvoie la longueur de la liste L.
Variable : cpt : entier, M : liste d’entiers
D ÉBUT
cpt, M ← 0, L ;
tant que non estVide(M) faire
cpt, M ← cpt+1, queue(M)
fin tq;
Renvoyer cpt
F IN

Utilisation des listes : exemple récursif
F ONCTION :
doubleListe (E L : liste d’entier) : liste
d’entier
S PÉCIFICATIONS :
Renvoie une nouvelle liste contenant les
valeurs de L doublées.
D ÉBUT
si estVide(L) alors
Renvoyer [ ]
sinon
Renvoyer
cons(2*tête(L),doubleListe(queue(L)))
fin si;
F IN

A vous de jouer ! Compléter les fonctions
F ONCTION : cptEgauxLIte (E e :
F ONCTION : cptEgauxLRec (E e :
entier, E L : liste d’entiers) : entier
entier, E L : liste d’entiers) : entier
S PÉCIFICATIONS : Compte le nombre
S PÉCIFICATIONS : Compte le nombre
d’éléments de L égaux à e (itératif)
d’éléments de L égaux à e (récursif)
Variable : cpt: entier ; M: liste d’entiers
D ÉBUT
si estVide(L) alors

D ÉBUT Renvoyer 0
M,cpt L,0 ;
sinon si tête(L)=e alors
tant que non estVide(M) faire Renvoyer 1+

si tête(M)=e alors cptEgauxLRec(e,queue(L))
cpt cpt+1
sinon

fin si; Renvoyer
M queue(M) cptEgauxLRec(e,queue(L))
fin tq; fin si;
Renvoyer cpt
F IN
F IN

Listes en Python
Remarque
En Python, les listes sont représentées par des tableaux.
liste vide : []
tête(liste) : liste[0]
queue(liste) : liste[1:]
cons(élément, liste) : [élément]+liste
estVide(liste) : not liste

Piles
Définition
Une pile est soit vide, soit constituée d’un élément, son sommet, suivi d’une
pile. On accède à ce qui vient d’être empilé. La lecture du sommet est
destructive.
Constantes : la pile vide [ ]
Suppression du sommet d’une pile non vide et retour de sa valeur :
F ONCTION : depiler(ES pile) : élément
Ajout d’un élément au sommet d’une pile :
P ROCÉDURE : empiler(E élément, ES pile)
Test qu’une pile est vide :
F ONCTION : estVide(E pile) : booléen
Exemple
P ← [ ] ; empiler (1, P) ; empiler(2, P) —-> P vaut [1, 2] (sommet : 2)
A ← depiler(P) —-> A vaut 2, P vaut [1]

A vous de jouer !
Calculer la valeur de la pile P après chaque étape

Variable : P : pile d’entiers ?
P ← [] []
empiler(i,P)
finPour [1,2,3]
empiler(depiler(P),P) [1,2,3]
empiler(P[1],P) erreur : P[1] illégal
empiler(P,4) erreur : usage : empiler(élt, pile)
P ← cons(3,P) erreur : cons illégal
depiler(P) [1,2]
depiler(P) [1]
depiler(P) []
depiler(P) erreur : P est vide

Utilisation des piles : exemple
P ROCÉDURE :
doublePile (ES P : pile d’entier)
S PÉCIFICATIONS :
Double les valeurs de P.
Variable : Q : pile d’entier
D ÉBUT
Q←[];
tant que non estVide(P) faire
empiler(2*depiler(P), Q)
fin tq;
tant que non estVide(Q) faire
empiler(depiler(Q), P)
fin tq;
F IN

A vous de jouer ! Compléter la fonction
P ROCÉDURE : invPileIte (ES P : pile d’entier)
S PÉCIFICATIONS : Inverse l’ordre des valeurs de la pile P.
Variable : Q, R : pile d’entier
D ÉBUT
Q, R ← [ ], [ ] ;
empiler(depiler(P), Q)
fin tq;
tant que non estVide(Q) faire
empiler(depiler(Q), R)
fin tq;
tant que non estVide(R) faire
empiler(depiler(R), P)
fin tq;
F IN
Piles en Python
Remarque
En Python, les piles sont représentées par des tableaux.
pile vide : []
depiler(P) : P.pop()
empiler(e, P) : P.append(e)
estVide(P) : not P

Files
Définition
Une file est soit vide, soit constituée d’un élément, sa tête, suivi d’une file, sa
queue. On accède au premier élément enfilé. La lecture du sommet est
destructive.
Constantes : la file vide [ ]
Suppression de la tête d’une file non vide et retour de sa valeur :
F ONCTION : defiler(ES file) : élément
Ajout d’un élément en fin de file :
P ROCÉDURE : enfiler(E élément, ES file)
Test qu’une file est vide :
F ONCTION : estVide(E file) : booléen
Exemple
F ← [] ; enfiler(1, F) ; enfiler (2, F) ; enfiler (3, F) —-> F = [1, 2, 3] (tête : 1)
A ← defiler(F) —-> A vaut 1, F vaut [2, 3]

A vous de jouer !
Calculer la valeur de la file F après chaque étape

Variable : F : file d’entiers ?
F ← [] []
enfiler(i,F)
finPour [1,2,3]
enfiler(defiler(F),F) [2,3,1]
enfiler(F[1],F) erreur : F[1] illégal
enfiler(F,4) erreur : usage : enfiler(élt, file)
F ← cons(3,F) erreur : cons illégal
defiler(F) [3,1]
defiler(F) [1]
defiler(F) []
defiler(F) erreur : F est vide

A vous de jouer ! Compléter la fonction
P ROCÉDURE : inverseFile (ES F : file d’entier)
S PÉCIFICATIONS : Inverse l’ordre des éléments de la file F
Variable : P : pile d’entier
D ÉBUT
P←[];
tant que non estVide(F) faire
empiler(defiler(F), P)
fin tq;
enfiler(depiler(P), F)
fin tq;
F IN

Files en Python
Remarque
En Python, les files sont représentées par des tableaux.
file vide : []
defiler(F) : F.popleft() [utilise la collection deque]
enfiler(e, F) : F.insert(0,e)
estVide(F) : not P

Attention
Ne pas confondre pseudo-code et Python

En pseudo-code, même si les tableaux, listes, piles, files partagent la même
notation, les opérateurs d’une structure ne fonctionnent pas sur les
autres ! C’est différent du Python !

Plan
1 Généralités

Motivation
Un bon algorithme...
... est un algorithme qui se termine, c’est à dire qui effectue un nombre fini
d’opérations. Cette section présente une méthode pour prouver qu’un
algorithme se termine.

Arrêt d’un algorithme itératif
Méthode
Pour prouver qu’un algorithme itératif se termine, on prouve :
qu’il y a un nombre fini d’itérations
que chaque itération se termine.

Premier exemple de preuve d’arrêt
Exemple
F ONCTION : F1 (E n : entier) : entier
Variable : res : entier
D ÉBUT
res ← 1
res ← res * i
fin pour;
Renvoyer res
F IN
Chaque itération contient 2 opérations donc se termine.

i parcourt les indices 1 à n donc il y a un nombre fini d’itérations.
Donc l’algorithme se termine.

Deuxième exemple de preuve d’arrêt
Exemple
F ONCTION : F (E n : entier) : entier
Variable : p, res : entier
D ÉBUT
p, res ← n, 0
tant que p>0 faire
p, res ← p div 2, res + 1
fin tq;
Renvoyer res
F IN
Chaque itération contient 2 affectations et 2 opérations donc se termine.

p ∈ N diminue strictement à chaque itération jusqu’à atteindre 0. Lorsqu’il
atteint 0, la boucle se termine donc il y a un nombre fini d’itérations.
Donc l’algorithme se termine.
A vous de jouer ! 1/2
F se termine-t-il ? Si oui, le prouver, sinon, corriger.
F ONCTION :
F (E n : entier) : entier
S PÉCIFICATIONS : Renvoie le Chaque itération contient 2

chiffre des unités de n ∈ N opérations donc se termine.
Si n=9 par exemple, i prend les
Variable : i : entier
valeurs 9, -1, -11, -21 ... et il y a
un nombre infini d’itérations :
D ÉBUT
i←n l’algorithme ne s’arrête pas.
tant que i 6= 0 faire Modification : remplacer la
i ← i - 10 condition i 6= 0 par i ≥ 10.
fin tq;
Renvoyer i
F IN

G se termine-t-il ? Si oui, le prouver, sinon, corriger.
F ONCTION :
G (E a,b : entier) : entier
S PÉCIFICATIONS : a, b ∈ N avec Chaque itération contient 5

a ≤ b. Calcule quelque chose. opérations dont se termine.
i progresse au moins d’une
Variable : i : entier unité à chaque itération, donc
i ≥ b en au maximum b-a
D ÉBUT itérations. Comme les itérations
i←a s’arrêtent lorsque i ≥ b, il y a un
tant que i<b faire nombre fini d’itérations.
i ← i + cond(i mod 7 = 0, 3, 1)
L’algorithme se termine.
fin tq;
Renvoyer i
F IN

Terminaison d’un algorithme récursif
Méthode
Pour prouver qu’un algorithme récursif se termine, on montre :
qu’il y a un nombre fini d’appels récursifs ;
qu’en dehors des appels récursifs, il y a un nombre fini d’opérations.

Exemple de preuve d’arrêt
Exemple
S PÉCIFICATIONS : calcule la factorielle d’un entier n ∈ N.
D ÉBUT
si n=0 alors
Renvoyer 1
sinon
Renvoyer n*F2(n-1)
fin si;
F IN
n ∈ N décroît d’une unité à chaque appel et il y a un cas de base pour

n=0, donc il y a un nombre fini d’appels récursifs.
En dehors des appels récursifs, il y a un nombre borné d’opérations.
L’algorithme se termine.
F se termine-t-il ? Si oui, le prouver, sinon, corriger.
F ONCTION :
F (E n : entier) : entier
S PÉCIFICATIONS : n ∈ N. En dehors des appels récursifs, il

Calcule 2n sans multiplication. y a un nombre fini d’opérations.
n ∈ N augmente d’une unité à
D ÉBUT chaque appel donc n’atteint
si n = 0 alors jamais 0.
Renvoyer 0
Modification : remplacer F (n + 1)
sinon
par F (n − 1).
Renvoyer 2+F(n+1)
fin si;
F IN

G se termine-t-il ? Si oui, le prouver, sinon, corriger.
F ONCTION :
G (E a,b : entier) : entier
En dehors des appels récursifs, il
S PÉCIFICATIONS : a, b ∈ N∗ avec y a un nombre fini d’opérations.
a ≤ b. Calcule quelque chose.
a diminue de 1 à chaque appel,
D ÉBUT 1 est un diviseur de b donc le cas
si b mod a = 0 alors de base est atteint en au plus
Renvoyer a a − 1 appels récursifs. Il y a donc
sinon un nombre fini d’appels récursifs.
Renvoyer G(a-1,b) L’algorithme se termine.
fin si;
F IN

Plan
1 Généralités

Motivation
... est un algorithme valide, c’est à dire conforme aux spécifications. Cette
section présente une méthode pour prouver qu’un algorithme est valide.

Validité d’un algorithme itératif
Vocabulaire
équation de récurrence : égalité reliant les valeurs des variables d’une
itération à la suivante ;
invariant de boucle : propriété censée être vraie à chaque itération.
Méthode
1 "lire" les équations de récurrence sur l’algorithme ;
2 chercher un invariant de boucle ;
3 prouver l’invariant par récurrence ou induction ;
4 écrire l’invariant à la fin des itérations.

Premier exemple de preuve de validité
vari : valeur de var à la fin de l’itération i.
F ONCTION :
1 Équation de récurrence :
F1 (E n : entier) : entier res0 = 1 et si i > 0, resi = resi−1 × i.
2 Invariant proposé : Invi : "resi = i!".
S PÉCIFICATIONS : 3 Preuve de l’invariant :
Calcule n! avec n ∈ N Initialisation : Pour i = 0, on a
res0 = 1 = 0! donc Inv0 est vrai.
Variable : res : entier Récurrence : Pour 1≤ i ≤ n, on
suppose Invi−1 vrai, c’est à dire
D ÉBUT resi−1 = (i − 1)!.
res ← 1 D’après les équations de récurrence,
pour i de 1 à n faire resi = resi−1 × i.
res ← res * i Donc resi = (i − 1)! × i = i!.
fin pour; Donc Invi est vrai.
Renvoyer res Conclusion : l’invariant est vrai pour
F IN toutes les itérations.
4 A la fin du pour, la valeur renvoyée est
resn = n! : l’algorithme est valide.
Deuxième exemple de preuve de validité
vari : valeur de var à la fin de l’itération i.
F ONCTION :
Cube (E n : entier) : entier Équations
  derécurrence
 :  
A0 1 Ai+1 Ai + 3
S PÉCIFICATIONS : B0  0 Bi+1  Bi + 2Ai + 1
  =   et 
C0  n Ci+1  = Ci − 1
  
Calcule n3 avec n ∈ N. 
Z0 0 Zi+1 Zi + Ai + Bi
Variable : A, B, C, Z : entier Invariant difficile : "trace" pour n=4 :
itération i Ai Bi Ci Zi
D ÉBUT 0 1 0 4 0
A, B, C, Z ← 1, 0, n, 0 ; 1 4 3 3 1
tant que C > 0 faire 2 7 12 2 8
Z←Z+A+B; 3 10 27 1 27
B←B+A+A+1; 4 13 48 0 64
A, C ← A+3, C-1 ; Invariant
fin tq;  proposé
  : 
Ai 3i + 1
Renvoyer Z Bi  3i 2 
F IN Inv i : 
Ci  = n − i 
  
3
Zi i
Deuxième exemple - suite
1 Équation
 de 
récurrence
  etinvariant
 :     
A0 1 Ai+1 Ai + 3 Ai 3i + 1
B0  0 Bi+1  Bi + 2Ai + 1 Bi  3i 2 
C0  = n et Ci+1  = Ci − 1
ER :        
 Invi : 
Ci  = n − i 
  
Z0 0 Zi+1 Zi + Ai + Bi Zi i3
2 Preuve de l’invariant :      
A0 1 3×0+1
B0  0 3 × 02 
Initialisation : Pour i = 0, 
C0  = n = n − 0
     : Inv0 est vrai.

3
Z0 0 0
  : Pour 0<i ≤ 
Récurrence n, onsuppose Invi vrai. On
 utilise
 ER et Invi :
Ai+1 Ai + 3 3i + 1 + 3 3(i + 1) + 1
Bi+1  Bi + 2Ai + 1 3i 2 + 2(3i + 1) + 1 3(i + 1)2 
Ci+1  = Ci − 1
   =  =  
 n − i − 1  n − (i + 1) 
3 2 3
Zi+1 Zi + Ai + Bi i + 3i + 1 + 3i (i + 1)
Donc Invi+1 est vrai.
Conclusion : l’invariant est vrai pour toutes les itérations.
3 Conclusion : à la fin du TantQue, Ci = 0 = n − i donc i = n.
La valeur renvoyée est Zn = n3 : l’algorithme est valide.
A vous de jouer ! Compléter la preuve
1 Eq. récurrence : res0 =T [0]
F ONCTION : somTab resi+1 =resi + T [i + 1]
(E T : tableau d’entiers) : entier 2 Invariant : Invi : "resi est la somme des
valeurs T [0] à T [i]".
S PÉCIFICATIONS : Renvoie 3 Preuve de l’invariant (n=taille(T )) :
la somme des valeurs de T. Initialisation : pour i = 0,
res0 = T [0] somme des valeurs de
Variable : res : entier T [0] à T [0]. Inv0 est vrai.
Récurrence : on suppose Invi vrai
D ÉBUT pour 0 ≤ i ≤ n − 2.
res ← T[0] Comme resi+1 =resi + T [i + 1]
pour i de 1 à et resi =T [0] + . . . + T [i]
taille(T)-1 faire on a resi+1 =T [0] + . . . + T [i + 1].
res ← res+T[i] Donc Invi+1 est vrai.
fin pour; Conclusion : l’invariant est vrai
Renvoyer res pour toutes les itérations.
F IN 4 A la fin du pour, l’algorithme renvoie
resn−1 = T [0] + . . . + T [n − 1] :
l’algorithme est valide.
Validité d’un algorithme récursif
Vocabulaire
équation de récurrence : égalité reliant le résultat de l’algorithme avec
celui des appels récursifs ;
invariant de récursion : propriété censée être vraie à chaque appel
récursif. Le plus souvent, c’est simplement le résultat principal de
l’algorithme.
Méthode
1 "lire" les équations de récurrence sur l’algorithme ;
2 poser l’invariant de récursion ;
3 prouver l’invariant par récurrence ou induction ;
4 la conclusion de la récurrence prouve l’algorithme.

Exemple de preuve de validité
1 Équation de récurrence :
F 2(0) =1 et F 2(n) = n × F 2(n − 1)
F ONCTION : pour n > 0.
F2 (E n : entier) : entier 2 Invariant proposé :
Invn : "F 2(n) = n!"
S PÉCIFICATIONS : calcule
la factorielle d’un entier n ∈ N.
3 Preuve de l’invariant :
Initialisation : Pour n = 0, on a
D ÉBUT F 2(0) = 1 = 0! donc Inv0 est vrai.
Récurrence : Pour n>0,
si n=0 alors
on suppose Invn−1 vrai,
Renvoyer 1
c’est à dire F 2(n − 1) = (n − 1)!
sinon
Alors F 2(n) = n × F 2(n − 1) =
Renvoyer n*F2(n-1)
n × (n − 1)! = n!.
fin si; Donc Invn est vrai.
F IN Conclusion : pour tout n ∈ N,
F 2(n) = n!
4 L’algorithme est valide.

A vous de jouer ! Compléter la preuve
Équations de récurrence :
si n < a alors F 4(a, n) = 0
et si n ≥ a alors F 4(n) = n + F 4(a, n − 1)
F ONCTION : Invariant :
F4 (E a, n : entier) : entier) Invn : "F 4(a, n) = somme de [a, n]".
Initialisation : Pour n < a, F (a, n) =0.
S PÉCIFICATIONS : Renvoie Comme [a, n] est vide, sa somme vaut 0.
la somme des entiers de [a, n] Donc Inv0 est vrai.
Récurrence : Pour n ≥ a,
D ÉBUT on suppose Invn−1 vrai :
Renvoyer cond(n<a, 0, F 4(a, n − 1) = somme de [a, n − 1].
n+F4(a,n-1)) Comme F 4(a, n) = n + F 4(a, n − 1),
F IN F 4(a, n) est la somme de [a, n].
Donc Invn est vrai.
Conclusion : pour tout n ∈ N,
F 4(a, n) renvoie la somme de [a, n].
L’algorithme est valide.

Plan
1 Généralités

Motivation
... est un algorithme efficace, c’est à dire qu’il effectue un nombre raisonnable
d’opérations et utilise un espace de calcul raisonnable.

Définitions
Définitions
Complexité en temps : nombre d’opérations élémentaires en fonction
des paramètres d’entrée.
Complexité en espace : nombre de données à mémoriser en fonction
des paramètres d’entrée.
Algorithme efficace : algorithme de faible complexité.
Algorithme optimal : algorithme de complexité minimale (impossible de
faire mieux).

Cadre du cours
Ce cours se limite :
à la complexité en temps, appelée abusivement "complexité" ;
au cas où elle s’exprime en fonction d’un entier n "taille de l’entrée" :
taille d’un tableau, longueur d’un entier...
Notation : Tn : complexité pour une taille d’entrée n.

Il effectue les simplifications suivantes :
opérations élémentaires comptées à raison d’une unité par opération
(modèle Word-Ram) ;
majoration du nombre d’opérations ("pire des cas") ;
comparaison de la croissance asymptotique de Tn (= pour de grandes
valeurs de n) avec celle de puissances, exp, log.

Premier exemple
F ONCTION :
F4 (E n : entier) : entier
Variable : som : nombre Nb opérations : 1 affectation,

n itérations composées
D ÉBUT d’1 modulo, 1 comparaison,
som ← 0 1 affectation,1 somme et
pour i de 1 à n faire éventuellement 1 produit.
si i mod 2 = 1 alors Simplification : chaque itération
som ← som + i*i génère entre 4 et 5 opérations.
sinon Complexité : entre 4n + 1 et
som ← som + i
5n + 1
fin si;
fin pour; Ordre de complexité : n.
Renvoyer som
F IN

Deuxième exemple
F ONCTION : F5 (E n : entier) : Nombre d’appels récursifs :

booléen nombre de fois que n peut être
divisé par 2.
S PÉCIFICATIONS : détermine si Pire des cas : n divisé par 2
n ∈ N∗ est une puissance de 2. plusieurs fois jusqu’à tomber sur
1, soit log2 (n) divisions.
D ÉBUT
Nombre d’appels : log2 (n)
si n=1 alors
appels récursifs, log2 (n) + 1 avec
Renvoyer true
le premier.
sinon si n mod 2 = 1 alors
Renvoyer false Nb d’opérations par appel :
sinon 5, sauf le dernier : 1.
Renvoyer F5(n/2) Complexité pire des cas :
fin si; 5log2 (n) + 1
F IN Ordre de complexité : log(n).

Domination de suites numériques
Définitions
Soient Tn et Un deux suites numériques.
Tn domine Un s’il existe C ∈ R et n0 ∈ N tels que ∀n ≥ n0 , Un ≤ CTn .
Tn et Un sont du même ordre si Tn domine Un et Un domine Tn .
Tn domine strictement Un si elle domine Un sans être du même ordre.
Notations de Landau
Tn domine Un : Tn = Ω(Un ) ou Un = O(Tn )
Tn et Un sont du même ordre : Tn = θ(Un ) ou Un = θ(Tn )
Tn domine strictement Un : Tn = ω(Un ) ou Un = o(Tn )
O Ω
o θ ω Non comparable

Domination de suites numériques - propriétés
Propriétés
Soient Tn et Un deux suites strictement positives à partir d’un certain rang.
si Tn /Un a pour limite 0, alors Un domine strictement Tn .
si Tn /Un a une limite finie >0, alors Tn et Un sont du même ordre.
si Tn /Un a pour limite +∞, alors Tn domine strictement Un .
Remarques
Réciproque de la deuxième propriété fausse ;
Deux suites qui ne se dominent pas l’une l’autre sont "non comparables
asymptotiquement".

A vous de jouer
Dire si chaque suite est o, θ, ω des suites de référence.

Tn 1 log(n) n nlog(n) n2 2n n!
2
3n − 6n + 500 ω ω ω ω θ o o
log(50n2 ) ω θ o o o o o
2
2(n ) ω ω ω ω ω ω o
2n − n2 ω ω ω ω ω θ o
(n + 1)! ω ω ω ω ω ω ω

Complexités comparées
Catégories de complexité
Un algorithme est dit :
à coût constant siTn = O(1) (abus de langage) ;
logarithmique si Tn = O(log(n)) ;
linéaire si Tn = θ(n) ;
semi-linéaire si Tn = θ(nlog(n)) ;
quadratique si Tn = θ(n2 ) ;
polynomial si Tn = O(na ) avec a entier naturel ;
exponentiel si Tn = θ(an ) avec a > 1.

Complexités comparées - suite
Propriétés
Croissances comparées : chaque suite est strictement dominée par la
suivante :√
1, log(n), n, n, nlog(n), n2 , n3 , 2n , 3n , n!
tous les logarithmes sont du même ordre de grandeur :
log10 (n) = θ(log2 (n)) = θ(ln(n)) etc.
o, O, ω, Ω, θ sont multiplicatives sur les suites strictement positives :
si a = o(a0 ) et b = o(b0 ) alors ab = o(a0 b0 ) et de même pour O, ω, Ω, θ.

Algorithmes itératifs - boucles imbriquées
Propriété
Si des boucles pour imbriquées contiennent un nombre borné d’opérations
élémentaires, alors leur complexité est du même ordre que le produit du
nombre de valeurs prises par les indices de boucle.
Exemple
D ÉBUT
pour j de 1 à i faire
op élém
fin pour;
fin pour;
F IN
i prend n valeurs = O(n), j prend i valeurs = O(n), donc l’ensemble des deux
boucles a une complexité O(n2 ).

Algorithmes itératifs - calculs de somme
Propriétés
n n n
X n(n + 1) X 2 n(n + 1)(2n + 1) X 3 n2 (n + 1)2
i= ; i = ; i =
2 6 4
i=1 i=1 i=1
Exemple
D ÉBUT
pour j de 1 à i faire
op élém
fin pour;
fin pour;
F IN
n X
i n
X X n(n + 1)
Nombre d’opérations : 1= i= =θ(n2 )
2
i=1 j=1 i=1

A vous de jouer !
Complexités en fonction de n ?
1 Pour i de 1 à n faire 1 Itérations à coût borné,
Pour j de 1 à n faire n valeurs pour les deux pour :
som ← som+1 Tn = θ(n2 )
2 Pour i de 1 à n faire 2 Itérations à coût borné,
Pour j de 1 à n faire n valeurs pour les trois pour :
Pour k de 1 à n faire Tn = θ(n3 )
som ← som+1 3
Pn Pn
Tn = i=1 j=i 2 =
Pn
3 Pour i de 1 à n faire 2 Pi=1 n − i + 1 =
n
Pour j de i à n faire 2 i 0 =1 i 0 = n(n + 1)
som ← som + 1 √
4 i 2 < n équivaut
√ ài < n
4 i ← 0 ; TantQue i²<n faire donc Tn = 2 n
i ← i+1

Algorithmes récursifs - méthode
Méthode pour les algorithmes récursifs

Chercher une équation de récurrence entre la complexité de l’algorithme
et celle de ses appels récursifs ;
Résoudre cette équation.

Algorithmes récursifs - exemple
Exemple
D ÉBUT
si n=0 alors
Renvoyer 1
sinon
Renvoyer n × F 2(n − 1)
fin si;
F IN

T0 = 1
Equation de récurrence :
Tn = 4 + Tn−1 si n > 0
Résolution : Tn = 4n + 1 = θ(n).

A vous de jouer !
Complexité en soustractions ? Compléter le raisonnement
F ONCTION : estPair (E n : entier) : booléen
D ÉBUT
Renvoyer cond(n=0, true, cond(n=1, false, estPair(n-2)))
F IN
Équation de récurrence : T0 =0, T1 =0, si n ≥ 2 alors Tn =1 + Tn−2

Valeurs de Tn : 0, 0, 1, 1, 2, 2, ...
Valeur de Tn en fonction de n : bn/2c.
Ordre : Tn est entre n/2 − 1 et n/2 donc θ(n).

Master Theorem
Master Theorem
Master Theorem : s’il existe quatre entiers a ≥ 0, b > 1, d ≥ 0 et n0 > 0 tels
que, pour tout n ≥ n0 , T (n) ≤ aT (d bn e) + O(nd ), alors
d
si bd > a

 O(n )
d
T (n) = O(n log n) si bd = a
log a
si bd < a

O(n log b )
Remarques
Le M.T. donne un ordre de complexité sans équation de récurrence
lorsque les appels se font avec une taille d’entrée divisée.
a représente le nombre d’appels récursifs dans le corps de l’algorithme,
b l’entier par lequel la taille de l’entrée est divisée à chaque appel,
O(nd ) les opérations de l’algorithme en plus des appels récursifs.

Master Theorem - exemple
Exemple
F ONCTION : F3 (E n, m : entier) :
entier
A partir de n=1 (n0 = 1),
D ÉBUT F3 fait 1 appel récursif (a = 1)
si n=0 alors au rang b n/2 c (b = 2).
Renvoyer 0 En dehors des appels, il effectue
sinon si n mod 2 = 0 alors O(1) = O(n0 ) opérations (d = 0).
Renvoyer 2*F3(n/2,m)
sinon On est dans le cas bd = a donc
Renvoyer Tn = O(n0 log(n)) = O(log(n)) :
n+2*F3((n-1)/2,m) l’algorithme est logarithmique.
fin si;
F IN

A vous de jouer !
Trouver a, b, d et un ordre de complexité
P ROCÉDURE : F (E n : entier)
S PÉCIFICATIONS : n ∈ N
D ÉBUT 2 appels récursifs : a=2

si n 6= 1 alors
au rang b n2 c : b=2
pour i de 0 à n-1 faire
pour j de 0 à n-1 faire autres opérations :
op élém θ(n2 ) : d=2
fin pour; cas bd > a :
fin pour; algorithme en O(n2 ).
F(n div 2)
F(n div 2)
fin si;
F IN

Plan
1 Généralités

Algorithme de recherche linéaire
Principe
Pour chercher un élément e dans un tableau T non trié, on le parcourt case
par case jusqu’à trouver e ou atteindre la fin du tableau.

Algorithme de recherche linéaire
F ONCTION : RechLin(E e : nombre, E T : tableau de nombres) : entier
S PÉCIFICATIONS : Si T contient e, renvoie le premier indice de T qui

contient e. Sinon, renvoie -1.
Variable : i : entier
D ÉBUT
i←0
tant que i<taille(T) et T[i]6=e faire
i ← i+1
fin tq;
si i=taille(T) alors
Renvoyer -1
sinon
Renvoyer i
fin si;
F IN
Complexité de la recherche linéaire
D ÉBUT
i←0
tant que i<n et T[i]6=e faire
i ← i+1
fin tq;
si i=taille(T) alors
Renvoyer -1
sinon
Renvoyer i
fin si;
F IN
Complexité : pire des cas pour e ∈ / T en notant n=taille(T) :

n itérations à coût constant + opérations à coût constant = θ(n).

Algorithme de recherche dichotomique
Principe
Pour chercher un élément e dans un tableau T trié, on compare e à la valeur
au milieu du tableau puis on continue à le chercher dans la bonne moitié du
tableau.

Algorithme de recherche dichotomique
F ONCTION : RechDic (E e : nombre, E T : tableau de nombres) : entier
S PÉCIFICATIONS : T trié. Renvoie le plus petit i tq T[i]=e ou -1.
Variable : deb, mil, fin : entier
D ÉBUT
deb, fin ← 0, taille(T)-1
tant que deb≤fin faire
mil ← (deb+fin) div 2
si T[mil]<e alors
deb ← mil+1
sinon
fin ← mil-1
fin si;
fin tq;
Renvoyer cond(deb<taille(T) et T[deb]=e, deb, -1)
F IN
A vous de jouer !
Trace de l’algorithme T=[1,2,3,3,3,4,6,9,10], e=3 ?
D ÉBUT
si T[mil]<e alors i debi mili fini T [debi ..fini ]
deb ← mil+1 0 0 ? 8 [1,2,3,3,3,4,6,9,10]
sinon 1 0 4 3 [1,2,3,3 ]
fin ← mil-1 2 2 1 3 [ 3,3 ]
fin si; 3 2 2 1
fin tq;
Renvoyer L’algorithme renvoie deb=2.
cond(deb<taille(T) et
T[deb]=e, deb, -1)
F IN

A vous de jouer !
Trace de l’algorithme pour T=[1,2,3,3,3,4,6,9,10] et e=5 ?
D ÉBUT
i debi mili fini T [debi ..fini ]
si T[mil]<e alors
deb ← mil+1 0 0 ? 8 [1,2,3,3,3,4,6,9,10]
sinon 1 5 4 8 [ 4,6,9,10]
fin ← mil-1 2 5 6 5 [ 4 ]
fin si; 3 6 5 5
fin tq; deb = 6 et T [deb] 6= 5 :
Renvoyer l’algorithme renvoie -1.
T[deb]=e, deb, -1)
F IN

Preuve d’arrêt
D ÉBUT
mil ← (deb+fin) div 2 fin-deb+1 est un entier naturel ;
si T[mil]<e alors
deb ← mil+1 il décroît strictement à chaque itération ;
sinon le tant que s’arrête lorsqu’il vaut 0 ou
fin ← mil-1 moins.
fin si; Il y a donc un nombre fini d’itérations.
fin tq; Chaque itération se termine.
Renvoyer Donc l’algorithme se termine.
T[deb]=e, deb, -1)
F IN

Preuve de validité (principe)
Notation : expri : valeur de expr à la fin de
l’itération i ; n : taille(T)
D ÉBUT Equations de récurrence :
deb, fin ← 0, taille(T)-1 mili+1 = (debi + fini ) div 2
tant que deb≤fin faire si T [mili+1 ] < e alors
mil ← (deb+fin) div 2 debi+1 = mili+1 + 1 et fini+1 = fini
si T[mil]<e alors sinon : debi+1 = debi et fini+1 = mili+1 − 1
deb ← mil+1
Invariant (admis) :
sinon 0 . . . debi − 1 . . . fini + 1 . . . n − 1
fin ← mil-1 <e ≥e
fin si;
En sortant du TantQue, deb = fin + 1 :
fin tq; 0 . . . deb − 1 deb . . . n − 1
Renvoyer <e ≥e
cond(deb<taille(T) et soit deb < n et T [deb] = e : alors deb
T[deb]=e, deb, -1) est le premier indice où se trouve e.
F IN sinon, c’est que e ∈/ T.
Dans les deux cas, l’algorithme renvoie le
bon résultat : l’algorithme est valide.
Complexité de l’algorithme dichotomique
Si n est une puissance de 2, dans le

D ÉBUT pire des cas où tout le tableau est <e :
deb, fin ← 0, taille(T)-1 fin − deb + 1 est divisé par 2 à chaque
tant que deb≤fin faire itération jusqu’à 0.
mil ← (deb+fin) div 2 Le nombre d’itérations k vérifie
si T[mil]<e alors n/2k −1 = 1 donc n = 2k −1 donc
deb ← mil+1 k = log2 (n) + 1.
chaque itération fait 7 ou 8 opérations
sinon
donc complexité en θ(log(n)).
fin ← mil-1
fin si; Sinon, 2k < n < 2k +1 :
fin tq; T est "compris" entre un tableau de
Renvoyer taille 2k et un de taille 2k +1 .
Complexité entre θ(log2 (2k )) = θ(k ) et
θ(log2 (2k +1 )) = θ(k + 1) = θ(k ).
T[deb]=e, deb, -1)
k < log2 (n) < k + 1 donc complexité
F IN θ(log(n)).
L’algorithme est logarithmique.

A vous de jouer !
Modifier pour renvoyer le plus grand i tel que T [i] = e
(ou -1 si e ∈
/ T ).
D ÉBUT
D ÉBUT
si T[mil]<e alors
si T[mil]≤e alors
deb ← mil+1
deb ← mil+1
sinon
sinon
fin ← mil-1
fin ← mil-1
fin si;
fin si;
fin tq;
fin tq;
Renvoyer
Renvoyer
cond(deb<taille(T) et T[deb]=e,
cond(fin≥0 et T[fin]=e, fin, -1)
deb, -1) F IN
F IN
0 . . . debi − 1 fini + 1 . . . taille(T ) − 1
0 . . . debi − 1 fini + 1 . . . n − 1 ≤e ... >e
<e ... ≥e
Plan
1 Généralités

Motivation du tri
Motivation
Trier permet de traiter plus efficacement ensuite.
On étudie 2 sortes de tris de tableaux 1D :
par valeurs : les données à trier ne peuvent prendre que certaines
valeurs : tri en Ω(n)
par comparaison : les données sont quelconques : tri en Ω(n log n)
Notation
n : taille du tableau à trier

Borne inférieure d’un tri de tableau
Pour trier un tableau, il faut parcourir toutes ses cases.

Donc sa complexité est au moins n, c’est à dire Ω(n).
Il est possible de faire θ(n), par exemple lorsque les données ne peuvent
prendre que certaines valeurs.
L’ordre de complexité n est donc une borne inférieure pour un tri de
tableau.

Tri par valeurs
P ROCÉDURE : TriValeurs ( ES D ÉBUT

T : tableau de nombre de taille n, Initialiser Cpt avec des 0
E p : entier) pour i de 0 à n-1 faire
Cpt[T[i]] ← Cpt[T[i]] + 1
S PÉCIFICATIONS : Les valeurs fin pour;
de T sont entre 0 et p-1. Trie T. j,k ← 0,0
tant que j<n faire
Variable : si Cpt[k]=0 alors
Cpt : tableau de nombre de taille p k ← k+1
j, k : entier sinon
T[j] ← k ; j ← j+1 ;
Cpt[k] ← Cpt[k]-1
fin si;
fin tq;
F IN
Complexité : θ(p + n) ou θ(n) si p = O(n).

A vous de jouer ! Trace pour p=4 et T=[1, 0, 3, 2, 2, 2]
i j k Cpt T
D ÉBUT
Initialisation :
Initialiser Cpt avec des 0
pour i de 0 à n-1 faire ? ? ? [0,0,0,0] [1,0,3,2,2,2]
Cpt[T[i]] ← Cpt[T[i]] + 1 Boucle pour :
fin pour; 0 ? ? [0,1,0,0] [1,0,3,2,2,2]
j,k ← 0,0 1 ? ? [1,1,0,0] [1,0,3,2,2,2]
tant que j<n faire 2 ? ? [1,1,0,1] [1,0,3,2,2,2]
si Cpt[k]=0 alors Après la boucle pour :
k ← k+1 ? 0 0 [1,1,3,1] [1,0,3,2,2,2]
sinon Boucle tant que :
T[j] ← k ; j ← j+1 ; ? 1 0 [0,1,3,1] [0,0,3,2,2,2]
Cpt[k] ← Cpt[k]-1 ? 1 1 [0,1,3,1] [0,0,3,2,2,2]
fin si; ? 2 1 [0,0,3,1] [0,1,3,2,2,2]
fin tq; A la fin de l’algorithme :
F IN ? 6 3 [0,0,0,0] [0,1,2,2,2,3]

Borne inférieure d’un tri par comparaison
Dans le cas général, on doit comparer les valeurs entre elles pour les
ordonner.
Nombre de comparaisons nécessaires : au moins n log n/4 (preuve dans
le cours) donc complexité Ω(n log n).
Il est possible de faire θ(n log n), par exemple avec le tri fusion.
L’ordre de complexité n log n est donc une borne inférieure d’un tri de
tableau par comparaison.

Tri à bulles
P ROCÉDURE : TriBulles (ES T : tableau de nombres de taille n)
S PÉCIFICATIONS : Trie le tableau T par ordre croissant.
D ÉBUT
pour j de n-1 à i+1 par pas de -1 faire
si T[j]<T[j-1] alors
T[j],T[j-1] ← T[j-1],T[j]
fin si;
fin pour;
fin pour;
F IN
Complexité : θ(n2 ) : ce tri n’est pas optimal.

A vous de jouer ! Trace pour T=[5,6,2,4,3,1]
i j T
P ROCÉDURE : TriBulles (ES
? ? [5,6,2,4,3,1]
T : tableau de nombres de taille n)
0 5 [5,6,2,4,1,3]
0 4 [5,6,2,1,4,3]
S PÉCIFICATIONS : Trie le tableau
0 3 [5,6,1,2,4,3]
T par ordre croissant.
0 2 [5,1,6,2,4,3]
0 1 [1,5,6,2,4,3]
D ÉBUT
Le plus petit est bien placé.
pour j de n-1 à i+1 1 5 [1,5,6,2,3,4]
par pas de -1 faire 1 4 [1,5,6,2,3,4]
si T[j]<T[j-1] alors 1 3 [1,5,2,6,3,4]
T[j],T[j-1] ← 1 2 [1,2,5,6,3,4]
T[j-1],T[j] Les 2 plus petits sont bien placés.
fin si; A la fin :
fin pour; 4 5 [1,2,3,4,5,6]
fin pour;
F IN

Preuve du tri à bulles 1/2
Arrêt : il y a un nombre fini

d’itérations (chaque pour
T : tableau de nombres de taille n)
parcourt un nombre fini de
valeurs) qui se terminent, donc
S PÉCIFICATIONS : Trie le tableau
l’algorithme se termine.
T par ordre croissant.
D ÉBUT Complexité : chaque itération

pour i de 0 à n-2 faire fait entre 4 et 12 opérations et le
pour j de n-1 à i+1 nombre d’itérations vaut
n−2 Xn−1 n−2
par pas de -1 faire X X
1 = n−1−i
si T[j]<T[j-1] alors
i=0 j=i+1 i=0
T[j],T[j-1] ← n−1
T[j-1],T[j]
X
= i0
fin si; i 0 =1
fin pour; n(n − 1)
=
fin pour; 2
F IN ∈ θ(n2 )
donc la complexité est θ(n2 ).
Preuve du tri à bulles 2/2
Validité (preuve complète cf cours) :

T : tableau de nombres de taille n) Invariant : Invi : "à la fin de
l’itération i du 1er pour, les (i+1)
S PÉCIFICATIONS : Trie le tableau plus petites valeurs sont bien
T par ordre croissant. placées."
Initialisation : avant la 1ère
D ÉBUT itération, les 0 premières cases
pour i de 0 à n-2 faire sont triées donc Inv-1 est vrai.
pour j de n-1 à i+1
par pas de -1 faire Hérédité : on suppose Invi vraie
si T[j]<T[j-1] alors et qu’il existe une itération i+1.
T[j],T[j-1] ← La plus petite valeur parmi
T[j-1],T[j] T[i+1..n-1] est échangée jusqu’à
fin si; T[i+1] donc Invi+1 est vrai.
fin pour; Conclusion : A la fin, i=n-2 : les
fin pour; n-1 plus petites valeurs sont à
F IN leur place donc la dernière
aussi : l’algorithme est valide.
Tri fusion
Principe
Algorithme de type "Diviser pour mieux régner" :
On trie chaque moitié du tableau
On fusionne les deux moitiés triées.
Il faut 2 algorithmes : l’algorithme de tri et l’algorithme de fusion

Algorithme de fusion
P ROCÉDURE : fusion (ES T : tableau de nombre, E deb1, fin1, fin2 : entier)
S PÉCIFICATIONS : T[deb1..fin1] et T[fin1+1..fin2] triés. Trie T[deb1..fin2].
Variable : T1, T2 : tab. de fin1-deb1+1 et fin2-fin1 nombres ; i,j : entiers
D ÉBUT
recopier T[deb1..fin1] dans T1 et T[fin1+1..fin2] dans T2
i,j ← 0,0
pour k de deb1 à fin2 faire
si j>=taille(T2) ou (i<taille(T1) et T1[i]<=T2[j])
alors
T[k] ← T1[i] ; i ← i+1
sinon
T[k] ← T2[j] ; j ← j+1
fin si;
fin pour;
F IN
A vous de jouer ! Trace de fusion([2,6,8,4,9], 0, 2, 4)
k i j T1 T2 T
P ROCÉDURE : fusion (ES T:
? 0 0 [2,6,8] [4,9] [?,?,?,?,?]
t. de nb, E deb1,fin1,fin2: entier)
0 1 0 [2,6,8] [4,9] [2,?,?,?,?]
1 1 1 [2,6,8] [4,9] [2,4,?,?,?]
Variable : i,j : entiers ; T1,T2 :
2 2 1 [2,6,8] [4,9] [2,4,6,?,?]
t. de fin1-deb1+1 et fin2-fin1 nb
3 3 1 [2,6,8] [4,9] [2,4,6,8,?]
4 3 2 [2,6,8] [4,9] [2,4,6,8,9]
D ÉBUT
recopier T[deb1..fin1] dans T1

recopier T[fin1+1..fin2] dans T2
i,j 0,0
pour k de deb1 à fin2 faire
si j>=taille(T2) ou
(i<taille(T1) et

T1[i]<=T2[j]) alors
T[k] T1[i] ; i i+1

sinon
T[k] T2[j] ; j j+1
fin si;
fin pour;
F IN
Algorithme de tri fusion
P ROCÉDURE : triFusionAux (ES T : tableau de nombre; E deb, fin : entier)

: tableau de nombre
S PÉCIFICATIONS : Trie T entre les indices deb et fin.
Variable : mil : entier
D ÉBUT
si deb<fin alors
triFusionAux(T,deb,mil)
triFusionAux(T,mil+1,fin)
fusion(T,deb,mil,fin)
fin si;
F IN

A vous de jouer ! Trace de
triFusionAux([5,6,2,4,3,1],0,5)
P ROCÉDURE : triFusionAux
[5,6,2,4,3,1]
(ES T : tableau de nombre; E deb, fin :
entier) : tableau de nombre
[5,6,2] [4,3,1]
Variable : mil : entier [5,6] [2] [4,3] [1]
D ÉBUT [5] [6] [4] [3]

si deb<fin alors
mil (deb+fin) div 2
[5,6] [3,4]
triFusionAux(T,deb,mil)
triFusionAux(T,mil+1,fin) [2,5,6] [1,3,4]
fusion(T,deb,mil,fin)
fin si;
F IN [1,2,3,4,5,6]

Tri fusion : dernière procédure
Quelles valeurs de deb et fin faut-il choisir pour trier tout le tableau ?
deb=0, fin=taille(T)-1
D’où la dernière procédure du tri fusion :
P ROCÉDURE : TriFusion(ES T : tableau de nombres)
S PÉCIFICATIONS : Trie T
D ÉBUT
TriFusionAux(T,0,taille(T)-1)
F IN

Quelques tris célèbres
Tri par insertion : pour k allant de 1 à taille(T)-1, T[k] est inséré parmi
T[0] à T[k-1]. Adapté lorsque les données sont presque triées.
Complexité : θ(n2 ).
Tri par sélection : pour k allant de 0 à taille(T)-2, on cherche le plus petit
élément parmi T[k] à T[taille(T)-1] et on l’échange avec T[k]. Adapté pour
de petits ensembles de données.
Complexité : θ(n2 ).
Tri par tas : On structure les données dans un arbre binaire dont les
nœuds sont partiellement ordonnés ("tas"). Le sommet de l’arbre est le
plus grand élément, on l’extrait et on refait un tas à partir des nœuds
restants.
Complexité : θ(n log n).
Tri rapide ou tri par pivot : on sépare un tableau entre les éléments
plus petits et plus grand qu’un certain élément du tableau ("pivot") et on
trie chaque moitié récursivement.
Complexité : θ(n2 ) dans le pire des cas, θ(n log n) en moyenne.

A vous de jouer !
Donner les étapes de tri du tableau [1, 3, 5, 2, 9, 4, 0] par sélection et par

insertion.
Sélection : [1, 3, 5, 2, 9, 4, 0]
[0, 3, 5, 2, 9, 4, 1]
"pour k allant de 0 à taille(T)-2, [0, 1, 5, 2, 9, 4, 3]
on cherche le plus petit élément [0, 1, 2, 5, 9, 4, 3]
parmi T[k] à T[taille(T)-1] [0, 1, 2, 3, 9, 4, 5]
et on l’échange avec T[k]." [0, 1, 2, 3, 4, 9, 5]
[0, 1, 2, 3, 4, 5, 9]
Insertion : [1, 3, 5, 2, 9, 4, 0]
[1, 3, 5, 2, 9, 4, 0]
"pour k allant de 1 à taille(T)-1, [1, 3, 5, 2, 9, 4, 0]
T[k] est inséré parmi T[0] à T[k-1]." [1, 2, 3, 5, 9, 4, 0]
[1, 2, 3, 5, 9, 4, 0]
[1, 2, 3, 4, 5, 9, 0]
[0, 1, 2, 3, 4, 5, 9]

Deux propriétés des tris
Un tri est stable s’il laisse les éléments égaux dans le même ordre.
utile pour trier successivement selon plusieurs critères ;
exemples : bulles, insertion, fusion ;
sinon, possibilité de mémoriser l’emplacement initial des éléments.
Un tri est en place s’il ne nécessite pas d’espace supplémentaire
important et modifie directement la structure à trier.
important si on dispose de peu de mémoire ;
exemples : bulles, sélection, insertion, tas.

Fin du cours
Merci pour votre attention !

Transparent Algo S 1

Transféré par

Droits d'auteur :

Formats disponibles

Transparent Algo S 1

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Transparent Algo S 1

Transféré par

Droits d'auteur :

Formats disponibles

Algorithmique 1

Sylvain Daudé (UM - FDS) Algorithmique 1 1 / 118

12h cours, 18h TD, 15h TP

Sylvain Daudé (UM - FDS) Algorithmique 1 2 / 118

Cet ouvrage de référence est disponible en ligne gratuitement. Il vous sera

Sylvain Daudé (UM - FDS) Algorithmique 1 3 / 118

3 Arrêt d’un algorithme

4 Validité d’un algorithme

5 Complexité en temps d’un algorithme

6 Algorithmes de recherche dans un tableau

Sylvain Daudé (UM - FDS) Algorithmique 1 4 / 118

3 Arrêt d’un algorithme

4 Validité d’un algorithme

5 Complexité en temps d’un algorithme

6 Algorithmes de recherche dans un tableau

Sylvain Daudé (UM - FDS) Algorithmique 1 5 / 118

Catégorie Nom Paramètres Type du résultat principal

Fonction : facto (E n : entier) : entier

Spécifications : renvoie la factorielle d'un entier naturel n

Variables : produit : entier

produit ← produit * i corps

Sylvain Daudé (UM - FDS) Algorithmique 1 7 / 118

Sylvain Daudé (UM - FDS) Algorithmique 1 8 / 118

F ONCTION : FactIt (E n : entier) : entier

S PÉCIFICATIONS : n ∈ N. Renvoie n! = 1 × 2 × ... × n avec 0! = 1

Variable : res : entier

Sylvain Daudé (UM - FDS) Algorithmique 1 9 / 118

F ONCTION : FactRec (E n : entier) : entier

S PÉCIFICATIONS : n ∈ N. Renvoie n! = 1 × 2 × ... × n avec 0! = 1

Sylvain Daudé (UM - FDS) Algorithmique 1 10 / 118

Type : catégorie d’une valeur : entier, nombre, booléen, tableau...

Sylvain Daudé (UM - FDS) Algorithmique 1 11 / 118

Trouver les types, constantes, variables, appels, opérations,

F ONCTION : PuisIt (E x : nombre,

Sylvain Daudé (UM - FDS) Algorithmique 1 12 / 118

Sylvain Daudé (UM - FDS) Algorithmique 1 13 / 118

Opérateurs de calcul : + - * / ˆ (puissance) div (quotient) mod (reste)

Sylvain Daudé (UM - FDS) Algorithmique 1 14 / 118

Les expressions suivantes sont-elles correctes ?

Sylvain Daudé (UM - FDS) Algorithmique 1 15 / 118

Sylvain Daudé (UM - FDS) Algorithmique 1 16 / 118

Qu’affichent les blocs d’instructions suivants ?

Sylvain Daudé (UM - FDS) Algorithmique 1 17 / 118

Que renvoient les blocs d’instruction suivants ?

Correction : 5 Correction : Rien ! (boucle infinie)

Sylvain Daudé (UM - FDS) Algorithmique 1 19 / 118

Sylvain Daudé (UM - FDS) Algorithmique 1 20 / 118

Qu’affichent les blocs d’instruction suivants ?

Sylvain Daudé (UM - FDS) Algorithmique 1 21 / 118

3 Arrêt d’un algorithme

4 Validité d’un algorithme

5 Complexité en temps d’un algorithme

6 Algorithmes de recherche dans un tableau

Sylvain Daudé (UM - FDS) Algorithmique 1 22 / 118

Sylvain Daudé (UM - FDS) Algorithmique 1 23 / 118

Sylvain Daudé (UM - FDS) Algorithmique 1 24 / 118

Ecrire la valeur du tableau T après les étapes suivantes

Sylvain Daudé (UM - FDS) Algorithmique 1 25 / 118

Sylvain Daudé (UM - FDS) Algorithmique 1 26 / 118

Création : T=[4,6,17] ou T=[0]3 ou T=[ii for i in range(n)]