Algorithmes utilisant les tableaux

1. 1. Recherche d'une valeur dans un tableau

Nous allons nous intéresser à un algorithme simple : celui de la recherche d'un élément de valeur donnée dans un tableau.

Un tableau au sens algorithmique est implémenté en Python avec un type construit appelé liste Python, que vous avez déjà étudié en détails ici.

En particulier, vous connaissez donc la syntaxe du test d'appartenance d'une valeur à un tableau :

if valeur in tableau:
		.................		
			

Mais on ne sait pas ce que Python fait derrière cette syntaxe pour trouver l'élément dans le tableau.

1.1. 1.1 Algorithme "naïf"

La méthode "naïve", c'est à dire qui est la plus simple, pour trouver un élément dans un tableau est la suivante :

pour chaque élément successif du tableau :
	si l'élément est la valeur recherchée :
		alors renvoyer VRAI
renvoyer FAUX	
				

→ on parcourt donc le tableau élément après élément; si on trouve la valeur, on sort du parcours et de la fonction en renvoyant VRAI; si on arrive à la fin du parcours et que l'on n'a pas trouvé la valeur, on sort de la fonction en renvoyant FAUX.

from random import randint

def recherche(tableau:list, valeur: int)->bool :
	.......................


			

1.2. 1.2. Comparaison avec l'algorithme utilisé par Python

Est-ce l'algorithme utilisé par Python "en interne" pour tester l'appartenance d'une valeur dans un tableau ? Impossible de le savoir directement...mais nous allons essayer de comparer son temps d'exécution avec celui de notre algorithme "naïf".

Pour cela, nous allons utiliser le module timeit qui permet de comparer le temps d'exécution ( ou de plusieurs exécutions ) d'un script Python :

from random import randint
from timeit import timeit

def recherche_naive(tableau:list, valeur: int)->bool :
	# la fonction ci-dessus
	............

def recherche_python(tableau:list, valeur: int)->bool :
	# la fonction utilisant le test d'appartenance Python
	............	
	
# Programme principal
tab = ...........

t1 = timeit(stmt = 'recherche_naive(tab, 15)', globals=globals(), number = 1000)
print(t1)

t2 = timeit(stmt = 'recherche_python(tab, 15)', globals=globals(), number = 1000)
print(t2)
			

• stmt est une chaîne de caractères donnant le bout de code à exécuter
• number est le nombre de répétitions de l'exécution du code
• Le module mesure la durée moyenne ( en secondes ) de l’exécution des fonctions sur plusieurs exécutions successives ( en effet, cette durée est influencée par de nombreux paramètres extérieurs au code lui-même et varie donc d'une exécution à l'autre.).
  t1 contiendra la durée moyenne d'exécution de la recherche "naïve", et t2 celle de la recherche "Python".

1.3. 1.3 Conclusion :

1.3.1. Coût en temps d'un algorithme

Dans le cas de notre fonction de recherche, l'algorithme "naïf" a un coût en temps plus grand que celui utilisé en interne par Python, il est donc moins efficace que ce dernier.

( Remarque : on peut aussi comparer les algorithmes en fonction de leur coût en espace, c'est à dire la plus ou moins grande quantité de mémoire dont ils ont besoin pour fonctionner; cependant nous ne nous y intéresserons pas dans ce chapitre et les suivants.)

1.3.2. Complexité temporelle d'un algorithme

L'algorithme "naïf" est extrêmement simple, mais la structure du tableau ne permet pas de l'améliorer.
Essayons d'analyser le coût temporel cet cet algorithme, et déterminons ce que l'on appellera sa complexité temporelle.

Nous ne pouvons pas prévoir quand cet algorithme s’arrête, mais nous pouvons dire que:

• Au mieux, on va trouver l'élément dans la première case
• Au pire, on parcourra l'ensemble des n éléments du tableau (si l'élément recherché est absent du tableau ou si il est en dernière case).
• En moyenne, si l'élément est présent, on parcourra n/2 éléments du tableau.

Dans notre cas, la complexité de la recherche dans un tableau augmentera proportionnellement avec la taille du tableau : si le tableau contient 30 000 noms, le pire cas demandera 30 000 étapes; avec 60 000 noms, il y aura 60 000 étapes, etc....

1.3.3. Quelques exemples de complexité...

1.3.4. Lien avec la durée d'exécution d'un programme

