用計(jì)算機(jī)編程解題的核心問題是算法,而組合數(shù)學(xué)是算法的主要內(nèi)容。組合數(shù)學(xué)對(duì)于參加信息學(xué)奧林匹克活動(dòng)的青少年而言,是一門提高思維能力、分析與判斷能力.以及自我構(gòu)造算法的重要課程!峨x散數(shù)學(xué)和組合數(shù)學(xué)》力求將分析問題與自己上機(jī)編程結(jié)合起來,這樣做可以化難為易。書上不但講了組合數(shù)學(xué)的原理、概念和分析問題的思路,還講了如何編程,并給出了參考程序,這對(duì)自學(xué)《離散數(shù)學(xué)和組合數(shù)學(xué)》極為有利。《離散數(shù)學(xué)和組合數(shù)學(xué)》是參加信息學(xué)奧林匹克競賽學(xué)生的必讀書,同時(shí)對(duì)于一些理工科的大學(xué)生也可用作學(xué)習(xí)編程解題的參考資料。
As in the first edition, the purpose of this book is to present an extensive range anddepth of topics in discrete mathematics and also work in a theme on how to do proofs.Proofs are introduced in the first chapter and continue throughout the book. Moststudents taking discrete mathematics are mathematics and computer science majors.Although the necessity of learning to do proofs is obvious for mathematics majors, itis also critical for computer science students to think logically. Essentially, a logicalbug-free computer program is equivalent to a logical proof, Also, it is assumed in thisbook that it is easier to use (or at least not misuse) an application if one understandswhy it works. With few exceptions, the book is self-contained. Concepts are developedmathematically before they are seen in an applied context.Additions and alterations in the second edition:
More coverage of proofs, especially in Chapter l. Added computer science applications, such as a greedy algorithm for coloring the nodes of a graph, a recursive algorithm for counting the number of nodes on a binary search tree, or an efficient algorithm for computing ab modn for very largevalues of a, b, and n.
An extensive increase in the number of problems in the first seven chapters.
More problems are included that involve proofs.
Additional material is included on matrices.
True-False questions at the end of each chapter.
Summary questions at the end of each chapter.
Functions and sequences are introduced earlier (in Chapter 2).
Calculus is not required for any of the material in this book. College algebra isadequate for the basic chapters. However, although this book is self-contained, some ofthe remaining chapters require more mathematical maturity than do the basic chapters,so calculus is recommended more for giving maturity, than for any direct uses.
This book is intended for either a one- or two-term course in discrete mathematics.The first eight chapters of this book provide a foundation in discrete mathematicsand would be appropriate for a first-level course for freshmen or sophomores. Thesechapters are essentially independent, so that the instructor can pick the material he/shewishes to cover. The remainder of the book contains appropriate material for a secofidcourse in discrete mathematics. These chapters expand concepts introduced earlier andintroduce numerous advanced topics. Topics are explored from different points of viewto show how they may be used in different settings. The range of topics include:
Logic-Including truth tables, propositional logic, predicate calculus, circuits, induction, and proofs.
Set Theory-Including cardinality of sets, relations, partially ordered sets, congruence relations, graphs, directed graphs, and functions.
Algorithms-Including complexity of algorithms, search and sort algorithms, theEuclidean algorithm, Huffmans algorithm, Prims algorithms, Warshalls algorithm, the Ford-Fulkerson algorithm, the Floyd-Warshall algorithm, and Dijkstrasalgorithms.
序言
1 真值表、邏輯和證明
1.1 語句和連接詞
1.2 條件語句
1.3 等價(jià)語句
1.4 公理系統(tǒng):論證和證明
1.5 命題邏輯的完備性
2 集合論
2.1 集合導(dǎo)引
2.2 集合運(yùn)算
2.3 Venn圖
2.4 布爾代數(shù)
2.5 關(guān)系
2.6 偏序集
2.7 等價(jià)關(guān)系
2.8 函數(shù)
3 邏輯、整數(shù)集和證明
3.1 謂詞演算
3.2 證明的概念與整數(shù)集的結(jié)構(gòu)
3.3 素?cái)?shù)
3.4 同余關(guān)系
4 函數(shù)
4.1 特殊函數(shù)
4.2 基數(shù)
4.3 基數(shù)的繼續(xù)討論
5 算法
5.1 “for”過程與矩陣算法
5.2 遞歸函數(shù)與算法
5.3 算法復(fù)雜性
6 圖、有向圖和樹
6.1 圖
6.2 有向圖
6.3 樹
6.4 歐拉路和歐拉回路
6.5 關(guān)聯(lián)矩陣和鄰接矩陣
7 計(jì)數(shù)
7.1 基本計(jì)數(shù)原理
7.2 包含排斥原理
7.3 排列與組合
7.4 生成排列與組合
7.5 廣義排列與組合
7.6 有重復(fù)的排列與組合
7.7 鴿巢原理
8 代數(shù)結(jié)構(gòu)
8.1 偏序集的進(jìn)一步討論
8.2 半群和半格
8.3 格
8.4 群
8.5 群和群同態(tài)
9 遞歸的進(jìn)一步討論
9.1 齊次線性遞歸關(guān)系
9.2 非齊次線性遞歸關(guān)系
9.3 有限差分
9.4 階乘多項(xiàng)式
9.5 差分的和
10 計(jì)數(shù)的進(jìn)一步討論
10.1 占有問題
10.2 Catalan數(shù)
10.3 廣義包含排斥與重排
10.4 Rook多項(xiàng)式和禁用位置
11 生成函數(shù)
11.1 定義生成函數(shù)
11.2 生成函數(shù)與遞歸關(guān)系
11.3 生成函數(shù)與計(jì)數(shù)
11.4 劃分
11.5 指數(shù)生成函數(shù)
12 圖論的進(jìn)一步討論
12.1 圖的代數(shù)性質(zhì)
12.2 平面圖
12.3 著色圖
12.4 哈密頓路和哈密頓圈
12.5 加權(quán)圖和最短路算法
13 樹
13.1 樹的性質(zhì)
13.2 分搜索樹
13.3 加權(quán)樹
13.4 遍歷二分樹
13.5 生成樹
13.6 極小生成樹
14 網(wǎng)絡(luò)
14.1 網(wǎng)絡(luò)和流
14.2 配
14.3 佩特里網(wǎng)
15 染色的枚舉
15.1 伯恩賽德定理
15.2 波利亞定理
16 環(huán)、整環(huán)和域
16.1 環(huán)和整環(huán)
16.2 整環(huán)
16.3 多項(xiàng)式
16.4 代數(shù)和多項(xiàng)式
參考文獻(xiàn)
部分習(xí)題答案
中英文詞匯表