提供了不少启示。
2.20 举例说明计算机中的博弈问题。
答：计算机中的博弈问题是人工智能领域研究的重点内容之一。其中最具代表性的是双人完备博弈，如国际象棋、西洋跳棋、围棋、中国象棋等。对于任何一种双人完备博弈，都可以用一个博弈树（与或树）来描述，并通过博弈树搜索策略寻找最佳解。1997年5月，由IBM公司研制的高性能并行计算机“深蓝”与国际象棋冠军卡斯帕罗夫交战，以两胜一负三平取得了胜利。 2.21 为什么说人要在计算能力上超过计算机是不现实的？
答：略。
2.22 简述计算机科学各主领域的内容。
答：计算机科学包括离散结构、程序设计基础、算法与复杂性、体系结构、操作系统、网络计算。程序设计语言、人机交互、图形学和可视化计算、智能系统、信息系统、软件工程、社会和职业问题、科学计算等主领域。对各个主领域的内容简述如下。
离散结构包括集合论、数理逻辑、代数系统、图论和组合数学等重要内容。
程序设计基础领域的知识由程序设计实践中所需要的基本技能和概念组成，该领域的知识单元包括了基本程序设计概念、基本数据结构、算法程序等。
算法是计算机科学和软件工程的基础。现实世界中任何软件系统的性能仅依赖于两个方面：所选择的算法、以及在各不同层次实现的效率。算法研究能够深刻理解问题的本质和可能的求解技术，而不依赖于具体的程序设计语言、程序设计模式、计算机硬件、或其他任何与实现有关的内容。
计算机在计算技术中处于核心地位。作为计算专业的学生，都应该对计算机系统的功能部件、功能特点、性能和相互作用有一定的理解，而不应该只将计算机看作是一个执行程序的黑盒子。
操作系统是对计算机硬件行为的抽象，程序员用它来对硬件进行控制。操作系统还负责管理计算机用户间的共享资源（如文件等）。 网络计算包括的子领域有：计算机通信网络的概念和协议、多媒体系统、Web标准和技术、网络安全、移动计算、以及分布式系统等。
程序设计语言是程序员与计算机交流的主要工具。一个程序员不仅要掌握一种程序设计语言，更要了解各种程序设计语言的不同风格。在工作中，程序员会将使用不同风格的语言，也会遇到许多不同的语言。为了迅速掌握一门新语言，程序员必须理解程序设计语言的语义以及在不同的程序设计范式之间设计上的折中。为了理解程序设计语言实用的一面，还要求具有程序设计语言翻译和诸如存储分配等方面的基础知识。
人机交互的重点，在于理解作为交互式对象的人的行为，知道怎样使用以人为中心的方法来开发和评价交互式软件系统。
图形学和可视化计算领域可以划分成计算机图形学、可视化、虚拟现实、计算机视觉等4个相互关联的领域。其中，计算机图形学是一门以计算机产生，并在其上展示的图像进行信息交流的艺术和科学；计算机图形学的目标是对人的视觉中心及其他认知中心有进一步深入的了解。可视化领域是为了确定并展示存在于（如计算和医学科学）和比较抽象的数据集中基本的相互关联的结构与关系；展示的主要目标应当是发掘在数据集中替在的信息，从而有助于用户对它们的理解。虚拟现实是要让户能够经历由计算机图形学以及可能的其他感知通道产生的三维环境，提供一种能增进用户与计算机创建的“世界”交互作用的环境。计算机视觉的目标是推导从一幅或多幅二维图像所表示的出三维图像世界的性质和结构。
智能系统依赖于一整套关于问题求解、搜索算法以及机器学习技术的专门知识表示机制和推理机制。
信息系统包括信息获取、信息数字化、信息表示、组织、转化和信息的表现；有效地访问和更新存储信息的算法、数据建模和数据抽象以及物理文件的存储技术、共享数据的信息安全、隐私性、完备性和保护。
软件工程是一门关于如何有效构建满足用户需求的软件系统所需的理论、知识和实践的学科。软件工程适应各种软件开发，它包含需求分析和规格、设计、构建、测试、运行和维护等软件系统生存周期的所有阶段。软件工程使用工程化的方法、过程、技术和度量标准。
通过学习社会和职业问题主领域的知识，学生需要了解计算学科本身基本的文化、社会、法律和道德等问题，知道这个学科的过去、现在和未来，同时也要了解在该学科的发展过程中起着重要作用的哲学问题、技术问题和美学价值观。学生应该有能力提出关于社会对信息技术的影响问题，以及对这些问题的可能答案进行评价的能力。最后，学生需要认识到软/硬件销售商和用户的权利，还必须遵守相关的职业道德。
科学计算领域提供了许多有价值的思想和技术，包括数值表示的精度、误差分析、数值技术、建模和仿真。 2.23 *计算机科学各主领域包括哪些基本问题？
答：计算机科学包括离散结构、程序设计基础、算法与复杂性、体系结构、操作系统、网络计算。程序设计语言、人机交互、图形学和可视化计算、智能系统、信息系统、软件工程、社会和职业问题、科学计算等主领域。
程序设计基础主领域的基本问题包括：（1）对给定的问题，如何进行有效的描述并给出算法？（2）如何正确选择数据结构？（3）
6
如何进行设计、编码、测试和调试程序？
算法与复杂性主领域的基本问题包括：（1）对于给定的问题类，最好的算法是什么？要求的存储空间和计算时间有多少？空间和时间如何折衷？（2）访问数据的最好方法是什么？（3）算法最好和最坏的情况是什么？（4）算法的平均性能如何？（5）算法的通用性如何？
体系结构主领域的基本问题包括：（1）实现处理器、内存和机内通信的方法是什么？（2）如何设计和控制大型计算系统，而且使其令人相信，尽管存在错误和失败，但它仍然是按照我们的意图工作的？（3）哪种类型的体系结构能有效地包含许多在一个计算中能并行工作的处理元素？（4）如何度量性能？
操作系统主领域的基本问题包括： （1）在计算机系统操作的每一个级别上，可见的对象和允许进行的操作各是什么？ （2）对于每一类资源，能够对其进行有效利用的最小操作集是什么？ （3）如何组织接口才能使得用户只需与抽象的资源而非硬件的物理细节打交道？ （4）作业调度、内存管理、通信、软件资源访问、并发任务间的通信以及可靠性与安全的控制策略是什么？（5）通过少数构造规则的重复使用进行系统功能扩展的原则是什么？
网络计算主领域的基本问题包括：（1）网络中的数据如何进行交换？（2）网络协议如何验证？（3）如何保证网络的安全？（4）分布式计算的性能如何评价？（5）分布式计算如何组织才能够使通过通信网连接在一起的自主计算机参加到一项计算中，而网络协议、主机地址、带宽和资源则具有透明性？
程序设计语言主领域的基本问题包括：（1）语言（数据类型、操作、控制结构、引进新类型和操作的机制）表示的虚拟机的可能组织结构是什么？（2）语言如何定义机器？机器如何定义语言？（3）什么样的表示法（语义）可以有效地用于描述计算机应该做什么？
人—机交互主领域的基本问题包括：（1）表示物体和自动产生供阅览的照片的有效方法是什么？（2）接受输入和给出输出的有效方法是什么？（3）怎样才能减小产生误解和由此产生的人为错误的风险？（4）图表和其他工具怎样才能通过存储在数据集中的信息去理解物理现象？
图形学和可视化计算主领域的基本问题包括：（1）如何选择支撑图像产生以及信息浏览的更好模型？（2）如何提取科学的（计算和医学）和更抽象的相关数据？（3）图像形成过程的解释和分析方法。
智能系统主领域的基本问题包括：（1）基本的行为模型是什么？如何建造模拟它们的机器？（2）规则评估、推理、演绎和模式计算在多大程度上描述了智能？（3）通过这些方法模拟行为的机器的最终性能如何？（4）传感数据如何编码才使得相似的模式有相似的代码？（5）电机编码如何与传感编码相关联？（6）学习系统的体系结构怎样？（7）这些系统是如何表示它们对这个世界的理解的？
信息系统主领域的基本问题包括：（1）使用什么样的建模概念来表示数据元素及其相互关系？（2）怎样把基本操作（如存储、定位、匹配和恢复）组合成有效的事务？（3）这些事务怎样才能与用户有效地进行交互？（4）高级查询如何翻译成高质量的程序？（5）哪种机器体系结构能够进行有效的恢复和更新？（6）怎样保护数据，以避免非授权访问、泄露和破坏？（7）如何保护大型的数据库，以避免由于同时更新引起的不一致性？（8）当数据分布在许多机器上时如何保护数据、保证性能？（9）文本如何索引和分类才能够进行有效的恢复？
软件工程主领域的基本问题包括：（1）程序和程序设计系统发展背后的原理是什么？（2）如何证明一个程序或系统满足其规格说明？（3）如何编写不忽略重要情况且能用于安全分析的规格说明？（4）软件系统是如何历经不同的各代进行演化的？（5）如何从可理解性和易修改性着手设计软件？
社会和职业问题主领域的基本问题包括：（1）计算学科本身的文化、社会、法律和道德的问题；（2）有关计算的社会影响问题，以及如何评价可能的一些答案的问题；（3）哲学问题；（4）技术问题以及美学问题。
科学计算主领域的基本问题包括：（1）如何精确地以有限的离散过程近似表示连续和无限的离散过程？（2）如何处理这种近似产生的错误？（3）给定某一类方程在某精确度水平上能以多快的速度求解？（4）如何实现方程的符号操作，如积分、微分以及到最小项的归约？（5）如何把这些问题的答案包含到一个有效的、可靠的、高质量的数学软件包中？
习题三
3.1 以“学生选课”为例，分析人们对客观世界的认识过程。
解：“学生选课”管理系统的研制过程蕴含了人们对客观世界从感性认识（通过E-R图，实现对例子的抽象）到理性认识（在关系数据理论的指导下，通过建立更为适合的关系模型而实现对例子的理性认识），再由理性认识回到实践（在实现对“例子”的感性认识和理性认识后，编写程序完成“学生选课”管理信息系统的工作）中来的科学思维方式。
3.2 请读者将所在班级若干学生（至少10人）以及他们选修课程的具体内容，根据以下关系模型进行填写。
学生（学号，姓名，年龄，性别）； 课程（课程号，课程名）；
学生选课（学号，课程号，成绩）；
7
解：
学生 课程 学号 96031101 96031102 96031103 96031104 96031105 96031106 96031107 96031108 96031109 960311010
学生选课 学号 96031101 96031101 96031104 96031104 96031106 96031106 96031106 96031108 96031109 960311010
3.3请读者将所在班级若干学生（至少10人）的具体内容，根据以下关系模型进行填写，并分析可能出现的问题。
学生（学号，姓名，年龄，性别，系名，系主任） 解： 学生 学号 96031101 96031102 96031103 96031104 96031105 96031106 96031107 96031108 96031109
该关系模式中出现了这样的传递函数依赖：学号（码）→系名，系名→系主任。因此，它不属于3NF。会出现插入异常、删除异常和冗余的问题。
3.4 什么是概念模型和关系模型？
8
姓名 黎明 李朋 张风 李红 王菲 周讯 刘德华 范冰冰 张艺谋 年龄 20 19 20 20 19 20 21 19 22 性别 男 男 男 女 女 女 男 女 男 系名 三院 三院 三院 三院 三院 三院 三院 三院 三院 系主任 黄廷磊 黄廷磊 黄廷磊 黄廷磊 黄廷磊 黄廷磊 黄廷磊 黄廷磊 黄廷磊 课程号 01 05 02 07 03 09 10 01 02 01 成绩 90 88 89 80 96 92 88 76 90 86 姓名 黎明 李朋 张风 李红 王菲 周讯 刘德华 范冰冰 张艺谋 巩丽 年龄 20 19 20 20 19 20 21 19 22 20 性别 男 男 男 女 女 女 男 女 男 女 课程号 01 02 03 04 05 06 07 08 09 10 课程名 计算机科学导论 高等数学 大学英语 离散数学 C语言 操作系统 汇编语言 编译原理 数据库系统概论 离散数学
解：概念模型用于信息世界的建模，是客观世界到信息世界的抽象。最常用的描述客观世界并建立概念模型的抽象方法是Ｅ-Ｒ方法（Entity-Relationship Approach），该方法也被称为实体－联系模型（或E-R图）。
关系模型支持的是一种二维表结构的数据模型，它由关系数据结构、关系数据操作和关系数据的完整性约束条件三部分组成。其中关系就是一张二维表。在关系模型中，客观世界的实体以及实体之间的各种联系均用关系来表示。 3.5简述计算学科中3个学科形态的主要内容。
解：计算学科中，按客观现象的研究过程，抽象形态包括以下4个步骤的内容：
（1）形成假设；
（2）建造模型并作出预测； （3）设计实验并收集数据； （4）对结果进行分析。
计算学科中，从统一合理的理论发展过程来看，理论形态包括以下4个步骤的内容： （1）表述研究对象的特征（定义和公理）；
（2）假设对象之间的基本性质和对象之间可能存在的关系（定理）； （3）确定这些关系是否为真（证明）； （4）结论。
计算学科中，从为解决某个问题而实现系统或装置的过程来看，设计形态包括以下4个步骤的内容： （1）需求分析； （2）建立规格说明； （3）设计并实现该系统； （4）对系统进行测试与分析。 3.6 什么是形式语言？试举例说明。
解：形式语言是进行形式化工作的元语言，它是以数学和数理逻辑为基础的科学语言。形式语言的基本特点有：
（1）有一组初始的、专门的符号集；
（2）有一组精确定义的，由初始的、专门的符号组成的符号串转换成另一个符号串的规则。在形式语言中，不允许出现根据形成规则无法确定的符号串。
比如：语言Z定义为：
初始符号集：{a，b，c，d，e，(，)，?，?，?，?}。形成规则：上述符号组成的有限符号串中，凡以符号“（”开头且以“）”结尾的符号串，为一公式，否则不是。
Z是一形式语言？
3.7 图灵机有什么特点？它的工作原理是什么？ 解：（1）图灵机的特点
① 图灵机由一条两端可无限延长的带子、一个读写头以及一组控制读写头工作的命令组成，如下图所示。图灵机的带子被划分为一系列均匀的方格。读写头可以沿带子方向左右移动，并可以在每个方格上进行读写。
? b b 1 0 1 0 0 0 1 0 b b b ? 读－写头 状态 ql 控制器 图灵机
② 写在带子上的符号为一个有穷字母表：{S0，S1，S2，?，Sp}。通常，可以认为这个有穷字母表仅有S0、S1两个字符，其中S0可以看作是“0”，S1可以看作是“1”，它们只是两个符号。
③ 机器的控制状态表为：{q1，q2，?，qm}。通常，将一个图灵机的初始状态设为q1，在每一个具体的图灵机中还要确定一个结束状态qw。
一个给定机器的“程序”认为是机器内的五元组（qiSjSkR（或L或N）ql）形式的指令集，五元组定义了机器在一个特定状态下读入
9
一个特定字符时所采取的动作。5个元素的含义如下：
qi表示机器目前所处的状态； Sj表示机器从方格中读入的符号；
Sk表示机器用来代替Sj写入方格中的符号；
R、L、N分别表示向右移一格、向左移一格、不移动； ql表示下一步机器的状态。 （2）图灵机的工作原理
机器从给定带子上的某起始点出发，其动作完全由其初始状态及机内五元组来决定。就某种意义而言，一个机器其实就是它作用于纸带上的五元组集。
3.8 计算题：在图灵的带子机中，设b表示空格，q1表示机器的初始状态，q4表示机器的结束状态，如果带子上的输入信息是11100101，读入头对准最右边第一个为1的方格，状态为初始状态q1。请写出执行以下命令后的计算结果。
q1 0 0 L q2 q1 1 0 L q3 q1 b b N q4 q2 0 0 L q2 q2 1 0 L q2 q2 b b N q4 q3 0 0 L q2 q3 1 0 L q3 q3 b b N q4
解：计算结果为00000000或0。（考试时需要写出步骤，标准见67页书籍） 3.9 简述冯·诺伊曼型计算机的体系结构及其特点。
解：冯·诺依曼计算机（单指令顺序存储程序式计算机）的体系结构由存储器、控制器、运算器、输入和输出设备等五个基本部件组成的，如图所示：
输入 设备 中央处理器 输出 设备 控制器 □□□?□□ 寄存器 主存储器 算术逻辑部件 辅助 存储 设备
冯·诺依曼计算机的体系结构
冯·诺依曼计算机的体系结构，也即存储程序式计算机的体系结构的特点，是将程序与数据一样看待，对程序像数据那样进行适当的编码，然后与数据一起共同存放在存储器中。这样，计算机就可以通过改变存储器中的内容，对数据进行操作。从原来对程序和数据的严格区别到一样看待，这个观念上的转变是计算机史上的一场革命，它反映的正是计算的本质，即符号串的变化。 3.10 为什么说，从原来对程序和数据的严格区别到后来的一样看待，这个观念上的转变是计算机史上的一场革命。
解：它反映的正是计算的本质，即符号串的变化。所以说从原来对程序和数据的严格区别到后来的一样看待，这个观念上的转变是计算机史上的一场革命。
3.11根据计算机输入设备和输出设备的定义，硬盘属于输入设备，还是输出设备？或者，既属于输入设备，又属于输出设备？ 解：输入和输出设备是人与计算机进行交互的两大部件，一类是将信息输入计算机；一类是将信息输出计算机。 硬盘既属于输入设备，又属于输出设备。
10