Algorithmique et complexité

I Notion de coût d'un programme
II Modèle
III En pratique
IV Simulation

Ces pages sont destinées à donner quelques principes simples permettant d'évaluer un programme.

I Notion de coût d'un programme

II Modèle

III En pratique

IV Simulation

I Notion de coût d'un programme

Algorithmique et complexité → I Notion de coût d'un programme

I Notion de coût d'un programme
II Modèle
III En pratique
IV Simulation

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.

Il faut ensuite trouver un compromis entre espace et temps.

Algorithmique et complexité → I Notion de coût d'un programme

II Modèle

Algorithmique et complexité → II Modèle

I Notion de coût d'un programme
II Modèle
III En pratique
IV Simulation

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 : $α \leftarrow β ⋆ γ$ , 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.

Algorithmique et complexité → II Modèle

III En pratique

Algorithmique et complexité → III En pratique

I Notion de coût d'un programme
II Modèle
III En pratique
IV Simulation

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-1 Taille

III-2 Coût

III-3 Complexité

III-4 Notations de Landau

III-5 Coûts d'opérations simples

III-6 Diviser pour régner

III-7 Pratiquement, que faire ?

III-8 Exercices d'application

Algorithmique et complexité → III En pratique

III-1 Taille

Algorithmique et complexité → III En pratique → III-1 Taille

I Notion de coût d'un programme
II Modèle
III En pratique
IV Simulation

On mesure la taille des données de type entier comme leur nombre de chiffres en base 2 :

T (n) = {\begin{cases} \lg (n) = [\log_{2} (n)] + 1 & si n est non nul \\ 1 & si n est nul \end{cases}

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 $

Algorithmique et complexité → III En pratique → III-1 Taille

III-2 Coût

Algorithmique et complexité → III En pratique → III-2 Coût

I Notion de coût d'un programme
II Modèle
III En pratique
IV Simulation

On évalue le coût

C (x)

pour l'entrée

x

, le coût le pire

𝒞 (n)

pour

n

donné qui est le coût maximal de l'algorithme pour des entrées

x

de taille

T (x)

inférieure à

n

𝒞 (n) = \max_{T (x) = n} C (x)

D'autres coûts peuvent être introduits comme le coût espéré

\sum_{T (x) = n} C (x) / \sum_{T (x) = n} 1 .

Plus généralement, on peut se donner une distribution de probabilité

\Pr

sur

{x, T (x) = N}

et évaluer

\sum_{T (x) = n} \Pr (t = x) C (x) .

Algorithmique et complexité → III En pratique → III-2 Coût

III-3 Complexité

Algorithmique et complexité → III En pratique → III-3 Complexité

I Notion de coût d'un programme
II Modèle
III En pratique
IV Simulation

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

\leq N

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

\leq t (N)

Algorithmique et complexité → III En pratique → III-3 Complexité

III-4 Notations de Landau

Algorithmique et complexité → III En pratique → III-4 Notations de Landau

I Notion de coût d'un programme
II Modèle
III En pratique
IV Simulation

Dans ce qui suit,

f

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,

$f = O (g)$ signifie que $∣ f (x) ∣ \leq c g (x)$ pour une constante $c$ et pour $x$ assez grand.
$f = Ω (g)$ signifie que $∣ f (x) ∣ \geq c g (x)$ pour une constante $c$ et pour $x$ assez grand.
$f = Θ (g)$ signifie que $c g (x) \leq ∣ f (x) ∣ \leq d g (x)$ pour des constantes $c$ et $d$ et pour $x$ assez grand.
$f = o (g)$ signifie que $\frac{f (x)}{g (x)}$ tend vers 0 lorsque $x \to ∞$ .
$f \sim g$ signifie que $\frac{f (x)}{g (x)}$ tend vers 1 lorsque $x \to ∞$ .

Exercice

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 ...

Exercice

Vocabulaire

Attention de bien définir quelle taille est adaptée au problème.

Algorithmique et complexité → III En pratique → III-4 Notations de Landau

III-5 Coûts d'opérations simples

Algorithmique et complexité → III En pratique → III-5 Coûts d'opérations simples

I Notion de coût d'un programme
II Modèle
III En pratique
IV Simulation

Soient

a

b

deux entiers, inférieurs ou égaux à

n

. Le nombre de bits dans la représentation binaire de

n

est

\lg (n) = ([\log n / \log 2] + 1) .

Si les entiers sont représentés en base

B

, le nombre de chiffres est

\lg_{B} (n) = [\log n / \log B] + 1 .

Tous deux sont en

Θ (\log 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-2 Coût de l'algorithme d'Euclide

III-5-3 Calcul modulaire modulo $n$

Algorithmique et complexité → III En pratique → III-5 Coûts d'opérations simples

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

I Notion de coût d'un programme
II Modèle
III En pratique
IV Simulation

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})$

