Discussion:Problème du sac à dos/Article de qualité

Cet article a été promu comme Article de qualité en vertu de ce vote.
Merci de remplacer ce modèle par {{Contestation CdQ}} si le vote est remis en cause.

Article promu au terme du second tour.

• Bilan : 16 pour, 3 contre, 2 neutre.
• Commentaire : proportion favorable de 84,21 % à l'issue de la procédure.

Hégésippe | ±Θ± 28 août 2006 à 02:22 (CEST)

Problème du sac à dos

Proposé par : Manproc 28 juin 2006 à 14:17 (CEST){{{4}}}

L'artice est très complet sur la question (il couvre notamment plein de variantes). Il est clair et bien écrit. Il est de plus beaucoup plus complet que l'article sur en: (ce n'est toutefois pas une preuve de qualité).

Je complète. L'article a vraiment bien évolué depuis sa proposition en AdQ et me parait vraiment d'excellente facture à ce jour, bien plus complet que pas mal de publications sur la question. J'invite tous les gens qui avaient pris une décision au premier tour à revoir leur copie pour évaluer la nouvelle mouture de l'article et je félicite l'ensemble des contributeurs (dont ceux qui travaille dessus en plein milieu de la nuit :) pour ce très bon article. Une question sous-jacente semble se poser et mérite réflexion, la position des articles mathématiques dans l'encyclopédie : Un article qui n'est pas accessible complètement aux béotiens (ce qui est le cas ici : même si une partie peut-être vulgarisée, il restera nécessairement des points très compliqués en raison de la nature même du problème, qui risque de sembler un peu indigeste aux yeux des non mathématiciens/informaticiens) ne peut-il avoir sa place parmi les articles de qualité de WP ? En d'autre terme : les articles de qualité sont-ils réservés aux domaine consensuels et accessibles ? Manproc 9 août 2006 à 12:25 (CEST)

il arrive que des articles à contenu technique soient validés AdQ cf déterminant (mathématiques) ou encore Substitution électrophile aromatique. D'ailleurs la promotion AdQ ne parle que de critères formels, pas de niveau du contenu. Il y a deux choses à distinguer : la vulgarisation, qui peut faire tomber dans des excès de simplification si on ne se surveille pas, et le "dé-jargonnage". En effet nous avons très souvent tendance à utiliser des mots et concepts compliqués quand les mêmees idées peuvent se formuler plus simplement (exemple idiot : parler de vecteur solution complique la lecture quand le n-uplet suffit largement), ou encore à considérer que le lecteur a l'habitude de nos notations même les plus simples (par exemple quand on note les numéros d'objet en indice, il faut introduire cette notation). Peps 9 août 2006 à 14:01 (CEST)

Votes

Format : Motivation, signature. Les votes non motivés ne seront pas pris en compte.

Pour

1. Pour Article complet --Julien Jorge 28 juin 2006 à 14:39 (CEST)

   Pour Très bonne article, présente bien le modèle mathématique et sa résolution algorithmique --Leroy Anthony 13 juillet 2006 à 13:40 (CEST) Moins de 50 contributions dans l'espace encyclopédique. Sebcaen | ☨ 13 juillet 2006 à 14:43 (CEST)

   Je contribue depuis longtemps mais en anonyme. Le vote pour cette page, m'a motivé a créé un compte... 17 juillet 2006 à 16:22 (CEST)

2. Pour Un effort réallisé sur les exemples. Je pense que la promotion des articles mathématiques a toute sa place sur Wikipédia. Channer 13 juillet 2006 à 18:30 (CEST)
3. Pour Les exemples rendent l'article accessible. Le problème du sac à dos est de plus l'un des problèmes NP-complets les plus simples à expliquer. Gene.arboit 25 juillet 2006 à 16:43 (CEST)
4. Pour On peut difficilement être plus complet sur ce sujet, sans tomber dans le travail inédit. FrançoisD 25 juillet 2006 à 16:59 (CEST)
5. Pour Très complet Benoît Guédas 28 juillet 2006 à 12:43 (CEST)
6. Pour Je vote pour même s'il me semble qu'il peut encore y avoir quelques aménagements pour rendre certaines parties de l'article plus accessibles. Peps 28 juillet 2006 à 14:10 (CEST)
7. Pour Complet et intéressant. --Reelax 28 juillet 2006 à 16:51 (CEST)
8. Pour article intéressant - je n'aurais peut-être pas voté s'il n'y avait eu cette remarque que c'est un article pour ceux qui comprennent les mathématiques. Oui, certains articls ne se lisent pas comme le Journal de Mickey, et Wikipedia ne doit pas être *seulement* un outil de vulgarisation. C'est pour cette raison qu'en son temps, j'avais proposé comme AdQ l'équation de Schrödinger . Etre de bon niveau ne devrait pas empêcher un article d'^rtre reconnu com excellent. Gérard 2 août 2006 à 20:41 (CEST)
9. Pour Au vu des changements effectués, et même si deux ou trois restent à faire, àma, l'article atteint des critères AdQ.Salle 9 août 2006 à 12:27 (CEST)
10. Pour Bon article, bien illustré. Jonathan71 11 août 2006 à 13:09 (CEST)
11. Pour Complet sous toutes ses formes, d'après moi. Daïn, the Dwarf causer ^? 17 août 2006 à 00:29 (CEST)
12. Pour Je n'avais jamais entendu parler de cela, mais la lecture de l'article m'a très bien renseigné. Je considère donc que cet article rempli la condition essentielle pour etre un AdQ. Rogilbert21 août 2006 à 20:54 (CEST)
13. Pour j'aime ├‎‎‎‎‎‎‎‎ΞyOne┤‎‎‎‎ 22 août 2006 à 15:07 (CEST)
14. Pour Promis, je ferais toutes les opéraions avant de partir en rando...bien --jonathaneo 24 août 2006 à 11:18 (CEST)
15. Pour Ouf enfin un article bien fait sur la randonée! RGAO 26 août 2006 à 23:17 (CEST)
16. Pour Parce que j'aime bien :-) Grimlock 26 août 2006 à 23:19 (CEST)

Contre

Contre Ça sert à quoi ? D'où a-t-on eu l'idée de se le poser ? — Régis Lachaume ✍ 12 juillet 2006 à 14:21 (CEST)

Le problème du sac à dos modélise des situations. Comme pour la plupart des outils mathématiques, la question "Ça sert à quoi ?" ne se pose pas. Prenons un exemple, les espaces vectoriels, ça sert à quoi ?

Quant à "D'où a-t-on eu l'idée de se le poser ?", même si je ne retrouve pas première apparition de ce problème, je doute que quelqu'un ait eu un jour l'« idée » de se le poser. Un jour un type avait un problème d'optimisation à résoudre, il l'a modélisé en termes mathématiques et, par analogie, lui a donné le nom de problème du « sac à dos ». Pour ce qui est du coté concret du problème, il y a trois exemples sur la page, il n'est pas nécésaire de faire une liste exhaustive. --Julien Jorge 13 juillet 2006 à 17:22 (CEST)

L'article a pas mal évolué et l'on comprend maintenant assez facilement le pourquoi du problème. (Et si un outil mathématique ça sert à quelque chose, par ex. un e.v. généralise la notion de vecteurs dans R^n et ça permet de résoudre simplement tout un tas de problèmes.) — Régis Lachaume ✍ 9 août 2006 à 00:59 (CEST)

1. Contre Un article réservé à ceux ayant un niveau élevé en mathématiques Doch54 13 juillet 2006 à 01:30 (CEST)

   De fait, c'est un problème mathématique... Manproc 13 juillet 2006 à 15:56 (CEST)

   Si la partie « modélisation mathématique » nécessite sans doute un certain niveau de math, le reste du document reste accessible, grâce aux nombreux exemples, à quiconque à déjà vu un contenant à contenance limitée, un objet ayant une masse et une situation apportant un profit (un salaire ? de l'argent de poche ?). La partie résolution a évidemment besoin d'un certain niveau d'algorithmique (au moins savoir ce qu'est un algorithme), pour cause, ce sont des algorithmes. --Julien Jorge 13 juillet 2006 à 17:28 (CEST)

   Contre Après une nuit de réflexion, en l'état actuel, j'ai vraiment trop de réserves...Salle 6 août 2006 à 17:10 (CEST)

2. Contre Semble contenir encore trop de fautes de frappe/orthographe/imprécisions typographiques (j'en ai trouvé trois en quelques dizaines de secondes). Je suis aussi gêné par l'inélégance de certaines phrases dont le style est un eu lourd. Allez je vais essayer d'en alléger une ou deux après avoir voté, mais ça ne suffira pas à alléger le français un peu pataud de trop de passage. --Touriste 9 août 2006 à 23:44 (CEST)

   Plus embêtant, en une bonne dizaine de minutes voire davantage, je n'ai pas du tout réussi à comprendre la preuve du 3-2 (j'aurais bien aimé la réécrire, mais j'ai pas réussi à voir où l'auteur voulait en venir -je décroche essentiellement au tour de passe-passe du "puis en" où on perd dramatiquement des contraintes à première vue, comment peut-ce n'être pas catastrophique je n'ai pas pigé... Mais bon de toutes façons, dans la mesure où j'arrive en principe d'habitude à lire des démonstrations et malgré mon manque de confiance en moi, je crois qu'il faut incriminer l'article plutôt que le lecteur. (Au-delà du fait que je n'ai pas compris, je ne suis pas certain que ce soit judicieux d'utiliser de façon apparemment désordonnée (ou dont je n'ai pas compris la motivation) des sommations pour j dans U et des sommations pour j dans S_i pour exprimer le même cardinal |S_i|) --Touriste 10 août 2006 à 00:26 (CEST)

a priori beaucoup de fautes ont été corrigé par une gentille wikifée, que je remercie ici. Manproc 22 août 2006 à 13:41 (CEST)

En effet, je reviens la veille de la date-limite (je suis du genre procrastinateur) et la nouvelle version de la démonstration se laisse lire en diagonale et comprendre. Cela étant, elle contient un certain nombre de fautes de frappe mineures et me semble pouvoir être davantage expliquée ; je vais m'y atteler, ne nous contentons pas de râler. Mais le fait qu'il existe encore (pour quelques minutes) dans l'article des typos comme « il suffit calculer» ou $s\cap g=\emptyset ~\forall s,t(...)$ me maintient dans ma conviction que l'article doit encore être travaillé : pour un typo qui me saute aux yeux, il doit en rester cinq que je ne vois pas, je connais mes capacités de relecture. Touriste * (Discuter) 27 août 2006 à 16:28 (CEST)

En regardant ça de plus près, d'une part merci à la dite wikifée qui a effectivement fourni quelque chose de très propre ; par contre en apprenant le sujet par le travail sur l'article, je vois quelques imprécisions supplémentaires (problème d'optimisation vs. problème de décision) dans le fond de l'article, que la fée en question a su contourner avec talent, mais qui me gênent fort pour un article labellisé. Je vais de ce pas les rapporter dans la page de discussion de l'article, où mes soucis seront plus à leur place qu'ici. Touriste * (Discuter) 27 août 2006 à 16:59 (CEST)

1. Contre Tenter de comprendre l'article renvoie dés l'introduction à "optimisation combinatoire" Je cite : "Un problème d'optimisation combinatoire consiste à trouver la meilleure solution dans un ensemble discret dit ensemble des solutions réalisables. En général, cet ensemble est fini mais de cardinalité très grande et il est décrit de manière implicite, c'est-à-dire par une liste, relativement courte, de contraintes que doivent satisfaire les solutions réalisables." C'est quoi sinon du charabia technique pour initiés ?.Une encyclopédie doit être didactique et expliciter clairement (avec renvoi explicatifs) et simplement ce dont elle parle, surtout quand le sujet est complexe sinon je ne vois pas l'interêt.SoCreate 25 août 2006 à 12:08 (CEST)

   Le reste de l'introduction explique le problème de façon claire, non ? Le fait de pas savoir ce qu'est un problème d'optimisation combinatoire n'est en rien bloquant. TomT0m 25 août 2006 à 14:47 (CEST)

   Le sac à dos est un exemple de problème d'optimisation combinatoire. Avant de critiquer la façon dont ce dernier terme est présenté (ce qui sort du sujet de l'article ici étudié), il faut lire au moins un exemple ce me semble !

   Quant à tes critiques, j'aime beaucoup la vulgarisation et j'essaie de vulgariser au maximum, mais elle ne doit pas être un alibi pour dire des âneries : ainsi la définition que tu cites (avec le mot discret, celui qui fâche sans doute), est la seule correcte, et comprendre ce "discret" n'est pas facile (ça demanderait un article en soi). C'est pourquoi la définition embraye tout de suite sur un "en général" que je trouve très concret. Surtout que, et tu ne le dis pas, on continue immédiatement avec un exemple. Un mot est du charabia technique seulement s'il n'a pas d'équivalent à la fois simple et rigoureux (peut être cardinalité, qui est pourtant du vocabulaire classique -> nombre d'éléments si tu préfères). Peps 25 août 2006 à 14:50 (CEST)

Neutre / autres

# (mais presque contre) J'aime bien l'idée qu'on n'est pas obligés tout le temps de ne faire que de la vulgarisation, et rien que pour ça, je suis tenté de voter pour. Cependant, il y a quelques points qui me chagrinent : la partie histoire me laisse un peu sur ma faim (je ne connais pas, mais j'ai l'impression qu'on pourrait faire mieux) ; la démonstration de NP-complétude est frustrante puisqu'elle renvoie à une autre propriété de NP-complétude qui est wikipediennement inexistante à l'heure actuelle ; j'aurais bien aimé qu'on tire la morale des divers points évoqués : NP-complets + algo approchés +algos exacts? en pratique, que parvient-on à calculer? et en combien de temps? je n'arrive vraiment pas à le voir et j'aurais aimé qu'on me l'explique (j'ai jeté un coup d'œil vite fait, il est tard, désolé si des choses m'ont échappé). Enfin, la rédaction pourrait être meilleure par endroits, il me semble.Salle 6 août 2006 à 02:11 (CEST)

1.  Neutre L'article a bien évolué, mais je ne suis pas assez calé pour juger. — Régis Lachaume ✍ 9 août 2006 à 00:59 (CEST)
2.  Neutre d'habitude je vote contre les articles scientifiques auxquels je comprend rien, là je comprend donc ... mais ça m'empeche pas de penser que des explications "vulgaires" seraient les bienvenues. Dans un article de ce niveau, je ne pense pas que ce soit la francisation du Turbo Pascal qui facilite vraiment la compréhension.--Aliesin 15 août 2006 à 02:00 (CEST)

Discussions

Je pense qu'il faudrait donner au moins une idée de la réduction de NP-complétude du problème. Autrement, qu'est-ce que les autres pensent de l'historique, maintenant ? Gene.arboit 12 juillet 2006 à 21:26 (CEST)

J'ai ajouté une preuve de NP complétude, à partir de couverture exacte pour que ça corresponde à ce qui est présenté sur la page des 21 problèmes NP-complets de Karp. Ceci dit, c'est tout frais et une relecture serait la bienvenue. La preuve est peut-être simplifiable ? En tout cas les non mathématiciens risquent de ne pas apprécier tous ces symboles ;-) --Julien Jorge 23 juillet 2006 à 15:51 (CEST)

J'ai fait une relecture, mais pas en profondeur (pas encore...). Il manque une référence à « Garfinkel et Nemhauser (1972) ». Un schéma du problème (en général, au moins) serait probablement bienvenu des non-mathématiciens. L'article espagnol a une image d'exploration d'un arbre... à quel algorithme s'applique-t-il ? J'espère que l'article va passer au 2e tour... il reste qq. jours ! Gene.arboit 23 juillet 2006 à 21:43 (CEST)

L'exploration de l'arbre correspond à une exécution de la procédure de séparation et d'évaluation. Un sous arbre correspond à la recherche d'une solution à un sous problème et la prise d'un arc correspond à l'affectation d'une valeur à une variable. Ça se lit en faisant des aller-retours de haut en bas et prioritairement à gauche (je ne sais pas si c'est clair...). L'algorithme de base est très simple, je pourrais l'ajouter ? J'ai ajouté la référence, je l'ai trouvée dans un article sur le sac à dos mais je n'ai pas pu avoir accès au livre. --Julien Jorge 24 juillet 2006 à 01:07 (CEST)

C'est donc pour l'algorithme qui prend un temps exponentiel... Ça serait une façon d'illustrer la difficulté du problème. Je vais essayer de faire une lecture définitive dans les jours qui suivent... Peut-être que Utilisateur:Jean-Luc W et Utilisateur:Dake pourraient aussi être intéressés. Gene.arboit 24 juillet 2006 à 16:15 (CEST)

Salut je trouve que l'article est bien mais considère comme allant de soi un certain nombre de choses difficiles pour les non initiés.

• j'ai essayé d'adoucir la formulation de la partie énoncé mathématiques en expliquant bien ce que représentent les variables
• j'ai intégré le dessin de l'article espagnol : même si on peut l'utiliser pour décrire l'algorithme de séparation et évaluation, il est possible de s'en servir aussi pour faire comprendre ce qu'on appelle "exploration systématique". J'ai essayé d'utiliser un langage descriptif plus naïf que algorithmique. Si ça vous paraît idiot, supprimez
• dans le paragraphe suivant (preuve de NP complétude), pour donner une autre idée de trucs un peu difficiles à passer pour le béotien, on parle d' "instance" comme d'une évidence. Il faudrait un petit rappel sur ce vocable. Il doit y avoir d'autres endroits mais je n'ai pas encore tout regardé de près.

Peps 26 juillet 2006 à 15:47 (CEST)

À vrai dire, je ne pense pas que l'on puisse expliquer une preuve de NP-complétude formellement (et donc proprement) tout en restant accessible à un public qui ne connaît pas le domaine de la complexité algorithmique. Si on considère que le lecteur connaît ce domane, alors il n'est pas exagéré de considérer qu'il sait ce qu'est une instance d'un problème, non ? --Julien Jorge 26 juillet 2006 à 16:27 (CEST)

Il faudrait au moins une page d'homonymie pour instance... ! Gene.arboit 26 juillet 2006 à 17:06 (CEST) Fait Gene.arboit 27 juillet 2006 à 19:05 (CEST)

Merci. Je pense, Julien, qu'on ne peut pas partir du principe que l'utilisateur sait déjà plein de choses avant de mettre les yeux sur l'article. Il faut essayer de satisfaire à la fois les lecteurs les plus ignares en leur présentant au minimum les grandes lignes, et les plus avertis en leur donnant du grain à moudre. Le coeur de cible c'est le lecteur honnête, décidé à faire quelques efforts, qui doit quand même comprendre une partie conséquente de l'article, et repérer que telle ou telle section, franchement technique, existe mais est au-dessus de son niveau. Peps 28 juillet 2006 à 14:10 (CEST)

• AMHA il manque un tout petit peu de blabla pour lier le tout et une illustration pour rendre tout ca visuel. Je pense notament qu'un petit exemple de resolution par programation dynamique serait une bonne idée.

Commentaires de Salle

J'aime bien l'idée qu'on n'est pas obligés tout le temps de ne faire que de la vulgarisation, et rien que pour ça, je suis tenté de voter pour. Cependant, il y a quelques points qui me chagrinent : la partie histoire me laisse un peu sur ma faim (je ne connais pas, mais j'ai l'impression qu'on pourrait faire mieux ; en particulier, sur les motivations du problème, la réponse apportée par Utilisateur:Julien Jorge ne me satisfait pas) ; la démonstration de NP-complétude est frustrante puisqu'elle renvoie à une autre propriété de NP-complétude qui est wikipediennement inexistante à l'heure actuelle ; j'aurais aussi bien aimé qu'on tire la morale des divers points évoqués : NP-complets + algo approchés +algos exacts? en pratique, que parvient-on à calculer? et en combien de temps? je n'arrive vraiment pas à le voir et j'aurais aimé qu'on me l'explique (j'ai jeté un coup d'œil vite fait, il est tard, désolé si des choses m'ont échappé). Enfin, la rédaction pourrait être meilleure par endroits, il me semble.Salle 6 août 2006 à 17:13 (CEST)

L'histoire pourrait être améliorée, j'en conviens... j'essaie d'y voir. Pour la NP-complétude, est-ce que c'est au sujet du problème de la couverture exacte ? On pourait au moins l'ébaucher, en effet... Une conclusion serait aussi de mise. Je peux essayer d'y voir, mais l'auteur principal est probablement mieux placé. Gene.arboit 7 août 2006 à 20:17 (CEST)

Par définition (mais je pense que tu le sais), une démonstration de NP-Complétude se fait à partir d'un problème déjà NP-Complet, sauf le fameux Théorème de Cook. J'avais commencé à essayer de reprendre des preuvex fréquentes de NP-Complétude, mais c'est un travail difficile et ce sont des articles qui n'intéressent personne (il n'y a qu'à voir les réaction ici : "c'est des maths : c'est nul"). Bref, amha c'est déjà un gros travail d'avoir placé la preuve de NP-Complétude pour le KP, si en plus il faut se taper les preuves pour toute la chaîne jusqu'au théorème de Cook, c'est le travail de plusieurs mois à temps plein :). Manproc 9 août 2006 à 12:17 (CEST)

En fait je ne le savais pas, mais c'est de ma faute, étant donné que l'information est accessible dans l'article Théorie de la complexité. J'apprécie les efforts qui ont été d'ores et déjà faits, et je change mon vote ; j'aurais peut-être juste aimé une conclusion, comme disait Gene.Arboit, parce qu'entre la NP-complétude, les algo exacts, et les algos approchés, on a un peu de mal à voir qui apporte quoi, et dans quelles limites.Salle 9 août 2006 à 12:27 (CEST)

Preuve de NP-complétude

(réponse de Julien Jorge que je transfère pour y répondre sur la page de discussion de l'article ; d'une part c'est plus à sa place qu'ici et d'autre part c'est plus pratique de disposer de deux teintes de fond pour savoir qui dit quoi...) --Touriste 10 août 2006 à 11:28 (CEST)