组合数学在计算机中的应用

目录

摘要.................................................................... ...................................................................... (1)

1.组合数学概述.................................................................... (1)

2.组合数学在生活中的应用.................................................................... . (1)

3.组合数学与计算机软件.................................................................... .. (1)

3.1 信息时代的组合数

学.................................................................

(2)

3.2 组合数学在计算机软件的应

用.................................................................

(2)

3.3组合数学与计算机软件的关

系.................................................................

(2)

3.4组合数学在国外软件业的发展状

况.................................................................

(2)

4 Ramsey 数在计算机科学中的应用.................................................................... . (3)

4.1Ramsey 定理和Ramsey

数.................................................................

(3)

4.2信息检

索.................................................................

(3)

参考文献.................................................................... ...................................................................... ..5

组合数学在计算机中的应用

摘要：介绍了组合数学的概念、起源与研究的主要内容,分析了组合数学的特点以及其在生活中的应用,阐述了组合数学与计算机软件的联系,并着重通过两个例子说明了Ramsey 数在计算机科学的信息检索中的重要应用。

关键词：组合数学;组合算法;Ramsey 数;信息检索;

1：组合数学概述

组合数学，又称为离散数学，但有时人们也把组合数学和图论加在一起算成是离散数学。组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。组合数学的发展改变了传统数学中分析和代数占统治地位的局面。现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好象是有思维的。

2：组合数学在生活中的应用

在日常生活中我们常常遇到组合数学的问题。如果你仔细留心一张世界地图，你会发现用一种颜色对一个国家着色，那么一共只需要四种颜色就能保证每两个相邻的国家的颜色不同。这样的着色效果能使每一个国家都能清楚地显示出来。但要证明这个结论确是一个着名的世界难题，最终借助计算机才得以解决，最近人们才发现了一个更简单的证明。

当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往往需要做些调整。从理论上讲，装箱问题是一个很难的组合数学问题，即使用计

算机也是不容易解决的。航空调度和航班的设定也是组合数学的问题。怎样确定各个航班以满足不同旅客转机的需要，同时也使得每个机场的航班起落分布合理。此外，在一些航班有延误等特殊情况下，怎样作最合理的调整，这些都是组合数学的问题。

组合数学在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软件。最近，德国一位着名组合数学家利用组合数学方法研究药物结构，为制药公司节省了大量的费用，引起了制药业的关注。

总之，组合数学无处不在，它的主要应用就是在各种复杂关系中找出最优的方案。所以组合数学完全可以看成是一门量化的关系学，一门量化了的运筹学，一门量化了的管理学。

3：组合数学与计算机软件

随着计算机网络的发展，计算机的使用已经影响到了人们的工作，生活，学习，社会活动以及商业活动，而计算机的应用根本上是通过软件来实现的。

3.1 信息时代的组合数学

现代数学可以分为两大类:一类是研究连续对象,如分析、方程等,另一类就是研究离散对象的组合数学。计算机科学就是算法的科学,而计算机所处理的对象是离散的数据,研究离散对象的科学恰恰就是组合数学。因此,在信息时代的今天,组合数学就是信息时代的数学。

3.2 组合数学在计算机软件的应用

随着计算机科学的发展,组合数学也在迅猛发展,而组合数学在理论方面的推进也促进计算机科学的发展。计算机软件空前发展的今天要求有相应的数学基础,组合数学作为大多数计算机软件设计的理论基础,它的重要性也就不言而喻。

组合数学在计算机方面的应用极其广泛。计算机软件与各种算法的研究分不开,为了衡量一个算法的效率,必须估计用此算法解答具有给定长的输入(问题) 时需要多少步(例如算术运算、二进制比较、程序调用等的次数) 。这要求对算法所需的计算量及存储单元数进行估算,这就是计数问题的内容,而组合数学分析主要研究内容就是计数和枚举的方法和理论。

3.3组合数学与计算机软件的关系

我国在软件上的落后，要说出根本的原因可能并不是很简单的事，除了技术和科学上的原因外，可能还跟我们的文化，管理水平，教育水平，思想素质等诸多因素有关。除去这些人文因素以外，一个最根本的原因就是我国的信息技术的数学基础十分薄弱，这个问题不解决，我们就难成为软件强国。然而问题决不是这么简单，信息技术的发展已经涉及到了很深的数学知识，而数学本身也已经发展到了很深、很广的程度并不是单凭几个聪明的头脑去想想就行了，而更重要的是需要集体的合作和力量，就象软件的开发需要多方面的人员的合作。美国的软件之所以能领先，其关键就在于在数学基础上他们有很强的实力，有很多杰出的人才。一般人可能会认为数学是一门纯粹的基础科学，1+1的解决可能不会有任何实际的意义。如果真是这样，一门纯粹学科的发展落后几年，甚至十年，关系也不大。然而中国的软件产业的发展已向数学基础提出了急切的需求：网络算法和分析，信息压缩，网络安全，编码技术，系统软件，并行算法，数学机械化和计算

机推理，等等。此外，与实际应用有关的还有许多许多需要数学基础的算法，如运筹规划，金融工程，计算机辅助设计等。如果我们的软件产业还是把眼光一直盯在应用软件和第二次开发，那么我们在应用软件这个领域也会让国外的企业抢去很大的市场。如果我们现在在信息技术的数学基础上，大力支持和投入，那将是亡羊补牢，犹未为晚；只要我们能抢回信息技术的数学基地，那么我们还有可能在软件产业的竞争中，扭转局面，甚至反败为胜。吴文俊院士开创和领导的数学机械化研究，为中国在信息技术领域占领了一个重要的阵地，有了雄厚的数学基础，自然就有了软件开发的竞争力。这样的阵地多几个，我们的软件产业就会产生新的局面。值得注意的是，印度有很好的统计和组合数学基础，这可能也是印度的软件产业近几年有很大发展的原因。

3.4 组合数学在国外软件业的发展状况

纵观全世界软件产业的情况，易见一个奇特的现象：美国处于绝对的垄断地位。造成这种现象的一个根本的原因就是计算机科学在美国的飞速发展。当今计算机科学界的最权威人士很多都是研究组合数学出身的。美国最重要的计算机科学系（MIT，Princeton，Stanford，Harvard，Yale，….）都有第一流的组合数学家。计算机科学通过对软件产业的促进，带来了巨大的效益，这已是不争之事实。组合数学在国外早已成为十分重要的学科，甚至可以说是计算机科学的基础。一些大公司，如IBM，AT&T都有全世界最强的组合研究中心。Microsoft 的Bill Gates 近来也在提倡和支持计算机科学的基础研究。例如，Bell实验室的有关线性规划算法的实现，以及有关计算机网络的算法，由于有明显的商业价值，显然是没有对外公开的。美国已经有一种趋势，就是与新的算法有关的软件是可以申请专利的。如果照这种趋势发展，世界各国对组合数学和计算机算法的投入和竞争必然

