从水木上看到个bt的课程：The Elements of Computing Systems

要求学生自己做个CPU，写一个操作系统、设计一个OO语言，
自己写编译器、自己实现一个运行时虚拟机，然后组成一个应用。

http://www1.idc.ac.il/tecs/

看完昨天的题目，超狗和求会不约而同地提出的一道类似题目

O(n)时间O(1)空间找出数组a中两两不连续的元素的最大和。

我的做法是这样的，其实不知道对不对。
设置三个变量，q,p,pi分别表示相对于当前位置i时，i-2位置的最大和以及i-1位置的最大和。
pi标记在i-1位置a[i-1]是否包含在这个和里面，1表示包含，0表示不包含。

初始化q=0,p=a[0],pi=1，从下标1开始循环。
则递推式为：
         max(q+a[i],q,p)     pi = 1
t=
         max(p+a[i],p)        pi = 0
其中如果t取值为q+a[i]或p+a[i]，则pi更新为1，否则为0
q=p;
p=t;
最后返回p作为这个最大值。
 --------------------------------------------------------------
下面尝试用循环不变式(loop invariant)来证明一下它的正确性。
（其中循环不变式是p，或说：进行到i时，前面i-1个元素组成的数组中"两两不连续的元素的最大和"）
1. 初始化：当i=1时，p=a[0]，由于i-1=0,此时数组只有一个元素，显然是正确的。
2. 过程：假设p,q,pi正确地表示当前状态，则：
当pi=1时，表示p包含了a[i-1]，我们不能把a[i]加到当前最大值上。
i长度的不变式必然是q+a[i],q,p中最大值。p更新为这个最大值同时pi相应更新。

当pi=0时，表示p没有包含a[i-1]，我们可以把a[i]加到当前最大值上进行比较。
p必然代表了当前最优的结果（至少比q优，如果假设成立则此时必然有p=q），因此不必考虑q。
p更新为max(p,a[i]+p)

3. 结束：此时i=n(数组长度为0，下标为0..n-1)
循环结束，由于p代表i-1=n-1时最优值，因此此时循环不变式保持。

综合1-3，证毕。

素网：一个HK教师介绍素数的website

很多有趣的东西，大多是数论的东西，围绕着素数展开。

http://hk.geocities.com/goodprimes/

PCP - Probabilistic Checkable Proof

 

 

Sent to you by iveney via Google Reader:

 

 

PCP - Probabilistic Checkable Proof

via 阅微堂 by zhiqiang on 10/19/08

PS: PCP可以说是理论计算机领域近20年来的最重要的结果之一，它给了NP问题一个新的刻画，并且提供了一种证明近似算法下界的方法。下面是yijia写的PCP介绍。

作者：yijia

我们可以从最基本的NP开始。一般NP的定义是基于nondeterministic Turing machine，但我们也可以用类似于Interactive Proof的系统来刻画：

一个语言是在NP内当且仅当存在一个多项式时间的算法  (i.e., prover) 满足下面一系列条件：

1. 有两个输入和，并且；
2. 对于任意的， 我们有
   2.1. 如果，那么存在一个使得，i.e., accepts ;
   2.2 如果，那么对于任意y都有，i.e., rejects .

在2.1中，可以看成是 的一个证明。对于3Sat问题，我们可以设计这样的: 是一个3CNF公式，而y是一个对中所有变元的赋值。Prover 就是用来验证y是否满足x。直观上必须读完整个才能确认。 那么有没有可能改进这一点，让只读的一部分，来增加效率? 比如现有的Graph Minor Theory的证明有几百页，如果只要其中几页就能确认其正确那么就会省去Reviewer的很多时间。如果是个确定时间的算法，这就等价于要求。那么如果每个NP问题都有这样的Prover， 我们就可以证明NP包含Subexponential Time里。一般公认这不可能成立。

但如果我们允许使用Randomness，问题就开始变得有趣了。这也就是Probabilistic Checkable Proof (PCP)。

要定义一个PCP系统, 我们先要给定两个函数。我们说一个随机算法是一个(r(n),q(n))-restricted verifier, 如果在输入上使用位随机数，访问的位。直观上，V 扔了个骰子，然后根据结果去访问证明y 的位。 当然V还要是一个多项式时间算法，， 同时满足所谓的non-adaptive条件（写起来太罗嗦了，所以就不写了)。

我们说这样的定义了一个语言当且仅当对于任意的， 我们有
(a) 如果，那么存在一个y 使得;
(b) 如果，那么对于任意y都有.

要注意的是并不是所有的都定义了一个语言，因为(b)不是总能满足的。

非常壮观的PCP定理就是

Theorem 1. NP=PCP()

也就是说，对于每个NP语言我们都可以构造一个，在每个上，仅使用位随机数，访问证明中的常数多位，就能以很高的概率正确判断是否。

由于可以证明PCP()对于多项式时间规约(PTIME reductions)封闭，所以PCP定理也可以叙述为

Theorem 2. 3Sat PCP()

除了本身非常有趣和counter intuitive，PCP的一个重要应用就是近似算法的下界:

Corollary. 如果NPP, 那么Max-3Sat没有PTAS，同时Max-Clique不存在constant approximation。

这个结论的证明就是通过PCP，构造所谓的Gap Instances：给定常数，-3Sat是如下的问题

input: 一个3CNF公式使得要么存在一个满足的赋值，要么所有的赋值最多满足-fraction的clauses。
question： 是否可满足？

Corollary 3. 存在一个，使得存在一个3Sat到-3Sat的规约。

实际上我们可以证明

Theorem PCP定理成立当且仅当上面的Corollary成立。

现在PCP定理有两个证明：一个就是由Arora，Sudan等人在90初完成的基于代数的方法，直接证明Theorem 2。证明的核心某种意义上就是Error Correcting Code。另一个就是Dinur前几年完成的基于Expander的组合方法，直接证明Cororllary 3。前者的证明很长，但实际上比较初等，而后者短一些且非常漂亮。

相关文章

• 高等理论计算机I
  姚期智教授给清华大学新入学研究生开的一门课，课程内容 在经典计算复杂性方面：NP完全性，多项式空间复杂性，对数空间复杂性，交互式证明系...
• Windows游戏中的NP完全问题
  上篇文章扫雷是NP完全问题之后，You Xu提到＂不光扫雷是NP 完全问题，空当接龙问题也极有可能是一个NP完全问题。目前最好的通用 planner只能解半副牌...
• 扫雷是NP完全问题
  本科时有同学扫雷最快可以在60多秒完成高级难度，让我这种最快130秒的人非常惭愧，当时就想着编一个全自动的扫雷程序，不过一直也没写。今天才...
• 素数筛法的复杂度
  Xie Xie给我看了一个链接性能调优--永远超乎想象，里面提到了素数筛法的复杂度，作者用实验发现此筛法是线形的。 所谓素数筛法就是那个求小于n的...
• TCS：NP-hard
  好久没有写我的理论计算机初步系列了，其实复杂性这一块，虽然平时经常遇到，但由于问题都过于本质和困难，想这方面问题的时间反而不多。Ko教...

---

© zhiqiang for 阅微堂, 2008. | 链接 | 5 条评论

 

 

Things you can do from here:

• Subscribe to 阅微堂 using Google Reader
• Get started using Google Reader to easily keep up with all your favorite sites