計算機科學基礎/什麼是計算

什麼是計算

在本課程中，我們將重點關注計算原理（重大理念），而不是計算機技術，計算機技術是原理的工具和應用。 計算 由一組原理或理念定義，這些原理或理念構成了基於這些原理建立的眾多技術的基礎。 技術可能是複雜的且不斷發展變化的，但原理保持不變。 在課程的後半部分，我們將學習各種技術以展示計算的能力以及如何應用原理。

除了計算原理和技術之外，還有計算實踐 - 專業人士為促進計算而做的事情。

右邊的圖表說明了計算原理和計算實踐之間的區別。 原理是技術和實踐的基礎。 消費者透過為他們構建的各種任務的應用程式來利用計算的能力。 我們相信每個人都需要了解計算原理，因為這些原理具有廣泛的適用性。 作為計算領域的專業人士，我們需要了解兩端和中間的一切 - 實踐（使計算有用和有效的活動和技能）。

在整本書中，我們將交替使用計算和 計算 這兩個術語。

計算原理

計算從根本上來說是關於資訊過程的。 計算的重大理念之一是資訊過程可以透過純粹的機械方式透過符號操作來執行。 執行計算的代理，無論是思考的人類還是機器（計算機），都無關緊要。 在本書的結尾，我們將看到這對所有現代計算機都是正確的 - 數字計算機根據指令盲目地操作兩個符號（零和一）。

一個類比

來自“思考即計算”一書 的以下類比說明了這一理念。 想象一下我們有以下符號表。

	a	b	c	d	e	f	g	h	i	j
a	aa	ab	ac	ad	ae	af	ag	ah	ai	aj
b	ab	ac	ad	ae	af	ag	ah	ai	aj	ba
c	ac	ad	ae	af	ag	ah	ai	aj	ba	bb
d	ad	ae	af	ag	ah	ai	aj	ba	bb	bc
e	ae	af	ag	ah	ai	aj	ba	bb	bc	bd
f	af	ag	ah	ai	aj	ba	bb	bc	bd	be
g	ag	ah	ai	aj	ba	bb	bc	bd	be	bf
h	ah	ai	aj	ba	bb	bc	bd	be	bf	bg
i	ai	aj	ba	bb	bc	bd	be	bf	bg	bh
j	aj	ba	bb	bc	bd	be	bf	bg	bh	bi

這些符號可以是任何符號集，為了簡單起見，我們選擇英語字母表中的字母。 我們可以定義一個過程 P，它將兩個符號（'a' 到 'j'）作為輸入並生成同一集中兩個符號作為輸出。 在內部，該過程使用第一個輸入符號來查詢以相同符號開頭的行，然後使用第二個輸入符號來查詢頂部具有相同符號的列，然後報告/返回交叉點的符號。 不難想象這樣的表格查詢過程可以由簡單的代理（例如裝置或機器）透過純粹的機械方式（盲目地）完成。 當然，人類可以做到這一點，但這種型別的符號操作不需要人類智力。 從這個思想實驗中可以得出兩個結論

• 符號操作可以機械地完成。
• 執行操作的機器不需要知道符號的含義，也不需要知道操作的目的。

如果我們知道如何解釋符號，這個過程是有意義的。 例如，如果符號 'a' 到 'j' 分別代表 0 到 9 的數量，那麼此過程執行一位十進位制加法。 例如，p(d, f) = p(3, 5) = ai = 08，這是 3+5 的正確結果。 下面的表格本質上與前面的表格相同，只是它使用了對人類有意義的符號。

	0	1	2	3	4	5	6	7	8	9
0	00	01	02	03	04	05	06	07	08	09
1	01	02	03	04	05	06	07	08	09	10
2	02	03	04	05	06	07	08	09	10	11
3	03	04	05	06	07	08	09	10	11	12
4	04	05	06	07	08	09	10	11	12	13
5	05	06	07	08	09	10	11	12	13	14
6	06	07	08	09	10	11	12	13	14	15
7	07	08	09	10	11	12	13	14	15	16
8	08	09	10	11	12	13	14	15	16	17
9	09	10	11	12	13	14	15	16	17	18

現在我們有了可以指示簡單代理新增兩個一位十進位制數字的簡單過程 P，我們可以設計一個新的過程 P1，該過程可以像下面圖表中所示那樣新增三個一位十進位制數字。

新的過程 P1 使用三個 P 過程例項來新增三個十進位制數字並返回兩個數字作為結果。 我們可以將過程視為具有輸入和輸出的機器，線條是管道，允許符號從一個地方移動到另一個地方。 不難想象，可以執行 P 的代理可以執行 P1，因為 P1 完全由 P 組成。 請注意，虛線矩形代表由 P 例項組成的新的過程 P1，並且 P1 給出的樣本輸入的答案是正確的。 同樣，在此過程中使用的符號可以是任何符號集，因為內部執行的是簡單的表格查詢。

現在想象一下，我們可以使用 P1 來構建更復雜的過程，例如下面圖表中的過程 P2。

P2 使用 P1 來新增兩個兩位數，實際上我們可以簡單地向設計中新增更多 P1 來處理任意數量的數字。

到目前為止，我們可以得出以下結論

• 任何可以執行 P 的機器都可以執行 P1、P2 等。
• 我們已經透過使過程更復雜來建立執行看似智慧活動的程式，同時讓簡單的機器仍然可以完成這些程式。

如果我們遵循相同的推理思路，不難想象我們可以建立越來越複雜的過程來指示簡單的機器做越來越智慧的事情，例如

