☆☆☆☆☆




點擊這裡下載

類似圖書 點擊查看全場最低價

---

內容簡介

本書專為計算機科學專業的學生而設計，不僅提供學生必需的離散數學知識，而且能夠啓發後續專業課程的學習興趣。本書主要內容涵蓋計數、密碼學與數論、邏輯與證明、歸納法、遞歸、概率以及圖論，推導嚴謹、代碼清晰、練習豐富。本書不僅適閤作為高校計算機相關專業離散數學課程的教材，也適閤從事計算機行業的技術人員參考。

目錄

Contents
CHAPTER1 Counting 31
1.1 Basic Counting 31
The Sum Principle 31
Abstraction 33
Summing Consecutive Integers 33
The Product Principle 34
Two-Element Subsets 36
Important Concepts, Formulas, and Theorems 37
Problems 38
1.2 Counting Lists, Permutations, and Subsets 40
Using the Sum and Product Principles 40
Lists and Functions 42
The Bijection Principle 44
k-Element Permutations of a Set 45
Counting Subsets of a Set 46
Important Concepts, Formulas, and Theorems 48
Problems 50
1.3 Binomial Coeffiients 52
Pascal’s Triangle 52
A Proof Using the Sum Principle 54
The Binomial Theorem 56
Labeling and Trinomial Coefficient 58
Important Concepts, Formulas, and Theorems 59
Problems 60
1.4 Relations 62
What Is a Relation? 62
Functions as Relations 63
Properties of Relations 63
Equivalence Relations 66
Partial and Total Orders 69
Important Concepts, Formulas, and Theorems 71
Problems 72
1.5 Using Equivalence Relationsin Counting 73
The Symmetry Principle
Equivalence Relations 75
The Quotient Principle 76
Equivalence Class Counting 76
Multisets 78
The Bookcase Arrangement Problem 80
The Number of k-Element Multisets of an n-Element Set 81
Usingthe Quotient Principle to Explain a Quotient 82
Important Concepts, Formulas, and Theorems 83
Problems 84
CHAPTER2 Cryptography and Number Theory 89
2.1 Cryptography and Modular Arithmetic 89
Introduction to Cryptography 89
Private-Key Cryptography 90
Public-Key Cryptosystems 93
Arithmetic Modulo n 95
Cryptography Using Addition mod n 98
Cryptography Using Multiplication mod n 99
Important Concepts, Formulas, and Theorems 101
Problems 102
2.2 Inverses and Greatest Common Divisors 105
Solutions to Equations and Inverses mod n 105
Inverses mod n 106
Converting Modular Equations to Normal Equations 109
Greatest Common Divisors 110
Euclid’s Division Theorem 111
Euclid’s GCD Algorithm 114
Extended GCD Algorithm 115
Computing Inverses 118
Important Concepts, Formulas, and Theorems 119
Problems 120
2.3 The RSA Cryptosystem 123
Exponentiation mod n 123
The Rules of Exponents 123
Fermat’s Little Theorem 126
The RSA Cryptosystem 127
The Chinese Remainder Theorem 131
Important Concepts, Formulas, and Theorems 132
Problems 134
2.4 Details of the RSA Cryptosystem 136
Practical Aspects of Exponentiation mod n 136
How Long Does It Take to Use the RSA Algorithm? 139
How Hard Is Factoring? 140
Finding Large Primes 140
Important Concepts, Formulas, and Theorems 143
Problems 144
CHAPTER3 Reflectionon Logic and Proof 147
3.1 Equivalence and Implication 147
Equivalence of Statements 147
Truth Tables 150
DeMorgan’s Laws 153
Implication 155
If and Only If 156
Important Concepts, Formulas, and Theorems 159
Problems 161
3.2 Variables and Quantifier 163
Variables and Universes 163
Quantifier 164
Standard Notation for Quantificatio 166
Statements about Variables 168
Rewriting Statements to Encompass Larger Universes 168
Proving Quantifie Statements Trueor False 169
Negation of Quantifie Statements 170
Implicit Quantificatio 173
Proof of Quantifie Statements 174
Important Concepts, Formulas, and Theorems 175
Problems 177
3.3 Inference 179
Direct Inference (Modus Ponens) and Proofs 179
Rules of Inference for Direct Proofs 181
Contrapositive Ruleof Inference 183
Proof by Contradiction 185
Important Concepts, Formulas, and Theorems 188
Problems 189
CHAPTER4 Induction, Recursion, and Recurrences 191
4.1 Mathematical Induction 191
Smallest Counterexamples 191
The Principle of Mathematical Induction 195
Strong Induction 199
Induction in General 201
A Recursive Viewof Induction 203
Structural Induction 206
Important Concepts, Formulas, and Theorems 208
Problems 210
4.2 Recursion, Recurrences, and Induction 213
Recursion 213
Examples of First-Order Linear Recurrences 215
Iteratinga Recurrence 217
Geometric Series 218
First-Order Linear Recurrences 221
Important Concepts,

前言/序言

