离散数学及其在计算机科学中的应用（英文版）

图书标准信息

• 作者 Cliff L Stein,Robert Drysdale,Kenneth Bogart 著
• 出版社 机械工业出版社
• 出版时间 2017-10
• 版次 1
• ISBN 9787111580973
• 定价 99.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 508页
• 丛书 经典原版书库

【内容简介】

本书专为计算机科学专业的学生而设计，不仅提供学生必需的离散数学知识，而且能够启发后续专业课程的学习兴趣。本书主要内容涵盖计数、密码学与数论、逻辑与证明、归纳法、递归、概率以及图论，推导严谨、代码清晰、练习丰富。本书不仅适合作为高校计算机相关专业离散数学课程的教材，也适合从事计算机行业的技术人员参考。

【作者简介】

克利福德斯坦，有名计算机科学家，名作算导论的作者之一。现为哥伦比亚大学计算机科学系和工程与运筹学系教授。罗伯特l.戴斯得尔，达特茅斯学院计算机科学系教授，曾任该系系主任8年，是算和计算几何学领域的知名学者。肯尼斯博加特，生前是达特茅斯学院数学系教授，一生致力于数学研究和工作，2005年由于交通事故不幸去世。

【目录】

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,