Introductory Discrete Mathematics

Häftad, Engelska, 2000

249 kr

Tillfälligt slut

This concise, undergraduate-level text focuses on combinatorics, graph theory with applications to some standard network optimization problems, and algorithms. Geared toward mathematics and computer science majors, it emphasizes applications, offering more than 200 exercises to help students test their grasp of the material and providing answers to selected exercises. 1991 edition.

Produktinformation

Utgivningsdatum2000-02-01
Mått166 x 233 x 13 mm
Vikt386 g
FormatHäftad
SpråkEngelska
SerieDover Books on Computer Science
Antal sidor256
FörlagDover Publications Inc.
ISBN9780486691152

Tillhör följande kategorier

Preface0 Set Theory and Logic0.1 Introduction to Set Theory0.2 Functions and Relations0.3 Inductive Proofs and Recursive Definitions0.4 The Language of Logic0.5 Notes and References0.6 Exercises1 Combinatorics1.1 Two Basic Counting Rules1.2 Permutations1.3 Combinations1.4 More on Permutations and Combinations1.5 The Pigeonhole Principle1.6 The Inclusion-Exclusion Principle1.7 Summary of Results in Combinatorics1.8 Notes and References1.9 Exercises2 Generating Functions2.1 Introduction 2.2 Ordinary Generating Functions2.3 Exponential Generating Functions2.4 Notes and References2.5 Exercises3 Recurrence Relations3.1 Introduction3.2 Homogeneous Recurrence Relations3.3 Inhomogeneous Recurrence Relations3.4 Recurrence Relations and Generating Functions3.5 Analysis of Alogorithms3.6 Notes and References3.7 Exercises4 Graphs and Digraphs4.1 Introduction4.2 Adjacency Matrices and Incidence Matrices4.3 Joining in Graphs4.4 Reaching in Digraphs4.5 Testing Connectedness4.6 Strong Orientation of Graphs4.7 Notes and References4.8 Exercises5 More on Graphs and Digraphs5.1 Eulerian Paths and Eulerian Circuits5.2 Coding and de Bruijn Digraphs5.3 Hamiltonian Paths and Hamiltonian Cycles5.4 Applications of Hamiltonian Cycles5.5 Vertex Coloring and Planarity of Graphs5.6 Notes and References5.7 Exercises6 Trees and Their Applications6.1 Definitions and Properties6.2 Spanning Trees6.3 Binary Trees6.4 Notes and References6.5 Exercises7 Spanning Tree Problems7.1 More on Spanning Trees7.2 Kruskal's Greedy Algorithm7.3 Prim's Greedy Algorithm7.4 Comparison of the Two Algorithms7.5 Notes and References7.6 Exercises8 Shortest Path Problems8.1 Introduction8.2 Dijkstra's Algorithm8.3 Floyd-Warshall Algorithm8.4 Comparison of the Two Algorithms8.5 Notes and References8.6 ExercisesAppendix What is NP-Completeness?A.1 Problems and Their InstancesA.2 The Size of an InstanceA.3 Algorithm to Solve a ProblemA.4 Complexity of an AlgorithmA.5 "The "Big Oh" or the O(·) Notation"A.6 Easy Problems and Difficult ProblemsA.7 The Class P and the Class NPA.8 Polynomial Transformations and NP-CompletenessA.9 Coping with Hard ProblemsBibliographyAnswers to Selected ExercisesIndex