Environnements de programmation Niv 1 - M1 OTG

TP NOTÉ

Ce TP noté nécessite une préparation préalable. Les documents sont autorisés, l'accès au cours et au web est autorisé, avec restriction sur les moyens d'échanges et de communications.

Exercice 1 : l'antiquité de la cryptographie⚓

Le code de César est une méthode de chiffrement de message très simple. Le premier personnage historique connu à l'avoir utilisé est Jules César (d'où son nom) pour ses communications militaires secrètes.

Le principe est très simple : il suffit de “ décaler ” chaque lettre du message de trois dans l'alphabet. Ainsi, 'a' devient 'd', 'b' devient 'e', 'c' devient 'f', … , 'w' devient 'z', 'x' devient 'a', 'y' devient 'b', et 'z' devient 'c'.

Pour cet exercice vous écrirez votre code dans un fichier selon la nommenclature ' [Nom_Prenom]_Crypto.py '.

1. Écrivez une fonction ' charToNum(c) ' qui prend en paramètre un caractère (i.e.: une chaîne contenant seulement un seul caractère) et qui renvoie un entier correspondant à la lettre associé dans l'alphabet commencant par 0. Voir le tableau ci-dessous:

abcdef ghijkl mnopqr stuvwx yz
012345 67891011 121314151617 181920212223 2425

Ainsi, par exemple:

  • charToNum('a') renvoie 0
  • charToNum('b') renvoie 1
  • charToNum('c') renvoie 2
  • …
  • charToNum('x') renvoie 24
  • charToNum('z') renvoie 25

Ici, et dans la suite de l'exercice, nous travaillerons avec des caractères de l'alphabet en minuscule seulement.

Indication: un façon simple, courte et élégante de faire est d'utiliser la différence par rapport à la numérotation de 'a' (dans la table de caractère) [◉] grâce à ' ord('a') '.

2.

a) Écrivez une fonction ' numToChar(n) ' qui prend en paramètre un entier et qui renvoie le caractère correspondant suivant le tableau vu ci-dessus.

b) Copier et modifier votre précédente en une fonction ' numToChar2(n) ' qui prend en paramètre un entier et qui renvoie le caractère correspondant suivant le tableau vu ci-dessus, mais cette fois-ci de façon cyclique. Ainsi, par exemple :

  • numToChar2(0) renvoie 'a'
  • numToChar2(-1) renvoie 'z'
  • numToChar2(-2) renvoie 'y'
  • numToChar2(25) renvoie 'z'
  • numToChar2(26) renvoie 'a'
  • numToChar2(27) renvoie 'b'

Indication: Servez-vous de l'opérateur modulo [◉] pour contraindre facilement un nombre dans un intervalle.

3.

a) En vous aidant des fonctions précédentes , écrivez une fonction ' changeCaractere(car, decal=3) ' qui prend un caractère ' car ' en paramètre et renvoie le caractère “ encrypter ” via un décalage de lettre donné par le paramètre ' decal ' (par défaut affecté à la valeur 3). Ainsi, par exemple :

  • changeCaractere('a') renvoie 'd'
  • changeCaractere('b') renvoie 'e'
  • changeCaractere('x') renvoie 'a'
  • changeCaractere('a', 6) renvoie 'g'
  • changeCaractere('e', -2) renvoie 'c'
  • changeCaractere('b', -3) renvoie 'y'

b) Copiez et modifiez la fonction précédente en une fonction ' changeCaractere2(car, decal=3) ' telle que lorsque le caractère passé en paramètre n'est pas compris dans l'alphabet minuscule ( entre 'a' et 'z' ) celui est ignoré de sorte à ce que la fonction renvoie le même caractère. Ainsi, par exemple :

  • changeCaractere2('a') renvoie 'd'
  • changeCaractere2(' ') renvoie ' '
  • changeCaractere2('b', -3) renvoie 'y'
  • changeCaractere2('!', 6) renvoie '!'
  • changeCaractere2('?', -2) renvoie '?'

Indication: En python, cette dernière condition peut être vérifiée simplement, pour un caractère affecté à une variable c, en testant si les expressions booléennes “ c < 'a' ” ou “ c > 'z' ” sont évaluées comme étant vraies.

c) Utilisez la fonction précédente pour écrire une fonction ' encrypt(chaine, decal=3) ' qui, pour une chaîne de caractères ' chaine ' passée en paramètre, renvoie une chaîne de caractères “ encryptée ” selon le déclage passé en paramètre via ' decal ' (par défaut affecté à la valeur 3). Ainsi, par exemple :

  • encrypt("patate") renvoie "sdwdwh"
  • encrypt("maison", 5) renvoie "rfnxts"
  • encrypt("canard", -3) renvoie "zxkxoa"

Indication: Une façon simple de construire un résultat est d'utiliser la concaténation de chaînes ( + ) avec une boucle for itérant sur une chaîne de caractères [◉] .

d) Écrivez une fonction ' decrypt(chaine, decal=3) ' qui, pour une chaîne de caractères (encryptée) ' chaine ' passée en paramètre, renvoie une chaîne de caractères “ décryptée ” selon le déclage passé en paramètre via ' decal ' (par défaut affecté à la valeur 3). Ainsi, par exemple :

  • decrypt("sdwdwh") renvoie "patate"
  • decrypt("rfnxts", 5) renvoie "maison"
  • decrypt("zxkxoa", -3) renvoie "canard"

Le cryptage par clé :

Le code César, beaucoup utilisé dans l'antiquité, est néanmoins facile à casser, notamment du fait que une lettre est toujours encrypter de la même manière, car le décalage est constant. Une amélioration à ce cryptage a été apporté en utilisant un décalage, des lettres du message à coder, en fonction des lettres d'un mot appelé “ clé ”. Le principe est simple, on additionne à chaque lettre du message (+1), les lettres du mot “ clé ” de façon cyclique.

Illustration par un exemple où, “ un message à coder ” est encrypter avec un mot “ clef ”.

4.

a) À l'aide des fonctions écrites en 1. & 2. écrivez une fonction ' addChars(c1, c2) ' qui “ additionne ” deux caractères +1 en fonction des numéros qui leur sont théoriquement associés plus un, tel que, par exemple :

  • addChars('a','a') renvoie 'b'
  • addChars('a','c') renvoie 'd'
  • addChars('z','a') renvoie 'a'
  • addChars('w','c') renvoie 'z'
  • addChars('w','d') renvoie 'a'

b) Écrivez une fonction ' subChars(c1, c2) ' qui “ soustrait ” deux caractère en fonction des numéros qui leur sont théoriquement associés moins un, tel que, par exemple :

  • subChars('a','a') renvoie 'z'
  • subChars('a','c') renvoie 'x'
  • subChars('z','a') renvoie 'y'
  • subChars('w','c') renvoie 't'
  • subChars('e','b') renvoie 'c'

c) Copiez et modifiez les deux fonctions précédentes en les fonctions ' addChars2(c1, c2) ' et ' subChars2(c1, c2) ' telle que, lorsqu'un des deux caractères passé en paramètre n'est pas compris dans l'alphabet minuscule la fonction renvoie ce même caractère. Si aucun des deux caractères n'est compris dans l'alphabet minuscule, la fonction renvoie le premier (e.g. 'c1'. Ainsi, par exemple :

  • addChars2('a','c') renvoie 'd'
  • addChars2('!','a') renvoie '!'
  • subChars2('w','c') renvoie 't'
  • subChars2('w','?') renvoie '?'
  • subChars2(';','#') renvoie ';'

5.

a) À l'aide des fonctions précédentes, écrivez une fonction ' encryptCle(chaine, cle) ' qui renvoie une chaîne de caractères qui correspond à ' chaine ' “ encryptée ” en utilisant la clé ' cle '. Ainsi, par exemple :

  • encryptCle("plume","a") renvoie "qmvnf"
  • encryptCle("tennis","ab") renvoie "ugopju"
  • encryptCle("table","salon") renvoie "mbnas"
  • encryptCle("bananes","swag") renvoie "uxohgbt"
  • encryptCle("tropfacilecetpnote","ezpz") renvoie "yrepkasiqeseypdoye"

Indication: Vous pouvez vous servir des opérateurs d'accès aux caractères d'une chaîne ( ' [] ' ) [◉] pour pouvoir accéder aux caractères de plusieurs chaînes différente au sein d'une même boucle.

