【算法论】上集 - 科学.pdf

算法(上册)A.A.馬尔科夫著胡世华唐稚松何成武科学出版社

序 1.一个計算过程从可变的初始材料导出所求的结果,在数学寻求两个自然数的最大公因子的欧几里得算法,是算法的典型例子.这里的初始材料是任意一对自然数.指合就是逐步构造皎小的一个.第三个数是第二个除第一个所得的余数.第四个又是第三个除第二个所得的余数,如此继續,直到除尽为止(没有余数),这时最后一次除法的除数便是算法所求的结果一两个給定自然数的最大公豹数,以下三点是算法的特征且决定了算法在数学中的作用 a)算法的定性:指分的准摘性不容計任何随意之处,而且要人人易懂.6)算法的大量性:由于在一定范围内可变动的初始材料而有的可能性。

化的基础上作出算法的一般理是很有盆的,这也就是本文的目的作者希望,他能满意地解决所提出的間题,此处所叙述的算法理论是从相当簡单,同时也较方便的“正规算法”的定义出发的,这种愿望究竟实現得如何,让讀者去判断.递归函数概念的算法理等价的.特罗斯(B.K:ⅡeTnOBc)已經证明这确是如此！本书叙述了算法论的基础及其在证明一些算法問题不可判定中的运用.此理的其它内容(在第4段中所提到的)应有专門的著述,作省希望以后能做这工作.6.本书分为六章.章中分节.节中分段．每段中的输断(即定理、辅助定理、推输)分别号,公式也分别号。