Dictionnaires, fonctions, code de Vigenère#

Le dictionnaire est une structure de données très utilisée. Elle est illustrée pour un problème de décryptage.

Fonctions#

Les fonctions sont des portions de programmes qui reproduisent les mêmes instructions. La fonction suivante calcule un polynôme de second degré $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.

[18]:

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 :

[19]:

def polynome(x, coefficient):
    return sum([x**i * c for i, c in enumerate(coefficient)])

De son utilisation ou appel :

[20]:

y = polynome(1.2, [1, 2, -1])  # calcul de -x^2 + 2x + 1 pour x = 1.2
y

[20]:

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 :

[21]:

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

[21]:

(2.9999999999999996, 9.965784284662087)

Les fonctions doivent porter des noms différents. Dans le cas contraire, seule la dernière existe.

[22]:

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

Exercice 1#

Les fonctions chr et ord sont symétriques l’une de l’autre : elles convertissent un nombre en lettre et réciproquement.

[23]:

print(chr(65), chr(97))
print(ord("B"), ord("b"))

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.

[24]:

def lettre_suivante(lettre):
    "à compléter"
    # ......
    # 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.

[25]:

def calcul(x):
    y = x**2
    z = x + y
    return z


# print(z)  # déclenche une exception

Mot-clé `return`#

Sans mot-clé ``return``, le résultat est ``None``.

[26]:

def calcul(x):
    y = x**2
    z = x + y


a = calcul(3)
print(a)

None

La fonction se termine après le premier return rencontré lors de l’exécution.

[27]:

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)

je passe par ici

[27]:

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.

[28]:

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)

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

[28]:

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.

[29]:

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 :

[30]:

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

[30]:

('d=', {'a': 'acronym', 'b': 'bizarre'}, 'l=', 2, 'b=', True, 'x=', 'acronym')

On utilise souvent un dictionnaire pour compter les lettres d’un texte :

[31]:

texte = "exemple de texte"
d = {}
for c in texte:
    d[c] = d.get(c, 0) + 1

d

[31]:

{'e': 6, 'x': 2, 'm': 1, 'p': 1, 'l': 1, ' ': 2, 'd': 1, 't': 2}

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 :

[33]:

f = [3, 4]
# d[f] = 0  # déclenche une exception

Lorsqu’on affecte une valeur à une clé, le dictionnaire crée la clé ou remplace la valeur précédente par la nouvelle :

[34]:

d = {}
d["a"] = 0  # création d'une clé
d["a"] = 1  # remplacement d'une valeur

d

[34]:

{'a': 1}

On peut aussi créer un dictionnaire de façon compacte :

[35]:

d = {s: len(s) for s in ["un", "deux", "trois"]}
d

[35]:

{'un': 2, 'deux': 4, 'trois': 5}

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.

[36]:

d = {s: len(s) for s in ["un", "deux", "trois", "quatre", "cinq"]}
d

[36]:

{'un': 2, 'deux': 4, 'trois': 5, 'quatre': 6, 'cinq': 4}

[37]:

ordonne = [(v, k) for k, v in d.items()]
ordonne

[37]:

[(2, 'un'), (4, 'deux'), (5, 'trois'), (6, 'quatre'), (4, 'cinq')]

[38]:

ordonne.sort()
ordonne

[38]:

[(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 :

[39]:

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.

[41]:

def mots_lettre_position(liste, lettre, position):
    "à compléter"
    # ......
    # 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 :

[42]:

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.

[43]:

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é) ?

[ ]:

Notebook on github