chapitre 1
chapitre 1
chapitre 1
Chapitre 1
THÉORIE DE LA COMPLEXITÉ ET
MESURE DE PERFORMANCE
3
CHAPITRE 1. THÉORIE DE LA COMPLEXITÉ ET MESURE DE PERFORMANCE
PARTIE 1.
COMPLEXITÉ D'UN ALGORITHME
1. Généralités
4
CHAPITRE 1. THÉORIE DE LA COMPLEXITÉ ET MESURE DE PERFORMANCE
Pour décrire un algorithme, on lui donne en général un nom, on précise quels sont les
paramètres qu’il peut prendre en entrée et le résultat qu’il est sensé renvoyer. On Utilise
des spécification de l’algorithme (des modifications de la mémoire).
En fin, l’algorithme est traduit sous forme d’un langage de programmation adapté. Il
est clair que les ordinateurs ne savent faire que des opérations extrêmement
élémentaires : accès mémoire et arithmétique essentiellement. C’est donc le travail de
l’informaticien d’écrire une solution à un problème complexe sous forme d’une suite
d’instructions élémentaires.
Terminaison
Pour montrer qu’un algorithme termine quel que soit le paramètre passé en entrée
respectant la spécification, il faut montrer que chaque bloc élémentaire décrit ci-dessus
termine, les boucles pour (for) et les instructions conditionnelles terminent forcément.
Le seul souci pourrait venir d’une boucle tantque (while).
Un algorithme comporte :
- Une partie temporelle : séquence d’instructions en principe savamment organisée,
- Une partie spatiale : ensemble de données plus ou moins structurées (nombres,
vecteurs, matrices, listes...).
Problème : donnée → l’algorithme fournir (nombre fini d’étapes)→ réponse
programme doit finir par s’arrêter
Formellement
Un problème abstrait = l’ensemble < E, A, S > où
E est une entrée (un des cas du problème),
A l’algorithme,
S la sortie (résultat ).
Un algorithme = < C entraînent → I >,
C : clauses (règles)
5
CHAPITRE 1. THÉORIE DE LA COMPLEXITÉ ET MESURE DE PERFORMANCE
I : instructions (traitements).
Ces règles forment une partition de l’univers:
- U des règles = tous les cas possibles.
- ∩ =Ø
→ L’algorithme ne doit pas oublier un cas, et on ne peut pas être dans deux cas à la fois.
– Le problème de tri d’un ensemble d’éléments selon une relation d’ordre (croissant ou
décroissant), avec un milliard d’éléments.
– Le problème de la Recherche pertinente dans des grandes bases de données.
6
CHAPITRE 1. THÉORIE DE LA COMPLEXITÉ ET MESURE DE PERFORMANCE
Pour chaque problème, nous trouvons des différentes variantes définis le corps de
l’algorithme. Ceci nous conduit à la nécessité d’estimer le coût d’un algorithme avant de
l’écrire et l’implémenter.
Cet outil permet de mesurer les ressources critiques (coûteuses) utilisées par les
algorithmes.
Les ressources coûteuses :
- Le temps d'exécution
- Programmation
- La mémoire
- Les processeurs
- Les messages
- Les implémentations matérielles d'un algorithme
- La surface du circuit ou le nombre de portes logiques
- L'énergie consommée
- Les radiations émises.
La conception de certains ordinateurs mobiles permet de présenter le problème suivant :
7
CHAPITRE 1. THÉORIE DE LA COMPLEXITÉ ET MESURE DE PERFORMANCE
L’exécution d’un algorithme est une séquence d’opérations nécessitant plus ou moins
de temps. Pour mesurer ce temps, il faut préciser quelles sont les opérations
élémentaires à prendre en compte.
Pour un algorithme numérique ce sont les opérations arithmétiques de base
(addition, multiplication, soustraction, division...), pour un algorithme de tri, ce sont les
comparaisons entre éléments à trier (opérations plus coûteuses). lire ou modifier un
élément d’un tableau, ajouter un élément à la fin d’un tableau, affecter un entier ou un
flottant. Les transferts de valeurs ou affectations sont souvent négligées.
8
CHAPITRE 1. THÉORIE DE LA COMPLEXITÉ ET MESURE DE PERFORMANCE
vue énergétique (imaginons les satellites…). Pour un problème donné, on peut donc être
amené à choisir entre un algorithme rapide mais utilisant beaucoup de mémoire, et un
algorithme plus lent qui utilise la mémoire de façon modérée.
Définition 4.
L’algorithme a un coût qui est lié :
- au nombre d’opérations effectuées (opérations arithmétiques, logiques, transferts...),
- à l’espace mémoire occupé par les données.
Evaluer ce coût revient à mesurer ce qu’on appelle la complexité de l’algorithme, en
temps comme en espace. Il s’agit donc de dénombrer des opérations et des octets.
Définition 5.
Coût de A sur n: l’exécution de l’algorithme A sur la donnée n requiert CA(n) opérations
élémentaires.
Estimer le coût d’une fonction sur une entrée de taille donnée signifie estimer le
nombre de ces opérations élémentaires effectuées par la fonction sur l’entrée. La
complexité en mémoire consiste à estimer la mémoire nécessaire à une fonction pour son
exécution.
9
CHAPITRE 1. THÉORIE DE LA COMPLEXITÉ ET MESURE DE PERFORMANCE
Définition 7. La taille d'une donnée est simplement la taille d'un bon codage en
mémoire de cette donnée exprimée en nombres de bits.
La taille d'un codage d'un entier n sera :
[(log2(n + 1)], et non pas n.
∄ d'ambiguïté, T(A,R, n)= T(n).
la mesure du plus mauvais cas, car elle garantit que tout comportement de
l'algorithme A utilisera au plus T(A,R, n) éléments de la ressource R.
Définitions 8.
On définit le Cas le pire et le cas moyen.
n désigne la taille de la donnée à traité.
Dans le pire des cas : CA(n) := max x|x|=n CA(x)
En moyenne : CMoyA (n) := ∑ x|x|=n pn(x)*CA(x)
pn : distribution de probabilité sur les données de taille n.
Problème : les calculs des fonctions de complexité sont difficiles à faire de manière
exacte.
Solution : procède par approximations des notations (O, Ω et Θ).
10
CHAPITRE 1. THÉORIE DE LA COMPLEXITÉ ET MESURE DE PERFORMANCE
Algorithme: Problème
Complexité?
C(n+1)=C(n) O(1)
C(n+1)=C(n)+1 O(n)
C(n+1)=C(n)+ε O(log2(n))
2n C(n)+1
C(n+1)=C(n)+n O(n2)
C(n+1)=2*C(n) O(2n)
Définition 9.
I : l’ensemble des données d’instances d’un problème abstrait Π.
In : les données de taille n (le coût dépend de la donnée)
c(i) : le coût de l’algorithme résolvant le problème Π pour une donnée i∈ In.
On définit 3 types de complexité :
→ Le coût dans le pire des cas (l’algorithme est le moins performant) :
Walgorithme(n) = max{c(i) | i∈ In}
→ Le coût dans le meilleur des cas (l’algorithme est le plus performant) :
Balgorithme(n) = min{c(i) | i∈ In}
→ Le coût dans cas moyen :
Aalgorithme = ∑𝒊∈𝑰𝒏 𝐩(𝐢) ∗ 𝐜(𝐢)
𝟏
En général : Aalgorithme = |𝐈𝐧| ∑𝒊∈𝑰𝒏 𝐜(𝐢)
Définitions 10.
La complexité pratique est une mesure précise des complexités temporelles et spatiales
pour un modèle de machine donné.
11
CHAPITRE 1. THÉORIE DE LA COMPLEXITÉ ET MESURE DE PERFORMANCE
Définition 11.
Un algorithme est dit optimal (performant) si sa complexité est la complexité minimale
(la borne inférieure de complexité) parmi les algorithmes de sa classe.
Exemple 2 :
On peut montrer que tout algorithme résolvant le problème du tri a une complexité
dans le pire des cas en Ω(nlgn). Le tri par fusion est en O(nlgn) dans le pire des cas : il
est donc optimal.
12
CHAPITRE 1. THÉORIE DE LA COMPLEXITÉ ET MESURE DE PERFORMANCE
PARTIE 2.
CLASSES ET COMPLEXITE D'UN
PROBLEME
Définition.
La complexité d’un problème est la complexité minimale dans le pire des cas d’un
algorithme qui le résout. C’est souvent la complexité en temps qu’on considère mais on
peut s’intéresser à d’autres mesures comme par exemple la complexité en espace-.
Calculer la complexité d’un problème est une chose extremement ardue en général. On
se contente souvent d’encadrer:
Pour trouver une borne supérieure, il suffit de trouver UN algorithme.
Pour trouver une ”bonne” borne inférieure, les choses sont souvent plus dures... :
par exemple, pour montrer par exemple qu’un problème est de complexité au
moins exponentielle, il faut montrer que TOUT algorithme le résolvant est
exponentiel.
selon Sophie Tison, Cerner exactement la complexité d’un problème est souvent fort
difficile: quand les deux bornes coıncident, c’est l’idéal mais c’est assez rare!
13
CHAPITRE 1. THÉORIE DE LA COMPLEXITÉ ET MESURE DE PERFORMANCE
On ne considère ici que des problèmes décidables. On suppose que toutes les machines
de Turing considérées s'arrêtent toujours. On définit le temps et espace de calcul
relativement aux machines de Turing.
14
CHAPITRE 1. THÉORIE DE LA COMPLEXITÉ ET MESURE DE PERFORMANCE
TIME(t(n)) = { L | L peut être décidé en temps t(n) par une machine de Turing
déterministe }.
NTIME(t(n)) = { L | L peut être décidé en temps t(n) par une machine de Turing
non déterministe }.
Classes importantes : celles des problèmes qui peuvent être résolus en temps
polynomial par une machine de Turing.
3.1.1. La classe P
Définition 1. La classe des problèmes qui peuvent être résolus en temps polynomial
par une machine déterministe.
P = ∪k≥0 TIME(nk)
Définition 2. La classe P (ou PTIME) est la classe des problèmes de décision pour
lesquels il existe un algorithme de résolution polynomial en temps.
3.1.2. La classe NP
Définition 1. Classe des problèmes qui peuvent être résolus en temps polynomial
par une machine non déterministe.
NP = ∪k≥0 NTIME(nk)
15
CHAPITRE 1. THÉORIE DE LA COMPLEXITÉ ET MESURE DE PERFORMANCE
La classe NP contient P et est contenue dans ExpTime (et même dans Pspace). Pour
beaucoup de propriétés NP, on n’a pas trouvé d’algorithme polynomial, mais pour
aucune d’entre elles, on n’a prouvé qu’elle ne pouvait pas être décidée en temps
polynomial.
P ⊆ NP ⊆ EXP
- SPACE (f(n)) : classe des problèmes de décision solvables par une TM (à K+2
bandes) en espace f(n)
- NSPACE (f(n)) : classe des problèmes de décision solvables par une NTM (à K+2
bandes) en espace f(n)
- PSPACE: classe de tous les problèmes de décision solvables par une TM utilisant un
espace de travail limité par le polynôme de la taille de l'entrée.
- NPSPACE : classe de tous les problèmes de décision solvables par une NTM en
espace polynomial de la taille de l'entrée.
16
CHAPITRE 1. THÉORIE DE LA COMPLEXITÉ ET MESURE DE PERFORMANCE
4. NP-Complétude
Définition.
Un problème est simple quand le nombre d’étapes nécessaires à sa résolution peut-être
borné par un polynôme ; c’est un problème polynomial, que l’on notera avec P.
Sinon, il est difficile : il s’agit d’un problème non-polynomial, noté NP.
De petites variations d’un problème peuvent être suffisantes pour passer d’un problème
P à un problème NP :
- On veut partitionner un ensemble en deux sous-ensembles de même cardinalité, telle
que la différence des sommes de ces sous-ensembles soit maximale.
- On veut partitionner un ensemble en deux sous-ensembles de même cardinalité, telle
que la différence des sommes de ces sous-ensembles soit minimale.
Il est facile de couper un ensemble en deux de façon à avoir cette différence maximale.
Exemple :
On peut trier l’ensemble, et prendre comme parties les éléments de la fin et les éléments du
début.
→ Obtenir une différence minimale est un problème de combinatoire.
Le problème qui se pose maintenant est de voir lorsque deux problèmes sont du même
niveau de difficulté. L’outil de base pour établir des relations entre les complexités de
différents problèmes est la Réduction.
Soit X une donnée d’entrée pour le problème Q, dont on veut une réponse ‘oui’ ou ‘non’.
On transforme X en une donnée d’entrée Y pour le problème Π avec un algorithme A.
La réponse donnée au problème Π avec la donnée Y doit être la même que celle donnée au
problème Q avec la donnée Y.
17
CHAPITRE 1. THÉORIE DE LA COMPLEXITÉ ET MESURE DE PERFORMANCE
Même réponse
entrée entrée
x Q? 𝝅? y
18