计算理论导引

摘要: 《计算理论导引》

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本书系统地介绍了计算理论的三个主要内容：自动机与语言、可计算性理论、计算复杂性理论。

• 《计算理论导引》 (提取码: ndju)

前置内容

• 自动机、可计算性与复杂性
  • 计算复杂性理论
  • 可计算性理论
  • 自动机理论
• 数学概念和术语
  • 集合
  • 序列和多元组
  • 函数和关系
  • 图
  • 字符串和语言
  • 布尔逻辑
  • 数学名词汇总
• 定义、定理和证明
• 证明的类型
  • 构造性证明
  • 反证法
  • 归纳法

自动机与语言

正则语言

• 有穷自动机
  • 有穷自动机的形式化定义
  • 有穷自动机举例
  • 计算的形式化定义
  • 设计有穷自动机
  • 正则运算
• 非确定性
  • 非确定型有穷自动机的形式化定义
  • NFA与DFA的等价性
  • 在正则运算下的封闭性
• 正则表达式
  • 正则表达式的形式化定义
  • 与有穷自动机的等价性
• 非正则语言

上下文无关文法

• 上下文无关文法概述
  • 上下文无关文法的形式化定义
  • 上下文无关文法举例
  • 设计上下文无关文法
  • 歧义性
  • 乔姆斯基范式
• 下推自动机
  • 下推自动机的形式化定义
  • 下推自动机举例
  • 与上下文无关文法的等价性
• 非上下文无关语言
• 确定型上下文无关语言
  • DCFL的性质
  • 确定型上下文无关文法
  • DPDA和DCFG的关系
  • 语法分析和LR(k)文法

可计算性理论

丘奇图灵论题

• 图灵机
  • 图灵机的形式化定义
  • 图灵机的例子
• 图灵机的变形
  • 多带图灵机
  • 非确定型图灵机
  • 枚举器
  • 与其他模型的等价性
• 算法的定义
  • 希尔伯特问题
  • 描述图灵机的术语

可判定性

• 可判定语言
  • 与正则语言相关的可判定性问题
  • 与上下文无关语言相关的可判定性问题
• 不可判定性
  • 对角化方法
  • 不可判定语言
  • 一个图灵不可识别语言

可归约性

• 语言理论中的不可判定问题
• 一个简单的不可判定问题
• 映射可归约性
  • 可计算函数
  • 映射可归约性的形式化定义

可计算性理论的高级专题

• 递归定理
  • 自引用
  • 递归定理的术语
  • 应用
• 逻辑理论的可判定性
  • 一个可判定的理论
  • 一个不可判定的理论
• 图灵可归约性
• 信息的定义
  • 极小长度的描述
  • 定义的优化
  • 不可压缩的串和随机性

复杂性理论

时间复杂性

• 度量复杂性
  • 大O和小o记法
  • 分析算法
  • 模型间的复杂性关系
• P类
  • 多项式时间
  • P中的问题举例
• NP类
  • NP中的问题举例
  • P与NP问题
• NP完全性
  • 多项式时间可归约性
  • NP完全性的定义
  • 库克列文定理
• 几个NP完全问题
  • 顶点覆盖问题
  • 哈密顿路径问题
  • 子集和问题

空间复杂性

• 萨维奇定理
• PSPACE类
• PSPACE完全性
  • TQBF问题
  • 博弈的必胜策略
  • 广义地理学
• L类和NL类
• NL完全性
• NL等于coNL

难解性

• 层次定理
• 相对化
• 电路复杂性

复杂性理论高级专题

• 近似算法
• 概率算法
  • BPP类
  • 素数性
  • 只读一次的分支程序
• 交错式
  • 交错式时间与交错式空间
  • 多项式时间层次
• 交互式证明系统
  • 图的非同构
  • 模型的定义
  • IP=PSPACE
• 并行计算
  • 一致布尔电路
  • NC类
  • P完全性
• 密码学
  • 密钥
  • 公钥密码系统
  • 单向函数
  • 天窗函数

---