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有多少的網絡節點？需要計算機集群了吧?。?br />
第一個例子：在網絡應用中（路由算法可能就是干這個的）
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元不久虧大了嗎！這種思想是先解決問題，有一套比較簡單的解決方案，謹慎地進行優化。）
