Dracenna a écrit :Troiz.
34 degrés (Celsius) aujourd'hui, 38 hier. On va vers le froid, c'est moi qui vous le dis !
_________________
Because we love our Vegemite
We all adore our Vegemite
It puts a rose in every cheek.

Ben il fait bon pour une fois, et y a même une brise revigorante
_________________
#nwnights-fr @ irc.darkmyst.org TitanQuest-FR

Childéric a écrit :Et c'est très bien. L'enseignement de la thermodynamique devrait être obligatoire : cela éviterait que, régulièrement, un imbécile pense avoir définitivement résolu le problème de l'énergie (et accessoirement inventé le mouvement perpétuel).
_________________
Lever le coude est la meilleure façon de ne pas baisser les bras.
Le droit à la différence s'arrête quand ça commence à m'emmerder sérieusement.
Le Colonel

M'en parlez pas, mon p'tit monsieur.
Dans le même genre d'idée, quelqu'un pense encore avoir prouvé P=NP.
_________________
Because we love our Vegemite
We all adore our Vegemite
It puts a rose in every cheek.

macteyss a écrit :C'est de la merde l'enseignement de la thermodynamique oui, il faut attendre de faire de la physique statistique pour y comprendre quelque chose !

Et pour rire avec nos amis belges (Gorion, reviens !) : [http]
_________________
"If the revolution ain't gon' be televised
Then fuck, I'll probably miss it" - Aesop Rock

Last.fm | RYM | XKCD c'est bon, mangez-en !

macteyss a écrit :Ca me rappelle furieusement un épisode des Simpsons avec cette phrase d'Homer à marge "Elle ne fonctionne pas la machine à mouvement perpétuel de Lisa, regarde, elle va de plus en plus vite...."

(il va sans dire que Lisa ne fut jamais au courant de sa trouvaille)
_________________
Cthulhu for president in 2004 2008 2012! / Mouchi vent de trol, mouchi frac de tot atrac / Soooooo cooooooooooooooooool !

preum'z alors

marrant on est en hiver, et il fait beau, mais putain qu'est-ce qu'il fait froid....
_________________
p'tite terrienne sans prétention

Deuze, POURQUOI ??? Faut t'il que je me leve à 7h quand j'ai cours à 12h30.
Sinon il fait beau. OUI beau. ni chaud ni froid.
_________________
Tant va la cruche au nain, qu'à la fin il vomit.
J'ai paniqué ... Hélas.
Encore Fallu(s) t'il que nous sa(u)chions son sexe.

Moubarak s'excite, l'Egypte vient de couper internet... à l'échelle du pays : [http]
_________________
"If the revolution ain't gon' be televised
Then fuck, I'll probably miss it" - Aesop Rock

Last.fm | RYM | XKCD c'est bon, mangez-en !

Gargamel a écrit :C'est pire que tout, ça ! Si on me laissait faire, ce serait direct au poteau et sans procès.
_________________
Lever le coude est la meilleure façon de ne pas baisser les bras.
Le droit à la différence s'arrête quand ça commence à m'emmerder sérieusement.
Le Colonel

Je croyais que c'était un problème ouvert, un de ceux dont on voit fleurir des démonstrations tous les ans, dont aucune n'a été validée ce jour. A moins que ce ne soit un problème indécidable selon ZFC (mais l'axiome du choix, c'est le mal*).

[*] Chaque fois que vous utilisez l'axiome du choix, Dieu tue un chaton. Mais lequel choisit-il ?
_________________
"If the revolution ain't gon' be televised
Then fuck, I'll probably miss it" - Aesop Rock

Last.fm | RYM | XKCD c'est bon, mangez-en !

Ah non, c'est vrai. P = NP.

C'est prouvé dans plein de films, comme Die Hard 4 (où le gars pirate en moins de deux un super ordinateur), Independance Day (ou un virus Mac pirate un ordinateur extraterrestre), ...

J'ai tout bon ?
_________________
#nwnights-fr @ irc.darkmyst.org TitanQuest-FR

