Intemperie

Le problème d'optimisation associé au problème de décision de SAT, c'est bien l'exhibition de variables qui satisfont la formule en question. C'est bien un problème NP-Difficile, et si tu as trouvé un algo' polynomial c'est soit que tu t'es planté dans ton algo', soit que tu t'es planté dans l'évaluation de sa complexité, soit que tu es très fort et que tu as montré que P=NP.
Mais étant donné que tu utilises des ref dans ton code Caml, je ne peux pas croire à la dernière proposition =D
(Toute l'épreuve papier + machine, que du OCaml et aucune réf', alors BON ...)

Bon, en fait lors de ma première proposition, j'avais un peu trop vite regroupé les disjonctions de cas, à tort. Il manquait juste des moins une fois sur deux. Mais l'idée était bonne.

f(n) = {
-n+1 si n = 2k
n+1 si n = 2k+1
-n-1 si n = -2k
n-1 si n = 2k+1
Avec k un entier naturel.
}

edit :
TLN : Voilà, j'ai retrouvé la même chose. Perso après mon premier essai, j'ai voulu voir si on pouvait démontrer que c'était impossible. J'ai procédé par construction, et il est devenu clair que c'était possible, et comment.

« Moi aussi j'ai fini à l'avance, mais j'ai préféré réviser mes katakanas que de demander une question supplémentaire xD »
Mauvais, j'suis passé aux kanji la semaine dernière moi. :D

Et ne sous-estimez pas la Puissance du Sphinx.

TLN : « Le problème d'optimisation associé au problème de décision de SAT, c'est bien l'exhibition de variables qui satisfont la formule en question. C'est bien un problème NP-Difficile, et si tu as trouvé un algo' polynomial c'est soit que tu t'es planté dans ton algo', soit que tu t'es planté dans l'évaluation de sa complexité, soit que tu es très fort et que tu as montré que P=NP. »
→ C'est un peu ce que j'ai dit dans mon paragraphe mais OK :)

TLN : « Mais étant donné que tu utilises des ref dans ton code Caml, je ne peux pas croire à la dernière proposition =D »
→ Parfois, les ref sont nécessaires. C'est un peu comme les @.

C'est un peu ce que j'ai dit dans mon paragraphe mais OK :)

Sauf qu'à ma connaissance les problèmes NP-Difficiles ne sont pas plus facile à résoudre en temps polynomial que les problèmes NP-Complet, donc ton paragraphe reste dénué de sens.

Parfois, les ref sont nécessaires. C'est un peu comme les @

Ou pas. Quand on sait pas coder on sait pas coder hein ...

@ Pikrass : Ouai moi aussi j'ai appris 8 kanji depuis le début de l'année. Mais bon je connais pas encore très bien mes katakanas donc bon ... xD
En fait je bosse pas assez mon japonais, et je n'ai que 2h de cours par semaine °° (c'est peu).

Bah j'ai acheté le livre de Maniette, j'en suis à 120 en moins d'une semaine. Ca marche impec', par contre le plus long sera d'apprendre les mots avec les prononciations.

Argh. Mais t'es trop un fou. Moi déjà que si j'apprends plus de 10 kanjis par jour je meurs ...

TLN : « C'est un peu ce que j'ai dit dans mon paragraphe mais OK :)
Sauf qu'à ma connaissance les problèmes NP-Difficiles ne sont pas plus facile à résoudre en temps polynomial que les problèmes NP-Complet, donc ton paragraphe reste dénué de sens. »
→ Sauf que la question 3, c'est SAT, et SAT, c'est NP-complet… Bon on va pas se taper dessus, je n'aime pas la complexité algorithmique :P

Jérémie, j'avais déjà entendu qu'à Thiers tu pouvais être insupportable quand tu voulais avoir raison, et ça se confirme :P

--
Jill-Jênn, qui est avec des gens bourrés au foyer de l'ENS qui sont en train d'écrire les mensurations des filles ayant la plus grosse poitrine sur le tableau à la craie xDDD, et est content de constater qu'il avait raison pour les 4 premières du classement :P

Y a ma voisine dedans ? xD

Sauf que la question 3, c'est SAT, et SAT, c'est NP-complet… Bon on va pas se taper dessus, je n'aime pas la complexité algorithmique :P

Je ne sais pas si tu étais bourré quand tu as écris ça, mais j'imagine que tu te souviens quand même qu'à chaque problème de décision NP-Complet est associé un problème d'optimisation NP-Difficile. Savoir si oui ou non une formule dans le cas général est satisfiable, c'est le problème SAT, qui est NP-Complet. Trouver les valeurs des variables qui la satisfont, c'est un autre problème, qui lui est NP-Difficile.

(Enfin y a intérêt à ce que je dise pas de conneries, vu comment je fais mon chieur xD)

C'est qui ta voisine ? Marianne ?

Oui, OK, donc question 3 c'est SAT donc NP-complet, question 5 c'est NP-difficile. En l'occurrence, c'était pour la question 3 que j'avais une solution polynomiale ; donc il faut que je vérifie :P

C'est qui ta voisine ? Marianne ?

Carole

Bien sûr que ta voisine est dans la listes des filles ayant la plus grosse poitrine ! Elle est 2e xD Je croyais que tu te référais à « Jérémie, j'avais déjà entendu qu'à Thiers tu pouvais être insupportable quand tu voulais avoir raison, et ça se confirme :P » xD

Ouai enfin je vois pas trop le rapport entre "j'avais déjà entendu qu'à Thiers tu pouvais être insupportable" et "Y a ma voisine dedans" hein xD
C'était qui sinon la première sur la liste ? °°

Et d'ailleurs qui c'est qui t'as dis que je pouvais être chiant à Thiers ? :o (des noms, je veux des noms)

Ben ta voisine à Thiers aurait pu penser que tu étais insupportable :)

Ben c'est Laurie la première sur la liste, tu imagines bien :) Elle est en agrégation de géologie cette année.

Euh ben moi, déjà.

--
Jill-Jênn, bourré :P

Ouai mais toi t'es plus à Thiers ça compte pas °°
Laurie je connais pas.
Et ma voisine à Thiers euh ... je lui parlais pas des masses non, mais je la faisais pas chier non plus. Mais c'est vrai qu'en y repensant, j'ai pas mal fait chier mes voisins de gauche qui ont changé plus d'une fois de place au cours de l'année xD

Non mais je ne savais même pas si tu avais une voisine à Thiers ou pas \^\^' C'est juste ce que tu avais dit qui m'y avait fait penser.