NSI Première
NSI Première
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.
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.
Traduisez cet algorithme en codant une fonction recherche(tableau,valeur).
Cette fonction prendra en argument un tableau et une valeur à chercher, et renverra True ou False selon que la valeur est présente ou non dans le tableau.
Vous testerez votre recherche sur un tableau de 50 valeurs entières entre 1 et 100 générées aléatoirement.
from random import randint
def recherche(tableau:list, valeur: int)->bool :
.......................
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)
t1 contiendra la durée moyenne d'exécution de la recherche "naïve", et t2 celle de la recherche "Python".Compléter le code ci-dessus avec le code des deux fonctions. Lancer le script plusieurs fois de suite, et comparer les valeurs de durée obtenues à chaque fois.
Que peut-on conclure ?
A conditions d'exécution identiques ( même ordinateur, même taille de données à traiter,...) tous les algorithmes ne se valent donc pas : certains sont plus efficaces que d'autre, c'est à dire qu'ils résoudront plus rapidement le problème pour lequel ils sont prévus.
On dit que leur coût en temps (ou coût temporel) est différent : un algorithme efficace aura un coût en temps plus faible qu'un autre algorithme moins efficace.
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.)
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:
La complexité temporelle d'un algorithme correspond à l'évaluation du coût en temps d'un algorithme quand la quantité de données qu'il traite augmente.
Elle dépend souvent de la quantité de données notée n.
Généralement, on s'intéressera à la complexité temporelle dans le pire des cas.
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....
On dira que la complexité d'une recherche linéaire dans un tableau est "en O(n)"
La notation "O(n)" ( "grand O de n" ou "O de n") est une notation mathématique qui résume la définition précédente et nous évite de dire à chaque fois : "dans le pire des cas", "proportionnel à", ...
L'étude de la complexité d'un algorithme prend du sens quand n devient très grand; pour n = 10 ou n = 20, cette notion n'a en effet pas beaucoup d'intérêt la plupart du temps...
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 :
La complexité temporelle d'un algorithme nous donne des indications sur le temps d'exécution d'un programme, MAIS si la complexité est théorique et ne dépend que de l'algorithme, le temps d'exécution lui est une notion pratique et dépend :
En conclusion la complexité temporelle N'EST PAS le temps d'exécution d'un programme, elle ne permet de comparer que l'efficacité d'ALGORITHMES entre eux.
Vous trouverez sur cette page un peu plus de détail sur cette notion de complexité des algorithmes.
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.
Tests du résultat d'une fonction : les tests unitaires
La notion de tests est fondamentale en informatique : certains systèmes ne peuvent se contenter d'un fonctionnement approximatif mais doivent au contraire être robustes, c'est à dire fonctionner correctement dans toutes les situations possibles.
Pour prouver qu'une fonction fait toujours correctement le travail pour lequel elle est prévue, il faudrait théoriquement la tester avec tous les arguments possibles et imaginables; c'est bien entendu impossible...
On peut cependant se contenter de tester son bon fonctionnement sur quelques arguments bien choisis : on parle alors de tests unitaires
En Python, on peut utiliser le module doctest pour réaliser ces tests unitaires; il permet d'indiquer dans la docstring de la fonction des tests à réaliser et le résultat attendu si elle fonctionne bien.
Si ce n'est pas le cas, un message est alors affiché signalant qu'il faut corriger son code !
Pour les fonctions suivantes, vous utiliserez ce module pour vérifier "automatiquement" que votre code fournit le bon résultat pour quelques tests unitaires donnés.
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
Vous devez coder la fonction maximum(tableau) qui renvoie le maximum d'un tableau.
Vous n'oublierez pas les annotations et la docstring
Vous utiliserez le code ci-dessous, qui permet de réaliser "automatiquement" des tests de bon fonctionnement de votre fonction à l'aide du module doctest :
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
minimum(tableau) renvoyant le minimum d'un tableauL'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
minimum(tableau) renvoyant la moyenne des éléments d'un tableau.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 !!
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...)
On va pour commencer considérer une fenêtre de largeur 1 élément.
def moyenne_glissante(t : list, n:int)->list:
"""
Fonction de calcul de la moynne glissante des valeurs d'un tableau
t = tableau des valeurs d'origine
n = largeur de la fenêtre
Renvoie un nouveau tableau contenant les moyennes glissantes.
"""
.................
Quelques indications :
moyenne() un "sous-tableau" extrait du tableau principal, et contenant les éléments sur lequel le calcul de la moyenne doit se faire.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...
Il va falloir vous documenter pour :
Dans l'onglet Outils du site, vous trouverez quelques éléments d'aide pour l'utilisation des fichiers sous Python et sur l'utilisation du module Matplotlib; n'hésitez pas à consulter d'autres ressources pour compléter ces informations.
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.
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 :
Mais il est aussi nécessaire de les démontrer.
Nous n'allons pas aujourd’hui démontrer un algorithme mais uniquement voir les deux choses qu'il faudrait démontrer...
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 :
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 ).
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.
Quand on a démontré que :
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.
Voici quelques questions pour tester si vous avez bien compris les notions de complexité et de preuve d'un algorithme.