问题标签 [deterministic]

晚上好，我想知道是否有人可以为我提供一个确定性算法的简单伪代码示例......我将不胜感激，一定会给你加分！！。谢谢

维基百科指出，确定性状态自动化“为每个输入字符串生成自动机的唯一计算（或运行）”。

我一直理解这一点，因为只有 1 种可能的路径来计算任何唯一的字符串。在这种情况下，以下是 DSM。

但是现在我想多了，并将描述解释为每个输入字符串都有一个可能的路径，并且该路径与所有其他输入字符串都是唯一的。在这种情况下，以下不是 DSM，因为“11”和“12”遵循相同的路径。

所以我的问题是，以下是 DSM 还是 NDSM？

我有一个事实...

我需要找出是否有任何一组（性别，年龄）有更多最喜欢的水果（上述事实的答案是（女性，年轻。）

我一直想弄清楚的是如何在序言中使用aggregateorfindall函数来返回某种类型的列表，例如....

...这样我就可以检查每个成员的总数并测试它是否大于 1。

任何想法将不胜感激。

假设我有两个确定性有限状态自动机，由以下转换图表示：

关键字 IF 的 FSA： IF

ID 的 FSA： [AZ][A-Z0-9]*

我可以使用什么算法将它们组合成具有三个最终状态的单个确定性有限状态自动机，由以下转换图表示：

我正在尝试构建一个确定性模拟，其中浮点数通过以下函数被截断：（我在这里找到它：http: //joshblog.net/2007/01/30/flash-floating-point-number-错误）

我的问题是：我将它除以 10000 的事实本身不是浮点错误的来源吗？ IE 每次发生除法时，都会产生一个新的浮点数，并可能产生更多不确定的结果。

编辑：这个怎么样？仅使用 2 的幂

这是一个关于浮点运算的跨平台一致性和确定性的问题（IE 在不同的 CPU/系统上产生不同的结果）

哪一个更有可能保持跨平台一致（伪代码）：

或者

平台是 C# 和 AS3。

.

AS3 版本：

- 好的，我添加了 AS3 版本以进行澄清，相当于上面的“C 伪代码”。正如您在 AS3 中看到的，所有计算，即使是整数，都会自动作为浮点数执行，不需要强制转换（也不能避免它或强制运行时执行真正的整数除法）希望这可以解释为什么我“强制转换”所有内容成花车：我不是！这只是在一种目标语言中发生的事情！

我需要将 32 位 IEEE754 浮点数转换为有符号的 Q19.12 定点格式。问题是它必须以完全确定的方式完成，所以通常的 (int)(f * (1 << FRACTION_SHIFT)) 是不合适的，因为它使用非确定性浮点数学。是否有任何“位摆弄”或类似的确定性转换方法？

编辑：在这种情况下确定性假设为：给定相同的浮点数据在不同平台上实现完全相同的转换结果。

我已设法将其归结为以下测试用例，但我想知道这是否是 C# 代码合同中静态检查器的限制，还是我缺少的东西。当我尝试使用一种代码来证明合同时，它会抛出一个不变的未经证实的警告，但是（我认为是）一种证明它可以正常工作的等效方法。

最初我认为这可能是因为我没有使用具有 Pure 属性的对象（因此代码合同无法评估属性是否是确定性的）而是在对象周围创建了 Pure 包装器（恰好是Nullable<Int64>）没有帮助。

第一个和第三个测试用例之间是否有区别，或者我认为它们是等价的是否正确，只是静态检查器无法正确评估第三种情况？

在工作中，我们正在讨论一个新平台的设计，其中一位高层管理人员说它需要运行我们当前的代码库（Linux 上的 C），但需要实时，因为它需要在不到一秒的时间内响应各种输入. 我指出：

1. 这并不意味着它需要“实时”，只是它需要更快的时钟和更精简的中断处理
2. 要考虑的关键点之一是正在使用的操作系统。他们想坚持使用嵌入式 Linux，我指出我们需要一个 RTOS。由于内核/用户空间内存分裂，使用 Linux 将阻止“实时”，因此 I/O 是通过文件和套接字完成的，这会引入延迟
3. 我们真正需要确定的是它是否需要确定性（例如，需要在 90% 的时间内在 <200 毫秒内响应输入）。

在我看来，如果第 3 点是真的，那么它需要是一个实时系统，然后第 2 点是最大的考虑因素。

我有信心回答，但后来我在想……别人怎么看？我是在正确的轨道上还是我错过了什么？

“实时”系统和“确定性”系统之间有什么区别吗？除了 RTC 和 RTOS，我还缺少执行真正实时系统所需的任何主要内容吗？

期待一些伟大的回应！

编辑：

到目前为止得到了一些很好的回应，看起来对我的系统和要求有点好奇，所以我会为感兴趣的人添加一些注释：

1. 我的公司卖几千的单位，所以我不想在价格上过分杀戮
2. 通常我们出售主处理器板和独立显示器。还有其他 CAN 设备的附加网络。
3. 该板（当前）运行设备，还充当网络服务器，将基本 XML 文档发送到最终用户的显示器

管理人员希望“快速”（<1s）更新显示器的要求出现在这里，但真正的限制来自于可以通过 CAN 连接的设备。这些设备通常是电机控制设备，其要求包括“必须在 200 毫秒内做出响应”。

我想知道当一个有错误状态时如何合并两个 DFA。具体来说，第一个 DFA 是这样的：

第二个并不重要，但它不需要错误状态，因为在每个状态下都需要一个“a”或“b”。所以我可以很好地使用产品构造，直到我到达状态 q3。假设机器位于 (q3,z)（其中 z 是来自第二个 DFA 的随机状态），然后读取 a。第二个可以愉快地继续，但是第一个 DFA 应该进入错误状态并且不再接受任何输入。因为这是联合，当然不是交集，所以我需要继续模拟第二个，看看它是否达到错误状态。

在构建联合 DFA 时如何显示这一点？