计算机数学全套电子课件完整版ppt整本书电子教案最全教学教程

1、绪论课程要求总评成绩=考试成绩70%+平时成绩30%平时成绩：以90分起评考勤：旷课-10分 迟到-5分作业：缺交-10分上课积极回答问题：+35分作业完成优秀：+35分课程内容第0章 数字系统第1章 集合与关系第3章 算法基础第4章 图论第5章 树4李尚志 咏数学模型数学精微何处寻,纷纭世界有模型.描摹万象得神韵,识破玄机算古今.岂是空文无实效,能生妙策济苍生.经天纬地显身手,七十二行任纵横.数学是“神马” 在高斯的眼里，数学是“科学之王”；在毕达哥拉斯眼中，“数支配着宇宙”；在笛卡儿眼中，“数学是知识的工具，亦是其他知识工具的源泉”，在很多经历过高考的学生看来，数学是他们的噩梦。数学有用吗

2、？当今的高速、便宜的计算机已经给深奥的数学进展找到了立即的实际应用。借助于“数学企业家”的帮助，公司现在能够改造这些方程和算法使之能应对一批商业挑战。下面是一些例子：腾讯公司副总裁吴军最新力作数学之美由创新工场董事长兼首席执行官李开复倾力作序推荐。数学之美的创作源自点击超百万的谷歌黑板报专题博客，吴军老师应出版要求重新编写。 几年前，“数学之美”系列文章原刊载于谷歌黑板报，获得上百万次点击，并被热情的读者广为传播，得到高度评价。读者说，读了“数学之美”，才发现大学时学的数学知识，比如马尔科夫链、矩阵计算，甚至余弦函数原来都如此亲切，并且栩栩如生，才发现自然语言和信息处理这么有趣，才真正明白“数

3、学是科学的皇后”这句名言。一个简单的例子在座的诸位同学中准有两位同学的生日在同一天，甚至在一个只有四、五十的团体里面，我也可以这样说这是为什么呢？一个班的同学的生日可以分两种情况：A表示该班至少有两个人的生日在同一天，则 表示该班任何两个同学的生日都不相同。设该班共有m个同学，则 发生的概率为从而“该班同学中至少有两位生日相同”的概率为m101520253035p0.11690.25290.41140.56870.70630.8144m4045505560p0.89120.94100.97040.98630.9941通过计算，我们很难想象到，一个班级60位同学，至少有两人的生日在同一天的概率竟

4、高达99%以上；而他们的生日全不相同，这个人们认为最有可能发生的事，反而是百里挑一的稀罕事！我们老祖宗早就发现了这个规律，假如我们一年中发生60件新鲜事（或不太顺心的事），那么我们总会感受到“双喜临门”(祸不单行)数学是沟通现实世界的桥梁高技术本质上是数学技术戴维(E. David, 1972年曾任尼克松总统的科学顾问，1966年入选美国工程院院士)在1984年说的一段话：“对数学研究的低水平的资助只能来自对于数学研究带来的好处的完全不妥的评价，显然，很少有人认识到当今被如此称颂的高技术本质上是数学技术。”. the low levels of support for mathematics

5、research can only flow from a totally inadequate preciation of the benefits it confers. Apparently, too few people recognize that the high technology that is so celebrated today is essentially mathematical technology.E. E. David Jr., Notices of American Mathematical Society, v. 31(1984), no. 2, p. 1

6、42. 钱学森教授1989年在中国数学会数学教育与科研座谈会上的讲话中说:“但是他(指美国Brown大学教授、应用数学家谢定裕)的题目叫“数学科技”, 我想不叫“数学科技”, 这是数学技术, 即怎样给一个方法, 能使科学的理论通过电子计算机解答具体的科学技术问题. 这包括两个方面, 第一就是要会用电子计算机, 会指挥它去算. 第二是电子计算机给出的解答, 在荧光屏上显示出来, 能够理解它, 别让它给唬住了. 我觉得后一个关于理解的问题, 就是要从宏观的整体角度去认识, 这也是数学问题.”21世纪是科学和工程数学化的世纪 美国科学基金会数学部主任Eisenstein在评述该基金会把数学科学列为2

7、002-2006该基金会五大创新项目(其他四个分别为: 环境中的生物复杂性,信息技术研究,纳米科学和工程,以及21世纪的劳动力)之首时所说的,“该重大创新项目背后的推动力就是一切科学和工程领域的数学化(Mathematization).”数学等于机会“我今天给你们的统计资料清楚地表明：“数学等于机会”。当我们为即将来临的世纪作准备时，不可能再送给美国父母和学生别的更关键的信息了。” “As the statistics I have related to you today make clear, Mathematics Equals Opportunity. There could be n

8、o more crucial massage to send to the parents and students of America as we prepare for the coming century. ”Richard W. Riley (克林顿任总统时的教育部长),数学建模竞赛全国大学生数学建模竞赛全国大学生数学建模竞赛：美国大学生数学建模竞赛http:/ 中国研究中心- 招聘条件Position title: Business Optimization(BJ)1Background in industrial engineering, operations research,

