Discrete mathematics for computer scientistsPDF|Epub|txt|kindle电子书版本网盘下载

Discrete mathematics for computer scientistsPDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

CHAPTER 1 Counting1

1.1 Basic Counting1

The Sum Principle1

Abstraction3

Summing Consecutive Integers3

The Product Principle4

Two-Element Subsets6

Important Concepts，Formulas，and Theorems7

Problems8

1.2 Counting Lists，Permutations，and Subsets10

Using the Sum and Product Principles10

Lists and Functions12

The Bijection Principle14

k-Element Permutations of a Set15

Counting Subsets of a Set16

Important Concepts，Formulas，and Theorems18

Problems20

1.3 Binomial Coefficients22

Pascal’s Triangle22

A Proof Using the Sum Principle24

The Binomial Theorem26

Labeling and Trinomial Coefficients28

Important Concepts，Formulas，and Theorems29

Problems30

1.4 Relations32

What Is a Relation？32

Functions as Relations33

Properties of Relations33

Equivalence Relations36

Partial and Total Orders39

Important Concepts，Formulas，and Theorems41

Problems42

1.5 Using Equivalence Relations in Counting43

The Symmetry Principle43

Equivalence Relations45

The Quotient Principle46

Equivalence Class Counting46

Multi sets48

The Bookcase Arrangement Problem50

The Number of k-Element Multisets of an n-Element Set51

Using the Quotient Principle to Explain a Quotient52

Important Concepts，Formulas，and Theorems53

Problems54

CHAPTER 2 Cryptography and Number Theory59

2.1 Cryptography and Modular Arithmetic59

Introduction to Cryptography59

Private-Key Cryptography60

Public-Key Cryptosystems63

Arithmetic Modulo n65

Cryptography Using Addition mod n68

Cryptography Using Multiplication mod n69

Important Concepts，Formulas，and Theorems71

Problems72

2.2 Inverses and Greatest Common Divisors75

Solutions to Equations and Inverses mod n75

Inverses mod n76

Converting Modular Equations to Normal Equations79

Greatest Common Divisors80

Euclid’s Division Theorem81

Euclid’s GCD Algorithm84

Extended GCD Algorithm85

Computing Inverses88

Important Concepts，Formulas，and Theorems89

Problems90

2.3 The RSA Cryptosystem93

Exponentiation mod n93

The Rules of Exponents93

Fermat’s Little Theorem96

The RSA Cryptosystem97

The Chinese Remainder Theorem101

Important Concepts，Formulas，and Theorems102

Problems104

2.4 Details of the RSA Cryptosystem106

Practical Aspects of Exponentiation mod n106

How Long Does It Take to Use the RSA Algorithm？109

How Hard Is Factoring？110

Finding Large Primes110

Important Concepts，Formulas，and Theorems113

Problems114

CHAPTER 3 Reflections on Logic and Proof117

3.1 Equivalence and Implication117

Equivalence of Statements117

Truth Tables120

DeMorgan’s Laws123

Implication125

If and Only If126

Important Concepts，Formulas，and Theorems129

Problems131

3.2 Variables and Quantifiers133

Variables and Universes133

Quantifiers134

Standard Notation for Quantification136

Statements about Variables138

Rewriting Statements to Encompass Larger Universes138

Proving Quantified Statements True or False139

Negation of Quantified Statements140

Implicit Quantification143

Proof of Quantified Statements144

Important Concepts，Formulas，and Theorems145

Problems147

3.3 Inference149

Direct Inference （Modus Ponens） and Proofs149

Rules of Inference for Direct Proofs151

Contrapositive Rule of Inference153

Proof by Contradiction155

Important Concepts，Formulas，and Theorems158

Problems159

CHAPTER 4 Induction，Recursion，and Recurrences161

4.1 Mathematical Induction161

Smallest Counterexamples161

The Principle of Mathematical Induction165

Strong Induction169

Induction in General171

A Recursive View of Induction173

Structural Induction176

Important Concepts，Formulas，and Theorems178

Problems180

4.2 Recursion，Recurrences，and Induction183

Recursion183

Examples of First-Order Linear Recurrences185

Iterating a Recurrence187

Geometric Series188

First-Order Linear Recurrences191

Important Concepts，Formulas，and Theorems195

Problems197

4.3 Growth Rates of Solutions to Recurrences198

Divide and Conquer Algorithms198

