Chapitre 1. Structurer les données

Évaluation des prérequis

Correction du QCM (Google Colab)

Activités d’introduction

Activité 1. Véhicule à essence et véhicule éléctrique

Objectifs. Spécifier un type abstrait, distinguer interface et implémentation d’un type abstrait

Enoncé

On considère :

• un véhicule à essence à transmission automatique. Cela signifie que le passage des vitesses est automatique.
• un véhicule électrique dépourvu de boite de vitesse

Lister cinq opérations minimales que le conducteur doit pouvoir réaliser pour conduire un véhicule indépendamment du type de motorisation.

Correction

• Démarrer
• Avancer
• Reculer
• Tourner à gauche ou à droite
• Freiner

Remarques.

• L'ensemble de ces opérations définit l'interface minimale du type abstrait "véhicule".
• "Véhicule" est un type abstrait car les opérations qui le caractérisent sont indépendantes du choix d'implémentation c'est-à-dire ici de la motorisation du véhicule.
• Spécifier un type abstrait signifie décrire les opérations de son interface. Dans cette activité nous avons spécifié le type abstrait "véhicule".

Activité 2. Point dans un repère orthonormé du plan

Objectif. Implémenter un type abstrait de donnée à partir de sa spécification

• Programmes à compléter Google Colab
• Correction Google Colab

Cours

Interface et implémentation

Interface

Un type abstrait de donnée est caractérisé par une interface de programmation, c'est-à-dire un ensemble d'opérations qui permettent de manipuler les données de ce type.

On distingue :

• les constructeurs, qui permettent de créer une nouvelle structure de données ;
• les mutateurs, qui permettent de modifier la structure de données, par exemple en ajoutant ou en retirant des données ;
• les accesseurs, qui donnent de l'information sur la structure de donnée comme par exemple son nombre d'éléments ;
• les itérateurs qui permettent d'énumérer les éléments de la structure de données.

Spécifier un type abstrait, c'est définir son interface sans préjuger de la façon dont ces opérations seront implémentées.

Implémentation

Implémenter un type abstrait, c'est fournir le code des opérations de son interface en utilisant des types existants du langage de programmation choisi.

Plusieurs implémentations peuvent répondre à la même spécification. Par exemple, dans l'activité 2., nous avons implémenté en Python le type abstrait point du plan en utilisant comme type existant d'abord un tableau (list) puis un dictionnaire (dict). Le programmeur peut alors choisir l'implémentation qui lui convient le mieux en fonction de ses priorités : rapidité d'exécution, économie de mémoire, gestion de données de grande taille.

Les listes chaînées

• Diaporama

Interface minimale

Une liste est une séquence ordonnée d'éléments. Son interface minimale est la suivante :

• creer_liste() : constructeur qui retourne une liste vide
• liste_vide(l) : accesseur qui retourne Vrai si la liste l est vide ;
• insérer(l, e) : mutateur qui insère e en tête de liste et retourne la nouvelle liste ;
• tête(l) : accesseur qui retourne l'élément en tête de liste (si celle-ci n'est pas vide) ;
• queue(l) : accesseur qui retourne la liste privée de son élément de tête (si la liste n'est pas vide) ;
• eléments_liste(l) : itérateur qui retourne un tableau contenant les éléments de la liste l, que l'on peut ensuite énumérer avec une boucle for.

Interface étendue

On peut enricihir l'interface d'une liste de plusieurs opérations :

• taille(l) : accesseur qui retourne le nombre d'élémnent de la liste ;
• ième(l, i) : accesseur qui retourne le i-ème élément de la liste ;
• ajouter_fin(l, e) : mutateur qui ajoute e à la fin de la liste ;
• insérer_ième(l, i, e) : mutateur qui insère l'élément e en i-ème position ;
• remplacer(l, i, e) : mutateur qui remplace le i-ème élément par e ;
• supprimer_ième(l, i) : mutateur qui supprimer le i-ème élément de la liste

Implémentations

Nous allons coder deux implémentations différentes d'une liste en Python :

• avec des tuples imbriqués ;
• puis avec des tableaux de taille fixée.

Cahier Jupyter dans Capytale (lien direct, code de partage : 56c2-3903530)

Les piles (LIFO)

• Applet
• Diaporama

Interface minimale

Une pile est un ensemble ordonné d'éléments qui se comporte comme une pile d'assiette : on peut ajouter une assiette sur la pile ou prendre l'assiette sur le dessus de la pile.

Son interface minimale est :

creer_pile() : constructeur qui retourne une pile vide ;

pile_vide : acccesseur qui retourne Vrai si la pile p esr vide ;

empiler(p, e) : mutateur qui ajoute e au sommet de la pile p ;

dépiler(p, e) : mutateur qui retire l'élément an sommet de pile (si elle n'est pas vide) et retourne la nouvelle pile ;