9、 mathematics, Artificial Intelligence, management science etc. 2. Knowledge in network design, job scheduling, data analysis, simulation and optimization 3Award in mathematical contest in modeling is a plus 4. Experience in industry is a plus 5. Experience in eclipse or programming model / architect

10、ure design is a plus-http:/ 竞赛的反响（一例）(19-Feb-2006)IBM 中国研究中心: Business Analysis Optimization Job Requirements:1、PhD M.S. in mathematics, statistics, computer science, industrial engineering management science etc.2、Self-motivated, responsible, able to wk independently under tight deadline willing to

11、 wk under pressure.3、Skill in applied mathematics, including mathematical programming, statistics, data mining, simulation etc.4、Knowledge in supply chain logistics strategy modeling, simulation, planning optimization. 5、Strong interest basic knowledge about industry trends, technologies, solutions

12、in analytics optimization. 6、Experience in ERP/SCM/CRM system SCM consulting practice is a plus. 7、Award in highly regarded mathematical modeling contest is a plus.8、Experience in eclipse, Java, architecture design is a plus.-March 26, 2009, http:/ 就读项目：全日制博士预期学制：4年（以学士学位入学），3年（以硕士学位入学）申请条件：1.平均分(GP

13、A)85分及以上； 2. 托福成绩92 分（internet-based网考）或者 IELTS 7分以上；3. 以下同学可放宽成绩要求：已有国际国内期刊发表论文者；国家或国际数学建模比赛获奖者；ACM程序设计竞赛获奖者；奖学金：Anotehr Example: CityUHK我院参赛成绩计算机学院参赛成绩汇总 奖项 年份 国一国二省一发表论文2009年2212010年2212011年2132012年221201322获奖证书我院参赛成绩2010年，我院参赛学生获得全国大学生数学建模竞赛专科组最高荣誉-高教社杯Thank You！第0章 数字系统第0章 数字系统为什么计算机采用二进制码表示呢？计

14、算机是一个逻辑运算机器。它借助于电子线路的on和off两种状态的组合来表达信息，这两种状态在数学里被解释为1和0。而其它的数、文字、或字符都要通过这两个数字进行相应的编码，才能被计算机理解。因此，以0和1为代码的二进制是计算机技术的数学基础。疑 问 0.1 数的进制三个基本概念数码：一组用来表示某种数制的符号。如1、2、A、B等。基数：数制所用的数码个数，用R表示，称R进制，逢R进一。位权：数码在不同位置上的权值。如十进制的个位位权是1，百位位权是100。十进制基数为10，数码为：0，1，2，3，4，5，6，7，8，9987.65=910281017100610-1510-29 8 7 . 6

15、 510210110010-110-2位权0.1数的进制 二进制数是以2为基数，以0、1作数码，按逢二进一规则来计数。 二进制数整数部分各数位的位权是：2i（i为整数部分的位数），小数部分各数位的位权是：2-j（j为小数部分的位数），如图所示。1 1 0 . 0 12221202-12-2数各数位的位权0.1 数的进制八进制数是以8为基数，以0、1、2、3、4、5、6、7作数字符号，按逢八进一规则来计数。 八进制数整数部分各数位的位权是：8i（i为整数部分的位数），小数部分各数位的位权是：8-j（j为小数部分的位数），如图所示。7 6 5 . 4 38281808-18-2数各数位的位权0.1

16、 数的进制 十六进制数是以16为基数，以0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F作数字符号，按逢十六进一规则来计数。 十六进制数整数部分各数位的位权是：16i（i为整数部分的位数），小数部分各数位的位权是：16-j（j为小数部分的位数），如图所示。1 A 5 . F 416216116016-116-2数各数位的位权0.1 数的进制数制系统的表示比如，101101在十进制中表示某个数，在二进制中则表示完全不同的另一个数。通常情况下，读者能从上下文知道所用的是什么数制。但是，如果我们要完全地明确表示一个数，就把基数作为下标来标记所用的数制系统十进制用下标10，二进制用下标2

17、，等等。例如，二进制的101101用1011012来表示，十进制的101101用10110110来表示。0.1 数的进制课堂练习：口答课本P6习题0.1的第6、7题0.1 数的进制2进制与10进制之间转换二进制数转换成十进制数：只需将二进制数的每一位乘上其对应的权值后累加起来即可。例如：(101.01)2= 12202112002 -112-2 =(5.25)10十进制数转换成二进制数：整数部分除以二取余法，小数部分乘二取整法。0.1 数的进制例：十进制数(25)10 转换成二进制数的转换过程：(25)10=K4K3K2K1K0 =(11001)220 余1 K022512 余0 K126 余

18、0 K2 余1 K321 余1 K4二进制整数部份高位二进制整数部份低位23例：将十进制数(14.125)10转换为二进制数。整数部分转换如下：142 7223 120余数111二进制整数部份低位二进制整数部份高位整数部份结果: 11100十进制小数转换成二进制小数：纯小数转换，采用基数连乘法。方法如下：（1）将十进制小数乘以 2 ，记下整数部分。 （2）将上一步乘积中的小数部分再乘以 2，记下整数部分。 （3）重复（2），直到小数部分为 0 , 或者满足精度要求为止。 （4）将各步求得的整数转换成 2 进制的数码，并按照和运算过程相同的顺序排列起来，即为所求的2进制小数。小数部分转换如下：0

