site de Fabien Torre, université de Lille


Travaux pratiques en Python

Séances de programmation en Python 3.

Exercice 1 : Les basiques de Python 3

Dans cette séance, on s'approprie l'environnement : l'éditeur de texte où l'on tape les programmes, l'enregistrement des programmes, l'appel à l'interprète Python dans le terminal.

Affichages

  1. Tester l'instruction d'affichage print de Python : afficher un nombre, une chaîne de caractères, une variable.
  2. Comment peut-on passer ou ne pas passer à la ligne ?

Boucles

  1. Écrire une boucle while qui compte jusqu'à 100.
    Idem avec une boucle for.
  2. À l'aide de boucles imbriquées, dessiner des figures géométriques : triangles et carrés, creux ou non.
    Idem à l'aide de procédures et de leurs paramètres.
    Idem avec des fonctions.

Listes

(voir détails dans le cours Python)

  1. Créer une liste vide.
    Créer une liste contenant des éléments.
  2. Afficher la longueur de cette liste.
  3. Remplacer l'une des valeurs, enlever une case et en ajouter une autre, puis affiche à nouveau la liste.
  4. Utiliser une boucle pour parcourir les éléments de la liste et les afficher un par un. Passer en revue les différentes syntaxes possibles.

Aléatoire en Python

  1. Tester les fonctions de la librairie random suivantes : (voir détails dans le cours Python) random.randint, random.randrange, random.choice, random.shuffle.
[ voir la correction (partielle) ][ récupérer ]

Exercice 2 : Implémentation du type abstrait « Entier »

  1. Implémenter le type abstrait « Entier » vu en cours en utilisant... les entiers de Python.
  2. Coder les opérations addition et multiplication sur ce nouveau type.
  3. Implémenter à nouveau le type abstrait « Entier » vu en cours cette fois en s'appuyant sur les listes de Python (une liste de n éléments quelconques représentera l'entier n).
  4. Est-il nécessaire de recoder les opérations addition et multiplication ?

Exercice 3 : Implémentation du type abstrait « Pile »

  1. Implémenter le type abstrait « Pile » vu en cours.
  2. Écrire une fonction qui permet d'inverser une pile.
  3. Écrire une fonction qui prend en entrée un texte composé de différentes parenthèses, accolades, crochets, ouvrants ou fermants, et qui vérifie que l'expression est bien parenthésée.
    On pourra par exemple suivre les étapes suivantes :
    • une fonction qui prend en entrée un caractère et renvoie vrai s'il s'agit d'un symbole ouvrant et faux sinon,
    • une fonction qui prend un symbole ouvrant et fournit en retour le caractère fermant correspondant,
    • enfin, la fonction de vérification.
  4. Écrire une fonction qui évalue une expression polonaise inversée, composée d'entiers entre 0 et 9 et des quatre opérations élémentaires.
    On pourra par exemple suivre les étapes suivantes :
    • une fonction qui prend en entrée un caractère et renvoie vrai s'il s'agit d'une opération élémentaire et faux sinon,
    • une fonction qui prend un symbole-opération et deux entiers et qui renvoie le résultat de l'opération,
    • enfin, la fonction d'évaluation.
[ voir la correction version 1 ][ récupérer ]
[ voir la correction version 2 ][ récupérer ]

