问题标签 [computer-science-theory]

我正在实现一个数据库搜索算法，它搜索 MongoDB 中的许多集合并根据整个数据库的状态返回优化的结果。我对实现没有任何问题，但是命名法和我应该如何构建文件系统让我很烦。我应该在模型-视图-控制器模式的哪个位置放置只读操作？是服务吗？它有一个控制器，但我认为它几乎不符合成为模型的标准。

我们总是听说死锁的必要条件之一是互斥，一次只能有一个线程持有锁。

但是，我认为非互斥锁可能导致死锁是不是错了？

考虑一个信号量的简单情况，它最多允许两个线程来保存它。假设我们有两个 2 信号量，A 和 B。假设我们有 4 个进程，进程 A1、A2、B1 和 B2。

假设进程 A1 和 A2 各自获取信号量 A，进程 B1 和 B2 获取信号量 B。如果我们达到 A1 和 A2 都想要信号量 B，而进程 B1 和 B2 都想要信号量 A，每个进程都没有放弃它们当前的锁，就会出现死锁，因为信号量只能由两个进程持有。但是信号量允许两个进程持有它，所以它不是互斥的！

有人可以解释这是不是错误的推理，还是我对互斥的解释是错误的？

也许这更像是一个范式/哲学问题，但我想知道很长一段时间“如果你安装 PHP，你会安装什么？” 是解释器/编译器还是语言结构（函数、语法元素等）还是完全不同的东西？

我不是php专家，也没有计算机科学，所以我很难真正理解......

我对自动机理论感兴趣，以提高我对编程和编译器设计的理解（我想在自己的项目中创建一些简单的语法，例如；L-Systems、AI、神经网络结构和智能对象-对象对话'AI对话'）但在我继续前进之前我需要学习一些东西。

在学习自动机理论之前，我需要学习很多新的符号和数学概念，由于符号的原因，我无法复制和粘贴示例，而且我没有发布图像所需的声誉，所以听到了 wiki 的链接文章。

维基百科上的上下文无关语法文章

在“正确的 CFG”标题下，您可以看到一些定义。我不明白他们。有人可以告诉我这个符号叫什么，所以我可以谷歌它。任何其他指示或信息也会有所帮助，但只知道几个关键词会有所帮助。此外，如果有人知道可以免费访问的综合资源，例如关于该符号主题的 IIT 视频讲座，我将永远感激不尽，因为我现在负担不起辅导甚至课本。

我目前用于自动机理论的资源（对于任何感兴趣的人）是YouTube 上的自动机 IIT 讲座理论。

我一直在研究旅行商问题，我有一个关于它是如何制定的问题。或者这可能是关于分类或子问题名称或问题变体的问题。

在旅行商问题中，城市在空间中的位置以及城市之间的距离被测量以形成具有加权连接的图，或者可以任意选择边缘上的权重，即使它们可能使城市无法布局在地图上？

如果其中一个被认为是标准的旅行推销员问题，那么另一个有名称吗？

最终，我想将以下 CFG 转换为乔姆斯基范式：

但是，我不确定我是否正确地进行了推导——这就是我所拥有的：

用终端替换非终端

有人可以告诉我这是否正确/在正确的轨道上吗？

谢谢你。

我需要为由具有相同数量的 a 和 b 的偶数长度回文组成的语言构造一个 CFG，然后证明它生成了该语言。

这是我得到的CFG：

S→ 阿巴 | 巴布| abSba | 巴萨布 | ε

我不确定该怎么做才能证明它（我只是在逻辑上想出了这个）......如果有人能指出我正确的方向，我将不胜感激。谢谢！

这个问题是关于解决方案之间是否存在一些抽象的相似性，导致出现排序和搜索等登录问题。或者，更简单地说，为什么 log 在算法复杂度中如此频繁地出现？

所以我有以下问题：

有k商店和n物品。每个商店都可以以不同的价格购买这些商品（有些商店没有所有商品）。但是如果你想在特定的商店购买，你必须支付一次性费用，每个商店都不一样。如何找到购买所有物品的最便宜方式？

我现在唯一的解决方案是尝试所有可能的商店组合并寻找最便宜的。有没有更好的方法或一些启发式近似？

我有一台带有下表给出的转换的图灵机

我正在输入字符串 aaaa。因此，如果我查看状态 A 中的第一个符号“a”，它表示将其替换为 X，进入状态 B，然后向左移动。这就是我感到困惑的地方。如果我正在查看第一个输入符号，如何向左移动？我只是去一个空白符号吗？

谢谢！