标签: discrete-mathematics

我正在写一个sokoban求解器,用于娱乐和练习,它使用一种简单的算法(类似于BFS,有点不同).

现在我想估计它的运行时间(O和omega).但需要知道如何计算网络中从顶点到另一个的非循环路径的计数.实际上我想要一个表达式来计算有效路径的数量,在两个顶点之间的顶点.

有效路径:

• 访问每个顶点0或一次.
• 没有电路

例如,这是一个有效的路径:

替代文字http://megapic.ir/images/f1hgyp5yxcu8887kfvkr.png

但这不是:

alt text http://megapic.ir/images/wnnif13ir5gaqwvnwk9d.png

需要一种找到两个顶点a和b之间的所有非循环路径的计数的方法.

欢迎对解决方法和技巧的评论.

假设我在NumPy中有一个包含连续可微函数评估的数组,我想找到局部最小值.没有噪音,所以每个点的值低于其所有邻居的值都符合我的局部最小值的标准.

我有以下列表理解,适用于二维数组,忽略边界上的潜在最小值:

import numpy as N

def local_minima(array2d):
    local_minima = [ index 
                     for index in N.ndindex(array2d.shape)
                     if index[0] > 0
                     if index[1] > 0
                     if index[0] < array2d.shape[0] - 1
                     if index[1] < array2d.shape[1] - 1
                     if array2d[index] < array2d[index[0] - 1, index[1] - 1]
                     if array2d[index] < array2d[index[0] - 1, index[1]]
                     if array2d[index] < array2d[index[0] - 1, index[1] + 1]
                     if array2d[index] < array2d[index[0], index[1] - 1]
                     if array2d[index] < array2d[index[0], index[1] + 1]
                     if array2d[index] < array2d[index[0] + …

我还没有找到一个好的答案.或者任何答案,就此而言.我被要求为CS课程教授一个离散的结构,但同时确保它不是一个离散的数学课程 - 由数学系提供.

许多大学提供分立结构课程.还有很多DS教科书.但是,当我查看课程大纲和教科书介绍时,从未使用过"离散结构"这个术语; 他们使用"离散数学"代替.DS仅出现在课程/教科书的标题中.

例子:

ODU的CS 381

维基百科上的离散结构条目

什么是离散结构,它与离散数学有什么不同？

如何在没有实际转换和计数的情况下获得数字的二进制表示中的"1"的数量？

例如

  def number_of_ones(n):
      # do something
      # I want to MAKE this FASTER (computationally less complex).
      c = 0
      while n:
        c += n%2
        n /= 2
      return c


>>> number_of_ones(5)
    2
>>> number_of_ones(4)
    1

我的问题是(g^x) mod p在JavaScript中快速计算,其中^是取幂,mod是模运算.所有输入都是非负整数,x大约有256位,p是2048位的素数,g最多可能有2048位.

我发现可以在JavaScript中执行此操作的大多数软件似乎都使用JavaScript BigInt库(http://www.leemon.com/crypto/BigInt.html).在我的慢速浏览器(使用SpiderMonkey的Firefox 3.0)上使用此库执行此类大小的单次取幂大约需要9秒.我正在寻找一种至少快10倍的解决方案.使用square-and-multiply(通过平方取幂,http://en.wikipedia.org/wiki/Exponentiation_by_squaring)的明显想法对于2048位数来说太慢了:它需要多达4096次乘法.

升级浏览器不是一种选择.使用其他编程语言不是一种选择.将数字发送到Web服务不是一种选择.

是否有更快的替代方案实施？

更新:按照下面的答案中提到的文章http://www.ccrwest.org/gordon/fast.pdf的建议做一些额外的准备工作(即预先计算几百个权力),可以做到2048-位模幂运算仅使用最多354次模乘.(传统的square-and-multiply方法要慢得多:它使用最多4096次模乘.)这样做可以在Firefox 3.0中将模幂运算速度提高6倍,在Google Chrome中提高4倍.我们没有获得4096/354的全速加速的原因是BigInt的模块化指数算法已经比正方形和乘法更快,因为它使用蒙哥马利减少(http://en.wikipedia.org/wiki/Montgomery_reduction) .

更新:从BigInt的代码开始,似乎值得做两个级别的手动优化(和内联)Karatsuba乘法(http://en.wikipedia.org/wiki/Karatsuba_algorithm),然后才恢复到基础-32768 O( n ^ 2)在BigInt中实现的乘法.对于2048位整数,这会使乘法乘以2.25倍.不幸的是,模运算不会变得更快.

更新:使用http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf和Karatsuba乘法和预计算功能中定义的修改后的Barrett约简(在http://www.ccrwest.org/gordon/中定义)fast.pdf),我可以在Firefox 3.0中将单次乘法所需的时间从73秒减少到12.3秒.这似乎是我能做的最好的,但它仍然太慢了.

更新:Flash Player中的ActionScript 2(AS2)解释器不值得使用,因为它似乎比Firefox 3.0中的JavaScript解释器慢:对于Flash Player 9,它似乎慢了4.2倍,对于Flash Player 10,似乎慢了2.35倍.有人知道ActionScript2和ActionScript3(AS3)之间的速度差异是否有数字运行？

更新:Flash Player 9中的ActionScript 3(AS3)解释器不值得使用,因为它与JavaScript int Firefox 3.0的速度几乎相同.

更新:在Flash Player 10的ActionScript 3(AS3)解释可高达6.5倍,比在Firefox 3.0的JavaScript解释器速度更快,如果int是用来代替Number,并Vector.<int>用来代替Array.对于2048位大整数乘法,至少它快2.41倍.因此,在AS3中进行模幂运算可能是值得的,如果可用的话,在Flash Player 10中执行它.请注意,这仍然比谷歌Chrome的JavaScript解释器V8慢.有关各种编程语言和JavaScript实现的速度比较,请参见http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.html.

更新:有一个非常快速的Java解决方案,如果安装了Java插件,可以从浏览器的JavaScript调用.以下解决方案比使用BigInt的纯JavaScript实现快约310倍. …

我遇到了一个常见的编程访谈问题:给定一个无符号整数列表,找到一个在列表中出现奇数次的整数.例如,如果给出列表:

{2,3,5,2,5,5,3}

解决方案将是整数5,因为它在列表中出现3次而其他整数出现偶数次.

我的原始解决方案包括设置一个排序数组,然后迭代数组:对于每个奇数元素,我会添加整数,而对于每个偶数元素,我会减去; 结束总和是解决方案,因为其他整数将取消.

但是,我发现只需在每个元素上执行XOR就可以实现更高效的解决方案 - 您甚至不需要排序数组!也就是说:

2^3^5^2^5^5^3 = 5

我从Discrete Structures类回忆起,我认为Associate Property适用于XOR操作,这就是为什么这个解决方案有效:

a^a = 0

和:

a^a^a = a

虽然我记得Associative Property适用于XOR,但是我很难找到特定于XOR的这个属性的逻辑证明(因特网上的大多数逻辑证据似乎更侧重于AND和OR操作).有谁知道为什么关联属性适用于XOR操作？

我怀疑它涉及包含AND和/或OR的XOR身份.

在研究JPEG文件的这篇文章时,我在上述文件的第7.3节中遇到了" 八法则 ".

尽管使用SmartScale扩展引入了1到16的其他块大小,超出原始JPEG标准中的固定大小8,但事实仍然是8的块大小仍然是默认值,而所有其他大小的DCT根据标准8x8 DCT进行缩放.

" 八法则 "解释了为什么大小8是DCT大小的正确默认值和参考值.

我的问题是

究竟这个"八大法则"究竟是什么？

• 从历史上看,是否进行了一项研究,评估了样本中的大量图像,得出的结论是8x8图像块包含足够的冗余数据以支持使用DCT的压缩技术？像8M(4Kx4K)这样非常大的图像尺寸在大多数数字图像/视频中迅速成为常态,这种假设是否仍然有效？

• 将宏块限制为8x8的另一个历史原因是较大宏块的计算上禁止的图像数据大小.使用现代超标量体系结构(例如CUDA),限制不再适用.

此前类似的问题存在- 1,2和3.但他们都没有打扰任何关于这个神秘的基本" 八法则 "的细节/链接/参考.

_{1.原始研究的参考/摘录/细节将受到高度赞赏,因为我想用具有非常大尺寸图像的现代数据集重复它以测试8x8宏块的最佳有效性.}

_{2.如果最近进行了类似的研究,也欢迎提及它.}

_{我确实理解SmartScale是有争议的.没有任何明显的潜在好处¹,充其量只能与jpeg标准^2的其他向后兼容扩展相媲美.我的目标是了解选择8x8作为DCT块大小(在jpeg图像压缩标准中)的原始原因是否仍然相关,因此我需要知道八个定律是什么.}

matplotlib.mlab.psd(...)并且scipy.signal.welch(...)都实现了Welch的平均周期图方法来估计信号的功率谱密度(PSD).假设将等效参数传递给每个函数,则返回的PSD应该是等效的.

但是,使用简单的正弦测试函数,当每个窗口使用的点数(nperseg关键字for scipy.signal.welch; NFFT关键字for mlab.psd)是偶数时,两种方法之间存在系统差异,如下所示,每个窗口64点的情况

顶部图显示通过两种方法计算的PSD,而底部图显示它们的相对误差(即两个PSD的绝对差除以它们的绝对平均值).较大的相对误差表明两种方法之间存在较大的不一致.

当每个窗口使用的点数为奇数时,这两个函数具有更好的一致性,如下所示,对于相同的信号,但每个窗口处理65个点

在信号中添加其他特征(例如噪声)会稍微减少这种影响,但它仍然存在,当每个窗口使用偶数个点时,两种方法之间的相对误差约为10%.(我意识到在每个窗口65个点上计算的PSD的最高频率的相对误差相对较大.但是,这是在信号的奈奎斯特频率,并且我不太关心如此高频率的特征.我当每个窗口的点数是偶数时,更关心大部分信号带宽的大而系统的相对误差.

这种差异是否有原因？一种方法在准确性方面是否优于另一种方法？我使用scipy版本0.16.0和matplotlib版本1.4.3.

用于生成上述图的代码包括在下面.对于纯正弦信号,设置A_noise = 0; 对于有噪声的信号,设置A_noise为有限值.

import numpy as np
import matplotlib.pyplot as plt
from scipy.signal import welch
from matplotlib import mlab

# Sampling information
Fs = 200.
t0 = 0
tf = 10
t = np.arange(t0, tf, 1. / Fs)

# Pure sinusoidal signal
f0 = 27.
y = np.cos(2 * np.pi * f0 …

在我大学的离散数学课程中,教师向学生展示Ackermann功能,并指导学生在纸上开发功能.

除了作为递归优化的基准之外,Ackermann函数是否有任何实际用途？

我正在尝试验证用户提供的一系列单词.我正在尝试提出一个评分系统,该系统将确定一系列单词确实是有效单词的可能性.

假设以下输入:

xxx yyy zzz

我要做的第一件事就是根据我拥有的单词数据库单独检查每个单词.所以,让我们说这xxx是在数据库中,所以我们100%确定它是一个有效的单词.然后让我们说yyy数据库中不存在,但其拼写的可能变化存在(比方说yyyy).我们不给出yyy100%的分数,但可能更低(让我们说90%).然后zzz在数据库中根本不存在.所以,zzz得分为0%.

所以我们有这样的事情:

xxx = 100%
yyy = 90%
zzz = 0%

进一步假设用户要么要么:

1. 提供所有有效单词的列表(最有可能)
2. 提供所有无效字的列表(可能)
3. 提供有效和无效单词组合的列表(不太可能)

总的来说,确定xxx yyy zzz一系列有效词的置信度得分的好评分系统是什么？我不是在寻找任何过于复杂的东西,但获得平均分数似乎并不合适.如果单词列表中的某些单词有效,我认为它增加了数据库中未找到的单词也是实际单词的可能性(这只是数据库的一个限制,它不包含该特定单词).

注意:输入通常至少为2个单词(大多数为2个单词),但可以是3,4,5(在极少数情况下甚至更多).