第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没有整数根，则程序将永远运行下去