March 14, 2010

两本童话

今晚在UME看的原声《波西·杰克逊和神火之盗》,原本是早早地奔去买记忆中今晚首映的爱丽丝的票的,结果被告知上映日期为3月26,今日上映的是神火之盗。售票小姐一脸疲倦地问我,看否?许是今天UME的人真的很多或者她有隐情。我心想看吧,都远远地跑来了,总不至于只纠结了下近来的记忆力就又坐半小时公交晃回去。


原来是本童话。和哈利波特差不多的海报,和哈利波特差不多的基调和色彩,和哈利波特差不多的养眼少年男主角,以及和哈利波特差不多的出身,我是说电影的出身。也是同样的三人小组,两男一女,一个精明一个忠诚一个万能。不过它比哈利波特好些,至少我看得懂。这片子几乎没什么出彩的地方,但它告诉了我们一些事情:
1. 具象化的美杜莎真是恶心,然后知道如何打败美杜莎吗?诀窍是iPhone。
2. 旅行中一定要随身携带Mac,和远方的伙伴保持通信了解法宝的使用方法,因为出发时太急促来不及说。
3. 美杜莎的头是个好武器,但赢了之后千万别高兴得亲她,这太恶心了。
4. 不要吃免费的食物!
5. 拿跑车做奖品的话,就不要把车钥匙放在车里,更不要给车加满油。
6. 最后我觉得,如果宙斯用闪电火和波塞冬打架的话,他会输的,因为水导电。
7. 最后的最后,他们怎么处理美杜莎的头了?扔垃圾桶里了?


回来的时候路过IFE,外带了杯摩卡,回到寝室看完了剩下一半的《了不起的狐狸爸爸》。也是一本童话。狐设是细长细长的身材,小小的脚尖走起来像跳芭蕾舞,通篇发光两次呈国旗色彩的皮毛,甚得我心。几首插曲都很美妙,尤其那首开篇歌词一胖一矮一瘦的童谣,还有那首一群农场工人围在一起唱的中间大段字幕组都没有翻译的小调。


剧情按着上头们的想法该是又不健康又不向上太不着调了,不过按着我的想法,导演绝对有才,他将狐狸偷鸡偷鸭偷苹果酒的传统演绎得真是有如是白的人(C,用一下你的冷笑话)拯救心上人一般波澜壮阔又富有幽默感,就连三个讨厌的农场主疯狂捣毁狐狸爸爸的大树狐狸一家子挖洞逃命的线路和节奏都极具美感,直至最后的营救战役Ash跑出的奥林匹克优美弧线以及最后的Nice Hit砸开门后冲出的得了狂犬病的Spitz犬(噢,我讨厌这个设定,干吗不挑其他的,癞皮狗吉娃娃什么的不是滑稽的多嘛。。)。最后,我真以为它抢着了尾巴领带会突然神智清灵把尾巴还给狐狸爸爸,可它竟然嘶哑咧嘴甩头扭腰地把尾巴上的毛全弄没了,导演,你也太狠了!好在,导演还是很明显地站在野生动物这边的,末了胜利归途中突然出现的不会讲英语也不会讲拉丁语朝狐狸爸爸举了举爪子又消失在林中的狼,我其实没太明白它和他的意图,但仍旧觉得感动。至少这是本快乐的可以笑着看完的片子,虽然狐狸一家从地洞里搬到了有黄色底和小花的墙纸的树屋里最后又搬到了下水道里,不过好在,狐狸爸爸的尾巴失而复得而且可以随意插拔,他们也可以每天吃超市里的免费食品,并且狐狸妈妈又怀孕了。
这可以是一本环保片,也可以是一本针对中产阶级的讽刺片,但我觉得重要的是它有一个美妙多彩的HAPPY ENDING. And I do love happy ending.

February 12, 2010

[读书笔记] 人工智能中的不确定知识与推理 PART 2:关于时间的概率推理

BOOK:Stuart Russell, Peter Norvig, Artifical Intelligence: A Modern Approach(中译第二版,姜哲等), Pearson


