Solution de l'épreuve d'informatique, CNC 2019 filières PSI et TSI

 Télécharger l'énoncé 

Problème - Réseau routier

Un réseau routier peut être représenté par un dessin qui se compose de points et de traits continus reliant deux à deux certains de ces points : les points sont les villes, et les lignes sont les routes. On considère que toutes les routes sont à double sens. Chaque route peut être affectée par une valeur qui peut représenter le temps ou la distance entre deux villes, ...

Partie 1 - Modélisation d'un réseau routier

On considère un réseau routier composé de n villes (avec n ≥ 2). Les villes du réseau routier sont numérotées par des entiers allant de 0 à n-1.

Pour plus de clarté, tous les exemples de ce problème seront appliqués sur le réseau routier de la figure 2.

I. 1- Représentation de la matrice du réseau routier en Python

Pour représenter la matrice symétrique R d'ordre n, on utilise une liste composée de n listes qui sont toutes de même longueur n.

Exemple

La matrice symétrique R, du réseau routier de la figure 2, est représentée par la liste R, composée de 8 listes, de taille 8 chacune :

R = [[0, 1, 1, 1, 0, 0, 0, 0],
     [1, 0, 1, 0, 1, 0, 0, 0],
     [1, 1, 0, 1, 1, 0, 0, 0],
     [1, 0, 1, 0, 1, 0, 1, 1],
     [0, 1, 1, 1, 0, 1, 1, 0],
     [0, 0, 0, 0, 1, 0, 1, 1],
     [0, 0, 0, 1, 1, 1, 0, 1],
     [0, 0, 0, 1, 0, 1, 1, 0]]

• À partir de la matrice symétrique R de la figure 2, donner les résultats des expressions suivantes : R[4][2] , R[1] , len(R[2]) , len(R)

  Solution

  • R[4][2] → 1
  • len(R[2]) → 8 : nombre de colonnes de la matrice
  • R[1] → [1, 0, 1, 0, 1, 0, 0, 0] : ligne 2 de la matrice
  • len(R) → 8 : nombre de lignes de la matrice

I. 2- Villes voisines

i et j sont deux villes dans un réseau routier représenté par une matrice symétrique R. Les villes i et j sont voisines, s'il existe une route entre la ville i et la ville j.

• 2. a- Écrire la fonction voisines(i,j,R), qui reçoit en paramètres deux villes i et j d'un réseau routier représenté par la matrice symétrique R. La fonction renvoie True si les villes i et j sont voisines, sinon, la fonction renvoie False.

  Exemple

  Résultat

  voisines(3, 0, R) → True
  voisines(3, 5, R) → False

  Solution

  
  

  Fonction voisines Python

  def voisines(i, j, R):
      # le graphique est représenté à l'aide d'une matrice d'adjacence
      # et nous savons que si la valeur (i, j) = 1, il y a une arête entre i et j
      # ce qui signifie que la ville i et la ville j sont adjacentes
      if R[i][j] == 1:
          return True
      return False

• 2. b- Écrire la fonction list_voisines(i,R), qui reçoit en paramètres une ville i d'un réseau routier représenté par la matrice symétrique R. La fonction renvoie la liste de toutes les villes voisines à la ville i.

  Exemple

  Résultat

  list_voisines(3, R) → [0, 2, 4, 6, 7]

  Solution

  
  

  Liste des voisines Python

  def list_voisines(i, R):
      # liste des villes voisines
      v = []
      # parcourir la ligne associée à la ville i
      for k in range(len(R[i])):
          if voisines(i, k, R):
              v.append(k)
      return v

I. 3- Degré d'une ville

Dans un réseau routier, le degré d'une ville i est le nombre de villes voisines à la ville i.

