1A - Enoncé 5 novembre 2025 - comptabilité schtroumph¶

Correction de l’examen du 5 novembre 2025.

Toutes les questions valent 2 points.

Q1 - Implémenter une fonction qui calcule la distance entre deux matrices¶

[32]:

import numpy as np


def distance(table1, table2):
    return np.abs(table1 - table2).sum()


table1 = np.array([[8, 7], [18, 18], [6, 8]])
table2 = np.array([[18, 18], [7, 9], [8, 6]])
distance(table1, table2)

[32]:

np.int64(45)

Le minimum serait…

[33]:

distance(np.array([[18, 18], [7, 8], [8, 6]]), table2)

[33]:

np.int64(1)

Et sinon une petite erreur en oubliant la permutation sur les colonnes.

[35]:

distance(np.array([[18, 18], [8, 7], [6, 8]]), table2)

[35]:

np.int64(7)

Q2 - Implémenter une fonction qui retourne les p ermutations des n premiers entiers¶

[2]:

import itertools

def permutations(n):
    return list(itertools.permutations(list(range(n))))

permutations(4)

[2]:

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

Q3, Q4 - Implémenter une fonction qui p ermute les colonnes d’une matrice.¶

[3]:

def permute_ligne_ou_colonne(table, permutation, axis):
    if axis == 0:
        if len(table.shape) == 2:
            return table[permutation, :]
        return table[list(permutation)]
    return table[:, permutation]


permute_ligne_ou_colonne(table1, [2, 1, 0], axis=0)

[3]:

array([[ 6,  8],
       [18, 18],
       [ 8,  7]])

Q5 - Ecrire une fonctionne qui retourne les deux p ermutations ligne/colonne qui minimise la distance entre les deux matrices, en déduire la case qui a changé.¶

[4]:

def optimise(table1, table2):
    best = None
    for p1 in permutations(table1.shape[0]):
        for p2 in permutations(table1.shape[1]):
            t = permute_ligne_ou_colonne(permute_ligne_ou_colonne(table1, p1, 0), p2, 1)
            d = distance(t, table2)
            if best is None or d < best:
                best = d
                perms = p1, p2
    return perms


optimise(table1, table2)

[4]:

((1, 0, 2), (1, 0))

Q6 - Quel est le coût de cette fonction ?¶

Si $i$ et $j$ sont les dimensions de deux tables, c’est $O((i!)(j!))$ .

Q7 - C’est beaucoup trop long.¶

On prop ose que calculer chaque p ermutation séparément. On cherche donc la meilleure p ermutation qui minimise la distribution de la somme par ligne et par colonne entre les deux matrices. Ecrire une fonctionne qui implémente ce raisonnement.

[37]:

def optimise_vecteur(vec1, vec2):
    best = None
    for p1 in permutations(vec1.shape[0]):
        t = permute_ligne_ou_colonne(vec1, p1, 0)
        d = distance(t, vec2)
        if best is None or d < best:
            best = d
            perm = p1
    return perm


def optimise_fast(table1, table2):
    return (
        optimise_vecteur(table1.sum(axis=1), table2.sum(axis=1)),
        optimise_vecteur(table1.sum(axis=0), table2.sum(axis=0)),
    )


optimise_fast(table1, table2)

[37]:

((1, 0, 2), (0, 1))

Le coût est en $O(i!) + O(j!)$ . Pas nécessairement optimal mais beaucoup plus rapide. On obtient la distance :

[38]:

p1, p2 = optimise_fast(table1, table2)
distance(table1[p1, :][:, p2], table2)

[38]:

np.int64(7)

Q8 - Mais c’est encore trop coûteux.¶

On cherche la matrice M qui minimise AM =B où A et B sont les sommes sur les colonnes où lignes des matrices de statistiques observées sur deux années.

Précisons d’abord ce qu’est une matrice de permutations $M$ : une matrice carrée dont les coefficients sont 0 ou 1. De plus, sur chaque ligne et chaque colonne, on ne trouve qu’un et un seul 1.

[39]:

M = np.array([[0, 1, 0], [0, 0, 1], [1, 0, 0]])
A = np.arange(6).reshape((3, -1))
print("A")
print(A)
print("M")
print(M)
print("M @ A")
print(M @ A)

A
[[0 1]
 [2 3]
 [4 5]]
M
[[0 1 0]
 [0 0 1]
 [1 0 0]]
