有趣的算法世界---附录(2)
二 关于算法的确定性
有人说算法的确定性是每一步都应是确定的,或执行无歧义,结果不应成为我们不可预测的东西?这也是从微观上讲吧,我想如此定义就没有不确定性的存在了.在一步中执行是不确定的,结果完全超出了我们的预测范围,就如整数群<Z,+>,+运算在Z上是封闭的,但有两个整数a,b,对于除法运算/,从整数集的角度看,“a/b“的结果你可能给算没了J,那是不允许的.目前的计算机要防止这一点,只要我们想一想我们如何辛苦的构建 好的,稳定的系统,就会明白这一点.
我认为,现在的“确定性“与“不确定性“,是在实际运算中,这一步到下一步的转换上,你是否可以预先确定.比如求和:
For i:=0 to n-1 Do
sum:=sum+a[i];
任何一步到下一步的转换,都是线形的,可唯一确定.但诸如遗传算法中,下一代的种群在具体的执行前是无法确定的,有很多可能性,就是说此步到下一步,不是线形的关系.我们称之为非确定性.
关于这个问题, 网友Dream_soft说到随机的本质问题.当然我们知道目前计算机的随机数都是”伪随机数”,通过一定算法得到的,不同于真正的随机.但要说到什么是真正的随机,这又是个近于哲学上的问题.我们就不说了.
三 关于算法与程序设计方法理论
网友dorcom提到了算法与编程,与语言体制,或者说,算法与程序设计方法学的关系.
我们知道,程序设计方法学,是研究程序设计理论的学科.我们以前程序设计,有抠机器代码的阶段(呵呵J,相当辛苦),后来出现了过程化程序设计,结构化程序设计,到现在的面向对象程序设计,大规模程序设计方法学等等.的确,程序设计方法理论的进步,帮我们解决了许多问题.我们的程序设计方便了,效率高了,可移植性好了,可重用性好了,易维护了,但是,它于算法要解决的不是同一问题.
所以谁也代替不了谁.无论哪方面,作为计算机科学与技术人员,我们都要掌握.
四 关于一些错误
文章是我现打的,没有底稿,所以出现了这样或那样的错误,还请大家原谅.尤其是网友zcr139, cadinfo等,非常感谢您指出了我的失误与错误.
五 关于写作计划和参考资料
构思这些文章的时候,我准备:
(1) 综述,吹起向算法进军的号角吧J.
(2) 什么是算法,一篇,讨论算法的定义和算法的一些特点.其中算法的定义参考了康立山老师的<<智能计算及其应用 讲义>>.可惜本资料是我们学校的内部资料,是并行计算和演化计算的好书,但不能为大家所看到.
(3) 算法之根,计划两篇,由Hilbert问题引出算法的本质问题,由代数结构和有穷自动机引出图灵机.介绍各种图灵机变形后,引出我心中的算法树,说明我们这次旅行的大致路线.其中图灵机定义和有关例子,参考了<<计算理论导引>>(美 Michael Sipser 著,张立昂等译)一书.
如此,我们第一部分就可以结束了.最后仍然是感谢大家.对鼓励我的网友我心存感谢,对批评我指正错误的网友我心存感激,而对那些喜欢了算法,准备细细看书的网友,呵呵,我心存敬佩~~~~
后注:又是因为不能一篇发帖才分作两篇的.J.呵呵,为什么要限制呢.
