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

Do you want to read our courses in English? please visit our new website cs-teachers.com Click here

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

Télécharger l'énoncé

Exercice - Somme et factoriel

  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

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
    • 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. 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 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
 voisines (3, 0, R)
True
 voisines (3, 5, R)
False
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
  list_voisines (3, R)
[ 0 , 2 , 4 , 6 , 7 ]
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
                                    

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
 degre (3, R)
5
 degre (2, R)
4
Solution
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
 liste_degres (R)
[ (0 , 3) , (1 , 3) , (2 , 4) , (3 , 5) , (4 , 5) , ( 5, 3) , (6 , 4) , (7 , 3) ]
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
                                    

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
 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
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
 tri_villes (R)
[3,4,2,6,0,5,1,7]
Solution
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.

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

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
 premier_entier ( [ 0 , 0 , 3 , 1 , 0 , 1 , 0 , 0 ] )
2
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
                                    

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

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
 couleurs_villes (R)
[ 2 , 1 , 3 , 1 , 2 , 1 , 3 , 2 ]
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
                                    

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
 chemin_valide((2,0,1,4,3),R)
True
 chemin_valide((3,1,4,7,R)
False
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
                                    

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 un simple, sinon, la fonction renvoie False.
Exemple
 chemin_simple(( 2, 0, 1, 4, 3 ),R)
True
 chemin_simple(( 6, 7, 3, 4, 2, 3, 6, 5 ),R)
False
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
                                    

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

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

IV. 13- Calcule 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.(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

Partager ce cours avec tes amis :

Rédigé par ESSADDOUKI Mostafa

The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.

Commentaire(s)