TP : Plus de modules

Lien vers le sujet de DM.

Hiérarchie en entreprise

Structure produit

Compétition (1/2)

Il est possible d'inverser la représentation pour obtenir une hiérarchie.

Compétition (2/2)

Notion d'arbre

• Une hiérarchie peut être représentée sous la forme d'un arbre.
• Un arbre de recherche binaire (BST - binary search tree ) ne comporte que 2 branches.
• Chaque noeud peut avoir un sous-noeud à gauche et/ou à droite.

Exemple avec 2 noeuds

Exemple avec 3 noeuds

Relation d'ordre

• La valeur du noeud à gauche est plus petite que celle du parent.
• La valeur du noeud à droite est plus grande que celle du parent.

Exemple :

Structure de données

from dataclasses import dataclass
from typing import Any

@dataclass
class Noeud:
    """Noeud d'un arbre binaire."""
    valeur: Any = None
    gauche: Any = None
    droite: Any = None

Noeud de départ

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

Noeud de départ identifié par l'ArbreBinaire

Structure de données

from dataclasses import dataclass

@dataclass
class ArbreBinaire:
    """Arbre binaire."""
    noeud: Noeud = None

Exemple complet

Recherche : principe

• On part du noeud à la racine.
• On utilise la relation d'ordre pour savoir si on doit aller à gauche ou à droite.
• On descend dans l'arbre jusqu'à trouver la valeur ou ne plus avoir de descendants.

Illustration de la recherche

Valeur recherchée : 25

Etapes de recherche

Algorithme de recherche dans un arbre binaire

def trouve_valeur_dans_arbre_binaire(arbre, valeur):
    """Trouve une valeur dans l'arbre binaire."""
    noeud = arbre.noeud
    while noeud != None and noeud.valeur != valeur:
        if valeur < noeud.valeur:
            noeud = noeud.gauche
        else:
            noeud = noeud.droite

    return noeud

Complexité

• Le nombre d'étapes est fonction de la profondeur .
• Pour un arbre binaire équilibré de noeuds, la recherche prend .
• Pour un arbre binaire non-équilibré de noeuds, la recherche prend .

Insertion : principe

• Si le noeud racine est vide, la nouvelle valeur est positionnée à la racine.
• Sinon :
  • On utilise la relation d'ordre pour descendre dans l'arbre.
  • On créé un nouveau noeud dans un nouvel emplacement.

Illustration de l'insertion

Etapes d'insertion

Problème

Etapes arbre binaire non-équilibré

Arbre non-équilibré

• Si on insère toujours des valeurs à droite (ou à gauche), on obtient l'équivalent d'une liste chaînée.
• On perd alors l'équilibre de l'arbre, et la complexité d'insertion et de recherche augmente.
• La complexité passe de logarithmique à linéaire dans les 2 cas.

Solution : rééquilibrage

• Un arbre binaire rouge-noir (red-black binary search tree ) rééquilibre l'arbre à chaque insertion.
• Des rotations sont effectuées pour échanger des noeuds.

Illustration d'un arbre rouge-noir

Etapes d'insertion dans un arbre rouge-noir

Complexité

Dans un arbre rouge-noir, la recherche et l'insertion sont en .

Généralisation

• Les arbres binaires ont de nombreuses propriétés intéressantes (complexité logarithmique).
• Toute hiérarchie ne peut être représentée avec un arbre binaire.
• Les arbres n-aires peuvent avoir descendants.
• Les descendants peuvent être une list.

Illustration d'un arbre n-aire

Exemple avec une structure produit

TP : Arbres binaires

Lien vers le sujet de TP.

Trajet le plus rapide

Réseau

Réseau social

Graphe orienté (1/2)

• Un graphe orienté (directed graph ou digraph ) est caractérisé par :
  • un ensemble de sommets (vertices ou vertex ).
  • un ensemble d'arcs (edges ).

Graphe orienté (2/2)

• Chaque arc a une origine (source ) et un but (target ).
• On note , un arc d'origine et de but .
• est un successeur de .
• est un prédécesseur de .

Exemple de graphe orienté

Graphe non-orienté (1/2)

• Un graphe non-orienté (undirected graph ) ou graphe symétrique est caractérisé par :
  • un ensemble de sommets.
  • un ensemble d'arêtes.

Graphe non-orienté (2/2)

