本章内容 4.1算法的概念 4.2算法的表示 4.3常用算法介绍 4.4并行算法 4.5算法的评价 4.6算法的设计要求 1958 g
本章内容 ◼ 4.1 算法的概念 ◼ 4.2 算法的表示 ◼ 4.3 常用算法介绍 ◼ 4.4 并行算法 ◼ 4.5 算法的评价 ◼ 4.6 算法的设计要求
4.1.1算法的定义 ■算法是程序设计的精髓,程序设计的实质就是 构造解决问题的算法,将其解释为计算机语 有关算法( al gor i thm)的定义不只一种,其中 种叙述为:算法是对特定问题求解步骤的 种描述,它是指令的有限序列,其中每一条指 令表示一个或多个操作 1958 g
4.1.1 算法的定义 ◼ 算法是程序设计的精髓，程序设计的实质就是 构造解决问题的算法，将其解释为计算机语言。 ◼ 有关算法(algorithm)的定义不只一种，其中 一种叙述为：算法是对特定问题求解步骤的一 种描述，它是指令的有限序列，其中每一条指 令表示一个或多个操作
曾获图灵奖的著名科学家克努斯(D. Knuth) 对算法这一概念给出了进一步的描述 个算法,就是一个有穷规则的集合,其中 之规则确定了一个解决某一特定类型问题的 运算序列。此外,算法的规则序列必须满足 下列五个重要条件: 1958 g
曾获图灵奖的著名科学家克努斯（D.Knuth） 对算法这一概念给出了进一步的描述。 ◼ 一个算法，就是一个有穷规则的集合，其中 之规则确定了一个解决某一特定类型问题的 运算序列。此外，算法的规则序列必须满足 下列五个重要条件：
(1)有穷性。算法必须总是在执行有穷步之后结束 (2)确定性。算法的每一步骤必须被确切地定义; (3)输入。算法有零个或多个输入; (4)输出。算法有一个或多个输出; (5)能行性。算法中有待执行的运算和操作必须是相当 基本的,即它们原则上都是能够精确地进行的,而且 用笔和纸做有穷次就可以完成 1958 g
（1） 有穷性。算法必须总是在执行有穷步之后结束； （2） 确定性。算法的每一步骤必须被确切地定义； （3） 输入。算法有零个或多个输入； （4） 输出。算法有一个或多个输出； （5）能行性。算法中有待执行的运算和操作必须是相当 基本的，即它们原则上都是能够精确地进行的，而且 用笔和纸做有穷次就可以完成
了算法的非形式化定义外,还有算法的形式化定义: 算法是一个四元组,即(O,,O,F)。 其中: 10是一个包含子集/和的集合它表示计算的状态。 2/表示计算的输入集合; 30表示计算的输出集合; 4F表示计算的规则,它是一个由Q到它自身的函数,且 具有自反性,即对于任何一个元素q∈Q,有F(q)=q。 1958 g
除了算法的非形式化定义外，还有算法的形式化定义： 算法是一个四元组，即（Q， I，O， F）。 其中： 1 Q 是一个包含子集I 和的集合它表示计算的状态。 2 I 表示计算的输入集合； 3 O 表示计算的输出集合； 4 F 表示计算的规则，它是一个由Q 到它自身的函数，且 具有自反性，即对于任何一个元素q∈ Q， 有F(q)=q