19、.125 20.250 20.500 21.000整数001 二进制小数首位 二进制整数末尾小数部份结果: . 001(14.125)10结果: (1110.001)20.1 数的进制10进制转化为8进制和16进制，以及8进制和16进制转化为10进制的方法，类似於2进制与10进制之间的转换。可自行参考书上例0.1.4和例 数的进制2进制与8进制之间转换8进制转化为2进制八进制转换为二进制时，只要把每一个八进制数字改写成等值的三位二进制数即可，且保持高低位的次序不变。八进制转换为二进制的关系：（0）8=000 （1）8=001 （2）8=010（3）8=011 （4）8=100 （5）8=101

20、（6）8=110 （7）8=111例 (71.23)8=( 111 001 . 010 011)2 7 1 2 3 =（111001.010011）2 0.1 数的进制2进制与8进制之间转换2进制转化为8进制二进制数转换成八进制数时，整数部分从低位向高位方向每三位用一个等值的八进制数来替换，最后不满三位时，在高位补零凑满三位；小数部分从高位向低位方向每三位用一个等值的八进制数来替换，最后不满三位时，在低位补零凑满三位八进制转换为二进制的关系：例1 ( 1101101110 . 110101)2 =（001 101 101 110 . 110 101）2= (1556.65)8 1 5 5 6

21、6 5例2（1101.01)2=(001 101.010)2=(15.2)8 1 5 20.1 数的进制2进制与16进制之间转换16进制转化为2进制十六进制转换为二进制时，只要把每一个十六进制数字改写成等值的四位二进制数即可，且保持高低位的次序不变。十六进制转换为二进制的关系：(0)16=0000 (1)16=0001 (2)16=0010 (3)16=0011(4)16=0100 (5)16=0101 (6)16=0110 (7)16=0111(8)16=1000 (9)16=1001 (A)16=1010 (B)16=1011(C)16=1100 (D)16=1101 (E)16=1110

22、 (F)16=1111例 (2C1.D)16=(0010 1100 0001. 1101)2 2 C 1 D =（1011000001.1101）20.1 数的进制2进制与16进制之间转换2进制转化为16进制二进制数转换成十六进制数时，整数部分从低位向高位方向每四位用一个等值的十六进制数来替换，最后不满四位时，在高位补零凑满四位；小数部分从高位向低位方向每四位用一个等值的十六进制数来替换，最后不满四位时，在低位补零凑满四位。例3 ( 1101101110.110101)2=(0011 0110 1110.1101 0100)2=（36E.D4)16 3 6 E D 40.1 数的进制课堂练习：

23、完成课本P7习题0.1的1，2，40.1 数的进制-数制加法运算十进制数相加的方法也可以用于二进制数相加把二进制数10011011和1001011相加。课堂练习：首先阅读例0.1.6，然后完成课本P6习题0.1的第3，5，8题Thank You！第1章 集合与关系广东科学技术职业学院计算机学院Septemper 20141.1 集合 集合与函数的概念对应用数学来说是最基本的。所有的数学，以及依赖于数学的计算机科学（如程序设计、数据结构、数据库和软件工程等课程）都要使用这些基本概念。本章主要讲述集合、关系、关系数据库和函数等知识501.1 集合集合的朴素定义：集合是一组无序的对象这一定义是德国数

24、学家康托尔於1895年首先给出的。由这一朴素定义得出的理论导致出悖论，在1902年英国数学家罗素提出的，罗素悖论可以简单描述为：我只给所有不给自己刮胡须的男人刮胡须，我也只给这些人刮脸。康托尔(1845-1918)，出身於俄罗斯的圣彼得堡，1862年入苏黎世大学学工,翌年转入柏林大学攻读数学和神学，受教于库默尔（Kummer）、维尔斯特拉斯（Weierstrass）和克罗内克(Kronecker)。1867获博士学位。1869年康托尔获得哈雷大学任教资格，并在那里一直工作到去世。康托尔1874年结婚，有5个子女。他忧郁的气质和妻子的乐观性情相互平衡。尽管他从父亲那里得到大笔遗产，但作为教授的收

25、入却很少，为此他曾试图得到柏林大学一个待遇更高的位置，对他的这一任命被Kronecker阻止了，因为Kronecker不同意康托尔集合论的观点。由于学术观点上受到的沉重打击，使康托尔曾一度患精神分裂症，虽在1887年恢复了健康，继续工作，但晚年一直病魔缠身。1918年1月6日在德国哈雷（Halle）-维滕贝格大学附属精神病院去世。罗素(1872-1970)：罗素生于一个以积极参与进步运动，热烈投身自由事业而闻名的英格兰家庭。年幼时成为孤儿的罗素由祖父母抚养，并在家里接受教育。1890年他进入剑桥的Trinity学院学习数学与伦理学。他在几何学基础方面的工作为他赢得一个研究员职位。1910年Tr

