Algo Parcours Suite

Identification

Infoforall

2 - Différents algorithmes de parcours


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 et de dictionnaires.

Logiciel nécessaire pour l'activité : Python 3 : Thonny, IDLE ...

Prérequis ✎ : Python - Stocker dans un dictionnaire

Evaluation ✎ : questions 01-02-08-09-10-16-18.

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

Nous avons vu un algorithme permettant de rechercher un élément dans un tableau :

Algorithme de recherche

    index0

    TANT QUE index < longueur et que tableau[index] est différent de x

      indexindex + 1

    Fin du TANT QUE

    SI index < longueur

      Renvoyer index

    Fin du Si

    Renvoyer VIDE

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(tableau, x) : '''Fonction qui renvoie l'index de l'élément x dans le tableau. None en cas d'échec de la recherche :: param tableau(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'index :: exemples :: >>> test = [10,20,30,40,50] >>> trouverIndex(test, 20) 1 >>> trouverIndex(test, 60) ''' index = 0 longueur = len(tableau) while index < longueur and tableau[index] != x : index = index + 1 if index < longueur : return index return None if __name__ == '__main__' : import doctest doctest.testmod()

✎ 01° Lancer le programme en mémoire pour vérifier qu'il passe bien les tests. Rajouter un deuxième doctest au passage.

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(tableau, x) : '''Fonction qui renvoie l'index de l'élément x dans le tableau. None en cas d'échec de la recherche :: param tableau(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'index :: exemples :: >>> test = [10,20,30,40,50] >>> trouverIndex(test, 20) 1 >>> trouverIndex(test, 60) ''' for index in range(len(tableau)) : if tableau[index] == x : return index return None 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'index.

On peut faire la même chose avec les dictionnaires en lisant une à une les clés à l'aide de la méthode keys. Il suffit de modifier un peu le code : la recherche se fait juste par clé et pas par index.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
def trouverCle(dictionnaire, x) : '''Fonction qui renvoie la première clé associée à la valeur x dans le dictionnaire. None en cas d'échec de la recherche :: param dictionnaire(dict) :: un dictionnaire :: param x(au choix) :: l'élément qu'on cherche à trouver dans le dictionnaire :: return (comme les clés) :: la clé correspondant à la valeur x :: exemples :: >>> test = {'boucle':'loop', 'données':'data', 'tant que':'while'} >>> trouverCle(test, 'data') 'données' >>> trouverCle(test, 'stack') ''' for cle in dictionnaire.keys() : if dictionnaire[cle] == x : return cle return None if __name__ == '__main__' : import doctest doctest.testmod()
Méthode keys

La méthode des dictionnaires keys permet de créer un ensemble contenant les clés du dictionnaire. On pourra ainsi le lire une à une avec une boucle for.

13 14 15
for cle in dictionnaire.keys() : if dictionnaire[cle] == x : return cle

03° Expliquer le fonctionnement de ce programme. Vous pouvez prendre l'exemple du doctest si vous le désirez. Attention, vous devez être capable d'écrire ce programme seul lors du DS. Comprendre son fonctionnement est donc fondamental.

...CORRECTION...

Si le dictionnaire est {'boucle':'loop', 'données':'data', 'tant que':'while'}, alors on commence la boucle avec cle valant 'boucle'.

On vérifie donc via la ligne 14 si la valeur dictionnaire[cle] correspond bien à x.

Si c'est le cas, on sort de la fonction en renvoyant la clé.

Sinon, on passe à la clé 'données', puis la clé 'tant que'...

Comme vous le voyez, on est obligé de taper dictionnaire[cle] pour obtenir la valeur associée à la clé.

Python intègre une méthode qui renvoie la clé ET la valeur, sous forme d'un tuple. Voici comme cela fonctionne :

Méthode items

La méthode des dictionnaires items permet de créer un ensemble contenant des tuples : les clés du dictionnaire ET leurs valeurs associées. On pourra ainsi lire une à une clé et valeur avec une boucle for.

