Aller au contenu principal

TP1 - Prise en main

Au préalable
  1. Se créer un dossier Terminale NSI sur votre ordinateur ou clé USB.
  2. Dans ce dossier, créer un dossier Structures Linéaires.
  3. Créer un nouveau fichier Python nommé TP1_Prise_En_Main.py.
Objectifs

À la fin de ce TP, vous devrez être capable de :

  • représenter une liste chaînée, une pile et une file ;
  • comprendre les opérations élémentaires associées à chacune de ces structures ;
  • utiliser des primitives pour manipuler une structure de données ;
  • distinguer le fonctionnement LIFO d'une pile du fonctionnement FIFO d'une file.
Principe du TP

Dans ce TP, nous utiliserons des objets Python simples pour simuler le fonctionnement des structures linéaires.

L'objectif n'est pas d'apprendre de nouvelles méthodes sur les listes Python, mais de comprendre comment fonctionnent les structures de données étudiées.

Listes chaînées​

Une liste chaînée est constituée de plusieurs éléments reliés les uns aux autres.

Chaque élément contient :

  • une valeur ;
  • la suite de la liste.

On adoptera dans ce TP la représentation suivante :

12 → 5 → 32 → ∅

En Python, cette liste sera représentée par :

[12, [5, [32, None]]]

None représente ici la fin de la liste.

Comprendre la représentation​

ExercicesTout déplier
  1. 1

    Associer chacune des listes Python suivantes à sa représentation sous forme de chaîne.

    L1 = [7, None]

    L2 = [4, [8, None]]

    L3 = [12, [5, [32, None]]]

    Par exemple :

    ? → ? → ∅
  2. 2

    Écrire la représentation Python correspondant à chacune des listes suivantes :

    8 → 3 → ∅

    puis

    42 → 17 → 9 → ∅
  3. 3

    Combien d'éléments possède la liste suivante ?

    L = [6, [2, [9, [4, None]]]]
  4. 4

    Quel est son premier élément ?

  5. 5

    Quelle partie de cette structure correspond à la liste :

    2 → 9 → 4 → ∅

Les primitives d'une liste​

Pour manipuler notre liste chaînée, on souhaite utiliser uniquement quelques fonctions.

On adoptera les primitives suivantes :

PrimitiveRôle
vide()créer une liste vide
est_vide(L)déterminer si une liste est vide
cons(x, L)ajouter x au début de L
tete(L)obtenir le premier élément
queue(L)obtenir la liste privée de son premier élément
ExercicesTout déplier
  1. 1

    Compléter les fonctions suivantes :

    def vide():
        return ...


    def est_vide(L):
        return ...


    def cons(x, L):
        return ...


    def tete(L):
        return ...


    def queue(L):
        return ...
  2. 2

    Tester ensuite :

    L = vide()

    L = cons(32, L)
    L = cons(5, L)
    L = cons(12, L)

    print(L)

Dessiner la liste obtenue sous la forme :

... → ... → ... → ∅
  1. 3

    Que renvoie :

    tete(L)
  2. 4

    Que renvoie :

    queue(L)
  3. 5

    Que renvoie :

    tete(queue(L))

    Expliquer ce dernier résultat.

Manipuler une liste chaînée​

On considère :

L = vide()

L = cons(8, L)
L = cons(15, L)
L = cons(4, L)
ExercicesTout déplier
  1. 1

    Représenter graphiquement L.

  2. 2

    Sans exécuter le programme, déterminer le résultat de :

    tete(L)
  3. 3

    Déterminer le résultat de :

    queue(L)
  4. 4

    Écrire une expression utilisant uniquement tete et queue permettant d'obtenir la valeur 8.

  5. 5

    Écrire les instructions permettant d'ajouter 20 en tête de L.

  6. 6

    Écrire une fonction :

    def longueur(L):

    qui renvoie le nombre d'éléments de la liste.

    Indication

    Tant que la liste n'est pas vide, on peut remplacer la liste par sa queue.

Les piles​

Une pile est une structure dans laquelle le dernier élément ajouté est le premier retiré.

On parle de fonctionnement : LIFO : Last In, First Out.

On peut comparer ce fonctionnement à une pile d'assiettes :

      ┌──────┐
      │  42  │ ← sommet
      ├──────┤
      │  17  │
      ├──────┤
      │   8  │
      └──────┘

L'élément 42, ajouté en dernier, sera retiré en premier.

Comprendre une pile​

ExercicesTout déplier

Une pile est initialement vide.

On effectue successivement les opérations suivantes :

empiler 12
empiler 7
empiler 25
dépiler
empiler 4
  1. 1

    Dessiner l'état de la pile après chaque opération.

  2. 2

    Quelle valeur est retirée lors de l'opération dépiler ?

  3. 3

    Quel élément se trouve finalement au sommet de la pile ?

  4. 4

    Dans quel ordre les éléments restants seraient-ils retirés si l'on vidait complètement la pile ?

Programmer une pile​

Nous allons représenter une pile à l'aide d'une liste Python.

Le sommet de la pile sera situé à la fin de la liste.

Par exemple :

P = [8, 17, 42]

représente :

      ┌──────┐
      │  42  │ ← sommet
      ├──────┤
      │  17  │
      ├──────┤
      │   8  │
      └──────┘
ExercicesTout déplier
  1. 1

    Compléter les primitives suivantes :

    def pile_vide():
        return ...


    def est_vide_pile(P):
        return ...


    def empiler(x, P):
        ...


    def depiler(P):
        ...


    def sommet(P):
        ...


    def taille_pile(P):
        return ...
attention

Une fois ces fonctions écrites, on manipulera les piles uniquement à l'aide de ces primitives.

Par exemple, il sera interdit d'écrire directement :

P.append(12)

dans la suite du TP.

