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

Télécharger l'énoncé

1. Écrire la fonction factoriel(k) qui reçoit en paramètre un entier positif k et qui renvoie la valeurdufactoriel de k: \(k!=1*2*3*...*k\).
   

   Solution

   def factoriel(k):
       f = 1
       for i in range(2, k+1):
           f *= i
       return f
                                               

2. Déterminer la complexité de la fonction factoriel (k), et justifier votre réponse.
   

   Solution

   la compléxité est \(O(k)\), parce que nous bouclons jusqu'à k, et à l'intérieur de la boucle, nous n'avons que des opérations élémentaires avec un coût \(O(1)\)

3. Écrire la fonction som_fact(L) qui reçoit en paramètre une liste L de nombres entiers positifs. La fonction renvoie la somme des factoriels des éléments de L.
   

   Exemple

    som_fact ([ 5, 3, 0, 6, 1 ]))
   848

   Solution

   def som_fact(L):
       s = 0
       for elm in L:
           s += factoriel(elm)
       return s
                                               

4. Déterminer la complexité de la fonction som_fact (L), et justifier votre réponse.
   

   Solution

   \(O(n*k)\), parce que nous bouclons sur tous les éléments, et à l'intérieur de la boucle, nous appelons les fonctions "factoriel" qui a un coût \(O(k)\) chacune

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, ...

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.

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

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

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 vaille 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

Solution

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

Solution

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
                                    

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

Solution

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

• 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

Solution

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

    return deg
                                    

• 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

Solution

def tri_degres(D):
    # Parcourez tous les éléments du tableau
    for i in range(len(D)):
        # Trouver l'élément minimum dans le tableau non trié restant
        min_idx = i
        for j in range(i+1, len(D)):
            # [1] : valeur de degré
            if D[min_idx][1] < D[j][1]:
                min_idx = j

        # Échanger l'élément minimum trouvé avec le premier élément
        D[i], D[min_idx] = D[min_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

Solution

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

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.

Principe de l’algorithme de glouton :

•   V est la liste des villes triées dans l’ordre décroissant des degrés des villes
•   C est une liste de même taille que V, initialisée par des 0
•   Pour toute ville k de V :
  C[k]première couleur non utilisée par les villes voisines à la ville k
•   Retourner la liste C

• 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

Solution

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
                                    

• 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

Solution

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 voisines
        # ajouter la couleur de i dans v
        if voisines(k, i, R):
            v.append(C[i])
    return v
                                    

• 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

Solution

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)

        # colorie la ville i avec col
        C[i] = col
    return C
                                    

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

Solution

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
        # arrêter et retourner False
        if voisines(T[i-1], T[i], R) == False:
            return False

    # Sinon retourner True
    return True
                                    

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 un simple, sinon, la fonction renvoie False.

Exemple

Solution

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
                                    

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

Solution

def liste_chemins(i, j, R):
    # l'idée ici est d'utiliser le parcours en largeur

    # Liste des chemins
    L = []

    # Créez 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:
        # Recupérer le premier chemin de la file d'attente
        path = file.pop(0)

        # Recupé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éez un tableau, dans lequel chaque élément représenté par un tuple
    # contient l'indice du chemin et sa longueur
    L = []
    for i in range(len(chemins)):
        L.append((i, len(chemins[i])))

    # Trier la liste
    tri_degres(L)

    # liste des chemins les plus courts
    short = []

    # ajouter le premier élément
    short = [chemins[L[-1][0]]]

    # # vérifier s'il y a un autre chemin avec la même longueur que le premier
    for i in range(len(L)-2, -1, -1):
        if L[i][1] == L[i+1][1]:
            short.append(chemins[L[i][0]])

        # Sinon quitter
        else:
            break

    return short
                                    

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\)).

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}*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

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
                                    

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.(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

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))
                                    

Télécharger la correction