离散数学

离散数学 课程作用

 

离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。

离散数学 发展方向

 

离散数学自身研究方面的进展随着计算机的发展而深入，特别在研究智能推理的非经典逻辑方面，在代数结构的深入探讨方面，在图论与群论相互结合的理论方面都有大量的新成果出现。随着计算机科学的发展，离散数学在上述各方面的研究将更加深入，且更具吸引力。新的，具有创造性的研究成果将会层出不穷，其研究的方向宽广且前景光明。

离散数学网络课程的建设还是一个较新的课题，需要做的工作还很多。比如，声音图形信息的科学处理，数据库之间的智能化管理，定理的自动证明，试卷的随机生成等等都是摆在课题研究面前的任务。因此，除了网络课程建设基本的工作外，还有大量的前沿性问题有待解决。离散数学网络课程的发展趋势还会向更专业，更尖端，更深入且更便于读者使用的方向迈进。

离散数学 参考资料

 

1.http://tieba.baidu.com/f?kz=74724382

2.http://www.jpk.pku.edu.cn/pkujpk/course/lssx/intro.htm

3.http://class.htu.cn/lisanshuxue/kechengjianjie.htm

离散数学 离散数学在生活中的应用

 

  组合数学

       有人认为广义的组合数学就是离散数学，也有人认为离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别。总之，组合数学是一门研究离散对象的科学。随着计算机科学的日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据。

       狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化等。

组合数学中的著名问题
       地图着色问题：对世界地图着色，每一种国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？这是图论的问题。
四色定理指出每个可以画出来的地图都可以至多用4种颜色来上色，而且没有两个相接的区域会是相同的颜色。被称为相接的两个区域是指他们共有一段边界，而不是一个点。

       这一定理最初是由FrancisGuthrie在1853年提出的猜想。很明显，3种颜色不会满足条件，而且也不难证明5种颜色满足条件且绰绰有余。但是，直到1977年四色猜想才最终由KennethAppel和WolfgangHaken证明。他们得到了J.Koch在算法工作上的支持。

      证明方法将地图上的无限种可能情况减少为1,936种状态（稍后减少为1,476种），这些状态由计算机一个挨一个的进行检查。这一工作由不同的程序和计算机独立的进行了复检。在1996年，NeilRobertson、DanielSanders、PaulSeymour和RobinThomas使用了一种类似的证明方法，检查了633种特殊的情况。这一新证明也使用了计算机，如果由人工来检查的话是不切实际的。

四色定理是第一个主要由计算机证明的理论，这一证明并不被所有的数学家接受，因为它不能由人工直接验证。最终，人们必须对计算机编译的正确性以及运行这一程序的硬件设备充分信任。参见实验数学。

       缺乏数学应有的规范成为了另一个方面；以至于有人这样评论“一个好的数学证明应当像一首诗——而这纯粹是一本电话簿！”

       船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？这是线性规划的问题。
       中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。这也是图论的问题。
任务分配问题（也称婚配问题）：有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少？这是线性规划的问题。