算法是不确定的还是模棱两可的?

问题描述 投票:0回答:1

CLSR表示算法是“定义明确的过程”。“定义明确”的确切含义。这是否意味着它不应模棱两可或不确定。如果是,则算法模糊或不确定的含义是什么。

algorithm turing-machines ambiguity non-deterministic
1个回答
0
投票

“定义明确的过程”仅意味着它应包含一系列处理每种可能的输入变化的步骤。例如,在决策树中,您需要考虑所有情况,直到到达问题分支为止。以找到列表最大值的算法为例:当您仅遇到整数时该怎么办?您如何比较它们?如果您尝试比较数组中两个不同类型的元素,会发生什么?数组中的元素可以接受的值是否受到限制?数组的大小呢?这样,您可以沿着这些路线找到大量其他问题。算法必须能够回答所有这些问题,因此是“定义明确的”。非确定性算法实际上是CS中一个很大的领域。请查看此Wikipedia链接以获取更多示例Non-deterministic algorithms。这些算法可以在后续运行中为同一输入生成不同的输出。例如,某些东西使用硬币翻转来打印“正面”或“尾巴”。因此,根据您的随机数,输出将在多次运行中发生变化。将其与确定性算法进行比较,后者每次都会对相同的输入产生相同的输出

© www.soinside.com 2019 - 2024. All rights reserved.