-计算科学简介 Lecture 1 - Introduction to Comp

官方信息技术老师·20 页·深入(追求细节与边界)·0 次浏览·2 天前
计算思维学科地图边界与本质

计算科学简介

看完你能讲清计算的本质、计算机科学的思维范式与可计算的边界

按 空格/→ 演示下一步

1 / 20 页

全部页面点击任意一页,跳回舞台从这页播放

计算思维学科地图边界与本质

计算科学简介

看完你能讲清计算的本质、计算机科学的思维范式与可计算的边界

1第 1 页 · 计算科学简介

什么是计算科学

手机、电脑、智能手表——你每天都在用这些设备。但计算科学家研究的不是这些铁盒子,而是铁盒子里正在发生的'计算'过程。这听起来有点反直觉,却是整个学科的认知起点。

研究对象是计算本身
不是硬件电子,而是能被描述和执行的信息处理过程
三个根本问题
什么能被算?多快能算完?用多少资源算?
科学+工程双重属性
既需要数学证明正确性,也要实际造出能跑的系统
层层抽象的视角
从0和1到算法再到应用,每层都可以独立研究
天文学与望远镜对应 →计算科学与计算机

天文学家透过望远镜研究宇宙,不研究玻璃镜片;计算科学家透过计算机研究计算,不研究电路

2第 2 页 · 什么是计算科学

计算思维的核心

做一道年夜饭级别的硬菜——你不会试图同时处理切菜、调味、火候三件事,而是先拆分成小块、再各个击破。这正是程序员的思考方式。

分解
把大问题拆成可单独处理的小问题
模式识别
在小问题里发现共性,把同类合并处理
抽象
只保留关键特征,忽略噪音细节
算法
给每一步排出明确、可复现的顺序
做年夜饭对应 →计算思维四步

备菜=分解、找菜谱共性=模式识别、只记关键步骤=抽象、按时操作=算法

3第 3 页 · 计算思维的核心

陈述性知识

上页我们讲了计算思维的四大支柱。现在换个角度:你写代码时,是在告诉计算机「怎么做」,还是「我要什么」?这一字之差,就是陈述性与命令式的分界。

描述目标
只说「我要什么结果」,不指定执行步骤
区别于命令式
命令式一步步写流程,陈述式只描述最终状态
典型代表
SQL 查询、HTML 标记、正则表达式、Prolog
易于推理
无显式控制流,便于形式化验证与并行执行
餐厅点菜对应 →陈述式编程

你对服务员说「要宫保鸡丁」,不关心厨师怎么炒;陈述式只声明结果,不写过程

4第 4 页 · 陈述性知识

过程性知识

上一页说「地球绕太阳转」是陈述性知识——只告诉你事实。但只背事实不会算具体轨道,计算机就帮不上忙。真正可执行的,是'怎么做'的过程性知识。

步骤与指令序列
由一系列有序动作构成,描述从初始状态到目标状态的路径
无歧义可执行
每步明确、确定;这正是计算机能消费它的根本原因
算法即其严格化
算法=过程性知识+终止性+有限性,是其最严苛的形式
陈述可推导过程
已知'加法交换律',就能推出多种等价求和流程
做菜菜谱对应 →过程性知识

备料→热锅→翻炒→装盘,每一步对应一条可执行指令

5第 5 页 · 过程性知识

两类知识的对比

知道 ≠ 会用——陈述与过程两类知识常被混为一谈,但在计算科学里必须分清本质。

陈述性知识
  • 回答「是什么」:描述事实与状态
  • 静态记录:棋谱、地图、公式定理
  • 可直接陈述:说出结论即完成
过程性知识
  • 回答「怎么做」:描述方法与步骤
  • 动态执行:下棋策略、算法推演
  • 需展开演练:走一遍才知对错
背下棋谱不等于会下棋——陈述性是「原料」,过程性是「加工方法」,两者兼备才算真懂。
6第 6 页 · 两类知识的对比

图灵机:计算的抽象模型

