FE-FFichiers, enregistrements et matrices

Matrice : produit, transposée, matrice stochastique et tableau stable

Idée directrice

Un calcul sur des matrices se ramène à des boucles imbriquées dont on fixe exactement le rôle : deux boucles choisissent la case du résultat, une troisième fait la somme, avec un accumulateur remis à 0 pour chaque case. Une propriété vraie « pour tous les éléments » (coefficients dans [0, 1], lignes de somme 1, égalité de deux tableaux, symétrie) se vérifie par un parcours qui s'arrête au premier contre-exemple. Et un module de haut niveau (tableau stable, produit, transposition) réutilise les modules déjà écrits au lieu de refaire leurs calculs.

Ce qui aide à reconnaître la démarche

« On se propose de générer une matrice … sachant que les éléments de cette matrice sont calculés comme suit » ; « … est dite stochastique … » ; « Un tableau T … est dit stable pour … » ; « Struct2[j, i] ← Struct1[i, j] » ; « Quelle est la déclaration valide de X ? » ; « Les lignes sont remplies jusqu'à la diagonale principale »

Besoin d’un point de départ ? Voir la méthode

Déclarer le type à la taille maximale (Mat = Tableau de 20 lignes et 20 colonnes de Réels) et, pour un vecteur, Tab = Tableau de 20 Réels.
Somme ou produit : pour chaque case du résultat, s ← 0, puis la boucle de sommation, puis l'affectation de la case.
Vérification « pour tout » : un booléen dans la condition des boucles Tant que, ou un parcours jusqu'à la première différence suivi du test sur le dernier élément examiné.
Comparer des réels à une précision fixée (Abs(a − b) ≤ 10⁻⁶) plutôt que par une égalité stricte.
Réutiliser les modules : Stable = Produit + Egalite ; Symetrique ne compare que les cases situées au-dessus de la diagonale.

Les pièges à vérifier dans ta démarche

Placer s ← 0 hors de la boucle qui choisit la case, ce qui fait cumuler les sommes. Inverser les indices du produit (M[j, i] au lieu de M[i, j]). Tester seulement la somme de chaque ligne sans vérifier que chaque élément est dans [0, 1]. Comparer des réels avec =. Parcourir toute la matrice alors qu'on peut s'arrêter au premier contre-exemple. Transposer sur place avec deux boucles complètes, ce qui échange chaque paire deux fois. Remplir une ligne de la droite vers la gauche alors qu'une case dépend de sa voisine de gauche.

Sujet principal

Exercice — matrices (5 points), dans l'esprit des sessions 2020–2026

6 questionsCorrigé masqué

Une ville gère trois stations de vélos en libre-service, numérotées 0, 1 et 2. Chaque nuit, les vélos sont redistribués : on note M[i, j] la proportion des vélos de la station i qui se retrouvent le lendemain à la station j. On obtient ainsi une matrice carrée M de dimension n × n (ici n = 3).

Une matrice carrée M de réels est dite stochastique lorsque chacun de ses éléments appartient à l'intervalle [0, 1] et que la somme des éléments de chaque ligne est égale à 1.

Si T[i] est le nombre de vélos de la station i un jour donné, le nombre de vélos de la station j le lendemain est P[j], où P est le produit du tableau T par la matrice M :

P[j] = \sum_{i=0}^{n-1} T[i] \times M[i, j]

Le tableau T est dit stable pour M lorsque P = T : la répartition des vélos ne change plus d'un jour à l'autre.

Exemple : pour la matrice M et le tableau T suivants :

i \ j	0	1	2
0	0,7	0,2	0,1
1	0,1	0,7	0,2
2	0,3	0,2	0,5

j	0	1	2
T[j]	110	120	70

Travail demandé :

Déclarer le type Mat d'une matrice carrée de 20 × 20 réels au plus et le type Tab d'un tableau de 20 réels.
Écrire l'algorithme d'une fonction Stochastique(M, n) qui vérifie si M est stochastique. Le parcours doit s'arrêter dès qu'une condition n'est pas respectée.
Écrire l'algorithme d'une procédure Produit(T, M, n, P) qui calcule le tableau P, produit de T par M.
Écrire l'algorithme d'une fonction Egalite(P, T, n) qui vérifie si les tableaux P et T sont égaux, en s'arrêtant à la première différence.
En faisant appel à Produit et à Egalite, écrire l'algorithme d'une fonction Stable(M, n, T) qui vérifie si T est stable pour M, la matrice M étant supposée stochastique.
Traces d'exécution.
1. Vérifier que la matrice M de l'exemple est stochastique, puis calculer P pour le tableau T de l'exemple. T est-il stable ?
2. Calculer P pour T = (100, 100, 100). Ce tableau est-il stable ?
3. On remplace M par la matrice M' dont les lignes sont (0,6 ; 0,3 ; 0,1), (0,4 ; 0,7 ; −0,1) et (0,2 ; 0,2 ; 0,6). Sur quelle ligne et pour quelle raison la fonction Stochastique s'arrête-t-elle ?

