Slt à tous !
Mes interventions sont rares mais là, je crois qu'il faut faire quelque chose.
Si vous faisiez de l'informatique un peu, hein ?
Bon, je crois que nous avons beaucoup d'humour dans ce sujet : surtout sur la fin avec betitout.
Dans un problème informatique, il faut, AMHA, décortiquer en solutions plus simple. Ici, c'est d'un emploi du temps dont il s'agit.
Quelqu'un a regarder la complexité en jeu ?
Rappel, lorsque l'on retire une petite quantité de données dans un problème et que l'on obtient le même ordre de grandeur, c'est que l'on est en face d'un problème np-complet.
np signifie non polynomial et complet, bah la complétude, comme dans R, il est complet cet ensemble.
Dans un ouvert, vous aurrez toujours une infinité d'élément, quelque soit le epsilon, tout petit, d'écart entre les 2 bornes !
C'est dur à montrer ça, au cas par cas, c'est pourquoi je préfaire retirer une petite quantité de données initiales ( nb prof, nb salle, nb classe) et constater que la complexité ne change pas.
Il est bien d'autres exemple de ce genre de problème et les emplois du temps en font partie.
Vous ne trouverez aucun logiciel de résolution d'emploi du temps, tant que l'exploration de résolution des pb np-comp ne sera pas aboutie.
Aujourd'hui, les recherches là-dessus sont telles que l'on enseigne la manière de reconnaître un pb np-comp puisque l'on ne sait pas ni le résoudre, ni dire si c'est possible : je ne plaisante pas.
Alors bon courage. J'peux vous garantir que si on a ne serait-ce qu'un début d'idée de solution, toute la planète le sait en moins d'un Clock-Tick d'éta hertz !!!
Vous savez pourquoi il y a marqué pf sur les corbillards allemands ??? Bon Foyage !
Alors un peu d'humour, moi aussi.
À pluche !
Cordialement.
Sril.
P.S. : la complexité "infinie" ne suffit pas, i.e., le np. Il faut en plus que chaque "sous-problème" forme une classe de l'ensemble de départ, et ainsi de suite. L'itération est non seulement sans fin mais en plus jamais calculable à chaque pas : impressionnant, non ?
Les seuls outils dont on dispose sont l'intelligence artificielle, dont beaucoup de programmeurs aiment à rappeler qu'il est criminel d'arrêter ce type de programme.
Un approche simple est connue sous le nom d'arbre alpha-béta ou min-max.
Voilà, j'ai fini d'étaler ma science.
12 juin 2008 à 13:53