b) Écrivez une fonction ' decryptCle(chaine, cle) ' qui renvoie une chaîne de caractères qui correspond à ' chaine ' “ décryptée ” en utilisant la clé ' cle '. Ainsi, par exemple :

  • decryptCle("qmvnf","a") renvoie "plume"
  • decryptCle("ugopju","ab") renvoie "tennis"
  • decryptCle("mbnas","salon") renvoie "table"
  • decryptCle("uxohgbt","swag") renvoie "bananes"
  • decryptCle("yrepkasiqeseypdoye","ezpz") renvoie "tropfacilecetpnote"

6. En utilisant les fonctions ci-dessus, écrivez un programme qui :

  1. Demande à l'utilisateur de choisir entre 2 modes de cryptage: le mode “ César ” et le mode “ par clé ” (on peut, par exemple, demander à l'utilisateur de rentrer des chiffres ( 1 ou 2 ) pour choisir)
  2. Demande à l'utilisateur de choisir entre 2 modes: le mode “ cryptage ” ou le mode “ décryptage ”
  3. Demande à l'utilisateur de taper un message
  4. Demande à l'utilisateur de rentrer:
    • Un décalage, si le mode de cryptage est celui de “ César ”
    • Une clé, si le mode de cryptage est “ par clé ”
  5. Décrypte ou encrypte le message selon les choix faits précédement.

Exemples d'utilisation :

Choisissez un mode de cryptage [ 1= code cesar; 2= par clef ] : 1
Quel mode [ 1= cryptage; 2= decryptage ] ? 1
message? cryptographions
decalage? 4
message encrypte : gvctxskvetlmsrw
 
Choisissez un mode de cryptage [ 1= code cesar; 2= par clef ] : 1
Quel mode [ 1= cryptage; 2= decryptage ] ? 2
message? gvctxskvetlmsrw
decalage? 4
message decrypte : cryptographions
 
Choisissez un mode de cryptage [ 1= code cesar; 2= par clef ] : 2
Quel mode [ 1= cryptage; 2= decryptage ] ? 1
message? notreprogrammemarchetil
clef?  letsgo
message encrypte : ztnkledtakhbyjgtyrtjnbs
 
Choisissez un mode de cryptage [ 1= code cesar; 2= par clef ] : 2
Quel mode [ 1= cryptage; 2= decryptage ] ? 2
message? ztnkledtakhbyjgtyrtjnbs
clef?  letsgo
message decrypte : notreprogrammemarchetil

Note : cet exercice est progressif et les questions sont donc dépendantes. Cependant, il n'est pas nécessaire de répondre aux questions 3 b) & 4 c) pour faire celles qui suivent.

Exercice 2 : des lignes aux fractales ⚓

Dans cet exercice, il s'agit de dessiner des fractales. Pour cela on va devoir implémenter en python des lignes sur un espace 2D (le objets sur cette espace sont donc construit avec des coordonées x et y. Ces lignes nous les représenterons comme des quadruplets, c'est à dire des 4-tuples, de la forme '  (x1,y1,x2,y2)  ' où '  x1  ' et '  y1  ' sont les coordonnées du point de départ de la ligne, et où '  x2  ' et '  y2  ' sont les coordonnées du point d'arrivée.

Pour dessiner les lignes il faudra utiliser un module complémentaire [◉], qui génère des fichiers .html. Pour cela le module fournit une fonction '  drawLineList()  ' qui prend en paramètre une liste de lignes. Il faudra donc mettre chaque lignes à dessiner dans une liste qu'on passera ensuite en argument de la fonction.

