标签: theory

如果唯一的负边缘成本来自初始节点怎么办？该算法仍然有效吗？

我觉得是的,因为我无法想到反例,但我无法证明这一点.有反例吗？

对于Dijkstra来说,负边是一个问题,因为如果有一条边可以在以后选择,而在很大程度上是负加权,则无法保证您选择的边产生最短路径.但如果唯一的负边缘从初始节点出来,我没有看到问题.

我不是在寻找算法.我正在寻找对Dijkstra的一些见解.

我在谈论有向图,如果这有所不同.

当我正在研究图灵机和PDA时,我认为第一台计算设备是图灵机.

因此,我认为存在一种称为图灵机的实用机器,其状态可以用一些特殊设备(比如触发器)来表示,它可以接受磁带中的输入.

因此我怀疑如何在磁带中表示输入字符串？.但是通过答案和我书中给出的细节,我才知道图灵机是一些假设的东西.

我的问题是,图灵机如何实际实施？例如,它如何用于检查当前处理器中的拼写错误.

图灵机是否已过时？还是他们还在使用？

好吧,这是CS领域的另一个理论领域.

在90年代,我在实施BST方面做得相当不错.我唯一无法理解的是算法的复杂性以平衡二叉树(AVL).

你能帮助我吗？

这主要是一个我非常好奇的理论问题.(我不是试图通过自己编写或任何东西来做到这一点,我不是在重新发明轮子.)

我的问题是大写/小写等价表如何适用于Unicode.

例如,如果我必须在ASCII中执行此操作,我会使用一个字符,如果它在[az]范围内,我会将A和a之间的差值相加.

如果它不属于该范围,我会为10个左右的重音字符加上一个小等价表加上ñ.(或者,我可以只有一个包含256个条目的完整等价数组,其中大多数与输入相同)

但是,我猜测有一种更好的方法来指定Unicode中的等价,假设有数十万个字符,理论上,可以添加一种新语言或一组字符(我期待你当发生这种情况时,不需要修补窗口).

Windows是否为每个字符都有一个巨大的硬编码等价表？或者这是如何实现的？

一个相关的问题是SQL Server如何实现基于Unicode的重音不敏感和不区分大小写的查询.它是否有一个内部表格,告诉它éëeÉÉ和Ë都等同于"e"？

在比较字符串时,这听起来不是很快.

它如何快速访问索引？它是否已将索引值转换为其"基本"字符,对应于该字段的整理？

有谁知道这些东西的内部？

谢谢!

我的问题更多的是历史性而非实际性:

1. 谁发明了它？
2. 首先使用哪种语言(以及在何种程度上)？
3. 什么是最初的想法,基本概念(这些天实际问题必须解决,欢迎论文)？
4. 是的Lisp空调系统的电流异常处理的祖先？

每个本科生编程入门课程都会回顾常用的无上下文语法子集:LL(k),SLR(k),LALR(k),LR(k).我们还被教导,对于任何给定的k,这些语法中的每一个都是下一个语法的子集.

我从未见过的是解释什么样的编程语言语法特征可能需要转移到不同的语言类.GLR解析器有一个明显的实际动机,即在解析C++时避免解析器和符号表的不合理混合.但是,LL和LR这两个"标准"类之间的差异呢？

两个问题:

1. 什么(一般)句法结构可以用LR(k)而不是LL(k')来解析？
2. 在哪些方面,如果有的话,这些结构是否表现为理想的语言结构？

通过使k尽可能小来减少语言能力有一个似是而非的理由,因为需要许多许多前瞻标记的语言对于人类来说难以解析,以及机器要解析的"更难".问题(2)隐含地询问相同的推理是否最终在类之间以及在类中保持.

编辑:这是一个例子来说明我正在寻找的各种答案,但对于常规语言而不是无上下文:

当描述一个普通的语言,人们通常得到三大运营商:+,*和?.现在,你可以删除+而不降低语言的力量; 而不是写作x+,你写xx*,效果是一样的.但是,如果x是一些大而多毛的表达,那么x由于人类的遗忘,这两个人可能会随着时间的推移而发散,产生一个与原作者意图不符的语法正确的正则表达式.因此,即使添加+不严格增加功率,它确实使符号更不容易出错.

是否存在具有类似实际(人类？)效果的结构,从LR切换到LL时必须"删除"？

我经常听到人们称赞语言,框架,结构等是"明确的".我试图理解这个逻辑.语言,框架等的目的是隐藏复杂性.如果它让你明确指定所有类型的细节,那么它不会隐藏太多的复杂性,只会移动它.什么是显性的如此伟大,你如何使语言/框架/ API"明确",同时仍然使其服务于隐藏​​复杂性的目的？

最近我看到一篇关于使用SAT解决难题的Reddit文章[1].这让我对这个"SAT"的事情非常好奇.我阅读了维基百科的文章,但我想请你们中的某些人以更多的外行术语为我解释.

什么是SAT,它有什么用？它可以用于遍历树结构吗？用于解析文本？换线[2]？对于垃圾箱包装[3]？这是一种优化技术吗？

在相关的说明中,我读到NP与P是关于选择哪个数字的集合为零而不是检查某些数字是否总和为零 - SAT是否与此相关？

[1] http://www.reddit.com/r/programming/comments/pxpzd/solving_hexiom_really_fast_with_a_sat_solver/

[2] http://en.wikipedia.org/wiki/Line_wrap

[3] http://en.wikipedia.org/wiki/Bin_packing_problem

为什么这段代码会抛出错误？

// global non-strict code
(function eval () { 'use strict'; });

现场演示: http ://jsfiddle.net/SE3eX/1/

所以,我们这里有一个命名函数表达式.我想明确指出这个函数表达式出现在非严格的代码中.如您所见,它的函数体是严格的代码.

严格的模式规则在这里:http://ecma-international.org/ecma-262/5.1/#sec-C

相关的子弹就是这个(它是列表中的最后一个):

它是一个SyntaxError,在严格模式代码中使用标识符eval或arguments作为FunctionDeclaration或FunctionExpression的标识符或作为形式参数名称(13.1).尝试使用Function构造函数(15.3.2)动态定义此类严格模式函数将引发SyntaxError异常.

请注意,如果函数声明/表达式本身出现在严格的代码中,则此规则仅适用,在上面的示例中不会出现这种情况.

但它仍然会抛出错误？为什么？

我正在研究一个涉及对大型文本数据库进行分类的问题.文本很短(每个3-8个单词),有10-12个类别,我希望对它们进行排序.对于这些功能,我只是使用每个单词的tf-idf频率.因此,特征的数量大致等于文本中整体出现的单词的数量(我正在删除停用词和其他一些词).

在尝试使用模型时,我有以下两个想法:

• 朴素贝叶斯(可能是sklearn多项式朴素贝叶斯实施)
• 支持向量机(在训练中使用随机梯度下降,也是sklearn实现)

我已经建立了两个模型,目前正在比较结果.

每种模型的理论优缺点是什么？为什么其中一个可以更好地解决这类问题？我是机器学习的新手,所以我想了解的是为什么人们会做得更好.

非常感谢!