图灵.mp4

好像近年大数据，人工智能很流行。回想二十多年前(1996年)刚开始参加工作时，接手教学的第一门课就是计算理论基础的<<计算机编译原理>>。这里推荐中英均可以从互联网上免费下载到的书 “Elements of the Theory of Computation (Harry R. Lewis & Christos H. Papadimitriou)” (中文翻译版为“计算理论基础(刘易斯，帕帕蒂米特里奥)”)，介绍了计算理论最核心、最基本的内容，包括形式语言与自动机、可计算性和计算复杂性三大部分。全书共分七章，分别为：集合、关系和语言；有穷自动机；上下文无关语言； Turing机；不可判定性；计算复杂性；NP完全性。第二版的目录为：
第1章 集合. 关系和语言
1.1 集合
1.2 关系与函数
1.3 特殊类型的二元关系
1.4 有穷集合与无穷集合
1.5 三个基本的证明技术
1.6 闭包与算法
1.7 字母表与语言
1.8 语言的有穷表示
参考文献
第2章 有穷自动机
2.1 确定型有穷自动机
2.2 非确定型有穷自动机
2.3 有穷自动机与正则表达式
2.4 正则语言与非正则语言
2.5 状态最小化
2.6 关于有穷自动机的算法
参考文献
第3章 上下文无关语言
3.1 上下文无关文法
3.2 语法分析树
3.3 下推自动机
3.4 下推自动机与上下文无关文法
3.5 上下文无关语言与非上下文无关语言
3.6 关于上下文无关文法的算法
3.7 确定性与语法分析
参考文献
第4章 Turing机
4.1 Turing机的定义
4.2 用Turing机计算
4.3 Turing机的扩充
4.4 随机存取Turing机
4.5 非确定型Turing机
4.6 文法
4.7 数值函数
参考文献
第5章 不可判定性
5.1 Church-Turing论题
5.2 通用Turing机
5.3 停机问题
5.4 与Turing机有关的不可判定问题
5.5 与文法有关的不可解问题
5.6 不可解的铺砖问题
5.7 递归语言的性质
参考文献
第6章 计算复杂性
6.1 P类
6.2 若干问题
6.3 布尔可满足性
6.4 NP类
参考文献
第7章 NP完全性
7.1 多项式时间归约
7.2 Cook定理
7.3 其他的NP完全问题
7.4 对付NP完全性
参考文献
索引

"Introduction to the Theory of Computation (3rd edition) (Author: Michael Sipser)"  ("计算理论导引（原书第3版)(迈克尔·西普塞)") 系統地介紹計算理論的三大主要內容：自動機與語言、可計算性理論和計算複雜性理論。同時，重點講解了可計算性和計算複雜性理論中的某些高級內容。

目錄
出版者的話
譯者序
第3版前言
第2版前言
第1版前言
第0章 緒論
  0.1 自動機、可計算性與複雜性
    0.1.1 計算複雜性理論
    0.1.2 可計算性理論
    0.1.3 自動機理論
  0.2 數學概念和術語
    0.2.1 集合
    0.2.2 序列和多元組
    0.2.3 函數和關係
    0.2.4 圖
    0.2.5 字元串和語言
    0.2.6 布爾邏輯
    0.2.7 數學名辭彙總
  0.3 定義、定理和證明
  0.4 證明的類型
    0.4.1 構造性證明
    0.4.2 反證法
    0.4.3 歸納法
  練習
  問題
  習題選解
第一部分自動機與語言
第1章 正則語言
  1.1 有窮自動機
    1.1.1 有窮自動機的形式化定義
    1.1.2 有窮自動機舉例
    1.1.3 計算的形式化定義
    1.1.4 設計有窮自動機
    1.1.5 正則運算
  1.2 非確定性
    1.2.1 非確定型有窮自動機的形式化定義
    1.2.2 NFA與DFA的等價性
    1.2.3 在正則運算下的封閉性
  1.3 正則表達式
    1.3.1 正則表達式的形式化定義
    1.3.2 與有窮自動機的等價性
  1.4 非正則語言
  練習
  問題
  習題選解
