Plan

• Listes chaînées
• Queue et FIFO
• Pile et LIFO
• Comparaison entre FIFO et LIFO
• Rappels sur la théorie des ensembles
• Rappels sur le calcul matriciel

Introduction

• En Python, une list permet de rassembler un nombre variable d'éléments.
• Nous allons voir une manière d'implémenter ce type de liste.

Notion de liste chaînée

• Une liste chaînée est une structure de données récursive.
• Une liste chaînée est composée de noeuds.
• Un noeud comporte 2 variables :
  • Une valeur,
  • Le noeud suivant.

Noeud d'une liste chaînée

2 noeuds

Structure de données

from dataclasses import dataclass

@dataclass
class Noeud:
    """Noeud de la liste chainee.
    
    La valeur peut etre n'importe quel objet 
    Python valide.
    Le suivant doit avoir pour type Noeud
    ou None.
    """
    valeur = None
    suivant = None

Noeud de départ

• Comment identifier le noeud de départ de la liste ?
• On souhaite que chaque noeud ait la même représentation.
• On introduit un nouveau type, Liste, qui référence le noeud de départ.
• Une Liste n'a pas de valeur.

Noeud de départ identifié par la liste

Structure de données

from dataclasses import dataclass

@dataclass
class Liste:
    """Liste chainee.

    Il s'agit simplement d'un point d'entree
    vers le 1er noeud de la liste chainee, 
    nommé initial.
    La variable initial doit avoir pour type
    Noeud ou None.
    """
    initial = None

Liste chaînée comportant 2 valeurs

Exemple avec 3 valeurs

liste_chainee = creer_liste_chainee(42, 3.14, "bonjour")

Dernier noeud

Le suivant du dernier noeud est None.

Parcours d'une liste chaînée

def parcours(liste_chainee, f):
    """Appelle f sur chaque valeur de la liste chaînée.

    liste_chainee - liste chaînée de type Liste.
    f - fonction prenant un argument.
    """
    noeud = liste_chainee.initial
    while noeud != None:
        f(noeud.valeur)       # appelle la fonction f
        noeud = noeud.suivant # passage au noeud suivant

Insertion au début

L'insertion au début est non-destructive.
Il est possible de construire des listes chaînées immutables.

Insertion au milieu

Insertion à la fin

Suppression au début

Suppression au milieu

Suppression à la fin

Liste doublement chaînée

from dataclasses import dataclass

@dataclass
class NoeudBidirectionnel:
    valeur = None
    suivant = None
    precedent = None   # Nouveau

@dataclass
class ListeBidirectionnelle:
    initial = None
    final = None       # Nouveau

Evaluation des listes chaînées

• Avantages :
  • Insertion rapide au début.
  • Insertion rapide à la fin pour une liste doublement chaînée.
• Inconvénients :
  • Pas d'indexation : il faut parcourir potentiellement tous les éléments pour en retrouver un.
  • Mémoire éparse : chaque noeud a sa propre adresse en mémoire.

Comparaison avec une list

• La Liste chaînée est un exercice intéressant pour comprendre comment une list peut être implémentée.
• La Liste chaînée introduite ici et dans le prochain TP a un but purement pédagogique.
• Dans du code industriel de production, utilisez une list.

TP : Manipulation d'une liste chaînée

Lien vers le sujet de TP.

Notion de file d'attente

• Une queue, également nommée file d'attente, est une collection.
• Cette collection comporte 2 opérations principales :
  • Empiler un élément.
  • Dépiler le 1er élément empilé.
• Premier entré, premier sorti.

Métaphore

Principe

Exemple avec 2 éléments

Structure de données

from dataclasses import dataclass

@dataclass
class Queue:
    """Queue utilisant une liste chainee.

    initial - doit avoir pour type 
              Noeud ou None.
    final - doit avoir pour type 
            Noeud ou None.
    """
    initial = None
    final = None

Empile

Dépile

Utilisation d'une list

def empile(queue, element):
    """Empile l'élément dans la queue.

    queue - la queue à modifier.
    element - element à empiler dans la queue.
    """
    queue.append(element)

def depile(queue):
    """Depile le 1er élément de la queue.

    queue - la queue à modifier.
    Retourne le 1er élément de la queue.
    """
    return queue.pop(0)

Exemple

queue = [6, 3, 7]
empile(queue, 10)
print(queue)       # [6, 3, 7, 10]

valeur = depile(queue)
print(valeur)      # 6
print(queue)       # [3, 7, 10]

Exemple

queue = deque([6, 3, 7])
empile(queue, 10)
print(queue)           # deque([6, 3, 7, 10])

valeur = depile(queue)
print(valeur)          # 6
print(queue)           # deque([3, 7, 10])

Notion de pile

