Discussion :

[chaton18]

Bonsoir,

J'ai un un exercice d'algorithmique à faire, je ne comprends pas par où je dois commencer. Pouvez vous me donner quelques indications pour mieux comprendre le sujet?

Voici l'exercice:
On dispose d'une salle dans laquelle on veut organiser des activités (par exemple, des cours). Chaque activité a une heure de début et une heure de fin. Chaque activité a, en outre, une priorité (on préfère organiser un examen plutôt qu'un cours). Ecrire un algorithme permettant de trouver quelles activités organiser pour faire le plus grand nombre d'activités possible. Comment généraliser si on dispose de plusieurs salles ?

Est ce qu'une activité peut prendre plus de temps q'un autre?
Est ce qu'il est favorable de prendre des activités à courte durée? Parce que je me dis que plus les activités sont courtes et plus il est possible de faire un grand nombre d'activités.

[Eusebius]

Est ce qu'une activité peut prendre plus de temps q'un autre?

Oui, c'est dans l'énoncé.

Est ce qu'il est favorable de prendre des activités à courte durée? Parce que je me dis que plus les activités sont courtes et plus il est possible de faire un grand nombre d'activités.

Tout dépend ! Dans certains cas, ce sera un bon choix, dans d'autres un mauvais... Ca dépendra de la structure des activités qui te sont proposées. Dans l'idéal il faudrait que ton algorithme s'adapte, mais en explorant ce problème tu te rendras compte qu'il est difficile de trouver un algo idéal, et qu'il y a des stratégies qui fonctionnent bien dans certains cas, et mal dans d'autres...

Cet exercice est équivalent à un problème d'algorithmique bien connu (que je décide de ne pas te pointer pour te laisser le plaisir d'imaginer des solutions toi-même), pour lequel on ne connait pas d'algorithme qui soit efficace dans tous les cas. Pour moi l'intérêt de l'exercice est de te faire imaginer diverses solutions, pas forcément de te faire trouver "la meilleure".

[chaton18]

Merci de m'avoir répondu.
Oui, je me suis rendue compte que ce n'était pas vraiment une bonne idée de favoriser les activités de courte durée.

[Eusebius]

Merci de m'avoir répondu.
Oui, je me suis rendue compte que ce n'était pas vraiment une bonne idée de favoriser les activités de courte durée.

Ca dépend ! Tu peux avoir plein d'activités courtes mais de priorité élevée, et dans ce cas ce sera intéresant. Pour évaluer les différentes techniques, il faut que tu aies des jeux de tests suffisamment variés.

Note : quand j'ai dit qu'on ne connaissait pas d'algorithme efficace dans tous les cas, je ne voulais pas dire qu'on ne savait pas résoudre le problème, mais seulement qu'on ne sait pas le résoudre de manière efficace dans tous les cas (les algos qui trouveront la meilleure solution dans tous les cas seront très longs -- si tu as fait de la complexité, ce problème est NP-complet).

[Jimmy_]

Tu as le choix, soit tu fais un programme qui calcule toutes les solutions, et tu choisis la meilleure. Cette algorithme est polynomial et donc sera très vite très long à l'execution.
Soit tu choisis un compromis local, tu auras un programme qui sera que juste long à l'execution, mais qui ne trouvera pas forcement la meilleure solution.

[Eusebius]

Cet algorithme est polynomial et donc sera très vite très long à l'execution.

Hum, sauf erreur grossière de ma part (c'est toujours possible), si tu arrives à trouver un algorithme polynomial pour ce problème, tu gagnes un très gros chèque.