Trivs i Lisebergs södra

Generic form The master theorem concerns recurrence relations of the form: In the application to the analysis of a recursive algorithm, the constants and function take on the following significance: n  is the size of the problem. a  is the number of subproblems in the recursion. n / b  is the size of each subproblem. (Here it is assumed that all subproblems are essentially the same size.) f  ( n ) is the cost of the work done outside the recursive calls, which includes the cost of dividing the problem and the cost of merging the solutions to the subproblems. Application to common algorithms Algorithm Recurrence Relationship Run time Comment Binary search O (log( n )) Apply Master theorem where  f ( n ) =  n c [3] Binary tree traversal O ( n ) Apply Master theorem where  f ( n ) =  n c [3] Optimal Sorted Matrix Search O ( n ) Apply  Akra-Bazzi theorem  for  p  = 1  and  g ( u ) = log( u ) ...

拜占庭帝国就是5～15世纪的东罗马帝国，拜占庭即现在土耳其的伊斯坦布尔。我们可以想象，拜占庭军队有许多分支，驻扎在敌人城外，每一分支由各自 的将军指挥。将军们只能靠通讯员进行通讯。在观察了敌人以后，忠诚的将军们必须制订一个统一的行动计划——进攻或者撤退。然而，这些将军中有叛徒，他们不 希望忠诚的将军们能达成一致，因而影响统一行动计划的制订与传播。问题是：将军们必须有一个协议，使所有忠诚的将军们能够达成一致，而且少数几个叛徒不能 使忠诚的将军们做出错误的计划——使有些将军进攻而另一些将军撤退了。 抽象出来，可以表述成： 拜占庭将军问题 ：设计一个协议，一个司令要送一个命令给他的n-1个副官，使得 IC1. 所有忠诚的副官遵守同一个命令。 IC2. 假如司令是忠诚的，则每一个忠诚的副官遵守他送出的该命令。 约定：忠诚的将军将遵守协议，而叛徒则可能破坏协议，尽可能的干绕其它人的判断。叛徒是匿名的。而且最后不需要确定谁是叛徒。 注意司令也有可能是叛徒，所以IC2与IC1是不同的。 递归设计协议OM(n, m)为 OM(n, 0): 司令发送命令给所有副官。 副官按照接收到的命令行事。 OM(n, m): 司令发送命令给所有副官，设副官i收到命令vi。 分为独立的n-1轮：对每个副官i，将其视为司令，使用协议A(n-1, m-1)将vi发送到所有其它副官。 这样每个副官都收到n-1条信息，每个副官都按照出现次数更多的命令行事（如果进攻和撤退的命令一样多，则默认取撤退）。 递归证明 引理：当n>2m+k，n个将军中至多k个叛徒，协议A(n, m)满足IC2，即司令是忠诚的，每个忠诚的副官将会执行司令的命令。 进而说明： 当n>3m时，n个将军，且至多m个叛徒，协议A(n, m)可以同时满足IC1和IC2。 更深刻的结论： 当n<=3m时，n个将军中的m个叛徒可以让将军们无法达成一致，也就是满足IC1和IC2的协议不可能存在。 参考： The Byzantine Generals Problem , the first paper involved 可信计算VII:拜占庭将军问题 Byzantine failure -- Wikipedia, the free encyclopedia

18世纪，英国学者贝叶斯(1702～1761)曾提出计算条件概率的公式用来解决如下一类问题：假设H[,1],H[,2]…互斥且构成一个完全事件， 已知它们的概率P(H[,i],i=1,2,…，现观察到某事件A与H[,1],H[,2]…相伴随而出现，且已知条件概率P(A/H[,i])，求 P(H[,i]/A)。贝叶斯公式（发表于1763年）为： P(H[,i]/A)=P(H[,i])P(A/H[,i])/[P(H[,1])P(A/H[,1]) P(H[,2])P(A/H[,2])…] 　　这就是著名的“贝叶斯定理”，一些文献中把P(H[,1])、P(H[,2])称为基础概率，P(A/H[,1])为击中率，P(A/H[,2])为误报率[1]。现举一个心理学研究中常被引用的例子来说明： 　　参加常规检查的40岁的妇女患乳腺癌的概率是1%。如果一个妇女有乳腺癌，则她有80%的概率 将接受早期胸部肿瘤X射线检查。如果一个妇女没有患乳腺癌，也有9.6%的概率将接受早期胸部肿瘤X射线测定法检查。在这一年龄群的常规检查中某妇女接受 了早期胸部肿瘤X射线测定法检查。问她实际患乳腺癌的概率是多大？ 　　设H[,1]＝乳腺癌，H[,2]＝非乳腺癌，A＝早期胸部肿瘤X射线检查（以下简称“X射 线检查”），已知P(H[,1])=1%,P(H[,2])=99%,P(A/H[,1])=80%,P(A/H[,2])=9.6%，求P(H[,1] /A)。根据贝叶斯定理，P(H[,1]/A)=(1%)(80%)/[(1%)(80%) (99%)(9.6%)]=0.078 其实，即使我们没有学过贝叶斯定律，也可以解决上述的问题。 如果患病和没有患病的人概率分别问 1%和 99%， 患病检查的概率和没有患病但是也检查的概率分别为80%和 9.6%。 那么我们做如下假设： 有10000个人， 其中100个为患病者；有80+950.4的人接受了检查，其中950.4为9900人中接受检查的人。 那么我们可以知道对于这10000人里面的一个， 如果她是来接受检查的1030人里面的一个，那么她属于患病的80人中的一个的概率就是80\1030，而这，就是贝叶斯定律给我们的答案。