在静态世界中,每一个随机变量的取值都是唯一固定的;而有时问题是动态的,环境状态会随时间不断变化,比如考虑病情的发展,因此有必要对时间上的不确定性建模。我们将状态的改变过程描述为一系列快照,每一个快照(或时间片)都描述了世界在某个特定时刻的状态,包含一个随机变量集合,其中一部分是可观察的,如证据变量Effect,另一部分是不可观察的,如Cause。为了方便标记,一般假设时间片间有一个固定的有限时间间隔,以整数标记。符号U1:3对应变量U1,U2,U3。

  • 马尔可夫假设
    马尔可夫假设认为,当前状态值只依赖于过去“有限的”已出现状态历史。这一假设使我们得以避免指定数目无界的条件假设表(过去的历史是无限的)。满足这一假设的过程被称为马尔可夫过程或者马尔可夫链,最简单的也应用最广的是一阶马尔可夫过程,即当前状态只依赖于相邻的前一个状态,与更早的状态无关:
          clause53    | 转移模型
    另外,也假设时刻t的证据变量只取决于当前状态:
          clause63    | 传感器模型
    一阶马尔可夫的假设在大多数情况下都只是一种近似,而且往往是太不精确的,有两种可能的弥补方法:1)提高马尔可夫过程的阶数;2)扩大状态变量集合。但是可以证明,提高阶数,总能够通过增加状态变量的个数重新形式化,以保持阶数不变。
  • 基本推理任务
    1)滤波和预测(Forward)
    滤波指在到目前为止所有已知的证据下,计算“当前”状态的后验概率分布,即已知直到时刻t的滤波结果,根据新的证据clause11 计算t+1时刻的滤波结果。滤波的过程可分为两步:首先,将当前状态分布由时刻t向前投影到时刻t+1;然后,通过新的证据进行更新。
           clause1211
    式子的第一部分是传感器模型,第二部分是一个求和式中,其中第一个因子是转移模型,第二个因子是时刻t状态分布。求和式完成滤波的第一步,总式子完成第二步。并且,可以认为因子2是沿着变量序列向前传递的“消息”f1:t,在每次转移时得到修正,并根据新的证据进行更新,也就是前向递归:
           clause1320
    预测指计算“未来”某个状态的后验概率分布,可以认为是没有增加新证据的条件下的滤波:
           clause148
    这也是一个前向递归,并且这个计算只涉及转移模型而与传感器模型无关。可以证明,预测结果分布会在将来收敛到一个不动点,之后一直保持不变,即稳态分布。收敛的时间称为混合时间,转移模型中的不确定性越多,混合时间就越短,未来也就越模糊。

    2)平滑(Backward)
    平滑指在到目前为止所有已知的证据下,计算“过去”状态的后验概率分布,也可分为两步:时刻1到k的前向递归和时刻k+1到t的后向递归。
            clause1514
    这个求和式中的因子1是传感器模型,因子3是转移模型,因子2是后向传递“消息”:
           clause1610  
    后向递归和前向递归复杂度相同,每次更新所需的空间和时间都是常量,与时间t无关,而是取决于状态空间的大小以及问题所需的特定时序模型。我们可以通过记录整个序列进行前向滤波的每步结果,来降低全序列平滑的时间复杂度为线性,这也就是Forward-Backward算法,先从时刻1到t前向滤波,再从时刻t到1后向平滑。这个基本算法有两个主要缺点:它提高了算法的空间复杂度;它需要修改才能工作在联机环境下,即对于不断新加入的证据,平滑以前的时间片。

    3)寻找最可能序列
    寻找最可能序列指给定一系列观察结果,找到最可能生成这些观察结果的状态序列。应当注意到,平滑计算得到的是“单个”时间片上的后验概率分布,而寻找最可能序列,需要考虑所有时间步上的“联合”概率分布,即
           clause913
    典型地,考虑动态规划的思想,寻找一条以每个时间片上的可能状态为节点最大化后验概率的路径,路径上的状态就组成了最可能序列。在一次前向的遍历中,计算并记录到达每一个状态的最可能路径的概率(通过其父节点上的最可能路径概率记录),并标记产生该概率的父节点。遍历结束后,通过标记就可以回溯到这条最大化概率的最可能路径。这就是经典的Viterbi算法,其空间和时间复杂度都是O(t)。
     
  • 隐马尔可夫模型Hidden Markov Model
    HMM指用“单一离散”随机变量描述过程状态的时序概率模型。该模型的可能取值就是世界的可能状态。多个状态变量可以组合成一个单一的“大变量”,以单个变量取值构成的所有可能元组为取值范围,来保持HMM框架。
    HMM使得所有的基本算法有一种非常简单而优雅的矩阵实现(优雅这词用的,作者太有爱了)。令状态变量用整数1,…,S表示,其中S为可能状态的数目,那么,转移模型就可表示为一个S×S的矩阵T,Tij表示从状态i转移到状态j的概率;对每个时间片t,传感器模型就可表示为一个对角型矩阵Ot(证据取值已知,因此为对角型),Oii表示当状态为i时生成证据et的概率;前向消息和后向消息用列向量表示:
           clause177 
    矩阵的形式化还揭示了改进算法的机会(值得借鉴的一句话)。
    我们可以通过取逆的方式调换等式位置,将前向消息修改为后向传递。那么Forward-Backward算法就可以被修改为:先执行标准的前向过程计算f t:1,但抛弃中间过程,然后b和f同时执行后向计算,得到平滑估计。这种修改降低了算法存储空间的需求,但它要求转移矩阵必须是可逆的,传感器矩阵也是可逆的,即所有观察值在每个状态下都是可能的。类似的,还可以修改平滑算法使之支持固定延时的联机平滑(Fixed-Lag-Smoothing算法)。
    HMM被广泛地应用于语音识别、动作手势识别等领域。
     
  • 卡尔曼滤波器Kalman Filter
    卡尔曼滤波用一些“连续”变量来描述系统的状态(可以是多元的),然后选用合适的条件概率密度“函数”来表示转移模型和传感器模型,典型地,如线性高斯分布。假设位置X由速度和前一时间点的位置决定:
           clause18[6]
    那么如果增加一个高斯噪声,就得到一个线性高斯转移模型:
           clause19[14]
    并且,其给出的单步预测分布也是高斯的,对给定新证据进行条件化后得到的更新分布也是高斯的。一个d元高斯分布的卡尔曼滤波公式传递的“消息”是一个d元均值向量和一个d×d协方差矩阵,其与通用滤波公式或HMM模型的滤波公式的功能是相同的,但由于高斯分布的特殊本质,附加了一些有趣的性质,比如方差值的更新与观察值无关,并且其会很快收敛到一个固定的值而大大简化后续的计算过程。
    卡尔曼滤波最常见的应用是物体运动轨迹的跟踪,甚者能够应用于任何通过连续状态变量和噪声测量来刻画的系统。但是注意,这些系统必须是“光滑的、表现良好”的,并且允许追踪者保持和更新一个合理近似于真实后验概率分布的高斯状态分布。这是因为卡尔曼率滤波器将高斯均值附近的状态Xt当作局部线性的,而“不光滑、表现不良”的系统是高度非线性的,比如Xt+1的取值会因Xt与环境中某值间的相对关系而改变,参考书中鸟撞树干的例子。这种情况下,就需要考虑使用切换卡尔曼滤波器,并行多个卡尔曼滤波器,再根据每个滤波器对当前数据的适合程度,对预测结果取加权和。
     
  • 动态贝叶斯网络Dynamic Bayesian Network
    DBN中的每个时间片都具有任意数量的状态变量和证据变量,HMM和卡尔曼滤波都是DBN的特殊形式。DBN通过将复杂系统的状态分解成一些组成变量,充分利用时序概率模型中的稀疏性,使得其比纯马尔可夫模型更适合大规模系统。DBN需要指定状态变量的先验概率、转移模型和传感器模型,后两者还需要指定相继时间片之间、状态变量与证据变量之间的链接关系的拓扑结构,如左下图所示。
             clause19[22]       graph5[4]
    DBN仍然是贝叶斯网络,因此变量消元、似然加权等推理方法仍然适用。但是DBN的精确推理是不适用的,随着规模的扩大(序列过长),变量消元的因子增长将是指数级的。近似推理中的似然加权也不是很好的选择,与真实的事件序列保持相当接近的样本比例将随着观察序列长度t的增加而呈指数级下降,举个极端的例子,以老板是否带伞来判断是否下雨的DBN,即使老板天天带伞,也仍然会产生有无尽的晴天的幻觉。
    一种比较有效的算法族是粒子滤波,它的工作机理是:首先根据时刻0的先验分布进行采样得到N个样本构成的总体,然后对接下去的每个时间片,对于每个样本通过转移模型使之向前传播,再赋予新证据的似然值进行加权,最后对总样本进行重采样,某个样本被选中的概率与其权值成正比,如右上图所示。例子滤波是高效的,它通过常数数目的样本维持对真实后验概率的良好近似,并且由于它是一个采样算法,能够很容易在混合的和连续的DBN中使用,被广泛应用于复杂的运动模式跟踪以及市场预测。
     

February 6, 2010

