Je cherche à savoir s'il y a un mot précis utilisé dans le cadre de la théorie de la complexité des algorithmes. Mon premier réflexe a été de chercher dans Wikipedia. Voici ce que dit l'article en anglais:
Problems that can be solved but not fast enough for the solution to be useful are called intractable http://en.wikipedia.org/wiki/Intractability
Sur http://www.granddictionnaire.com , on trouve uniquement 'intractable' dans le contexte de la médecine, dont la traduction est 'réfractaire'; je ne sais pas si ça peut convenir dans ton contexte...
Par contre ce même dictionnaire indique que 'tractable' existe aussi bien en français qu'en anglais, dans le contexte de l'intelligence informatique.
« A problem is said to be tractable if a solution is feasible given finite resources, i.e. a solution call be found using a reasonable amount of time and space. »
Donc peut-être que 'intractable' est un néologisme, et qu'on peut utiliser le même mot en français dans ce contexte...
Dans ton cas, « intractable » est « non résoluble en temps polynomial. »
Car t'as plein de problème plus durs qu'NP, qui sont (au moins) tout autant intractables… (et donc ta citation, c'est de la merde, si je puis m'exprimer ainsi).
Va chercher quelques papiers (de préférence académiques, comme des supports de cours) en français sur "3-SAT", "coloriage de graphe" et "problème du sac-à-dos", tu devrais avoir des traductions.
J'ai fini par trouver.
Effectivement, (in)tractable se traduit par (in)traitable dans le domaine de la complexité des algorithmes.
Plusieurs personnes me l'ont dit (ici et sur developpez.com), mais je ne pouvais pas les croire sur parole.
Ce n'est qu'en mettant dans google "intraitable NP-complet"[1] que j'ai fini par en être convaincu: les cours d'algorithmique (celui[2] traduisant quelques passages de l'ouvrage de Cormen[3] par exemple) parlent bien de problèmes traitables et intraitables.
# google
Posté par gaaaaaAab . Évalué à 2.
dans le contexte, insoluble a l'air pas mal.
[^] # Re: google
Posté par aurel (site web personnel, Mastodon) . Évalué à 2.
[^] # Re: google
Posté par gaaaaaAab . Évalué à 1.
[^] # Re: google
Posté par tiot (site web personnel) . Évalué à 4.
Insoluble me paraît très mauvais.
[^] # Re: google
Posté par gaaaaaAab . Évalué à 2.
cf http://linuxfr.org/comments/1075397.html#1075397
[^] # Re: google
Posté par gaaaaaAab . Évalué à 2.
bon, oubliez moi sur ce thread, je raconte vraiment nimp' :D
# Début de réponse.
Posté par GCN (site web personnel) . Évalué à 2.
http://www.wordreference.com/enfr/intractable
[^] # Re: Début de réponse.
Posté par GCN (site web personnel) . Évalué à -1.
# Wikipedia
Posté par Amine "nh2" Brikci-Nigassa (site web personnel) . Évalué à 2.
Problems that can be solved but not fast enough for the solution to be useful are called intractable
http://en.wikipedia.org/wiki/Intractability
Seulement, je n'arrive pas à trouver le mot équivalent en français. Il est peut être dans l'article [[théorie_de_la_complexité_des algorithmes]] http://fr.wikipedia.org/wiki/Th%C3%A9orie_de_la_complexit%C3(...) mais je ne vois pas lequel c'est :-(
GNU's Not Unix / LINUX Is Not Unix Xernel
# granddictionnaire.com
Posté par jigso . Évalué à 1.
Par contre ce même dictionnaire indique que 'tractable' existe aussi bien en français qu'en anglais, dans le contexte de l'intelligence informatique.
« A problem is said to be tractable if a solution is feasible given finite resources, i.e. a solution call be found using a reasonable amount of time and space. »
Donc peut-être que 'intractable' est un néologisme, et qu'on peut utiliser le même mot en français dans ce contexte...
# inextricable
Posté par fyah . Évalué à 5.
Qui ne peut être démêlé, élucidé: Un problème inextricable.
Cdlt,
# Intracteur à voile.
Posté par Axioplase ıɥs∀ (site web personnel) . Évalué à 2.
Car t'as plein de problème plus durs qu'NP, qui sont (au moins) tout autant intractables… (et donc ta citation, c'est de la merde, si je puis m'exprimer ainsi).
Va chercher quelques papiers (de préférence académiques, comme des supports de cours) en français sur "3-SAT", "coloriage de graphe" et "problème du sac-à-dos", tu devrais avoir des traductions.
# [Résolu] "intractable" = "intraitable"
Posté par Amine "nh2" Brikci-Nigassa (site web personnel) . Évalué à 1.
Effectivement, (in)tractable se traduit par (in)traitable dans le domaine de la complexité des algorithmes.
Plusieurs personnes me l'ont dit (ici et sur developpez.com), mais je ne pouvais pas les croire sur parole.
Ce n'est qu'en mettant dans google "intraitable NP-complet"[1] que j'ai fini par en être convaincu: les cours d'algorithmique (celui[2] traduisant quelques passages de l'ouvrage de Cormen[3] par exemple) parlent bien de problèmes traitables et intraitables.
Merci à tous.
[1] http://www.google.com/search?hl=fr&q=intraitable+NP-Comp(...)
[2] http://www.ift.ulaval.ca/~bherer/Chapitre%209%20(np-completu(...)
[3] http://books.google.com/books?id=NLngYyWFl_YC&pg=PA968&a(...)
GNU's Not Unix / LINUX Is Not Unix Xernel
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.