NSI Première

Différents algorithmes de parcours

⏪

⏬

1 - Recherche

2 - max, min

3 - Terminaison

Nous avons vu que parcourir un tableau élément par élément nécessite un algorithme dont le coût est linéaire : sa complexité est Θ(n).

Nous allons voir aujourd'hui d'autres algorithmes ayant la même complexité (le même cout) mais permettant de faire d'autres choses.

On y parlera d'ailleurs de tableaux

Logiciel nécessaire pour l'activité : Python 3 : Spyder, Edupython, Pizzo ...

A faire et peut être ramasser à la fin du cours ✎ : questions 7-8-9.

1 - Recherche du premier indice comportant un élément

⇩ ⇧ ⤊

Nous avions déjà vu un algorithme permettant de rechercher un élément dans un tableau dans l'activité précédente :

Algorithme de recherche

    i ← 0

    TANT QUE i < longueur et que t[i] est différent de x

      i ← i + 1

    Fin du TANT QUE

    SI i < longueur

      Renvoyer i

    Fin du Si

    Renvoyer VIDE

On remarquera que puisqu'il s'agit de lire les éléments sans savoir à l'avance où s'arrêter, on utilise une boucle non bornée TANT QUE.

On peut alors l'implémenter de différentes façons en fonction du langage utilisé.
Voici l'exemple de sa transposition directe en Python (vu dans l'activité précédente).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
def trouverIndex(t, x): '''Fonction qui renvoie l'indice de l'élément x dans le tableau t. None en cas d'échec de la recherche :: param t(list) :: un tableau contenant le même type d'élément que le paramètre x :: param x(au choix) :: l'élément qu'on cherche à trouver dans le tableau :: return (int) :: le numéro d'indice :: exemples :: >>> test = [10,20,30,40,50] >>> trouverIndex(test, 20) 1 >>> trouverIndex(test, 60) ''' i = 0 longueur = len(t) while i < longueur and t[i] != x: i = i + 1 if i < longueur: return i return None # Inutile en réalité : ce serait fait automatiquement if __name__ == '__main__': import doctest doctest.testmod()

✎ 01° Lancer le programme en mémoire pour vérifier qu'il passe bien les tests de la documentation.

Question : rajouter un autre exemple dans la documentation. Vérifier qu'il ne provoque pas d'erreurs.

Rappel : les exemples de la documentation sont bien de la DOCUMENTATION. C'est l'activation de la fonction testmod présente dans le module doctest qui permet d'utiliser ces tests en vérification automatique.

On peut néanmoins faire plus simple en Python en profitant des boucles FOR et du fait qu'on sorte immédiatement des fonctions dès qu'on rencontre un return.
De l'extérieur, ça ne change rien : seul le code interne est différent.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
def trouverIndex(t, x): '''Fonction qui renvoie l'indice de l'élément x dans le tableau. None en cas d'échec de la recherche :: param t(list) :: un tableau contenant le même type d'élément que le paramètre x :: param x(au choix) :: l'élément qu'on cherche à trouver dans le tableau :: return (int) :: le numéro d'indice :: exemples :: >>> test = [10,20,30,40,50] >>> trouverIndex(test, 20) 1 >>> trouverIndex(test, 60) ''' for i in range(len(t)): if t[i] == x: return i return None # Inutile en réalité : ce serait fait automatiquement if __name__ == '__main__': import doctest doctest.testmod()

✎ 02° Lancer le programme en mémoire pour vérifier qu'il passe bien les tests. Expliquer pourquoi la fonction ne renvoie pas systématiquement None alors que la dernière instruction de la fonction (ligne 17) est return None.

Ici, on n'utilise pas une boucle FOR nominative car on a besoin de renvoyer le numéro d'indice.

Utiliser un POUR pour créer une boucle non bornée ?

Revoyons la différence entre algorithme et implémentation.

Le dernier code est beaucoup plus simple que le premier MAIS il pose un problème : il possède une sortie finale qui est provoquée en fonction d'une condition à l'intérieur d'une boucle. Cela ne permet pas de vérifier facilement la correction du code (démontrer qu'il fait bien ce qu'on lui demande).

