Discrete mathematicsPDF|Epub|txt|kindle电子书版本网盘下载

Discrete mathematicsPDF格式电子书版下载

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

1 Sets and Logic1

1.1 Sets2

1.2 Propositions14

1.3 Conditional Propositions and Logical Equivalence20

1.4 Arguments and Rules of Inference31

1.5 Quantifiers36

1.6 Nested Quantifiers49

Problem-Solving Corner：Quantifiers57

Chapter 1 Notes58

Chapter 1 Review58

Chapter 1 Self-Test60

Chapter 1 Computer Exercises60

2 Proofs62

2.1 Mathematical Systems，Direct Proofs，and Counterexamples63

2.2 More Methods of Proof72

Problem-Solving Corner：Proving Some Properties of Real Numbers83

2.3 Resolution Proofs +85

2.4 Mathematical Induction88

Problem-Solving Corner：Mathematical Induction100

2.5 Strong Form of Induction and the Well-Ordering Property102

Chapter 2 Notes109

Chapter 2 Review109

Chapter 2 Self-Test109

Chapter 2 Computer Exercises110

3 Functions，Sequences，and Relations111

3.1 Functions111

Problem-Solving Corner：Functions128

3.2 Sequences and Strings129

3.3 Relations141

3.4 Equivalence Relations151

Problem-Solving Corner：Equivalence Relations158

3.5 Matrices of Relations160

3.6 Relational Databases165

Chapter 3 Notes170

Chapter 3 Review170

Chapter 3 Self-Test171

Chapter 3 Computer Exercises172

4 Algorithms173

4.1 Introduction173

4.2 Examples of Algorithms177

4.3 Analysis of Algorithms184

Problem-Solving Corner：Design and Analysis of an Algorithm202

4.4 Recursive Algorithms204

Chapter 4 Notes211

Chapter 4 Review211

Chapter 4 Self-Test212

Chapter 4 Computer Exercises212

5Introduction to Number Theory214

5.1 Divisors214

5.2 Representations of Integers and Integer Algorithms224

5.3 The Euclidean Algorithm238

Problem-Solving Corner：Making Postage249

5.4 The RSA Public-Key Cryptosystem250

Chapter 5 Notes252

Chapter 5 Review253

Chapter 5 Self-Test253

Chapter 5 Computer Exercises254

6Counting Methods and the Pigeonhole Principle255

6.1 Basic Principles255

Problem-Solving Corner：Counting267

6.2 Permutations and Combinations269

Problem-Solving Corner：Combinations281

6.3 Generalized Permutations and Combinations283

6.4 Algorithms for Generating Permutations and Combinations289

6.5 Introduction to Discrete Probability +297

6.6 Discrete Probability Theory +301

6.7 Binomial Coefficients and Combinatorial Identities313

6.8 The Pigeonhole Principle319

Chapter 6 Notes324

Chapter 6 Review324

Chapter 6 Self-Test325

Chapter 6 Computer Exercises326

7Recurrence Relations327

7.1 Introduction327

7.2 Solving Recurrence Relations338

Problem-Solving Corner：Recurrence Relations350

7.3 Applications to the Analysis of Algorithms353

7.4 The Closest-Pair Problem +365

Chapter 7 Notes370

Chapter 7 Review371

Chapter 7 Self-Test371

Chapter 7 Computer Exercises372

8 Graph Theory373

8.1 Introduction373

8.2 Paths and Cycles384

Problem-Solving Corner：Graphs395

8.3 Hamiltonian Cycles and the Traveling Salesperson Problem396

8.4 A Shortest-Path Algorithm405

8.5 Representations of Graphs410

8.6 Isomorphisms of Graphs415

8.7 Planar Graphs422

8.8 Instant Insanity +429

Chapter 8 Notes433

Chapter 8 Review434

Chapter 8 Self-Test435

Chapter 8 Computer Exercises436

9 Trees438

9.1 Introduction438

9.2 Terminology and Characterizations of Trees445

Problem-Solving Corner：Trees450

9.3 Spanning Trees452

9.4 Minimal Spanning Trees459

9.5 Binary Trees465

9.6 Tree Traversals471

9.7 Decision Trees and the Minimum Time for Sorting477

9.8 Isomorphisms of Trees483

9.9 Game Trees +493

Chapter 9 Notes502

Chapter 9 Review502

Chapter 9 Self-Test503

Chapter 9 Computer Exercises505

10Network Models506

10.1 Introduction506

10.2 A Maximal Flow Algorithm511

10.3 The Max Flow，Min Cut Theorem519

10.4 Matching523

Problem-Solving Corner：Matching528

Chapter 10 Notes529

Chapter 10 Review530

Chapter 10 Self-Test530

Chapter 10 Computer Exercises531

11 Boolean Algebras and Combinatorial Circuits532

11.1 Combinatorial Circuits532

11.2 Properties of Combinatorial Circuits539

11.3 Boolean Algebras544

Problem-Solving Corner：Boolean Algebras549

11.4 Boolean Functions and Synthesis of Circuits551

11.5 Applications556

Chapter 11 Notes564

Chapter 11 Review565

Chapter 11 Self-Test565

Chapter 11 Computer Exercises567

12Automata，Grammars，and Languages568

12.1 Sequential Circuits and Finite-State Machines568

12.2 Finite-State Automata574

12.3 Languages and Grammars579

12.4 Nondeterministic Finite-State Automata589

12.5 Relationships Between Languages and Automata595

Chapter 12 Notes601

Chapter 12 Review602

Chapter 12 Self-Test602

Chapter 12 Computer Exercises603

Appendix605

A Matrices605

B Algebra Review609

C Pseudocode620

References627

Hints and Solutions to Selected Exercises633

Index735