• 3- Écrire la fonction degre(i,R), qui reçoit en paramètres une ville i d'un réseau routier représenté par la matrice symétrique R. La fonction renvoie le degré de la ville i.

  Exemple

  Résultat

  degre(3, R) → 5
  degre(2, R) → 4

  Solution

  
  

  Degré d'une ville Python

  def degre(i, R):
      # le degré est la longueur de la liste des voisines
      v = list_voisines(i, R)
      return len(v)

I. 4- Liste des degrés des villes

• 4. Écrire la fonction liste_degres(R), qui reçoit en paramètre la matrice symétrique R représentant un réseau routier. La fonction renvoie une liste D contenant des tuples. Chaque tuple de D est composé de deux éléments : une ville du réseau routier, et le degré de cette ville.

  Exemple

  Résultat

  liste_degres(R) → [(0, 3), (1, 3), (2, 4), (3, 5), (4, 5), (5, 3), (6, 4), (7, 3)]

  Solution

  
  

  Liste des degrés Python

  def liste_degres(R):
      deg = []
      # pour chaque sommet (ville)
      for i in range(len(R)):
          # ajouter un tuple contenant la ville (i) et son degré
          deg.append((i, degre(i, R)))
      return deg

I. 5- Tri des villes

• 5. a- Écrire la fonction tri_degres(D), qui reçoit en paramètre la liste D des degrés des villes. La fonction trie les tuples de la liste D dans l'ordre décroissant des degrés des villes.

  Exemple

  Résultat

  tri_degres([(0,3), (1,3), (2,4), (3,5), (4,5), (5,3), (6,4), (7,3)])
  → [(3,5), (4,5), (2,4), (6,4), (0,3), (5,3), (1,3), (7,3)]

  Solution

  
  

  Tri des degrés Python

  def tri_degres(D):
      # Parcourir tous les éléments du tableau
      for i in range(len(D)):
          # Trouver l'élément maximum dans le tableau non trié restant
          max_idx = i
          for j in range(i+1, len(D)):
              # [1] : valeur de degré
              if D[max_idx][1] < D[j][1]:
                  max_idx = j
          # Échanger l'élément maximum trouvé avec le premier élément
          D[i], D[max_idx] = D[max_idx], D[i]

• 5. b- Écrire la fonction tri_villes(R), qui reçoit en paramètre la matrice symétrique R représentant un réseau routier. La fonction renvoie la liste des villes triées dans l'ordre décroissant des degrés des villes.

  Exemple

  Résultat

  tri_villes(R) → [3, 4, 2, 6, 0, 5, 1, 7]

  Solution

  
  

  Tri des villes Python

  def tri_villes(R):
      L = liste_degres(R)
      tri_degres(L)
      res = []
      for elm in L:
          res.append(elm[0])
      return res

Partie 2 - Coloration optimale des villes d'un réseau routier

Une coloration des villes du réseau routier est une affectation de couleurs à chaque ville, de façon à ce que deux villes voisines soient affectées par deux couleurs différentes. Le nombre minimum de couleurs nécessaires pour colorier un réseau routier est appelé : nombre chromatique.

On cherche à construire une liste C qui contiendra les couleurs des villes. Ces couleurs seront représentés par des entiers strictement positifs : chaque élément C[k] contiendra la couleur de la ville k du réseau routier.

Pour construire la liste C des couleurs, on propose d'utiliser un algorithme, appelé : algorithme de glouton. C'est un algorithme couramment utilisé dans la résolution de ce genre de problèmes, afin d'obtenir des solutions optimales.

II. 6- Premier entier qui n'existe pas dans une liste d'entiers

• 6- Écrire la fonction premier_entier(L), qui reçoit en paramètre une liste L de nombres entiers positifs. La fonction renvoie le premier entier positif qui n'appartient pas à la liste L.

  Exemple

  Résultat

  premier_entier([0, 0, 3, 1, 0, 1, 0, 0]) → 2

  Solution

  
  

  Premier entier manquant Python

  def premier_entier(L):
      # obtenir l'élément maximum dans L
      maximum = max(L)
      for i in range(1, maximum):
          # si i n'est pas présent dans L, retourner i
          if i not in L:
              return i
      # sinon retourner maximum+1
      return maximum+1