13 14 15
for (cle, valeur) in dictionnaire.items() : if valeur == x : return cle

04° En regardant la ligne 13, à quoi voit-on que items renvoie bien un tuple ? Cette indication est-elle indispensable pour l'interpréteur ?

...CORRECTION...

Aux parenthèses autour de (cle, valeur).

Elles sont au final plus destinées à l'humain qui lit le code qu'à l'interpréteur Python qui l'interprète.

Dans la plupart des codes, les parenthèses seront absentes.

05° Exécuter le code suivant pour placer la fonction en mémoire. La tester dans le Shell. Fournir au moins un de vos tests ainsi que le résultat. Expliquer alors comment fonctionne la fonction en vous basant sur votre exemple.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
def trouverCle(dictionnaire, x) : '''Fonction qui renvoie la première clé associée à la valeur x dans le dictionnaire. None en cas d'échec de la recherche :: param dictionnaire(dict) :: un dictionnaire :: param x(au choix) :: l'élément qu'on cherche à trouver dans le dictionnaire :: return (comme les clés) :: la clé correspondant à la valeur x :: exemples :: >>> test = {'boucle':'loop', 'données':'data', 'tant que':'while'} >>> trouverCle(test, 'data') 'données' >>> trouverCle(test, 'stack') ''' for (cle, valeur) in dictionnaire.items() : if valeur == x : return cle return None if __name__ == '__main__' : import doctest doctest.testmod()

...CORRECTION...

Si le dictionnaire est { 'a':45, 'b':55, 'c':20}

  • Lors de la première boucle, on aura cle valant 'a' et valeur valant 45.
  • Lors du deuxième passage, on aura cle valant 'b' et valeur valant 55.
  • Lors dudernier passage, on aura cle valant 'c' et valeur valant 20.

Maintenant que nous savons trouver le premier élément, nous allons voir d'autres lectures séquentielles : la recherche d'un maximum ou d'un minimum.

Comment choisir si on utilise keys ou items ?

C'est comme on veut. On a juste le choix et les deux méthodes sont au programme.

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 60 89 15 56 82 1 86 97 24 86 75 6 14 69 98 31 37 89 91 56

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 stockée dans maximum à donc un sens.

Algorithme de recherche de maximum

Principe

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

