标签: computation-theory

在大学学习期间,我必须学习很多关于计算理论的知识.我研究了三个学期的主题.我很难过,我不得不承认我忘记了很多.

我想知道这是个人问题,还是我们只需要学习很多(或多或少)无用的东西.

所以我的问题是:您认为计算理论领域中哪些主题最重要,哪些部分值得学习,以及您在正常工作中使用哪些主题？

就个人而言,我很高兴我听说过语言理论(尤其是常规语言=>正则表达式 - 当它们可以应用时,何时不应用)以及不同的时间(和空间)复杂性,特别是O(n)符号.

但我们还要研究更多,包括:

• 可计算性理论
  • 停止问题
  • 半昏人问题
• 复杂性理论
  • P = NP？
• 逻辑理论
  • 命题演算
  • 谓词逻辑

听到这些话题很有意思,但我不确定深入研究它们是多么必要.

我知道这个问题是主观的,答案会因您的日常工作和个人经历而有很大不同.但是我想知道可能比我记忆中更有趣的主题.

我一直在努力应对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

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

在使用泵浦引理检查给定语言是否规则时,我有点困惑.

假设我们必须检查是否:

L. 语言是否接受0常规或非常规的语言？

我们知道这是常规的,因为我们可以为L构建DFA.但我想用抽取引理来证明这一点.

现在假设,我拿一个字符串w= "0000":

现在,将分字符串x = 0,y = 0和z = 00.现在应用泵浦引理i = 2,我将得到字符串"00000",这是我的语言不存在所以通过引入引理证明语言不规则.但它被DFA接受了吗？

任何帮助将不胜感激,
谢谢

在正式语言的乔姆斯基分类中，我需要一些Non-Linear, Unambiguous and also Non-Deterministic上下文无关语言（N-CFL）的例子吗？

1. 线性语言：对于哪些线性文法是可能的（？CFG）例如
   L ₁ = {a ⁿ b ⁿ | ? 0 }

2. 确定性上下文无关语言（D-CFG）：对于哪些确定性下推自动机（D-PDA）是可能的，例如
   L ₂ = {a ⁿ b ⁿ c ^m | ? 0，米？0 }
   L ₂是明确的。

非线性的CF 文法是非线性的。
L _nl = {w: n _a (w) = n _b (w)} 也是一个非线性 CFG。

-- 3. Non-Deterministic Context Free Language(N-CFG) : 对于哪个only Non-Deterministic Push-Down-Automata(N-PDA)是可能的，例如
L ₃ = {ww ^R | ? {a, …

我在理解位反转算法方面取得了一些进展，使用基于 D.Knuth 的想法的非平凡（二进制分区）魔术常数，但我无法理解这些非连续掩码是如何工作的，这些掩码似乎在不同的距离上散布着位。它总是一个两步过程，交换 lsb 和 msb 位，中间保持不变，但它同时在寄存器的多个部分执行此操作。LUT、基于x86 asm的位反转属于微不足道的类别，因此认为它们无关紧要。

经典二进制（递归）分区位反转算法 64 位（平凡）

x = ((x >> 1) & c1) | ( (x & c1) << 1); //0x5555555555555555ULL
x = ((x >> 2) & c2) | ( (x & c2) << 2); //0x3333333333333333ULL
x = ((x >> 4) & c3) | ( (x & c3) << 4); //0x0F0F0F0F0F0F0F0FULL
x = ((x >> 8) & c4) | ( (x & c4) << 8); //0x00FF00FF00FF00FFULL
x = ((x >>16) & c5) | ( …

我想知道一个算法的复杂度和一个问题的复杂度之间的区别，也就是这两个东西的不同点

今天是个好日子！

我正在尝试解决这个练习以达到学习目的。有人可以指导我解决这 3 个问题吗？

就像我尝试了第一个问题，将两个由“+”分隔的二进制数相加。我尝试通过用相应数量的 1 或零表示每个数字来进行 2 个数字加法，例如 5 = 1 1 1 1 1 或 0 0 0 0 0，然后将它们相加，结果也将采用与所表示的相同的格式，但如何添加或表示 2 个二进制文件并用 + 分隔它们，但没有得到任何线索。图灵机的头会从左边移动到+号，然后再向+号左右移动吗？但是添加将如何执行。就我所知而言，TM 不能简单地添加二进制数，我们必须制定一些逻辑来表示其二进制数，就像简单地添加 2 个数字的情况一样。比较两个二进制文件的情况是否相似？问候

是否有一种算法可以解决以下决策问题：

给定一个G由其转移矩阵定义的强连通加权有向图，是否存在一个G没有负循环的强连通生成子图？

的强连通生成子图G是与G共享相同顶点的强连通子图G。您可以查看本文以了解强连接生成子图的定义。在本文中，他们提出了最小强连通子图问题的近似。

解决这个问题的一个简单方法是使用 Ford-Bellman 或 Floyd-Warshall 算法找到图的负循环，从这个循环中删除一条边，并在图仍然强连通时重复。但是这种简单的方法时间复杂度很低，因为我们可能会运行福特贝尔曼算法并多次检查强连通性——而且我无法证明这个算法是否在所有情况下都是正确的。

我希望在这里找到专家，他们可以告诉我这个决策问题是否可以在多项式时间内解决，以及什么算法可以解决这个问题。提前谢谢了。

Datalog不是图灵完备的。

但它的计算类是什么？

它相当于有限状态机或下推机（即上下文无关）……还是介于两者之间？

给定两种非常规语言，它们的联合是正规的吗？

另外，为什么 L = L ₁？L ₂ = {a ⁱ b ^j | i,j >= 0} L ₁ = {a ⁱ b ^j | 的并集 i >= j} 和 L ₂ = {a ⁱ b ^j | 我<j}？

那么，L ₁ = {a ⁱ b ^j |的并集是什么？i > j} 并且 L ₂ = {a ⁱ b ^j | 我<j}？