演算法

出自維基百科,自由嘅百科全書
Jump to navigation Jump to search
一個用來解決「盞燈唔着」呢個問題嘅演算法;演算法可以用流程圖表示。

演算法粵拼:jin2 syun3 faat3英文:algorithm)係數學電腦科學上嘅一個概念,指一串能夠完全唔含糊噉教一個人或者一部電腦點樣解決某啲特定問題嘅指示。演算法又有分好多唔同種,唔同種嘅演算法可以用來解決唔同嘅問題,由簡單嘅算術以至自動化嘅認知等等都有演算法可以做得到。

一個演算法可以喺有限嘅時空之內透過一套有精確定義形式語言來表達[1][2],用來計一啲函數[3]。噉講嘅意思係話,一個演算法會要求某啲特定嘅輸入(Input),跟住啲指示會描述一柞運算,而當呢柞運算由人或者電腦執行嗰陣,會經過一連串數量有限嘅中介狀態[4],最後產生一個輸出(Output)[5],並且喺呢個最終狀態嗰度終止執行。由一個中介狀態去到下一個嘅過程唔一定係決定性(Deterministic)嘅,有好多演算法都涉及一啲帶有些少隨機性喺入面嘅運算。

演算法嘅概念經已存在咗超過 2,000 年,有得一路追溯到去古希臘數學家嗰度,例如係由呢啲數學家諗出來嘅愛氏篩同埋輾轉相除法呀噉[6],而「Algorithm」呢個字係由 9 世紀嘅波斯人數學家花剌子密波斯文:محمد بن موسى خوارزمی)個姓嗰度來嘅(佢個羅馬字係「Algoritmi」),佢做咗一啲相關嘅研究,局部噉確立咗演算法嘅概念[6]。現代嘅演算法概念係喺 1928 年由德國數學家打域囂拔(David Hibert)喺佢嘗試解決可判定性嘅問題嗰陣奠定嘅。自從嗰陣開始,演算法同相關嘅研究就喺數學同電腦科學呢兩個領域嗰度俾人廣泛噉採用。

定義[編輯]

非正式定義[編輯]

唔正式噉講,「演算法」呢個詞嘅定義可以係指「一串能夠精確噉定義一系列作業嘅規則」[7][8]。呢個定義包含嗮所有嘅電腦程式-就連啲唔曉做數字上嘅運算嘅程式都包含喺呢個定義之內。另外,一般來講,一串規則要識喺有限嘅時間之內行完先可以算係演算法[9]。正話提咗嘅輾轉相除法同埋上面嗰個流程圖所描述嘅都係符合呢個定義嘅演算法。

美國邏輯學家 George Boolos 同佢嘅同事係噉樣描述「演算法」呢個概念嘅[10]

原版英文:"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 可以係是旦一個細過無限大嘅整數。呢啲指示都要幾明確至得,要有一個形式,令到曉計數嘅機器(例如係電腦)或者一個淨係曉用符號嘅人類能夠跟從佢哋。

上面呢段嘢當中所講嘅「列舉到嘅無限集」係數學上嘅一個概念,指一個包含咗多樣嘢嘅集,而呢個集包含嘅物件有無限噉多件,但係啲件數可以用由 1 開始嘅整數來數佢。所以 Boolos 同佢啲同事講緊就係話:一個演算法係一連串指令,例如係一柞好似「 代表輸出, 代表輸入」噉嘅算式;而呢柞指令能夠由是旦一啲輸入嗰度計同整一啲輸出出來俾人睇,而且呢啲輸入-至少喺理論上-係幾大都得嘅(但係當然,實際上因為人有嘅電腦嘅運算能力有限,所以對於輸入嘅大細梗會有個上限)。

對於 Boolos 等人嘅睇法,學界都有些少爭詏[11][12]

正式定義[編輯]

睇埋[編輯]

參考書[編輯]

  • 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. 6.0 6.1 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.