算法导论33.2 Exercises 答案

33.2-1

引理33.3说明了，只要至少有一次算法\(A\)进行了一次错误判断，那么整个集合就排除掉至少一半的专家。也就是说，\(A\)只要产生最多\(\lceil\lg n\rceil\)次错误的答案，就清空一次集合\(S\)。考虑\(A\)回答错误了某个问题后，集合\(S\)是第\(k\)次被清空，这说明\(A\)最多回答错误了\(k\lceil\lg n\rceil\)次。

如果专家在某一次回答中被从\(S\)中移出去，那么它进行了一次错误的回答。由于\(S\)被清空\(k\)次，因此他至少在这个过程中回答错误了\(k\)次问题。也就是说，\(\forall i\in[1,n],m_i\ge k\)均成立，因此有\(m^{\ast}\ge k\)。

使用\(k\le m^{\ast}\)这个事实，回代到上面的\(k\)，我们可以知道\(A\)最多回答错误了\(m^{\ast}\lceil\lg n\rceil\)次。

33.2-2

令\(f(x)=\ln (1-x)+x^2+x\)，那么我们只需要证明\(\forall x\in[0,1/2],f(x)\ge 0\)即可。

实际上，\(f(0)=0,f(1/2)=\dfrac{3}{4}-\ln 2>0\)。

可以知道，\(f'(x)=-\dfrac{1}{1-x}+2x+1=\dfrac{x(2x-1)}{1-x}\)。那么\(\forall x\in[0,1/2],f'(x)\ge 0\)成立。

因此\(f(x)\)在\([0,1/2]\)上是单调递增的，有\(f(x)\ge f(0)=0\)，因此原结论成立。