sommet(p) : accesseur qui retourne le sommet de la pile (si elle n'est pas vide) ;

elements_pile(p) : itérateur qui énumère les éléments de la pile.

Remarques.

La différence entre une liste et une pile est que l'on ne définit pas d'mutateurs supplémentaires tels que insérer_ième ou remplacer

Dans une pile, le dernier élément ajouté sera le premier élément retiré. On parle de structure de donnée de type LIFO, acronyme de "Last In, First Out" signifiant "dernier arrivé, premier sorti".

Implémentations

Nous allons coder deux implémentations différentes des piles en Python : par un tableau puis par une liste.

1. Ouvrez ce Cahier Jupyter dans Capytale (lien direct, code de partage : 7b0b-3903697).
2. Complétez l'implémentation d'une pile par un tableau (Question 1 du cahier Jupyter.)
3. Sur papier ou dans une feuille de tableur, comparer les interfaces minimales d'une liste et d'une pile.
   Correction

   Catégorie	Liste	Pile	Catégorie
   Constructeur	créer_liste	créer_pile	Constructeur
   mutateur	insérer	empiler	mutateur
   Accesseur	queue	dépiler
   	tête	sommet	Accesseur
   	liste_vide	pile_vide
   Itérateur	éléments_liste	éléments_pile	Itérateur

   Les interfaces minimales d'une liste et d'une pile sont très similaires. La seule différence importante porte sur les mutateurs queue et dépiler :

   • queue est un accesseur ce qui signifie qu'il ne modifie pas la liste sur laquelle il s'applique. Il renvoie un nouvel objet de type Liste.
   • Au contraire, dépiler est un mutateur ce qui signifie qu'il modifie la liste sur laquelle il s'applique.

4. En déduire l'implémentation d'une pile par une liste. On complétera pour cette question le Cahier Jupyter précédent (Question 3) après avoir exécuté le cadre de la Question 2 pour charger en mémoire l'implémentation d'une liste par des tuples.

Les files (FIFO)

• Applet
• Diaporama

Interface minimale

Une file est un ensemble ordonné d'élément qui se comporte comme une file d'attente : un nouvel arrivant se met à la fin de la file, tandis que la prochaine personne serivie est celle en tête de file.

Son interface minimale est :

• créer_file() : constructeur qui retourne une file vide ;
• file_vide(f) : accesseur qui retourne vrai si la file f est vide ;
• enfiler(f, e) : mutateur qui ajoute e à la fin de la file f ;
• défiler(f) : mutateur qui retire l'élément en début de file (si elle n'est pas vide) ;
• tête_file(f) : accesseur qui retourne le premier élément de la file (si elle n'est pas vide) ;
• éléments_file(f) : itérateur qui énumère les éléments de la file.

Remarque. Dans une file, contrairement à dans une pile, le premier élément ajouté sera le premier élément retiré. On parle de structure de donnée de type FIFO, acronyme de "First In, First Out" signifiant "premier entré, premier sorti". C'est cohérent avec la méthaphore de la file d'attente : le premier client arrivé doit être le premier client servi.

Implémentations

Nous allons coder trois implémentations des files en Python : par un tableau, par un tableau circulaire puis par deux piles.

1. À l'aide du diaporama, comparer les implémentations par tableau simple et par tableau circulaire. Quel est l'avantage de l'implémentation par tableau circulaire ? Quel est son défaut ?
   Réponse

   • Avantage du tableau circulaire. Dans l'implémentation par tableau simple, chaque défilage demande le décallage d'un rang de chaque élément du tableau (complexité temporelle en \(O(n)\))). Au contraire, dans l'implémentation par tableau circulaire, aucun décallage n'a lieu tant pour le défilage que l'enfilage (compléxité temporelle en \(O(1)\))).
   • Inconvénient du tableau circulaire. Dans l'implémentation par tableau circulaire, les rangs de fin et de début de file sont plus difficiles à déterminer que dans l'implémentation par tableau. On doit utiliser l'opérateur Python % pour obtenir des restes par la division euclidienne par la longueur du tableau.
