Activité 2¶

Compétences évaluées
Concevoir des solutions algorithmiques
Traduire un algorithme dans un langage de programmation

Faites le maximum d'exercices. Le barème est indicatif, c'est surtout votre démarche et les compétences globales que je vais évaluer. Si vous n'avez pas terminé à la première session de TP alors vous pourrez continuer à la session suivante ou même chez vous si vous le souhaitez. La qualité du code sera prise en compte. Je pourrais être amené à vous demander des explications détaillées sur votre code.

Toutes les structures de données contiennent uniquement des entiers.

Vous devez créer des classes et ne pas utiliser de types construits Python (pas de liste, de tuples, de dictionnaires, etc)

Tests

L'instruction d'assertion assert permet de tester votre code et vous indique quel résultat est attendu. Si aucune erreur n'est renvoyée alors votre code passe les tests, sinon vous devrez modifier votre code pour passer les tests.

Exercice 1 (7 points)¶

C'est votre premier jour à l'entreprise Goutgole, le Team Lead débarque en sueur et vous tend un bout de papier qui spécifie une interface pour pouvoir implémenter une liste chaînée.

Une liste chaînée :

est_vide(L) : renvoie Vrai si la liste L est vide, Faux sinon
taille(L) : renvoie le nombre d’éléments de la liste L
ajouter_debut(L, M) : ajoute un maillon d au début de la liste L
ajouter_fin(L, M) : ajoute un maillon d à la fin de la liste L
get_dernier_maillon(L) -> entier : renvoie le dernier élément de la liste
recuperer_valeur(L, i) -> entier : renvoie la valeur du maillon M à l'indice \(i\)

Implémenter cette structure de données en complétant le code ci-dessous.

class Maillon:
    def __init__(self, valeur):
        #...........Completer
        #...........Completer

class ListeChainee:
    def __init__(self):
        #...........Completer
        #...........Completer

    def est_vide(self):
        """ Vérifier si la liste chaînée est vide
        """
        #...........Completer

    def get_taille(self):
        """ Retourner le nombre d'éléments
        """
        self.taille = 0
        if self.est_vide():
            #...........Completer

        maillon = self.tete

        while maillon :
            #...........Completer
            #...........Completer
        return self.taille

    def ajouter_debut(self, m):
        """ Ajouter un maillon m au début de la liste L
        """
        ancienne_tete = #...........Completer
        self.tete = #...........Completer
        m.suivant = #...........Completer
        self.taille = #...........Completer

    def ajouter_fin(self, m):
        """ Ajouter un maillon m à la fin de la liste L
        """
        maillon = #...........Completer
        if maillon is None:
            self.tete = #...........Completer
        else:
            while maillon:
                # On est arrivé au dernier élément
                if maillon.suivant is None:
                    #...........Completer
                    break
                else:
                    #...........Completer
        #...........Completer

    def get_dernier_maillon(self):
        """ Retourner le dernier maillon
        """
        maillon = #...........Completer
        if maillon is None:
            return None
        else:
            while maillon:
                # On est arrivé au dernier élément
                if #...........Completer:
                    return #...........Completer
                else:
                    #...........Completer

    def get_valeur_maillon_indice(self, indice):
        """ Retourner maillon à un indice particulier
        """
        maillon = #...........Completer
        if indice > self.get_taille() or indice < 0:
            raise IndexError("Erreur d'indice")
        elif maillon is None :
            return None
        else:
            #...........Completer
                if i == indice:
                    return maillon.valeur
                #...........Completer

# TESTS :ne changez pas ce code, si une erreur est renvoyée
# analysez l'erreur et modifiez votre code en conséquence
# si vous êtes pensez qu'il y a une erreur de mon côté, ou si vous avez
# une question alors levez la main

m_tete = Maillon(0)
liste_chainee = ListeChainee()
assert(liste_chainee.est_vide())

liste_chainee.tete = m_tete
assert(not liste_chainee.est_vide())
assert(liste_chainee.get_taille() == 1)

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

m_tete.suivant = m1
m1.suivant = m2
m2.suivant = m3
m3.suivant = m4
assert(liste_chainee.get_taille() == 5)

m5 = Maillon(5)
liste_chainee.ajouter_debut(m5)
assert(liste_chainee.tete == m5)
assert(liste_chainee.get_taille() == 6)

m6 = Maillon(6)
liste_chainee.ajouter_fin(m6)
assert(liste_chainee.get_taille() == 7)
assert(liste_chainee.get_dernier_maillon().valeur == 6)
assert(liste_chainee.get_valeur_maillon_indice(0) == 5)

Exercice 2 (5 points)¶