日趋激烈。美国政府也成立了离散数学及理论计算机科学中心DIMACS（与Princeton大学，Rutgers大学，AT&T 联合创办的，设在Rutgers大学），该中心已是组合数学理论计算机科学的重要研究阵地。美国国家数学科学研究所（Mathematical Sciences Research Institute，由陈省身先生创立）在1997年选择了组合数学作为研究专题，组织了为期一年的研究活动。日本的NEC公司还在美国的设立了研究中心，理论计算机科学和组合数学已是他们重要的研究课题，该中心主任R. Tarjan即是组合数学的权威。

除上述以外，欧洲也在积极发展组合数学，英国、法国、德国、荷兰、丹麦、奥地利、瑞典、意大利、西班牙等国家都建立了各种形式的组合数学研究中心。近几年，南美国家也在积极推动组合数学的研究。澳大利亚，新西兰也组建了很强的组合数学研究机构。值得一提的是亚洲的发达国家也十分重视组合数学的研究。日本有组合数学研究中心，并且从美国引进人才，不仅支持日本国内的研究，还出资支持美国的有关课题的研究，这样使日本的组合数学这几年的发展极为迅速。台湾、香港两地也从美国引进人才，大力发展组合数学。新加坡，韩国，马来西亚也在积极推动组合数学的研究和人才培养。台湾的数学研究中心也正在考虑把组合数学作为重点方向来发展。世界各地对组合数学的如此钟爱显然是有原因的，那就是没有组合数学就没有计算机科学，没有计算机软件。

4 Ramsey 数在计算机科学中的应用

4.1 Ramsey 定理和Ramsey 数

众所周知,若有n +1 只鸽子同时飞进n 个鸽巢中,则一定有某个鸽巢中至少飞进两只鸽,这就是有名的鸽巢原理(也叫抽屉原理) 。它非常简单,其正确性也显而易见,但却有很广泛的应用。鸽巢原理有如下重要的推广:

