Algo Parcours Suite

Identification

Infoforall

3 - 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 02-03-09-10-11-21-24-25-26.

Documents de cours : open document ou pdf

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

01° Utiliser le jeu de cartes fourni et les indices de 0 à 7 pour placer 8 cartes (face non visible) en dessous des indices. On utilisera le jeton i pour préciser sur quel indice on travaille actuellement.

De façon à simuler le fonctionnement d'un ordinateur, on s'imposera de n'avoir qu'une carte visible à la fois : retourner une carte revient donc à évaluer t[i].

Déterminer un ensemble de manipulation permettant de savoir s'il y a un As parmi ces cartes. Dans ce cas, on veut obtenir l'indice où se trouve le premier As rencontré.

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

    i0

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

      ii + 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()

✎ 02° 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()

✎ 03° 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.

04° Utiliser le jeu de cartes fourni et les indices de 0 à 7 pour placer 8 cartes (face non visible) en dessous des indices. On utilisera le jeton i pour préciser sur quel indice on travaille actuellement et on dispose d'un jeton M qui pourra pointer vers l'une des cartes. Exemple : placer le jeton mémoire à proximité de la carte d'indice 5 permet de placer cette carte en mémoire. Pratique pour comparer la carte en cours à une carte en mémoire.

De façon à simuler le fonctionnement d'un ordinateur, on s'imposera de n'avoir qu'une carte visible à la fois : retourner une carte revient donc à évaluer t[i].

Déterminer un ensemble de manipulation permettant de pouvoir renvoyer la plus grande carte présente parmi les huits.

En cas d'égalité, ça ne change rien : on veut juste la valeur de la carte, pas la position.

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

    maxit[0]

    i ← 1

    TANT QUE i < longueur

      SI t[i] > maxi

        maxit[i]

      Fin du SI

      ii + 1

    Fin du TANT QUE

    Renvoyer maxi

05° 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

    maxit[0]

    POUR i variant de 1 à (longueur -1)

      SI t[i] > maxi

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

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

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

07° 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-

08° 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()

✎ 09° 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.

✎ 10° 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()

✎ 11° 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...

12° 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

Rappel : Preuve de terminaison

La preuve de terminaison d'un algorithme permet d'affirmer qu'il s'arrête de façon certaine (c'est à dire qu'il ne boucle pas infiniment) sur toutes les entrées valides qu'on lui fournit (c'est à dire les entrées respectant les préconditions).

Pour faire la preuve de terminaison, il faut montrer que :

  • ses boucles s'expriment sous la forme TANT QUE VARIANT > 0
  • avec un VARIANT de boucle pouvant s'écrire comme une suite un strictement décroissante d'entiers.

13° Montrer la terminaison de l'algorithme suivant 

  • 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

    maxit[0]

    i ← 1

    TANT QUE i < longueur

      SI t[i] > maxi

        maxit[i]

      Fin du SI

      ii + 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
i1

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
ii + 1

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

iN+1iN + 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.

4 - Séance 2 : et pour les dictionnaires ?

Cette partie nécessite que vous sachiez travailler avec les dictionnaires.

Deux solutions :

  1. Vous n'avez pas encore eu le temps de faire les activités Python traitant des dictionnaires (Stocker dans un dictionnaire et Lire le contenu d'un dictionnaire)
  2. Vous les avez réalisées mais ça date d'avant les vacances : plus trop de souvenirs...

Dans un cas comme dans l'autre, nous allons voir un petit résumé du fonctionnement des dictionnaires avant de passer à la suite de l'activité.

Voyons maintenant comment faire tout cela avec les dictionnaires.

Un petit rappel sur les dictionnaires ?

1 - Déclaration d'un dictionnaire en Python

Les éléments délimitateurs sont les accolades. Chaque élément du dictionnaire est séparé des autres par une virgule. On donne d'abord la clé, suivi du symbole : puis de la valeur associée à la clé.

Exemple avec un dictionnaire de traduction FRANCAIS (pour la clé) et ANGLAIS (pour la valeur)

1
dicoFR_AN = {'encodage' : "encoding", 'cryptage' : "encryption"}

Pour plus de clarté, on pourrait taper le code ainsi :

1 2 3 4
dicoFR_AN = { 'encodage' : "encoding", 'cryptage' : "encryption" }

Une fois, cette variable en mémoire, on peut chercher son type :

>>> type(dicoFR_AN) <class 'dict'>
2 - Nombre de couples clés-valeurs enregistrées