Je ne voudrais pas dire de connerie, mes souvenirs commençant à dater un tantinet, mais il me semble bien que ce soit un problème indécidable, équivalent au problème de l'arrêt d'une machine de Türing... (Si y'a gourance de ma part, merci de rectifier).
_________________
Lever le coude est la meilleure façon de ne pas baisser les bras.
Le droit à la différence s'arrête quand ça commence à m'emmerder sérieusement.
Le Colonel

Moui moui moui, si c'est indécidable, alors les proposition « P=NP » et « P≠NP » peuvent toutes deux être acceptées comme axiomes supplémentaires non ? C'est pas un peu emmerdant vu qu'on parle d'algorithmes ? Ou alors je n'ai rien compris, ce qui est possible étant donné que je suis physicien et que ces questions me passent à des années lumières au dessus de la tête .

Si vous avez des références (lisibles, pas du Bourbaki-like donc) sur ces questions ou sur la logique formelle, je suis preneur.
_________________
"If the revolution ain't gon' be televised
Then fuck, I'll probably miss it" - Aesop Rock

Last.fm | RYM | XKCD c'est bon, mangez-en !

j'ai RIEN compris

je suis une quiche en math et en physique (8 et 4 en bac D respectivement).


Z'êtes violent les gars là !
_________________
Les convictions sont des ennemis de la vérité plus dangereux que les mensonges

En gros, si j'ai bien compris le biniou, ça vaut juste dire qu'on trouvera pas mieux que la force brute dans certains cas, et qu'on ne pourra pas trouver de méthode de calcul "polynomial" pour certains algorithmes.

[edit] Gottorp : je te rejoins sur cela
_________________
#nwnights-fr @ irc.darkmyst.org TitanQuest-FR

Childéric a écrit :'tain, je vais me laisser entrainer et je vais sûrement dire des conneries, depuis le temps que je n'ai pas pratiqué le machin...

Bon, en gros c'est pas emmerdant du tout, vu qu'un algorithme et une démonstration mathématiques, au bout du compte, c'est la même chose (correspondance de Curry Howard). Et, dans une théorie, cela ne pose pas de souci de rajouter des axiomes, pourvu que cela ne rende pas la théorie contradictoire.

Exemples : l'hypothèse du continu, l'axiome du choix... Ou encore les différentes version de l'axiome des parallèles d'Euclide qui donnent, selon celle qu'on a choisi, les géométries euclidienne, riemanienne et celle-dont-j'ai-oublié-le-nom.

En vertu de la correspondance sus-nommée, si ça ne perturbe pas la théorie de rajouter des axiomes, ça ne doit pas non plus traumatiser les algorithmes, qui ne sont après tout que les démonstrations des théorèmes.
_________________
Lever le coude est la meilleure façon de ne pas baisser les bras.
Le droit à la différence s'arrête quand ça commence à m'emmerder sérieusement.
Le Colonel

Aha, je vais pouvoir me permettre d'étaler un peu ma science.

N=NP est un problème fondamental en informatique, et sans doute le plus étudié et le plus populaire. Il fait partie des 7 problèmes du millénaire pour la résolution desquels un prix de un million de US$ est attribué (un seul problème a été résolu à ce jour, et le type a refusé ce prix. Classique !). Régulièrement, on voit fleurir des preuves (fausses) que N = NP (ou le contraire). Pour vous dire, ma copine m'a offert un T-shirt « Chuck Norris solved N=NP » (et je le porte en ce moment). Évidemment, la réponse N=NP si P=1 ou N=0 n'est pas satisfaisante.

Sans entrer dans les détails, P et NP sont deux classes de problèmes, deux niveaux de difficulté de problèmes. Il s'agit de problèmes de décision, c'est-à-dire que la réponse au problème est "oui" ou "non". Exemples de problème : « est-ce que 4+7=11 ? », « le chemin le plus court de Paris à Marseille fait-il moins de 300km ? », « 1117 est-il un nombre premier ? », « étant donné une position au jeu de go, le joueur blanc peut-il gagner ? ».

La difficulté est jugée (en l'occurrence) par le temps T que nécessite la résolution du problème par rapport à la longueur x de l'énoncé du problème. P signifie qu'il faut un temps polynomial par rapport à x. Ça signifie que si on double la taille de l'énoncé, la résolution prendra un temps P(2) x T où P(2) est constant. Pour faire simple, on considère que les problèmes de type P sont faciles, parce que les ordinateurs sont de plus en plus puissants ; si un problème de type P et de taille x est difficile aujourd'hui, il sera probablement faisable dans 10 ans.

Les problèmes de type NP sont définis presque pareil. La seule différence, c'est que l'ordinateur a le choix entre plusieurs instructions et qu'il les effectue toutes en même temps. À chaque instruction, il effectue un certain nombre de calculs indépendants en parallèle, mais comme il a plusieurs choix pour chacun de ces calculs, le nombre de calculs qu'il effectue en parallèle est multiplié à chaque instruction. Un tel ordinateur (qui n'existe pas à ce jour, c'est ce qu'on appelle une machine de Turing Non déterministe -- d'où le N de NP) résoud un problème NP en temps polynomial. Un exemple typique de problème NP est le problème du sac à dos illustré ici: [http] ; « étant donné un sac d'une certaine capacité, étant donné des objets avec un certain poids et un certain prix, quelle est la valeur maximale des objets que je peux transporter ? » (en fait, pour en faire un problème décisionnel, il faut demander : puis-je mettre dans le sac suffisamment d'objets pour obtenir une valeur supérieure à k).

Il est facile de prouver que les problèmes P sont tous équivalents (pour une certaine définition d'équivalence), c'est-à-dire qu'ils sont tous aussi difficiles les uns que les autres et que si on sait en résoudre un, on sait résoudre tous les autres. De même pour la classe NP (c'est le théorème de Cook).

La question est : un problème de type NP est-il aussi difficile qu'un problème de type NP ?

On ne sait pas. Et c'est pas faute de chercher depuis des décennies. Le meilleur algorithme pour des problèmes NP que l'on connaisse prend un temps polynomial. En gros, pour le problème du sac à dos, on vérifie toutes les combinaisons d'objets possibles (on peut être un peu plus intelligent que ça, mais globalement, on n'échappe pas à l'exponentielle) ; c'est ce qu'on appelle le calcul brute force. Ça veut dire que si on prend un problème NP de taille x, qu'on ajoute quelques données au problème, on double le temps de résolution. Imaginez, votre problème NP comprend 20.000 lignes et il vous faut 6 mois de calcul pour trouver la solution ; maintenant, vous avez un problème de 20.010 lignes et il vous faut 1 an de calcul ; maintenant, on vous donne un problème de 40.000 lignes...

Pourquoi cette question est importante ? D'abord, résoudre plus efficacement des problèmes de type NP serait vraiment cool. Moi, j'utilise des solveurs SAT (le problème NP le plus connu) tous les jours. En fait, 50% de mon travail actuel porte sur SAT.
Ensuite, de nombreux outils utilisent le fait que certains problèmes sont difficiles à résoudre. Typiquement, la crypto. Déchiffrer un message si vous n'avez pas la clef est très difficile. Et si le méchant hackeur achète un ordi plus puissant, on double la taille des clefs et le hackeur devra attendre plusieurs millénaires avant de pouvoir hacker votre compte bancaire (sauf s'il prouve P=NP).