26、inity学院任命他教授逻辑和数学原理的课程罗素毕生为进步事业而战斗。他有强烈的和平主义观点，他对第一次世界大战的抗议使他失去了Trinity学院的位置。由于一篇被认为具有煽动性的文章使他在1918年被囚禁6个月。罗素还为英国妇女的选举权而斗争。1961年在他89岁高龄时第二次入狱，原因是加入呼吁核裁军的抗议活动。罗素最伟大的工作是他提出的可以作为所有数学学科基础的原理。他与怀特海合著的数学原理对逻辑学、数学、集合论、语言学和分析哲学有着巨大影响。1950年，罗素获得诺贝尔文学奖，以表彰其“多样且重要的作品，持续不断的追求人道主义理想和思想自由”。引言 计算机中的数据类型就是建立在集合概念之上

27、的。其中的结构体类型就是编程者自己根据实际需要使用基本的数据类型而构造的一种新的数据类型。这种类型能把多个不同类型的信息作为一个整体。 struct my_struct char name20； int age; float height; float weight; my_friend; 这里关键字struct声明了一个结构my_struct，它是一个存放着字符型、整型、浮点型的不同数据的集合引言 在C语言中，下面程序用来求出6个数中的最小值。 #include main() int s6,min,i;printf(input 6 numbers:n);for(i=0;i6;i+) scan

28、f(%d,&si);min=s0;for(i=0;isi) min=si;printf(min=%dn,min);其中的主函数main()就是一个由具有不同功能的句子所组成的集合。1.1 集合（温故）关于集合，下面的知识你懂的1、集合的概念、组成集合元素的特点；2、集合的表示；3、特殊集合：空集、常用数集 R Z N Q C4、集合与元素关系 5、集合与集合的关系：6、集合运算：交集、并集、补集1.1 集合（知新）幂集课堂练习1、口答完成课本P18页习题1.1的4，7，82、上黑板完成课本P18页习题1.1的1，53、思考完成课本P19页习题1.1的91.1 集合-划分集合的划分是集合中元素之

29、间的一种分类。在信息科学中，对知识库分类就是集合的一种划分。集合X的一个划分是把集合X分成互不重叠的一些子集。一般地，一个集合X的若干个非空子集组成的集合S，如果X的每个元素都属于且只属于S中的某一个元素，就称S为X的一个划分。注意，如果S是X的一个划分，则S必定是两两不相交的，且S=X。简而言之：1、互斥原则2、穷尽原则课堂练习1、完成习题1.1的3一组元素的次序有时往往是重要的。一个由两个元素组成的有序偶（或序偶），写为（a,b）。这与另一个序偶（b,a）是不同的，除非a=b。用另一种形式可表示为（a,b）=（c,d）当且仅当a=c，b=d。比如，平面直角坐标系中任意一点可用二元有序数组（

30、x,y）来表示；空间直角坐标系中任意一点用三元有序数组（x,y,z）来表示。 笛卡尔集：如果X和Y是集合，令XY表示序偶（x,y）的集合，我们把XY称为X和Y的笛卡儿积。即 1.1 集合-笛卡尔集例1.1.13 P17 请自行阅读P17例1.1.14n元序组课堂练习1、完成习题1.1的21.1 集合-集合运算律 P16你是否观察到，除了对合律，其它集合运算律都是成对 出现的，这种特性称为对偶性，只要将 和 ， 和U对换，一个公式就变成了它的对偶式。公式对偶性在命题逻辑的运算律中还会出现。有了集合的运算律，我们可以很方便地利用运算律对复 杂的集合运算进行化简和推导例： 试证明 证明： 1.2 关

31、系 每天我们都要涉及各种关系。例如，雇员与其工资之间的关系，一个商行与它的电话号码之间的关系。关系这个概念对今后学习数据结构和数据库都很重要。目前最常用的数据库Oracle、SQL Server、DB2都是关系型数据库系统，数据库中常见的分类、排序，实质上是关系的应用。在信息科学中二元关系以及以此为基础的关系代数是关系数据库的基础。关系的表示列表 一般地，关系可以想象成一个列表，表1.2.1说明了一些学生与一些课程的关系。 关系的表示集合表1.2.1，学生若选了某课程，用关系术语就说，学生与这门课程有关系，在数学上用序偶表示，如（比尔，计算机）、（玛丽，数学），因此，我们把关系定义为序偶的集合

