2015-10-14 12:29:49 u013795675 阅读数 397
  • R语言知识体系概览

    R语言是一门统计语言,主要用于数学建模、统计计算、数据处理、可视化 等几个方向,R语言天生就不同于其他的编程语言。R语言封装了各种基础学科的计算函数,我们在R语言编程的过程中只需要调用这些计算函数,就可以构建出面向不同领域、不同业务的、复杂的数学模型。掌握R语言的语法,仅仅是学习R语言的第一步,要学好R语言,需要你要具备基础学科能力(初等数学,高等数学,线性代数,离散数学,概率论,统计学) + 业务知识(金融,生物,互联网) + IT技术(R语法,R包,数据库,算法) 的结合。所以把眼光放长点,只有把自己的综合知识水平提升,你才真正地学好R语言。换句话说,一旦你学成了R语言,你将是不可被替代的。

    11207 人正在学习 去看看 张丹

概念

  1. 集合元素
  2. 有序对
  3. 有序对的相等
  4. 笛卡尔积A×B={<x,y>|xA,yB}
  5. 关系xRy
  6. 定义域、值域:
    domR={x|yB,<x,y>R}
    ranR={y|xA,<x,y>R}
  7. 关系的性质
    • 自反性
    • 对称性
    • 传递性
    • 反自反性 x,xRx
    • 反对称性 x,y,if xRy,yRxx=y
  8. 等价关系
  9. 等价类
  10. 等价类性质
    • a[a]
    • [a]=[b]aRb
    • [a][b]=aRb
2008-03-11 12:33:00 dlyhlq 阅读数 4715
  • R语言知识体系概览

    R语言是一门统计语言,主要用于数学建模、统计计算、数据处理、可视化 等几个方向,R语言天生就不同于其他的编程语言。R语言封装了各种基础学科的计算函数,我们在R语言编程的过程中只需要调用这些计算函数,就可以构建出面向不同领域、不同业务的、复杂的数学模型。掌握R语言的语法,仅仅是学习R语言的第一步,要学好R语言,需要你要具备基础学科能力(初等数学,高等数学,线性代数,离散数学,概率论,统计学) + 业务知识(金融,生物,互联网) + IT技术(R语法,R包,数据库,算法) 的结合。所以把眼光放长点,只有把自己的综合知识水平提升,你才真正地学好R语言。换句话说,一旦你学成了R语言,你将是不可被替代的。

    11207 人正在学习 去看看 张丹

我来一本推荐:

离散数学导学
http://book.jqcq.com/product/408873.html
离散数学的基本概念与基础知识,并把理论知识与一系列实际应用联系起来。主要内容包括:命题逻辑和谓词逻辑、类型集合论、布尔代数、关系、函数、序列、归纳法、图论、组合数学等。通过适当的教学方法,可以加深学生对离散数学的理解。本书适合所有学习离散数学的学生,并可作为相关专业的教材。

离散数学及其应用(英文版,第4版) 离散数学及其应用(英文版,第4版)
http://book.jqcq.com/product/303083.html
离散数学所获得的经验基础上写出的,其目的是为学生提供准确而可读的教材,使离散数学的概念和技术得以清晰地介绍和演示。向爱怀疑的学生们展示离散数学的实用性。为计算机科学专业的学生提供一切必需的数学基矗使数学专业的学生理解数学概念的重要性以及这些概念为什么对应用而言是重要的。为教师(指导者)设计一个灵 ...

离散数学与组合数学(第5版) 离散数学与组合数学(第5版)
http://book.jqcq.com/product/586647.html
离散数学是大学计算机专业最重要的必修课程之一,是许多计算机专业课程的基矗组合数学是研究图论、密码学、编码理论、算法复杂性的基本数学工具。本书是一个优秀的离散数学与组合数学的入门教材,包括计数、数理逻辑、集合论、图论、应用代数等基本内容,还有与计算技术密切相关的许多算法。作者Grimaldi教授具有极其极其 ...

离散数学及其应用(原书第5版)
http://book.jqcq.com/product/620737.html
离散数学教材,为全球多所大学广为采用。本书全面而系统地介绍了离散数学的理论和方法,内容涉及数学推理、组合分析、离散结构和算法设计。全书取材广泛,除包括定义、定理的严密陈述外,还配备大量的实例和图表的说明,各种练习和题目,以及丰富的历史资料和网站资源。第5版在前四版的基础上做了大量的改进,使其成为? ...

离散数学(第四版)
http://book.jqcq.com/product/583297.html
离散数学的入门教材,充分考虑到了初学者的需要,内容、例题、习题都作了精心的挑选和组织,讲解细致,叙述浅显易懂,循序渐进,用例贴近日常生活或计算机应用,并注重算法。主要内容包括集合、关系、函数、图论、组合数学、组合电路设计、有限自动机、算法、逻辑等。本书可作为计算机专业或其他相关专业的离散数学教 ...

数据结构与STL(英文版) 数据结构与STL(英文版)
http://book.jqcq.com/product/345529.html
数据结构及其实现的基础知识。书中引导学生通过对方法接口、示例和应用的学习,逐渐理解和掌握如何高效地使用数据结构。适合课堂教学和自学参考。 本书特色大多数数据结构用STL(标准模板库)提供,并详细探究了STL数据结构的规范实现,同时讨论了一些数据结构的其他实现方式,可以使学生尽早接触工程实践,为未来 ...

数据结构 C++语言描述(英文影印版)
http://book.jqcq.com/product/306107.html
数据结构。内容从数据结构的基本原理到面向对象程序设计的方法。书内使用适应面极广的C++语言。全书14章分别为:1.绪论;2.基本数据类型;3.抽象数据类型与类;4.集合类;5.栈与队列;6.抽象运算符;7.类属数据类型;8.类与动态存储;9.链表;10.递归;11.树;12.继承与抽象类;13.先进的非线性结构;14.构建集合。书后 ...

计算机算法(C++版)
http://book.jqcq.com/product/413600.html
算法在设计与分析文献的一本经典著作。书中介绍了算法和算法性能的基本知识,基本的数据结构知识,重点讨论了不同的算法设计策略,研究了下界理论等,提供了计算机算法的设计技术和有效的算法分析,以及大量的详细实例和实际应用。同时,对NP难和NP完全问题能否有效求解进行了分析。本书还汇聚了各种随机算法与并行算法 ...

数据结构与算法分析:C++描述(第3版) 数据结构与算法分析:C++描述(第3版)
http://book.jqcq.com/product/431801.html
算法分析的经典教材,书中使用主流的程序设计语言C++作为具体的实现语言。书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。本书适合作为计算机相关专业本科生的数据结构课程和研究生算法分析课程的教材。本科生的数据结构 ...
参考资料:http://www.jqcq.com/forum

(摘自 http://zhidao.baidu.com/question/35635271.html?si=5

2015-07-02 21:54:36 love125 阅读数 369
  • R语言知识体系概览

    R语言是一门统计语言,主要用于数学建模、统计计算、数据处理、可视化 等几个方向,R语言天生就不同于其他的编程语言。R语言封装了各种基础学科的计算函数,我们在R语言编程的过程中只需要调用这些计算函数,就可以构建出面向不同领域、不同业务的、复杂的数学模型。掌握R语言的语法,仅仅是学习R语言的第一步,要学好R语言,需要你要具备基础学科能力(初等数学,高等数学,线性代数,离散数学,概率论,统计学) + 业务知识(金融,生物,互联网) + IT技术(R语法,R包,数据库,算法) 的结合。所以把眼光放长点,只有把自己的综合知识水平提升,你才真正地学好R语言。换句话说,一旦你学成了R语言,你将是不可被替代的。

    11207 人正在学习 去看看 张丹

一    集合

基数Cardinality):集合内元素的个数。A的基数一般记为|A|。

平凡子集:P的平凡自己只有2个,P和 Φ。  (之所以谓之“平凡”,时因为每个集合均有这两个子集【Φ的这2个子集重合】)

幂集(Power Set):集合A所有的子集构成的集合,为A的幂集。(其实称幂集,与原文power set关系不大,是因为Card P(A)的值为2^n【n为A中元素的个数】,恰为2 n次  幂,故称之为幂集。有些书籍会以2^A来表示A的幂集。)

对称差(Symmetric difference):把P和Q的所有元素扣除P和Q的公共元素所组成的集合。【P∪Q-P∩Q】


二   归纳方法


数学归纳法的推广

1.有限归纳法

设S为一命题,若

(1)s(n0)成立(n0 >= 1)。

(2)由n0 <= n <= m0 - 1对s(n)成立,能推出s(n + 1)成立。【数学归纳法在有限范围内的应用,故称之为有限归纳法】

则s(n)对n0 <= n <= m0都成立。                                                      

2.归纳法

设S为一命题,若

(1)s(n0)成立(n0 >= 1)。

(2)假设n0 <= n <= k时s(n)成立,能推出s(k + 1)成立。【由假定一个范围里都成立,推出下一个成立,论据加强了】

则s(n)对n >= n0都成立。    


二   二元关系


各类二元关系的性质

