77
《偉大的計算原理》一導讀
前 言
就在70年前，除了少數專家之外，沒有人聽說過計算機。現在，計算機、軟件和網絡無處不在。在地球上的任何地方，它們都以更快的發展速度給我們的生活帶來了各種各樣的好處。
在這麼短的幾十年中，我們學會了設計和建造如此規模的係統，這真是一件令人吃驚的事。如今，通過支持大規模合作，計算技術使得知識工作能夠自動化，同時也在不斷擴大生產力。第二次機器革命正撲麵而來1。這是如何實現的？是什麼樣的偉大思想使這一切成為可能？
計算機給我們帶來好處的同時也帶來憂慮。計算機帶來的自動化是否會使很多工人失業？計算機是否會成為終極監督工具而使我們失去隱私？計算機是否會發展出超越人類的智能？計算機能做的事情會有限製嗎？
我們相信，理解計算的原理和法則可以幫助人們理解計算是如何完成如此之多的工作的，並消除他們的憂慮。為此我們寫了這本書，書中介紹了關於計算的一些最重要的原理，並以任何對計算有一定了解的人都能理解的方式呈現。
計算機科學（computer science）不隻是設計計算設備的工程領域，它是一門關於信息處理的科學。計算受科學原理和法則支配，這些原理和法則告訴我們計算機能做什麼、不能做什麼。信息的法則揭示了根據物理法則無法直接得出的新的可能性和限製。專家們賦予計算機許多計算科學（computing science）告訴我們不可能擁有的能力，同時，這些專家又低估了計算機真正的能力。
計算機科學與很多其他領域相互交叉。許多科學與工程領域都有計算（computational）分支，如計算物理、計算化學、生物信息學、數字化產品設計與製造、計算社交網絡、計算心髒病學等2。各層次的教育者正努力在他們擁擠的課程表中加入計算相關的課程，以保證課程體係的先進性。但仍有很多中學由於缺少計算機科學方麵的教師而不能開設計算機課程。在商業領域，諸如“大數據”“雲計算”“網絡安全”等熱門詞匯也散發出共同的信號，期望“計算原理”在數據管理、分布式計算、信息保護中發揮作用。
一直以來，人們把計算看作一個按照摩爾定律高速發展的技術領域3。而我們的觀點有所不同，我們相信計算更應該被描述為一個科學領域，具有跨越所有計算技術以及人工或自然的信息處理的基本原理。我們需要一種新的方法來刻畫計算。就像望遠鏡之於天文學、顯微鏡之於生物學，計算機是計算的工具，而非計算的研究對象。
本書的重要原理框架（great principles framework）就是這樣一種新的方法。它將計算原理分為6個類別：通信、計算、協作、記憶（存儲）、評估和設計。計算原理是指用來指導或約束我們如何操縱物質和能量來進行計算的聲明。計算原理可以是：（1）重現，包括描述可重複的因果關係的定律、過程及方法；（2）行為準則。局部性原理（locality principle）就是重現的一個例子：每一個計算在一定的時間間隔內，其對數據的訪問都聚集在一個小的子集裏。行為準則的一個例子就是網絡程序員將協議軟件劃分為多個層次。所有這些原理的目的，都是希望通過增進理解和降低複雜性從而得到良好的設計。
每種計算技術都利用了這些類別的原理。這個框架是廣泛和全麵的，覆蓋了計算的每個部分，包括算法、係統和設計。
從事計算工作的人員形成了許多計算領域（computing domain）——實踐社區，如人工智能、網絡安全、雲計算、大數據、圖形學以及科學計算（computational science）等。這些領域都專注於推進領域向前發展並與其他社區互動，它們既從計算原理中獲益，又受其約束。沒有這些計算領域的原理框架是不完整的。
由於這6個類別過於龐大，我們決定將其所覆蓋的範圍分成11個更容易管理的模塊，就像你在目錄中看到的那樣。關於這一點，我們將在第1章中詳細說明。
從機器到通用的數字化
計算的機器是早期計算領域的關注中心（從20世紀40年代到20世紀60年代）。計算被看作機器執行複雜演算、解方程、破譯密碼、分析數據及管理業務流程的行為。那時的先驅們將計算機科學定義為研究以計算機為中心的各種現象。
然而，這些年來，這一定義變得越來越沒有意義。20世紀80年代的科學計算運動認為，計算是除了傳統的理論和實驗之外的一種新的做科學研究的方法。他們使用“計算思維”（computational thinking）這個術語作為研究和問題求解的思維訓練，而不是作為建造計算機的方法。十年之後，一些領域的科學家開始發現各自領域內的自然信息處理，其中包括生物學（DNA翻譯）、物理學（量子信息4）、認知科學（腦力過程）、視覺（圖像識別）和經濟學（信息流）。計算的重點從機器轉變到信息處理，包括人工信息和自然信息。
現在，隨著幾乎所有事物的數字化，計算進入了人們的日常生活，包括求解問題的新方法，藝術、音樂、電影的新形式，社交網絡，雲計算，電子商務，以及新的學習方法等。用計算作比喻成為日常語言中的必要組成部分，比如“我的軟件有反應了”或“我的大腦崩潰了需要重啟”這樣的表達方式。
為了應對這些變化，各大學一直都在設計新的基於原理的方法來開展關於“計算”的教學。華盛頓大學是這方麵的先驅之一，它開發了關於熟練掌握信息技術的一門課程和教材，目前已經在高中和大學中廣泛使用，以幫助學生學習並應用基本計算原理5。教育考試基金會（Educational Testing Foundation）與美國國家自然科學基金會（National Science Foundation）合作，開發了一門新的基於計算原理的先修課程6。現在很多人使用“計算思維”這個詞，指的是在很多領域和日常生活中使用計算原理，而不僅局限於科學計算7。
隨著計算領域的日趨成熟，它吸引了其他領域的眾多追隨者。我們知道有16本書是為感興趣的非專業人員來解釋計算的各個方麵8。大部分書關注的隻是單個部分的內容，如信息、編程、算法、自動化、隱私以及互聯網原理等。本書則將這個領域作為一個整體來看待，給出所有各部分如何組合在一起的係統敘述。讀者會發現在所有這些部分的背後是一套連貫的原理。
根據教授從其他專業轉到計算機科學的研究生的經驗，我們發現對於初學者來說，原理框架比技術框架更容易理解。當早期核心技術很少的時候，用技術思想的觀點來描述該領域是一種好方法。1989年，美國計算機協會（Association for Computing Machinery，ACM）列出了9大核心技術。而在2005年，ACM列出了大約14種，到了2013年，則有約18種。本書的6類原理框架並不是重新定義計算的核心知識，但它確實提供了一種看待該領域並降低其表麵複雜性的新方式。
目 錄
第1章 作為科學的計算
計算的範型
計算的重要原理
計算在科學中的位置
本書的關注點
總結
致謝
第2章 計算領域
領域和基本原理
信息安全
人工智能
雲計算
大數據
總結
第3章 信息
信息的表示
通信係統
信息的測量
信息的轉換
交互係統
解決悖論
信息和發現
總結
致謝
第4章 機器
機器
可以計算的機器
程序及其表示
棧式計算機：計算機係統的一種簡單模型
過程與異常
選擇的不確定性
結論
第5章 程序設計
程序、程序員和程序設計語言
程序設計實踐
程序中的錯誤
自動翻譯
總結
第6章 計算
簡單問題
實例1 簡單的線性搜索
實例2 二分搜索
實例3 排序
實例4 矩陣乘法
指數級困難問題
實例5 所有的十位數
實例6 背包問題
實例7 參觀所有城市
實例8 合數分解
計算困難但容易驗證的問題
NP完全
不可計算問題
總結
第7章 存儲
存儲係統
存儲器的基本使用模型
命名
映射
虛擬存儲
共享
能力
認證
層級結構中的定位
為什麼局部性是基礎
結論
第8章 並行
並行計算的早期方向
並行係統的模型
協作的順序進程
功能係統
事件驅動的係統
MapReduce係統
協作的順序進程
功能係統
結論
第9章 排隊
排隊論遇上計算機科學
用模型計算和預測
服務器、作業、網絡和規則
瓶頸
平衡方程
ATM
電話交換機
分時係統
用模型來計算
結論
第10章 設計
什麼是設計
軟件係統的準則
需求
正確性
容錯性
時效性
適用性
設計原理、模式和示意
原理
模式
示意
軟件係統的設計原理
層級式聚合
封裝
級別
虛擬機
對象
客戶端與服務器
總結
第11章 網絡
彈性網絡
數據包交換
互聯網絡協議
傳輸控製協議
客戶端與服務器
域名係統
網絡軟件的組織結構
萬維網
網絡科學
致謝
第12章 後記
沒有意識的機器
智能機器
架構和算法
經驗思維
一個嶄新的機器時代來臨
我們的思維方式正在轉變
設計的核心性
各章概要
注釋
參考文獻
索引
最後更新：2017-06-26 14:02:07