标签: computer-science

多任务操作系统的特征是什么？
是什么让它多任务处理？
是否有非多任务操作系统？

我有一个图表,n节点作为邻接矩阵.

是否有可能在不到O(n)时间内检测到水槽？

如果有,怎么样？如果不是,我们如何证明呢？

接收器顶点是一个顶点,具有来自其他节点的入射边缘,没有出射边缘.

问题

什么是最有效的MGU算法？它的时间复杂度是多少？它是否足以简单地描述为堆栈溢出答案？

我一直试图在谷歌找到答案,但继续寻找我只能通过ACM订阅访问的私人.PDF.

我在SICP找到了一个讨论:这里

解释什么是"最通用的统一算法":取两个包含"自由变量"和"常量"的表达式树...例如

 e1 = (+ x? (* y? 3) 5)
 e2 = (+ z? q? r?)

然后,Most General Unifier算法返回最通用的绑定集,使两个表达式等效.

即

mgu(e1,e2) = (x = z), q = (* y 3), y = unbound, r = 5

通过"最一般",您可以改为绑定(x = 1)和(z = 1),这也会使e1和e2等效,但它会更具体.

SICP文章似乎暗示它相当昂贵.

有关信息,我问的原因是因为我知道类型推断也涉及这种"统一"算法,我想了解它.

如何确定在处理递归运行时构建的递归树的高度？它与确定常规树的高度有何不同？

alt text http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/ch4-9.gif

编辑:对不起,我的意思是添加如何从递归关系中获取递归树的高度.

我最近一直在研究我的基本数据结构,试图确保我已经冷却了它们.

"基本",我指的是真正基本的.像红黑树和布鲁姆过滤器这样的花哨的东西显然值得了解,但它们通常要么是基本的增强(红黑树是具有特殊属性的二元搜索树以保持平衡)或者它们仅在非常有用具体情况(布隆过滤器).

到目前为止,我在以下数据结构中"流畅":

• 数组
• 链接列表
• 栈/队列
• 二叉搜索树
• 堆/优先级队列
• 哈希表

但是,我觉得我错过了一些东西.我有什么基本的遗忘吗？

编辑:发布问题后添加这些

• 字符串(由catchmeifyoutry建议)
• 套(彼得建议)
• 图(由Nick D和aJ建议)
• B树(由tloach建议)
  • 关于这些是否过于花哨,我有点不确定,但我认为它们与基本结构(并且非常重要)有足够的不同,值得研究作为基础.

我一直在网上搜索,我发现有些矛盾的答案.一些消息来源声称,语言/机器/什么具备的,你是图灵完备当且仅当它有两个有条件和无条件分支(我的猜测是一种多余的),有的说只有无条件的要求,别人只有条件是必须的.

阅读德国Z3和ENIAC,维基百科说:

德国Z3(显示于1941年5月工作)由Konrad Zuse设计.它是第一台通用型数字计算机,但它是机电式的,而不是电子的,因为它使用了继电器用于所有功能.它使用二进制数学逻辑计算.它可以通过穿孔带编程,但缺少条件分支.虽然不是为图灵完整性而设计的,但它偶然发生在1998年(但为了利用这种图灵完整性,复杂,聪明的黑客是必要的).

究竟是什么复杂,聪明的黑客？

R. Rojas撰写的1998年论文摘要也指出(请注意,我没有读过这篇论文,它只是IEEE的一个片段.):

由Konrad Zuse在1938年至1941年之间建造的计算机器Z3可以仅执行在穿孔带中编码的浮点算术运算(加法,减法,乘法,除法和平方根)的固定序列.从计算历史的角度来看,一个有趣的问题是这些操作是否足以进行通用计算.该论文表明,实际上,包含这些算术指令的单个程序循环可以模拟其磁带具有给定有限大小的任何图灵机.这是通过纯粹的算术方法模拟条件分支和间接寻址来完成的.因此,Zuse的Z3至少在原则上与今天具有有限寻址空间的计算机一样普遍.

简而言之,SOers,Turing-completeness究竟需要什么类型的分支？假设无限的内存,只有一个goto或jmp分支结构(没有if或jnz构造)的语言可以被认为是图灵完备吗？

可能重复:
实现二进制搜索有哪些缺陷？

我正在仔细阅读维基百科页面的二进制搜索,并偶然发现了Knuth的一句话:

"尽管二元搜索的基本思想相对简单,但细节可能会非常棘手"

我记得在我的计算机科学课程中实施了几个二进制搜索,但是不记得它非常棘手.然而,这篇文章指出,90%的被调查专业人员在几小时后无法工作.我想假设这不是因为这些是非常糟糕的程序员,而是存在天真实现不能解释的边缘情况.

Knuth所指的细节是什么？如果实现二进制搜索算法,需要注意哪些常见问题？

注意我读了Bloch关于Programming Pearls bug的文章(中点的int溢出).还有别的事吗？

的背景

我最近发布了一个答案,其中我不同地称为#{}文字,操作符和(在一个草稿中)"文字构造函数".这个定义的松软并没有真正影响答案的质量,因为问题更多的是关于它的作用以及如何为它找到语言参考,但我不满意无法指出准确的规范定义什么叫做Ruby语法的这个元素.

的红宝石手册提到在上一节该语法元素表达替代,但并没有真正定义了语法本身的术语.几乎每一个参考这个语言元素表示,它使用了串插,但不定义它是什么是.

维基百科定义

以下是维基百科的一些定义,暗示这种结构(严格来说)既不是文字也不是运算符.

1. 文字(计算机编程)
2. 操作员(编程)

问题

有谁知道这个语言元素的正确用语是什么？如果是这样,你能指点一个正式的定义吗？

我正在使用Minimax使计算机连接6.我也在使用Alpha-Beta修剪来加速算法.

我想添加一个转置表来使算法更快.我绝对没有经验.

有人可以解释换位表的基础知识,以及它们如何应用于Connect 6这样的游戏？指向有用资源的链接没问题.

我熟悉哈希表.

我找到了什么:

1)https://www.chessprogramming.org/Transposition_Table

该链接给出了转置表的一个很好的解释,但完全集中在国际象棋上,因此难以弄清楚换位表如何独立于国际象棋.

直觉上,我希望"数学"答案all (==1) [1,1..]是True因为列表中只包含1的所有元素都等于1.但我理解"计算上",评估无限列表以检查事实上,每个元素实际上等于1将永远不会终止,因此表达式将"评估"到底部或?.

我发现这个结果反直觉而且有点令人不安.我认为列表无限的这个事实在数学上和计算上都会混淆这个问题,我很乐意听到在这个领域有一些见解和经验的人

我的问题是,哪个是数学上最正确的答案？?还是True？关于为什么一个答案比另一个答案更正确的一些详细说明也将受到高度赞赏.

编辑:这可能间接地与库里 - 霍华德同构(程序是证明和类型是定理)和哥德尔的不完备性定理有关.如果我没记错的话,其中一个不完备性定理可以(非常粗略地)总结为"足够强大的形式系统(如数学或编程语言)无法证明所有可以在系统中表达的真实陈述"