问题标签 [computation-theory]

我最近被要求创建一个程序来查找文本片段中的最佳匹配。我已经成功编写了这个程序，但我对它的时间复杂度有疑问。

问题定义如下。

给定查询，在文档中查找查询词的出现并突出显示最佳标记。

我的程序花费的时间

O(m + n + p)

这里

m = 文档长度（以字符为单位）

n = 查询的字符长度

p = 文档中的总匹配数

在这种情况下，最大的术语总是“m”，因为在大多数情况下，文档会比查询本身大。

我可以安全地推断出我的程序的时间复杂度是 O(m) 吗？

可能重复：
比较浮点值 比较浮点值
有多危险？

我不明白，为什么在编程中比较实数是一种不好的做法？当然，我知道实数可以用某种精确度来表示。你能给我解释一个不比较这种数字的重要理由吗？例子会很好，文章也很受欢迎。预先感谢。

我需要帮助解决我在计算课程模型中遇到的几个硬件问题。我阅读了文本中的相关章节（Michael Sipser's Introduction to the Theory of Computation），但我觉得这些硬件问题需要这本书没有给我的知识......第一个问题是：

(1) 证明不存在这样的语言 L 使得 L* = {a}* {b}* 提示是使用矛盾。

显然右边是正则表达式；零个或多个 a 后跟零个或多个 b。这也可能是空字符串 epsilon。

我的麻烦来自于 L*。由于语言 L 上的 *，我完全不知道应用于语言的 * 是什么，或者如何使用这个等式。

对此问题的任何帮助或资源将不胜感激。

=====

第二个问题比较简单，感觉差不多可以了。我可以为自己辩护，所以我想问题是正式写出来。第二个问题是这样的：

(2) 证明如果 A 和 V 是相同字母表 (sigma) 上的语言并且 A（是 B 的子集），那么 A*（是 B* 的子集）。提示是使用归纳法。

现在显然（例如）如果 sigma = {1, 0}

A = {00, 01, 10, 11}

B = {00, 01, 10, 11, 100, 101, 110, 111}

然后 A* 中的任何内容都在 B* 下关闭，因为 B = A + 其他一些东西......如果有人可以帮助我将其形式化为归纳形式，我将不胜感激。

谢谢

想象一块立方体形状的瑞士奶酪。我们通过 20x20x20 的网格对奶酪进行建模。为简单起见，我们假设每个网格立方体完全由奶酪或完全由空气组成。然后我们在瑞士奶酪立方体的上侧倒入水，水只能通过立方体中的气孔渗入奶酪。水可能会从顶部流到底部的连续通道，但如果两个立方体通过面（不仅仅是边缘或角落）连接，它可能只会从一个空气立方体流到下一个空气立方体。水也可以在弯道上流动，例如在水槽排水管中，但它可能不会在奶酪块的侧壁上流出。

现在让我们以编程方式实现瑞士奶酪的模型，如上所述，空气和奶酪块的随机分布，奶酪的概率为p，空气的概率为1 - p，并模拟水流过奶酪，以找出，水是否流到瑞士奶酪块的底部。

通过以不同的奶酪和空气概率反复模拟流过瑞士奶酪立方体的水，我们可以确定 p 与水流到瑞士奶酪立方体底部的概率之间的关系，我们将其命名为q。结果如下所示：

我的问题：为什么会有这么奇怪的曲线？

本题摘自德国第 23 届联邦信息学竞赛（2004/2005）。网络上没有提供“为什么这么奇怪的曲线”的答案（提供的解决方案）。

我希望我在正确的地方提出这类问题。

我正在尝试构建一个使用正则表达式之类的工具来查找字符串中的模式（不是文本字符串，但这现在并不重要）。我熟悉自动机理论，即我知道如何实现基本的正则表达式匹配，如果字符串匹配我的正则表达式，则输出真或假，通过以教科书的方式模拟自动机。

