Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente Prochaine révisionLes deux révisions suivantes |
restricted:opti-c-tp2 [2023/09/19 22:09] – edauce | restricted:opti-c-tp2 [2023/09/19 22:34] – edauce |
---|
| |
<note important> | <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> | </note> |
| |
| |
| |
* 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. |
| |
* 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. | * 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'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:__** |