自反性:... 自反闭包:...R(A)    [reverse]         ...

对称性:... 对称闭包:...S(A)    [symmetric]· 反...

传递性:... 传递闭包:...  R*

关于传递闭包(R*)的定理:

设|A| = n,R是A上的二元关系,则存在正整数k,k <= n,使得R* = R ∪ R^2 ∪ R^3 ∪.....∪ R^k。

由定理,求R*时,k取到n时,已经足够大了,于是可用R* = R ∪ R^2 ∪ R^3 ∪.....∪ R^n来求R*。

据此求法有比较有效的Warshall算法

设R是n个元素上的二元关系,

(1)(a,j)nxn是R的相关矩阵;

(2)  i <- 1;

(3)  for j = 1 to n do

    if aj,i =1,then do

for k = 1 to n do

aj,k <- aj,k  ∪ ai,k

(4)i <- i + 1

(5)if i <= n,then go (3) else stop.

其结果已变成R*的矩阵形式了,算法时间杂度为O(n^3),是一好算法。

Warshall 的C语言实现:


//Warshall算法C语言实现

#include <stdio.h>


#define N 3


int main (void)
{
int a[N][N] = {{1,1,0},{0,0,1},{0,0,0}},i,j,k;


for(i = 0; i < N; i ++)
for(j = 0; j < N; j ++)
{
if(a[j][i] == 1)
for(k = 0; k < N; k ++)
a[j][k] = a[j][k] || a[i][k];
}


for(i = 0; i < N; i ++) // 结果输出
{
for(j = 0; j < N; j ++)
printf("%d\t",a[i][j]);
printf("\n");
}


return 0;
}


     


2018-02-03 11:56:44 xyisv 阅读数 4998
  • R语言知识体系概览

    R语言是一门统计语言,主要用于数学建模、统计计算、数据处理、可视化 等几个方向,R语言天生就不同于其他的编程语言。R语言封装了各种基础学科的计算函数,我们在R语言编程的过程中只需要调用这些计算函数,就可以构建出面向不同领域、不同业务的、复杂的数学模型。掌握R语言的语法,仅仅是学习R语言的第一步,要学好R语言,需要你要具备基础学科能力(初等数学,高等数学,线性代数,离散数学,概率论,统计学) + 业务知识(金融,生物,互联网) + IT技术(R语法,R包,数据库,算法) 的结合。所以把眼光放长点,只有把自己的综合知识水平提升,你才真正地学好R语言。换句话说,一旦你学成了R语言,你将是不可被替代的。

    11207 人正在学习 去看看 张丹

自从我们学院进行软件 工程认证后,期末考试的专业课全部是大题。这次离散数学的最后一题是:利用本学期学到的离散数学的知识阐释其在一个软件工程中的应用。

下面说说离散数学的应用。

离散数学在数据结构中的应用
数据结构中将操作对象间的关系分为四类:集合、线性结构、树形结构、图状结构或网状结构。数据结构研究的主要内容是数据的逻辑结构,物理存储结构以及基本运算操作。其中逻辑结构和基本运算操作来源于离散数学中的离散结构和算法思考。离散数学中的集合论、关系、图论、树四个章节就反映了数据结构中四大结构的知识。如集合由元素组成,元素可理解为世上的客观事物。关系是集合的元素之间都存在某种关系。例如雇员与其工资之间的关系。图论是有许多现代应用的古老题目。瑞士数学家列昂哈德·欧拉在18世纪引进了图论的基本思想,他利用图解决了哥尼斯堡七桥问题。还可以用边上带权值的图来解决诸如寻找交通网络里两城市之间最短通路的问题。而树反映对象之间的关系,如组织机构图、家族图、二进制编码都是以树作为模型来讨论。

离散数学在数据库中的应用
数据库技术被广泛应用于社会各个领域,关系数据库已经成为数据库的主流,离散数学中的笛卡儿积是一个纯数学理论,是研究关系数据库的一种重要方法,显示出不可替代的作用。不仅为其提供理论和方法上的支持,更重要的是推动了数据库技术的研究和发展。关系数据模型建立在严格的集合代数的基础上,其数据的逻辑结构是一个由行和列组成的二维表来描述关系数据模型。在研究实体集中的域和域之间的可能关系、表结构的确定与设计、关系操作的数据查询和维护功能的实现、关系分解的无损连接性分析、连接依赖等问题都用到二元关系理论。

