離散數(shù)學(xué)

前言

　　現(xiàn)代社會(huì)與計(jì)算機(jī)日益密切地融合，而數(shù)字計(jì)算機(jī)本質(zhì)上是一種“離散”的機(jī)器，并越來(lái)越多地用于處理離散的對(duì)象，從而使“離散數(shù)學(xué)”成為計(jì)算機(jī)科學(xué)不可或缺的理論基礎(chǔ)和工具，并推動(dòng)離散數(shù)學(xué)本身進(jìn)一步發(fā)展和豐富。作為計(jì)算機(jī)專業(yè)最重要的必修課程之一，近年來(lái)離散數(shù)學(xué)越來(lái)越受到重視，它不僅是學(xué)習(xí)后繼課程的基礎(chǔ)，更是培養(yǎng)學(xué)生的思維、提高分析問(wèn)題和解決問(wèn)題的能力的重要途徑?！　”緯?shū)第一版成書(shū)于1985年，11年后，為了適應(yīng)計(jì)算機(jī)學(xué)科的迅速發(fā)展作了一次修訂。如今，距第二版成書(shū)又過(guò)去了13年。期間，不僅計(jì)算機(jī)學(xué)科本身又有了許多重大進(jìn)展，而且目前的社會(huì)環(huán)境、高校和學(xué)生的情況都與以往大不一樣。正是基于這樣的背景，我們對(duì)第二版再次作了全面修訂，以適應(yīng)學(xué)科的發(fā)展和教學(xué)的需要?！　〉谌娴膬?nèi)容組織主要依據(jù)教育部計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)教學(xué)指導(dǎo)分委員會(huì)制定的《高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)發(fā)展戰(zhàn)略研究報(bào)告暨專業(yè)規(guī)范》，并參考了美國(guó)計(jì)算機(jī)學(xué)會(huì)ACM的Computing Curricula 2005。與第二版相比較，第三版的涵蓋面有所擴(kuò)大，增加了初等數(shù)論、組合數(shù)學(xué)等方面的內(nèi)容；與計(jì)算機(jī)科學(xué)的結(jié)合更緊密，增加了離散數(shù)學(xué)應(yīng)用的內(nèi)容；壓縮了某些較抽象、實(shí)際應(yīng)用中較少涉及的內(nèi)容，如集合的基數(shù)等?！　”緯?shū)前兩版的顯著特點(diǎn)是：簡(jiǎn)潔、條理清晰。第三版在保持這兩個(gè)特點(diǎn)的基礎(chǔ)上，把離散數(shù)學(xué)與計(jì)算機(jī)科學(xué)有機(jī)地聯(lián)系起來(lái)，力圖將本教材編寫成“面向計(jì)算機(jī)科學(xué)的”離散數(shù)學(xué)。一方面加強(qiáng)學(xué)生對(duì)基本內(nèi)容的掌握，培養(yǎng)分析問(wèn)題和解決問(wèn)題的能力；另一方面，進(jìn)一步激發(fā)學(xué)生的學(xué)習(xí)興趣。此外，第三版對(duì)學(xué)生的實(shí)際情況也作了充分考慮，對(duì)難點(diǎn)和重點(diǎn)的討論盡可能地做到直觀、循序漸進(jìn)、詳盡，并適當(dāng)?shù)刈髁艘恍W(xué)習(xí)指導(dǎo)。　　第三版包含的內(nèi)容較多，一般需要兩個(gè)學(xué)期才能全部覆蓋。教師可根據(jù)具體的專業(yè)方向、教學(xué)目標(biāo)、學(xué)生的情況等進(jìn)行適當(dāng)組合。本書(shū)在內(nèi)容的組織上已經(jīng)充分考慮到這樣的需要，盡可能地保持各章節(jié)內(nèi)容的自含，以便于取舍。

內(nèi)容概要