• Chaque arête a 2 extrémités (éventuellement confondues).
• Tout graphe orienté admet un graphe non-orienté sous-jacent.
• Le graphe sous-jacent est composé de l'ensemble des arêtes correspondant aux arcs du digraph.

Exemple de graphe non-orienté

Graphe partiel

• On peut restreindre un graphe (orienté ou non) à une partie de ses arcs ou arêtes.
• Il s'agit d'un graphe partiel.

Graphe orienté	: graphe partiel de

Graphe induit

• On peut restreindre un graphe (orienté ou non) à une partie de ses sommets.
• Il s'agit d'un graphe induit (ou sous-graphe).

Graphe orienté	: graphe induit de

Graphe simple

• Un graphe est dit simple s'il existe au plus un arc (ou arête) entre une origine et un but.
• Dans ce cas, un arc est noté .

Graphe orienté (non simple)	: graphe simple

Graphe antisymétrique

• Un graphe orienté simple est dit antisymétrique si, pour tout arc , il n'existe pas d'arc .

Graphe simple (non antisymétrique)	: graphe antisymétrique

Chemin

• Un chemin d'un graphe orienté est une suite d'arcs.
• L'origine d'un arc est le but de l'arc prédécédent.
• Le chemin désigne un chemin d'origine , de but et de longueur .

Chemin

Chemin simple

• Un chemin simple ne passe pas 2 fois par le même arc.

Chemin non simple	Chemin simple

Cycle (ou circuit)

• Dans un graphe orienté, un circuit est un chemin dont l'origine et le but sont confondus.
• Dans un graphe non-orienté, un cycle est un chemin dont l'origine et le but sont confondus.

Circuit	Cycle dans le graphe sous-jacent

Circuit élémentaire

• Un circuit est élémentaire s'il ne passe pas 2 fois par le même sommet (sauf l'origine et le but).

Circuit non élémentaire	Circuit élémentaire

Boucle

• Une boucle est un circuit composé d'un seul arc.

DAG (Directed Acyclic Graph )

• Un DAG est un graphe orienté sans circuit.
• Ce type de graphe est courant.

n'est pas un DAG	DAG

Fermeture transitive - définition (1/2)

• La fermeture transitive (ou clôture transitive) d'un graphe simple comporte les sommets et les arcs de . On y ajoute d'autres arcs.
• Pour tout couple de sommets et de , s'il existe un chemin entre et mais pas d'arc , alors on ajoute l'arc .

Fermeture transitive - exemple (2/2)

Graphe simple	Fermeture transitive

Graphe connexe

• Un graphe non-orienté est connexe s'il existe un chemin entre chaque couple de sommets de ce graphe.

Graphe non connexe	Graphe connexe

Composante connexe

• La composante connexe d'un sommet est l'ensemble des sommets qui lui sont reliés.

Graphe fortement connexe

• Un graphe orienté est fortement connexe s'il existe un chemin entre chaque couple de sommets de ce graphe.

Graphe non fortement connexe	Graphe fortement connexe

Composante fortement connexe

• La composante fortement connexe d'un sommet est l'ensemble des sommets tels qu'il existe un chemin de à , et un chemin de à .

Arbre

• En théorie des graphes, un arbre est un graphe non-orienté simple, connexe et sans cycle.
• Deux sommets quelconques ne sont reliés que par un unique chemin.
• Le nombre d'arcs est relié au nombre de sommets par la relation : .

Forêt

• Une fôret est un graphe non-orienté dont les composantes connexes sont des arbres.

Arborescence

• Une arborescence est un graphe orienté possédant un sommet privilégié, la racine.
• Il existe un unique chemin de la racine à tout autre sommet.
• La racine n'a pas de prédécesseur.
• Tout autre sommet a un unique prédécesseur : son parent.

Plusieurs représentations

• Il existe plusieurs manières de représenter un graphe en informatique.
• Chaque représentation a des avantages et des inconvénients.
• Un type de représentation ne convient pas à tous les types de graphes.

Liste de listes d'arcs (1/4)

• Le graphe orienté peut être caractérisé par une liste de sommets.
• Chaque sommet est caractérisé par une liste d'arcs et une éventuelle étiquette.

Liste de listes d'arcs (2/4)

• sommet 0 :
• sommet 1 : ,
• sommet 2 :
• sommet 3 : ,
• sommet 4 :

Liste de listes d'arcs (3/4)

