只是想知道是否有人可以解释为什么"不稳定的排序"被认为是坏的？基本上我没有看到任何真正重要的情况.有人可以提供吗？
经典正则表达式等价于有限自动机.大多数当前的"正则表达式"实现并不严格地说正则表达式,但更强大.有些人开始使用术语"模式"而不是"正则表达式"来更准确.
什么是可以用现代"正则表达式"描述的形式语言分类,例如Perl 5中支持的模式？
更新:"Perl 5"我的意思是在Perl 5中实现的模式匹配功能,并被许多其他语言(C#,JavaScript等)采用,而不是Perl特有的任何东西.例如,我不想考虑在模式中嵌入Perl代码的技巧.
我对NP完全问题的掌握得体; 那不是问题.我没有的是很好地理解他们在"真正的"编程中出现的位置.有些人(比如背包和旅行推销员)很明显,但其他人似乎并没有明显与"真实"问题联系在一起.
我曾经多次遇到过困难问题,只是意识到这是一个众所周知的NP Complete问题,已被广泛研究过.如果我更快地识别出连接,我可以节省相当多的时间来研究现有解决方案以解决我的具体问题.
是否有任何资源(在线或打印)专门连接NP Complete到真实世界的实例？
编辑:例如,我正在研究一个程序,该程序试图根据年龄,年级和原始学校将学生分成小组,这实际上是图形分区问题.我花了一段时间才意识到这种联系.
我一直在考虑使用Haskell的Parsec解析库来解析Java的一个子集作为递归下降解析器,作为更传统的解析器生成器解决方案(如Happy)的替代.Parsec似乎很容易使用,解析速度绝对不是我的一个因素.不过,我想知道是否可以用Parsec实现"备份",这是一种通过依次尝试每个产品来找到正确生产的技术.举一个简单的例子,考虑JLS Java语法的开头:
Literal:
IntegerLiteral
FloatingPointLiteral
我想要一种方法来不必弄清楚我应该如何命令这两个规则来使解析成功.就目前而言,这样一个天真的实现:
literal = do {
x <- try (do { v <- integer; return (IntLiteral v)}) <|>
(do { v <- float; return (FPLiteral v)});
return(Literal x)
}
无法工作......像"15.2"之类的输入将导致整数解析器首先成功,然后整个事情将会扼杀"." 符号.当然,在这种情况下,您可以通过重新订购两个产品来解决问题.然而,在一般情况下,发现这样的事情将成为一场噩梦,我很可能会错过一些案例.理想情况下,我想要一种方法让Parsec为我找出这样的东西.这可能,或者我只是想对图书馆做太多事情？Parsec文档声称它可以"解析上下文敏感的,无限的前瞻语法",所以看起来像我应该能够在这里做点什么.
我是一名对生物信息学研究感兴趣的CS研究生.我对生物学没有很好的经验.什么是计算机科学家最好的生物信息学书籍？
我试图(经典地)证明
~ (forall t : U, phi) -> exists t: U, ~phi
在Coq.我想要做的是证明它是相反的:
1. Assume there is no such t (so ~(exists t: U, ~phi))
2. Choose arbitrary t0:U
3. If ~phi[t/t0], then contradiction with (1)
4. Therefore, phi[t/t0]
5. Conclude (forall t:U, phi)
我的问题是第(2)和(5)行.我无法弄清楚如何选择U的任意元素,证明它的一些东西,并得出一个结论.
任何建议(我不承诺使用对立面)？
正则表达式通常被指向不完全转换的语言的经典示例.例如,"正则表达式"作为这个SO问题的答案给出,寻找不是图灵完整的语言.
在我的,或许有点基本的,理解转向完整性的概念,这意味着不能使用正则表达式检查"平衡"的模式.平衡意义具有与结束字符相同数量的开始字符.这是因为要做到这一点需要你有某种状态,以允许你匹配开始和结束字符.
然而,正则表达式的.NET实现引入了平衡组的概念.此构造旨在让您回溯并查看先前的组是否匹配.这意味着.NET正则表达式:
^(?<p>a)*(?<-p>b)*(?(p)(?!))$
可以匹配以下模式:
ab
aabb
aaabbb
aaaabbbb
... etc. ...
这是否意味着.NET的正则表达式是图灵完成的？或者还有其他缺少的东西,这些语言需要图灵完成吗？
我必须确定一种语言(例如L = {a ^ nb ^ mc ^ s | 0 <= n <= m <= s})是否是常规的,无上下文的,递归的,递归可枚举的或者都不是.
我知道如何确定一个语言是正规(找到DFA或正则表达式的工作)或上下文(找到一个PDA或上下文无关文法的作品); 我知道递归语言有一个总是停止的图灵机器,并且一个递归可枚举的语言有一个可能不会停止的图灵机.
所以问题是:是否有一个快速的标准来确定语言是递归还是递归可枚举或两者都没有？例如,我不需要构建一个PDA来理解语言是无上下文的,我不能通过它需要一个堆栈来看待它; 有没有类似的快速解决问题的方法(希望能省去构建图灵机的麻烦)？
recursion computer-science turing-machines context-free-grammar
好的,我有一个问题.我有一套各种尺寸的瓶装"A",里面装满了水.然后我又拿了另一套各种尺寸的瓶子"B",都是空的.
我想将水从A转移到B,知道每组的总容量是相同的.(即:组A含有与组B相同的水量).
这当然是微不足道的,只需拿B中的第一个瓶子,倒入A中的第一个瓶子直到它满了.然后,如果B中的瓶子中还有水,请继续使用A中的第二个瓶子等.
但是,我想尽量减少浇注总量(从瓶子倒入另一个瓶子的动作,每个动作计数1,与其涉及的水量无关)
我想找到一个贪婪的算法来做到这一点,或者如果不可能,至少是一个有效的算法.然而,效率是算法正确性的次要因素(我不想要一个次优的解决方案).
当然,这个问题只是计算机程序中管理个人开支的真正问题的隐喻.
我正在查看一些代码,并看到了关于"滞后"的脱离背景评论.我想我已经弄明白代码的作用,所以我的问题不涉及任何具体的问题.我根本不明白这个术语的含义或它在编程中的适用方式.我环顾四周,看到了一些数学定义,但想了解更多信息.据我所知,Hysteresis与根据过去X发生的事情预测或假设X的给定状态有关？