Chapitre : Notion d’un Algorithme et complexité
1. Définition d’un Algorithme : décrit une suite finie, organisée et non ambiguë
d’opérations élémentaires pour résoudre un problème posé.
Remarque : Cette solution n’est pas unique en générale.
2. Problématique de l’Algorithmique :
a. Trouver une méthode de résolution (exacte ou approchée) du problème.
Ex 1 : soient a,b,c trois nombres réels, quelles sont les solutions de l’équation :
ax2+bx+c=0
Solution : « la solution est bien connue ».
Ex2 : Soient les six nombres : a,b,c,d,e,f. quelles sont les solutions de l’équation :
ax5+bx4+cx3+dx2+ex+f=0.
Solution : « selon la théorie de Galois, pas de méthode générale pour le résoudre ».
b. Trouver une méthode efficace (étude de complexité)
3. Définition d’un programme : c’est la réalisation (l’implémentation) d’un algorithme au
moyen d’un langage donné sur une machine.
4. Quels est les critères attendus d’un algorithme ?
Les critères attendus d’un algorithme sont :
La terminaison.
La fiabilité par rapport (le temps et l’espace).
4.1 Terminaison : pas de boucle infinie.
Ex :
Void Syracuse (int a) {
While (a != 1){
If (a % 2 ==0) a/=2 ;
Else a=(3*a +1)/2 ;
[Link]( a) ;
}
}
La communauté scientifique n’a pas réussi à prouver que cet algorithme se termine
pour chaque entrée a.
Cet exemple montre le fait que nous n’avons pas de méthode générale pour décéder si
un algorithme termine ou non.
PROBLEME DE TERMINAISON
ENTREE : Algorithme A.
SORTIE : un booléenne indiquant si A terminé ou non.
C’est un problème indécidable, c’est-à-dire incalculable.
Ex : le problème de Hilbert : l’existence d’une racine carré entière pour une équation
polynomiale à coefficients entiers.
5. Notion de la complexité Algorithmique : c’est l’étude de l’efficacité d’un algorithme
de point de vue le temps et l’espace.
5.1 Complexité d’une entrée (variable ou Partie donnée)
a. Définition : la complexité ou la taille d’une entrée est le nombre d’octets
nécessaires à sa représentation.
b. Complexité d’un booléenne : un booléenne nécessite pour sa représentation un
octet sa complexité est constante.
Une matrice de n*m de booléennes est de complexité n*m=constante.
c. Complexité d’un entier :
i. Un entier = allouer un nombre fixe d’octets complexité =constante.
ii. Un entier = allocation dynamique d’octets qui nécessite sa représentation ;
Complexité = log 2(a+1)
Pour chaque entier a on a besoin n bits tel que : a <=2n-1 n =log2(a-1)
5.2 Complexité d’un programme (Partie instruction)
Un programme est un objet qui à partir de toute entrée permet d’exécuter des
instructions en consommant deux ressources :
Le temps : le nombre des instructions élémentaires pour être exécuter.
Espace : le nombre d’octet utilisés pour l’exécution d’un programme. Il ne tient pas
en compte l’espace utilisé par les entrées.
Instruction élémentaire : une instruction est dite élémentaire si elle peut être
exécutée en un temps fixe.
Pour chaque instruction Ik il existe nk instructions élémentaires.
NBIE() : Instruction entier
Séquence d’instructions :
I1
I2
S= …
…
Ink
NBIE(S)= ∑ NBIE(Ii)=n1 + n2 +n3 + ………..+ nk
Instructions conditionnelles
If (cond) EXP1
Cod =
Else EXP2
NBIE(Cod) = NBIE(cod) + max ( NBIE(EXP1), NBIE(EXP2))
Instruction d’itération finie bornée
Boucle Cond
ITFB = BI ;
FIN Boucle
NBIE(ITFB) = [NB(Cond) + NB(BI)] X NBr_itération
Instruction d’itération non bornée
NBIE(ITFB) = [NB(Cond) + NB(BI)] X MAX_NBr_itération
Ex : complexité en temps
La manipulation des entiers de taille fixe montre que les opérations comme l’addition
doit être considéré comme des opérations élémentaires.
A l’opposé si l’on considère des entiers de taille variables les opérations ne peuvent
être considérées comme élémentaires.
Int fact( int n){
Int f=1, i=1 ;
For (int i=1 ; i<=n ; i++) f=f*i ;
Return f ;
}
La complexité en temps est 0(n).
Ex : complexité en espace
C’est l’espace nécessaire pour l’exécuter un programme. On distingue deux cas :
Dans les algorithmes itératifs, l’espace utilisé peut se résumer à l’ensemble des
variables dynamique.
Ex : int *t= new int [100] ;
Dans les algo récursifs on ajoute au précédent l’espace réservé pour les appels
récursifs.
Int fact( int n){
If (n==1) return 1 ;
Else return n*fact(n-1) ;
}
La complexité en temps est 0(n).
La complexité en espace est 0(n).
6. Typologie de complexité
Il existe trois types de complexités, on illustre ces types par l’exemple ci-dessous :
Void T(int n){
If (n==0) [Link](« le nombre est nulle ») ;
Else if (n%2==0) while(n>1) n=n/2 ;
Else while (n>1)n=n-1;
}
6.1 Complexité en pire des cas
C’est le plus grand nombres d’opérations qui doivent être exécutés dans un programme.
Ex : la complexité de l’exemple ci-dessus en pire des cas est : O(n).
6.2 Complexité en moyenne des cas.
C’est la moyenne des complexités d’un programme.
Ex : la complexité de l’exemple ci-dessus en moyenne des cas est : O(log2(n)).
6.3 Complexité en meilleurs des cas.
C’est la complexité minimale d’un programme.
Ex : la complexité de l’exemple ci-dessus en meilleurs des cas est : O(1).
7. La complexité d’un problème
Il n’existe pas une méthode générale pour calculer la complexité d’un programme, mais on
cherche la classe à laquelle elle appartient.
7.1 Notion de Laundou
Définition : pour chaque fonction f(n), on dit f est d’ordre de grandeur de g(n) et on écrit f
est O(g(n)) s’il existe deux constantes a et b positives tel que :
a g(n) < f(n) < b g(n)
si n +∞ le rapport f(n)/g(n) est borné.
Ex :
F(n)= 3n2-7n+4
G(n)=n2
si n +∞ f(n)/g(n) =3 donc f(n) est d’ordre de grandeur de g(n).
7.2 Classes algorithmiques
Notation Type de 10^8 ops/sec
O(1) complexité
constante Temps constant
O(log(n)) logarithmique -7
10 secondes
O(n) linéaire -6
10 secondes
O(nlog(n)) quasi-linéaire -5
10 secondes
2 quadratique -4
O(n ) 10 secondes
3 cubique -2
O(n ) 10 secondes
p polynomiale 11 jours si p = 7
O(n )
n exponentielle 14
O(2 ) 10 années
O(n!) factorielle 142
10 années