G = [
    [1],      # 0 -> 1
    [3, 4],   # 1 -> 3, 1 -> 4
    [4],      # 2 -> 4
    [0, 2],   # 3 -> 0, 3 -> 2
    []        # aucun
]

Liste de listes d'arcs (4/4)

• Il est possible également de représenter un graphe non-orienté en dupliquant les arcs pour former les arêtes.
• Avantages : simplicité de mise à jour et de parcours.
• Inconvénients : difficulté d'obtention de la liste des prédécesseurs sans dupliquer les arcs (pour avoir les arcs "retour").

Matrice d'adjacence (1/6)

• Un graphe simple à sommets numérotés peut être représenté par une matrice carrée d'entiers.
• L'élément vaut 1 si l'arc existe, et 0 sinon.

Matrice d'adjacence (2/6)

Matrice d'adjacence (3/6)

Matrice d'adjacence (4/6)

M = [
    [0, 1, 0, 0, 0],
    [0, 0, 0, 1, 1],
    [0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0],
    [0, 0, 0, 0, 0]
]

Matrice d'adjacence (5/6)

• Si les arcs sont étiquettés, on peut utiliser ce type de représentation :

M = [
    [None,  "a", None, None, None],
    [None, None, None,  "b",  "c"],
    [None, None, None, None,  "e"],
    [ "f", None,  "g", None, None],
    [None, None, None, None, None]
]

Matrice d'adjacence (6/6)

• Avantages : représentation compacte, rapidité des recherches (notamment des prédécesseurs) et simplicité des algorithmes de calcul.
• Inconvénients : nombreux zéros dans la matrice (information "inutile"), redondance des informations pour les graphes non-orientés, ne convient que pour les graphes simples.

Matrice d'incidence (1/5)

• Un graphe non-orienté à sommets numérotés et arêtes numérotées peut être représenté par une matrice carrée d'entiers.
• L'élément vaut 1 si le sommet est l'une des 2 extrémités de l'arête , et 0 sinon.
• Une colonne de cette matrice comporte donc toujours deux éléments à 1 : les 2 extrémités de l'arête.

Matrice d'incidence (2/5)

Matrice d'incidence (3/5)

Matrice d'incidence (4/5)

M = [
    [1, 0, 0, 0, 1, 0],
    [1, 1, 1, 0, 0, 0],
    [0, 0, 0, 1, 0, 1],
    [0, 1, 0, 0, 1, 1],
    [0, 0, 1, 1, 0, 0]
]

Matrice d'incidence (5/5)

• Avantages : informations non redondantes pour les graphes non-orientés, représentation compacte, rapidité des recherches.
• Inconvénients : nombreux zéros dans la matrice (information "inutile"), certaines opérations matricielles ne s'appliquent pas.

Intérêt

• Tous les algorithmes d'analyse de graphes ont besoin de parcourir les graphes.
• Les algorithmes de parcours constituent le socle de ces algorithmes plus avancés.

Principe

• On parcourt chaque sommet du graphe.
• Les ordres de parcours dépendent de l'ordre des sommets et de l'ordre des successeurs de chaque sommet.
• Il existe 2 algorithmes principaux de parcours d'un graphe :
  • le parcours en profondeur,
  • le parcours en largeur.

Parcours en profondeur

• Le parcours en profondeur (DFS - Depth-First Search ) consiste à aller aussi profondément que possible dans le graphe à chaque étape.
• On visite le 1er successeur du 1er sommet, puis son 1er successeur, puis son 1er successeur, etc.
• On remonte ensuite la chaîne pour visiter le 2e successeur du dernier sommet visité, puis le 1er successeur de ce nouveau sommet, etc.

Exemple avec une arborescence

Ordre de visite : 0, 1, 4, 10, 11, 5, 6, 2, 7, 12, 13, 14, 3, 8, 9.

Exemple avec un graphe simple

Ordre de visite : 0, 1, 3, 2, 4.

Exemple avec un graphe non-connexe

Ordre de visite : 0, 3, 2, 7, 12, 11, 6, 13, 14, 9, 10, 8, 4, 1, 5, 11, 15, 16, 17, 18, 19.

Complexité

• Chaque sommet est visité.
• Or, les sommets déjà visités sont marqués pour ne pas être traités à nouveau.
• Donc chaque sommet est visité exactement 1 fois.
• Chaque arc d'origine est visité 1 fois.
• Dans le pire cas, le nombre maximal d'opérations sera limité soit par le nombre de sommets, soit par le nombre d'arcs.
• La complexité est donc , où est le nombre d'arc et est le nombre de sommets.

