Archive for the ‘Algorithm/Mathematics’ Category
CLRS Problem 11.1-4
简单来说就是给定一个未初始化的巨大的数组，然后通过它实现一个字典。所谓未初始化是指一开始里面元素的值都是随机的，巨大是指可以假设数组长度范围很大，对这个数组做初始化工作（例如清零）的代价自然也是很大。现在的问题是，利用这个数组设计出来的字典，要求初始化、查找、插入、删除操作都能在O(1)时间内完成。
Intructor’s Manual 上的解答设计了一个很巧妙的验证策略。假设T为那个巨大的数组，S为辅助栈，那么对于一个键k，如果k存在于这个字典中，则T[k]保存的是 k在S中的位置j，而S[j]则保存了k值。即1 ≤ T[k] ≤ top[S], S[ T[k] ] = k, T [ S[j] ] = j，我们称这个条件为“验证环”。这个设计的关键在于T和S能够互相验证，从而排除了未初始化位置上随机值的干扰。
还有一个问题就是，键k对应的值v应该怎么保存呢？其实只要维护另外一个和T或者S平行的数组就行了，既然S的元素个数远小于T，选择和S平行即可。
根据这个验证策略，我们就能设计出词典的基本操作了：
初始化：建立一个大小为0的栈
查找：给定键k，检查 1 ≤ T [k] ≤ top[S] && S[ T[k] ] = k，如果满足则返回对应值，否则返回NULL
插入：如果键已经存在则直接替换；否则将新的键值入栈，并且维护T[k] ← top[S]
删除：要确保两件事，一是验证环要被破坏，二是栈S的空洞要被填补。通过把栈顶的元素移动到要删除的元素位置，我们能同时确保这两点：
S[ T[k] ] ← S[ top[S] ] S[ T[k] ] ← S [ top[S] ] T[ S[ T[k] ] ] ← T [k] T[k] ← 0 top[S] ← top[S] − 1
所有操作都能在O(1)时间内完成
原题：We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage, and initializing the entire array is impractical because of its size. Describe a scheme for implementing a direct-address dictionary on a huge array. Each stored object should use O(1) space; the operations SEARCH, INSERT, and DELETE should take O(1) time each; and the initialization of the data structure should take O(1) time. (Hint: Use an additional stack, whose size is the number of keys actually stored in the dictionary, to help determine whether a given entry in the huge array is valid or not.)
Chomp游戏
把一堆石子排成n行m列，两人轮流从里面取出石子，条件是取出一个石子后所有在它右边和上面的石子也要被取走。谁取走最后一个石子就算输。以3*5的棋盘举例来说，先手取了(2,5)，因此(3,5)也要被取走；后手取了(3,3)，同时也要取走(3,4)。现在棋盘的状态如下（O代表这个位子的石子还没被取走，x代表已经被取走）：
3 O O x x x 2 O O O O x 1 O O O O O 1 2 3 4 5
接下来先手又取了(2,1)，于是第二排和第三排就一颗石子都不剩了
3 x x x x x 2 x x x x x 1 O O O O O 1 2 3 4 5
后手取(1,2)
3 x x x x x 2 x x x x x 1 O x x x x 1 2 3 4 5
接下来先手就只能取最后一个石子了，后手胜。
这个游戏像是Nim Game的二维版本。于是问题也来了，能不能保证先手或者后手有必胜策略呢？
答案是除了1*1的棋盘，对于其他大小的棋盘，先手总能赢。有一个很巧妙的证明可以保证先手存在必胜策略，可惜这个证明不是构造性的，也就是说没有给出先手怎么下才能赢。证明如下：
如果后手能赢，也就是说后手有必胜策略，使得无论先手第一次取哪个石子，后手都能获得最后的胜利。那么现在假设先手取最右上角的石子(n,m)，接下来后手通过某种取法使得自己进入必胜的局面。但事实上，先手在第一次取的时候就可以和后手这次取的一样，进入必胜局面了，与假设矛盾。
另外这个证明是基于Zermelo’s theory，这个理论保证在这样一种游戏中（两人博弈，信息完全公开，不存在偶然事件且能在有限步里面决出胜负），先手或后手肯定存在一种必胜策略。
相关链接：
http://en.wikipedia.org/wiki/Zermelo’s_theorem_(game_theory)
几个有趣的Quine变种
Quine是指一类能生成自己的程序，例如下面这个C程序运行后就能把自己的源码完整的打印出来：
char*f="char*f=%c%s%c;main()
{printf(f,34,f,34,10);}%c";
main(){printf(f,34,f,34,10);}
这类程序的构造方法计算理论导引或者其他相关的书籍中都有涉及，这里不再赘述。这个月看到几个Quine的变种，都挺有趣的。
首先是sigfpe构造出来的三阶Quine，这是一个只有两行的Haskell程序：
q a b c=putStrLn $ b ++ [toEnum 10,'q','('] ++ show b ++ [','] ++ show c ++ [','] ++ show a ++ [')']
main=q "q a b c=putStrLn $ b ++ [toEnum 10,'q','('] ++ show b ++ [','] ++ show c ++ [','] ++ show a ++ [')']" "def q(a,b,c):print b+chr(10)+'q('+repr(b)+','+repr(c)+','+repr(a)+')'" "def e(x) return 34.chr+x+34.chr end;def q(a,b,c) print b+10.chr+'main=q '+e(b)+' '+e(c)+' '+e(a)+' '+10.chr end"
这段程序牛逼在哪里呢？运行后这个程序首先会输出一个Python程序，然后再运行这个Python程序会输出一段Ruby代码，最后这个Ruby代码的运行结果是原来的程序。或者说
$ runhaskell quine.hs | python | ruby
的运行结果就是这段程序本身。
另外两个Quine变种都和zip有关。一个是解压得到自己的gzip文件；另一个看起来更强大一点（不过是真的“更强大”吗？），解压自己能得到一个图片和自己本身，基于lz77算法。
两个zip quine的下载地址分别是http://upload-001.yo2cdn.com/wp-content/uploads/74/7487/2009/09/selfgz.rar和http://steike.com/code/useless/zip-file-quine/droste.zip。
两个和函数构造相关的趣味面试题
http://stackoverflow.com/questions/731832/interview-question-ffn-n
http://stackoverflow.com/questions/732485/interview-question-ffx-1-x
问题描述很简单，第一个问题是实现一个函数f，参数为一个带符号的32位整型，使得f(f(x)) = -x，即调用两次后返回的结果为原来的相反数；另一个问题也是实现一个函数g，参数为一个32位浮点，最后使得g(g(x)) = 1/x。如果不能满足所有的情况，就满足尽可能多的情形。
第二个问题比第一个问题简单一点，目前支持数最高的两个答案如下：
Read the rest of this entry »
安全方面的经典论文：A Logic of Authentication
最近有点忙，今天总算在某个课题deadline前把论文憋出来交上去了。跑这儿来推荐两篇上个月看到的比较有意思的paper，都比较偏理论，也很老。
今天写介绍下第一篇，剑桥大学的A Logic of Authentication，中了SOSP ’89，整理后发在1990年的ACM Transactions on Computer Systems上。
http://www.csie.fju.edu.tw/~yeh/research/papers/os-reading-list/burrows-tocs90-logic.pdf
（另一篇是Safe Kernel Extensions Without Run-Time Checking，改天再写点介绍）
这篇paper的主要工作是通过构造一种多种类的模态逻辑(many-sorted model logic)，来检查网络中验证协议的安全性。
基础的逻辑分三部分：
原语，如验证双方A和B，以及服务器S，下文用P Q R泛指
密钥，如K_ab代表a和b之间的通讯密钥，K_a代表a的公钥，{K_a}^{-1}代表对应的私钥，下文用K泛指
公式（或者陈述），用N_a, N_b等表示，下文用X Y泛指
接下来定义以下约定（constructs）
P 信任 X: 原语P完全信任X
P 看到 X: 有人发送了一条包含X的信息给P，P可以阅读它或者重复它（当然通常是在做了解密操作后）
P 说了 X: 原语P发送过一条包含X的信息，同时也可以确定P是相信X的正确性的
P 控制 X: P可以判定X的正确与否。例如生成密钥的服务器通常被默认为拥有对密钥质量的审核权。
X 是新鲜的: 在此之前X没有被发送过。这个事实可以通过绑定一个时间戳或者其他只会使用一次的标记来证明。
P <-K-> Q: P和Q可以通过共享密钥K进行通讯，且这个K是好的，即不会被P Q不信任的原语知道。
K-> P: P拥有K这么一个公钥，且它对应的解密密钥K^{-1}不会被其他不被P信任的原语知道。
P <=X=> Q: X是一个只被P和Q或者P和Q共同信任的原语知道的陈述，只有P和Q可以通过X来相互证明它们各自的身份，X的一个例子就是密码。
{X}_K: X是一个被K加密了的陈述
<X>_Y: 陈述X被Y所绑定，Y可以用来证明发送X的人的身份
好了，总算把这些约定列完了，然后来看看通过这些约定能推出一些什么东东：
如果 P 相信 (P <-K-> Q), 且 P 看到 {X}_K，那么 P 相信 Q 说了 X。
这个例子很简单，既然P Q有安全的密钥K，那么P看到通过K加密后的X肯定认为就是Q发出的。
又比如，
如果 P 相信 Q 控制 X，P 相信 (Q 相信 X)，那么 P 相信 X
也很容易理解，既然 P 相信 Q 的判断，那么 Q 相信什么 P 自然也就相信了。
再举一个例子
如果 P 相信 Y 是新鲜的，那么 P 相信 (X, Y) 也是新鲜的。
这里(X, Y)表示 X 和 Y 的简单拼接，也很容易理解，既然 Y 之前没出现过，那么 X 和 Y 的组合自然也没出现过。
一个协议要被定义为安全，最起码要满足
A 相信 A <-K->B，B 相信 A <-K->B
即双方要互相信任密钥是安全的
再健壮一点的协议，还要满足
A 相信 (B 相信 (A 相信 A <-K->B))，反之一样
即A B不仅相信密钥，也相信对方相信自己对密钥的信任。
有 了这些简单却强大的工具后，接下来这篇paper开始着手分析一些协议，包括Kerberos协议，Andrew Secure RPC 握手协议等，还指出了其中的一些问题和改进措施，例如CCITT X.509 协议中可以通过重复发送一条老的信息来模仿成加密双方中的一员。
具体的分析不贴上来了，一方面对于我这个不熟悉TeX的人来说码公式实在麻烦，另一方面我实在困死了 =_=
建议有兴趣的朋友好好看看这篇经典paper
Godel, Escher, Bach [2]
1. 素数判定的形式化系统，精彩！
合数的判定系统比较容易构造，素数的判定当然不能简单的通过“不是合数”来解决。
首先构造一个不整除的概念(DND)
公理模式：xyDNDx，其中x和y是短横组成的符号串。（a>b，a自然不整除b）
生成规则：如果xDNDy是个定理，那么xDNDxy也是个定理。
接下来定义一个描述z在2到x的范围内没有因子的语言，zDFx (Divisor-Free)
规则1：如果–DNDz是个定理，那么zDF–也是个定理。
规则2：如果zDFx与x-DNDz都是定理，那么zDFx-也是个定理。
好了，到这里已经能检查一个数是否在给定范围内找出因子了，定义素数(Pz)就变得很简单。
规则：若z-DFz是个定理，那么Pz-是个定理。
再处理一个特例，为2制定一条公理
公理：P- -
Godel, Escher, Bach [1]
1. 哥德尔定理
用比较通俗的英文来说，就是
All consistent axiomatic formulations of number theory include undicidable propositions.
2. 图形和衬底也许会不带有完全相同的信息
There exist formal systems whose negative space (set of non-theorems) is not the positive space (set of theorems) of any formal system.
用更technical的说法
There exist recursively enumerable sets which are not recursive.
这里recursively enumerable指能按照typographical规则生成，而recursive则对应域指衬底也是个图形的图形。
由此得出一个结论
There exist formal systems for which there is no typographical decision procedure.
证明很简单，用反证法。如果所有的形式系统都能有typographical的判定方法，那么逐个测试所有的符号串，从而能生成一个非定理集合，与前面的定理矛盾。
3. 关于那个数列谜题
{Ai} = 1, 3, 7, 12, 18, 26, 35, 45, 56, 69, …
既然讲到了衬底自然要考虑这个，负空间数列为
{Bi} = 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, …
An = An-1 + Bn-1
Rotating Calipers
中文翻译应该叫旋转卡壳，搜狗提醒说卡应该读成qia
http://cgm.cs.mcgill.ca/~orm/rotcal.html
涉及的问题：
- Computing distances
- Enclosing rectangles
- Triangulations
- Properties of convex polygons
- Thinnest transversals
带环链表求环的起点
很经典的问题了，求环的长度可以用两个步长分别为1和2的指针遍历链表，直到两者相遇，此时慢指针走过的长度就是环的长度。另外相遇后把其中指针重新设定为起始点，让两个指针以步长1再走一遍链表，相遇点就是环的起始点。
证明也很简单，注意第一次相遇时
慢指针走过的路程S1 = 非环部分长度 + 弧A长
快指针走过的路程S2 = 非环部分长度 + n * 环长 + 弧A长
S1 * 2 = S2，可得 非环部分长度 = n * 环长 – 弧A长
指针A回到起始点后，走过一个非环部分长度，指针B走过了相等的长度，也就是n * 环长 – 弧A长，正好回到环的开头。
Sorting Networks
算法导论第27章，在并行处理的条件下效率很高的排序算法。
介绍
如下面左图所示，每条横线(wire)代表一个待 比较的数值，竖线(comparator)表示连接的两条横线要做一次比较，并将较小的值放在输出横线的上方，较大的放在下面。排序过程就是从左往右依次 调用各个comparator（在同一位置上的comparator可以同时做）
有图表示了四个数字3, 2, 4, 1在经过这个Sorting Network时的行为。（由于背景为深色，建议点击图片查看）
下图是一个冒泡排序的Sorting Network表示
可以看到所有的比较都没有并行，效率很低。接下来先介绍一个0-1原理，然后利用它来构造一些比较高效的网络。
性质
首先是引理27.1：
对 于输入数据A = <a_1, a_2, .., a_n>，如果某个比较网络(comparison network)的输出是B = <b_1, b_2, …, b_n>，那么对于任一单调递增的函数f，这个网络能把输入数据f(A) = <f(a_1), f(a_2), …, f(a_n)>变为f(B) = <f(b_1), f(b_2), …f(b_3)>
这个引理的证明很简单，关键在于min(f(x), f(y)) = f(min(x,y))
接下来就是0-1原理：
一个有n个输入数据的比较网络，如果它能将仅由0和1组成的序列正确的排序（这种输入共有2^n种可能），那么它也能正确的将任意数字组成的序列排序。
证明也不难，利用前面的引理反正即可得到这个定理。
双调排序
接 下来先考虑双调序列(bitonic sequence)这种特殊情况，所谓双调序列就是先单调递增，后单调递减，或者可以通过环形旋转变化出上述特性的序列，比如<1, 4, 6, 8, 3, 2>和<6, 9, 4, 2, 3, 5>都满足条件（对于后面一种序列，只要把最后的3, 5移到序列开头就行了）。
双调排序(bitonic sorter)有若干步骤，其中有一步叫做half-cleaner，每一次half-cleaner讲数据放到一个深度为1的排序网络中，第i行和第i+n/2行比较(i=1,2,..,n/2)
引理27.3：
做完上述的half-cleaner后，输出的上半部分和下半部分都保持双调的特点，而且上半部分的每个元素都不大于下半部分的任一元素。
分四种情况讨论即可。
通过递归调用half-cleaner即可完成双调队列的排序。要对n个元素进行双调排序Bitonic-Sorter(n)，首先调用Half-Cleaner(n)，将元素分成上下两部分，接着依次对这两部分执行Bitonic-Sorter(n/2)即可。
调用的深度D(n) = lgn
归并网络
书上只给出了对0-1序列排序的算法，任意数字的排序算法留作了习题。
合并网络基于这样一个事实：对于两个已经排序了的序列X = 00000111，Y = 00001111，将Y倒过来后和X拼接的结果是一个双调序列。对这个双调序列再做一次Bitonic-Sorter就能有序。
通 过修改Bitonic-Sorter方法的第一步就能实现Merger，关键在于隐式的反转输入的下半部分。Half-Cleaner方法中比较了第i和 第i+n/2两个元素，如果下半部分反转的话就相当于比较第i和第n-i+1个元素。直接继续执行Bitonic-Sorter方法即可，如下图所示。
排序网络
我们已经有了构造一个排序网络所需的工具，接下来介绍一种利用归并网络进行排序的并行版本。
大致方法和传统的归并排序类似，从最小的颗粒开始二分增长，直到整个序列有序。
这样，一共需要lg(n)次Merger，每次归并中需要做lg(i)次Sorter，排序的总深度
D(n) =
0 (n = 1)
D(n/2) + lg(n) (n = 2^k且 k>=1)
由Master Method可推出D(n) = big-omega(lg^2(n))
也就是说理想的并行环境中，n个数可以在O(lg^2(n))时间内完成排序。
Bitonic Sorter http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm
图片来自于Wikipedia以及算法导论附图
Powered by FireStats