问题标签 [computer-science-theory]

我正在阅读有关 lambda 演算的内容。从此处http://www.toves.org/books/lambda/第 2.1 节的末尾开始：

它说

事实上，尽管如此，y 应该达到 3 而不是 5，因为第一次 beta-reduction 应该将 1 插入到表达式中 x 的位置。出于这个原因，惰性参数必须在每次归约时保留当前变量上下文，在这种情况下记住表达式 λy.x × y 内的 x = 3 但在表达式外保持 x = 1 的事实。

但是我对 beta 减少期间的操作顺序感到困惑。不幸的是，这里的解释是模棱两可的。它们可能意味着 x 应该在 (λx.λy.x × y) 内为 1，然后 y = 3 因为这是要传入的下一个参数，并且 x 已经设置（感觉不对），或者我们走下面的路线：

我们是否同意 (λx.(λx.λy.x × y) 3 ((λz.x + z) 2)) 1
与 (λx.(λt.λy.t × y) 3 ((λz. x + z) 2)) 1

x 是一个界限吗？不应该是1吗？

这意味着当我们减少它时： (λt.λy.t × y) 3 ((λz.1 + z) 2)) x = 1 (λy.3 × y) ((λz.1 + z) 2)) x = 1, t = 3 3 × ((λz.1 + z) 2)) x = 1, t = 3, y = ((λz.1 + z) 2)) 3 × ((λz.1 + z) 2)) x = 1, t = 3, y = ((λz.1 + z) 2)), z = 2 3 × (1 + 2) x = 1, t = 3, y = ((λz.1 + z) 2)), z = 2 3 x 3 = 9

那是对的吗？还是我错误地减少了它？

如果算法：如何定义计算复杂度：

• ...产生许多结果？作为一个总数（那么产生一组的算法k不能比O(k)快）或每个元素（那么必须将估计值相乘以将其与不产生集合的算法进行比较）？
  • 存储复杂性如何——估计是否反映了整个集合是否需要一次出现在内存中，或者每个连续元素都可以产生和丢弃？
• ...有多个参数？每个参数的单独数字或组合的数字？

适合这两种情况的示例是k从 中选择元素N。例如，根据是否需要~k或~N需要步骤，估计是否存在差异？

我希望看到一些确凿的证据：这些案例中术语的正式定义和/或如何在 CS 论文中消除这些歧义，而不仅仅是随机的想法和/或个人经验。目标是制定一个完整的、最先进的解决方案，以一劳永逸地消除我（和其他人）文本中的这些歧义。

_{让我对此感到困惑的问题是：O(1) 中的唯一（非重复）随机数？,你如何有效地生成一个介于 0 和上限 N 之间的 K 个非重复整数的列表，用于选择单个值的随机组合的算法？,有效地从链表中选择一组随机元素。}

给定两个数组：

计算两个数组x, y中满足x之前条件的元素个数。y

目前进展：

按索引对数组进行排序。例如，这将是：

并将每个元组与另一个元组进行比较。如果元组a的两个索引都低于或高于 tuple b，则增加满足条件的元素数。

这有(N^2)/2的时间复杂度，所以O(N^2)，太慢了。我知道没有更好的最坏情况复杂性，但我最感兴趣的是平均结果。那么：有没有更好的方法/算法？

我想过使用传递属性（如果两者都(x,y)满足(y,z)条件，那么(x,z)也满足它），但没有运气。

测试用例

对于数组：

满足条件的对是：

对于数组：

满足条件的对是：

我注意到 AND、OR、NOT 这三个逻辑门在功能上是完整的，这意味着我只能通过这三个门来表示任何真值表。

所以，我想知道我是否只能用这三个门来表示任何可计算的函数？

这是问题所在：

这是我第一次遇到它时的推理路线：

• 这个好像很难
• 为其查找正则表达式似乎很棘手，因此我无法按照此路径将正则表达式转换为 DFA
• 所以我决定解决问题的第一部分：接受一个“a”个数是 3 的倍数的字符串。这很简单，你只需要 3 个状态：1、2、3，以 1 为起始状态，如果有输入'a'，则进入下一个，如果是'b'，则停留在该状态，并且开始状态也是完成状态。但在本练习中，这 3 个州实际上是 3 个“大”州。然后问题就变成了设计这些“大国”的内部结构以及它们如何相互作用。

我别无选择，只能使用猜测来得出解决方案。这是我想出的（1,2,3 是完成状态，3 是开始状态，如果收到输入“a”，7 和 9 都变为 1）： 我还使用了 DFA 最小化，并发现它已经很小了。但是，教科书给出了另一种解决方案：

但我不明白它是如何正确的！我只是想不通:(。我什至不知道我的解决方案是否 100% 正确。请帮助我，非常感谢 :)

我的问题是关于最大流量和最小切割算法。我想知道为什么最大流量和最小切割之间有很强的对偶性？

我最近开始研究图及其不同的遍历算法，似乎无法回答这个问题。我真的需要你的帮助，我什至不知道从哪里开始。PS昨天是我的生日，我不想因为这个问题而哭泣。

纽约的一家公司生产汽车用蓝色卤素灯泡。不幸的是，很难始终如一地给灯泡着色。当然，将看起来相似的灯泡成对包装也很重要。为了成对包装灯泡，从装配线出来的灯泡首先被分成两组共享相似颜色的灯泡（例如，一组较暗的灯泡，另一组较亮的灯泡），然后在每组内形成对。

由于需求增加，公司希望雇佣更多的工人将灯泡分成两组。为了确定申请者是否具备适当的技能来完成这项相当微妙的任务，他们被要求进行这个简单的测试：给定一组 nn 个灯泡，比较每对灯泡并确定两个灯泡的颜色是否“相似”或“不同”。申请人还可以选择对每对说“不确定”。公司希望聘用判断一致的申请人。如果可以将 n 个灯泡分成两组，使得 (i) 对于确定为“相似”的每一对 {a,b}，a和 b 确实属于同一集合，并且 (ii) 对于确定为“不同”的每一对 {a,b}，a 和 b 确实属于不同的集合。

对于给定的n个灯泡的测试结果，m个判断，设计一个O(n+m)-time算法来判断判断是否一致。在实践中，应要求申请人做出最少数量的判断，但您的算法应该适用于任何整数 m≥0。

太感谢了！

我很难用 O 表示法定义以下算法的运行时间。我的第一个猜测是 O(n)，但迭代次数和我应用的次数之间的差距并不稳定。我如何错误地定义了这个？

我现在遇到了这个问题： http ://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3155 问题要求计算冒泡排序算法执行的平均交换次数给定的数据是前 n 个（随机列出的 1 到 n 个）自然数的打乱顺序。

所以，我想：

1. 可能的最大交换次数=n(n-1)/2。（当它们按降序排列时。）
2. 可能的最小交换次数=0。（当它们按升序排列时。）

所以，这个分布的模式是(0+n(n-1)/2)/2 =n(n-1)/4。但是，事实证明这是答案。我不明白为什么模式与平均值一致。

我需要为可以生成包含所有符号的任何短语的语言构建一个 CFG。

我认为这是不对的。有没有办法让它工作，所以它可以生成任何短语？