Python L1, TD/TP 11.03

Dictionnaires ; Exercices

Je vous ai déjà dit, que nous allons travailler intensément avec les dictionnaires, car c'est la structure de données la plus importante en Python. Elle conditionne la totalité de la "couche objet" du langage, et détermine son caractère dynamique. Les dictionnaires sont utilisés comme les environnements (associations entre les noms des variables et leurs valeurs). Si vous ne connaissez pas les dictionnaires, vous ne connaissez pas Python. En L2 on n'a pas le temps de répéter le cours sur les dictionnaires, mais si on ne les connaît pas, c'est disqualifiant, cela empêche l'apprentissage de toute autre chose.

De plus, vous les trouverez, dans la forme très similaire, en Javascript (où ils s'appellent "objets"), et ils existent sous d'autres noms, dans d'autres langages (pratiquement tous), comme Java (HashMaps), Smalltalk, Lua (tables), ou Ruby (hashes).

Rappelons (pour ces oiseaux rares qui lisent ces notes) que les dictionnaires sont des tableaux indexés par d'autres choses que les entiers, par ex. par des chaînes, ou des tuples : A["dog"] "chien" ; d[1,7] = 666, etc. (Ici d[1,7] équivaut d[(1,7)], l'indice est un tuple). Les indices dans ce domaine s'appellent des clés et peuvent être hétérogènes (de types différents dans le même dictionnaire). Les clés n'ont pas le droit d'être modifiables ! Les dictionnaires peuvent être construits littéralement, par ex. : A = {"dog":"chien", "Smurf":"Schtroumpf", ("nom","prénom"):{"x":["Michael","Jackson"], 12 : ("abattoir",5)}}, etc. Ensuite on peut récupérer, modifier, ou insérer des valeurs dedans à volonté. On peut vérifier si une clé existe par : clé in dictionnaire, qui retourne vrai ou faux. La boucle for sur le dictionnaire, parcourt les clés.

Répétons : Les variables Python sont des clés dans des dictionnaires gérés en interne, et les valeurs des variables sont des valeurs associées à ces clés. En particulier, si vous demandez la valeur de globals(), vous aurez le dictionnaire système, avec les variables, fonctions et modules définis. Toute fonction a son dictionnaire "privé" de variables locales.


Exercice 0.

Inversion d'un dictionnaire.

Ceci est une "stratégie" très utile, pour la construction des annuaires inversés, pour plusieurs raisonnements statistiques, pour l'aide à la recherche (indexation "inversée" du domaine : Pour chercher les items dans un documents, on fait un index, la liste de mots-clés présents dans le texte ; mais pour un moteur de recherche, il est utile de savoir, pour un mot-clé, quels sont les documents qui les contiennent. C'est ça l'index inversé. Pour les annuaires téléphoniques inversés il y a des services spéciaux dans les Pages Jaunes.

Si vous avez un simple dictionnaire, par ex. d={'dog':'chien','red':'rouge','two':'deux'}, on peut aisément construire le dictionnaire inverse : {'chien':'dog','rouge':'red','deux':'two'}. On construit t=list(d.items()). Ensuite on assemble une liste t1 de tuples dans l'ordre inverse, et finalement d1=dict(t1).

Construisez une fonction qui effectue cette opération.
Cependant, cela ne marchera pas toujours de manière simpliste, les valeurs dans un dictionnaire peuvent être quelconques, et les clés non (doivent être "hashables"), la paire 'x':[2,10] n'est pas réversible. Supposons cependant que ce soit le cas, que toutes les valeurs utilisées soient hashables. Alors un autre problème se pose : Si d={'Jean':12,'Pierre':4,'Tom':12,'Marie':2,'Alain':0,'Laurent':2}, même si les entiers peuvent être utilisés comme clés, l'inversion simple n'est pas possible, car les clés se répètent. Quelle est la valeur attachée à 12?
Implémenter la stratégie suivante. Si une valeur est unique, pas de problème, on inverse les clé ↔ valeur. Sinon, on combine les valeurs identiques en une clé, et les clés en une liste de valeurs : d1={12:['Jean','Tom'],2:['Marie','Laurent'],4:'Pierre',0:'Alain'}. La construction du nouveau dictionnaire accumule les valeurs. Si le nombre de valeurs égales est plus grand que 2, ceci doit aussi marcher.

(Ceci est un "pattern de programmation" assez typique, utile par ex. pour la statistique des textes. Afin de trouver le nombre d'occurrences d'un caractère dans une chaîne, on la parcourt, et pour chaque caractère dedans, on l'utilise comme la clé dans un dictionnaire au début vide. Si la clé est absente dans le dictionnaire, on l'insère, avec la valeur 1, et si elle est dèjà là, in incrémente de 1 la valeur associée. Ici la procédure sera un peu différente, mais la philosophie reste la même. Faites cet exercice aussi, ainsi qu'un légèrement plus compliqué : le nombre d'occurrences des paires contiguës, par ex. de pq, qr, rs, tu, uv, dans 'pqrstuv'. Ainsi vous comprendrez mieux les idées de base.)


