NOTION D’ALGORITHME

I- ALGORITHME :

1-  Définition :

Un algorithme est une suite d’instructions bien définie qui prend en entrée une
valeur ou un ensemble de valeur, et qui permet de réaliser une tache bien
spécifiée (Ex : retourner une valeur ou un ensemble de valeur).
Pour assurer la portabilité d’un algorithme dans tout langage, il est écrit dans
un langage appelé le pseudo-code.

2-  Compositions :
Un algorithme est composé de trois grandes parties :
-   La déclaration de variable
-   Le corps de l’algorithme composé d’une suite d’instructions.
-   La sortie qui représente l’opération attendue

Variable :
X : nombre entier
Y : nombre réel
DEBUT :
X=X+1
Y=3*Y
Z=X/Y
SORTIE :
Afficher Z

Dans la suite d’instructions élémentaires formant le corps de l’algorithme,

l'ordre est important.
Il existe deux grands types d’instructions :
-   Les instructions élémentaires et
-   Les instructions composées.

3-  Instructions élémentaires :
Une instruction élémentaire est soit :
-   Une affectation désignée par le symbole ←.
Ex : 𝑎 ← 3 :on affecte la valeur 3 à la variable a
-   Une opération élémentaire : addition, soustraction, multiplication ou
division.
-   Les comparaisons : < ou > ou =
-   L’accès à la mémoire.
Ex : Afficher a
4- Les instructions composées :

a- Les instructions de test :

Si condition alors
Instruction1
Sinon Si condition alors
Instruction2 Instructions
Fin si Fin si

Exemple :

Variable
a : nombre entier
b : nombre entier
DEBUT :
a←3 1af
b←9 1af
c←axb 1af+1am+1ope+1am= 4op
si c>5 alors 1am+1comp=2 ope
a←a+1 1afe+1am+1ope=3ope
sinon
b←b+2 1af+1am+1op=3ope
fin si
afficher(a,b,c)

b- La boucle non bornée :

Une boucle est une structure répétitive ou itérative, c’est à dire que la
boucle effectue n  fois un calcul sous le contrôle d’une condition d’arrêt.

Tant que condition faire

Instructions
Fin tant que

Application 1 :
Écrire un algorithme qui permet de convertir un nombre entier positif a en
base b. On utilisera la boucle tant que avec une condition d’arrêt.

c- La boucle bornée :
Pour compteur= valeur initiale à valeur finale faire
Instructions
Fin pour

Application 2 :
Écrire un algorithme qui permet de calculer la somme des n premiers entiers.

5-  Vérification d’un algorithme :

Pour vérifier qu’un algorithme marche bien, on peut le tester à la main pour
certaine valeur.

Application 3 :
Soit l’algorithme suivant :
NOM : FACT On considère l’algorithme ci-contre:
Variable : 1-   Tester, à la main, cet algorithme
N,i,S :entiers pour N   =   5 en donnant les
DEBUT: résultats à chaque itération.
LIRE N 2-   Quelle est l’importance de
S←1 déclarer S← 1.
Traitement :
Pour i=1 à N faire
S←Sxi
Fin pour
Sortie : afficher S

Remarques :
Dans le langage algorithmique le décompte des nombres commence par 1
tandis que dans le langage python, il commence par 0.

Application 3 :
Soit l’algorithme ci-dessous :
VARIABLE
t : TABLEAU d'entiers
x : nombre entier
tr : booléen (VRAI ou FAUX)
i : nombre entier
DEBUT
tr ← FAUX
i←1
TANT que i<=longueur(t) et que tr==FAUX:
si t[i]=x alors
tr ← VRAI
fin si
i ← i+1
fin TANT que
renvoyer LA VALEUR de tr
FIN
Faites tourner à la main l'algorithme "x est-il présent dans le tableau t ?" avec
t=[5,8,15,53] et x=12.

II- Complexité d'un algorithme :

1-­‐  Complexité  temporelle  d’un  algorithme  :

 
Pour  mesurer  la  performance  d’un  algorithme,  on  utilise  la  notion  de  complexité.  Il  existe  
deux  types  de  complexité  :  
§   La  complexité  spatiale  :  permet  de  quantifier  l’utilisation  de  la  mémoire.  
§   La  complexité  temporelle  :  permet  de  quantifier  la  vitesse  d’exécution.  
Nous  étudierons  la  complexité  temporelle.  
 
