问题标签 [discrete-mathematics]

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

许多大学提供离散结构课程。还有很多DS教科书。但是当我查看课程大纲和教科书介绍时，从未使用过“离散结构”一词；他们改用“离散数学”。DS 仅出现在课程/教科书的标题中。

例子：

ODU 的 CS 381

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

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

我将教授离散结构的低年级课程。我之所以选择教科书《离散结构、逻辑和可计算性》，部分原因是它包含有助于使用函数式编程语言实现的示例和概念。（我也认为这是一本很好的教科书。）

我想要一种易于理解的 FP 语言来说明 DS 概念并且学生可以使用。大多数学生最多只有一两个学期的 Java 编程。在查看了 Scheme、Erlang、Haskell、Ocaml 和 SML 之后，我选择了 Haskell 或 Standard ML。出于以下概述的原因，我倾向于 Haskell，但我希望那些在其中一个或另一个中活跃的程序员的意见。

• Haskell 和 SML 都具有模式匹配，这使得描述递归算法变得轻而易举。
• Haskell 有很好的列表推导，可以很好地匹配这些列表的数学表达方式。
• Haskell 有惰性求值。非常适合使用列表理解技术构建无限列表。
• SML 有一个真正的交互式解释器，可以在其中定义和使用函数。在 Haskell 中，函数必须在单独的文件中定义并在用于交互式 shell 之前进行编译。
• SML 以易于理解的语法明确确认函数参数和返回类型。例如：val foo = fn : int * int -> int。Haskell 的隐式 curry 语法有点迟钝，但并不完全陌生。例如：foo :: Int -> Int -> Int。
• Haskell 默认使用任意精度的整数。它是 SML/NJ 中的一个外部库。SML/NJ 默认将输出截断为 70 个字符。
• Haskell 的 lambda 语法很微妙——它使用单个反斜杠。SML 更明确。不过，不确定我们是否会在这个类中需要 lambda。

本质上，SML 和 Haskell 大致等价。我倾向于 Haskell，因为我喜欢 Haskell 中的列表推导和无限列表。但我担心 Haskell 紧凑语法中大量的符号可能会给学生带来问题。根据我在 SO 上阅读其他帖子所收集到的信息，不建议从 FP 开始的初学者使用 Haskell。但我们不会构建成熟的应用程序，只是尝试简单的算法。

你怎么看？

编辑：在阅读了您的一些出色回复后，我应该澄清一些要点。

在 SML 中，在解释器中定义函数和在外部文件中定义函数之间没有语法上的区别。假设您要编写阶乘函数。在 Haskell 中，您可以将此定义放入文件中并将其加载到 GHCi 中：

对我来说，这很清楚、简洁，并且符合书中的数学定义。但是如果你想直接在 GHCi 中编写函数，你必须使用不同的语法：

当使用交互式解释器时，从教学的角度来看，当学生可以在文件和命令行中使用相同的代码时，非常非常方便。

“显式确认函数”是指在定义函数时，SML 会立即告诉您函数的名称、参数的类型和返回类型。在 Haskell 中，你必须使用:type命令，然后你会得到有点令人困惑的咖喱符号。

Haskell 还有一件很酷的事情——这是一个有效的函数定义：

同样，这符合他们可能在教科书中找到的定义。在 SML 中不能这样做！

为了使 Boyer-Moore 算法成为最坏情况线性，失配表的计算必须是 O(m)。然而，一个简单的实现将遍历所有后缀 O(m) 以及该后缀中的所有位置可以检查是否相等......这是 O(m ³ )！

下面是建表算法的简单实现。所以这个问题变成了：我怎样才能把这个算法的运行时间提高到 O(m)？

为了让思想休息，这不是家庭作业。当有人发布改进想法时，我会添加修订。

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

例如

我正在尝试为以下语句构造一个反例：如果 A 为 0 或 B 为 0，则 A*B 为 0。

这是我的尝试：如果 A*B 不是 0，那么 A 不是 0 或 B 不是 0。

原始陈述是正确的，但是相反的陈述是错误的，因为 A和B 都必须非零才能使 A*B 非零......我做错了什么吗？

我正在为离散数学考试而学习，但我发现了这个我无法弄清楚的练习。

