ALGORITHMIQUE, cours 1
Introduction
• Selon le Petit Robert : "ensemble des règles opératoires propres à
un calcul.”
• Un peu plus précisement : Une séquence de pas de calcul qui
prend un ensemble de valeurs comme entrée (input) et produit un
ensemble de valeurs comme sortie (output).
• Un algorithme résout toujours un problème de calcul. L’énoncé
du problème spécifie la relation input / output souhaitée.
Exemples :
1. Multiplication
Input : deux entiers a et b
Output : leur produit ab
Algorithme : celui de l’école
2. Plus Grand Commun Diviseur (PGCD)
Input : deux entiers a et b
Output : pgcd(a,b)
Algorithme : celui d’Euclide
3. Primalité
Input : un entier a
Question : a est-il un entier premier?
Cas spécial : problème de décision - output = réponse oui/non à une
question.
Donner une définition précise de la notion d’algorithme est assez
difficile et complexe.
Il existe plusieurs définitions mathématiques depuis les années 30.
exemples :
• fonctions récursives
• -calcul
• machines de Turing
• RAM
Fait :
Toutes ces définitions sont équivalentes
Thèse de Church :
Tout ce qui est calculable intuitivement est aussi
calculable par les objets formels ci-dessus
Mais :
Il existe des problèmes non calculables (indécidables)
exemple :
Problème de l’arrêt
Input : Un algorithme (programme) A et un input I
Output : A termine-t-il pour I?
preuve de l’indecidabilité (par l’absurde)
Supposons que le problème de l’arrêt soit décidable.
Cela signifie alors qu’il existe un programme B qui décide si un programme
s’arrête. Définissons maintenant le programme C suivant:
– C s’arrête quand le programme qu’il prend en entrée ne s’arrête pas.
– C ne s’arrête pas quand le programme qu’il prend en entrée s’arrête.
Bien sûr, un tel programme ne peut pas exister car si on l’utilise sur lui même, on
obtient une contradiction. Et donc le problême de l’arrêt est indécidable.
(Random Access Machine : machine à accès
aléatoire)
Dans ce cours, on étudie seulement des problèmes pour lesquels il
existe des algorithmes.
En fait, on s’intéressera aux problèmes pour lesquels il existe des
algorithmes efficaces.
Un exemple typique de problème décidable pour lequel il n’y a pas
d’algorithme efficace : le jeu d’échec (nombre de configurations est
environ 10 puissance 50)
On veut une mesure pour comparer des algorithmes
On voudrait que la complexité :
• ne dépende pas de l’ordinateur
• ne dépende pas du langage de programmation
• ne dépende pas du programmeur
• ... etc ...
• soit indépendante des détails
de l’implémentation
On choisit de travailler sur un modèle d’ordinateur :
RAM:
• ordinateur idéalisé
• mémoire infinie
• accès à la mémoire en temps constant
Le langage de programmation sera un pseudo-PASCAL.
Pour mesurer la complexité en temps on choisit une opération
fondamentale pour le problème de calcul particulier, et on calcule
le nombre d’opérations fondamentales exécutées par l’algorithme.
Le choix est bon si le nbre total d’opérations est proportionnel au
nbre d’opérations fondamentales.
Le temps de l’exécution dépend de la taille de l’entrée. On veut
considérer seulement la taille essentielle de l’entrée.
Cela peut être par exemple :
• le nombre d’éléments combinatoires dans l’entrée
• le nombre de bits pour représenter l’entrée
• ... etc ...
Soit A un algorithme
Dn l’ensemble des entrées de taille n
I 2 Dn une entrée
définition :
1. coutA(I) = le nbre d’op. fondamentales exécutées par A sur I
2. la complexité de A en pire cas :
MaxA(n) = Max{coutA(I); I 2 Dn}
Soit Pr une distribution de probabilités sur Dn
RECHERCHE
Input : L,n,x ; où L est un tableau [1, . . . ,n] et x est l’élément recherché
Output : l’indice de x dans L (0 si x 62 L)
Algorithme : Recherche Séquentielle (RS)
var L : array [1, . . . ,n] of element;
x : element;
j : integer;
begin
j:=1;
while j n and L[j]6=x do begin
j:=j+1;
end { while }
if j>n then j:=0;
end
complexité en pire cas de RS :
MaxRS(n) = n
complexité en moyenne de RS :
On suppose que :
• tous les éléments sont distincts
• Pr[x 2 L] = q
• si x 2 L alors toutes les places sont équiprobables
Pour 1 i n soit
Ii = {(L,x) : L[i] = x} et In+1 = {(L,x) : x 62 L}
Exercice Ecrire un algorithme pour trouver la médiane de trois entiers. (Par
définition, la médiane de 2k - 1 éléments est le keme plus grand).
– Combien de comparaisons fait votre algorithme en pire cas?
– En moyenne?
– Quel est la complexité de ce problème?
Exercice Ecrire un algorithme pour trouver la médiane de trois entiers. (Par
définition, la médiane de 2k - 1 éléments est le keme plus grand).
– Combien de comparaisons fait votre algorithme en pire cas?
– En moyenne?
– Quel est la complexité de ce problème?
Pr[Ii] = q
n pour 1 i n et coutRS(Ii) = i
Pr[In+1] = 1 - q et coutRS(In+1) = n
Opération de base : comparaison de x avec un élément de L.
Exercice Ecrire un algorithme pour trouver la médiane de trois entiers. (Par
définition, la médiane de 2k - 1 éléments est le keme plus grand).
– Combien de comparaisons fait votre algorithme en pire cas?
– En moyenne?
– Quel est la complexité de ce problème?
Exercice Ecrire un algorithme pour trouver la médiane de trois entiers. (Par
définition, la médiane de 2k - 1 éléments est le keme plus grand).
– Combien de comparaisons fait votre algorithme en pire cas?
– En moyenne?
– Quel est la complexité de ce problème?
définition :
O(f) = {g : 9c 2 R+,9n0 2 N+,8n n0, g(n) c · f(n)}
On dit que "g est dans grand O de f”.
exemples :
f(n) =
n3
2
g1(n) = n2 + 17n + 15 g2(n) = 5n3
• g1 2 O(f) : on prend n0 = 1 et c = 2(1 + 17 + 15) et
alors n2 + 17n + 15 c · n3
2 si n 1
• g2 2 O(f) : on choisit c = 10 et alors 5n3 10 · n3
2
• f 2 O(g2)
• f 62 O(g1) sinon n3
2 c · n2 + 17c · n + 5c et donc
si n est grand on a n
2 c + 2 ce qui est impossible.
Attention : les fonctions peuvent être incomparables au sens du
O
Exercice Donner un exemple de deux fonctions f et g telles que
f 62 O(g) et g 62 O(f).
définition :
(f) = {g : 9c > 0,9n0 2 N+,8n n0 g(n) c · f(n)}
proposition 1 :
g 2 O(f) , f 2
(g)
preuve :
g(n) c · f(n) , f(n)
1
c
· g(n)
définition :
(f) = O(f) \
(f)
proposition 2 :
(f) = {g : 9c1,c2,9n0 2 N+,8n n0 c1·f(n) g(n) c2·f(n)}
(f) est appelé l’ordre exact ou ordre de grandeur de f.
proposition 3 :
La relation f R g si f 2 (g) est une relation d’équivalence.
Exercice
1. L’ordre exact de la fonction 3n2 + 10n log n + 100 est:
1. (n log n)
2. (n3)
3. (n2)
4. (log n)
2. Soient 0 < a < b deux constantes. On a:
1. (loga n) < (logb n)
2. (loga n) = (logb n)
3. (loga n) > (logb n)
4. (loga n) et (logb n) sont incomparables
Exercice
• Montrer que
(f + g) = (Max{f,g}).
• Soit p(n) = aknk + . . . + a1n + a0 un polynôme de degré k. Montrer que
p(n) 2 (nk).
Exercice
Supposons que f(n) 2 (g(n)). Est-ce qu’il est vrai que 2f(n) 2 (2g(n))?
Dans le cas affirmatif prouvez le, sinon donnez un contre-exemple.
définition :
On définit de la façon suivante l’ordre partiel sur l’ordre de
grandeur des fonctions :
(f) (g) si f 2 O(g)
On a alors:
(f) = (g) si f 2 (g)
(f) < (g) si f 2 O(g)etg 62 O(f)
Enumerer en ordre croissant l’ordre exact des fonctions suivantes:
n, 2n, n log n, ln n, n + 7n5, log n,
p
n, en, 2n-1, n2, n2 +
log n, log log n, n3, (log n)2, n!, n3/2.
(log et ln dénotent respectivement la fonction de logarithme en base de 2 et en
base de e.)
proposition 4 : (admise)
• lim
n!1
g
f
= c > 0 alors g 2 (f)
• lim
n!1
g
f
= 0 alors g 2 O(f) et f 62 O(g)
( (g) < (f))
• lim
n!1
g
f
= +1 alors f 2 O(g) et g 62 O(f)
( (f) < (g))
On va comparer les algorithmes selon l’ordre de grandeur de
leur complexité.
définition :
La complexité C(n) d’un problème P est la complexité du meilleur
algorithme qui résoud P.
• Si un algorithme A résoud P en temps f(n)
alors C(n) 2 O(f)
• Si l’on prouve que tt algorithme qui résoud P travaille en
temps au moins g(n) alors C(n) 2
(g)
• Si f 2 (g) alors C(n) 2 (f) = (g) et c’est la
complexité du problème
Exercice
1. Supposons que
lim
n!1
f(n)
g(n)
= 1.
1. On a toujours (f) < (g)
2. On a toujours (f) = (g)
3. On a toujours (f) > (g)
4. (f) et (g) peuvent être incomparables
2. Supposons que (f) = (g). Est-ce que limn!1
f(n)
g(n)
1. existe toujours et = 1
2. existe toujours et = 0
3. existe toujours et = c, où c est une constante positive
4. n’existe pas toujours.
Exercice
Montrer que est une relation d’équivalence.
Un rapide rappel
Rappel
Un arbre est un graphe non-orienté acyclique et connexe
Définition
Un arbre enraciné (rooted tree) est un arbre avec un sommet
distingué.
Le sommet distingué s’appelle la racine (root) de l’arbre.
Définition
Soit T = (V,E) un arbre enraciné au sommet r, x un sommet de T.
• si {y,x} est une arête de T et y est un ancêtre de x, alors y est
le père de x, et x est un fils de y.
• la racine de l’arbre n’a pas de père. si x et y ont le même père,
alors ils sont frêres.
• un sommet sans fils est un sommet externe ou feuille (leaf). les
autres sommets sont les sommets internes
• le nombre de fils d’un sommet x est le degré de x.
Définition
La profondeur du sommet x est la longueur de la chaine entre la
racine et le sommet x.
La hauteur (ou profondeur) de l’arbre est :
Max
x2V
{profondeur(x)}
Les arbres binaires sont définis récursivement.
Définition
un arbre binaire est une structure sur un ensemble fini de sommets.
Il est :
• soit vide (ne contient pas de sommet)
• soit l’union de 3 ensemble disjoints de sommets :
• un sommet appelé racine
• un arbre binaire : le sous-arbre gauche
• un arbre binaire : le sous-arbre droit
La racine d’un sous-arbre gauche non vide est appelé le fils gauche
de la racine de l’arbre.
Définition
Soit a un réel non négatif.
bac est le plus grand entier qui est a.
dae est le plus petit entier qui est a.
exemples
b c = 3
d e = 4
b5c = d5e = 5
notation
log désigne le logarithme en base 2.
Théorème 1
La profondeur d’un arbre binaire à n sommets est au moins blog nc
Preuve
a. A la profondeur l, il y a au plus 2l sommets dans l’arbre.
Parce que : c’est vrai à la profondeur 0, et si c’est vrai à la profondeur l - 1, à la
profondeur l il y a au plus 2 fois autant de sommets, donc au plus 2l.
b. Un arbre binaire de profondeur d a au plus 2d+1 - 1 sommets.
Parce que: on somme les sommets selon leur profondeur.
et alors : Nombre de sommets
Pd
l=0 2l = 2d+1 - 1
c. Soit d la profondeur de l’arbre. On suppose que d < blog nc, alors
d blog nc - 1. Il vient que n 2blog nc - 1 2log n - 1 < n ce qui est une
contradiction.
TRI (sorting)
Input : Une liste de n entiers (a1,a2, . . . ,an)
Output : Une permutation (a0
1,a0
2, . . . ,a0
n) de la liste d’entrée telle
que a0
1 a0
2 . . . a0
n ou a0
1 a0
2 . . . a0
n.
Souvent les entiers sont une partie d’une donnée plus complexe,
l’entier est alors la clé de la donnée. Et on triera les données d’après
les clés.
La structure de donnée est une liste A à n éléments avec A[i] = ai
au début et A[i] = a0
i à la fin.
L’opération de base pour les algorithmes de tri est la comparaison :
A[i] : A[j], c’est la seule opération permise sur les clés.
Tri par selection
Idée :
On recherche le minimum de la liste et on le met en première
position, et on recommence sur la fin de la liste où l’on a ajouté
l’élément qui se trouvait en première place.
Après le k-ième placement, les k plus petits éléments de la liste
sont à leur place définitive.
Exemple :
Input : 101 115 30 63 47 20
selection de 20
Placement : 20 115 30 63 47 101
selection de 30
Placement : 20 30 115 63 47 101
selection de 47
Placement : 20 30 47 63 115 101
selection de 63
Placement : 20 30 47 63 115 101
selection de 101
Placement : 20 30 47 63 101 115
output : 20 30 47 63 101 115
procedure TRI-SELECTION
Input :
A: array [1..n] of integer
var i, j, k : integer
begin
i :=1
while i<n do begin { i-ème placement }
j:=i
for k:=i+1 to n do
if A[k]<A[j] then j:=k
A[j]$A[i] { placement du minimum }
end
end
Complexité
• Nombre de comparaisons en itération i :
(n - i + 1) - 1 = n - i
Tri par insertion (séquentielle)
Idée :
• On fait n itérations.
• Après l’itération (i - 1) les premiers (i - 1) éléments de la liste
sont triés.
• A l’itération i on insère d’une manière séquentielle le i-ème
élément parmi les premiers (i - 1) éléments.
Exemple :
Input : 101 115 30 63 47 20
Itération 1 : 101 115 30 63 47 20
Itération 2 : 101 115 30 63 47 20
Itération 3 : 30 101 115 63 47 20
Itération 4 : 30 63 101 115 47 20
Itération 5 : 30 47 63 101 115 20
Itération 6 : 20 30 47 63 101 115
output : 20 30 47 63 101 115
procedure TRI-INSERTION
Input :
A: array [1..n] of integer
var i, x, k : integer
begin
for i:=2 to n do begin
k:=i-1 ; x:=A[i]
while A[k]>x do begin
A[k+1]:=A[k] ; k:=k-1 end
A[k+1]:=x
end
end
Complexité
• Nombre de comparaisons à l’itération i :
au plus i
On considère la méthode suivante,
réalisant le tri par insertion d’un tableau T à N éléments,
numérotés de 1 à N :
– pour chaque i 2 [ 2, . . . ,N ],
– j := i - 1.
– tant que (j > 0) et T[j] > T[j + 1],
– échanger les contenus de T[j] et T[j + 1].
– j := j - 1.
Rappelons que dans le pire des cas, le nombre d’échanges
nécessaires est égal à 1 + 2 + . . . (N - 1) = N(N-1)
2 .
Exercice 1
Soient (a1, . . . ,ap) et (b1, . . . ,bp) deux suites d’entiers dont les
éléments sont triés
par ordre croissant. Soit T = (a1,b1,a2,b2, . . . ,ap,bp).
Démontrer, par récurrence sur p, que le tri par insertion de T
nécessite, dans le pire des cas,
seulement p(p+1)
2 échanges.
Exercice 2
On considère à présent un tableau T arbitraire
de taille n = 2 × p, et l’on considère la méthode suivante :
– trier sur place, par insertion, le sous-tableau de T d’indices
paires,
– trier sur place, par insertion, le sous-tableau de T d’indices
impaires,
– trier, par insertion, le tableau T résultant.
Quel est, dans le pire des cas, le coût de ce tri? Comparer la valeur
obtenue avec celle
du tri par insertion simple. Est-elle meilleure ou pire?
Tri rapide (quicksort)
Idée :
On partage la liste à trier en deux sous-listes telles que tous les
éléments de la première soient plus petits que les éléments de la
seconde. Par récurrence, on trie les deux sous-listes.
Comment partager la liste en deux?
On choisit une des clés de la liste, et on l’utilise comme pivot.
La liste d’origine est donc coupée en trois : une première liste (à
gauche) composée des éléments au pivot, le pivot (à sa place
définitive) et une liste (à droite ) composée des éléments > au pivot.
Notre choix : le pivot est le premier élément de la liste.
Supposons qu’on a une procédure PARTITION(A,i,j,k) qui effectue
la partition de la sous-liste de A entre les indices i et j, en fonction
du pivot A[i], et rend comme résultat l’indice k, où ce pivot a été
placé.
Avec cette procédure, on peut écrire une procédure TRI-RAPIDE.
procedure TRI-RAPIDE
Input :
A: array [1..n] of integer
i, j : integer
var k : integer
begin
if i<j then begin
PARTITION(A,i,j,k)
TRI-RAPIDE(A,i,k-1)
TRI-RAPIDE(A,k+1,j)
end
end
procedure PARTITION
Input : A: array [1..n+1] of integer
i, j, k : integer
var l : integer
begin
l:=i+1; k:=j
while l<=k do begin
while A[l]<=A[i] do l:=l+1
while A[k]>A[i] do k:=k-1
if l<k then do begin
A[l]$A[k]; l:=l+1; k:=k-1; end
end
A[i]$A[k]
end
Complexité
• Complexité en pire cas : (n2)
En effet, le pire cas se produit lorsqu’une des partitions est vide et
l’autre est de taille n - 1.
Dans ce cas, on a :
t1 = 1
tn = tn-1 + n
Et la solution de cette équation de récurrence est : n2
Complexité
• Complexité en meilleur cas : (n × log(n))
En effet, le meilleur cas se produit lorsque les deux partitions sont
de même taille.
Dans ce cas, on a :
t1 = 1
tn = 2tn/2 + n
Et la solution de cette équation de récurrence est : n × log(n) + n
Tri Fusion
Le principe
En appliquant la méthode diviser pour régner au problème du tri
d’un tableau, on obtient facilement le tri par fusion.
On appelle ce tri mergesort en anglais.
Le principe est de diviser une table de longueur n en deux tables de
longueur n/2, de trier récursivement ces deux tables, puis de
fusionner les tables triées.
Le principe
Première phase : Découpe :
1. Découper le tableau en 2 sous-tableaux égaux (à 1 case près)
2. Découper chaque sous-tableau en 2 sous-tableaux égaux
3. Ainsi de suite, jusqu’à obtenir des sous-tableaux de taille 1
Le principe
Deuxième phase : Tri/fusion :
1. Fusionner les sous-tableaux 2 à 2 de façon à obtenir des
sous-tableaux de taille 2 triés
2. Fusionner les sous-tableaux 2 à 2 de façon à obtenir des
sous-tableaux de taille 4 triés
3. Ainsi de suite, jusqu’à obtenir le tableau entier
Exercice
• Donner un code, dans le langage que vous voulez, qui
implémente le Tri Fusion.
• Dérouler votre code sur la liste d’entiers :
3 6 78 32 5 1 10 23 9 11 33
Exercice : complexité
Quelle est la complexité du Tri Fusion?
Tri à Bulle
Le principe
• On compare les éléments deux à deux de la gauche vers la droite,
en les échangeant pour les classer quand c’est nécessaire.
• Quand on arrive à la fin de la liste, on recommence, jusqu’à ce
que la liste soit classée.
• On détecte que la liste est classée quand on a fait un passage sans
Exercice
• Ecrire une procédure Tri-Bulle
• Dérouler l’algorithme sur la liste :
2 4 7 5 3 1
Combien avez vous fait de comparaisons?
Variantes :
• Tri Boustrophedon
• Tri Shuttle
TRI PAR TAS (HEAPSORT)
Idée :
On sélectionne les minimums successifs en utilisant une structure
de donnée particulière : le tas
Définition
Un arbre parfait est un arbre binaire dont les feuilles sont situées sur
deux niveaux successifs : l’avant dernier niveau est complet, et les
feuilles du dernier niveau sont regroupées le plus à gauche possible.
Définition
Un arbre parfait partiellement ordonné est un arbre parfait dont les
sommets sont étiquetés par des éléments à trier, et tel que l’élément
associé à chaque sommet est aux éléments associés aux fils de ce
sommet.
Définition
Un tas (heap) est un tableau t représentant un arbre parfait
partiellement ordonnée selon les règles suivantes :
• t[1] est la racine
• t[2i] et t[2i + 1] sont les fils gauche et droite de t[i] (s’ils
existent)
Exemple 3 5 9 6 8 11 10 12 18 14
Propriétés simples d’un tas
• t[bi/2c] est le père de t[i] (i 2)
• Si le nombre de sommets n est pair, alors t[n/2] a un seul fils
t[n]
• Si i > bn/2c, alors t[i] est une feuille
Idée du tri par tas
I. On construit le tas
II. On enlève successivement le minimum du tas et on reconstruit
CONSTRUCTION DU TAS
L’essentiel est une procédure AJOUT qui ajoute un élément
nouveau à un tas.
On ajoute cet élément comme une feuille (au dernier niveau), puis
on l’échange avec son père tant qu’il est inférieur à celui-ci.
la structure de tas sur le reste des éléments
procedure AJOUT
Input : t : array [1..n] of integer ; p, x : integer {la procédure ajoute l’élément x
dans le tas t qui contient p éléments}
var i : integer
begin
if p<n then begin {on place x à la dernière feuille}
p:=p+1 ; t[p]:=x ; i:=p ;
{on échange tant que x est < que son père}
while i>1 and t[i] < t[bi/2c] do begin
t[i] $ t[bi/2c] ; i := bi/2c
end
end
else writeln(“débordement du tas”)
end
Complexité en pire cas
La procédure AJOUT fait au plus blogpc comparaisons.
Pourquoi?
Parce que la hauteur d’un arbre parfait à p sommets est blog pc.
SUPPRESSION DU MINIMUM ET REORGANISATION DU
TAS
La procédure DESTRUCTION remplace la racine du tas par la
dernière feuille.
Pour réorganiser le tas, on échange cet élément avec le plus petit de
ses deux fils tant qu’il est supérieur à celui-ci.
procedure DESTRUCTION
Input :
t : array [1..n] of integer
p, min : integer
{DESTRUCTION retourne dans min le minimum des p éléments du tas et
réorganise le tas}
var i, j : integer
begin
min:=t[1] {retour du minimum}
t[1] := t[p] ; p:=p-1 {nouvelle taille du tas}
i:=1 {réorganisation du tas}
while i bp/2c do begin
{calcul de l’indice du plus petit des deux fils de t[i], ou de son seul fils}
if 2i=n or t[2i] < t[2i + 1] then j:=2i else j:=2i+1
{échange entre deux éléments qui sont père et fils}
if t[i] > t[j] then begin t[i] $ t[j] ; i:=j end
else exit
end
end
Complexité de DESTRUCTION en pire cas :
2[log p]
L’algorithme TRI-TAS
• On ajoute successivement chacun des n éléments dans le tas
t[1 . . . p], p augmente de 1 après chaque adjonction. A la fin on a un
tas de taille n.
• Tant que p > 1, on supprime le minimum du tas, on décroit p de
1, et on range le minimum à la (p + 1)eme place. Puis on
réorganise le tas. t[p + 1 . . . n] contient les n - p plus petits
éléments en ordre décroissant.
procedure TRI-TAS
Input : t : array [1..n] of integer
var p, min : integer
begin
p:=0
while p < n do {construction du tas}
AJOUT(t,p,t[p+1]);
{p augmente de 1 à chaque appel}
while p > 1 do begin
DESTRUCTION(t,p,min)
{p diminue de 1 à chaque appel}
t[p+1]:=min
end
end
Exercice
Trier le tableau suivant en utilisant l’algorithme TRI-RAPIDE:
1 21 5 34 32 67 6 0 200 25 65 4 24 33.
Quel est le nombre de comparaisons utilisées?
Exercice
Quelle est la valeur retournée par la procédure PARTITION quand tous les
éléments dans le tableau A[i..j] ont la même valeur?
Exercice
On se donne un tableau de n éléments qui ont chacun une couleur soit rouge, soit
blanc. On veut obtenir un tableau avec deux zones: à gauche tous les éléments
rouges, à droite tous les éléments blancs.
Ecrivez une procédure qui réalise cette organisation du tableau en ne testant
qu’une seule fois la couleur de chaque élément. Essayez de minimiser le nombre
moyen des échanges d’éléments. Calculez ce nombre.
FIN.
Introduction
• Selon le Petit Robert : "ensemble des règles opératoires propres à
un calcul.”
• Un peu plus précisement : Une séquence de pas de calcul qui
prend un ensemble de valeurs comme entrée (input) et produit un
ensemble de valeurs comme sortie (output).
• Un algorithme résout toujours un problème de calcul. L’énoncé
du problème spécifie la relation input / output souhaitée.
Exemples :
1. Multiplication
Input : deux entiers a et b
Output : leur produit ab
Algorithme : celui de l’école
2. Plus Grand Commun Diviseur (PGCD)
Input : deux entiers a et b
Output : pgcd(a,b)
Algorithme : celui d’Euclide
3. Primalité
Input : un entier a
Question : a est-il un entier premier?
Cas spécial : problème de décision - output = réponse oui/non à une
question.
Donner une définition précise de la notion d’algorithme est assez
difficile et complexe.
Il existe plusieurs définitions mathématiques depuis les années 30.
exemples :
• fonctions récursives
• -calcul
• machines de Turing
• RAM
Fait :
Toutes ces définitions sont équivalentes
Thèse de Church :
Tout ce qui est calculable intuitivement est aussi
calculable par les objets formels ci-dessus
Mais :
Il existe des problèmes non calculables (indécidables)
exemple :
Problème de l’arrêt
Input : Un algorithme (programme) A et un input I
Output : A termine-t-il pour I?
preuve de l’indecidabilité (par l’absurde)
Supposons que le problème de l’arrêt soit décidable.
Cela signifie alors qu’il existe un programme B qui décide si un programme
s’arrête. Définissons maintenant le programme C suivant:
– C s’arrête quand le programme qu’il prend en entrée ne s’arrête pas.
– C ne s’arrête pas quand le programme qu’il prend en entrée s’arrête.
Bien sûr, un tel programme ne peut pas exister car si on l’utilise sur lui même, on
obtient une contradiction. Et donc le problême de l’arrêt est indécidable.
(Random Access Machine : machine à accès
aléatoire)
Dans ce cours, on étudie seulement des problèmes pour lesquels il
existe des algorithmes.
En fait, on s’intéressera aux problèmes pour lesquels il existe des
algorithmes efficaces.
Un exemple typique de problème décidable pour lequel il n’y a pas
d’algorithme efficace : le jeu d’échec (nombre de configurations est
environ 10 puissance 50)
On veut une mesure pour comparer des algorithmes
On voudrait que la complexité :
• ne dépende pas de l’ordinateur
• ne dépende pas du langage de programmation
• ne dépende pas du programmeur
• ... etc ...
• soit indépendante des détails
de l’implémentation
On choisit de travailler sur un modèle d’ordinateur :
RAM:
• ordinateur idéalisé
• mémoire infinie
• accès à la mémoire en temps constant
Le langage de programmation sera un pseudo-PASCAL.
Pour mesurer la complexité en temps on choisit une opération
fondamentale pour le problème de calcul particulier, et on calcule
le nombre d’opérations fondamentales exécutées par l’algorithme.
Le choix est bon si le nbre total d’opérations est proportionnel au
nbre d’opérations fondamentales.
Le temps de l’exécution dépend de la taille de l’entrée. On veut
considérer seulement la taille essentielle de l’entrée.
Cela peut être par exemple :
• le nombre d’éléments combinatoires dans l’entrée
• le nombre de bits pour représenter l’entrée
• ... etc ...
Soit A un algorithme
Dn l’ensemble des entrées de taille n
I 2 Dn une entrée
définition :
1. coutA(I) = le nbre d’op. fondamentales exécutées par A sur I
2. la complexité de A en pire cas :
MaxA(n) = Max{coutA(I); I 2 Dn}
Soit Pr une distribution de probabilités sur Dn
RECHERCHE
Input : L,n,x ; où L est un tableau [1, . . . ,n] et x est l’élément recherché
Output : l’indice de x dans L (0 si x 62 L)
Algorithme : Recherche Séquentielle (RS)
var L : array [1, . . . ,n] of element;
x : element;
j : integer;
begin
j:=1;
while j n and L[j]6=x do begin
j:=j+1;
end { while }
if j>n then j:=0;
end
complexité en pire cas de RS :
MaxRS(n) = n
complexité en moyenne de RS :
On suppose que :
• tous les éléments sont distincts
• Pr[x 2 L] = q
• si x 2 L alors toutes les places sont équiprobables
Pour 1 i n soit
Ii = {(L,x) : L[i] = x} et In+1 = {(L,x) : x 62 L}
Exercice Ecrire un algorithme pour trouver la médiane de trois entiers. (Par
définition, la médiane de 2k - 1 éléments est le keme plus grand).
– Combien de comparaisons fait votre algorithme en pire cas?
– En moyenne?
– Quel est la complexité de ce problème?
Exercice Ecrire un algorithme pour trouver la médiane de trois entiers. (Par
définition, la médiane de 2k - 1 éléments est le keme plus grand).
– Combien de comparaisons fait votre algorithme en pire cas?
– En moyenne?
– Quel est la complexité de ce problème?
Pr[Ii] = q
n pour 1 i n et coutRS(Ii) = i
Pr[In+1] = 1 - q et coutRS(In+1) = n
Opération de base : comparaison de x avec un élément de L.
Exercice Ecrire un algorithme pour trouver la médiane de trois entiers. (Par
définition, la médiane de 2k - 1 éléments est le keme plus grand).
– Combien de comparaisons fait votre algorithme en pire cas?
– En moyenne?
– Quel est la complexité de ce problème?
Exercice Ecrire un algorithme pour trouver la médiane de trois entiers. (Par
définition, la médiane de 2k - 1 éléments est le keme plus grand).
– Combien de comparaisons fait votre algorithme en pire cas?
– En moyenne?
– Quel est la complexité de ce problème?
définition :
O(f) = {g : 9c 2 R+,9n0 2 N+,8n n0, g(n) c · f(n)}
On dit que "g est dans grand O de f”.
exemples :
f(n) =
n3
2
g1(n) = n2 + 17n + 15 g2(n) = 5n3
• g1 2 O(f) : on prend n0 = 1 et c = 2(1 + 17 + 15) et
alors n2 + 17n + 15 c · n3
2 si n 1
• g2 2 O(f) : on choisit c = 10 et alors 5n3 10 · n3
2
• f 2 O(g2)
• f 62 O(g1) sinon n3
2 c · n2 + 17c · n + 5c et donc
si n est grand on a n
2 c + 2 ce qui est impossible.
Attention : les fonctions peuvent être incomparables au sens du
O
Exercice Donner un exemple de deux fonctions f et g telles que
f 62 O(g) et g 62 O(f).
définition :
(f) = {g : 9c > 0,9n0 2 N+,8n n0 g(n) c · f(n)}
proposition 1 :
g 2 O(f) , f 2
(g)
preuve :
g(n) c · f(n) , f(n)
1
c
· g(n)
définition :
(f) = O(f) \
(f)
proposition 2 :
(f) = {g : 9c1,c2,9n0 2 N+,8n n0 c1·f(n) g(n) c2·f(n)}
(f) est appelé l’ordre exact ou ordre de grandeur de f.
proposition 3 :
La relation f R g si f 2 (g) est une relation d’équivalence.
Exercice
1. L’ordre exact de la fonction 3n2 + 10n log n + 100 est:
1. (n log n)
2. (n3)
3. (n2)
4. (log n)
2. Soient 0 < a < b deux constantes. On a:
1. (loga n) < (logb n)
2. (loga n) = (logb n)
3. (loga n) > (logb n)
4. (loga n) et (logb n) sont incomparables
Exercice
• Montrer que
(f + g) = (Max{f,g}).
• Soit p(n) = aknk + . . . + a1n + a0 un polynôme de degré k. Montrer que
p(n) 2 (nk).
Exercice
Supposons que f(n) 2 (g(n)). Est-ce qu’il est vrai que 2f(n) 2 (2g(n))?
Dans le cas affirmatif prouvez le, sinon donnez un contre-exemple.
définition :
On définit de la façon suivante l’ordre partiel sur l’ordre de
grandeur des fonctions :
(f) (g) si f 2 O(g)
On a alors:
(f) = (g) si f 2 (g)
(f) < (g) si f 2 O(g)etg 62 O(f)
Enumerer en ordre croissant l’ordre exact des fonctions suivantes:
n, 2n, n log n, ln n, n + 7n5, log n,
p
n, en, 2n-1, n2, n2 +
log n, log log n, n3, (log n)2, n!, n3/2.
(log et ln dénotent respectivement la fonction de logarithme en base de 2 et en
base de e.)
proposition 4 : (admise)
• lim
n!1
g
f
= c > 0 alors g 2 (f)
• lim
n!1
g
f
= 0 alors g 2 O(f) et f 62 O(g)
( (g) < (f))
• lim
n!1
g
f
= +1 alors f 2 O(g) et g 62 O(f)
( (f) < (g))
On va comparer les algorithmes selon l’ordre de grandeur de
leur complexité.
définition :
La complexité C(n) d’un problème P est la complexité du meilleur
algorithme qui résoud P.
• Si un algorithme A résoud P en temps f(n)
alors C(n) 2 O(f)
• Si l’on prouve que tt algorithme qui résoud P travaille en
temps au moins g(n) alors C(n) 2
(g)
• Si f 2 (g) alors C(n) 2 (f) = (g) et c’est la
complexité du problème
Exercice
1. Supposons que
lim
n!1
f(n)
g(n)
= 1.
1. On a toujours (f) < (g)
2. On a toujours (f) = (g)
3. On a toujours (f) > (g)
4. (f) et (g) peuvent être incomparables
2. Supposons que (f) = (g). Est-ce que limn!1
f(n)
g(n)
1. existe toujours et = 1
2. existe toujours et = 0
3. existe toujours et = c, où c est une constante positive
4. n’existe pas toujours.
Exercice
Montrer que est une relation d’équivalence.
Un rapide rappel
Rappel
Un arbre est un graphe non-orienté acyclique et connexe
Définition
Un arbre enraciné (rooted tree) est un arbre avec un sommet
distingué.
Le sommet distingué s’appelle la racine (root) de l’arbre.
Définition
Soit T = (V,E) un arbre enraciné au sommet r, x un sommet de T.
• si {y,x} est une arête de T et y est un ancêtre de x, alors y est
le père de x, et x est un fils de y.
• la racine de l’arbre n’a pas de père. si x et y ont le même père,
alors ils sont frêres.
• un sommet sans fils est un sommet externe ou feuille (leaf). les
autres sommets sont les sommets internes
• le nombre de fils d’un sommet x est le degré de x.
Définition
La profondeur du sommet x est la longueur de la chaine entre la
racine et le sommet x.
La hauteur (ou profondeur) de l’arbre est :
Max
x2V
{profondeur(x)}
Les arbres binaires sont définis récursivement.
Définition
un arbre binaire est une structure sur un ensemble fini de sommets.
Il est :
• soit vide (ne contient pas de sommet)
• soit l’union de 3 ensemble disjoints de sommets :
• un sommet appelé racine
• un arbre binaire : le sous-arbre gauche
• un arbre binaire : le sous-arbre droit
La racine d’un sous-arbre gauche non vide est appelé le fils gauche
de la racine de l’arbre.
Définition
Soit a un réel non négatif.
bac est le plus grand entier qui est a.
dae est le plus petit entier qui est a.
exemples
b c = 3
d e = 4
b5c = d5e = 5
notation
log désigne le logarithme en base 2.
Théorème 1
La profondeur d’un arbre binaire à n sommets est au moins blog nc
Preuve
a. A la profondeur l, il y a au plus 2l sommets dans l’arbre.
Parce que : c’est vrai à la profondeur 0, et si c’est vrai à la profondeur l - 1, à la
profondeur l il y a au plus 2 fois autant de sommets, donc au plus 2l.
b. Un arbre binaire de profondeur d a au plus 2d+1 - 1 sommets.
Parce que: on somme les sommets selon leur profondeur.
et alors : Nombre de sommets
Pd
l=0 2l = 2d+1 - 1
c. Soit d la profondeur de l’arbre. On suppose que d < blog nc, alors
d blog nc - 1. Il vient que n 2blog nc - 1 2log n - 1 < n ce qui est une
contradiction.
TRI (sorting)
Input : Une liste de n entiers (a1,a2, . . . ,an)
Output : Une permutation (a0
1,a0
2, . . . ,a0
n) de la liste d’entrée telle
que a0
1 a0
2 . . . a0
n ou a0
1 a0
2 . . . a0
n.
Souvent les entiers sont une partie d’une donnée plus complexe,
l’entier est alors la clé de la donnée. Et on triera les données d’après
les clés.
La structure de donnée est une liste A à n éléments avec A[i] = ai
au début et A[i] = a0
i à la fin.
L’opération de base pour les algorithmes de tri est la comparaison :
A[i] : A[j], c’est la seule opération permise sur les clés.
Tri par selection
Idée :
On recherche le minimum de la liste et on le met en première
position, et on recommence sur la fin de la liste où l’on a ajouté
l’élément qui se trouvait en première place.
Après le k-ième placement, les k plus petits éléments de la liste
sont à leur place définitive.
Exemple :
Input : 101 115 30 63 47 20
selection de 20
Placement : 20 115 30 63 47 101
selection de 30
Placement : 20 30 115 63 47 101
selection de 47
Placement : 20 30 47 63 115 101
selection de 63
Placement : 20 30 47 63 115 101
selection de 101
Placement : 20 30 47 63 101 115
output : 20 30 47 63 101 115
procedure TRI-SELECTION
Input :
A: array [1..n] of integer
var i, j, k : integer
begin
i :=1
while i<n do begin { i-ème placement }
j:=i
for k:=i+1 to n do
if A[k]<A[j] then j:=k
A[j]$A[i] { placement du minimum }
end
end
Complexité
• Nombre de comparaisons en itération i :
(n - i + 1) - 1 = n - i
Tri par insertion (séquentielle)
Idée :
• On fait n itérations.
• Après l’itération (i - 1) les premiers (i - 1) éléments de la liste
sont triés.
• A l’itération i on insère d’une manière séquentielle le i-ème
élément parmi les premiers (i - 1) éléments.
Exemple :
Input : 101 115 30 63 47 20
Itération 1 : 101 115 30 63 47 20
Itération 2 : 101 115 30 63 47 20
Itération 3 : 30 101 115 63 47 20
Itération 4 : 30 63 101 115 47 20
Itération 5 : 30 47 63 101 115 20
Itération 6 : 20 30 47 63 101 115
output : 20 30 47 63 101 115
procedure TRI-INSERTION
Input :
A: array [1..n] of integer
var i, x, k : integer
begin
for i:=2 to n do begin
k:=i-1 ; x:=A[i]
while A[k]>x do begin
A[k+1]:=A[k] ; k:=k-1 end
A[k+1]:=x
end
end
Complexité
• Nombre de comparaisons à l’itération i :
au plus i
On considère la méthode suivante,
réalisant le tri par insertion d’un tableau T à N éléments,
numérotés de 1 à N :
– pour chaque i 2 [ 2, . . . ,N ],
– j := i - 1.
– tant que (j > 0) et T[j] > T[j + 1],
– échanger les contenus de T[j] et T[j + 1].
– j := j - 1.
Rappelons que dans le pire des cas, le nombre d’échanges
nécessaires est égal à 1 + 2 + . . . (N - 1) = N(N-1)
2 .
Exercice 1
Soient (a1, . . . ,ap) et (b1, . . . ,bp) deux suites d’entiers dont les
éléments sont triés
par ordre croissant. Soit T = (a1,b1,a2,b2, . . . ,ap,bp).
Démontrer, par récurrence sur p, que le tri par insertion de T
nécessite, dans le pire des cas,
seulement p(p+1)
2 échanges.
Exercice 2
On considère à présent un tableau T arbitraire
de taille n = 2 × p, et l’on considère la méthode suivante :
– trier sur place, par insertion, le sous-tableau de T d’indices
paires,
– trier sur place, par insertion, le sous-tableau de T d’indices
impaires,
– trier, par insertion, le tableau T résultant.
Quel est, dans le pire des cas, le coût de ce tri? Comparer la valeur
obtenue avec celle
du tri par insertion simple. Est-elle meilleure ou pire?
Tri rapide (quicksort)
Idée :
On partage la liste à trier en deux sous-listes telles que tous les
éléments de la première soient plus petits que les éléments de la
seconde. Par récurrence, on trie les deux sous-listes.
Comment partager la liste en deux?
On choisit une des clés de la liste, et on l’utilise comme pivot.
La liste d’origine est donc coupée en trois : une première liste (à
gauche) composée des éléments au pivot, le pivot (à sa place
définitive) et une liste (à droite ) composée des éléments > au pivot.
Notre choix : le pivot est le premier élément de la liste.
Supposons qu’on a une procédure PARTITION(A,i,j,k) qui effectue
la partition de la sous-liste de A entre les indices i et j, en fonction
du pivot A[i], et rend comme résultat l’indice k, où ce pivot a été
placé.
Avec cette procédure, on peut écrire une procédure TRI-RAPIDE.
procedure TRI-RAPIDE
Input :
A: array [1..n] of integer
i, j : integer
var k : integer
begin
if i<j then begin
PARTITION(A,i,j,k)
TRI-RAPIDE(A,i,k-1)
TRI-RAPIDE(A,k+1,j)
end
end
procedure PARTITION
Input : A: array [1..n+1] of integer
i, j, k : integer
var l : integer
begin
l:=i+1; k:=j
while l<=k do begin
while A[l]<=A[i] do l:=l+1
while A[k]>A[i] do k:=k-1
if l<k then do begin
A[l]$A[k]; l:=l+1; k:=k-1; end
end
A[i]$A[k]
end
Complexité
• Complexité en pire cas : (n2)
En effet, le pire cas se produit lorsqu’une des partitions est vide et
l’autre est de taille n - 1.
Dans ce cas, on a :
t1 = 1
tn = tn-1 + n
Et la solution de cette équation de récurrence est : n2
Complexité
• Complexité en meilleur cas : (n × log(n))
En effet, le meilleur cas se produit lorsque les deux partitions sont
de même taille.
Dans ce cas, on a :
t1 = 1
tn = 2tn/2 + n
Et la solution de cette équation de récurrence est : n × log(n) + n
Tri Fusion
Le principe
En appliquant la méthode diviser pour régner au problème du tri
d’un tableau, on obtient facilement le tri par fusion.
On appelle ce tri mergesort en anglais.
Le principe est de diviser une table de longueur n en deux tables de
longueur n/2, de trier récursivement ces deux tables, puis de
fusionner les tables triées.
Le principe
Première phase : Découpe :
1. Découper le tableau en 2 sous-tableaux égaux (à 1 case près)
2. Découper chaque sous-tableau en 2 sous-tableaux égaux
3. Ainsi de suite, jusqu’à obtenir des sous-tableaux de taille 1
Le principe
Deuxième phase : Tri/fusion :
1. Fusionner les sous-tableaux 2 à 2 de façon à obtenir des
sous-tableaux de taille 2 triés
2. Fusionner les sous-tableaux 2 à 2 de façon à obtenir des
sous-tableaux de taille 4 triés
3. Ainsi de suite, jusqu’à obtenir le tableau entier
Exercice
• Donner un code, dans le langage que vous voulez, qui
implémente le Tri Fusion.
• Dérouler votre code sur la liste d’entiers :
3 6 78 32 5 1 10 23 9 11 33
Exercice : complexité
Quelle est la complexité du Tri Fusion?
Tri à Bulle
Le principe
• On compare les éléments deux à deux de la gauche vers la droite,
en les échangeant pour les classer quand c’est nécessaire.
• Quand on arrive à la fin de la liste, on recommence, jusqu’à ce
que la liste soit classée.
• On détecte que la liste est classée quand on a fait un passage sans
Exercice
• Ecrire une procédure Tri-Bulle
• Dérouler l’algorithme sur la liste :
2 4 7 5 3 1
Combien avez vous fait de comparaisons?
Variantes :
• Tri Boustrophedon
• Tri Shuttle
TRI PAR TAS (HEAPSORT)
Idée :
On sélectionne les minimums successifs en utilisant une structure
de donnée particulière : le tas
Définition
Un arbre parfait est un arbre binaire dont les feuilles sont situées sur
deux niveaux successifs : l’avant dernier niveau est complet, et les
feuilles du dernier niveau sont regroupées le plus à gauche possible.
Définition
Un arbre parfait partiellement ordonné est un arbre parfait dont les
sommets sont étiquetés par des éléments à trier, et tel que l’élément
associé à chaque sommet est aux éléments associés aux fils de ce
sommet.
Définition
Un tas (heap) est un tableau t représentant un arbre parfait
partiellement ordonnée selon les règles suivantes :
• t[1] est la racine
• t[2i] et t[2i + 1] sont les fils gauche et droite de t[i] (s’ils
existent)
Exemple 3 5 9 6 8 11 10 12 18 14
Propriétés simples d’un tas
• t[bi/2c] est le père de t[i] (i 2)
• Si le nombre de sommets n est pair, alors t[n/2] a un seul fils
t[n]
• Si i > bn/2c, alors t[i] est une feuille
Idée du tri par tas
I. On construit le tas
II. On enlève successivement le minimum du tas et on reconstruit
CONSTRUCTION DU TAS
L’essentiel est une procédure AJOUT qui ajoute un élément
nouveau à un tas.
On ajoute cet élément comme une feuille (au dernier niveau), puis
on l’échange avec son père tant qu’il est inférieur à celui-ci.
la structure de tas sur le reste des éléments
procedure AJOUT
Input : t : array [1..n] of integer ; p, x : integer {la procédure ajoute l’élément x
dans le tas t qui contient p éléments}
var i : integer
begin
if p<n then begin {on place x à la dernière feuille}
p:=p+1 ; t[p]:=x ; i:=p ;
{on échange tant que x est < que son père}
while i>1 and t[i] < t[bi/2c] do begin
t[i] $ t[bi/2c] ; i := bi/2c
end
end
else writeln(“débordement du tas”)
end
Complexité en pire cas
La procédure AJOUT fait au plus blogpc comparaisons.
Pourquoi?
Parce que la hauteur d’un arbre parfait à p sommets est blog pc.
SUPPRESSION DU MINIMUM ET REORGANISATION DU
TAS
La procédure DESTRUCTION remplace la racine du tas par la
dernière feuille.
Pour réorganiser le tas, on échange cet élément avec le plus petit de
ses deux fils tant qu’il est supérieur à celui-ci.
procedure DESTRUCTION
Input :
t : array [1..n] of integer
p, min : integer
{DESTRUCTION retourne dans min le minimum des p éléments du tas et
réorganise le tas}
var i, j : integer
begin
min:=t[1] {retour du minimum}
t[1] := t[p] ; p:=p-1 {nouvelle taille du tas}
i:=1 {réorganisation du tas}
while i bp/2c do begin
{calcul de l’indice du plus petit des deux fils de t[i], ou de son seul fils}
if 2i=n or t[2i] < t[2i + 1] then j:=2i else j:=2i+1
{échange entre deux éléments qui sont père et fils}
if t[i] > t[j] then begin t[i] $ t[j] ; i:=j end
else exit
end
end
Complexité de DESTRUCTION en pire cas :
2[log p]
L’algorithme TRI-TAS
• On ajoute successivement chacun des n éléments dans le tas
t[1 . . . p], p augmente de 1 après chaque adjonction. A la fin on a un
tas de taille n.
• Tant que p > 1, on supprime le minimum du tas, on décroit p de
1, et on range le minimum à la (p + 1)eme place. Puis on
réorganise le tas. t[p + 1 . . . n] contient les n - p plus petits
éléments en ordre décroissant.
procedure TRI-TAS
Input : t : array [1..n] of integer
var p, min : integer
begin
p:=0
while p < n do {construction du tas}
AJOUT(t,p,t[p+1]);
{p augmente de 1 à chaque appel}
while p > 1 do begin
DESTRUCTION(t,p,min)
{p diminue de 1 à chaque appel}
t[p+1]:=min
end
end
Exercice
Trier le tableau suivant en utilisant l’algorithme TRI-RAPIDE:
1 21 5 34 32 67 6 0 200 25 65 4 24 33.
Quel est le nombre de comparaisons utilisées?
Exercice
Quelle est la valeur retournée par la procédure PARTITION quand tous les
éléments dans le tableau A[i..j] ont la même valeur?
Exercice
On se donne un tableau de n éléments qui ont chacun une couleur soit rouge, soit
blanc. On veut obtenir un tableau avec deux zones: à gauche tous les éléments
rouges, à droite tous les éléments blancs.
Ecrivez une procédure qui réalise cette organisation du tableau en ne testant
qu’une seule fois la couleur de chaque élément. Essayez de minimiser le nombre
moyen des échanges d’éléments. Calculez ce nombre.
FIN.
to be continue
اريد حل للتطبيقات الموجودة مع الدرس وشكرا
ردحذف