Ramsey 定理设q1 , q2 , ?, qn ; t 是正整数,且qi>=t ( i =1 , 2 , ?, n) ,则存在最小的正整数r (记作r ( q1 ,q2 , ?qn ; t) 使得:对任意m 元集合s ,若m E r ,当把S 的所有t 元子集放到n 个盒子里时,那么存在某个i (1 <=n) 和某qi 个元素,它的所有t 元子集都在第i 个盒子里。这是称r ( q1 , q2 , ?qn ; t) 为Ramsey 数。

上述定理是Ramsey1930 年提出并给出证明。

当t =1 时,Ramsey 定理就是加强形式的鸽巢原理,且容易求出

r ( q1 , q2 , ?qn ;1) = Σqi - n +1(i=1~n)

Ramsey 定理是组合论中一个重要的存在性定理,它的发表推动了组合论等数理科学的发展,而且关于Ram2sey 定理和Ramsey 数自身的研究目前已成为组合学中一个重要的分支———n +1 ———Ramsey 理论。但是,Ram2sey 定理只保证了Ramsey 数的存在性,并没有给出计算Ramsey 数的有效方法。目前,确定Ramsey 数的问题仍是一个尚未解决的大难题,要找到一个很小的Ramsey 数是很困难的。虽然如此,由于其重要的理论价值和广泛的应用价值,确定Ramsey 数是很有意义的。下面用两个例子说明Ramsey 数在信息检索、分组交换网设计等计算机科学领域中的重要应用。

4.2 信息检索

信息检索是计算机科学中一个基本而又重要的问题。如何组织数据,使用什么样的查找方法,对检索的效率有很大的影响。所熟知的在有序表结构上的二分搜索算法是一种很有效的方法,那么二分搜索是最好的算法吗?Yao利用Ramsey 数对这一问题作了肯定的回答。

具体地讲,假设一个表有n 个不同的项,其元素取自键空间M = { 1 ,2 , ?, m},

希望找到在表中存储M 的任意n 元子集S 的方法,使得容易回答下述询问: X 在S 中吗? 如何存储M 的n 元子集的规则称为一个表结构或( m , n) 2表结构。最简单的表结构是有序表结构,它是按上升序列出S 中的元素。更一般的是按置换排序的表结构,其方法是固定{ 1 ,2 , ?, n} 的一个置换,根据比置换的次序列出S 中的元素。

信息检索的计算复杂性依赖于表结构和搜索策略。复杂性的度量是最坏情形下确定x 是否在S 中所需要的询问次数。例如,对有序表结构,如果用二分搜索,所需要的询问次数是[log2 ( n +1 ) ] 。复杂性f ( m , n) 定义为所有的( m , n) 2表结构和搜索策略下的复杂性的最小值。关于f ( m , n) ,Yao证明了: 定理1 对每个n ,存在数N ( n) 使得f ( m , n) = [log2 ( n +1 ) ]对所有m>=N ( n) 成立。

据此定理,对充分大的m ,就信息检索来说,用有序表结构是最有效的方法。

利用下述两个引理,立即可得此定理的证明。

引理1 若m >=2 n -1 , n >=2 ,对于按置换排序的表结构。无论采用何种策略,在最坏情形下要确定x 是否在S 中至少需要[log2 ( n +1 ) ]次检查。

引理2 给定n ,存在数N ( n) 具有下述性质:若m >=N ( n) ,且给定一个( m , n) 2表结构,则存在有2 n -1个键的集合K ,使得对应于K 的n 元子集的表形成按置换排序的表结构。

参考文献

【1】杨骅飞. 组合数学及其应用[M]. 北京:北京理工大学出版社,1992.

【2】杨振生. 组合数学及其算法[M]. 合肥:中国科学技术大学出版社,1997. 【3】卢开澄,卢华明. 组合数学(第3 版) [M]. 北京:清华大学出版社,2002.

【4】

【5】陈树柏. 网络图论及其应用[M]. 北京:科学出版社,1982.

【6】hschild,J.H.s pencer.Ramse yTheor y ( secondedition ) [M].JohnWile y8.Sons,New.York,1990.

离散数学在计算机科学中的应用

离散数学在计算机科学中的应用 本学期我们开了一门新的课程——离散数学，这是一门艰深又充满挑战的课程，随着学习的深入，我逐步加深了对它的了解。 首先简单介绍一下离散数学的定义及其在各学科领域的重要作用。离散数学(Discrete mathe matics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。 随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。 由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。 由此可见，离散数学在计算机科学中具有广泛的应用，下面我将一一陈述。 1 离散数学在关系数据库中的应用 关系数据库中的数据管理系统向用户提供使用的数据库语言称为数据子语言，它是以关系代数或谓词逻辑中的方法表示。由于用这种数学的方法去表示，使得对这些语言的研究成为对关系代数或逻辑谓词的研究，优化语言的表示变成为对关系代数与谓词逻辑的化简问题。由于引入了数学表示方法，使得关系数据库具有比其它几种数据库较为优越的条件。正因为如此关系数据库迅速发展成为一种很有前途、很有希望的数据库。另外，离散数学中的笛卡儿积是一个纯数学理论，是研究关系数据库的一种重要方法，显示出不可替代的作用。不仅为其提供理论和方法上的支持，更重要的是推动了数据库技术的研究和发展。关系数据模型建立在严格的集合代数的基础上，其数据的逻辑结构是一个由行和列组成的二维表来描述关系数据模型。在研究实体集中的域和域之间的可能关系、表结构的确定与设计、关系操作的数据查询和维护功能的实现、关系分解的无损连接性分析、连接依赖等问题都用到二元关系理论。 2 离散数学在数据结构中的应用 计算机要解决一个具体问题，必须运用数据结构知识。对于问题中所处理的数据，必须首先从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序，进行测试、调整直至得到问题的最终解答。而寻求数学模型就是数据结构研究的内容。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描 述。数据结构中将操作对象间的关系分为四类：集合、线性结构、树形结构、图状结构或网状结构。

计算机科学中的数学理论

致力于打造高品质文档计算机科学中的数学理论 计算机科学中的数学理论 计算机科学中的数学理论 计算机科学中的数学理论 精品源自化学科 引言 随着计算机现代智能的高速发展,计算机已经完全融入我们的生活,甚至占据了重要领域,从国家核心科技到每个人生活的小细节,都离不开计算机的覆盖和使用。我们简单的在键盘上操作几个键,打出一系列符号命令,就能使计算机按照人类的要求,高速运行和进展,从而达到人力所不能达到的速度和正确率。 1 计算机中所需要的数学理论 计算机学科最初是来源于数学学科和电子学学科,计算机硬件制造的基础是电子科学和技术,计算机系统设计、算法设计的基础是数学,所以数学和电子学知识是计算机学科重要的基础知识。计算机学科在基本的定义、公理、定理和证明技巧等很多方面都要依赖数学知识和数学方法。计算机数学基础是计算机应用技术专业必修并且首先要学习的一门课程。它大概可分类为: 1.1 高等数学高等数学主要包含函数与极限、导数与微分、微分中值定理与导数的应用、不定积分、定积分及应用、空间解析几何与向量代数、多元函数微分法及其应用、重积分、曲线积分与曲面积分、无穷级数、微分方程等。各种微积分的运算正是计算机运算的基础。 1.3 概率论与数理统计概率统计与数理统计包含随机事件与概率、随机变量的分布和数学特征、随机向量、抽样分布、统计估计、假设检验、回归分析等。概率论与数理统计是研究随机现象客观规律并付诸应用的数学学科,通过学习概率论与数理统计,使我们掌握概率论与数理统计的基本概念和基本理论,初步学会处理随机现象的基本思想和方法,培养解决实际问题的能力。这些都是计算机编程过程中不可或缺的基础理论知识和技能。 2 计算机编程中数学理论的应用 计算机的主要专业知识包括计算机组成原理、操作系统、计算机网络、高级语言程序设计、数据结构、编译原理、数据库原理、软件工程等。计算机程序设计主要包括如:C语言、C++、JA V A、编译语言、汇编语言等编程语言的基本概念、顺序结构程序设计、分支结构程序设计、循环结构设计、函数、指针、数组、结构、联合以及枚举类型、编译预处理、位运算、文件等内容,掌握利用各种编程语言进行程序设计的基本方法,以及编程技巧。算法是编程的核心,算法的运用离不开数学,数学运算正是编程的基础。 计算机科学是对计算机体系,软件和应用进行探索性、理论性研究的技术科学。由于计算机与数学有其特殊的关系,故计算机科学一直在不断地从数学的概念、方法和理论中吸取营养;反过来,计算机科学的发展也为数学研究提供新的问题、领域、方法和工具。近年来不少人讨论过数学与计算机科学的关系问题,都强调其间的密切联系。同时,人们也都承认,计算机科学仍有其自己的特性,它并非数学的一个分支,而有自身的独立性。正确说法应该是:由于计算机及程序的特殊性,

数学在计算机里的应用

数学在计算机中的应用 摘要：结合自身的学习经历和所接触的数学与计算机知识，来谈一下自己对计算机应用的理解和认识，在文章中针对不同的课程可能会谈到一些具体的应用，但重点想突出数学方法与思维对计算机应用的影响。 关键字：离散数学C语言数字逻辑算法设计与分析 上了是十几年学，数学可以说是我的老朋友了。从幼儿园的识数开始，到如今的高等数学，数学学习始终贯穿这我的学习历程，中我们也不难发现数学在教育中的地位。数学作为一门基础课程，它的身影可以说是无处不在的。作为一名计算机系的学生，本来以为可以摆脱数学的”噩梦”的，但是接下来的学习让我再一次失望了。原来学计算机，除了学习高数，线性代数，数理统计外，还要学习一科专门为计算机开设的《离散数学》。 记得在一节课上，一位老师说过：“一位从本科就是计算机专业的博士说：‘研究计算机就是研究数学’。”虽然我现在无法体会到这句话，也不论这就话是否完全正确，但它总能说明了一点：数学在计算机中必然会发挥巨大的作用。 作为一个大三的本科生也许我的知识不够全面，理解也不是那么透彻，我在此只想根据自己的学习经历来谈一下个人的见解—数学在计算机中的应用。 也许我们小的时候，只知道学习数学有趣。等我们慢慢长大，随着学习的深入，我们总是喜欢问这样一个问题：学数学有什么用呢？我们总是告诉自己，学会加减乘除就足以应付生活了，再学深入那些抽象的知识一点用处也没了。其实数学作为一门基础课程也许在现实中确实没有什么用处，但数学作为一种工具，它很好地锻炼了我们的思维，让我们的思维变得活起来。而在计算机中，大家也都有一个共识：学不好数学的人也很难学好计算机。虽然这个也有点片面，但我们不否认这其中总有一定道理的。计算机的知识也是相当抽象化的模型，需要我们具有良好的逻辑思维户外清晰地脉络，而数学好的人这种思维往往是比较突出的。因此，我们经常发现，现实中有非常多的搞计算机搞得比较好的，他们的前身是学数学专业的。从基础方面，数学思维为计算机的学习打下一个良好的基础，站在今天，我不再去抱怨以前的数学学习是多么的艰难，而是有一种风雨之后见彩虹的喜悦，我不能否认，数学确实对我在计算机中的学习产生了潜移默化的影响，而这种影响确实是那么的有益。 记得刚开始学习编程的时候，接触的《C语言程序设计》，程序里的许多样题都是一些小的数学案例。用计算机程序计算和1+2+…+100=，求1！+2！+…+10!=….等，我想大家都不会陌生。是的正是这些小的数学例题，把我们的计算机学习一步步的引向远方。这些样题虽然不难，但它却包含了许多的思想。编程确实是用一种计算机的语言来表达数学的思想。我们必须像往常一样有一个明确的条理性，找出其中的规律，然后一步步求解。不过不同的是，现在不再需要我们在纸上用笔一步步的演算，而是把我们的思维赋予计算机来演算。 接下来的学习，作为一名计算机的学生，总要接触一门《离散数学基础》。刚开始我们会产生一个疑问，我们学计算机的干嘛要学习那么多数学。但随着老师的介绍，我们只能默默接受计算机学子的命运，别抱怨了，埋头学吧！介绍说：离散数学是研究离散量的结构和相互关系的学科，它在计算复杂性理论，软件工程，算法和数据结构，数字逻辑电路等各领域都有广泛应用，同时也能适当培养学生的抽象思维和慎密逻辑推理能力。也许那时候还感觉软件工程，数据结构还很陌生，感觉到学习数学依旧痛苦，没有感到那些抽象的理论到底有什么用啊，不会是在吓唬我们吧？但接下来在以后的学习中，它的确得到了广泛应用。

用计算机编制数学游戏

用计算机编制数学游戏 作者：范新雨许家豪鲁贤欢李寒松指导老师：徐李林 摘要：“数和形的概念不是从其他任何地方，而是从现实世界上得来的。”数学来源于实践又反过来为实践服务。在科技日新月异的今天，数学广泛的应用性日愈显示出其特有的魅力。下面就让我们来用计算机探索编制数学游戏的奥秘。关键词：计算机编制数学游戏 计算机与数学 计算机科学和数学的关系有点奇怪。二三十年以前，计算机科学基本上还是数学的一个分支。而现在，计算机科学拥有广泛的研究领域和众多的研究人员，在很多方面反过来推动数学发展，从某种意义上可以说是孩子长得比妈妈还高了。 但不管怎么样，这个孩子身上始终流着母亲的血液。这血液是the mathematical underpinning of computer science(计算机科学的数学基础)，-- 也就是理论计算机科学。 现代计算机科学和数学的另一个交叉是计算数学/数值分析/科学计算，传统上不包含在理论计算机科学以内。所以本文对计算数学全部予以忽略。最常和理论计算机科学放在一起的一个词是什么?答：离散数学。这两者的关系是如此密切，以至于它们在不少场合下成为同义词。 传统上，数学是以分析为中心的。数学系的同学要学习三四个学期的数学分析，然后是复变，实变，泛函等等。实变和泛函被很多人认为是现代数学的入门。在物理，化学，工程上应用的，也以分析为主。 随着计算机科学的出现，一些以前不太受到重视的数学分支突然重要起来。人们发现，这些分支处理的数学对象与传统的分析有明显的区别：分析研究的对象是连续的，因而微分，积分成为基本的运算;而这些分支研究的对象是离散的，因而很少有机会进行此类的计算。人们从而称这些分支为“离散数学”。“离散数学”的名字越来越响亮，最后导致以分析为中心的传统数学分支被相对称为“连续数学”。 离散数学经过几十年发展，基本上稳定下来。一般认为，离散数学包含以下学科： 1) 集合论，数理逻辑与元数学。这是整个数学的基础，也是计算机科学的基础。 2) 图论，算法图论;组合数学，组合算法。计算机科学，尤其是理论计算机科学的核心是算法，而大量的算法建立在图和组合的基础上。 3) 抽象代数。代数是无所不在的，本来在数学中就非常重要。在计算机科学中，人们惊讶地发现代数学竟然有如此之多的应用。 当然，还远远不止是这些。 现代社会科学技术高速发展，数学学科的发展也已经到了非常抽象的地步，

