Algorithmique et complexité
Algorithmique et complexité
Ces pages sont destinées à donner quelques principes simples permettant d'évaluer un programme.
I Notion de coût d'un programme
Algorithmique et complexité
→ I Notion de coût d'un programme
L'exécution d'un programme a toujours un coût. Il existe deux paramètres essentiels pour mesurer ce coût :
- Le temps d'exécution : la complexité en temps.
- L'espace mémoire requis : la complexité en espace.
Lorsqu'on fait un programme, il faut donc
- évaluer les ressources nécessaires : place mémoire et temps d'exécution.
- évaluer le nombre d'opérations élémentaires pour avoir une idée du coût en temps. Ce qui compte comme opérations dépend du type de problème [cela peut être des opérations du type comparaison, des opérations d'accès au disque ou des opérations arithmétiques]. Elles n'ont pas forcément le même poids. Certaines peuvent être négligeables devant d'autres mais si on les exécute très souvent, il faut quand même en tenir compte.
II Modèle
Algorithmique et complexité
→ II Modèle
Pour pouvoir évaluer ces coûts de manière théorique, on définit un modèle abstrait d'ordinateur et on évalue les coûts de ce modèle. Par exemple, dans le cas d'une RAM (Random Acces Machine), on se donne une suite infinie de cases dans lesquelles on peut stocker un entier arbitrairement grand et un programme, c'est-à-dire une suite finie d'instructions permises :
- arithmétique : , où est une des opérations addition, soustraction, multiplication, division d'entiers : ce type d'instruction calcule la valeur et la stocke dans
;
- branchement : Si alors i. Ici, i est l'indice d'une instruction, et une opération de comparaison.
- arrêt.
En pratique, il n'est pas vrai que la mémoire est illimitée. Les nombres stockés en mémoire sont limités. Et les opérations élémentaires n'ont pas toutes le même coût. On ne tient pas non plus compte des opérations qui, relativement aux autres, consomment peu de temps, telles que les tests, les affectations et les incrémentations.
Bien que très approximatif et ne tenant pas compte de la place mémoire, ce décompte du nombre d'opérations permet de comparer plusieurs algorithmes et correspond en général assez bien aux mesures que l'on peut faire dans une implémentation spécifique de l'algorithme.
III En pratique
Algorithmique et complexité
→ III En pratique
La plupart des algorithmes que nous verrons dans la suite sont de type arithmétique et les données sont des entiers, des listes d'entiers.
III-5 Coûts d'opérations simples
III-1 Taille
Algorithmique et complexité
→
III En pratique
→ III-1 Taille
On mesure la taille des données de type entier comme leur nombre de chiffres
en base 2 :
Si les entiers qu'on considère sont de taille petite
[par exemple si tous les entiers qu'on considère sont inférieurs à 10000], on pourra prendre
T = 1.
Exercice
Nombre de chiffres en base \( b \)
Nombre de chiffres en base \( b \)
Nombre de chiffres en base \( b \)
III-2 Coût
Algorithmique et complexité
→
III En pratique
→ III-2 Coût
On évalue le coût
C(x) pour l'entrée
x,
le coût le pire
pour
n donné qui est le coût
maximal de l'algorithme pour des entrées
x de taille
T(x) inférieure à
n :
D'autres coûts peuvent être introduits comme
le coût espéré
Plus généralement, on peut se donner une distribution de probabilité Pr sur et évaluer
Plus généralement, on peut se donner une distribution de probabilité Pr sur et évaluer
III-3 Complexité
Algorithmique et complexité
→
III En pratique
→ III-3 Complexité
On emploie souvent le mot complexité à la place de
coût. La complexité évalue la difficulté intrinsèque des problèmes : par exemple
Tout algorithme capable de traiter toutes les instances de taille a un coût minimal de T(N) dans le cas le pire.
L'algorithmique fournit des résultats positifs du type : L'algorithme Truc traite une instance de taille N en temps .
Tout algorithme capable de traiter toutes les instances de taille a un coût minimal de T(N) dans le cas le pire.
L'algorithmique fournit des résultats positifs du type : L'algorithme Truc traite une instance de taille N en temps .
III-4 Notations de Landau
Algorithmique et complexité
→
III En pratique
→ III-4 Notations de Landau
Dans ce qui suit,
f et
g sont des fonctions d'une variable
x qui est soit
un entier positif, soit un réel,
g est une fonction positive pour
x assez grand,
Comparer des ordres de grandeur
Classer des ordres de grandeur
Un algorithme est dit polynomial si son coût est au plus polynomial en la taille
des entrées.
D'autres termes sont utilisés : sous-linéaire, linéaire, quadratique,
exponentielle ...
Attention de bien définir quelle taille est adaptée au problème.
- f = O(g) signifie que pour une constante c et pour x assez grand.
- signifie que pour une constante c et pour x assez grand.
- signifie que pour des constantes c et d et pour x assez grand.
- f = o(g) signifie que tend vers 0 lorsque .
- signifie que tend vers 1 lorsque .
Exercice
Comparer des ordres de grandeur
Classer des ordres de grandeur
Exercice
Vocabulaire
Attention de bien définir quelle taille est adaptée au problème.
III-5 Coûts d'opérations simples
Algorithmique et complexité
→
III En pratique
→ III-5 Coûts d'opérations simples
Soient
a et
b deux entiers, inférieurs ou égaux à
n.
Le nombre de bits dans la représentation binaire de
n est
Si les entiers sont représentés en base
B, le nombre de chiffres est
Tous deux sont en
.
Une opération sur des entiers de taille "petite" [par exemple, ayant un chiffre en base B, on parle d'entiers simple précision] est appelée opération élémentaire.
La taille d'un entier est donc mesurée en général par lg(n).
Une opération sur des entiers de taille "petite" [par exemple, ayant un chiffre en base B, on parle d'entiers simple précision] est appelée opération élémentaire.
La taille d'un entier est donc mesurée en général par lg(n).
III-5-1 Opérations élémentaires
III-5-1 Opérations élémentaires
Algorithmique et complexité
→
III En pratique
→
III-5 Coûts d'opérations simples
→ III-5-1 Opérations élémentaires
Le nombre d'opérations élémentaires pour des entiers grands
(multi-précision)
pour les quatre opérations
de base nécessaires avec des algorithmes classiques
(ceux que vous utilisez pour faire une opération à la main)
est résumé dans le tableau suivant :
| Opération | Complexité en bits | pour a et b inférieurs à n |
| addition a + b | O(lg(a) + lg(b)) | O(lg(n)) |
| soustraction a - b | O(lg(a) + lg(b)) | O(lg(n)) |
| multiplication ab | O(lg(a) lg(b)) | O(lg(n)2) |
| division a = bq + r | O(lg(q) lg(b)) | O(lg(n)2) |
III-5-2 Coût de l'algorithme d'Euclide
Algorithmique et complexité
→
III En pratique
→
III-5 Coûts d'opérations simples
→ III-5-2 Coût de l'algorithme d'Euclide
| Algorithme | Complexité en bits |
| Algorithme d'Euclide | O((lg(n))2) |
| Algorithme étendu | O((lg(n))2) |
III-5-3 Calcul modulaire modulo n
Algorithmique et complexité
→
III En pratique
→
III-5 Coûts d'opérations simples
→ III-5-3 Calcul modulaire modulo
n
| Opération | Complexité en bits |
| addition modulaire | O(lg(n)) |
| soustraction modulaire | O(lg(n)) |
| multiplication modulaire | O((lg(n))2) |
| inversion modulaire | O((lg(n))2) |
| exponentiation modulaire | O((lg(n))3) |
III-6 Diviser pour régner
Algorithmique et complexité
→
III En pratique
→ III-6 Diviser pour régner
On a un problème avec une solution "simple"
algosimple(x) pour des
entrées
x de taille petite.
Pour
x de taille grande, on le décompose en plus petites entrées
x1,
...,
xr, de taille plus petite. Par exemple, on décompose le problème
en deux avec des tailles moitié. On fait alors tourner le programme
algo (x) sur
ces entrées. Éventuellement, pour pouvoir décomposer le problème et le recomposer,
on a d'autres petites choses à faire
dont le coût est en
f(x).
Input: x
Output: algo( x )
si x est petit ou simple alors
retourner alogsimple(x)
Décomposer x en sous-entrées x1, ..., xt
pour i = 1 à t faire
recombiner les yi en une solution y pour x
retourner y
Si le coût du programme est C(x), on a donc
pour
x > T1 ;
C(x) pour
x < T1 est le coût de l'algorithme simple.
Par exemple, si l'on a décomposé le problème en deux problèmes
de taille moitié, pour
x > T1,
.
Il reste à évaluer à partir de cette inégalité de récurrence
quel est le coût. Pour cela on s'inspire du lemme suivant.
Démonstration
Il existe des versions avec des relations du type
où le comportement asymptotique de
f est connu.
Dans les cas réels, la fonction C n'est pas définie sur , on ne la connait souvent bien que sur une classe d'entiers (par exemple dans le cas de dichotomie, sur les entiers de la forme 2k). On fait alors des hypothèses raisonnables sur la fonction de coût pour pouvoir appliquer ce lemme ou une variante (croissance, ...)
Diviser pour régner
Input: x
Output: algo( x )
si x est petit ou simple alors
retourner alogsimple(x)
Décomposer x en sous-entrées x1, ..., xt
pour i = 1 à t faire
recombiner les yi en une solution y pour x
retourner y
Si le coût du programme est C(x), on a donc
Lemme
Soit
une fonction vérifiant
C(x) = 0 pour
x < 1 et
pour certains
a > 0,
b > 1 et
c réels et pour
. Une
borne supérieure pour
C(x) lorsque
est
Démonstration
On écrit
x = bn x0 avec
x0 inférieur à une constante
T0,
d'où
.
Par récurrence,
La dernière inégalité n'est valable que si
a est différent de
bk.
On a alors
avec
D(x) fonction bornée
et
Donc
C(x) est la forme
avec
C2 et
C3 bornés.
Par récurrence,
| C(x) | |
- Si a < bk, c'est un O(xk).
- Si a > bk, c'est un .
- Si a = bk,
C(x)
Il existe des versions avec des relations du type
Dans les cas réels, la fonction C n'est pas définie sur , on ne la connait souvent bien que sur une classe d'entiers (par exemple dans le cas de dichotomie, sur les entiers de la forme 2k). On fait alors des hypothèses raisonnables sur la fonction de coût pour pouvoir appliquer ce lemme ou une variante (croissance, ...)
Exercice
Application
III-7 Pratiquement, que faire ?
Algorithmique et complexité
→
III En pratique
→ III-7 Pratiquement, que faire ?
- Choisir la fonction taille pour les entrées.
- Compter le nombre de boucles.
- Évaluer le coût des opérations à l'intérieur : est-ce une opération élémentaire, donc à coût en O(1) ?
- Dans le cas d'un branchement, évaluer le coût de la branche la plus coûteuse.
Voici deux exemples :
Racine carrée entière d'un entier n
Input: n un entier positif
Output: la racine carrée par défaut d'un entier n
; ;
tant que faire
;
retourner racine
Recherche du plus petit élément d'une liste en O(n)
Input: une liste x de longueur n
Output: la position du plus petit élément de la liste x
pour i = 1 à n faire
si x[i] < x[k] alors
retourner k
III-8 Exercices d'application
Algorithmique et complexité
→
III En pratique
→ III-8 Exercices d'application
Exercice
Dans
cet exercice
,
vous sont présentés des algorithmes. Vous devez donner leur ordre de complexité.
Prenez le temps de les comprendre en même temps. Faites attention à ce qu'est la
taille dans chacun des problèmes donnés.
IV Simulation
Algorithmique et complexité
→ IV Simulation
IV-1 Addition dans Pari/GP
Algorithmique et complexité
→
IV Simulation
→ IV-1 Addition dans Pari/GP
On fait 5000 additions de nombres dont la taille (longueur en base 2) est 3000 + 5000i pour i = 1 , 30. Le calcul est fait avec le logiciel GP/Pari.
IV-2 Addition dans Octave
Algorithmique et complexité
→
IV Simulation
→ IV-2 Addition dans Octave
tic
for i=1:nb
a+b;
end
elapsed_time = toc ;
On fait 10000 additions de nombres dont la taille (longueur en base 2) est 30000 + 50000i pour i = 1 , 30. Le calcul est fait avec le logiciel Octave![]()
Des droites de pentes diverses ont été tracées en vert
ainsi que des paraboles en bleu pour donner des points de repère.
On fait 10000 additions de nombres dont la taille (longueur en base 2) est 30000 + 50000i pour i = 1 , 30. Le calcul est fait avec le logiciel Octave
IV-3 Multiplication dans Pari/GP
Algorithmique et complexité
→
IV Simulation
→ IV-3 Multiplication dans Pari/GP
On fait 5000 multiplications de nombres dont la taille (logarithme en base 2) est 0 + 1000i pour i = 1 , 30. Le calcul est fait avec le logiciel GP/Pari.
Les graphes tracés sont les courbes d'équation
- en vert,
- y = x en bleu,
- y = x1.25 en noir,
- y = x2 en violet.
IV-4 Multiplication dans Octave
Algorithmique et complexité
→
IV Simulation
→ IV-4 Multiplication dans Octave
On fait 3000 multiplications de nombres dont la taille (longueur en base 2) est 10000 + 5000i pour i = 1 , 30. Le calcul est fait avec le logiciel Octave