离散数学和组合数学

快捷方式: 差异，相似，杰卡德相似系数，参考。

离散数学和组合数学之间的区别

离散数学 vs. 组合数学

离散数学（Discrete mathematics）是数学的几个分支的总称，研究基于离散空间而不是连续的数学结构。与連續变化的实数不同，离散数学的研究对象——例如整数、图和数学逻辑中的命题——不是連續变化的，而是拥有不等、分立的值。因此离散数学不包含微积分和分析等「连续数学」的内容。离散对象经常可以用整数来枚举。更一般地，离散数学被视为处理可数集合（与整数子集基数相同的集合，包括有理数集但不包括实数集）的数学分支。 。但是，“离散数学”不存在准确且普遍认可的定义。实际上，离散数学经常被定义为不包含连续变化量及相关概念的数学，甚少被定义为包含什么内容的数学。 离散数学中的对象集合可以是有限或者是无限的。有限数学一词通常指代离散数学处理有限集合的那些部分，特别是在与商业相关的领域。 隨著電腦科學的飛速發展，離散數學的重要性則日益彰顯。它為許多資訊科學課程提供了數學基礎，包括資料結構、演算法、資料庫理論、形式語言與作業系統等。如果沒有離散數學的相關數學基礎，學生在學習上述課程中，便會遇到較多的困難。此外，離散數學也包含了解決作業研究、化學、工程學、生物學等眾多領域的數學背景。由於運算對象是離散的，所以電腦科學的數學基礎基本上也是離散的。我們可以說電腦科學的數學語言就是離散數學。人們會使用離散數學裡面的槪念和表示方法，來研究和描述電腦科學下所有分支的對象和問題，如電腦運算、程式語言、密碼學、自動定理証明和軟件開發等。相反地，计算机的應用使離散數學的概念得以應用於日常生活當中（如運籌學）。 虽然离散数学的主要研究对象是离散对象，但是连续数学的分析方法往往也可以采用。数论就是离散和连续数学的交叉学科。同样的，有限拓扑（对有限拓扑空间的研究）从字面上可看作离散化和拓扑的交集。. 广义的组合数学（Combinatorics）就是离散数学，狭义的组合数学是组合计数、图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别。总之，组合数学是一门研究可數或离散对象的科学。随着计算机科学的日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据。 狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。 组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化（最佳組合）等。.

代数结构

在泛代数中代数结构是在一种或多种运算下封闭的一个或多个集合。 例如，群、环、域、和格的代数结构。更复杂的结构可以被定义为通过引入多个操作，不同的基础集，或通过改变限定公理。更复杂的代数结构的实例包括向量空间，模和代數 (環論)。关于代数结构的的详细情况，参见各个链接。 一个代数结构包含集合及符合某些公理的运算或关系。 集U上定义二元运算形成的系统称为代数系统，如果对于任意a,b∈U,恒有（a·b)∈U。二元运算可推广至多元运算F,则相应的封闭性要求则改为：对于任意a,b,c,d,……∈U,恒有F(a,b,c,d,……)∈U。有的书上对封闭性未作要求，并称之为广群。运算f是一个从A×B→C的映射，若A.

代数结构和离散数学 · 代数结构和组合数学 · 查看更多 »

图论

图论（Graph theory）是组合数学的一个分支，和其他数学分支，如群论、矩阵论、拓扑学有着密切关系。图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。 图论起源于著名的柯尼斯堡七桥问题。该问题于1736年被欧拉解决，因此普遍认为欧拉是图论的创始人。 图论的研究对象相当于一维的单纯复形。.

图论和离散数学 · 图论和组合数学 · 查看更多 »

四色定理

四色定理是一个著名的数学定理：如果在平面上劃出一些邻接的有限区域，那么可以用四种颜色来给这些区域染色，使得每两个邻接区域染的颜色都不一样；另一个通俗的说法是：每个无外飞地的地图都可以用不多於四种颜色来染色，而且不會有两个邻接的区域颜色相同。被称为邻接的两个区域是指它们有一段公共的边界，而不仅仅是一个公共的交点。例如右图左下角的圆形中，红色部分和绿色部分是邻接的区域，而黄色部分和红色部分则不是邻接区域。 “是否只用四种颜色就能为所有地图染色”的问题最早是由一位英国制图员在1852年提出的，被称为“四色问题”或“四色猜想”。人们发现，要证明宽松一点的“五色定理”（即“只用五种颜色就能为所有地图染色”）很容易，但四色问题却出人意料地异常困难。曾经有许多人发表四色问题的证明或反例，但都被证实是错误的。 1976年，数学家凱尼斯·阿佩爾和沃夫冈·哈肯借助电子计算机首次得到一个完全的证明，四色问题也终于成为四色定理。这是首个主要借助计算机证明的定理。这个证明一开始并不为许多数学家接受，因为不少人认为这个证明无法用人手直接验证。尽管随着计算机的普及，数学界对计算机辅助证明更能接受，但仍有数学家希望能够找到更简洁或不借助计算机的证明。.

四色定理和离散数学 · 四色定理和组合数学 · 查看更多 »

算法