2. Ouvrez ce Cahier Jupyter dans Capytale (lien direct, code de partage 91a6-3903715).
3. Charger en mémoire les implémentations d'une liste et d'une pile.
4. Complétez l'implémentation d'une file par un tableau puis par un tableau circulaire.
5. Complétez l'implémentation d'une file par deux piles. On utilisera pour cela uniquement l'interface d'une pile.

Exercices

Ces exercices sont à faire sur le cahier pour s’entrainer à l’épreuve écrite. Des ressources Python sont tout de même fournies pour tester les codes Python écrits.

Exercices d’application directe

Exercice 1. Utilisation de l’interface d'une pile

On rappelle qu’une pile est une structure de données abstraite fondée sur le principe « dernier arrivé, premier sorti » :

On munit la structure de données Pile des quatre fonctions primitives suivantes. On suppose que ces quatre fonctions ont été programmées préalablement en Python sans préciser le détail de l'implémentation.

• empiler(p, e) : ajoute l'élément e sur la pile p, ne renvoie rien ;
• depiler(p) : enlève le sommet de la pile p et renvoie la valeur de ce sommet ;
• pile_vide(p) : renvoie True si la pile p est vide et False sinon ;
• creer_pile() : renvoie une pile vide.

Dans cet exercice, seule l'utilisation de ces quatre fonctions sur la structure de données pile est autorisée (sauf mention contraire). De plus, toutes les piles étudiées ne contiennent que des nombres entiers positifs.

1. Remarquez que l'interface d'une pile donnée précédemment diffère de celle vue dans le cours. Nous l'abordons ici car elle est récurrente dans les sujets de Bac. Pour chaque opération de cette interface, indiquer à quelle catégorie d'opération elle appartient c'est-à-dire : est-ce un constructeur, un mutateur, un accesseur ou un itérateur ? Remarque. Attention, il y a un piège, l'une des opérations de l'interface précédente est hybride, c'est-à-dire appartient en même temps à deux catégories d'opération.
2. On exécute le programme Python suivant :

   p = creer_pile()
   empiler(p, 2)
   empiler(p, 4)
   empiler(p, 8)
   depiler(p)
   empiler(p, 1)
   

   Représenter l'état de la pile p à l'issue de l'exécution de ce programme.
   Réponse attendue

   
3. Proposer un programme qui crée une pile q dont l'état est donné ci-dessous :
   Réponse attendue

   q = creer_pile()
   empiler(q, 3)
   empiler(q, 5)
   empiler(q, 8)
   empiler(q, 2)
   

4. On suppose dans cette question que le contenu d'une pile p est le suivant (les éléments étant empilés par le haut) :

   

   Quelle sera le contenu de la pile q après exécution de la suite d’instructions suivante ?

   q = creer_pile_vide()
   while not est_vide(p):
       empiler(q, depiler(p))
   

   Réponse

   Réponse attendue

   

   Explications

   La suite d'instructions précédente transfère le contenu de la pile p vers la pile q.

   
5. On souhaite écrire une fonction somme qui prend en entrée une pile de nombres et renvoie la somme des nombres de cette pile. Recopier et compléter le programme Python suivant implémentant la fonction somme en remplaçant les ... par les bonnes instructions. Remarque. Attentoion, la pile passée en paramètre doit conserver son état d'origine.

   def somme(p):
       q = creer_pile_vide()
       s = 0
       while not est_vide(p):
           x = depiler(p)
           empiler(q, x)
           ???
       while not est_vide(q):
           ???
           empiler(p, x)
       return ???
   

   Réponse attendue

   def somme(p):
       q = creer_pile_vide()
       s = 0
       while not est_vide(p):
           x = depiler(p)
           empiler(q, x)
           s += x
       while not est_vide(q):
           x = depiler(q)
           empiler(p, x)
       return s
   