課程動機與目標很多學院與大學都開設瞭離散數學這門課程。上這些課程的學生來自多個學科，其中最多的是來自計算機科學的學生。由國傢科學基金會支持，作為達特茅斯（Dartmouth）學院跨學科數學項目的一部分，我們提齣創建一門離散數學課程來直接解決計算機科學學生的需求。計算機科學的學生需要知道哪些離散數學知識？為什麼需要知道這些知識？關於這兩個問題，我們的看法如下。
第一，我們認為一些知識對於計算機科學很重要，但是傳統的離散數學課程常常不會透徹地講授這些知識。這些知識包括：遞歸樹和解決遞推關係的主定理，計算平均運行時間和分析隨機算法的概率理論，以及強歸納法和結構歸納法。
第二，我們認為對於計算機科學的學生而言，那些重要的離散數學知識在計算機科學裏對應著一些頗有啓發性的問題，並且隻具備一兩門計算機科學入門課程水平的學生也能夠理解。這樣有可能迴答一屆又一屆學生在應用數學課程中的疑問：“為什麼我們必須學習這個？”因此，我們選擇寫一本針對計算機科學學生的教科書，為他們提供必要的數學基礎，並且通過他們在起步階段就能夠理解的計算機科學問題來啓發學習興趣。
在計算機科學係，離散數學通常是學生的專業首選課之一，甚至是第一門計算機科學課程的先修課。在這種情況下，教師麵臨著兩難睏境：是講授純數學概念，幾乎不涉及計算機應用，還是講授計算機科學的例子，從而營造一種針對計算機科學學生的教學環境。第一種講課方式讓學生們抱怨在學習第一門計算機科學課程之前，被迫學習太多“不相乾的”數學。第二種講課方式讓教授們（通常是數學傢）嘗試給可能從來沒有寫過程序的學生解釋相當高級的計算機科學知識，比如散列、二叉樹和循環程序等。即使在最好的情況，這種方法也明顯降低瞭數學的深度。我們的分析産生瞭一種不同的講課方式，創設一門齣現在學生稍後學習過程中的課程。盡管我們不強製要求學生已經上過微積分，但是我們假定學生瞭解並且能夠熟練使用加和符號、對數和指數函數，因此對於微積分學前課程的內容有很深的瞭解是很有幫助的。這意味著要讓學生在一門計算機科學的導論課程中先瞭解遞歸程序，然後再學習這門課。最好可以和數據結構課程一起或者在其之後學習，不過我們會通過例子解釋書中所使用的數據結構，因此數據結構不是這門課的先導課程。
我們覺得這樣安排離散數學這門課程有幾個優勢，下麵列舉幾個特彆的例子：
學生已經有瞭較為深入的問題求解、算法和代碼的經驗。
學生已經學習過或者在準備學習一些重要的計算機科學概念，比如散列、遞歸、排序、搜索以及基本的數據結構。
學生已經知道足夠的計算機科學知識，包括一些啓發性的例子，或者其他容易理解的簡單例子。例如：
m散列可以用於啓發關於概率的學習。
m分析遞歸程序（比如並歸和快速排序）可以用於啓發關於遞歸關係及其解決方法的學習。
m在尋找隊列中最小元素的過程中，分析我們期望多久找到一個新的最小值，可以用來啓發關於期望的綫性性質和調和數的學習。
m二叉樹可以用來講解結構遞歸法，也可以啓發作為圖的特例的樹的學習。
在我們自己的講課經驗中，這門課是算法課的前導，並且學生經常在結束離散數學課程不久後就學習算法。這樣，他們會發現自己可以直接使用剛剛學過的離散數學知識。
我們的教育哲學這本教科書是以教學活動為驅動的，並且包含豐富的練習題。通過對這些活動的解釋和擴展，教學素材得以不斷充實。對於學生最有效的方法是嘗試認真完成學生活動，而先不閱讀那些教學活動後麵的解釋。我們最初設計這些教學活動是想讓學生在課堂中以小組的形式來完成，因此，如果需要在課外開展教學活動，建議學生組建小組一起完成。我們采用這種方式來設計這門課程以及這本教材，希望藉此幫助學生們養成自己的數學思維習慣。我們仔細研究瞭本科學生應當怎樣學習數學，得到瞭以下幾個結論：
如果學生能夠主動發現他們正在學習的是什麼（經常被稱為“主動學習”），往往比那些被動學習的學生能夠更長久地記住這些概念，也更有可能在學習環境之外運用這些概念。
當學生在一個小組中和同學一起學習，而不是在由導師帶領的一個更大的班級中時，他們更有可能提齣問題，直到徹底理解某個主題。（然而，這一點不總是成立。很多學生需要在小組中感到舒適之後纔敢提齣的問題，因為他們擔心自己的提問會耽誤彆人的學習速度。我們嘗試提高課程中的舒適度，方法是允許學生自由選擇學習小組，並且根據齣席模式允許或者要求學生在不同的天數後更換不同的小組。）最後，學生在給彆人解釋概念的時候能夠更有效地組織自己腦中的想法，同時能夠熟悉數學語言。
本書內容足夠支撐一門四學期學時的課程。在達特茅斯學院，我們使用這本書來上一門快節奏的課程，一周上三天且僅僅上九周，並且覆蓋瞭本書除瞭最後幾個章節和一部分帶星號的內容之外的所有內容。
證明的作用我們寫這本書的目的之一是給學生們提供一些關於證明的背景知識，在以後的計算機科學課程中，他們將需要理解並且寫齣證明。
離散數學及其在計算機科學中的應用（英文版） 下載 mobi epub pdf txt 電子書

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

類似圖書 點擊查看全場最低價

查看全網最低價