Optimiser la note moyenne

Un professeur cherche à optimiser la note moyenne de son examen. Son barème est le suivant pour ses 10 questions : [ 1, 1, 1, 2, 2, 2, 3, 3, 3, 4]. Il est seulement possible de permuter les points associés au dix questions. Pour chaque question et chaque étudiant, la réponse est soit fausse, soit bonne.

La classe Bereme

import numpy


class Bareme:
    def __init__(self, bareme=None):
        self.bareme = numpy.array(bareme or [1, 1, 1, 2, 2, 2, 3, 3, 3, 4])

    def __str__(self):
        # facultatif: juste pour print(bareme)
        return f"Bareme: {self.bareme}"

    def __len__(self):
        # facultatif: retourne le nombre de questions
        # bareme = Bareme() .... len(bareme) --> appelle Bareme.__len__
        return len(self.bareme)

    def mean(self, classe):
        # Pour écrire ceci :
        # bareme = Bareme()
        # classe = [Eleve(n_questions=len(bareme)) for i in range(100)]
        # moyenne = bareme.mean(classe)
        # Cette fonction est nécessaire pour vérifier que l'optimisation a fonctionné.
        notes = [e.note(self) for e in classe]
        return sum(notes) / len(classe)


b = Bareme()
b.bareme

array([1, 1, 1, 2, 2, 2, 3, 3, 3, 4])

La classe Eleve

class Eleve:
    def __init__(self, notes=None, n_questions=None):
        if notes is None:
            # on tire des notes au hasard
            self.notes = numpy.random.randint(0, 2, n_questions)
        else:
            self.notes = numpy.array(notes)

    def __str__(self):
        return f"Eleve: {self.notes}"

    def note(self, b):
        return (self.notes * b.bareme).sum() / b.bareme.sum()


eleve = Eleve(n_questions=len(b))
print(eleve)
print(eleve.note(b))

Eleve: [1 0 1 1 0 0 0 1 1 0]
0.45454545454545453

Une classe

bareme = Bareme()
classe = [Eleve(n_questions=len(bareme)) for i in range(100)]
moyenne = bareme.mean(classe)
moyenne

0.5050000000000003

Une barème optimisé

On pourrait tester toutes les permutations. C’est la version gloutonne. Mais elle prendrait trop de temps. On part sur une intuition : il faut associer le plus grand nombre de points à la question à laquelle les étudiants ont le mieux répondu. On procède de même pour les autres questions. Il faut trier les questions par ordre croissant des taux de réponses.

class BaremeOpt(Bareme):
    def optimize(self, classe):
        matrice_notes = numpy.array([e.notes for e in classe])
        v = matrice_notes.sum(axis=0)
        els_pos = list((v, i) for i, v in enumerate(v))
        els_pos.sort()
        perm = [tu[1] for tu in els_pos]
        b = self.bareme.copy()
        for i, p in enumerate(perm):
            self.bareme[i] = b[p]

bareme = BaremeOpt()
classe = [Eleve(n_questions=len(bareme)) for i in range(100)]
print(f"moyenne avant optimisation: {bareme.mean(classe)}")
bareme.optimize(classe)
print(f"moyenne après optimisation: {bareme.mean(classe)}")

moyenne avant optimisation: 0.49000000000000005
moyenne après optimisation: 0.4890909090909088

Une erreur

Pour une exécution, l’optimisation n’a pas fonctioné. Est-ce l’idée de l’optimisation qui est fausse ou son implémentation. Pour comprendre, on cherche un cas simple :

for i in range(100):
    bareme = BaremeOpt([1, 2, 3])
    classe = [Eleve(n_questions=3) for i in range(3)]
    m1 = bareme.mean(classe)
    bareme.optimize(classe)
    m2 = bareme.mean(classe)
    if m2 < m1:
        print(f"moyenne avant-après optimisation: {m1} - {m2} - barème={bareme}")
        for e in classe:
            print(e)
        break

Pourtant sur cet exemple, l’algorithme d’optimisation devrait fonctionner. La démonstration plus bas nous l’assure. C’est donc l’implémentation qui est fausse.

class BaremeOpt2(Bareme):
    def optimize(self, classe):
        matrice_notes = numpy.array([e.notes for e in classe])
        v = matrice_notes.sum(axis=0)
        els_pos = list((v, i) for i, v in enumerate(v))
        els_pos.sort()
        perm = [tu[1] for tu in els_pos]
        b = self.bareme.copy()
        for i, p in enumerate(perm):
            # self.bareme[i] = b[p]  # -> l'erreur est là
            self.bareme[p] = b[i]

for i in range(100):
    bareme = BaremeOpt2([1, 2, 3])
    classe = [Eleve(n_questions=3) for i in range(3)]
    m1 = bareme.mean(classe)
    bareme.optimize(classe)
    m2 = bareme.mean(classe)
    if m2 < m1:
        print(f"moyenne avant-après optimisation: {m1} - {m2} - barème={bareme}")
        for e in classe:
            print(e)
        break

Tout fonctionne.

Démonstration

et les taux de bonnes réponses à deux questions, et , les barèmes correspondant. La note moyenne est . Faut-il associer à ou ?

Cette quantité est positive si ( et ) ou et ), c’est à dire si les taux de bonnes réponses et les barèmes associées sont classés dans le même ordre.

Ce problème est une variante de celui de la location de ski où il faut donner N paires skis de tailles différentes à N skieurs de tailles différentes (Recherche Opérationnelle: Programmation dynamique, chaînes de Markov, files d’attente).

---

Notebook on github