前页留下一个根本问题——「怎样的过程才算真正可计算」?图灵的答案是:把它简化成一个工人、一条传送带、一本手册的数学模型。

纸带
一条无限长的格子带,每格存一个符号,既是输入也是输出
读写头
每次指向一格,读出当前符号或写入新符号
状态寄存器
记住机器当前处于什么状态,像工人「现在在想哪一步」
转移规则
根据当前状态和读到的符号,决定写什么、移到哪、下一状态
工人照手册在传送带前作业对应 →图灵机运行

传送带是纸带,工人是读写头,手册就是转移规则,工人当前在第几步就是状态

7第 7 页 · 图灵机:计算的抽象模型

图灵机的运行机制

图灵机单步循环:读—查—写—移—变状态,再到判停机节点。

图解渲染中…
n2δ: 输入 (状态, 符号),输出 (新符号, 移动, 新状态)n4磁头每次只能 L 或 R 移动一格n6终止态分 q_accept 与 q_reject,两者均触发停机
8第 8 页 · 图灵机的运行机制

通用图灵机

一台机器能模拟任何其他机器——通用性的深远意义

通用图灵机
一台机器能模拟任何其他机器——通用性的深远意义
9第 9 页 · 通用图灵机

冯·诺依曼架构

中心思想:指令与数据共存于同一存储器,由控制单元统一调度。

图解渲染中…
mem存储程序:指令与数据共用此空间,是核心创新cpu执行单元,按取指-译码-执行循环工作cu发出控制信号,调度各部件时序out1输出设备呈现结果
10第 10 页 · 冯·诺依曼架构

指令的执行周期

CPU 执行每条指令都要走完这四步,然后立刻从头开始下一条。

1
取指
CPU 按 PC 地址从内存读出指令,送入 IR;同时 PC 自增指向下一条
2
译码
控制单元解析操作码,确定操作类型并生成各部件的控制信号
3
执行
ALU 按控制信号完成算术、逻辑运算或计算访存地址
4
写回
结果写回寄存器或内存,为下一条指令的取指与执行做好准备
11第 11 页 · 指令的执行周期

内存层级结构

执行一条指令时,CPU 拿到数据就开始干活。但数据放在哪里,速度差着几个数量级。从 CPU 内置的寄存器一路往外走,每远一步就慢一点,但能装的东西就多一点。

寄存器
CPU 内部,1 拍可访问,容量仅几十字节
缓存 L1/L2/L3
分级缓冲,纳秒级延迟,KB~MB 量级
主存(内存)
程序运行时数据所在,几十纳秒,GB 量级
外存(硬盘/SSD)
断电不丢失,毫秒级延迟,TB 量级
办公桌与档案室对应 →内存层级

桌面 = 寄存器,抽屉 = 缓存,办公位 = 主存,档案室 = 外存

AMAT=htfast+(1h)tslow\text{AMAT} = h \cdot t_{fast} + (1-h) \cdot t_{slow}
12第 12 页 · 内存层级结构

编译与解释

计算机只认 0 和 1 组成的机器指令,但程序员写的是 Python、Java 这种接近人类语言的代码。这中间怎么搭桥?主要有两条路——编译与解释。

编译
一次性把整个源文件翻译成机器码,产出独立可执行文件
解释
逐行读取源代码,每读一句就翻译一句并立即执行
混合模式
先编译成字节码等中间产物,再交给虚拟机解释执行
权衡取舍
编译运行快但需为每种平台单独编译;解释天然跨平台但速度较慢
翻译书与同声传译对应 →编译与解释

整本译完装订成册再读,对应编译产出可执行文件;说一句翻一句,对应边读边执行

13第 13 页 · 编译与解释

编程语言的本质

上一页看到编译器翻译代码,但它凭什么'读懂'你的程序?因为编程语言是种'形式语言'——它和自然语言一样,也分语法、语义、语用三个层次,只是规则严苛得多。