Mais nous ne parlons ici que de la complexité temporelle d'un ALGORITHME !
Si nous voulons savoir quelle sera la durée d'exécution du programme c'est une autre question :

2. 2. Extremum ( maximum ou minimum ), moyenne

L'algorithme de recherche d'une valeur dans un tableau est basé sur le parcours du tableau et la comparaison de chaque élément à la valeur recherchée.
Sur cette base nous pouvons imaginer des traitement différents des éléments du tableau.

2.1. 2.1 Recherche du maximum

L'algorithme de recherche d'un maximum est le suivant :

maximum ← 0

pour chaque élément successif du tableau:
	si élément > maximum
		maximum ← élément

renvoyer maximum		
				

import doctest

def maximum(tableau:list)->int:
    """
        Docstring de la fonction :
            .....................
            
        Tests unitaires :
            
        >>> maximum([1, 10, 8, 17, 0, 3, 6, 12, 14, 18, 15, 4, 7, 16, 13, 2, 9, 19, 5, 11])
        19
            
        >>> maximum([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])
        1
            
        >>> maximum([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19])
        19
            
        >>> maximum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 0])
        19
        
        >>> maximum([48, 89, 75, 12, 31, 80, 86, 52, 52, 75, 26, 94, 48, 70, 76, 9, 6, 64, 71, 31])
        94
    """
    
    ................... # code de la fonction
	
# Programme principal

doctest.testmod()	# exécution des test unitaires
			
			

2.2. 2.2. Recherche du minimum

2.3. 2.3. Calcul d'une moyenne

L'algorithme de calcul d'une moyenne est le suivant :

somme ← 0

pour chaque élément successif du tableau
	ajouter élément à somme
	
