Korfhage R.R. Discrete Computational Structures

Springer, 1974. — 389 p.The digital computer is a machine which is inherently finite in all of its aspects which are of importance to a programmer or user. Whether the problem posed to the computer relates to numerical computation, symbol manipulation, information retrieval, or picture generation, the procedures and results are restricted by the finiteness of word length and memory size, and by the discrete time steps in which a computer operates. Hence for a thorough understanding of the capabilities and limitations of computers, it is important to be aware of the impact of these restrictions. Thus the purpose of this text is to bring together many of the concepts from discrete mathematics which are important to computing. Throughout I have tried to keep two questions in mind: (1) How does this topic influence the theory and practice of computing? (2) How is the computer used to solve problems in this topic? These questions cannot always be given equally good answers, and there are topics, particularly early in the book, where any relation between the topic and computing is largely suppressed. Hopefully, these topics are few and brief, and in the nature of a mathematical background necessary to the remainder of the book.
The text is designed as a sophomore- or junior-level book, corresponding to the course B3, Introduction to Discrete Structures, in the ACM Curriculum 68. Thus I assume that the student knows and can use at least one high level programming language, and I use this assumption in both the text and the exercises. I view B3 as the more mathematical half of a one-year course. Thus the student who has covered the material presented here should be ready to use these mathematical concepts in courses which deal more specifically and directly with computers. He should have the basic mathematics to enable him to feel comfortable in undergraduate courses in data structures (the natural follow-up to B3), switching circuits, and automata theory. With this in mind, topics such as lists, circuit design, and finite state machines have been largely omitted, to be covered in succeeding courses.
This book is not intended as a formal, rigorous introduction to the theory of discrete structures, although I believe that the mathematical content is accurate and not misleading. It has been my experience that most computer science students at this level do not appreciate the subtleties of the theory. Hence I have tried to motivate the theoretical constructs as thoroughly as possible from computing, and to present any arguments, however formal, in an informal setting. Nevertheless, I firmly believe that the instructor should be willing and able to put the challenge of formal work to those students who can absorb more theory.
The text is quite loosely structured, with ample material so that the instructor can pick and choose. Very little mathematical background is required of the student, although students who have had a course in the foundations of modern mathematics will find much of Chapters 1 and 9 to be review material. Basically there are five sections to the text, and almost any permutation of these sections makes sense. However, my experience with the material has led me to the present order, both among and within sections.Basic Forms and Operations
Undirected Graphs
Gorn Trees
Directed Graphs
Formal and Natural Languages
Finite Groups and Computing
Partial Orders and Lattices
Boolean Algebras
The Propositional Calculus
Combinatorics
Systems of Distinct Representatives
Discrete Probability