Exo Liste

Identification

Infoforall

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
lstA = insererTete(nouvelleListeVide(), 8) lstA = insererTete(lstA, 6 ) lstA = insererTete(lstA, 4) x = contenu(accesTete(lstA)) lstB = supprimerTete(lstA) a = contenu(sucesseur(accesTete(lstA)))

...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
lst = insererTete(nouvelleListeVide(), 1) lst = insererTete(lst, 10 ) lst = insererTete(lst, 100)

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 :

  1. Supprimer et mémoriser i têtes
  2. Insérer l'élément en tant que nouvelle tête.
  3. 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 :

  1. Supprimer et mémoriser i têtes
  2. Supprimer la tête actuelle sans la mémoriser.
  3. 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.