论数学与计算机科学的关系

数学与计算机科学 计算机科学与数学之间有密切的联系，计算机内部的计算式是以二进制的方式进行的，各种程序也在应用数学的思想和算法，所以说这两者是密不可分的。事实上，计算机科学的一些奠基者，即如冯?诺依曼和图灵等，曾经都直接从事数学哲学（基础）的研究，而且，在二次世界大战后的一些年中，计算机科学家们更不断由数学哲学中吸取了一些十分重要的思想，后者并在以后的人工智能研究中得到了进一步的应用。数学哲学（数学基础研究）的概念和理论在计算机科学的历史发展中发挥了十分重要的作用，其中模糊数学从数学手段上武装了电子计算机, 使电子计算机能够在相当程度上模拟人脑的模糊思维。在以精确数学和二值逻辑为基础上建立起来的一般电子计算机, 尽管在运算速度、记忆能力等方面超过人脑, 在确定性环境中能做出人脑难以快速做出的判断。 虽然我们目前还没有开离散数学这门课，但是通过网络，我去了解了离散数学在计算机中的应用。离散数学在关系数据库、数据结构、编译原理、人工智能、计算机硬件设计、计算机纠错码中都有广泛的应用。以下是应用方面的概述。 离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。 由此可见，数学对于计算机的发展以及应用有不小的作用，虽然现在我们学的仅仅是数学本身，但是需要我们在实践中去将这两门学科结合在一起，在学习数学的过程中，多思考，建立起数学的思维模式。在计算机的应用中，使用这种思维模式，这两者就都能游刃有余的应用起来。 2012/4/6

数学、逻辑与计算机科学的关系

数学、逻辑与计算机科学的关系数学、逻辑是与计算机科学密不可分的。数学是基础材料，逻辑是支柱，计算机科学是大厦。 首先，是数学与逻辑的关系。 数学基础的讨论主要在19世纪末20世纪初，当时对数学的看法有许多流派，其中一派是逻辑主义学派，认为数学可以完全由逻辑得到。但后来数理逻辑中的一些深刻结果则否定了这种观点。事实上，数学不能完全由逻辑得到，即，如果要求数学是无矛盾的，那么，它就不可能是完备的。 现在对数学看法的主流是源于Hilbert的形式主义数学的观点。粗略地说，就是公理化的观点。也就是说，人们可以从实际出发（也可以从空想出发），给出一组无矛盾、不多余的公理，这种公理系统下就形成一种数学。在建立公理以后的事情则属于逻辑。 所以，逻辑是数学的重要方法和基础，但不是数学的全部。反过来，数学也不包括逻辑的全部。逻辑学主要是（至少曾经是）哲学的一支，它不仅研究逻辑命题的推演关系，也研究这种关系为什么是对的，等等。逻辑学中影响数学的主要是形式逻辑和数理逻辑，但涉及哲学思辨的部分就不在数学的范畴之中了。 其次，是数学与计算机的关系。 因为计算机是一种进行数值计算、逻辑推理、符号处理等方面信息加工的机器，有人就称它为数学的机器;近年由于计算机应用的拓广，其系统软件与应用软件发展很大，吸引了甚为巨大的社会人力与财力，形成了一种新兴的工业，人们认为这是继土木工程，机械工程、电子工程之后的一种新的工程—软件工程。由于它具有数学的特征，即高度的精确性，广泛的应用性，与推理的严谨可靠性。因此，计算机科学被称程序为具有数学性质的学科。 计算机科学是对计算机体系，软件和应用进行探索性、理论性研究的技术科学。由于计算机与数学有其特殊的关系，故计算机科学一直在不断地从数学的概念、方法和理论中吸取营养;反过来，计算机科学的发展也为数学研究提供新的问题、领域、方法和工具。近年来不少人讨论过数学与计算机科学的关系问题，都强调其间的密切联系。同时，人们也都承认，计算机科学仍有其自己的特性，它并非数学的一个分支，而有自身的独立性。正确说法应该是:由于计算机及程

