484 lines
18 KiB
ReStructuredText
484 lines
18 KiB
ReStructuredText
########
|
||
À propos
|
||
########
|
||
|
||
|
||
|
||
*************
|
||
Problématique
|
||
*************
|
||
|
||
*Contexte: Élèves d'une classe, places assises dans une salle*
|
||
|
||
*Contraintes:
|
||
Le niveau de bavardage d'un élève, les liens sociaux entre élèves*
|
||
|
||
Comme tout enseignant j'ai été et je suis encore confronté au problème de la
|
||
gestion de classe et plus précisément aux interactions efficaces ou inefficaces
|
||
des élèves au sein d'une classe.
|
||
|
||
En effet, les associations d´élèves bavards entre eux peuvent mettre à mal une séance.
|
||
Dissocier une binôme productif peut l'être également.
|
||
|
||
Pour "régler" cela, la démarche consiste à créer un plan de classe afin de diriger
|
||
ou limiter les liens que peuvent avoir les élèves entre eux durant une séance.
|
||
Ainsi, j'ai tenté plusieurs fois de casser les bavardages entre plusieurs
|
||
camarades en les disposant dans la classe à divers endroits et ce dans le
|
||
but d'arriver à un équilibre entre bonne dynamique du groupe classe du point
|
||
de vue de l'ambiance et du travail et la limitation des bavardages, de l'inattention.
|
||
|
||
Voulant également passer la certification ISN, il me fallait trouver un projet
|
||
qui m'intéressait et qui semblait pertinent pour le dossier à présenter.
|
||
|
||
|
||
|
||
*****************
|
||
Solution proposée
|
||
*****************
|
||
|
||
*La solution proposée doit:
|
||
- utiliser Python
|
||
- être simple d'utilisation (IHM, import de la liste des élèves,...)
|
||
- proposer un placement automatique des élèves en fonction de certaines contraintes
|
||
- permettre d'éditer cette solution de positionnement ou d'en créer une
|
||
- permettre de modifier les contraintes*
|
||
|
||
|
||
|
||
**********
|
||
Conception
|
||
**********
|
||
|
||
|
||
1ère phase de recherche
|
||
=======================
|
||
|
||
J'ai tout d'abord commencé par faire des recherches sur cette thématique.
|
||
Au hasard de mes recherches, je suis tombé sur une application web, `xperprof`_,
|
||
permettant de génerer un plan de classe.
|
||
Cette application propose une fonction de positionnement aléatoire des élèves et
|
||
notamment la capacité de ne pas soumettre certaines tables à l'algorithme et ainsi
|
||
créer des zones vide autour de certains élèves.
|
||
Une première idée d'algorithme m'est venue : le positionnement aléatoire.
|
||
|
||
J'ai toutefois continué mes recherches et ai vu une analogie de mon projet avec
|
||
un jeu d'échec.
|
||
Un article du blog de `Jean-François GAZET`_ au sujet la création d'un jeu d'échec m'a apporter quelques idées
|
||
pour mon développement. Il m'a aider à définir quelques éléments de l'implémentation, à savoir :
|
||
|
||
- l'IHM: mode console ou graphique ?
|
||
- la façon de représenter un élève, un plan de classe
|
||
- la notion de "critères" que j'ai requalifié de "contraintes" pour mon projet
|
||
- la stratégie algorithmique pour proposer une solution
|
||
|
||
Restait un élément à préciser : le format de données utilisé pour contenir la liste des élèves.
|
||
Mais ce dernier point n'était qu'une formalité.
|
||
|
||
|
||
IHM
|
||
===
|
||
|
||
J'ai tout de suite souhaité que mon application fonctionne en mode console pour deux raisons :
|
||
|
||
- la première :
|
||
Pour moi une application doit pouvoir fonctionner en mode console et pouvoir proposer
|
||
une interface graphique au besoin.
|
||
J'espérais ainsi passer la majeure partie du temps pour développer l'API et passer le reste sur
|
||
l'Interface-Homme-Machine.
|
||
- la seconde (qui est une conséquence de la première) :
|
||
Compte-tenu du délai qui m'était imposé je ne voulais pas passer trop de temps dans l'apprentissage
|
||
d'une librairie graphique.
|
||
|
||
|
||
Format de la liste des élèves
|
||
=============================
|
||
|
||
Afin de charger directement dans l'application une liste des élèves à manipuler,
|
||
il est nécessaire de choisir un format de fichier.
|
||
|
||
Le format **.csv** est celui retenu, de part sa simplicité à le générer.
|
||
Le séparateur de champ sera le point-virgule.
|
||
|
||
L'en-tête du ficher élèves est la suivante :
|
||
|
||
.. figure:: _static/figure2.png
|
||
:align: center
|
||
:scale: 60 %
|
||
|
||
|
||
Classes ``Student`` et ``SeatingPlan``
|
||
======================================
|
||
|
||
Dans le contexte de la classe, un **élève** est un individu portant certains attributs, comme
|
||
un nom, un prénom, une liste d'amis dans cette même classe ou à l'extérieur,...
|
||
Un **plan de classe** également peut porter certaines propriétés, comme ses dimensions,
|
||
la liste des sièges disponibles, leurs occupants,...
|
||
|
||
Ces deux éléments peuvent de surcroît interagir.
|
||
|
||
Il est alors apparu évident de considérer, d'un point de vue informatique, ces notions
|
||
comme des structures de données à part entière.
|
||
Ainsi leur définition, leur création, leur manipulation s'en trouveraient facilitées.
|
||
|
||
Dès lors, le choix du paradigme de programmation orientée objet a été décidé.
|
||
|
||
Deux classes, ont donc été définies pour cela :
|
||
|
||
- la classe ``Student``, pour définir les élèves
|
||
- la classe ``SeatingPlan``, pour définir le plan de classe
|
||
|
||
Student
|
||
-------
|
||
|
||
Un élève est défini par :
|
||
|
||
- son nom
|
||
- un niveau de bavardage
|
||
- une liste d'amis
|
||
|
||
::
|
||
|
||
def __init__(self, name, chat_lvl=0, friends=[]):
|
||
""" Instancie un objet plan de classe.
|
||
|
||
:param name:
|
||
Nom de l'élève.
|
||
:type name: str
|
||
:param chat_lvl:
|
||
Coefficient ou niveau de bavardage.
|
||
:type chat_lvl: int
|
||
:param friends:
|
||
Liste d'amis.
|
||
:type friends: list
|
||
"""
|
||
self.name = name
|
||
self.chat_lvl = chat_lvl
|
||
self.friends = friends
|
||
|
||
SeatingPlan
|
||
-----------
|
||
|
||
Un plan de classe est défini par :
|
||
|
||
- un nombre de rangées
|
||
- un nombre de colonnes
|
||
- une "cartographie" de la classe
|
||
|
||
À l'origine, la cartographie de mon plan de classe prenait la forme d'une liste
|
||
imbriquée, comme dans `jepychess`_.
|
||
Cette représentation a évolué pour une structure plus souple et surtout en adéquation
|
||
avec celle utilisée dans l'algorithme de calcul.
|
||
|
||
::
|
||
|
||
def __init__(self, row=5, col=8):
|
||
""" Instancie un objet plan de classe.
|
||
|
||
:param row:
|
||
Nombre de rangées dans la classe.
|
||
:type row: int
|
||
:param col:
|
||
Nombre de colonnes dans la classe.
|
||
:type col: int
|
||
:param mapping:
|
||
Représentation du plan de la classe.
|
||
:type mapping: dict
|
||
"""
|
||
self.row = row
|
||
self.col = col
|
||
self.mapping = {(i, j): None for i in range(row)
|
||
for j in range(col)}
|
||
|
||
|
||
Les contraintes
|
||
===============
|
||
|
||
Les contraintes sont les conditions suivant lesquelles on accepte que deux
|
||
élèves soient voisins dans le plan de classe.
|
||
|
||
Pour commencer, celles-ci seront "naïves". C'est-à-dire qu'elles seront basées
|
||
sur une valeur entière représentant le niveau de bavardage de l'élève.
|
||
Puis, elles sreont redéfinies pour prendre appui sur les relations sociales
|
||
entre les élèves (qui est ami avec ami).
|
||
|
||
Ainsi, deux élèves pourront être voisins si la différence entre leur niveaux
|
||
respectifs de bavardage est d'au moins une valeur fixée.
|
||
De la même manière, deux élèves pourront être voisins, si leur lien social
|
||
est minimal.
|
||
|
||
Les niveaux ou coefficients de bavardage seront définis comme suit :
|
||
|
||
.. figure:: _static/figure1.png
|
||
:align: center
|
||
:scale: 60 %
|
||
|
||
|
||
2nde phase de recherches : l'algorithme ?
|
||
=========================================
|
||
|
||
Balbutiements
|
||
-------------
|
||
|
||
Initialement, en me basant sur l'exemple de `xperprof`_, j'ai réalisé un placement
|
||
aléatoire sous contrainte, des élèves dans le plan de classe.
|
||
Le résultat fût concluant mais chaque lancement de cet algorithme produisait une seule proposition
|
||
qui pouvait ou non, être complète en raison de contraintes parfois trop fortes.
|
||
|
||
La première difficulté est ainsi apparue: satisfaire des contraintes tout en proposant des solutions possibles.
|
||
|
||
L'algorithme **alpha-beta** cité dans le blog de `Jean-François GAZET`_ m'a dirigé vers les méthode de résolution
|
||
de jeu d'échec, de dames ou plus généralement de problèmes NP-complet.
|
||
Mais également sur le fait de considérer les différentes étapes de recherche de complétion du plan de classe comme
|
||
un arbre de recherche.
|
||
|
||
Mes diverses lectures ainsi que des recherches sur l'Internet m'ont amené au problème des N-Reines.
|
||
Diverses méthodes de programmation permettent de résoudre ce problème : comme la programmation par contraintes.
|
||
|
||
Résoudre un problème de satisfaction de contraintes... ?
|
||
--------------------------------------------------------
|
||
|
||
J'ai vu la résolution de ma problématique comme un problème de satisfaction de contraintes et me suis mis en
|
||
quête de réponses concernant la programmation par contraintes.
|
||
|
||
Plusieurs possibilités
|
||
|
||
Je me suis alors tourné vers un algorithme avec retour sur trace.
|
||
|
||
L'algorithme au final
|
||
---------------------
|
||
|
||
Validateur de contraintes
|
||
"""""""""""""""""""""""""
|
||
|
||
::
|
||
|
||
def respect_constraints(self, seat, student, seatingplan, solution):
|
||
"""Indique si une place associée à une élève satisfait aux
|
||
contraintes, à savoir si :
|
||
|
||
- l'élève n'a pas déjà été positionné
|
||
- la place n'est pas déjà occupée
|
||
- la place est libre, que son voisinage est composé de bons voisins
|
||
en termes de bavardages.
|
||
|
||
:param seat:
|
||
Place que l'on veut associer à un élève.
|
||
:type seat: tuple
|
||
:param student:
|
||
Élève que l'on veut associer à une place.
|
||
:type student: Student
|
||
:param seatingplan:
|
||
Plan de classe.
|
||
:type seatingplan: SeatingPlan
|
||
:param solution:
|
||
Associations 'place - élève' valides.
|
||
:type solution: dict
|
||
|
||
:rtype: bool
|
||
|
||
.. todo::
|
||
- Modifier le traitement des contraintes de façon à tolérer
|
||
un certains nombre de voisins ne satisfaisants pas aux
|
||
contraintes.
|
||
- Ajouter les liens sociaux comme contraintes supplémentaires.
|
||
"""
|
||
# L'association en cours est supposée valide
|
||
result = True
|
||
# Si l'élève en cours a déjà été traité, l'association est invalide
|
||
if student in solution.values():
|
||
result = False
|
||
# return False
|
||
# Si la place en cours a déjà été traitée, l'association est invalide
|
||
elif seat in solution.keys():
|
||
result = False
|
||
# return False
|
||
else:
|
||
# Si non, veŕifions le voisinage de la place
|
||
# Récupérons le voisinage de la place en cours
|
||
neighbourhood = self.get_neighbourhood(seatingplan,
|
||
seat,
|
||
self.NEIGHBOURHOOD_RADIUS)
|
||
|
||
for neighbour_seat in neighbourhood:
|
||
# On ne teste les contraintes que sur les sièges déjà occupés
|
||
# donc sur ceux faisant déjà partie des solutions
|
||
if neighbour_seat in list(solution.keys()):
|
||
# On récupère l'élève du siège voisin
|
||
neighbour = solution[neighbour_seat]
|
||
|
||
# Lequel de l'élève en cours ou du voisin
|
||
# est le plus bavard ?
|
||
max_chat_lvl = max(student.chat_lvl,
|
||
neighbour.chat_lvl)
|
||
|
||
# Les contraintes portent sur la différence de
|
||
# coefficient de bavardage entre deux voisins:
|
||
if max_chat_lvl == 5:
|
||
result = result and self.are_safe_neighbours(
|
||
student,
|
||
neighbour,
|
||
self.DELTA_FOR_MAX_CHAT_LVL_5)
|
||
|
||
elif max_chat_lvl == 4:
|
||
result = result and self.are_safe_neighbours(
|
||
student,
|
||
neighbour,
|
||
self.DELTA_FOR_MAX_CHAT_LVL_4)
|
||
|
||
elif max_chat_lvl == 3:
|
||
result = result and self.are_safe_neighbours(
|
||
student,
|
||
neighbour,
|
||
self.DELTA_FOR_MAX_CHAT_LVL_3)
|
||
|
||
elif max_chat_lvl == 2:
|
||
result = result and self.are_safe_neighbours(
|
||
student,
|
||
neighbour,
|
||
self.DELTA_FOR_MAX_CHAT_LVL_2)
|
||
|
||
elif max_chat_lvl == 1:
|
||
result = result and self.are_safe_neighbours(
|
||
student,
|
||
neighbour,
|
||
self.DELTA_FOR_MAX_CHAT_LVL_1)
|
||
|
||
else:
|
||
result = result and True
|
||
# Le siège voisin n'est pas occupé, il est donc valide
|
||
result = result and True
|
||
# retournons la validité de l'association
|
||
return result
|
||
|
||
Le solveur
|
||
""""""""""
|
||
|
||
::
|
||
|
||
def solve(self, seatingplan, students_list):
|
||
"""Cherche pour une liste de places et une liste d'élèves, un ensemble
|
||
de dispositions dans un plan de classe respectueuses de certaines
|
||
contraintes décrites dans la fonction 'respect_constraints' ci-dessus.
|
||
|
||
:param seatingplan:
|
||
Plan de classe.
|
||
:type seatingplan: SeatingPlan
|
||
:param students_list:
|
||
Liste d'élèves à positionner dans le plan de classe.
|
||
:type students_list: list
|
||
:param solution:
|
||
Solution de placement proposée.
|
||
:type solutions: dict
|
||
|
||
:return:
|
||
Disposition des élèves dans le plan de classe.
|
||
:rtype: generator
|
||
"""
|
||
# Liste des places
|
||
seats_list = list(seatingplan.mapping.keys())
|
||
|
||
# Quantités de places et d'élèves à traiter
|
||
number_of_seats = len(seats_list)
|
||
number_of_students = len(students_list)
|
||
|
||
# On stocke nos associations 'place - élève' dans un dictionnaire
|
||
solution = {}
|
||
|
||
# Indexes de départ dans nos listes de places et d'élèves
|
||
idx_seat = 0
|
||
idx_student = 0
|
||
|
||
# Retour sur trace (backtracking)
|
||
backtrack = False
|
||
# Fin du parcours
|
||
end = False
|
||
|
||
# On commence notre recherche
|
||
while not end:
|
||
# On ne revient pas encore en arrière
|
||
while not backtrack:
|
||
# Place à traiter
|
||
current_seat = seats_list[idx_seat]
|
||
# Élève à traiter
|
||
current_student = students_list[idx_student]
|
||
|
||
# L'association 'place - élève' est-elle satisfaisante ?
|
||
if self.respect_constraints(current_seat,
|
||
current_student,
|
||
seatingplan,
|
||
solution):
|
||
# Oui, alors associons l'élève à cette place
|
||
solution[current_seat] = current_student
|
||
|
||
# Est-ce qu'on a traité tous les élèves dans
|
||
# notre parcourt ?
|
||
if (idx_student == number_of_students-1):
|
||
# Oui, alors renvoyons notre solution
|
||
yield {p: s for p, s in solution.items()}
|
||
del solution[current_seat]
|
||
|
||
# A-t'on traité toutes les places ?
|
||
if (idx_seat != number_of_seats-1):
|
||
# Non, on passe à la suivante
|
||
idx_seat = idx_seat + 1
|
||
else:
|
||
# Oui, on revient en arrière
|
||
backtrack = True
|
||
else:
|
||
# Non, on passe au suivant en recommençant à la
|
||
# première place
|
||
idx_seat = 0
|
||
idx_student = idx_student + 1
|
||
|
||
# Les contraintes n'ont pas été satisfaites,
|
||
# il nous reste des places à traiter
|
||
elif (idx_seat != number_of_seats-1):
|
||
# On passe à la suivante
|
||
idx_seat = idx_seat + 1
|
||
|
||
else:
|
||
# Si non, on revient en arrière
|
||
backtrack = True
|
||
|
||
# Sommes-nous remonté jusqu'au premier élève ?
|
||
end = (idx_student == 0)
|
||
|
||
# On revient sur nos pas...
|
||
while (backtrack and not end):
|
||
# Prenons l'élève précédent
|
||
idx_student = idx_student - 1
|
||
current_student = students_list[idx_student]
|
||
# On récupère (et on enlève des solutions) la place qui lui
|
||
# est associée
|
||
current_seat = list(solution.keys())[list(solution.values())
|
||
.index(current_student)]
|
||
solution.pop(current_seat)
|
||
idx_seat = seats_list.index(current_seat)
|
||
|
||
# Il nous reste des places
|
||
if (idx_seat != number_of_seats-1):
|
||
# Prenons la place suivante et stoppons notre retour
|
||
# en arrière
|
||
idx_seat = idx_seat + 1
|
||
backtrack = False
|
||
# Ou nous sommes revenu au premier élève, on stop là
|
||
elif idx_student == 0:
|
||
end = True
|
||
|
||
|
||
|
||
********************************
|
||
Bilan et améliorations possibles
|
||
********************************
|
||
|
||
L'algorithme fonctionne bien dès lors que l'échantillon d'élèves n'est pas trop grand.
|
||
|
||
|
||
|
||
|
||
|
||
|
||
.. _xperprof: https://www.xperprof.fr/generateur_plan_de_classe
|
||
.. _Jean-François GAZET: https://fr.jeffprod.com/blog/2014/comment-programmer-un-jeu-dechecs.html
|
||
.. _jepychess: `Jean-François GAZET`_
|