Dans cette exercice on fera usage des 2 formules de construction suivante (crééent une nouvelle ligne à partir d'une ligne) :

  1. $ligne_1(x_1,y_1,x_2,y_2) → \\~~~ (x_1+\frac{1}{5} \times (x_2-x_1), \\~~~ y_1+\frac{1}{5} \times (y_2-y_1),\\~~~ x_1+(\frac{1}{2} \times (x_2-x_1)-\frac{\sqrt{7}}{9} \times (y_2-y_1),\\~~~ y_1+\frac{1}{2} \times (y_2-y_1)+\frac{\sqrt{7}}{9} \times (x_2-x_1))$
  2. $ligne_2(x_1,y_1,x_2,) →\\~~~ (x_1+\frac{1}{2} \times (x_2-x_1)-\frac{\sqrt{7}}{9} \times (y_2-y_1), \\~~~ y_1+\frac{1}{2} \times (y_2-y_1)+ \frac{\sqrt{7}}{9} \times (x_2-x_1), \\~~~ x_1+ \frac{4}{5} \times (x_2-x_1), \\~~~ y_1+ \frac{4}{5} \times (y_2-y_1))$

En python, pour utiliser la fonction “ racine carré ”, il faut écrire en début de code:

#importer le module 'math'
import math

puis appeler la fonction '  sqrt()  ' comme ceci :

#renvoie la racine carré de 5
math.sqrt(5)

1.

a) Écrivez 2 fonctions qui prennent chacune une ligne l en parmètre:

  • ' line1(l) ' qui renvoie une ligne formée selon la formule (1).
  • ' line2(l) ' qui renvoie une ligne formée selon la formule (2).

Indication : Traduit en python, les calculs de ces deux fonctions, pour les coordonnées des lignes produites, s'écriraient respectivement :

x1 + (1/5)*(x2-x1)
y1 + (1/5)*(y2-y1)
x1 + (1/2)*(x2-x1) - (math.sqrt(7)/9)*(y2-y1)
y1 + (1/2)*(y2-y1) + (math.sqrt(7)/9)*(x2-x1)

x1 + (1/2)*(x2-x1) - (math.sqrt(7)/9)*(y2-y1)
y1 + (1/2)*(y2-y1) + (math.sqrt(7)/9)*(x2-x1)
x1 + (4/5)*(x2-x1)
y1 + (4/5)*(y2-y1)

b) Écrivez un programme, ' pyramide.py ', qui:

  1. créé une liste vide
  2. créé une ligne partant du point (50,400) jusqu'au point (750,400)
  3. utilise les fonctions précédentes pour générer deux nouvelles lignes
  4. rajoute les deux lignes en bout de liste
  5. génère l'affichage de la liste de lignes

Le fichier généré devrait produire l'affiche suivant:

2.

a) En utilisant les fonction précédentes, écrivez une fonction ' listSublines(l) ' qui prend une ligne en paramètre et renvoie une liste contenant les 2 lignes donnée selon les formules (1) et (2).

b) Écrivez une fonction ' generateListSublines(lst) ' qui prend en paramètre une liste de lignes et qui renvoie une liste contenant (uniquement) les lignes générées par la fonction précédente. Ainsi, par exemple :

l1= (50,400,350,400)
l2=(450,400,750,400)
lst= []
lst.append(l1)
lst.append(l2)

resLst= generateListSublines(lst)

lld.drawLineList(resLst)

génère un fichier qui produit l'affichage suivant:

3.

a) Créez une fonction ' fractale(n) ' qui prend en paramètre un entier ' n ' et une ligne ' l ' implémente l'algorithme suivant :

  1. Soit 'resL', 'tmpL' et 'iL' trois listes vides
  2. Ajouter 'l' à 'resL'
  3. Ajouter 'l' à 'iL'
  4. Pour i allant de 0 à n :
    1. Affecter à 'tmpL' le résultat de 'generateListSublines(iL)'
    2. Concaténer 'tmpL' à 'resL'
    3. Affecter à 'iL' la valeur/contenu de 'tmpL'
  5. renvoyer 'resL'

b) Écrivez un programme ' fractale.py ' qui demande à l'utilisateur un entier ' n '. Puis à partir d'une ligne ' l ' qui part du point (50,400) jusqu'au point (750,400) fait un appel à la fonction précédente en passant ' n ' et ' l ' en argument. Enfin, il devra génèrer l'affichage de la liste de lignes ainsi obtenu.

Ainsi, par exemple, si l'utilsateur rentre ' 4 ' le fichier généré devrait produire l'affichage suivant:

Points bonus : Rajouter des commentaires (lignes commençant par #), dans votre code, qui expliquent ( « grosso-modo » ) le fonctionnement de l'algorithme ci-dessus.

Rendu : ⚓

Tous vos noms de fichiers rendus devront être préfixés par " [M1_OTG]_NomPrenom_ ". Rendez votre travail via le répertoire seafile dédié: https://seafile.unistra.fr/u/d/9929f9f759/, mdp: m1_otg_TPRendu

Corrections : ⚓

exercice 1 - exercice 2