ITnews 版 (精华区)

发信人: petrel (紫燕＊自在飞花轻似梦*燕燕于飞), 信区: ITnews
标  题: 有趣的算法世界---附录(1)    PercyLee（原作）
发信站: 哈工大紫丁香 (2003年08月13日19:44:03 星期三), 站内信件

有趣的算法世界---附录(1)
看了许多的网友评论;谢谢大家,使我获益菲浅.在大家的帮助下得到成长,真是件快乐的
事.但因为前已声明,所以有些问题不敢不交代.另外,对于网友中谈到的比较好的问题,我
也谈谈自己的看法.
               一   关于算法的有穷性
这个问题是无法避免的.我有责任给大家说明我当初的想法.
首先,是在上学期听康老师(康立山老师,武大教授,兼聘地大计科系主任)讲演化计算时的
一句反问引发的思考,算法是否可以无穷执行.当然,在这之前,我所受的教育就是,算法的
性质其一就是有穷性.大二数据结构老师特意讲算法与程序的区别(记得那时听课是点了
头的J),我想,本科教育就截止于此.
既然喜欢的老师有这一句反问,我想追查下去.为什么可以,或者,为什么不可以?翻了许多
书,发现各书是各有差别的.我们选择有代表的两家.
一是清华殷人昆老师的数据结构(c++描述)教材.他的算法定义有五个特性:
(1)               输入.必须有0或多个输入.
(2)               输出.一个或多个输出.
(3)               确定性.每一步都应确定地,无歧义地定义.
(4)               有穷性.无论在什么情况下都应在执行有穷步后结束.
(5)               有效性.
我是简短的转述.老实说,不管殷老师数据结构如何,这个算法的定义给我们本科生实在是
很蹩脚.这个确定性本身就让人难于理解(算法的每一步什么叫确定地定义?你难不成反过
来说满足确定性?).而有穷性的定义,是机器实际执行有穷步,还是算法表达语言的有穷步
?
另外,他认为操作系统不是算法,原因是由于不符性质(4).
另一教材是电子工业出版社Clifford A. Shaffer 著,张铭等译的<<数据结构与算法分析
>>,里面关于算法的性质与”有穷性”相关的有:
(2)     具体步骤.每一步必须在有限的时间内执行完毕.
(4)
(4)              (4)         有限性.一种算法必须由有限步骤组成,否则,”我们就
不可能将它写出来,也不可能将它作为计算机程序来实现”.
(6)                   (6)                可终止性. 算法必须可以终止,即不能进
入死循环.
一个概念的定义,我觉得有两点因素,一是符合直觉观念,二是方便研究使用.有人说也有
个历史问题,事实上概念不应该局限于历史,如果新情况允许改,就可以突破.
比较上面的两种定义,我们不难发现后者的细致.事实上,我在<<什么是算法>>里的算法定
义,源引于康立山老师的<<智能计算及其应用  讲义>>中的定义:
算法,即一步一步求解问题的方法，它有如下的特征：
(1)必为一有限的文本表示;
     (2)每一步必有可能在有限的时间内机械的完成。
