Différences

Ci-dessous, les différences entre deux révisions de la page.

--- restricted:opti-c-tp2 [2023/09/19 22:08] – edauce
+++ restricted:opti-c-tp2 [2023/09/19 22:36] (Version actuelle) – 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,Lu10,...,Ve14,Ve16) - ici: K = 20.
-  * Professeurs : (Dupont, Durand, Duval, …) - par ex: m = 32.
-  * Classes : (6A,6B,...,3D) - par ex: n = 16.
 <note important>
-Cet énoncé de TP est à rendre et contient plusieurs questions à rédiger. Il est donc conseillé d'utiliser un environnement de programmation de type 'jupyter notebook' contenant à la fois du code exécutable et des commentaires formattés (cellules 'markdown'). Vous utiliserez ces cellules formattées pour répondre à certaines questions
+Ce TP à rendre et contient plusieurs questions à rédiger. Il est donc conseillé d'utiliser un environnement de programmation de type 'jupyter notebook' contenant à la fois du code exécutable et des commentaires formattés (cellules 'markdown'). Vous utiliserez ces cellules formattées pour répondre à certaines questions.
 </note>
-**__Problème no 1:__**
+==== Problème no 1 ====
+On a K créneaux horaires, m enseignants et n classes d’élèves.
+  * Créneaux : (Lu8,Lu10,...,Ve14,Ve16) - ici: K = 20.
+  * Professeurs : (Dupont, Durand, Duval, …) - par ex: m = 32.
+  * Classes : (6A,6B,...,3D) - par ex: n = 16.
 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).
@@ Ligne 94: / Ligne 96: @@
-  * Créez un programme python dasn lequel qui définit un problème d'emploi du temps à partir d'une matrice d'affectations ''A''. Cette  contiendra à peu près les mêmes fonctions, c'est à dire ''affiche_edt'',   ''randomVoisin'', ''tousLesVoisins'', ''J'', ''argmin_J''. En particulier, la fonction de coût sera égale au nombre total de collisions dans la matrice s. (rq : il existe une manière de calculer le nombre de collisions en O(K*N))
+  * En vous inspirant du [[opti-C-TP1|TP1]], définissez les fonctions ''affiche_edt'', ''randomVoisin'', ''tousLesVoisins'', ''J'', ''argmin_J'' adaptées aux problèmes d'emploi du temps. En particulier, la fonction de coût sera égale au nombre total de collisions dans la matrice s.
+  * 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 le travail du TP1 (ou inspirez-vous de la [[opti-C-TP1C|correction du TP1]]), pour coder des algorithmes d'optimisation qui, partant d’une solution s prise au hasard, permettent permet de trouver un emploi du temps sans collision.
+  * Reprenez certains algorithmes d'optimisation du [[opti-C-TP1|TP1]] (Monte Carlo, Glouton, Tabou, ...) qui, partant d’une solution s prise au hasard, effectuent une recherche par voisinage pour trouver un emploi du temps sans collision. Quels sont les algorithmes les plus efficaces?
-  * Essayez de faire en sorte que vos classes et fonctions soient suffisamment génériques pour pouvoir résoudre à la fois des problèmes de voyageur et des problèmes d'emploi du temps.
-**__Problème no 2:__**
+==== Problème no 2 ====
 Reprenez le problème précédent en considérant les contraintes suivantes: