问题标签 [discrete-mathematics]

所以我正在从麻省理工学院的 OpenCourseWare 学习离散数学课程，我想知道......我看到了关系和图形之间的联系，但还不足以“拥有”它。我也在 SQL 中实现了一个简单的状态机，所以我很好地理解了图表，只是没有更严格地研究关系和集合是如何应用的。我是否应该遵循 Yegge 的思路，只浏览那些我不喜欢摸索的东西，等我学到更多东西后再回来？我希望能够更好地分析我每天创建的图形结构（听起来很有趣），并且我想确保我现在没有传递有价值的信息。

（编辑：我想更好地了解不同的集合和关系属性如何与图论等事物相关，以及基本图论如何与集合/关系相关。）

有什么好的资源可以让我了解更多信息吗？我正在使用 Rosen 的第 5 版离散数学及其应用，以防万一。

谢谢！

数学技能变得越来越重要，我想知道在继续学习更多 CompSci 特定内容之前，哪里是复习一些基础知识的好地方？

一个拥有大量视频和练习的网站将是双赢的，但我似乎找不到。

离散数学（也是有限数学）处理诸如逻辑、集合论、信息论、部分有序集合、证明、关系和许多其他主题的主题。

对于其他数学分支，也有支持编程的工具。对于统计，R和S内置了许多有用的统计函数。对于数值分析，Octave可以用作语言或集成到 C++ 中。

我不知道任何专门处理离散数学的语言或包（尽管几乎每种语言都可用于实现离散数学中使用的算法，但应该有专门为这些应用程序设计的库或环境）。

我对如何将一组序列映射到连续整数感到困惑。

所有的序列都遵循这个规则：

我正在寻找一种解决方案，它能够在给定这样的序列的情况下计算一个整数以查找表并给定表中的索引，生成序列。

示例：对于长度 3，有 5 个有效序列。执行以下地图（最好是双向）的快速功能将是一个很好的解决方案

• 练习的重点是获得一个在有效序列和单元格之间具有 1-1 映射的打包表。
• 集合的大小仅受可能的唯一序列数的限制。
• 我现在不知道序列的长度是多少，但它会是一个很小的，<12，预先知道的常数。
• 我迟早会谈到这个，但我会把它扔掉，让社区在此期间获得“乐趣”。

这些是不同的有效序列

这些不是

与此相关

每个节点都连接到每个其他节点（没有冗余连接）的图是如何调用的？

我知道这张图有 N * (N - 1) / 2 条边。

我正在开发一个应用程序，可以优化地为医院的护士分配轮班。我相信这是一个离散变量的线性规划问题，因此可能是 NP-hard：

• 每天，每位护士（约 15-20 名）都被分配一个轮班
• 有少量（约 6 个）不同的班次
• 有相当多的约束和优化标准，无论是与一天有关，还是与员工有关，例如：
  • 每天必须为每个班次分配最少人数
  • 一些班次重叠，因此如果有人在做中间班次，则可以在早期班次少一个人
  • 有些人更喜欢早班，有些人更喜欢晚班，但需要最少的换班才能获得更高的轮班工作工资。
  • 一个人一天不能晚班，第二天早班（由于最低休息时间规定）
  • 会议分配的工作周长度（不同的人不同）
  • ...

所以基本上有大量（大约 20*30 = 600）个变量，每个变量都可以取少量的离散值。

目前，我的计划是使用修改后的最小冲突算法

• 从随机分配开始
• 对每个人和每一天都有一个健身功能
• 选择健身值最差的人或日子
• 为那一天/人随机选择一项任务，并将其设置为产生最佳适应度值的值
• 重复直到达到最大迭代次数或对于选定的日期/人无法找到改进

有更好的想法吗？我有点担心它会陷入局部最优。我应该使用某种形式的模拟退火吗？或者不仅考虑一次只改变一个变量，还特别考虑两个人之间的轮班切换（当前手动算法的主要组成部分）？我想避免根据当前的约束来定制算法，因为这些可能会改变。

编辑：没有必要找到严格的最优解；名册目前是手动完成的，我很确定结果在大多数情况下都不是最理想的——应该不难打败它。短期调整和手动覆盖也肯定是必要的，但我不认为这会是一个问题；将过去和手动分配标记为“固定”实际上应该通过减少解决方案空间来简化任务。

我正在寻找一种使用离散和快速方法计算导数的方法。因为现在我不知道我所拥有的方程的类型，所以我正在寻找类似于我们可以找到的积分方法的离散方法，例如欧拉方法。

我需要检查关系是否传递？

您能否建议一些算法来检查关系的传递性？

我将关系存储为布尔矩阵，如果元素相关，则为1 ，否则为0，如图形中。

谢谢。

我目前使用的算法很快就会遇到非常高的数字。我要在算法中的一个步骤将x提高到应用于y的 totient 函数的结果。结果是您可能会遇到非常大的数字。

例如。计算10 模 53的乘法阶数时：

以下算法在避免大数字方面表现更好，但在10^mOrder大于数据类型的容量时仍然失败：

恐怕这个问题有点技术性，但我希望有人可能偶然发现了类似的主题，或者给我一些指示。

如果 G 是一个群（在代数结构的意义上），并且如果 g ₁ , ..., g _n是 G 的元素，是否有算法（或某些专用程序中的函数，如 GAP）来确定是否存在是 G 的一个子群，使得这些元素构成该子群陪集的一组代表？（我们可以假设 G 是一个置换群，甚至可能是完全对称群。）

（当然有几种算法可以找到给定子群的陪集，例如 Todd-Coxeter 算法；这是一种逆问题。）

谢谢，丹尼尔