第02章 计算与计算科学
北京大学《信息技术导论》课程第2章，主讲：苏庆新（SQN），2008年 原始文件：第02章 计算与计算科学.ppt，1.53MB，PowerPoint 97-2003二进制格式
本章结构
本章共 3 大节，从计算的本质出发，延伸到人工智能与计算学科全景：
- 计算的本质 — 计算之源、图灵机模型、计算学科定义、七大研究领域
- 人工智能 — AI 定义、图灵测试、机器智能的边界
- 计算学科的专业方向与知识领域 — CS/CE/SE/IT 四专业方向 + 各学科知识体系
一、计算的本质
1. 计算之源
计算的定义：计算就是符号串的变换。从一个已知的符号串开始，按照一定的规则，一步一步地改变符号串，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。
算法的定义：求解某类问题的通用法则或方法，即符号串变换的规则。
广义计算观：
- 一个函数变化（把 x 变成 f(x)）就是一个计算
- 如果把一切都看作信息，计算就是对信息的变换
- 自然界充满了计算：小球落地弹起，大地就是一个系统，输入=小球扔下去，输出=小球弹回来，完成了一次信息变换
2. 图灵机模型
图灵机是一种抽象计算模型，用来精确定义可计算函数。
三大组成：
- 一个有限状态控制器
- 一条可以无限延伸的带子（存储符号）
- 一个在带子上左右移动的读写头
阿兰·图灵（Alan Turing）的贡献：
- 16岁：研究爱因斯坦相对论
- 24岁：提出图灵机理论
- 31岁：参与破译德国密码机器 Enigma
- 33岁：设想仿真系统
- 35岁：提出自动程序设计概念
- 38岁：设计”图灵测试”
图灵最大的贡献：把”算法”这个基本而深刻的概念，用图灵机模型讲清楚了。
历史地位：ACM 从 1966 年起设立最高荣誉奖——ACM 图灵奖，纪念这位”计算机理论之父”。
3. 计算学科的认知
背景：1984 年美国计算机科学与工程博士单位评审部讨论认知问题，促使 ACM 与 IEEE/CS 于 1985 年春联手组成任务组。经过近 4 年工作，提交了里程碑报告：《计算作为一门学科》（Computing as a Discipline）。
报告论证了计算作为一门学科的事实，将计算机科学、计算机工程、计算机信息学等专业统一归入计算学科。
计算学科的定义：
对描述和变换信息的算法过程进行的系统研究，包括理论、分析、设计、效率、实现和应用等。
研究范围包括：
- 算法与可计算性的理论研究
- 可计算硬件和软件的实际实现
- 所有科目的理论研究、实验方法和工程设计
4. 计算机科学七大研究领域
| 序号 | 研究领域 | 核心内容 |
|---|---|---|
| 1 | 计算机系统结构 | 硬件体系、组成原理 |
| 2 | 程序设计科学与方法论 | 语言、范式、方法学 |
| 3 | 软件工程基础理论 | 开发方法、质量、管理 |
| 4 | 人工智能与知识处理 | 智能系统、知识表示、推理 |
| 5 | 网络、数据库及计算机辅助技术 | 分布式系统、信息管理、CAD/CAM |
| 6 | 理论计算机科学 | 可计算性、计算复杂性、形式化方法 |
| 7 | 计算机科学史 | 学科发展历程、思想演进 |
二、人工智能
1. 什么是人工智能
研究人类智能活动的规律，构造具有一定智能的人工系统，研究如何让计算机去完成以往需要人的智力才能胜任的工作——也就是研究如何应用计算机的软硬件来模拟人类某些智能行为的基本理论、方法和技术。
核心问题：“无心”的机器——计算机有智能吗？
2. 图灵测试（Turing Test）
图灵提出的思想实验：
一个人在不知情的条件下，通过一种特殊的方式，和一台机器进行问答。如果在相当长时间内，他分辨不出与他交流的对象是人还是机器，那么这台机器就可以认为是能思维的。
这是判断机器具备智能的经典行为主义标准。
三、计算学科的专业方向与知识领域
1. 背景
信息技术迅速扩展到各个领域，社会对信息的依赖快速增长。IEEE/CS 和 ACM 任务组在 2001-2005 年提交了 5 个分支学科的教程及总报告（CC2005）：
- 计算机科学（CS）
- 信息系统（IS）
- 软件工程（SE）
- 计算机工程（CE）
- 信息技术（IT）
中国情况：教育部计算机教指委《计算机专业规范》采纳了 CC2005 中的四个分支学科（CS/CE/SE/IT），以专业方向形式规范。
2. 学科专业名称演变史
| 时间 | 事件 |
|---|---|
| 1956年 | 中国开设”计算装置与仪器”专业 |
| 1962年 | 美国普渡大学开设最早的计算机科学学位课程 |
| 1968年 | NATO 会议提出”软件工程”概念（应对软件危机） |
| 1970年代 | 计算机工程从电子工程中脱离，成为独立二级学科 |
| 1980年代 | 英、澳最早开设单独的软件工程学位课程 |
| 1990年代 | 信息系统和信息技术学位课程大量出现 |
3. 四大专业方向对比
计算机科学（CS）
- 定位：计算各学科的基础
- 关注：计算的理论基础和算法
- 去向：软件开发及其相关理论研究
- 知识领域（14个）：离散结构 / 程序设计基础 / 算法与复杂性 / 程序设计语言 / 计算机结构与组织 / 操作系统 / 人机交互 / 图形学与可视计算 / 智能系统 / 信息管理 / 网络计算 / 软件工程 / 数值计算科学 / 社会和职业问题
计算机工程（CE）
- 定位：现代计算系统和设备上软件与硬件的设计、构造、实施与维护
- 关注：设计并实施集软件和硬件为一体的系统（如嵌入式系统）
- 知识领域（18个核心）：电路和信号 / 数字逻辑 / 电子学 / VLSI设计与构造 / 计算机体系结构和组织 / 计算机系统工程 / 嵌入式系统 / 数字信号处理 / 数据库系统 / 算法和复杂性 / 人机交互 / 计算机网络 / 操作系统 / 程序设计基础 / 社会和职业问题 / 软件工程 / 离散结构 / 概率和统计
软件工程（SE）
- 定义：以系统的、学科的、定量的途径，把工程应用于软件的开发、运营和维护；同时研究上述过程中的各种方法和途径。
- 关注：以工程规范进行的大规模软件系统开发与维护，尽可能避免软件系统潜在风险
- 两大方向：工程学 + 方法学
- 知识领域（CCSE，11个）：计算的本质 / 数学与工程基础 / 职业训练 / 软件建模与分析 / 软件设计 / 软件验证 / 软件进化 / 软件过程 / 软件质量 / 软件管理 / 系统与应用专题
信息技术（IT）
- 定位：在一定组织及社会环境下，通过选择、创造、应用、集成和管理的计算技术来满足用户的需求
- 关注：基于计算机的新产品及其正常运行和维护，使用相关技术计划、实施和配置计算机系统
- 与信息系统的区别：IT 更关注”技术”层面，IS 更侧重”信息”层面
- 知识领域（12个）：信息技术基础 / 人机交互 / 程序设计基础 / 信息保障与安全 / 信息管理 / 集成程序设计技术 / 计算机网络 / 平台技术 / 系统管理与维护 / 系统集成和体系结构 / 信息技术与社会环境 / 系统和技术
关键洞见
- 计算的本质是信息变换：从符号串变换到函数映射，再到自然界的系统输入-输出，计算是一个普适概念
- 图灵的奠基地位：图灵机=算法的数学精确定义，没有图灵机就没有现代计算机的理论基础
- 计算学科的工程属性：从”计算机科学”到四大专业方向，学科越来越工程化、应用化
- 软件工程的提出源于危机：软件危机-NATO会议-软件工程，是问题驱动的学科发展
- AI 的行为主义定义：图灵测试是功能主义/行为主义的智能判定标准——不问内部机制，只看外部表现
知识关联
- 《SICP》-计算机程序的构造和解释-第二版 — 计算即符号操作，与本章”计算=符号串变换”思想同根
- 《结构化计算机组成》-Structured-Computer-Organization-第6版-Tanenbaum — 计算机系统结构方向的深入教材
- 《算法导论》-Introduction to Algorithms-第3版-CLRS — 算法与复杂性领域的核心教材
- 《程序员修炼之道》-从小工到专家 — 软件开发方法论与职业素养
- 《代码整洁之道》-Clean Code-Robert-C-Martin — 软件工程实践
- 中断系统-第13章-计算机组织与系统结构 — 计算机组成方向的课程笔记
- 设计模式课程 第3讲（原则） — 软件设计原则