Exercice 4 : implémentation d'un type produit

  1. Implémenter en Python (à l'aide de listes ou de dictionnaires) le type abstrait « Étudiant » vu en cours (on rappelle qu'un étudiant est composé d'un nom, d'un prénom, d'une année de naissance, d'une note en informatique et d'une note de mathématiques).
    Bien travailler en particulier la procédure dont le rôle est d'afficher un étudiant.
  2. Créer quelques étudiants et tester chacune des fonctions.
[ voir la correction version 1 ][ récupérer ]
[ voir la correction version 2 ][ récupérer ]

Exercice 5 : tableaux de nombres

  1. Définir en Python un tableau d'entiers.

Écrire (et valider sur le tableau déjà défini) les fonctions qui :

  1. calcule la moyenne des nombres contenus dans un tableau donné,
  2. compte le nombre d'occurrences d'un élément,
  3. compte combien d'éléments sont supérieurs ou égaux à 10,
  4. teste si un élément est présent ou non,
  5. etc.

Nous nous intéressons maintenant à des tableaux beaucoup plus grands. Tout d'abord nous voulons créer de tels tableaux remplis de manière aléatoire, à l'aide du module random.

Écrire les fonctions qui, pour une taille donnée n :

  1. fournit un tableau de n entiers aléatoires,
  2. construit le tableau des n premiers entiers mélangés aléatoirement.

Enfin, nous utilisons le module time (voir détails dans le cours Python) pour mesurer le temps nécessaire à l'exécution d'un bloc d'instructions.

  1. Sur des grands tableaux, mesurer le temps nécessaire à chacune des fonctions calculant la moyenne et recherchant un élément.
[ voir la correction ][ récupérer ]

Exercice 6 : tableaux d'enregistrements

  1. Créer une promotion comme un tableau d'étudiants,
  2. implémenter la fonction moyenne d'un étudiant dédiée cette représentation,
  3. pour chaque discipline, la fonction moyenne de la promotion,
  4. la fonction qui trouve l'étudiant ayant eu la note moyenne maximale,
  5. etc.
[ voir la correction ][ récupérer ]
  1. (à la maison) Généraliser à un type d'étudiant qui possède un nombre quelconque de notes.

Exercice 7 : Algorithmes avancés sur les tableaux

Sur les tableaux quelconques

  1. Implémenter une fonction index_minimum(t,d,f) qui renvoie le numéro de la case contenant la plus petite valeur du tableau t entre les cases d et f.
  2. Programmer un tri à bulles.

Sur les tableaux déjà triés

On suppose disposer d'un tableau de nombres rangés par ordre croissant.

  1. Implémenter une fonction de recherche d'un élément utilisant une boucle tant que et tirant parti du fait que les éléments sont ordonnés.
  2. Écrire une fonction de recherche dichotomique.
  3. Proposer une procédure insertion(e,t,n) qui ajoute un élément e à sa place dans un tableau t de taille n.

Autres méthodes de tri

  1. tri_extraction utilisant index_minimum(t,d,f) : on récupère le minimum du tableau et on le place dans la première case, on récupère le minimum du tableau privé de la première case et on le place dans la deuxième, etc.
  2. tri_insertion utilisant insertion(e,t,n) : prendre le ième élément et le mettre à sa place dans les i-1 premières cases déjà triées.
[ voir la correction ][ récupérer ]

Exercice 8 : Comparaison expérimentale des méthodes de tri

Préliminaires

On veut dans cette séance comparer les méthodes de tri (comme le tri à bulles par exemple) en terme de temps de calcul et en fonction de la taille et de la nature des tableaux à trier.

De nouveaux points techniques sont nécessaires, essentiellement : savoir produire des fichiers texte en Python (voir détails dans le cours Python) et connaître les bases de gnuplot.

gnuplot est un outil qui permet de tracer des courbes à partir de données brutes. Par exemple, l'instruction :

$ gnuplot
gnuplot> plot 'stats.dat' with lines

permet de tracer les points qui se trouvent dans le fichier stats.dat sous la forme suivante (un point par ligne, valeur en abscisse, une tabulation, valeur en ordonnée) :

100     2
200     14
300     26
400     48
500     72
600     111
700     142
800     194
900     238
1000    298

C'est ce type de fichier que l'on veut faire produire par Python (la première colonne pourrait correspondre aux tailles des tableaux considérés, la seconde aux temps de traitement nécessaires).

Fonctions à implémenter

  1. Écrire une fonction copie (t) qui renvoie un nouveau tableau contenant dans le même ordre les mêmes valeurs que le tableau t ; vérifier qu'une modification de la copie n'altère pas le tableau original.
  2. Proposer une fonction inverse (t) qui fournit un nouveau tableau contenant les mêmes valeurs que le tableau t mais dans l'ordre inverse.
  3. Implémenter des fonctions pour produire des tableaux :
    • une fonction tableau_premiers_entiers (n) qui produit un tableau contenant dans l'ordre tous les entiers de 1 à n,
    • une fonction tableau_premiers_entiers_melanges (n) qui propose ces mêmes entiers mélangés aléaoirement,
    • une fonction tableau_premiers_entiers_inverses (n) qui propose ces mêmes entiers du plus grand au plus petit.
  4. Proposer une procédure ligne_dans_fichier (f,n,t) dont le rôle est d'écrire dans le fichier f la valeur (numérique) de n, une tabulation, la valeur (numérique) de t et enfin un passage à la ligne.
  5. Écrire une fonction temps_tri_bulles (t) qui fait une copie du tableau t et renvoie le temps nécessaire au tri à bulles pour classer cette copie.
  6. Coder la procédure stats_melange (nmin,nmax,pas,fois) qui pour chaque taille de tableau comprise entre nmin et nmax en avançant de pas en pas produit fois tableaux mélangés aléatoirement et écrit dans un fichier le temps moyen nécessaire au tri à bulles pour classer ces tableaux.
  7. Même question avec la fonction stats_ordonne (nmin,nmax,pas,fois) pour des tableaux déjà ordonnés.
  8. Même question avec la fonction stats_inverse (nmin,nmax,pas,fois) pour des tableaux déjà ordonnés mais en ordre inverse.
  9. Produire à l'aide de votre code des fichiers de statistiques pour des tailles de tableau variant de 100 en 100, entre 100 et 1000, avec 5 répétitions pour chaque taille de tableau. Visualiser ces données avec gnuplot et comparer l'évolution du temps nécessaire au tri bulles selon le type de tableaux et selon leurs tailles.
  10. Généraliser votre code pour pouvoir également comparer les méthodes de tri entre elles : tri à bulles, tri insertion, tri extraction et tri rapide.
  11. Tester des modifications des méthodes de tri, calculer les écarts-types des temps de calcul sur les tableaux mélangés, explorer les possibilités de gnuplot, expliquer théoriquement les courbes obtenues.

Au final, on doit obtenir des images comme celles-ci :

Exercice 9 : Conjecture de Syracuse

Explications

Ce problème est apparu pour la première fois dans les années 30. Puis, à nouveau, à l'université de Syracuse (New York) dans les années 50. Aucune solution n'étant trouvée, le problème s'est propagé aux autres universités américaines. Dans le contexte de la guerre froide, on évoque (comme une plaisanterie ?) une manœuvre russe pour paralyser la recherche américaine.

L'énoncé de ce problème est le suivant. On part d'un entier n auquel on fait subir une transformation :

  • si n est pair, on le divise par deux ;
  • si n est impair, on le multiplie par 3, et ajoute 1.

Puis, on recommence sur le résultat. Par exemple, en partant de n=10, on obtient :

10 5 16 8 4 2 1 4 2 1 etc.

Conjecture : quel que soit l'entier n, on finit par retomber sur 1.

Implémentations Python

  1. Définir la carte d'identité d'un entier comme l'enregistrement de :
    • cet entier,
    • sa trajectoire (les entiers rencontrés jusqu'à 1),
    • sa durée de vol (le nombre d'entiers rencontrés avant de trouver 1),
    • son altitude maximale (le plus grand entier rencontré).
  2. Proposer une procédure qui affiche une telle carte.
  3. Écrire une fonction qui permet de tester la conjecture pour un entier donné et qui renvoie sa carte d'identité renseignée.
  4. Écrire ensuite une fonction qui teste tous les entiers dans un intervalle donné et renvoie toutes les cartes d'identité de ces entiers.
  5. Utiliser cette fonction pour afficher les cartes présentant une durée de vol strictement supérieure à 100.
  6. Implémenter un tri à bulles pour classer des cartes par altitude décroissante.
[ correction jusqu'à la question 3 ][ récupérer ]

Exercice 10 : Chiffrement et décryptage

Préliminaires

Dans cette séance, on s'intéresse au chiffrement de textes par substitution, à leur déchiffrement, et enfin au moyen de casser un tel cryptage. Un chiffrement par substitution consiste simplement à remplacer systématiquement une lettre par une autre.

Certains chiffrements par substitution sont dits par décalage ou appelés chiffre de César : dans ces cas, une lettre et sa remplaçante sont toujours séparées dans l'alphabet par le même nombre de lettres. Un chiffrement par décalage répandu sur le web se nomme ROT13 : une lettre et sa remplaçante sont à une distance de 13 dans l'alphabet (le a est remplacé par le n, le b par le o, etc.).

Par souci de simplicité, on ne considère que des textes en minuscules, sans accent et sans symbole de ponctuation. Seul l'espace est utilisé entre les mots mais n'est pas remplacé par le chiffrement.

Cette séance va nécessiter de traiter des chaînes de caractères qu'il peut être commode de voir comme des listes de caractères, ce que permet Python.

Concernant les caractères eux-mêmes, on rappelle qu'il est possible de repérer un caractère par un numéro (son code ASCII).

Nous aurons également besoin de stocker les correspondances entre lettres, ce qui peut être fait à l'aide de dictionnaires Python (que nous avions déjà utilisés pour coder des enregistrements).

Enfin, pour décrypter un texte sans connaître la règle de chiffrement, il est courant d'utiliser la fréquence d'apparition des lettres dans la langue choisie. On considérera qu'en français les lettres se rangent comme suit, de la plus fréquente à la moins fréquente :

e a i t s n l u r o d m c p v q h f b g j x y w z k

Fonctions à implémenter

On va d'abord réaliser et tester quelques fonctions pour gérer les dictionnaires, chiffrer et déchiffrer des textes.

  1. chiffrement_lettre (l,d) renvoie la correspondance de la lettre l dans le dictionnaire d si cette correspondance existe, renvoie la lettre l elle-même sinon.
  2. chiffrement_phrase (p,d) construit une nouvelle chaîne de caractères correspondant au chiffrement caractère par caractère de la phrase p à l'aide du dictionnaire d. Définir un dictionnaire et tester ces fonctions en codant une phrase quelconque.
  3. inverse_dico (d) renvoie un nouveau dictionnaire qui inverse les clefs et les valeurs du dictionnaire d. Tester en déchiffrant la phrase précédemment codée.
  4. dico_rot_13 () construit un dictionnaire correspondant au chiffrement en ROT13. Tester à nouveau pour chiffrer une phrase quelconque. Quelles solutions sont possibles pour le déchiffrement ?

On veut maintenant déchiffer un texte codé par une technique de substitution mais on ne dispose pas du dictionnaire utilisé. L'objectif est de décoder le texte mystère suivant.

or z f kcgrkcgh fnnggh mg ug rofo onaougugna fqgb cn u eorrofu rgswfny or gafoa y cng fnbognng xfuorrg iwpaghafnag ga mfyoh or fqfoa gag woblg ufoh cng hgwog yg ufrlgcwh r fqfoa wgycoa f rf uohgwg ipcw gqoagw r lcuorofaopn yg hgh yghfhawgh or kcoaaf rf npcqgrrg pwrgfnh rf qorrg yg hgh fogcj ga gafdroa hf ygugcwg yfnh r org yg hcrroqfn iwgh blfwrghapn yfnh rf bfwprong yc hcy bgaag org gha ygh irch honscrogwgh grrg n gha scgwg bpuiphgg kcg yg hfdrg yg ugw ga f gnqowpn awpoh uorrgh yg rpns gn rfwsgcw grrg n f mfufoh irch y cn kcfwa yg uorrg grrg gha hgifwgg yc bpnaongna ifw cng bwokcg f igong qohodrg kco xorawg f awfqgwh cng ufhhg yg wphgfcj ga yg qfhg wgnygt qpch lfdoacgr ygh ipcrgh y gfc rf qgsgafaopn bpuug pn igca rg hciiphgw gha ifcqwg pc ipcw fonho yowg nfong pn n z awpcqg ifh y fwdwgh y cng bgwafong yougnhopn qgwh r gjawguoag pbboygnafrg f r gnywpoa pc h grgqgna rg xpwa upcrawog ga kcgrkcgh uohgwfdrgh dfaohhgh yg dpoh lfdoaggh ignyfna r gag ifw rgh sgnh kco xcogna rgh ipchhogwgh ga rgh xogqwgh yg blfwrghapn pn wgnbpnawg or gha qwfo rg ifruogw nfon hgaosgwg ufoh apcag r org f r gjbgiaopn yg bg ipona pbboygnafr ga y cn ghifbg awohag ga drfnblfawg kco dpwyg rf ugw gha bpcqgwag y gifohhgh dwpchhforrgh yg uzwag pypwoxgwfna ho ghaoug ifw rgh lpwaobcragcwh fnsrfoh r fwdchag z upnag hpcqgna f cng lfcagcw yg kcontg pc qonsa iogyh or z xpwug cn aforroh iwghkcg ouigngawfdrg ga blfwsg r fauphilgwg yg hgh ifwxcuh fc irch iwpxpny yg bg aforroh npn rpon yg r gjawguoag pwognafrg yg r org b gha f yowg yg rf irch grposngg rgswfny h gafoa dfao rco ugug cng igaoag lcaag kc or pbbcifoa kcfny ipcw rf iwguogwg xpoh ga ifw lfhfwy mg xoh hf bpnnfohhfnbg bgaag bpnnfohhfnbg ucwoa dogn qoag gn fuoaog bfw or z fqfoa bgwagh yfnh rg blgw wgbrch yg kcpo gjboagw r onagwga ga r ghaoug mg qoh kc or fqfoa wgbc cng xpwag gycbfaopn lgcwgchgugna hgwqog ifw ygh xfbcragh hiowoacgrrgh igc bpuucngh ufoh kc or gafoa onxgbag yg uohfnalwpiog ga hcmga f yg ufrlgcwgchgh fragwnfaoqgh y gnalpchofhug ga yg ugrfnbprog dogn kc or gca blgt rco dgfcbpci yg roqwgh or h gn hgwqfoa wfwgugna hgh iwonboifcj fuchgugnah bpnhohafogna f blfhhgw ga f igblgw pc f xrfngw hcw rf irfsg ga f awfqgwh rgh uzwagh gn kcgag yg bpkcorrfsgh ga y gblfnaorrpnh gnapuprpsokcgh hf bprrgbaopn fcwfoa ic xfowg gnqog f cn hefuugwyfu yfnh bgh gjbcwhopnh or gafoa pwyonfowgugna fbbpuifsng ifw cn qogcj ngswg npuug mcioagw kco fqfoa gag fxxwfnblo fqfna rgh wgqgwh yg rf xfuorrg ufoh kc pn n fqfoa ic ygboygw no ifw ugnfbgh no ifw iwpughhgh f fdfnypnngw hpn mgcng ufhhf eorr or bpnhoygwfoa bpuug hpn ywpoa yg rg hcoqwg ifwapca or n gha ifh ouiwpdfdrg kcg rgh ifwgnah yg rgswfny mcsgfna kcg bgrco bo fqfoa rf agag cn igc ygwfnsgg hg hpogna fiirokcgh f bpnxowugw mcioagw yfnh hpn pdhaonfaopn yfnh rg dca yg ugaawg cng ghigbg yg sfwyogn ga yg hcwqgorrfna fciwgh yc xcsoaox hpch rf rfaoacyg yg r org yg hcrroqfn rgh loqgwh hpna wfwgugna wospcwgcj ga b gha cn gqgngugna kcfny fc ygbron yg r fnngg rg xgc ygqogna onyohignhfdrg bgignyfna qgwh rg uorogc y pbapdwg or z gca cng mpcwngg y cn xwpoy wgufwkcfdrg mchag fqfna rg bpcblgw yc hprgor mg ug xwfzfoh cn blguon f awfqgwh rgh aforroh qgwh rf lcaag yg upn fuo kcg mg n fqfoh ifh qc ygicoh kcgrkcgh hgufongh mg ygugcwfoh frpwh f blfwrghapn f cng yohafnbg yg ngcx uorrgh yg r org ga rgh xfboroagh ipcw frrgw ga wgqgnow gafogna dogn uponh swfnygh kc fcmpcwy lco gn fwwoqfna f rf lcaag mg xwfiifo hgrpn upn lfdoacyg ga ng wgbgqfna ifh yg wgipnhg mg blgwblfo rf brgx pc mg hfqfoh kc grrg gafoa bfblgg m pcqwoh rf ipwag ga m gnawfo cn dgfc xgc xrfudfoa yfnh rg xpzgw b gafoa cng hcwiwohg ga f bpci hcw cng ygh irch fswgfdrgh mg ug ygdfwwfhhfo yg upn ifrgapa mg awfonfo cn xfcagcor fciwgh ygh dcblgh igaorrfnagh ga m faagnyoh ifaoguugna r fwwoqgg yg ugh lpagh igc fiwgh rf apudgg yg rf ncoa orh fwwoqgwgna ga ug xowgna cn fbbcgor apca f xfoa bpwyofr mcioagw apca gn wofna y cng pwgorrg f r fcawg hg ypnnfoa yc upcqgugna ga iwgifwfoa kcgrkcgh ipcrgh y gfc ipcw rg hpcigw rgswfny gafoa yfnh cng yg hgh bwohgh y gnalpchofhug bfw yg kcgr fcawg npu fiigrgw bgrf or fqfoa awpcqg cn doqfrqg onbpnnc xpwufna cn sgnwg npcqgfc ga uogcj gnbpwg or fqfoa blfhhg ga faawfig fqgb r fhhohafnbg yg mcioagw cn hbfwfdgg kc or bwpzfoa apca f xfoa npcqgfc ga hcw rgkcgr or yghowfoa fqpow upn pionopn rg rgnygufon ufaon

Les étapes à réaliser sont les suivantes.

  1. compte_lettres (p) construit un dictionnaire faisant correspondre chaque lettre apparaissant dans la phrase p à son nombre d'occurrences dans cette même phrase. Tester sur le texte mystère.
  2. tri_bulles_dico (d) est un tri à bulles modifié pour renvoyer les clefs d'un dictionnaire d, ordonnées par valeurs décroissantes. Tester sur le dictionnaire précédemment calculé par compte_lettres.
  3. arrays2dict (ks,vs) renvoie un dictionnaire dont les clefs correspondent au tableau ks et qui associe pour chacune de ces clefs la valeur se trouvant à la même position dans le tableau vs. Utiliser cette fonction pour combiner le tableau fourni par tri_bulles_dico et le tableau des lettres de l'alphabet classées par fréquences décroissantes dans la langue française.
  4. decrypte (pc,ll) doit décrypter la phrase pc à l'aide des lettres de l'alphabet rangées par ordre de fréquence décroissante dans la langue utilisée et disponible dans le tableau ll. Décoder le texte mystère à l'aide de cette fonction.
Fabien Torre Valid HTML5! Valid CSS!
Accueil > Enseignement > En pratique > Programmation > Python
(contenu mis à jour )
site de Fabien Torre, université de Lille

Description

Survoler un lien de navigation pour lire sa description ici...