Données Liste

Identification

Infoforall

11 - type abstrait de données Liste

⏪

⏬

⏩

1 - 1 Liste

2 - 2 Listes !

3 - Liste (Tête, Queue)

4 - Implémentation

5 - FAQ
Analogie des dossiers suspendus

L'an dernier, vous avez vu la différence entre un algorithme et son implémentation concrète en programme : un même algorithme peut être implémenté par un programme dans différents langages ou même en différentes versions de programmes pour un même langage. Tant que les programmes vont la même chose, l'utilisateur ne verra pas la différence.

ALGORITHME    ⇒ Implémentation ⇒ PROGRAMME           

Nous allons cette année faire la même chose pour les données : on fait travailler les algorithmes sur des types abstraits de données. On va ensuite les implémenter en machine sous différents types (implémentés).

ALGORITHME    ⇒ Implémentation ⇒ PROGRAMME           

TYPE ABSTRAIT ⇒ Implémentation ⇒  TYPE (implémenté)  

Le mot structure de données fait lui référence à n'importe quel type de données ayant un rôle de conteneur et sur lequel on peut agir en utilisant des fonctions bien précises.

Conclusion de cette présentation

Les Types Abstraits vont nous permettre de résoudre les problèmes sans avoir à savoir comment les données sont réellement stockées et implémentées en machine.

Nous allons simplement nous concentrer sur les deux points fondamentaux suivants :

  1. Comment classifier les données de notre problème ?
  2. Comment utiliser ces données ?

Documents de cours : open document ou pdf

Exercices supplémentaires 🏠 : Exercices

1 - La Liste en tant que type abstrait de données

⇩ ⇧ ⤊

On peut travailler et réfléchir à la gestion de données purement théoriques, sans se soucier de la façon dont elles vont être implémentées par votre programme.

1.1 1er partie de la définition de Liste : l'idée générale

1.1.A Propriétés générales d'organisation

Le type abstrait Liste a les propriétés suivantes :

  • Le mot Element désigne une valeur de la Liste.
  • Le mot Place fait référence au conteneur dans lequel on stocke un Element individuel de la Liste. On pourrait utiliser également le mot Emplacement, mais c'est plus long à écrire. On peut le voir comme un dossier suspendu ou comme un casier...
  • Une Liste une structure linéaire composée d'une séquence finie et ordonnée de Places.
  • On doit pouvoir insérer et supprimer au moins une Place (dont la situation est à choisir : cela peut être au début, ou à la fin, ou partout...)
  • On doit pouvoir accéder à toutes les Places.
  • On doit pouvoir lire un Elément en connaissant la Place qu'il occupe
  • On doit pouvoir trouver le successeur unique de chaque Place.

On peut résumer cela en disant qu'il s'agit d'une structure de données dans laquelle on peut accéder librement à n'importe quelle donnée.

Vous pouvez appréhender le type abstrait Liste en faisant une analogie avec des dossiers suspendus :

Analogie des dossiers suspendus
1.1.B Vocabulaire
  • On désigne la première Place de la Liste sous le nom de tête (head en anglais). On ordonne les autres Places à partir du nombre de sauts nécessaires pour les atteindre à partir de la tête : la tête est à la distance 0, la suivante à 1...
  • L'ensemble des autres Places de la Liste porte le nom de queue (tail en anglais).
  • La dernière Place de la Liste porte le nom de fin. Attention, on trouve parfois également le mot queue pour désigner la fin. Ici, nous utiliserons bien uniquement fin.
  • La Liste est homogène si tous les éléments stockés sont de même type. Sinon elle est inhomogène.
1.1.C Exemple

Deux façons de voir graphiquement une liste contenant une tête dont l'élément est 5 suivie d'une queue contenant les éléments 8, 2 et 3.

  • 5 → 8 → 2 → 3
  • 3 ← 2 ← 8 ← 5
Analogie des dossiers suspendus
1.1.D Propriétés mathématiques ?

Le choix a été fait ici de définir les propriétés sous forme de phrases informelles.

On pourrait formaliser tout cela de façon rigoureuse et établir précisément toutes les propriétés mathématiques que doit avoir le type Liste.

Avantage de la définition globale : facile à comprendre.

Désavantage de la définition globale : pas de formalisme mathématique, les preuves et démonstrations manquent de rigueur.

Vous répondrez aux questions 01 à 05 sous la forme de d'un tableau à quatre colonnes :

Question Tête Queue Liste
01
...
05

01° Sur la Liste, ci-dessous, quel est l'élément contenu dans la tête ? Quelle est la séquence d'éléments qui forme la queue  Quels éléments contient la Liste au total ?

12 → 4 → 5 → -15

...CORRECTION...

La tête est ici identifiée par la couleur ET le sens des flèches.

La tête contient donc l'élément 12.

La queue est donc composée de la séquence (4, 5, -15).

La liste complète est donc (12, 4, 5, -15).

02° Même question : quels sont les éléments de la tête, de la queue, et de la Liste totale ?

23 ← 12 ← 460 ← 1

...CORRECTION...

La tête est ici identifiée par la couleur ET le sens des flèches.

La tête contient donc 1.

La queue est donc composée de (460, 12, 23).

La liste complète est donc (1, 460, 12, 23).

03° Sans l'information couleur. Même question : quels sont les éléments de la tête, de la queue, et de la Liste totale ?

21 → 12 → 13 → 0

...CORRECTION...

La tête est ici identifiée par le sens des flèches : c'est le premier élément.

La tête contient donc 21.

La queue est donc composée de (12, 13, 0).

La liste complète est donc (21, 12, 13, 0).

04° Quels sont les éléments de la tête, de la queue, et de la Liste totale ?

20 ← 45 ← 10 ← 18

...CORRECTION...

La tête est ici identifiée par le sens des flèches : c'est le premier élément.

La tête contient donc 18.

La queue est donc composée de (10, 45, 20).

La liste complète est donc (18, 10, 45, 20).

05° Seule la tête est indiquée. Quels sont les éléments de la tête, de la queue, et de la Liste totale ?

23 - 12 - 460 - 1

...CORRECTION...

La tête est ici identifiée par la couleur.

La tête contient donc 1.

La queue est donc composée des éléments situés linéairement derrière cette tête : (460, 12, 23).

La liste complète est donc (1, 460, 12, 23).

1.2 Représentation graphique d'une Liste

1.2.A Représentation Tête → Queue

Une Liste NON VIDE est fondamentalement une tête menant à une queue.

5 → 8 → 2 → 3

Si le 5 est la tête d'une Liste nommée lst1, on peut noter sa queue lst2.

5 → lst2

On pourrait alors noter ceci : lst1 = (5, lst2).

D'ailleurs, lst2 est également une Liste  : sa tête contient 8 et mène à une queue lst3...

8 → lst3

lst2 = (8, lst3)

On obtient alors l'enchaînement suivant, qui est assez proche des appels de fonctions récursives :

  • lst1 = (5, lst2)
  • lst2 = (8, lst3)
  • lst3 = (2, lst4)
  • lst4 = (3, lst5)
  • lst5 = ()
1.2.B Définition

