Examen de BPI - session normale - 20 décembre 2023
Durée : 2 heures.
Aucun document autorisé à l'exception d'une feuille manuscrite format A4 recto verso.
Consignes générales
L'épreuve doit être réalisée exclusivement sur la machine et dans l'environnement mis à disposition.
Toute tentative de communication ou de fraude, oral ou via des dispositifs portables (clé USB, disques durs externes, etc.), entraînera un renvoi devant la Section Disciplinaire de Grenoble-INP.
À la fin de l'épreuve, vous devez rendre votre code comme cela vous a été expliqué en début d'examen : si vous arrêtez ou redémarrez la machine brutalement, votre code risque d'être perdu !
Il est très fortement recommandé de sauvegarder régulièrement pour ne pas risquer de perdre votre travail en cas de panne de la machine.
En cliquant sur les liens en bleu, vous pouvez accéder à la documentation Python ainsi qu'au site du cours BPI.
La clarté du code produit sera un critère déterminant dans la notation.
On s'attend à ce que l'exécution de pylint sur votre code n'affiche aucun avertissement et attribue un score de 10/10.
Le barème est donné à titre indicatif. L'examen peut être découpé en 4 parties de difficulté croissante :
- la version du tri sur des tableaux ;
- la version du tri sur des listes chaînées ;
- la première partie de l'exercice sur les poèmes ;
- la deuxième partie de l'exercice sur les poèmes.
On vous recommande donc de traiter les parties séquentiellement. Les deux versions du tri correspondent à la partie « exercices » des TP alors que la partie sur les poèmes est du niveau d'un « mini-projet ».
Le sujet paraît long, car on détaille précisément ce qui est attendu en donnant des exemples, mais les fonctions demandées ne sont en pratique pas très longues à écrire.
On n'écrira pas de méthodes dans cette épreuve, uniquement des fonctions.
Vous ne devez pas implanter de fonction récursive dans cette épreuve.
Exercice : le tri du cocktail shaker (10 pts)
Consignes générales pour l'exercice
On va implanter dans cet exercice l'algorithme préféré de James Bond : le tri du cocktail shaker.
Si on suppose qu'on veut trier un tableau d'entiers par ordre croissant, le principe de cet algorithme peut-être résumé simplement comme suit.
- On parcourt le tableau de la première à la dernière case, en échangeant deux à deux les cases qui ne sont pas dans le bon ordre (croissant) : dit autrement, si
tab[i] > tab[i+1]alors on échangetab[i]ettab[i+1]; - une fois arrivé à la fin du tableau, si aucun échange n'a eu lieu pendant le parcours précédent, alors le tableau est trié donc la fonction est terminée ;
- sinon, on re-parcourt le tableau cette fois-ci en sens inverse, en partant de la fin pour remonter vers le début, en échangeant là-aussi les cases consécutives qui ne sont pas dans l'ordre croissant ;
- une fois revenu au début du tableau, si aucun échange n'a eu lieu pendant le parcours précédent, alors le tableau est trié donc la fonction est terminée ;
- sinon, on repart à l'étape 1 pour re-parcourir le tableau du début à la fin, et ainsi de suite.
On fournit trois fichiers pour cet exercice :
cocktail_tab.pycontient la version tableau du tri ;cocktail_liste.pycontient la version liste chaînée du tri ;cocktail.pycontient le programme principal et des tests, vous n'avez pas besoin de le modifier.
Si vous appelez le programme simplement sans paramètre (./cocktail.py), il lancera une série de tests sur des tableaux et listes de petites tailles pour vous aider à repérer visuellement vos erreurs.
Si vous appelez le programme avec la commande ./cocktail.py --test, il lancera des tests bruts sur beaucoup de tableaux et de listes de plus grandes tailles, pour vous convaincre que vos fonctions sont correctes.
On va implanter cet algorithme d'abord avec des tableaux statiques puis avec des listes doublement chaînées.
Consigne importante : dans tout l'exercice, vous ne devez utiliser aucune primitive fournie dans la bibliothèque Python, à l'exception de len et range qui sont autorisées.
Implantation avec des tableaux statiques
Toutes les fonctions demandées dans cette partie doivent être complétées dans le fichier cocktail_tab.py.
On travaillera exclusivement sur des tableaux statiques : pas des tableaux dynamiques (list Python).
Question 1 (3 pts)
Complétez la fonction parcourir_echanger_tab(tab, inv) qui prend en paramètre le tableau d'entiers tab qu'on veut parcourir, ainsi qu'un booléen inv qui vaut True ssi on veut parcourir le tableau en « sens inverse » (c'est-à-dire en partant de la fin et en remontant vers le début).
Cette fonction doit parcourir le tableau case par case dans le sens dépendant de inv et échanger deux à deux les éléments consécutifs qui ne sont pas par ordre croissant.
Elle renvoie un booléen valant True ssi il y a eu au moins un échange pendant le parcours.
Question 2 (2 pts)
Compléter la fonction trier_tab(tab) qui prend en paramètre le tableau d'entiers à trier.
Cette fonction doit appeler parcourir_echanger_tab(tab, inv) tant qu'il y a eu au moins un échange lors du parcours.
On doit alterner le sens du parcours à chaque appel en passant la valeur appropriée pour inv.
La fonction doit s'arrêter dès qu'un parcours n'a donné lieu à aucun échange.
Implantation avec des listes chaînées
On va maintenant implanter exactement le même tri sur des listes doublement chaînées d'entiers à la place des tableaux d'entiers.
Toutes les fonctions demandées dans cette partie doivent être complétées dans le fichier cocktail_liste.py.
On donne dans ce fichier la classe Cellule représentant les cellules de nos listes doublement chaînées.
Une cellule sera composée d'une valeur, d'une référence vers la cellule précédente et d'une référence vers la cellule suivante ;
On fournit un « afficheur » __str__ qui permettra d'afficher le contenu d'une cellule cell en écrivant simplement print(cell).
On donne aussi la classe Liste représentant les listes doublement chaînées : chaque liste sera équipée d'un élément fictif (sentinelle) en tête (contenant le caractère T en tant que valeur) et d'un élément fictif en queue (contenant le caractère Q en tant que valeur). Ces « valeurs » T et Q ne servent en fait qu'à rendre l'affichage plus lisible : vous ne devez jamais accéder ni à liste.tete.val ni à liste.queue.val dans les fonctions qu'on vous demande d'écrire, mais toujours comparer les références de vos cellules avec liste.tete et liste.queue pour savoir si vous êtes au bout de la liste.
On peut donc représenter une liste doublement chaînée par le schéma suivant :
(où Ø symbolise la « valeur » None).
Le constructeur de la classe liste renvoie une liste « vide », c'est-à-dire sans cellule significative, mais contenant bien les deux sentinelles.
On fournit également une fonction remplir_liste(liste, tab) qui prend en paramètre une liste vide et un tableau contenant des entiers et qui remplit la liste avec les mêmes valeurs dans le même ordre : par exemple, le schéma ci-dessus représente une liste après avoir appelé remplir_liste(liste, [3, 1, 4, 2, 7]) ;
On donne aussi une fonction afficher_liste(liste) qui affiche le contenu de la liste (y compris les éléments fictifs en tête et en queue) sous le format T <-> 3 <-> 1 <-> 4 <-> 2 <-> 7 <-> Q.
On fournit enfin une fonction echanger_cellules(cell) dont le but est d'échanger la cellule cell avec sa suivante cell.suiv.
On considère comme prérequis que cell et cell.suiv sont des cellules significatives (c'est-à-dire pas les éléments fictifs en tête et en queue).
La fonction renvoie une référence vers la « nouvelle » cellule cell (pour être plus clair : vers la cellule qui était cell.suiv au début de la fonction).
Par exemple, si on appelle echanger_cellules(cell) avec cell pointant sur la cellule contenant la valeur 4 dans la liste exemple ci-dessous :
(où Ø symbolise la « valeur » None).
Alors, après l'exécution de la fonction, on a échangé les cellules contenant 4 et 2, et on renvoie une référence vers la cellule contenant 2, comme illustré dans la figure ci-dessous :
(où Ø symbolise la « valeur » None).
Question 3 (1 pt)
Compléter la fonction liste_vide_ou_singleton(liste) qui renvoie True ssi la liste ne contient aucun ou qu'un seul élément significatif (c'est-à-dire sans compter les éléments fictifs en tête et queue).
Question 4 (3 pts)
Compléter la fonction parcourir_echanger_liste(liste, inv) qui prend en paramètre un booléen inv qui vaut True ssi on veut parcourir la liste en « sens inverse » (c'est-à-dire en partant de la queue et en remontant vers la tête).
Cette fonction doit parcourir la liste cellule par cellule dans le sens dépendant de inv et échanger deux à deux les cellules consécutives qui ne sont pas par ordre croissant. On utilisera évidemment la fonction echanger_cellules de la question précédente pour échanger des cellules par modification des chaînages, sans changer les valeurs.
Elle renvoie un booléen modif valant True ssi il y a eu au moins un échange pendant le parcours.
Question 5 (1 pt)
Compléter la fonction trier_liste(liste) qui doit trier la liste en appelant la fonction parcourir_echanger_liste de la question précédente tant qu'il y a eu au moins un échange lors du parcours.
On doit alterner le sens du parcours à chaque appel en passant la valeur appropriée pour inv.
La fonction doit s'arrêter dès qu'un parcours n'a donné lieu à aucun échange.
Mini-projet : génération de poèmes (10 pts)
Consignes générales pour le mini-projet
Dans cet exercice, et pour finir le semestre sur une note culturelle, nous allons écrire un programme qui génère aléatoirement des poèmes à partir d'une base de mots fournie.
Toutes les fonctions demandées doivent être implantées dans le fichier poemes.py qui fournit un squelette du code attendu ainsi que des fonctions de test.
Si vous appelez le programme simplement sans paramètre (./poemes.py), il lancera les tests sur le fichier poemes1.txt, qui est assez court pour permettre de vérifier facilement que votre code fonctionne.
Si vous ajoutez un nom de fichier en paramètre sur la ligne de commande (par exemple : ./poemes.py poemes2.txt), c'est ce fichier qui sera utilisé par les tests du programme principal.
Dans cet exercice, vous êtes libres d'utiliser toutes les primitives fournies par la bibliothèque Python.
Première partie
Les fonctions demandées dans cette première partie ne sont pas très difficiles à écrire, mais nécessitent de bien comprendre les structures de données non triviales utilisées et de savoir utiliser la bibliothèque standard Python pour travailler avec des chaînes de caractères, de l'aléatoire ainsi que des fichiers.
Question 1 (2 pts)
Compléter la fonction lire_paquets_mots(nom_fichier) qui doit lire un fichier texte contenant des mots et renvoyer un dictionnaire (dict Python) contenant ces mots selon le format décrit ci-après.
On vous fournit deux fichiers exemples poemes1.txt et poemes2.txt pour illustrer le format attendu en entrée (on supposera que les fichiers fournis sont corrects : on ne vous demande pas de gérer d'éventuelles erreurs dans les fichiers d'entrées).
Par exemple, le fichier poemes1.txt contient :
1 2 3 4 5 6 7 8 | |
On appelle paquet de mots une succession de mots terminée par une ligne vide. Dans l'exemple ci-dessus, il y a donc trois paquets de mots :
- « il fait beau son sang est chaud elle descend dans le metro » est un paquet de mots ;
- « sur le plateau pour les verseaux » est un paquet de mots ;
- « du Sornin » est un paquet de mots.
Dans un paquet, on peut avoir plusieurs lignes de mots, séparées par un retour à la ligne. Par exemple, dans le premier paquet ci-dessus, on a trois lignes :
- « il fait beau » ;
- « son sang est chaud » ;
- « elle descend dans le metro ».
La fonction lire_paquets_mots doit donc lire le fichier et renvoyer un dictionnaire :
- dont chaque clé sera un entier représentant le numéro du paquet (0, 1, 2, ...) ;
- dont chaque valeur sera un paquet de mots, représenté par un tableau dynamique (list Python) dont chaque case contiendra une ligne du paquet.
Par exemple, si on exécute print(lire_paquets_mots("poemes1.txt")), on devra obtenir l'affichage suivant :
1 2 | |
Note : le retour à la ligne après la dernière virgule de la première ligne a été ajouté pour rendre cet énoncé plus lisible, il n'est pas nécessaire de le gérer dans votre programme.
On attire votre attention sur la méthode strip (voir sa documentation) applicable sur une chaîne de caractères et qui retire les espaces au début et à la fin de la chaîne.
Question 2 (2 pts)
Compléter la fonction generer_poemes_3_vers(paquet0, paquet1, paquet2) qui prend trois paquets de mots en paramètres et renvoie un tableau dynamique contenant tous les poèmes de trois vers créés à partir des 3 paquets passés en paramètres.
Chaque élément du tableau dynamique renvoyé est un tuple composé de trois vers : le premier vers appartenant au premier paquet paquet0, le deuxième vers appartenant au deuxième paquet paquet1 et le troisième vers appartenant au troisième paquet paquet2.
Un vers correspondra ici à une ligne de mots dans le fichier passé initialement à la fonction lire_paquets_mots de la question précédente.
Par exemple, si on exécute :
1 2 3 | |
alors on devra obtenir l'affichage suivant :
1 2 3 4 5 6 | |
Question 3 (1 pt)
Compléter la fonction poeme_aleatoire(poemes) qui prend en paramètre un tableau dynamique contenant des poèmes et en renvoie un tiré aléatoirement.
Par exemple, si on exécute :
1 2 | |
alors on pourra obtenir l'affichage ('elle descend dans le metro', 'pour les verseaux', 'du Sornin').
Notez bien que votre fonction doit fonctionner quelque-soit le nombre de vers composant le poème.
Deuxième partie
Cette partie est difficile : on vous recommande de ne vous y lancer qu'après avoir traité correctement toutes les questions précédentes, s'il vous reste du temps.
Question 4 (3 pts)
Compléter la fonction génératrice generer_indices(indices_max) qui produit des tuples contenant toutes les combinaisons de valeurs inférieures ou égales aux maximums contenus dans le tableau dynamique passé en paramètre indices_max.
On rappelle qu'une fonction génératrice produit séquentiellement des valeurs grâce au mot-clé yield.
Par exemple, si indices_max est [2, 1, 0] alors la fonction devra produire la séquence de tuples suivante :
1 2 3 4 5 6 | |
Indice : si vous ne voyez pas comment aborder cette question, on recommande de diviser le travail en deux parties :
- une fonction « classique »
plus_un(tab, indices_max)qui prend en paramètre un tableau dynamiquetabcontenant l'état actuel de l'énumération et la fait progresser d'un pas : par exemple, sitabcontient[1, 0, 0]au début de la fonction alors il devra contenir[1, 1, 0]à la fin, puis[2, 0, 0]à la fin de l'appel suivant et ainsi de suite ; - une fonction génératrice qui utilise
plus_unpour générer les tuples dans l'ordre attendu jusqu'à la fin de l'énumération.
Question 5 (2 pts)
Compléter la fonction tous_les_poemes qui prend en paramètre un dictionnaire contenant des paquets de mots (comme renvoyé par la fonction lire_paquets_mots de la première question) et renvoie un tableau dynamique contenant tous les poèmes possibles, chaque poème étant construit en prenant un vers de chaque paquet de mots et stocké dans un tableau dynamique (on renvoie donc un tableau dynamique de tableaux dynamiques de vers). Cette fonction utilisera la fonction generer_indices de la question précédente.
Par exemple, l'exécution de :
1 2 | |
devra produire l'affichage suivant :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | |