Les contributions sont bienvenues soit sous la forme de commentaires à la suite des définitions, soit sous la forme de nouvelles définitions (voir l'encadré ci-contre).

Contributions are welcome either as comments to the posts or as suugestion (see the frame on the right hand side).
[Draft of the English version]

Las contribuciones son bienvenidas, ya sea como comentarios siguientes definiciones, ya sea como nuevas definiciones (ver cuadro aquí-contra).

Nicolas Balacheff, CNRS, LIG Grenoble

2012/11/16

Problème

"Un problème est défini comme un couple (I, Q) : l'ensemble des instances du problème (I) peut être décrit par plusieurs paramètre et la (ou les) question(s) (Q) porte(nt) sur ces instances (spécifiant les propriétés de la solution attendue). Fixer une instance du problème c'est instancier le problème. Réduire l'ensemble de définition des instances permet de considérer les sous-problèmes de (I,Q)." (Ouvrier-Buffet 2016 p.338)

1 commentaire:

  1. Référent initial de cette définition pour préciser la signification de "instance" :

    "For our purpose, a problem will be a general question to be answered, usually by processing several parameters, or free variables, whose values are left unspecified. A problem is described by giving: (1) a general description, and (2) a statement of what properties the answer or solution, is required to satisfy. An instance of a problem is obtained by specifying particular values for all the problems parameters" (Garey & Johnson 1979 p.4)

    Garey M. R., Johson D. S. (1979) Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman.

    RépondreSupprimer