Oh, et si vous prouvez N=NP, vous voudrez peut-être résoudre Eternity II. C'est un puzzle NP-complet et le résoudre vous donnera 2M US$.
_________________
Because we love our Vegemite
We all adore our Vegemite
It puts a rose in every cheek.

alors, je dis Preums', et je me fous du reste
_________________
p'tite terrienne sans prétention

Deuz.

Merci pour les précisions Gargamel.
_________________
"If the revolution ain't gon' be televised
Then fuck, I'll probably miss it" - Aesop Rock

Last.fm | RYM | XKCD c'est bon, mangez-en !

Merci Garga, ça me rappelle le bon temps. Du coup, je suis plus enclin à te pardonner ta tentative d'empoisonnement massive de la fine fleur de la Biblio à l'aide d'un poison australien.
_________________
Lever le coude est la meilleure façon de ne pas baisser les bras.
Le droit à la différence s'arrête quand ça commence à m'emmerder sérieusement.
Le Colonel

Moi pas. Quelle horreur (à noter que je me suis à nouveau retrouvé face à cette horreur quand je suis allé cherché du champagne chez le producteur, encore heureux qu'il avait une bonne petite eau minérale (aux doux extraits de minéraux qui vont bien ) bénite pour chasser le vilain démon Australien...)
_________________
#nwnights-fr @ irc.darkmyst.org TitanQuest-FR

preum's
_________________
p'tite terrienne sans prétention

Deuze.


Dracenna a écrit :Je reprends un peu le cours de notre convers pour simplement t'informer que beaucoup de cartons m'entourent encore... Donc oui, tu attendras... etc...
_________________
Alors qu'est-ce qu'on fait ? On continue dans la grâce ?

TSHAW.

Troiz.
_________________
#nwnights-fr @ irc.darkmyst.org TitanQuest-FR