Parcours en largeur

• Le parcours en largeur (BFS - Breath-First Search) consiste à visiter d'abord tous les successeurs directs.
• Une fois que tous les successeurs directs ont été visités, on passe aux successeurs du 1er successeur, etc.

Exemple avec une arborescence

Ordre de visite : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14.

Exemple avec un graphe simple

Ordre de visite : 0, 1, 3, 4, 2.

Exemple avec un graphe non-connexe

Ordre de visite : 0, 3, 4, 2, 8, 9, 1, 5, 11, 7, 6, 12, 13, 14, 10, 15, 16, 18, 17, 19.

Complexité

• On parcourt chaque sommet exactement une fois.
• La complexité est en , où est le nombre d'arc et est le nombre de sommets.

Intérêt

• De nombreux algorithmes ne fonctionnent qu'avec des graphes acycliques.
• Il faut donc pouvoir identifier si un cycle existe avant d'utiliser de tels algorithmes.

Principe

• Pour identifier un cycle, on peut utiliser le parcours en profondeur.
• On ajoute un argument à la fonction récursive pour identifier le chemin courant.
• Si on cherche à revisiter un sommet dans ce chemin, on a identifier un cycle.
• Il ne reste plus qu'à retourner ce cycle.

Interface

def identifie_cycle(m):
    """Retourne le premier cycle identifié ou None."""
    marque = []
    for s in range(len(m)):
        cycle = identifie_cycle_dans_chemin(m, s, marque, [])
        if cycle != None:
            return cycle

    return None

Exemple

cycle = identifie_cycle(G)
print(cycle)

[0, 1, 3, 0]

Complexité

• La complexité est la même que pour le parcours en profondeur : .

Principe

• On associe un poids à chaque arc ou arête.
• Le poids est un nombre flottant.
• Le poids peut donc être positif ou négatif.
• Exemple :
  • un sommet peut représenter une ville,
  • une arête pondérée peut représenter le temps de trajet entre ces villes.

Liste de listes de listes (1/3)

• Pour un graphe non-pondéré, on pouvait utiliser une liste de listes.
• Chaque sous-liste représente les successeurs d'un sommet.
• Pour ajouter les poids, on ajoute une dimension.
• On obtient la hiérarchie suivante :
  • liste de sommets
    • liste de successeurs
      • liste des labels et poids

Liste de listes de listes (3/3)

• Avantages : évolution simple d'une représentation non-pondérée.
• Inconvénient : mêmes inconvénients qu'avec une liste de listes, plus difficile à comprendre et à maintenir.

Matrice d'adjacence (1/5)

• On peut représenter un graphe orienté valué à sommets avec une matrice carrée telle que a pour valeur le poids de l'arc si cet arc existe, ou sinon.

Matrice d'adjacence (2/5)

Matrice d'adjacence (3/5)

Matrice d'adjacence (4/5)

M = [
    [None,   42, None, None,  None],
    [None, None, None,   21, -56.7],
    [None, None, None, None,   7  ],
    [3.14, None,   -8, None,  None],
    [None, None, None, None,  None]
]

Matrice d'adjacence (5/5)

