09年離散數(shù)學復習大綱

1、2009年離散數(shù)學課程復習大綱離散數(shù)學雖然是近幾十年來產(chǎn)生出的一門新課，就其數(shù)學內(nèi)容來說卻不是新的，有些內(nèi)容甚至是很古典的。隨著計算機科學的發(fā)展和計算機應用領域的日益廣泛，迫切需要適當?shù)臄?shù)學工具來解決計算機科學各個領域中提出的有關離散量的理論問題，離散數(shù)學就是適應這種需要而建立的，它綜合了計算機科學中所用到的研究離散量的各個數(shù)學課題，并進行系統(tǒng)、全面的論述，從而為研究計算機科學及相關學科提供了有利的理論基礎和工具。一、總則1、本課程的教學目的和要求： 離散數(shù)學是計算機科學及相關學科的一門非常重要的專業(yè)基礎課。教學的目的是培養(yǎng)學生的數(shù)學思維能力，通過教學，最終使學生能夠在眾多的概念中要找出最重要

2、的，在眾多的定理中找出最根本的，將這些少量的概念和定理能夠透徹地理解，自如地運用，就達到了掌握離散數(shù)學的教學要求。2、本課程的主要內(nèi)容： 樸素集合論、古典數(shù)理邏輯、圖論、組合數(shù)學基礎、初等數(shù)論、離散概率、抽象代數(shù)學（包括群、環(huán)、域、格、布爾代數(shù)）。3、考核重點與難點： 離散數(shù)學包含的數(shù)學內(nèi)容非常多，這些數(shù)學內(nèi)容彼此間的獨立性很強，每一個內(nèi)容都可以作為一門課單獨講授，而在一個學期里講授離散數(shù)學這門課，就只能講授各個內(nèi)容的最基本的知識，為學生今后進一步學習打下基礎。因此，教師在認真講解基本概念和知識外，更重要的是培養(yǎng)學生的數(shù)學思維能力，決不能將離散數(shù)學講成數(shù)學，這就是離散數(shù)學教學的重點，同時也是離

3、散數(shù)學教學的難點。4、本課程的知識范圍及相關課程的關系： 離散數(shù)學涉及的數(shù)學領域非常廣，同時與計算機科學和相關學科關系非常密切，是很多計算機有關課程的基礎，如：高級語言、數(shù)據(jù)結構、編譯原理、操作系統(tǒng)、可計算性理論、人工智能、形式語言與自動機、信息管理與檢索以及開關理論等，離散數(shù)學也是研究自動控制、管理科學、電子工程等的重要工具。5、教材的選用：屈婉玲、耿素云等編著離散數(shù)學普通高等教育“十一五”國家級規(guī)劃教材，高等教育出版社。屈婉玲、耿素云等編著離散數(shù)學（第2版）21世紀大學本科計算機專業(yè)系列教材，清華大學出版社。二、課程內(nèi)容第一部分 數(shù)理邏輯1、考核內(nèi)容：命題及表示、命題公式與翻譯、真值表與等

4、價公式、重言式與蘊涵式、其他聯(lián)結詞、對偶與范式、推理理論。一階邏輯的概念與表示、一階邏輯公式與翻譯、變量的約束、一階邏輯的等值式、前束范式。2、考核重點：命題邏輯中的基本概念和基本推理方法。變量的約束和前束范式。第二部分 集合論1、考核內(nèi)容：集合的概念與表示、集合的運算。序偶與笛卡爾積、關系及表示、關系的性質、復合關系和逆關系、關系的閉包運算、等價關系與等價類、偏序關系與哈斯圖。函數(shù)的概念、逆函數(shù)和復合函數(shù)。2、考核重點： 集合的基本概念和基本運算。關系的閉包運算、等價關系、等價類、偏序關系與哈斯圖。逆函數(shù)和復合函數(shù)。第三部分 代數(shù)結構1、考核內(nèi)容： 代數(shù)系統(tǒng)的引入、運算及性質，群和子群的定義

5、與判定定理，群的陪集分解、循環(huán)群與置換群，格與布爾代數(shù)。2、考核重點： 代數(shù)系統(tǒng)的運算與性質，子群的定義與判定定理，循環(huán)群的計算，幾類格的定義。第四部分 組合數(shù)學1、 考核內(nèi)容：基本計數(shù)規(guī)則、排列與組合、二項式定理與組合恒等式。2、 考核重點：排列與組合、二項式定理。第五部分 圖論1、考核內(nèi)容： 圖的基本概念、歐拉圖與漢密爾頓圖、平面圖、對偶圖。2、考核重點： 圖的基本術語，以及圖的相關定理的應用，平面圖、對偶圖等的定義和平面圖的判定。第六部分 初等數(shù)論1、 考核內(nèi)容：素數(shù)、最大公約數(shù)與最小公倍數(shù)、同余、一次同余方程與密碼學。2、 考核重點：素數(shù)、一次同余方程與RSA公鑰密碼。第七部分 離散概率1、考核內(nèi)容：隨即事件與概率、事件的運算、條件概率與獨立性、離散型隨機變量及其分布律、數(shù)學期望、方差。2、考核重點： 事件的運算、離散型隨機變量數(shù)學期望、方差。三、考試題型(一) 填空題例如：設全集E=a,b,c,d,e,A=a,b,c,B=a,d,e,則 AB= , AB=_, A-B=_,AB=_。 答案；，（二）計算題例如：設集合Aa，