Recursion Trees201

Three Different Behaviors209

Important Concepts，Formulas，and Theorems210

Problems212

4.4 The Master Theorem214

Master Theorem214

Solving More General Kinds of Recurrences217

Extending the Master Theorem218

Important Concepts，Formulas，and Theorems220

Problems221

4.5 More General Kinds of Recurrences222

Recurrence Inequalities222

The Master Theorem for Inequalities223

A Wrinkle with Induction225

Further Wrinkles in Induction Proofs227

Dealing with Functions Other Than nc230

Important Concepts，Formulas，and Theorems232

Problems233

4.6 Recurrences and Selection235

The Idea of Selection235

A Recursive Selection Algorithm236

Selection without Knowing the Median in Advance237

An Algorithm to Find an Element in the Middle Half239

An Analysis of the Revised Selection Algorithm242

Uneven Divisions244

Important Concepts，Formulas，and Theorems246

Problems247

CHAPTER 5 Probability249

5.1 Introduction to Probability249

Why Study Probability？249

Some Examples of Probability Computations252

Complementary Probabilities253

Probability and Hashing254

The Uniform Probability Distribution256

Important Concepts，Formulas，and Theorems259

Problems260

5.2 Unions and Intersections262

The Probability of a Union of Events262

Principle of Inclusion and Exclusion for Probability265

The Principle of Inclusion and Exclusion for Counting271

Important Concepts，Formulas，and Theorems273

Problems274

5.3 Conditional Probability and Independence276

Conditional Probability276

Bayes’ Theorem280

Independence280

Independent Trials Processes282

Tree Diagrams284

Primality Testing288

Important Concepts，Formulas，and Theorems289

Problems290

5.4 Random Variables292

What Are Random Variables？292

Binomial Probabilities293

A Taste of Generating Functions295

Expected Value296

Expected Values of Sums and Numerical Multiples299

Indicator Random Variables302

The Number of Trials until the First Success304

Important Concepts，Formulas，and Theorems306

Problems307

5.5 Probability Calculations in Hashing310

Expected Number of Items per Location310

Expected Number of Empty Locations311

Expected Number of Collisions312

Expected Maximum Number of Elements in a Location of a Hash Table315

Important Concepts，Formulas，and Theorems320

Problems321

5.6 Conditional Expectations，Recurrences，and Algorithms325

When Running Times Depend on More than Size of Inputs325

Conditional Expected Values327

Randomized Algorithms329

Selection Revisited331

QuickSort333

A More Careful Analysis of RandomSelect336

Important Concepts，Formulas，and Theorems339

Problems340

5.7 Probability Distributions and Variance343

Distributions of Random Variables343

Variance346

Important Concepts，Formulas，and Theorems354

Problems355

CHAPTER 6 Graphs359

6.1 Graphs359

The Degree of a Vertex363

Connectivity365

Cycles367

Trees368

Other Properties of Trees368

Important Concepts，Formulas，and Theorems371

Problems373

6.2 Spanning Trees and Rooted Trees375

Spanning Trees375

Breadth-First Search377

Rooted Trees382

Important Concepts，Formulas，and Theorems386

Problems387

6.3 Eulerian and Hamiltonian Graphs389

Eulerian Tours and Trails389

Finding Eulerian Tours394

Hamiltonian Paths and Cycles395

NP-Complete Problems401

Proving That Problems Are NP-Complete403

Important Concepts，Formulas，and Theorems406

Problems407

6.4 Matching Theory410

The Idea of a Matching410

Making Matchings Bigger414

Matching in Bipartite Graphs417

Searching for Augmenting Paths in Bipartite Graphs417

The Augmentation-Cover Algorithm420

Efficient Algorithms426

Important Concepts，Formulas，and Theorems427

Problems428

6.5 Coloring and Planarity430

The Idea of Coloring430

Interval Graphs433

Planarity435

The Faces of a Planar Drawing437

The Five-Color Theorem441

Important Concepts，Formulas，and Theorems444

Problems445

APPENDIX A Derivation of the More General Master Theorem449

More General Recurrences449

Recurrences for General n451

Removing Floors and Ceilings452

Floors and Ceilings in the Stronger Version of the Master Theorem453

Proofs of Theorems453

Important Concepts，Formulas，and Theorems457

Problems458

APPENDIX B Answers and Hints to Selected Problems461

Bibliography477

Index479