算法(翻译,来自Wiki)分析报告.doc

算法 译自From Wikipedia, the free encyclopedia ? 一种计算在位置名为A和B的两个数字a 和b的最大公约数 (g.c.d.) 的算法（欧几里得的算法）的流程图。 ??????? 该算法通过在两个循环中连续减进行的：如果测试B≥A产生的是是（或真）（更准确地说位置B的数字b是大于或等于位置 A的数字a）那么，算法指定B←B?A(意思是数字b?a替换旧b)。同样，如AB，那么A←A?B。当B（的内容）为0时进程终止，在A生成最大公约数（按照Scott 2009:13派生的算法；符号和绘图风格按照Tausworthe1977）。 ??????? 在数学和计算机科学中，算法是一个计算的分步过程。算法用于计算、数据处理和自动推理。 ??????? 算法是一种表达成定义明确的有限指令表的一个函数的计算的有效方法。从初始状态和初始输入（可能为空）开始，指令描述当执行一个计算时通过有限数量的明确 定义的连续状态，最终产生输出并在最终的结束状态终止。从一种状态过渡到下一步并不是一定确定的；一些称为随机算法的算法，将随机输入纳入。 ??????? 尽管阿尔·克沃理滋米（al Khwārizmī）的算法提到使用印度-阿拉伯数字进行算术的规则及线性和二次方程的系统解决方案，但成为现代算法的一部分的公式化始于1928年试图解决大卫·希尔伯特（David Hilbert）构 成的决策问题 (Entscheidungsproblem）。随后的公式化被构架成试图定义有效的计算或有效的方法；这些公式化包括1930年、1934年和 1935年的高德尔-赫尔布兰德-克林（G?del–Herbrand–Kleene）的递归函数，1936年的阿隆索·丘尔奇（Alonzo Church）的λ演算、1936年的爱米尔·泊思特（Emil Post）的公式1和1936–7和1939年的阿兰·图灵的图灵机。给予算法一个正式的定义，对应的直观的概念仍然是一个具有挑战性的问题。 1? 非正式定义 ??????? 围绕算法的定义的各种观点的详细介绍，请参考算法特征化。以详细方式指定的简单的加法算法的示例在算法的特征化中描述的有，请参见算法的例子 ??????? 虽然没有普遍接受的算法的正式定义，但非正式的定义可能是精确地定义一个序列的一组规则，其中会包括所有的计算机程序，包括不执行数值计算的程 序。对一些人来说，程序只是一种算法，如果它最终停止的话。对另一些人来讲，程序只是一种算法，如果它执行了许多计算步骤的话。 ??????? 算法的一个典型的例子是欧几里得的确定两个整数的最大公约数的算法；一个（有其它的）由上述流程图描述的示例并在后节中作为例子。 ??????? 布劳思杰弗里（Boolos Jeffrey，1974年、1999年）在以下引文中提供字的一个非正式的意思： ??????? 不会有任何人用一些记数法可以写得足够快或足够长或足够小?(?无限的越来越小......你会试图在分子、原子、电子上写)来列出可数的无限集的所 有成员，写出它们的名字，一个接一个。但人可以做点同样有用的某些事，在某些可数无限集的情况下：他们可以给显式指令来确定集的任意有限的n的第n个成 员。这种指令是非常明确地给予的，以一种它们可以被计算机或被一个能够履行对符号进行非常初级操作的人遵循的形式。 ??????? 可数的无限一词意味着用整数或许能扩展到无穷大的数数。因此，布劳思杰弗里说算法意味着从一个任意的输入整数或数个整数，理论上可 以从0到无穷大选择来创造输出整数的过程。因而算法可以是如y=m+n------两个任意输入变量m和n产生输出y的代数方程。但众多的作者试 图界定表明这个词意味着比这更多的东西的概念，关于次序（对求和的例）： ?????? 为指定的计算机（机器或人类，配有必要的内部信息和能力）有哪些信誉好的足球投注网站、解码然后处理任意输入的整数/符号m和n、符号+和=...并在合理的时间内有 效地以指定的格式在指定的地点产生输出整数y制定的移动的快速、高效、良好的进程的精确指令(计算机理解的语言)。 ??????? 算法的概念也用于定义可判定性的概念。这一概念是解释正式系统怎样从一小套的公理和规则开始进入的的中心。在逻辑中，算法需要完成的时间不能测量，因为它 显然不与我们习惯的物理维度相关。从这种不确定性上特征化进行着工作，阻止既适合具体（在某种意义上)又适合这一术语的抽象用法的算法的定义的不可利用 性。 2 公式化 ??????? 算法是计算机处理数据的必不可少的方式。许多计算机程序包含计算机应执行（按特定的顺序）的详细的特别的指定任务的算法，如计算雇员的薪水或打印学生的报 告卡。因此，算法可以被认为是一种任何能通过完备图灵系统模拟的操作序列。断言这个的论文作者包括明