32、。定义1.2.1 设X和Y是集合，一个从X到Y的二元关系R是笛卡儿积XY的一个子集。用记号xRy表示（x,y） R。而当（x,y） R时，我们也说x与y有关系R。 也就是说，一个从X到Y的二元关系是有序对的集合R，其中每个有序对的第一个元素取自X，第二个元素取自Y。例1.2.2 令X = 比尔，玛丽，贝思，戴夫 Y = 计算机，数学，艺术，历史表1.2.1所表示的关系R可以写为 R=（比尔,计算机),（玛丽,数学),（比尔,艺术）,(贝思，历史）,(贝思，计算机),(戴夫，数学）（贝思，历史） R，我们可写为：贝思R历史，它表示贝思选修历史课。R的定义域是X（表中的第一列），值域是Y（表中的第

33、二列）。 一个关系可以由简单地列出那些属于它的序偶而给出。下一个例子表明，关系也可以由给出规则的方法来定义。例1.2.3 令X=2，3，4 和 Y=3，4，5，6，7我们定义一个从X到Y 的关系R如下： 如果x整除y，则（x,y） R根据R的定义，我们可以写出R中的有序,得到 R = （2,4），（2,6），（3,3），（3,6），(4,4)把关系R写成列表的形式，可以得到表1.2.2R的定义域是2,3,4，值域是3,4,6。此例中的关系有时也写成R = （x，y）| x整除y，x X，y Y。阅读 P21 例1.2.4关系的表示关系图某个集合上的关系可以表示成一个有向图（也称关系图）。 先画

34、出顶点（或结点），表示X的元素，然后，如果元素（x,y）在关系R中，我们就画一条从x到y的有向边（带箭头的线）。一个关系中的形如（x,x）的元素，对应着一个从x到x的有向边。这样的有向边也称为一个环。右图表示关系R=1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4）例1.2.5 在集合X=a，b，c，d上定义一个关系R： R=（a,a）,（b,c）,（c,b）,（d,d）此关系可以用如下的关系图表示出来，如下图所示。课堂练习P28 习题1.2 的1,2,3,4关系的特殊性质偏序关系定义1.2.19 集合X上的关系R，如果它是自反

35、的，反对称的和传递的，则R称为一个偏序关系。提问：判断下列关系是不是偏序关系？（1）正整数集Z+上的整除关系：（2）实数集R上的大于或小于关系；（3）集合X的幂集上的包含关系 如果R是集合X上的一个偏序关系，我们就用符号xy来表示（x，y） R或xRy。它只是意味着，集合X中的元素的一种次序。对于x，y X，如果有x y，或者y x成立，就说x和y是可比的。如果既没有x y，也没有y x，就说x和y是不可比的。全序关系定义1.2.23 假设R是集合X上的一个偏序关系，如果X中的任何一对元素x、y都是可比的，也就是说，有xRy或者yRx，二者必有其一，此时称R是全序关系，集合X称为全序集。提问：

36、判断下列说法是否正确（1）正整数集Z+上的“小于等于”关系是偏序关系也是全序关系。（2）正整数集Z+上的“整除”关系是偏序关不是全序关系；课题练习：习题1.2 P29的7，8关系运算关系是以有序对为元素的集合，所以它可以进行集合的一般运算，也可以进行“新”运算。 P27 例1.2.26设A=1，2，3，B=1，2，3，4，从A到B的关系R1=（1，1），（2，2），（3，3）和关系R2=（1，1），（1，2），（1，3），（1，4），那么R1R2 =（1，1），（2，2），（3，3），（1，2），（1，3），（1，4）R1R2 =（1，1）R1R2 =（2，2），（3，3）它们定义了从A到B的

37、另一些关系。关系的运算逆关系定义1.2.24 令R是从X到Y的关系。R的逆关系表示为R-1，是由下式定义的从Y到X的关系 R-1 = （y，x）|（x，y）RP26 例1.2.25 关系R= （2，4），（2，6），（3，3），（3，6），（4，4）的逆关系是 R-1 = （4,2），（6,2），（3,3），（6,3），（4,4）关系的运算复合关系定义1.2.27 令R1是一个从X到Y的关系，R2是从Y到Z的关系，关系R1和R2复合表示为R2 R1，是一个由下式定义的从X到Z的关系： R2R1=（x，z）| 存在y, 使得（x,y）R1且（y,z） R2 此处要注意这两个关系的先后次序，R2R

38、1表示先R后R2。R2R1 的有序对(x,z)是由(x,y),(y,z)通过中间元素y“结合”而成的。阅读P27例1.2.28，例1.2.29（关系的幂运算）课堂练习：P29 习题1.2的6,9,111.3 等价关系生活中常常对事物进行分类，如垃圾分类、图书分类。通过分类便于认识和管理事物。集合划分是集合元素之间的一种分类，什么情况下集合元素可以分类？如何分类呢？定义1.3.1 集合X上的一个关系R，如果它是自反的、对称的和传递的，称R为集合X上的一个等价关系。提问：判断下列关系是否等价关系（1）一个班级上的“同乡”关系（2）正整数集上的“整除”关系。（3）正整数集上的“同奇偶性”关系例1.3

39、.3 考虑在集合X=1，2，3，4，5上的关系 R=（1，1），（1，3），（1，5），（2，2），（2，4），（3，1），（3，3），（3，5） （4，2），（4，4），（5，1），（5，3），（5，5），画出R的关系图，根据关系图判断R是不是等价关系。图？从关系图看到，R满足自反性、对称性、传递性，所以R是等价关系。并且集合X的元素按照关系R分成了2,4,1,3,5两类，称为等价类。等价类定义1.3.8 令R是集合X上的一个等价关系。 X，由X中与元素a具有等价关系R的全体元素组成的X的子集a，称为由关系R确定的a的等价类。阅读P33 例1.3.10，例1.3.11（恒等关系），例1.3.

40、12（同余关系）反过来，由等价类可以确定等价关系定理1.3.15 令S= T1，T2，Tn 是集合X的一个划分，在集合X上定义关系：xRy表示x、y同时属于某一个Ti，则关系R是等价关系。定理1.3.15告诉我们，划分和等价关系是同一个硬币的两面。一方面，集合X的每一个划分以一种自然方式确定了X上的一个等价关系；另一方面，每个非空集合X上的等价关系以同样一种自然方式确定了一个X的划分。例1.3.16 考虑集合X = 1，2，3，4，5，6上的一个划分S = 1,3,5 , 2,6 ，4 由定理1.3.15可知，X上的划分S确定一个等价关系R。根据等价关系的定义，等价类2,6包含着序偶（2,2）

41、，（2,6），（6,2），（6,6），同理可写出等价类1,3,5和4包含的序偶。从而，等价关系 R=（1,1,），（1,3），（1,5），（3,1,），（3,3），（3,5），（5,1），（5,3），（5,5），（2,2），（2,6），（6,2），（6,6），（4,4）课堂练习：P37习题1.3的1,6（判断等价关系），3（求等价类）,8，2（求等价关系）课堂练习P37习题1.3判断等价关系：1,6求等价类：3求等价关系：8划分、等价关系、等价类概念之间关系如果R是集合X的一个等价关系，则等价类是集合X的一个划分。1.4 关系矩阵关系的表示常用列表、有序对、关系图，再介绍一种表示从X到Y的关系

42、的便利方法关系矩阵。它是01矩阵（后面第3章介绍矩阵的相关知识）。计算机可以用这种方法来对一个关系进行分析。我们用X中元素来标记行（以任意的次序），用Y中元素来标记列（也是任意的次序）。如果有x R y , 我们就令x行y列的元素之值为1，否则，其值为0。这个矩阵就称为关系R的矩阵（与X和Y的次序对应），简称关系矩阵。阅读P38 例1.4.1，例1.4.2，例1.4.3关系矩阵特征满足自反性、对称性、反对称性的关系R，其关系矩阵特征阅读P39(1)(2)(3)课堂练习：P40习题1.4的1,2,3关系矩阵的关系运算关系复合关系矩阵相乘例1.4.6 令R1是从X = 1,2,3 到Y = a,b

43、的关系，定义为： R1=(1, a), (2,b), (3, a), (3,b) 令R2是从Y到Z=x , y , z的关系，定义为： R2=（a，x），（a,y）, (b,y) , (b,z) 则R1与R2的复合是R2R1=(1, x),(1,y), (2,y),(2,z), (3, x),(3,y), (3,z) 而R1对应于次序1,2,3和a，b的关系矩阵是： A1 R2的对应于次序a，b和x,y,z的关系矩阵是： A2 两个矩阵相乘得：再将矩阵之积A1 A2 中，非0元素用1代替定理1.4.7 令R1是从X到Y的关系，R2是从Y到Z的关系。选择好X,Y和Z的次序，所有的关系矩阵都是与这

44、个次序相对应的。令R1的关系矩阵是A1，R2的关系矩阵是A2。则R2R1的关系矩阵是：在矩阵之积A1A2中，把非0项用1代替而得的矩阵。课堂练习：P41习题1.4的4,5,6,8,7 1.5 关系数据库比较流行的数据模型有三种：层次模型、网状模型、关系模型。应用最广泛的为关系模型。关系数据模型的基本结构是表（Table)，由行和列组成，表又称为关系(Relation，)。关系数据库中的几个名词，在不同领域有不同称谓：列、行、二维表属于日常用语；属性、元组、关系属于数学用语；字段、记录、数据库是数据库领域用语。如果一个表有n列，其对应的关系就称为n元关系。表1.5.1表示一个4元关系字段、记录、

45、数据库字段：表格的每一列称为一个字段（属性），字段名相当标题栏中的标题。表1.5.1包含了4个字段（属性）：ID号、姓名、位置、年龄。表的每一列数据都属于同一类型。记录：表格中的每一行称为一条记录（元组），记录是由若干相关的属性组成。如表1.5.1的第一条记录是(22012,Johnson,捕手,22)，表中每条记录是4元组。数据库：由相互关联的数据表组成，它可以是一个文件，也可以由若干文件，按照一定法则组织而成。数据库管理系统则是一些程序，它能帮助用户访问数据库中的信息。由E.F.科德（Codd）在1970年提出的关系数据库模型，就是基于n元关系的概念。表1.5.1所表示的关系可以表示为4元

46、组的集合。（22012，Johnson，捕手，22），（93831，Glover，外场，24）， （58199，Battery，投手，18），（84341，Cage，捕手，30）， （01180，Homer，一垒，37)，（26710，Score，投手，22）， （61049，Johnson, 外场，30），（39826，Singleton，二垒，31）关系模型特点关系模型的特点是：1、每一列是基本数据，不能再分解；2、表中每一列必须是相同数据类型（如字符型、数值型）；3、每一列的名字必须唯一；4、表中不能有内容完全相同的行；5、行的顺序、列的顺序不影响表所表示对的信息的含义关键字主键(Key

47、)关键字是指表中的某一列，该列的值能唯一的标识一行。如表1.5.1的4个属性：ID号、姓名、位置，年龄，只有ID号字段为关键字，因为每个人的ID号是唯一的，即对于表中的每一条记录，ID号的值是唯一的。在绝大多数情况下，姓名字段都是不能设定为关键字的，因为不同的人可以有相同的姓名。同理，我们也不能把位置或年龄作为关键字。关键字可以由多个字段构成。在表1.5.1中，姓名和位置的联合可以作为关键字，因为一个运动员可以唯一地由姓名和位置来确定。数据库的基本操作运算计算机系统可以把大量的信息存放在数据库中。人们可以对数据进行各种操作，比如，一个数据库管理系统要执行查询、插入、删除，以及从一些重叠的数据库

