Algorithmique et structures de données

Une structure de données est un objet informatique ayant pour objectif de structurer de l’information. Ce sont des composantes critiques de nombreux programme informatiques et il est donc important d’utiliser des structures de données adaptés pour écrire des programmes performant.

Un exemple typique que vous manipuler est les list et dict en Python. Il existe beaucoups, beaucoups d’autres.

Sémantique et implémentation

Dans la suite on va distinguer deux choses:

• la sémantique d’une structure de données représente l’ensemble des opérations qu’elle supporte.
  
• l’implémentation d’une structure de données représente comment celle-ci est programmé

Les séquences

Représente une suite d’éléments indicés par un entier. Les opérations typiques:

• L’accès à un élément de la suite
• Ajouter un élément à la suite
• Supprimer un élément à la suite

Les ensembles

Représente un ensemble d’éléments, c’est-à-dire, des éléments sans ordres ni repetitions. Les opérations typiques:

• Tester l’appartenance d’un élément à l’ensemble
• Ajouter un élément à l’ensemble
• Supprimer un élément à l’ensemble

Les structures de données applicatives (mapping, dict, …)

Réprésente un ensemble d’association entre des clés et des valeurs. Les opérations typiques:

• Associer une clé à une valeur
• Récupérer la valeur associée à la clé
• Supprimer une association clé/valeur

Les structures de données sur des valeurs ordonnées

Pour une collection de valeurs qui ont un ordre les une par rapport aux autres, on peut vouloir des opérations supplémentaires:

• Récupérer la valeur minimale/maximal
• Récupérer toutes les valeurs dans un interval de valeur

Python et les structures de données

Python fournit deux choses intéressantes:

1. Des interfaces abstraites qui décrivent le comportement d’une structure de données
2. Des implémentation standard concrètes et (très) efficaces de ces structures de données

Les interfaces abstraites se trouvent dans le module collection.abc documentation qui donne la correspondance entre les méthodes spéciales de Python et des interfaces standards.

Par exemple, la classe abstraite Sequence représente une classe qui doit se comporter comme un tuple. On va faire une implémenation de Sequence à l’aide de tuple pour l’exemple. Pour ça il faut implémenter __getitem__ qui donne le résultat d’un accès à un indiceet __len__ qui donne la longueur.

from collections.abc import Sequence

class MesTuple(Sequence):
    def __init__(self, values):
        self._data = tuple(values) # on stock les valeur dans un tuple

    def __getitem__(self, indice):
        return self._data[indice]

    def __len__(self):
        return len(self._data)

    def __repr__(self): # Uniquement pour faire joli, ce n'est pas nécessaire
        return f"MesTuple{self._data}"

un_tuple = MesTuple("poulet roti")
print(un_tuple)
print(un_tuple[0])
print(un_tuple[-1])

MesTuple('p', 'o', 'u', 'l', 'e', 't', ' ', 'r', 'o', 't', 'i')
p
i

Un exemple complet: les listes simplement chainées

On va faire une implémentation complète de Sequence via une structure de liste chainée et en faire l’étude de complexité.

Une liste chainée va représenter une Sequence via des maillons qui chacun va pointer sur le maillon suivant et une tête de chaîne.

class Maillon:
    def __init__(self, valeur, suivant):
        self._valeur = valeur
        self._suivant = suivant

    @property
    def valeur(self):
        return self._valeur

    @property
    def suivant(self):
        return self._suivant

    def get(self, index):
        if index == 0:
            return self.valeur
        if self.suivant:
            return self.suivant.get(index-1)
        raise IndexError()


class ListeChainee(Sequence):
    def __init__(self, valeurs):
        maillon = None
        for valeur in reversed(valeurs):
            maillon = Maillon(valeur, maillon)
        self._premier_maillon = maillon 

    def __len__(self):
        n = 0
        maillon = self._premier_maillon
        while maillon is not None:
            n += 1
            maillon = maillon.suivant
        return n
             
    def __getitem__(self, index):
        return self._premier_maillon.get(index)

    def __repr__(self):
        return "⇝".join(self)

L = ListeChainee("poulet roti")
print(L)
print(L[1], L[2], len(L))

p⇝o⇝u⇝l⇝e⇝t⇝ ⇝r⇝o⇝t⇝i
o u 11

Analyse de complexité

La liste chainée prends un temps \(O(n)\) au pire cas à récupérer une valeur avec \(n\) la taille de la liste. Ce n’est pas une très bonne structure de données (mais elle a son utilité de temps en temps).

Exercice 1

En vous inspirant de mon implémentation de ListeChainée, implémenter MutableSequence (i.e. le type abstrait de liste) avec une liste chainée. Donnez la complexité de votre implémentation

Exercice 2

1. Proposez une implémentation de Set en utilisant une liste chaînée.
2. Implémenter MutableSet avec une table de hashage à partir de l’implem de Set

Exercice 3

Proposez une implémentation de MutableMapping tel que:

• Les clés doivent n’être que des chaînes de caractères
• Les clés ne sont pas sensible à la case (aux majuscules)

• Fichier de corrections

Compiled the: mar. 26 nov. 2024 11:44:00 CET