NB : M, n et T sont saisis dans le programme appelant. Chaque algorithme est accompagné du tableau de déclaration de ses objets locaux.

Voir la correction commentéeAprès avoir posé votre démarche

Nouveaux types
Mat = Tableau de 20 lignes et 20 colonnes de Réels
Tab = Tableau de 20 Réels

2. Idée : une propriété « pour tous les éléments » se vérifie par un parcours qui s'arrête au premier contre-exemple : un booléen ok contrôle les deux boucles Tant que. La somme d'une ligne n'est testée qu'une fois la ligne entièrement parcourue.

Fonction Stochastique (M : Mat, n : Entier) : Booléen
DEBUT
    ok ← Vrai
    i ← 0
    Tant que ok Et (i < n) Faire
        s ← 0
        j ← 0
        Tant que ok Et (j < n) Faire
            Si (M[i, j] < 0) Ou (M[i, j] > 1) Alors
                ok ← Faux
            Sinon
                s ← s + M[i, j]
                j ← j + 1
            Fin Si
        Fin Tant que
        Si ok Et (Abs (s - 1) > 0.000001) Alors
            ok ← Faux
        Fin Si
        i ← i + 1
    Fin Tant que
    Retourner ok
FIN

Objet	Type / Nature	Rôle
ok	Booléen	Vrai tant que aucune condition n'est violée
i, j	Entier	Indices de ligne et de colonne
s	Réel	Somme des éléments de la ligne i

Le corrigé officiel de la session de contrôle 2022 écrit le test de la somme s = 1. En machine, les réels sont arrondis : avec des réels en virgule flottante, 0,7 + 0,2 + 0,1 donne 0,9999999999999999, et le test s = 1 rejetterait la première ligne de l'exemple. On compare donc à une précision fixée, Abs(s − 1) ≤ 10⁻⁶.

3. Idée : P[j] est une somme sur i ; l'accumulateur est remis à 0 pour chaque j, c'est-à-dire pour chaque case de P.

Procédure Produit (T : Tab, M : Mat, n : Entier, @ P : Tab)
DEBUT
    Pour j de 0 à n - 1 Faire
        x ← 0
        Pour i de 0 à n - 1 Faire
            x ← x + T[i] * M[i, j]
        Fin Pour
        P[j] ← x
    Fin Pour
FIN

Objet	Type / Nature	Rôle
i, j	Entier	Indices
x	Réel	Somme en cours pour la case j

4. Idée : même schéma d'arrêt anticipé : on avance tant que les éléments sont égaux, puis on retourne le test sur le dernier élément examiné.

Fonction Egalite (P, T : Tab, n : Entier) : Booléen
DEBUT
    i ← 0
    Tant que (i < n - 1) Et (Abs (P[i] - T[i]) ≤ 0.000001) Faire
        i ← i + 1
    Fin Tant que
    Retourner Abs (P[i] - T[i]) ≤ 0.000001
FIN

Objet	Type / Nature	Rôle
i	Entier	Indice de parcours

5. Idée : Stable ne recalcule rien elle-même ; elle enchaîne les deux modules. P est un objet local.

Fonction Stable (M : Mat, n : Entier, T : Tab) : Booléen
DEBUT
    Produit (T, M, n, P)
    Retourner Egalite (P, T, n)
FIN

Objet	Type / Nature	Rôle
P	Tab	Produit de T par M
Produit	Procédure	Calculer P
Egalite	Fonction	Comparer P et T

6.a Idée : on vérifie ligne par ligne, puis on calcule P colonne par colonne de M. Tous les éléments de M sont dans [0, 1], et chaque ligne a pour somme 1 : 0,7 + 0,2 + 0,1 = 0,1 + 0,7 + 0,2 = 0,3 + 0,2 + 0,5 = 1. M est stochastique.

P[0] = 110 × 0,7 + 120 × 0,1 + 70 × 0,3 = 110

P[1] = 110 × 0,2 + 120 × 0,7 + 70 × 0,2 = 120

P[2] = 110 × 0,1 + 120 × 0,2 + 70 × 0,5 = 70

