关于算法定义的确定性



我正在阅读一篇关于算法定义的笔记,它有两个要求,我不知道它们之间有什么区别

确定性:每条指令都应该是清晰明确。(我找到了一个完全相同的消息来源(

从我拥有的资源来看,有5个要求:输入、输出、确定性、有限性和有效性。我能理解除了确定性之外的其他4个。如果以上不准确,有人能提供一些更好的定义吗?

根据以上内容,我只怀疑至少有两个微妙之处需要考虑。。。


以下答案的结论:definiteness = defined(clear) + only_one(unambiguous)

算法应该清晰无误。每一个步骤(或阶段(及其输入/输出都应该清晰明了,并且只能产生一种意义。

例如,如果一步是将两个整数相加,我们必须定义"整数"one_answers"加法"运算:例如,我们不能在一个地方使用相同的符号来表示加法,在其他地方使用乘法。

如果呈现给受过教育的人,文本应该允许他按照你想象的方式手动模拟执行(采取相同的步骤,获得相同的结果(。

当你不太理解某个作者提供的术语的定义时,寻找它的其他定义通常会很有帮助。我特别喜欢wiktionary.org中的"确定性"定义:

  1. 没有任何疑问

在这种情况下,clear变为可理解,而毫不含糊则变为具有单一含义的

这只是意味着算法中的指令应该有一个并且只有一个解释。此外,这种解释应该是显而易见的。

像"重复步骤1到4几次"这样的说法不符合标准,因为"几次"可能意味着不同的人尝试的次数不同。

另一方面,像"重复步骤1到4,直到x等于y"这样的语句,其中xy是算法中的一些参数,这确实是明确无误的。

最新更新