Compléter la Pile suivante en implémentant uniquement les primitives (c'est à dire les opérations essentielles) suivantes :

Créer une pile vide PileVide() → Pile.
Renvoyer le nombre d’éléments de la pile Taille(P: Pile)
Ajouter un élément Empiler(e : Element) (push)
Renvoie l'élément se situant au sommet de la pile et le retire Dépiler(P: Pile) -> Element (pop)

class Maillon:
    def __init__(self, valeur, suivant=None):
        #...........Completer
        #...........Completer

class Pile:
    def __init__(self):
        #...........Completer
        self.sommet = None

    def empiler(self, maillon):
        #...........Completer
        #...........Completer
        #...........Completer
        #...........Completer

    def depiler(self):
        if self.taille > 0:
            #...........Completer
            #...........Completer
            #...........Completer
            return valeur

# TESTS :ne changez pas ce code, si une erreur est renvoyée
# analysez l'erreur et modifiez votre code en conséquence
# si vous êtes pensez qu'il y a une erreur de mon côté, ou si vous avez
# une question alors levez la main

p = Pile()
assert(p.taille == 0)

m17 = Maillon(17)
p.empiler(m17)
assert(p.taille == 1)
assert(p.depiler() == 17)
assert(p.taille == 0)

m28 = Maillon(28)
p.empiler(m17)
p.empiler(m28)
assert(p.taille == 2)
assert(p.depiler() == 28)
assert(p.taille == 1)
assert(p.depiler() == 17)
assert(p.taille == 0)

Exercice 3 (4 points)¶

Cette fois-ci on utilise une liste doublement chaînée, c'est à dire qu'on garde un pointeur vers l'élémént suivant et l'élément précédent. Compléter la File ci-dessous. Seules les opérations suivantes sont requises :

Créer une file vide FileVide() → File
Renvoyer le nombre d’éléments de la file Taille(F: File)
Enfiler un nouvel élément Enfiler(e : Element)
Défiler un élément, supprime et renvoie le premier élément Defiler(e : Element) -> Element

class Maillon:
    def __init__(self, valeur, precedent=None,  suivant=None):
        self.valeur = #...........Completer
        self.precedent = #...........Completer
        self.suivant = #...........Completer

class File:

    def __init__(self):
        self.longueur = 0
        self.tete = #...........Completer
        self.queue = #...........Completer

    def enfiler(self, valeur):
        maillon = #...........Completer
        if self.longueur == 0:
            self.tete = self.queue = #...........Completer
        else:
            maillon.suivant = #...........Completer
            self.queue.precedent = #...........Completer
            self.queue = #...........Completer
            self.queue.precedent = None
        #...........Completer

    def defiler(self):
        if self.longueur == 0:
            return None
        else:
            tmp_tete = #...........Completer
            if self.tete.precedent:
                tmp_precedent =  #...........Completer
                self.tete.precedent = None
                self.tete = #...........Completer
            #...........Completer
            return tmp_tete

# TESTS :ne changez pas ce code, si une erreur est renvoyée
# analysez l'erreur et modifiez votre code en conséquence
# si vous êtes pensez qu'il y a une erreur de mon côté, ou si vous avez
# une question alors levez la main

f = File()
assert(f.longueur == 0)

f.enfiler(17)
assert(f.longueur == 1)
assert(f.defiler().valeur == 17)
assert(f.longueur == 0)

f.enfiler(18)
f.enfiler(19)
f.enfiler(20)

assert(f.defiler().valeur == 18)
assert(f.defiler().valeur == 19)
assert(f.defiler().valeur == 20)

assert(f.longueur == 0)

Exercice 4 (4 points)¶

Ecrivez une fonction inverser(P: Pile) qui inverse l'ordre des éléments de votre Pile en utilisant votre File. Réfléchissez avant de coder en utilisant une feuille de papier.

m1 = Maillon(1)
m2 = Maillon(2)
m3 = Maillon(3)

p = Pile()
p.empiler(m1)
p.empiler(m2)
p.empiler(m3)

f = File()

def inverser(pile, file):
    #...........Completer
    #...........Completer
    #...........Completer
    #...........Completer
    return pile

inverser(p, f)

# TESTS :ne changez pas ce code, si une erreur est renvoyée
# analysez l'erreur et modifiez votre code en conséquence
# si vous êtes pensez qu'il y a une erreur de mon côté, ou si vous avez
# une question alors levez la main

assert(p.depiler() == 1)
assert(p.depiler() == 2)
assert(p.depiler() == 3)

Exercice 5 : bonus¶

Etudier la complexité des opérations de votre implémentation d'une File utilisant une liste chaînée (rédigez un paragraphe sous forme de commentaire : # Ceci est un commentaire Python). Comparez en particulier la complexité pour l'opération "Défiler" avec l'implémentation du cours utilisant le type list Python.