On peut utiliser la fonction native len pour obtenir le nombre de clés-valeurs enregistrées dans un dictionnaire.

Exemple

>>> d = {'encodage' : "encoding", 'cryptage' : "encryption"} >>> nbr = len(d) >>> nbr 2

Le dictionnaire contient bien 2 ensembles clés-valeurs, et pas 4 éléments indépendants.

3 - Rajouter une clé et sa valeur associée

Contrairement aux tableaux, on peut facilement rajouter des éléments dans un dictionnaire.

Par contre, attention à la syntaxe : on utilise des crochets et pas des accolades !

Exemple

>>> d = {'encodage' : "encoding", 'cryptage' : "encryption"} >>> d {'encodage': 'encoding', 'cryptage': 'encryption'} >>> d['balise'] = "tag" >>> d {'encodage': 'encoding', 'cryptage': 'encryption', 'balise': 'tag'} >>> nbr = len(d) >>> nbr 3

Le dictionnaire contient bien maintenant 3 ensembles clés-valeurs.

4 - Accès à l'une des valeurs

Pour accéder à l'un des éléments en particulier, on peut noter le nom de la variable-dictionnaire suivi de crochets et y placer la clé voulue. Comme avec un tableau mais avec la clé plutôt qu'avec un index chiffré.

Cela donne donc la notation monDictionnaire[maCle] donne maValeur.

Exemple

>>> d['boucle'] 'loop' >>> d['tableau'] 'array'
>>> d['lapin'] 'Traceback (most recent call last): File "", line 1, in d['lapin'] KeyError: 'lapin'

On remarquera que tenter d'accéder à une clé inconnue crée une erreur et une interruption du programme. Comme lorsqu'on demande l'index 20 d'un tableau qui ne comporte que 10 éléments.

La correspondance clé - valeur donne ceci sur l'exemple

Clé 'boucle' 'tableau'
Elément 'loop' 'array'
5 - Que peut-on utiliser pour faire une clé ?

Presque tout.

La seule chose qui ne puisse pas être une clé, c'est une variable mutable ou un contenu mutable.

6 - Le dictionnaire Python est mutable

Les objets dict sont des objets mutables : on peut modifier leur contenu sans modifier la référence de l'objet en lui-même.

En gros, comme les tableaux.

Du coup, on peut modifier un dictionnaire qu'on passe en paramètre à une fonction par effet de bord.

La puissance de cet objet est que

  • Si on veut modifier la valeur associée à une clé existence : on modifie la valeur
  • Si on veut "modifier" la valeur associée à une clé qui n'existe pas en réalité : on crée le couple
  • Un exemple avec un oubli un remplacement initial de overflow par overflaw :

    >>> d = {} >>> d['boucle'] = 'loop' >>> d['dépassement'] = 'overflaw' >>> d {'boucle': 'loop', 'dépassement': 'overflaw'}

    Tentons de changer la valeur associée à "dépassement" :

    >>> d['dépassement'] = 'overflow' >>> d {'boucle': 'loop', 'dépassement': 'overflow'}

    Et pour rappel : si la clé n'existe pas, on crée juste une nouvelle entrée :

    >>> d['balise'] = 'tag' >>> d {'boucle': 'loop', 'dépassement': 'overflow', 'balise': 'tag'}
7 - Connaître l'existence d'une clé

C'est très facile, puisque c'est fondamental pour ne pas déclencher d'erreur.

Il existe un mot-clé Python qui permet de tester l'existence d'un élément dans un conteneur : in (dans, en anglais)

Il suffit d'évaluer l'expression suivante : cleTestee in monDict : l'interpréteur Python va renvoyer une valeur booléenne : True ou False.

Un exemple :

>>> d = {} >>> d['boucle'] = 'loop' >>> d['dépassement'] = 'overflow' >>> 'boucle' in d True >>> 'toto' in d False >>> 'loop' in d False

On notera donc qu'on teste l'existence de la clé et pas l'existence d'une valeur.

D'ailleurs, en réalité, il s'agit d'un raccourci pour l'expression suivante que nous allons voir dans la partie suivante : cleTestee in monDict.keys() : l'interpréteur Python va renvoyer une valeur booléenne : True ou False.

Un exemple :

>>> d = {} >>> d['boucle'] = 'loop' >>> d['dépassement'] = 'overflow' >>> 'boucle' in d True >>> 'toto' in d False >>> 'loop' in d False
8 - 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.

