设1={1,2,...,n}是1的一个子集.mc(x)是一个偏假p正确蒙特卡罗算法.该算法用于判定所给的整数1≤x≤n是否为集合S中的整数,即x∈S.设q=1-p.由偏假算法的定义可知,对任意x∈S有Prob{mc(x)=true}=1.当x∈S时,Prob{mc(x)=truc}≤q.考虑下面的产生S中随机元素的算法GenRand如下:
假设由语句“x=rnd.Random(n)+1;"产生的整数x∈S的概率为r,证明算法GenRand返回的整数不在S中的概率最多为
设S,T,M为任意集合,判断下列命题的真假。
(1)∅是∅的子集。
(2)如果S∪T=SUM,则T=M。
(3)如果S-T=∅,则S=T。
(4)如果~SUT=E,则ST。
(5)S⊕S=S。