我本人喜欢这个定义.仍回到有穷性的问题上,再看看网友的讨论,主要可分为:
happycock, javaboy的: 算法与程序不同.
Violetblue 的:无穷执行将无用.
至于Dream_soft的,的确是高论,让我最有收获,后面再说.首先一点,算法应该是用来解决
问题的,大家应该没有异议.当然手段是计算.另外,我们大家都承认的是,算法的每一步肯
定应该在有限时间里执行完成.即使从直觉观念来出发,在其中的一步中陷入无穷执行的
话,那么我们就会怀疑这个所谓的”算法”要解决什么问题了.这个”有穷性”,可以称为
微观的.我们的争论点是,从宏观整体上讲,算法可以无穷执行吗?
张译的教材中说”有穷性”,是描述的”有穷步”,否则表达就成问题.这有点元语言与形
式语言的味道.算法的描述步骤嘛,而不是算法本身的执行.这个观点我也是同意的,我喜
欢的那个定义说算法”必为一有限文本的表示”,也是这个意思.但其中没有说明算法不
可以无穷时间的执行.
无穷执行就无用吗?我的直觉中没有这个概念.在说Hilbert问题时,曾经说数学家的直觉
观念中算法是必须在有穷时间结束的,我觉得那是因为他要解决的问题(不定方程是否有
整数解),是要么有解,要么无解的,当然我们希望尽快有个答案的.但实际问题中,许多不
是靠”解”来解决问题的,如那个自动窗的问题,那是一种活动的控制,我们不需要解,而
是就这样一直做下去的控制;康老师说钟表的问题,我想也是这个意思.
当然,张译的教材中又补充一条,(6)可终止性.可他似乎说的是避免死循环,我想死循环也
应该是以是否有用为标准的,哦,太功利了?嘻嘻,那算法应该加个停机条件是吧,但加停机
条件的未必不可以无穷执行.
还是说网友Dream_soft的观点,源引如下:
“第一，算法应该是有穷，我这样想是因为算法应该是针对可计算的问题的。大家都知
道，可计算性的一个判别标准就是是否停机，如果不能停机，也就是说算法是永不中止
的话，那就属于不可计算的问题了。由于图灵机停机问题是不可计算的，也就是说我们
没有一个通用的算法来判断一个图灵机对某个输入是否停机。如果说算法可以是无限的
，那么就可以说对图灵机停机问题存在算法，也就是说停机问题是可解的了，这和数学
上的结论不合。”
很显然这个是令我最头痛的一个J.首先这个理由是最具本质的,有穷性源于问题的可判定
性,又即可计算性的问题.我们知道,图灵机又可以分为识别器和判定器.前者可以解决所
有可图灵识别的问题,但可图灵识别未必可判定.比如停机问题就是典型的不可判定问题
.
我们再举一个不可判定的问题, Hilbert问题中的那个有限时间内判断不定方程是否有整
数解的问题.已证明它是不可判定的.但诸如下面的图灵机M(带子两边无限长,初始值是所
有的整数,从左到右按数轴的顺序)是一种解法:
M=”对于给定的不定方程,做
(1)     从整数0开始,验证0是否是不定方程的解,如果是,转(4);否则
(2)     向右移动一个位置,假设到n,验证n是否是不定方程的解,如果是,转(4);否则移
到-n验证之,如果是不定方程的解,转(4);否则
(3)     移到n,转(2);
(4)     输出结果,停机.“
显然对于有整数解的不定方程,这个图灵机一定可以找到一个解而停机,但如方程本身无
整数解,则此图灵机是不停机的.
我们能叫它算法吗?这个问题我也想了很久.当初我的想法是,这个图灵机,是否停机与问
题是相关的,有的方程是停机的,有的不是.加之前面的原因,没有理由一定定义算法不可
无穷执行.当然,从可判定性出发,定义算法解就是任意情况下可在有穷时间内得出问题解
的解法,也是可以接受的.但有很大一部分解法,包括那些问题本身重点不在于解的,都被
排除之外了.
最近在看数学分析,有一处具有可比性.在讲数列的极限的时候,先是收敛到一个有穷值的
,就称数列的极限为该值,该数列为收敛数列.但发散数列有极限吗?后面讲到一类特殊的
发散数列时,补充定义了∞(无穷大),又定义了极限为∞的数列.这样实数集R也要扩充了
,把-∞和+∞加入了.
发散数列有极限吗?能用直觉观念否定吗?能用无用论否定吗?事实上都不能否定,这样的
定义反而有利于问题的讨论;只是,在需要时,我们可以明示说明,是有穷极限.
所以我喜欢康老师那个定义,干干净净,具有包容性,但又不遗漏本质.在研究可计算性和
计算复杂性的时候,我们强调好的算法要算的尽可能快,不要不停机.但广义的算法,就让
它是成为解决问题的方法吧.只要符合我们<<什么是算法>>里的定义.
这就是我当初的观点.关于那个操作系统不是算法,我一直以为是为了防止“泛算法论“
.算法虽然是计算机科学的本质问题之一,但如操作系统,它的处理机调度有算法,内存的
管理有算法,但整体的堆积就不要是算法了吧,它超出了我们算法的定义,当作算法来研究
也的确太不方便了.
需要说明的是这是个人观点,可供您思考但不要您以此为准.您如果有好的异议和证据,也
可以通过信箱联系我:
 percylee@eyou.com
or
non-leaf@sohu.com

--

燕燕于飞，差池其羽。
          燕燕于飞，颉之颃之。
                    燕燕于飞，上下其音。

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 172.16.8.35]