01 计算是什么？

计算的本质 Foundations of Computation

程序 = 数据结构 + 算法

理论主轴：计算的形式结构 工程主轴：语言与程序的实现

01_什么是计算 02_状态机与自动机 03_图灵机与可计算性 04_抽象与分层 05_复杂性与约束

工程对应：

• C 语言

• 汇编

• ELF

• 静态链接

• 动态链接

数字电路，状态机，图灵机，编程语言，编译与链接，程序的表示

理解状态与转换。

计算是什么？状态+转换+可计算性

数字逻辑与计算机组成，数字电路，组合逻辑与时序逻辑，存储器结构，ALU，物理状态实现。

自动机理论，有限自动机，图灵机。DFA,NFA，可计算性，复杂性基础。形式计算模型。

编译相关，编译原理，词法、语法、语义，中间表示、代码生成。程序是如何被转换的。

程序设计语言原理PL，静态类型，动态类型，函数式，命令式，抽象机制，作用域。

计算机组成原理。书 《计算机组成与设计（Patterson & Hennessy）》，《计算机系统要素（Nand2Tetris）》

看数字逻辑、组合逻辑与时序逻辑、CPU 设计、指令集结构、控制单元

落点，状态如何被存储？指令如何改变状态？程序如何驱动状态变化？

CSAPP，关注

第2章：信息的表示

第3章：程序的机器级表示

第7章：链接

第8章：异常控制流

落点，C 程序如何变成机器指令？栈帧是什么？控制流如何被打断？

自动机与可计算性，《Introduction to Automata Theory》（Hopcroft）

重点，有限状态机，图灵机，可计算性。

落点：状态机是所有系统的抽象原型。图灵完备意味着什么？

一个系统“是什么”——从计算模型和结构上定义它。

状态是什么？输入输出是什么？哪种模型？

数字电路、计算机组成。回答计算的物理本体

CASPP 前半部分，数据表示，程序表示转换，指令，过程调用。回答程序是什么，执行是什么？

操作系统绪论，回答，OS 是什么模型

数据结构中归于递归栈，状态转移。计算的表达结构

计算模型，可计算性，Introduction to Automata Theory, Languages, and Computation

程序求值（语言与解释器），SICP

系统结构（状态与抽象层），OSTEP