P = (110 ; 120 ; 70) = T : T est stable pour M. Les 300 vélos se redistribuent chaque nuit sans que le nombre de vélos de chaque station change.

6.b Avec T = (100, 100, 100), P[j] vaut 100 fois la somme de la colonne j de M : P = (110 ; 110 ; 80) ≠ T. Egalite s'arrête dès la première case (i = 0), puisque P[0] = 110 ≠ 100 : ce tableau n'est pas stable. Le nombre total de vélos reste 300, mais ils ne sont pas répartis de façon stable.

6.c La ligne 0 de M' est correcte : ses éléments sont dans [0, 1] et 0,6 + 0,3 + 0,1 = 1. Sur la ligne 1, l'élément M'[1, 2] = −0,1 est négatif : ok devient Faux et le parcours s'arrête, la ligne 2 n'étant jamais examinée. Pourtant 0,4 + 0,7 − 0,1 = 1 : tester seulement les sommes des lignes ne suffit pas.

Changer d’énoncé, garder le raisonnement

Choisis un seul transfert après le sujet principal. Qu’est-ce qui change ? Quel résultat ou quelle méthode peux-tu réutiliser ? Les autres exercices restent disponibles pour une prochaine séance.

Variantes rencontrées : matrice remplie ligne par ligne par la somme des derniers éléments de la ligne précédente (contrôle 2015) ; sommes des diagonales avec propagation des retenues (principale 2018) ; produit de deux matrices M₁ × M₂ (contrôle 2020) ; procédure de transposition Struct2[j, i] ← Struct1[i, j] à analyser par des questions V/F sur le type X, les paramètres et le rôle (contrôle 2021) ; matrice stochastique et tableau stable (contrôle 2022) ; triangle de Pascal rempli jusqu'à la diagonale puis parcouru selon ses diagonales ascendantes (principale 2026).

Exercices d'entraînement — une nuance à la fois

1 Drill FE-F.1 — produit de deux matrices : un accumulateur remis à 0 pour chaque case

Entraînement 01 / 03

Drill FE-F.1 — produit de deux matrices : un accumulateur remis à 0 pour chaque case

5 questionsCorrigé masqué

Soient A une matrice de n × m entiers et B une matrice de m × p entiers (n, m et p de l'intervalle [2, 30]). On se propose de calculer la matrice Pr de n × p entiers définie, pour 0 ≤ i ≤ n − 1 et 0 ≤ j ≤ p − 1, par :

Pr[i, j] = \sum_{k=0}^{m-1} A[i, k] \times B[k, j]

Exemple : pour n = 2, m = 3, p = 2 et les matrices suivantes :

A :

i \ j	0	1	2
0	2	-1	3
1	0	4	1

B :

i \ j	0	1
0	1	5
1	2	0
2	-3	2

Travail demandé :

Déclarer le type Mat commun aux trois matrices, de 30 × 30 entiers au plus.
Pourquoi le nombre de colonnes de A doit-il être égal au nombre de lignes de B ?
Écrire l'algorithme d'une procédure Prod_Mat(A, B, Pr, n, m, p) qui calcule Pr.
Donner la matrice Pr de l'exemple, en détaillant le calcul de Pr[0, 0].
Un élève place l'instruction s ← 0 juste après Pour i de 0 à n - 1 Faire, au lieu de la placer juste avant Pour k de 0 à m - 1 Faire. Quelle matrice obtient-il pour l'exemple ?

NB : A, B, n, m et p sont saisis dans le programme appelant.

Voir la correction commentéeAprès avoir posé votre démarche

1. Mat = Tableau de 30 lignes et 30 colonnes d'Entiers.

2. Pr[i, j] associe la ligne i de A, qui a m éléments, à la colonne j de B, qui en a autant que B a de lignes : le produit terme à terme n'a de sens que si ces deux nombres sont égaux.

3. Idée : trois boucles imbriquées. Les deux premières choisissent la case (i, j) de Pr ; la troisième fait la somme sur k, avec un accumulateur remis à 0 pour chaque case.

Procédure Prod_Mat (A, B : Mat, @ Pr : Mat, n, m, p : Entier)
DEBUT
    Pour i de 0 à n - 1 Faire
        Pour j de 0 à p - 1 Faire
            s ← 0
            Pour k de 0 à m - 1 Faire
                s ← s + A[i, k] * B[k, j]
            Fin Pour
            Pr[i, j] ← s
        Fin Pour
    Fin Pour
FIN

Objet	Type / Nature	Rôle
i, j, k	Entier	Indices
s	Entier	Somme en cours pour la case (i, j)

4. Pr[0, 0] = 2 × 1 + (−1) × 2 + 3 × (−3) = 2 − 2 − 9 = −9.

i \ j	0	1
0	-9	16
1	5	2

5. Idée : avec s ← 0 au début de chaque ligne, la somme de Pr[i, 0] n'est pas effacée avant le calcul de Pr[i, 1]. Pr[0, 1] reçoit −9 + 16 = 7 au lieu de 16, et Pr[1, 1] reçoit 5 + 2 = 7 au lieu de 2 :

i \ j	0	1
0	-9	7
1	5	7

Seule la première colonne est juste : c'est le symptôme d'un accumulateur mal placé.

2 Drill FE-F.2 — transposée : Tr[j, i] ← A[i, j], matrice symétrique et transposition sur place

Entraînement 02 / 03

Drill FE-F.2 — transposée : Tr[j, i] ← A[i, j], matrice symétrique et transposition sur place

5 questionsCorrigé masqué

La transposée d'une matrice A de L lignes et C colonnes est la matrice Tr de C lignes et L colonnes telle que Tr[j, i] = A[i, j]. Une matrice carrée A d'ordre n est dite symétrique si elle est égale à sa transposée, c'est-à-dire si A[i, j] = A[j, i] pour tous i et j. Les matrices sont de type Mat (tableau de 10 lignes et 10 colonnes d'entiers) ; leurs lignes et leurs colonnes sont numérotées à partir de 0.

