Discrete Mathematics with Computer Science Applications
This formal text should be on every computer engineer's bookshelf. This is an introductory text to introduce
discrete mathematics and its computer science applications. You only need high school algebra to understand
this text. This work provides a set of useful tools for modeling problems in computer science. Each chapter
has numerous examples and self tests. Solutions are provided in the book.
A glance at the contents below will assure you of how thorough the book is in its coverage of the subject. Each chapter starts with the simpler concepts before moving on the the more advanced stuff. Great for PROVING programming rigor, etc, etc.
Contents:
Chapter 1: Introduction to Discrete Mathematics
What is Discrete Mathematics
Tools, Techniques, and Methodologies
An Algorithmic Language
Pseudocode
Assignment Statements
Control Statements
Chapter 2: Logic and Sets
Logic and Propositions
Propositions
Logical Operations
Predicate Logic
Proofs
Direct Proofs
Contrapositive Proofs
Proofs by Contradiction
Existence Proofs
Counterexamples
Mathematical Induction
Principle of Mathematical Induction
Inductive Definition
Correctness of Algorithms
Assertions
Sequence Statements
Conditional Statements
Iteration
Basic Properties of Sets
Definitions of Sets
Some Special Sets
Operations on Sets
Properties and Identities
More on Sets
Power Sets
Product Sets
Partitions of a Set
Application: A Look at Knowledge-Based Systems
Chapter 3: Relations and Functions
Relations
Binary Relations
Graphical Representation of Relations
Matrix Representation of Relations
Properties of Relations
Reflexive Relations
Symmetric Relations
Transitive Relations
Equivalence Relations and Partitions
Order Relations
Transitive Closure
Composition of Relations
Logical Matrix Product
The Identity Relation
Inverse Relations
Functions
Injections and Surjections
Functions and Cardinality
Invertible Functions
Binary Operations
Functions in Computer Languages
Application: Database Management Systems
Chapter 4: Combinatorics
Selecting Elements from a Set
Definitions
Counting Formulas
Patterns and Partitions
Algorithm Analysis
Order Classes
Common Order Classes
Application: How Fast Can We Sort?
Chapter 5: Undirected Graphs
Simple Graphs
Paths, Cycles, and Connectivity
Eulerian Paths
Hamiltonian Circuits
Isomorphisms
Trees
Minimal Spanning Trees
Rooted Trees
Sorting and Searching
Application: Syntax of Languages
Chapter 6: Directed Graphs
Digraphs
Degrees, Paths, and Cycles
Consistent Labeling
Path Problems in Digraphs
Existence of Paths
Warshall's Algorithm
Shortest Paths
Number of Paths
Application: Routing in Communications Networks
Chapter 7: Boolean Algebra
Boolean Expressions
Expressions
DeMorgan's Laws
Representation of Expressions
Minterms
Normal Form
Complete Sets of Operations
Minimization of Boolean Expressions
Karnaugh Maps
Karnaugh Maps for Four Variables
Switching Theory
Circuit Diagrams
Complete Sets of Logic Gates
A Control Switch Example
Application: Designing a 2-Bit Adder
Chapter 8: Algebraic Systems
Semigroups, Monoids, and Groups
Semigroups
Monoids
Submonoids
Groups
Subgroups
Building New Algebras
Product Algebras
Quotient Algebras
Cosets
Lagrange's Theorem
Morphisims of Algebraic Structures
Homomorphisms Between Monoids
Isomorphisms of Monoids
Fundamental Theorem of Homomorphisms for Monoids
Group Homomorphisms
Fundamental Theorem of Homomorphisms for Groups
Application: Group Codes
Chapter 9: Machines and Computations
Automata as Models
Finite State Automata Without Outputs
Definition of a Finite State Automata
Finite State Automata as Language Recognizers
Limits of Finite State Automata as Language Recognizers
Finite State Automata With Outputs
Moore Machines
Mealy Machines
Turing Machines
Effective Procedures
Turing's Model of Computation
Turing Machines as Language Recognizers
Turing Machines as Function Computers
Church-Turing Thesis
Application: Problem Solving
Chapter 10: Probability
Elementary Properties of Probability
Uniform Probability Space
Conditional Probability
Bayes' Theorem
Independent Events
Repeated Trials and Expected Values
The Binomial Distribution
Random variables and Distributions
Expected Values
Application: An Average Case Analysis
Book Stats:
Cover: Hardcover
Condition: Highlighting and pencil marks - well used
Pages: 504
Author(s): Skvarcius, R; Robinson, WB
Publisher: Benjamin Cummings
ISBN: 0-8053-7044-7
