L’algorithmique est une vaste discipline étudiant les moyens de trouver une suite d’opérations permettant de résoudre un problème ou de répondre à une question. On appelle ces suites d’instructions des algorithmes. Il existe de nombreux algorithmes comme une recette de cuisine ou des instructions pour construire un modèle en Lego. Nous nous intéresserons ici aux algorithmes du monde informatique qui peuvent néanmoins avoir des répercutions dans d’autres disciplines.
Nous verrons qu’il existe plusieurs familles de problèmes et donc d’algorithmes.
Nous allons étudier notre premier algorithme sur le problème de recherche d’occurrence, c’est à dire trouver si un élément est dans une liste (ou un tableau). Nous voulons donc savoir si un élément x est dans le tableau t. Voici donc un algorithme permettant de répondre à cette question :
VARIABLES
t : tableau d'entiers
x : nombre entier
present : booléen (VRAI ou FAUX)
i : nombre entier
DEBUT
present ← FAUX
i ← 1
tant que i<=longueur(t) et que present==FAUX:
si t[i]==x:
present ← VRAI
fin si
i ← i+1
fin tant que
renvoyer la valeur de present
FIN
Deux remarques :
1) Prenons par exemple t=[2,4,8,12,45] et x=8 et faisons tourner l’algorithme.
Déroulé de l'algorithme
| boucle | present | i |
| init. | FAUX | 1 |
| 1 | FAUX | 2 |
| 2 | FAUX | 3 |
| 3 | VRAI | 4 |
On sort de la boucle car present = VRAI et l'algorithme renvoie donc VRAI
2) Faites tourner l’algorithme à la main avec t=[4,9,12] et x=23
Déroulé de l'algorithme
| boucle | present | i |
| init. | FAUX | 1 |
| 1 | FAUX | 2 |
| 2 | FAUX | 3 |
| 3 | FAUX | 4 |
On sort de la boucle car 4 > 3 et l'algorithme renvoie donc FAUX
La complexité d’un algorithme permet de mesurer son efficacité et ainsi de le comparer aux autres algorithmes. Nous nous intéresserons au temps d’exécution pour mesurer la complexité (il est possible d’utiliser la mémoire utilisée). Pour estimer le temps d’exécution on comptera les opérations dans l’algorithme dans le pire des cas, c’est à dire dans le cas qui prend le plus de temps.
Par exemple pour l’algorithme précédent, le pire des cas est lorsqu’il ne trouve pas l’élément à chercher.
3) Reprenons donc l’algorithme précédent et comptons le nombre d’opérations pour qu’il se termine. Nous supposerons que le tableau en entrée contient n éléments.
VARIABLES
t : tableau d'entiers
x : nombre entier
present : booléen (VRAI ou FAUX)
i : nombre entier
DEBUT
present ← FAUX
i ← 1
tant que i<=longueur(t) et que present==FAUX:
si t[i]==x:
present ← VRAI
fin si
i ← i+1
fin tant que
renvoyer la valeur de present
FIN
Voici le contenu qui s’affiche quand on clique sur la ligne ci-dessus.
DEBUT
present ← FAUX [1 fois]
i ← 1 [1 fois]
tant que i<=longueur(t) et que present==FAUX: [n+1 fois]
si t[i]==x: [n fois]
present ← VRAI [0 fois]
fin si
i ← i+1 [n fois]
fin tant que
renvoyer la valeur de present [1 fois]
FIN
Il y a donc 3n+4 opérations.
Pour comparer les algorithmes il faut exprimer la complexité de manière plus simple qu’avec le nombre exact d’opérations. Pour cela, on ne va garder que l’ordre de grandeur asymptotique. C’est à dire qu’on s’intéresse uniquement à la plus grande puissance de n dans l’expression de la complexité. Et on notera le résultat avec un O majuscule (on dira « grand O »).
Par exemple 6n² + 5n + 45 = O(n²), on dira que la complexité est en « grand O de n² ».
4) Quelle est alors la complexité de notre algorithme ?
La complexité est en O(n).
5) Écrire un algorithme (en pseudo-code) qui permet de déterminer le maximum dans un tableau d’entiers. Faire tourner l’algorithme sur le tableau [2,6,4,1,9] puis déterminer la complexité de l’algorithme.
Déroulé de l'algorithme
VARIABLES
t : tableau d'entiers
max : nombre entier
i : nombre entier
DEBUT
max ← t[1]
i ← 2
tant que i<=longueur(t):
si t[i] > max:
max ← t[i]
fin si
i ← i+1
fin tant que
renvoyer la valeur de max
FIN
Déroulé de l'algorithme
| boucle | max | i |
| init. | 2 | 2 |
| 1 | 6 | 3 |
| 2 | 6 | 4 |
| 3 | 6 | 5 |
| 4 | 9 | 6 |
On sort de la boucle car 6 > 5 et l'algorithme renvoie donc 9
DEBUT
max ← t[1] [1 fois]
i ← 2 [1 fois]
tant que i<=longueur(t): [n fois]
si t[i] > max: [n-1 fois]
max ← t[i] [n-1 fois]
fin si
i ← i+1 [n-1 fois]
fin tant que
renvoyer la valeur de max [1 fois]
FIN
Il y a donc 4n opérations.
La complexité est en O(n).
6) Écrire un algorithme qui permet de calculer la moyenne des entiers d’un tableau. Faire tourner l’algorithme sur le tableau [2,6,4,1,9] puis déterminer la complexité de l’algorithme.
Déroulé de l'algorithme
VARIABLES
t : tableau d'entiers
somme : nombre entier
moyene : nombre flottant
i : nombre entier
DEBUT
somme ← 0
i ← 1
tant que i<=longueur(t):
somme ← somme + t[i]
i ← i+1
fin tant que
moyenne = somme / longueur(t)
renvoyer moyenne
FIN
Déroulé de l'algorithme
| boucle | somme | i |
| init. | 0 | 1 |
| 1 | 2 | 2 |
| 2 | 8 | 3 |
| 3 | 12 | 4 |
| 4 | 13 | 5 |
| 5 | 22 | 6 |
On sort de la boucle car 6 > 5 et l'algorithme renvoie donc 22/5 = 4.4
DEBUT
somme ← 0 [1 fois]
i ← 1 [1 fois]
tant que i<=longueur(t): [n+1 fois]
somme ← somme + t[i] [n fois]
i ← i+1 [n fois]
fin tant que
moyenne = somme / longueur(t) [1 fois]
renvoyer moyenne [1 fois]
FIN
Il y a donc 3n+5 opérations.
La complexité est en O(n).
7) Écrire un programme en Python qui va permettre de mesurer le temps d’exécution de l’algorithme de recherche d’occurrence (On appelle cela un benchmark). Le programme doit faire les choses suivantes :
Essayer avec n = 10, 100, 1000… et voir si le temps d’exécution correspond bien à la complexité.
Voici le contenu qui s’affiche quand on clique sur la ligne ci-dessus.
import random
import time
n = 10
t = []
# On remplit le tableau avec des nombres aléatoires entre 0 et n
print("Création du tableau…")
for i in range(n):
t.append(random.randint(0,n))
# Algorithme de recherche
def recherche(t,k):
"""
Cherche k dans le tableau t
"""
i = 0
present = False
while i < len(t):
if t[i] == k:
present = True
i = i + 1
return present
# Heure de début
t1 = time.time()
# On cherche un nombre qui n'est pas dans le tableau
recherche(t,n+1)
# Heure de fin
t2 = time.time()
print("n =",n,"| temps :",t2-t1)
n = 10 | temps : 2.86102294921875e-06
n = 100 | temps : 1.33514404296875e-05
n = 1000 | temps : 0.00015878677368164062
n = 10000 | temps : 0.0015091896057128906
n = 100000 | temps : 0.01606440544128418
n = 1000000 | temps : 0.15948057174682617
n = 10000000 | temps : 1.6848335266113281
La complexité est bien en O(n) car le temps augmente linéairement avec n (il est multiplié par 10 quand n est multiplié par 10).