moyenne ← somme / n ( n = nombre d'éléments du tableau )

renvoyer moyenne		
			

3. 3. Application : le filtrage numérique

3.1. 3.1. Pourquoi filtrer un signal numérique ?

Les signaux numériques ( par exemple la musique numérisée ) même si ils ont été enregistrés dans de bonnes conditions ( en studio par exemple ), ne sont pas exempts de défauts.

On « voit » par exemple que le signal ci-contre est en réalité une sinusoïde, mais que celle-ci est « parasitée » par de nombreux « pics » vers le bas ou le haut ; l’origine de ces parasites peut être diverse ( bruit de fond du secteur à 50 Hz, parasites aléatoires, interférences,...).
Dès lors, comment fait-on pour extraire uniquement le signal « utile » dans cet ensemble de données, à savoir récupérer une ( plus ou moins ) « belle » sinusoïde ?

Vous allez voir, ce n'est pas compliqué : un signal numérique, ce n’est rien d’autre qu’une succession de valeurs distinctes stockées dans un tableau; il suffit pour les filtrer de faire des calculs de moyenne sur ces valeurs, et ça, vous savez faire !!

3.2. 3.2. Calculer la moyenne glissante sur un ensemble de valeurs

Mais pour filtrer un signal, nous n’allons pas faire la moyenne de toutes les valeurs constituant le signal comme on l'a fait au 2.3 ( on obtiendrait alors zéro, le signal contenant à peu près autant de valeurs positives que négatives...) !

L’idée est en fait de calculer la valeur moyenne "à un instant donné" des valeurs, c’est à dire calculée sur quelques valeurs successives dans le tableau.

Le principe en est le suivant :

Pour chaque élément i du tableau :

    • on calcule la moyenne sur un sous-ensemble de n éléments du tableau avant et après l’élément i, celui-ci compris ( ce sous-ensemble est appelé « fenêtre » de calcul ; n est appelée « largeur » de la fenêtre )
    • on range la valeur moyenne comme élément d'un nouveau tableau
    • on passe à l’élément suivant ( i + 1)

On obtient ainsi un nouveau tableau contenant les moyennes successivement calculées
			

Voila un exemple avec une fenêtre de calcul de 1 élément ( 1 avant / 1 après, soit une moyenne glissante sur 3 éléments ) :

La fenêtre de calcul se "déplaçant" ainsi sur l’ensemble des valeurs semble "glisser" sur cet ensemble, d’où le nom de moyenne glissante utilisé pour ce calcul.

( Remarque : on constate que les premiers et les derniers éléments ne peuvent logiquement pas être traités avec cette méthode...)

3.3. 3.3. Mini-projet : filtrage d'un "vrai" signal

Vous allez maintenant appliquer le principe du filtrage par moyenne glissante à une série « réelle » de données issues d’un signal numérique.
Vous disposez pour cela du fichier signal_bruit.txt qui contient la suite des valeurs d’un signal « bruité » qu’il va falloir traiter...

4. 4. Preuve d'algorithme : Terminaison et Correction

Nous allons dans cette partie commencer à nous poser une question que nous reverrons en algorithmique cette année : la question de la preuve d'un algorithme.

4.1. 4.1 Pourquoi une preuve ?

Vous connaissez le théorème ci-contre et vous savez très bien dessiner un triangle rectangle quelconque et vérifier que ce théorème est correct.
Mais vous savez aussi que ce théorème a été démontré et qu'au delà de tous les tests que l'on pourrait faire, il a été vérifié théoriquement.

Et bien c'est la même chose pour les algorithmes; on peut :

• Les utiliser (en supposant qu'ils fonctionnent bien)
• Les tester avec des batteries de valeurs particulières ( les tests unitaires que vous avez faits ci-dessus )

Mais il est aussi nécessaire de les démontrer.

4.2. 4.2 comment structurer le raisonnement ?

Nous n'allons pas aujourd’hui démontrer un algorithme mais uniquement voir les deux choses qu'il faudrait démontrer...

4.2.1. 4.2.1 Terminaison

La première chose à démontrer c'est sa terminaison, c'est à dire le fait qu'il va s'arrêter, en dehors de toute autre considération.

En effet un algorithme, la plupart du temps, effectue un grand nombre d'actions et utilise donc une boucle. Il est important de savoir si l'algorithme va s'arrêter ( sans chercher à savoir s'il remplit bien son rôle ).

Par exemple dans l'algorithme de recherche de maximum que nous venons de voir :

mettre 0 dans maximum

pour tous les éléments du tableau
	si élément > maximum
		mettre élément dans maximum

renvoyer maximum		
				

On peut constater que :

• l'algorithme parcourt tous les éléments du tableau sans les modifier.
• Le test de comparaison est effectué pour chaque élément du tableau
• Une fois tous les éléments parcourus, l'algorithme s'arrête

Comme le tableau a nécessairement une longueur finie ( contrairement aux mathématiques, rien ne peut être infini en informatique, sauf certaines boucles mal codées...) l'algorithme va nécessairement se terminer.
Nous venons de prouver la terminaison de l'algorithme ( sans, encore une fois, avoir prouvé que celui ci nous donnait bien le maximum du tableau ).

4.2.2. 4.2.2 Correction et invariant de boucle

• Qu'un algorithme de recherche trouve bien l'élément cherché
• Qu'un algorithme de tri rend bien un tableau trié...

Et cette démonstration va s'appuyer sur une notion importante : l'invariant de boucle.
En effet un algorithme, la plupart du temps, effectue un grand nombre d'actions et utilise donc une boucle.
Pour appuyer la démonstration il faut donc trouver une proposition vraie tout au long du déroulement de l'algorithme.

Par exemple dans l'algorithme de recherche que nous venons de voir :

pour tout les éléments du tableau
	si l'élément est l'élément recherché
		renvoyer Vrai
renvoyer Faux	
			

Un invariant de boucle pourrait être :

"l'élément cherché est placé entre l'élément courant et la fin du tableau" 
			

Ces notions de démonstration et d'invariant de boucle ne sont pas faciles a aborder, car, la plupart du temps, la compréhension de l'algorithme semble nous rendre inutile sa démonstration... Mais sur des algorithmes plus complexes c'est une démarche mathématique importante.

4.2.3. 4.2.3. Conclusion

Quand on a démontré que :

• L'algorithme se termine ( preuve de terminaison )
• L'algorithme est correct ( preuve de correction )

On a alors réalisé une preuve mathématique de l'algorithme. On est sur de son bon fonctionnement dans n'importe quelle situation.
Il reste alors à le coder et un "bon" algorithme peut être "mal" codé, il faut donc bien faire attention, dans la phase d'implémentation, à respecter l'algorithme tel qu'il a été écrit.

5. 5. QCM

Voici quelques questions pour tester si vous avez bien compris les notions de complexité et de preuve d'un algorithme.