Understanding Computation: Pillars, Paradigms, Principles

Computation theory is a discipline that uses mathematical concepts and tools to expose the nature of "computation" and to explain a broad range of computational phenomena: Why is it harder to perform some computations than others? Are the differences in difficulty that we observe inherent, or are they artifacts of the way we try to perform the computations? How does one reason about such questions?

This unique textbook strives to endow students with conceptual and manipulative tools necessary to make computation theory part of their professional lives. The work achieves this goal by means of three stratagems that set its approach apart from most other texts on the subject.

For starters, it develops the necessary mathematical concepts and tools from the concepts' simplest instances, thereby helping students gain operational control over the required mathematics. Secondly, it organizes development of theory around four "pillars," enabling students to see computational topics that have the same intellectual origins in physical proximity to one another. Finally, the text illustrates the "big ideas" that computation theory is built upon with applications of these ideas within "practical" domains in mathematics, computer science, computer engineering, and even further afield.

Suitable for advanced undergraduate students and beginning graduates, this textbook augments the "classical" models that traditionally support courses on computation theory with novel models inspired by "real, modern" computational topics, such as crowd-sourced computing, mobile computing, robotic path planning, and volunteer computing.

Arnold L. Rosenberg is Distinguished Univ. Professor Emeritus at University of Massachusetts, Amherst, USA. Lenwood S. Heath is Professor at Virgina Tech, Blacksburg, USA.

計算理論是一門利用數學概念和工具來揭示「計算」的本質並解釋各種計算現象的學科：為什麼有些計算比其他計算更難？我們觀察到的困難差異是固有的，還是我們嘗試進行計算的方式的產物？如何對這些問題進行推理？

這本獨特的教科書旨在使學生具備使計算理論成為他們專業生活的一部分所需的概念和操作工具。該書通過三種策略實現了這一目標，使其方法與大多數其他相關主題的教材有所不同。

首先，它從概念的最簡單實例開始發展必要的數學概念和工具，從而幫助學生對所需的數學獲得操作控制。其次，它將理論的發展組織成四個「支柱」，使學生能夠看到在物理上有相同智力起源的計算主題彼此靠近。最後，該教材通過在數學、計算機科學、計算機工程甚至更遠的領域內應用這些思想的「實際」領域，來說明計算理論所建立的「大思想」。

適用於高年級本科生和初級研究生，這本教科書通過受到「真實、現代」計算主題啟發的新模型來補充傳統上支持計算理論課程的「經典」模型，例如群眾外包計算、移動計算、機器人路徑規劃和志願計算。

Arnold L. Rosenberg 是美國麻省大學阿默斯特分校的杰出名譽教授。 Lenwood S. Heath 是美國弗吉尼亞理工大學的教授。