Listes - Implémentation et algorithmes

On utilisera dans toutes les questions de ce contrôle la classe Maillon ainsi que l'interface des objets de type Liste tels que définis dans le cours. Ainsi, on pourra utiliser sans justification supplémentaire :

utiliser le constructeur Maillon(v: int, s: Maillon) pour créer un nouveau maillon.
accéder aux attributs valeur et suivant des objets Maillon ;
utiliser les fonctions creer_vide, est_vide, est_singleton, ajoute, tete, queue et affiche afin de manipuler des objets de type Liste.

Ces fonctions ne modifient pas les objets qu’elles prennent en argument. On rappelle que la fonction ajoute a pour signature Maillon, int -> Maillon.

m = Maillon(2, Maillon(3, None))
m = ajoute(m, 1)
affiche(m)   

1 - 2 - 3 - x

Listes chaînées¶

On considère le code suivant :

m4 = Maillon(4, None)
m3 = Maillon(3, m4)
m2 = Maillon(2, None)
m1 = Maillon(1, m2)

Représenter à l’aide d’un schéma l’état de la mémoire de l’ordinateur à l’issue de l’exécution des instructions précédentes. En déduire l’affichage réalisé par le code :
1 2
for m in [m1, m2, m3, m4]: affiche(m)
```
1 - 2 - x
2 - x
3 - 4 - x
4 - x
```
Quel est l’affichage réalisé par les instructions affiche(m1) et affiche(m2) après l'exécution de l'instruction :
1
m1 = Maillon(5, Maillon(6, m3))
1 2
affiche(m1) affiche(m2)
```
5 - 6 - 3 - 4 - x
2 - x
```
Justifier à l’aide d’un schéma.
Quel est l’affichage réalisé par les instructions affiche(m1) et affiche(m2) après l'exécution de l'instruction :
1
m2.suivant = m3
1 2
affiche(m1) affiche(m2)
```
5 - 6 - 3 - 4 - x
2 - 3 - 4 - x
```

Quel est l’affichage réalisé par les instructions affiche(m1) et affiche(m2) après l'exécution de l'instruction :

1	`m4.suivant = m2`

affiche(m1)
affiche(m2) 

5 - 6 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 - 2 - 3 - 4 -

On peut étudier l'effet de ces instructions avec Pythontutor.

On souhaite écrire le code d’une fonction concatene, itérative, qui prend en entrée deux arguments m1 et m2 de type Maillon supposés non vides et qui relie les deux chaînes correspondantes entre elles de la manière suivante : on parcourt la chaîne commençant par le maillon m1 jusqu’au dernier maillon non vide, et affecte à son attribut suivant le maillon m2.

Écrire le code d’une fonction concatene correspondant à la description de l’énoncé, sans se soucier d’en écrire la documentation.

def concatene(m1, m2):
    """ Maillon, Maillon -> Nonetype """
    maillon_courant = m1
    while maillon_courant.suivant is not None:
        maillon_courant = maillon_courant.suivant
    maillon_courant.suivant = m2

On considère le code suivant :

a = Maillon(1, Maillon(2, None))
b = Maillon(3, Maillon(4, None))

Justifier vos réponses aux questions suivantes en réalisant un schéma explicatif par question.

On exécute l’instruction concatene(a, b).

Quel est l’affichage alors réalisé par l’instruction affiche(a) ?
1 2
concatene(a, b) affiche(a)
```
1 - 2 - 3 - 4 - x
```
On exécute une deuxième fois l’instruction concatene(a, b).

Quel est l’affichage alors réalisé par l’instruction affiche(a) ?
1 2 3
concatene(a, b) affiche(a) # ne termine pas # car la liste dont le premier maillon est a est cyclique.

On exécute une troisième fois l’instruction concatene(a, b).

Que se passe-t-il ?

concatene(a, b) # ne termine pas
# comme la liste dont le premier maillon est a est cyclique,
# la condition de la boucle while de la fonction concatene
# est toujours vérifiée (on n'atteint jamais None).
affiche(a) 

Étude de fonctions récursives¶

Soit la fonction d suivante :

def d(l):
   """ Liste -> Liste """
   if est_vide(l):
      return l
   else:
      reste = d(queue(l))
      new = ajoute(ajoute(reste, tete(l)), tete(l))
      return new

Déterminer l'affichage réalisé par affiche(d(l)), si l est la liste \((1, 2, 3)\).

Vous justifierez votre réponse par un arbre d'appel, en y représentant les listes de manière "naturelle". Ainsi, le premier nœud de l'arbre sera :

l = creer_vide()
l = ajoute(ajoute(ajoute(l, 3), 2), 1) 
affiche(l)
affiche(d(l))

1 - 2 - 3 - x
1 - 1 - 2 - 2 - 3 - 3 - x

Soit f la fonction suivante :

def f(l1, l2):
    """ Liste, Liste -> Liste """
    if est_vide(l1):
        return l2
    elif est_vide(l2):
        return l1
    else:
        intermediaire = f(queue(l1), queue(l2))
        return ajoute(ajoute(intermediaire, tete(l2)), tete(l1))

Déterminer l'affichage réalisé par affiche(f(l1, l2)), si l1 est la liste (1, 2, 3) et l2 est la liste (4, 5, 6). Vous justifierez vos réponses par un arbre d'appel.

l1 = creer_vide()
l1 = ajoute(ajoute(ajoute(l1, 3), 2), 1) 
l2 = creer_vide()
l2 = ajoute(ajoute(ajoute(l2, 6), 5), 4) 
affiche(l1)
affiche(l2)
affiche(f(l1, l2))