II. 7- Liste des couleurs des villes voisines à une ville

• 7- Écrire la fonction couleurs_voisines(k,C,R), qui reçoit en paramètres une ville k d'un réseau routier représenté par la matrice symétrique R, et la liste C des couleurs des villes du réseau. La fonction renvoie la liste des C[i] telle que i est une ville voisine à la ville k.

  Exemple

  Résultat

  couleurs_voisines(4, [0,0,0,1,0,0,0,0], R) → [0, 0, 1, 0, 0]
  couleurs_voisines(0, [0,0,3,1,2,0,3,0], R) → [0, 3, 1]

  Solution

  
  

  Couleurs des voisines Python

  def couleurs_voisines(k, C, R):
      # Couleurs des voisines de la ville k
      v = []
      # parcourir la ligne associée à la ville k
      for i in range(len(C)):
          # Si les villes i et k sont voisines
          # ajouter la couleur de i dans v
          if voisines(k, i, R):
              v.append(C[i])
      return v

II. 8- Coloration des villes

• 8- Écrire la fonction couleurs_villes(R), qui reçoit en paramètre la matrice symétrique R représentant un réseau routier. La fonction renvoie la liste C des couleurs des villes, en utilisant le principe de glouton cité ci-dessus.

  Exemple

  Résultat

  couleurs_villes(R) → [2, 1, 3, 1, 2, 1, 3, 2]

  Solution

  
  

  Coloration gloutonne Python

  def couleurs_villes(R):
      C = [0] * len(R)
      # parcourir toutes les villes
      for i in range(len(R)):
          # obtenir la couleur des voisins de la ville i
          v = couleurs_voisines(i, C, R)
          # obtenir la première couleur possible
          col = premier_entier(v)
          # colorier la ville i avec col
          C[i] = col
      return C

Partie 3 - Chemins dans un réseau routier

III. 9- Chemin entre deux villes

Dans un réseau routier, un chemin est un tuple T qui contient des villes du réseau, et qui satisfait les deux conditions suivantes :

• Le tuple T contient au moins deux villes du réseau routier ;
• Deux villes consécutives dans T sont voisines.

• 9- Écrire la fonction chemin_valide(T,R), qui reçoit en paramètres un tuple T contenant des villes du réseau routier représenté par la matrice symétrique R. La fonction renvoie True si le tuple T satisfait les deux conditions c1 et c2 citées ci-dessus, sinon, la fonction renvoie False.

  Exemple

  Résultat

  chemin_valide((2,0,1,4,3), R) → True
  chemin_valide((3,1,4,7), R) → False

  Solution

  
  

  Chemin valide Python

  def chemin_valide(T, R):
      # Si la longueur < 2, retourner False
      if len(T) < 2:
          return False
      # du deuxième élément jusqu'à la fin
      for i in range(1, len(T)):
          # vérifier si la ville actuelle et la ville précédente ne sont pas voisines
          if voisines(T[i-1], T[i], R) == False:
              return False
      # Sinon retourner True
      return True

III. 10- Chemin simple entre deux villes

Dans un réseau routier, un chemin simple est un chemin qui passe une seule fois par la même ville.

• 10- Écrire la fonction chemin_simple(T,R), qui reçoit en paramètres un chemin T dans un réseau routier représenté par la matrice symétrique R. La fonction renvoie True si le chemin T est simple, sinon, la fonction renvoie False.

  Exemple

  Résultat

  chemin_simple((2,0,1,4,3), R) → True
  chemin_simple((6,7,3,4,2,3,6,5), R) → False

  Solution

  
  

  Chemin simple Python

  def chemin_simple(T, R):
      # Si le chemin T n'est pas valide, retourner False
      if chemin_valide(T, R) == False:
          return False
      # Tableau pour compter le nombre d'occurrences de chaque ville dans le chemin
      v = [0]*len(R)
      for i in range(len(T)):
          # augmenter le nombre d'occurrences de la ville i
          v[T[i]] += 1
          # si le nombre d'occurrences de la ville i est supérieur à 1, retourner False
          if v[T[i]] > 1:
              return False
      # Sinon retourner True, chemin valide
      return True