第2章 上下文無關文法
  2.1 上下文無關文法概述
    2.1.1 上下文無關文法的形式化定義
    2.1.2 上下文無關文法舉例
    2.1.3 設計上下文無關文法
    2.1.4 歧義性
    2.1.5 喬姆斯基範式
  2.2 下推自動機
    2.2.1 下推自動機的形式化定義
    2.2.2 下推自動機舉例
    2.2.3 與上下文無關文法的等價性
  2.3 非上下文無關語言
  2.4 確定型上下文無關語言
    2.4.1 DCFL的性質
    2.4.2 確定型上下文無關文法
    2.4.3 DPDA和DCFG的關係
    2.4.4 語法分析和LR(k)文法
  練習
  問題
  習題選解

第二部分 可計算性理論
第3章 丘奇圖靈論題
  3.1 圖靈機
    3.1.1 圖靈機的形式化定義
    3.1.2 圖靈機的例子
  3.2 圖靈機的變形
    3.2.1 多帶圖靈機
    3.2.2 非確定型圖靈機
    3.2.3 枚舉器
    3.2.4 與其他模型的等價性
  3.3 演算法的定義
    3.3.1 希爾伯特問題
    3.3.2 描述圖靈機的術語
  練習
  問題
  習題選解
第4章 可判定性
  4.1 可判定語言
    4.1.1 與正則語言相關的可判定性問題
    4.1.2 與上下文無關語言相關的可判定性問題
  4.2 不可判定性
    4.2.1 對角化方法
    4.2.2 不可判定語言
    4.2.3 一個圖靈不可識別語言
  練習
  問題
  習題選解
第5章 可歸約性
  5.1 語言理論中的不可判定問題
  5.2 一個簡單的不可判定問題
  5.3 映射可歸約性
    5.3.1 可計算函數
    5.3.2 映射可歸約性的形式化定義
  練習
  問題
  習題選解
第6章 可計算性理論的高級專題
  6.1 遞歸定理
    6.1.1 自引用
    6.1.2 遞歸定理的術語
    6.1.3 應用
  6.2 邏輯理論的可判定性
    6.2.1 一個可判定的理論
    6.2.2 一個不可判定的理論
  6.3 圖靈可歸約性
  6.4 信息的定義
    6.4.1 極小長度的描述
    6.4.2 定義的優化
    6.4.3 不可壓縮的串和隨機性
  練習
  問題
  習題選解

第三部分 複雜性理論
第7章 時間複雜性
  7.1 度量複雜性
    7.1.1 大O和小o記法
    7.1.2 分析演算法
    7.1.3 模型間的複雜性關係
  7.2 P類
    7.2.1 多項式時間
    7.2.2 P中的問題舉例
  7.3 NP類
    7.3.1 NP中的問題舉例
    7.3.2 P與NP問題
  7.4 NP完全性
    7.4.1 多項式時間可歸約性
    7.4.2 NP完全性的定義
    7.4.3 庫克列文定理
  7.5 幾個NP完全問題
    7.5.1 頂點覆蓋問題
    7.5.2 哈密頓路徑問題
    7.5.3 子集和問題
  練習
  問題
  習題選解
第8章 空間複雜性
  8.1 薩維奇定理
  8.2 PSPACE類
  8.3 PSPACE完全性
    8.3.1 TQBF問題
    8.3.2 博弈的必勝策略
    8.3.3 廣義地理學
  8.4 L類和NL類
  8.5 NL完全性
  8.6 NL等於coNL
  練習
  問題
  習題選解
第9章 難解性
  9.1 層次定理
  9.2 相對化
  9.3 電路複雜性
  練習
  問題
  習題選解
第10章 複雜性理論高級專題
  10.1 近似演算法
    10.2 概率演算法
    10.2.1 BPP類
    10.2.2 素數性
    10.2.3 只讀一次的分支程序
  10.3 交錯式
    10.3.1 交錯式時間與交錯式空間
    10.3.2 多項式時間層次
  10.4 互動式證明系統
    10.4.1 圖的非同構
    10.4.2 模型的定義
    10.4.3 IP=PSPACE
  10.5 並行計算
    10.5.1 一致布爾電路
    10.5.2 NC類
    10.5.3 P完全性
  10.6 密碼學
    10.6.1 密鑰
    10.6.2 公鑰密碼系統
    10.6.3 單向函數
    10.6.4 天窗函數
  練習
  問題
  習題選解
參考文獻
索引

关于Turing和他的博士学位导师Church还有故事: 丘奇和图灵.pdf