Discrete Computational Structures

Discrete Computational Structures

1st Edition - January 1, 1974

Write a review

  • Author: Robert R. Korfhage
  • eBook ISBN: 9781483264295

Purchase options

Purchase options
DRM-free (PDF)
Sales tax will be calculated at check-out

Institutional Subscription

Free Global Shipping
No minimum order


Discrete Computational Structures describes discrete mathematical concepts that are important to computing, covering necessary mathematical fundamentals, computer representation of sets, graph theory, storage minimization, and bandwidth. The book also explains conceptual framework (Gorn trees, searching, subroutines) and directed graphs (flowcharts, critical paths, information network). The text discusses algebra particularly as it applies to concentrates on semigroups, groups, lattices, propositional calculus, including a new tabular method of Boolean function minimization. The text emphasizes combinatorics and probability. Examples show different techniques of the general process of enumerating objects. Combinatorics cover permutations, enumerators for combinations, Stirling numbers, cycle classes of permutations, partitions, and compositions. The book cites as example the interplay between discrete mathematics and computing using a system of distinct representatives (SDR) problem. The problem, originating from group theory, graph theory, and set theory can be worked out by the student with a network model involving computers to generate and analyze different scenarios. The book is intended for sophomore or junior level, corresponding to the course B3, "Introduction to Discrete Structures," in the ACM Curriculum 68, as well as for mathematicians or professors of computer engineering and advanced mathematics.

Table of Contents

  • Preface


    Chapter 1 Basic Forms and Operations

    1. Introduction

    2. Elements and Sets

    3. Subsets

    4. Venn Diagrams and Set Complements

    5. Computer Representation of Sets

    6. Set Operations

    7. Set Algebra

    8. Computer Operations on Sets

    9. Product Sets

    10. Relations, Mappings, Functions

    11. Equivalence and Order Relations

    12. The Lattice of Subsets

    13. Vectors and Matrices

    Chapter 2 Undirected Graphs

    1. Graph Theory

    2. Basic Definitions

    3. Special Classes of Graphs

    4. Matrix Representation of Graphs

    5. Relations among Graph Matrices

    6. Invariants and Graph Isomorphism

    7. Cycle Basis

    8. Maximal Complete Subgraphs

    9. Storage Minimization for Matrices

    10. Bandwidth of Cubic Graphs

    11. Bandwidth of Bipartite Graphs

    12. Planar Graphs and the Four Color Conjecture


    Chapter 3 Gorn Trees

    1. Introduction

    2. Tree Domains

    3. Trees

    4. Prefix Representation and Tree Forms

    5. Explicit Definitions

    6. Searching, Subroutines, and Theorem Proving


    Chapter 4 Directed Graphs

    1. Introduction

    2. Basic Definitions

    3. Special Classes of Graphs

    4. Matrix Representation of Directed Graphs

    5. Flowcharts

    6. Networks

    7. Minimal Cost Flows

    8. Pruning Branches to Find the Shortest Path

    9. Critical Paths

    10. Graphs of Multiprocessing Systems

    11. Information Networks


    Chapter 5 Formal and Natural Languages

    1. Introduction

    2. Semigroups

    3. Formal Languages

    4. Backus Naur Form and Algol-Like Languages

    5. Semantics of Formal Languages

    6. Natural Languages


    Chapter 6 Finite Groups and Computing

    1. Definitions of Groups and Subgroups

    2. Groups of Graphs

    3. Graphs of Groups

    4. Generators and Relations

    5. Permutations and Permutation Groups

    6. Permutation Generators

    Chapter 7 Partial Orders and Lattices

    1. Introduction

    2. Partial Orders

    3. Lattices

    4. Specialized Lattices

    5. Atomic Lattices


    Chapter 8 Boolean Algebras

    1. Introduction

    2. Properties of Boolean Algebras

    3. Boolean Algebras and Set Algebras

    4. Boolean Functions

    5. Switching Circuits

    6. Boolean Function Minimization

    7. Computer Arithmetic


    Chapter 9 The Propositional Calculus

    1. Introduction

    2. Fundamental Definitions

    3. Truth Tables

    4. Well-Formed Formulas

    5. Minimal Sets of Operators

    6. Polish Notation

    7. Proofs in Logic

    8. Sets and Wordsets


    Chapter 10 Combinatorics

    1. Introduction

    2. Permutations of Objects

    3. Combinations of Objects

    4. Enumerators for Combinations

    5. Enumerators for Permutations

    6. Stirling Numbers

    7. Cycle Classes of Permutations

    8. Partitions and Compositions


    Chapter 11 Systems of Distinct Representatives

    1. Introduction and History

    2. The Third Question, General Case

    3. The Third Question, Partition Case

    4. Summary


    Chapter 12 Discrete Probability

    1. Probabilities on a Discrete Set

    2. Conditional Probability and Independence

    3. Computation of Binomial Coefficients

    4. Distributions

    5. Random Numbers


    Answers and Hints for Selected Exercises


Product details

  • No. of pages: 396
  • Language: English
  • Copyright: © Academic Press 1974
  • Published: January 1, 1974
  • Imprint: Academic Press
  • eBook ISBN: 9781483264295

About the Author

Robert R. Korfhage

About the Editor

Werner Rheinboldt

Ratings and Reviews

Write a review

There are currently no reviews for "Discrete Computational Structures"