HW2-计算机科学与导论-思想与方法.doc

2.1 为什么说科学研究是从问题开始的？ 答：科学研究从问题开始，或者说科学始于问题而非观察；尽管通过观察可以引出问题，但在观察时必定带有问题，带有预期的设想，漫无目的的观察是不存在的。 2.2 欧拉是如何对“哥尼斯堡七桥问题”进行抽象的？ 答：为了解决哥德斯堡七桥问题，欧拉用4个点代表4个城区，用关于这4个点的7条线表示4个城区之间的7座桥，从而得到一个含有4个点和7条线的无向图。这样做是基于该问题本质考虑的，它抽象出问题最本质的东西，忽视问题非本质的东西（如桥的长度、宽度等）。最终将哥尼斯堡七桥问题抽象为一个数学问题，即经过图中每边一次且仅一次的回路问题。欧拉在论文中论证了这样的回路是不存在的，后来，人们把有这样回路的图称为欧拉图。 2.3 简述“欧拉回路”与“哈密尔顿回路”的区别。 答：“哈密尔顿回路问题”是访问除原出发结点以外的每个结点一次且仅一次并回到出发点，而“欧拉回路问题”是访问每条边一次且仅一次并回到出发点。对任一给定的图是否存在“欧拉回路”前面已给出充分必要条件，而对任一给定的图是否存在“哈密尔顿回路”至今仍未找到满足该问题的充分必要条件。 2.4 判断下列图中，哪个存在欧拉路径，哪个存在欧拉回路。 答：a、b、c、d都存在欧拉路径，a存在欧拉回路。 2.5 判断下列图中，哪个存在哈密尔顿回路 答：b存在哈密尔顿回路。 2.6赛纳河流经巴黎的这一段河中有两个岛，河岸与岛间架设了15座桥。如下图所示。问：（l）能否从某地出发，经过这15座桥各一次后再回到出发点？ （2）若不要求回到出发点，能否在一次散步中，穿过所有的桥各一次？若可以，请把路径写出。 答：（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为并行计算机系统最大的加速能力（单位：倍），则 设f=1%，p→(，则Sp=100。这说明在并行计算机系统中即使有无穷多个处理器，若串行执行操作占全部操作的1%，则其解题速度与单处理器的计算机相比最多也只能提高100倍。因此，对难解性问题而言，单纯地提高计算机系统的速度是远远不够的，而降低算法复杂度的数量级才是最关键的问题。 2.11* 对于本质上可以进行并行计算的特定问题（如Google的有哪些信誉好的足球投注网站引擎，其计算本质上是并行的，该引擎可以在不同的处理器上运行不同的查询），阿姆达尔定律对这类问题适用吗？ 答：适用。 2.12 简述停机问题。 答：停机问题是指：针对任意给定的图灵机和输入，寻找一个一般的算法（或图灵机），用于判定给定的图灵机在接收了初始输入后，能否到达终止状态，即停机状态。若能找到这样的算法，我们说停机问题可解，否则，不可解。换句话讲说，就是我们能不能找到这样一个测试程序，它能判断出任意的程序在接收了某个输入并执行后，能不能终止。若能，则停机问题可解，否则，不可解。 2.13 简述找零问题、背包问题与贪婪算法。 答：设有不同面值的钞票，要求用最小数量的钞票给顾客找某数额的零钱，这就是通常说的找零问题。 给定n种物品和一个背包，设Wi为物品i的重量，Vi为其价值，C为背包的重量容量，要求在重量容量的限制下，尽可能使装入的物品总价最大，这就是背包问题。 贪婪算法是一种传统的启发式算法，它采用逐步构造最优解的方法，即在算法的每个阶段，都作出在当时看上去最好的决策，以获得最大的“好处”，换言之，就是在每一个决策过程中都要尽可能的“贪”， 直到算法中的某一步不能继续前进时，算法才停止。在算法的过程中，“贪”的决策一旦作出，就不可再更改，作出“贪”的决策的依据称为贪婪准则。贪婪算法是从局部的最优考虑问题的解决方案，具有简单快捷的优点。但是，这种从局部，而不是从