　　《離散數(shù)學(xué)（第3版）》前兩版的顯著特點(diǎn)是：簡(jiǎn)潔、條理清晰。第三版在保持這兩個(gè)特點(diǎn)的基礎(chǔ)上，把離散數(shù)學(xué)與計(jì)算機(jī)科學(xué)有機(jī)地聯(lián)系起來(lái)，力圖將本教材編寫成“面向計(jì)算機(jī)科學(xué)的”離散數(shù)學(xué)。一方面加強(qiáng)學(xué)生對(duì)基本內(nèi)容的掌握，培養(yǎng)分析問(wèn)題和解決問(wèn)題的能力；另一方面，進(jìn)一步激發(fā)學(xué)生的學(xué)習(xí)興趣。此外，第三版對(duì)學(xué)生的實(shí)際情況也作了充分考慮，對(duì)難點(diǎn)和重點(diǎn)的討論盡可能地做到直觀、循序漸進(jìn)、詳盡，并適當(dāng)?shù)刈髁艘恍W(xué)習(xí)指導(dǎo)。

書(shū)籍目錄

第一章 集合論1.1 集合的概念和術(shù)語(yǔ)1.1.1 集合的基本概念和表示1.1.2 集合之間的關(guān)系1.1.3 集合簇1.2 集合的運(yùn)算1.2.1 集合的基本運(yùn)算1.2.2 冪集1.2.3 n元組和笛卡兒乘積1.2.4廣義并和廣義交1.3 集合運(yùn)算的性質(zhì)1.3.1 集合恒等式1.3.2 集合演算1.3.3 對(duì)偶原理1.4 有限集合的計(jì)數(shù)1.5 羅素悖論1.6 小結(jié)1.7 習(xí)題第二章 數(shù)論基礎(chǔ)2.1 最大公因數(shù)和最小公倍數(shù)2.1.1 整除、同余、最大公因數(shù)和最小公倍數(shù)2.1.2 歐幾里得算法2.1.3 最大公因數(shù)和最小公倍數(shù)的性質(zhì)2.2 素?cái)?shù)2.2.1 整數(shù)的素分解2.2.2 素性探測(cè)2.3 一次同余方程2.3.1 一次同余方程2.3.2 一次同余方程組2.3 3 大整數(shù)的剩余表示法2.4 RSA公鑰密碼體制2.5 小結(jié)2.6 習(xí)題第三章 命題邏輯3.1 命題和命題公式3.1.1 命題與邏輯聯(lián)結(jié)詞3.1.2 命題公式3.2 等值演算3.2.1 等值的概念3.2.2 等值演算3.2.3 對(duì)偶原理3.3 范式3.3.1 主析取范式3.3.2 主合取范式3.3.3 聯(lián)結(jié)詞的功能完備集3.4 命題邏輯的推理理論3.5 小結(jié)3.6 習(xí)題第四章 一階邏輯4.1 謂詞4.1.1 謂詞和量詞4.1.2 謂詞公式4.2 等值演算和前束范式4.3 一階邏輯的推理理論4.4 小結(jié)4.5 習(xí)題第五章 關(guān)系5.1 關(guān)系的概念5.1.1 二元關(guān)系5.1.2 二元關(guān)系的表示5.1.3 n元關(guān)系5.2 關(guān)系運(yùn)算5.2.1 關(guān)系的基本運(yùn)算5.2.2 關(guān)系運(yùn)算的性質(zhì)5.3 關(guān)系的特殊性質(zhì)及其閉包5.3.1 關(guān)系的特殊性質(zhì)5.3.2 關(guān)系的閉包5.4 等價(jià)關(guān)系和劃分5.4.1 等價(jià)關(guān)系和等價(jià)類5.4.2 劃分和等價(jià)關(guān)系5.5 偏序關(guān)系5.5.1 偏序關(guān)系和偏序集5.5.2 哈斯圖5.5.3 偏序集的性質(zhì)5.5.4 拓?fù)湫蛄?.5.5 格5.6 小結(jié)5.7 習(xí)題第六章 函數(shù)和集合的基數(shù)6.1 函數(shù)的概念和性質(zhì)6.1.1 函數(shù)的基本概念6.1.2 函數(shù)的復(fù)合和逆6.2 集合的基數(shù)6.2.1 集合的等勢(shì)6.2.2 可數(shù)集6.2.3 無(wú)限集和集合的基數(shù)6.3 不可解問(wèn)題6.3.1 不可解問(wèn)題的存在性6.3.2 停機(jī)問(wèn)題6.4 小結(jié)6.5 習(xí)題第七章 圖論基礎(chǔ)7.1 圖及其表示7.1.1 圖的概念7.1.2 圖的矩陣表示7.1.3 幾種特殊的圖7.1.4 子圖和圖運(yùn)算7.2 握手定理7.3 圖的連通性7.3.1 通路和回路7.3.2 圖的連通性7.3.3 矩陣運(yùn)算和連通性7.4 最短通路和Dijkstra算法7.4.1 廣度優(yōu)先搜索算法7.4.2 帶權(quán)圖和Dijkstra算法7.5 頂點(diǎn)著色7.6 圖同構(gòu)7.7 小結(jié)7.8 習(xí)題第八章 具有特殊性質(zhì)的圖8.1 歐拉圖8.1.1 歐拉圖的概念8.1.2 無(wú)向歐拉圖的性質(zhì)8.1.3 有向歐拉圖的性質(zhì)8.2 哈密頓圖8.2.1 哈密頓圖的概念8.2.2 無(wú)向哈密頓圖的性質(zhì)8.2.3 格雷碼8.2.4 競(jìng)賽圖8.3 平面圖8.3.1 平面圖的概念8.3.2 平面圖的性質(zhì)8.4 無(wú)向樹(shù)8.4.1 無(wú)向樹(shù)的概念8.4.2 無(wú)向樹(shù)的基本性質(zhì)8.4.3 求最小生成樹(shù)的Kruskal算法8.5 有向樹(shù)8.5.1 有向樹(shù)和根樹(shù)及其簡(jiǎn)單性質(zhì)8.5.2 求最優(yōu)樹(shù)的Huffman算法8.6 小結(jié)8.7 習(xí)題第九章 基本計(jì)數(shù)方法9.1 鴿籠原理9.2 加法原理與乘法原理9.3 排列與組合9.3.1 排列9.3.2 組合9.4 二項(xiàng)式系數(shù)9.5 可重復(fù)的排列和組合9.5.1 可重復(fù)的排列9.5.2 可重復(fù)的組合9.6 容斥原理9.7 生成排列和組合9.7.1 生成排列9.7.2 生成組合9.9 習(xí)題第十章 遞推關(guān)系和生成函數(shù)10.1 遞推關(guān)系10.2 常系數(shù)線性遞推關(guān)系10.2.1 求解常系數(shù)線性齊次遞推關(guān)系10.2.2 求解常系數(shù)線性非齊次遞推關(guān)系10.3 生成函數(shù)10.3.1 冪級(jí)數(shù)型生成函數(shù)10.3.2 指數(shù)型生成函數(shù)10.4 生成函數(shù)應(yīng)用舉例10.5 小結(jié)10.6 習(xí)題第十一章 代數(shù)結(jié)構(gòu)基礎(chǔ)11.1 代數(shù)系統(tǒng)11.2 二元運(yùn)算的性質(zhì)11.3 半群和獨(dú)異點(diǎn)11.4 同態(tài)和同構(gòu)11.5 小結(jié)11.6 習(xí)題第十二章 群12.1 群12.2 子群12.2.1 子群12.2.2 元素的階12.3 循環(huán)群和群的直積12.3.1 循環(huán)群12.3.2 群的直積12.4 陪集和正規(guī)子群12.5 群同態(tài)12.6 變換群和置換群12.7 群碼12.7.1 糾錯(cuò)碼的基本概念12.7.2 線性碼的生成矩陣與校驗(yàn)矩陣12.7.3 群碼12.8 小結(jié)12.9 習(xí)題第十三章 環(huán)和域13.1 環(huán)13.1.1 環(huán)的定義13.1.2 特殊元素和性質(zhì)13.1.3 環(huán)的分類13.2 子環(huán)、理想和商環(huán)13.2.1 子環(huán)和理想13.2.2 商環(huán)13.3 環(huán)同態(tài)13.4 一元多項(xiàng)式環(huán)與多項(xiàng)式編碼13.4. 1域上的一元多項(xiàng)式13.4.2 一元多項(xiàng)式環(huán)的主理想13.4.3多項(xiàng)式編碼13.5 域13.5.1 域的基本概念和簡(jiǎn)單性質(zhì)13.5.2 有限域13.5.3 擴(kuò)域的性質(zhì)和幾何作圖問(wèn)題13.6 小結(jié)13.7 習(xí)題第十四章 格和布爾代數(shù)14.1 格14.1.1 偏序格14.1.2 代數(shù)格14.2 有界格、有補(bǔ)格和分配格14.3 布爾代數(shù)14.3.1 布爾格和布爾代數(shù)14.3.2 有限布爾代數(shù)14.3.3 對(duì)偶原理14.4 小結(jié)14.5 習(xí)題參考文獻(xiàn)

