離散數(shù)學(xué)結(jié)構(gòu)
定 價(jià)：32 元
- 作者：歐陽丹彤等編著
- 出版時(shí)間：2011/6/1
- ISBN：9787040330540
- 出 版 社：高等教育出版社
- 中圖法分類：O158
- 頁碼：321
- 紙張：膠版紙
- 版次：1
- 開本：16K
本書是在吉林大學(xué)《離散數(shù)學(xué)》（高等教育出版社，1983年）以及《離散數(shù)學(xué)》（高等教育出版社，2002年）的基礎(chǔ)上，結(jié)合多年的教學(xué)實(shí)踐編寫而成。本書分為8章，主要內(nèi)容包括集合論基礎(chǔ)知識、計(jì)數(shù)理論、古典數(shù)理邏輯、圖與網(wǎng)絡(luò)、數(shù)論基礎(chǔ)知識、抽象代數(shù)的群、環(huán)和域、格和布爾代數(shù)，以及計(jì)算模型中的三種類型的結(jié)構(gòu)。
第一章 集合論基礎(chǔ)
1.1 集合的基本概念
習(xí)題1.1
1.2 關(guān)系
1.2.1 關(guān)系的基本概念及其性質(zhì)
1.2.2 等價(jià)關(guān)系
1.2.3 偏序關(guān)系
習(xí)題1.2
1.3 映射
1.3.1 集合的基數(shù)
1.3.2 可數(shù)集合
1.3.3 不可數(shù)集合
習(xí)題1.3
1.4 集合在計(jì)算機(jī)科學(xué)中的應(yīng)用
1.4.1 關(guān)系在關(guān)系數(shù)據(jù)庫中的應(yīng)用
1.4.2 關(guān)系代數(shù)與數(shù)據(jù)子語言
1.4.3 等價(jià)關(guān)系在計(jì)算機(jī)中的應(yīng)用
1.4.4 序關(guān)系在項(xiàng)目管理中的應(yīng)用
第二章 計(jì)數(shù)
2.1 兩個(gè)基本計(jì)數(shù)原理
2.1.1 加法原理
2.1.2 乘法原理
習(xí)題2.1
2.2 排列與組合
2.2.1 集合的排列數(shù)和組合數(shù)
2.2.2 多重集的排列數(shù)和組合數(shù)
習(xí)題2.2
2.3 二項(xiàng)式定理
2.3.1 二項(xiàng)式定理
2.3.2 二項(xiàng)式定理的推廣
習(xí)題2.3
2.4 容斥原理
2.4.1 容斥原理
2.4.2 容斥原理的應(yīng)用
習(xí)題2.4
2.5 鴿巢原理
2.5.1 簡單的鴿巢原理
2.5.2 加強(qiáng)的鴿巢原理
習(xí)題2.5
第三章 古典數(shù)理邏輯
3.1 命題邏輯
3.1.1 命題與公式
3.1.2 命題公式的等價(jià)關(guān)系和蘊(yùn)涵關(guān)系
3.1.3 范式
3.1.4 命題邏輯在二值邏輯器件和語句邏輯中的應(yīng)用
習(xí)題3.1
3.2 謂詞邏輯
3.2.1 謂詞邏輯的基本概念
3.2.2 謂詞公式
3.2.3 謂詞公式的等價(jià)關(guān)系和蘊(yùn)涵關(guān)系
3.2.4 范式
3.2.5 謂詞邏輯的應(yīng)用
習(xí)題3.2
第四章 圖與網(wǎng)絡(luò)
4.1 圖
4.1.1 圖的基本概念
4.1.2 權(quán)圖Dijkstra算法
習(xí)題4.1
4.2 樹
4.2.1 樹及其等價(jià)命題
4.2.2 最優(yōu)樹Kruskal算法
4.2.3 求最優(yōu)樹的其他算法
習(xí)題4.2
4.3 有向圖 歐拉路
4.3.1 有向圖與有向樹
4.3.2 歐拉路 歐拉圖
4.3.3 無向圖 無向圖中的歐拉路
習(xí)題4.3
4.4 哈密頓圖
4.4.1 哈密頓路 哈密頓圖的必要條件
4.4.2 哈密頓圖的若干充分條件
習(xí)題4.4
4.5 平面圖
4.5.1 平面圖判定 庫拉托夫斯基判定準(zhǔn)則
4.5.2 平面圖的歐拉公式
4.5.3 平面圖的著色
習(xí)題4.5
4.6 匹配 二部圖
習(xí)題4.6
4.7 Konig無限性引理
習(xí)題4.7
4.8 網(wǎng)絡(luò)優(yōu)化算法
4.8.1 單源最短路徑問題具體算法及實(shí)現(xiàn)和比較
4.8.2 最大流問題具體算法及實(shí)現(xiàn)和比較
習(xí)題4.8
第五章 數(shù)論基礎(chǔ)
5.1 整除性 輾轉(zhuǎn)相除
5.1.1 整除及其性質(zhì)
5.1.2 輾轉(zhuǎn)相除
習(xí)題5.1
5.2 互質(zhì) 質(zhì)因數(shù)分解
5.2.1 整數(shù)互質(zhì)
5.2.2 質(zhì)數(shù)與合數(shù) 算術(shù)基本定理
習(xí)題5.2
5.3 合同 一次同余式
5.3.1 合同及其性質(zhì)
5.3.2 剩余類 一次同余式
習(xí)題5.3
5.4 九韶定理 歐拉函數(shù)
5.4.1 一次同余式組秦九韶定理
5.4.2 一元高次同余式的化簡
5.4.3 剩余系遍歷歐拉函數(shù)
習(xí)題5.4
5.5 一元高次同余式 二次剩余
5.5.1 一元高次同余式的解
5.5.2 二次同余式 二次剩余
習(xí)題5.5
5.6 數(shù)論在計(jì)算機(jī)通信安全中的應(yīng)用
5.6.1 密碼系統(tǒng)
5.6.2 愷撒密碼
5.6.3 Vigenere密碼
5.6.4 希爾密碼
5.6.5 RSA公鑰系統(tǒng)
習(xí)題5.6
第六章 群、環(huán)、域
6.1 代數(shù)系統(tǒng)
習(xí)題6.1
6.2 群的定義
6.2.1 半群
6.2.2 群
6.2.3 群的性質(zhì)
6.2.4 置換群
習(xí)題6.2
6.3 子群及其陪集
6.3.1 子群的定義
6.3.2 子群的判別條件
6.3.3 循環(huán)群
6.3.4 陪集
習(xí)題6.3
6.4 群的同態(tài)及同構(gòu)
6.4.1 同態(tài)映射
6.4.2 同構(gòu)映射
6.4.3 同態(tài)核
習(xí)題6.4
6.5 環(huán)
6.5.1 環(huán)的定義及性質(zhì)
6.5.2 環(huán)同態(tài)
習(xí)題6.5
6.6 域的特征 素域
6.6.1 域的特征
6.6.2 素域
習(xí)題6.6
6.7 多項(xiàng)式
6.7.1 多項(xiàng)式的整除性
6.7.2 多項(xiàng)式的根
6.7.3 有理域上的多項(xiàng)式
6.7.4 分圓多項(xiàng)式
習(xí)題6.7
6.8 有限域
習(xí)題6.8
6.9 群環(huán)域在計(jì)算機(jī)科學(xué)中的應(yīng)用
6.9.1 計(jì)數(shù)問題
6.9.2 糾錯(cuò)碼
6.9.3 多項(xiàng)式編碼方法及其實(shí)現(xiàn)
習(xí)題6.9
第七章 格與布爾代數(shù)
7.1 引言
7.2 格的定義
習(xí)題7.2
7.3 格的性質(zhì)
7.3.1 對偶原理
7.3.2 格的其他性質(zhì)
7.3.3 格的同態(tài)與同構(gòu)
習(xí)題7.3
7.4 幾種特殊的格
7.4.1 有界格
7.4.2 有余格
7.4.3 分配格
7.4.4 模格
習(xí)題7.4
7.5 布爾代數(shù)
7.5.1 布爾代數(shù)的定義及其性質(zhì)
7.5.2 有限布爾代數(shù)的表示理論
7.5.3 布爾代數(shù)的同態(tài)與同構(gòu)
習(xí)題7.5
7.6 布爾表達(dá)式的化簡問題
習(xí)題7.6
7.7 格與布爾代數(shù)在計(jì)算機(jī)科學(xué)中的應(yīng)用
7.7.1 開關(guān)電路函數(shù)
7.7.2 邏輯門
7.7.3 全加器的邏輯設(shè)計(jì)
第八章 語言和有限狀態(tài)機(jī)
8.1 語言和語法
8.1.1 語法結(jié)構(gòu)
8.1.2 語法結(jié)構(gòu)的類型
8.1.3 演繹樹
8.1.4 巴克斯-諾爾形式
習(xí)題8.1
8.2 帶有輸出的有限狀態(tài)機(jī)
習(xí)題8.2
8.3 沒有輸出的有限狀態(tài)機(jī)
習(xí)題8.3
8.4 語言識別
8.4.1 正則集合
8.4.2 克林定理
8.4.3 其他幾種類型的有限狀態(tài)機(jī)
習(xí)題8.4
8.5圖靈機(jī)
習(xí)題8.5
參考文獻(xiàn)
結(jié)論：這樣的圖有兩類，或者都是偶數(shù)度點(diǎn)或者有兩個(gè)奇數(shù)度點(diǎn)。
現(xiàn)在再回頭來看對應(yīng)七橋問題的圖，所有的點(diǎn)都是奇數(shù)度點(diǎn)，共有4個(gè)，故這個(gè)圖肯定不能一筆畫成。因此歐拉指出上述所要求的散步路線是不存在的。
從數(shù)學(xué)的觀點(diǎn)看，圖的理論在開始時(shí)似乎價(jià)值不大，因?yàn)樗懻摰膬?nèi)容多為娛樂性的一些難題。但是近代的數(shù)學(xué)發(fā)展，特別是計(jì)算機(jī)學(xué)科誕生后的現(xiàn)代，圖與網(wǎng)絡(luò)作為一種工具在計(jì)算機(jī)科學(xué)與技術(shù)、信息、經(jīng)濟(jì)、工程和管理等諸多領(lǐng)域的應(yīng)用中發(fā)揮著重要的作用。
我們知道計(jì)算機(jī)中數(shù)據(jù)結(jié)構(gòu)，離不開數(shù)組、串、各種鏈接表、樹和圖，因此圖是計(jì)算機(jī)中數(shù)據(jù)表示、存儲和運(yùn)算的基礎(chǔ)。下面再看現(xiàn)實(shí)生活中關(guān)于圖與網(wǎng)絡(luò)的幾個(gè)小例子。
平面圖問題 在一塊地上蓋有3座房子，并且挖了3口井供房主人使用。由于土質(zhì)和氣候等關(guān)系，這些井中的這一個(gè)或那一個(gè)常常干枯。因此各座房子的主人有時(shí)要到這個(gè)井去打水，有時(shí)要到那個(gè)井去打水，3個(gè)井都可能需要去。不久，這3個(gè)房子的主人相互間變成了冤家，于是決定修建各家通往3個(gè)井的小道，使得他們在去3個(gè)井的途中不會相遇。你能否幫他們設(shè)計(jì)整個(gè)的小道路線，滿足他們的要求？
最優(yōu)支撐樹問題 某一地區(qū)有若干個(gè)主要城市，擬修建高速公路把這些城市連接起來，使得從其中任何一個(gè)城市都可以經(jīng)高速公路直接或間接到達(dá)另一個(gè)城市。假設(shè)已經(jīng)知道了任意兩個(gè)城市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最�。�
最大流問題 假設(shè)從城市P到城市Q的一個(gè)公路網(wǎng)，公路網(wǎng)中每段公路上每天可以通過的汽車的數(shù)量有上限，那么經(jīng)過該公路網(wǎng)，每天最多可以有多少輛汽車從城市P到城市Q？
上述例子都易于用圖形的形式直觀地描述和表達(dá)，在其中的最優(yōu)支撐樹問題和最大流問題中，每條路還標(biāo)有成本費(fèi)用值和汽車流量這種權(quán)值，把這種加了權(quán)的圖形稱為網(wǎng)絡(luò)。為了討論方便，本章對圖和網(wǎng)絡(luò)不做嚴(yán)格區(qū)分。與圖和網(wǎng)絡(luò)相關(guān)的最優(yōu)化問題稱為網(wǎng)絡(luò)優(yōu)化問題，這在追求最低成本、獲取最高利潤、強(qiáng)化效率的市場經(jīng)濟(jì)時(shí)代，正獲得廣泛的應(yīng)用。
……
書單推薦
