跳转至

计算理论

Abstract

浙江大学 “理论计算机科学导引” 课程及相关知识笔记

手写笔记如下:(仅供参考,可能存在笔误或者错误)

TOC 手写笔记 by HobbitQia
97.1 MB / 28 P / 2024-1-20

下载

  • Preliminaries (Language) - P2
  • Automata - P4

    • NFA (Non-deterministic Finite Automata) - P7
  • REX (Regular Expression) - P12

    • Pumping Theorem - P15
  • CFG (Context-Free Grammar) - P17

    • CNF (Chomsky Norm Form) - P18
  • PDA (Pushdown Automata) - P20

    • CFG <-> PDA - P22
    • Pumping Theorem for CFL - P26
  • Turing Machine - P30

    • TM - P35
    • NTM (non-deterministic TM) - P36
  • Desicion Problem - P38

    • Church-Turing Thesis - P38
    • Encode and Decision Problem - P38
    • Reduction - P41
    • Countable Problem - P43
    • Halting Problem - P45
    • Rice's Theorem - P48
    • Self-Print Program - P51
    • Turing Enumerable - P53
  • Computability - P54

    • Numerical Function - P54
    • \(\mu\)-recursive - P59
  • Conrestricted Grammar - P61

  • Complexity Problem- P62

    • Time Complexity - P62

      • P&NP - P63
      • NP Complete Problem - P66
    • Space Complexity - P70

      • PSAPCE/NPSPACE - P70
      • Hierachy Theorem - P71

最后更新: 2024年1月20日 14:12:23
创建日期: 2023年9月30日 09:19:27

评论