第4章算法 当我们试图用计算机解决一个问题时,大 体都要经历如下几个步骤: 1958 g
第4章 算法 当我们试图用计算机解决一个问题时，大 体都要经历如下几个步骤：
1.把问题抽象为一个带有一般性的数学问题,即数 学化。这一步要引入一些数学概念,给出所求问题 的已知条件、所要求的结果、以及在已知条件和所 要求的结果之间存在着的隐式或显式的联系 2.建立相应的求解方法。这一步要给出问题的求解模型 即确定问题的数据模型并在此模型上定义一组运算 然后借助于对这组运算的调用和控制,根据已知数 据导出所要求的结果。 3.用一种程序设计语言描述算法。即将非形式自然语 言表达的算法转变为一种程序设计语言表达的算法 也可称做程序设计或程序编制。 4 编辑、调试和测试程序代码,直到输岀所要求的 结果。 1958 g
1. 把问题抽象为一个带有一般性的数学问题，即数 学化。这一步要引入一些数学概念，给出所求问题 的已知条件、所要求的结果、以及在已知条件和所 要求的结果之间存在着的隐式或显式的联系。 2. 建立相应的求解方法。这一步要给出问题的求解模型， 即确定问题的数据模型并在此模型上定义一组运算， 然后借助于对这组运算的调用和控制，根据已知数 据导出所要求的结果。 3. 用一种程序设计语言描述算法。即将非形式自然语 言表达的算法转变为一种程序设计语言表达的算法。 也可称做程序设计或程序编制。 4. 编辑、调试和测试程序代码，直到输出所要求的 结果
获得了计算方法和算法,并不等于问题可解, 是否可解取决于算法的存在性和计算的复杂性 即是否存在求解算法,算法所需要的时间和空 间在数量级上能否被接受。 1958 g
◼ 获得了计算方法和算法，并不等于问题可解， 是否可解取决于算法的存在性和计算的复杂性。 即是否存在求解算法，算法所需要的时间和空 间在数量级上能否被接受
■1900年,数学家希尔伯特在巴黎举行的世界数 学家大会上发表了至今仍著名的演说。在演说 中,他提出了23个数学问题,这就是著名的 “希尔伯特23个问题”,并认为它们是对下 个世纪的挑战。其中的第10个问题是“丢番图 方程的可解性问题”。其具体涵义是设计一个 算法来测试多项式是否有整数根。将该问题做 相应简化可以设 1958 g
◼ 1900年，数学家希尔伯特在巴黎举行的世界数 学家大会上发表了至今仍著名的演说。在演说 中，他提出了23个数学问题，这就是著名的 “希尔伯特23个问题”，并认为它们是对下一 个世纪的挑战。其中的第10个问题是“丢番图 方程的可解性问题”。其具体涵义是设计一个 算法来测试多项式是否有整数根。将该问题做 相应简化可以设:
D={plp是有整数根的x的多项式},则集合D是否 可判定?答案是否定的。 我们可以把多项式输入到计算机中进行处理,当 x赋值为0,-1,1,-2,2,-3,3,…时,分 别求出多项式的值,一旦求得0值,就接受,如 果p没有整数根,则程序将永远运行下去。 1958 g
D={p|p是有整数根的 x的多项式}，则集合D是否 可判定？答案是否定的。 我们可以把多项式输入到计算机中进行处理，当 x赋值为0，-1，1，-2，2，-3，3，……时，分 别求出多项式的值，一旦求得0值，就接受，如 果p没有整数根，则程序将永远运行下去
本章内容 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