计算机科学与导论-思想与方法习题答案
习题一
1.1 简述计算学科的定义及其根本问题。
答：计算学科是对描述和变换信息的算法过程进行的系统研究，包括理论、分析、设计、效率、实现和应用等。 学科的根本问题是：什么能被（有效地）自动进行。 1.2 简述计算学科专业名称的演变。
答：计算学科专业名称主要包括：计算机科学、信息系统、软件工程、计算机工程、和信息技术。
1962年，美国普渡大学开设了最早的“计算机科学”学位课程。当时，在美国的一些高校还开设有与计算相关的两给学位课程：电子工程和信息系统。而在我国，早在1956年，就开设了“计算装置与仪器”专业。
20世纪70年代，在美国，“计算机工程”（也被称为“计算机系统工程”）从电子工程学科中脱离出来，成为一个独立的二级学科，并被人们所接受。
随着软件规模及其复杂度的增加，制造可靠软件的困难越来越大，出现了所谓的软件危机；针对这种情况，1968年秋，北大西洋公约组织（NATO）在当时的联邦德国召开了一次会议，提出了软件工程的概念。20世纪70年代未、80年代初，在一些计算机科学专业的学位课程中，引入了软件工程的内容，然而，这些内容，只能让学生了解软件工程，却不能使学生明白如何成为一名软件工程师。于是，人们开始构建单独的软件工程学位课程。20世纪80年代，英国和澳大利亚，最早开设了“软件工程”这样的学位课程。
20世纪90年代，计算机已成为公司各级人员使用的基本工具，而计算机网络则成为公司信息的中枢，人们相信它有助于提高生产力，而原有的学术学位课程并不能满足社会的需求，于是，在美国等西方国家，不少大学相继开设了“信息系统”、“信息技术”等学位课程。
至此，需要指出的是，即使在美国，5个分支学科（专业）同时在一所大学开设的情况也是不多的，更多的高校仍然是以传统的“计算机科学”为主；在我国，则是以“计算机科学与技术”为主。 1.3 简述计算学科主要专业培养的不同。
答：对计算学科五个主要专业的培养侧重点简述如下。
（1）计算机科学，涉及很宽的范围，包括了计算的理论、算法和实现，以及机器人技术、计算机视觉、智能系统、生物信息学和其他新兴的有前途的领域。
计算机科学是计算各学科的基础，计算机科学专业培养的学生，更关注计算的理论基础和算法，并能从事软件开发及其相关的理论研究。
（2）计算机工程，是对现代计算系统和由计算机控制的有关设备上的软件与硬件的设计、构造、实施和维护进行研究的学科。 计算机工程专业培养的学生，更关注设计并实施集软件和硬件设备为一体的系统，如嵌入式系统。
（3）软件工程，是指以系统、学科、定量的方法，把工程应用于软件的开发、运行和维护；同时，展开对上述过程中各种方法和途径进行研究的学科。
软件工程专业培养的学生，更关注以工程规范进行的大规模软件系统开发与维护的原则，并尽可能避免软件系统潜在的风险。 （4）信息系统，是指如何将信息技术的方法与企业生产和商业流通结合起来，以满足这些行业需求的学科。
信息系统培养的学生，更关注信息资源的获取、部署、管理及使用，并能分析信息的需求和相关的商业过程，能详细描述并设计那些与目标相一致的系统。
（5）信息技术，从广义上来说，它包括了所有计算技术的各个方面，在此专指作为一门学科的信息技术。它侧重在一定组织及社会环境下，通过选择、创造、应用、集成和管理的计算技术来满足用户的需求。
与信息系统相比，信息技术更关注于“信息技术”的技术层面，而信息系统则重于“信息技术”的“信息”层面。
信息技术专业培养的学生，更关注基于计算机的新产品及其正常的运行和维护，并能使用相关的信息技术来计划、实施和配置计算机系统。
1.4 学科知识体由哪三个层次组成？
答：学科知识体依次由分枝领域、知识单元、以及知识点三个层次组成。
最高层是分支领域，它代表一个特定的学科子领域；例如，“计算机科学”知识体由DS（离散结构）、PF（程序设计基础）、AL（算法和复杂性）、AR（体系结构和组织）、OS（操作系统）、NC（网络计算）、PL（程序设计语言）、HC（人机交互）、GV（图形学和可视化计算）、IS（智能系统）、IM（信息管理）、SP（社会与职业问题）、SE（软件工程）、CN（计算科学和数值计算方法）等14个分枝领域组成。
分支领域之下又分为更小的知识单元，它代表该领域中的主题模块；例如，在计算机科学知识体中，分枝领域“DS（离散结构）”又由DS1（函数、关系、集合）、DS2（基本逻辑）、DS3（证明方法）、DS4（计算基础）、DS5（图和树）、DS6（离散概率）等6个知识单元组成。
知识单元又被细分为众多的知识点，这些知识点构成了知识体结构的最底层。例如，在上述例子中，知识单元“DS1（函数、关系、
1
集合）”又有函数 (满射，到内的映射，逆函数，复合函数)、关系 (自反，对称，传递，等价关系)、集合 (文氏图, 补集，笛卡尔积，幂集)、鸽笼原理、基数性和可数性等知识点组成。
1.5 分别列出计算机科学、计算机工程、软件工程和信息技术四个专业的核心课程。
答：计算机科学专业的核心课程包括：计算机导论、程序设计基础、离散结构、算法与数据结构、计算机组成基础、计算机体系结构、操作系统、数据库系统原理、编译原理、软件工程、计算机图形学、计算机网络、人工智能、数字逻辑、社会与职业道德。
计算机工程专业的核心课程包括：计算机导论、程序设计基础、离散结构、算法与数据结构、电路与系统、模拟与数字电子技术、数字信息处理、数字逻辑、计算机组成结构、计算机体系结构、操作系统、计算机网络、嵌入式系统、软件工程、数据库系统原理、社会与职业道德。
软件工程专业的核心课程包括：程序设计基础、面向对象方法学、数据结构和算法、离散结构、计算机体系结构、操作系统和网络、数据库、工程经济学、团队激励和沟通、软件工程职业实践、软件工程与计算、软件工程导论、软件代码开发技术、人机交互的软件工程方法、大型软件系统设计与软件体系结构、软件测试、软件设计与体系结构、软件详细设计、软件工程的形式化方法、软件质量保证与测试、软件需求分析、软件项目管理、软件过程与管理、软件工程综合实习（含毕业设计）。
信息技术四个专业的核心课程包括：信息技术导论、信息技术应用数学入门、程序设计与问题求解、数据结构与算法、计算机系统平台、应用集成原理与工具、Web系统与技术、计算机网络与互联网、数据库与信息管理技术、人机交互、面向对象方法、信息保障与安全、社会信息学、信息系统工程与实践、系统管理与维护。 1.6 为什么说“计算机导论”课程的构建是一个重大问题？
答：计算已成为一个庞大的学科，它涉及了数学、科学、工程和商业等领域，并包括了专业实践所需要的大量基础知识。学科知识体，以及核心知识单元等内容的给出，为学科专业教学计划的制定奠定了基础。然而，由于知识单元，特别是知识点的大量罗列，也为计算学科的教学带来了挑战。要解决计算学科内容大量罗列而产生的问题，就不得不先解决计算教育面临的另一个重要问题，即“计算机导论”课程的构建问题。
1.7 简述“计算机导论”课程构建的关键及要实现的目标。
答：“计算作为一门学科”报告认为，“计算机导论”课程要培养学生面向学科的思维能力，使学生领会学科的力量，以及从事本学科工作的价值之所在。报告希望该课程能用类似于数学那样严密的方式将学生引入到计算学科各个富有挑战性的领域之中。
CC2001报告认为，不管怎样设计，“计算机导论”这门课都应该讲授学科中那些富有智慧的核心思想。CC2004和CC2005则进一步指出，该课程的关键是课程的结构设计问题，现有的浓缩版结构显然不是一种好的课程结构，期待人们在该课程的结构设计上有所突破。 1.8 简介计算学科二维定义矩阵的概念。
答：“计算作为一门学科”报告给出了计算学科二维定义矩阵的概念，为我们认知学科提供了一个模型。计算学科二维定义矩阵是对学科一个高度的概括；其横向维由抽象、理论、设计等3个过程组成，纵向维由离散结构（DS）、程序设计基础（PF）、算法与复杂性（AL）、体系结构（AR）、操作系统（OS）、网络计算（NC）、程序设计语言（PL）、人机交互（HC）、图形学和可视化计算（GV）、智能系统（IS）、信息管理（IM）、软件工程（SE）、社会与职业问题（SP）、科学计算（CN）等14个学科知识领域组成。
在该定义矩阵中，不变的是3个过程（也称为3个学科形态）；变化的是3个过程的具体内容（值），这一维的取名可以是学科知识领域（或学科主领域），也可以为分支学科等。
1.9 本书是如何对“计算机导论”课程结构进行设计的？
答：本书将计算学科的认知问题具体为计算学科二维定义矩阵的认知问题，从而使计算学科的认知具体化。认知学科终究是通过概念来完成的，而学科中所有的概念都蕴含在定义矩阵中。于是，可以从定义矩阵出发介绍学科，并在学科思想、方法这个较高的层面讲授“计算机导论”课程，为学生后续专业课程的学习提供必要的认知基础。因此，本书将焦点放在定义矩阵，将把握学科的本质问题归约为把握定义矩阵的本质问题，即对定义矩阵的“横向”和“纵向”关系的把握。
“横向”关系，即抽象、理论和设计3个过程的关系，是定义矩阵中最为重要的内容。它反映的是，人们在计算领域的认识规律，即是从感性认识（抽象）到理性认识（理论），再由理性认识（理论）回到实践（设计）的过程。“横向”关系还蕴含着学科中的基本问题。由于人们对客观世界的认识过程就是一个不断提出问题和解决问题的过程，这种过程反映的正是抽象、理论和设计3个过程之间的相互作用，它与3个过程在本质上是一致的。因此，在“计算机导论”课程的设计上，有必要将它与3个过程一起列入最重要的内容。
“纵向”关系，即各分支领域中具有共性的核心概念、数学方法、系统科学方法、社会与职业问题等内容的关系。这些内容蕴含在学科3个过程中，并将学科各分支领域结合成一个完整的体系，而不是互不相关的领域。
显然，在定义矩阵中，“横向”关系最重要，“纵向”关系次之。因此，在“计算机导论”课程的设计上，可以将本章列为第一章，而将学科的基本问题，抽象、理论和设计3个过程，学科中的核心概念，数学方法，系统科学方法，以及社会与职业问题分别列为第二至第七章。
沿着定义矩阵这个关于学科概念的认知模型进行导引，优点在于，对学科进行总结的系统性。这种总结是回顾性的总结，不足在于，对学科有争论的问题以及未来探索性的展望作用有限。为此，有必要构建最后一章，即“探讨与展望”。
2
1.10 阅读前言，简述计算教育面临的三个重大问题，了解三个重大问题产生的背景。
答：计算学科的“存在性”证明问题、计算学科核心课程的设置问题、以及“计算机导论”课程的构建问题是计算教育面临的三个重大问题。
1989年，ACM攻关组提交了“计算作为一门学科”报告，明确指出了计算教育面临的上述三个重大问题。“计算作为一门学科”报告解决了计算教育面临的第一个重大问题，即学科的“存在性”证明问题。经过十多年的发展，计算学科已经成为大学最活跃的学科；计算教育是否列入学科的争论已经不存在了，现在的问题是如何找到一种方法来满足这种需求。
CC1991报告与“计算作为一门学科”报告一脉相承，由于没有给出学科核心课程的详细内容，最终没有获得预期的效果。CC2001接受了CC1991的教训，给出了计算机科学（CS）核心课程的详细设计，为CE2004、SE2004、IT2005等报告的制定提供了模式。现在，计算学科有了非常详细的专业核心课程。然而，学科内容的庞杂，给计算学科的教学带来了困难。要解决计算学科内容庞杂的问题，就不得不解决“计算机导论”课程的构建问题。
“计算作为一门学科”报告希望“计算机导论”课程能用类似于数学那样严密的方式将学生引入计算学科各个富有挑战性的领域之中。CC2001报告介绍了该课程的构建问题，并希望这门课讲授学科中那些富有智慧的核心思想。CC2004和CC2005则进一步指出，该课程的关键是课程的结构设计问题，现有的浓缩版结构显然不是一种好的课程结构，报告期待人们在该课程的结构设计上有所突破。
习题二
2.1 为什么说科学研究是从问题开始的？
答：科学研究从问题开始，或者说科学始于问题而非观察；尽管通过观察可以引出问题，但在观察时必定带有问题，带有预期的设想，漫无目的的观察是不存在的。
2.2 欧拉是如何对“哥尼斯堡七桥问题”进行抽象的？
答：为了解决哥德斯堡七桥问题，欧拉用4个点代表4个城区，用关于这4个点的7条线表示4个城区之间的7座桥，从而得到一个含有4个点和7条线的无向图。这样做是基于该问题本质考虑的，它抽象出问题最本质的东西，忽视问题非本质的东西（如桥的长度、宽度等）。最终将哥尼斯堡七桥问题抽象为一个数学问题，即经过图中每边一次且仅一次的回路问题。欧拉在论文中论证了这样的回路是不存在的，后来，人们把有这样回路的图称为欧拉图。
2.3 简述“欧拉回路”与“哈密尔顿回路”的区别。
答：“哈密尔顿回路问题”是访问除原出发结点以外的每个结点一次且仅一次并回到出发点，而“欧拉回路问题”是访问每条边一次且仅一次并回到出发点。对任一给定的图是否存在“欧拉回路”前面已给出充分必要条件，而对任一给定的图是否存在“哈密尔顿回路”至今仍未找到满足该问题的充分必要条件。
2.4 判断下列图中，哪个存在欧拉路径，哪个存在欧拉回路。
答：a、b、c、d都存在欧拉路径，a存在欧拉回路。
2.5 判断下列图中，哪个存在哈密尔顿回路
3
答：b存在哈密尔顿回路。
2.6赛纳河流经巴黎的这一段河中有两个岛，河岸与岛间架设了15座桥。如下图所示。问：（l）能否从某地出发，经过这15座桥各一次
后再回到出发点？
（2）若不要求回到出发点，能否在一次散步中，穿过所有的桥各一次？若可以，请把路径写出。
cAB东 区D
答：（1）不能
（2）可以，从C或D出发都能找到这样的路径。例如：C－A－C－A－C－B－C－B－A－D－A－D－A－D－B－D
2.7 以“梵天塔问题”为例，说明理论上可行的计算问题实际上并不一定能行。
答：对于许多问题，我们可以找到相应的算法，从而证明该问题在理论上是可计算的。例如，对于“梵天塔问题”，可以基于递归方法给出相应的求解算法。但是，由于该问题的复杂度过高，又使得实际上是不可行的。例如，对于“梵天塔问题”， 当盘子个数为64时，需要移动盘子的次数为264-1=18446744073709551615，如果每秒移动一次，也需要花费大约5849亿年的时间；假定计算机以每秒1000万个盘子的速度进行搬迁，则需要花费大约58490年的时间。 2.8什么是顺序程序？什么是并行程序？
答：略。
2.9 什么是NP类问题？请举例说明。
答：在计算复杂性理论中，将所有可以在多项式时间内求解的问题称为P类问题，而将所有在多项式时间内可以验证的问题称为NP类问题。例如“证比求易算法”。 2.10 简述阿姆达尔定律。
答：设f为求解某个问题的计算存在的必须串行执行的操作占整个计算的百分比，p为处理器的数目，Sp为并行计算机系统最大的加速能力（单位：倍），则
≤
Sp?11?ff?p
设f=1%，p→?，则Sp=100。这说明在并行计算机系统中即使有无穷多个处理器，若串行执行操作占全部操作的1%，则其解题速度
4
与单处理器的计算机相比最多也只能提高100倍。因此，对难解性问题而言，单纯地提高计算机系统的速度是远远不够的，而降低算法复杂度的数量级才是最关键的问题。
2.11* 对于本质上可以进行并行计算的特定问题（如Google的搜索引擎，其计算本质上是并行的，该引擎可以在不同的处理器上运行不同的查询），阿姆达尔定律对这类问题适用吗？
答：适用。 2.12 简述停机问题。
答：停机问题是指：针对任意给定的图灵机和输入，寻找一个一般的算法（或图灵机），用于判定给定的图灵机在接收了初始输入后，能否到达终止状态，即停机状态。若能找到这样的算法，我们说停机问题可解，否则，不可解。换句话讲说，就是我们能不能找到这样一个测试程序，它能判断出任意的程序在接收了某个输入并执行后，能不能终止。若能，则停机问题可解，否则，不可解。 2.13 简述找零问题、背包问题与贪婪算法。
答：设有不同面值的钞票，要求用最小数量的钞票给顾客找某数额的零钱，这就是通常说的找零问题。
给定n种物品和一个背包，设Wi为物品i的重量，Vi为其价值，C为背包的重量容量，要求在重量容量的限制下，尽可能使装入的物品总价最大，这就是背包问题。
贪婪算法是一种传统的启发式算法，它采用逐步构造最优解的方法，即在算法的每个阶段，都作出在当时看上去最好的决策，以获得最大的“好处”，换言之，就是在每一个决策过程中都要尽可能的“贪”， 直到算法中的某一步不能继续前进时，算法才停止。在算法的过程中，“贪”的决策一旦作出，就不可再更改，作出“贪”的决策的依据称为贪婪准则。贪婪算法是从局部的最优考虑问题的解决方案，具有简单快捷的优点。但是，这种从局部，而不是从整体最优上考虑问题的算法，并不能保证求得的最后解为最优解。 2.14 简述“两军问题”。
答：两军问题可以这样描述：一支白军被围困在一个山谷中，山谷的两侧是蓝军。困在山谷中的白军人数多于山谷两侧的任一支蓝军，而少于两支蓝军的总和。若一支蓝军对白军单独发起进攻，则必败无疑；但若两支蓝军同时发起进攻，则可取胜。两支蓝军希望同时发起进攻，这样他们就要传递信息，以确定发起攻击的具体时间。假设他们只能派谴士兵穿越白军所在的山谷（惟一的通信信道）来传递信息，那么在穿越山谷时，士兵有可能被俘，从而造成消息的丢失。现在的问题是：如何通信，以便蓝军必胜。 2.15 简述互联网软件的分层结构。
答：Internet软件有四个层次（图2.11），即应用层，传输层，网络层和链路层，每层均有相应的协议进行支撑，每台Internet上的机器都具有这样的软件及层次结构。一条信息在应用层产生，向下通过传输层和网络层的处理，然后通过链路层被传递。这个信息由目的地的链路层接收，通过网络层和传输层的逆操作，最后将信息送到应用层。
2.16 “生产者－消费者问题”和“哲学家共餐问题”反映的是计算学科中的什么问题？
答：反映了计算学科中的进程同步问题。 2.17 用图表示程序的3种基本结构。
答：
A T P F A B P F T A B (a) 顺序结构 (b) 选择结构 (c) 循环结构
2.18 “GOTO语句问题”的提出直接导致了计算学科哪一个分支领域的产生？
答：关于“GOTO语句”问题的争论直接导致了一个新的学科分支领域，即程序设计方法学的产生。 2.19 “图灵测试”和“中文屋子”是如何从哲学的角度反映人工智能本质特征的？
答：“图灵测试”不要求接受测试的思维机器在内部构造上与人脑一样，它只是从功能的角度来判定机器是否能思维，也就是从行为主义这个角度来对“机器思维”进行定义。尽管图灵对“机器思维”的定义是不够严谨的，但他关于“机器思维”定义的开创性工作对后人的研究具有重要意义，因此，一些学者认为，图灵发表的关于“图灵测试”的论文标志着现代机器思维问题讨论的开始。
西尔勒借用语言学的术语非常形象地揭示了“中文屋子”的深刻寓意：形式化的计算机仅有语法，没有语义。因此，他认为，机器永远也不可能代替人脑。作为以研究语言哲学问题而著称的分析哲学家西尔勒来自语言学的思考，的确给人工智能涉及的哲学和心理学问题
5