Introductory Discrete Mathematics

Mehr zum Buch

This concise text introduces discrete mathematics for undergraduate students in computer science and mathematics. It emphasizes the importance of combinatorial mathematics and algebraic and logical structures, highlighting the connection between computer science and mathematics. Key topics include combinatorics, graph theory with applications to network optimization, and algorithms. Chapters 0–3 address fundamental operations with sets, mathematical induction, basic counting principles, permutations, combinations, the inclusion-exclusion principle, generating functions, recurrence relations, and an introduction to algorithm analysis. Applications are emphasized, and over 200 exercises at the end of these chapters help students assess their understanding. Chapters 4 and 5 explore graphs and digraphs, focusing on their connectedness properties and applications such as graph coloring, particularly in coding and related problems. The final chapters tackle two significant network optimization issues: the minimal spanning tree problem and the shortest distance problem. An appendix provides a brief, nontechnical overview of computational complexity and NP-completeness, rounding out the text's comprehensive approach to discrete mathematics.