Pour transposer une matrice carrée A sur place, sans seconde matrice, un élève écrit la séquence suivante :

Pour i de 0 à n - 1 Faire
    Pour j de 0 à n - 1 Faire
        x ← A[i, j]
        A[i, j] ← A[j, i]
        A[j, i] ← x
    Fin Pour
Fin Pour

Travail demandé :

Écrire l'algorithme d'une procédure Transposer(A, L, C, Tr), puis donner Tr pour la matrice A de 2 lignes (1, 2, 3) et (4, 5, 6).
Écrire l'algorithme d'une fonction Symetrique(A, n) qui compare chaque élément situé au-dessus de la diagonale à son symétrique et s'arrête à la première différence.
Pour A1 de lignes (2, 7, 1), (7, 0, 5), (1, 5, 3), puis pour A2 de lignes (2, 7, 1), (7, 0, 5), (4, 5, 3), donner le résultat de Symetrique et le nombre de comparaisons effectuées.
Donner le contenu de A après la séquence de l'élève pour la matrice de lignes (1, 2, 3), (4, 5, 6), (7, 8, 9), et expliquer le résultat.
Corriger la séquence de l'élève.

Voir la correction commentéeAprès avoir posé votre démarche

1. Idée : on parcourt A et on range chaque élément à la place obtenue en échangeant ses deux indices ; Tr a C lignes et L colonnes.

Procédure Transposer (A : Mat, L, C : Entier, @ Tr : Mat)
DEBUT
    Pour i de 0 à L - 1 Faire
        Pour j de 0 à C - 1 Faire
            Tr[j, i] ← A[i, j]
        Fin Pour
    Fin Pour
FIN

Tr a 3 lignes et 2 colonnes :

i \ j	0	1
0	1	4
1	2	5
2	3	6

2. Idée : A[i, j] = A[j, i] est automatique sur la diagonale, et comparer (i, j) puis (j, i) ferait deux fois le même test : on ne parcourt que j > i.

Fonction Symetrique (A : Mat, n : Entier) : Booléen
DEBUT
    ok ← Vrai
    i ← 0
    Tant que ok Et (i < n - 1) Faire
        j ← i + 1
        Tant que ok Et (j < n) Faire
            Si A[i, j] ≠ A[j, i] Alors
                ok ← Faux
            Fin Si
            j ← j + 1
        Fin Tant que
        i ← i + 1
    Fin Tant que
    Retourner ok
FIN

Objet	Type / Nature	Rôle
ok	Booléen	Vrai tant que aucune différence n'est trouvée
i, j	Entier	Indices

3. A1 : les paires (0, 1), (0, 2) et (1, 2) sont égales : Symetrique retourne Vrai après 3 comparaisons. A2 : A2[0, 1] = A2[1, 0] = 7, puis A2[0, 2] = 1 ≠ A2[2, 0] = 4 : Symetrique retourne Faux après 2 comparaisons.