1 - 2 - 3 - x
4 - 5 - 6 - x
1 - 4 - 2 - 5 - 3 - 6 - x

Tri par insertion¶

L’objectif de cet exercice est d’étudier une implémentation récursive des algorithmes de tri classique : le tri par insertion et le tri par sélection.

Partie A

On commence par détailler le fonctionnement de l'algorithme du tri par insertion. Pour ce faire, il est nécessaire d'écrire une fonction auxiliaire, inserer_dans_liste_triée.

La fonction inserer_dans_liste_triée prend en argument une liste l supposée triée par ordre croissant et un entier e quelconque et renvoie la liste composée des éléments de l et de e également triée par ordre croissant. Par exemple, si l est la liste (1, 2, 3, 5) et e est l'entier 4, inserer_dans_liste_triée(l, e) renvoie la liste (1, 2, 3, 4, 5).

Déterminer sans justifier votre réponse dans chacun des cas ci-dessous la liste renvoyée par l’instruction :

inserer_dans_liste_triée(l, e)
1. l = (), e = 3
  
  Renvoie (3)
2. l = (4, 5, 6), e = 3
  
  Renvoie (3, 4, 5, 6)
3. l = (11, 14, 18), e = 4
  
  Renvoie (4, 11, 14, 18)
4. l = (19, 20, 23), e = 22.
  
  Renvoie (19, 20, 22, 23)

En déduire une fonction récursive inserer_dans_liste_triée, qui réponde à la question de l’énoncé. On ne se souciera pas d’écrire la documentation de cette fonction. On pourra écrire dans le code i à la place de inserer_dans_liste_triée.

def i(l, e):
    if est_vide(l):
        return ajoute(creer_vide(), e)
    else:
        if e <= tete(l):
            return ajoute(l, e)
        inter = i(queue(l), e)
        return ajoute(inter, tete(l))

On rappelle l’algorithme du tri par insertion d’une liste l :

Si la liste l est vide alors elle est triée.
Sinon :
- On trie récursivement la queue de la liste l. On note cette liste l’.
- On insère l’élément de tête de la liste l "au bon endroit" dans l’ de telle sorte que la liste résultant soit également triée.

Recopier et compléter sur votre copie le schéma ci-dessous :

2. Compléter directement sur l'énoncé le code ci-dessous.

def tri_insertion(l):
    """ Liste -> Liste
    Renvoie la liste des éléments de l triés par ordre croissant. """
    if est_vide(l):
        return l
    else:
        # 1 - On trie récursivement la queue de la liste
        trie_intermediaire = tri_insertion(queue(l))
        # Affichage pour analyse
        affiche(trie_intermediaire)
        # 2 - On insère dans la queue triée récursivement
        # l'élément de tête de la liste. La liste résultat
        # est triée par ordre croissant
        resultat = i(trie_intermediaire, tete(l))
        # Affichage pour analyse
        print(f"On y insère {tete(l)}")
        return resultat

Déterminer les affichages réalisés par l’instruction tri_insertion(l), quand l est la liste (8, 9, 1).

On pourra suivre l’exécution de l’algorithme à l’aide d’un arbre d’appel.
1 2 3
l = ajoute(ajoute(ajoute(creer_vide(), 1), 9), 8) l = tri_insertion(l) affiche(l)
```
x
On y insère 1
1 - x
On y insère 9
1 - 9 - x
On y insère 8
1 - 8 - 9 - x
```

Partie B

On rappelle que l'on a écrit en TP le code des fonctions suivantes :

minimum(l: Liste) -> int : renvoie le plus petit élément de l ;
supprime(l: Liste, e: int) -> Liste : renvoie la liste des éléments de l où la première occurrence de e a été supprimée (e est supposé présent dans la liste l).

En utilisant uniquement les fonctions de l'interface du type Liste ainsi que les fonctions minimum et supprime, écrire une fonction récursive tri_selection qui trie la liste l à l'aide de l'algorithme du tri par sélection dont on rappelle le principe ci-dessous :

Si la liste l est vide, alors il n'y a rien à faire.
Sinon :
- On calcule la valeur du minimum m de la liste l ;
- On calcule la liste l' obtenue en supprimant de la liste des éléments de l la première occurence de m ;
- On ajoute l'élément m en tête de la liste l' (que l'on a préalablement triée).

def minimum(l):
    """ Liste -> int
    Renvoie le minimum d'une liste non vide. """
    if est_vide(queue(l)):
        return tete(l)
    else:
        return min(tete(l), minimum(queue(l)))

def supprime(l, e):
    """ Liste, int -> Liste
    Renvoie la liste des éléments de l sans la première occurrence de e.
    e est supposé appartenir à la liste l. """
    if tete(l) == e:
        return queue(l)
    else:
        return ajoute(supprime(queue(l), e), tete(l))

def tri_selection(l):
    if est_vide(l):
        return l
    else:
        m = minimum(l)
        lp = supprime(l, m)
        reste_trie = tri_selection(lp)
        return ajoute(reste_trie, m)

l = ajoute(ajoute(ajoute(creer_vide(), 1), 9), 8)
affiche(tri_selection(l))

1 - 8 - 9 - x

Justifier que votre fonction tri_selection est récursive.

On réalise un appel récursif à la cinquième ligne du code de tri_selection : reste_trie = tri_selection(lp).