标签: discrete-mathematics

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

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

有一台机器有O(1)内存.我们想要第一次传递n个数字(逐个),我们再次排除两个数字,我们将n-2传递给机器.写一个找到缺失数字的算法.这是一个面试问题,我无法解决.

给定n个节点,如果每个节点连接到每个其他节点(除了它自己),则连接数将为n*(n-1)/ 2

如何证明这一点？

这不是一个家庭作业问题.我已经远离CS教科书,并且忘记了如何证明这一点的理论.

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

假设以下输入:

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(在极少数情况下甚至更多).

给定一个大的稀疏矩阵(比如说10k +乘以1M +),我需要找到形成密集矩阵(所有非零元素)的行和列的子集,不一定是连续的.我希望这个子矩阵在某些宽高比约束内尽可能大(不是最大和,但是最大数量的元素).

这个问题是否有任何已知的确切或aproxamate解决方案？

对谷歌的快速扫描似乎给出了很多接近但不完全的结果.我应该寻找什么条款？

编辑:只是为了澄清; 子矩阵不需要是连续的.事实上,行和列顺序是完全任意的,因此邻接完全无关紧要.

基于Chad Okere的想法的想法

1. 从最大计数到最小计数排序行(不是必需但可能有助于执行)
2. 选择两个具有"大"重叠的行
3. 添加不会减少重叠的所有其他行
4. 记录该集
5. 添加任何行减少重叠最少
6. 在#3重复,直到结果变小
7. 从#2开始,使用不同的起始对
8. 继续,直到您确定结果足够好

在昨晚观看橄榄球的时候,我想知道是否有任何分数是不可能的,因为你只能得到3,5或7分的分数.不用花很长时间就可以得到任何大于4的数字.5 = 5,6 = 3 + 3,7 = 7,8 = 3 + 5,9 = 3 + 3 + 3,10 = 5 + 5,依此类推.

将该想法扩展为5,7和9会产生以下可能的分数:

5,7,9,10,12,14 // and now all numbers are possible.  

对于7,9和11:

7,9,11,14,16,18,20,22,23,25,27 // all possible from here

我在脑海中做了这些,任何人都可以提出一个好的算法来确定最低分数,高于该分数,在给定一组分数的情况下,所有分数都可以达到.

我这样建模:

forall a < 10:
   forall b < 10:
      forall c < 10:
          list.add(3a + 5b + 7c);
list.sort_smallest_first();

然后检查列表中是否有超过3的序列(可能的最小分数).对于除了琐碎案件之外的任何事情,似乎都是不切实际和缓慢的.

邮票问题是一个数学问题,询问如果信件只能容纳有限数量的邮票,那么不能放在信封上的最小邮资价值是多少,而这些邮票可能只有某些指定的面值.

例如,假设信封只能容纳三个邮票,可用的邮票价值分别为1美分,2美分,5美分和20美分.然后解决方案是13美分; 因为任何较小的值都可以获得最多三个邮票(例如4 = 2 + 2,8 = 5 + 2 + 1等),但要获得13美分,必须使用至少四个邮票.

是否有算法给出允许的最大邮票数量和邮票的面值,人们可以找到不能放在信封上的最小邮资？

另一个例子:
最多可以使用5个标记
值:
1,4,12,21无法达到的最小值是72.可以使用特定组合创建值1-71.

最后我可能会使用Java来编写代码.

我想优化所有30到30个矩阵,条目为0或1.我的目标函数是决定因素.一种方法是采用某种随机梯度下降或模拟退火.

我看了一下,scipy.optimize但就我所知,它似乎并不支持这种优化.scipy.optimize.basinhopping看起来很诱人,但似乎需要连续变量.

Python中是否有用于此类通用离散优化的工具？

通过从左到右旋转 2 个列表，找到两个列表中每个对应项之间差异的绝对值的最小可能总和，因为它们的长度相同。

旋转样品：

List [0, 1, 2, 3, 4, 5] rotated to the left = [1, 2, 3, 4, 5, 0]

List [0, 1, 2, 3, 4, 5] rotated to the right= [5, 0, 1, 2, 3, 4]

绝对差之和：

List 1 = [1, 2, 3, 4]
List 2 = [5, 6, 7, 8]

Sum of Abs. Diff. = |1-5| + |2-6| + |3-7| + |4-8| = 16

再一次，对于任意长度的列表和整数值，任务是通过简单地旋转到一个或两个列表的左/右来寻找最小的总和。

我对旋转和获取最小绝对差和没有问题。我只想知道更聪明的方法，因为我的算法会检查每个可能的组合，这很慢。

这是我的蛮力方法：

list1 = [45, 21, 64, 33, 49] …

在这里，我试图以最小的边缘去除来断开图中的两个顶点。

在此图形中，在两个顶点A和Z之间，您可以找到很多答案。以最佳方式，您可以从A到B仅移除一条边。

是否有针对此的特定算法？

我发现了一些使用最大流量最小割定理解决此问题的建议，但我并没有获得将这个问题转换为最大流量最小割定理的一般想法。同样，在此过程中，我可能最终会删除F和G之间无用的边缘。