离散数学

discrete mathematics研究离散量的结构及其相互关系的一门数学学科。是现代数学的重要组成部分。形成于本世纪70年代。由于计算机科学是以数据结构、算法和程序设计为核心的，而这些内容所涉及的对象如数据、语言、程序等都是离散的，需要用离散数学的一些基本概念和理论来描述和处理，因此离散数学构成了计算机科学的理论基础。 离散数学的形成与计算机科学的发展有着紧密的联系。离散数学中的许多内容在计算机诞生以前较多地是作为纯数学的内容而被研究的，应用范围不广。随着计算机科学的迅速发展和计算机的广泛应用，在计算机科学及其相关领域中，提出了大量的有关离散对象的理论问题，迫切需要用相应的数学工具去给予合理的描述并加以解决。于是，人们把计算机科学中所涉及的有关研究离散量的数学理论和方法综合在一起，进行系统的、全面的论述，便形成了离散数学这门学科。离散数学这一名称是由美国IEEE计算机协会典型课程分委员会于1974年正式提出的，1976年又把它列为计算机专业的核心课程。 离散数学的内容十分丰富，主要涉及集合论、数理逻辑、代数结构、图论、组合论、可行计算理论等。这些理论，在计算机科学的各个领域中有着极其广泛的应用。例如，数理逻辑是计算机数字电路设计、程序设计的理论基础和有力工具；形式语言的研究不仅需要数理逻辑的基础，还要涉及代数结构中的一些概念和理论；在现代通信系统以及计算机系统设计中，为了保证信息传输的正确性，要研究检错和纠错技术，而群论就是设计检错、纠错码的基本数学工具；图论为含有二元关系的离散系统提供了有效的数学模型，在算法、语言、数据库、网络理论、开关理论、编译技术、操作系统等领域中发挥了重要应用；有效算法的研究是算法理论的核心问题。有效算法是指在合理的时间内能由计算机完成的算法。如果不寻求有效算法，即使计算机的运算速度再快，贮存量再大，许多复杂问题在客观条件限定的时间内仍然得不到解决。而有效算法的研究与组合优化密切相关。 离散数学为计算机科学的发展奠定了基础。反过来，计算机科学的迅速发展又促进了离散数学不断深化、发展。例如1976年阿贝尔等人利用计算机证明了100多年未解决的图论难题——四色问题。又如，计算机的应用推动了近世代数的发展，出现了“计算机代数”。它的应用范围远远超过计算机科学本身，在生物学、化学、量子物理、广义相对论和天体力学中得到重要应用。 （方锦暄）