[关闭]
@bintou 2016-01-28T08:23:14.000000Z 字数 1466 阅读 5199

《计算理论导引》学习笔记

计算理论 学习笔记


ITOC(Introduction to Theory Of Computation)主讲三大内容:什么是计算;什么可计算;如何度量计算问题的效率。大致上来说,首先我们需要一种准确的表达法来说明到底计算本质上是什么,不同的科学家抽象出不同的计算模型,于是我们就要考查这些模型的表达能力(第一部分)。其次,我们发现计算是有局限的,不是什么问题都能计算,那到底什么是可计算的问题呢?有什么问题是不可计算的呢(不存在算法)?(第二部分)如果某些问题是可解的,存在某种算法可以解决这个问题,那么这种算法的效率如何度量呢?我们需要一种通用的标准度量,並建立相關理論。(第三部分)

2016年元月 by Bintou

第0章 引論

0.1 自动机、可计算性、复杂性

0.2 數學表示與術語

0.3 定義、定理與證明

0.4 证明的类型

學習時間安排:一天或者半天;應該無難點。

第1章 正則語言

Language(语言),对计算问题的高度抽象表达。整本书的重点是“计算“,如果能体会出在描述计算理论时语言的定义所产生的巨大作用,则理解就上了一个台阶。只是,第一章并不能产生这么大的效用,需持续关注。

1.1 有限自动机

概念:FA、語言、正則語言、正則操作
定理:正則語言類在正則操作(並、交、串聯)下封閉;

1.2 非确定性

重點:體會計算的非確定性
難點:DFA與NFA的等價

对非确定性的两种解读:1、并行执行;2、总是猜对执行路径。哪一种更好?
问题:为什么我们需要“不确定性“?

1.3 正则表达

1.4 非正则语言

要點:自動機的計算侷限
難點:Pumping Lemma及其應用

2016年元月22日上午,自己重新複習了一遍第1章,感覺很容易,然而依然感覺有意思。

第2章 上下文无关语言

2.1 上下文无关文法

重点:歧义性

问题1:为什么把能以不同方式生成的字符串称为歧义?
问题2:为什么需要“最左派生“这个定义?

2.2 下推自動機

下退自动机(PDA)比有限自动机的能力更强,主要体现在哪里?为什么PDA能力会更强呢?

问题1:在Lemma 2.21的证明中,如何确保可被匹配的串w一定会被匹配?
回答:构造算法是非确定性算法。重点体会非确定性选择的含义。

问题2:在Lemma 2.27的证明中,如果p不可达q,那么的构造是否还合法(会出现不合法的情况)?
回答:暂无

2.3 非上下文無關語言

2.4 (忽略)

第3章 丘奇-圖靈命題

這一章的主要內容介紹圖靈機及其相關概念。其主旨是進一步刻畫計算的本質。重點要區分兩個概念:圖靈可判定與圖靈可識別。從算法的角度看,前者要求計算這有限步之後停機,而後者沒有。明白了這個區別,就對計算機的有限計算有了更深入的理解。

3.1 圖靈機

一種計算模型

3.2 圖靈機的各種變形

3.3 算法的定義

第4章 判定性

4.1 可判定语言

4.2 停机问题

重点:对角线法、停机问题不可判定的证明

5 可归约性

这一章的重点是理解归约的本质、过程与应用。

5.1 语言理论中的不可判定问题

针对RL与CFL的若干语言形成的判定性问题进行证明。

5.2 一个简单的不可判定问题:PCP问题

只是一个证明!PCP问题的描述很简单,其不可判定性倒是颇令人感到意外。这里除了一个结论,一个冗长的证明外,内容不多。

5.3 不可判定问题的形式化定义:映射可归约性

重点:Mapping Reducibility的定义

第6章 计算理论的高级专题

61. 递归定理

递归定理展示“程序自我复制是可能的“这样一个简单而令人吃惊的结论。

The Quine Page,里面收集了大量不同语言写成的Quine程序:自己输出自己源代码的程序。

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注