M @ A
[[2 3]
 [4 5]
 [0 1]]

$MA$ permute les lignes, $AM$ permute les colonnes. Donc trouver la matrice $M$ qui minimise $\lVert AM - B \rVert^2$ où $B$ obtenue avec une permutation des colonnes de la matrice $A$ permettrait de déterminer cette permutation. Ce n’est pas un système d’équations en bonne et due forme mais c’en est un.

[40]:

M, _, rang, _ = np.linalg.lstsq(table1, table2)
print(M)
print("rang", rang)

[[ 1.76711027  2.68346008]
 [-1.00760456 -1.85931559]]
rang 2

Le problème est qu’il y a plus d’inconnues que d’équations, d’où le rang faible (2). Avant de revenir à cette option. On part dans une autre direction. La plus grande des catégories de populations a beaucoup de chance d’être la plus grande l’année suivante. Donc la recherche du maximum dans les matrices A et B dévoile une partie de la matrice M. On applique cette idée aux sommes des lignes et des colonnes.

[42]:

def optimise_vecteur_tri(vec1, vec2):
    # on tri dans l'ordre croissant
    pos_vec1 = sorted([(v, i) for i, v in enumerate(vec1)])
    pos_vec2 = sorted([(v, i) for i, v in enumerate(vec2)])
    # on a deux permutations, il suffit de les composer.
    p1 = list(p[1] for p in pos_vec1)
    p2 = list(p[1] for p in pos_vec2)
    p = [p1[p2[i]] for i in range(len(p1))]
    return tuple(p)


def optimise_fast_tri(table1, table2):
    return (
        optimise_vecteur_tri(table1.sum(axis=1), table2.sum(axis=1)),
        optimise_vecteur_tri(table1.sum(axis=0), table2.sum(axis=0)),
    )


table1 = np.array([[8, 7], [18, 18], [6, 8]])
table2 = np.array([[18, 18], [7, 9], [8, 6]])
p1, p2 = optimise_fast_tri(table1, table2)
p1, p2, distance(table1[p1, :][:, p2], table2)

[42]:

((1, 0, 2), (0, 1), np.int64(7))

On revient au problème d’optimisation : $\lVert AM - B \rVert^2$ . Il faudrait pouvoir forcer les coefficients de la matrice à être 0 ou 1 en ajoutant une contrainte. On utilise pour cela fonction $f(x)=x(1-X)$ qui vaut 0 quand $x \epsilon \{0,1\}$ . On cherche donc $M$ qui minimise $\lVert AM - B \rVert^2 + \lambda \lVert M^2*(1-M)^2\rVert$ où * est une multiplication terme à terme. Mais résoudre ce problème n’est pas simple. On en restera là pour le moment.

Q9 - Comment utiliser cette fonction pour implémenter une version plus rapide de la fonction à la question 5.¶

Le code de la question précédente répond à la question.

Q10 - La troisième année, une colonne est coupée en deux : une catégorie est divisée en deux sous-catégorie. Que proposez-vous pour y remédier ?¶

L’idée est assez simple, on choisit au hasard deux lignes de la seconde matrice et on les aggrège. On utilise la fonction précédente pour en déduire les deux permutations les moins coûteuses puis on conserve le coût de cette permutation. On fait de même pour toutes les paires et on ne garde que la meilleure paire.

Ce n’était pas demandé dans l’énoncé mais on pourait implémenter ce schéma comme suit :

[45]:

def optimise_fast_tri_paire(table1, table2):
    best = None
    for i in range(table2.shape[0] - 1):
        for j in range(i + 1, table2.shape[0]):
            table2p = np.zeros(table1.shape, dtype=table2.dtype)
            table2p[:, :] = table2[:-1, :]
            table2p[i, :] += table2[j, :]
            p1, p2 = optimise_fast_tri(table1, table2p)
            t = table1[p1, :][:, p2]
            d = distance(t, table2p)
            if best is None or d < best[0]:
                best = d, p1, p2, (i, j)
    return best


table1 = np.array([[8, 7], [18, 18], [6, 8]])
# on divise par deux les deux valeurs de la dernière ligne
# et on les réplique
table2 = np.array([[18, 18], [7, 9], [4, 3], [4, 3]])
optimise_fast_tri_paire(table1, table2)

[45]:

(np.int64(7), (1, 0, 2), (0, 1), (2, 3))

Tout est cohérent.

Notebook on github