Techniques I learned in my discrete math course from university helped me quite a bit with the Professor Layton games.
That counts as helpful... right?
There are a lot of real-life examples where map coloring algorithms are helpful, besides just for coloring maps. The question on my final exam had to do with traffic light programming on a six-way intersection.
As San Jacinto indicates, the fundamentals of programming are very much bound up in discrete mathematics. Moreover, 'discrete mathematics' is a very broad term. These things perhaps make it harder to pick out particular examples. I can come up with a handful, but there are many, many others.
Compiler implementation is a good source of examples: obviously there's automata / formal language theory in there; register allocation can be expressed in terms of graph colouring; the classic data flow analyses used in optimizing compilers can be expressed in terms of functions on lattice-like algebraic structures.
A simple example the use of directed graphs is in a build system that takes the dependencies involved in individual tasks by performing a topological sort. I suspect that if you tried to solve this problem without having the concept of a directed graph then you'd probably end up trying to track the dependencies all the way through the build with fiddly book-keeping code (and then finding that your handling of cyclic dependencies was less than elegant).
Clearly most programmers don't write their own optimizing compilers or build systems, so I'll pick an example from my own experience. There is a company that provides road data for satnav systems. They wanted automatic integrity checks on their data, one of which was that the network should all be connected up, i.e. it should be possible to get to anywhere from any starting point. Checking the data by trying to find routes between all pairs of positions would be impractical. However, it is possible to derive a directed graph from the road network data (in such a way as it encodes stuff like turning restrictions, etc) such that the problem is reduced to finding the strongly connected components of the graph - a standard graph-theoretic concept which is solved by an efficient algorithm.
I've been taking a course on software testing, and 3 of the lectures were dedicated to reviewing discrete mathematics, in relation to testing. Thinking about test plans in those terms seems to really help make testing more effective.
Understanding of set theory in particular is especially important for database development.
I'm sure there are numerous other applications, but those are two that come to mind here.
In build systems it's popular to use topological sorting of jobs to do.
By build system I mean any system where we have to manage jobs with dependency relation.
It can be compiling program, generating document, building building, organizing conference - so there is application in task management tools, collaboration tools etc.
Modus tollens 是卡尔·波普尔将科学视为证伪的概念的核心，测试也应该以大致相同的方式进行。我们试图伪造该功能在每种显式和隐式情况下始终有效的说法，而不是试图验证它在狭义上是否有效，即它可以以某种禁止的方式工作。
I believe testing itself properly procedes from modus tollens, a concept of propositional logic (and hence discrete math), modus tollens being:
P=>Q. !Q, therefore !P.
If you plug in "If the feature is working properly, the test will pass" for P=>Q, and then take !Q as given ("the test did not pass"), then, if all these statements are factually correct, you have a valid, sound basis for returning the feature for a fix. By contrast, many, maybe most testers operate by the principle:
"If the program is working properly, the test will pass. The test passed, therefore the program is working properly."
This can be written as: P=>Q. Q, therefore P.
But this is the fallacy of "affirming the consequent" and does not show what the tester believes it shows. That is, they mistakenly believe that the feature has been "validated" and can be shipped. When Q is given, P may in fact either be true or it may be untrue for P=>Q, and this can be shown with a truth table.
Modus tollens is core to Karl Popper's notion of science as falsification, and testing should proceed in much the same way. We're attempting to falsify the claim that the feature always works under every explicit and implicit circumstance, rather than attempting to verify that it works in the narrow sense that it can work in some proscribed way.
发布评论
评论（6）
离散数学已经触及软件开发的各个方面，因为软件开发的核心是以计算机科学为基础的。
http://en.wikipedia.org/wiki/Discrete_math
阅读该链接。您将看到有许多实际应用，尽管此维基百科条目主要涉及理论术语。
Discrete math has touched every aspect of software development, as software development is based on computer science at its core.
http://en.wikipedia.org/wiki/Discrete_math
Read that link. You will see that there are numerous practical applications, although this wikipedia entry speaks mainly in theoretical terms.
我在大学离散数学课程中学到的技术对我玩雷顿教授游戏有很大帮助。
这算是有帮助的......对吧？
除了为地图着色之外，还有很多现实生活中的例子表明地图着色算法很有帮助。我期末考试的问题与六路交叉口的交通灯编程有关。
Techniques I learned in my discrete math course from university helped me quite a bit with the Professor Layton games.
That counts as helpful... right?
There are a lot of real-life examples where map coloring algorithms are helpful, besides just for coloring maps. The question on my final exam had to do with traffic light programming on a six-way intersection.
正如 San Jacinto 所指出的，编程的基础知识与离散数学密切相关。此外，“离散数学”是一个非常广泛的术语。这些事情可能会让挑选特定例子变得更加困难。我能想出一些，但还有很多很多其他的。
编译器实现是一个很好的例子来源：显然其中有自动机/形式语言理论；寄存器分配可以用图形着色来表示；用于优化编译器的经典数据流分析可以用类格代数结构上的函数来表达。
有向图使用的一个简单示例是在构建系统中，该构建系统通过执行拓扑排序来获取各个任务中涉及的依赖关系。我怀疑，如果您尝试在没有有向图概念的情况下解决这个问题，那么您可能最终会尝试使用繁琐的簿记代码在整个构建过程中跟踪依赖关系（然后发现您对循环依赖不太优雅）。
显然，大多数程序员不会编写自己的优化编译器或构建系统，因此我将从我自己的经验中选择一个示例。有一家公司为卫星导航系统提供道路数据。他们希望对数据进行自动完整性检查，其中之一是网络应该全部连接起来，即应该可以从任何起点到达任何地方。通过尝试查找所有位置对之间的路线来检查数据是不切实际的。然而，可以从道路网络数据中导出有向图（以编码转弯限制等内容的方式），从而将问题简化为找到图的强连接组件 - 标准图 -通过有效算法解决的理论概念。
As San Jacinto indicates, the fundamentals of programming are very much bound up in discrete mathematics. Moreover, 'discrete mathematics' is a very broad term. These things perhaps make it harder to pick out particular examples. I can come up with a handful, but there are many, many others.
Compiler implementation is a good source of examples: obviously there's automata / formal language theory in there; register allocation can be expressed in terms of graph colouring; the classic data flow analyses used in optimizing compilers can be expressed in terms of functions on lattice-like algebraic structures.
A simple example the use of directed graphs is in a build system that takes the dependencies involved in individual tasks by performing a topological sort. I suspect that if you tried to solve this problem without having the concept of a directed graph then you'd probably end up trying to track the dependencies all the way through the build with fiddly book-keeping code (and then finding that your handling of cyclic dependencies was less than elegant).
Clearly most programmers don't write their own optimizing compilers or build systems, so I'll pick an example from my own experience. There is a company that provides road data for satnav systems. They wanted automatic integrity checks on their data, one of which was that the network should all be connected up, i.e. it should be possible to get to anywhere from any starting point. Checking the data by trying to find routes between all pairs of positions would be impractical. However, it is possible to derive a directed graph from the road network data (in such a way as it encodes stuff like turning restrictions, etc) such that the problem is reduced to finding the strongly connected components of the graph - a standard graph-theoretic concept which is solved by an efficient algorithm.
我一直在学习软件测试课程，其中 3 个讲座专门讨论与测试相关的离散数学。从这些角度思考测试计划似乎确实有助于提高测试效率。
对集合论的理解对于数据库开发尤其重要。
我确信还有许多其他应用程序，但这里想到的是这两个。
I've been taking a course on software testing, and 3 of the lectures were dedicated to reviewing discrete mathematics, in relation to testing. Thinking about test plans in those terms seems to really help make testing more effective.
Understanding of set theory in particular is especially important for database development.
I'm sure there are numerous other applications, but those are two that come to mind here.
只是众多例子之一......
在构建系统中，流行使用作业的拓扑排序来完成。
我所说的构建系统是指我们必须管理具有依赖关系的作业的任何系统。
它可以编译程序、生成文档、搭建建筑、组织会议——因此在任务管理工具、协作工具等方面都有应用。
Just example of one of many many...
In build systems it's popular to use topological sorting of jobs to do.
By build system I mean any system where we have to manage jobs with dependency relation.
It can be compiling program, generating document, building building, organizing conference - so there is application in task management tools, collaboration tools etc.
我相信测试本身正确地从 modus tollens 出发，modus tollens 是命题逻辑（以及离散数学）的概念，modus tollens 是：
P=>Q。 ！Q，因此！P。
如果您在 P=>Q 中插入“如果该功能正常工作，测试将通过”，然后将 !Q 视为给定（“测试未通过”），那么，如果所有这些陈述实际上都是正确的，您就有了返回该功能进行修复的有效、合理的基础。相比之下，许多（也许是大多数）测试人员的操作原则是：
“如果程序正常工作，测试就会通过。测试通过了，因此程序工作正常。”
这可以写成：P＝＞Q。 Q，因此 P。
但这是“肯定结果”的谬误，并且没有显示测试人员认为它显示的内容。也就是说，他们错误地认为该功能已经“验证”并且可以发货。当给定Q时，P实际上可能为真，也可能为不真，因为P＝＞Q，并且这可以用真值表来示出。
Modus tollens 是卡尔·波普尔将科学视为证伪的概念的核心，测试也应该以大致相同的方式进行。我们试图伪造该功能在每种显式和隐式情况下始终有效的说法，而不是试图验证它在狭义上是否有效，即它可以以某种禁止的方式工作。
I believe testing itself properly procedes from modus tollens, a concept of propositional logic (and hence discrete math), modus tollens being:
P=>Q. !Q, therefore !P.
If you plug in "If the feature is working properly, the test will pass" for P=>Q, and then take !Q as given ("the test did not pass"), then, if all these statements are factually correct, you have a valid, sound basis for returning the feature for a fix. By contrast, many, maybe most testers operate by the principle:
"If the program is working properly, the test will pass. The test passed, therefore the program is working properly."
This can be written as: P=>Q. Q, therefore P.
But this is the fallacy of "affirming the consequent" and does not show what the tester believes it shows. That is, they mistakenly believe that the feature has been "validated" and can be shipped. When Q is given, P may in fact either be true or it may be untrue for P=>Q, and this can be shown with a truth table.
Modus tollens is core to Karl Popper's notion of science as falsification, and testing should proceed in much the same way. We're attempting to falsify the claim that the feature always works under every explicit and implicit circumstance, rather than attempting to verify that it works in the narrow sense that it can work in some proscribed way.