离散数学在编译原理中的应用
编译程序是计算机的一个十分复杂的系统程序。一个典型的编译程序一般都含有八个部分:词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、错误检查和处理程序、各种信息表格的管理程序。离散数学里的计算模型章节里就讲了三种类型的计算模型:文法、有限状态机和图灵机。具体知识有语言和文法、带输出的有限状态机、不带输出的有限状态机、语言的识别、图灵机等。短语结构文法根据产生式类型来分类:0型文法、1型文法、2型文法、3型文法。以上这些在离散数学里讲述到的知识点在编译原理的词法分析及语法分析中都会用到。因此,离散数学也是编译原理的前期基础课程。

离散数学在人工智能中的应用
在人工智能的研究与应用领域中,逻辑推理是人工智能研究中最持久的子领域之一。逻辑是所有数学推理的基础,对人工智能有实际的应用。采用谓词逻辑语言的演绎过程的形式化有助于我们更清楚地理解推理的某些子命题。逻辑规则给出数学语句的准确定义。离散数学中数学推理和布尔代数章节中的知识就为早期的人工智能研究领域打下了良好的数学基础。许多非形式的工作,包括医疗诊断和信息检索都可以和定理证明问题一样加以形式化。因此,在人工智能方法的研究中定理证明是一个极其重要的论题。在这里,推理机就是实现(机器)推理的程序。它既包括通常的逻辑推理,也包括基于产生式的操作。推理机是使用知识库中的知识进行推理而解决问题的。所以推理机也就是专家的思维机制,即专家分析问题、解决问题的方法的一种算法表示和机器实现。当然以上说的是专家系统,一般来说这种人工智能已经被基于统计学习的机器学习所取代。

离散数学在计算机体系结构中的应用
在计算机体系结构中,指令系统的设计和改进内容占有相当重要的地位,指令系统的优化意味着整个计算机系统性能的提高。指令系统的优化方法很多,一种方法是对指令的格式进行优化,一条机器指令是由操作码和地址码组成,指令格式的优化是指如何用最短的位数来表示指令的操作信息和地址信息,使程序中的指令的平均字长最短。为此可以用到哈夫曼的压缩概念,哈夫曼(Huffman)压缩是一种无损压缩法。Huffman压缩概念的基本思想是,当各种事件发生的概率不均等时,采用优化技术对发生概率最高的事件用最短的位数(时间)来表示(处理),而对出现概率较低的允许用较长的位数(时间)来表示(处理),就会导致表示(处理)的平均位数(时间)的缩短。利用哈夫曼算法,构造出哈夫曼树。方法是将指令系统的所有指令的使用频度进行统计,并按使用频度由小到大排序,每次选择其中最小的两个频度合并成一个频度是它们二者之和的新结点。再按该频度大小插入余下未参与结合的频度值中。如此继续进行,直到全部频度结合完毕形成根结点为止,之后,对每个结点向下延伸的两个分支,分别标注“1”或“0”,从根结点开始,沿线到达各频度结点所经过的代码序列就构成了该指令的哈夫曼编码。这样得到的编码系列就符合了指令使用概率低的指令编以长码,指令使用概率高的指令编以短码的初衷。

补充
离散数学在计算机研究中的作用越来越大,计算机科学中普遍采用离散数学中的一些基本概念、基本思想、基本方法,使得计算机科学越趋完善与成熟。离散数学在计算机科学和技术中有着广泛应用,除了在上述提到的领域中发挥了重要作用外,在其他领域也有着重要的应用,如离散数学中的数理逻辑部分在计算机硬件设计中的应用尤为突出,数字逻辑作为计算机科学的一个重要理论,在很大程度上起源于离散数学的数理逻辑中的命题与逻辑演算。利用命题中各关联词的运算规律把由高低电平表示的各信号之间的运算与二进制数之间的运算联系起来,使得我们可以用数学的方法来解决电路设计问题,使得整个设计过程变得更加直观,更加系统化。集合论在计算机科学中也有广泛的应用,它为数据结构和算法分析奠定了数学基础,也为许多问题从算法角度如何加以解决提供了进行抽象和描述的一些重要方法,在软件工程和数据库中也会用到。代数结构是关于运算或计算规则的学问,在计算机科学中,代数方法被广泛应用于许多分支学科,如可计算性与计算复杂性、形式语言与自动机、密码学、网络与通信理论、程序理论和形式语义学等,格与布尔代数理论成为电子计算机硬件设计和通讯系统设计中的重要工具,图论对开关理论与逻辑设计、计算机制图、操作系统、程序设计语言的编译系统以及信息的组织与检索起重要作用,其平面图、树的研究对集成电路的布线、网络线路的铺设、网络信息流量的分析等的实用价值显而易见