Une Liste peut être :

  • soit une liste vide (c'est le cas de base)
  • soit un couple (tête, queue), la queue étant elle-même une liste (c'est le cas récursif)

On pourrait remonter dans l'autre sens dans nos déclarations et obtenir ceci :

  • lst4 = (3, ())
  • lst3 = (2, (3, ()))
  • lst2 = (8, (2, (3, ())))
  • lst1 = (5, (8, (2, (3, ()))))

    • Remarquez bien que la queue de lst4 est vide. C'est possible puisque qu'une queue est une liste et qu'une liste peut être vide.

1.2.C Représentation en séquence ordonnée

On dispose donc de plusieurs façons pour représenter symboliquement nos listes :

Avec des parenthèses : (5, (8, (2, (3)))) ou plus facilement par (5, 8, 2, 3)

Avec des crochets : [5, [8, [2, [3]]]] ou plus facilement par [5, 8, 2, 3]

Avec chevrons : <5, <8, <2, <3>>>> ou plus facilement par <5, 8, 2, 3>

Avec des accolades : {5, {8, {2, {3}}}} ou plus facilement par {5, 8, 2, 3}

On évitera cette notation "accolades" car on pourrait confondre avec les ensembles mathématiques, où un élément ne peut être présent qu'une fois. Or, dans une liste, une même valeur peut être présente plusieurs fois.

Il faut juste choisir, le noter clairement.

Dans le cadre de ce cours, nous utiliserons les parenthèses.

(5, 8, 2, 3)

La représentation n'est qu'une apparence externe

Comprennez bien qu'on peut représenter des données identiques de plusieurs façons, tout en ne changeant rien aux données elles-mêmes.

C'est le principe de l'interface : la mécanique interne de fonctionnement est indépendante de la façon dont on génère sa représentation externe.

06° Donner deux représentations de la liste suivante :

  • comme une imbrication (tête, queue)
  • comme une simple séquence linéaire d'éléments :

12 → 4

...CORRECTION...

En représentation (tête, queue)

(12, liste2)

(12, (4, ()))

En séquence linéaire : (12, 4)

07° Donner deux représentations de la liste suivante :

  • comme une imbrication (tête, queue)
  • comme une simple séquence linéaire d'éléments :

5 → 2 → 10

...CORRECTION...

Première représentation

(5, liste2)

(5, (2, liste3))

(5, (2, (10, ())))

La deuxième représentation est donc (5, 2, 10).

1.3 Signatures et erreur de Type

1.3.A Signature : définition

Une signature est une formulation précise de la syntaxe et des types pour utiliser correctement un opérateur ou une fonction. Elle signale :

  • le symbole de l'opérateur ou le nom de la fonction
  • les types des entrées
  • où placer les entrées par rapport à l'opérateur ou lors de l'appel d'une fonction
  • le type de la réponse

Exemple 1 : signature de la fonction native len() :

len(str) → int
len(list) → int
len(tuple) → int
len(dict) → int

Exemple 2 : quelques signatures disponibles sur les strings en Python :

str + str → str
str * int → str
int * str → str
str in str → bool
str in list → bool
str < str → bool
str.lower() → str

Intérêt :

  • Lorsqu'on respecte une signature, il n'y aura pas d'erreur de SYNTAXE. La demande est correctement formulée.
  • C'est comme cela que Python sait si une expression que vous transmettez est "valide" ou non. L'interpréteur cherche à trouver un motif correspondant à une signature connue.
  • Il s'agit de contraintes liées uniquement au type, pas au contenu réel envoyé : même si le contenu est du bon type, il peut y avoir une erreur d'EXECUTION.
1.3.B  : Signature non valide : erreur de Type
>>> "Pom !" * 4 'Pom ! Pom ! Pom ! Pom !' >>> "Pom !" * 4.0 TypeError: can't multiply sequence by non-int of type 'float'

Selon les langages, elle sera détectée avant l'exécution ou pendant l'exécution.

Python ne les détecte que lors de l'exécution de l'expression problématique. Ocaml les détecte avant exécution.

1.3.C Signature valide

Respecter une signature veut dire qu'il n'y a pas d'erreur de SYNTAXE sur cette expression.

Respecter une signature ne veut pas dire qu'il n'y aura pas d'erreur d'EXECUTION ou d'erreur SEMANTIQUE.

Exemple 1 : la signature int // int → int existe mais :

>>> 6 // (5 - 5) ZeroDivisionError: division by zero

Ici, nous avons bien une erreur d'exécution : la signature est bonne mais pas l'exécution de la demande.

Exemple 2 : la signature float + float → float existe mais également la signature tuple + tuple → tuple !

>>> 6,2 + 1,3 (6, 3, 3)

Ici, nous avons bien une erreur de sémantique si vous avez voulu additionner deux flottants : vous avez oublié que c'est le point qui fait office de virgule et Python a lui traité la demande comme ce qu'elle veut dire : elle a utilisé la deuxième signature puisque pour lui 6,2 est le tuple (6, 2).

>>> 6,2 (6, 2)

08° Taper ceci dans la console Python et, pour chaque opération :

  1. Donner l'association type-opérateur qu'on vient de tenter d'utiliser (exemple int + int) et dire si cette association est acceptée en Python.
  2. Si elle existe, donner la signature fournie par cette syntaxe (exemple int + int -> int )
  3. Si elle existe, donner la sémantique de cette signature (exemple : + symbolise une addition entre deux entiers en Python)
>>> 46 // 10 >>> 46 % 10 >>> [46] + [10] >>> [46] * [10] >>> [46] * 10

...CORRECTION...

>>> 46 // 10 4
  1. L'association int // int est acceptée par Python
  2. La signature est int // int -> int
  3. La sémantique de cette signature correspond à la recherche du quotient d'une division euclidienne (on peut faire 4 paquets de 10 objets avec 46 objets)
>>> 46 % 10 6
  1. L'association int % int est acceptée par Python
  2. La signature est int % int -> int
  3. La sémantique de cette signature correspond à la recherche du reste d'une division euclidienne (il va rester 6 objets si on fait des paquets de 10 objets avec 46 objets)
>>> [46] + [10] [46, 10]
  1. L'association list + list est acceptée par Python
  2. La signature est list + list -> list
  3. La sémantique de cette signature correspond à la concaténation de deux list Python.
>>> [46] * [10] TypeError: can't multiply sequence by non-int of type 'list'
  1. L'association list * list n'est pas acceptée par Python. Elle provoque donc une erreur de type.
>>> [46] * 10 [46, 46, 46, 46, 46, 46, 46, 46, 46, 46]
  1. L'association list * int ou int * list est acceptée par Python
  2. La signature est int * list -> list
  3. La sémantique de cette signature correspond à la répétition des éléments d'une list-Python pour créer une nouvelle list-Python.
1.4 Spécification d'une fonction

La connaissance de la signature permet d'éviter les erreurs de type, mais pas les erreurs d'exécution.

Pour éviter les erreurs d'exécution, il faut donner une description encore plus précise de la fonction : sa spécification.

Une SPECIFICATION de fonction consiste à fournir :

  • son NOM,
  • sa SIGNATURE,
  • une DESCRIPTION textuelle de ce que fait cette fonction.
  • les éventuelles PRECONDITIONS éventuelles sur les paramètres d'entrée : quelles sont les conditions supplémentaires en plus du simple type (entier NON NUL, texte SANS ESPACE...)
  • les éventuelles POSTCONDITIONS sur la réponse fournie par la fonction : quelles sont les propriétés supplémentaires que le concepteur garantit sur la sortie.
1.5 Primitives

A Vocabulaire : fonctions d'interface

Fonctions d'interface d'un module : en informatique, les fonctions d'interface caractérisent les fonctions qui sont utilisables par l'utilisateur d'un module :

PROG. UTILISATEUR  ⇔ INTERFACE ⇔ Logique interne

Le module est formé par les deux boîtes de droite : Interface + Logique interne, ou fonctions publiques et fonctions privées.

Un algorithme ne pas manipuler les données du type abstrait qu'en utilisant les fonctions d'interface de ce type type abstrait.

 ALGORITHME       ⇔ INTERFACE ⇔ Données internes

Le type abstrait est formé par les deux boîtes de droite : Interface + Données internes.

B Vocabulaire : fonctions primitives

Trois idées caractérisent ces fonctions particulières :

  1. Les opérations primitives font partie des fonctions d'interface disponibles pour ce type abstrait de données.

    2. Mais attention : toutes les fonctions d'interface ne sont pas des opérations primitives.

  2. Les opérations primitives sont les briques d'actions fondamentales permettant d'agir sur ce type de données.

    3. En utilisant uniquement les primitives, on doit pouvoir créer toutes les autres fonctions permettant d'agir sur ce type.

  3. Même si la notion de coût n'existe pas réellement pour une idée abstraite, les futures implémentations des primitives devront avoir le coût le plus faible possible (un coût constant si possible).
1.6 2nd partie de la définition de Liste : spécifications des primitives

1.6.A Dépendances du type abstrait Liste

Les dépendances de type sont les autres types abstraits qui font apparaître dans les signatures des primitives du type étudié. Il faut définir et clarifier ces autres types pour éviter toute ambiguïté sur le nouveau type.

Pour définir notre Liste, nous allons avoir besoin des autres types suivants :

  • Vide pour référencer l'absence d'information,
  • Booléen,
  • Entier Naturel,
  • Elément (le type des données que nous allons pouvoir ranger dans la Liste),
  • Place (le conteneur permettant de stocker un Elément). On décide du fait qu'une Place ne peut pas être vide : si elle existe, c'est qu'elle contient un Element.

On peut donc voir la Liste comme une sorte de conteneur de Places, chaque Places contenant elle-même un Element.

1.6.B Spécifications : définition

Voici les primitives d'une Liste immuable. Nous allons voir que toutes ne sont pas nécessaires mais qu'il faut pouvoir les recréer avec celles que vous avez au départ.

Fondamentales

  1. nouvelleListeVide() → Liste

    2. DESCRIPTION : Renvoie une nouvelle Liste VIDE initialement.

  2. estListeVide(lst:Liste) → Booléen

    3. DESCRIPTION : Renvoie VRAI si la liste lst fournie est vide, FAUX sinon.

  3. inserer(lst:Liste, elt:Elément, ...) → Liste

    4. DESCRIPTION : Renvoie une nouvelle Liste comportant le nouvel élément à une position définie : en tête de liste, en fin de liste, à un indice i précis. Certaines valeurs seront donc décalées par rapport à la Liste initiale.

    Voici plusieurs versions qui pourraient convenir, la dernière étant la plus générique :

    insererTete(lst:Liste, elt:Elément) → Liste

    DESCRIPTION : Renvoie une nouvelle Liste où l'élément est placé en tête de liste, provoquant le décalage des autres élements.

    insererFin(lst:Liste, elt:Elément) → Liste

    DESCRIPTION : Renvoie une nouvelle Liste où l'élément est placé en fin de liste.

    inserer(lst:Liste, elt:Elément, i:Entier Naturel) → Liste

    DESCRIPTION : Renvoie une nouvelle Liste comportant le nouvel élément à la position indiquée par l'indice fourni. Certains emplacements sont donc décalés d'une position par rapport à la Liste initiale.

    • Pour insérer comme nouvelle Tête, on doit donc envoyer i valant 0.
    • Pour insérer juste avant la fin, on doit envoyer longueur -1.
    • Pour insérer comme nouvelle fin, on doit envoyer longueur qui correspond à un indice "vide" pour la liste de départ.

    PRECONDITIONS :

    • l'indice i (s'il existe) caractérise un indice valide pour l'insertion
    • elt doit avoir un type compatible avec le reste des Eléments si la Liste est homogène.

    POSTCONDITION : la Liste renvoyée possède un emplacement en plus mais lst est inchangée.

    Exemples d'utilisation

    lstA = nouvelleListeVide()
    lstB = inserer(lstA, 5, 0)
    lstB contient alors (5, () ) qu'on pourrait noter simplement (5, ).

    lstC = inserer(lstB, 15, 0)
    lstC contient alors (15, (5, () )) qu'on pourrait noter (15, 5, ).

    lstD = inserer(lstC, 25, 1)
    lstD contient alors (15, (25, (5, () ))) qu'on pourrait noter (15, 25, 5, ).

    lstE = inserer(lstD, 50, 3)
    lstE contient alors (15, (25, (5, (50, () )))) qu'on pourrait noter (15, 25, 5, 50, ).

  4. supprimer(lst:Liste, ...) → Liste

    5. DESCRIPTION : Renvoie une nouvelle Liste dans laquelle on a supprimé un emplacement prédéfini dans la Liste NON VIDE reçue. Certains emplacements sont donc décalés d'une position par rapport à la Liste initiale.

    Voici plusieurs versions qui pourraient convenir, la dernière étant la plus générique :

    supprimerTete(lst:Liste) → Liste

    DESCRIPTION : Renvoie une nouvelle Liste dans laquelle on a supprimé l'ancien emplacement en tête de liste. Certains emplacements sont donc décalés par rapport à la Liste initiale.

    supprimerFin(lst:Liste) → Liste

    DESCRIPTION : Renvoie une nouvelle Liste dans laquelle on a supprimé l'ancien emplacement en fin de liste. Certains emplacements sont donc décalés d'une position par rapport à la Liste initiale.

    supprimer(lst:Liste, i:Entier Naturel) → Liste

    DESCRIPTION : Renvoie une nouvelle Liste dans laquelle on a supprimé l'ancien emplacement ayant cet indice. Certains emplacements sont donc décalés d'une position par rapport à la Liste initiale.

    • Pour supprimer l'élément de Tête, on doit donc envoyer i valant 0.
    • Pour supprimer l'élément de fin, on doit envoyer longueur -1.

    PRECONDITION :

    • la Liste est NON VIDE.
    • l'indice i (s'il existe) est un indice VALIDE.

    POSTCONDITION : la Liste renvoyée possède un emplacement en moins mais lst est inchangée.

    Exemple d'utilisation

    Partons de lstE contenant (15, (25, (5, (50, () )))) ou simplement (15, 25, 5, 50, ).
    lstF = supprimer(lstE, 1)
    lstF contient alors (15, (5, (50, () ))) ou simplement (15, 5, 50, ).

    lstG = supprimer(lstF, 2)
    lstG contient alors (15, (5, () )) ou simplement (15, 5, ).

