寻找离散数学知识有用的例子

Question

在看了Michael Feather的SCNA演讲"Self-Education and the Craftsman“之后，我很感兴趣地听到了软件开发中离散数学被证明是有帮助的实际例子。

Answer 1

离散数学已经触及了软件开发的方方面面，因为软件开发的核心是计算机科学。

http://en.wikipedia.org/wiki/Discrete_math

请阅读该链接。您将看到有许多实际应用，尽管这篇维基百科条目主要是从理论上讲的。

Answer 2

我在大学离散数学课上学到的技巧对我玩Layton教授游戏有很大帮助。

这算是有帮助的..。对吗？

除了为地图着色之外，还有许多现实生活中的例子表明地图着色算法是有帮助的。我期末考试的题目是关于六向十字路口的红绿灯编程。

Answer 3

正如圣哈辛托所指出的那样，编程的基本原理与离散数学密切相关。此外，“离散数学”是一个非常宽泛的术语。这些事情可能会让挑选特定的例子变得更加困难。我可以想出几个，但还有很多其他的。

编译器实现是一个很好的例子来源:显然，其中有自动机/形式语言理论；寄存器分配可以用图着色来表示；用于优化编译器的经典数据流分析可以用格型代数结构上的函数来表示。

一个简单的例子是在构建系统中使用有向图，该系统通过执行拓扑排序来获取单个任务中涉及的依赖项。我怀疑，如果您试图在没有有向图的概念的情况下解决这个问题，那么您最终可能会试图通过繁琐的记账代码来跟踪整个构建过程中的依赖项(然后发现您对循环依赖项的处理不够优雅)。

显然，大多数程序员不会编写自己的优化编译器或构建系统，所以我将从自己的经验中选择一个示例。有一家公司为卫星导航系统提供道路数据。他们希望对数据进行自动完整性检查，其中之一是网络应该全部连接起来，即应该可以从任何起点到达任何地方。通过尝试找到所有位置对之间的路径来检查数据将是不切实际的。然而，可以从道路网络数据中推导出有向图(以某种方式对转弯限制等内容进行编码)，从而将问题简化为寻找图的强连接分量-这是一个标准的图论概念，可通过有效的算法解决。