问题标签 [deterministic]

我想在mathematica中创建一个模块，如果自动机是确定性的则返回。我正在考虑，如果有 2 个转换从同一状态开始并读取相同的符号，或者存在一个空转换，则自动机不是确定性的。

我想调试这段代码，但我不能：

A 是一个自动机，其中第一个元素是状态列表，第二个是字母表，第三个是转换，第四个是初始状态，第五个是最终状态列表。

主要问题是，当我将函数应用于 A 时，它永远不会结束。

编辑：已解决

这是最终代码：

增加/减少标准库集合（例如 std::map）的迭代器所需的时间是否有上限？（假设容器本身没有改变。）

我是学生，在我的编程课程中，我们必须学习 Haskell。所以我是新手，我没有那么多经验。另外我不熟悉在论坛上发布问题。

所以首先我会发布图书馆，我必须与之合作。（DA：确定性自动机）

toDA 函数在其列表表示中采用自动机并将其转换为自动机。此功能和图书馆的其余部分由讲座主席提供。

现在的问题是写一个类型的函数

该函数接受一个自动机、一个状态和一个字符串，并在读取字符串后返回自动机的状态。

到目前为止，这个想法很清楚。DA 型自动机有一个状态转移函数增量。所以函数“advance”必须以某种方式调用那个 delta 函数。但是我怎样才能访问一个集成在一个类型中的函数呢？

There are 3 popular beach resorts, A, B, and C, which reside on a line:

The distances between the resorts is 1k. John owns an ice-cream truck located in beach resort A and another located in beach resort C. Two busses full of ice-cream-craving children will arrive at the beach resorts (A, B, and C) tomorrow, but John does not know for which resort each bus is headed and when each bus will arrive (the busses can arrive at different times). He plans to dispatch an ice-cream truck from its current location to a beach resort as soon as a bus arrives at that resort. Each truck can only serve a single beach resort, that is, once a truck is dispatched to a beach resort it must remain there all day. John wants to design an algorithm that minimizes the sum of distances his trucks traverse in order to reach the busses’ locations.

Show that for every deterministic algorithm ALG, there is some scenario (i.e., schedule and locations of bus arrivals) in which the total distance John’s trucks traverse under ALG is 3OPT, where OPT is the value of the optimal solution in that scenario.

我正在为 iOS 开发一个带有 Box2D 物理的多人游戏。多人游戏像往常一样使用锁步方法。游戏定时更新物理世界。具有相同 CPU 的 iOS 设备之间不存在不同步。

但是，在使用 Apple A6 芯片的新 iOS 设备进行测试时，发生了不同步。查看我的日志文件给我的印象是异步发生的速度非常快，这可能是因为一些浮点操作我还没有找到。

我可以保证只有Box2D是游戏设计中唯一需要同步的模块，根据我的日志，所有的多人游戏命令和输入都没有不同步。

我尝试将所有超验函数：sinf、cosf、pow、sqrtf、atan2f 更改为双版本，但没有任何运气。

有什么方法可以强制 Apple A6 将浮点数与 Apple A5 一样处理，就像某些编译器选项一样？

我将非常感谢任何答案。

在我的一项学校工作中，我需要使用确定性算法 (http://en.wikipedia.org/wiki/Deterministic_encryption) 来加密几个字段。

在这种特定情况下，我必须用布尔值加密一个表。这很好，除了使用确定性算法这样做几乎没有用处。

为什么呢？（你可能会问）

碰巧当我加密（例如）值“true”时，我总是得到“AB1”的密文，而当我加密值 false 时，我总是得到“SQ2”的密文。因此，我没有用值“真”和“假”填充表，而是用值“AB1”和“SQ2”填充表。任何攻击者都会立即明白我的表存储布尔值，他很快就会发现 AB1=true 和 SQ2=false。

这是我想在作业中防止的。为了避免这个问题，我尝试使用具有某些属性的数字。例如，“真”的值被一个素数替换，而“假”的值被一个非素数替换。因此，我的表将充满许多不同的素数和非素数。

如果不是为了一件小事，这将是一个可以接受的解决方案：我们可以计算的素数是“有限的”（计算大素数需要很长时间）。在 10000000 个数字的区间中，只有 664579 是素数（只有 6.64579% ）。

所以我考虑使用奇数而不是质数，但我不确定奇数的质量。我认为攻击者将能够从密码中检索“奇怪”的属性，从而进行攻击。

我对奇数的假设正确吗？还有其他解决方案吗？你们有什么想法吗？

我真的很感激任何帮助或想法，提前佩德罗。

我在一个非常规范的环境中工作，我们需要能够生成相同的二进制输入，每次构建产品时提供相同的源代码。我们目前使用的是一个古老版本的 g++，该版本已被修补，不会在生成的二进制文件中写入日期/时间之类的东西，这些二进制文件会随着构建而改变，但我想更新到 g++ 4.7.2。有谁知道补丁，或者对我需要寻找什么来获取两个相同的源代码并产生相同的二进制输出有什么建议？

我对这些东西真的很陌生，所以我为这里的noobishness道歉。

构造一个Deterministic Finite Automaton识别以下语言的 DFA：

每个部分的自动化(at least 2 a's, odd # of b's)很容易单独制作......谁能解释一种将它们组合成一个系统的方法？谢谢。

我试图找出在三种情况下接受重复字符串（ww）的图灵机的时间复杂度：1 磁带确定性机器、2 磁带确定性机器和 1 磁带非确定性机器。

现在我的想法是

• 1-tape 确定性机器需要 O(n^2) 来找到中点（通过重复删除输入中的第一个和最后一个符号）和 O(n^2) 来比较前半部分和后半部分（因为它必须来回 n/2 次，每次通过 n/2 的字符串），

• 2-tape TM 需要 O(n^2) 找到中点，O(n) 将后半部分复制到第二个磁带，然后 O(n) 同时比较两半，

• 而不确定的人猜测中点并取 O(n^2) 来比较两半。

但是，我觉得这三种情况不应该都具有相同的 O(n^2) 时间复杂度，所以想知道我的推理是否在某个地方不正确（或者我是否正确并且只是在思考这个问题）。任何输入将不胜感激！

我想做一些随机播放，每次运行我的程序时都是一样的：

这是一种方法：

但是评估需要一段时间，而且看起来很浪费而且相当不雅。

是否有某种方法可以直接生成 shuffle 39038，而无需生成和消耗所有序列？

（我已经意识到我可以对它们进行硬编码，或者用宏将精力带回到编译时间。这也似乎有点垃圾。）