Importante si on utilise les indices

  1. longueur(lst:Liste) → Entier Naturel

    2. DESCRIPTION : Renvoie le nombre d'éléments stockés dans la liste.

Interactions avec les Places

  1. acces(lst:Liste, ...) → Place

    2. DESCRIPTION : Renvoie la Place correspondant à une position définie.

    PRECONDITION : la Liste reçue doit être NON VIDE.

    Voici plusieurs versions qui pourraient convenir, la dernière étant la plus générique :

    accesTete(lst:Liste) → Place

    DESCRIPTION : Renvoie la Place correspondant à la tête.

    accesFin(lst:Liste) → Place

    DESCRIPTION : Renvoie la Place correspondant à la fin.

    acces(lst:Liste, i:Entier Naturel) → Place

    DESCRIPTION : Renvoie la Place correspondant à l'indice i fourni.

    PRECONDITION :

    • la Liste est NON VIDE.
    • l'indice i (s'il existe) est un indice VALIDE.

    POSTCONDITION : la Liste est inchangée.

    Les deux dernières primitives interagissent directement avec une Place. Attention, dans l'esprit de ce type abstrait Liste, la connaissance d'une Place doit venir de l'utilisation de acces().

  2. contenu(plc:Place) → Elément

    3. DESCRIPTION : Renvoie l'Elément référencé par plc.

    PRECONDITION : plc est une Place valide, contenant un élément compatible avec les autres si la Liste est homogène.

    POSTCONDITION supplémentaire : si la Liste est homogène le type de l'Elément est compatible avec ceux de la Liste.

  3. successeur(plc:Place) → Place

    4. DESCRIPTION : Renvoie la Place qui succède à plc, une Place NON FIN.

    PRECONDITION : plc est une Place qui ne doit pas être la dernière de la Liste, la Fin.

L'une des spécificités du type abstrait Liste est que sa définition est plutôt large car

  • on n'explique pas vraiment ce qu'est une Place. Il faut juste que votre type Place soit lui clairement défini.
  • on n'impose pas spécifiquement d'endroit où agir. Il faut juste que votre version soit claire à ce sujet.