6. Écrire une fonction est_present qui prend comme paramètres une pile de nombres et un nombre v. Cette fonction doit renvoyer True si le nombre v est présent dans le pile p et False dans le cas contraire. On s'inspirera de la fonction somme de la question précédente. Remarque. Attention, la pile passée en paramètre doit conserver son état d'origine.
   Réponse attendue

   def est_present(p, v):
       q = creer_pile_vide()
       trouvee = False
       while not est_vide(p):
           x = depiler(p)
           empiler(q, x)
           if x == v:
               trouvee = True
       while not est_vide(q):
           x = depiler(q)
           empiler(p, x)
       return trouvee
   

7. Écrire une fonction comptage qui prend comme paramètres une pile de nombres et un nombre v. Cette fonction doit renvoyer le nombre d'occurences du nombre v dans le pile p . On s'inspirera de la fonction est_present de la question précédente. Remarque. Attention, la pile passée en paramètre doit conserver son état d'origine.
   Réponse attendue

   def comptage(p, v):
       q = creer_pile_vide()
       n = 0
       while not est_vide(p):
           x = depiler(p)
           empiler(q, x)
           if x == v:
               n += 1
       while not est_vide(q):
           x = depiler(q)
           empiler(p, x)
       return n
   

Exercices type BAC

Exercice 1. Pile de crêpes (Sujet 0)

Projet Replit d'accompagnement (À compléter, Correction)

Cet exercice porte sur la notion de pile et sur la programmation de base en Python.

On rappelle qu’une pile est une structure de donnée abstraite fondée sur le principe « dernier arrivé, premier servi » :

On munit la structure de donnée Pile de quatre fonctions primitives définies dans le tableau ci-dessous :

Structure de donnée abstraite : Pile

Utilise : Element, bool

Opérations : creer_pile_vide : \(\varnothing \longrightarrow\)Pile creer_pile_vide() renvoie une pile vide est_vide : Pile \(\longrightarrow\) bool est_vide(pile) renvoie True si pile est vide, False sinon empiler : Pile, Element \(\longrightarrow\) Pile empiler(pile, element) ajoute element au sommet de pile depiler : Pile \(\longrightarrow\) Element depiler(pile) renvoie l’élément au sommet de pile en le retirant de pile

Question 1.

On suppose dans cette question que le contenu de la pile p est le suivant (les éléments étant empilés par le haut) :

Quelle sera le contenu de la pile q après exécution de la suite d’instructions suivante ?

q = creer_pile_vide()
while not est_vide(p):
    empiler(q, depiler(p))

Réponse

Réponse attendue

Explications

La suite d'instructions précédente transfère le contenu de la pile p vers la pile q.

Question 2.

On appelle hauteur d’une pile le nombre d'éléments qu'elle contient. La fonction hauteur_pile prend en paramètre une pile p et renvoie sa hauteur. Après appel de cette fonction, la pile p doit avoir retrouvé son état d'origine.

Exemple. Si p est la pile de la question 1, hauteur(p) renvoie 4.

Recopier et compléter sur la copie le programme Python suivant implémentant la fonction hauteur_pile en remplaçant les ??? par les bonnes instructions.

def hauteur_pile(p):
    q = creer_pile_vide()
    n = 0
    while not est_vide(p):
        ???
        x = depiler(p)
        empiler(q, x)
    while not est_vide(q):
        ???
        empiler(p, x)
    return ???

Réponse attendue

Réponse attendue

def hauteur_pile(p):
    q = creer_pile_vide()
    n = 0
    while not est_vide(p):
        n += 1
        x = depiler(p)
        empiler(q, x)
    while not est_vide(q):
        x = depiler(q)
        empiler(p, x)
    return n

Explications

Le principe de la fonction hauteur_pile est en quatre étapes :

1. Prendre en entrée une pile p.
2. Transférer le contenu de la pile p passée en paramètre vers une pile auxiliaire q. Pendant le dépilage de la pile p, la variable compteur n comptant le nombre de dépilages est incrémentée.
3. Retransférer le contenu de la pile auxiliaire vers la pile p pour reconstituer son état initial.
4. Renvoyer n qui contient le nombre d'éléments de la pile p c’est-à-dire sa taille.