4. Idée : chaque paire (i, j), (j, i) avec i ≠ j est rencontrée deux fois par la double boucle complète : une fois pour (i, j), une fois pour (j, i). Elle est donc échangée deux fois, ce qui la remet en place. A reste inchangée :

i \ j	0	1	2
0	1	2	3
1	4	5	6
2	7	8	9

5. On n'échange que les éléments situés au-dessus de la diagonale, en remplaçant la seconde boucle par Pour j de i + 1 à n - 1 Faire. On obtient bien la transposée :

i \ j	0	1	2
0	1	4	7
1	2	5	8
2	3	6	9

3 Drill FE-F.3 — remplir une matrice ligne par ligne par une règle : le triangle de Bell

Entraînement 03 / 03

Drill FE-F.3 — remplir une matrice ligne par ligne par une règle : le triangle de Bell

7 questionsCorrigé masqué

On remplit une matrice carrée M d'entiers, ligne par ligne, jusqu'à la diagonale principale (colonnes 0 à i pour la ligne i), selon la règle suivante :

M[0, 0] = 1 ;
pour i ≥ 1, le premier élément de la ligne i est le dernier élément de la ligne précédente : M[i, 0] = M[i − 1, i − 1] ;
pour i ≥ 1 et 1 ≤ j ≤ i : M[i, j] = M[i, j − 1] + M[i − 1, j − 1].

Les nombres de la colonne 0 sont appelés nombres de Bell.

Travail demandé :

Donner les cinq premières lignes de M (lignes 0 à 4).
Écrire l'algorithme d'une procédure Bell(M, N) qui remplit les N premières lignes de M (2 ≤ N ≤ 15).
Expliquer pourquoi, dans la ligne i, les éléments doivent être calculés de la gauche vers la droite.
Écrire l'algorithme d'une procédure Nombres(M, N, B) qui remplit un tableau B par les N premiers nombres de Bell, puis donner B pour N = 6.

NB : M est de type Mat (tableau de 15 lignes et 15 colonnes d'entiers), B est de type Tab (tableau de 15 entiers) et N est saisi dans le programme appelant.

Voir la correction commentéeAprès avoir posé votre démarche

1. Idée : chaque ligne commence par le dernier élément de la ligne au-dessus, puis chaque élément est la somme de son voisin de gauche et de l'élément situé au-dessus de ce voisin. Par exemple, M[3, 2] = M[3, 1] + M[2, 1] = 7 + 3 = 10.

1
1 2
2 3 5
5 7 10 15
15 20 27 37 52

2. Idée : la case M[0, 0] est fixée à part ; pour les lignes suivantes, la première case vient de la ligne précédente et les autres se calculent par la règle, pour j de 1 à i.

Procédure Bell (@ M : Mat, N : Entier)
DEBUT
    M[0, 0] ← 1
    Pour i de 1 à N - 1 Faire
        M[i, 0] ← M[i - 1, i - 1]
        Pour j de 1 à i Faire
            M[i, j] ← M[i, j - 1] + M[i - 1, j - 1]
        Fin Pour
    Fin Pour
FIN

Objet	Type / Nature	Rôle
i, j	Entier	Indices de ligne et de colonne

3. M[i, j] utilise M[i, j − 1], l'élément situé à sa gauche dans la même ligne : cet élément doit donc être déjà calculé. Parcourir la ligne de droite à gauche lirait des cases encore vides. Dans le triangle de Pascal, au contraire, chaque case ne dépend que de la ligne précédente, et l'ordre de parcours de la ligne est indifférent.

Procédure Nombres (M : Mat, N : Entier, @ B : Tab)
DEBUT
    Pour i de 0 à N - 1 Faire
        B[i] ← M[i, 0]
    Fin Pour
FIN

Pour N = 6, M doit contenir six lignes ; la ligne 5 commence par M[4, 4] = 52. B = (1, 1, 2, 5, 15, 52).

Relier ce raisonnement au bac

Choisis une filière pour voir les sujets qui étayent ce scénario.

Tu écris. Tu continues.

Où veux-tu aller ?

Matrice : produit, transposée, matrice stochastique et tableau stable

Exercice — matrices (5 points), dans l'esprit des sessions 2020–2026

Changer d’énoncé, garder le raisonnement

Exercices d'entraînement — une nuance à la fois

Drill FE-F.1 — produit de deux matrices : un accumulateur remis à 0 pour chaque case

Drill FE-F.2 — transposée : Tr[j, i] ← A[i, j], matrice symétrique et transposition sur place

Drill FE-F.3 — remplir une matrice ligne par ligne par une règle : le triangle de Bell

Relier ce raisonnement au bac