离散数学 英文版2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

离散数学 英文版PDF格式电子书版下载

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

1 Sets and Logic1

1.1 Sets2

1.2 Propositions14

1.3 Conditional Propositions and Logical Equivalence21

1.4 Arguments and Rules of Inference31

1.5 Quantifiers36

1.6 Nested Quantifiers51

Problem-Solving Corner:Quantifiers60

Notes62

Chapter Review62

Chapter Self-Test63

Computer Exercises64

2 Proofs66

2.1 Mathematical Systems,Direct Proofs,and Counterexamples67

2.2 More Methods of Proof76

Problem-Solving Corner:Proving Some Properties of Real Numbers87

2.3 Resolution Proofs90

2.4 Mathematical Induction93

Problem-Solving Corner:Mathematical Induction106

2.5 Strong Form of Induction and the Well-Ordering Property108

Notes115

Chapter Review115

Chapter Self-Test116

Computer Exercises116

3 Functions,Sequences,and Relations117

3.1 Functions117

Problem-Solving Corner:Functions135

3.2 Sequences and Strings136

3.3 Relations148

3.4 Equivalence Relations159

Problem-Solving Corner:Equivalence Relations166

3.5 Matrices of Relations168

3.6 Relational Databases173

Notes178

Chapter Review178

Chapter Self-Test179

Computer Exercises180

4 Algorithms181

4.1 Introduction181

4.2 Examples of Algorithms186

4.3 Analysis of Algorithms193

Problem-Solving Corner:Design and Analysis of an Algorithm211

4.4 Recursive Algorithms213

Notes220

Chapter Review221

Chapter Self-Test221

Computer Exercises222

5 Introduction to Number Theory223

5.1 Divisors223

5.2 Representations of Integers and Integer Algorithms234

5.3 The Euclidean Algorithm248

Problem-Solving Corner:Making Postage259

5.4 The RSA Public-Key Cryptosystem260

Notes263

Chapter Review263

Chapter Self-Test263

Computer Exercises264

6 Counting Methods and the Pigeonhole Principle265

6.1 Basic Principles265

Problem-Solving Corner:Counting277

6.2 Permutations and Combinations278

Problem-Solving Corner:Combinations291

6.3 Generalized Permutations and Combinations293

6.4 Algorithms for Generating Permutations and Combinations299

6.5 Introduction to Discrete Probability305

6.6 Discrete Probability Theory309

6.7 Binomial Coefficients and Combinatorial Identities320

6.8 The Pigeonhole Principle325

Notes330

Chapter Review330

Chapter Self-Test330

Computer Exercises332

7 Recurrence Relations333

7.1 Introduction333

7.2 Solving Recurrence Relations345

Problem-Solving Corner:Recurrence Relations358

7.3 Applications to the Analysis of Algorithms361

Notes373

Chapter Review373

Chapter Self-Test374

Computer Exercises374

8 Graph Theory376

8.1 Introduction377

8.2 Paths and Cycles388

Problem-Solving Corner:Graphs399

8.3 Hamiltonian Cycles and the Traveling Salesperson Problem400

8.4 A Shortest-Path Algorithm407

8.5 Representations of Graphs412

8.6 Isomorphisms of Graphs417

8.7 Planar Graphs425

8.8 Instant Insanity431

Notes435

Chapter Review436

Chapter Self-Test437

Computer Exercises438

9 Trees440

9.1 Introduction440

9.2 Terminology and Characterizations of Trees448

Problem-Solving Corner:Trees453

9.3 Spanning Trees454

9.4 Minimal Spanning Trees461

9.5 Binary Trees467

9.6 Tree Traversals474

9.7 Decision Trees and the Minimum Time for Sorting480

9.8 Isomorphisms of Trees486

9.9 Game Trees496

Notes505

Chapter Review505

Chapter Self-Test506

Computer Exercises508

10 Network Models510

10.1 Introduction510

10.2 A Maximal Flow Algorithm516

10.3 The Max Flow,Min Cut Theorem524

10.4 Matching528

Problem-Solving Corner:Matching533

Notes534

Chapter Review535

Chapter Self-Test536

Computer Exercises536

11 Boolean Algebras and Combinatorial Circuits537

11.1 Combinatorial Circuits537

11.2 Properties of Combinatorial Circuits544

11.3 Boolean Algebras549

Problem-Solving Corner:Boolean Algebras554

11.4 Boolean Functions and Synthesis of Circuits556

11.5 Applications561

Notes570

Chapter Review570

Chapter Self-Test571

Computer Exercises572

12 Automata,Grammars,and Languages573

12.1 Sequential Circuits and Finite-State Machines573

12.2 Finite-State Automata579

12.3 Languages and Grammars585

12.4 Nondeterministic Finite-State Automata595

12.5 Relationships Between Languages and Automata602

Notes608

Chapter Review609

Chapter Self-Test609

Computer Exercises611

13 Computational Geometry612

13.1 The Closest-Pair Problem612

13.2 An Algorithm to Compute the Convex Hull617

Notes625

Chapter Review625

Chapter Self-Test625

Computer Exercises626

Appendix627

A Matrices627

B Algebra Review631

C Pseudocode644

References650

Hints and Solutions to Selected Exercises655

Index754