2-­‐  Complexité  d’une  affectation  :  
L’objectif   d’un   calcul   de   complexité   algorithmique   temporelle   est   de   pouvoir   comparer  
l’efficacité   d’algorithmes   résolvant   un   même   problème.   Dans   une   situation   donnée,   cela  
permet  donc  d’établir  lequel  des  algorithmes  disponibles  est  le  plus  optimal.  
 
a-­‐   Notation  :  
La  complexité  en  temps  d’un  algorithme  sera  exprimée  par  une  fonction,  
notée  𝑇  (pour  Time),  qui  dépend  :  
§   de  la  taille  des  données  passées  en  paramètres.  
On  notera  𝑛  le  nombre  de  données  à  traiter.  
§   de  la  manière  dont  les  différentes  valeurs  des  données  sont  réparties.  
 
b-­‐   Notion  de  coût  :  
Pour  comparer  des  algorithmes,  il  n’est  pas  nécessaire  d’utiliser  la  fonction  𝑇,  mais  
seulement  l’ordre  de  grandeur  asymptotique,  noté  𝑂  («  grand  O  »).  
 
Exemple  :  
§   𝑇1 𝑛 = 7 = 𝑂 1  
§   𝑇2 𝑛 = 12𝑛 + 5 = 𝑂 𝑛  
§   𝑇3 𝑛 = 4𝑛2 + 2𝑛 + 6 = 𝑂 𝑛2  
§   𝑇4(𝑛) = 2 + (𝑛 − 1)×5 = 𝑂(𝑛)  
 
c-­‐   Type  de  complexité  :  
 
 
 
 
 
  

 
d-­‐   Règle  de  calcul  de  la  complexité  des  opérations  élémentaires  :  
 
§   Les affectations comptent pour 1 unité de temps :
Exemple : 𝑎 ← 3 compte pour 1 unité de temps.

§   Les comparaisons comptent pour 1 unité de temps.

Exemple : 5 < 7 comptent pour 1 unité de temps

§   L'accès à la mémoire comptent pour une 1 unité de temps :

Exemple : lire a comptent pour 1 unité de temps.

§   Chaque opération élémentaire compte pour une 1 unité de temps :

Exemple : 2+6 comptent pour 1 unité de temps.

Application : Déterminer la complexité des algorithmes suivants :

1-   𝑎 ← 𝑎 + 3   3 ope T=O(1)

)
2-    

T = O(1)

 
 
 
e-­‐   Complexité  d’une  opération  conditionnelle  :  
Si  P  est  une  opération  conditionnelle  du  type  :  Si  b  alors  Q1  sinon  Q2  finsi  
La  complexité  de  P  est  :  
Coût(P)=  Coût(Text)+max(Coût(Q1),  Coût(Q2))  
 
 
  
Déterminer  la  complexité  de  ce  algorithme  :  
 

 
 
 
d-­‐   Complexité  d’une  boucle  :  
La  complexité  d’une  boucle  est  égale  à  la  multiplication  de  nombre  de  répétition  par  la  somme  
du  coût  de  chaque  instruction  𝑥6  corps  de  la  boucle  :  
𝐶𝑜û𝑡 𝑏𝑜𝑢𝑐𝑙𝑒  𝑓𝑜𝑟 = 𝐶𝑜û𝑡(  𝑥6 )  

𝐶𝑜û𝑡 𝑏𝑜𝑢𝑐𝑙𝑒  𝑤ℎ𝑖𝑙𝑒 = (𝐶𝑜û𝑡 𝑐𝑜𝑚𝑝𝑎𝑟𝑎𝑖𝑠𝑜𝑛 + 𝐶𝑜û𝑡(  𝑥6 ))  

 
Application  :    Déterminer  la  complexité.  
 
1-­‐    

 
2-­‐  

 
3-­‐  

 
 
 
  
 
e-­‐   Complexité  de  fonctions  composées  :  
 
Application  :  Déterminer  la  complexité  de  la  fonction  ci-­‐dessous  :  
 

 
 
f-­‐   Complexité  de  fonction  récursive  :    
 
Application  :  Soit  la  fonction  récursive  ci-­‐dessous  :  
 

 
 
1-­‐   Démontrer  que  la  complexité  est  donnée  par  la  formule  :  
𝑇H = 𝑇HIJ + 4      et      𝑇K = 2  
2-­‐   En  déduire  𝑇H = 4𝑛 + 2 = 𝑂(𝑛)