| 17 sriliam, le 26 fév 2008 à 04:04:55Slt à 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. | 23 jtotoff, le 6 sep 2008 à 14:19:53Enfin un peu de sérieux ! Je pense malheureusement que les chefs d'établissement scolaires font confiance aux charlatans informatiques... et produsient caque année des edt ineptes, qui ne correspondent ni au confort des élèves ni à celui de leurs profs.
Bref, la seule manière existant actuellement pour "résoudre" (de manière non optimale mais adéquats) un pb np-complet est d'utiliser des heuristiques... En gros, ceci veut dire qu'on ajoute un peu "d'expertise" pour aboutir à une solution pas trop débile...
Du temps où j'étais élève ds un gd lycée parisien comptant plus d'1 milliers d'élèves et regroupant collège, lycée et classes prépas, nous ne disposions pas de moyens informatiques... et les edt étaient rarement débiles et révisés après la rentrées. Comme quoi, les compétences se perdent ! | 24 sriliam, le 7 sep 2008 à 13:43:32Du sérieux ? Mais il n'y a que ça ici, non ?
Charlatans informatique ? Je trouve que tu y vas un peu fort.
Ce qu'il faut bien comprendre, à mon humble avis, c'est que lorsque l'on étudie les problèmes np-complet, les enseignants disent immédiatement qu'il n'y a pas de solution et que l'on ne sait pas dire si il en existera un jour. Du coup, le cours se cantonne à pouvoir reconnaître un problème np-complet d'un autre problème non np-complet, sachant que si l'on arrive à en résoudre un np-complet, on les a tous résolus !
Ensuite, une fois fait, c'est-à-dire d'avoir assimilé les 3 méthodes de reconnaissance d'un problème np-complet (algébrique, matricielle et analytique), l'enseignant présente par l'exemple, en général, les solutions utilisées pour tout de même s'en sortir : la recherche d'heuristiques en fait partie et passe en général par les moteurs d'inférences et la cognition.
Étant donné que l'enseignant se veut relativement exhaustif dans le contenu de son cours, ce n'est pas le problème des emplois du temps qui est présenté mais souvent des jeux, notamment de stratégie, comme le go.
Ensuite, le pauvre programmeur qui s'est bien fait largué sur toute la ligne du fait d'une telle complexité doit comprendre le cours qu'il a eu de tout ça pour l'appliquer à tel ou tel problème particulier, comme l'aide à la décidion d'un emploi du temps, par exemple. Je ne vois vraiment pas de charlatanisme là-dedans : je pense que chacun essaye, à son niveau, d'y mettre du sien pour que cela fonctionne correctement.
Je n'ai pas connaissance d'un quelconque logiciel permettant de faire ça et effectivement, même si on se prend énormément la tête, la solution "à la main" est souvent aussi bonne, voire meilleure si l'on est très intelligent, ce qui n'est pas mon cas.
Bien cordialement. |
|
|
1ere stg gestion programme eco chapitre 2
