Programmation 2 - TP2 ============================= Ce document est téléchargeable à l'adresse : https://pageperso.lis-lab.fr/~florian.bridoux/cours/PROG2/ Exercice 1. Découverte ----------- Tapez les commandes suivantes dans l’interpréteur : dico = {"Alice": 1.75, "Bob": 1.8, "Charlie": 1.72} print(dico) type(dico) dico["Alice"] dico["Bob"] dico["David"] dico["charlie"] len(dico) dico.pop("Bob") dico.append("Damien") dico["Elea"] = 1.9 print(dico) dico[3.14] = 42 dico[(1, 2, 3, 4)] ='1234' l = [1, 2] dico[l] = 0 dico[tuple(l)] = 0 print(dico) print(dico.get("Bob")) print(dico.get("Damien")) Exercice 2. Clés d’un dictionnaire ----------- Soit un dictionnaire Python associant des mots à leur définition, écrire une fonction filter_dict(dct, letter) qui créé un nouveau dictionnaire contenant les mots (et leur définition) commençant par une lettre letter donnée en paramètre. Testez votre fonction avec: dico = {"chien": "meilleur ami de l'homme", "chat": "encore mieux qu'un chien", "ecureuil": "super mignon"} print( filter_dict(dico, "c")) Exercice 3. Valeurs d’un dictionnaire ----------- Un dictionnaire associe des clés à des valeurs. Par construction les clés sont uniques, donc il est possible de connaitre le nombre de clés différentes avec len(d) où d est un dictionnaire. En admettant que les valeurs d’un dictionnaire sont faites de types primaires comme les chaînes decaractères ou les entiers, écrire une fonctionnum_different_values(d) qui renvoie le nombre de valeurs différentes qu’il y a dans un dictionnaire. Testez votre fonction avec: dico = {"Alice": 1.75, "Bob": 1.8, "Charlie": 1.75} print( num_different_values(dico) ) Exercice 4. Cryptographie ----------- Cet exercice met en pratique plusieurs méthodes de cryptographie (ou chiffrement). Chaque méthode utilise une clé pour modifier un message de manière à ce qu’on ne puisse plus le lire sans la clé (encryptage). Étant donné la clé, on peut toutefois appliquer l’opération inverse (décryptage) qui permet de retrouver le message d’origine. Dans cet exercice, on considèrera que les messages à crypter ou décrypter ne contiennent que des caractères alphabétiques en majuscules et des espaces. 1) Chiffre de César Cette méthode consiste à remplacer chaque lettre du message par la lettre se trouvant n rangs plus loin dans l’alphabet. On fait l’opération inverse pour effectuer un décryptage. Par exemple, si on choisit comme clé 3, en cryptant, A devient D,B devient E, etc. Pour décrypter, on applique une clé de -3, c’est-à-dire D devient A, E devient B, etc. On utilise l’indice décalé modulo 26, donc Z devient C. Cette méthode decryptographie aurait été inventée par César pour communiquer avec ses armées. a) Écrire une fonction make_alphabet(n) qui retourne un dictionnaire qui à chaque caractère majuscule de l’alphabet associe le caractère en positions plus loin dans l’alphabet (−25 <= n <=25). Le caractère espace devra être associé à lui-même. Indice :vous pouvez utiliser une chaîne de caractères contenant l’alphabet 'ABC...YZ'. b) Écrire une fonction cesar_crypt(key, message) qui crypte le message passé en paramètre étant donné comme clé le décalage à effectuer. Cette fonction utilisera make_alphabet pour créer un dictionnaire d’associations entre les caractères non-cryptés et les caractères cryptés. c) Décryptez le message “K BJNF QSPHSBNNFS FO QZUIPO” dont vous ne connaissez pas la clé. 2) Chiffre de Vigenère Afin de combler les faiblesses du chiffre de César, la méthode de Vigenère change le décalage à chaque caractère crypté. La clé est la séquence de décalages à appliquer, que l’on répète jusqu’à avoir traité tout le texte. Pour décrypter le message, on applique l’opposé des décalages. Par exemple, pour une clé de [1, 2, 3], on obtient En clair: "BONJOUR" Décalage: [+1,+2,+3,+1,+2,+3,+1] a) Écrire une fonction vigenere_crypt(key, message) qui crypte le message étant donné comme clé une liste d’entiers représentant les décalages à effectuer. Cette fonction devra utiliser une liste de dictionnaires contenant l’alphabet correspondant à chaque décalage. b) Déterminez le message qui se cache derrière “NE CTETXT FBV JLK” étant donné que sa clé de cryptage était [2, 0, 1, 9]. 3) Le chiffre du téléphone rouge Une méthode inviolable était utilisée pour crypter les communications pendant la guerre froide. L’idée était toujours d’utiliser un décalage variable selon l’indice du caractère du message, mais avec une clé aussi longue que le message pour qu’il ne soit pas possible de retrouver cette dernière à l’aide d’analyses statistiques. Le défaut de cette méthode est qu’il fallait faire passer la clé à la cible du message par un autre canal sécurisé (par exemple par la valise diplomatique). a) Écrire une fonction generate_key(n) qui génère une clé aléatoire de taille n à l’aide du module random, puis écrire une fonction coldwar_crypt(message) qui génère une telle clé, puis utilise la fonction vigenere_cryptpour crypter le message. La clé devra être affichée dans le terminal pour que l’utilisateur puisse l’envoyer par un autre moyen à son destinataire. Exercice 5. Tri par comptage ----------- Lorsque l’on travaille sur une liste contenant des entiers dans un intervalle relativement petit, il est possible de les trier à l’aide de l’algorithme suivant : — Soit l une liste d’entiers non triée. — Trouver le plus petit et plus grand élément de l, notés ci-après lmin et lmax. — Compter le nombre d’occurrences de chaque entier entre lmin et lmax dans l. — Créer une liste vide l2. — Pour chaque entier lmin <= i <= lmax en ordre croissant : — Ajouter n fois i à l2 où n est le nombre d’occurrences de i dans l. — Retourner la liste ordonnée l2. Implémentez cet algorithme en python3.