Introduction à l’algorithmique

Introduction

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.

Recherche d’occurrence

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 :

un algorithme s’écrit en langage naturel avec quelques notations informatiques. Mais il doit pouvoir être implémenté dans n’importe quel langage.
on fait commencer la numérotation des tableaux à 1 (vraisemblablement car l’algorithmique est née avant l’informatique).

Pour comprendre un algorithme, il faut le faire tourner à la main sur un exemple simple.

1) Prenons par exemple t=[2,4,8,12,45] et x=8 et faisons tourner l'algorithme.

i=1
present=FAUX
i<=5 et present=FAUX -> on rentre dans la boucle
t[i]≠8 -> On n'entre pas dans le si
i=2
retour au début de la boucle

i=2
present=FAUX
i<=5 et present=FAUX -> on rentre dans la boucle
t[i]≠8 -> On n'entre pas dans le si
i=3
retour au début de la boucle

i=3
present=FAUX
i<=5 et present=FAUX -> on rentre dans la boucle
t[i]=8 -> On entre dans le si
present=VRAI
i=4
retour au début de la boucle

i=4
present=VRAI
i<=5 et present=VRAI -> on n'entre pas dans la boucle
On renvoie VRAI

2) Faites tourner l’algorithme à la main avec t=[4,9,12] et x=23

i=1
present=FAUX
i<=3 et present=FAUX -> on rentre dans la boucle
t[i]≠23 -> On n'entre pas dans le si
i=2
retour au début de la boucle

i=2
present=FAUX
i<=3 et present=FAUX -> on rentre dans la boucle
t[i]≠23 -> On n'entre pas dans le si
i=3
retour au début de la boucle

i=3
present=FAUX
i<=3 et present=FAUX -> on rentre dans la boucle
t[i]≠23 -> On n'entre pas dans le si
i=4
retour au début de la boucle

i=4
present=FAUX
i>3 et present=FAUX -> on n'entre pas dans la boucle
On renvoie FAUX

Complexité

Nombre d'opérations

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

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.

Ordre de grandeur asymptotique

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

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

max = 2
i=2
i<=5 -> on rentre dans la boucle
t[i]>=2 -> On entre dans le si
max=6
i=3
retour au début de la boucle

max = 6
i=3
i<=5 -> on rentre dans la boucle
t[i]<6 -> On n'entre pas dans le si
i=4
retour au début de la boucle

max = 6
i=4
i<=5 -> on rentre dans la boucle
t[i]<6 -> On n'entre pas dans le si
i=5
retour au début de la boucle

max = 6
i=5
i<=5 -> on rentre dans la boucle
t[i]>=6 -> On entre dans le si
max=9
i=6
retour au début de la boucle

max = 9
i=6
i>5 -> on n'entre pas dans la boucle

on renvoie max

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.

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

somme = 0
i=1
i<=5 -> on rentre dans la boucle
somme = 2
i=2
retour au début de la boucle

somme = 2
i=2
i<=5 -> on rentre dans la boucle
somme = 8
i=3
retour au début de la boucle

somme = 8
i=3
i<=5 -> on rentre dans la boucle
somme = 12
i=4
retour au début de la boucle

somme = 12
i=4
i<=5 -> on rentre dans la boucle
somme = 13
i=5
retour au début de la boucle

somme = 13
i=5
i<=5 -> on rentre dans la boucle
somme = 22
i=6
retour au début de la boucle

somme = 22
i=6
i>5 -> on n'entre pas dans la boucle

moyenne = somme / 5 = 4.4
on renvoie 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 :

implémenter l'algorithme de recherche dans une fonction recherche(t, k) ;
générer un tableau de longueur n rempli avec des entiers aléatoires ;
enregistrer l’heure de début (voir le module time et la méthode time()) ;
exécuter l’algorithme de recherche avec un nombre qui n’est pas dans le tableau ;
avec l’heure de fin, afficher le temps d’exécution.

Essayer avec n = 10, 100, 1000… et voir si le temps d’exécution correspond bien à la complexité.

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