### 1.1.1 計算機與計算 計算機是當代最偉大的發明之一。自從人類制造出第一臺電子數字計算機，迄今已近 70 年。經過這么多年的發展，現在計算機已經應用到社會、生活的幾乎每一個方面。人們用計 算機上網沖浪、寫文章、打游戲或聽歌看電影，機構用計算機管理企業、設計制造產品或從 事電子商務，大量機器被計算機控制，手機與電腦之間的差別越來越分不清，……總之計算 機似乎無處不在、無所不能。那么，計算機究竟是如何做到這一切的呢？為了回答這個問題， 需要了解計算機的工作原理。 提到計算機，人們頭腦中會首先浮現出顯示器、鍵盤、主機箱等一堆設備——計算機硬 件。了解一點硬件設備的基本知識自然是需要的，不過從學習用計算機解決問題這個層次看， 并不需要掌握多少底層硬件知識。在此我們僅介紹現代計算機的主要功能部件，目的是要了 解用計算機解決問題的計算機制。現代計算機的主要功能部件如圖 1.1 所示。  CPU、指令與程序 中央處理單元（CPU）是計算機的計算部件，能夠執行機器指令，或簡稱指令（instruction）。 每條指令表達的是對特定數據執行特定操作。某種 CPU 能執行的全體指令是由該 CPU 的制 造商設計并保持固定不變的，稱為該 CPU 的指令集。例如，Intel 公司為它的 80x86 系列處 理器設計了上百條的指令。 外行人也許會以為，計算機功能如此強大，必定是因為它能執行功能強大的指令。然而 事實并非如此。即使是當今技術最先進、計算能力最強大的計算機，它的 CPU 也只會執行一 些非常簡單的指令，例如將兩個數相加、測試兩個數是否相等、把數據放入指定的存儲單元 等等。 由于每條機器指令都只能完成很簡單的操作，因此僅靠少數幾條指令是做不了什么復雜 的事情的。但是，如果將成千上萬條簡單指令組合起來，卻能解決非常復雜的問題！亦即， 復雜操作可以通過執行按特定次序排列的許多簡單操作而實現。這種由許多指令按次序排列 而成并交給計算機逐條執行的指令序列稱為程序（program）。為了用計算機解決問題，把問 題的解法表達成一個指令序列（即程序）的過程，稱為程序設計或編程（programming）。可 見，計算機所做的所有神奇的事情，都是靠一步一步執行的、平凡而乏味的簡單指令序列做 到的。計算機一點也不神奇，它唯一會做的事情就是機械地執行預定的指令序列。 存儲器 存儲器是計算機的記憶部件，用于存儲數據和程序。 存儲器分為主存儲器和次級存儲器，它們是用不同的物理材料制造的。CPU 只能直接訪 問主存儲器，也只有主存儲器才能提供與 CPU 相匹配的存取速度。但主存儲器需要靠持續供 電來維持存儲，一旦斷電，存儲的數據或程序就會消失。為了持久存儲信息，可以使用即使 斷電也能維持存儲的次級存儲器，如當前普遍使用的磁盤。CPU 不能直接訪問次級存儲器， 次級存儲器上的數據或程序必須先送到主存儲器中，才能被 CPU 存取或執行。次級存儲器的 讀寫速度遠遠低于主存儲器，這個差別極大地影響了用計算機解決問題時所使用的方法。 現代計算機在體系結構上的特點是：數據和程序都存儲在主存儲器中，CPU 通過訪問主 存儲器來取得待執行的指令和待處理的數據。這稱為馮·諾伊曼（von Neumann）體系結構。 輸入/輸出設備 輸入和輸出設備提供了人與計算機進行交互的手段。我們通過輸入設備向計算機輸入信 息，計算機則通過輸出設備將計算結果告訴我們。傳統的輸入設備有鍵盤和鼠標等，輸出設 備有顯示器和打印機等。現代的觸摸屏則兼具輸入和輸出的功能。 計算 了解了計算機的組成，就能理解計算機解決問題的過程是怎樣的。我們來看一個常見任 務——用計算機寫文章——是如何解決的。為了解決這個問題，首先需要編寫具有輸入、編 輯、保存文章等功能的程序，例如微軟公司的程序員們所寫的 Word 程序。如果這個程序已 經存入我們計算機的次級存儲器（磁盤），通過雙擊 Word 程序圖標等方式可以啟動這個程序， 導致該程序從磁盤被加載到主存儲器中。然后 CPU 逐條取出該程序的指令并執行，直至最后 一條指令執行完畢，程序即告結束。在執行過程中，有些指令會導致與用戶的交互，例如用 戶利用鍵盤輸入或刪除文字，利用鼠標點擊菜單進行存盤或打印等等。就這樣，通過執行成 千上萬條簡單的指令，最終解決了用計算機寫文章的問題。 針對一個問題，設計出解決問題的程序（指令序列），并由計算機來執行這個程序，這 就是計算（computation）。 通過計算，使得只會執行簡單操作的計算機能夠完成神奇的復雜任務，所以計算機的神 奇表現其實都是計算的威力。如果讀者對計算的能力還有疑問，下面這個例子或許能打消這 個疑問。Lucy 是一個只學過加法的一年級小學生，她能完成一個乘法運算任務嗎？答案是肯 定的！解決問題的關鍵在于編寫出合適的指令序列讓 Lucy 機械地執行。例如下列“程序” 就能使 Lucy 算出 m×n： ``` 在紙上寫下 0，記住結果； 給所記結果加上第 1 個 n，記住結果； 給所記結果加上第 2 個 n，記住結果； …… 給所記結果加上第 m 個 n，記住結果。至此就得到了 m×n。 ``` 不難看出，這個指令序列的每一步都是 Lucy 能夠做到的，因此最后確實能完成乘法運 算。這就是“計算”所帶來的成果①。 計算機就是通過這樣的“計算”來解決所有復雜問題的。執行大量簡單指令組成的程序 雖然枯燥繁瑣，但計算機作為一種機器，其特長正在于機械地、忠實地、不厭其煩地執行大 量簡單指令！ > ① 當然，這種計算看上去就很繁瑣，原因在于用到的基本指令（加法）太簡單。如果 Lucy 學習了更“高級” 的指令（如乘法口訣等），就可以更快捷地完成乘法運算。 計算機的通用性 通過前面的介紹，可知計算機就是進行“計算”的機器。顯然，這里的“計算”并不是日常說的數學計算。事實上，計算機在屏幕上顯示信息，在 Word 文檔中查找并替換文本， 播放 mp3 音樂，這些都是計算。 理解了計算機是如何計算的，也就能理解為什么計算機具有通用性，能解決各種不同類 型的問題。其中的奧秘就在于程序。如果想用計算機寫文章，就將 Word 之類的程序加載到 主存中讓 CPU 去執行，這時計算機就成了一臺電子打字機；如果想用計算機聽音樂，就將 Media Player 之類的程序加載到主存中讓 CPU 去執行，這時計算機就成了一臺音頻播放機； 如果將 IE 之類的程序加載到主存中讓 CPU 去執行，計算機就可以在互聯網上瀏覽信息。總 之，一臺計算機的硬件雖然固定不變，但通過加載執行不同的程序，就能實現不同的功能， 解決不同的問題。 我們平時說的計算機都是指通用計算機，能夠安裝執行各種不同的程序。其實在工業控 制和嵌入式設備等領域，也存在專用計算機，它們只執行預定的程序，從而實現固定的功能。 例如號稱電腦控制的洗衣機，其實就是能執行預定程序的計算機。 計算機科學 為了更好地利用計算機解決問題，人們深入研究了關于計算的理論、方法和技術，形成 了專門研究計算的學問——計算機科學（computer science）①。 計算機科學包含很多內容，本書的主題是計算機科學家在用計算機解決問題時建立的一 些思想和方法，這些思想和方法普遍存在于計算機科學的各個分支之中。作為例子，我們來 看計算機科學家思考的一個根本問題：到底什么問題是計算機可計算的？一般人會以為，一 個問題能不能用計算機計算，取決于該計算機的計算能力；而計算機的計算能力又取決于 CPU 的運算速度、指令集、主存儲器容量等硬件指標。真如此的話，顯然巨型計算機應該具 有比微型計算機更強大的計算能力。然而，作為計算機科學理論基礎的可計算性理論卻揭示 了一個出人意料的結論：所有計算機的計算能力都是一樣的！盡管不同計算機有不同的指令 集和不同性能的硬件，但一臺計算機能解決的問題，另一臺計算機肯定也能解決。