标签: computer-science

什么是期货？这与懒惰的评估有关.

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

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

你能帮助我吗？

信号量可以低于0吗？我的意思是,说我有一个N = 3的信号量,我称之为"向下"4次,然后N将保持为0,但是一个进程将被阻止？

而另一方面,如果在一开始我打电话,N可以高于3吗？因为正如我所看到的那样,如果在开始时N可以高于3,我会调用几次,然后我可以调用更多次,因此在关键部分放入更多进程然后信号量允许我.

如果有人为我澄清一点,我会非常感激.

格雷格

目标

如何使用尽可能少的数据对描述如何将静态列表从一个订单重新排序到另一个订单的数据进行编码？

我有一种感觉,有一个算法或计算机科学术语可以帮助我,但现在我太过坚持问题,找出其他方法来看待它.

背景动机

我有一个部署到远程位置的程序,所有通信都是通过间歇性的极其昂贵的卫星连接进行的.这有点夸张,但数据成本接近每千字节一美元,每天只能发生几次.

在一天开始时,向用户提供项目列表,他们在现场外出并做东西,但最终结果或多或少是以不同顺序排序的相同项目列表.还有其他数据,但这对这个问题并不重要.

现在我发回所有发生的动作的记录并按顺序播放它们.当用户对系统感到满意时,移动记录列表开始接近仅发回所有项目的大小,并且通常移动的某些组合导致撤消先前的移动记录.

假设

• 起始列表和结束列表由完全相同的项目组成
• 每个项目都有一个唯一的id(32位整数)
• 每个项目都有一个唯一的排序oder(32位整数)
• 用户将拥有数百至数千或更多项目的列表
• 用户通常会在一天内重新订购约100件商品
• 可以检测到对订单的更改将项目移动到列表中的新位置
• 一些"移动"可能会撤消之前的移动
• 用于计算最佳解决方案的计算资源是便宜/无限的
• 传输时间很昂贵
• 发回更改数据比发回整个列表便宜

最简单的数据结构

出于解决此问题的目的,假设以下数据结构可用.

• 项目清单
  • ITEM_ID
  • 排序
• MoveRecord
  • item_a_id
  • new_a_position

这是一个示例列表.每个列表中的项目是相同的.请注意,即使只有少数项目已更改,但每个项目ID都有一个新的排序顺序,因此您不能只发送新的item_id/sort_order_id对.

**List 1: Original List**    **List 2: Re-ordered List**    
order - id                    order - id
     1. 10                         1. 90
     2. 20                         2. 30
     3. 30                         3. 40
     4. 40                         4. 50
     5. 50                         5. 60
     6. 60                         6. 10
     7. 70                         7. 80
     8. 80                         8. 70
     9. 90                         9. 20

如何使用尽可能少的数据编码将列表1的顺序转换为列表2的顺序所需的更改？

好奇心是否有可能证明 …

在我接受的CS课程中,有一个不常规的语言示例:

{a^nb^n | n >= 0}

我可以理解它不常规,因为没有有限状态自动机/机器可以编写验证和接受此输入,因为它缺少一个内存组件.(如果我错了,请纠正我)

关于常规语言的维基百科条目也列出了这个例子,但没有提供(数学)证明为什么它不常规.

任何人都可以启发我并为此提供证据,或者指出我太好的资源？

多路复用意味着什么(以它的抽象形式)？我知道你在硬件中有'多路复用器',在网络中有'多路复用'.一个好的高级定义会是什么？

我正在审查算法课程中的一些旧笔记,动态编程问题对我来说似乎有点棘手.我有一个问题,我们有无限量的硬币,有一些面额x1,x2,... xn我们想要改变一些价值X.我们正在设计一个动态程序来决定是否可以改变X是否制造(不是最小化硬币数量,或返回哪些硬币,只是真或假).

我已经做了一些关于这个问题的思考,我可以看到这样做的递归方法,就像它...

MakeChange(X, x[1..n this is the coins])
    for (int i = 1; i < n; i++)
    {
        if ( (X - x[i] ==0) || MakeChange(X - x[i]) )
            return true;
    }
    return false;

