5 - Exercices Listes
Exerices sur le type abstrait Liste Récursive.
1 - Fonctions primitives disponibles
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().
01° 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 |
|
...CORRECTION...
L1 : lstA référence (8, ())
L2 : lstA référence (6, (8, ()))
L3 : lstA référence (4, (6, (8, ()))
L3 : x référence 4
L4 : lstB référence (6, (8, ()))
L5 : lstA référence toujours (4, (6, (8, ())). Le contenu du successeur de sa tête est donc 6.
02° Fournir les instructions pour créer une liste dont la tête est 100 et dont les données sont 100, 10, 1 .
...CORRECTION...
1
2
3 |
|
Attention pendant le DS : il faut ici commencer par créer progressivement la liste en commençant par le 1.
03° Réaliser 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.
premier(lst:Liste) → Elément
ENTREE : lst, une Liste NON VIDE
SORTIE : l'Elément contenu dans la tête
...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))
2 - Autres fonctions
Nous prendrons maintenant uniquement les 5 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
- premier(lst:Liste NON VIDE) → Element
Nous ne laisserons donc pas l'utilisateur manipuler directement les Places, qui deviennent totalement invisibles pour lui.
04° Réaliser l'algorithme longueur() en version 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é
...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
05° Réaliser l'algorithme longueur() en version version récursive utilisant que le cas de base est la liste vide qui peut répondre 0.
Sinon, on devra répondre 1 pour la tête actuelle et demander à la queue quelle est sa propre longueur.
...CORRECTION...
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))
06° Réaliser l'algorithme de inserer(), fonction qui insère un élément à la position qu'on lui transmet. 0 pour devant la tête, longueur-1 pour devant la fin et longueur pour en faire la nouvelle fin.
ALGORITHME inserer(lst:Liste, elt:Elément, i:Entier Naturel VALIDE) → Liste NON VIDE
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.
Puisqu'on ne peut agir que sur la tête, il faut vous souvenir qu'il faut :
- Supprimer et mémoriser i têtes
- Insérer l'élément en tant que nouvelle tête.
- Replacer les i têtes que nous avions stockées.
...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
07° Réaliser l'algorithme de supprimer(), fonction qui supprime l'élément à la position donnée. 0 pour la tête, longueur-1 pour la fin par exemple.
ALGORITHME supprimer(lst:Liste NON VIDE, i:Entier Naturel VALIDE) → 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.
Puisqu'on ne peut agir que sur la tête, il faut vous souvenir qu'il faut :
- Supprimer et mémoriser i têtes
- Supprimer la tête actuelle sans la mémoriser.
- Replacer les i têtes que nous avions stockées.
...CORRECTION...
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
08° 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)
3 - Coûts
09° En considérant que nous parviendrons à implémenter les primitives à côut constant, expliquer pour le coût des fonctions inserer() supprimer() et ieme() est linéaire par rapport à la position i reçue.
...CORRECTION...
Supprimer les i têtes est linéaire par rapport à i puisque supprimer une tête est à coût constant mais qu'on le fait i fois en boucle.
Rajouter une tête, supprimer une tête ou lire le premier est à coût constant.
Replacer les i têtes est linéaire par rapport à i puisque insérer une tête est à coût constant mais qu'on le fait i fois en boucle.
Pour inserer() le coût sera donc certainement en θ(1*i + 1 + 1*i), soit du θ(2i + 1). En analyse asymptotique, nous allons garder θ(i) uniquement.
10° Expliquer pourquoi on peut écrire que la complexité des trois fonctions précédentes est en O(n) sachant que nous avons trouvé θ(i) à la question précédente.
RAPPEL : i est l'indice où agir et n le nombre d'éléments dans la liste.
...CORRECTION...
θ(i) veut dire que le coût est toujours linéaire à i.
Or, i est forcément inférieur ou égal à n. Le coût de l'action est donc nécessairement inférieur ou égal à un coût linéaire en n.
C'est exactement le sens de la notation O(n) : le coût est linéaire en n ou mieux.
FIN
Activité publiée le 21 10 2020
Dernière modification : 21 10 2020
Auteur : ows. h.