令人怀念课堂的书

X

2007-12-05 16:12:38 胖子

　　interesting...

2007-12-05 16:15:38 吕合肥

　　我当时把这本书当作侯世达的书买了，后来发现不是，也不后悔。确实非常好，只是对NP不完全的介绍不够深入，我至今还是不知道那是什么？

2007-12-06 18:28:23 NullPointer

　　我大二那年暑假把GEB当宝贝一样看了两遍，结果大四那年上张立昂的算法复杂性还是挂掉了。。。考试的时候睡着了。
　　
　　后来我看了许多更复杂的算法书，但一开始看GEB的不求甚解但努力琢磨的状态是最美好的。

2007-12-06 21:16:16 无止境

　　给我邮寄过来。

2007-12-06 22:05:12 艾芙

　　让我冒着出错被人砸版砖的危险来解释一下P/NP/NP-Complete/NP-Hard。
　　
　　1，计算复杂性
　　这是描述一种算法需要多少“时间”的度量。（也有空间复杂性，但因为它们能相互转换，所以通常我们就说时间复杂性。对于大小为 n 的输入，我们用含 n 的简化式子来表达。（所谓简化式子，就是忽略系数、常数，仅保留最“大”的那部分）
　　比如找出 n 个数中最大的一个，很简单，就是把第一个数和第二个比，其中大的那个再和第三个比，依次类推，总共要比 n-1 次，我们记作 O(n) (对于 n 可以是很大很大的情况下，-1可以忽略不计了）。
　　再比如从小到大排好的 n 个数，从中找出等于 x 的那个。一种方法是按着顺序从头到尾一个个找，最好情况是第一个就是 x，最坏情况是比较了 n 次直最后一个，因此最坏情况下的计算复杂度也是 O(n)。还有一种方法：先取中间那个数和 x 比较，如偏大则在前一半数中找，如偏小则在后一半数中找，每次都是取中间的那个数进行比较，则最坏情况是 lg(n)/lg2。忽略系数lg2，算法复杂度是O(lgn)。
　　
　　2，计算复杂性的排序：
　　根据含 n 的表达式随 n 增大的增长速度，可以将它们排序：1 < lg(n) < n < nlg(n) < n^2 < ... < n^k (k是常数）< ... < 2^n。最后这个 2 的 n 次方就是级数增长了，读过棋盘上放麦粒故事的人都知道这个增长速度有多快。而之前的那些都是 n 的多项式时间的复杂度。为什么我们在这里忽略所有的系数、常数，例如 2*n^3+9*n^2 可以被简化为 n^3？用集合什么的都能解释，我忘了精确的说法了。如果你还记得微积分的话就想像一下对 (2*n^3+9*n^2)/(n^3) 求导，结果是0，没区别，对不？
　　
　　2，P 问题：对一个问题，凡是能找到计算复杂度可以表示为多项式的确定算法，这个问题就属于 P (polynomial) 问题。
　　
　　3，NP 问题：
　　NP 中的 N 是指非确定的(non-deterministic）算法，这是这样一种算法：（1）猜一个答案。（2）验证这个答案是否正确。（3）只要存在某次验证，答案是正确的，则该算法得解。
　　NP (non-deterministic polynomial)问题就是指，用这样的非确定的算法，验证步骤（2）有多项式时间的计算复杂度的算法。
　　
　　4，问题的归约：
　　这……我该用什么术语来解释呢？集合？太难说清了……如果你还记得函数的映射的话就比较容易想象了。
　　大致就是这样：找从问题1的所有输入到问题2的所有输入的对应，如果相应的，也能有问题2的所有输出到问题1的所有输出的对应，则若我们找到了问题2的解法，就能通过输入、输出的对应关系，得到问题1的解法。由此我们说问题1可归约到问题2。
　　
　　5，NP-Hard：
　　有这样一种问题，所有 NP 问题都可以归约到这种问题，我们称之为 NP-hard 问题。
　　
　　6，NP完全问题 (NP-Complete)：
　　如果一个问题既是 NP 问题又是 NP-Hard 问题，则它是 NP-Complete 问题。可满足性问题就是一个 NP 完全问题，此外著名的给图染色、哈密尔顿环、背包、货郎问题都是 NP 完全问题。
　　
　　从直觉上说，P<=NP<=NP-Complete<=NP-Hard，问题的难度递增。但目前只能证明 P 属于 NP，究竟 P=NP 还是 P 真包含于 NP 还未知。
　　
　　=========================
　　发现我好像徒劳地敲了一堆文字。要把这么深奥的问题解释清楚，我功力还远不够呢。:(
　　

2007-12-06 23:05:24 晃悠

　　数学白痴要在这里晕厥咧

2007-12-06 23:30:44 小满是男生

　　恩,强贴.虽然短了.豆瓣貌似找不到更好的评论了,豆瓣貌似急功近利了,为了吸引竞争,悬挂了这么根短萝卜就想让我们这帮驴友使劲跑~呵呵

2007-12-06 23:46:59 安*幸福七种

　　艾芙,你太强了.

2007-12-07 00:04:20 范范，拒绝流浪

　　2007-12-06 23:05:24: 晃悠　　数学白痴要在这里晕厥咧
　　同意 也赞lz 让我也想看看这书了

2007-12-07 08:02:53 艾芙

　　惭愧，只是我的专业而已。
　　我尝试着浅显地介绍NP，结果发现还是绕不开那些术语~~比如“归约”，怎么都解释不清。
　　还是让“数学白痴”（决无贬义，术业有专攻而已）们晕厥了，抱歉抱歉。

2007-12-07 14:29:06 胖子

　　解释计算复杂性排序的时候说说大O小o的含义可能更清楚，当然求导比较直观。
　　
　　解释P和NP很难避免解释图灵机，这也是我向别人描述的时候最头疼的问题。另外，P,NP,NP-complete都是针对判定问题的，而NP-hard则不限于判定问题。比如TSP问题（n个城市的最短路）是个优化问题，它是NP-hard，但从定义上讲它不是NP问题，自然也不是NP-complete；TSP问题的判定问题（判断最短路是否小于某一个值）则即是NP问题也是NP-complete，同时也是NP-hard。
　　
　　P vs. NP是所谓的七大数学问题之一，Clay Mathematics Institute悬赏一百万美元给解决这个问题的（http://www.claymath.org/millennium/P_vs_NP/），计算机理论的社区里屡屡在4月1号传出该问题已被解决的消息。
　　
　　我念书的时候比较强的结果是Arora针对Euclidean TSP给出了一类PTAS（http://citeseer.ist.psu.edu/arora96polynomial.html），就是可以通过多项式算法以任意精度逼近最优解。看上去很美，其实只有理论意义。因为任意精度的代价是多项式次数无限增长，实际应用中平方级的复杂性已经让人皱眉了，三次方的复杂性简直是令人崩溃。不过无论如何，那个证明很漂亮。有七八年没关注这方面的消息了，不知最新进展如何。
　　
　　最早看七八十年代的paper的时候很多人在证明之前会说"assume P!=NP..."，后来说的人越来越少了，估计是实在懒得提，虽然没有被证明。

2007-12-07 22:46:52 吕合肥

　　保存学习了，谢谢艾芙！！！

2007-12-08 10:46:21 艾芙

　　谢谢胖子。citeseer 啊，多亲切、简直是衣食父母一样的站点啊！我有两年没有去过了。。。
　　
　　大O小o...在这个无法输入公式的地方要说清它们的区别可不容易。不过我上面那个导数的说法~~~啊，地洞地洞我要找地洞~~~~
　　判定问题和图灵机这两个概念，不引入一大堆的定义和符号，我是不觉得自己有能力说清它们了~~判定，就是判定呗，大家意会吧。
　　
　　胖子读研的时候做的是什么呀，能读些这方面的论文，真有趣。我做的就是大俗的课题，研究生时的专业课更土，算法课上得比在南大读本科时的还要简单，没言语了。。。所以现在除了还记得一些本科时就学到的基础知识外，再没啥存货可说了:(我的庸俗的、非常“上海”的研究生三年啊~~

2007-12-31 00:58:28 VviiviV

　　感谢艾芙，1－4点看懂了，NP-Hard和NP完全问题没看懂。有所收获。

2008-01-02 19:19:59 MGhostSoft

　　阿列夫零是可列集的基数。所有可列集都能建立一一对应的关系，我们规定自然数集的基数是阿列夫零。阿列夫零是一种无穷大，但它只是“最小的”无穷大。具有阿列夫零个数量的东西，我们可以按照一定规律把它列出来（例如所有整数，可以按照 0,1,-1,2,-2,3,-3,... ，一个也不漏一个也不多），但还有些集合不能这样列，比如你找不到一种规律列出 (0,1) 之间的所有实数。事实上，实数集的基数叫做阿列夫一，(0,1)、[0,1]的基数都是这个。
　　但基数没有上限，因为任何一个集合都与它的幂集不对等，所以它的幂集的基数总是比那个集合本身大。
　　一个集合的幂集就是它的所有自己构成的集合。一个集合的基数为n，那其幂集的基数就是 2^n 。
　　我写过一篇文章叫做《一对多关系数据模型使用键链接的合理性的数学原理》，解释了其中的很多概念，可以在 http://joinbbs.myjoin.cn/viewtopic.php?t=2056 看到。

2008-02-27 22:34:54 etone

　　elfe你介绍的不错。补充几点哈：
　　
　　1. 计算复杂性：有必要区分一下算法的复杂度和问题的复杂度。
　　
　　简言之，算法的复杂度刻画了这个算法在最坏情况下（最坏的输入），消耗的资源。时间是最自然、也是最宝贵的资源:)
　　
　　（注：以上是经典定义，亦有专门关于平均复杂度的研究。）
　　
　　而问题的复杂度是指：解决这个问题的最优的算法的复杂度。一个问题的复杂度，刻画了解决这个问题，在最坏情况下，消耗的“必要”资源。类似于这样的数学刻画，在计算机科学中，被成为“下界”（lower bound）。
　　
　　复杂度，甚至广义的理论计算机科学的研究对象，就是“问题”。复杂度这个学问所作的事情就是通过刻画问题的复杂度，来把问题归类。P和NP就是两个问题类（也叫复杂类）。
　　
　　2. 关于确定性：简言之，“确定”复杂度是指找到一个正确答案需要的资源；“非确定”复杂度是指：给你个答案，判断这个答案正确（或 不正确）需要的复杂度。
　　
　　（注：判断正确和判断不正确是两种不同的情况，相应的复杂类如NP和co-NP）
　　
　　“确定”与“非确定”作为一种计算的现象，普遍存在。并不局限于P和NP的区别，只不过P和NP最著名、也最基本。
　　
　　3. 关于模型：提到下界，就必须规定计算模型，也就是算法可以作什么，不可以作什么。否则如果一个算法可以作任何事，例如未卜先知，那么讨论“必要”消耗的资源也就没有意义了。
　　
　　关于计算，比较古典的模型就是图令机。它基本上就是个有着无限内存的小霸王学习机。数学上等价于目前人类造出来的最牛B计算设备+无限内存。
　　
　　（注：目前人类尚未造出真正的量子计算机。加拿大的D-wave被指造假。）
　　
　　图灵机在数学上不算是个很干净的模型，boolean circuits和cell automata都具有更强的组合数学趣味，也等价于图灵机。
　　
　　4. 关于归约：简言之，归约就是“你办事，我放心”。把问题A归约到问题B，就是指：通过解决问题B，问题A也可以得到解决。
　　
　　但要注意的是，归约本身也是个计算的过程，因此也要遵循计算模型的限制，也有复杂度。能在NP里面闭合的归约，也须得是多项式时间可以算出来的，所谓polynomial-time reductions。否则NP-complete就无法正确定义了。
　　
　　归约类似于问题之间的"小于等于"关系，A能被有效的归约到B，则B的复杂度不小于A的(加归越的复杂度)，即B比A“难”。这个-hard的后缀就是这么来的。
　　
　　5. 关于完全类：和确定性一样，“完全”也是普遍存在的一个概念，并不局限于NP类里面。简言之，在一个问题类里面“完全”的问题是指：这个问题类里面，这些问题是最难的——它们是这个复杂类的脊梁，垮了一个，整个类全垮。（这么说其实不确，大家听听就好。）
　　
　　有些复杂类，是没有完全集的。NP是有的，就是NP-complete。
　　
　　6. 关于P vs NP：
　　我很喜欢一个关于P=NP的类比。
　　
　　如果NP=P了，那么为一个数学命题找一个证明，就会跟读一个证明验证它正不正确一样简单。
　　
　　所以人们相信NP不等于P，否则如果NP=P，那说明“证明NP=P”这件事将会和“读NP=P的证明”一样容易，可为什么到现在还证不出来:)
　　
　　这个比喻相信很多对“确定性”概念深究的人都会想到。在06年的国际数学家大会上，这个比喻也被Avi Wigderson介绍给了数学家。参见" P, NP and Mathematics - a computational complexity perspective".
　　
　　最近十几年里，也发生了一些大事，没有被教科书记载。这牵涉到一个更好玩的类比：
　　
　　如果有个火星人成功证明了NP猜想或雷曼猜想，地球人懒得通读长达100页的证明，那么地球人可以规定一套海王星语，让勤劳的火星人用这海王星语重写证明，虽然证明变成了200页，但这次地球人可以随机选读10个字节！就可以99％的成功率来判定火星人的证明正确与否。
　　
　　这个结果就是著名的PCP:probabilistically checkable proofs。对PCP定理的证明，涉及了若干篇重要的论文，也是理论计算机科学的“史上最长证明”。
　　
　　另外一个值得一提的重要结果就是“自然证明”：natural proofs。由Razborov和Rudich于十年前得之。讲的是：NP猜想无法通过自然证明获得（原结果是关于circuits模型，但可以推广到图灵机模型）。所谓“自然证明”，就是人类有生之年能读完的长度的基于构造的证明，一言毙之：不很bt的证明。Razborov和Rudich证明了“要证明NP!=P，那个证明必然非常bt”:)
　　
　　
　　这两个结果都得到了Godel Prize，这个奖是用来奖励理论计算机科学中里程碑式的结果。
　　
　　回头看去，伟大的结果往往都可以用浅显的语言表述，却能够让人类对这个世界的认识更加深刻。
　　
　　在理论计算机科学中，“问题”、“解决”、“证明”，不但像数学一样，是我们在作的事情；很多时候，它们就是我们研究的论题本身。这也是理论计算机科学迷人的地方——我们证明着数学定理，我们也在研究“证明”这件事。

2008-02-27 22:59:14 etone

　　另：关于Arora96的Euclidean TSP的结果。这是近似算法里面的一个重要结果，但其实和NP猜想甚至复杂度都关系不大。
　　
　　很多NP-hard问题都有PTAS甚至FPTAS（这个比PTAS更强，是NP-hard优化问题能做到的极致了），不会直接影响到NP和P的关系。
　　
　　Arora的结果很重要，一个是因为TSP本身是极难的，可以证明在NP!=P的假设下没有多项式时间的近似比为多项式的近似算法。但想不到加上个Euclidean metric的限制，就突然有了PTAS，这是个巨大的惊喜。
　　
　　另一个原因是，Arora的证明有很深的几何背景，间接推动了近些年对于metric embedding的研究热潮。
　　
　　一定程度上说，Arora96算是个几何的结果。

2008-03-06 12:55:11 艾芙

　　关于归约的“简言之”够清楚简单，赞。
　　
　　P=NP 的类比和那个不很bt的证明好有意思。很符合直觉，一说出来也确实觉得浅显明了，但没人告诉时是就绝对的堵。
　　
　　这门学科有趣的东西真多，学不了，就等着谁来为它们写科普吧。etone 要不你来？
　　

2008-03-06 23:31:30 etone

　　科普我总有一天要写的。但要先修炼到能把这些问题讲好，而且也有人肯看我写的。否则既不科，也不普。
　　
　　真要有那么一天，你要在豆瓣上给我写评论啊。

2008-03-07 07:46:53 艾芙

　　希望到那天我能够在自己的书店里卖你的书。你要赏光来做个小型签售+讲座喏。

2008-03-07 17:47:00 etone

　　“小型”不行。不够大型的俺都不稀得去。
　　
　　怎么也得像李开复老师那样，走到哪里都有粉丝团献花。再收他50几批“关门弟子”，还得是女弟子，还得是处女，恐龙的不要。
　　

2008-03-08 09:43:48 艾芙

　　嗨哟，您出息了呢。
　　那抱歉，我小庙容不了大和尚的，你还是去上海书城吧。那里常有粉丝们嗖嗖的窜来窜去，可拉风了:P

2009-06-11 22:51:45 心向明镜台

　　说实话，自己有点看不懂，不知是不是不懂逻辑学的缘故，反正关于推理的部分还让我蛮纠结的。??

2009-09-27 23:44:15 三浦ウリエ

　　数学白痴飘过。。从高中起就是学文的。。不过除去数学的部分这本书真的让人受益匪浅~~这篇评论变成学习贴了= =

> 我来回应

X

登录 · · · · · ·

Email:

密  码: 忘记密码了

在这台电脑上记住我

>还没有注册...