转换这个动态程序对我来说并不容易.我怎么能接近这个？

有谁知道是否call/cc可以用lambdas和闭包实现？

它似乎会call/cc中断程序的流程(就像异常一样),但lambdas和闭包不能这样做.因此我认为call/cc无法通过lambdas和闭包实现.

还有什么想法吗？

我正在编写教程,教孩子们(9到13岁)关于编程.我从计算机本身开始,他们没有那么多与计算机科学有关,而是更多地涉及解决计算问题的过程.

有了这个起点,我指导他们理解机器可以帮助我们解决某些计算问题.人们擅长抽象思维和想象力,但计算机在遵循一个明确规定的例程时非常棒.他们可以一次又一次地以惊人的速度做到这一点!

我的教程已经介绍了以二进制格式表示数字.但是你如何代表负数呢？在任何符号系统中,有很多方法可以做到这一点,但为计算机选择的系统有一个非常特殊的原因:减少添加有符号整数值所涉及的机器数量.我们不希望构建和构建单独的芯片只是为了处理负数,我们想要使用我们用于自然数算术的相同芯片!

如果有人在街上问你(这看起来完全不现实)"计算机如何代表负数,为什么他们用这种方式代表他们呢？"

我的具体问题:

1. 计算机如何代表负数？

2. 为什么计算机以这种方式表示负数？

我猜这个经验丰富的开发人员不得不考虑一下这个问题.有些人甚至可能无法得出答案.我不是想要浮夸,这是来自实际经验,我问过专业开发人员这个问题他们无法回答.他们画了一个空白的凝视.给他们JBoss和JavaBeans,他们会让你充满信心.好笑!我也很难解决这个问题,我每次都要提醒自己,我需要一张纸或白板来制定解决方案.我希望能引导学生更好地了解他们正在使用的机器.

我有一个数据集.该集合的每个元素由数字和分类变量组成.分类变量是名义上的和有序的.该数据集中有一些自然结构.通常,专家使用他们的"专家知识"对我的数据集进行聚类,但我希望自动化这个聚类过程.

大多数聚类算法使用对象之间的距离(Euclidean,Mahalanobdis等)将它们分组.但很难找到混合数据类型的一些合理指标,即我们找不到"玻璃"和"钢铁"之间的距离.所以我得出结论,我必须使用条件概率 P(feature = 'something' | Class)和一些依赖于它们的效用函数.对于分类变量是合理的,并且假设它们正常分布,它对数值变量很好.

所以我很清楚像K-means这样的算法不会产生好的结果.

这时我尝试使用COBWEB算法,这完全符合我使用条件概率的想法.但是我遇到了另一个障碍:如果不是不可能的话,聚类的结果很难解释.因此,我希望获得类似于描述每个聚类(例如if feature1 = 'a' and feature2 in [30, 60], it is cluster1)的一组规则,例如用于分类的决策树.

所以,我的问题是:

是否存在适用于混合数据类型的现有聚类算法,并产生可理解的(对于人类而言合理的)聚类描述.

附加信息:

据我所知,我的任务是在概念聚类领域.由于研究领域的原因,我不能像它所建议的那样定义一个相似性函数(它作为呐喊项目的最终目标) - 它在形式化方面非常复杂和无情.据我所知,最合理的方法是COBWEB中使用的方法,但我不确定如何调整它,所以我可以得到一个不可靠的集群描述.

决策树

正如建议的那样,我尝试在聚类输出上训练决策树,从而将聚类描述作为一组规则.但不幸的是,对这个规则的解释几乎和原始聚类输出一样难.根节点中只有少数第一级规则确实没有任何意义:更接近叶子 - 我们没有意义.其次,这些规则与任何专业知识都不相符.

所以,我得出的结论是聚类是一个黑盒子,不值得尝试解释它的结果.

也

我有一个有趣的想法是以某种方式修改"回归决策树"算法:而不是计算组内方差,计算类别效用函数并将其用作拆分标准.因此,我们应该有一个带有叶子集群和集群描述的决策树.但我没有尝试这样做,我不确定准确性和其他一切.