Discrete Mathematics: International Edition
Autor Richard Johnsonbaughen Limba Engleză Paperback – 14 ian 2008
Focused on helping students understand and construct proofs and expanding their mathematical maturity, this best-selling text is an accessible introduction to discrete mathematics. Johnsonbaugh’s algorithmic approach emphasizes problem-solving techniques. The Seventh Edition reflects user and reviewer feedback on both content and organization.
Preț: 746.91 lei
Preț vechi: 878.71 lei
-15% Nou
Puncte Express: 1120
Preț estimativ în valută:
143.01€ • 148.92$ • 118.65£
143.01€ • 148.92$ • 118.65£
Cartea se retipărește
Doresc să fiu notificat când acest titlu va fi disponibil:
Se trimite...
Preluare comenzi: 021 569.72.76
Specificații
ISBN-13: 9780131354302
ISBN-10: 0131354302
Pagini: 792
Dimensiuni: 203 x 254 x 30 mm
Greutate: 1.23 kg
Ediția:7Nouă
Editura: Pearson Education
Colecția Pearson Education
Locul publicării:Upper Saddle River, United States
ISBN-10: 0131354302
Pagini: 792
Dimensiuni: 203 x 254 x 30 mm
Greutate: 1.23 kg
Ediția:7Nouă
Editura: Pearson Education
Colecția Pearson Education
Locul publicării:Upper Saddle River, United States
Cuprins
1 Sets and Logic
1.1 Sets
1.2 Propositions
1.3 Conditional Propositions and Logical Equivalence
1.4 Arguments and Rules of Inference
1.5 Quantifiers
1.6 Nested Quantifiers
Problem-Solving Corner: Quantifiers
2 Proofs
2.1 Mathematical Systems, Direct Proofs, and Counterexamples
2.2 More Methods of Proof
Problem-Solving Corner: Proving Some Properties of Real Numbers
2.3 Resolution Proofs
2.4 Mathematical Induction
Problem-Solving Corner: Mathematical Induction
2.5 Strong Form of Induction and the Well-Ordering Property Notes Chapter Review Chapter Self-Test Computer Exercises
3 Functions, Sequences, and Relations
3.1 Functions
Problem-Solving Corner: Functions
3.2 Sequences and Strings
3.3 Relations
3.4 Equivalence Relations
Problem-Solving Corner: Equivalence Relations
3.5 Matrices of Relations
3.6 Relational Databases
4 Algorithms
4.1 Introduction
4.2 Examples of Algorithms
4.3 Analysis of Algorithms
Problem-Solving Corner: Design and Analysis of an Algorithm
4.4 Recursive Algorithms
5 Introduction to Number Theory
5.1 Divisors
5.2 Representations of Integers and Integer Algorithms
5.3 The Euclidean Algorithm
Problem-Solving Corner: Making Postage
5.4 The RSA Public-Key Cryptosystem
6 Counting Methods and the Pigeonhole Principle
6.1 Basic Principles
Problem-Solving Corner: Counting
6.2 Permutations and Combinations
Problem-Solving Corner: Combinations
6.3 Generalized Permutations and Combinations
6.4 Algorithms for Generating Permutations and Combinations
6.5 Introduction to Discrete Probability
6.6 Discrete Probability Theory
6.7 Binomial Coefficients and Combinatorial Identities
6.8 The Pigeonhole Principle
7 Recurrence Relations
7.1 Introduction
7.2 Solving Recurrence Relations
Problem-Solving Corner: Recurrence Relations
7.3 Applications to the Analysis of Algorithms
8 Graph Theory
8.1 Introduction
8.2 Paths and Cycles
Problem-Solving Corner: Graphs
8.3 Hamiltonian Cycles and the Traveling Salesperson Problem
8.4 A Shortest-Path Algorithm
8.5 Representations of Graphs
8.6 Isomorphisms of Graphs
8.7 Planar Graphs
8.8 Instant Insanity
9 Trees
9.1 Introduction
9.2 Terminology and Characterizations of Trees
Problem-Solving Corner: Trees
9.3 Spanning Trees
9.4 Minimal Spanning Trees
9.5 Binary Trees
9.6 Tree Traversals
9.7 Decision Trees and the Minimum Time for Sorting
9.8 Isomorphisms of Trees
9.9 Game Trees
10 Network Models
10.1 Introduction
10.2 A Maximal Flow Algorithm
10.3 The Max Flow, Min Cut Theorem
10.4 Matching
Problem-Solving Corner: Matching
11 Boolean Algebras and Combinatorial Circuits
11.1 Combinatorial Circuits
11.2 Properties of Combinatorial Circuits
11.3 Boolean Algebras
Problem-Solving Corner: Boolean Algebras
11.4 Boolean Functions and Synthesis of Circuits
11.5 Applications
12 Automata, Grammars, and Languages
12.1 Sequential Circuits and Finite-State Machines
12.2 Finite-State Automata
12.3 Languages and Grammars
12.4 Nondeterministic Finite-State Automata
12.5 Relationships Between Languages and Automata
13 Computational Geometry
13.1 The Closest-Pair Problem
13.2 An Algorithm to Compute the Convex Hull
Appendix
A Matrices
B Algebra Review
C Pseudocode
References
Hints and Solutions to Selected Exercises Index
1.1 Sets
1.2 Propositions
1.3 Conditional Propositions and Logical Equivalence
1.4 Arguments and Rules of Inference
1.5 Quantifiers
1.6 Nested Quantifiers
Problem-Solving Corner: Quantifiers
2 Proofs
2.1 Mathematical Systems, Direct Proofs, and Counterexamples
2.2 More Methods of Proof
Problem-Solving Corner: Proving Some Properties of Real Numbers
2.3 Resolution Proofs
2.4 Mathematical Induction
Problem-Solving Corner: Mathematical Induction
2.5 Strong Form of Induction and the Well-Ordering Property Notes Chapter Review Chapter Self-Test Computer Exercises
3 Functions, Sequences, and Relations
3.1 Functions
Problem-Solving Corner: Functions
3.2 Sequences and Strings
3.3 Relations
3.4 Equivalence Relations
Problem-Solving Corner: Equivalence Relations
3.5 Matrices of Relations
3.6 Relational Databases
4 Algorithms
4.1 Introduction
4.2 Examples of Algorithms
4.3 Analysis of Algorithms
Problem-Solving Corner: Design and Analysis of an Algorithm
4.4 Recursive Algorithms
5 Introduction to Number Theory
5.1 Divisors
5.2 Representations of Integers and Integer Algorithms
5.3 The Euclidean Algorithm
Problem-Solving Corner: Making Postage
5.4 The RSA Public-Key Cryptosystem
6 Counting Methods and the Pigeonhole Principle
6.1 Basic Principles
Problem-Solving Corner: Counting
6.2 Permutations and Combinations
Problem-Solving Corner: Combinations
6.3 Generalized Permutations and Combinations
6.4 Algorithms for Generating Permutations and Combinations
6.5 Introduction to Discrete Probability
6.6 Discrete Probability Theory
6.7 Binomial Coefficients and Combinatorial Identities
6.8 The Pigeonhole Principle
7 Recurrence Relations
7.1 Introduction
7.2 Solving Recurrence Relations
Problem-Solving Corner: Recurrence Relations
7.3 Applications to the Analysis of Algorithms
8 Graph Theory
8.1 Introduction
8.2 Paths and Cycles
Problem-Solving Corner: Graphs
8.3 Hamiltonian Cycles and the Traveling Salesperson Problem
8.4 A Shortest-Path Algorithm
8.5 Representations of Graphs
8.6 Isomorphisms of Graphs
8.7 Planar Graphs
8.8 Instant Insanity
9 Trees
9.1 Introduction
9.2 Terminology and Characterizations of Trees
Problem-Solving Corner: Trees
9.3 Spanning Trees
9.4 Minimal Spanning Trees
9.5 Binary Trees
9.6 Tree Traversals
9.7 Decision Trees and the Minimum Time for Sorting
9.8 Isomorphisms of Trees
9.9 Game Trees
10 Network Models
10.1 Introduction
10.2 A Maximal Flow Algorithm
10.3 The Max Flow, Min Cut Theorem
10.4 Matching
Problem-Solving Corner: Matching
11 Boolean Algebras and Combinatorial Circuits
11.1 Combinatorial Circuits
11.2 Properties of Combinatorial Circuits
11.3 Boolean Algebras
Problem-Solving Corner: Boolean Algebras
11.4 Boolean Functions and Synthesis of Circuits
11.5 Applications
12 Automata, Grammars, and Languages
12.1 Sequential Circuits and Finite-State Machines
12.2 Finite-State Automata
12.3 Languages and Grammars
12.4 Nondeterministic Finite-State Automata
12.5 Relationships Between Languages and Automata
13 Computational Geometry
13.1 The Closest-Pair Problem
13.2 An Algorithm to Compute the Convex Hull
Appendix
A Matrices
B Algebra Review
C Pseudocode
References
Hints and Solutions to Selected Exercises Index
Caracteristici
• Strong emphasis on reading and writing proofs – Illustrates most proofs of theorems with annotated figures to provide additional explanation and insight into the proofs.
• Extensive discussion of algorithms, recursive algorithms, and the analysis of algorithms – The algorithms are written in a flexible form of pseudocode, which resembles currently popular languages such as C, C++, and Java.
• Over 500 worked examples throughout the text.
• Over 3500 exercises – Approximately one third have answers at the back of the book.
• Extensive applications with an emphasis on computer science.
• Emphasis on the interplay among the various topics – For example, mathematical induction is closely tied to recursive algorithms; the Fibonacci sequence is used in the analysis of the Euclidean algorithm; many exercises throughout the book require mathematical induction; demonstrations of how to characterize the components of a graph by defining an equivalence relation on the set of vertices; and more.
• Figures and tables – Illustrate concepts, show how algorithms work, elucidate proofs, and motivate the material. Figure captions provide additional explanation and insight into figures accompanying proofs.
• Summaries of the mathematical and algorithm notation used in the book on the inside covers.
• Extensive discussion of algorithms, recursive algorithms, and the analysis of algorithms – The algorithms are written in a flexible form of pseudocode, which resembles currently popular languages such as C, C++, and Java.
• Over 500 worked examples throughout the text.
• Over 3500 exercises – Approximately one third have answers at the back of the book.
• Extensive applications with an emphasis on computer science.
• Emphasis on the interplay among the various topics – For example, mathematical induction is closely tied to recursive algorithms; the Fibonacci sequence is used in the analysis of the Euclidean algorithm; many exercises throughout the book require mathematical induction; demonstrations of how to characterize the components of a graph by defining an equivalence relation on the set of vertices; and more.
• Figures and tables – Illustrate concepts, show how algorithms work, elucidate proofs, and motivate the material. Figure captions provide additional explanation and insight into figures accompanying proofs.
• Summaries of the mathematical and algorithm notation used in the book on the inside covers.
Caracteristici noi
• Increased number of examples and exercises throughout:
– Also expands discussion and adds motivation for most of the examples.
– More examples and exercises are included to highlight common errors
• Expanded treatment of problem solving:
– Problem-Solving Tips sections include expanded advice and examples on how to do proofs, how to write up proofs, and common errors in proofs.
– Two new Problem-Solving Corners have been added, one on quantifiers, the other on proofs (see Proving Some Properties of Real Numbers).
• Expanded discussion of proof writing:
– Sections 2.1 and 2.2 are new extended sections on mathematical systems and proof techniques.
– There are expanded subsections on proofs of equivalence and existence proofs (including constructive and nonconstructive existence proofs).
– Nearly every proof is preceded by a Discussion section and/or accompanied by a figure.
Reorganization of introductory chapters:
– The first chapter from the previous edition (Logic and Proofs) has been divided into two chapters – Logic (Chapter 1) and Proofs (Chapter 2).
– Except for the section on sets, Chapters 2 (The Language of Mathematics) and 3 (Relations) in the sixth edition have been combined into Chapter 3 (Functions, Sequences, and Relations) in this revision.
• Earlier introduction of sets – Now the first section of the book.
– Permits the use of set terminology throughout the book.
– Makes sets available for proofs in examples and exercises, thus providing more interesting examples earlier than in the previous editions.
• Content-specific changes:
– The description and notation for integers (Z, Z+ , Z- , Znonneg), rational numbers (with Z replaced by Q), and real numbers (with Z replaced by R) are introduced early (in Section 1.1, Sets).
– Proofs, rather than sketches of proofs as in the sixth edition, are provided for Theorems 5.1.17 and 5.1.22, which give the greatest common divisor and least common multiple of two integers given their prime factorizations.
– Recursive algorithms are given (Algorithms 5.3.9 and 5.3.10) to compute the greatest common divisor of two integers a and b, gcd(a, b), and to compute integers s and t satisfying gcd(a, b) = sa + tb.
– The Inclusion-Exclusion Principle has been added to Section 6.1.
– Internet addressing is now included in Section 6.1.
– Several practice exercises have been added to Section 6.1 that specifically say to use either the Multiplication Principle or the Addition Principle. These exercises precede other exercises that require the reader to figure out which Principle to use or require using both Principles.
– The section on Generalized Permutations and Combinations (Section 6.6 in the sixth edition) now follows Sections 6.1 and 6.2 (Basic Principles, Permutations and Combinations) since generalized permutations and combinations are so closely related to the material in Sections 6.1 and 6.2.
– More exercises on graph isomorphism have been added (Section 8.6). The exercises have been divided into those that ask for a proof that two given graphs are isomorphic, those that ask for a proof that two given graphs are not isomorphic, and those that ask the reader to determine, with a proof, whether two given graphs are isomorphic.
– In Section 9.3, there are several new backtracking exercises including the popular Sudoku puzzle.
• Updated Web site at http://condor.depaul.edu/~rjohnson/dm7th/
– Includes expanded explanations of difficult material and links to other sites for additional information about discrete mathematics topics.
– A WWW icon signals that an expanded explanation or a link is at the book’s web site.
– Also includes supplementary material, computer programs, and an errata list.
– Also expands discussion and adds motivation for most of the examples.
– More examples and exercises are included to highlight common errors
• Expanded treatment of problem solving:
– Problem-Solving Tips sections include expanded advice and examples on how to do proofs, how to write up proofs, and common errors in proofs.
– Two new Problem-Solving Corners have been added, one on quantifiers, the other on proofs (see Proving Some Properties of Real Numbers).
• Expanded discussion of proof writing:
– Sections 2.1 and 2.2 are new extended sections on mathematical systems and proof techniques.
– There are expanded subsections on proofs of equivalence and existence proofs (including constructive and nonconstructive existence proofs).
– Nearly every proof is preceded by a Discussion section and/or accompanied by a figure.
Reorganization of introductory chapters:
– The first chapter from the previous edition (Logic and Proofs) has been divided into two chapters – Logic (Chapter 1) and Proofs (Chapter 2).
– Except for the section on sets, Chapters 2 (The Language of Mathematics) and 3 (Relations) in the sixth edition have been combined into Chapter 3 (Functions, Sequences, and Relations) in this revision.
• Earlier introduction of sets – Now the first section of the book.
– Permits the use of set terminology throughout the book.
– Makes sets available for proofs in examples and exercises, thus providing more interesting examples earlier than in the previous editions.
• Content-specific changes:
– The description and notation for integers (Z, Z+ , Z- , Znonneg), rational numbers (with Z replaced by Q), and real numbers (with Z replaced by R) are introduced early (in Section 1.1, Sets).
– Proofs, rather than sketches of proofs as in the sixth edition, are provided for Theorems 5.1.17 and 5.1.22, which give the greatest common divisor and least common multiple of two integers given their prime factorizations.
– Recursive algorithms are given (Algorithms 5.3.9 and 5.3.10) to compute the greatest common divisor of two integers a and b, gcd(a, b), and to compute integers s and t satisfying gcd(a, b) = sa + tb.
– The Inclusion-Exclusion Principle has been added to Section 6.1.
– Internet addressing is now included in Section 6.1.
– Several practice exercises have been added to Section 6.1 that specifically say to use either the Multiplication Principle or the Addition Principle. These exercises precede other exercises that require the reader to figure out which Principle to use or require using both Principles.
– The section on Generalized Permutations and Combinations (Section 6.6 in the sixth edition) now follows Sections 6.1 and 6.2 (Basic Principles, Permutations and Combinations) since generalized permutations and combinations are so closely related to the material in Sections 6.1 and 6.2.
– More exercises on graph isomorphism have been added (Section 8.6). The exercises have been divided into those that ask for a proof that two given graphs are isomorphic, those that ask for a proof that two given graphs are not isomorphic, and those that ask the reader to determine, with a proof, whether two given graphs are isomorphic.
– In Section 9.3, there are several new backtracking exercises including the popular Sudoku puzzle.
• Updated Web site at http://condor.depaul.edu/~rjohnson/dm7th/
– Includes expanded explanations of difficult material and links to other sites for additional information about discrete mathematics topics.
– A WWW icon signals that an expanded explanation or a link is at the book’s web site.
– Also includes supplementary material, computer programs, and an errata list.