Discussion:Non-déterminisme/Admissibilité

L'admissibilité de la page « Non-déterminisme » est débattue.

Consignes quant à cette procédure :

Qui peut participer ?

Le créateur de la page et les contributeurs ayant un compte ayant fait au moins cinquante contributions aux articles (espace principal) de fr.wikipedia.org au lancement de cette procédure peuvent exprimer leur avis.

Les avis des personnes n’ayant pas de compte ou un compte ayant moins de 50 contributions sont déplacés dans « Avis non décomptés » et ne sont en principe pas pris en considération. Lors de la clôture, les avis sans argumentaire sont également déplacés et ne sont pas pris en compte.

Durée de la consultation

Si un consensus clair s'est dégagé le 8 janvier après l'expiration de sept jours pleins de débat (168 heures), un contributeur ayant réalisé au moins 500 modifications et ayant 3 mois d'ancienneté (utilisateur autopatrolled) qui n'aura pas pris part au débat peut clore la proposition et indiquer si la page est conservée ou supprimée (la suppression devant être demandée à un administrateur). Dans le cas contraire, la discussion se poursuit et peut être close à partir du 15 janvier.

Voir toutes les procédures en cours

Important

• Copiez le lien *{{L|Non-déterminisme}} et collez-le dans la section du jour de la page principale « Débat d'admissibilité » . Attention, un décalage d'un jour est possible en fonction de la mise en page.
• Avertissez le créateur, les principaux contributeurs de l’article et, si possible, les projets associés en apposant le message {{subst:Avertissement débat d'admissibilité|Non-déterminisme}} sur leur page de discussion.

Non-déterminisme

Proposé par : Jean-Christophe BENOIST (d) 31 décembre 2011 à 01:05 (CET)

Cet article, au sujet mal défini, et par conséquent sans interwiki, traite sans doute (mais ce n'est pas clair) de la notion d'automate fini non déterministe, qui est déjà traité par ailleurs. Le sujet mériterait - certes - un article séparé, mais le contenu actuel me semble irrécupérable, et le titre trop vague. Quant à la notion générale de non-déterminisme, c'est bien sûr un redirect sur déterminisme. --Jean-Christophe BENOIST (d) 31 décembre 2011 à 01:05 (CET)

Conclusion

 Suppression traitée par Buisson (d) 8 janvier 2012 à 00:54 (CET)

Raison : Consensus.

Supprimer :

Discussions

Toutes les discussions vont ci-dessous.

En fait il y a plutôt trop d'interwikis potentiels, voir en:non-determinism, il y a également indéterminisme (philo, pas sûr que ce soit la traduction correcte), machine de Turing non déterministe qui permet de définir la classe NP (temps polynomial non déterministe) ... L'article traite surtout (sommairement et sans source) du non déterminisme en prolog (aucune idée si c'est pertinent et correct, mais les automates finis avec des transition non déterministes ne sont invoqués que comme exemple, ce n'est pas le sujet). Ne faudrait-il pas poser la question sur le projet informatique ? Ce serait a minima à conserver en page d'homonymie sinon. Pas sûr par ailleurs que le tiret soit correct en français. Proz (d) 1 janvier 2012 à 21:57 (CET)

Bonjour. En complément des trois situations particulières en informatique signalées plus bas, il en existe une quatrième: le problème suivant (en) requêtes hors domaine est considéré par cette procédure: sélection non-déterministe. -- Concernant les autres emplois du terme, ils sont en majorité revendiqués dans les domaines des sciences cognitives; il est peut-être intéressant de les mettre en relation avec un problème formulé mathématiquement comme pour cet exemple, mais ce n'est sans doute pas évident. --Askedonty (d) 4 janvier 2012 à 21:04 (CET)

Avis

Entrez ci-dessous votre avis sur l’admissibilité du thème à l’aune de l’existence de sources extérieures et sérieuses ou des critères d'admissibilité des articles. Il est recommandé d'accentuer l'idée principale en gras (conserver, fusionner, déplacer, supprimer, etc.) pour la rendre plus visible. Vous pouvez éventuellement utiliser un modèle. N’oubliez pas qu’il est obligatoire d’argumenter vos avis et de les signer en entrant quatre tildes (~~~~).

Supprimer

1.  Supprimer Proposant. --Jean-Christophe BENOIST (d) 31 décembre 2011 à 01:05 (CET)
2.  Supprimer d'accord avec le proposant. Vague, TI, ingérable. --Eodial (d) 1 janvier 2012 à 02:56 (CET)

   Clairement ce n'est pas documenté mais j'ai du mal à voir en quoi ce serait ingérable. http://msdn.microsoft.com/fr-fr/library/ms178091.aspx, http://www.laurentbloch.org/spip.php?article113, http://www-lipn.univ-paris13.fr/taln09/pdf/TALN_6.pdf, http://pop-art.inrialpes.fr/~girault/Cours/Automates/td4.html, etc, etc. --Askedonty (d) 2 janvier 2012 à 07:46 (CET)

   automate fini non déterministe est totalement gérable en effet; mais ce n'est pas cet article. Cet article semble être - au mieux - une page d'homonymie. Les liens que tu donnes pointent sur des sujets très divers, ce qui abonde dans le sens de la non-gérabilité.. Quelle serait la définition à mettre en gras dans l'introduction ? Je reste pour la suppression, quitte à recréer une page d'homonymie, nommée éventuellement autrement (avec ou sans tiret etc..) --Jean-Christophe BENOIST (d) 2 janvier 2012 à 10:21 (CET)

   J'avais suivi dans ce sens mais le sujet ne s'arrête pas aux automates (même si ça ne va pas très-très loin justement). Il y a des stratégies non-déterministes: traitement des aléas, du langage naturel, et le systèmes des certificats. Je crois que c'est le principe pour PROLOG, sous cet aspect. D'autre part, en ce me concerne si je cherche à comprendre le déterminisme je cherche d'abord à le délimiter, d'où le non-déterminisme. --Askedonty (d) 2 janvier 2012 à 12:08 (CET)

   Je vois ce que tu veux dire. Reste à déterminer : si cet article existe : page d'homonymie ou article à part entière ? Si article à part entière : quelle articulation avec indéterminisme ? Il ne faudrait pas non plus dans ce cas que cela soit une compilation "maison" de tous les concepts avec "non-déterministe" dans le nom, ce qui serait une sorte de TI (mais une telle compilation ne pose pas de problème dans le cas d'une page d'homonymie). --Jean-Christophe BENOIST (d) 2 janvier 2012 à 12:29 (CET)

   Oui, clairement ça n'est pas limité aux automates à nombre fini d'états, voir Théorie de la complexité des algorithmes (sur lequel l'article devrait pointer), et il y a bien une idée commune derrière tout ça. L'introduction actuelle ne semble pas absurde non plus. Il y a forcément un sujet du style en:non-deterministic algorithm. Si quelqu'un s'y connaissait un peu en prolog (ou programmation par contraintes ?) ça permettrait d'y voir plus clair (pour le tiret je ne sais pas vraiment, mon habitude est de ne pas en mettre). Proz (d) 2 janvier 2012 à 12:33 (CET)

   Ah là, tout à fait d'accord pour avoir un article algorithme non déterministe, qui permet de définir NP. Je ne suis pas contre recycler (et renommer) cet article ainsi. Mais avant, il y aurait déjà un article séparé sur NP à faire, et sur les machines de Turing non déterministes (par ordre d'importance). Mais on reste avec les questions fondamentales 1) est-ce que on traite un sujet dans cet article, lequel ? 2) Est-ce que on traite N sujets sous forme de page d'homonymie ? 3) Est-ce que on traite N sujets sous forme d'article général, avec articulation à définir avec indéterminisme et source secondaire sur le sujet pour éviter le TI 4) On supprime, et on recrée plus tard à tête reposée le ou les articles qui vont bien. Je suis toujours pour 4) tant que 1) 2) ou 3) n'est pas clairement défendu et étayé. --Jean-Christophe BENOIST (d) 2 janvier 2012 à 15:02 (CET)

   Pour définir formellement NP il y a déjà machine de Turing non déterministe, et NP est déjà couvert par plusieurs articles (un article spécifique est peut-être possible mais pas d'urgence ama), il ne me semble pas que ce serait l'objectif de algorithme non déterministe plus large. Un tel article ne couvrirait pas tout, il semble y avoir des choses du ressort de la programmation, les exemples d'Askedonty parlent de requêtes non déterministes dans les bases de données. Ca peut aussi être un article destiné à évoluer en page d'homonymie (un peu le cas actuel), pas de risque de TI si les choses sont bien séparées. En fait tout semble pouvoir se régler en faisant évoluer l'article, éventuellement en le renommant, donc je ne vois pas trop pourquoi supprimer, sans non plus être très attaché à l'existant, mais bon ce n'est pas le seul article à peine ébauché sur un vrai sujet. Proz (d) 4 janvier 2012 à 22:42 (CET)

   Le problème paraît être qu'il n'y a en réalité pas de rapport immédiat entre non-déterminisme ici et déterminisme mais plutôt avec Déterminisme (Calculabilité). En dehors de Prolog et Datalog il n'y a en effet pas de raison de citer "non-déterministe" de manière aussi impressionante parceque le non-déterminisme s'y réduit à peu-près à ce qui semble être une rustine algorithmique( "fairness"), l'opérateur à point fixe et ses accessoires, qui servent à s'installer dans NDB-PTIME, une rustine conceptuelle (mais de potentiel non négligeable). Au bout du compte la suppression du contenu de l'article pourrait être considérée relativement à ceci et à ceci, et l'intitulé donc en fonction. --Askedonty (d) 6 janvier 2012 à 11:15 (CET)

3.  Supprimer. Nécessité de positionner la notion par rapport à Stochastique voire Heuristique. --Agamitsudo (d) 7 janvier 2012 à 11:52 (CET)

Avis non décomptés

Exception étant faite pour le créateur de l’article, les avis d’utilisateurs récemment inscrits (moins de cinquante contributions...) ou non identifiables (IP, opinions non signées...) ne sont en principe pas pris en compte. Si vous êtes dans ce cas, vous pouvez toutefois participer aux discussions ou vous exprimer ci-dessous pour information :

Proposition de modification

• changement de nom => non-déterminisme (en informatique)
• changement de contenu (ci dessous)
• voir l'état actuel (Utilisateur:Bdenis/brouillon#Non-d.C3.A9terminisme_.28en_informatique.29) et la discussion (Discussion_utilisateur:Bdenis/brouillon)

Non-déterminisme (en informatique)

La notion de non-déterminisme est particulière en informatique : elle renverse le problème du déterminisme, la question n'est pas de savoir si l'avenir est ou n'est pas prévisible, mais de savoir comment prendre en compte l'ensemble des avenirs possibles et aller au delà pour affirmer quelque chose.

Un film peut en donner une idée Smoking / No Smoking de Alain Resnais, qui développe l'ensemble des possibles provenant d'une situation donnée en 2 films, l'un commençant avec

La notion de non-déterminisme apparait en informatique, entre autres, dans la théorie des automates d'état finis (Automate fini), dans le problème "P=NP ?" (Théorie de la complexité des algorithmes) et on la retrouve également en Prolog ou dans l'algorithmique basée sur les points de choix (backtrack).

Automate d'états finis non-déterminisme

Automate NonDéterministe reconnaissant un 1 e n Avant-Avant-Derniere position

(voir Automate fini)

L'approche déterministe semble plus restreinte moins puissante, elle demande de devoir se situer dans une perspective déterministe et refuse d'avoir un doute sur l'avenir. Dans une approche non-déterministe, il semble que l'on gagne en puissance d'expression, car même en l'absence de connaissance de l'avenir l'automate peut prolonger ces calculs en suggérant diverses pistes possibles sans savoir laquelle sera "la bonne". En fait, il s'avère qu'il y a équivalence en matière d'expressivité entre le non-déterminisme et le déterminisme. Ce que saura "calculer" un automate non-déterministe, un automate déterministe pourra aussi le calculer.

Exemple d'automate

L'automate ci-contre présente deux transitions possibles pour 1 sur le début, soit une boucle sur le préfixe, soit une transition en avant vers la fin. Cet automate est donc non-déterministe.

Le langage accepté par cet automate est constitué des mots qui contiennent un 1 en avant-avant-dernière position (un 1 à l'antépénultième position). Lors de la lecture séquentielle d'un caractère, sa position relative par rapport à la fin est inconnue, il se peut que cela soit l'avant-avant-dernier caractère du mot à lire ou pas. Le non-déterminisme utilisé par cet automate propose de considérer ces deux possibilités : c'est l'avant-avant-dernier caractère ou pas.

La théorie des langages formels montre que pour tout langage reconnu par un automate non-déterministe fini, il existe un automate fini déterministe reconnaissant ce même langage.

Dans le cas du langage défini ci-contre, les automates déterministes reconnaissant ce même langage comportent un beaucoup plus grand nombre d'états (la borne du nombre d'états dans le cas général de la détermination d'un automate non-ddéterministe est en 2^n où n est le nombre d'état de l'automate non-déterministe initial), le non-déterminisme introduit une plus grande concision dans l'écriture de l'automate ; cependant, à l'exécution, il n'y a pas nécessairement de gain.

P=NP?

(voir Problème P = NP)

Même si la chose peut sembler lointaine (et bien caché dans l'article Problème P = NP), le N de P=NP signifie Non-déterministe. Il ne faut donc oublier que NP signifie : Non-déterministe Polynomial et non pas Non Polynomial comme une lecture trop rapide ou intuitive pourrait le laisser imaginer.

Dans le cas d'un problème NP, comme la recherche d'une affectation de variables booléennes pour satisfaire un ensemble de contraintes, il y a un ensemble de possibles équivalents sous un certain point de vue (évaluer la valeur de vérité de chaque contrainte) et qui nécessiterait une fonction de choix (un oracle) ou une exploration exhaustive de l'ensemble de ces possibles pour trouver la bonne affectation.

Ce que dit le problème P=NP, c'est que l'exploration de l'ensemble des possibles est incomparablement plus couteux (exponentielle) que d'explorer un possible en particulier (polynomial), mais que cela mis à part, si l'on pouvait explorer cet ensemble de possible comme s'il n'y avait qu'à explorer qu'un seul de ces possible (le bon), le problème serait "raisonable" (polynomial).

Au passage, le "couteux" de l'exploration combinatoire d'une situation problème donnée rend la mise en œuvre peu réaliste, mais cela ne signifie pas qu'il y a imprédictibilité de la (ré)solution du problème donnée au sens le plus large du terme, entre autres car l'ensemble des possibles est fini, grand mais fini.

Non-déterminisme Prolog

En Prolog, le non-déterminisme entraine la possibilité de présenter l'ensemble des réponses possibles à une requête donnée. Ceci repose sur la sémantique de Prolog qui utilise un 'ou' logique à la place de l'alternative ou conditionnelle usuellement utilisée dans les langages de programmation (et qui ressemble plus à un 'ou exclusif' ne laissant pas la place aux deux branches de l'alternative) ou au 'ou bien' qui opère de même.

Exemples d'utilisation du non-déterminisme en Prolog

Quelques idées d'exemples :

• La modélisation des automates d'états finis non-déterminisme est parfois un peu difficile avec les langages de programmation usuel, avec Prolog cela vient naturellement en utilisant la non-déterminisme de Prolog.
• La résolution de problèmes combinatoires (ex : le compte est bon)
• La résolution de problèmes NP

Un exemple explicite, construire P une partie de E :

 partie([],[]).
 partie([E|L],P):-partie(L,P).
 partie([E|L],[E|P]):-partie(L,P).

ainsi

 ?- partie([1,2,3],R).
   R = [];
   R = [3];
   R = [2];
   R = [2, 3];
   R = [1];
   R = [1, 3];
   R = [1, 2];
   R = [1, 2, 3];

Algorithmes de backtrack

(voir Retour sur trace)

Il existe une technique de programmation, non attachée à un langage en particulier, qui développe une approche non-déterministe. C'est la technique du backtrack. Il s'agit de conserver en mémoire les choix effectués lors de la résolution d'un problème et les contextes de la résolution (à l'exécution) lors de ces prises de décision. En cas d'échec final de la résolution, la technique du backtrack consiste à revenir sur ces choix, remettre en cause un à un les choix effectués (en général on commence par le dernier), pour les changer en d'autres décisions et recommencer uen tentative de résolution.

Les techniques de backtrack existent en particulier dans les problèmes de satisfaction de contraintes, les optimisations combinatoires.

Non-déterminisme et déterminisme en informatique

Il y a un paradoxe à parler de non-déterminisme en informatique, car, si l'on excepte quelques domaien de l'informatique comme l'algorithmique probabiliste qui a besoin de hasard et donne des résultats imprévisibles, la notion de non-déterminisme en informatique rentre dans les formes qui renforcent le déterminisme dont se targue en général l'informatique. Une approche non-déterministe (automate, programme prolog, etc.) est tout à fait déterminé, et déterministe. Relancer deux fois la manip, le résultat sera le même : ouf ! et heureusement pour deux formes de programmation ...

Le non-déterminisme en informatique et un déterminisme.

{{Portail|Informatique théorique}} [[Catégorie:Logique mathématique]]