[读书笔记] 人工智能中的不确定知识与推理 PART 1:概率推理

BOOK:Stuart Russell, Peter Norvig, Artifical Intelligence: A Modern Approach(中译第二版,姜哲等), Pearson


不确定性的研究来源于一个不幸的事实:智能体几乎从来无法了解关于其环境的全部事实, 因此对其行动的可行程度构造一个完备而正确的描述是几乎不可能的。书中概括规则不确定性的来源为三个方面:1)惰性,对所有相关规则的一一罗列着实过于繁杂;2)理论的无知,现代科学在大多数领域都无法掌握完备的规则;3)实践的无知,即使掌握所有规则,我们也无法对其一一验证。

题外话:书中第一章绪论提到一种观点“要解决一个难题,你必须已经差不多知道答案”,这里的解决指的是AI方法的解决,直白地说,人类无法通过人工智能来解决连自己都找不到头绪的问题。这种观点缠绕着AI由古至今,数学的上限决定了AI发展的上限,学者们能做的只是不断逼近却无法超越(也许),这是哲学与数学产生的基础所决定的可悲事实。

因此,我们只能期待智能体在给定所拥有的环境信息下,在可以执行的规划中选择性能度量达到最大的一个,即理性决策(期望效用最大化)。理性决策是概率理论和效用理论的结合,前者提供一种方法以概括不确定性,后者对智能体的偏好进行表示和推理使其选择能产生最高期望效用的行动。
那么,作为一种合格的不确定性推理模型,首先要合理地表示各种不确定的规则,而后对于给定的观察事实(证据)能够给出各种规划的效用分布情况,最后针对效用分布作出理性决策。这样的推理模型有很多,其中一种最基础也是已经得到成熟发展的不确定知识表示方法,就是贝叶斯网络。

  • 朴素贝叶斯模型Naive Bayesian Model
    这来源于概率论中著名的贝叶斯法则Bayes' Rule:P(a|b) = P(b|a)·P(b) / P(a)(书中有句话说,这个简单的公式是几乎所有概率推理的现代人工智能系统的基础,在此表示同意)。通过合并条件的方式,我们得到如下的概率分布,即朴素贝叶斯模型(Cause指原因,Effect指各种受其影响的结果):
              clause111
    NBM的成立以条件的独立性假设为前提,也就是说,每一个Effect变量取值都由Cause导致,但是它们彼此之间没有直接影响。条件独立断言对全联合概率分布作了理想式的简化,使得概率系统能够进行规模扩展(将一张大的概率表分割成很多小的概率表来处理,复杂度由O(2^n) 降至O(n) )。并且,其相较绝对独立性断言更加普遍容易获得。虽然条件独立性假设在大多数情况下都不成立,但是NBM比纯粹的逻辑智能体要好得多。
     
  • 贝叶斯网络Bayesian Network
    贝叶斯网络为任意的全联合概率分布提供了一种简便的规范,它是一个有向无环图,每个节点都标注了定量概率信息,用于表示变量之间的依赖关系。如下图所示,箭头由父节点指向子节点,节点Xi 有一个条件概率分布P(Xi | Parent(Xi)) 量化父节点对其的影响,没有连线的变量间相互独立。BN是一种局部结构化系统,具有紧致性,假设系统有n个随机布尔变量,每个变量受到至多k个其他随机变量的影响,那么整个BN可以由不超过n·2^k个数据完全描述,而全联合概率分布则需要2^n个。
             graph122
    BN节点的正确添加次序是:首先添加“根本原因”节点,然后加入受它们影响的变量,直到叶子;错误的添加次序将带来糟糕的网络和额外不必要的需指定的数据,但是尽管如此,它们都表示完全相同的全联合概率分布。
    全联合概率分布中的每个条目都可以通过BN的信息计算出来,有公式
             clause210
    这是BN的数值语义,另外还有与之等价的拓扑语义,其有两种描述,指出图中条件独立的节点:1) 给定父节点,一个节点与它的非后代节点是条件独立的;2) 给定一个节点的父节点、子节点以及子节点的父节点,那么这个节点与网络中的其他节点是条件独立的(又称马尔可夫覆盖Markov Blanket,第一次正式在教科书中与Markov 碰面,幸会幸会~)。
    另,混合贝叶斯网络Hybrid Bayesian Network,指的是同时包含离散随机变量和连续随机变量(比如,概率是高斯分布的)的网络。
     
  • 基于贝叶斯网络的概率推理
    对于任意一种概率推理系统,其最基本的任务是:在给定某些证据(如诸多Effect )后,计算一组查询变量(如Cause )的后验概率分布。

    1)精确推理。
    既然贝叶斯网络给出了全联合概率分布的完备表示,那么查询P(X | e) 就根据网络写成条件概率乘积的形式,然后通过枚举网络中的所有变量并把条件概率表中的对应条目乘起来后求和的方式来回答查询(Enumeraton-Ask)。对X的每一取值x,其计算过程可以用一棵树来表达,如下图左。算法对这棵树作深度优先递归,对每条路径求积,在分支节点处求和,不断递归得到x的后验概率。
           graph2_thumb23           graph3_thumb3
    这种算法是对全联合查询的简单修改,其对全联合分布求和但不显式地构造它。可以看到,它重复计算了很多子表达式,对于一个有n个布尔变量的网络,时间复杂度始终都是O(2^n)。
    那么很自然地,我们能想到对这些子式只进行一次计算,并保存计算结果以备将来使用,来降低时间复杂度。典型地,有变量消元算法(Variable Elimination)。算法在查询求值之前,先剪除所有即非查询变量亦非证据变量祖先的节点,然后从右到左计算表达式。表达式中的所有计算因子都用概率分布来表达,因其变量个数有些写作二元向量,有些写作矩阵。因子间的相乘,以概率分布的点积来代替,使得所有的中间结果被保留下来。这种点积不是矩阵乘法,而是两个具有同一些因子的概率分布的消元联合,如f1(A, B)·f2(B, C) = f3(A, B, C),若有f1(T, T) = 0.3,f2(T, F) = 0.6,那么就有f3(T, T, F) = 0.18。最后,通过不断的消元点积,得到查询所需的分布。
    变量消元算法的时间和空间需求取决于算法运行过程中构造的最大因子,而后者又进一步取决于变量消元次序和网络结构。对于单连通的网络(如上图左),其与网络复杂度成线性关系;但对于多连通的网络(如上图右),书中称这种情况下将有指数级的时间和空间复杂度,并其与计算逻辑命题的布尔满足赋值个数问题难度相当(归约方法证明),是一个#P问题,严格地难于NPC问题。团算法(Clustering)可将这种图中的单独节点联合,形成团节点,最终使得网络结构是一个单连通图,但这种构造也是NPC的(计算理论无处不在XD)。

    2)近似推理。
    由于大规模多连通网络中的精确推理是不可操作的,就有必要考虑近似的推理方法。
    最Naive的,我们通过直接采样的方法,按照拓扑次序依次对每个变量进行采样,被采样变量值的概率分布依赖于其父节点的赋值,再按概率随机对其赋值,多次重复得到大量样本后,就可以计算查询在样本集中的概率分布。显然,此概率分布在极限情况下能过收敛到查询的真实值,且准确度与采样个数有关。直接采样方法有两种衍生算法,用于计算条件概率:拒绝采样(Rejection Sampling),直接采样后剔除证据与查询不同的样本,再归一化概率分布;似然加权(Likelyhood Weighting),这种方法只生成与证据一致的样本,但在生成样本的过程中计算似然权值w补偿真实采样分布与期望采样分布之间的差距,w是每个证据变量在给定其父节点条件下的取值概率的乘积。容易察觉到,前者的可用样本总是很少因此效率低下,而后者的效率虽然较前者要高,但当证据变量个数增加时,大多数样本的权值都将变得非常低,性能将大受影响。
    比较普适地,近似推理有三族主流的方法,分别为变分近似(Variational Approximation)、信度传播(Belief Propagation)以及马尔可夫链蒙特卡洛(Markov Chain Monte Carlo,MCMC)方法。
    MCMC方法:通过对前一个样本进行随机改变而生成下一个样本,在每一步采样循环中,对某个非证据变量Xi 进行采样,其转移方向取决于Xi 的马尔可夫覆盖中变量的当前值。MCMC方法认为采样过程最终会进入一种“动态平衡”,处于这样的情况下,长期来看在每个状态上花费的时间都与其后验概率成正比,也就是稳态分布(Stationary Distribution):
             clause3_thumb11
    其中,π(x) 为状态x的概率,q(x'→x)为状态x转移到x'的概率。
    有性质称为细致平衡(Detailed Balance),意味着任何两种状态之间的期望流量相等:
            clause4_thumb7
    吉布斯采样器(Gibbs Sample)是MCMC方法的一个简单变体,容易证明其满足与真实厚颜概率一致的细致平衡。
    变分近似方法:其基本思想是提出一个原问题的易于处理的简化版本,并通过调整变分参数,使简化问题与原问题之间的距离函数最小化,以保证其与原问题尽可能地相似。
    信度传播方法:又称环传播(Loop Propagation),由Judea Pearl在1982年提出,现被应用于超大规模和非常高连通度的贝叶斯网络,是一种以局部的信度传递代替全局积分的算法,虽然有时会不正确或不收敛,但在绝大多数情况下其结果与真实值是非常接近的。
     
  • 不确定推理的其它方法
    缺省推理(Default Reasoning):它不是把结论当作“在某种程度上相信”,而是“相信,除非找到相信其它事物的更好理由”。在这种体系下,推理总是选择相信缺省值,除非出现某种更特定的值,将缺省值覆盖,如我们相信“张三有两条腿”,除非有信息“张三只有一条腿”。
    基于规则(Rule-Based):这种方法建立在基于规则的逻辑系统之上,对每条规则增加某种“伪因子”以容纳不确定性,曾被广泛应用于专家系统。但由于其无法很好地适应规则集的膨胀和新规则的不断加入,这种方法现在已不被推荐使用。
    无知问题Dempster-Shafer理论:这一理论的存在是为了处理不确定性与无知性的区别,它使用区间值信度来表示智能体对命题概率的知识,允许我们通过信度的变化程度对“无知性”进行表达。比如抛硬币的问题,当硬币均匀时,我们知道正反面出现的概率各为0.5,但是我们对硬币是否均匀却是无知的,此时,该理论认为正反面出现的概率均为[0, 1],那么如果有专家作出检测硬币是均匀的概率是0.9,那么该理论认为,正反面出现的概率就均为[0.45, 0.55]。
    模糊集与模糊逻辑:模糊集理论对命题的定义十分接近自然语言,模糊谓词的真值是介于0和1之间的一个数值,这就意味着,模糊集是一个没有清晰边界的集合,比如我们描述一个人是否高,这就可以用模糊集理论来表述。模糊集理论和基于其的模糊逻辑通常被应用于构造控制系统,但是它和基于规则的推理方法一样,都具有真值函数性,这是说,复合语句的真值通过其各组成部分的真值来计算。而除非存在非常强的独立性假设,这种概率组合是行不通的。这使得模糊集理论在处理复杂网络的问题上,将带来灾难性的不正确信度。
     

February 2, 2010

寒假始

1日,抱着大大的一束百合,打了两次的,才找到莹妞说的新开的高级会所附近的某新开的酒店,末了上楼还被当成送花的小妹= =,酒店经理义正言辞地对俺说“怎也不知道带个花瓶来!”。离被告知的时间已过半小时又一刻,主角们竟都还没到,在场的全是三姑六婆或者花白头发的叔爷们,么有一人认识俺的><,所幸俺临危不惧才不致酿成惨剧。

许是订婚请的人本不多,又是中午能来的更少(俺也是头一遭参加,说是订婚酒女方中午男方晚上),一顿饭吃下来除了主人家,只认识三颗人,两颗是我初中同学一颗是我小学同学T T。真是有史以来最寂寞的一顿酒席。不过见到久违的同学还是开心的,另加兄愈发惊艳,安小妹则愈发讨喜,笑问何时办喜酒,两人竟均答“如果一个人也行,那便可以办了”。我对八卦真是迟钝吧,记忆中两人都是花草有主的。

算来离家已近8年,和家乡已经有些脱节了,逢人说话讲方言要先思考半拍关于如何表达,不识得新开的酒店餐厅、新造的街道小区、其实是南边大片新造和东面大片改造的所有。这个地方和我的记忆愈发不像了,初中时在江滨闲逛可从来不会遇到黑不溜秋的黑人。希望那些好吃的小食店别拆别搬别换老板最重要别变味道最好别加价!

January 17, 2010

和我一样的数字控?Sugar Shikao~

又是一个四十代的叔叔。小小的眼睛,戴着眼镜,拍照时超严肃。薄薄的嘴唇,有次听Live音轨某段长达4秒像被掐住脖子般的笑声着实吓了我一大跳。声音有些沙,丝毫谈不上温润,有种我难以形容的粗颗粒磨砂质感。还带点恣意、随性,或者调侃的意味。心情好的时候听起来会觉得调皮,有趣。心情不好的时候听起来会觉得刺耳,闹心。

十足的才子,多产,不仅自销。却似乎从不曾红得通透的样子,总也见不到他的通告。词曲皆通。擅于玩弄各种音乐元素的混合搅拌,写些奇怪的歌词,用些异世界的词藻。作品的题目里经常出现数字,分数、日期、时间或者其他无意义乱敲等等等。

认识须贺是因为看了《Honey & Clover》发现某人居然和Spitz平摊了插曲曲目觉得挺厉害、后来看《xxxHOLiC》听OP的声音好耳熟曲子节奏好有趣一看居然又是某人,心想算了,既然有缘,给你个机会让我喜欢你吧。然后。。恩。

须贺写的曲子总是很丰富,能听到各种风格在一起打架。我不太爱好电子乐,却很喜欢须贺写的。有一种玩耍的心态。调子有时会很扭捏,乍一听有想马上关掉的冲动。也可以用诡异来形容。怎么说呢,不太流畅,总猜不到他下一小节会怎么写怎么编曲用什么样的方式唱。也可以说满是新意。普通速以下的曲子相对入耳些,只是杀伤力太大。他这样的嗓子,唱什么都觉得动情。

4904[4]  o0043[4]

须贺发高音的方式很独特,有些像喝醉酒扯着嗓子唱歌的大叔。声音真得不得了,能感觉到声带绷紧后颤抖的频率,抖抖抖就像他笑起来的样子。须贺写的词有时会很晦涩,有时会很冷清,透着令人窒息的孤独感,和他的声音一起,打击得我无力还手。像是眼前有一条路,一步一步地走着,却总没有尽头。身边的人不断路过,有快有慢,我出声,却连自己也什么都没有听到。
坐公交的时候听他唱歌,窗外的人和车和房子和灯光变成一些大大的色块不断向后飞跃。车停。有人下车。如果下雨,我就会觉得没由来的伤感。
[7月7日]是这样的歌。[夏陰~なつかげ~]也是。还有[Happy Birthday],是一首遇上什么伤心事时听都没得商量直接让人掉眼泪的歌。

suga-shikao-kono-yubi-tomare[5] thumb2[4] thumb[3]

AUCK-19005[3] s1799064[3] 3767191271063530_2 3767641271122488_2

最喜欢他的一张专辑是[Sugarless],也是我曾经有过的所有Blog名字的来源。这似乎也是须贺卖得最好的一张专辑,也似乎是须贺最慢节奏的一张专辑。有几首虽谈不上快乐却可以闭上眼睛跟着左右摇摆的曲子。须贺絮絮叨叨,呢喃着一些不着边际的往事。那些无比意识流的歌词,在昏黄色灼热的午后不断穿行的思绪。偶然觉得安静,仿佛空气停止流动。偶尔又觉得胸闷而烦躁,电吉他蛮很的高音便开始肆虐。有些混沌。然后又说慢下来慢下来吧,我们正在长长的坡道上夕阳照着影子稀疏而温暖。

很想知道一些他对于生活的看法,因为须贺风光前似乎曾经很不幸,东大毕业却在小广告公司拿很低的薪水,经济窘迫。有这样经历的人,似乎不是分外努力便是就此沉沦。不过,对于我这样的局外人,只要能他还能继续写歌继续唱,就想抱着感谢的心情继续听下去。说到底,也只不过在哪个不知道的地方远远地观望他的路人而已。也许,大家都孤独。(我也学他意识流,哦也~)

※推荐
推荐3首歌。Room201。Happy Birthday。夜空ノムコウ。网上找到的[夜空ノムコウ]版本居然是须贺和YUI合唱的,真让人惊喜。其实还有首有名且有趣的[19才],现今还做着我的手机铃声,只是排在第四位。



January 10, 2010

2009年终盘点

今日小雨。湿哒哒粘糊糊的,红茶包也有些潮气。趁着复习的中场休息,做一下09的年终盘点。盘点是每年必做的,数数听过什么歌、看过什么片子、去过什么地方、买了什么东西,还有花了多少钱,当然这个就不贴出来了,秘密啊。


※音乐
09年L团的各位大叔们还在玩SOLO,正经的单曲一枚也没有。BLESS不算,1.27才release,再好听也是要算在10年的;Hurry Xmas双小鹿版也不算,理由同去年,想抢钱明说嘛,还在Super Live上说应Fans的要求再发行,Fans的要求是你们几个快点并回来别到处沾花惹草好不好,海豆子你说谎不脸红。不过,今年圣诞的Goods还是要小赞下的,小鹿手办和帽子都很可爱(扯远了)。

# 新添的Artists:
シド / DREAMS.COME.TRUE / 吉田拓郎 / レミオロメン / Sukima.Switch
Lisa.Hannigan / Heinz.Holliger / Travis
# 删去的Artists:
N.A.
# 第一耳就爱上的歌:
Yui:[Again](钢炼OP1,唱的时候背不下歌词总跟不上她的快嘴巴)
绚香:[梦を味方に] [みんな空の下](恭喜结婚,10年好好休养,早日归来)
JUJU with JAY'ED:[明日がくるなら]
ステレオポニー:[泪のムコウ](没记错的话,是高达00的OP之一,几个小姑娘歌写的不错,但现场有待加强)
スキマスイッチ:[全力少年] [水色のスカート](第一次听是在玩太鼓达人的时候,前奏太悠扬以致开唱后有些跟不上节奏,真难,不过好听,后来找到作为插曲的片子[东京糖衣巧克力]也很有特点)
flumpool:[星に願いを] (Live时不断下坠的流星背景真震撼)
Sukima Switch:[ゴールデンタイムラバー] [雫](钢炼最近的OP,歌词里有一句“How Many?需要多少代价来交换?”真是切题)
UVERworld:[美影意志] [アイ・アム Riri](其实AwakEVE碟里几乎所有的歌都很赞,非要挑出一些的话,[美]的旋律很流畅,[Riri]的歌词有一句Rap后的平调“それは それは 悲しみのストーリー”唱的我心里直发寒)
ゆず:[逢いたい] [虹] (也许大抵叫[虹]的曲子我都会喜欢吧。柚子今年Best Artist唱抢拍了> <|||,听说是设备的问题)
いきものがかり:[YELL](今年最好的励志曲。不似[みんな空の下]忧伤、比[虹]更有深度。Super Live上和高中生的合唱很感人)
遊助:[ひまわり] (歌是好歌,词是好词,但现场待磨练)
レミオロメン:[粉雪](其实我第一次听这歌是小田爷爷唱的)
Innocence Mission:[Beautiful changes] [500 Miles](两首念念叨叨的歌~)
Lisa.Hannigan:[I Don't Know] [Ocean and a Rock](声音很丰富的乡村音乐)
Muse:
[Resistance]
# 新收的常听大碟:
UVERworld:[AwakEVE](我并不因为它也带awake字眼而赞赏它,Takuya∞的声音的确很棒)
flumpool:[Unreal](白金碟。08年11月release的,我收的晚了。赞赞赞~)
Lisa Hannigan:[Sea Sew]
Muse:[Resistance]
一张从VeryCD扒下来的VA碟:
[The Music From Beautiful Angel]
吉田拓郎、DREAMS COME TRUE、福山大叔的几张补完的精选
今年收了好些Mozart的东西,几本想听的歌剧、一张10CD的Ingrid Haebler老太太的[Mozart Complete Works for Piano]、一张10CD的Mozart诞辰250年时的庆生碟、Jeno Jando的钢琴协奏曲、还有各种版本的K.314(Heinz Holliger老头吹得最好~)
其他还有Hifetz的几张贝多芬小提琴协奏曲、一张Maria Kligel、Ilya Kaler等等的[BRAHMS: Double Concerto for Violin &Cello;SCHUMANN: Cello Concerto in A Minor](赞的)、一套30CD的拿索丝企鹅评鉴三星极品全收藏(想着VeryCD要被封火急火燎地收的,还没听完)等等
还有一张很有趣的OST [Nodame Cantabile Best 100 Collection Box]收录了Nodame有趣的乱蓬蓬组曲^^
-------------------------------
大致就是这样。今年因为忙,听的歌有些少,也没怎么关注新出的大碟们。看来10年要是闲下来,得做很多补完计划。不过,看各种年终Live的样子,今年似乎没出其他什么十分出彩的歌,难道也是因为金融危机?


※影像
这个就更加有些少了。好多连载的新番追到一半因为忙就给忘了,再闲下来的时候就懒得再看了,《天地人》是一个,《东京地震8.0》又是一个。忙碌有时也不知是不是好事。10年因为福山大叔的关系想要从头到尾地追《龙马传》,可它偏偏到现在还没有字幕片源(大河剧看无字的话太辛苦,方言土话太多了),老天是让我从此不看片,好好学习天天向上吗?还是想让我去看美剧。。

# 夏之岚
首先画风很独特,尤其在处理光影时坚硬的轮廓线,突兀,但却很能抓眼球,有些像彩色玻璃的感觉,其实也贴切,夏天的光就是如此直白的。其次是OP,虽然曲子一样,可是居然每集的歌词都不一样,而且写得很大胆很有趣。最后才是剧情、节奏和各种各样奇妙的人物。新奇是这片子带给我最大的感受,它很特别。
# 轻音少女
腾讯盘点的时候把它归入宅部,有些搞不懂,我一点不宅的说。和草莓棉花糖一样气质的片子,全片男人少得可怜。音乐元素,几首原创曲都不错。笑点也很充分,看这种片子会很快乐。其实今年我看完了[初恋限定],还觉得是挺好的消遣,不过这么宅男向的片子就不列了。
# 钢炼FA
BONES的作品很少有不值得看的。他们本身推翻前部钢炼要重拍就已让我很纠结,虽然水岛精二有些扯。这期的本子是按照漫画来写的,剧情也许说得通很多,但人设为啥要改呢,头发为啥是金色轮廓线的呢,为啥还偶尔画走形缺钱吗。哎,可能是我太习惯一作了。不过,今年还是会继续追的,年番就是辛苦。
# 化物语
好吧。我承认,新房昭之是个好监督。这么既叫好又叫座的片子,不看可惜了。
# 续夏目友人帐
还是前作一样清新的感觉。亮点是黑白喵咪老师和脸上长爬虫的捉妖帅哥~
# 东之伊甸
大饼同志推荐之一。短。监督讲故事的能力很强大,节奏很紧凑,悬念抓得也很牢,虽然结局有些难懂。
# Coraline
其实我也老把它念作卡洛琳,的确长得像嘛。巧的是今年几部不错的动画都是木偶动画。这部特别的地方在眼睛,像日本人讲究名字一样,故事设定里只要眼睛被剥夺换做纽扣,就永远也回不到现实世界。色彩设定也很出彩。
# 夏日大作战
大饼同志推荐之二。言简意赅就是宅男宅女拯救世界的故事。出彩的地方是对虚拟世界的设定,关于盗取很多ID就会不断变大的具象化很有趣。
# Mary & Max
4月的片子。澳大利亚产。我12月才看。对人物的刻画很细腻。友谊万岁。据说是导演半自传式的片子,那猜猜他是里头的谁?
# 飞屋环游记
Pixar大作。一个关于一个退休的老头、一个黄帽子小胸章控和一只曾经会说话的短腿狗狗牵着一坨彩色气球下面挂了个房子打败了一个养了很多说话狗狗的坏人探险家拯救了一只五彩斑斓长嘴长脚大尾巴鸟的故事。很开心并且有些温暖的故事。另,皮肤的材质做得真棒,不愧是Pixar。
# The 9
色调有些灰。故事也有些灰。不过小人们各自的构造都挺有趣,拉链实在是个很奇妙的东西。

# 疯狂的赛车
今年看的第一本电影。难得的国产好电影。难得的从一开始没有让我猜出结局的好电影。
# 南京!南京!
我和Cmm、Q殿最后一次一起去电影院,还3个人看了一场变相包场的《东邪西毒》,虽然我不喜被90后像极了的王家卫。在新开的近江电影大世界,去的路上还路过Cmm出生的卫生院。我记得这些事情比电影清楚。最后说一句,电影不错,至少它能上映很不错。
# 第九区
我花了1.5个礼拜断断续续地看完了它。对种族间关系的探讨很深刻很有内容可以挖掘,尤其是特意用仿记录片的方式剪辑,导演想让观众思考的意图十分地明显。从技术上讲实在很诧异它居然是一部小成本片。另,大虾长得真不好。再另,今年好些片子都有9,是因为09年吗?
# 2012
这片子我在电影院看了两次,一次中文边上太吵一次英文外面开始下雨夹雪。场面很震撼。事后对2012是否末日的深究有些有趣。
# Hard Candy
06年的片子。很不知如何形容的一部片子。连剧情我也无法用一句话描述。它很复杂。一个未成年少女使计杀死了诱骗她并诱杀她朋友的成年男子?太简单了。中途一段阉割手术的心理描写十分出色。
# The Red Violin
98年的片子。讲一支也许是受了诅咒的红色的小提琴的各个主人们的故事。也很复杂。似乎是说,音乐是要用生命去体验的。
# Orlando
今年年中的时候挑了好些Tilda Swinton的片子看。Orlando是其中挺特别的一本。幻想色彩浓厚,讲了一个将近1600年的故事。对Swinton个人魅力的诠释也很充分,她实在是一个十分有气质的女人。
# …太多了,我不列了,累死了

# 白色巨塔
日版的。属于补完计划。很经典。对社会的看法,就剧集而言,十分深刻。手术镜头还是不敢看。
# LOVE SHUFFLE
很欢乐的一本爱情剧集。适宜茶余饭后和朋友一同笑笑看看。Q殿推荐。
# 一公升的眼泪
补完计划。我没流眼泪。不过,还是赞下众演员的敬业演出和编剧的感人不懈。
# 龙樱
第一本在PSP上看了的剧集。总在晚上。总会看得热血沸腾。然后后悔应该早看到这片子,当年高三就该好好学习天天向上。
---------------------------------
以上。我觉得我写这日志写得都快虚脱了。好片无限量,我写不完啊。。


※移动
今年去过的地方也很少,还是因为忙>< 。去了几次上海看展看演唱会。去了几趟北京呆了好久好久好久却哪儿也没去,只待在满是烟尘的工地上。唯一称得上旅游的就只有暑假随团去了趟洛阳和西安,看了看向往已久的古建筑们和美女们,当然还有坑里的泥人们,吃了很多清真美食,末了回来的时候还看了一眼都快3岁的龙凤胎(我还是弄不清楚我和他们什么关系,只明白是亲戚)。


※新置物品
这个我就不多写了,不然真的要虚脱了。手都有写发抖了。这一部分,总之很多很多。新购PSP3000一台、白色木兰台灯一座、新杯子若干、衣服一打、裤子一坨等等等等。


以上。终于完了。

January 8, 2010

[备考笔记] THEORY OF COMPUTATION

好课。本科大四的时候还主动选修了的课。老师高高的。挺帅。却挑了个实在不怎么好的时间上课。周一大早。我总醒不来,醒来了也想着去了反正迷糊还是多睡会养好精神下午好干活就又躺下了。然后转眼就要考试了。再看书,那些本科时不懂的依旧不懂。却又有些大四时备考数值分析时热血沸腾的感觉。

对那些曾经Make Me无比Confused的概念和理论一一罗列解析:

  • 可数无穷Countably Infinite及对角化论证Diagonal Argument
    这是计算理论里第一个十分纠结的概念。可数无穷很难在脑子里成像,书上给出的定义是“可数无穷集合A与N之间存在一个双射f ”,也就是说,A的元素与N存在一一对应的关系。我们可以像数自然数一样枚举它,如果你活得像宇宙一样长,就可以永远抱着数完它的信心。
    Cantor的对角化原理可以用来证明某集合是不可数的,通常假设某集合是可数的,并罗列其与N间的双射关系为一列,那么若集合不可数,则可以按照对角原则构造一些元素,使其属于该集合但按照其构造规则不能被罗列。WIKI上给出了十分详细的证明,关于可数无穷集的幂集和实数的不可数问题。
    那么,我们可以对不可数无穷做以下描述:就是那些比可数无穷还要长的数列们,即使你活得像宇宙一样长,也还是放弃吧。
     
  • 确定型有穷自动机DFA与非确定性有穷自动NDFA的等价
    等价,指的是其接受相同的语言。如果对于某类语言,有一台NDFA按照非确定的规则转换状态接受它,那么就存在一台DFA以NDFA每读入一段输入串后的可能状态集合为状态,按照确定的规则接受它。并且,这样的构造是指数的。
     
  • 正则Regular与非正则语言以及泵定理Pumping Lemma
    正则语言可以用表达式写出来,可以被FA接受,其中可能用到组合字符串是可以穷举的;非正则语言是难以预料的,只能用文字来表述,比如根据前端决定后段的字符串。
    泵定理描述正则语言中某些字串可以被无限重复(Kleene)的特性,相应地,可以用来反证某些语言是非正则,即假设其正则,但举例一个带n的特殊字符串,其长度大于n,无论怎么分解为xyz,y≠e,|xy|≤n,但重复y段i次后得到的xy^iz不属于该语言。(PS:其实泵定理只对不可穷举且存在环的正则语言成立。)这里有两个技巧:第一是如何选一个特殊的字符串,a^nb^n、ww^r之类是最常想到的;第二是如何证明“无论怎么分解”,通常最简单的方法就是分情况讨论。当然,证明本身就带有艺术性,需要因地制宜。
    正则语言在并、连接、Kleene、补、交下封闭的,也可以此反证语言非正则,如交,使某语言与某正则语言相交得到非正则语言。将封闭性和泵定理结合,是一种比较方便的证明非正则的方法。
     
  • 等价类和状态最小化
    一个正则语言的等价类为它本身、续尾后能被接受的字符串和续尾后不能被接受的字符串。
    状态间的等价,≡是说对于状态p和q,想要到达最终状态,要走的路是一样的(当然,走不通的路也是一样的)。带下标n的≡则是说如果只走n步或更少,那状态p和q是≡的。那么其实,≡就是≡下标∞。
    用状态最小化算法寻找FA的标准型状态,就是从下标0开始,不断分裂寻找等价状态(以相同的字符串走到终点),直到不可分。
     
  • 下推自动机PDA的转移关系们
    ((p, a, β), (q, γ)) 当状态为p且输入带读入a且β在栈顶时,抛出β,推入γ,且转换状态为q;
    ((p, a, e), (q, b)) 当状态为p且输入带读入a时,推入b,且转换状态为q;
    ((p, a, b), (q, e)) 当状态为p且输入带读入a且b在栈顶时,抛出b,且转换状态为q;
    ((p, e, e), (q, e)) 当状态为p时,转换状态为q。
     
  • 上下文无关语言Context-free与非上下文无关语言以及泵定理二世
    上下文无关语言CFL是一种可以从某一个种子开始向两边无限蔓延开的语言,生成什么字串只与文法相关,而与种子当前的上下文无关。
    泵定理二世基于语法分析树描述CFL中某些推导规则可被无限重复(S→aSb)的特性,可用来证明某些语言非上下文无关,即假设其上下文无关,但举例一个带n的特殊字符串,定义n与φ(G)之间的关系使得字符串长度大于φ(G),分解为uvxyz,v≠e,y≠e,重复v、y段i次后得到的uv^ixy^iz不属于该语言。其技巧与泵定理一世大同小异。
    CFL在并、连接、Kleene下封闭,交和补下不封闭。CFL包含正则语言,其与正则语言的交仍是CFL。因此,也可用封闭性证明。
     
  • Chomsky范式
    Chomsky范式要求每条规则的右边必须小于2,见wiki。普通CFL可按如下步骤转换为Chomsky范式:
    1. 对所有的结束字符串a,引入一个非借助状态A,增加规则A→a,那么X→a就变为X→A;
    2. 消去e规则:a) 寻找所有可能推导出e的状态集合Λ,包括X→e,Y→X,Z→XY;
                           b) 对所有含有n个属于Λ的状态的规则,替换为2^n条新规则,
                               如X→AYZBY,Y∈Λ替换为X→AYZBY、X→AZBY、X→AYZB和X又AZB;
                           c) 消去所有e规则。
    3. 分割所有长规则(右边大于2),如X→ABCD变为X→YD、Y→ZC和Z→AB。
    4. 消除规则中的单链,即若存在规则X→Y,而Y总是推出Z,且Z有规则Z→a,则替换X→Y为X→a。
    用动态规划的方法确定字符串是否能被某CFG输出,其前提是该CFG以备Chomsky化。
     
  • 判定Decide与半判定Semidecide、递归Recursive与递归可枚举Recursively Enumerable、递归函数
    对于w∈L,图灵机M始终生成接受格局;对于w∈L,M始终生成拒绝格局。这时,就称M判定L,而L是递归的,即可判定的。若只满足前半部分,则称M半判定L,L是递归可枚举的,即可半判定的。
    对于所有w∈Σ*,有M(w)=f(w),即M在输入w上停机并在带上写f(w),称M计算f,f为递归函数。
    半判定的M不是算法。存在非递归的递归可枚举语言。
    如果一个问题和它的补都是递归可枚举语言,则其实递归语言。
     
  • 几种扩展图灵机与标准图灵机间的等价性
    k带图灵机:标准图灵机M'将带形式化地分为2k条轨道(间隔排序),其中k条用来记录k带图灵机M相应条带上的信息,另k条来用来模拟带头的位置。M的t步,M'需要O(t*(|x|+t))步来完成,|x|为输入的长度。
    双向无穷带图灵机:可以用2带图灵机模拟,再推到标准图灵机,模拟花费线性时间,因为这种图灵机每步只有一条轨道是活动的。
    k带头图灵机:将标准图灵机的带形式化地分为k+1条轨道,1条用来记录信息,其余用于模拟带头的位置。那么,每步的模拟将带来两次扫描,一次确定带头位置,一次改变符号或移动带头。这样的模拟需要花费平方时间。
    非确定型图灵机:由于非确定性图灵机可能产生的格局是有限的,设最大为r,那么设计3带图灵机,第1条带存储输入w且永远不变使得每种计算可在相同的输入上重新开始,每一次计算按照{1, 2,.., r}*生成的顺序转移格局,第2条拷贝第1条的数据赞着第3条中记录的顺序模拟计算,两次模拟计算间生成新的顺序存储于第3条中。这样的模拟至多会在r+r^2+…+r^n次失败尝试后,才会产生对应NTM的选择。因此,这样的模拟需要花费指数级的时间。
     
  • 通用图灵机对任意图灵机的模拟
    对任意一台图灵机M=(K, Σ, δ, s, H),可以通过二进制编码的方式描述其所有的状态、符号和状态转移表。其每个状态表示为以q开头,长度为i,2^i≥|K|的二进制字符串;每个字符表示为以a开头,长度为j,2^j≥|Σ|+2(2为←和→符号)的二进制字符串。那么状态转移表就可表示为相应的多个二进制四元组,并以字典升序排列,如(q, a, s, a)表示为(q01, a100, q00, a100)。注意:停机状态不会出现在任意一个四元组的第一分量上,因此在四元组中搜不到的格局就是停机格局。
    那么,设计这样一种3带机器U':初始化时,第1条带写入输入字符串w,第2条带写入上述形式描述的“M”(应该只是四元组集),第3条带写入q0^i(初始状态)。在每一步对M的模拟中,U'搜索第2条带直到发现“第一分量与第3条带相同”“第二分量与第1条带相同”的四元组。若发现,则“把第3条带上的状态改为第三分量”“完成第四分量编码的操作(写第1带或左右移)”;若未发现,即停机。
    最后,用标准图灵机U模拟U',就得到了通用图灵机。
     
  • 停机问题是递归可枚举的,但是非递归
    任何可以归约到停机问题的问题都是不可判定的,即没有算法。
     
  • P类与NP类
    P类问题是存在确定型图灵机在多项式时间O(n^k)内能解决的问题;
    NP类问题是存在不确定型图灵机在多项式时间O(n^k)内能解决的问题,即确定性图灵机需要指数时间O(c^(n^k))。
    P类问题是NP类的子集。
    NP完全问题是最难的NP问题,所有NP问题都可以归约至它,也就是说,NP类等于P类,当且仅当NP完全问题属于P类。
     p&np[9]
    p&np2[6] 
    # 老师ppt上的两张图,很具象地表达了NP、P、停机问题、SAT、RE、RE补等之间的关系
     
  • COOK定理Cook–Levin theorem
    Cook定理说,SAT(Boolean Satisfiability)是NPC问题。简单地说,如果对某一个布尔表达式B.E.,存在使其布尔运算结果为1的组合,其就属于SAT。显然,SAT是一个NP问题。那么,对于任意一个NP问题,即存在一个NTM在P(n)时间内解决它,只要找到其归约到SAT的方法(存在多项式时间的映射F),就可以证明SAT是NPC的。
    我们可以将NTM接受该NP问题的过程画成一张P(n)*P(n)的表格,那么,我们可以定义一个布尔表达式F来表述该表格,F∈SAT当且仅当表格对应的输入被NTM接受。F=φ(cell)∧φ(start)∧φ(move)∧φ(accept)。φ(cell)是对表格中每个单元的值的要求,φ(start)是对表格初始状态的要求,φ(move)是对其转移过程的要求,φ(accept)是对其接受格局的要求。wiki上给出了另一种形式的F定义,或者说是要求的划分,证明过程也很详细。但是无论如何定义,其都有一个准则,即F能够准确地涵盖表格的所有内容,包括初始格局、接受格局、转移的中间格局等等。F=1将生成所有NTM的接受表格。并且,生成F本身的算法复杂度是O(P(n)^2)。
    类似的,SAT可以归约到3SAT,其也是NPC问题。
    Cook定理给出了第一个NPC问题,可以用来证明其他问题是NPC问题(把SAT归约到该问题),不过构造,实在是门技巧,还需要极多的灵感。