III. 11- Plus court chemin entre deux villes

On suppose que la fonction liste_chemins(i,j,R), reçoit en paramètres deux villes i et j d'un réseau routier représenté par la matrice symétrique R. Cette fonction renvoie une liste qui contient tous les chemins simples entre la ville i et la ville j.

Le plus court chemin entre une ville i et une ville j est un chemin simple entre la ville i et la ville j, et qui traverse le moins de villes.
NB : On peut trouver plusieurs plus courts chemins entre deux villes.

• 11- Écrire la fonction pc_chemins(i,j,R), qui reçoit en paramètres deux villes i et j d'un réseau routier représenté par la matrice symétrique R. Cette fonction renvoie la liste de tous les plus courts chemins entre la ville i et la ville j.

  Exemple

  Résultat

  pc_chemins(0, 7, R) → [(0, 3, 7)]
  pc_chemins(7, 1, R) → [(7, 3, 0, 1), (7, 3, 2, 1), (7, 3, 4, 1), (7, 5, 4, 1), (7, 6, 4, 1)]

  Solution

  
  

  Liste des chemins (BFS) Python

  def liste_chemins(i, j, R):
      # l'idée ici est d'utiliser le parcours en largeur
      # Liste des chemins
      L = []
      # Créer une file d'attente qui stockera les chemins
      file = []
      # initialiser la file d'attente avec le premier chemin à partir de source i
      file.append([i])
      # Tant qu'il y a un chemin
      while file:
          # Récupérer le premier chemin de la file d'attente
          path = file.pop(0)
          # Récupérer le dernier sommet du chemin
          dernier = path[-1]
          # Un chemin est trouvé
          if dernier == j:
              # ajouter ce chemin à L (convertir la liste vers un tuple)
              L.append(tuple(path))
          # parcourir les voisines de "dernier"
          for voisine in list_voisines(dernier, R):
              # si la voisine n'est pas sur le chemin
              if voisine not in path:
                  # créer un nouveau chemin à partir du chemin précédent
                  nouveau_chemin = list(path)
                  # ajouter le sommet "voisine" dans le nouveau chemin
                  nouveau_chemin.append(voisine)
                  # insérer ce nouveau chemin dans la file d'attente
                  file.append(nouveau_chemin)
      # retourner la liste des chemins
      return L
  
  def pc_chemins(i, j, R):
      chemins = liste_chemins(i, j, R)
      # Créer un tableau, dans lequel chaque élément représenté par un tuple
      # contient l'indice du chemin et sa longueur
      L = []
      for k in range(len(chemins)):
          L.append((k, len(chemins[k])))
      # Trier la liste
      tri_degres(L)
      # liste des chemins les plus courts
      short = []
      # ajouter le premier élément
      short.append(chemins[L[0][0]])
      # vérifier s'il y a d'autres chemins avec la même longueur que le premier
      for k in range(1, len(L)):
          if L[k][1] == L[0][1]:
              short.append(chemins[L[k][0]])
          else:
              break
      return short

Partie 4 - Calcul du nombre de chemins entre deux villes

Dans cette partie, on considère que le module numpy est importé :

from numpy import *

On suppose que le réseau routier est représenté par la matrice symétrique R, et que la matrice R est créée par la méthode array() du module numpy.

Exemple

R = array([[0, 1, 1, 1, 0, 0, 0, 0], 
           [1, 0, 1, 0, 1, 0, 0, 0], 
           [1, 1, 0, 1, 1, 0, 0, 0], 
           [1, 0, 1, 0, 1, 0, 1, 1], 
           [0, 1, 1, 1, 0, 1, 1, 0], 
           [0, 0, 0, 0, 1, 0, 1, 1], 
           [0, 0, 0, 1, 1, 1, 0, 1], 
           [0, 0, 0, 1, 0, 1, 1, 0]])