2014-12-18 20:45:26 utimes 阅读数 7984
  • R语言知识体系概览

    R语言是一门统计语言,主要用于数学建模、统计计算、数据处理、可视化 等几个方向,R语言天生就不同于其他的编程语言。R语言封装了各种基础学科的计算函数,我们在R语言编程的过程中只需要调用这些计算函数,就可以构建出面向不同领域、不同业务的、复杂的数学模型。掌握R语言的语法,仅仅是学习R语言的第一步,要学好R语言,需要你要具备基础学科能力(初等数学,高等数学,线性代数,离散数学,概率论,统计学) + 业务知识(金融,生物,互联网) + IT技术(R语法,R包,数据库,算法) 的结合。所以把眼光放长点,只有把自己的综合知识水平提升,你才真正地学好R语言。换句话说,一旦你学成了R语言,你将是不可被替代的。

    11207 人正在学习 去看看 张丹

引言

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

随着信息时代的到来,工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化,离散数学的重要性逐渐被人们认识。离散数学课程所传授的思想和方法,广泛地体现在计算机科学技术及相关专业的诸领域,从科学计算到信息处理,从理论计算机科学到计算机应用技术,从计算机软件到计算机硬件,从人工智能到认知系统,无不与离散数学密切相关。

由于数字电子计算机是一个离散结构,它只能处理离散的或离散化了的数量关系, 因此,无论计算机科学本身,还是与计算机科学及其应用密切相关的现代科学研究领域,都面临着如何对离散结构建立相应的数学模型;又如何将已用连续数量关系建立起来的数学模型离散化,从而可由计算机加以处理。由此可见,离散数学在计算机科学中具有广泛的应用.

如何学习离散数学 

学习离散数学有两项最基本的任务:其一是通过学习离散数学,使学生了解和掌握在后续课程中要直接用到的一些数学概念和基本原理,掌握计算机中常用的科学论证方法,为后续课程的学习奠定一个良好的数学基础;其二是在离散数学的学习过程中,培训自学能力、抽象思维能力和逻辑推理能力,以提高专业理论水平。因此学习离散数学对于计算机、通信等专业后续课程的学习和今后从事计算机科学等工作是至关重要的。但是由于离散数学的离散性、知识的分散性和处理问题的特殊性,使部分学生在刚刚接触离散数学时,对其中的一些概念和处理问题的方法往往感到困惑,特别是在做证明题时感到无从下手,找不到正确的解题思路。因此,对离散数学的学习方法给予适当的指导和对学习过程中遇到的一些问题分析是十分必要的。

认知离散数学

离散数学是计算机科学基础理论的核心课程之一,是计算机及应用、通信等专业的一门重要的基础课。它以研究量的结构和相互关系为主要目标,其研究对象一般是有限个或可数个元素,充分体现了计算机科学离散性的特点。学习离散数学的目的是为学习计算机、通信等专业各后续课程做好必要的知识准备,进一步提高抽象思维和逻辑推理的能力,为计算机的应用提供必要的描述工具和理论基础。

  • 定义和定理多 离散数学是建立在大量定义、定理之上的逻辑推理学科,因此对概念的理解是学习这门课程的核心。在学习这些概念的基础上,要特别注意概念之间的联系,而描述这些联系的实体则是大量的定理和性质。在考试中有一部分内容是考查学生对定义和定理的识记、理解和运用,因此要真正理解离散数学中所给出的每个基本概念的真正的含义。比如,命题的定义、五个基本联结词、公式的主析取范式和主合取范式、三个推理规则以及反证法;集合的五种运算的定义;关系的定义和关系的四个性质;函数(映射)和几种特殊函数(映射)的定义;图、完全图、简单图、子图、补图的定义;图中简单路、基本路的定义以及两个图同构的定义;树与最小生成树的定义。掌握和理解这些概念对于学好离散数学是至关重要的。
  • 方法性强 在离散数学的学习过程中,一定要注重和掌握离散数学处理问题的方法,在做题时,找到一个合适的解题思路和方法是极为重要的。如果知道了一道题用怎样的方法去做或证明,就能很容易地做或证出来。反之,则事倍功半。在离散数学中,虽然各种各样的题种类繁多,但每类题的解法均有规律可循。所以在听课和平时的复习中,要善于总结和归纳具有规律性的内容。在平时的讲课和复习中,老师会总结各类解题思路和方法。作为学生,首先应该熟悉并且会用这些方法,同时,还要勤于思考,对于一道题,进可能地多探讨几种解法。
  • 抽象性强 离散数学的特点是知识点集中,对抽象思维能力的要求较高。由于这些定义的抽象性,使初学者往往不能在脑海中直接建立起它们与现实世界中客观事物的联系。不管是哪本离散数学教材,都会在每一章中首先列出若干个定义和定理,接着就是这些定义和定理的直接应用,如果没有较好的抽象思维能力,学习离散数学确实具有一定的困难。因此,在离散数学的学习中,要注重抽象思维能力、逻辑推理能力的培养和训练,这种能力的培养对今后从事各种工作都是极其重要的。在学习离散数学中所遇到的这些困难,可以通过多学、多看、认真分析讲课中所给出的典型例题的解题过程,再加上多练,从而逐步得到解决。在此特别强调一点:深入地理解和掌握离散数学的基本概念、基本定理和结论,是学好离散数学的重要前提之一。所以,同学们要准确、全面、完整地记忆和理解所有这些基本定义和定理。
  • 内在联系性 离散数学的三大体系虽然来自于不同的学科,但是这三大体系前后贯通,形成一个有机的整体。通过认真的分析可寻找出三大部分之间知识的内在联系性和规律性。如:集合论、函数、关系和图论,其解题思路和证明方法均有相同或相似之处。

