Geodesic
Guessing secrets
The electronic journal of combinatorics, Tome 8 (2001) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Suppose we are given some fixed (but unknown) subset $X$ of a set $\Omega$, and our object is to learn as much as possible about the elements of $X$ by asking binary questions. Specifically, each question is just a function $F: \Omega \rightarrow \{0,1\}$, and the answer to $F$ is just the value $F(X_i)$ for some $X_i \in X$, (determined, for example, by a potentially malevolent but truthful, adversary). In this paper, we describe various algorithms for solving this problem, and establish upper and lower bounds on the efficiency of such algorithms.
DOI : 10.37236/1557
Classification : 68R05, 05C65, 68M10, 91A05, 91A43, 91A80
Mots-clés : game of two players, optimal strategy, algorithm, graph, hypergraph 
@article{10_37236_1557,
     author = {Fan Chung and Ronald Graham and Tom Leighton},
     title = {Guessing secrets},
     journal = {The electronic journal of combinatorics},
     year = {2001},
     volume = {8},
     number = {1},
     doi = {10.37236/1557},
     zbl = {0961.68100},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1557/}
}
TY  - JOUR
AU  - Fan Chung
AU  - Ronald Graham
AU  - Tom Leighton
TI  - Guessing secrets
JO  - The electronic journal of combinatorics
PY  - 2001
VL  - 8
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1557/
DO  - 10.37236/1557
ID  - 10_37236_1557
ER  - 
%0 Journal Article
%A Fan Chung
%A Ronald Graham
%A Tom Leighton
%T Guessing secrets
%J The electronic journal of combinatorics
%D 2001
%V 8
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/1557/
%R 10.37236/1557
%F 10_37236_1557
Fan Chung; Ronald Graham; Tom Leighton. Guessing secrets. The electronic journal of combinatorics, Tome 8 (2001) no. 1. doi: 10.37236/1557

Cité par Sources :