Il faudra écrire :

empiler(12, P)
  1. 2

    Tester les opérations suivantes :

    P = pile_vide()

    empiler(34, P)
    empiler(76, P)
    empiler(43, P)

    a = depiler(P)

    empiler(42, P)

    b = taille_pile(P)
  2. 3

    Sans utiliser Python, représenter l'état de la pile après chaque instruction.

  3. 4

    Que contient la variable a ?

  4. 5

    Que contient la variable b ?

  5. 6

    Quel est l'élément situé au sommet de P ?

Retourner une pile​

On considère la pile suivante :

      ┌──────┐
      │   4  │
      ├──────┤
      │   8  │
      ├──────┤
      │  12  │
      └──────┘
ExercicesTout déplier

On souhaite construire une deuxième pile contenant les mêmes valeurs, mais dans l'ordre inverse :

      ┌──────┐
      │  12  │
      ├──────┤
      │   8  │
      ├──────┤
      │   4  │
      └──────┘
  1. 1

    Compléter la fonction suivante :

    def inverser_pile(P):
        nouvelle = ...

        while not ... :
            ...

        return ...

    Vous devez utiliser uniquement les primitives définies précédemment.

  2. 2

    Créer la pile de l'énoncé, utiliser la fonction sur elle, et vérifier le résultat.

Les files​

Une file fonctionne différemment d'une pile.

Le premier élément ajouté est également le premier élément retiré.

On parle de fonctionnement FIFO : First In, First Out.

On peut comparer cette structure à une file d'attente :

sortie ← [Alice] [Bilal] [Chloé] [David] ← entrée

Alice est arrivée en premier : elle quittera donc la file en premier.

Comprendre une file​

ExercicesTout déplier

Une file est initialement vide.

On effectue successivement :

enfiler 12
enfiler 7
enfiler 25
défiler
enfiler 4
  1. 1

    Dessiner l'état de la file après chaque opération.

    Vous pourrez utiliser la représentation :

    sortie ← [ ... ] [ ... ] [ ... ] ← entrée
  2. 2

    Quelle valeur est retirée lors de l'opération défiler ?

  3. 3

    Quel élément se trouve maintenant en première position ?

  4. 4

    Dans quel ordre les éléments seraient-ils retirés si l'on vidait complètement la file ?

Programmer une file​

Une file sera également représentée par une liste Python.

On adoptera la convention suivante :

sortie ← [12, 7, 25] ← entrée

Ainsi :

  • les nouveaux éléments sont ajoutés à droite ;
  • les éléments sont retirés à gauche.
ExercicesTout déplier
  1. 1

    Compléter les primitives suivantes :

    def file_vide():
        return ...


    def est_vide_file(F):
        return ...


    def enfiler(x, F):
        ...


    def defiler(F):
        ...


    def premier(F):
        ...


    def taille_file(F):
        return ...
attention

Comme pour les piles, la file devra ensuite être manipulée uniquement grâce aux primitives.

  1. 2

    On exécute :

    F = file_vide()

    enfiler(67, F)
    enfiler(34, F)
    enfiler(78, F)

    a = defiler(F)

    enfiler(23, F)

    b = taille_file(F)

    Représenter l'état de la file après chaque opération.

  2. 3

    Que contient a ?

  3. 4

    Que contient b ?

  4. 5

    Quel élément sera retiré lors du prochain appel à :

    defiler(F)

Une file d'impression​

En salle des profs, plusieurs enseignants envoient des documents vers une imprimante.

Les documents sont placés dans une file d'impression dans leur ordre d'arrivée.

ExercicesTout déplier

On effectue :

impressions = file_vide()

enfiler("rapport.pdf", impressions)
enfiler("graphique.png", impressions)
enfiler("programme.py", impressions)
  1. 1

    Quel fichier sera imprimé en premier ?

  2. 2

    Quel fichier sera imprimé en dernier ?

  3. 3

    Compléter le programme suivant permettant d'imprimer tous les documents :

    while not ... :

        document = ...

        print("Impression de", ...)
  4. 4

    Pourquoi une file est-elle plus adaptée qu'une pile pour gérer les impressions ?

Pile ou file ?​

Pour chacune des situations suivantes, indiquer s'il serait plus pertinent d'utiliser une pile ou une file.

Justifier chaque réponse.

ExercicesTout déplier
  1. 1

    Les documents envoyés vers une imprimante.

  2. 2

    La fonction Annuler d'un logiciel de dessin.

  3. 3

    Les clients attendant à une caisse.

  4. 4

    L'historique des pages permettant de revenir à la page précédente dans un navigateur.

  5. 5

    Les tâches envoyées successivement à une machine qui doit les traiter dans leur ordre d'arrivée.

  6. 6

    Les appels successifs de fonctions effectués par un programme.

Le jeu des cartes​

On possède une file contenant des cartes numérotées.

Par exemple :

sortie ← [4] [7] [2] [9] [5] ← entrée

On souhaite appliquer plusieurs fois l'opération suivante :

  1. retirer la première carte ;
  2. placer cette carte à la fin de la file.

Ainsi :

sortie ← [4] [7] [2] [9] [5] ← entrée

devient :

sortie ← [7] [2] [9] [5] [4] ← entrée
ExercicesTout déplier
  1. 1

    Écrire une fonction :

    def rotation(F):

    qui effectue une rotation de la file.

    Vous devez utiliser uniquement les primitives :

    enfiler
    defiler
  2. 2

    Tester votre fonction sur la file définie par :

    F = file_vide()

    enfiler(4, F)
    enfiler(7, F)
    enfiler(2, F)
    enfiler(9, F)
    enfiler(5, F)
  3. 3

    Effectuer trois rotations successives et prévoir l'état de la file avant d'exécuter le programme.