• Une pile est une collection.
• Cette collection comporte 2 opérations principales :
  • Empiler un élément.
  • Dépiler le dernier élément empilé.
• Dernier entré, premier sorti.

Métaphore

Principe

Exemple avec 2 éléments

Structure de données

from dataclasses import dataclass

@dataclass
class Pile:
    """Pile utilisant une liste chainee.

    initial - doit avoir pour type 
              Noeud ou None.
    """
    initial = None

Empile

Dépile

Utilisation d'une list

def empile(pile, element):
    """Empile l'élément dans la pile.

    pile - la pile à modifier.
    element - element à empiler dans la pile.
    """
    pile.insert(0, element)

def depile(pile):
    """Depile le 1er élément de la pile.

    pile - la pile à modifier.
    Retourne le 1er élément de la pile.
    """
    return pile.pop(0)

Exemple

pile = [6, 3, 7]
empile(pile, 10)
print(pile)           # [10, 6, 3, 7]

valeur = depile(pile)
print(valeur)         # 10
print(pile)           # [6, 3, 7]

Exemple

pile = deque([6, 3, 7])
empile(pile, 10)
print(pile)            # deque([10, 6, 3, 7])

valeur = depile(pile)
print(valeur)          # 10
print(pile)            # deque([6, 3, 7])

FIFO LIFO

FIFO dans la réalité

Les queues de messages

• Ordonnanceur de tâches (systèmes d'exploitation).
• Traitements asynchrones dans un système.
• Version itérative d'algorithmes récursifs.

LIFO dans la réalité

• Pile d'appels de fonctions.
• Interpréteur.
• Version itérative d'algorithmes récursifs.

TP : Queues de messages simples

Lien vers le sujet de DM.

Intérêt

• Nous avons vu le type set dans le cours précédent.
• Le DM n°3 vous demande d'implémenter les opérations classiques sur les ensembles.
• Nous revenons rapidement sur ces définitions pour préparer le DM.

Ensemble vide

Ensemble avec quelques éléments

Ensembles disjoints

Sous-ensemble

Intersection

Union

Exclusion

Différence

Intérêt

• En prévision du DM n°3 et de l'examen.
• Pour faire des jeux vidéos.
• Pour la conception assistée par ordinateur.

Déterminant d'une matrice 2x2

Expansion de Laplace

Déterminant d'une matrice 3x3

Il s'agit d'une définition récursive.

Expansion de Laplace

Déterminant d'une matrice NxN

Les sont les mineurs des matrices de la première ligne de .

Mineur d'une matrice

Le mineur d'une matrice aux indices est noté .

Système d'équations linéaires

Sous forme matricielle

Résolution du système

Problème : L'inversion matricielle n'est pas trivialle.

Matrice Identité

L'élément neutre de la multiplication matricielle est noté et comporte des 0 partout sauf sur sa diagonale, composée de 1.

Matrice triangulaire

Soit la partie supérieure de la matrice, soit la partie inférieure de la matrice, n'est composée que de 0.

est triangulaire supérieure.
est triangulaire inférieure.

Matrice diagonale

Tous les éléments de la matrice sont nuls, sauf ceux sur sa diagonale.

Puissance d'une matrice diagonale

Donc :

Diagonalisation : principe (1/2)

• Si une matrice est diagonalisable alors on peut l'écrire où est sa matrice diagonale, et P la matrice de passage.
• Pour diagonaliser, on calcule les valeurs propres telles que .
• Pour chaque valeur propre, on calcule le vecteur propre associé tel que .

Diagonalisation : principe (2/2)

• La matrice diagonale équivalent s'obtient en mettant les valeurs propres sur la diagonale.
• La matrice de passage est obtenue en mettant les vecteurs propres obtenus en colonnes.

Matrice augmentée

Elimination de Gauss Jordan (1/3)

On sait que les opérations suivantes sont possibles pour résoudre le système sans changer la solution :

• Interchanger 2 lignes.
• Multiplier une ligne par un scalaire non-nul.
• Ajouter un multiple d'une ligne à une autre.

Elimination de Gauss Jordan (2/3)

• On parcourt chaque colonne de :
  • Le pivôt est l'élément sur la diagonale dans cette colonne : .
  • On parcourt chaque ligne de sauf celle où se trouve le pivôt :
    • On calcule le coefficient multiplicateur .
    • On soustrait fois la ligne à la ligne .

Elimination de Gauss Jordan (3/3)

La solution est la dernière colonne dont chaque élément est divisé par le pivôt sur la même ligne.

Exemple

On considère, dans , le système suivant :

Sous forme matricielle

Matrice augmentée

Sous forme de tableau

Echange lig2 et lig3

Un pivôt ne peut pas être nul.

Dernière étape

Division de la dernière colonne par les pivôts

DM : Retours sur les fonctions et le débogage

Lien vers le sujet de DM.