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

3. Écrire une boucle while qui compte jusqu'à 100. Idem avec une boucle for.
4. À 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.

Listes

(voir détails dans le cours Python)

5. Créer une liste vide. Créer une liste contenant des éléments.
6. Afficher la longueur de cette liste.
7. Remplacer l'une des valeurs, enlever une case et en ajouter une autre, puis afficher à nouveau la liste.
8. 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

9. Tester les fonctions de la librairie random suivantes : (voir détails dans le cours Python) random.randint, random.randrange, random.choice, random.shuffle.

Exercice 2 : 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 :

2. calcule la moyenne des nombres contenus dans un tableau donné,
3. compte le nombre d'occurrences d'un élément,
4. compte combien d'éléments sont supérieurs ou égaux à 10,
5. recherche la valeur maximale du tableau,
6. teste si un élément est présent ou non,
7. 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 :

7. fournit un tableau de n entiers aléatoires,
8. 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.

8. Sur des grands tableaux, mesurer le temps nécessaire à chacune des fonctions calculant la moyenne et recherchant un élément.

Exercice 3 : tableaux d'enregistrements, les étudiants

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.

6. (à la maison) Généraliser à un type d'étudiant qui possède un nombre quelconque de notes.

Exercice 4 : tableaux d'enregistrements, les restaurants

Préliminaires

0. Récupérer le dossier tp-restos.
   Une liste de restaurants vous est fournie et, pour chaque restaurant, vous pouvez accéder à son nom, son adresse (à travers num et rue), sa localisation exprimée cette fois en latitude et longitude (lat et lon), sa position dans le classement (pos), sa note et le nombre d'avis qui ont été émis sur ce restaurant (votes).
   Ci-dessous les premières lignes du fichier exercices.py qui montrent la récupération des restaurants, l'accès au classement et au nom d'un restaurant, et enfin une boucle sur la liste des restaurants.

   from restos import liste_restos
   
   # affichage des informations sur un restaurant, à compléter
   def affiche_resto (resto):
       print('[',resto.get('pos'),']',end=' ')
       print(resto.get('nom'))
       print()
   
   # boucle sur tous les restaurants, pour affichage
   for resto in liste_restos:
       affiche_resto(resto)
   

   Votre travail consiste à poursuivre l'écriture de ce fichier, sans en modifier la première ligne.
1. Compléter l'affichage d'un restaurant. Appliquer à tous les restaurants de la liste.

Notes et avis

2. Afficher le nombre de restaurants disponibles.
3. Calculer combien d'avis ont été donnés au total. Combien d'avis a reçus un restaurant en moyenne ?
4. Afficher la moyenne des notes, ainsi que l'écart-type.
5. Afficher le nombre de restaurants ayant une note de 4,5 ou plus.

Localisation/identification des restaurants

6. Calculer la moyenne des latitudes et des longitudes. À quel endroit correspondent ces coordonnées (utiliser par exemple ce site ou directement Google Maps pour visualiser sur une carte la localisation calculée) ?
   Idem avec uniquement les restaurants ayant reçu plus de 50 avis.
7. Indiquer si oui ou non il y a un restaurant dans la rue alphonse mercier. Idem avec la rue du port.
8. Afficher la description du restaurant classé à la première position. Idem avec le restaurant placé à la dernière position.
9. Afficher toutes les informations disponibles sur le restaurant la ducasse. Idem pour le restaurant qui se trouve au 14 rue des postes.
10. Produire la liste des restaurants se trouvant rue du molinel.
11. Identifier le restaurant ayant reçu le plus d'avis.

Coup d'œil en arrière

La liste_restos jusque là utilisée correspond à la dernière année disponible. Le code python ci-dessous vous permet d'accéder aux informations sur les restaurants pour les années précédentes.

# récupération des archives
from restos import archives

# constitution de la liste des restaurants 2018
liste_restos_2018 = archives["2018"]

12. Reprendre les mêmes questions pour l'année précédente. Si ce n'est déjà fait, c'est le bon moment pour utiliser procédures et fonctions.
13. Quels sont les restaurants qui sont apparus lors de la dernière année ?
    Des restaurants se trouvaient-ils à la même adresse ?
    Quels restaurants ont disparu ?
14. Identifier le restaurant qui a le plus progressé dans le classement.
    Identifier le restaurant qui a chuté le plus durement.
15. Montrer l'évolution d'un restaurant donné au fil des années.

Adresses et rues

16. Détecter les adresses partagées par plusieurs restaurants.
17. Identifier la ou les rue(s) ayant le plus de restaurants.
18. Trouver la meilleure rue pour les restaurants (la rue avec la meilleure moyenne de notes, ou les rues où chaque restaurant a une note strictement supérieure à 4, etc.).
19. Idem avec la rue à ne pas fréquenter pour ses restaurants.

Il est possible de reprendre les deux dernières questions en jugeant une rue, non plus sur la moyenne des notes de ses restaurants, mais sur leur classement moyen.

Plus encore...

20. Afficher les restaurants par ordre de classement.
21. Reprendre les questions impliquant des calculs de moyennes et calculer cette fois des médianes.
22. Produire une cartographie des restaurants lillois. Par exemple, une telle cartographie des restaurants est jugée satisfaisante.
    

Exercice 5 : 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.

Exercice 6 : 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 7 : 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 :

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.

Exercice 8 : 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.

Les étapes à réaliser sont les suivantes.

5. 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.
6. 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.
7. 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.
8. 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.

Exercice 9 : 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 10 : 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.

Exercice 11 : 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.