什么是形式语言
为机器设计的符号系统:字符表+形成规则,机器可判定、无歧义
语法 Syntax
规定字符串如何组成合法程序——词法(token)+句法(树结构)
语义 Semantics
合法程序'做什么':每个语句对应的计算效果与状态变化
语用 Pragmatics
社区约定的惯用法:命名风格、设计模式、'这样写更好'的实践
法律条文对应 →编程语言三层次

句式规范对应语法,条文内容对应语义,判案解释原则对应语用

LΣ(Σ 是字符表, L 是合法字符串集合)L \subseteq \Sigma^* \quad (\Sigma\text{ 是字符表},\ L\text{ 是合法字符串集合})
14第 14 页 · 编程语言的本质

语言的层次结构

从人能写什么,到机器能懂什么——三个层级如何递进又闭合。

图解渲染中…
a1CPU直接执行的0/1序列,最底层b1用MOV/ADD等助记符替代二进制c1C/Python等,接近人类思维的表达
15第 15 页 · 语言的层次结构

静态类型 vs 动态类型

区分编译时检查与运行时检查的时机与代价——决定了一个错误在写代码时,还是在用户手里被发现。

静态类型
  • 检查时机:编译时一次性扫全部代码
  • 类型与变量:声明时绑定,运行中不变
  • 失败方式:编译报错,运行前已排除
动态类型
  • 检查时机:运行到那一行才检查
  • 类型与变量:值带类型,变量可随时换
  • 失败方式:运行时报错,可能漏到线上
关键系统与团队工程选静态;脚本/原型/数据处理选动态。真正的安全来自测试覆盖,不在类型系统本身。
16第 16 页 · 静态类型 vs 动态类型

高级语言的执行方式

很多人以为语言非编译即解释,实际还存在混合型;混淆根源在于把『语言的特性』和『实现的特性』混为一谈。

编译型语言
  • 执行方式:一次性整体翻译为机器码再运行
  • 中间产物:生成独立可执行文件(如 .exe)
  • 权衡取舍:运行快、启动慢,跨平台需分别编译
解释型语言
  • 执行方式:逐行读取、逐句翻译执行
  • 中间产物:无独立产物,解释器即为执行环境
  • 权衡取舍:启动快、运行慢,天然跨平台
正确的理解是:编译与解释是连续光谱——Java、Python 等混合型先编译为字节码,再由 VM 解释或 JIT 编译,并非非此即彼。
17第 17 页 · 高级语言的执行方式

核心概念自测

点击作答

以下哪项最能准确概括编译器与解释器的本质区别?

18第 18 页 · 核心概念自测

知识体系回顾

  • 问题、模型、机器:计算科学的三个分析层级
  • 图灵机划定可计算性,冯·诺依曼主导实现
  • 语言是对机器复杂度的逐级封装
  • 类型系统是程序行为的形式契约
延伸主题:不可计算问题的具体例子RISC-V 与 CISC 架构对比λ 演算与类型论简介
19第 19 页 · 知识体系回顾

课后思考

先合上书自己想一分钟,再点开参考答案——好问题往往比标准答案更值得琢磨。

1从图灵机到冯·诺依曼架构,贯穿始终的核心抽象是什么?为什么说「程序与数据共存于内存」是一次范式飞跃?

参考答案图灵机抽象出「状态+读写头+规则」,把指令也变成了数据;冯·诺依曼把程序放进内存,机器从此能修改自身行为。核心是从「专用」走向「通用」。

2如果用一句话向非程序员解释「为什么代码必须先翻译成机器语言才能执行」,你会怎么说?这个翻译带来了什么「收益」和「代价」?

参考答案类比:源代码像菜谱,机器码像厨师的具体动作。收益是人能读、能跨平台;代价是性能开销和失去对底层的直接控制——所以 C/C++ 至今不可被替代。

3图灵完备意味着「一切可计算的都能算」,那现实中为什么还有「不可解」的问题?这种理论上限对我们选择编程语言有什么启示?

参考答案图灵完备是能力天花板,不是效率保证。停机问题、指数复杂度问题理论可解但实际不可行。这提醒我们:选语言不只是语法偏好,更要看问题规模与生态约束。

20第 20 页 · 课后思考