问题标签 [computer-science-theory]

我正在研究一个有趣的问题，即寻找一种更有效的方法来存储人类疟原虫的基因组，我认为获得您的一些见解会很有用！

所以这里是背景信息：假设我们只使用 2 位来存储基因组的所有 4 个核苷酸（A、C、T、G），但由于基因组仍然超长，我们知道它占用了大量空间. 然而，我们知道 80% 的基因组要么是 A 要么是 T——我们如何利用这些知识以更有效的方式存储基因组？

现在我正在玩一些想法：

1. 找到一些方法来编码大字符串 A 或大字符串 T - 这需要超过 2 位，但如果字符串特别大，它可以减小大小。例如，如果“01”是“T”的代码，那么“1101”可能是“3 T”的代码（在前两位之后使用正常的二进制系统）。这将为我们节省两位。
2. 只需将 A 存储为“0”，将 T 存储为“1”，以减少这些字母使用的位数。

还有其他人有什么好的想法可以使这种数据存储尽可能高效吗？我很想听听他们讨论！

贪心找零算法是一种通过选择可用硬币的最高面额来进行找零的算法，直到它达到它试图做出的找零数量。令人惊讶的是，该算法实际上可以以最有效的方式对美国和欧元硬币面额进行更改！

然而，贪心算法有时会因为改变而失败。假设我们有面额 [25,15,1] 并试图赚 31 美分。贪心算法会选择 25,1,1,1,1,1,1（7 个硬币），而 31 美分实际上可以作为 15,15,1（3 个硬币）。

我想知道是否有办法使贪婪算法对包括面额 1 的欧元硬币子集（欧元硬币列表为 1,2,5,10,20,50,100,200）失败。虽然我可以使贪心算法使具有其他值的子集失败，对于欧元硬币的子集，我似乎无法使其失败。

一些资源说，只要最高元素加上最低元素小于第二高元素的两倍（因此在上面的示例中，25 + 1 < 15 + 15），贪心算法就会失败，但是没有办法做到这一点可以用欧元硬币的一个子集。

将字符串解释为Z ≥0二进制中的数字（可能带有前导零，这里没有模运算）。以下语言{0, 1}是否正常 {xyz : |x| = |y| = |z| and x + y = z}？

我认为为了证明这种语言的非规律性，我应该应用 Pumping Lemma 并证明不存在满足所有三个 Pumping lemma 条件的可能设置。

我已经阅读了包括关于图灵机的维基百科在内的文章。这里还有关于图灵机的问题。读完之后，我对 TM 的理解是它只是一个具有无限磁带、R/W 磁头和一个带有规则的表的逻辑机器。如果这是真的，没有那个表，图灵机就什么都不是。即使是一台简单的计算机也可以完成从简单的文字处理到玩游戏的所有工作，但图灵机与计算机相比又如何。

这只是一个实验而不是我需要做的实际事情

试图/x:\[((\d),?)*\]/

字符串示例 {x:[1,2,3] y:[5,6,7]} {x:[99,32,67,57,83] y:[5,6,7]} 是否可以使用单个正则表达式解析出数组 x 中的值。我尝试过使用捕获组，但它们只捕获最后一场比赛？

这是不是用正则表达式可以完成的事情，还是上下文无关？

我尝试过对量词进行懒惰和贪婪的评估，但没有运气。这就像我希望它对字符串的一部分贪婪而对其他人懒惰。

2遍就可以轻松完成。首先提取 x 并提取值。这是否意味着它可以一次性完成？（我的猜测不是因为你可以对一个使用惰性量词而对另一个使用贪婪）

我很好奇为什么大多数分布式计算抽象都是建立在由crash-stop process abstraction、perfect link abstraction和perfect failure detector abstraction. 为什么不建立在更类似于真实世界的故障恢复抽象之上，我认为它由crash-recovery process abstraction、logged perfect link abstraction和组成eventually perfect failure detector abstraction。

例如，perfect failure detector abstraction是基于synchronous system现实世界更像是partial synchrony。为什么我们不在类似的东西之上构建更高层次的抽象partial synchrony呢？

在大学里，我刚学了平面图（二维图）。所以，我想知道是否有可能存在空间图（3 维图）。

我一直在尝试从 A2OJ 2C 梯子：Fox and Box Accumulation解决这个问题：

Fox Ciel 在她的房间里有n 个盒子。它们具有相同的尺寸和重量，但它们可能具有不同的强度。第i ^个盒子在其顶部最多可以容纳x _i个盒子（我们将x _i称为盒子的强度）。

由于所有盒子的大小都相同，因此夏尔不能在某个盒子的顶部直接放置一个以上的盒子。例如，假设 Ciel 有三个盒子：第一个有强度 2，第二个有强度 1，第三个有强度 1。她不能同时将第二个和第三个盒子直接放在第一个盒子的顶部。但是她可以把第二个盒子直接放在第一个上面，然后第三个盒子直接放在第二个上面。我们将这样的盒子结构称为一堆。

Fox Ciel 想用所有的箱子堆起来。每堆从上到下都会包含一些盒子，在第 i 个盒子的顶部不能有超过x i_个 ^盒子。她需要建造的最少桩数是多少？

输入

第一行包含一个整数n ( 1 ≤ n ≤ 100 )。下一行包含n 个整数x ₁ , x ₂ , ..., x _n (0 ≤ x _i  ≤ 100)。

输出

输出一个整数——可能的最小堆数。

我有一个贪婪的解决方案，但我无法严格证明它。这就是为什么我需要你们的帮助！

我的算法如下（非常直观）：

1. 对 input_array 进行排序。

2. 初始化一个名为 pile_array 的数组。

3. 从上到下开始建桩，即先从最低强度开始。我选择 input_array 中强度最低的框，然后将其从 input_array 中删除，并将其添加到 pile_array。

4. 然后，在步骤 3 中删除元素后，我从 input_array 中的剩余元素中检查下一个强度最低的块，并查看是否可以将其添加到 pile_array 以形成有效堆。如果可以，就去做。否则继续。（此步骤中选择的元素当然可能具有与添加到 pile_array 中的最后一个元素相同的强度。）

5. 然后我对该元素重复步骤 3，即在 pile_array 中添加元素并从 input_array 中删除它。

6. 在我们无法再填充 pile_array 之后，我将一个已预初始化的计数器增加 1。然后我清除 pile_array（以便我可以重用它）。

7. 对输入数组的所有剩余元素重复此过程。

8. 然后我输出答案作为计数器。

该实现具有 O(n^2) 复杂度。

现在主要问题是：我无法证明我的算法给出了最佳大小的解决方案。我尝试了以下方法：

1. 通过交换证明任何最优解都可以转化为上述构造的贪心解。失败是因为我无法在非贪婪解决方案中获得任何有用的结构......

2. 通过“贪婪总是领先”方法证明：到目前为止，我的主要思想是，任何不完全相同的最优解都小于所有块的最大“强度/容量使用”。但我无法正式化我的论点。

我很想有人给我一个关于算法证明的提示。请帮忙，因为我无法继续我的生活，直到我证明这个问题是因为强迫症:(。

简单评论一下：我刚刚检查了传奇大师游客 (Gennady Korotkevich) 在比赛期间实施了相同的算法。刚才我也实现了上面的算法，得到了Accepted。所以放心，这个算法是正确的。

如何设计一个可以识别平衡括号串的图灵机？例如 （（））（）。

我以为我理解稳定匹配，但对配对真的很困惑，有人可以帮我简单地理解这一点吗？