Exercice 1.

Mémoïzation (et le triangle de Pascal)

Ceci est un rappel ! (Nous avons déjà fait un exercice similaire, avec la suite de Fibonacci).

le développement binomial : \(\displaystyle{(a+b)^n = \sum_{m=0}^n {\left(\begin{array}{c} n \\ m \end{array}\right) a^m b^{n-m}}}\) utilise les coefficients binomiaux (ou de Newton) \(\left(\begin{array}{c} n \\ m \end{array}\right)\), ou \(C_n^m\).

Ils s'expriment par \(\left(\begin{array}{c} n \\ m \end{array}\right) = \displaystyle{\frac{n!}{m!\cdot (n-m)!}}\), mais peuvent être définis récursivement :
\(\left(\begin{array}{c} n \\ m \end{array}\right) = \left(\begin{array}{c} n-1 \\ m-1 \end{array}\right) + \left(\begin{array}{c} n-1 \\ m \end{array}\right)\), avec \(\left(\begin{array}{c} n \\ 0 \end{array}\right)=\left(\begin{array}{c} n \\ n \end{array}\right) = 1\).

Implémenter la procédure bino(n,m) qui calcule et retourne \(C_n^m\). Vérifier que si n dépasse 20, et m est proche de n/2 (le voisinage de la colonne centrale du triangle de Pascal), le temps de calcul commence à grandir, pour n=30, m=14 (disons), le temps d'attente devient insupportable.

Implémenter la stratégie de mémoïsation. Déclarer à l'extérieur de la fonction un dictionnaire, dont les clés sont des tuples (n,m) pour n=0 et 1 (trois au total, car m varie entre 0 et n).

La fonction commence par vérifier si le tuple de ses paramètres sont déjà dans le dictionnaire, st si c'est le cas, on retourne la valeur associée, qui est la réponse. Sinon, on lance la formule récursive (en vérifiant, bien sûr, si m=0 ou m=n), et le résultat est stocké dans le dictionnaire, avant le retour. Trouvez l'exercice sur Fibonacci.


Dictionnaires et matrices creuses

Exercice 2.

Comme il a été dit, on peut indexer les dictionnaires par des tuples, par ex. d[7,12] = "valeur". Ceci ressemble à l'indexation d'une matrice 2-dimensionnelle (sauf qu'avec des listes de listes en Python, on écrira d[7][12]). Or, dans les calculs de toute sorte, on trouve fréquemment des grandes matrices, dont la plupart (parfois presque tous) des éléments est égale à zéro. L'usage d'un dictionnaire à la place des listes peut économiser beaucoup de mémoire.

Vous pouvez penser à utiliser des fonctions auxiliaires pour les dictionaires, comme


Dictionnaires et Graphes

Exercice 3.

Un graphe est une structure topologique (des choses dans l'espace, qui ont des relations entre elles), composée de noeuds, et des arêtes (ou arcs), qui connectent les noeuds dans un certain ordre. Les noeuds peuvent (d'habitude : doivent) être identifiables, par ex. par des étiquettes : textuelles ou numériques. Les arcs aussi, mais nous pouvons considérer qu'un arc est identifié par la paire de noeuds qu'il connecte.

Les graphes sont des structures très universelles, qui peuvent décrire une multitude des choses, et plusieurs algorithmes dessus (par exemple : l'existence d'un chemin entre deux noeuds) ne dépendent pas des détails, seulement de la structure globale. Les graphes peuvent représenter les relations de dépendence, de voisinage, de similitude, etc. Une grande partie d'Informatique concerne les graphes, leur construction et leur analyse.

Représenter un graphe en Python, à l'aide des dictionnaires.

Les données de départ sont :

Voici le début de l'exercice, qui sera continué plus tard.


Animation

Votre devoir maison se concrétise, vous allez travailler sur la simulation des automates cellulaires, et vous allez les animer avec Matplotlib. Les détails vous seront donnés prochainement, à présent il faut s'entrainer avec Matplotlib, et ceci vous prendra du temps.
Je considère comme acquis :

TOUT ceci vous a déjà été présenté. Si vous avez des problèmes, posez des questions. Avant l'énoncé du devoir, vous aurez une courte collection d'exercices-essais. Faites-les ici ou/et chez vous, pas besoin de m'envoyer quoi que ce soit, mais si quelqu'un le fait, je pourrai lui apporter des conseils.


Modification interactive du graphique.


Semaine dernière
Semaine suivante
Retour à l'index