Discrete mathematics for computer scientistsPDF电子书下载

CHAPTER 1 Counting 1

1.1 Basic Counting 1

The Sum Principle 1

Abstraction 3

Summing Consecutive Integers 3

The Product Principle 4

Two-Element Subsets 6

Important Concepts，Formulas，and Theorems 7

Problems 8

1.2 Counting Lists，Permutations，and Subsets 10

Using the Sum and Product Principles 10

Lists and Functions 12

The Bijection Principle 14

k-Element Permutations of a Set 15

Counting Subsets of a Set 16

Important Concepts，Formulas，and Theorems 18

Problems 20

1.3 Binomial Coefficients 22

Pascal’s Triangle 22

A Proof Using the Sum Principle 24

The Binomial Theorem 26

Labeling and Trinomial Coefficients 28

Important Concepts，Formulas，and Theorems 29

Problems 30

1.4 Relations 32

What Is a Relation？ 32

Functions as Relations 33

Properties of Relations 33

Equivalence Relations 36

Partial and Total Orders 39

Important Concepts，Formulas，and Theorems 41

Problems 42

1.5 Using Equivalence Relations in Counting 43

The Symmetry Principle 43

Equivalence Relations 45

The Quotient Principle 46

Equivalence Class Counting 46

Multi sets 48

The Bookcase Arrangement Problem 50

The Number of k-Element Multisets of an n-Element Set 51

Using the Quotient Principle to Explain a Quotient 52

Important Concepts，Formulas，and Theorems 53

Problems 54

CHAPTER 2 Cryptography and Number Theory 59

2.1 Cryptography and Modular Arithmetic 59

Introduction to Cryptography 59

Private-Key Cryptography 60

Public-Key Cryptosystems 63

Arithmetic Modulo n 65

Cryptography Using Addition mod n 68

Cryptography Using Multiplication mod n 69

Important Concepts，Formulas，and Theorems 71

Problems 72

2.2 Inverses and Greatest Common Divisors 75

Solutions to Equations and Inverses mod n 75

Inverses mod n 76

Converting Modular Equations to Normal Equations 79

Greatest Common Divisors 80

Euclid’s Division Theorem 81

Euclid’s GCD Algorithm 84

Extended GCD Algorithm 85

Computing Inverses 88

Important Concepts，Formulas，and Theorems 89

Problems 90

2.3 The RSA Cryptosystem 93

Exponentiation mod n 93

The Rules of Exponents 93

Fermat’s Little Theorem 96

The RSA Cryptosystem 97

The Chinese Remainder Theorem 101

Important Concepts，Formulas，and Theorems 102

Problems 104

2.4 Details of the RSA Cryptosystem 106

Practical Aspects of Exponentiation mod n 106

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

How Hard Is Factoring？ 110

Finding Large Primes 110

Important Concepts，Formulas，and Theorems 113

Problems 114

CHAPTER 3 Reflections on Logic and Proof 117

3.1 Equivalence and Implication 117

Equivalence of Statements 117

Truth Tables 120

DeMorgan’s Laws 123

Implication 125

If and Only If 126

Important Concepts，Formulas，and Theorems 129

Problems 131

3.2 Variables and Quantifiers 133

Variables and Universes 133

Quantifiers 134

Standard Notation for Quantification 136

Statements about Variables 138

Rewriting Statements to Encompass Larger Universes 138

Proving Quantified Statements True or False 139

Negation of Quantified Statements 140

Implicit Quantification 143

Proof of Quantified Statements 144

Important Concepts，Formulas，and Theorems 145

Problems 147

3.3 Inference 149

Direct Inference （Modus Ponens） and Proofs 149

Rules of Inference for Direct Proofs 151

Contrapositive Rule of Inference 153

Proof by Contradiction 155

Important Concepts，Formulas，and Theorems 158

Problems 159

CHAPTER 4 Induction，Recursion，and Recurrences 161

4.1 Mathematical Induction 161

Smallest Counterexamples 161

The Principle of Mathematical Induction 165

Strong Induction 169

Induction in General 171

A Recursive View of Induction 173

Structural Induction 176

Important Concepts，Formulas，and Theorems 178

Problems 180

4.2 Recursion，Recurrences，and Induction 183

Recursion 183

Examples of First-Order Linear Recurrences 185

Iterating a Recurrence 187

Geometric Series 188

First-Order Linear Recurrences 191

Important Concepts，Formulas，and Theorems 195

Problems 197

4.3 Growth Rates of Solutions to Recurrences 198

Divide and Conquer Algorithms 198

Recursion Trees 201

Three Different Behaviors 209