Dans cette partie, on propose de résoudre le problème suivant :

• Soit p un entier strictement positif.
• Quel est le nombre de chemins (simples ou non) entre une ville i et une ville j, passant exactement par p routes ?

Par exemple, dans le réseau routier de la figure 2, pour aller de la ville 1 à la ville 3, en passant exactement par 5 routes, on peut trouver plusieurs chemins, dont voici quelques uns :

(1,4,5,7,6,3) , (1,4,6,5,4,3) , (1,2,3,4,2,3) , (1,0,2,0,2,3)

Pour résoudre ce problème, on doit procéder ainsi :

• Calculer la matrice \(M = R^p\) (matrice symétrique R élevée à la puissance p)
• Chaque élément M[i][j] représente le nombre de chemins, entre la ville i et la ville j, passant par p routes ;
• La matrice M est symétrique aussi. Le nombre de chemins, entre la ville i et la ville j, est le même que celui entre la ville j et la ville i.

Exemple

Par exemple, entre la ville 1 et la ville 7 :

• Il y a 0 chemins qui passent exactement par deux routes (dans la matrice \(M = R^2\)) ;
• Il y a 5 chemins qui passent exactement par trois routes (dans la matrice \(M = R^3\)).

IV. 12- Produit matriciel

On considère la matrice A, de m lignes et n colonnes, et la matrice B de n lignes et p colonnes. En effectuant le produit matriciel de A et B, on obtient la matrice C de m lignes et p colonnes, sachant que les coefficients de la matrice C sont calculés par la formule suivante : \[ \forall i,j : c_{i,j} = \sum_{k=0}^{n-1} a_{ik} \times b_{kj} \]

• 12. Écrire la fonction produit_matriciel(A,B), qui reçoit en paramètres deux matrices symétriques A et B, de même dimension. La fonction calcule et renvoie une nouvelle matrice symétrique C, qui contient le produit matriciel de A et B. La fonction doit économiser le temps de calcul, en calculant une seule fois les coefficients symétriques dans la matrice C.

  Solution

  
  

  Produit matriciel optimisé Python

  def produit_matriciel(A, B):
      n = len(A)
      C = zeros((n, n))
      # boucler sur la matrice triangulaire supérieure
      for i in range(n):
          for j in range(i, n):
              s = 0
              for k in range(n):
                  s += A[i][k] * B[k][j]
              # Parce que la matrice est symétrique, alors
              # C[i][j] et C[j][i] ont la même valeur
              C[i][j] = C[j][i] = s
      return C

IV. 13- Calcul de la puissance par 'exponentiation rapide'

Lorsqu'il s'agit d'une matrice carrée, le calcul de la puissance devient crucial. L'exponentiation rapide est un algorithme qui permet de minimiser le nombre de multiplications effectuées dans le calcul de la puissance.
Pour calculer \(x^n\), le principe de l'exponentiation rapide est le suivant :

• Si n=1, alors \(x^n = x\)
• Si n est pair, alors \(x^n = (x^2)^{n/2}\)
• Si n est impair alors, \(x^n = x \times (x^2)^{(n-1)/2}\)

• 13- Écrire la fonction puissance(R,n), reçoit en paramètres la matrice symétrique R représentant un réseau routier, et un entier strictement positif n. En utilisant le principe de l'exponentiation rapide, la fonction calcule et renvoie la matrice \(R^n\).

  Solution

  
  

  Exponentiation rapide Python

  def puissance(R, n):
      if n == 1:
          return R
      elif n % 2 == 0:
          return puissance(produit_matriciel(R, R), n//2)
      else:
          return produit_matriciel(R, puissance(produit_matriciel(R, R), (n-1)//2))