Exo Liste

Identification

Infoforall

5 - Exercices Listes

⏪

⏬

⏩

1 - Primitives

2 - Autres

3 - Côuts

Exerices sur le type abstrait Liste Récursive.

Exercices liés à cette activité Données TAD Liste

1 - Fonctions primitives disponibles

⇩ ⇧ ⤊

Nous prendrons uniquement les 7 opérations primitives suivantes :

  • nLV() → Liste VIDE
  • estLV(lst:Liste) → Booléen
  • insT(lst:Liste, elt:Elément) → Liste NON VIDE
  • supT(lst:Liste NON VIDE) → Liste
  • accT(lst:Liste NON VIDE) → Place
  • contenu(plc:Place) → Elément
  • succ(plc:Place) → Place|Vide

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 insT().

01° Donner le contenu des variables au fur et à mesure de l'exécution de cette suite d'actions. On utilisera la représentation imbriquée pour les listes.

1 2 3 4 5 6
lstA = insT(nLV(), 8) lstA = insT(lstA, 6 ) lstA = insT(lstA, 4) x = contenu(accT(lstA)) lstB = supT(lstA) a = contenu(succ(accT(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 = insT(nLV(), 1) lst = insT(lst, 10 ) lst = insT(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.

Contrairement au cours, utilisez un pseudo-code Python et pas le pseudo-code algorithmique : = plutôt que la flèche, fin des blocs indiquée par la fin de l'indentation et plus par 'Fin du TANT QUE'...

premier(lst:Liste NON VIDE) → Elément

ENTREE : lst, une Liste NON VIDE

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

...CORRECTION...

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

RENVOYER contenu(accT(lst))

2 - Autres fonctions

⇩ ⇧ ⤊

Nous prendrons maintenant uniquement les 5 opérations primitives suivantes :

  • nLV() → Liste VIDE
  • estLV(lst:Liste) → Booléen
  • insT(lst:Liste, elt:Elément) → Liste NON VIDE
  • supT(lst:Liste NON VIDE) → Liste
  • premier(lst:Liste NON VIDE) → Element

    • Nous ne laisserons donc plus 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 compteur et 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

  • nb = 0
  • TANT QUE NON estLV(lst)
  • nb = nb + 1
  • lst = supT(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() / ins(), fonction qui insère un élément à la position qu'on lui transmet.

  • 0 pour insérer une nouvelle tête,
  • longueur pour en faire la nouvelle fin,
  • longueur-1 pour le mettre en avant-dernière position.

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

  • /// Etape 1 : on supprime et mémorise les i premières têtes
  • memoire = nLV()
  • POUR k variant de 0 à (i - 1) . . . . . . . . . . on fait la boucle i fois
  • element = premier(lst) . . . . . . . . on lit la 1er valeur de lst
  • lst = supT(lst) . . . . . . . . . . on supprime la tête
  • memoire = insT(memoire, element) . . . . on rajoute en mémoire
  • /// Etape 2 : on insère le nouvel élément
  • lst = insT(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 = supT(memoire) . . . . . on supprime la tête
  • lst = insT(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

  • /// Etape 1 : on supprime et mémorise les i premières têtes
  • memoire = nLV()
  • POUR k variant de 0 à (i - 1) . . . . . . . . . . on fait la boucle i fois
  • element = premier(lst) . . . . . . . . on lit la 1er valeur de lst
  • lst = supT(lst) . . . . . . . . . . on supprime la tête
  • memoire = insT(memoire, element) . . . . on rajoute en mémoire
  • /// Etape 2 : on supprime encore une tête
  • lst = supT(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 = supT(memoire) . . . . . on supprime la tête
  • lst = insT(lst, element) . . . . . . . on rajoute dans lst
  • RENVOYER lst

08° Réaliser un algorithme ieme() qui renvoie l'élément placé en position i.

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

ENTREES :

  • lst, une Liste NON VIDE
  • i, un Entier Naturel correspondant à un indice valide, c'est à dire entre 0 pour obtenir la tête et (longueur-1) pour obtenir la fin.

SORTIE : l'Element en position i.

...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

  • /// Etape 1 : on supprime i têtes
  • POUR k variant de 0 à (i - 1)
  • lst = supT(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 à l'aide de quelques phrases pourquoi le coût des fonctions inserer() supprimer() et ieme() est linéaire par rapport à l'indice i reçu.

...CORRECTION...

Deux solutions pour fournir les explications à chaque fois : soit on décrit les actions avec des phrases, soit avec une équation.

Pour insérer ou supprimer :

  • Créer une nouvelle Liste VIDE est à coût constant.
  • Supprimer et mémoriser i têtes consiste à faire i fois 3 opérations à coût constant. C'est donc linéaire en i.
  • Insérer ou supprimer une tête supplémentaire est à coût constant.
  • Remettre en place les i têtes précédentes consiste à faire i fois 3 opérations à coût constant. C'est donc linéaire par rapport à i.
  • Renvoyer la nouvelle liste est à coût constant.

Pour l'analyse asymptotique du coût, on prend le coût le plus important, soit ici un coût linéaire sur i.

i peut avoir comme valeur (n-1) dans le pire des cas, on en déduit que le coût est également coût linéaire sur n.

Pour ieme :

On réalise :

  • i fois une action à coût constant, c'est donc linéaire en i
  • puis une action à coût constant.

En prenant le coût le plus important, on obtient une fonction à coût linéaire par rapport à i et donc à n dans le pire des cas.

10° Réaliser les mêmes explications sur les coûts mais en utilisant plutôt le système de notation asymptotique permettant de traduire cela par des équations.

...CORRECTION...

Pour insérer ou supprimer :

En cumulant les coûts des différentes phases,

𝞗(1 + i*3 + 1 + i*3 + i) =
𝞗(3 + 6*i) =
𝞗(6*i) =
𝞗(i) = 𝓞(n) puisque i ≤ n

Pour ieme :

En cumulant les coûts des différentes phases,

𝞗(i*1 + 1) =
𝞗(i) = 𝓞(n) puisque i ≤ n

Il s'agit donc encore une fois d'une fonction à coût linéaire par rapport à n dans le pire des cas.

FIN

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


⏪

⏫

⏩