徽标
联盟百科
通讯
下载应用,请到 Google Play
新! 在您的Android™设备上下载联盟百科!
下载
比浏览器更快的访问!
 

组合数学

指数 组合数学

广义的组合数学(Combinatorics)就是离散数学,狭义的组合数学是组合计数、图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别。总之,组合数学是一门研究可數或离散对象的科学。随着计算机科学的日益发展,组合数学的重要性也日渐凸显,因为计算机科学的核心内容是使用算法处理离散数据。 狭义的组合数学主要研究满足一定条件的组态(也称组合模型)的存在、计数以及构造等方面的问题。 组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化(最佳組合)等。.

24 关系: 中華民國公益彩券一笔画问题幻方代数结构任务分配问题六合彩图论四色定理离散数学算法线性规划组合优化组合计数置換組合狐狸、鹅、豆子问题階乘计算机科学賽馬邮递员问题自然数NP完全数理逻辑整數分拆

中華民國公益彩券

公益彩券統一識別標誌 中華民國公益彩券為臺灣的博彩,從1999年12月1日開始發行,法源依據為1995年7月公佈施行的《公益彩券發行條例》,以提升社會福利為主要目的之一。每五年換發行業者,第二標起改成七年換發行業者。第四標起改為十年換發行業者。.

新!!: 组合数学和中華民國公益彩券 · 查看更多 »

一笔画问题

一笔画问题是图论中一个著名的问题。一笔画问题起源于柯尼斯堡七桥问题。数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题,也提出了一笔画定理,顺带解决了一笔画问题Janet Heine Barnett, 。一般认为,欧拉的研究是图论的开端。 与一笔画问题相对应的一个图论问题是哈密顿问题。.

新!!: 组合数学和一笔画问题 · 查看更多 »

幻方

幻方,有时又称魔方(该称呼现一般指立方体的魔術方塊)或纵横图,由一组排放在正方形中的整数组成,其每行、每列以及两条对角线上的数之和均相等。通常幻方由从1到N^2的连续整数组成,其中N为正方形的行或列的数目。因此N阶幻方有N行N列,并且所填充的数为从1到N^2。 幻方可以使用N阶方阵来表示,方阵的每行、每列以及两条对角线的和都等于常数M_2(N),如果填充数为1,2,\dots,N^2,那么有.

新!!: 组合数学和幻方 · 查看更多 »

代数结构

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

新!!: 组合数学和代数结构 · 查看更多 »

任务分配问题

任务分配问题是在加权二分图中寻找最大(或最小)加权匹配的问题。.

新!!: 组合数学和任务分配问题 · 查看更多 »

六合彩

2009年版本六合彩彩票 六合彩(Mark Six)是香港唯一的合法彩票,亦是少數獲香港政府准許合法進行的賭博之一。但六合彩在中国大陆地区属违法行为。 香港政府規定未滿18歲人士,一律不得進行投--。非香港居民亦可於香港境內投--六合彩,但不可在境外投--。.

新!!: 组合数学和六合彩 · 查看更多 »

图论

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

新!!: 组合数学和图论 · 查看更多 »

四色定理

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

新!!: 组合数学和四色定理 · 查看更多 »

离散数学

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

新!!: 组合数学和离散数学 · 查看更多 »

算法

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

新!!: 组合数学和算法 · 查看更多 »

线性规划

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

新!!: 组合数学和线性规划 · 查看更多 »

组合优化

组合最优化,在应用数学和理论计算机科学的领域中,组合优化是在一个有限的对象集中找出最优对象的一类课题。在很多组合优化的问题中,穷举搜索/枚举法是不可行的。组合优化的问题的特征是可行解的集是离散或者可以简化到离散的,并且目标是找到最优解。常见的例子有旅行商问题和最小生成樹。二维的例子,比如服装厂做衣服,衣服分成很多块,这些块需要从布料上切下来。怎么切,剩下的废布料最少?三维的例子,如集装优化。 组合优化的难处,主要是加进来拓扑分析,不同的拓扑形态下,不同部分的约束关系便不同,算法也就要调整。如果给定一个拓扑形态,组合优化往往就退化成一个整数优化的问题了。 Category:應用數學.

新!!: 组合数学和组合优化 · 查看更多 »

组合计数

组合计数是组合数学中最基本也是最古老的内容之一。研究的最基本问题是:满足特定条件下的计数对象的数目。所运用的方法,较古典的有生成函数、组合双射、分析等,近代则有大量概率论、现代代数结构的方法。 category:组合计数.

新!!: 组合数学和组合计数 · 查看更多 »

置換

排列(Permutation)是將相異物件或符號根據確定的順序重排。每個順序都稱作一個排列對於不排序的情形,請見條目組合。。例如,從一到六的數字有720種排列,對應於由這些數字組成的所有不重複亦不闕漏的序列,例如"4, 5, 6, 1, 2, 3" 與1, 3, 5, 2, 4, 6。 置換的廣義概念在不同語境下有不同的形式定義:.

新!!: 组合数学和置換 · 查看更多 »

組合

在組合數學,一個集的元素的組合(Combination)是一個子集。S的一個k-組合是S的一個有k個元素的子集。若兩個子集的元素完全相同並順序相異,它仍視為同一個組合,這是組合和排列不同之處。.

