问题标签 [computer-science-theory]

我知道 Perl 正则表达式引擎的某些功能不是正则的。但是，它是什么类？它可能与上下文无关，但 CS 理论从来都不是我最擅长的学科。

这是我的任务之一。我有一个图灵机模拟，可以模拟一个忙碌的海狸功能。我已经做了一些关于证明这个问题的研究，但仍然没有得到它，所以我想也许你可以在这里帮助我。对我来说，这是一个很好的来源或如何论证这一点的例子。

我试图找回密码。想到这一点，我意识到“密码恢复”问题是 NP 问题的一个很好的例子。如果您知道密码，则很容易在多项式时间内对其进行验证。但是，如果您不知道密码，则必须搜索可能的解决方案的整个空间，这可能会花费指数级时间。

现在我的问题是：这是否表明 P != NP 因为“密码恢复”是 NP 的一个元素，可以证明它需要多于多项式时间才能运行？

在阅读“计算机科学和编程法则”页面后没有找到这条法则，谁能告诉我这条法则是什么？

法律的重点是载体是信息。换句话说，您不能将硬盘上的信息与硬盘的分子结构分开。您无法将雕像提供的信息与雕像的形状和物理结构分开。您无法将大脑中的信息与存储该信息的大脑中神经元的物理结构分开。

多年前我读过法律，但无法在互联网上找到它。你能帮忙吗？

在我们的办公室里，我们有一个办公室男孩（高中毕业（10+2年）），目前学习成绩一般）。他想学习编程。我已经开始教他计算机科学基础知识（计算机科学史、数字系统等），但我没有足够的时间和他在一起（因为我的空闲时间非常有限，更重要的是我不想用勺子喂他）。现在我不知道如何填补理论阅读的空白。

现在我的问题是，谁能给我指出一些计算机科学导论的在线资源（最好是简单的英语）。

此外，我计划让他开始使用 Think Like A Computer Scientist - Python 版这本书开始编程。如果有人知道更好的书或在线资源 - 最好是 Python，请指出。

谢谢

是否有可能获得 Math.random() 的 Big O 估计值？

首先，请原谅我英语不好。

我遇到了以下问题：我必须以固定顺序（例如 A -> D -> F）找到 2 个以上点之间的最短路径。我熟悉 Dijkstra 的算法。但是那个只计算两点之间的最短路径。我也听说过 TSP，但这似乎也不合适。因为没有修复顺序。我已经在网上搜索了我的问题，但也许这不是一个很受欢迎的问题，或者我使用了错误的关键词。

尽管如此，还是要有一个解决方案，因为有很多路线规划器，都成功地提供了这个功能。

所以拜托，任何人都可以通过命名一个算法来帮助我解决我的问题，或者给我一些建议。

非常感谢您的帮助！你真诚的，安杰洛

//edit 呵呵，很尴尬。看来我想了很久，所以我没有描述真正的问题。就是这样：有一些票，只能从头使用。

T1：A -> B（费用 50） T2：B -> C（费用 50） T3：A -> B -> C（费用 80） 给定路线是 A -> B -> C

现在你看，如果我们将给定的路线视为两个独立的问题，我们的总成本将变为 100，但显然 Ticket T3 是更好的解决方案。

假设我有一种只由平衡括号组成的语言，即 {ε, ( ), ( ( ) ), ( ) ( ), ( ( ( ) ) ), ( ( ) ( ) ), ... } 和 I' m 要求为它写一个递归定义。有人可以给我一个例子，看看它可能是什么样子吗？- 我对这种类型的计算机科学理论有点陌生。

Quine-McCluskey的标准成本函数似乎涉及最小化与门的数量。出于我的目的，我需要最小化文字的数量而不是与门的数量（例如，我会选择 ab+cd 而不是 abcde，因为它有 4 个文字而不是 5 个，即使它还有 1 个与门）。谁能给我一些关于这种不同的成本函数将如何改变算法的指示？

它是由某种算法或数学程序生成的，用于测试代码是否产生所需的结果并且没有运行时/堆栈错误？或者是否有其他类型的启发式过程来决定要进行哪些更改。