Description des entrées / sortie

  • ENTREES :
    • tableau : un tableau d'au moins un élément.
    • (optionnelle selon les langages d'implantation): longueur, le nombre d'éléments dans le tableau
  • SORTIE : la valeur maximale.

Description de l'algorithme

    maxitableau[0]

    index ← 1

    TANT QUE index < longueur

      SI tableau[index] > maxi

        maxitableau[index]

        indexindex + 1

      Fin du SI

    Fin du TANT QUE

    Renvoyer maxi

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

...CORRECTION...

index peut s'identifier à une suite arithmétique de raison 1 et de valeur initiale 1. car

  • index vaut 1 initialement
  • On augmente index de 1 à chaque tour de boucle

On peut donc écrire ceci : indexn = 1 + n.

On a donc écrire le TANT QUE de cette façon :

  • TANT QUE index < longueur
  • TANT QUE 1 + n < longueur
  • TANT QUE longueur > 1 + n
  • TANT QUE longueur - 1 - n > 0
  • La suite longueur - 1 - n est bien une suite strictement décroissante d'entiers.

    On peut donc bien écrire TANT QUE uN > 0 avec uN une suite strictement décroissante d'entiers.

    On vient de démontrer que la boucle se termine nécessairement.

Voici une implantation en Python utilisant les boucles bornées FOR sur les index : elle joue le même rôle que la boucle non bornée WHILE.

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(tableau) : '''Fonction qui renvoie la valeur maximale lue dans le tableau :: param tableau(list) :: un tableau d'éléments qu'on peut comparer :: return (type en fonction 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 = tableau[0] for index in range( 1, len(tableau) ) : if tableau[index] > maxi : maxi = tableau[index] return maxi if __name__ == '__main__' : import doctest doctest.testmod()

07° La boucle FOR commence-t-elle à zéro ?

Autre question : 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.

Sinon, c'est maxi = tableau[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-

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

Dernière fonction typique : la moyenne.

On doit alors créer une variable-mémoire, disons somme dans laquelle on place la somme progressive des éléments du tableau.

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

✎ 09° 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(tableau) : '''Fonction qui renvoie la valeur moyenne des valeurs du tableau :: param tableau(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 ''' somme = 0 longueur = len(tableau) for index in range(longueur) : somme = somme + tableau[index] return somme / longueur if __name__ == '__main__' : import doctest doctest.testmod()

✎ 10° La méthode du FOR avec l'index 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 element in tableau

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 tableau(list) :: un tableau NON VIDE d'entiers ou de flottants

11° 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 bien entendue la réponse B.

3 - Et pour les dictionnaires ?

Voyons maintenant comment faire tout cela avec les dictionnaires. Reprenons par exemple notre exemple des lettres dans le texte de Lovecraft, celui de l'activité Python.

1 2 3 4 5 6 7 8 9 10 11
lettres = { 't': 7264, 'h': 5222, 'e': 10006, 'd': 3662, 'u': 2296, 'n': 5681, 'w': 1922, 'i': 5163, 'c': 2065, 'o': 5750, 'r': 4665, 'b': 1325, 'y': 1538, 'p': 1310, 'l': 3647, 'v': 654, 'a': 6610, 'f': 1786, 'g': 1758, 's': 5026, 'm': 1884, 'k': 671, 'j': 55, 'x': 88, 'q': 77, 'z': 73 }

Nous allons devoir feinter pour l'initialisation puisqu'il n'y a pas de première valeur : l'index 0 n'existe pas.

L'une des solutions peut consister à placer None dans maximum au départ. Regardons ce que cela peut donner :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
lettres = { 't': 7264, 'h': 5222, 'e': 10006, 'd': 3662, 'u': 2296, 'n': 5681, 'w': 1922, 'i': 5163, 'c': 2065, 'o': 5750, 'r': 4665, 'b': 1325, 'y': 1538, 'p': 1310, 'l': 3647, 'v': 654, 'a': 6610, 'f': 1786, 'g': 1758, 's': 5026, 'm': 1884, 'k': 671, 'j': 55, 'x': 88, 'q': 77, 'z': 73 } def trouverMax(entree) : maximum = None for cle in entree.keys() : if maximum == None : maximum = entree[cle] elif entree[cle] > maximum : maximum = entree[cle] return maximum

12° Placer la fonction et la variable-dictionnaire en mémoire. Tester l'instruction suivante dans le Shell :

>>> trouverMax(lettres) 10006

Ca fonctionne. Mais ...

13° Imaginons que vous ayez un dictionnaire ayant 1 milliard d'entrées. Combien de fois allez-vous faire le test de la ligne 16 inutilement ?

...CORRECTION...

Comme on lit les entrées une à une et que maximum n'est None qu'au début, nous allons faire 999 999 999 fois le test pour rien.

Pour faire mieux, il faudra une valeur initiale qui soit la plus petite possible. Moins l'infini ?

Elle est encodé sous le nom de inf dans le module math de Python.

>>> from math import inf >>> -78000 > -inf True

Voilà une fonction de recherche de maximum basée sur une valeur initiale de -∞ et sur la méthode keys.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
from math import inf lettres = { 't': 7264, 'h': 5222, 'e': 10006, 'd': 3662, 'u': 2296, 'n': 5681, 'w': 1922, 'i': 5163, 'c': 2065, 'o': 5750, 'r': 4665, 'b': 1325, 'y': 1538, 'p': 1310, 'l': 3647, 'v': 654, 'a': 6610, 'f': 1786, 'g': 1758, 's': 5026, 'm': 1884, 'k': 671, 'j': 55, 'x': 88, 'q': 77, 'z': 73 } def trouverMax(entree) : maximum = - inf for cle in entree.keys() : if entree[cle] > maximum : maximum = entree[cle] return maximum

14° Mettre en mémoire la fonction et le dictionnaire. Tester dans le Shell :

>>> trouverMax(lettres) 10006

...CORRECTION...

Comme on lit les entrées une à une et que maximum n'est None qu'au début, nous allons faire 999 999 999 fois le test pour rien.

En réalité, nous n'avons pas besoin ici de la clé, nous n'avons besoin que des valeurs. Et bien, il existe une méthode permettant de faire cela !

  • La méthode keys permet de récupérer les clés du dictionnaire.
  • La méthode items permet de récupérer les clés ET les valeurs associées du dictionnaire.
  • La méthode values permet de récupérer les valeurs du dictionnaire.

15° Mettre en mémoire la fonction utilisant values et le dictionnaire. Tester dans le Shell :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
from math import inf lettres = { 't': 7264, 'h': 5222, 'e': 10006, 'd': 3662, 'u': 2296, 'n': 5681, 'w': 1922, 'i': 5163, 'c': 2065, 'o': 5750, 'r': 4665, 'b': 1325, 'y': 1538, 'p': 1310, 'l': 3647, 'v': 654, 'a': 6610, 'f': 1786, 'g': 1758, 's': 5026, 'm': 1884, 'k': 671, 'j': 55, 'x': 88, 'q': 77, 'z': 73 } def trouverMax(entree) : maximum = - inf for valeur in entree.values() : if valeur > maximum : maximum = valeur return maximum
>>> trouverMax(lettres) 10006

Comme vous pouvez le voir, on obtient juste la valeur maximum. Pas la lettre correspondante. Comment faire ? Utiliser la méthode items plutôt que juste values.

✎ 16° Utiliser la fonction trouverCleMax qui ne renvoie pas la VALEUR maximale mais un tuple contenant une CLE correspondant à la valeur MAXIMALE et la valeur elle-même.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
from math import inf lettres = { 't': 7264, 'h': 5222, 'e': 10006, 'd': 3662, 'u': 2296, 'n': 5681, 'w': 1922, 'i': 5163, 'c': 2065, 'o': 5750, 'r': 4665, 'b': 1325, 'y': 1538, 'p': 1310, 'l': 3647, 'v': 654, 'a': 6610, 'f': 1786, 'g': 1758, 's': 5026, 'm': 1884, 'k': 671, 'j': 55, 'x': 88, 'q': 77, 'z': 73 } def trouverCleMax(entree) : maximum = - inf cle_max = None for cle, valeur in entree.items() : if valeur > maximum : maximum = valeur cle_max = cle return cle_max, maximum

Que renvoie la fonction si on l'utilise ainsi dans le Shell ?

>>> trouverCleMax(lettres)

17° QCM. Cet algorithme qui a besoin de lire les éléments un par un est :

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

...CORRECTION...

Comme on parcourt une à une toutes les clés du dictionnaire : linéaire.

✎ 18° Question finale pas facile : modifier maintenant la fonction précédente : on veut renvoyer le pourcentage de présence de cette lettre par rapport aux autres. Il va donc falloir calculer en plus le nombre total de caractères lus en faisant la somme des lettres rencontrées. La fonction devra donc renvoyer la clé maximale et le pourcentage de cette lettre dans le texte.

4 - FAQ

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.

Si vous avez fait l'activité OpenData, vous savez ce que nous allons faire maintenant : des calculs et de l'évaluation non pas d'un tableau de valeurs mais d'un tableau d'enregistrements !

Activité publiée le 13 03 2020
Dernière modification : 13 04 2020
Auteur : ows. h.