标签: computer-science

我知道这是一个数学/形式语言/自动机/计算机科学问题,而不是一个编程问题,但我希望我能在关于命题和谓词演算之外的形式逻辑上获得一些可理解的教科书(不是难以理解的专着)的建议.我对monadic二阶逻辑和BüchiAutomata特别感兴趣.

目前,我只发现 了Bakhadyr Khoussainov,Anil Nerode的Automata理论及其应用.自动机,逻辑和无限游戏作者:ErichGrädel,Thomas Wilke(编辑).和传播系统的正式模型:语言,自动机和 Monadic 二阶逻辑 Benedikt Bollig ......超越我的脑海.

我试图在这里理解SICP中描述的统一算法

特别是,在"尽可能扩展"的过程中,有一个检查(标有星号"*"的第一个地方),它检查右手"表达式"是否是已经绑定到某个东西的变量.当前帧:

(define (extend-if-possible var val frame)
  (let ((binding (binding-in-frame var frame)))
    (cond (binding
       (unify-match
        (binding-value binding) val frame))
      ((var? val)                      ; *** why do we need this?
       (let ((binding (binding-in-frame val frame)))
         (if binding
             (unify-match
              var (binding-value binding) frame)
             (extend var val frame))))
      ((depends-on? val var frame)
       'failed)
      (else (extend var val frame)))))

相关评论指出:

"在第一种情况下,如果我们尝试匹配的变量没有绑定,但我们试图匹配它的值本身就是一个(不同的)变量,有必要检查该值是否绑定,并且如果是的话,要匹配它的价值.如果比赛的双方都没有约束,我们可能会绑定到另一方."

但是,我想不出这实际上是必要的情况.

我认为,它正在谈论的是你目前可能有以下框架绑定的地方:

{?y = 4}

然后要求"extendIfPossible"绑定从？z到？y.

当出现"*"检查时,当被要求用"？y"扩展"？z"时,我们看到"？y"已经绑定到4,然后递归地尝试将"？z"与"4"统一,这导致我们用"？z = 4"扩展框架.

没有检查,我们最终只用"？z =？y"扩展框架.但在这两种情况下,只要？z还没有被其他东西绑定,我就没有看到问题.

请注意,如果- Z 就已经被绑定到别的东西,然后代码没有达到部分标有"*"(我们早就递归到什么？ž统一已经匹配).

经过深思熟虑之后,我意识到可能存在某种形式的争论,即生成一个"最简单"的MGU(Most General Unifier).例如,您可能希望MGU具有引用其他变量的最少数量的变量...也就是说,我们宁愿生成替换{？x = 4,？y …

我认为标题准确地总结了我的问题,但只是详细说明一下.

我不想使用正则表达式来验证现有字符串的属性,而是使用正则表达式来生成具有某些属性的字符串.

注意:该函数不需要生成满足正则表达式的每个字符串(因为对于许多正则表达式而言,这将是无限数量的字符串).只需抽取许多有效字符串即可.

这样的事情有多可行？如果解决方案太复杂/太大,我对一般性讨论/大纲感到满意.此外,我对任何现有的程序或库(.NET)感兴趣.

Fortran-> Algol-> Cpl-> Bcpl-> C-> C++ - > Java .....

似乎每种语言都建立在祖先语言之上.我的问题:新语言扩展为父语言还是有某种技巧？

例如Java中的System.out.print(); 它实际上是C中的printf(),依此类推(printf实际上是......在Cpl中)？

如果是这样,这是否会使每一种语言变慢并需要更多内存？新语言与框架之间的区别是什么？

在阅读有关Spring如何工作的内容时,我已经看过这个术语,我刚刚阅读了有关JPA实现性能的文章,它有下一个统计信息:

EclipseLink                                                           3215 ms
(Run-time weaver - Spring ReflectiveLoadTimeWeaver weaver  )
EclipseLink (Build-time weaving)                                      3571 ms
EclipseLink (No weaving)                                              3996 ms

那么,有人可以用简单的英语解释什么是编织？

谢谢!

根据这个问题,.Net字典将其分配的空间大小调整为至少是当前大小两倍的素数.为什么使用素数而不仅仅是当前大小的两倍是很重要的？(我试图用我的google-fu功能找到答案,但无济于事)

我正在尝试用Python实现Heap Sort,但我似乎无法做到正确.我试图实现这个伪代码,但我的代码没有排序!它只是筛选到荒谬的效果.我倾向于认为问题出在这一行:

将堆的根(最大值)与堆的最后一个元素交换

我如何获得最大值？

这就是我所拥有的:

def my_heap_sort(sqc):                    
    def heapify(count):                
        start = (count-2)/2            
        while start >= 0:              
            sift_down(start, count-1)  
            start -= 1                 

    def swap(i, j):                    
        sqc[i], sqc[j] = sqc[j], sqc[i]

    def sift_down(start, end):         
        root = start                   

        while (root * 2 + 1) <= end:   
            child = root * 2 + 1       
            temp = root                
            if sqc[temp] < sqc[child]: 
                temp = child+1         
            if temp != root:           
                swap(root, temp)       
                root = temp            
            else:                      
                return                 

    count = len(sqc)                   
    heapify(count)                     

    end = count-1 …

我很难用O表示法定义以下算法的运行时间.我的第一个猜测是O(n),但是迭代和我应用的数字之间的差距并不稳定.我怎么错误地定义了这个？

public int function (int n ) 
{
  if ( n == 0) {
    return 0;
  }

  int i = 1;
  int j = n ;
  while ( i < j ) 
  {
    i = i + 1;
    j = j - 1;
  }
  return function ( i - 1) + 1;
}

我是编程新手,目前参加CSC 110课程.我们的任务是创建一组函数,使用给定的一些数据执行各种操作.我已经把所有数据都放到了字典中,但是我在获取我想要的数据时遇到了一些麻烦.

这是我的问题:

我有一个字典,存储了一堆国家,后面是一个包含人口和GDP的列表.格式化这样的东西

{'country': [population, GDP], ...}

我的任务是遍历这个并找到人口或GDP最高的国家然后打印:

'The country with the highest population is ' + highCountry+\
    ' with a population of ' + format(highPop, ',.0f')+'.')

为了做到这一点,我写了这个函数(这个函数专门用于最高人口,但它们看起来都是一样的).

def highestPop(worldInfo):
        highPop = worldInfo[next(iter(worldInfo))][0] #Grabs first countries Population
        highCountry = next(iter(worldInfo))#Grabs first country in worldInfo

        for k,v in worldInfo.items():
                if v[0] > highPop:
                    highPop = v[0]
                    highCountry = k

        return highPop,highCountry

虽然这对我有用,但我认为有一种更简单的方法可以做到这一点.另外,我不是100%确定如何[next(iter(worldInfo))]运作.这只是抓住它看到的第一个值吗？

感谢您的帮助!

编辑:对不起我想我不清楚.我需要通过国家人口以及国家名称.所以我可以在我的主要功能中打印它们.

所以我希望能够在C#中解析和评估"骰子表达式".骰子表达式定义如下:

<expr> :=   <expr> + <expr>
            | <expr> - <expr>
            | [<number>]d(<number>|%)
            | <number>
<number> := positive integer

所以例如d6+20-2d3是允许的,并且应该评估为

rand.Next(1, 7) + 20 - (rand.Next(1, 4) + rand.Next(1, 4))

也d%应该相当于d100.

我知道我可以解决一些解决方案,但我也知道这似乎是一个非常典型的计算机科学类型的问题,所以必须有一些我应该研究的超优雅解决方案.

我希望我的解析结果具有以下功能:

• 我应该能够输出表达式的规范化形式; 我首先考虑骰子,按骰子大小排序,并始终使用前缀.所以例如上面的样本会变成1d6-2d3+20.任何实例d%也会变成d100标准化形式.
• 我应该能够随意评估表达式,每次滚动不同的随机数.
• 我应该能够用最大化的所有骰子卷来评估表达式,因此例如上面的样本将给出(确定性地)1*6+20+2*3 = 32.

我知道这正是Haskell的类型,可能还有其他功能类型的语言,但是如果可能的话,我想留在C#中.

我最初的想法倾向于递归,列表,也许还有一些LINQ,但是,如果我尝试没有知道事物的人的一些指示,我肯定它最终会成为一个不优雅的混乱.

另一种可能有效的策略是一些基于正则表达式的初始字符串替换,将骰子表达式转换为rand.Next调用,然后进行即时评估或编译......这实际上有用吗？我怎么能避免rand每次都创建一个新对象？