查看文章

This paper presents some optimal interactive algorithms for some problems related to learning of monotone Boolean functions. These algorithms are based on the fundamental Hansel theorem. The advantage of the algorithms is that they are not heuristics, as is often the case of many known algorithms for general Boolean functions, but they are optimal in the sense of the Shannon function. This paper also formulates a new problem for the joint restoration of two nested monotone Boolean functions f₁ and f₂. This formulation allows one to further decrease the dialogue with an expert and restore nonmonotone functions of the form f ₂&|f ₁. The effectiveness of the proposed approaches is demonstrated by some illustrative computational experiments.