Question 3.

On souhaite écrire une fonction max_pile ayant pour paramètre une pile p et un entier i. Cette fonction renvoie la position j de l'élément maximum parmi les i derniers éléments empilés de la pile p. Après appel de cette fonction, la pile p devra avoir retrouvé son état d'origine. La position du sommet de la pile est 1.

Exemple. Si p est la pile de la question 1, max_pile(p, 2) renvoie 1.

1. Quelles préconditions doivent être vérifiées sur les paramètres de la fonction max_pile ? (on suppose que p est bien une pile et i un entier)

2. Coder en python la fonction max_pile. On vérifiera les préconditions à l'aide de deux assertions. On pourra utiliser la fonction hauteur_pile pour vérifier que la valeur de i est valide.

Réponse attendue

1. • p doit être non vide.
   • i doit être compris entre 1 et la hauteur de la pile.

2. def max_pile(p, i):
       assert not est_vide(p), "pile vide !"
       assert i > 0 and i <= hauteur_pile(p), "i invalide !"
       max = depiler(p)
       empiler(p, max)
       q = creer_pile_vide()
       j = 1
       for k in range(1, i + 1):
           x = depiler(p)
           empiler(q, x)
           if x > max:
               max = x
               j = k
       while not est_vide(q):
           x = depiler(q)
           empiler(p, x)
       return j
   

Question 4.

Créer une fonction retourner ayant pour paramètre une pile p et un entier j. Cette fonction inverse l'ordre des j derniers éléments empilés de p et ne renvoie rien. On pourra utiliser deux piles auxiliaires.

Exemple. Si p est la pile de la question 1., après l'appel retourner(p, 3), l'état de la pile psera :

Réponse attendue

Réponse attendue

def retourner(p, j):
    q = creer_pile_vode()
    r = creer_pile_vode()
    for i in range(j):
        x = depiler(p)
        empiler(q, x)
    while not est_vide(q):
        x = depiler(q)
        empiler(r, x)
    while not est_vide(r):
        x = depiler(r)
        empiler(p, x)

Explications

Le transfert des éléments de la pile d'origine vers une pile auxiliaire puis le retour des éléments dans la pile d'origine ne modifie pas l'ordre des éléments dans la pile d'origine. Il faut donc utiliser une seconde pile auxiliaire :

La fonction retourner réalise donc trois étapes :

1. dépiler les éléments à retourner vers la première pile auxiliaire ;
2. dépiler la première pile auxiliaire vers la seconde pile auxiliaire ;
3. dépiler la seconde pile auxiliaire vers la pile de départ.

Question 5.

L'objectif de cette question est de trier une pile de crêpes.

On modélise une pile de crêpes par une pile d'entiers représentatnt le diamètre de chaque crêpe de la plus grande (placée en bas de la pile) à la plus petite (placée en haut de la pile).

On dispose uniquement d’une spatule que l’on peut insérer dans la pile de crêpes de façon à retourner l'ensemble des crêpes qui lui sont au dessus.

Le principe est le suivant :

• On recherche la plus grande crêpe.
• On retourne la pile à partir de cette crêpe de façon à mettre cette plus grande crêpe en haut de la pile.
• On retourne l'ensemble de la pile de façon à ce que cette plus grande crêpe se retrouve tout en bas.
• La plus grande crêpe étant à sa place, on recommence les étapes précédentes avec le reste de la pile.

Exemple.

Créer la fonction tri_crepes ayant pour paramètre une pile p. Cette fonction trie la pile p selon la méthode présentée précédemment et ne renvoie rien. On utilisera les fonctions créées dans les questions précédentes.

Exemple. Soit la pile p suivante :

Après l’appel tri_crepes(p), la pile p devient :

Réponse attendue

Réponse attendue

def tri_crepes(p):
    h = hauteur_pile(p)
    for i in range(h):
        j = max_pile(p, h - i)
        retourner(p, j)
        retourner(p, h - i)

Explications

Pour expliquer le principe de la fonction tri_crepes, prenons l'exemple de la pile suivante :

Exercice 2. Expression bien parenthesée (Métropole, 11 mai 2022)

Énoncé

Exercice 3. Notation polonaise inversée (Mayotte-Liban, 19 mai 2022)

Énoncé