假设我对 s 之前的所有as 感兴趣，在 s 之前b没有更多a的bs，所以，这个正则表达式：a[^a]*b。但我不只是想知道我的字符串是否包含这样的部分，我想将 . 作为输出a，以便我可以检查它（请记住，我实际上不是在处理文本）。

总结：假设我a用括号标记 ，如下所示：(a)[^a]*b然后在输入字符串上运行它，bcadacb然后我想要第二个a作为输出。

或者，更一般地说，可以找出输入字符串中的哪些字符与正则表达式的哪一部分匹配吗？它是如何在文本编辑器中完成的？他们至少知道比赛从哪里开始，因为他们可以突出显示比赛。我必须使用回溯方法，还是有更智能、计算成本更低的方法？

编辑：正确的反向引用，即用括号捕获和用 \1 引用等可能不是必需的。我确实知道反向引用确实需要回溯（或类似的东西）并使问题（IIRC）NP-hard。从本质上讲，我的问题是：在没有反向引用的情况下，捕获部分的计算成本是否比正确的反向引用低？

我正在寻求解释如何证明计算模型是等价的。我一直在阅读有关该主题的书籍，但省略了等价证明。我对两个计算模型等效意味着什么有一个基本概念（自动机视图：如果它们接受相同的语言）。是否有其他思考等价的方法？如果你能帮助我理解如何证明图灵机模型等价于 lambda 演算，那就足够了。

众所周知，C++ 模板是图灵完备的，CSS 是图灵完备的（！），并且C# 重载解决方案是 NP-hard（即使没有泛型）。

但是 C# 4.0（具有协/逆变、泛型等）编译时图灵是否完整？

我正在研究优先级队列，它使用二进制堆作为其内部数据结构。考虑到块大小为 M 的外部存储器模型，幻灯片声称 deleteMin 需要大约2log(n/M)块访问。

为什么是这样？我在描述自下而上启发式（Wegener 93）的原始论文中找不到解释，在幻灯片中也找不到。

第一个块包含堆的根和第一个 log(M) 级别。之后，对于每个节点，它必须在每个级别读取一个块，其中将包含两个连续的子节点。只有在极少数情况下（因此是“近似值”）它才必须读取两个块来获取节点的两个子节点。由于将使用单个块访问读取第一个 log(M) 级别，因此它只需加载最低(log n - log M) = log n/M级别的块。

从哪里来2？它必须在缓存驱逐时将块写回磁盘，但这通常不是与负载有关吗？

我希望我已经很好地解释了这个问题。非常感谢！

我四处寻找有关 Big-Theta 的信息，我想我已经对它有了一个不错的理解。然而，问题仍然存在：当预期输入大小较小时，Big Theta Notation 是否是算法效率的有效衡量标准？

我认为当预期输入大小很小时，Big Theta Notation 不是算法效率的有效度量。首先是我对 Big Theta 的部分理解：如果函数 f(n) 是 O(n) 和 Big Omega(n)，那么它就是 Big Theta(n)。所有这些值的数学定义要求 n>n0。因此，根据我的推理，小输入大小有可能（并且很可能）小于 n0。因此，我的推理是，对于 n< n0 的值，Big Theta Notation 不是算法效率的有效度量。

根据维基百科，我正在尝试理解NP、NP complete和NP hard的概念。

如果我正确理解给定的文本：

编辑：根据大卫更正

NP == 决策问题，其答案可以在多项式时间内得到验证（给定解决方案）

NP 完成== NP和NP 困难同时

NP 难== 存在一个NP 完全问题，它是多项式时间图灵可约简到它。

所以为了理解NP完整性的概念，我需要先了解NP硬度。所以我试着根据上面的说法来分析一下什么是NP难。所以我得到：

NP hard == 有一个问题是NP hard 和NP同时存在的，可以归结为它。但是定义中有一个循环。什么是非周期性定义？