认知解题规范

一般来说,离散数学的考试要求分为:了解、理解和掌握。了解是能正确判别有关概念和方法;理解是能正确表达有关概念和方法的含义;掌握是在理解的基础上加以灵活应用。为了考核学生对这三部分的理解和掌握的程度,试题类型一般可分为:判断题、填空题、选择题、计算题和证明题。判断题、填空题、选择题主要涉及基本概念、基本理论、重要性质和结论、公式及其简单计算;计算题主要考核学生的基本运用技能和速度,要求写出完整的计算过程和步骤;证明题主要考查应用概念、性质、定理及重要结论进行逻辑推理的能力,要求写出严格的推理和论证过程。

学习离散数学的最大困难是它的抽象性和逻辑推理的严密性。在离散数学中,假设让你解一道题或证明一个命题,你应首先读懂题意,然后寻找解题或证明的思路和方法,当你相信已找到了解题或证明的思路和方法,你必须把它严格地写出来。一个写得很好的解题过程或证明是一系列的陈述,其中每一条陈述都是前面的陈述经过简单的推理而得到的。仔细地写解题过程或证明是很重要的,既能让读者理解它,又能保证解题过程或证明准确无误。一个好的解题过程或证明应该是条理清楚、论据充分、表述简洁的。针对这一要求,在讲课中老师会提供大量的典型例题供同学们参考和学习。

通过离散数学的学习和训练,能使同学们学会在离散数学中处理问题的一般性的规律和方法,一旦掌握了离散数学中这种处理问题的思想方法,学习和掌握离散数学的知识就不再是一件难事了。

学习离散数学的目的

一般来说,离散数学内容广泛且高度抽象,可以说是一门既难教又难学的课程,这无疑给教师的教学和学生的学习带来了一定的难度。一方面,离散数学不仅 是为专业服务的基本理论,而且通过该课程可以培养学生的抽象思维和缜密概括的能力,但其概念多,理论性强,高度抽象性的特点却令许多学生望而生畏。学生在 学习这门课程时,往往看不到离散数学在计算机科学中的具体应用,因而放松对离散数学的学习,失去学习的兴趣。

离散数学的生命力在于其深刻的理论和广泛的应用。其实,深刻的理论和广泛的应用是相辅相成的。学生之所以对离散数学的学习兴趣不高,除了离散数学本身理论性 强、比较抽象以外,还有一个原因就是对于这些理论方面的知识,学生在学习过程中并不会切实地感受到学好它的作用和成效,因此只把应付考试作为学习这门课程 的目的。作为老师,我们在教学之初就应该向学生们指明,学习离散数学的目的在于培养学生的抽象推理、逻辑思维和归纳构造等能力,提高学生利用数学方法解决问题的技能,以及为后续课程作必要的准备,为学生的进一步学习奠定计算机数学的基础。它所涉及的概念、方法和理论,大量地应用在数字电路、编译原理、数据结构、操作系统、数据库、算法等领域。

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

在人工智能中的应用

人工智能是计算机学科中一个非常重要的方向,离散数学在人工智能中的应用主要是数理逻辑部分在人工智能中的应用。数理逻辑包括命题逻辑和谓词逻辑,命题逻辑就是研究以命题为单位进行前提与结论之间的推理,而谓词逻辑就是研究句子内在的联系。大家都知道,人工智能共有两个流派,连接主义流派和符号主义流派。其中在符号主义流派里,他们认为现实世界的各种事物可以用符号的形式表示出来,其中最主要的就是人类的自然语言可以用符号进行表示。语言的符号化就是数理逻辑研究的基本内容,计算机智能化的前提就是将人类的语言符号化成机器可以识别的符号,这样计算机才能进行推理,才能具有智能。由此可见数理逻辑中重要的思想、方法及内容贯穿到人工智能的整个学科。

