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¶
[1]:
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
[1]:
array([1, 1, 1, 2, 2, 2, 3, 3, 3, 4])
La classe Eleve¶
[3]:
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¶
[4]:
bareme = Bareme()
classe = [Eleve(n_questions=len(bareme)) for i in range(100)]
moyenne = bareme.mean(classe)
moyenne
[4]:
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.
[5]:
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]
[6]:
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 :
[7]:
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.
[8]:
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]
[9]:
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¶
\(v_i\) et \(v_j\) les taux de bonnes réponses à deux questions, et \(b_i\), \(b_j\) les barèmes correspondant. La note moyenne est \(v_i b_i + v_j b_j\). Faut-il associer \(b_i\) à \(v_i\) ou \(v_j\) ?
Cette quantité est positive si (\(v_i < v_j\) et \(b_i < b_j\)) ou \(v_i > v_j\) et \(b_i > b_j\)), 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).