Listes

I/ Définition

1) Arbre unaire

Un arbre unaire est un arbre (binaire) dans lequel chaque nœud (autre que la feuille) n'a qu'un enfant (on choisit ici celui de droite).

On choisit de dessiner chaque enfant à droite de son parent. Par exemple pour la liste L→I→S→T→E :

Pour éviter de confondre parent et enfant (ou précédent et suivant) on dessine plutôt un graphe orienté :

Plutôt que arbre unaire on préfère parler de liste.

La représentation interne en machine est un graphe en peigne (Allen Newell 1957) :

ou chaînée (John McCarthy 1958) :

2) Éléments

Les nœuds de la liste s'appellent ses éléments.

Vue comme un arbre, une liste n'a qu'une feuille. On l'appelle le dernier élément de la liste.

La racine de la liste s'appelle aussi son premier élément.

Pour une liste, l'enfant d'un élément (vu comme un élément) s'appelle l'élément suivant. Le parent d'un élément s'appelle l'élément précédent.

3) En Python

Pour construire facilement une liste, on a intérêt à utiliser une méthode append qui ajoute le nouvel élément à la fin de la liste. On commence par ces méthodes :

• __init__ crée la liste et donne une valeur à son premier (et seul) élément.
• est_dernier vérifie si la liste ne contient qu'un seul élément (en bref, que c'est le dernier élément).
• append ajoute un élément à la fin de la liste.
• __repr__ affiche la liste, récursivement :
  • L'affichage d'une liste à un seul élément, est cet élément.
  • L'affichage d'une liste à plusieurs éléments est obtenu en affichant cet élément, puis en affichant la suite de la liste.

On écrit tout ça dans un fichier texte nommé listes.py :

class Liste():
    def __init__(self,elt):
        self.valeur = elt
        self.suivant = None
    def est_dernier(self):
        return self.suivant is None
    def append(self,elt):
        if self.est_dernier():
            self.suivant = Liste(elt)
        else:
            self.suivant.append(elt)
    def __repr__(self):
        return self.valeur+str(self.suivant).replace('None','.')

Ensuite, ce script permet de facilement construire puis afficher une liste :

from listes import *

liste = Liste('L')
for lettre in 'ISTE':
    liste.append(lettre)

print(liste)

L'exécution de ce script produit l'affichage LISTE. mais aussi la création d'un fichier listes.pyc qui n'est pas un fichier texte : c'est un binaire exécutable et la création de cet exécutable à partir du source listes.py est la compilation. L'extension .pyc signifie d'ailleurs « Python compilé ».

4) Recherche

On recherche un élément dans la liste, en parcourant récursivement celle-ci :

class Liste():
    ...
    def contient(self,elt):
        if self.valeur==elt:
            return True
        elif self.est_dernier():
            return self.valeur==elt
        else:
            return self.suivant.contient(elt)

Ce parcours est à la fois en largeur et en profondeur. Il est donc de complexité linéaire (voir cours de première).

On peut programmer récursivement les algorithmes vus en Première.

En Haskell

a) Longueur d'une liste

longueur :: [Int] -> Int
longueur [] = 0
longueur (x:xs) = 1 + longueur xs

b) Recherche

dedans :: Int -> [Int] -> Bool
dedans _ [] = False
dedans e (x:xs)
            | e==x = True
            | otherwise = dedans e xs

c) Somme

somme :: [Int] -> Int
somme [] = 0
somme (x:xs) = x+somme xs

II/ Exemples

1) Chaînes de caractères

Une chaîne d'ADN (ou d'ARN) est une liste d'acides nucléiques, résumés par des lettres :

Une chaîne d'ADN pouvant être très longue, il est impossible d'accéder à un élément sans compter. C'est caractéristique d'une liste chaînée.

La lecture d'un texte se fait lettre par lettre, de gauche à droite. On peut donc aussi modéliser un texte par une liste chaînée de lettres. L'ADN en est un cas particulier avec les lettres A, C, G, T. Voici un extrait d'un gène d'arabica :

AAGGTCCCTTATGATGCTGGCTTCTCTATTGATGATGATTACCAAGGAAGATCCCATTCCCCAGTATCCTGCGATGAACA

2) Liaison série

Lorsque des informations circulent sur une liaison série (usb, TCP, ...) c'est l'une après l'autre, et pour accéder à un élément on est obligé de parcourir tous ceux qui le précèdent.

3) Les listes de Python