48、中组合记录的操作。在例1.5.1中，“找出所有的外场手”就是一个有意义的关系查询。下面我们讨论对关系的基本操作运算。选择：选择操作符Sc是从n元关系中选择符合给定条件c的某些n元组构成新的n元关系。投影：投影操作符P（i1，i2，im)将n元组（a1，a2，an）映射为m元组（ai1，ai2，aim）。也就是在n元组的关系中选择符合给定条件的那些列i1，i2，im构成一个m元新关系。连接：选择和投影操作通常用来处理单个的关系。而连接运算J用于处理两个关系，它从两个关系中产生一个新关系。阅读P43例1.5.2（选择）阅读P43例1.5.3（投影）阅读P44例1.5.4（连接）从例中看到，选择运算

49、的结果是一个表的水平方向的子集，此处的选择操作符：运动员位置=捕手。投影运算的结果是一个表的垂直方向的子集，例中投影操作符：运动员姓名，位置。连接运算首先将关系R,S形成笛卡尔积RS，然后根据连接条件，从RS中选出某些元组，最后对选择的元组进行投影操作，消除重复列和多余字段列。例中连接操作符：运动员ID号=PID分配。数据库查询的综合操作：阅读P45例1.5.5，例1.5.6课堂练习：P46习题1.5的1,21.6 函数函数广泛存在于数学和计算机科学之中，虽它们对函数定义的表述不同，但本质上都是由输入、输出、对应关系（算法）三部分组成，是一系列有序对，即满足特定条件的一种关系。C语言中，将输入

