问题标签 [computation-theory]

我试图最小化这个 DFA：http: //img145.imageshack.us/img145/3006/dfac.png

这是我最小化的 DFA：http: //img195.imageshack.us/img195/4131/mdfa.png

我对么？谢谢

PS-这是作业。我们可以讨论家庭作业。我不是在问答案，我只是想知道我是否走在正确的轨道上，因为这是我第一次处理状态机。

我在理解机器识别和决定语言的含义时遇到了一些麻烦。我认为我接近定义但不正确。

当有人说图灵机T识别语言L时

其中 DFA = 确定性有限自动机

我的理解是，这意味着可以构建一个图灵机，给定任何类型的输入（字符串、汽车、人，等等！）将能够告诉你你作为输入提供的东西是否是 DFA . 我的意思是，将始终接受 DFA 并始终拒绝非 DFA 输入。

也就是说，如果该输入是L. 另一个例子是说那个人 X 是他父亲的识别者，因为无论你放在他面前的东西是什么，他都能告诉你他面前的东西是否是他的父亲。这个对吗？哪一部分不正确？

另一方面，a deciderover a 语言似乎是一个图灵机，它永远不会loops，也就是说，对于任何输入，它总是会在接受或拒绝状态下停止。这与我上面关于识别器的解释是否相似或相同？

谢谢

L={ww|w 属于 {0,1}*} 的补集的 CFG 是多少？

这样的事情存在吗？如果是这样，你能举个例子吗？谢谢。

在谈论时间复杂度时，我们通常使用n作为输入，这并不是对实际输入大小的精确度量。我无法证明，当对输入（s）使用特定大小时，算法保持在相同的复杂度类中。

例如，采用一个简单的顺序搜索算法。在最坏的情况下，它需要 W(n) 时间。如果我们应用特定的输入大小（以 2 为底），则顺序应该是 W(lg L)，其中 L 是最大整数。

我如何证明顺序搜索或任何算法保持相同的复杂性类别，在这种情况下是线性时间？ 我知道需要进行某种替代，但我对如何得出结论感到不安。

编辑

我想我可能已经找到了我正在寻找的东西，但我并不完全确定。

如果将最坏情况的时间复杂度定义为 W(s)，即输入大小为 s 的算法完成的最大步数，则根据输入大小的定义，s = lg n，其中 n 是输入。那么，n = 2^s，得出时间复杂度为W(2^s)，指数复杂度的结论。因此，二进制编码的算法性能是指数的，而不是线性的，因为它在数量级上。

我需要开发一个在特定时间（每 15 分钟）运行作业的网站，我将使用 cron 来运行网页。

存储工作信息的最佳方式是什么？一些工作将每天进行，另一些工作则每 8 小时一次等。更复杂的是，我还需要考虑时区差异。这应该不会太难，因为 PHP 有很多时区函数，但是我如何将它集成到下一个要运行的作业的编程中呢？

另一个问题是，用户将如何输入信息以运行作业？一种类似于http://www.webcron.org的选项是要求用户选择作业必须运行的频率，但我如何将该信息存储在数据库中？

任何帮助将不胜感激！

我一直在努力应对 Greplin 挑战的第 3 级。对于那些不熟悉的人，这里是问题：

您必须找到数组的所有子集，其中最大数字是剩余数字的总和。例如，对于以下输入：

(1, 2, 3, 4, 6)

子集将是

1 + 2 = 3

1 + 3 = 4

2 + 4 = 6

1 + 2 + 3 = 6

这是您应该在其上运行代码的数字列表。密码是子集的数量。在上述情况下，答案是 4。

3、4、9、14、15、19、28、37、47、50、54、56、59、61、70、73、78、81、92、95、97、99

我能够编写一个解决方案，构建所有 400 万个以上 22 个数字的组合，然后对它们进行测试，这将使我得到正确的答案。问题是它需要 40 多分钟才能完成。在网上搜索，似乎有几个人能够编写一个算法来在不到一秒钟的时间内得到答案。任何人都可以用伪代码解释比计算昂贵的蛮力方法更好的方法来解决这个问题吗？快把我逼疯了！

我需要一个 CFG，它将生成除回文以外的字符串。已经提供了解决方案，如下所示。（计算理论导论-Sipser）

我大致了解了这个语法是如何工作的。它要求通过产生式插入一个在其任一半具有相应不相等字母的子字符串S -> aTb | bTa，从而确保永远不会生成回文。

我将按照我的理解写下前两个产生式的语义，

• S生成不能是回文的字符串，因为它们的第一个和最后一个字母不相等
• R由至少一个S作为子字符串组成，确保它永远不是回文。

我不完全理解第三个产生式的语义，即 .

在我看来，T 可以生成 a 和 b 的任意组合，即 {a, b}*。为什么它不能像

两者不是等价的吗？由于后者更直观，为什么不使用它？

考虑一个从训练集训练的机器学习算法，在 PAC 学习模型的帮助下，我们获得了所需训练样本大小的界限，因此错误受限（通过 epsilon）的概率是有界的（通过 delta）。

PAC 学习模型对计算（时间）复杂性有何看法。假设一个学习算法有更多的时间（比如更多的迭代），错误和错误被限制的概率如何变化

作为一种需要一小时训练的学习算法，在金融预测问题中没有实际用途。我需要性能如何随着给定算法的时间变化而变化，包括误差范围和误差有界的概率是多少

您如何确定特定字母表上有多少不同的转换图？例如，字母表 {x, y} 上有多少个 TG。我正在上一堂课，上面有 Daniel IA Cohen 的书“计算机理论导论”中的类似问题。有很多关于如何创建 TG 的示例，但无法确定每种语言可以创建多少个。我假设我正在寻找有限数量的 TG？非常感谢！