“为字母 Sigma = {0,1,2} 中的语言构建一个基本的有限自动机 (DFA,NFA,NFA-lambda)，其中字符串中元素的总和是偶数并且这个总和大于 3”

我尝试使用 Kleene 的定理连接两种语言，例如连接与此正则表达式相关的一种语言：

(00 U 11 U 22 U 02 U 20)*- 偶数元素

有了这个

(22 U 1111 U 222 U 2222)*- 总和大于 3 的那些

这有道理吗？？我认为我的正则表达式很松散。

我在网上浏览了具体数学的内容。我至少听说过提到的大部分功能和技巧，但有一整节是关于特殊数字的。这些数字包括斯特林数、欧拉数、谐波数等。现在我从来没有遇到过这些奇怪的数字。它们如何帮助解决计算问题？它们一般用在什么地方？

一个具体的例子

我需要生成一个介于 0 和 2 之间的随机数，包括 0 和 2。（或在 -1、0 和 1 之间随机选择）。

天真的方法是执行类似rand() mod 3whererand()返回整数的操作。这种方法不会生成统计上的随机数，除非 的上界rand()不是互质的（下界为 0）。

例如，假设 rand() 返回 2 位（从 0 到 3，包括），模数将映射：

0 -> 0
1 -> 1
2 -> 2
3 -> 0

如果返回更多位，则这种向 0 的偏斜显然会小得多，但无论如何，偏斜将保持不变。

一般问题

有没有办法在 0 和 n-1 之间生成一个均匀分布的随机数，其中 n 与 2 互质？

假设一个游戏中一个人掷出 20 个 8 面骰子，总共有 8^20 种可能的结果。为了计算特定事件发生的概率，我们将事件发生的方式数除以 8^20。

可以计算出正确获得 5 个骰子值 3 的方法的数量。（20 选择 5）给了我们 3 的订单数量。7^15 给了我们在 15 次掷骰中无法获得 3 的方式的数量.

答案也可以看成我可以用多少种方式重新排列字符串 3,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0,0,0 ,0,0（20 选择 5）乘以我们为零的值的总数（假设 7 个合法值）7^15（这是正确的）。

• 问题 1：我如何计算获得完全相同值的 5 个骰子的方法数量（即，对于所有骰子值）。注意：如果我只是天真地使用上面的第一个答案并乘以 bt 8，我会得到大量的重复计算吗？

  我知道我可以解决每种情况 (5 1's), (5, 2's), (5, 3's), ... (5's, 8) 对它们求和（更简单地说 8*(5 1's) ）。然后减去重叠数的总和 (5 1's) 和 (5 2's), (5 1's) 和 (5 3's)... (5 1's) 和 (5, 2's) 和 ...和 ​​(5, 8's)但这似乎非常混乱。我会以一种扩展到大量样本和大量类的方式对此进行概括。

• 如何计算获得至少5 个相同值的骰子的方法数？

  所以 111110000000000000000 或 11110100000000000002 或 11111100000001110000 或 11011211222222223333，但不是 00001111222233334444 或 0630511514225。

我正在寻找解释数学或指向支持此的库（尤其是 python 模块）的答案。细节和例子的加分。

给定一个大的稀疏矩阵（比如 10k+ x 1M+）​​，我需要找到一个子集，不一定是连续的，形成密集矩阵（所有非零元素）的行和列。我希望这个子矩阵在某些纵横比约束内尽可能大（不是最大的总和，而是最大的元素数量）。

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

在 Google 上快速浏览一下似乎会给出很多接近但不完全准确的结果。我应该寻找哪些条款？

编辑：只是为了澄清；子矩阵不必是连续的。事实上，行和列的顺序是完全任意的，所以相邻性是完全无关的。

基于 Chad Okere 的想法

1. 将行从最大计数排序到最小计数（不是必需的，但可能有助于提高性能）
2. 选择具有“大”重叠的两行
3. 添加不会减少重叠的所有其他行
4. 记录那套
5. 添加任何行以最少的方式减少重叠
6. 在 #3 重复，直到结果变小
7. 使用不同的起始对从 #2 重新开始
8. 继续直到你认为结果足够好