章節(jié)摘錄

　　第一章　集合論　　集合是數(shù)學(xué)的基本概念，很多數(shù)學(xué)家都認(rèn)為，所有的數(shù)學(xué)都可以用集合論的術(shù)語(yǔ)來(lái)表示。集合論的起源可以追溯到16世紀(jì)末，但它的創(chuàng)立是在19世紀(jì)末由德國(guó)數(shù)學(xué)家康托爾（G.Cantor）完成的。最初，為了建立微積分學(xué)的嚴(yán)格的理論基礎(chǔ)，人們對(duì)數(shù)集進(jìn)行了研究，直到l876～1883年，康托爾對(duì)任意元素的集合進(jìn)行了系統(tǒng)的研究，提出了基數(shù)、序數(shù)和良序集等理論，從而奠定了集合論的基礎(chǔ)。這樣的集合論基于直觀的集合概念，稱為樸素集合論。l900年前后，由于各種悖論的發(fā)現(xiàn)，特別是1901年羅素（B.Russell）悖論的發(fā)現(xiàn)，使集合論的發(fā)展一度受阻。l908年，策墨羅（E.Zermelo）提出了第一個(gè)集合論的公理系統(tǒng)，使數(shù)學(xué)哲學(xué)中產(chǎn)生的一些矛盾基本上得到統(tǒng)一。在此基礎(chǔ)上，集合論與邏輯學(xué)相互融合并迅速發(fā)展，逐步形成了各種公理集合論?，F(xiàn)在，集合論不僅作為一門純數(shù)學(xué)成為數(shù)理邏輯的一個(gè)主要分支，而且作為精確、嚴(yán)謹(jǐn)而又簡(jiǎn)便的語(yǔ)言，已經(jīng)滲透到現(xiàn)代數(shù)學(xué)的各個(gè)領(lǐng)域，成為整個(gè)數(shù)學(xué)的基礎(chǔ)?！　∮?jì)算機(jī)科學(xué)對(duì)集合論感興趣，是因?yàn)樗谟?jì)算機(jī)科學(xué)中被廣泛地應(yīng)用，是建立數(shù)學(xué)模型以及進(jìn)行深入探討的有力工具。比如，在形式語(yǔ)言、編譯理論、信息檢索、數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)、算法分析、數(shù)據(jù)庫(kù)、有限自動(dòng)機(jī)、人工智能等等許多領(lǐng)域中，集合論都是不可缺少的理論工具，起著重要的作用。　　本書(shū)僅限于討論樸素集合論。本章介紹集合的基礎(chǔ)知識(shí)，主要包括集合的概念、集合運(yùn)算及其基本性質(zhì)、n元組和笛卡兒乘積等等，這些基本概念是離散數(shù)學(xué)的基礎(chǔ)，將貫穿整個(gè)課程。集合論的其他重要內(nèi)容，如關(guān)系、函數(shù)、基數(shù)等等，將在第五章和第六章中講述?！　　?/pre>








圖書(shū)封面






評(píng)論、評(píng)分、閱讀與下載



還沒(méi)讀過(guò)(60)
勉強(qiáng)可看(435)
一般般(742)
內(nèi)容豐富(3079)
強(qiáng)力推薦(252)


 


    離散數(shù)學(xué) PDF格式下載