Différences
Ci-dessous, les différences entre deux révisions de la page.
Prochaine révision | Révision précédente Prochaine révisionLes deux révisions suivantes | ||
restricted:opti-c-tp2 [2022/05/24 12:01] – créée edauce | restricted:opti-c-tp2 [2023/09/19 22:35] – edauce | ||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
+ | ==== TP2 : Problème d’emploi du temps ==== | ||
+ | On a K créneaux horaires, m enseignants et n classes d’élèves. | ||
+ | * Créneaux : (Lu8, | ||
+ | * Professeurs : (Dupont, Durand, Duval, …) - par ex: m = 32. | ||
+ | * Classes : (6A, | ||
+ | |||
+ | <note important> | ||
+ | Ce TP à rendre et contient plusieurs questions à rédiger. Il est donc conseillé d' | ||
+ | </ | ||
+ | |||
+ | == Problème no 1 == | ||
+ | |||
+ | Chaque classe est suivie par 6 professeurs. Chaque professeur est affecté à 3 classes et réalise 3 séances pour chaque classe. Ainsi, chaque professeur réalise un total de 9 séances par semaine, et chaque classe suit 3x6 = 18 séances de cours (à répartir sur 20 créneaux disponibles). | ||
+ | |||
+ | **remarque** : on vérifie 3m = 6n soit m = 2n | ||
+ | |||
+ | === Affectation des professeurs === | ||
+ | |||
+ | On suppose pour simplifier que les professeurs sont désignés par un numéro unique (de 0 à m-1) ainsi que les classes (classes 0 à n-1) et les créneaux (de 0 à K-1). | ||
+ | On suppose qu’est donné au départ le tableau d’affectation (donnant les classes affectées à chaque professeur). Ainsi, pour tout i, A(i) ={A(i, | ||
+ | |||
+ | <note tip> | ||
+ | Indication: on veut définir la matrice des affectations '' | ||
+ | Le code suivant est souvent incorrect (car un professeur paut etre affecté 2 fois à la même classe): | ||
+ | <code python> | ||
+ | profs = list(range(32))*3 | ||
+ | A={} | ||
+ | for i in range(16): | ||
+ | A[i] = [] | ||
+ | for j in range(6): | ||
+ | prof = np.random.choice(profs) | ||
+ | | ||
+ | | ||
+ | </ | ||
+ | </ | ||
+ | |||
+ | |||
+ | __**Question**__ | ||
+ | Testez ces deux codes. Réfléchissez à une méthode permettant d' | ||
+ | * en effectuant un grand nombre de tirages (méthode de monte carlo) | ||
+ | * à partir d'une affectation initiale incorrecte, par permutation (méthode glouton) | ||
+ | |||
+ | < | ||
+ | remarque : Il est également possible de contourner le problème en retirant un nouveau professeur chaque fois qu'il y a collision. Le code suivant fonctionne la plupart du temps: | ||
+ | <code python> | ||
+ | profs = list(range(32))*3 | ||
+ | A={} | ||
+ | for i in range(16): | ||
+ | A[i] = [] | ||
+ | for j in range(6): | ||
+ | for trial in range(10): | ||
+ | prof = np.random.choice(profs) | ||
+ | if prof not in A[i]: | ||
+ | break | ||
+ | if trial<9: | ||
+ | | ||
+ | | ||
+ | else: | ||
+ | | ||
+ | break | ||
+ | </ | ||
+ | </ | ||
+ | |||
+ | === Emploi du temps === | ||
+ | Etant données une affectation '' | ||
+ | Pour tout i, s(i) = (s(i,0), (s(i,1), s(i,2),... ,s(i,19)) qui est une permutation de la liste (A(i,0), A(i,0), A(i,0), A(i,1), A(i,1), A(i,1), …, A(i,5), A(i,5), A(i,5), -1, -1) où les valeurs -1 correspondent aux 2 séances d’”étude”. | ||
+ | Une solution prend donc la forme d’une matrice de n lignes et K colonnes. | ||
+ | |||
+ | <note tip> | ||
+ | A nouveau pour vous aider, voici les lignes de code permettant de définir un emploi du temps aléatoire: | ||
+ | <code python> | ||
+ | s = [] | ||
+ | for i in range(16): | ||
+ | s.append([]) | ||
+ | for j in range(6): | ||
+ | s[i].extend([A[i][j], | ||
+ | s[i].extend([-1, | ||
+ | s[i] = np.random.permutation(s[i]) | ||
+ | s = np.array(s) | ||
+ | </ | ||
+ | </ | ||
+ | |||
+ | __Questions: | ||
+ | * Combien ce problème accepte-t-il de solutions? | ||
+ | * Comment définiriez-vous le voisin d’une solution s donnée? | ||
+ | * En fonction de la définition précédente, | ||
+ | |||
+ | __Problème: | ||
+ | |||
+ | |||
+ | |||
+ | On appelle collision le fait qu’un même professeur apparaisse 2 fois ou plus dans le même créneau (autrement dit une collision est un triplet (i,j,k) tel que (i $\neq$ j), (s(i, | ||
+ | |||
+ | |||
+ | * En vous inspirant du [[opti-C-TP1|TP1]], | ||
+ | |||
+ | * Il existe une manière de calculer le nombre de collisions en O(K*N). Décrivez le principe de cet algorithme, puis écrivez-le. | ||
+ | |||
+ | * Reprenez certains algorithmes d' | ||
+ | |||
+ | |||
+ | == Problème no 2 == | ||
+ | |||
+ | Reprenez le problème précédent en considérant les contraintes suivantes: | ||
+ | * Chaque professeur suit 5 classes et assure 2 séances par classe. | ||
+ | * Chaque professeur effectue 10 séances par semaine | ||
+ | * 10 professeurs sont affectés à chaque classe | ||
+ | * Il y a 20 classes | ||
+ | * Il y a 40 professeurs | ||
+ | |||
+ | L' |