在人工智能的研究与应用领域中,逻辑推理是人工智能研究中最持久的子领域之一。逻辑是所有数学推理的基础,对人工智能有实际的应用。采用谓词逻辑语言的演绎过程的形式化有助于我们更清楚地理解推理的某些子命题。逻辑规则给出数学语句的准确定义。离散数学中数学推理和布尔代数章节中的知识就为早期的人工智能研究领域打下了良好的数学基础。许多非形式的工作,包括医疗诊断和信息检索都可以和定理证明问题一样加以形式化。因此,在人工智能方法的研究中定理证明是一个极其重要的论题。在这里,推理机就是实现(机器)推理的程序。它既包括通常的逻辑推理,也包括基于产生式的操作。推理机是使用知识库中的知识进行推理而解决问题的。所以推理机也就是专家的思维机制,即专家分析问题、解决问题的方法的一种算法表示和机器实现。

在数据库系统理论中的应用

集合论是离散数学中极其重要的一部分,它在数据库中有着广泛的应用。我们可以利用关系理论使数据库从网络型、层次型转变成关系型,这样使数据库中的数据容易表示,并且易于存储和处理,使逻辑结构简单、数据独立性强、数据共享、数据冗余可控和操作简单。当数据库中记录较多时,集合中的笛卡儿积方便了记录的查询、插入、删除和修改。 关系数据库中的数据管理系统向用户提供使用的数据库语言称为数据子语言,它是以关系代数或谓词逻辑中的方法表示。由于用这种数学的方法去表示,使得对这些语言的研究成为对关系代数或逻辑谓词的研究,优化语言的表示变成为对关系代数与谓词逻辑的化简问题。由于引入了数学表示方法,使得关系数据库具有比其它几种数据库较为优越的条件。正因为如此关系数据库迅速发展成为一种很有前途、很有希望的数据库。另外,离散数学中的笛卡儿积是一个纯数学理论,是研究关系数据库的一种重要方法,显示出不可替代的作用。不仅为其提供理论和方法上的支持,更重要的是推动了数据库技术的研究和发展。关系数据模型建立在严格的集合代数的基础上,其数据的逻辑结构是一个由行和列组成的二维表来描述关系数据模型。在研究实体集中的域和域之间的可能关系、表结构的确定与设计、关系操作的数据查询和维护功能的实现、关系分解的无损连接性分析、连接依赖等问题都用到二元关系理论。

在数据结构中的应用

计算机要解决一个具体问题,必须运用数据结构知识。对于问题中所处理的数据,必须首先从具体问题中抽象出一个适当的数学模型,然后设计一个解此数学模型的算法,最后编出程序,进行测试、调整直至得到问题的最终解答。而寻求数学模型就是数据结构研究的内容。寻求数学模型的实质是分析问题,从中提取操作的对象,并找出这些操作对象之间含有的关系,然后用数学的语言加以描述。数据结构中将操作对象间的关系分为四类:集合、线性结构、树形结构、图状结构或网状结构。数据结构研究的主要内容是数据的逻辑结构,物理存储结构以及基本运算操作。其中逻辑结构和基本运算操作来源于离散数学中的离散结构和算法思考。离散数学中的集合论、关系、图论、树四个章节就反映了数据结构中四大结构的知识。如集合由元素组成,元素可理解为世上的客观事物。关系是集合的元素之间都存在某种关系。例如雇员与其工资之间的关系。图论是有许多现代应用的古老题目。伟大的瑞士数学家列昂哈德·欧拉在18 世纪引进了图论的基本思想,他利用图解决了有名的哥尼斯堡七桥问题。还可以用边上带权值的图来解决诸如寻找交通网络里两城市之间最短通路的问题。而树反映对象之间的关系,如组织机构图、家族图、二进制编码都是以树作为模型来讨论。

在编译原理中的应用

编译程序是计算机的一个十分复杂的系统程序。一个典型的编译程序一般都含有八个部分:词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、错误检查和处理程序、各种信息表格的管理程序。离散数学里的计算模型章节里就讲了三种类型的计算模型:文法、有限状态机和图灵机。具体知识有语言和文法、带输出的有限状态机、不带输出的有限状态机、语言的识别、图灵机等。短语结构文法根据产生式类型来分类:0 型文法、1 型文法、2 型文法、3 型文法。以上这些在离散数学里讲述到的知识点在编译原理的词法分析及语法分析中都会用到。因此,离散数学也是编译原理的前期基础课程。

