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.
我們要設(shè)計(jì)一個程序，它能夠知道足夠的配對信息，以便決定新的配對能否是聯(lián)通的。非正式地，我們把設(shè)計(jì)這樣的方法稱為聯(lián)通問題。這個問題出現(xiàn)在很多重要的應(yīng)用中。
（看起來沒什么復(fù)雜的算法，是因?yàn)橐?guī)模小，10個配對用人腦就能算出來。it possible for a human to do。可是在大型應(yīng)用中就不能，internet有多少的網(wǎng)絡(luò)節(jié)點(diǎn)？需要計(jì)算機(jī)集群了吧！）
第一個例子：在網(wǎng)絡(luò)應(yīng)用中（路由算法可能就是干這個的）
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.
第二個例子：電網(wǎng)（在不架設(shè)額外的電纜的基礎(chǔ)上，如何使所有的節(jié)點(diǎn)連接。電纜就是money啊！好的算法可以節(jié)省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
我們需要一個具體的、定義好的任務(wù)，但是也有很多其他的，與我們要解決的問題相關(guān)的問題。
例如：上述的聯(lián)通問題，只要求知道兩個節(jié)點(diǎn)（一對）是否可以彼此相連，并沒有涉及到要我們描述任何一條或者所有聯(lián)通的路徑。增加需求，會使問題變得更困難，也許會引導(dǎo)我們走向不同類型的算法。
（把大象裝進(jìn)冰箱，似乎是三個步驟的很簡單的算法。可是大象太大了需要切割開來，分塊裝進(jìn)冰箱，算法完全變了。算法變成了法律，大象是不能隨便屠宰的，要愛護(hù)動物，不是嗎？雖然它不是小動物，也不可愛。）
11、有一段很難翻譯，我理解了大概意思：需求說明要求做什么，算法相應(yīng)地設(shè)計(jì)。不要把問題搞復(fù)雜了，滿足要求就行了。復(fù)雜的要求對應(yīng)著復(fù)雜的算法，不僅難以設(shè)計(jì)，而且效率也不高的，何苦呢？所以，可以看出理解需求的重要性，算法是需求的產(chǎn)物。
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.
用抽象操作術(shù)語組織算法，并不意味著不能解決聯(lián)通問題了。這種做法能使算法更加通用，解決其他的問題。
（很多語言支持泛型了，如c++。java從1.5開始也支持泛型了吧。實(shí)際上泛型就是這種思想，拋去具體的操作對象，專注于算法描述。典型的把不變和變化的東西分開的思想。）
（學(xué)東西要先學(xué)變化很小的原理，在明白原理的基礎(chǔ)上可以趕時(shí)髦，學(xué)新技術(shù)，那學(xué)習(xí)速度很快。上來就趕時(shí)髦，學(xué)什么IDE，還有成堆的新技術(shù)，會累死你，也學(xué)不好。將來很可能稱為軟件藍(lán)領(lǐng)吧。純屬本人自勵，沒有惡意^_^）
13、Exercises練習(xí)題
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.
針對一個問題開發(fā)一個高效的算法，第一步就是要實(shí)現(xiàn)一個簡單的解決問題的算法。如果我們要解決的問題很簡單，那么簡單的實(shí)現(xiàn)就能完成我們的工作。如果需要更加精密的算法，那么簡單的算法能夠提供給我們一個驗(yàn)證正確性的方案，并且也為估算算法的性能提供了基準(zhǔn)。我們總是很關(guān)注高效，但是在開發(fā)中我們的最最關(guān)心的首要問題是這種解決問題的方式是否正確。
（這里講到簡單算法的意義。一個簡單的算法，很容易被驗(yàn)證是正確的。比如數(shù)錢，雖然有高效的驗(yàn)鈔機(jī)，但是我們往往會親手再數(shù)一遍，這樣心里才踏實(shí)。動手?jǐn)?shù)錢的效率雖然低，但是正確可能會高點(diǎn)。萬一多給人家100元不久虧大了嗎！這種思想是先解決問題，有一套比較簡單的解決方案，謹(jǐn)慎地進(jìn)行優(yōu)化。）