On fera donc bien la différence entre l'algorithme qui impose de faire une boucle non bornée et l'implémentation de cet algorithme en Python qui permet :

  • Soit d'utiliser un while (c'est plus "propre")
    • 1 2 3 4 5 6 7
    def trouverIndex(t, x): i = 0 longueur = len(t) while i < longueur and t[i] != x: i = i + 1 if i < longueur: return i
  • Soit d'utiliser un for associé à un return (c'est plus simple mais moins "propre")
    • 1 2 3 4
    def trouverIndex(t, x): for i in range(len(t)): if t[i] == x: return i

On pourrait même utiliser une boucle for plus proprement, pour recréer le comportement du while, mais cela reviendrait plus ou moins à recréer un code encore plus complexe que celui avec le while !

2 - Recherche de valeur maximale ou minimale

⇩ ⇧ ⤊

Nous n'avons pas le choix : il va falloir lire les éléments un par un. Et jusqu'au bout cette fois.

Il s'agit donc encore une fois d'un algorithme linéaire. On pourra donc écrire Θ(n).

↓
Index 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 68 69 42 72 7 64 10 60 32 74 32 36 79 9 29 60 86 56 16 52
max max max max max max

Comme vous le voyez, le principe est de lire les éléments un par un et d'écraser les valeurs anciennes du maximum si on en découvre une plus grande.

Seule la valeur finale de maxi après avoir parcouru tout le tableau a donc un sens.

Algorithme de recherche de maximum ("version TANT QUE")

Principe

On place le premier élément du tableau en tant que valeur maximale. Ensuite, on compare chaque élément lu séquentiellement à ce maximum : on remplace le maximum si l'élément lu est plus grand.

