0. 计算机科学研究：抽象计算机 真实计算机 计算机应用
1.1
1) 计算机科学定义
2) 计算机科学这么广泛的原因：Chomsky,Karp, Babayan, Boutang
3) 计算思维 外部特征：ABC； 内部特征：Acu-exams-cp.
其中exams 的 e 是effectiveness, 竟然译作“构造”.
4) 计算机科学为什么是交响乐? 逻辑思维----使之正确 算法思维----使之巧妙 系统思维----使之实用
其中的主语是计算过程
1.2 在冯诺依曼机上操作数字符号
1)
2) 冯诺依曼模型
a.二进制数据及其算术逻辑操作
b.存储程序计算机
c.串行执行
3) 二进制
a.转化
b.补码
c.计算:忽略最高位溢出的“1”
d.八位二进制补码:$[-128,127]$
4)浮点数，占位符：用 "%c" 实现 "%d",用$\tau=\frac{\sqrt 5 +1}{2}$计数.
1.3 当代计算机科学的三个基本追求
a.巴比奇问题 b.布什问题 c.图灵问题
计算机类型：客户端，服务端,嵌入式
1.4 计算机科学的三个奇妙
1) 指数之妙
a.问题运算量随问题规模指数增长
b.计算速度随时间指数增长
$\Delta$ 拐点：1945年电子计算机ENIAC诞生
2) 模拟之妙 例子
3) 虚拟之妙 例子
2. 逻辑思维
a.比特精准的最基本的体现
b.关注计算过程的比特精准的正确性与通用性
c.布尔逻辑，图灵机，图灵机的通用性与局限，Godel不完备性定理
$\Delta$ 概念、例子.
要点: 布尔逻辑比特精准地定义、建模、推导、证明逻辑命题
2.1 布尔逻辑
1) n-in m-out 个数 $(2^{m})^{2^n}$，事实上只有 1-out
2) 析取、合取范式的写法
3) Kleene表达式个数: $K(1)=6,K(2)=84$
2.2 图灵机:参考实验部分
2.3 图灵机的通用性
a. 计算机能求解任意可计算问题; 真实计算机：精度、存储有限
b. 丘奇—图灵论题：人=图灵机能自动执行的计算；无限存储冯诺依曼机=图灵机
局限性：停机问题
2.4 Godel不完备性定理实例：戈德斯坦定理
3. 算法思维
- 定义：一个算法是一组有穷的规则，给出了求解特定类型问题的运算序列
五个特征：有穷性、确定性、输入(0/多)、输出(1/多)、能行性
- 各种排序
- 复杂度的计算 动态规划算法：$O(n)$
- 记号 $O$ $\Omega$ $\Theta$
- P vs. NP