数学在计算机中的应用

离散数学在计算机方面的应用 计算机学科主要脱胎发源于数学学科，离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。计算机学科中普遍采用了离散数学的基本概念、基本思想和基本方法，并把离散数学作为自己的理论基础和重要的数学工具。 离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。它是以研究离散性的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数个元素。由于计算机科学的迅速发展，与其有关的领域中，提出了许多有关离散量的理论问题，需要用某些数学的工具做出描述和深化。离散数学把计算机科学中所涉及到的研究离散量的数学综合在一起，进行较系统的、全面的论述，为研究计算机科学的相关问题提供了有力的工具。 数学课程所涉及的概念、方法和理论，大量地应用在数据结构、数据库系统、编译原理、人工智能、计算机体系结构、算法分析与设计、软件工程、多媒体技术、数字电路、计算机网络等专业课程以及信息管理、信号处理、模式识别、数据加密等相关课程中。它所提供的训练十分有益于学生概括抽象能力、逻辑思维能力、归纳构造能力的提高，十分有益于学生严谨、完整、规范的科学态度的培养。这些能力与态度是一切软、硬件计算机科学工作者所不可缺少的，为学习计算机科学的后续课程、从事科研或工程技术工作以及进一步提高科学技术水平奠定理论基础。离散数学提供的营养滋补了计算机科学的众多领域，学好了离散数学就等于掌握了一把开启计算机科学之门不可缺少的钥匙。从学科比较和联系的视角，对离散数学在计算机学科中的应用进行客观理智的分析，可以给予我们诸多启示，进而指导计算机专业学科教育教学的改革和发展。 一、离散数学在数据结构中的应用 计算机要解决一个具体问题，必须运用数据结构知识。对于问题中所处理的数据，必须首先从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序，进行测试、调整直至得到问题的最终解答。而寻求数学模型就是数据结构研究的内容。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。数据结构中将操作对象间的关系分为四类：集合、线性结构、树形结构、图状结构或网状结构。数据结构研究的主要内容是数据的逻辑结构，物理存储结构以及基本运算操作。其中逻辑结构和基本运算操作来源于离散数学中的离散结构和算法思考。离散数学中的集合论、关系、图论、树四个章节就反映了数据结构中四大结构的知识。如集合由元素组成，元素可理解为世上的客观事物。关系是集合的元素之间都存在某种关系。例如雇员与其工资之间的关系。图论是有许多现代应用的古老题目。伟大的瑞士数学家列昂哈德·欧拉在18世纪引进了图论的基本思想，他利用图解决了有名的哥尼斯堡七桥问题。还可以用边上带权值的图来解决诸如寻找交通网络里两城市之间最短通路的问题。而树反映对象之间的关系，如组织机构图、家族图、二进制编码都是以树作为模型来讨论 二、离散数学在数据库中的应用 数据库技术被广泛应用于社会各个领域，关系数据库已经成为数据库的主流，离散数学中的笛卡儿积是一个纯数学理论，是研究关系数据库的一种重要方法，显示出不可替代的作用。不仅为其提供理论和方法上的支持，更重要的是推动了数据库技术的研究和发展。关系数据模型建立在严格的集合代数的基础上，其数据的逻辑结构是一个由行和列组成的二维表来描述关系数据模型。在研究实体集中的域和域之间的可能关系、表结构的确定与设计、关系操作的数据查询和维护功能的实现、关系分解的无损连接性分析、连接依赖等问题都用到二元关系理论。 三、离散数学在编译原理中的应用

数学与计算机科学系

数学与计算机科学系 2009年工作总结及2010年 工作意见 二OO九年十二月二十四日

数学与计算机科学系2009年工作总结 2009年，在学院党委和行政的正确领导下，我系以《铜陵学院2009年工作要点》和《数学与计算机科学系2009年工作计划》为指导，紧紧围绕学院的中心工作，坚持以发展为主题，以“建设应用型本科高校”为主线，认真开展学习实践科学发展观活动；突出应用型学科专业和师资队伍建设两个重点；强化教学管理和学生管理；加强党的建设、思想政治教育、精神文明建设、就业指导以及综合治理、防控甲流感等工作；积极推进各项改革，保持和维护学院稳定，各项工作都取得了显著成果，圆满完成了年初提出的工作目标和任务。 一年来，我们主要做了以下几方面的工作： 一、认真开展学习实践科学发展观活动 根据学院党委的部署和学院学习实践活动办公室的具体安排，在党委督导组的指导和全系共产党员、全体师生共同努力下，从今年3月到8月，我系147名师生党员全部参加了学习实践活动。 这次教育活动，坚持从我院和我系的实际出发，认真组织，精心谋划。对每个阶段都做出了具体的安排，三个阶段环环相扣，整个活动有计划、有安排、有措施、有总结，各项活动开展得扎扎实实，井然有序。着重抓解放思想大讨论、领导班子专题民主生活会、分析检查报告、制定整改落实方案等关键环节。 在整个学习实践活动中，我系的党员干部做到了带头参加学习，带头作辅导报告，带头制定并落实主题实践活动方案，在学习讨论和专题民主生活会和组织生活会上带头发言，诚心诚意地开展谈心活动，联系个人实际查找问题和不足；积极开展批评和自我批评；真心实意剖析原因，提出

数学在各方面的的应用