Important Concepts，Formulas，and Theorems 210

Problems 212

4.4 The Master Theorem 214

Master Theorem 214

Solving More General Kinds of Recurrences 217

Extending the Master Theorem 218

Important Concepts，Formulas，and Theorems 220

Problems 221

4.5 More General Kinds of Recurrences 222

Recurrence Inequalities 222

The Master Theorem for Inequalities 223

A Wrinkle with Induction 225

Further Wrinkles in Induction Proofs 227

Dealing with Functions Other Than nc 230

Important Concepts，Formulas，and Theorems 232

Problems 233

4.6 Recurrences and Selection 235

The Idea of Selection 235

A Recursive Selection Algorithm 236

Selection without Knowing the Median in Advance 237

An Algorithm to Find an Element in the Middle Half 239

An Analysis of the Revised Selection Algorithm 242

Uneven Divisions 244

Important Concepts，Formulas，and Theorems 246

Problems 247

CHAPTER 5 Probability 249

5.1 Introduction to Probability 249

Why Study Probability？ 249

Some Examples of Probability Computations 252

Complementary Probabilities 253

Probability and Hashing 254

The Uniform Probability Distribution 256

Important Concepts，Formulas，and Theorems 259

Problems 260

5.2 Unions and Intersections 262

The Probability of a Union of Events 262

Principle of Inclusion and Exclusion for Probability 265

The Principle of Inclusion and Exclusion for Counting 271

Important Concepts，Formulas，and Theorems 273

Problems 274

5.3 Conditional Probability and Independence 276

Conditional Probability 276

Bayes’ Theorem 280

Independence 280

Independent Trials Processes 282

Tree Diagrams 284

Primality Testing 288

Important Concepts，Formulas，and Theorems 289

Problems 290

5.4 Random Variables 292

What Are Random Variables？ 292

Binomial Probabilities 293

A Taste of Generating Functions 295

Expected Value 296

Expected Values of Sums and Numerical Multiples 299

Indicator Random Variables 302

The Number of Trials until the First Success 304

Important Concepts，Formulas，and Theorems 306

Problems 307

5.5 Probability Calculations in Hashing 310

Expected Number of Items per Location 310

Expected Number of Empty Locations 311

Expected Number of Collisions 312

Expected Maximum Number of Elements in a Location of a Hash Table 315

Important Concepts，Formulas，and Theorems 320

Problems 321

5.6 Conditional Expectations，Recurrences，and Algorithms 325

When Running Times Depend on More than Size of Inputs 325

Conditional Expected Values 327

Randomized Algorithms 329

Selection Revisited 331

QuickSort 333

A More Careful Analysis of RandomSelect 336

Important Concepts，Formulas，and Theorems 339

Problems 340

5.7 Probability Distributions and Variance 343

Distributions of Random Variables 343

Variance 346

Important Concepts，Formulas，and Theorems 354

Problems 355

CHAPTER 6 Graphs 359

6.1 Graphs 359

The Degree of a Vertex 363

Connectivity 365

Cycles 367

Trees 368

Other Properties of Trees 368

Important Concepts，Formulas，and Theorems 371

Problems 373

6.2 Spanning Trees and Rooted Trees 375

Spanning Trees 375

Breadth-First Search 377

Rooted Trees 382

Important Concepts，Formulas，and Theorems 386

Problems 387

6.3 Eulerian and Hamiltonian Graphs 389

Eulerian Tours and Trails 389

Finding Eulerian Tours 394

Hamiltonian Paths and Cycles 395

NP-Complete Problems 401

Proving That Problems Are NP-Complete 403

Important Concepts，Formulas，and Theorems 406

Problems 407

6.4 Matching Theory 410

The Idea of a Matching 410

Making Matchings Bigger 414

Matching in Bipartite Graphs 417

Searching for Augmenting Paths in Bipartite Graphs 417

The Augmentation-Cover Algorithm 420

Efficient Algorithms 426

Important Concepts，Formulas，and Theorems 427

Problems 428

6.5 Coloring and Planarity 430

The Idea of Coloring 430

Interval Graphs 433

Planarity 435

The Faces of a Planar Drawing 437

The Five-Color Theorem 441

Important Concepts，Formulas，and Theorems 444

Problems 445

APPENDIX A Derivation of the More General Master Theorem 449

More General Recurrences 449

Recurrences for General n 451

Removing Floors and Ceilings 452

Floors and Ceilings in the Stronger Version of the Master Theorem 453

Proofs of Theorems 453

Important Concepts，Formulas，and Theorems 457

Problems 458

APPENDIX B Answers and Hints to Selected Problems 461

Bibliography 477

Index 479