算法
算法(英语:algorithm),在数学(算学)和电脑科学之中,一个被定义好的、计算机可施行之指示的有限步骤或次序,常用于计算、数据处理(Data processing)和自动推理。作为一个有效方法(Effective method),算法被用于计算函数,它包含了一系列定义清晰的指令,并可于有限的时间及空间内清楚的表述出来。
算法中的指令描述的是一个计算,当其执行/Execution (computing)}}时能从一个初始状态和初始输入(可能为空)开始,经过一系列有限而清晰定义的状态最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。包括随机化算法在内的一些算法,都包含了一些随机输入。
早在尝试解决希尔伯特提出的判定问题时,关于算法的一个不完全的概念已经初步定型,并在其后的正式化阶段中尝试定义“有效可计算性(Effective calculability)”或者“有效方法(Effective method)”。这些尝试包括库尔特·哥德尔、雅克·埃尔布朗和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数,阿隆佐·邱奇于1936年提出的λ演算,1936年埃米尔·莱昂·珀斯特(Emil Leon Post)的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当下,依然常有符合直觉的想法难以定义为形式化算法的情况。
历史
算法在中国古代文献中称为“术”,最早出现在《周髀算经》、《九章算术》。特别是《九章算术》,给出四则运算、最大公约数、最小公倍数、开平方根、开立方根、求素数的埃拉托斯特尼筛法,线性方程组求解的算法。三国时代的刘徽给出求圆周率的算法:刘徽割圆术。
自唐代以来,历代更有许多专门论述“算法”的专著:
- 唐代:《一位算法》 一卷,《算法》 一卷;
- 宋代:《算法绪论》 一卷、《算法秘诀》 一卷;最著名的是杨辉的《杨辉算法》;
- 元代:《丁巨算法》;
- 明代:程大位 《算法统宗》
- 清代:《开平算法》、《算法一得》、《算法全书》。
而英文名称“algorithm”来自于9世纪波斯数学家花拉子米(比阿勒·霍瓦里松,波斯语:خوارزمی ,拉丁转写:al-Khwarizmi),因为比阿勒·霍瓦里松在数学上提出了算法这个概念。“算法”原为“algorism”,即“al-Khwarizmi”的音转,意思是“花拉子米”的运算法则,在18世纪演变为“algorithm”。
欧几里得算法被人们认为是史上第一个算法。
第一次编写程序是爱达·勒芙蕾丝(Ada Byron)于1842年为巴贝奇分析机编写求解解伯努利微分方程的程序,因此爱达·勒芙蕾丝被大多数人认为是世界上第一位程序员。因为查尔斯·巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机,这个算法未能在巴贝奇分析机上执行。
因为“well-defined procedure”缺少数学上精确的定义,19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了著名的图灵论题,并提出一种假想的计算机的抽象模型,这个模型被称为图灵机。图灵机的出现解决了算法定义的难题,图灵的思想对算法的发展起到了重要的作用。
特征
以下是高德纳在他的著作《计算机程序设计艺术》里对演算法的特征归纳:
- 输入:一个算法必须有零个或以上输入量。
- 输出:一个算法应有一个或以上输出量,输出量是算法计算的结果。
- 明确性:算法的描述必须无歧义,以保证算法的实际执行结果是精确地符合要求或期望,通常要求实际执行结果是确定的。
- 有限性:依据图灵的定义,一个演算法是能够被任何图灵完备系统模拟的一串运算,而图灵机只有有限个状态、有限个输入符号和有限个转移函数(指令)。而一些定义更规定演算法必须在有限个步骤内完成任务。
- 有效性:又称可行性。能够实现,算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。
基本要素
算法的核心是建立问题抽象的模型和明确求解目标,之后可以根据具体的问题选择不同的模式和方法完成算法的设计。
常用设计模式
完全遍历法和不完全遍历法:在问题的解是有限离散解空间,且可以验证正确性和最优性时,最简单的算法就是把解空间的所有元素完全遍历一遍,逐个检测元素是否是我们要的解。这是最直接的算法,实现往往最简单。但是当解空间特别庞大时,这种算法很可能导致工程上无法承受的计算量。这时候可以利用不完全遍历方法——例如各种搜索法和规划法——来减少计算量。
分治法:把一个问题分割成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。
动态规划法:当问题的整体最优解就是由局部最优解组成的时候,经常采用的一种方法。
贪婪算法:常见的近似求解思路。当问题的整体最优解不是(或无法证明是)由局部最优解组成,且对解的最优性没有要求的时候,可以采用的一种方法。
线性规划法:见条目。
简并法:把一个问题通过逻辑或数学推理,简化成与之等价或者近似的、相对简单的模型,进而求解的方法。
常用实现方法
顺序计算、并行计算和分布式计算:顺序计算就是把形式化算法用编程语言进行单线程序列化后执行。
确定性算法和非确定性算法
精确求解和近似求解
形式化算法
算法是计算机处理信息的本质,因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务,如计算职工的薪水或打印学生的成绩单。一般地,当算法在处理信息时,会从输入设备或数据的存储地址读取数据,把结果写入输出设备或某个存储地址供以后再调用。
实现
算法不单单可以用计算机程序来实现,也可以在人工神经网络、电路或者机械设备上实现。