50、与输出之间的关系看成是一种函数关系。定义1.6.1 设R是集合A到集合B的一个关系，对于任意的xA ，存在唯一的y B，使得(x,y) R，则称关系R为集合A到集合B的函数。此处的定义与我们中学数学里的函数定义是一致的：对每一个x，通过规则f，都有唯一确定的y与之对应，我们就说y是x的函数，记为y = f(x)。有时候，我们把f(x)称为x的像，x称为f(x)的原像。单射、满射、双射在数学里，函数符号通常用一个英文字母f、g、h或希腊字母表示。但在计算机科学里，函数的符号可根据具体情况选用不同的字符，如max、min、average、delete_string等。函数和关系两个概念的区别：阅读

51、P49例1.6.3，例1.6.4，例1.6.5变量之间的对应可分为：一对一，多对一，一对多，其中哪种对应方式构成函数？在函数f:X Y上,其对应可分为：单射、满射、双射。阅读P49定义1.6.6P50例定义1.6.11函数运算反函数、复合函数由于函数是特殊类型的关系，类似于关系的逆、关系的复合，我们可以定义反函数、函数的复合。函数二元运算、一元运算课堂练习：P53习题1.6的1,3函数运算取整函数递归定义我们常说的“知道他的过去，就知道他的现在；知道他的过去和现在，就可知道他的将来”，正是体现了递归的思想。一般地，如果一个问题可以归结到其前面的一个问题或几个问题，这就是递归问题。有些数学教材上

