算法 

应对灯泡不亮的简单算法流程图

算法algorithm),在數學算學)和電腦科學之中,為任何一系列良定义的具體計算步驟[1],常用於計算數據處理英语Data processing自動推理。作为一个有效方法英语Effective method,算法被用於計算函數[2],它包含了一系列定义清晰的指令[3],并可于有限的时间及空间内清楚的表述出来[4]

算法中的指令描述的是一個計算,當其執行英语Execution (computing)時能從一個初始狀態和初始輸入(可能爲)開始,[5]經過一系列有限[6]而清晰定義的狀態最終產生輸出[7]停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。包括隨機化算法在内的一些算法,都包含了一些隨機輸入。[8][9]

早在尝试解决希尔伯特提出的判定问题时,关于算法的一个不完全的概念已经初步定型,並在其后的正式化阶段中尝试定义“有效可計算性英语Effective calculability[10]”或者“有效方法英语Effective method[11]”。这些尝试包括库尔特·哥德尔雅克·埃尔布朗斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的遞歸函數阿隆佐·邱奇於1936年提出的λ演算,1936年埃米爾·萊昂·珀斯特英语Emil Leon PostFormulation 1艾倫·圖靈1937年提出的圖靈機。即使在當下,依然常有符合直覺的想法難以定義爲形式化算法的情況。[12]

  1. ^ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein; 殷建平等译. 第1章 算法在计算机中的作用. 算法导论 原书第3版. 北京: 机械工业出版社. 2013年1月: 3[5]. ISBN 978-7-111-40701-0 (中文). 
  2. ^ "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)
  3. ^ 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).
  4. ^ "Any classical mathematical algorithm, for example, can be described in a finite number of English words"(Rogers 1987:2).
  5. ^ "An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins"(Knuth 1973:5)
  6. ^ "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)
  7. ^ "An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs"(Knuth 1973:5)
  8. ^ Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without use of continuous methods or analogue devices... carried forward deterministically, without resort to random methods or devices, e.g., dice" Rogers 1987:2).
  9. ^ Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without use of continuous methods or analogue devices ... carried forward deterministically, without resort to random methods or devices, e.g., dice" Rogers 1987:2).
  10. ^ Kleene(斯蒂芬·科尔·克莱尼)1943 in Davis 1965:274
  11. ^ Rosser(巴克利·羅瑟)1939 in Davis 1965:225
  12. ^ Moschovakis, Yiannis N. What is an algorithm?. (编) Engquist, B.; Schmid, W. Mathematics Unlimited—2001 and beyond. Springer. 2001: 919–936 (Part II). 



取材自維基百科 - 中文時事百科