Toutes les structures de données qui collent à la définition et qui possèdent ces primitives sont donc des Listes.

Résumé : les 8 types de primitives qu'il faudra avoir ou reconstruire à partir des autres :

Fondamentales

  1. nouvelleListeVide() → Liste VIDE
  2. estListeVide(lst:Liste) → Booléen
  3. inserer(lst:Liste, elt:Elément, i:Entier Naturel INDICE VALIDE) → Liste NON VIDE
  4. supprimer(lst:Liste NON VIDE, i:Entier Naturel INDICE VALIDE) → Liste

Importante si on utilise les indices

  1. longueur(lst:Liste) → Entier Naturel

Interactions avec les Places

  1. acces(lst:Liste NON VIDE, i:Entier Naturel INDICE VALIDE) → Place
  2. contenu(plc:Place) → Elément
  3. successeur(plc:Place NON FIN) → Place

09° Donner le contenu des variables au fur et à mesure de l'exécution de cette suite d'actions. J'utilise une syntaxe Python en tant que pseudo-langage algorithmique.

1 2 3 4 5 6 7
lstA = inserer(nouvelleListeVide(), 4, 0) lstB = inserer(lstA, 6, 1) lstB = inserer(lstB, 10, 0) x = contenu(acces(lstB, 2)) lstC = supprimer(lstB, 2) lstC = inserer(lstC, 100, 1) a = contenu(sucesseur(acces(lstC, 0)))

Attention, ce n'est pas un algorithme : un algorithme doit résoudre un problème ou répondre à une question. Ici, il ne s'agit que d'une suite d'actions.

...CORRECTION...

1 2 3 4
lstA = inserer(nouvelleListeVide(), 4, 0) lstB = inserer(lstA, 6, 1) lstB = inserer(lstB, 10, 0) x = contenu(acces(lstB, 2))

Ligne 1 : lstA contient (4, () ) ou (4, )

Ligne 2 : lstB contient (4, (6, () )) ou (4, 6)

Ligne 3 : on modifie lstB en lui affectant la réponse de la fonction, qui contient (10, (4, (6, () ))) ou (10, 4, 6)

Ligne 4 : x contient 6

5 6 7
lstC = supprimer(lstB, 2) lstC = inserer(lstC, 100, 1) a = contenu(sucesseur(acces(lstC, 0)))

Ligne 5 : lstC contient (10, (4, () )) ou (10, 4)

Ligne 6 : lstC contient (10, (100, (4, () ))) ou (10, 100, 4)

Ligne 7 : on récupère la Place de tête, on cherche son successeur et on lit l'élément qui s'y trouve : c'est donc 100.

10° On vous donne ci-dessous l'affectation d'une Liste générée en rajoutant des éléments au fur et à mesure à une Liste vide.

1
lstA = inserer(inserer(inserer(nouvelleListeVide(), 4, 0), 6, 0), 8, 0)
  1. Expliquer que le contenu de cette Liste soit (8, 6, 4) en détaillant le fonctionnement en 3 étapes.
  2. Fournir ensuite les instructions qui permettraient de passer de la Liste lstA contenant (8, 6, 4) à une Liste lstB (10, 6, 4)

...CORRECTION...

1
lstA = inserer(inserer(inserer(nouvelleListeVide(), 4, 0), 6, 0), 8, 0)

Python exécute cette première fonction et on récupère donc une première liste contenant (4, ) en position 0.

1
lstA = inserer(inserer( (4, ), 6, 0), 8, 0)
1
lstA = inserer(inserer( (4, ), 6, 0), 8, 0)

Python doit maintenant générer, à partir de (4, ), une nouvelle liste où 6 est en position de tête (indice 0).

1
lstA = inserer( (6, 4), 8, 0)

Il exécute et on récupère donc une liste contenant (6, 4) en position 0.

1
lstA = inserer( (6, 4), 8, 0)

On voit qu'on doit maintenant rajoutant à la liste (6, 4) un élément valant 8 et se trouvant en place 0.

On obtient donc au final (8, 6, 4).

Pour créer la liste B, il suffit de demander d'utiliser les primitives de cette façon&nbs:;

2 3
lstB = supprimer(lstA, 0) lstA = inserer(lstA, 10, 0)
1.7 Muable ou immuable

Une Liste est immuable lorsqu'on renvoie la référence d'une nouvelle Liste lorsqu'on ajoute ou retire un élément.

L'information apparaît clairement sur les SIGNATURES, sur les PROTOTYPES et donc dans la SPECIFICATION.

On aurait également pu créer des fonctions d'interface pour un type abstrait muable.

Voici la signature des fonctions qui diffèrent de la version immuable :

  • inserer(lst:Liste, elt:Elément, i:Entier Naturel) → Vide

    • DESCRIPTION : Ne renvoie rien mais modifie la Liste directement.

    PRECONDITIONS : l'indice i caractérise un indice valide.

  • supprimer(lst:Liste, i:Entier Naturel) → Vide

    • DESCRIPTION : Ne renvoie rien la Liste est modifiée directement.

    PRECONDITION : l'indice i caractérise un indice valide.

    Dans ce cas d'un muable, plutôt que de ne rien renvoyer, on utilise souvent la sortie pour renvoyer l'élément qu'on vient de supprimer.

  • supprimer(lst:Liste, i:Entier Naturel) → Element

    • PRECONDITION : l'indice i caractérise un indice valide.

    POSTCONDITION : la Liste est modifiée directement et on renvoie l'élément qu'on vient de supprimer de la Liste.

11° On suppose pour cette question qu'on dispose d'un type abstrait Liste muable. Que doit-on noter pour indiquer qu'on veut obtenir une modification de la Liste lstA contenant (10, 100) en (1, 10, 100) ?

  1. lstA = inserer(lstA, 1, 0)
  2. lstA = inserer(lstA, 0, 1)
  3. inserer(lstA, 1, 0)
  4. inserer(lstA, 0, 1)

Donner la bonne réponse et expliquer le problème engendré par les 3 autres propositions.

...CORRECTION...

Les cas A et B sont nécessairement faux puisque la fonction inserer() ne renvoie rien dans le cas d'un type muable.

C'est donc C ou D.

La position d'insertion est le 3e argument à envoyer. Il faut donc envoyer 0 en dernière position.

Sur le cas D, on demande d'insérer la valeur 0 en position 1. Ce n'est pas cela qu'on veut.

La bonne réponse est donc C : on insère la valeur 1 en position 0 directement dans la liste muable.

2 - Deux Listes en tant que type abstrait de données !

⇩ ⇧ ⤊

Pour aller plus loin et décrire plus précisément ce qu'est une Liste, il va falloir définir ... Place.

Il existe deux grandes familles fonctions :

  1. les fonctions itératives
  2. les fonctions récursives

De la même façon, il existe deux grandes familles de Listes :

  1. Les Listes itératives
  2. Les Listes récursives
2.1 Liste itérative 

Principe : la Liste itérative est une liste dans laquelle :

  • Les Places sont des cases qui ne "bougent" pas : elles possèdent un numéro (un indice) constant
  • les Eléments peuvent éventuellement changer de Place.

Idée sous-jacente : l'armoire avec des casiers fixes.

  • La Liste est l'armoire.
  • Les Places sont des casiers fixés dans la structure, sur lequel un numéro est inscrit définitivement
  • Les Eléments sont les choses qu'on place dans les casiers.

Dans la logique itérative, une fonction assemble elle-même les sous-réponses fournies par d'autres fonctions ou opérateurs qu'elle active.

Si on ramène cela à la logique de la localisation des Places depuis la Liste, cela donne la Liste Itérative : il existe un mécanisme permettant de rattacher chaque indice à une Place. Si on lui fournit un indice, la Liste peut donc localiser immédiatement la Place correspondante et son Elément :