Les listes Python ne sont pas des listes. En effet il est possible d'accéder à n'importe quel élément de la « liste » L avec L[i]. Cela est dû à la méthode __getitem__ des listes Python. La méthode __iter__ permet bel et bien de parcourir une liste élément après élément, mais les listes chaînées se distinguent des listes Python, non par ce qu'elles peuvent faire, mais par ce qu'elles ne peuvent pas faire. On peut néanmoins simuler des listes chaînées avec des listes Python, en créant une classe ne possédant que les méthodes qui caractérisent une liste.

a) Interface

On commence par ne définir que les méthodes :

class Liste():
	def __init__(self,L=[]):
		pass
	def dernier(self):
		pass
	def empiler(self,elt):
		pass
	def premier(self):
		pass
	def pousser(self,elt):
		pass
	def __iter__(self):
		pass
	def __repr__(self):
		pass

Cela revient à dire qu'une liste est un objet Python qui peut être parcourue itérativement, où on peut insérer un élement soit au début de la liste (pousser) soit à la fin (empiler) et où l'on peut lire directement le premier et le dernier élément, et eux seuls.

Cette classe vide est une interface.

b) Implémentation

Les méthodes qui caractérisent une liste chaînée peuvent simplement être celles de son attribut qui est une liste Python :

class Liste():
	def __init__(self):
		self.contenu = []
	def dernier(self):
		return self.contenu.pop()
	def empiler(self,elt):
		self.contenu.append(elt)
	def premier(self):
		return self.contenu.pop(0)
	def pousser(self,elt):
		self.contenu.insert(0,elt)
	def __iter__(self):
		return self.contenu.__iter__()
	def __repr__(self):
		return str(self.contenu)

c) Utilisation

On vérifie que la liste ainsi créé est chaînée :

L = Liste(['L','I','S','T','E'])

print(L[0])

Le message d'erreur est à comprendre comme une impossibilité d'accéder directement à un élément de la liste :

TypeError: 'Liste' object does not support indexing

Par contre elle peut être parcourue itérativement :

for e in L:
	print(e)

ne donne pas de message d'erreur mais :

L
I
S
T
E

Contrairement aux éléments d'une liste, les clés d'un dictionnaire sont accessibles rapidement (et pas seulement pour les dictionnaires de Python).

III/ Recherche de motif

On voudrait savoir si le motif ATTAC se trouve quelque part dans la chaîne d'ADN vue ci-dessus. L'algorithme ci-dessous, dû à Horspool (1990, d'après Boyer et Moore) utilise un parcours particulier de la liste.

1) Prétraitement du motif

Pour chacune des lettres A, C, G, T, on mémorise la distance entre cette lettre et la fin du motif :

En Python, on fabrique un dictionnaire, qui, à chaque lettre, associe la distance de décalage :

def prétraitement(motif):
    table = {}
    lm = len(motif)
    for k in range(lm-1):
        table[motif[k]] = k
    for c in 'ACGT':
        if c in table:
            table[c] = lm-1-table[c]
        else:
            table[c] = lm
    return table

2) Déroulé de l'algorithme

On place le motif à côté de la chaîne :

Le motif n'est pas reconnu parce qu'en face du C il y a autre chose que C : il y a T. Comme la distance associée à T est 2, on décale le motif de 2 crans vers la droite :

Cette fois-ci il y a coïncidence à la fin. On vérifie en repartant vers la gauche que c'est aussi le cas avant. Mais l'avant-dernière lettre (en face du A) est un C, pas un A. La distance de C est 5, donc on décale de 5 crans :

Comme au début, il y a un T en face du C. On décale donc de 2 crans :

En face du C il y a un A donc on ne décale que d'un cran :

T : 2 crans :

Les C coïncident mais en face du A il y a un G. On décale encore, de 5 crans qui est la distance du C :

T : 2 crans

C mais les lettres précédentes ne coïncident pas, donc 5 décalages :

T donc 2 crans :

G donc 5 crans :

T donc 2 crans :

A donc un seul cran :

T donc 2 crans :

A donc un seul cran :

Et on a trouvé une occurrence de ATTAC dans la chaîne d'ADN. Au cours de la recherche, on a décalé le motif de 37 lettres en seulement 15 étapes.

3) Fonction Python

La fonction chercher renvoie None si le motif n'est pas dans la chaîne d'ADN, et sinon, l'indice de la première occurence du motif dans le texte.

def chercher(motif,texte):
    d = prétraitement(motif)
    lm = len(motif)
    curseur = 0
    while curseur <= len(texte)-lm:
        if texte[curseur+lm-1]==motif[lm-1]:
            if [texte[k] for k in range(curseur,curseur+lm)]==list(motif):
                return curseur
        curseur += d[texte[curseur+lm-1]]