• Avantages : mêmes avantages qu'une matrice d'adjacence non-pondérée.
• Inconvénients : mêmes inconvénients qu'une matrice d'adjacence non-pondérée (mais pas d'inconvénient supplémentaire contrairement à la liste de listes de listes).

Structures de données (1/3)

@dataclass
class Sommet:
    """Sommet d'un graphe."""
    label: int = 0

@dataclass
class Arc:
    """Arc d'un graphe orienté"""
    origine: int = 0
    but: int = 0
    poids: float = 0.

@dataclass
class GraphePondere:
    """Graphe orienté pondéré."""
    sommets: List = field(default=list)
    arcs: List = field(default=list)

Structures de données (2/3)

s0 = Sommet(0)
s1 = Sommet(1)
s2 = Sommet(2)
s3 = Sommet(3)
s4 = Sommet(4)

a0 = Arc(origine=0, but=1, poids=42)
a1 = Arc(origine=1, but=3, poids=21)
a2 = Arc(origine=1, but=4, poids=-56.7)
a3 = Arc(origine=2, but=4, poids=7)
a4 = Arc(origine=3, but=2, poids=-8)
a5 = Arc(origine=3, but=0, poids=3.14)

G = GraphePondere(sommets=[s0, s1, s2, s3, s4],
                  arcs=[a0, a1, a2, a3, a4, a5])

Structures de données (3/3)

• Avantages : Les données sont plus structurées qu'avec une liste de liste de listes.
• Inconvénients : On a les mêmes inconvénients qu'avec une liste de listes.

Principe

• La recherche du chemin le plus court dans un graphe pondéré est un problème classique.
• Le poids d'un chemin est égal à la somme des poids des arcs sur ce chemin.
• Il existe différents algorithmes pour résoudre ce problème.
• Nous étudierons uniquement l'algorithme Bellman-Ford dans ce cours.

Bellman-Ford - principe (1/2)

• L'algorithme Bellman-Ford permet de construire un arbre des plus courts chemins (SPT - shortest path tree ).
• Cet algorithme considère les graphes orientés pondérés sans circuit négatif.

Bellman-Ford - principe (2/2)

• Cet algorithme part d'un sommet donné.
• Au départ, on évalue toutes les distances de aux autres sommets à l'infini.
• On effectue, sur le principe, un parcours en largeur pour réévaluer à chaque étape la distance minimale de à chaque autre sommet.
• L'implémentation suivante utilise une matrice d'adjacence.

Bellman-Ford - algorithme (1/4)

def adjacents(m, s):
    """Renvoie les arcs adjacents à s dans m."""
    adj = []
    for j in range(len(m[s])):
        if m[s][j] != None:
            adj.append(Arc(origine=s, but=j, poids=m[s][j]))

    return adj

Complexité

• La complexité de l'algorithme Bellman-Ford est en , où est le nombre d'arcs et le nombre de sommets.
• Cet algorithme est applicable dans de nombreux cas en pratique, sa complexité est correcte et son implémentation est relativement simple.
• L'algorithme de Dijkstra offre une meilleure complexité en , mais son implémentation implique souvent une queue de priorité, que nous n'avons pas abordé.

Problème d'ordonnancement

• Un problème d'ordonnancement simple est caractérisé par un ensemble de tâches à exécuter.
• Chaque tâche a une durée déterminée.
• Chaque tâche a des contraintes de précédence : pour exécuter une tâche, ses prédecesseurs doivent être exécutés préalablement.

Caractérisation des tâches

• Tâche critique : son exécution ne peut être allongée ou différée sans allonger la durée du projet.
• Marge libre d'une tâche : temps maximal dont cette tâche peut être allongée ou différée sans retarder le projet, indépendamment des autres tâches.

Méthode PERT (1/2)

• La méthode PERT (Project Evaluation and Review Technique ) utilise un DAG (graphe orienté acyclique) pour représenter et solutionner un problème d'ordonnancement.
• Le sommet début est à la racine du graphe.
• Le sommet fin marque la fin du projet.

Méthode PERT (2/2)

• Chaque tâche est représentée par un arc pondéré par la durée de la tâche.
• Les relations de précédences sont représentées par des arcs de poids nul.

Exemple (2/3)

Chemin critique

• Un chemin critique est un chemin de poids maximal allant de début à fin.
• Il peut y avoir plusieurs chemins critiques.
• Toute tâche sur un chemin critique est une tâche critique.
• Nous cherchons à trouver un chemin critique.

Exemple de chemin critique

Plus long chemin (1/2)

• Un chemin critique est donc un plus long chemin de début à fin.
• Il est possible d'utiliser un algorithme de plus court chemin pour calculer un plus long chemin.
• L'astuce consiste à créer un DAG équivalent avec des poids négatifs.
• Un poids de 2 devient donc un poids de -2 par exemple.

Plus long chemin (2/2)

• Avec des poids négatifs, le plus court chemin va trouver le plus long chemin en valeur absolue.
• Comme PERT utilise un DAG, on va pouvoir utiliser Bellman-Ford.
• En effet, un DAG ne contient pas de circuit et par conséquent, il ne contient pas de circuit négatif.

Exemple de plus long chemin

Exemple

c = chemin_critique(M)
print(c)

[0, 3, 6, 8, 10, 13, 14]

Complexité

• On utilise Bellman-Ford, et donc la complexité est similaire : , où est le nombre d'arcs et le nombre de sommets.

TP : Graphes

Lien vers le sujet de TP.