# 演算法

## 定義

### 非正式定義

 「 原版英文："No human being can write fast enough, or long enough, or small enough† ( †"smaller and smaller without limit ...you'd be trying to write on molecules, on atoms, on electrons") to list all members of an enumerably infinite set by writing out their names, one after another, in some notation. But humans can do something equally useful, in the case of certain enumerably infinite sets: They can give explicit instructions for determining the nth member of the set, for arbitrary finite n. Such instructions are to be given quite explicitly, in a form in which they could be followed by a computing machine, or by a human who is capable of carrying out only very elementary operations on symbols." 粵文翻譯：冇一個人類寫得夠快夠長夠細粒，能夠將一個「列舉到嘅無限集」（Emumerably infinite set）包含嘅物件用某啲符號寫嗮出來。但係對住某啲列舉到嘅無限集，人類曉做一啲同等有用嘅嘢（註：指演算法）：佢哋識得俾一啲指示出來去揾出個集所包含嘅第 n 件物件，當中 n 可以係是旦一個細過無限大嘅整數。呢啲指示都要幾明確至得，要有一個形式，令到曉計數嘅機器（例如係電腦）或者一個淨係曉用符號嘅人類能夠跟從佢哋。 」

## 參考書

• Berlinski, David (2001). The Advent of the Algorithm: The 300-Year Journey from an Idea to the Computer. Harvest Books. ISBN 978-0-15-601391-8.
• Chabert, Jean-Luc (1999). A History of Algorithms: From the Pebble to the Microchip. Springer Verlag. ISBN 978-3-540-63369-3.
• Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introduction To Algorithms, Third Edition. MIT Press. ISBN 978-0262033848.
• Harel, David, Feldman, Yishai (2004). Algorithmics: The Spirit of Computing. Addison-Wesley. ISBN 978-0-321-11784-7.
• Knuth, Donald E. (2000). Selected Papers on Analysis of Algorithms. Stanford, California: Center for the Study of Language and Information.
• Knuth, Donald E. (2010). Selected Papers on Design of Algorithms. Stanford, California: Center for the Study of Language and Information.
• Wallach, Wendell; Allen, Colin (November 2008). Moral Machines: Teaching Robots Right from Wrong. USA: Oxford University Press. ISBN 978-0-19-537404-9.

## 攷

1. "Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2).
2. Well defined with respect to the agent that executes the algorithm: "There is a computing agent, usually human, which can react to the instructions and carry out the computations" (Rogers 1987:2).
3. "an algorithm is a procedure for computing a function (with respect to some chosen notation for integers) ... this limitation (to numerical functions) results in no loss of generality", (Rogers 1987:1).
4. "A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a 'computational method'" (Knuth 1973:5).
5. "An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs" (Knuth 1973:5).
6. Cooke, Roger L. (2005). The History of Mathematics: A Brief Course. John Wiley & Sons.
7. Stone 1973:4.
8. Boolos and Jeffrey 1974,1999:19.
9. Stone simply requires that "it must terminate in a finite number of steps" (Stone 1973:7–8).
10. Boolos and Jeffrey 1974,1999:19.
11. Knuth 1973:7 states: "In practice we not only want algorithms, we want good algorithms ... one criterion of goodness is the length of time taken to perform the algorithm ... other criteria are the adaptability of the algorithm to computers, its simplicity and elegance, etc."
12. Stone 1973:7–8 states that there must be, "...a procedure that a robot [i.e., computer] can follow in order to determine precisely how to obey the instruction." Stone adds finiteness of the process, and definiteness (having no ambiguity in the instructions) to this definition.