Jozef Gruska: Foundations of computing

International Thompson Computer Press. April 1997.

Paperback, xv+716 pages, 214 figures/tables, ISBN: 1-85032-243-0

Price: US $35.95, UK £25.95, Canada $50.95

About the book

An innovative, synthetizing, much broader than usual, precise but not too formal and focused presentation of fundamentals of modern computing as rich on interesting/important and indispensible conceptual tools and methods as well as deep/exciting results for undergraduate and graduate students in computing and related areas (engineering, science, mathematics,...). Suitable also as a refernce book or a handbook for all ambitious professionals in computing and related areas with heavy and/or deep use of computing.

Main areas covered by the book: analysis of algorithms, discrete mathematics, automata and formal languages, models of (sequential and parallel) computers, computational complexity, computability and limitations of formal systems, rewriting systems, cryptographyand interactive/cryptographical protocols, interconnection (multiprocessor) networks and communication complexity.

The book has 11 chapters, 214 figures/tables, 277 examples, algorithms/protocols, 574 exercises in the text, 641 exercises/questions at the end of the chapters, 588 bibliographical references, and a detailed index (48 pages).

Emphases are on motivations, illustrations, explanations and presentation of strong concepts, methods and results, including the very recent ones.

The book is organized into three parts. The first part, the first two chapters, presents basic concepts of complexity analysis, probability, number theory and discrete mathematics (from a computing point of view). The second part, chapters 3 to 8, presnets the basics of automata theory, universal computers, complexity theory, computability, rewriting systems (for strings, graphs) and cryptography. The third part, chapters 9 to 11, presents interactive/cryptographic protocols, interconnection (multiprocessor) networks and communication complexity.

The book is suitable for a synthetising course on fundamentals and covers what a graduate should know from the automata-computers-formal languages-complexity part of theory of computing. The book can also be used for a variety of specialized courses on the advanced undergraduate or graduate level. For example, for complexity theory (chapters 4, 5, and potentially also 6, 9 and 11), models of computers (chapters 4 and 10), cryptography and interactive/cryptographic protocols (chapters 8 and 9), automata and formal languages (chapters 3, 7 (and 4)), computability (chapter 6 (and 4), communication networks (chapter 10), communication complexity (chapter 11), analysis of algorithms (chapter 11), discrete mathematics (chapter 2).

The book is to be supported by a web-pages supplement including an additional chapter "Frontiers",.....



1. Fundamentals, 76 pages

2. Foundations, 75 pages 3. Automata, 62 pages 4. Computers, 82 pages 5. Complexity, 72 pages 6. Computability, 48 pages 7. Rewritting, 47 pages 8. Cryptography, 34 pages 9. Protocols, 34 pages 10. Networks, 69 pages 11. Communications, 39 pages Bibliography, 588 references

Index, 48 pages