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

內(nèi)容概要

離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)基礎(chǔ)理論的核心課程，也是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支?！陡叩葘W(xué)校計(jì)算機(jī)類課程應(yīng)用型人才培養(yǎng)規(guī)劃教材:離散數(shù)學(xué)》包含了集合論、圖論、數(shù)理邏輯、組合數(shù)學(xué)、代數(shù)系統(tǒng)等內(nèi)容。在介紹離散數(shù)學(xué)主要內(nèi)容的同時(shí)，對(duì)相關(guān)知識(shí)的專業(yè)應(yīng)用也做了實(shí)用性介紹。

書籍目錄

第一篇 集 合 論 第1章 集合 1.1 集合的概念與表示 1.1.1 集合及其表示 1.1.2 子集與冪集 1.2 集合的運(yùn)算 1.2.1 集合的交、并、補(bǔ)、差 1.2.2 集合運(yùn)算的性質(zhì) 1.3 容斥原理 本章小結(jié) 習(xí)題一 第2章 關(guān)系 2.1 關(guān)系的概念與表示 2.1.1 笛卡兒積 2.1.2 關(guān)系的概念 2.1.3 關(guān)系的表示 2.2 關(guān)系的基本性質(zhì) 2.2.1 自反 2.2.2 對(duì)稱 2.2.3 傳遞 2.3 關(guān)系的運(yùn)算 2.3.1 關(guān)系的交、并、補(bǔ)、差 2.3.2 關(guān)系的復(fù)合 2.3.3 關(guān)系的逆 2.3.4 關(guān)系的閉包 2.4 等價(jià)關(guān)系與序關(guān)系 2.4.1 等價(jià)關(guān)系與劃分 2.4.2 序關(guān)系 本章小結(jié) 習(xí)題二 第3章 函數(shù) 3.1 函數(shù)的概念與分類 3.1.1 函數(shù)的概念 3.1.2 函數(shù)的分類 3.2 函數(shù)的運(yùn)算 3.2.1 函數(shù)的復(fù)合 3.2.2 函數(shù)的逆 3.3 計(jì)算機(jī)科學(xué)中常用的兩類函數(shù) 3.3.1 取整函數(shù) 3.3.2 哈希函數(shù) 3.4 基數(shù) 3.4.1 基數(shù)的概念 3.4.2 可數(shù)集與不可數(shù)集 本章小結(jié) 習(xí)題三 第二篇 圖 論 第4章 圖 4.1 圖的概念與表示 4.1.1 圖的基本概念 4.1.2 圖的矩陣表示 4.2 路徑與連通性 4.2.1 路徑與回路 4.2.2 圖的連通性 4.3 歐拉圖與漢密爾頓圖 4.3.1 歐拉圖 4.3.2 漢密爾頓圖 4.4 圖的應(yīng)用 4.4.1 最短路徑問(wèn)題 4.4.2 支配集與通信系統(tǒng)建站問(wèn)題 本章小結(jié) 習(xí)題四 第5章 樹 5.1 樹與圖的生成樹 5.1.1 樹的概念與性質(zhì) 5.1.2 圖的生成樹 5.2 根樹 5.2.1 根樹的基本概念 5.2.2 二叉樹 5.2.3 二叉樹的遍歷 5.3 樹的應(yīng)用 5.3.1 決策樹 5.3.2 二叉搜索樹 5.3.3 最優(yōu)二叉樹與哈夫曼編碼 本章小結(jié) 習(xí)題五 第三篇 數(shù)理邏輯 第6章 命題邏輯 6.1 命題與命題公式 6.1.1 命題的概念與表示 6.1.2 命題聯(lián)結(jié)詞 6.1.3 命題公式 6.2 命題公式的真值賦值與分類 6.2.1 真值表 6.2.2 重言式、矛盾式與可滿足式 6.2.3 邏輯等價(jià)與邏輯蘊(yùn)涵 6.3 范式 6.3.1 合取范式與析取范式 6.3.2 主析取范式與主合取范式 6.3.3 聯(lián)結(jié)詞的完備集 6.4 命題邏輯的推理理論 6.4.1 推理的形式結(jié)構(gòu) 6.4.2 推理規(guī)則 本章小結(jié) 習(xí)題六 第7章 謂詞邏輯 7.1 謂詞與謂詞公式 7.1.1 個(gè)體、謂詞與量詞 7.1.2 項(xiàng)與謂詞公式 7.1.3 變?cè)募s束 7.2 謂詞邏輯的語(yǔ)義 7.2.1 真值與解釋 7.2.2 永真式、矛盾式與可滿足式 7.2.3 邏輯等價(jià)與邏輯蘊(yùn)涵 7.3 前束范式 7.4 謂詞邏輯的推理理論 本章小結(jié) 習(xí)題七 第四篇 組合數(shù)學(xué) 第8章 組合數(shù)學(xué) 8.1 基本計(jì)數(shù)原理 8.1.1 加法原理 8.1.2 乘法原理 8.2 排列與組合 8.2.1 排列 8.2.2 組合 8.2.3 廣義的排列與組合 8.3 二項(xiàng)式系數(shù)與組合恒等式 8.3.1 二項(xiàng)式系數(shù) 8.3.2 組合恒等式 8.4 鴿籠原理 8.4.1 鴿籠原理的簡(jiǎn)單形式 8.4.2 鴿籠原理的一般形式 8.5 遞歸關(guān)系及其解法 8.5.1 遞歸關(guān)系的定義 8.5.2 逆向代換法 8.5.3 常系數(shù)齊次線性遞歸關(guān)系 8.5.4 常系數(shù)非齊次線性遞歸關(guān)系 本章小結(jié) 習(xí)題八 第五篇 代數(shù)系統(tǒng) 第9章 代數(shù)系統(tǒng) 9.1 代數(shù)系統(tǒng)的概念及運(yùn)算性質(zhì) 9.1.1 代數(shù)系統(tǒng)的概念 9.1.2 二元運(yùn)算的性質(zhì) 9.2 代數(shù)系統(tǒng)的同態(tài)與同構(gòu) 9.2.1 同態(tài)與同構(gòu) 9.2.2 同態(tài)的性質(zhì) 9.3 群 9.3.1 半群與獨(dú)異點(diǎn) 9.3.2 群及其基本性質(zhì) 9.3.3 子群與陪集 9.3.4 循環(huán)群與置換群 9.4 環(huán)與域 9.4.1 環(huán)與域的概念 9.4.2 環(huán)與域的性質(zhì) 9.5 格與布爾代數(shù) 9.5.1 格的概念與性質(zhì) 9.5.2 分配格、有補(bǔ)格 9.5.3 布爾代數(shù) 本章小結(jié) 習(xí)題九 附錄A 參考文獻(xiàn)

