離散數(shù)學基礎(chǔ)及實用算法

前言

　　離散數(shù)學形成于20世紀70年代初期，是隨著計算機科學的發(fā)展和計算機應用的日趨廣泛而建立起來的一個數(shù)學分支，它為計算機科學技術(shù)和工程應用提供了有力的理論工具，其中涉及的概念、原理和方法在計算機及相關(guān)學科領(lǐng)域都有著重要應用。離散數(shù)學與計算機科學中的數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、算法分析、邏輯設(shè)計、系統(tǒng)結(jié)構(gòu)、機器定理證明等課程聯(lián)系緊密，是培養(yǎng)學生縝密思維，提高學生素質(zhì)的核心課程之一。因此，離散數(shù)學已經(jīng)顯示出強大的生命力和滲透力，發(fā)展前景廣闊?！　”菊n程不但要培養(yǎng)學生的抽象思維能力，而且更注重培養(yǎng)學生運用數(shù)學方法解決實際問題的能力。然而，從作者多年講授離散數(shù)學的效果來看，有不少學生在學習完抽象的數(shù)學理論后，對于其中相關(guān)理論和方法的學習目標和作用并不明確，也不知道這些理論的真正作用，尤其是不能將離散數(shù)學的學習與其計算機實現(xiàn)相結(jié)合。往往是單純地學習理論知識，缺乏與實際問題的聯(lián)系，這是離散數(shù)學教學時一個亟待改進的問題?！　”緯奶厣　”窘滩脑趦?nèi)容取材和寫作風格上做了相應的整合與嘗試。將抽象的離散數(shù)學理論和具體的計算機實現(xiàn)有機地聯(lián)系起來，提出了離散數(shù)學的教學離不開計算機實驗的思想，主要表現(xiàn)在：　?。?）將離散數(shù)學理論教學與算法實現(xiàn)結(jié)合?！　。?）將多種算法和數(shù)據(jù)結(jié)構(gòu)有機結(jié)合?！　。?）將離散數(shù)學理論與應用結(jié)合?！　。?）通俗易懂、循序漸進地給出算法的實現(xiàn)。　　本書的主要內(nèi)容　　本教材分為基本理論和算法實現(xiàn)兩個部分?；纠碚摪〝?shù)理邏輯、集合與關(guān)系、代數(shù)系統(tǒng)以及圖論四方面內(nèi)容；算法實現(xiàn)穿插于理論介紹之后，詳細地給出了具體的實現(xiàn)算法，其目的都是為讀者進一步理解基本理論。本書所提供的源程序可以作為讀者自主開發(fā)的基礎(chǔ)。

內(nèi)容概要

　　《離散數(shù)學基礎(chǔ)及實用算法》包括離散數(shù)學基礎(chǔ)理論和算法實現(xiàn)兩部分內(nèi)容。基礎(chǔ)理論部分包括數(shù)理邏輯、集合與關(guān)系、代數(shù)系統(tǒng)以及圖論等。算法實現(xiàn)部分以大量的算例系統(tǒng)地給出了離散數(shù)學中典型理論成果的計算機實現(xiàn)?！峨x散數(shù)學基礎(chǔ)及實用算法》包含豐富的算法、大量的應用實例，在詳細解釋源代碼的同時，為讀者進一步自主開發(fā)提供了便利?！　　峨x散數(shù)學基礎(chǔ)及實用算法》可以作為普通高等學校、計算機、信息科學或其他相關(guān)專業(yè)本、?？平滩模瑫r，可供科技人員、教學人員以及研究生參考。將離散數(shù)學理論教學與算法實現(xiàn)結(jié)合。將多種算法和數(shù)據(jù)結(jié)構(gòu)有機結(jié)合。將離散數(shù)學理論與應用結(jié)合。通俗易懂、循序漸進地給出算法的實現(xiàn)。

書籍目錄

第1篇 數(shù)理邏輯及實用算法第1章 命題邏輯1.1 命題的基本概念1.2 命題聯(lián)結(jié)詞1.3 命題公式與翻譯1.4 真值表與等價公式1.5 重言式與蘊含式1.6 其他聯(lián)結(jié)詞1.7 對偶與范式1.8 命題演算的推理理論第2章 謂詞邏輯2.1 謂詞的概念與表示2.2 謂詞公式與翻譯2.3 變元的約束2.4 謂詞公式的等價式與蘊含式2.5 謂詞公式的范式2.6 謂詞演算的推理理論第3章 數(shù)理邏輯中的實用算法3.1 命題公式的真值表算法3.2 命題公式的主析（合）取范式算法山第2篇 集合與關(guān)系及實用算法第4章 集合與關(guān)系4.1 集合的基本概念4.2 集合的運算4.3 序偶與笛卡爾積4.4 關(guān)系及其表示4.5 關(guān)系的性質(zhì)4.6 復合關(guān)系和逆關(guān)系4.7 關(guān)系的閉包運算4.8 集合的劃分與覆蓋4.9 等價關(guān)系與等價類4.1 0相容關(guān)系與相容類4.1 1偏序關(guān)系與偏序集第5章 函數(shù)5.1 函數(shù)的概念5.2 逆函數(shù)和復合函數(shù)5.3 基數(shù)的概念5.4 基數(shù)的比較第6章 集合與關(guān)系中的實用算法6.1 集合的基本運算算法6.2 集合的冪集算法6.3 關(guān)系的閉包運算算法6.4 等價關(guān)系和等價類算法第3篇 代數(shù)系統(tǒng)及實用算法第7章 代數(shù)系統(tǒng)7.1 代數(shù)系統(tǒng)的引入7.2 運算及其性質(zhì)7.3 半群7.4 群與子群7.5 阿貝爾群與循環(huán)群7.6 陪集與拉格朗日定理7.7 同態(tài)與同構(gòu)7.8 環(huán)與域第8章 代數(shù)系統(tǒng)中的實用算法8.1 代數(shù)系統(tǒng)性質(zhì)判定算法8.2 群的判定算法第4篇 圖論及實用算法第9章 圖論9.1 圖的基本概念9.2 路與回路9.3 圖的矩陣表示9.4 歐拉圖和哈密爾頓圖9.5 平面圖9.6 對偶圖與著色9.7 樹與生成樹9.8 根樹及其應用第10章 圖論中的實用算法10.1 計算機中圖的表示10.2 圖的連通性算法10.3 歐拉圖的判定算法10.4 哈夫曼樹的構(gòu)造算法10.5 最小生成樹算法第11章 程序集成11.1 系統(tǒng)總界面的開發(fā)11.2 系統(tǒng)總界面算法參考文獻

