计算理论

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

评论