Издательство John Wiley, 2002, -552 pp.
Here is a first-year course in discrete mathematics, requiring no calculus or computer programming experience, for students on computer science and mathematics courses. The approach stresses finding efficient algorithms, rather than existential results. It provides an introduction to constructing proofs (especially by induction), and an introduction to algorithmic problem solving. All algorithms are presented in English, in a format compatible with the PASCAL programming language. The text contains many exercises, with answers at the back of the book (detailed solutions being supplied for difficult problems).
1 Sets and Algorithms: Introduction, Binary Arithmetic and the Magic Trick Revisited, Algorithms, Between Decimal and Binary, Set Theory and the Magic Trick, Pictures of Sets, Subsets, Set Cardinality and Counting
Functions, Boolean Functions and Boolean Algebra, A Look Back
2 Arithmetic: Introduction, Exponentiation, A First Look, Induction, Three Inductive Proofs, Exponentiation Revisited, How Good is Fast Exponentiation?, How Logarithms Grow, The "Big Oh" Notation, 2^n does not equal O(p(n)): Proof by Contradiction, Good and Bad Algorithms, Another Look Back
3 Arithmetic of Sets: Introduction, Binomial Coefficients, Subsets of Sets, Permutations, An Application of Permutations: The Game of Mastermind, The Binomial Theorem, Important Subsets
4 Number Theory: Greatest Common Divisors, Another Look at Complexities, The Euclidean Algorithm, Fibonacci Numbers, The Complexity of the Euclidean Algorithm, Congruences and Equivalence Relations, An Application: Public Key Encryption Schemes, The Dividends
5 Graph Theory: Building the LAN, Graphs, Trees and the LAN, A Good Minimum-Weight Spanning Tree Algorithm, An Ode to Greed, Graphical Highlights
6 Searching and Sorting: Introduction: Record Keeping, Searching a Sorted File, Sorting a File, Search Trees, Lower Bounds on Sorting, Recursion, MERGESORT, Sorting It All Out
7 Recurrence Relations: Beginnings of Sequences, Iteration and Induction, Linear Homogeneous Recurrence Relations with Constant Coefficients, LHRRWCCs with Multiple Roots: More About Rabbits, Divide-and-Conquer Recurrence Relations, Recurring Thoughts
8 More Graph Theory: Minimum-Distance Trees, Eulerian Cycles, Hamiltonian Cycles, Minimum-Weight Hamiltonian Cycles, Graph Coloring and an Application to Storage Allocation
Solutions to Questions
Here is a first-year course in discrete mathematics, requiring no calculus or computer programming experience, for students on computer science and mathematics courses. The approach stresses finding efficient algorithms, rather than existential results. It provides an introduction to constructing proofs (especially by induction), and an introduction to algorithmic problem solving. All algorithms are presented in English, in a format compatible with the PASCAL programming language. The text contains many exercises, with answers at the back of the book (detailed solutions being supplied for difficult problems).
1 Sets and Algorithms: Introduction, Binary Arithmetic and the Magic Trick Revisited, Algorithms, Between Decimal and Binary, Set Theory and the Magic Trick, Pictures of Sets, Subsets, Set Cardinality and Counting
Functions, Boolean Functions and Boolean Algebra, A Look Back
2 Arithmetic: Introduction, Exponentiation, A First Look, Induction, Three Inductive Proofs, Exponentiation Revisited, How Good is Fast Exponentiation?, How Logarithms Grow, The "Big Oh" Notation, 2^n does not equal O(p(n)): Proof by Contradiction, Good and Bad Algorithms, Another Look Back
3 Arithmetic of Sets: Introduction, Binomial Coefficients, Subsets of Sets, Permutations, An Application of Permutations: The Game of Mastermind, The Binomial Theorem, Important Subsets
4 Number Theory: Greatest Common Divisors, Another Look at Complexities, The Euclidean Algorithm, Fibonacci Numbers, The Complexity of the Euclidean Algorithm, Congruences and Equivalence Relations, An Application: Public Key Encryption Schemes, The Dividends
5 Graph Theory: Building the LAN, Graphs, Trees and the LAN, A Good Minimum-Weight Spanning Tree Algorithm, An Ode to Greed, Graphical Highlights
6 Searching and Sorting: Introduction: Record Keeping, Searching a Sorted File, Sorting a File, Search Trees, Lower Bounds on Sorting, Recursion, MERGESORT, Sorting It All Out
7 Recurrence Relations: Beginnings of Sequences, Iteration and Induction, Linear Homogeneous Recurrence Relations with Constant Coefficients, LHRRWCCs with Multiple Roots: More About Rabbits, Divide-and-Conquer Recurrence Relations, Recurring Thoughts
8 More Graph Theory: Minimum-Distance Trees, Eulerian Cycles, Hamiltonian Cycles, Minimum-Weight Hamiltonian Cycles, Graph Coloring and an Application to Storage Allocation
Solutions to Questions