计算理论大纲

本文最后更新于:2021年7月13日 上午

一个相当玄学的课,很多时候觉得自己充分理解了,结果全错了……

计算理论大纲

自动机与语言

正则语言

有穷自动机 DFA

  • 语言描述
  • 形式化定义:(Q,,δ,q0,F)(Q,\sum,\delta,q_0,F)
  • 接受的语言 A=L(M)A=L(M)
    • 正则语言
  • 设计方法:把自己假想为机器
  • 工具箱:正则运算——并、连接、星号
    • 正则语言在正则运算下封闭

非确定型 NFA

  • 非确定型
    • 方便证明正则运算的封闭性
  • 语言描述
  • 形式化定义
  • NFA=DFA
    • NFA转DFA方法

正则表达式 REX

  • 形式化定义
    • ϵ\epsilon\emptyset的区别
  • L(R)=L(MDFA)=(LNFA)L(R)=L(M_{DFA})=(L_{NFA})
    • R转NFA办法
非正则语言
  • 泵引理

    • 条件1中的ii可以为0
    • 条件3在证明非正则性很有用
  • 典型非正则语言

    • {0n1nn0}\{0^n1^n|n\geq 0\}
    • {ωω中0和1的个数相等}\{\omega|\omega\text{中0和1的个数相等}\}
    • {ωωω{0,1}}\{\omega\omega|\omega\in\{0,1\}^*\}

上下文无关文法

上下文无关文法概述 CFG

  • 形式化定义:(V,,R,S)(V,\sum,R,S)
    • 歧义性:最左派生
  • 设计上下文无关文法:考察子串
  • 乔姆斯基范式

下推自动机 PDA

  • PDA=非确定型有穷自动机+栈
    • 非确定型下推自动机=上下无关文法
      • PDA 转 CFG
      • CFG 转 PDA
  • 形式化定义:(Q,,Γ,δ,q0,F)(Q,\sum,\Gamma,\delta,q_0,F)
    • 检验空串:$\$
  • 正则语言\in上下文无关语言

非上下文无关语言

  • 泵引理

    • 条件1中的ii可以为0
    • 条件3在证明非上下文无关语言很有用
  • 典型非上下文无关语言

    • {anbncnn0}\{a^nb^nc^n|n\geq0\}
    • {aibjck0ijk}\{a^ib^jc^k|0\leq i \leq j\leq k\}
    • {ωωω{0,1}}\{\omega\omega|\omega\in\{0,1\}^*\}

可计算理论

丘奇——图灵论题

图灵机 TM

  • TM=无限大容量存储+任意访问内部数据+有穷自动机
  • 停机=接受/拒绝
  • 形式化描述:(Q,,Γ,δ,q0,qaccept,qreject)(Q,\sum,\Gamma,\delta,q_0,q_{accept},q_{reject})
  • 接受,除此之外拒绝或不停机——图灵可识别 L(TM)L(TM)
  • 接受,除此之外拒绝——图灵可判定

图灵机的变形

  • 多带图灵机=单带图灵机
  • 非确定型图灵机=确定型图灵机
  • 图灵可识别的语言=能被枚举器枚举的语言

可判定性

可判定语言

  • 可判定语言:ADFA,ANFA,AREX,EDFA,EQDFAACFG,ECFGA_{DFA},A_{NFA},A_{REX},E_{DFA},EQ_{DFA},A_{CFG},E_{CFG}
    • A接受串问题、E空性质测试、EQ判断是否为统一语言
    • 正则语言上下文无关的可判定的图灵可识别的\text{正则语言}\subset\text{上下文无关的}\subset\text{可判定的}\subset\text{图灵可识别的}

不可判定性

  • 不可判定的:ATMA_{TM}
    • 但是可识别
  • 补图灵可识别
    • 可判定的语言=图灵可识别+补图灵可识别

可归约性

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

  • 不可判定的:HALTTM,ETMHALT_{TM},E_{TM}

复杂性理论

事件复杂性

  • 渐进记法:大O
  • 时间复杂性类:TIME(t(n))TIME(t(n))O(t(n))O(t(n))的图灵机判定所有语言的集合
  • 复杂性关系
    • t(n)t(n)多带图灵机=t2(n)t^2(n)单带图灵机
    • t(n)t(n)非确定型单带图灵机=2t(n)2^{t(n)}确定型单带图灵机
    • 模型为单带图灵机的时间复杂度类TIME(O(nlogn))TIME(O(nlogn))判定的语言都是正则语言

P类

  • P:确定型单带图灵机在多项式时间内可判定的语言类
    • 所有的上下文无关语言都是P的成员

NP类

  • NP:非确定型多项式时间图灵机NTM判定
    • 证明每一分支最多使用多项式个步骤

NP完全性

  • NP-complete:NPC问题多项式时间可解,则所有的NP问题多项式时间可解

  • NPC问题:可满足性问题SAT

  • 多项式时间可归约:ApBA\leq_pBωAf(ω)B\omega\in A \Leftrightarrow f(\omega)\in B

    • NPC证明:1. 属于NP 2. 能够归约一个NPC
  • 库克-列文定理:SAT是NP完全的

    • 3SAT是NP完全的
    • HAMPATH是NP完全的

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!