新!!: 组合数学和組合 · 查看更多 »

狐狸、鹅、豆子问题

、鹅、豆子问题〔又称狼、羊、菜问题〕是一则古老的智力游戏题。.

新!!: 组合数学和狐狸、鹅、豆子问题 · 查看更多 »

階乘

一个正整数的階乘(factorial)是所有小於及等於該數的正整數的積,并且有0的阶乘为1。自然數n的階乘寫作n!。1808年,基斯頓·卡曼引進這個表示法。 亦即n!.

新!!: 组合数学和階乘 · 查看更多 »

计算机科学

计算机科学用于解决信息与计算的理论基础,以及实现和应用它们的实用技术。 计算机科学(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,这两个领域在某些学科,例如数理逻辑、范畴论、域理论和代数,也不断有有益的思想交流。.

新!!: 组合数学和计算机科学 · 查看更多 »

賽馬

賽馬(Horse racing)是一项已经存在很多世纪的马術运动,廣義而言是使用人類馬科動物比賽的賽事。罗马帝国时代的二轮战车比赛就是一个较早的例子,又或者如同挪威神话中神奧丁和巨人Hrungnir之间的战马比赛。它不可避免的常与赌博——对比赛结果的打赌活动——联系在一起。 在世界很多地区非常流行的赛马方式是纯种马比赛。賽馬車(或稱辔马赛)在美国、加拿大、澳大利亚、法国、意大利和斯堪的纳维亚半岛比较流行,在其他的地区就相对少了。夸特赛马在美国也很流行。 在很多国家,对马的饲养、训练和比赛现在已经成为一种重要的经济活动,在很大程度上,赛马投注是马业的巨大支柱。杰出非凡的马匹能赢得数百万美元,通过提供马群服务如配种可以赚取更多的钱。 在流行赛马的国家里,比赛的风格、距离和比赛的类型是各不相同的,很多国家国内的赛马类型也各不相同。拿英国来说,有一种叫國家狩獵賽馬的障碍赛马(篱笆或者栅栏),还有在特定距离内的无障碍比赛(平地赛马)。.

新!!: 组合数学和賽馬 · 查看更多 »

邮递员问题

邮递员问题(也称邮路问题,Route Inspection Problem,或中国邮路问题,China Route Inspection Problem,或中国邮递员问题Chinese Postman Problem)是一个图论问题。此問題為在一個連通的無向圖中找到一最短的封閉路徑,且此路徑需通過所有邊至少一次。 簡單來說,邮递员问题就是在一個已知的地區,郵差要設法找到一條最短路徑,可以走過此地區所有的街道,且最後要回到出發點, 此問題是圖遍歷問題的一種。无向图的中国邮路问题是容易解决的,是P问题;而有向图的中国邮路问题是NP完全问题。中国邮递员问题由管梅谷教授在1960年提出,而美國國家標準和技術研究院(NIST)的 Alan Goldman 首先將此問題命名为中国邮路问题。.

新!!: 组合数学和邮递员问题 · 查看更多 »

自然数

数学中,自然数指用于计数(如「桌子上有三个苹果」)和定序(如「国内第三大城市」)的数字。用于计数时称之为基数,用于定序时称之为序数。 自然数的定义不一,可以指正整数 (1, 2, 3, 4, \ldots),亦可以指非负整数 (0, 1, 2, 3, 4, \ldots)。前者多在数论中使用,后者多在集合论和计算机科学中使用,也是 标准中所采用的定义。 数学家一般以\mathbb代表以自然数组成的集合。自然数集是一個可數的,無上界的無窮集合。.

新!!: 组合数学和自然数 · 查看更多 »

NP完全

NP完全或NP完備(NP-Complete,縮寫為NP-C或NPC),是計算複雜度理論中,決定性問題的等級之一。NPC問題,是NP(非決定性多項式時間)中最難的決定性問題。因此NP完備問題應該是最不可能被化簡為P(多項式時間可決定)的決定性問題的集合。若任何NPC問題得到多項式時間的解法,那此解法就可應用在所有NP問題上。更詳細的定義容下敘述。 一個NPC問題的例子是子集合加總問題,題目為 這個問題的答案非常容易驗證,但目前沒有任何一個夠快的方法可以在合理的時間內(意即多項式時間)找到答案。只能一個個將它的子集取出來一一測試,它的時間複雜度是Ο(2n),n是此集合的元素數量。.

新!!: 组合数学和NP完全 · 查看更多 »

数理逻辑

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

新!!: 组合数学和数理逻辑 · 查看更多 »

整數分拆

一個正整數可以寫成一些正整數的和。在數論上,跟這些和式有關的問題稱為整數拆分、整數剖分、整數分割、分割數或切割數(Integer partition)。其中最常見的問題就是給定正整數n,求不同數組(a_1,a_2,...,a_k)的數目,符合下面的條件:.

新!!: 组合数学和整數分拆 · 查看更多 »

重定向到这里:

排列组合排列與組合組合數學组合学组合数论组合论计数论证

传出传入
嘿!我们在Facebook上吧! »