Cela ressemble énormément aux tableaux statiques, si ce n'est qu'on doit pouvoir rajouter ou supprimer des cases.

Avantage : Lecture ou modification d'un élément unique

Connaissant simplement un indice, on accède immédiatement à chaque Place et Element.

Désavantage : insertion ou permutation

Il est difficile d'effectuer des permutations de valeurs ou d'insérer une nouvelle donnée. Voici un exemple où on tente de produire (D, A, B, C) à partir de (A, B, C, D).

Les Places sont fixes mais on peut modifier l'association Place -> Elément. On ne déplace donc pas les Places. mais on permute les Elements dans les Places.

On se rend compte que le nombre de déplacements est linéaire par rapport au nombre d'éléments dans la Liste.

2.2 Liste récursive 

Principe : la Liste récursive permet d'atteindre directement la tête, les autres cases devant alors être trouvées de proche en proche.

  • Depuis la Place de tête, on peut atteindre son successeur.
  • Depuis le successeur, on peut atteindre le successeur du successeur...
  • On peut modifier la Place vers laquelle pointe la Liste récursive pour indiquer où se trouve la tête.

Idée sous-jacente : le tiroir à dossier suspendus.

  • La Liste est le tiroir.
  • Les Places sont les dossiers suspendus, sans numérotation
  • Les Eléments sont les choses qu'on place dans les dossiers suspendus

Dans la logique récursive, la fonction délègue une grande partie des calculs à une autre fonction qui délègue elle-même le travail jusqu'à tomber sur une fonction cas de base qui pourra enfin répondre seule à une partie du problème. Les réponses remontent alors peu à peu jusqu'à la première fonction. La fonction initiale n'a finalement qu'un petit calcul à réaliser à partir de la réponse que lui a fourni la seule fonction qu'elle avait activé au départ.

Si on ramène cela à la logique de la localisation des Places depuis la Liste, cela donne la Liste Récursive : cette fois, on ne peut accéder directement qu'à la Place de Tête. On peut accéder à toutes les autres places, mais il faudra les parcourir une à une puisque chaque Place est l'unique détentrice de l'identité de la Place suivante :

Désavantage : lecture ou modification d'un Elément

Le nombre d'opérations nécessaire à la lecture de toute la Liste récursive est linéaire par rapport au nombre d'éléments dans la Liste puisqu'on part de la tête pour parcourir une à une toutes les Places.

Avantage : insertion ou modification de la séquence

L'avantage de ce genre de Liste vient du fait qu'il n'y pas de liaison enregistrée dans la Liste elle-même entre Places et indices. Chaque Place gère seule son successeur. Il suffit donc de modifier quelques liaisons de successeurs ou d'accès pour parvenir à modifier le déroulé de la séquence.

Si on étudie la modification, on se rend compte qu'on aura toujours que 3 modifications de liaisons à faire quelque soit le nombre d'éléments dans la Liste.

2.4 Et le type list de Python alors ?

Plusieurs choses à comprendre :

  1. Le type list-Python n'est pas un type abstrait mais une implémentation.
  2. La list-Python est plutôt une implémentation muable d'une Liste Itérative.
  3. Néanmoins, la list-Python est une extension de cette idée : on peut insérer en fin de liste avec la méthode append(), et supprimer en fin de liste avec la méthode pop().