>>> d = {'alice':12, 'bob':45, 'clark': -2} >>> d.keys() dict_keys(['alice', 'bob', 'clark'])

Cela nous permettra d'écrire un code qui veut dire en Français : Pour chaque clé du dictionnaire, réalise ce qui est indenté.

>>> d = {'alice':12, 'bob':45, 'clark': -2} >>> for cle in d.keys(): print(cle) alice bob clark

Et si on veut les valeurs au contraire ?

Et bien, si on connaît la clé, on peut accéder facilement à la valeur associée :

>>> d = {'alice':12, 'bob':45, 'clark': -2} >>> for cle in d.keys(): print(d[cle]) 12 45 -2

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
def trouverCle(d, 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 d(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 d.keys(): if d[cle] == x: return cle return None # Inutile en réalité : ce serait fait automatiquement 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.

Cela nous permettra d'écrire un code qui veut dire en Français : Pour chaque clé du dictionnaire, réalise ce qui est indenté.

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

14° 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 d[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 d[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 d.items(): if valeur == x: return cle

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

16° Exécuter le code suivant pour placer la fonction en mémoire. La tester dans la Console. 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(d, 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 d(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 d.items(): if valeur == x: return cle return None # Inutile en réalité : ce serait fait automatiquement 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 du dernier passage, on aura cle valant 'c' et valeur valant 20.

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.

Pour la recherche du maximum et du minimum, 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'indice 0 n'existe pas.

L'une des solutions peut consister à placer None dans maxi 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(d): maxi = None for cle in d.keys(): if maxi == None: maxi = d[cle] elif d[cle] > maxi: maxi = d[cle] return maxi

17° Placer la fonction trouverMax et le dictionnaire lettres en mémoire. Tester l'instruction suivante dans la Console/Shell :

>>> trouverMax(lettres) 10006

Ca fonctionne. Mais ...

18° 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(d): maxi = - inf for cle in d.keys(): if d[cle] > maxi: maxi = d[cle] return maxi

19° Mettre en mémoire la fonction et le dictionnaire. Tester dans la console :

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

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

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(d): maxi = - inf for valeur in d.values(): if valeur > maxi: maxi = valeur return maxi
>>> 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.

✎ 21° Lancer la nouvelle fonction trouverCleMax ci-dessous lorsqu'on l'utilise comme présenté plus bas dans la Console. Quel est le type de la réponse obtenue ?

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(d): maxi = - inf cle_max = None for (cle, valeur) in d.items(): if valeur > maxi: maxi = valeur cle_max = cle return cle_max, maxi
>>> trouverCleMax(lettres)

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

✎ MAISON° Réaliser la fiche résumé de cette activité. Elle devra comporter les points suivants vous permettant de réviser rapidement :

  • Etre capable d'écrire seul l'algorithme permettant de chercher un élément x dans un tableau
  • Fournir une implémentation de cet algorithme sous forme d'une fonction Python avec un while
  • Fournir une implémentation de cet algorithme sous forme d'une fonction Python avec un for
  • Pouvoir expliquer quelle est la version la plus propre
  • Etre capable d'écrire seul l'algorithme permettant de chercher le plus grand élément dans un tableau
  • Etre capable d'écrire seul l'algorithme permettant de chercher le plus petit élément dans un tableau
  • Etre capable d'écrire seul l'algorithme permettant de chercher la valeur moyenne des éléments d'un tableau
  • Savoir comment fonctionne range en Python
  • Etre capable de lire la valeur associée à la clé d'un dictionnaire d
  • Etre capable d'utiliser la méthode keys pour obtenir une à une toutes les clés d'un dictionnaire d
  • Fournir une fonction Python permettant de trouver la plus grande valeur présente dans un dictionnaire
  • Etre capable de donner le coût de la recherche d'un élément, du maximum, du minimum ou de la moyenne dans un tableau ou un dictionnaire

✎ 24° Question pas facile. Modifier maintenant la fonction précédente : on veut renvoyer le pourcentage de présence de cette lettre par rapport aux autres.

Pour calculer ce pourcentage p, il faut réaliser le calcul suivant :

 p = NBR_LETTRE_MAX / NBR_TOTAL_LETTRES 

Il va donc falloir calculer le nombre total de caractères lus en faisant la somme des lettres rencontrées (7264+5222+10006+...) et le nombre de fois où le caractère le plus courant apparaît (10006 pour le e).

Pour respecter le principe "Une tâche = une fonction", commencez par créer une fonction somme qui renvoie le nombre total de caractères dans le dictionnaire qu'on lui transmet.

Ensuite, modifiez la fonction trouverCleMax pour qu'elle fasse appel à somme de façon à renvoyer le pourcentage p de cette lettre dans le texte.

✎ 25° Créer une fonction qui permette d'afficher à l'écran les clés et les valeurs associées à ces clés pour les clés de quatre lettres dont la valeur associée est 5 ou plus dans le dictionnaire ci-dessous qui ce discourstir de ce discours dont les mots ont été répertoriés :

d = {'le': 23, 'ministre': 1, 'des': 19, 'solidarités': 1, 'et': 21, 'de': 44, 'la': 15, 'santé': 2, 'a': 5, 'présenté': 1, 'une': 7, 'communication': 1, 'sur': 9, 'covid': 1, '19': 1, '': 185, 'à': 13, '13': 2, 'heures': 1, 'aujourd’hui': 1, '73': 1, 'cas': 3, 'ont': 3, 'été': 4, 'recensés': 1, 'territoire': 5, 'ce': 4, 'qui': 9, 'représente': 1, '59': 1, 'nouveaux': 1, 'en': 17, 'plus': 11, '12': 1, 'guéris': 1, 'deux': 3, 'décédés': 1, 'cette': 2, 'crise': 1, 'comporte': 1, 'trois': 1, 'stades': 1, 'chaque': 1, 'stade': 7, 'appelle': 1, 'réponses': 1, 'différentes': 1, 'france': 1, 'franchi': 1, '2': 3, 'du': 14, 'plan': 2, 'prévention': 3, 'gestion': 1, 'défini': 1, 'par': 3, 'les': 26, 'autorités': 2, 'virus': 6, 'commence': 1, 'circuler': 1, 'dans': 13, 'certaines': 3, 'parties': 1, 'national': 3, 'il': 7, 'est': 9, 'particulier': 3, 'concentré': 1, 'clusters': 4, 'premier': 1, 'cluster': 2, 'se': 10, 'trouve': 2, 'l’oise': 4, 'communes': 4, 'creil': 1, 'crépy': 1, 'valois': 1, 'vaumoise': 1, 'lamorlaye': 1, 'lagny': 1, 'sec': 1, 'second': 1, 'haute': 2, 'savoie': 2, 'commune': 2, 'balme': 3, 'l’objectif': 2, 'pouvoirs': 1, 'publics': 1, 'limiter': 3, 'diffusion': 2, 'd’empêcher': 1, 'ou': 2, 'tout': 1, 'moins': 1, 'retarder': 1, 'aussi': 2, 'longtemps': 1, 'que': 5, 'possible': 4, 'passage': 2, 'au': 8, '3': 1, 'où': 2, 'circulera': 1, 'largement': 1, 'population': 1, 'l’enjeu': 1, 'gagner': 1, 'temps': 1, 'pour': 8, 'mieux': 1, 'préparer': 1, 'si': 5, 'sortir': 1, 'l’épidémie': 1, 'grippe': 1, 'afin': 1, 'événements': 1, 'ne': 7, 'télescopent': 1, 'pas': 6, '1': 2, 'implique': 1, 'adaptation': 1, 'd’actions': 1, 'mesures': 7, 'propres': 1, 'n’ont': 1, 'raison': 2, 'd’être': 2, 'vient': 1, 'seulement': 1, 'chine': 1, 'd’italie': 1, 'n’y': 1, 'confiner': 1, 'personnes': 4, 'revenant': 1, 'zones': 4, 'avaient': 1, 'classées': 1, 'comme': 2, 'orange': 1, 'titre': 2, 'voyages': 1, 'non': 1, 'nécessaires': 1, 'continuent': 1, 'déconseillés': 1, 'contraintes': 1, 'justifient': 1, 'peuvent': 2, 'être': 3, 'levées': 1, 'élèves': 1, 'retour': 1, 'lombardie': 1, 'vénétie': 1, 'vont': 3, 'pouvoir': 1, 'retourner': 1, 'l’école': 1, 'revanche': 1, 'contraignantes': 2, 'décidées': 1, 'tous': 3, 'rassemblements': 6, 'collectifs': 1, 'interdits': 2, 'jusqu’à': 2, 'nouvel': 2, 'ordre': 2, 'cinq': 2, 'mentionnées': 1, 'sont': 4, 'particulièrement': 2, 'touchées': 1, 'établissements': 3, 'scolaires': 1, 'comptent': 1, 'contacts': 1, 'présentent': 2, 'donc': 1, 'un': 5, 'risque': 1, 'élevé': 1, 'rouvriront': 1, 'lundi': 1, 'sera': 2, 'proposé': 1, 'aux': 5, 'parents': 1, 'démarche': 2, 'd’évaluation': 1, 'permettra': 1, 'décider': 1, 'tester': 1, 'fonction': 1, 'ces': 3, 'investigations': 1, 'décideront': 1, 'quels': 1, 'inclure': 1, 'n’hésiteront': 1, 'fermer': 1, 'nécessaire': 3, 'toujours': 2, 'concernées': 1, 'recommandé': 2, 'habitants': 1, 'leurs': 2, 'déplacements': 2, 'ils': 4, 'déplacer': 1, 'nourrir': 1, 'faire': 1, 'courses': 1, 'mais': 2, 'doivent': 2, 'rendre': 1, 'renoncer': 1, 'inutiles': 1, 'recourir': 1, 'télétravail': 1, 'plutôt': 1, 'd’aller': 1, 'travailler': 1, 'reste': 3, 'vigilance': 1, 'symptômes': 1, 'mêmes': 1, 'applicables': 1, 'série': 1, 'raisonnables': 1, 'arrêtées': 1, 'convient': 1, 'd’abord': 1, 'rappeler': 1, 'efficaces': 1, 'quotidien': 1, 'laver': 1, 'mains': 1, 'très': 1, 'régulièrement': 1, 'tousser': 1, 'éternuer': 1, 'son': 1, 'coude': 1, 'utiliser': 1, 'mouchoirs': 1, 'usage': 1, 'unique': 1, 'rester': 1, 'chez': 1, 'soi': 1, 'quand': 3, 'on': 1, 'malade': 1, 'rappelé': 2, 'personne': 1, 'n’a': 1, 'besoin': 1, 'porter': 2, 'masque': 3, 'médecin': 1, 'demande': 1, 'd’en': 1, 'précipiter': 1, 'pharmacies': 2, 'demander': 1, 'peut': 1, 'créer': 1, 'pénurie': 1, 'instructions': 1, 'données': 1, 'délivrer': 1, 'sauf': 1, 'indication': 1, 'enfin': 2, 'avec': 4, 'brassage': 1, 'populations': 1, 'gouvernement': 1, 'décidé': 1, 'd’adopter': 1, 'politique': 1, 'stricte': 1, 'matière': 1, 'seront': 4, '5': 1, '000': 1, 'milieu': 2, 'confiné': 1, 'annulés': 2, 'préfets': 1, 'recevront': 1, 'indications': 1, 'annuler': 1, 'également': 2, 'lien': 2, 'maires': 1, 'y': 1, 'compris': 1, 'ouvert': 1, 'conduisent': 1, 'mélanges': 1, 'issues': 1, 'circule': 1, 'possiblement': 1, 'exemple': 1, 'maire': 2, 'paris': 2, 'cannes': 2, 'semi': 1, 'marathon': 1, 'prévu': 3, 'dimanche': 1, '1er': 1, 'mars': 3, 'ainsi': 1, 'salon': 1, 'mipim': 1, '10': 1, 'carnaval': 1, 'd’annecy': 1, '6': 1, '8': 1, 'annulé': 1, 'provisoires': 1, 'sans': 1, 'doute': 1, 'appelées': 1, 'évoluer': 1, 'président': 1, 'république': 1, 'coordination': 1, 'niveau': 1, 'européen': 1, 'début': 1, 'semaine': 1, 'nouvelle': 1, 'réunion': 1, 'ministres': 1, 'fera': 1, 'point': 1, 'pratiques': 1, 'suivre': 1, 'conseils': 1, 'voyageurs': 1, 'ministère': 1, 'l’europe': 1, 'affaires': 1, 'étrangères': 1, 'évitant': 1, 'cela': 1, 'hors': 1, 'l’union': 2, 'européenne': 2, 'l’intérieur': 1}

✎ 26° Créer maintenant une fonction qui renvoie le mot de 5 lettres ou plus qui apparaît le plus dans le dictionnaire, ainsi que le nombre de fois où il apparaît.

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 09 2020
Auteur : ows. h.