.. _td1acenoncesession3rst: ================================================= 1A.1 - Dictionnaires, fonctions, code de Vigenère ================================================= .. only:: html **Links:** :download:`notebook `, :downloadlink:`html `, :download:`python `, :downloadlink:`slides `, :githublink:`GitHub|_doc/notebooks/td1a/td1a_cenonce_session3.ipynb|*` Le dictionnaire est une structure de données très utilisée. Elle est illustrée pour un problème de décryptage. .. code:: ipython3 from jyquickhelper import add_notebook_menu add_notebook_menu() .. contents:: :local: Fonctions ~~~~~~~~~ Les fonctions sont des portions de programmes qui reproduisent les mêmes instructions. La fonction suivante calcule un polynôme de second degré :math:`x^2+x-5`. A chaque fois qu’on appellera la fonction ``polynome``, elle fera le même calcul sur des ``x`` différents. Cela évite principalement d’avoir à recopier les mêmes lignes à chaque fois qu’on en a besoin. .. code:: ipython3 def polynome ( x ) : x2 = x*x return x2 + x - 5 Une fonction commence toujours par ``def``. Entre parenthèses, ce sont les paramètres (ou entrées de la fonction). Ce qui suit le mot-clé ``return`` est le résultat de la fonction (ou sa sortie). Parmi les fonctions, il y a celles qui existent déjà et celles que vous écrivez. La fonction ``cos`` existe déjà : elle fait un calcul qu’il n’est pas besoin de réécrire. La fonction ``polynome`` décrite plus haut n’existait pas avant de l’avoir définie. On distingue la définition d’une fonction : .. code:: ipython3 def polynome ( x, coefficient ) : return sum ( [ x**i * c for i,c in enumerate(coefficient) ] ) De son utilisation ou appel : .. code:: ipython3 y = polynome ( 1.2, [ 1, 2, -1] ) # calcul de -x^2 + 2x + 1 pour x = 1.2 y .. parsed-literal:: 1.96 On peut appeler une fonction depuis une autre fonction. Une fonction peut prendre autant de paramètres que l’on veut à condition qu’ils aient des noms différents. On peut aussi leur associer une **valeur par défaut** : .. code:: ipython3 from math import log # on importe une fonction existante def log_base ( x, base = 10 ) : return log (x) / log(base) y = log_base (1000) # identique à y = log_base (1000, 10) z = log_base (1000, 2) # logarithme en base deux y,z .. parsed-literal:: (2.9999999999999996, 9.965784284662087) Les fonctions doivent porter des noms différents. Dans le cas contraire, seule la dernière existe. .. code:: ipython3 def polynome ( x ) : # remplacée par la seconde fonction return x*x + x - 5 def polynome ( x, coefficient ) : return sum ( [ x**i * c for i,c in enumerate(coefficient) ] ) y = polynome(4) # déclenche une exception :: --------------------------------------------------------------------------- TypeError Traceback (most recent call last) in () 3 def polynome ( x, coefficient ) : 4 return sum ( [ x**i * c for i,c in enumerate(coefficient) ] ) ----> 5 y = polynome(4) # déclenche une exception TypeError: polynome() missing 1 required positional argument: 'coefficient' Exercice 1 ~~~~~~~~~~ Les fonctions `chr `__ et `ord `__ sont symétriques l’une de l’autre : elles convertissent un nombre en lettre et réciproquement. .. code:: ipython3 print ( chr( 65 ), chr (97) ) print ( ord("B"), ord ("b") ) .. parsed-literal:: A a 66 98 Le symbol ``%`` permet d’obtenir le reste d’une division entière. L’exercice consiste à écrire une fonction qui retourne la lettre suivante dans l’ordre alphabétique. La lettre qui suit ``z`` est ``a``. .. code:: ipython3 def lettre_suivante(lettre) : # ...... return .... Fonctions dans le détail ~~~~~~~~~~~~~~~~~~~~~~~~ Variable locale ^^^^^^^^^^^^^^^ **Une variable créée à l’intérieur d’une fonction n’existe pas à l’extérieur : c’est une variable locale.** C’est pourquoi le code suivant provoque une erreur car la variable ``z`` n’existe pas en dehors de la fonction ``calcul``. Les variables ``y`` ou ``z`` ne servent que d’intermédiaire de calcul. Le seul résultat qui sort de la fonction suit le mot-clé ``return``. .. code:: ipython3 def calcul(x) : y = x**2 z = x + y return z print(z) # déclenche une exception :: --------------------------------------------------------------------------- NameError Traceback (most recent call last) in () 4 return z 5 ----> 6 print(z) NameError: name 'z' is not defined Mot-clé ``return`` ^^^^^^^^^^^^^^^^^^ **Sans mot-clé ``return``, le résultat est ``None``.** .. code:: ipython3 def calcul(x) : y = x**2 z = x + y a = calcul(3) print(a) .. parsed-literal:: None La fonction se termine après le premier ``return`` rencontré lors de l’exécution. .. code:: ipython3 def valeur_absolue(x) : print("je passe par ici") if x < 0 : y = -x return y else : y = x return y print("je ne passe jamais par ici") valeur_absolue(-5) .. parsed-literal:: je passe par ici .. parsed-literal:: 5 Fonction récursive ~~~~~~~~~~~~~~~~~~ **Une fonction peut être récursive : elle s’appelle elle-même.** Mais il est important de savoir qu’il existe un cas dans lequel elle ne s’appelle pas pour arrêter la récursion. .. code:: ipython3 def recursive(x) : if x / 2 < 1 : print("je ne m'appelle pas pour x=",x) return 1 else : print("je m'appelle pour x=",x) return recursive (x/2) + 1 recursive( 10 ) .. parsed-literal:: je m'appelle pour x= 10 je m'appelle pour x= 5.0 je m'appelle pour x= 2.5 je ne m'appelle pas pour x= 1.25 .. parsed-literal:: 4 Dictionnaires ~~~~~~~~~~~~~ clé - valeur ^^^^^^^^^^^^ Une **liste** est un ensemble d’autres objets indexés par des entiers. Un **dictionnaire** est un ensemble d’autres objets indexés par presque n’importe quoi. .. code:: ipython3 d = { } # un dictionnaire vide d = { 'a' : 'acronym', 'b': 'bizarre' } # un dictionnaire qui associe 'acroym' à 'a' et 'bizarre' à 'b'. z = d ['a'] # z reçoit la valeur associée à 'a' et stockée dans le dictionnaire d Quelques fonctions utiles : .. code:: ipython3 d = { 'a' : 'acronym', 'b': 'bizarre' } l = len(d) # retourne le nombre d'élément de d b = 'a' in d # b vaut True si une valeur est associée à 'a', on dit aussi que la clé 'a' est présente x = d.get ('a', '') # x vaut d['a'] si la clé 'a' existe, il vaut '' sinon "d=",d,"l=",l,"b=",b,"x=",x .. parsed-literal:: ('d=', {'a': 'acronym', 'b': 'bizarre'}, 'l=', 2, 'b=', True, 'x=', 'acronym') On utilise souvent un dictionnaire pour compter les lettres d’un texte : .. code:: ipython3 texte = "exemple de texte" d = { } for c in texte : d[c] = d.get(c,0) + 1 d .. parsed-literal:: {'t': 2, 'l': 1, 'e': 6, ' ': 2, 'x': 2, 'm': 1, 'd': 1, 'p': 1} Les valeurs peuvent être n’importe quoi, y compris des listes ou des dictionnaires. Les clés doivent être des types `immuables `__ (nombre, chaînes de caractères, ``tuple`` incluant des types immuables). Si vous utilisez un autre type, cela déclenche une erreur : .. code:: ipython3 f = [3,4] d[f] = 0 # déclenche une exception :: --------------------------------------------------------------------------- TypeError Traceback (most recent call last) in () 1 f = [3,4] ----> 2 d[f] = 0 TypeError: unhashable type: 'list' Lorsqu’on affecte une valeur à une clé, le dictionnaire crée la clé ou remplace la valeur précédente par la nouvelle : .. code:: ipython3 d = { } d['a'] = 0 # création d'une clé d['a'] = 1 # remplacement d'une valeur d .. parsed-literal:: {'a': 1} On peut aussi créer un dictionnaire de façon compacte : .. code:: ipython3 d = { s:len(s) for s in ['un', 'deux', 'trois'] } d .. parsed-literal:: {'un': 2, 'trois': 5, 'deux': 4} notions de coût ^^^^^^^^^^^^^^^ Il est aussi rapide d’accéder à un élément d’un dictionnaire que d’accéder à un élément d’une liste : `TimeComplexity `__. C’est une `table de hashage `__ qui permet d’obtenir ce résultat. ordonner les éléments d’un dictionnaire ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Les éléments d’un dictionnaire ne sont pas ordonnées ou tout du moins ne le sont pas d’une façon prédictible. Pour les parcourir dans un ordre précis, il faut utiliser une liste puis les ordonner. L’exemple suivant montre comment ordonner les éléments par ordre croissant de valeur, puis par ordre alphabétique en cas d’ex aeco. .. code:: ipython3 d = { s:len(s) for s in ['un', 'deux', 'trois', 'quatre', 'cinq'] } d .. parsed-literal:: {'cinq': 4, 'deux': 4, 'quatre': 6, 'trois': 5, 'un': 2} .. code:: ipython3 ordonne = [ (v,k) for k,v in d.items()] ordonne .. parsed-literal:: [(4, 'cinq'), (5, 'trois'), (4, 'deux'), (6, 'quatre'), (2, 'un')] .. code:: ipython3 ordonne.sort() ordonne .. parsed-literal:: [(2, 'un'), (4, 'cinq'), (4, 'deux'), (5, 'trois'), (6, 'quatre')] **A quoi ça sert ?** on se sert beaucoup des dictionnaires pour compter la fréquences des caractères, des mots ou de couples de mots dans un texte. On les ordonne ensuite par fréquences décroissantes pour obtenir les mots ou caractères les plus fréquents. Exercice 2 : recherche dans une liste ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ On considère une liste de mots : .. code:: ipython3 mots = ['eddard', 'catelyn', 'robb', 'sansa', 'arya', 'brandon', 'rickon', 'theon', 'rorbert', 'cersei', 'tywin', 'jaime', 'tyrion', 'shae', 'bronn', 'lancel', 'joffrey', 'sandor', 'varys', 'renly', 'a' ] Il faut écrire une fonction qui retourne tous les mots de la liste qui ont un ‘y’ en seconde position. .. code:: ipython3 def mots_lettre_position (liste, lettre, position) : # ...... return [ .... ] Exercice 3 : utilisation d’un dictionnaire ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ On modifie la fonction précédente ``mots_lettre_position`` de telle sorte qu’elle s’écrive comme suit : .. code:: ipython3 def mots_lettre_position (dictionnaire_bien_choisi, lettre, position) : return dictionnaire_bien_choisi. get ( (position, lettre) , [] ) Construisez le dictionnaire ``dictionnaire_bien_choisi`` pour que cela fonctionne. Combien de mots sont stockés dans ``dictionnaire_bien_choisi`` ? **Reformulation** Lorsqu’on cherche un mot dans un dictionnaire (un vrai), on tourne peu de pages pour le trouver puisqu’ils sont triés par ordre alphabétique. Maintenant, si on souhaite trouver tous les mots dans la seconde lettre est ``e``, c’est impossible à moins de trier les mots par leur seconde lettre : il faudrait un dictionnaire différent pour chaque position de lettre. L’objectif de cet exercice est de concevoir une sorte de dictionnaire qui permette de retrouver tous les mots ayant telle lettre à telle position. Exercice 4 : crypter de décrypter selon Vigenère ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Le `code de César `__ est une permutation de lettre ou un décalage. Toutes les lettres du message sont décalées d’un nombre fixe : - ``JENESUISPASCODE`` - ``MHQHVXLVSDVFRGH`` Le `code de Vigenère `__ introduit un décalage qui dépend de la position de la lettre dans le message à coder. On choisit d’abord un mot qui servira de code (par exemple ``DOP``) puis on le traduit en décalages : ``[3, 14, 15]`` en servant de la position des lettres dans l’alphabet. Pour coder, on décale la première lettre de 3, la seconde de 14, la troisième 15, la quatrième de 3 à nouveau… L’objectif de cette partie est d’écrire une fonction qui crypte le message précédent et une autre qui décrypte. .. code:: ipython3 def code_vigenere ( message, cle) : # ...... à remplir return message_code A quelle condition le code de Vigenère est un simple code de César ? Pensez-vous qu’il soit possible de casser le code de Vigenère (de le décrypter sans la clé) ?