>>> t = [10, 100, 6] >>> t.append(1000) >>> t [10, 100, 6, 1000] >>> t.pop() 1000 >>> t [10, 100, 6]
  • La list-Python est donc l'implémentation d'une Liste Itérative possédant quelques attributs des Listes Récursives. Un savant mélange des deux.

    • 3 - Liste récursive couple (Tête, Queue)

    ⇩ ⇧ ⤊

    3.1 La Liste Récursive couple (Tête, Queue)

    C'est une Liste Récursive IMMUABLE très simple : on accède, insère ou supprime uniquement au niveau de la tête de liste.

    En réalité, on obtient donc une version très proche de la Liste de la partie 1 : celle où la Queue d'une Liste est fondamentalement une Liste elle-même.

    3.2 Primitives de la Liste (Tête, Queue)

    On donne les opérations primitives les plus basiques qui soient (sous entendu "il semble logique de pouvoir les implémenter par des fonctions ayant un coût constant").

    L'accès, la lecture et la suppression se feront donc uniquement sur la Place de tête puisque c'est la seule directement accessible.

    Les opérations primitives restreintes semblent donc différentes de celles d'une Liste classique. Voici les noms qu'on leur donne (ainsi que quelques alias plus courts à noter).

    1. nouvelleListeVide() → Liste

      2. DESCRIPTION : Renvoie une nouvelle Liste qui est VIDE initialement.

      Exemple d'utilisation

      lstA = nouvelleListeVide()
      Le contenu de lstA est alors () par exemple.

    2. estListeVide(lst:Liste) → Booléen
      estLVd()

      3. DESCRIPTION : Renvoie VRAI si la liste lst fournie est vide, FAUX sinon.

      Exemple d'utilisation

      lstA = nouvelleListeVide()
      estListeVide(lstA)       renvoie alors VRAI.

    3. inserer()
      insererTete(lst:Liste, elt:Elément) → Liste
      insT()
      cons()

      4. DESCRIPTION : Renvoie une nouvelle Liste comportant le nouvel élément à la position de la Tête. Certains emplacements sont donc décalés d'une position par rapport à la Liste initiale.

      PRECONDITIONS : elt doit avoir un type compatible avec le reste des Eléments si la Liste est homogène.

      POSTCONDITION : la Liste renvoyée est NON VIDE et possède un emplacement en plus mais lst est inchangée.

      La Liste est ici immuable puisqu'on renvoie une nouvelle Liste, plutôt que de juste modifier l'ancienne en mémoire.
      Dans LISP, cette fonction se nomme cons (comme construct).

      Exemple d'utilisation

      lstA = nouvelleListeVide()
      lstB = insererTete(lstA, 5)
      lstB contient alors (5, ()) qu'on pourrait noter simplement (5,).

      lstB = insererTete(lstB, 15)
      lstB contient alors quelque chose comme (15, (5, ())), qu'on peut plutôt représenter par (15, 5). Graphiquement, les relations entre les Places donnent alors ceci :

      Place (15) qui mène à une Place (5)
    4. supprimer()
      supprimerTete(lst:Liste) → Liste
      supT()
      cdr()
      recupererQueue()

      5. DESCRIPTION : Renvoie une copie de lst privée de sa tête. Elle renvoie donc la queue de lst.

      PRECONDITION : lst doit être NON VIDE.

      Historiquement, dans LISP cette fonction se nomme cdr (contents of decrement register).

      Exemple d'utilisation

      On considère que lstB contient (25, (15, (5, ()))) ou (25, 15, 5) Place (25) qui mène à une Place (15) qui mène à une Place (5)
      lstC = supprimerTete(lstB)
      lstC contiendra alors (15, (5, ())) ou (15, 5). Place (15) qui mène à une Place (5)
      lstB contient toujours (25, (15, (5, ())))

    5. longueur()

      6. On décide de ne pas mettre longueur() ici car il faudrait d'autres informations que la simple localisation de la tête pour agir.

    6. acces()
      accesTete(lst:Liste) → Place
      tete()

      7. DESCRIPTION : Renvoie la Place de la Tête.

      PRECONDITION : La Liste doit être NON VIDE.

      contenu() et successeur() sont inchangées.

    7. contenu(plc:Place) → Elément

      8. DESCRIPTION : Renvoie l'Elément référencé par plc.

      PRECONDITION : plc est une Place valide, contenant un élément compatible avec les autres si la Liste est homogène.

      POSTCONDITION : si la Liste est homogène le type de l'Elément est compatible avec ceux de la Liste.

      Exemple d'utilisation

      On considère que lstB contient (25, (15, (5, ())))
      ref = accesTete(lstB)
      recup = contenu(ref)
      recup contient alors 25. La liste lstB n'a pas été modifiée.

      On aurait pu noter directement :
      recup = contenu(accesTete(lstB))

    8. successeur(plc:Place) → Référence Vide|Place

      9. DESCRIPTION : Renvoie la Place située à la suite de plc, ou Vide si cette Place n'a pas de successeur.

      Exemple d'utilisation

      On considère que lstB contient (25, (15, (5, ())))
      ref = accesTete(lstB)
      ref = successeur(ref)
      ref = successeur(ref)
      recup = contenu(ref)
      On obtient alors la valeur 5 dans recup. La liste lstB n'a pas été modifiée.

    Nous prendrons uniquement les 7 opérations primitives suivantes :

    • nouvelleListeVide() → Liste VIDE
    • estListeVide(lst:Liste) → Booléen
    • insererTete(lst:Liste, elt:Elément) → Liste NON VIDE
    • supprimerTete(lst:Liste NON VIDE) → Liste
    • accesTete(lst:Liste NON VIDE) → Place
    • contenu(plc:Place) → Elément
    • successeur(plc:Place NON FIN) → Place

    On remarquera que l'utilisateur ne crée jamais directement de Place : c'est la structure de données qui s'en charge lorsqu'on active insererTete().

    La suite ?

    Vous allez voir maintenant :

    1. qu'on peut manipuler les données abstraites sans toucher un clavier
    2. qu'on peut recréer les primitives manquantes en utilisant ces 7 primitives
    3. qu'il s'agit donc bien d'une Liste
    4. qu'avec juste l'idée de cette Liste, on peut prévoir qu'elles actions seront rapides ou longues qu'on réalisera l'implémentation.

    12° Donner le contenu des variables au fur et à mesure de l'exécution de cette suite d'actions. J'utilise une syntaxe Python en tant que pseudo-langage algorithmique.

    1 2 3 4 5 6
    lstA = insererTete(nouvelleListeVide(), 4) lstB = insererTete(lstA, 6 ) lstC = insererTete(lstB, 0) x = contenu(accesTete(lstC)) lstD = supprimerTete(lstC) a = contenu(sucesseur(accesTete(lstD)))

    Attention, ce n'est pas un algorithme : un algorithme doit résoudre un problème ou répondre à une question. Ici, il ne s'agit que d'une suite d'actions.

    ...CORRECTION...

    Ligne 1 : lstA contient (4, ()) ou (4,)

    Ligne 2 : lstB contient (6, (4, ())) ou (6, 4)

    Ligne 3 : lstC contient (0, (6, (4, ()))) ou (0, 6, 4)

    Ligne 4 : x contient 0

    Ligne 5 : lstD contient (6, (4, ())) ou (6, 4)

    Ligne 6 : on récupère la zone de tête, on cherche son successeur et on lit l'élément qui s'y trouve : c'est donc 4.

    PSEUDO-CODE PYTHON

    Pour les algorithmes de cette section, on utilisera du pseudo-code Python françisé mais en respectant globalement la façon de faire de Python (sans s'embêter avec les : en fin de déclaration par exemple).

    • L'appartenance à un bloc SI, POUR, TANT QUE ect... est signalée par
      • L'indentation en pseudo-Python
      • Le fait de ne pas avoir rencontré Fin POUR, Fin SI ect... en pseudo-langage classique.
    • L'affectation est signalée par
      • Le symbole = en pseudo-Python
      • La flèche ← en pseudo-langage classique.
    • RENVOYER x plutôt que return x
    • NON plutôt que not
    • POUR i variant de 0 à 10 plutôt que for i in range(11):
    • POUR chaque valeur v du tableau t plutôt que for v in t:
    • TANT QUE v est différent de a plutôt que while v != a:
    • SI-SINON SI-SINON qui remplaceront les if-elif-else

    Sur votre copie papier, on acceptera que vous utilisiez les alias courts.

    13° Deux questions.

    Question 13.a

    Réaliser l'algorithme premier() qui correspond au fait de récupérer la valeur de la tête directement, plutôt que de devoir utiliser et taper deux primitives.

    ALGORITHME premier(lst:Liste) → Elément

    ENTREE : lst, une Liste NON VIDE

    SORTIE : l'Elément contenu dans la tête

    Question 13.b

    Si on suppose que les primitives de base contenu() et accesTete() devraient être implémentables par des fonctions à coût constant, que pouvez-vous dire du coût supposé de la fonction premier() une fois implémentée ?

    ...CORRECTION...

    ALGORITHME de premier(lst:Liste) → Elément

    ENTREE : lst, une Liste NON VIDE

    SORTIE : l'Elément contenu dans la tête

    RENVOYER contenu(accesTete(lst))

    Si accesTete() est supposée à cout constant, si contenu() est supposée à cout constant, il ne faudra jamais que deux actions basiques pour réaliser cette tâche. On peut donc supposer qu'on parviendra à implémenter premier() à coût constant.

    14° Quelle expression doit-on évaluer pour savoir si une Liste lst n'est pas VIDE en utilisant le pseudo langage et les primitives disponibles ?

    Votre expression devra être évaluée à VRAI si la liste n'est pas vide et à FAUX si la liste est vide.

    ...CORRECTION...

    La question "La liste est-elle non vide ?" est l'inverse booléen de la primitive estListeVide().

    Il suffit donc d'utiliser ceci :

    NON estListeVide(lst)

    15° Deux questions.

    Question 15.a

    Réaliser l'algorithme longueur() qui correspond au fait de récupérer le nombre d'éléments dans la Liste. Il faudra utiliser une version itérative utilisant un TANT QUE.

    ALGORITHME longueur(lst:Liste) → Entier Naturel

    ENTREE : lst, une Liste (attention, elle pourrait être vide, aucune précondition autre que le type)

    SORTIE : le nombre d'éléments contenus dans lst

    POSTCONDITION :lst est inchangé

    On rappelle qu'on a décidé de travailler sur un type Liste immuable.

    Question 15.b

    Si on suppose que les 7 primitives de base devraient être implémentables par des fonctions à coût constant, que pouvez-vous dire du coût supposé de la fonction longueur() une fois implémentée ?

    Question 15.c

    Après avoir regardé ma correction, un élève pense que la liste est modifiée. Expliquez lui pourquoi il se trompe.

    ...CORRECTION...

    ALGORITHME longueur(lst:Liste) → Entier Naturel

    ENTREE : lst, une Liste (qui peut être vide)

    SORTIE : le nombre d'éléments contenus dans lst

    • nb = 0
    • TANT QUE NON estListeVide(lst)
    • nb = nb + 1
    • lst = supprimerTete(lst)
    • RENVOYER nb

    Analyse asymptotique de la boucle :

    Le traitement d'une Place se fait à coût constant car chaque tour de boucle ne comporte que des opérations qu'on estime à coût constant.

    • le test initial avec un appel à estListeVide() (coût constant),
    • une incrémentation simple (à coût constant),
    • une affectation avec appel à supprimerTete() (coût constant).

    Comme il faut autant de tours de boucle que de Places présentes, on obtient un coût linéaire et une complexité θ(n) puisqu'on devra réellement vérifier toutes les Places.

    Analyse asymptotique de l'algorithme :

    • On a une première affectation simple(coût constant)
    • Une boucle à coût linéaire
    • On renvoie juste une réponse déjà calculée (coût constant)

    On en déduit que le coût futur de cette fonction devrait être linéaire dans ces conditions.

    Pour la question C, il suffit de signaler que lorsqu'on écrir lst = supprimerTete(lst), cela veut dire qu'on stocke la nouvelle liste supprimerTete(lst) dans une nouvelle variable locale qui porte le même nom mais désigne bien une autre donnée.

    16° Réaliser l'algorithme longueur() en utilisant cette fois une version récursive.

    Pour cela, demandez-vous

    • Pour quel cas de base un appel de la fonction pourra répondre seule ?
    • Que devra faire la fonction qui s'occupe d'une Place une fois qu'elle aura reçu la réponse du successeur ?

    ALGORITHME longueur(lst:Liste) → Entier Naturel

    ENTREE : lst, une Liste (attention, elle pourrait être vide, aucune précondition autre que le type)

    SORTIE : le nombre d'éléments contenus dans lst

    On rappelle qu'on a décidé de travailler sur un type Liste immuable.

    ...CORRECTION...

    Le principe général est de considèrer qu'une Liste dit que sa longueur est 0 si elle est vide et que sinon, la fonction répondra 1 + la réponse de la queue de la liste.

    ALGORITHME longueur(lst:Liste) → Entier Naturel

    ENTREE : lst, une Liste (qui peut être vide)

    SORTIE : le nombre d'éléments contenus dans lst

    • SI estListeVide(lst)
    • RENVOYER 0
    • SINON
    • RENVOYER 1 + longueur(supprimerTete(lst))

    Dans la suite des exercices, on considère donc qu'on peut désormais utiliser ces deux fonctions.

    • premier(lst:Liste NON VIDE) → Elément
    • longueur(lst:Liste) → Entier Naturel

    17° Trouver l'algorithme de inverser(), qui doit renvoyer une nouvelle Liste où tous les éléments sont inversés : le dernier est le premier, l'avant-dernier est le deuxième...

    ALGORITHME inverser(lst:Liste) → Liste

    DESCRIPTION : renvoie une nouvelle Liste où l'ordre des éléments est inversé par rapport à lst.

    POSTCONDITION : la Liste renvoyée à la même longueur que lst et lst est inchangée.

    Si on envoie (5, 15, 100, 1), on doit recevoir (1, 100, 15, 5).

    Vous pouvez utiliser les 7 opérations primitives ainsi que longueur(), et premier().

    Evaluer ensuite son coût supposé après implémentation.

    ...CORRECTION...

    ALGORITHME inverser(lst:Liste) → Liste

    ENTREE : lst, une Liste (qui peut être vide)

    SORTIE : une nouvelle Liste en ordre inverse

    • lst_inverse = nouvelleListeVide()
    • TANT QUE NON estListeVide(lst)
    • element = premier(lst)
    • lst = supprimerTete(lst)
    • lst_inverse = insererTete(lst_inverse, element)
    • RENVOYER lst_inverse

    Une version avec une boucle bornée POUR est bien entendu possible : il suffit de lancer un appel à longueur() pour connaître le nombre de tours de boucle à faire.

    Estimation du coût d'une future implémentation

    Si on considère que la future implémentation permette d'avoir un coût constant pour nouvelleListeVide() estListeVide() supprimerTete() insererTete(), on aura 4 opérations à coût constant par tour de boucle. Un tour de boucle est donc à coût constant.

    On va réaliser un nombre de tour de boucle qui dépend de la longueur de la liste initiale. Le coût est donc linéaire et la complexite en θ(n).

    18° Le but de cette question est de créer les opérateurs inserer() et supprimer() avec gestion de l'indice pour savoir où réaliser l'action. Nous pourrons ainsi agir sur n'importe quel indice et pas uniquement la tête.

    Vous pouvez utiliser les 7 opérations primitives ainsi que longueur(), premier() et inverser().

    • ALGORITHME inserer(lst:Liste, elt:Elément, i:Entier Naturel) → Liste

      • DESCRIPTION : Renvoie une nouvelle Liste comportant le nouvel élément à la position indiquée par l'indice fourni. Certains emplacements sont donc décalés d'une position par rapport à la Liste initiale.

      • Pour insérer comme nouvelle Tête, on doit donc envoyer i valant 0.
      • Pour insérer juste avant la fin, on doit envoyer longueur -1. Cela doit avoir comme conséquence de pousser la fin en position longueur (attention, longueur étant le nombre d'éléments de l'ancienne liste)
      • Pour insérer comme nouvelle fin, on doit envoyer longueur qui correspond à un indice "vide" pour la liste de départ.

      PRECONDITIONS : l'indice i caractérise une indice valide pour l'insertion et elt doit avoir un type compatible avec le reste des Eléments si la Liste est homogène.

      POSTCONDITION  : la Liste renvoyée possède un emplacement en plus mais lst est inchangée.

      Exemples d'utilisation

      lstA = nouvelleListeVide()
      lstB = inserer(lstA, 5, 0)
      lstB contient alors (5, () ) qu'on pourrait noter simplement (5, ).

      lstC = inserer(lstB, 15, 0)
      lstC contient alors (15, (5, () )) qu'on pourrait noter (15, 5, ).

      lstD = inserer(lstC, 25, 1)
      lstD contient alors (15, (25, (5, () ))) qu'on pourrait noter (15, 25, 5, ).

      lstE = inserer(lstD, 50, 3)
      lstE contient alors (15, (25, (5, (50, () )))) qu'on pourrait noter (15, 25, 5, 50, ).

    • ALGORITHME supprimer(lst:Liste, i:Entier Naturel) → Liste

      • DESCRIPTION : Renvoie une nouvelle Liste dans laquelle on a supprimé l'ancien emplacement ayant cet indice. Certains emplacements sont donc décalés d'une position par rapport à la Liste initiale.

      • Pour supprimer l'élément de Tête, on doit donc envoyer i valant 0.
      • Pour supprimer l'élément de fin, on doit envoyer longueur -1.

      PRECONDITION : l'indice i est un indice valide, la Liste reçue doit être NON VIDE.

      POSTCONDITION : la Liste renvoyée possède un emplacement en moins mais lst est inchangée.

      Exemple d'utilisation

      Partons de lstE contenant (15, (25, (5, (50, () )))) ou simplement (15, 25, 5, 50, ).
      lstF = supprimer(lstE, 1)
      lstF contient alors (15, (5, (50, () ))) ou simplement (15, 5, 50, ).

      lstG = supprimer(lstF, 2)
      lstG contient alors (15, (5, () )) ou simplement (15, 5, ).

    Estimer le coût de ces fonctions dans une implémentation future.

    ...CORRECTION...

    ALGORITHME inserer(lst:Liste, elt:Elément, i:Entier Naturel) → Liste

    ENTREES :

    • lst, une Liste (qui peut être vide),
    • elt, l'Elément à insérer, homogène avec les autres si la Liste est homogène.
    • i, un Entier Naturel correspondant à un indice valide d'insertion, c'est à dire entre 0 et longueur, longueur correspondant à placer l'élément derrière toutes les autres.

    SORTIE : une nouvelle Liste pour lequel l'élément occupe la Place d'indice i.

    • /// Etape 1 : on supprime et mémorise les i premières têtes
    • memoire = nouvelleListeVide()
    • POUR k variant de 0 à (i - 1) . . . . . . . . . . on fait la boucle i fois
    • element = premier(lst) . . . . . . . . on lit la 1er valeur de lst
    • lst = supprimerTete(lst) . . . . . . . . . . on supprime la tête
    • memoire = insererTete(memoire, element) . . . . on rajoute en mémoire
    • /// Etape 2 : on insère le nouvel élément
    • lst = insererTete(lst, elt)
    • /// Etape 3 : on replace les i éléments supprimés
    • POUR k variant de 0 à (i - 1) . . . . . . . . on fait la boucle i fois
    • element = premier(memoire) . . . . . . on lit la 1er valeur en mémoire
    • memoire = supprimerTete(memoire). . . . . on supprime la tête
    • lst = insererTete(lst, element) . . . . . . . on rajoute dans lst
    • RENVOYER lst

    Notez bien qu'en raison de la nature immuable de notre type, ce n'est pas la vraie Liste reçue dans le paramètre lst qui est modifiée.

    Estimation du futur coût

    Toutes les fonctions utilisées ici devraient être à cout constant.

    On effectue deux boucles en réalisant i tours à chaque fois. Pour la recherche de coût, on peut considérer qu'elles auront presque toutes la même durée d'exécution une fois implémentées.

    On a (1 + i*3 + 1 + i*3) utilisations de primitives, soit 2 + 6*i "actions élémentaires".

    La complexité est donc θ(i) et comme l'indice i est nécessairement (voir précondition) inférieur à n, on pourra écrire 𝓞(n).

    On obtient donc un coût linéaire (mais on ne va pas nécessairement jusqu'au bout, cela dépend de l'indice).

    Insérer en tête serait toujours à coût constant.

    Insérer en fin serait toujours à coût exactement linéaire.

    Pour l'algorithme suivant, il n'y a que l'étape 2 qui change : on supprime une tête en plus plutôt que d'en insérer une nouvelle.

    ALGORITHME supprimer(lst:Liste, i:Entier Naturel) → Liste

    ENTREES :

    • lst, une Liste NON VIDE
    • i, un Entier Naturel correspondant à un indice valide, c'est à dire entre 0 et longueur-1.

    SORTIE : une nouvelle Liste pour lequel l'élément occupant la Place d'indice i a été supprimé. Les autres éléments ont donc été décalés.

    • /// Etape 1 : on supprime et mémorise i têtes
    • memoire = nouvelleListeVide()
    • POUR k variant de 0 à (i - 1)
    • element = premier(lst)
    • lst = supprimerTete(lst)
    • memoire = insererTete(memoire, element)
    • /// Etape 2 : on supprime l'élément d'indice i
    • lst = supprimerTete(lst)
    • /// Etape 3 : on replace les i éléments supprimés
    • POUR k variant de 0 à (i - 1)
    • element = premier(memoire)
    • memoire = supprimerTete(memoire)
    • lst = insererTete(lst, element)
    • RENVOYER lst

    Estimation du coût d'une future implémentation

    Raisonnement similaire au cas précédent : le coût devrait être linéaire.

    19° Réaliser un algorithme ieme() qui ramène l'élément placé en position i d'une Liste NON VIDE. L'autre précondition est que l'indice fourni soit valide pour cette liste.

    ALGORITHME ieme(lst:Liste NON VIDE, i:Entier Naturel INDICE VALIDE) -> Element

    ...CORRECTION...

    Le principe est de supprimer i têtes.

    Pas la peine de stocker, la liste est IMMUABLE : on ne coupe donc pas vraiment la liste de base.

    Il suffit ensuite de renvoyer le premier élément de la liste obtenue.

    ALGORITHME ieme(lst:Liste, i:Entier Naturel) → Element

    ENTREES :

    • lst, une Liste NON VIDE
    • i, un Entier Naturel correspondant à un indice valide, c'est à dire entre 0 et longueur-1.

    SORTIE : l'Element en position i.

    • /// Etape 1 : on supprime i têtes
    • POUR k variant de 0 à (i - 1)
    • lst = supprimerTete(lst)
    • /// Etape 2 : on renvoie le premier
    • RENVOYER premier(lst)

    20° Réaliser un algorithme recherche() qui renvoie l'indice du premier élément ayant la bonne valeur présent dans une Liste NON VIDE. Si l'élément n'est pas présent, la fonction renvoie -1.

    ALGORITHME recherche(lst:Liste, x:Elément) -> Entier

    ...CORRECTION...

    Comme vous pouvez le remarquer, avec quelques opérations primitives, on peut parvenir à réaliser des fonctions beaucoup plus complexes que les opérations primitives.

    CONCLUSION - Savoir créer les primitives manquantes

    A partir de primitives restreintes de la version Tête-Queue, vous devez être capables de recréer les suivantes et donc connaître par coeur les façons de procéder :

    • Une primitive premier() qui n'est qu'un raccourci pour contenu(acces()).
    • Une primitive longueur() dont le principe interne est d'avoir un compteur pour le nombre de tête et de les supprimer une par une TANT QUE la queue obtenue n'est pas vide.
    • Une primitive insérer() qui permet d'insérer en position i, et dont le principe interne est
      1. De supprimer et mémoriser i éléments de tête dans une nouvelle liste-mémoire
      2. D'insérer la nouvelle tête
      3. De replacer dans la liste les têtes mémorisées dans la liste-mémoire.
    • Une primitive supprimer() qui permet de supprimer l'élément en position i, et dont le principe interne est
      1. De supprimer et mémoriser i éléments de tête dans une nouvelle liste-mémoire
      2. De supprimer la tête actuelle (la numéro i)
      3. De replacer dans la liste les têtes mémorisées dans la liste-mémoire
    • Une primitive acces() qui permet de lire l'élément en position i, et dont il existe deux méthodes.

      • Première version qui fonctionne qui profite de l'immuabilité et dont le principe est :

      1. De supprimer (sans mémoriser) i éléments de tête
      2. De lire l'élément en tête de la nouvelle liste

      Deuxième version qui fonctionne qui utilise successeur() et contenu() et dont le principe est :

      1. D'accéder à la Place de tête
      2. D'utiliser i fois successeur()
      3. De lire le contenu() de la Place obtenue

    4 - Implémentation

    ⇩ ⇧ ⤊

    4.1 Vocabulaire retenu sur ce site
    • un algorithme manipule des types abstraits de données (c'est la phase de conception théorique)
    • le passage de l'idée abstraite à sa réalisation concrète en machine se nomme l'implémentation.
    • un programme manipule des types (implémentés) (c'est la phase de réalisation pratique).

    ALGORITHME    ⇒ Implémentation ⇒ PROGRAMME           

    TYPE ABSTRAIT ⇒ Implémentation ⇒  TYPE (implémenté)  

    • Type abstrait de données  une idée abstraite mais précise de la façon de traiter les données. On trouve souvent l'acronyme TAD.
    • Type : l'implémentation en machine d'une donnée. Cela regroupe donc les types simples et les types construits.
    • Type simple : l'implémentation en machine d'une donnée unique, comme un entier, un flottant...
    • Type structuré, type construit : l'implémentation en machine d'une donnée se comportant comme un conteneur : elle contient d'autres données.

      • D'où le nom de la fonction native Python type().

    Une structure de données est le nom qu'on donne à l'ensemble d'un type associé aux fonctions qu'on peut appliquer aux données stockées.

    4.2 Implémentation de certains types abstraits en Python

    Selon les langages, certains types abstraits sont déjà implémentés efficacement en pratique. Le langage de programmation possède alors déjà des types natifs permettant de les utiliser.

    Par exemple, en Python :

    • On gère le type abstrait booléen en utilisant le type natif bool.
    • On gère le type abstrait entier en utilisant le type natif int.
    • On gère le type abstrait nombre à virgule en utilisant le type natif float.
      Donc tous les nombres réels ne seront pas réellement tous bien enregistrés.
    • On gère le type abstrait tableau statique (array en anglais) en utilisant le type natif ... list.
    • On gère le type abstrait tableau dynamique (vector en anglais) en utilisant le type natif list.
    • On gère le type abstrait tableau associatif en utilisant le type natif dict.
    • On gère le type abstrait p-uplet nommé en utilisant le type natif dict.
    • On gère le type abstrait p-uplet en utilisant le type natif tuple.
    • On gère le type abstrait ensemble en utilisant le type natif set.

    Comme vous le voyez, pas d'implémentation native de Listes récursives en Python. Nous allons devoir les faire à la main dans les prochaines activités.

    🏠 TRAVAIL PERSONNEL° Réaliser les exercices supplémentaires Maison (voir le lien) en rédigeant correctement vos réponses.

    Exercices

    5 - FAQ

    ⇩ ⇧ ⤊

    Rien pour le moment

    -

    Activité publiée le 21 09 2020
    Dernière modification : 24 09 2022
    Auteur : ows. h.


    ⏪

    ⏫

    ⏩