2007年10月12日 8:35:57
9、Our problem is to devise a program that can remember sufficient information about the pairs it has seen to be able to decide whether or not a new pair of objects is connected. Informally, we refer to the task of designing such a method as the connectivity problem. This problem arises in a number of important applications.
我们要设计一个程序，它能够知道足够的配对信息，以便决定新的配对能否是联通的。非正式地，我们把设计这样的方法称为联通问题。这个问题出现在很多重要的应用中。
（看起来没什么复杂的算法，是因为规模小，10个配对用人脑就能算出来。it possible for a human to do。可是在大型应用中就不能，internet有多少的网络节点？需要计算机集群了吧！）
第一个例子：在网络应用中（路由算法可能就是干这个的）
For example, the integers might represent computers in a large network, and the pairs might represent connections in the network. Then, our program might be used to determine whether we need to establish a new direct connection for p and q to be able to communicate or whether we could use existing connections to set up a communications path.
第二个例子：电网（在不架设额外的电缆的基础上，如何使所有的节点连接。电缆就是money啊！好的算法可以节省money。）
Similarly, the integers might represent contact points in an electrical network, and the pairs might represent wires connecting the points. In this case, we could use our program to find a way to connect all the points without any extraneous connections, if that is possible.
10、We are asking for a program that does a specific and well-defined task. There are many other related problems that we might want to have solved as well.
For example, our connectivity-problem specification requires only that our program somehow know whether or not any given pair p-q is connected, and not that it be able to demonstrate any or all ways to connect that pair. Adding a requirement for such a specification makes the problem more difficult and would lead us to a different family of algorithms
我们需要一个具体的、定义好的任务，但是也有很多其他的，与我们要解决的问题相关的问题。
例如：上述的联通问题，只要求知道两个节点（一对）是否可以彼此相连，并没有涉及到要我们描述任何一条或者所有联通的路径。增加需求，会使问题变得更困难，也许会引导我们走向不同类型的算法。
（把大象装进冰箱，似乎是三个步骤的很简单的算法。可是大象太大了需要切割开来，分块装进冰箱，算法完全变了。算法变成了法律，大象是不能随便屠宰的，要爱护动物，不是吗？虽然它不是小动物，也不可爱。）
11、有一段很难翻译，我理解了大概意思：需求说明要求做什么，算法相应地设计。不要把问题搞复杂了，满足要求就行了。复杂的要求对应着复杂的算法，不仅难以设计，而且效率也不高的，何苦呢？所以，可以看出理解需求的重要性，算法是需求的产物。
12、Organizing our algorithms in terms of these abstract operations does not seem to foreclose any options in solving the connectivity problem, and the operations may be useful for solving other problems.
用抽象操作术语组织算法，并不意味着不能解决联通问题了。这种做法能使算法更加通用，解决其他的问题。
（很多语言支持泛型了，如c++。java从1.5开始也支持泛型了吧。实际上泛型就是这种思想，拋去具体的操作对象，专注于算法描述。典型的把不变和变化的东西分开的思想。）
（学东西要先学变化很小的原理，在明白原理的基础上可以赶时髦，学新技术，那学习速度很快。上来就赶时髦，学什么IDE，还有成堆的新技术，会累死你，也学不好。将来很可能称为软件蓝领吧。纯属本人自励，没有恶意^_^）
13、Exercises练习题
1.1 Give the output that a connectivity algorithm should produce when given the input 0-2, 1-4, 2-5, 3-6, 0-4, 6-0, and 1-3.
我的答案：
0-2 0-2
1-4 1-4
2-5 2-5
3-6 3-6
0-4 0-4
6-0 6-0
1-3 3-6-0-4-1
1.2 List all the different ways to connect two different objects for the example in Figure 1.1.
我的答案：
3-4
4-9
8-0
2-3
5-6
2-9 2-3-4-9 9-4-3-2
5-9
7-3
4-8
5-6
0-2 0-8-4-3-2 2-9-4-8-0
1.3 Describe a simple method for counting the number of sets remaining after using the union and find operations to solve the connectivity problem as described in the text.
不懂
14、The first step in the process of developing an efficient algorithm to solve a given problem is to implement a simple algorithm that solves the problem. If we need to solve a few particular problem instances that turn out to be easy, then the simple implementation may finish the job for us. If a more sophisticated algorithm is called for, then the simple implementation provides us with a correctness check for small cases and a baseline for evaluating performance characteristics. We always care about efficiency, but our primary concern in developing the first program that we write to solve a problem is to make sure that the program is a correct solution to the problem.
针对一个问题开发一个高效的算法，第一步就是要实现一个简单的解决问题的算法。如果我们要解决的问题很简单，那么简单的实现就能完成我们的工作。如果需要更加精密的算法，那么简单的算法能够提供给我们一个验证正确性的方案，并且也为估算算法的性能提供了基准。我们总是很关注高效，但是在开发中我们的最最关心的首要问题是这种解决问题的方式是否正确。
（这里讲到简单算法的意义。一个简单的算法，很容易被验证是正确的。比如数钱，虽然有高效的验钞机，但是我们往往会亲手再数一遍，这样心里才踏实。动手数钱的效率虽然低，但是正确可能会高点。万一多给人家100元不久亏大了吗！这种思想是先解决问题，有一套比较简单的解决方案，谨慎地进行优化。）
