Author: Jozef GruskaThe applied nature of modern computing has created a great need for an accessible treatment of the theoretical foundations of computer science. Foundations of Computing appeals to all computer or information science majors and graduates. Other books, such as the two-volume Handbook of Theoretical Computer Science by van Leeuwen, are targeted to specialists. In contrast, the book reviewed here emphasises motivation, interpretation, and explanation; serving the dual role of a textbook and a reference book.
The book supplies its motivation by relating theoretical models to practical examples. Despite the formality and rigor of the topic, the book maintains a balance of complexity and uses illustrations to help students grasp the essentials. In the reviewers knowledge, the only other book similar in scope is Models of Computation: Exploring the Power of Computing, by J.E. Savage, which also describes theoretical computer science while focusing on real world problems.
The book covers an impressive array of topics ranging from automata and Turing machines to algorithms, complexity theory, and computability, and term rewriting. Often topics from the backbone of theoretical computer science are coherently mixed with more applied material. Parallel processing, cryptography, networking and communications theory are also presented. As an example, the cryptography chapter covers secret key cryptosystems, public key cryptosystems, and the relationship between cryptography and randomness. However, formal semantics, a main constituent of theoretical computer science, is not treated.
The text begins with over 150 pages dedicated to the mathematics and notational conventions used throughout the rest of the book. Very little is assumed as regards the mathematical knowledge of the reader. Topics in this section include: sets, relations, functions, graphs, languages, algebras, and fundamental techniques such as recurrences, generating functions, asymptotics, and probabilities.
Each chapter follows a similar format. The chapters begin with clearly stated learning objectives, and proceeds with progressively more complex examples, punctuated with numerous simple exercises for self-test. Rarely is a theorem presented without a preceding discussion to act as motivation. Algorithms are given in Pascal-like pseudo-code, which should pose no problems to anyone who has even the most rudimentary programming skills. Diagrams are frequently employed. Theorems, algorithms and key terminology are marked in bold typeface, and therefore easy to find. Each chapter concludes with a series of exercises, given in increasing order of difficulty. More difficult exercises are marked by one or two asterisks. A historial and bibliographical discussion provides references for further study.
In summation, this is a comprehensive, unique, textbook, of value to anyone interested in computing theory, and well-deserving of a place on the book-shelf of students and serious practitioners.
©
Copyright 2000 by ACM, Inc.
Last Modified:
Location: www.acm.org/crossroads/xrds6-5/foundations.html