章節(jié)摘錄

　　從以上的分析可以看出，表達思想的語句有不同的類別，數(shù)理邏輯中研究的是出現(xiàn)較多而又比較規(guī)范的語句即可以判斷出真或假的陳述句。　　定義1.1.1 命題（proposition）　　凡是能判斷是真或是假的陳述句稱為命題。　　這里所說的“真”可以理解為正確的、符合事實邏輯的；“假”可以理解為錯誤的，不符合事實邏輯的。本書中一般用True或者T來表示真，用False或F表示假.　　如前面的（1）－（5）都是命題，（6）－（11）都不是命題。　　在判定一個命題的真假時，從語法上就是看它是否是陳述句。由于在推理過程中，無法從疑問句、祈使句、感嘆句中獲取有用的信息。因此，一切疑問句、祈使句、感嘆句都不能稱為命題。但需要注意的是，那些“自指謂”的陳述句，不在其列。如“本頁這一行的這句話是假話”這一語句，它的結(jié)論是對自身而言的，就是所謂的“自指謂”。這種“自指謂”的語句往往會產(chǎn)生自相矛盾的結(jié)論，即所謂的悖論。如上面這句話，如果承認它是真的，由于本頁這一行中沒有別的話，所以必須承認它是假的；另一方面，如果承認它是假的，這剛好就是這句話所說的，所以又必須承認它是真的。因此，這句話本身包含了悖論，故我們在判斷一個語句是否是命題時把這種語句排除在命題之外?！　∩鲜稣Z句（11）也是這種情況?！　±?.1.1 中國在第30屆奧運會上取得金牌數(shù)和獎牌數(shù)第一。　　解：這句話，雖然不能馬上分辨真假，但是只要在倫敦奧運會結(jié)束時就可以驗證，還是可以知道的，因此是命題?！　±?.1.2 “一個偶數(shù)可表示成兩個素數(shù)之和”（哥德巴赫猜想）?！　〗猓哼@句話是命題，或為真或為假，只不過當今尚不知其是真命題還是假命題?！　±?.1.3 雪是黑的?！　〗猓哼@是一個陳述句，可確定真值。顯然其真值為假，或說為F。所以，是一個命題.　　定義命題的目的是希望我們在推理時能從命題中獲取有用信息。由于本章主要介紹的是有關(guān)命題推理的理論方法，因此，盡量不要去糾纏各種具體命題的真假問題，而是將命題當作是一個抽象的數(shù)據(jù)概念來處理，把命題定義成非真必假的陳述句。此時，所關(guān)心的并不僅僅是這些陳述句究竟是真還是假，更關(guān)心的是它可以被賦予真或假的可能性，以便考查被賦予真值后它與其他命題的聯(lián)系?！　≡跀?shù)理邏輯中，使用大寫字母A，B，…，P，Q，…，或者用帶有下標的大寫字母，如A1，B5，Pi等表示命題。例如，　　P：今天下雨?！　可表示“今天下雨”這個命題的名?！　∫部梢杂眉臃嚼ㄌ柕臄?shù)字表示命題，例如，[12]：今天下雨?！　”硎久}的符號稱為命題表示符，P或[12]稱為標識符。

編輯推薦

　　《離散數(shù)學基礎(chǔ)及實用算法》可以作為普通高等學校、計算機、信息科學或其他相關(guān)專業(yè)本、?？平滩模瑫r，可供科技人員、教學人員以及研究生參考。將離散數(shù)學理論教學與算法實現(xiàn)結(jié)合。將多種算法和數(shù)據(jù)結(jié)構(gòu)有機結(jié)合。將離散數(shù)學理論與應用結(jié)合。通俗易懂、循序漸進地給出算法的實現(xiàn)。

圖書封面

評論、評分、閱讀與下載

---

    離散數(shù)學基礎(chǔ)及實用算法 PDF格式下載

---