matrix67 |
2009-02-28 14:24 | 
大学生活的乐趣不光体现在吃喝玩乐上，更重要的是它所提供的自由学习的场所。你可以在网上搜索课表，看看什么时候什么教室有什么牛B课，记在手机中的待办事项中，到时候到那个教室去旁听。旁听的乐趣就在于，你可以去学任何你想学的东西，不用交作业，不用怕点你名，不用记笔记，不用考试，只需要挂个耳朵在那儿听牛B东西就行了。前天一大早就被兔子叫起来，跟着一起去旁听了一节数理逻辑。
课程内容很简单，毕竟也才只讲了两周，一切都是很基础的。老师讲得很好，对联结词、命题公式、真值表等概念都说得很细致，即使完全没接触过这方面东西的人也能弄明白。作为信科的专业课，老师也简单提到了SAT问题：给定一串由AND, OR, NOT, 逻辑变量和括号组成的表达式，是否能给变量取值使得整个表达式为真？如果存在这样的“成真赋值”，我们就称表达式是一个“可满足式”。最简单的例子，p∧q就是可满足的，把p、q都取真即可；p∧(¬p)就不可满足，该式无论如何都为假。判断一个逻辑表达式是否可满足是一个经典的NPC问题，目前除了枚举之外还没有更好的算法。
还有一种逻辑表达式，不管初始值是什么，整个式子恒为真。例如，p∨(¬p)就是永真式。看起来，判定一个式子永真比判定一个式子可满足似乎要困难得多，因为前者比后者要强得多。而事实却是，这两个问题可以（在多项式的时间内）相互转化，它们在复杂程度上并无区别。如果你找到了一种可满足式判定算法，你便立即拥有了永真式判定算法。换句话说，你的算法若能找出一个成真赋值，你就能利用该算法立即得出该式所有赋值结果是否都为真。这个问题的问法很有艺术性，它有意屏蔽掉了永假式判定这一桥梁。事实上，一个表达式要么可满足要么永假，而从永假到永真只有一步之遥——只需要在最前面加一个“非”即可。也就是说，如果有一个程序，它能告诉我逻辑表达式A是否可满足，那么我就把¬A输进去：如果它说¬A不可满足，意即¬A的任何赋值结果均为假，反过来A就是永真的；如果它说¬A可以满足，意即程序找到了¬A的一个成真赋值，反过来便成为了A永真的一个反例。
如果删除字符串A中的若干字母可以得到字符串B，我们就说A包含B（熟悉相关概念的网友可能知道，有一个准确的说法叫做“B是A的子序列”，但为了避免和后面的“序列”混淆，我们不用这种说法）。例如，字符串“matrix”包含了“mix”，也包含“ati”，但不包含“it”。字符串序列aaaaa, ab, bbaa, baaaa, aa, bbacc, cbcacc, bb中的每个字符串都不包含它前面的任何一个字符串，我们称这样的字符串序列为“非生成序列”（我自己取的名字，意思是说任一字符串都不能由前面的项通过添加字母生成出来）。我们可以构造出任意长的非生成序列，例如字符串长度严格递减的序列，或者所有不同的长度为n的字符串。现在的问题是，你能构造出一个无穷长的非生成序列吗？当然，你不能使用无穷多种字母来达到这一点。
世上绝无“非材”(1)
“然而，大自然的元素是守恒的，任何废弃物都可以转化为由同种元素构成的新物体。从这一方面来看，所有废物都能变废为宝，理论上便没有所谓的垃圾了……”
我从化学书上抬起头。化学书上说的这些我从小便坚信不疑。每样东西都有不止一个用途，只是有时候人们还没想到罢了。真的，你想想，原子弹都能拿来开山路，菜刀还能用来砍人呢。所以，每当看到有人烧垃圾或者埋垃圾，我就一阵恶心。
不过现在我有点不相信这个了。我看了看我的右手边。书桌下是一叠整齐的瓷砖。现在是星期天上午，我算着。还剩下两天了。
上星期二，隔壁刚装修好房子。铺完地板后他们还剩下了十几二十块瓷砖。这些瓷砖都是剩余的边角料，它们的大小形状完全相同；但很气人的是，它们的形状既不是什么正方形，也不是什么三角形，而是一种歪七歪八的不规则四边形。邻居觉得扔了可惜，便想把它们卖了。然而没想到这些东西卖不掉，因为它们形状虽然相同，但这种不规则形状必须处理成规则的形状之后才能利用，显然意义不大。正当邻居不知该怎么办时，我抱走了这些瓷砖，说了一句“留给我，一个星期以内我一定能想出不错的用途来。”
无意间我接受了一个任务：七天内把这些瓷砖用完。
我一直很喜欢有各种惊异性质的奇怪函数，比如阶梯状的连续函数、只在一点连续的函数、任意小的区间所对应的值域都是整个实数域的函数等等。在这里面，最令人吃惊的是恐怕要数在平面上处处稠密的单值函数（其实前面那个函数显然也有这样的性质）。这样的函数打破了一维和二维之间的界线，启发人们重新思考稠密性的意义。不过，有人提到，这两个函数之所以在平面上稠密，是因为它们在平行于x轴的直线上都是稠密的。我们自然开始设想，有不有可能在平面上找到这样一个点集，它在平面上处处稠密，但在任意一条平行于坐标轴的直线上都无处稠密呢？
这是可以办到的。为了简便起见，我们只考虑平面区域[0,1]×[0,1]上的点集。让我们考虑由所有满足以下条件的点(x,y)所组成的点集：x和y都是有限小数，并且小数位数是相同的。例如，点(0.0516, 0.1025)就属于这个点集，但(0.23, 0.1001)就不属于这个点集，(1/3, π/6)就更不属于该点集了。显然，对于任何一个有限小数x'，直线x=x'上都只有有限多个点；类似地，对于任意一个有限小数y'，直线y=y'上都只有有限多个点。因此，该点集在所有平行于坐标轴的直线上都无处稠密。有趣的是，该点集在整个平面区域内却处处稠密。在任意小的区间x'-ε≤x≤x'+ε，y'-ε≤y≤y'+ε中，总存在一对小数位数相同的x和y。我们只需要写出一个比ε更小的有限小数λ，然后取(x'+λ, y'+λ)（只保留和λ相同的位数），则该点必然在前面所说的范围内。
密码学的应用范围非常广泛。每一样简单的社交活动里都有很大的学问。考虑这样一个问题，两个人想通过一部电话打牌，但他们都不信任对方。有没有可能仅通过一部电话实现扑克牌协议，并且保证游戏的公正性呢？
扑克牌的信息隐蔽性带来了很多与密码学协议相关的有趣问题。两个象棋大师可以在洗澡间一边冲澡一边大喊“炮八平五”、“马八进七”，一对围棋情侣可以在床上一边亲热一边呻吟“点三三”、“拆二”。等事情办完了，一盘精彩的棋局或许也就结束了。这些棋类游戏之所以可以“盲下”，就是因为在棋类游戏中，双方的局面信息都是完全公开的。不过，打牌就是另外一码事了。你说你出方片7，我怎么知道你有一个方片7？事先发牌？那谁来负责发牌呢？怎样发牌呢？难道我告诉你“发到你手中的是两张3一张5一张8一张9”？这样一看，两个人“盲打扑克牌”似乎是不可能的了，要么需要借助道具，要么需要第三者的帮助。不过，运用密码学知识，我们可以设计一套扑克牌协议，该协议能够实现随机的、隐蔽的、公平的发牌，并且不需要其它东西的帮助。我们以一手五张牌为例，说明如何实现“两人各摸五张牌”的程序。
