計算機科學基礎/演算法與程式
一個演算法可以定義為解決特定問題的一組步驟。例如，廚師在準備特定型別的食物時可能會使用食譜。類似地，在計算機科學中，演算法是用來建立程式的概念解決方案。重要的是要區分演算法和程式。演算法的實現被稱為程式。
計算機是關於資訊過程的。一旦資訊使用不同的符號模式具體地表示出來，就可以對其進行處理以得出新的資訊。我們瞭解到計算機在內部使用二進位制系統將所有內容表示為位元序列 - 零和一。《位元爆炸》一書的第一章談到了位元的數字爆炸，這是計算和技術創新的結果，這些創新使我們能夠將資訊轉換為位元並以前所未有的速度進行共享。
建立資訊過程是本章的主題。我們將瞭解到，資訊過程始於對問題的概念解決方案，然後可以以機器可以理解的方式進行實現（編碼）。概念解決方案稱為演算法，可執行的實現稱為程式。
演算法是一個相當花哨的名字，它代表一個簡單的想法：解決問題的一步一步的解決方案。阿維·維格德森曾經說過，演算法是自然、人類和計算機的通用語言。這個想法已經存在很長時間了。你已經熟悉了許多演算法，比如繫鞋帶、衝咖啡、傳送電子郵件，以及根據食譜烹飪菜餚。計算中的演算法是為計算機設計的。想象一下，我們建造了一臺可以執行第一章中描述的單一位加法過程的機器。回想一下，該過程使用簡單的表格查詢來執行加法。如果我們給機器兩個數字並讓它執行操作，它會返回兩個數字作為答案。當然，輸入和輸出中的數字必須正確地表示（編碼）。即使機器不理解加法，它也應該能夠正確地執行加法。但是，機器不會執行加法，除非它被指示這樣做。指示機器執行加法的命令（帶輸入值）稱為指令。我們已經想象到，使用加法過程來建立其他更復雜的程式來執行更令人印象深刻的活動並不難。在我們能夠建立這些程式之前，我們必須確定一個問題並找到一個概念解決方案。通常情況下，概念解決方案是可以透過人手工執行的解決方案。這種概念解決方案就是演算法。
演算法是計算機科學學科的核心部分。正如我們在第一章中討論的那樣，計算可以透過簡單的裝置盲目地或純粹地機械地完成。任何計算（資訊過程）的智慧都體現在定義它的演算法中。
為了使演算法有用，它必須是正確的 - 步驟必須合乎邏輯，並且特定於機器可以執行的 - 並且必須是有效的 - 它必須在合理的時間內完成。演算法的正確性和效率是演算法研究中的兩個關鍵問題。
研究演算法使我們能夠以概念的方式解決問題，而與執行解決方案的機器無關。演算法必須以一種明確且人類可以理解的方式傳達概念解決方案。用於描述演算法的符號系統應該允許我們描述和推理紙上的想法。一旦在紙上驗證了演算法的正確性，就可以將其作為特定機器可以理解的程式來實現。
艾倫·圖靈是第一個從數學角度研究演算法的人，他建立了一個通用機器模型，後來被稱為圖靈機。他還證明了在某些情況下計算是不可避免的 - 我們必須對結果進行計算，這將計算與數學區分開來（計算機科學的誕生）。圖靈機可以以標準形式表示/編碼資訊，並根據規則（演算法）解釋和更新表示，這也是表示的一部分。這個機器模型簡單而強大。事實上，它是計算機科學家已知的，最強大的計算模型。圖靈機可以執行我們所能構建的任何機器所做的任何計算。圖靈機等價物是基於這個想法定義的。
圖靈機模型使我們能夠抽象地研究演算法。例如，我們可以將每個演算法視為一個狀態機：演算法總是從一個狀態開始 - 由輸入和內部資訊的資料表示表示 - 並透過一系列狀態移動到其最終狀態，作為執行演算法中規定的操作的結果。當可能的初始狀態數量接近無窮大時，同一個演算法可以生成可能無限多的計算。這解釋了為什麼很難透過測試來驗證演算法的正確性，因為初始狀態可能太多，無法窮舉列舉。
演算法只是一組步驟，使我們能夠解決特定問題。步驟是工作單元，它是明確的，並且可以在固定時間內完成。例如，將一壺水燒開是製茶過程/演算法中的一個步驟。在計算中，我們處理資訊的表示（資料），因此一個步驟可以是新增兩個整數並將結果儲存到變數中。我們將在後面解釋如何定義和使用變數。
工作單元的定義取決於執行工作的代理能夠做什麼。計算中的演算法必然會受到計算機器能力的影響。回想一下，演算法必須以機器可以理解的程式語言實現/描述，然後機器才能執行該任務。存在許多不同的程式語言，因此表達相同演算法的不同方式。特定機器唯一可以理解的語言稱為機器語言。機器語言是用由零和一（二進位制位）組成的指令編寫的，因為計算機從根本上來說是能夠操縱兩種型別符號的機器。每種型別的機器都被設計為理解自己的本機語言——零和一的模式——因為它們的計算硬體可能非常不同。正如你能想象的那樣，用機器語言編寫程式可能非常困難。通常我們編寫程式用高階語言表達我們的演算法 - 接近自然語言的語言，例如英語。然後，我們使用工具（編譯器和直譯器）將我們用高階語言編寫的程式翻譯成機器語言，這類似於在國外旅行時使用個人口譯員，因為我們不理解本機語言。要在不同的機器上運行同一個程式，我們只需重新編譯它或使用不同的直譯器。高階語言隱藏了機器之間的差異，使我們能夠以機器無關的方式編寫程式，這節省了大量時間。當我們用高階語言編寫程式時，我們使用所有計算機都支援的抽象。例如，如果高階語言允許表達加法，我們假設所有計算機都可以做到。
程式語言（高階或機器級）是用於向機器表達演算法的工具。當我們建立演算法來概念化地解決問題時，我們希望使它們獨立於語言。一個設計良好的食譜應該適用於不同廚房的不同廚師。因此，工作步驟或工作單元必須用更高的抽象來定義——所有語言都支援的一組通用資料結構、操作和控制結構。透過使用抽象概念化地建立演算法，允許我們人類在更接近我們所知的問題域的更高層次上思考。當演算法在特定語言中實現時，抽象步驟可以對映到語言中的特定表示式。我們有信心我們擁有的工具鏈可以將解決方案轉換為機器級可執行程式碼。下圖顯示了相同的演算法可以在多種程式語言中實現，並且生成的程式可以在不同的機器模型上執行（可能經過一些轉換）。
以下是我們可以假設所有高階語言都支援的常見操作和控制結構
- 資料結構：單值變數和值列表。
- 操作：算術運算、比較和關係運算（和、或和非）
- 控制結構：順序（一個接一個）、條件（根據條件選擇）和重複
這裡是一個用虛擬碼（自然語言）定義的演算法。該演算法查詢數字列表中的最大數字，步驟如下：
- 將最大值（一個變數）設定為列表中第一個數字的值（儲存和檢索值）。
- 遍歷列表，一次比較一個數字與最大值，如果該數字大於最大值，則用該數字替換最大值（條件和重複）。
- 儲存在最大值中的值就是答案。
我們知道該解決方案是正確的，因為它很簡單。我們知道如何手動執行它，但我們當然不會使用虛擬碼中表達的過程來解決問題。有必要以這種詳細的方式設計和表達演算法以供計算機使用。請記住，計算機是機械地執行計算的機器，因此指令必須是特定的。即使虛擬碼使用自然語言，也必須使用前面提到的對計算機通用的結構（資料結構、操作和控制結構）。您可能想知道為什麼我們不能要求計算機檢視整個列表並像我們人類一樣識別出最大的數字。計算機是簡單的機器，不會思考。它們被設計為執行簡單的操作，例如透過符號操作新增兩個數字。即使我們作為人類，也無法掃描一個長列表，比如一百萬個數字，並一眼找到最大的數字。我們編寫的演算法必須用計算機可以做的事情來表達，並且可以擴充套件到任意大小的輸入（資料集）。我們剛剛研究的演算法可以處理任何大小的列表。事實上，對於計算機來說，列表有三個數字還是三百萬個數字幾乎沒有區別。
另一種表達相同演算法的方法是使用稱為流程圖的圖形符號。
該圖表更清晰地顯示瞭解決方案的邏輯。有兩個條件——檢查條件和作為結果採取的相應操作。最上面的條件定義了一個重複（迴圈），因為它們是一個無條件的分支，回到條件，如沒有標籤的箭頭所示。
虛擬碼和流程圖都描述了對同一個問題的相同解決方案。它們是同一個想法的不同表現形式。下圖顯示了該演算法在 Scratch 中的實現。
如您所見，演算法的具體實現必須使用特定實現語言中可用的構建“塊”。圖中沒有顯示的是從檔案或使用者輸入填充列表的部分。程式碼的結構類似於流程圖。
總之，構建和研究演算法允許我們以與語言和計算環境無關的方式研究（演算法）問題的解決方案。我們可以使用“查詢最大數字”演算法作為單個塊來形成更復雜的演算法，但我們需要記住這個塊不是一個工作單元，因為涉及的步驟數量取決於輸入大小（列表的長度）。我們將在未來討論函式分解（使演算法簡單）和演算法複雜度分析（計算演算法的成本）時重新討論此主題。
程式 每個軟體程式歸根結底都包含兩個元件——資料（結構）和演算法。我們將研究計算機科學中的一些基本演算法和資料結構。
按照這個http://csunplugged.org/sites/default/files/activity_pdfs_full/unplugged-02-image_representation.pdf 影像表示活動來了解影像如何在傳真機中編碼、傳輸和複製。
按照這個http://⁰csunplugged.org/sites/default/files/activity_pdfs_full/unplugged-04-error_detection.pdf 錯誤檢測活動來了解演算法如何檢測並糾正單個位錯誤。
一個類似的演算法，Luhn 演算法，用於驗證信用卡號碼。
文字壓縮 是計算中的另一項重要任務。以下活動演示了壓縮演算法的工作原理：http://csunplugged.org/sites/default/files/activity_pdfs_full/unplugged-03-text_compression.pdf
為什麼搜尋很重要？我們每天都在做。這也是一項好生意。谷歌的使命是整理世界資訊並使其普遍可訪問和使用。顯然，能夠快速找到我們需要的 資訊非常有用且有利可圖。
我們可以透過順序遍歷資訊列表並檢查每個資訊來始終找到一條資訊。你能用虛擬碼或流程圖符號描述演算法嗎？結構上，該演算法應該類似於“查詢最大數字”演算法。該演算法需要兩個輸入：列表和我們要查詢的目標專案。重複步驟是獲取下一個專案並將其與目標進行比較。用於比較的資訊也稱為鍵，因為它決定搜尋是否成功。例如，如果我們有一個學生列表，我們可以按姓氏、出生日期或鞋碼來搜尋學生，這些都是搜尋鍵。
順序搜尋很簡單，但如果我們經常需要執行它，則成本可能很高。但是，如果列表按搜尋鍵排序，我們可以利用資料的這種排序屬性來使用更好的演算法。想想一本教科書的索引、電話簿或字典。它們都是以某種方式排序的。例如，電話簿中的家庭電話號碼通常按所有者的姓氏排序，而商務電話號碼按商務型別排序。字典或教科書的索引中的條目按字母順序排序。當我們搜尋資訊時，這種有序性如何幫助我們？它允許我們估計搜尋目標的位置。 數字猜測遊戲很好地說明了這個想法。如果數字列表是隨機的但按升序排序，我們總是可以猜測目標數字位於搜尋範圍的中間（最初是整個列表）。如果我們運氣不好，我們可以消除一半的候選者——如果中間的數字大於搜尋目標，新的搜尋範圍將是先前搜尋範圍的前半部分，否則是後半部分。想象一下比較次數的減少！我們將在討論演算法複雜度時詳細研究該演算法。
請觀看以下影片 演算法如何塑造我們的世界。你能解釋演算法正在以哪些方式塑造我們的世界嗎？
在計算的世界裡，我們透過量化資訊來儲存和處理資料（資訊的表示）。這種量化過程將世界簡化為可計數和可衡量的事物，並強調抽象和效率（速度）。我們不能被現實的抽象所迷惑，認為它們就是真實的世界，就像抽象主義那樣。正如弗雷德里克·布魯克斯警告我們，“模型是對現實世界中令人恐懼的複雜問題的有意簡化，以幫助我們解決問題。地圖並非地形。”