附录三关于数学在理科中应用的调查报告 我们对理科中物理、化学、计算机基础中数学知识的应用进行了相关的调查。调查过程中翻阅了大量的相关资料，并询问了不少相关的专家，现将结果公布如下： 一、物理学中的数学知识 数学是物理学的基础和工具。离开了数学，物理学几乎寸步难行。现行大学物理系的数学教材几乎囊括了所有高等数学的基础知识。理论物理和实验物理都必需具备相当高深的数学知识。 理论物理中所应用的数学知识有：空间及其拓朴、映射、实分析、群论、线性代数、方阵代数、微分流形和张量、黎曼流行、李导数、李群、矢量分析、积分变换（包括傅里叶变换和拉普拉斯变换）、偏微分方程、复变函数、球函数、柱函数、函数、格林函数、贝塞尔函数、勒让德多项式等。 实验物理中所应用的数学知识呈主要集中在概率统计学中。包括一维、多维随机变量及其分布、概率分布、大数定律、中心极限定理、参数估计、极大似然法等。其中概率分布包括伯努力分布、泊松分布、伽马分布、分布、t分布、F分布等。 从上可以看出，上述数学知识对物理专业来讲，必需了解，且有的需要深入了解。比如群论、空间及拓朴、积分变换、偏微分方程、概率分布、参数估计等。工科和理科、师范类和非师范类、物理专业和非物理专业、其物理学习中所应用的数学知识也有范围和程度上的变化。工科就没有理科要求高，物理专业中所涉及的数学知识也比非物理专业所学物理课本上的数学知识丰富的多。 二、化学中的数学知识 初等化学只是简单介绍物质的组成、结构、性质、变化及合成。除了相应的计算外，与数学的联系没有物理学那么紧密。高等化学需要更深入的研究物质，因此需要相应的高等数学知识为基础。下面我们就化学理论和化学实验两种课程来讨论。 化学理论中所应用的数学知识有：级数及其应用、幂级数与Taylor展开式、Fourier级数、Forbemus方法、Bessel方程、Euler-Maclaurh加法公式、String公式、有限差分、矩阵、一阶偏微分方程、二阶偏微分方程、常微分方程（包括一阶、二阶、线性、联立）、特殊函数（包括贝尔函数和勒让德多项式）积分变换、初步群论等。 化学实验中所应用的数学知识有：随机事件及其概率、随机变量的数字特征、随机分量及其分布、大数定理、中心极限定理、参数估计等。 从上面可以看出，化学中的数学知识主要应用于计算，因此大部分是一些数学公式和方程，并没有更深一步理论推导及逻辑思维、形象思维的要求。所以，化学专业中数学知识的要求不高，只限于了解并会套公式而已。

数学在计算机编程中的应用

题目：数学在计算机编程中的应用学院：计算机与信息科学学院 专业年级：2009级计算机科学与技术（师范）

学生姓名：祝柱杰 学号：20090512160 指导教师：沈林 职称：讲师 2011年11 月30 日 数学在计算机编程中的应用 采用递归算法来解决该问题，因为递归算法有这样特征描述：为了求解出规模为n的问题的解，我们先设法将它分解成一些规模较小的问题，然后从这些较小问题的解能方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的方法分解，分解成规模更小的问题。并能从这些更小的问题的结构造出规模稍大问题的解。现在，严格按照递归算法来解决问题。先定义递归方法hanio(int n,char A,char B,char C)，按如下步骤进行解题（设初始盘子个数为n）：若A塔上仅仅只有一个盘子（n=1），则直接从A移动到C，问题完全解决。若A塔上有一个以上的盘子（n>1），则需要考虑以下三个步骤。第一步：把（n-l价盘子从Ａ塔经过移动，叠放到B塔上。在不违反规则情况下，所有（n-l）个盘子不能作为一个整体一起移动，而是要符合要求地从一个塔移到另一个塔上。用

hanio(n-l,B,A,C)调用递归方法，注意：这里是借助于C塔，将（n-l价盘子从A 塔移动到B塔，A是源塔，B是目标塔。第二步：将剩下的第l个盘子（也就是最底下的一个）直接从A塔叠放到空着的c塔上。第二三步：用第一步的方法，再次将B塔七的所有盘子叠放到c塔上。同样，这一步实际上也是由一系列更小的符合规则的移动盘子的操作组成的。用hanio(n-l,B,A,C)调用递归方法。 数学是计算机的鼻祖, 计算机学科就是一门脱胎于数学学科的学科，在计算机专业中也普遍采用了数学的基本概念、基本思想以及相应的数学基本方法。数学理论是计算机的基础，而学习学计算机专业，编程又是必须学习的，而编程思想却又是数学思想在计算机应用中的最直接的体现。 在商业的开发环境,比如做游戏开发,就需要数学基础很深的人工智能了。很多公司也会找那些数学系的来做开发,对他们来说,由于他们的数学概念模型已经建立了起来了所以他们在计算机方面也会很快就上手,并且很不会比计算机专业的学生差。 随着计算机技术的快速发展，数学知识在计算机技术发展中，尤其是在计算机应用程序设计中处于极其重要的地位。同时，用数学思维解决各种程序设计方面的难题也是一个十分重要的步骤。在程序设计当中所解决的相当一部分问题都会涉及到各种各样的科学计算，这需要程序员将实际问题转换为程序，要经过对问题抽象的过程，建立起完善的数学模型，才能设计出好的软件。 数学在编程中的体验不光是算法过程的书写，还有逻辑思维方面的能力。而软件编程的思维定式决定了一个人编程的水平，在编程过程中，数学思维清晰，编写出来的程序让人耳目一新。结合教学，通过调查分析，了解到超过85%的学生，他们在编程时是根据语法而编写程序，完全脱离了软件编程的思维，这种思维定式使得他们编写的程序相当糟糕，没有一点逻辑。所以数学思维不够，在软件编程会有很多的疑虑，显的有点缩手缩尾，而且写的程序也不够健全，缺乏逻辑。

《易学与数学和计算机科学》-图解乾坤生六子

图解乾坤生六子 （含：计算机验证程序） 中国古文明是一个早产的文明，在纸张还没有发明的年代，就创造出了完整的文字、历法、数学等等。在秦汉以前，记载主要以竹简、木牍为主，虽然有少量的锦帛、兽皮等，但是存世的及其稀少。以考古发掘出的竹简和木牍来看，这种载体根本不适合记录图形、公式等！以至于很多与图形、数学公式等相关的知识，只能以描述性文字记载下来。这样就造成了很多具有争议的问题，并且其精确性令人颇为担心。以易经来讲，其中描述乾坤变化的仅仅八个字“乾道成男，坤道成女”，一般人很难理解这究竟是怎么个“成”法。所幸的是在清代医学家郑寿全所著的《医理真传》中，讲解了其对“乾道成男，坤道成女”-乾坤生六子的理解，使得我们可以更准确的理解这个变化道理。但这仍然是描述性的，没有图形给出，今笔者就此将其中的变化规律以图形的形式给出，并且分析出其数学规律。 如上图，将其中的阴阳爻以0和1代替，就可以发现，其描述的规律实际上就是一种数学运算法则：逻辑与运算以及逻辑或运算。 逻辑与运算的运算法则是：0&1=0，0&0=0，1&0=0，1&1=1；（& 与运算符） 逻辑或运算的运算法则是：0|1=1，0|0=0，1|0=1，1|1=1；（| 与运算符） 解：设阳爻为0，阴爻为1，初爻为数据的第一位，二爻为第二位，三爻为第三位，转换成二进制数据（如震：110，艮011）。再设乾为Q,坤为K,运算结果为R.则： 乾道运算为， Q|001=R1 R1<