Algorithmique et complexité → III En pratique → III-5 Coûts d'opérations simples → III-5-1 Opérations élémentaires

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

I Notion de coût d'un programme
II Modèle
III En pratique
IV Simulation

Algorithme	Complexité en bits
Algorithme d'Euclide	$O ((\lg (n))^{2})$
Algorithme étendu	$O ((\lg (n))^{2})$

Algorithmique et complexité → III En pratique → III-5 Coûts d'opérations simples → III-5-2 Coût de l'algorithme d'Euclide

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

I Notion de coût d'un programme
II Modèle
III En pratique
IV Simulation

Opération	Complexité en bits
addition modulaire $a + b mod n$	$O (\lg (n))$
soustraction modulaire $a - b mod n$	$O (\lg (n))$
multiplication modulaire $a b mod n$	$O ((\lg (n))^{2})$
inversion modulaire $a^{- 1} mod n$	$O ((\lg (n))^{2})$
exponentiation modulaire	$O ((\lg (n))^{3})$

Algorithmique et complexité → III En pratique → III-5 Coûts d'opérations simples → III-5-3 Calcul modulaire modulo

n

III-6 Diviser pour régner

Algorithmique et complexité → III En pratique → III-6 Diviser pour régner

I Notion de coût d'un programme
II Modèle
III En pratique
IV Simulation

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

x_{1}

, ...,

x_{r}

, 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)

Diviser pour régner

Input:

x

Output:

algo (x)

x

est petit ou simple alors
retourner alogsimple(x)
Décomposer

x

en sous-entrées

x_{1}

, ...,

x_{t}

pour

i = 1

t

faire

y_{i} \leftarrow algo (x_{i})

recombiner les

y_{i}

en une solution

y

pour

x

retourner

y

Si le coût du programme est

C (x)

, on a donc

C (x) \leq C (x_{1}) + . . . + C (x_{r}) + f (x)

pour

x > T_{1}

;

C (x)

pour

x < T_{1}

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 > T_{1}

C (x) \leq 2 C (x / 2) + f (x)

. Il reste à évaluer à partir de cette inégalité de récurrence quel est le coût. Pour cela on s'inspire du lemme suivant.

Lemme

Soit

C : ℝ^{+} \to ℝ^{+}

une fonction vérifiant

C (x) = 0

pour

x < 1

C (x) \leq a C (\frac{x}{b}) + c x^{k}

pour certains

a > 0

b > 1

c

réels et pour

x \in ℝ^{+}

. Une borne supérieure pour

C (x)

lorsque

x \to ∞

est

{\begin{cases} O (x^{\log_{b} a}) & si a > b^{k} \\ O (x^{k} \log x) & si a = b^{k} \\ O (x^{k}) & si a < b^{k} . \end{cases}

Démonstration

On écrit

x = b^{n} x_{0}

avec

x_{0}

inférieur à une constante

T_{0}

, d'où

n \leq \log_{b} (x) + N_{0}

.
Par récurrence,

\begin{aligned} C (x) & \leq a (a C (\frac{x}{b^{2}}) + A (\frac{x}{b})^{k}) + A x^{k} \\ \leq a^{n} C (\frac{x}{b^{n}}) + A \sum_{i = 0}^{n - 1} a^{i} (\frac{x}{b^{i}})^{k} \\ \leq a^{n} C_{0} + A x^{k} \frac{(a / b^{k})^{n} - 1}{a / b^{k} - 1} \end{aligned}

La dernière inégalité n'est valable que si

a

est différent de

b^{k}

. On a alors

a^{n} = x^{\log_{b} (a)} \times D (x)

avec

D (x)

fonction bornée et

b^{kn} = x^{k} c_{1} .

Donc

C (x)

est la forme

C_{2} ∣ C_{3} x^{\log_{b} (a)} - x^{k} ∣

avec

C_{2}

C_{3}

bornés.

Si $a < b^{k}$ , c'est un $O (x^{k})$ .
Si $a > b^{k}$ , c'est un $O (x^{\log_{b} (a)})$ .
Si $a = b^{k}$ ,
$\begin{aligned} C (x) & \leq a^{n} C_{0} + A n x^{k} \\ \leq O (x^{k}) + O (x^{k} \log_{b} (x)) = O (x^{k} \log_{b} (x)) . \end{aligned}$

Il existe des versions avec des relations du type

C (x) \leq a C (\frac{x}{b}) + f (x)

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

2^{k}

). On fait alors des hypothèses raisonnables sur la fonction de coût pour pouvoir appliquer ce lemme ou une variante (croissance,

C (x) + C (y) \leq C (x + y)

...)

