11 - type abstrait de données Liste
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érentes structures de données.
TYPE ABSTRAIT ⇒ Implémentation ⇒ STRUCTURE DE DONNEES
Conclusion de cette présentation
Le but de toutes les activités qui suivent est donc de combler le vide qui existe entre :
- Le type abstrait le plus généraliste qui soit : l'ensemble mathématique
- Le type construit le plus basique qui soit : le tableau statique dont l'implémentation avait été présenté en 1er.
Documents de cours : open document ou pdf
1 - La Liste en tant que type abstrait de données
Nous allons voir ici qu'on peut travailler sur des données organisées de façon purement théorique, répondant à des contraintes théoriques, sans se soucier de la façon dont elles vont être concrétement programmées en interne par votre programme.
1) Définition du type abstrait Liste (1/2) : leurs propriétés générales
1a) Propriétes générales d'organisation
Le type abstrait Liste a les propriétés suivantes :
- C'est une structure linéaire composée d'une séquence finie et ordonnée d'éléments stockés à une certaine place.
- On doit pouvoir insérer et supprimer des informations
- On doit pouvoir accéder directement à certaines places (au moins la première place).
- On doit pouvoir lire un élément en connaissant la place qu'il occupe
- On doit pouvoir trouver le successeur unique de chaque place.
Finalement, vous pouvez appréhender le type abstrait Liste en faisant une analogie avec des dossiers suspendus :
1b) 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).
- Si tous les éléments stockés sont de même type, on dit que la Liste est homogène, sinon elle est inhomogène.
1c) 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
1d) 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écisement 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êmes questions : 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êmes questions : 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).
2) Représentations du contenu d'une Liste
Comment représenter une telle Liste ?
2a) Représentation Tête - Queue
Une tête menant à une queue, voilà ce qui est vraiment fondamental dans une Liste.
5 → 8 → 2 → 3
Le 5 étant la tête de la Liste qu'on nommera lst1, on peut noter sa queue lst2.
5 → lst2
On pourrait alors noter ceci : lst1 = (5, lst2).
Et que contient lst2 : une tête 8 et une queue lst3...
8 → lst3
lst2 = (8, lst3)
On obtient alors l'enchaînement suivant (si vous avez déjà fait la partie sur la récursivité, cela devrait vous rappeler l'empilement) :
- lst1 = (5, lst2)
- lst2 = (8, lst3)
- lst3 = (2, lst4)
- lst4 = (3, lst5)
- lst5 = ()
2b) Définition
On remarque donc qu'une Liste peut être
- soit un couple (tête, queue),
- soit une liste vide.
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.
2c) Représentation en séquence ordonnée
On dispose donc de pluqsieurs 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 des accolades : {5, {8, {2, {3}}}} ou plus facilement par {5, 8, 2, 3}
Attention, avec cette notation, à ne pas confondre avec les vrais ensembles mathématiques où un élément ne peut être présent qu'une fois.
Ou avec chevrons : <5, <8, <2, <3>>>> ou plus facilement par <5, 8, 2, 3>
Il faut juste choisir, le noter clairement.
Ici, nous utiliserons des parenthèses par exemple.
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 interne.
Lorsqu'on décide de dire qu'on va écrire les listes en utilisant les parenthèses ou les crochets ou les accolades, cela ne veut pas dire qu'à l'interne ce sont des n-uplets, des tableaux ou des dictionnaires.
06° Donner deux représentations de la liste suivante (en mode (tete, queue)) puis 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 (en mode (tete, queue)) puis 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).
3) Signature et syntaxe autorisée
3a) Définition de signature
Une signature correspond aux attendus sur les types des arguments d'entrée et sur le type de la réponse renvoyée pour les opérateurs ou les fonctions.
Exemple 1 : signature de la fonction 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
Certaines existent, d'autres non.
Intérêt :
- Il s'agit de contraintes liées uniquement au type, pas sur le contenu réel envoyé.
- 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 lui transmettez est "valide" ou non. L'interpréteur cherche à trouver un motif correspondant à une signature connue.
3b) La signature est inexistante : TypeError
Utiliser une signature inexistante provoque une erreur de TYPE.
>>> "Pom !" * 4
'Pom ! Pom ! Pom ! Pom !'
>>> "Pom !" * 4.0
TypeError: can't multiply sequence by non-int of type 'float'
Les signatures sont donc très importantes et permettent notamment de vérifier la correction des programmes.
3c) La signature existe :
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 :
- 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.
- Si elle existe, donner la signature fournie par cette syntaxe (exemple int + int -> int )
- 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
- L'association int // int est acceptée par Python
- La signature est int // int -> int
- 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
- L'association int % int est acceptée par Python
- La signature est int % int -> int
- 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]
- L'association list + list est acceptée par Python
- La signature est list + list -> list
- 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'
- 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]
- L'association list * int ou int * list est acceptée par Python
- La signature est int * list -> list
- 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.
4) Définition du type abstrait Liste (2/2) : les signatures disponibles
4a) 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.
4b) Vocabulaire : opérations primitives
Trois idées caractérisent ces fonctions particulières :
- Les opérations primitives font partie des fonctions d'interface disponibles pour ce type abstrait de données, mais toutes les fonctions d'interface ne sont pas des opérations primitives.
- Les opérations primitives sont les briques d'actions fondamentales permettant d'agir sur ce type de données.
- Les futures fonctions implémentant ces opérations primitives devront avoir le coût le plus faible possible (se rapprochant d'un coût constant si possible).
4c) Signatures des opérations primitives du type abstrait Liste
Pour le type abstrait Liste, voici les signatures attendues, tant pour Liste qui utilisent le type abstrait Place et Elément :
Dans l'idée des dossiers suspendus :
- La Liste est le meuble de rangement.
- Les Places sont les dossiers suspendus ou les cases, ou un moyen de les identifier clairement
- Les Eléments sont les choses qu'on range dans les Places.
- a() → Liste
- b(Liste) → Entier Naturel
- c(Liste) → Booléen
- d(Liste, Elément, Entier Naturel) → Liste
- e(Liste, Entier Naturel) → Liste
- f(Liste, Entier Naturel) → Place
- g(Place) → Place
- h(Place) → Elément
On voit que pour définir Liste, il faut au préalable avoir défini les types suivants :
- Booléen,
- Entier Naturel,
- Elément (quels sont les types autorisés en tant qu'élements de la liste ?),
- Place : un conteneur permettant de stocker au moins l'élément.
Comme vous pouvez le voir, la connaissance des signatures donnent des informations sur la SYNTAXE autorisée mais pas vraiment sur la SEMANTIQUE de ces demandes...
5) Définition compléte du type abstrait Liste
Nous avons vu que :
- Les signatures donnent des informations sur la SYNTAXE disponible.
- Les propriétés générales donnent des informations sur la signification des actions disponibles.
(1) + (2) nous permet alors de donner une SEMANTIQUE à la SYNTAXE.
On peut donc maintenant donner la SPECIFICATION des fonctions a() b() c() d() e() f() g() h()
- un NOM explicite,
- la SIGNATURE,
- la DESCRIPTION textuelle qui contient, de fait, une bonne partie des POSTCONDITIONS.
- les PRECONDITIONS éventuelles et
- D'éventuelles POSTCONDITIONS SUPPLEMENTAIRES, souvent plus formelles que celles qui sont simplement écrite dans la DESCRIPTION textuelle
- listeVide() → Liste
- longueur(lst:Liste) → Entier Naturel
- estListeVide(lst:Liste) → Booléen
- inserer(lst:Liste, elt:Elément, i:Entier Naturel) → Liste
- 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.
- supprimer(lst:Liste, i:Entier Naturel) → Liste
- 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.
- acces(lst:Liste, i:Entier Naturel) → Place
- contenu(plc:Place) → Elément
- successeur(plc:Place) → Place
DESCRIPTION : Renvoie une nouvelle Liste qui est vide initialement.
DESCRIPTION : Renvoie le nombre d'éléments stockés dans la liste.
DESCRIPTION : Renvoie VRAI si la liste lst fournie est vide, FAUX sinon.
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.
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 supplémentaire : la Liste renvoyée possède un emplacement en plus mais lst est inchangée.
Exemples d'utilisation
lstA = listeVide()
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, ).
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.
PRECONDITION : l'indice i est un indice valide, la Liste reçue ne peut donc pas être vide.
POSTCONDITION supplémentaire : 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, ).
DESCRIPTION : Renvoie la Place correspondant à l'indice i fourni .
PRECONDITION : l'indice i caractérise un indice valide, la Liste reçue ne peut donc pas être vide.
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() et on est donc en mesure de prévoir l'indice de cette place.
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.
DESCRIPTION : Renvoie la Place située à la suite de plc.
PRECONDITION : plc caractérise une Place valide ayant bien un successeur. Il ne peut donc pas s'agir de la dernière place.
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. Le tout est que votre propre version possède bien des opérations primitives du type Liste et que, dans votre version, le type Place soit clairement défini. 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 primitives.
- listeVide() → Liste
- longueur(lst:Liste) → Entier Naturel
- estListeVide(lst:Liste) → Booléen
- inserer(lst:Liste, elt:Elément, i:Entier Naturel) → Liste
- supprimer(lst:Liste, i:Entier Naturel) → Liste
- acces(lst:Liste, i:Entier Naturel) → Place
- contenu(plc:Place) → Elément
- successeur(plc:Place) → 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 | |
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 | |
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 | |
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 | |
- Expliquer que le contenu de cette Liste soit (8, 6, 4) en détaillant le fonctionnement en 3 étapes.
- Fournir ensuite les instructions qui permettraient de passer de la Liste lstA contenant (8, 6, 4) à une Liste lstB (10, 6, 4)
...CORRECTION...
1 | |
Python exécute cette première fonction et on récupère donc une première liste contenant (4, ) en position 0.
1 | |
1 | |
Python doit maintenant générer, à partir de (4, ), une nouvelle liste où 6 est en position de tête (indice 0).
1 | |
Il exécute et on récupère donc une liste contenant (6, 4) en position 0.
1 | |
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 | |
6) Muable ou immuable
Vous devez impérativement comprendre que la version proposée ici est immuable puisqu'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.
On aurait également pu créer des fonctions d'interface pour un type abstrait muable.
Du coup, voici la signature des fonctions qui diffèrent de la version immuable :
- inserer(lst:Liste, elt:Elément, i:Entier Naturel) → Vide
- supprimer(lst:Liste, i:Entier Naturel) → Vide
- supprimer(lst:Liste, i:Entier Naturel) → Element
DESCRIPTION : Ne renvoie rien mais modifie la Liste directement.
PRECONDITIONS : l'indice i caractérise un indice valide.
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.
PRECONDITION : l'indice i caractérise un indice valide.
POSTCONDITION : la Liste est modifiée directement et on revient 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) ?
- lstA = inserer(lstA, 1, 0)
- lstA = inserer(lstA, 0, 1)
- inserer(lstA, 1, 0)
- 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écisement ce qu'est une Liste, il va falloir définir plus précisement comment on peut localiser une Place.
Il existe deux grandes familles de Listes, tout comme il existe deux grandes catégories de fonctions :
- les fonctions itératives
- les fonctions récursives
De la même façon, nous allons voir qu'il existe :
- Les Listes itératives
- Les Listes récursives
2.1 - Liste itérative
Idée sous-jacente : l'armoire avec des casiers fixes.
- La Liste est l'armoire.
- Les Places sont les casiers sur lequel le numéro est inscrit
- Les Eléments sont les choses qu'on place dans le casier
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 une Place à chaque indice. 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.
Avantage : Lecture ou modification d'un élément unique
L'avantage est qu'on accède directement à chaque Place et donc chaque Element immédiatement.
Désavantage : insertion ou permutation
Il est assez difficile d'effectuer des permutations de valeurs ou d'insérer une nouvelle donnée. Voici un exemple où on tente de produite (D, A, B, C) à partir de (A, B, C, D).
Les Places sont fixes mais on peut modifier l'associaton Place-Elément. Dans ce cas, il faudra permuter les Elements des Places plutôt que déplacer les Places.
On se rend assez facilement compte que le nombre de déplacements est linéaire par rapport au nombre d'éléments dans la Liste.
Cela correspond bien à l'idée de ce qu'est concrètement un tableau statique : un ensemble de zones-mémoires dont l'adresse est calculable en fonction de la zone mémoire de tête et la taille de chaque case en octets.
adresse(i) = adresse(0) + i * taille_case
Exemple : la case 0 est stockée en 4000 et chaque case possède une capacité de 8 octets.
- La case 0 est en 4000.
- La case 1 est en 4008.
- La case 2 est en 4016.
- La case 3 est en 4024.
- ...
2.3 Liste récursive
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
On se rend assez facilement compte que le nombre d'opérations nécessaire à la lecture de toute la Liste est linéaire par rapport au nombre d'éléments dans la Liste.
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 ?
Attention, plusieurs choses à comprendre :
- Le type list-Python est plutôt une implémentation muable d'une Liste Itérative.
- 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]
3 - Liste récursive basique : (Tête, Queue)
3.1 La Liste Récursive (Tête, Queue)
Nous allons donc travailler avec une version limitée de ce type de liste : on peut accèder, insérer ou supprimer uniquement la Tête, puisque c'est la seule information dont on dispose sur notre Liste depuis l'intérieur de la Liste.
Dans le cadre de cette activité, on travaillera avec
- une Liste immuable (mais on aurait pu gérer le cas muable)
- pour laquelle la seule Place dont on connaisse la référence à coup sûr est la Tête et donc
- dans laquelle les opérations primitives d'insertion, de suppression et d'accès agissent uniquement sur la Tête.
Il s'agit donc d'une Liste Récursive car pour accèder à la Place 2, la Liste doit faire appel à la Place 0 (la Tête) qui fait appel à la Place 1, qui fait elle-même appel à la Place 2.
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 (sans entendu "il semble logigue 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 Tête puisque c'est la seule Place 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 sur papier.
- listeVide() → Liste
longueur()- estListeVide(lst:Liste) → Booléen
estLVd() inserer()
insererTete(lst:Liste, elt:Elément) → Liste
insT()
cons()supprimer()
supprimerTete(lst:Liste) → Liste
supT()
cdr()
recupererQueue()acces()
accesTete(lst:Liste) → Place
tete()- contenu(plc:Place) → Elément
- successeur(plc:Place) → Place
DESCRIPTION : Renvoie une nouvelle Liste qui est vide initialement.
Exemple d'utilisation
lstA = listeVide()
Le contenu de lstA est alors () par exemple.
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.
DESCRIPTION : Renvoie VRAI si la liste lst fournie est vide, FAUX sinon.
Exemple d'utilisation
lstA = listeVide()
estListeVide(lstA) renvoie alors VRAI.
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 supplémentaire : la Liste renvoyée 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 _cons_truct).
Exemple d'utilisation
lstA = listeVide()
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 :
DESCRIPTION : Renvoie une copie de lst privée de sa tête. Elle renvoie donc la queue de lst.
PRECONDITION : lst ne doit pas être 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)
lstC = supprimerTete(lstB)
lstC contiendra alors (15, (5, ())) ou (15, 5).
lstB contient toujours (25, (15, (5, ())))
DESCRIPTION : Renvoie la Place de la Tête.
PRECONDITION : La Liste n'est pas vide.
Par contre, contenu() et successeur() sont inchangées : la Liste ne peut pas accèder à une autre Place que la tête initialement, pas contre, connaissant la Tête, on va pouvoir trouver d'autres Places progressivement. Attention, dans l'esprit de ce type abstrait, la connaissance d'une Place doit venir de l'utilisation de acces() et on est donc en mesure de prévoir l'indice de cette place.
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.
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))
DESCRIPTION : Renvoie la Place située à la suite de plc.
PRECONDITION : plc caractérise une Place valide ayant bien un successeur. Il ne peut donc pas s'agir de la dernière place.
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 avons 7 opérations primitives :
- listeVide() → Liste
- estListeVide(lst:Liste) → Booléen
- insererTete(lst:Liste, elt:Elément) → Liste
- supprimerTete(lst:Liste) → Liste
- accesTete(lst:Liste) → Place
- contenu(plc:Place) → Elément
- successeur(plc:Place) → Place
La suite ?
Vous allez voir maintenant :
- qu'on peut manipuler les idées : nos données abstraites vont être traitées avec nos primitives abstraites, sans toucher un clavier
- qu'on peut recréer les autres primitives avec ces 7 primitives
- qu'on peut donc bien nommer ce type abstrait limité une Liste
- mais qu'on va voir rapidement, et sans programmation réelle, que certaines actions seront faciles et d'autres plus compliquées à gérer une fois qu'on passera réellement à 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 | |
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 : par exemple).
- on garde l'indentation comme signe d'appartenance à un bloc plutôt que de devoir noter Fin POUR, Fin SI...
- 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 != a plutôt que while v != a:
- Idem pour le SI-SINON SI-SINON qui remplacera le if-elif-else
on garde le symbole = de l'affectation Python plutôt que de passer par la flèche ←
Sur votre copie papier, on acceptera que vous utilisiez les alias plus courts (fournis en 3.2) en pour les opérations primitives.
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...
Une entrée "LISTE PAS VIDE" doit donner VRAI sur cette question.
Une entrée "LISTE VIDE" doit donner FAUX sur cette question.
On voit donc que 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 a accès à ces deux nouvelles fonctions.
- premier(lst:Liste) → Elément
- longueur(lst:Liste) → Entier Naturel
Rajout d'opérations primitives
premier(lst:Liste) → Elément
PRECONDITION : lst est une Liste non vide.
POSTCONDITION : Renvoie l'Elément stocké dans la Place de tête.
Exemple d'utilisation
On considère que lstB contient (25, (15, (5, ())))
recup = premier(lstB)
recup contient alors 25. La liste lstB n'a pas été modifiée.
longueur(lst:Liste) → Entier Naturel
DESCRIPTION : Renvoie le nombre d'éléments stockés dans la liste.
Exemple d'utilisation
On considère que lstB contient (25, (15, (5, ()))) ou (25, 15, 5) en représentation simple
nb = longueur(lstB)
On obtient alors la valeur 3 dans nb.
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 supplémentaire : 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 = listeVide()
- 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 listeVide() 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 ici est maintenant de créer les opérateurs manquants : inserer() et supprimer() pour que cela permette d'agir sur n'importe quel indice et pas uniquement la Tête : insererTete() et supprimerTete() correspondent à l'action sur l'indice 0 finalement.
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
- 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.
- ALGORITHME supprimer(lst:Liste, i:Entier Naturel) → Liste
- 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.
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.
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 supplémentaire : la Liste renvoyée possède un emplacement en plus mais lst est inchangée.
Exemples d'utilisation
lstA = listeVide()
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, ).
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.
PRECONDITION : l'indice i est un indice valide, la Liste reçue ne peut donc pas être vide.
POSTCONDITION supplémentaire : 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émoire les i premières têtes
- memoire = listeVide()
- 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 éléments que nous avions enlevé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.
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 crée une liste pour stocker les éléments devant celui à insérer
- memoire = listeVide()
- 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 éléments que nous avions enlevé
- 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, i:Entier Naturel) -> Element
...CORRECTION...
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.
Avec les opérations primitives de la Liste Récursive, on peut finalement agir comme on le veut, partout dans la Liste et retrouver toutes les primitives du type abstrait Liste. Par contre, cela aura un coût, nous en parlerons justement en TP.
CONCLUSION IMPORTANTE 1 : Deux idées de la Liste
En théorie, une Liste Itérative et une Liste Récursive sont similaires puisqu'on peut retrouver toutes les primitives du type Liste à partir des primitives de ces types particuliers.
Néanmoins, similaire en théorie ne veut pas dire similaire en action.
Listes itératives
AVANTAGE : permettent d'accéder facilement à n'importe quelle Place. L'accès direct permet la dichotomie par exemple.
DESAVANTAGE : elles auront du mal à gérer les suppressions, les insertions (et donc les concaténations) qui ont un coût plutôt linéaire.
Listes récursives
AVANTAGE : permettent de gérer un peu mieux les suppressions, les insertions (et donc les concaténations)
DESAVANTAGE : auront plus de mal à gérer les accès par indice. Par construction, on doit passer d'une Place à une autre. Impossible de faire de la dichotomie par exemple.
CONCLUSION IMPORTANTE 2 - 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 le 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
- De supprimer et mémoriser i éléments de tête
- D'insérer la nouvelle tête
- De replacer les têtes mémorisées
- Une primitive supprimer() qui permet de supprimer l'élément en position i, et dont le principe interne est
- De supprimer et mémoriser i éléments de tête
- De supprimer la tête actuelle (la numéro i)
- De replacer les têtes mémorisées
- Une primitive acces() qui permet de lire l'élément en position i, et dont il existe deux méthodes.
- De supprimer (sans mémoriser) i éléments de tête
- De lire l'élément en tête (le "premier")
- D'accéder à la Cellule de Tête
- D'utiliser i fois successeur()
- De lire le contenu() de la Cellule obtenue
Première version qui fonctionne qui profite de l'immuabilité et dont le principe est :
Deuxième version qui fonctionne qui utilise successeur() et contenu() et dont le principe est :
4 - Implémentation
Rappel :
- 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 structure de données (c'est la phase de réalisation pratique).
ALGORITHME ⇒ Implémentation ⇒ PROGRAMME
TYPE ABSTRAIT ⇒ Implémentation ⇒ STRUCTURE DE DONNEES
4.1 Vocabulaire retenu sur ce site
- 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 integer en utilisant le type natif entier.
- On gère le type abstrait nombre réel 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.
5 - FAQ
Rien pour le moment
-
Activité publiée le 21 09 2020
Dernière modification : 24 09 2022
Auteur : ows. h.