算法 

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

算法(英語:algorithm),在数学算学)和计算机科学之中,指一个被定义好的、计算机可施行其指示的有限步骤或次序[1],常用于计算数据处理自动推理。算法可以使用条件语句通过各种途径转移代码执行(称为自动决策),并推导出有效的推论(称为自动推理),最终实现自动化。

相反,启发式是一种解决问题的方法,可能没有完全指定,也可能不能保证正确或最优的结果,尤其是在没有明确定义的正确或最优结果的问题领域。[2]例如,社交媒体推荐系统依赖于启发式,尽管在21世纪的流行媒体中被广泛称为算法,但由于问题的性质,它无法提供正确的结果。

早在尝试解决希尔伯特提出的判定问题时,算法的不完整概念已经初步定型;在其后的正式化阶段中人們尝试去定义“有效可计算性英语Effective calculability[3]”或者“有效方法英语Effective method[4]”。这些尝试包括库尔特·哥德尔雅克·埃尔布朗斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数阿隆佐·邱奇于1936年提出的λ演算,1936年埃米尔·莱昂·珀斯特英语Emil Leon Post波斯特-图灵机艾伦·图灵1937年提出的图灵机。即使在当下,依然常有符合直觉的想法难以定义为形式化算法的情况。[5]

算法是有效方法英语Effective method,包含一系列定义清晰的指令[6],并可于有限的时间及空间内清楚的表述出来[7]。算法中的指令描述的是一个计算,它执行英语Execution (computing)時从一个初始状态和初始输入(可能为)开始,[8]经过一系列有限[9]而清晰定义的状态最终产生输出[10]停止于一个终态。 一个状态到另一个状态的转移不一定是确定的。 包括随机化算法在内的一些算法,都包含了一些随机输入。[11][12]

  1. ^ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein; 殷建平等译. 第1章 算法在计算机中的作用. 算法导论 原书第3版. 北京: 机械工业出版社. 2013年1月: 3[5] [2017-11-14]. ISBN 978-7-111-40701-0 (中文). 
  2. ^ David A.Grossman,Ophir Frieder,“信息检索:算法和启发式”,2004年第2版,ISBN 1402030045
  3. ^ Kleene(斯蒂芬·科尔·克莱尼)1943 in Davis 1965:274
  4. ^ Rosser(巴克利·羅瑟)1939 in Davis 1965:225
  5. ^ Moschovakis, Yiannis N. What is an algorithm?. Engquist, B.; Schmid, W. (编). Mathematics Unlimited—2001 and beyond. Springer. 2001: 919–936 (Part II) [2012-09-27]. (原始内容存档于2021-04-24). 
  6. ^ 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).
  7. ^ "Any classical mathematical algorithm, for example, can be described in a finite number of English words"(Rogers 1987:2).
  8. ^ "An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins"(Knuth 1973:5)
  9. ^ "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)
  10. ^ "An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs"(Knuth 1973:5)
  11. ^ 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).
  12. ^ 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).



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