52、把递归又称为递推。递归地定义非负整数集上的函数，要使用两个步骤：基础步骤：规定这个函数在0处的值。（已解决的基础问题）递归步骤：给出从较小整数的值来求当前值的规则。(自身调用语句）如在求阶乘n!运算中,已解决的基础问题是0!=1，自身调用语句（递归算法）为：n!=(n-1)! n下函数取整(floor)、上取整函数(ceiling)定义1.6.21 X的下取整函数（floor function），表为 ，是小于或等于的最大整数。的上取整函数(ceiling function)，表为 ，是大于或等于的最小整数。阅读P52例1.6.22，例1,6,23，例1.6.24，例1.6.25课堂练习： P

53、53习题1.6的9Thank You！第3章 算法基础学习算法的重要性 数学中有很多重要的思想，比如算法思想和化归思想，它们在解决一般的问题时也很有用。其中的算法思想在计算机科学中更是十分重要。所谓算法就是按部就班地解决某个问题的方法和步骤。 随着人们对计算机兴趣的增长，算法的概念有了更广泛的含义，不仅包含做算术的过程，而且包含所有确定的解题过程。本章介绍算法的概念及其表示方法，在此基础上讨论几个常见的算法，如欧氏算法、搜索和排序、整数运算、以及递归算法等。本章内容3.1 算法的概念3.2 算法的表示 3.3 欧几里德算法 3.4 搜索与排序3.5 整数运算算法3.6 矩阵运算3.7 递归算法

54、 3.1 算法的概念1、引例 例3.1.1下面的罗杰斯烹饪鲤鱼的步骤就给我们提供了一个算法的范例：(1)取一条斤重的鲤鱼，并把它放在清水里游上6小时；(2)刮鱼鳞去骨切片；(3)给鱼涂上黄油，并撒上盐和胡椒；(4)把鱼片放在烤炉里用温火烘烤25分钟；(5)取出并享用。3.1 算法的概念2、算法 算法：由给定的一些数据，按照某种规定的顺序进行运算的一个运算序列，称为算法。一个算法就是一组有限的指令序列，其中每一条指令表示一个或多个操作。3.1 算法的概念3、算法的特征输 入：算法从某个特定对象的集合得到输入值。 输 出：对每个输入值集合，算法都能从一个指定的集合中给出输出值。输出值就是问题的解。

55、 确定性：每一条指令必须有确切的含义，不能产生二义性。在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。3.1 算法的概念3、算法的特征 唯一性：每一步执行后所得到的中间结果是唯一的，且仅依赖于输入和先前步骤的结果。 有穷性：任何算法都会在有限条指令执行完毕后结束，且每一步都可在有穷时间内完成。 通用性：算法过程可以应用于一类问题，而不只是用于特定的输入值。3.1 算法的概念3、算法的特征例3.1.2 求a、b、c三个数中的最大值 考虑如下算法： 1. x：=a 2. if bx then x：=b 3. if cx then x：=c分析该算法的执行过程，是否具有

56、算法的几条性质？3.1 算法的概念4、算法的选择标准空间复杂度时间复杂度算法复杂度3.1 算法的概念4、算法的选择标准例3.1.3对于下面的程序段，写出表示语句x:=x+1执行次数的式子。 1. x=0 2. for i=1 to n do 3. for j=1 to i do 4. x:=x+13.1 算法的概念4、算法的选择标准例3.1.4计算多项式Pn(x)=an xnan-1 xn-1a1 xa0在x=t时的值。解法1： 如果直接计算每一项再求和，显然，计算an xn需要作n次乘法，因此，计算Pn(x)的值就需要作n(n-1)21= n(n+1)/2次乘法及n次加法运算。3.1 算法的

57、概念4、算法的选择标准根据Pn(x)= Pn-1(x) an xn可写出如下伪代码。procedure poly(a,n,t)s:= a0for i:=1 to ns:=san tn end解法二，解法三参见课本从此例可以看出不同算法的复杂度不同3.1 算法的概念5、算法的三种基本结构顺序结构选择结构循环结构流程图表示法常用图例 3.1 算法的概念5、算法的三种基本结构3.1 算法的概念5、算法的三种基本结构3.1 算法的概念5、算法的三种基本结构3.1 算法的概念5、算法的三种基本结构作业P118 习题3.13.2算法的表示 算法可以用自然语言、传统流程图、N-S流程图、伪码、计算机语言等不

58、同方法来表示。除了强调语句的精确的语法，本书都用伪码描述算法3.2算法的表示例子引例：查找几个数中最大值的算法就可以直接用中文描述。具体的步骤是：1、设临时最大值等于序列中的第一个整数。2、将序列中的下一个整数与临时最大值比较，如果这个数大于临时最大值，置临时最大值为这个整数3、如果序列中还有其它的整数，重复前一步骤。4、当序列中没有留下可比的整数时停止，此刻的临时最大值就是序列中的最大整数。3.2算法的表示例子对应的伪码Procedure max(s1，sn，n)max:=s1for i：=2 to n if simax then /发现一个较大的数值 max：= si return（max

59、）分析执行过程3.2算法的表示例子算法3.2.1 找出三个数中的最大值输入：，三个数输出：，中的最大值Procedure max（，）：if bx then /判断b是否大于x，若b大于x，则修改x x：=b3.2算法的表示例子if cx then /判断c是否大于x，若c大于x，则修改x x：=creturn（x）end max分析执行过程，参见课本P120它对应的C+代码如下：#includeint max(int a,int b,int c) /自定义求三个数的最大值的函数max，其中a,b,c是形参。 int t;if(ab) t=a;if(bt) t=b;if(ct) t=c;ret

60、urn t;void main() int s; int a,b,c; scanf(%d%d%d,&a,&b,&c); printf(a=%d,b=%d,c=%dn,a,b,c); s=max(a,b,c); /调用自定义函数，其中a,b,c是实参。 printf(最大数=%dn,s);在if-then结构中 if p then action 如果条件p为真，则执行action，然后把控制权交给action后面的语句；如果条件p为假，则把控制权直接交给action后面的语句。 if-then-else语句是二选一的结构，结构形式为 if p then action 1 else action