在计算机硬件设计中的应用

数字逻辑作为计算机的一个重要理论,在很大程度上起源于离散数学的数理逻辑中的命题与逻辑演算,其在计算机硬件设计中的应用更为突出。利用命题中各关联词的运算规律把又电平表示的各信号之间的运算于二进制数之间的运算联系起来,使得我们可以用与非门或者用或非门来解决电路设计问题,使得整个设计过程更加直观、系统化。数理逻辑在程序设计中起到花间的作用,当一个程序初稿拿出来以后,如果我们想分析一下其中是否有冗余存在,这时就用到了离散数学中命题演算的基本等式。

在计算机纠错码中的应用

计算机中,常常需要将二进制数字信号进行传递。这种传递的距离近则数米、数毫米,远则超过数千公里。在传递过程中,由于存在各种干挠,常常会使二进制信号产生失真现象。而利用离散数学的集合论、群论和数理逻辑来分析研究计算机纠错码的纠错能力,是离散数学在计算机科学中的一个重要应用方面。代数系统在计算机中的应用广泛,例如有限机,开关线路的计数等方面。但最常用的是在纠错码方面的应用。在计算机和数据通信中,经常需要将二进制数字信号进行传递,这种传递常常距离很远,所以难免会出现错误。通常采用纠错码来避免这种错误的发生,而设计的这种纠错码的数学基础就是代数系统。纠错码中的一致校验矩阵就是根据代数系统中的群概念来进行设计的,另外在群码的校正中,也用到了代数系统中的陪集。

在生物信息学中的应用

生物信息学是现代计算机科学中一个崭新的分支,它是计算机科学与生物学相结合的产物。目前,在美国有一个国家实验室Sandia国家实验室,主要进行组合编码理论和密码学的研究,该机构在美国和国际学术界有很高的地位。另外,由于DNA是离散数学中的序列结构,美国科学院院士,近代离散数学的奠基人Rota教授预言,生物学中的组合问题将成为离散数学的一个前沿领域。而且,IBM公司也将成立一个生物信息学研究中心。在1994年美国计算机科学家阿德勒曼公布了DNA计算机的理论,并成功地运用DNA计算机解决了一个有向哈密尔顿路径问题,这一成果迅速在国际产生了巨大的反响,同时也引起了国内学者的关注。DNA计算机的基本思想是:以DNA碱基序列作为信息编码的载体,利用现代分子生物学技术,在试管内控制酶作用下的DNA序列反应,作为实现运算的过程;这样,以反应前DNA序列作为输入的数据,反应后的DNA序列作为运算的结果,DNA计算机几乎能够解决所有的NP完全问题。 

在其他方面的应用

 对谓词演算公理系统的研究使得美国数理逻辑学家罗宾逊于1965 年创立了“消解原理”的算法,在此算法的基础上,法国马赛大学的柯尔密勒设计并实现了一种基于谓词演算的逻辑程序设计语言PROLOG(programming in logic) ,该语言不久即在众多计算机上得以实现. 这样一来,现实世界中的问题只要能用谓词演算公理系统方式表示出来,就可以将它写成PROLOG程序,然后在计算机上得以实现。


参考文献

[1] Discrete mathematics From Wikipedia, the free encyclopedia

[2] Discrete mathematics at the utk.edu Mathematics Archives, providiing links to syllabi, tutorials, programs, etc.

[3] Weisstein, Eric W., "Discrete mathematics", MathWorld.
[4]  Biggs, Norman L. (2002), Discrete mathematics, Oxford Science Publications (2nd ed.), New York: The Clarendon Press Oxford University Press, p. 89, ISBN 9780198507178, MR 1078626, Discrete Mathematics is the branch of Mathematics in which we deal with questions involving finite or countably infinite sets.

[5] Wilson, Robin (2002). Four Colors Suffice. London: Penguin Books. ISBN 978-0-691-11533-7.

[6] Samuel R. Buss (1998). Handbook of Proof Theory. Elsevier. p. 13. ISBN 978-0-444-89840-1.

[7] 耿素云,屈婉玲,离散数学[M].北京:高等教育出版社,1998.

[8] 左孝凌,李永监,刘永才编著.离散数学[M].上海:上海科学技术文献出版社,2004.

[9] 朱一清.离散数学[M].北京:电子工业出版社,2004


关于Discrete Mathematics更多讨论与交流,敬请关注本博客和新浪微博songzi_tea.

没有更多推荐了,返回首页