浅析数学在计算机科学及应用中的应用

图1 为两相开关建立模型的有穷自动机 3.4 离散数学与编译原理 编译程序是计算机学科中比较高深的专业课，是计算机的一个十分复杂的系统程序。一个典型的编译程序而论，一般都含有八个部分：词法分析程序，语法分析程序，语义分析程序，中间代码生成程序，代码优化程序，目标代码生成程序，错误检查和处理程序，各种信息表格的管理程序。 离散数学里的计算模型章节里就讲了三种类型的计算模型：文法、有限状态机和图灵机。具知识有语言和文法，带输出的有限状态机，不带输出的有限状态机，语言的识别，图灵机等。短语结构文法根据产生式类型来分类：0型文法，1 型文法，2型文法，3 型文法。以上这些在离散数学里讲述到的知识点在编译原理的词法分析及语法分析中都会用到。 由于自然语言都极为复杂，对一个自然语言，看起来不大可能说出它的所有语法规则，因此，将一个语言自动翻译成另一个语言的研究，引出形式语言的概念。与自然语言不同，形式语言是由一组意义明确的语法规则定义的，语法规则不仅对于语言学和自然语言的研究十分重要，而且对于程序设计语言的研究也很重要。 形式语言的句子是用语法来描述的。在程序设计语言的应用中，经常出现两类问题：（1）怎么能够确定一组单词是否组合成了形式语言的一个有效句子？（2）怎么才能产生形式语言的一个有效句子。在考虑这两类问题时，文法的使用十分有益。 离散数学里定义了短语结构文法。G=（V,T,S,P）由下列四部分组成：词汇表V，由V 的所有终结符组成的V的子集合T,V的初始符S，和产生式集合P。集合V-T , 记为N，N中的元素称为非终结符。P中的每个产生式的左边必须至少包含一个非终结符。 编译原理中的词法分析运用了不确定的有穷自动机，确定的有穷自动机，从正规表达式到NFA。在语法分析中运用了上下文无关文法，非上下文无关文法，LL(1)文法，LR 文法。这些表达式与文法都在离散数学中有相关的描述。因此，离散数学也是编译原理的前期基础课程。 3.5 离散数学与人工智能 人工智能是以让机器完成那些如果由人来做则需要智能的事情的科学。虽然人工智

计算机应用数学

