09年離散數(shù)學(xué)復(fù)習(xí)大綱

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

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

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

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

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