Description des entrées / sortie

  • ENTREES :
    • t : un tableau non vide : il possède au moins un élément.
    • (optionnelle selon les langages d'implémentation): longueur, le nombre d'éléments dans le tableau
  • SORTIE : la valeur maximale.

Description de l'algorithme

    maxi ← t[0]

    i ← 1

    TANT QUE i < longueur

      SI t[i] > maxi

        maxi ← t[i]

      Fin du SI

      i ← i + 1

    Fin du TANT QUE

    Renvoyer maxi

03° Cette version de l'algorithme présente une boucle non bornée : est-il vraiment judicieux d'utiliser une boucle non bornée pour la recherche du maximum ?

...CORRECTION...

Puisqu'on sait qu'on va devoir lire tous les éléments pour trouver le maximum, on peut également simplement utiliser une boucle bornée.

Algorithme de recherche de maximum ("version POUR")

Principe

On place le premier élément du tableau en tant que valeur maximale. Ensuite, on compare chaque élément lu séquentiellement à ce maximum : on remplace le maximum si l'élément lu est plus grand.

Description des entrées / sortie

  • ENTREES :
    • t : un tableau non vide : il possède au moins un élément.
    • (optionnelle selon les langages d'implémentation): longueur, le nombre d'éléments dans le tableau
  • SORTIE : la valeur maximale.

Description de l'algorithme

    maxi ← t[0]

    POUR i variant de 1 à (longueur -1)

      SI t[i] > maxi

        maxi ← t[i]

      Fin du SI

    Fin du POUR

    Renvoyer maxi

Encore une fois, pas de tableau vide à gérer.

On remarquera que le cas d'un tableau d'un seul élément ne pose pas problème : la boucle devrait aller de 1 à 0... Et ne démarrera donc pas.

04° Réaliser l'implémentation de cet algortihme via une fonction Python :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
def trouverMax(t): '''Fonction qui renvoie la valeur maximale lue dans le tableau non vide :: param t(list) :: un tableau non vide d'éléments comparables entre eux :: return (type des valeurs du tableau) :: la valeur maximale :: exemples :: >>> test = [10,20,60,40,50] >>> trouverMax(test) 60 >>> test = [10,20,60,40,50,100] >>> trouverMax(test) 100 >>> test = [100,20,60,40,50] >>> trouverMax(test) 100 ''' pass

La correction est fournie ci-dessous si vraiment vous bloquez.

...CORRECTION...

Voici l'implémentation Python utilisant cette version.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
def trouverMax(t): '''Fonction qui renvoie la valeur maximale lue dans le tableau :: param t(list) :: un tableau d'éléments qu'on peut comparer :: return (type des valeurs du tableau) :: la valeur maximale :: exemples :: >>> test = [10,20,60,40,50] >>> trouverMax(test) 60 >>> test = [10,20,60,40,50,100] >>> trouverMax(test) 100 >>> test = [100,20,60,40,50] >>> trouverMax(test) 100 ''' maxi = t[0] for i in range( 1, len(t) ): if t[i] > maxi: maxi = t[i] return maxi if __name__ == '__main__': import doctest doctest.testmod()

05° Trois questions :

  1. La boucle FOR commence-t-elle à zéro ?
  2. Pourquoi noter len(t) en ligne 20 Python alors qu'on a longueur -1 dans la version algorithme ?
  3. Quelle ligne poserait problème si le tableau était vide ?

...CORRECTION...

Non, elle commence à 1. Par défaut, si on ne précise pas la valeur de départ, l'interpréteur Python place 0. Mais on peut placer une première valeur.

La différence entre l'algorithme et le code Python sur la valeur finale notée vient du fait, qu'en Python, la valeur fournie pour la borne finale n'est pas atteinte : on s'arrête juste avant cette valeur.

C'est maxi = t[0] qui posera problème avec un tableau vide : l'élément 0 n'existe pas.

range

Taper range(6) permet d'obtenir l'ensemble suivant (0,1,2,3,4,5).

En réalité, Python remplit la valeur initiale par 0 et l'incrémentation par 1.

Taper range(6) revient à avoir tapé range(0, 6, 1)

Quelques exemples :

>>> for x in range(0,6,1): print(x,end='-') 0-1-2-3-4-5- >>> for x in range(2,6,1): print(x,end='-') 2-3-4-5- >>> for x in range(1,6,2): print(x,end='-') 1-3-5- >>> for x in range(6,1,-1): print(x,end='-') 6-5-4-3-2-

06° Modifer la fonction pour qu'elle accepte également des tableaux nuls. Il faudra alors qu'elle renvoie ... rien si l'entrée est un tableau vide.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
def trouverMax(t): '''Fonction qui renvoie la valeur maximale lue dans le tableau potentiellement vide :: param t(list) :: un tableau (potentiellement vide) d'éléments comparables entre eux :: return (type des valeurs du tableau) :: la valeur maximale :: exemples :: >>> test = [10,20,60,40,50] >>> trouverMax(test) 60 >>> test = [10,20,60,40,50,100] >>> trouverMax(test) 100 >>> test = [100,20,60,40,50] >>> trouverMax(test) 100 ''' pass

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
def trouverMax(t): '''Fonction qui renvoie la valeur maximale lue dans le tableau :: param t(list) :: un tableau d'éléments qu'on peut comparer :: return (type des valeurs du tableau) :: la valeur maximale :: exemples :: >>> test = [10,20,60,40,50] >>> trouverMax(test) 60 >>> test = [10,20,60,40,50,100] >>> trouverMax(test) 100 >>> test = [100,20,60,40,50] >>> trouverMax(test) 100 ''' if len(t) == 0: maxi = t[0] for i in range( 1, len(t) ): if t[i] > maxi: maxi = t[i] return maxi if __name__ == '__main__': import doctest doctest.testmod()

✎ 07° Ecrire une fonction trouverMin en vous inspirant de notre version maximale.

Dernière fonction typique : la moyenne.

On doit cette fois créer une variable-mémoire, disons s (s comme somme), dans laquelle on place la somme progressive des éléments du tableau.

Connaissant la longueur du tableau, on va alors renvoyer s / longueur.

✎ 8° Ecrire un algorithme (en français donc) qui réalise cette tâche. L'algorithme doit être transposable dans n'importe quel langage et ne doit pas contenir d'instructions non basiques.

Et voici une version Python possible de cette fonction :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
def trouverMoy(t): '''Fonction qui renvoie la valeur moyenne des valeurs du tableau :: param t(list) :: un tableau NON VIDE d'entiers ou de flottants :: return (float) :: la valeur moyenne :: exemples :: >>> test = [10,20,60,40,50] >>> trouverMoy(test) 36.0 >>> test = [100,20,60,40,50] >>> trouverMoy(test) 54.0 ''' s = 0 longueur = len(t) for i in range(longueur): s = s + t[i] return s / longueur if __name__ == '__main__': import doctest doctest.testmod()

✎ 9° La méthode du FOR avec l'indice n'est pas indispensable : on ne modifie pas les éléments du tableau. Créer une fonction qui calcule la moyenne mais en utilisant plutôt  for v in t , où on note v pour valeur.

Dernière chose : on remarque que si le tableau est vide, sa longueur vaut 0. C'est bien pour cela que nous avons rajouté la précondition documentaire sur la ligne 4.

4
:: param t(list) :: un tableau NON VIDE d'entiers ou de flottants

Diviser par longueur qui vaudrait 0 en L20 risque de poser des problèmes...

10° QCM. Ces algorithmes (recherche, maximum, minimum et moyenne) ont donc besoin de lire les éléments un par un. Sont-ils :

  • A : Des algorithmes à complexité constante (en Θ(1)) : temps d'exécution constant quelque soit la taille du tableau d'entrée
  • B : Des algorithmes à complexité linéaire (en Θ(n)) : le temps d'exécution double si l'entrée double
  • C : Des algorithmes à complexité quadratique (en Θ(n2)) : le temps d'exécution est multiplié par 4 si l'entrée double
  • D : Des algorithmes à complexité cubique (en Θ(n3)) : le temps d'exécution est multiplié par 8 si l'entrée double

...CORRECTION...

Comme on parcourt le tableau séquentiellement et une seule fois, la réponse est la réponse B.

3 - Terminaison

⇩ ⇧ ⤊

11° Montrer la terminaison de l'algorithme : on doit pouvoir montrer que le TANT QUE peut s'écrire TANT uN > 0 avec uN une suite strictement décroissante d'entiers.

  • ENTREES :
    • t : un tableau non vide : il possède au moins un élément.
    • (optionnelle selon les langages d'implémentation): longueur, le nombre d'éléments dans le tableau
  • SORTIE : la valeur maximale.

Description de l'algorithme

    maxi ← t[0]

    i ← 1

    TANT QUE i < longueur

      SI t[i] > maxi

        maxi ← t[i]

      Fin du SI

      i ← i + 1

    Fin du TANT QUE

    Renvoyer maxi

...CORRECTION...

Etape 1 : avant de rentrer dans la boucle

Ligne 2 : on voit que i vaut 1 initialement.

2
i ← 1

Comme nous avons fait 0 tour de boucle TANT QUE, nous noterons ceci :

i0 = 1 (1)

Etape 2 : que se passe-t-il à chaque tour de boucle ?

Ligne 6 : on voit qu'on augmente i de 1 à chaque tour de boucle. La raison vaut donc +1.

6
i ← i + 1

On peut donc écrire que i après n+1 tours de boucles vaut i après n tours plus 1.

iN+1 ← iN + 1

Nous avons donc affaire à une suite iN arithmétique de raison r = +1 et de valeur initiale i0 = 1 (voir (1)).

iN = i0 + r*n

iN = 1 + 1*n

On obtient donc juste :

iN = 1 + n (2)

Etape 3 : recherche du VARIANT

On cherche à voir si la condition de boucle de la ligne 3 peut s'écrire sous cette forme :

TANT QUE un > 0:

On commence la démonstration en récupérant la condition de boucle réelle et on tente de la ramener à la forme attendue pour prouver la terminaison :

TANT QUE i < longueur:

On remplace donc i par iN et on en tente de revenir à la forme attendue.

TANT QUE iN < longueur:

On commence par inverser le sens de l'inégalité.

TANT QUE longueur > iN :

On remplace iN en utilisant (2) :

TANT QUE longueur > (1 + n):

Pour revenir à la forme attendue, on doit passer les termes de droite à gauche :

TANT QUE longueur > + (1 + n):
TANT QUE (longueur - (1 + n) ) > 0:
TANT QUE (longueur - 1 - n) > 0:

Nous obtenons alors le VARIANT de boucle uN exprimé de cette façon :

TANT QUE uN > 0:    avec uN = (longueur - 1) - n

Etape 4 : conclusion

On voit que le variant est une suite d'entiers dont la raison est r = -1 : on perd 1 à chaque fois. La suite est donc décroissante.

Nous obtenons donc bien

  1. une condition du type  TANT QUE uN > 0 
  2. avec un variant  uN = (longueur - 1) - n  qui est bien une suite d'entiers strictement décroissante.

Nous venons donc de prouver la terminaison de cette boucle.

Dans les prochaines activités Algorithmique, nous verrons comment créer un algorithme plus performant qu'un algorithme linéaire mais nécessitant des données triées.

Activité publiée le 01 03 2021
Auteur : Andjekel
Source : ows. h.


⏪

⏫