-- 算法（algorithm），在數學（算學）和電腦科學之中，為任何良定义的具體計算步驟的一个序列，常用於計算、和自動推理。精確而言，算法是一個表示爲有限長列表的。算法應包含清晰定義的指令用於計算函數。 算法中的指令描述的是一個計算，當其時能從一個初始狀態和初始輸入（可能爲空）開始，經過一系列有限而清晰定義的狀態最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化算法在内的一些算法，包含了一些隨機輸入。 形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，並在其后尝试定义或者中成形。这些尝试包括库尔特·哥德尔、雅克·埃尔布朗和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算，1936年的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前，依然常有直覺想法難以定義爲形式化算法的情況。.

离散数学和算法 · 算法和组合数学 · 查看更多 »

线性规划

在數學中，線性規劃（Linear Programming，簡稱LP）特指目標函數和約束條件皆為線性的最優化問題。 線性規劃是最優化問題中的一個重要領域。在作業研究中所面臨的許多實際問題都可以用線性規劃來處理，特別是某些特殊情況，例如：網路流、多商品流量等問題，都被認為非常重要。目前已有大量針對線性規劃算法的研究。很多最優化問題算法都可以分解為線性規劃子問題，然後逐一求解。在線性規劃的歷史發展過程中所衍伸出的諸多概念，建立了最優化理論的核心思維，例如「對偶」、「分解」、「凸集」的重要性及其一般化等。在微观经济学和商业管理领域中，线性规划亦被大量应用于例如降低生产过程的成本等手段，最終提升產值與營收。乔治·丹齐格被認爲是线性规划之父。.

离散数学和线性规划 · 线性规划和组合数学 · 查看更多 »

计算机科学

计算机科学用于解决信息与计算的理论基础，以及实现和应用它们的实用技术。 计算机科学（computer science，有时缩写为CS）是系统性研究信息与计算的理论基础以及它们在计算机系统中如何与应用的实用技术的学科。 它通常被形容为对那些创造、描述以及转换信息的算法处理的系统研究。计算机科学包含很多分支领域；有些强调特定结果的计算，比如计算机图形学；而有些是探討计算问题的性质，比如计算复杂性理论；还有一些领域專注于怎样实现计算，比如程式語言理論是研究描述计算的方法，而程式设计是应用特定的程式語言解决特定的计算问题，人机交互则是專注于怎样使计算机和计算变得有用、好用，以及随时随地为人所用。 有时公众会误以为计算机科学就是解决计算机问题的事业（比如信息技术），或者只是与使用计算机的经验有关，如玩游戏、上网或者文字处理。其实计算机科学所关注的，不仅仅是去理解实现类似游戏、浏览器这些软件的程序的性质，更要通过现有的知识创造新的程序或者改进已有的程序。 尽管计算机科学（computer science）的名字里包含计算机这几个字，但实际上计算机科学相当数量的领域都不涉及计算机本身的研究。因此，一些新的名字被提议出来。某些重点大学的院系倾向于术语计算科学（computing science），以精确强调两者之间的不同。丹麦科学家Peter Naur建议使用术语"datalogy"，以反映这一事实，即科学学科是围绕着数据和数据处理，而不一定要涉及计算机。第一个使用这个术语的科学机构是哥本哈根大学Datalogy学院，该学院成立于1969年，Peter Naur便是第一任教授。这个术语主要被用于北欧国家。同时，在计算技术发展初期，《ACM通讯》建议了一些针对计算领域从业人员的术语：turingineer，turologist，flow-charts-man，applied meta-mathematician及applied epistemologist。 三个月后在同样的期刊上，comptologist被提出，第二年又变成了hypologist。 术语computics也曾经被提议过。在欧洲大陆，起源于信息（information）和数学或者自动（automatic）的名字比起源于计算机或者计算（computation）更常见，如informatique（法语），Informatik（德语），informatika（斯拉夫语族）。 著名计算机科学家Edsger Dijkstra曾经指出：“计算机科学并不只是关于计算机，就像天文学并不只是关于望远镜一样。”（"Computer science is no more about computers than astronomy is about telescopes."）设计、部署计算机和计算机系统通常被认为是非计算机科学学科的领域。例如，研究计算机硬件被看作是计算机工程的一部分，而对于商业计算机系统的研究和部署被称为信息技术或者信息系统。然而，现如今也越来越多地融合了各类计算机相关学科的思想。计算机科学研究也经常与其它学科交叉，比如心理学，认知科学，语言学，数学，物理学，统计学和经济学。 计算机科学被认为比其它科学学科与数学的联系更加密切，一些观察者说计算就是一门数学科学。 早期计算机科学受数学研究成果的影响很大，如Kurt Gödel和Alan Turing，这两个领域在某些学科，例如数理逻辑、范畴论、域理论和代数，也不断有有益的思想交流。.

离散数学和计算机科学 · 组合数学和计算机科学 · 查看更多 »

数理逻辑

数理逻辑是数学的一个分支，其研究对象是对证明和计算这两个直观概念进行符号化以后的形式系统。数理逻辑是数学基础的一个不可缺少的组成部分。 数理逻辑的研究范围是逻辑中可被数学模式化的部分。以前称为符号逻辑（相对于哲学逻辑），又称元数学，后者的使用现已局限于证明论的某些方面。.

数理逻辑和离散数学 · 数理逻辑和组合数学 · 查看更多 »