• 整數減法
• 比較兩個整數（減法並檢查結果的符號）
• 整數乘法（重複加法）
• 使用一對整數表示分數，並在它們上進行算術運算
• 使用整數矩陣表示方程組，並使用矩陣運算來求解它們
• 使用方程組來建模複雜的物理系統，並對這些系統進行數值模擬

總之，從這個例子中我們可以看到，簡單的符號操作可以組裝起來形成更大的過程，透過計算過程來執行驚人的活動。 這些活動不僅限於數值計算。 如果我們可以將抽象概念表示為符號（就像我們將抽象量表示為具體數字一樣），並設計過程來根據概念之間的關係運算子號，那麼我們可以將推理建模為計算過程。 這就是計算機科學的本質 - 具有兩個基本要素的資訊過程：表示和一組用於操作表示的規則。 請注意，這與電子裝置或物理學無關。 執行這些過程的機器不需要知道符號的含義，也不需要知道為什麼該過程會產生正確的結果。 機器只需要盲目地遵循過程（一組規則）。

例如，您可以閱讀關於 查爾斯·巴貝奇 設計的可以對多項式函式進行製表的機械計算機（差分機）的資訊

另一個類比

理查德·費曼 在他的計算機啟發式講座（1 小時 15 分鐘）中使用了另一個類似的類比（檔案管理員）來解釋計算機從內部到外部的工作方式：http://www.youtube.com/watch?v=EKWGGDXe5MA

歷史

現在我們已經瞭解了什麼是計算，本質上是某種符號操作。 計算機執行驚人任務的能力取決於其根據定義良好的規則運算子號的能力。 事實上，數字計算機只操作兩個符號 - 零和一。 計算的智慧在於規則/程式的設計和實現。

在將來，當談論計算機機器時，我們將看到計算機是根據這些原理構建的。

你可能想知道這些想法從哪裡來。歷史上許多人對計算和計算機的概念做出了重大貢獻。德國哲學家戈特弗裡德·萊布尼茨（1646-1716）被認為是第一個夢想將推理簡化為計算並製造出能夠執行這種計算的機器的人。他觀察到，在算術中，我們用符號來表示抽象的量，並根據規則操縱這些符號以獲得有用的結果。他夢想著，我們可以用符號來表示抽象的思想，並透過類似於我們在算術中進行的具體的符號操作，根據思想之間的邏輯來推理這些思想。這種操作能得到正確的結果，不是因為做操作的人很聰明，而是因為操作規則反映了數量之間的關係以及思想之間的邏輯關係。

由於萊布尼茨的夢想，現在我們有了計算機科學和稱為計算機的通用機器。計算機從根本上來說是一種物理裝置，它可以根據非常簡單的邏輯規則操縱符號。幾乎所有的計算機都是電子裝置，因為用這種方式建造起來比較便宜和容易。計算機科學從根本上來說是關於資訊處理（處理抽象思想）的，資訊處理透過符號操作進行，符號操作遵循一個配方（一組規則）。這種配方也被稱為演算法。難怪有這麼多計算機程式設計書籍被稱為食譜 :) 在計算機科學中，我們研究如何表示資訊，以及如何設計和應用演算法以獲得有意義的結果。通常有許多方法可以執行相同的任務。比較演算法以進行評估被稱為演算法（複雜性）分析。將演算法（配方）傳達給計算機稱為程式設計/軟體開發。我們用來進行這種通訊的語言被稱為計算機程式語言。程式設計的產物是計算機程式或軟體。我們在軟體開發過程中嘗試應用的工程學科，以生產高質量的軟體，被稱為軟體工程。所以計算機科學更多地是關於解決問題，而不是計算機。計算科學可能是這個學科更合適的名稱。

計算實踐

原則是在計算的各個方面都滲透的基本思想。實踐不是原則，但非常有用，因為它們可以識別計算專業人士的核心實踐。實踐，有時也被稱為“訣竅”，定義了一個人的技能組合和能力水平：初學者、熟練者和專家。計算的四個核心實踐在計算大原則專案中被確定出來：

• 程式設計（包括多語言程式設計實踐）
• 系統與系統思維
• 建模、驗證、測試和度量
• 創新

程式設計是計算機科學不可分割的一部分，因為它讓我們能夠以具體的方式探索計算機科學中的抽象思想。它也是一個激動人心的創造過程，當我們能夠讓計算機做有用的事情時，它會帶來極大的滿足感。在本課程中，我們將使用一種非常高階的圖形程式設計環境進行程式設計，以探索計算機科學中的思想。

唐納德·克努特認為程式設計就像創作：寫得好的程式讓人們（包括你自己）讀起來很愉快。他認為程式設計具有三方面的回報 

• 美麗的程式碼（審美）
• 做有用的工作（人道主義）
• 得到報酬（經濟）

計算機程式設計本質上是教計算機如何做事。正如我們之前提到的，計算機是簡單的機器，嚴格按照指令行事。為了讓計算機執行正確的任務，我們程式中的指令必須正確且合乎邏輯。可以在計算機上執行的程式稱為軟體 - 充當計算機的大腦。有錯誤的軟體被稱為有bug（見這個名字的由來）的軟體。在實際計算機上測試軟體可以幫助捕獲軟體中的大多數bug。測試幾乎可以立即反饋我們的程式的質量，以便我們可以修復bug並改進它。正因為如此，我們相信程式設計讓我們成為更好的思考者和學習者。我們將看到為什麼很難證明程式的正確性。