标签: computer-science

Dijkstra是最多产的计算机科学家之一.他写了着名的EWD.阅读所有内容是不可行的.但我认为有一些我们都必须阅读.

哪一个是必读的？

什么是队列在计算机科学中的实际应用.我们在哪里使用它们？为什么？我听说我们在视频游戏和计算机模拟程序中使用它们,是真的吗？为什么？除了这两个领域,队列作为数据结构的其他实际应用是什么？

我阅读了http://swtch.com/~rsc/regexp/regexp1.html,其中作者说,为了在正则表达式中进行反向引用,在匹配时需要回溯,这使得最坏情况的复杂度呈指数级增长.但我并不确切地知道为什么反向引用会引入回溯的必要性.有人可以解释为什么,也许提供一个例子(正则表达式和输入)？

我有一个DAG(每边的成本/权重),并希望找到两组节点之间的最长路径.与图中的节点总数相比,两组起始节点和目标节点是不相交的并且尺寸较小.

我知道如何在一个开始节点和目标节点之间有效地执行此操作.使用多个,我可以列出从每个开始到每个目标节点的所有路径并选择最长的路径 - 但这需要二次数的单路径搜索.有没有更好的办法？

如果您现在有机会参加一门计算机科学课程,结果会大大增加您在学科领域的知识,那会是什么？本科或研究生水平.

编译器？分布式算法？并发理论？先进的操作系统？

让我知道为什么.

(请注意,我很欣赏这不是一个遥不可及的场景 - 但时间和惯性可能会阻止人们参加课程或阅读书籍等等)

我正在阅读我的AI教科书,我很好奇启发式的单调性和可接受性之间的区别(我知道它们不是互相排斥的).

据我所知,一个可接受的启发式只是意味着你可以确保获得解决方案的最短路径(如果存在的话).

我正在努力的是单调属性的概念.有人可以用我可能理解的方式向我描述这个吗？

同样,我如何确定给定的启发式是否是单调/可接受的？本书中给出的一个例子是8件式滑动拼图.我正在考虑的一种启发式是不合适的瓦片,直观地我可以说我知道它是可以接受的,但我没有正式的方式来显示它是否是可接受的/单调的.

我正在寻找一种方法来使用Oracle数据库进行BITOR()并且遇到了一个建议,只需使用BITAND()代替BITOR(a,b)替换为+ b - BITAND(a,b).

我用手测试了几次并验证它似乎适用于我能想到的所有二进制数,但我无法想出为什么这是正确的快速数学证明.
有人可以开导我吗？

规则引擎和专家系统有什么区别？

例1:假设我有一个程序来确定新驾驶执照的到期日期.它需要签证有效期,护照号码,生日等输入.它根据此输入确定驾驶执照的到期日期.如果输入没有足够的有效标识来允许新的驾驶执照,它甚至会出错.

例2:假设我正在制作游戏Monopoly的在线版本.我希望能够改变比赛的规则(比如传球去400美元,或者没有人可以购买房产,直到他们两次落在同一个房产上等).我在代码中有一个模块来处理这些规则.

这些都是规则引擎还是专家系统？它们看起来都很相似.它只是一个同义词吗？

我在大学里有一门名为算法分析的课程,我们目前正在研究不同的复杂性类别 - P,NP,NP-hard等.

我们已经讨论过NP完全问题作为NP与NP之间的交集,以及NP中包含的P问题.我们还讨论了一些例子,主要是NP完全问题(k-coloring,k-clique,SAT).

大多数时候,我们通过以下方式证明问题是NP完全的:

一个.找到一个不确定的算法来解决它(使用选择,成功,失败);

湾 减少已知的NP完全问题.

问题是这些问题,当在确定性机器上运行时(顺序而不是在遇到选择时同时分支)具有指数时间解决方案.

我的问题是 - 我从未遇到过在指数时间内既不能在多项式时间内解决的问题; 多项式时间问题在P中,指数时间问题通常在NP完全中.

这里有一个有用的维恩图:http: //en.wikipedia.org/wiki/Np_complete

1. 我想知道一个问题的例子既不是在NP中,也不是在NP中.

2. 另外,本质上是指数问题,比如生成NP-complete集的幂集？或者该名称仅适用于仅使用指数时间算法的问题,因为没有其他明显的方法可以解决它？

好的,所以我给了Rosh Oxymoron的答案,因为他实际列出了一些疑似在P和NPC之间的问题的例子.谢谢你的帮助,我实际上注意到我把这个问题放错了地方.还有:https: //cstheory.stackexchange.com/

在那里我发现了以下非常有用的回答我的问题: https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc 这是专门约我问及: https://开头cstheory .stackexchange.com/questions/52/hierarchyies-in-np-under-the-assumption-that-p-np ,如果与初始问题不完全相关,通常很有趣.

非常感谢,

担

我正试图找到二进制图像的非零(x,y)坐标.

我发现了一些函数的引用countNonZero(),它只计算非零坐标,findNonZero()而且我不确定如何访问或使用它,因为它似乎完全从文档中删除了.

这是我发现的最接近的参考,但仍然没有任何帮助.我将不胜感激任何具体的帮助.

编辑: - 要指定,这是使用C++