Exercice

Application

Algorithmique et complexité → III En pratique → III-6 Diviser pour régner

III-7 Pratiquement, que faire ?

Algorithmique et complexité → III En pratique → III-7 Pratiquement, que faire ?

I Notion de coût d'un programme
II Modèle
III En pratique
IV Simulation

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

d \leftarrow 1

;

racine \leftarrow 0

;
tant que

racine \times racine < = n

faire

racine \leftarrow racine + 1

;
retourner

racine

Il y a ici au plus

\sqrt{n}

passages dans la boucle et à chaque fois une addition élémentaire est faite. La taille

T

d'un entier

n

étant

Θ (\log n)

, le coût de l'algorithme est en

\exp (O (T))

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

k \leftarrow 1

pour

i = 1

n

faire
si

x [i] < x [k]

alors

k \leftarrow i

retourner

k

On compte le nombre de passages dans la boucle, la comparaison étant considérée comme une opération élémentaire. Il y en a

n - 1 = O (T)

si la liste est de taille inférieure à

T

. Le coût est donc au plus linéaire en

T

Algorithmique et complexité → III En pratique → III-7 Pratiquement, que faire ?

III-8 Exercices d'application

Algorithmique et complexité → III En pratique → III-8 Exercices d'application

I Notion de coût d'un programme
II Modèle
III En pratique
IV Simulation

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.

Algorithmique et complexité → III En pratique → III-8 Exercices d'application

IV Simulation

Algorithmique et complexité → IV Simulation

IV-1 Addition dans Pari/GP

Algorithmique et complexité → IV Simulation → IV-1 Addition dans Pari/GP

I Notion de coût d'un programme
II Modèle
III En pratique
IV Simulation

On fait 5000 additions de nombres dont la taille (longueur en base 2) est

3000 + 5000 i pour i = 1, 30

. Le calcul est fait avec le logiciel GP/Pari.

Des droites de pentes diverses ont été tracées en vert ainsi que des paraboles en bleu pour donner des points de repère.

Algorithmique et complexité → IV Simulation → IV-1 Addition dans Pari/GP

IV-2 Addition dans Octave

Algorithmique et complexité → IV Simulation → IV-2 Addition dans Octave

I Notion de coût d'un programme
II Modèle
III En pratique
IV Simulation

elapsed_time = toc ;
On fait 10000 additions de nombres dont la taille (longueur en base 2) est

30000 + 50000 i 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.

Algorithmique et complexité → IV Simulation → IV-2 Addition dans Octave

IV-3 Multiplication dans Pari/GP

Algorithmique et complexité → IV Simulation → IV-3 Multiplication dans Pari/GP

I Notion de coût d'un programme
II Modèle
III En pratique
IV Simulation

On fait 5000 multiplications de nombres dont la taille (logarithme en base 2) est

0 + 1000 i pour i = 1, 30

. Le calcul est fait avec le logiciel GP/Pari.

Les graphes tracés sont les courbes d'équation

$y = x^{\frac{\log (3)}{\log (2)}}$ en vert,
$y = x$ en bleu,
$y = x^{1.25}$ en noir,
$y = x^{2}$ en violet.

Les échelles ne sont pas précisées intentionnellement car elles n'ont pas de signification ici.

Algorithmique et complexité → IV Simulation → IV-3 Multiplication dans Pari/GP

IV-4 Multiplication dans Octave

Algorithmique et complexité → IV Simulation → IV-4 Multiplication dans Octave

I Notion de coût d'un programme
II Modèle
III En pratique
IV Simulation

On fait 3000 multiplications de nombres dont la taille (longueur en base 2) est

10000 + 5000 i pour i = 1, 30

. Le calcul est fait avec le logiciel Octave

Algorithmique et complexité → IV Simulation → IV-4 Multiplication dans Octave

document donnant quelques notions d'algorithmique en vue d'une utilisation dans un cours d'algèbre effective.
: complexity, Exercices interactifs Mathématiques

Veuillez noter que les pages WIMS sont générées interactivement; elles ne sont pas des fichiers HTML ordinaires. Elles doivent être utilisées interactivement EN LIGNE. Il est inutile pour vous de les ramasser par un programme robot.

Algorithmique et complexité