|
Theoretical computer science treats any computational subject for which a good model can be created.
Research on formal models of computation was initiated in the 1930s and 1940s by Turing, Post, Kleene,
Church, and others. In the 1950s and 1960s programming languages, language translators, and operating
systems were under development and therefore became both the subject and basis for a great deal of
theoretical work. The power of computers of this period was limited by slow processors and small
amounts of memory, and thus theories (models, algorithms, and analysis) were developed to explore
the efficient use of computers as well as the inherent complexity of problems. The former subject
is known today as algorithms and data structures, the latter computational complexity.
The focus of theoretical computer scientists in the 1960s on languages is reflected in the first textbook on
the subject, Formal Languages and Their Relation to Automata by John Hopcroft and Jeffrey Ullman. This
influential book led to the creation of many language-centered theoretical computer science courses;
many introductory theory courses today continue to reflect the content of this book and the interests
of theoreticians of the 1960s and early 1970s.
Although the 1970s and 1980s saw the development of models and methods of analysis directed at understanding
the limits on the performance of computers, this attractive new material has not been made available at
the introductory level. This book is designed to remedy this situation.
This book is distinguished from others on theoretical computer science by its primary focus on real
problems, its emphasis on concrete models of machines and programming styles, and the number and variety of
models and styles it covers. These include the logic circuit, the finite-state machine, the pushdown
automaton, the random-access machine, memory hierarchies, the PRAM (parallel random-access machine),
the VLSI (very large-scale integrated) chip, and a variety of parallel machines.
The book covers the traditional topics of formal languages and automata and complexity classes but
also gives an introduction to the more modern topics of space-time tradeoffs, memory hierarchies,
parallel computation, the VLSI model, and circuit complexity. These modern topics are integrated
throughout the text, as illustrated by the early introduction of P-complete and NP-complete problems.
The book provides the first textbook treatment of space-time tradeoffs and memory hierarchies as well as a
comprehensive introduction to traditional computational complexity. Its treatment of circuit complexity is
modern and substantative, and parallelism is integrated throughout.
John E. Savage joined the Brown University faculty in 1967 where he has been active in faculty
governance, most recently serving as a Faculty officer (2000-2003) including Chair of the Faculty
(2001-2002). He chaired the Task Force on Faculty Governance (2002-2003) that completely revised
Brown's system of faculty governance. He is a founder of the Department of Computer Science and was
its Chairman from 1985 until 1991. From 1965 until 1967 he was Member of Technical Staff at Bell
Telephone Laboratories in Holmdel, NJ. He was a member of the
MIT Corporation Visiting Committee for
the Department of Electrical Engineering and Computer Science from 1991-2002. He is a John Simon
Guggenheim Memorial Foundation Fellow, and a Fellow of the American Association for the Advancement
of Science, the Association for Computing Machinery, and the Institute for Electrical and Electronics
Engineers. He received a Fulbright-Hays Research Award in 1973.
Click here to visit John's Web pages at
Brown University.
"A magnificent piece of work! Models of Computation gives a
superb treatment of modern complexity theory, in a perfect textbook
style. Your book fills the gap which all of us felt existed too
long. Congratulations on this excellent contribution to our field."
— Jan van Leeuwen
Professor of Computer Science
Utrecht University
Netherlands
"This is an impressive book. The subject has been thoroughly researched
and carefully presented. All the machine models central to the modern
theory of computation are covered in depth; many for the first time in
textbook form. Readers will learn a great deal from the wealth of
interesting material presented."
— Andrew C. Yao
Professor of Computer Science
Princeton University
"Models of Computation is an excellent new book that
thoroughly covers the theory of computation including
significant recent material and presents it all with
insightful new approaches. This long-awaited book will
serve as a milestone for the theory community."
— Akira Maruoka,
Professor of Information Sciences
Tohoku University
|
About this book
About the author