计算机应用数学01332 （考试时间2011-4-17下午） 1．关于函数|sin | ()cos x f x x xe -=()x -∞<<+∞的说法中，正确的是奇函数 3．当0x →时，与2 ()(1cos )ln(12)f x x x =-+为同阶无穷小的是 4x 。 4．曲线ln y x =上一点P 的切线经过原点(0,0)，则点P 的坐标为（( e ,1 ) ）。 5．下列关于函数f(x)=2x+1(x>0)的奇偶性的说法正确的是（ 非奇非偶函 ）。 6．极限 x x x 2sin lim ∞ → 的值为（ 0 ）。 7．函数f(x)= |x| 在 （0，0 ）点处 连续 。 8．方程3310x x -+=在区间(0,1)内（ 有唯一实根）。 9．求导正确的函数是 (e -x )/=-e -x 10．对于函数 ()3 32x x f -= ，在区间 []1,0上满足拉格朗日中值定理的点ξ是( 2 1 ) 。 11．直线L1: 1 1+x = y =21-z 和 直线L2: x= 31+y = 4 2-z 之间的最短距离为（ 3 3 ）。 12．定积分 ? 3 1 3d x x 的值为（ 20 ） 。 13．设 A,B,C 均为n 阶方阵，且 ABC=E ,其中E 为 n 阶单位阵。则必有（CBA=E ）。 14．设 A 为n 阶方阵, B 是 A 经过若干次初等变换得到的矩阵, 则有 若|A|=0,则一定有 |B|=0 15．下列各式中错误的是（ A ）。 A ．{x}∈{x} B ．{x}? {x} C ．{x}∈{x,{x}} D ．{x}?{x,{x}} 16．极限)2 -4(lim 2 2 x x x -→ 的值为（ 4 ）。 17 . f(x)=sin(x2-x)是（有界函数） 18.函数1--=x e y x 在[0,+∞)上的单调性是（单调增加 ）。 19．积分 ? x x d 12 的值为（ c x +-1）。 20. 非齐次线性方程组Ax=b 中未知量个数为n ，方程个数为m ，系数矩阵A 的秩为r ，则（r=m 时，方程组Ax=b 有解 21. 行列式 5 6 2 143312---的值为（ -33 ）。 22. 设A={a,b} ,则A 的幂集)(A ρ为（ {φ,{a},{b},{a,b} } ）。 23. 设321,,ααα均为3维列向量，记矩阵 ),,(321ααα=A ，) 93,42,(321321321ααααααααα++++++=B ， 如果1=A ，那么= B （ 2 ）。 25.当ｘ→0 时，xcosx 是（ 无穷小量）。 26.下列关于函数单调性的说法正确的是（函数f(x)= x+1 （- ∞ < x < + ∞）是单调递增函数）。 27.说法正确的是 设 ()y f x =在[,]a b 上连续，且无零点，则()f x 在[,]a b 上恒为正或恒为负 28．下列几对函数中，)(x f 与)(x g 相同的是f(x)=|x| 与2 )(x x g = 29. 设f ′ (x)存在，a 为常数，则h a h x f a h x f h )()(lim 0--+→等于（ )('2x f a ）。 30. 已知 x y 2tan =,则dy 等于（ xdx tgx 2sec 2 ）。 31. 方程sinx=x 的根的个数为（1个 ）。 32 函数2 11 21)(+-= x x f 的奇偶性是（偶函数 ）。 33. 函数 x y sin =的周期是（ π ）。 34. y=lnsinx 的导数为（ ctgx ）。 35. 以向量a=(8,4,1)，b=(2,-2,1)为邻边的平行四边形面积为（ 182 ） 36 过点（1，1，2）且以n=(1,2,1)为法向量的平面方程为（x+2y+z-5=0 ） 37. 设行向量组)1,1,1,2(，),,1,2(a a ，),1,2,3(a ，)1,2,3,4(线性相关，且1≠a ，则a 的值为（ 1/2 ）。 38. 设矩阵A m ×n 的秩为r(A)＝m

组合数学在计算机科学中的应用

文章编号:167121742(2006)增20094204 组合数学在计算机科学中的应用 陈 家*, 杨光崇 (成都信息工程学院计算科学系,四川成都610225) 摘要:介绍了组合数学的概念、起源与研究的主要内容,分析了组合数学的特点,阐述了组合数学与计算机软 件的联系,并着重通过两个例子说明了Ramsey 数在计算机科学的信息检索、分组交换网设计分支中的重要应用。 关 键 词:组合数学;组合算法;Ramsey 数;信息检索;分组交换网 中图分类号:O157 文献标识码:A *成都信息工程学院计算科学系信息与计算科学专业2001级3班 1 组合数学的概念 组合数学是近年来随着计算机科学的发展而新兴起来的一门综合性、边缘性学科。组合数学是什么,有很多不同的看法。Richard A.BrualDi 所著5Introductory Combinatorics 6中认为组合数学研究的是事物按照某种规则的安排,主要有:存在性问题,计数性问题和对已知安排的研究。Daniel I. A.Cohen 所著5Basic Techniques of Combinatorial T heory 6中这样描述:组合数学就是对给定描述的事物有多少种或者某种事物发生的途径有多少种的研究。综合以上观点,组合数学就是主要研究/事物的安排0中涉及的数学问题。 2 组合数学研究的主要内容 与传统的数学课程相比,组合数学研究的是一些离散的事物之间存在的数学关系,包括存在性问题、计数性问题、构造性问题以及最优化问题等,其主要内容是计数和枚举。计数问题是组合学中研究得最多的内容,它出现在所有的数学分支中。计算机科学需要研究算法,必须对算法所需的运算量和存储单元作出估计,即算法的时间复杂性和空间复杂性分析,其中组合数学的研究主要包括以下内容[1- 3]:排列组合;生成函数和递推关系;容 斥原理和鸽巢原理;Burnside 定理与P lya 定理;线性规划等等。3 组合数学与计算机软件 311 信息时代的组合数学 现代数学可以分为两大类:一类是研究连续对象,如分析、方程等,另一类就是研究离散对象的组合数学。计算机科学就是算法的科学,而计算机所处理的对象是离散的数据,研究离散对象的科学恰恰就是组合数学。因此,在信息时代的今天,组合数学就是信息时代的数学。 312 组合数学在计算机软件的应用 随着计算机科学的发展,组合数学也在迅猛发展,而组合数学在理论方面的推进也促进计算机科学的发展。计算机软件空前发展的今天要求有相应的数学基础,组合数学作为大多数计算机软件设计的理论基础,它的重要性也就不言而喻。 组合数学在计算机方面的应用极其广泛。计算机软件与各种算法的研究分不开,为了衡量一个算法的效率,必须估计用此算法解答具有给定长的输入(问题)时需要多少步(例如算术运算、二进制比较、程序调用等的次数)。这要求对算法所需的计算量及存储单元数进行估算,这就是计数问题的内容,而组合数学分析主要研究内容就是计数和枚举的方法和理论。 第21卷增刊 2006年12月成 都 信 息 工 程 学 院 学 报JOURNAL OF CHENGDU UNIVERSIT Y OF INFORMATION T EC HNOLOGY Vol.21Suppl.Dec.2006

数学建模在计算机专业的应用

应用一图论算法 图论在计算机处理问题中占有重要地位，现实中的很多问题最终都可以转化成图论问题，或者要借助图结构来存储和处理。但是怎么把一图存入计算机就要涉及到数学建模的知识。 比如下面一图： 如果要求出从节点v1到节点v5的所有路径，就可以借助计算机来很轻松的解决。但前提条件是，必须要把图以一种计算机可以理解的形式存进去，即要把它抽象为数学问题。 在此，我们需要定义一些关于图的概念，以便更好的描述问题。 边与顶点的关系有如下几种典型情况： 简单图：无自回环，无重边的图。

无向图：边没有指向， 1212 e. i i i i i ψ（）={v,v}=v v此时称边e i与顶点12 i i v,v关联，称 顶点 1 i v与顶点 2 i v邻接。 有向图:边有指向， 1212 e. i i i i i ψ u u u u u r （）=（v,v）=v v 下面是具体涉及到图如何存储的问题： 1.图G(V,E)的关联矩阵x R=(r) ij n m ，若G(V,E)为无向图， 1 2 i j ij i j j i j j v e r v e e v e e ? ? =? ? ? 与不关联 与关联,为非自回环 与关联,为自回环 若G(V,E)为有向图， 1 2 i j ij i j i j v e r v e v e ? ? =? ? ? 与不关联 是的起点 是的终点 因此该图可以用关联矩阵表示出来，如下所示 1100000 1010100 0101001 0011010 0000111 R ?? ? ? ? = ? ? ? ?? 这样，我们就可以以矩阵的形式将图存入计算机

组合数学在计算机中的应用

目录 摘要 (1) 1.组合数学概述 (1) 2.组合数学在生活中的应用 (1) 3.组合数学与计算机软件 (1) 3.1 信息时代的组合数学 (2) 3.2 组合数学在计算机软件的应用 (2) 3.3组合数学与计算机软件的关系 (2) 3.4组合数学在国外软件业的发展状况 (2) 4 Ramsey 数在计算机科学中的应用 (3) 4.1Ramsey 定理和Ramsey 数 (3) 4.2信息检索 (3) 参考文献 (5)

组合数学在计算机中的应用 摘要：介绍了组合数学的概念、起源与研究的主要内容,分析了组合数学的特点以及其在生活中的应用,阐述了组合数学与计算机软件的联系,并着重通过两个例子说明了Ramsey 数在计算机科学的信息检索中的重要应用。 关键词：组合数学;组合算法;Ramsey 数;信息检索; 1：组合数学概述 组合数学，又称为离散数学，但有时人们也把组合数学和图论加在一起算成是离散数学。组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。组合数学的发展改变了传统数学中分析和代数占统治地位的局面。现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好象是有思维的。 2：组合数学在生活中的应用 在日常生活中我们常常遇到组合数学的问题。如果你仔细留心一张世界地图，你会发现用一种颜色对一个国家着色，那么一共只需要四种颜色就能保证每两个相邻的国家的颜色不同。这样的着色效果能使每一个国家都能清楚地显示出来。但要证明这个结论确是一个著名的世界难题，最终借助计算机才得以解决，最近人们才发现了一个更简单的证明。 当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往往需要做些调整。从理论上讲，装箱问题是一个很难的组合数学问题，即使用计算机也是不容易解决的。航空调度和航班的设定也是组合数学的问题。怎样确定各个航班以满足不同旅客转机的需要，同时也使得每个机场的航班起落分布合理。此外，在一些航班有延误等特殊情况下，怎样作最合理的调整，这些都是组合数学的问题。 组合数学在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软件。最近，德国一位著名组合数学家利用组合数学方法研究药物结构，为制药公司节省了大量的费用，引起了制药业的关注。 总之，组合数学无处不在，它的主要应用就是在各种复杂关系中找出最优的方案。所以组合数学完全可以看成是一门量化的关系学，一门量化了的运筹学，一门量化了的管理学。 3：组合数学与计算机软件 随着计算机网络的发展，计算机的使用已经影响到了人们的工作，生活，学习，社会活动以及商业活动，而计算机的应用根本上是通过软件来实现的。