章節(jié)摘錄

版權(quán)頁(yè)：   插圖：   5.2.3 二叉樹的遍歷 利用樹進(jìn)行信息處理，經(jīng)常會(huì)涉及逐個(gè)不重復(fù)地訪問(wèn)樹中的所有結(jié)點(diǎn)，這稱為樹的遍歷。二叉樹的遍歷是最基本的遍歷算法，下面介紹二叉樹遍歷的三種常用算法。 根據(jù)定義，二叉樹由根結(jié)點(diǎn)和左、右兩棵子樹三部分構(gòu)成，如果用T代表訪問(wèn)根結(jié)點(diǎn)，L代表遍歷左子樹，尺代表遍歷右子樹，則二叉樹可以有TLR、LTR、LRT、TRL、RTL和RLT六種遍歷方式，然而經(jīng)常用到的總是先左后右的順序，所以我們將TLR表示的遍歷稱為先根遍歷，LTR表示的遍歷稱為中根遍歷，而LRT表示的遍歷稱為后根遍歷。具體的說(shuō)，二叉樹的先根遍歷算法如下： （1）訪問(wèn)根結(jié)點(diǎn)； （2）對(duì)根結(jié)點(diǎn)的左子樹進(jìn)行先根遍歷； （3）對(duì)根結(jié)點(diǎn)的右子樹進(jìn)行先根遍歷。 二叉樹的中根遍歷算法如下： （1）對(duì)根結(jié)點(diǎn)的左子樹進(jìn)行中根遍歷； （2）訪問(wèn)根結(jié)點(diǎn)； （3）對(duì)根結(jié)點(diǎn)的右子樹進(jìn)行中根遍歷。 二叉樹的后根遍歷算法如下： （1）對(duì)根結(jié)點(diǎn)的左子樹進(jìn)行后根遍歷； （2）對(duì)根結(jié)點(diǎn)的右子樹進(jìn)行后根遍歷； （3）訪問(wèn)根結(jié)點(diǎn)。 [例5.14） 對(duì)圖5-15中的二叉樹，先根遍歷訪問(wèn)各結(jié)點(diǎn)的川頁(yè)序依次為：v1，v2，v4，v8，v5，v3，v6，v9，v10，v7；中根遍歷訪問(wèn)各結(jié)點(diǎn)的順序依次為：v4 v8 v2 v5 v1 v9 v6 v10 v3 v7；后根遍歷訪問(wèn)各結(jié)點(diǎn)的順序依次為： v8 v4 v5 v2 v9 v10 v6 v7 v3 v10。 利用二叉樹可以表示算術(shù)表達(dá)式。表示時(shí)，通常將運(yùn)算符放在分支結(jié)點(diǎn)上；數(shù)值或變量放在葉結(jié)點(diǎn)上；被減數(shù)和被除數(shù)作為其雙親結(jié)點(diǎn)的左孩子。 （例5.15] 算術(shù)表達(dá)式a+b×c-（d+e）／f可表示成圖5-16中的二叉樹。 中根遍歷訪問(wèn)各結(jié)點(diǎn)的結(jié)果是：a+b×c-（d+e）／f。 先根遍歷訪問(wèn)各結(jié)點(diǎn)的結(jié)果是：+a-×bc／+df／。 后根遍歷訪問(wèn)各結(jié)點(diǎn)的結(jié)果是：abc×de+f／-+。 上述遍歷結(jié)果顯示，中根遍歷的結(jié)果是還原算術(shù)表達(dá)式，這樣的表示因?yàn)檫\(yùn)算符放在參與運(yùn)算的兩個(gè)量之間，也稱為中綴表示；先根遍歷的結(jié)果是將運(yùn)算符放在參加運(yùn)算的兩個(gè)量之前，因而稱為前綴表示或波蘭式；后根遍歷的結(jié)果是將運(yùn)算符放在參加運(yùn)算的兩個(gè)量之后，因而稱為后綴表示或逆波蘭式。對(duì)于每個(gè)運(yùn)算，由于參與運(yùn)算的量的個(gè)數(shù)固定，因此前綴表示和后綴表示都無(wú)須括號(hào)；只有中綴表示為了區(qū)分不同運(yùn)算之間的優(yōu)先級(jí)，才須加上括號(hào)。

編輯推薦

《高等學(xué)校計(jì)算機(jī)類課程應(yīng)用型人才培養(yǎng)規(guī)劃教材:離散數(shù)學(xué)》適合作為計(jì)算機(jī)和相關(guān)專業(yè)本科生“離散數(shù)學(xué)”的教學(xué)用書，也可以作為對(duì)離散數(shù)學(xué)感興趣的學(xué)生的參考書。

圖書封面

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

---

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

---