Réseaux, tris et graphes

Graphes : implémentation et parcours¶

Tous les graphes considérés dans cet exercice seront des graphes orientés, dont les sommets sont des entiers numérotés de \(0\) à \(n - 1\) pour un certain entier \(n \in \mathbb{N}^{*}\) (\(n\) est alors appelé l'ordre du graphe).

On peut implémenter ces types de graphes à l'aide d'une liste d'adjacence adj. On stocke à l'indice i de adj la liste des successeurs du sommet i dans le graphe. On donne ci-dessous le code d'une classe Graphe dont le constructeur Graphe prend en argument un entier n et créé un graphe d'ordre n, initialement sans aucun arc.

class Graphe:
    def __init__(self, n):
        """ Graphe, int -> Nonetype """
        self.ordre = n
        self.adj = [[] for _ in range(n)]

    def sommets(self):
        """ Graphe -> [int]
        Renvoie la liste des sommets du graphe """
        return [i for i in range(self.ordre)]

    def voisins(self, s):
        """ Graphe, int -> [int]
        Renvoie la liste triée des successeurs du sommet s """
        return sorted(self.adj[s])

    def ajoute_arc(self, source, destination):
        """ Graphe, int, int -> Nonetype
        Ajoute l'arc source -> destination """
        self.adj[source].append(destination)

    def decrire(self):
        """ Graphe -> Nonetype
        Affiche une description informelle du graphe self """
        print(f"Graphe d'ordre {self.ordre}")
        for sommet in self.sommets():
            decrire_voisins = " ".join([str(s)
                                        for s in self.voisins(sommet)])
            print(f"Sommet {sommet} -> " + decrire_voisins)

La variable g de type Graphe représente le graphe \(G\) ci-dessous.

print(g.adj)    

[[1, 2], [2], [0], [0]]

Donner les instructions python permettant d'instancier une variable g de type Graphe correspondant au graphe \(G\) et d'ajouter les arcs issus du sommet 0.

On considérera dans la suite de l'exercice que la variable g décrit complètement et correctement le graphe \(G\) :
1
g.decrire()
```
Graphe d'ordre 4
Sommet 0 -> 1 2
Sommet 1 -> 2
Sommet 2 -> 0
Sommet 3 -> 0
```

Écrire une méthode degre de la classe Graphe qui étant donné un sommet s du graphe self renvoie le nombre de successeurs de s dans le graphe self.

def degre(self, s):
    """ Graphe, int -> int
    Renvoie le degré (sortant) du sommet s """
    pass

for s in [0, 1, 2, 3]:
    print(g.degre(s), end=' ')          

2 1 1 1

Écrire une méthode degre_max de la classe Graphe qui renvoie le maximum des degrés (sortants) des sommets du graphe self (suposé non vide).

def degre_max(self):
    """ Graphe -> int
    Renvoie le maximum des degrés (sortants) des sommets du graphe """
    pass

print(g.degre_max())          

Compléter le code de la méthode matrice de la classe Graphe qui renvoie la matrice d'adjacence du graphe self. On rappelle que si \(G\) est un graphe orienté d'ordre \(n\), la matrice d'adjacence du graphe \(G\) est la matrice de taille \(n\times n\) dont le coefficient \((i, j)\) vaut True si et seulement si \(j\) est un successeur de \(i\) dans le graphe \(G\).

def matrice(self):
    """ Graphe -> [[int]]
    Renvoie la matrice d'adjacence du graphe self """
    # mat est une matrice de taille n × n (où n = self.ordre)
    mat = [[False for i in range(self.ordre)]
            for j in range(self.ordre)]
    # À compléter

for ligne in g.matrice():
    print(ligne)

[False, True, True, False]
[False, False, True, False]
[True, False, False, False]
[True, False, False, False]

4. La variable gp de type Graphe représente le graphe \(G'\) ci-dessous.

Graphe d'ordre 9
Sommet 0 -> 5 7
Sommet 1 -> 8
Sommet 2 -> 4 5 6
Sommet 3 -> 
Sommet 4 -> 
Sommet 5 -> 1 2 6 8
Sommet 6 -> 2
Sommet 7 -> 3 6
Sommet 8 ->

On donne le code python de la fonction parcours1.

 def parcours1(G, depart, vus):
     """ Graphe, Sommet, [Sommet] -> [Sommet] """
     vus.append(depart)
     for destination in G.voisins(depart):
         if not destination in vus:
             parcours1(G, destination, vus)
     return vus

À quel type de parcours de graphe cela correspond-t-il ? Déterminer l'affichage réalisé par l'instruction print(parcours1(gp, 0, [])).

Un élève un peu maladroit écrit la fonction parcours2 suivante.

def parcours2(G, depart):
    """ Graphe, int, [int] -> [int] """
    vus = []
    à_explorer = []
    à_explorer.append(depart)
    while len(à_explorer) > 0:
        sommet = à_explorer.pop()
        vus.append(sommet)
        for destination in reversed(G.voisins(sommet)):
            if not destination in vus:
                à_explorer.append(destination)
    return vus

print(parcours3(gp, 0))    

[0, 5, 1, 8, 2, 4, 6, 6, 8, 7, 3]

Quel type de parcours l'élève tente-t-il d'implémenter ?

Que constate-t-on ? Comment corriger ce problème ?

Donner la liste des sommets visités (ordonnée par ordre de visite) obtenue lors d'un parcours en largeur du graphe \(G'\) depuis le sommet \(0\).

Algorithmes de tri¶

On pourra utiliser dans cet exercice sans justification supplémentaire les fonctions permettant de manipuler les listes : creer_vide, est_vide, est_singleton, tete, queue, ajoute. On rappelle que l'instruction ajoute(l, x) renvoie sans effet de bord une liste dont le premier élément est x suivit de la liste des éléments de l.

La fonction récursive fusionner écrite en TP est incorrecte. Écrire une fonction récursive fusionner qui étant donné deux listes l1 et l2 toutes les deux triées par ordre croissant renvoie correctement une liste l dont les éléments sont ceux de l1 et l2 triés par ordre croissant.

def fusionner(l1, l2):
    """ Liste, Liste -> Liste
    l1 et l2 sont triées par ordre croissant
    Renvoie la liste des éléments de l1 et l2 triés par ordre croissant """

affiche(l3)
affiche(l4)
affiche(fusionner(l3, l4))

1 - 3 - x
5 - 6 - x
1 - 3 - 5 - 6 - x

le tri rapide ou tri pivot (en anglais quicksort) est un algorithme de tri inventé par C.A.R. Hoare en 19613 et fondé sur la méthode de conception diviser pour régner. On peut en résumer le principe avec l'image suivante :

Diviser :: choisir un élément dit seuil au hasard dans la liste. On divise la liste l en deux listes : la liste l1 des éléments de l qui sont inférieurs ou égaux à seuil, la liste l2 des éléments de l qui sont supérieurs strictement à seuil.
Régner :: trier récursivement les listes l1 et l2 en des listes l1_triee et l2_triee.
Combiner :: fusionner les éléments de l1_triee, l2_triee et seuil en une liste triée.

Précisions. Afin de simplifier l'écriture des fonctions implémentant le tri rapide, on utilisera les simplifications suivantes :

dans cet exercice, seuil ne sera pas choisit de manière aléatoire. On prendra toujours le premier élément de la liste l comme seuil.
comme seuil est le premier élément de la liste l, on divisera directement la queue de l lors de l'étape "divison" du tri rapide.
La liste l est la liste \((5, 1, 9, 4, 3, 5, 6)\).
1. Expliquer pourquoi l'opération de division produit les listes \(l_1 = (1, 4, 3, 5)\) et \(l_2 = (9, 6)\).
2. Donner les listes \(l_1'\) et \(l_2'\) obtenues à la fin de l'étape "régner".
3. En déduire la liste \(l\) obtenue à la fin de l'étape "combiner".

Écrire une fonction diviser qui étant donné une liste l et un entier seuil, renvoie deux listes l1 et l2 de telle sorte que les éléments de l1 sont les éléments de l inférieurs ou égaux à seuil, les éléments de l2 sont les éléments de l strictement supérieurs à seuil.

On pourra au choix écrire une fonction itérative ou bien compléter le code de la fonction récursive diviser ci-dessous:

def diviser(l, seuil):
    """ Liste, int -> Liste, Liste
    Diviser la liste l en deux listes :
    - l1 (éléments y de l tels que y <= seuil)
    - l2 (éléments y de l tels que y > seuil) """
    if ...:
        return ...
    else:
        l1, l2 = diviser(queue(l), seuil)
        if ...:
            return ...
        else:
            return ...

affiche(l2)          
l21, l22 = diviser(l2, 3)
affiche(l21)
affiche(l22)

3 - 3 - 1 - 8 - 5 - 2 - 0 - x
3 - 3 - 1 - 2 - 0 - x
8 - 5 - x

Écrire une fonction combiner qui étant donné un entier x, une liste l1 (supposée triée et dont tous les éléments sont inférieurs ou égaux à x), une liste l2 (supposée triée et dont tous les éléments sont strictement supérieurs à x) renvoie la liste triée dont les éléments sont, ceux de l1, x, et ceux de l2.

On pourra au choix écrire une fonction itérative ou bien compléter le code de la fonction récursive combiner ci-dessous:

def combiner(l1, x, l2):
    """ Liste, int, Liste -> Liste
    l1 est triée, y <= x pour tout y appartenant à l1
    l2 est triée, x < y pour tout y appartenant à l2
    Renvoie une liste triée constituée des éléments de
    la liste l1, de ceux la liste l2 et de l'élément x """
    if est_vide(l1):
        return ...
    else:
        reste = combiner(queue(l1), x, l2)
        return ...

affiche(l5)          
affiche(l6)          
affiche(combiner(l5, 5, l6))

1 - 3 - 4 - 5 - x
6 - 9 - x
1 - 3 - 4 - 5 - 5 - 6 - 9 - x

Écrire une fonction tri_rapide qui trie récursivement la liste l de la manière suivante :
- si l est la liste vide ou la liste constituée d'un seul élément on renvoie l ;
- on divise la liste queue(l) en deux listes l1 et l2 en choisissant comme seuil tete(l) ;
- on trie récursivement l1 et l2 en des listes l1_triee et l2_triee ;
- on combine les listes l1_triee, l2_triee, l'élément tete(l) et on renvoie le résultat.
1 2 3 4
def tri_rapide(l): """ Liste -> Liste Trie la liste l """ pass
1 2
affiche(l) affiche(tri_rapide(l))
```
5 - 1 - 9 - 4 - 3 - 5 - 6 - x
1 - 3 - 4 - 5 - 5 - 6 - 9 - x
```
Dresser l'arbre d'appel de l'instruction tri_rapide(l) lorsque l est la liste \((5, 1, 9, 4, 3, 5, 6)\). On n'indiquera que les appels récursifs à tri_rapide que l'on abrègera en tr. Les valeurs de retour seront indiquées en rouge sur l'arbre.
On admet que la fonction diviser effectue \(n\) opérations élémentaires lorsque l est constituée de \(n\) éléments. On admet que combiner effectue dans le pire des cas \(n_1\) opérations élémentaires lorsque la liste l1 est constituée de \(n_1\) éléments (ce nombre ne dépend pas de la taille de la liste l2).
1. Comment appelle-t-on la complexité de la fonction diviser ?
2. Dans le pire des cas, la fonction tri_fusion à une complexité quadratique en la taille de la liste l. Donner sans justifier un exemple de liste l pour laquelle l'instruction tri_fusion réalise un nombre d'opérations élémentaires de l'ordre de \(n^2\), lorsque l est constituée de \(n\) éléments.
  
  Indication. On pourra chercher une liste l de telle sorte que l'on effectue un maximum d'appels dans le pire des cas de la fonction combiner. Un point bonus sera attribué si vous parvenez à expliquer votre réponse à l'aide d'un arbre d'appel.
3. Lorsque l est une liste contituée de \(n\) éléments, l'instruction tri_rapide(l) réalise "en moyenne" un nombre de l'ordre de \(n\log_2(n)\) opérations élémentaires. Comment appelle-t-on la complexité "en moyenne" de la fonction tri_rapide ?

Protocoles réseaux¶

Les adresses IP sont composées de 4 octets, soit 32 bits. Elles sont notées X1.X2.X3.X4, où X1, X2, X3 et X4 sont les valeurs des 4 octets, convertis en notation décimale. La notation X1.X2.X3.X4/n signifie que les \(n\) premiers bits de poids fort de l'adresse IP représentent la partie "réseau", les bits suivants représentent la partie "hôte".

On représente ci-dessous un réseau dans lequel \(R1\), \(R2\), \(R3\), \(R4\), \(R5\) et \(R6\) sont des routeurs. Le réseau local \(L1\) est relié au routeur \(R1\) et le réseau local \(L2\) est relié au routeur \(R6\). Par exemple le routeur \(R1\) appartient au réseau \(112.44.65.0/24\) et l'adresse de son interface sur ce réseau est \(112.44.65.32\).

On donne également des extraits de la table de routage des routeurs \(R1\) à \(R5\) dans le tableau suivant.

Un paquet part du réseau local \(L1\) à destination du réseau local \(L2\).
1. En utilisant l'extrait de la table de routage de \(R1\), vers quel routeur \(R1\) envoie-t-il ce paquet : \(R2\) ou \(R3\) ? Justifier.
2. À l'aide des extraits de tables de routage ci-dessus, nommer les routeurs traversés par ce paquet, lorsqu'il va du réseau \(L1\) au réseau \(L2\).
La liaison entre \(R1\) et \(R2\) est rompue.
1. Sachant que le réseau utilise le protocole RIP (distance en nombre de sauts) pour configurer les tables de routage, donner les deux chemins possibles que pourra suivre un paquet allant de \(L1\) vers \(L2\).
2. Dans les extraits de tables de routage ci-dessus, quelle(s) ligne(s) seront modifiées ? Préciser comment.
On a rétabli la liaison entre \(R1\) et \(R2\).

Pour tenir compte du débit des liaisons, on décide d'utiliser le protocole OSPF (distance liée au coût des liaisons), pour déterminer les tables de routage. Le coût des liaisons entre les routeurs est donné ci-dessous :
- \(R1-R2\) : 100
- \(R1-R3\) : 100
- \(R2-R4\) : 1
- \(R2-R5\) : 10
- \(R2-R6\) : 10
- \(R3-R4\) : 10
- \(R4-R5\) : 1
- \(R4-R6\) : 10
- \(R5-R6\) : 1
- Le coût \(C\) d'une liaison est donné ici par la formule \(C = \dfrac{10^9}{BP}\), où \(BP\) est la bande passante de la connexion en bps (bit par seconde). Sachant que la bande passante de la laison \(R2-R3\) est de 10Mbps, calculer le coût correspondant. Quelle est la bande passante de la laison \(R2-R4\) ?
- Donner sans justifier le chemin parcouru par un paquet partant du réseau \(L1\) et arrivant au réseau \(L2\), en utilisant le protocole \(OSPF\). Préciser le coût de ce chemin.