第 4 章　馮·紐曼、波蘭數學家與排序、博弈演算法的創世紀#

本章導言#

戰後十年，演算法從戰爭工具變成科學方法：馮·紐曼一人貢獻了三塊基石——存儲程序計算機、歸併排序、賽局理論；Dijkstra 則以一個年輕工程師的 20 分鐘，寫下最短路徑的永恆程序。本章三節。

4.1 馮·紐曼（John von Neumann）與排序演算法：1945 年歸併排序的思維脈絡與 EDVAC 報告的存儲程序革命#

4.1.1 歸併排序：1945 年的原始碼#

馮·紐曼 1945 年為 EDVAC 手寫的程式清單中包含歸併排序——被視為已存檔最早的複雜演算法實作之一。其分治思想：

比較型排序的下界 \(\Omega(n\log n)\) 由決策樹論證給出（\(n!\) 個排列、二叉樹深度至少 \(\log_2 n!\)）——歸併排序恰好貼住下界。他還在清單中插入自檢碼（對拍）——演算法測試思想的遠古萌芽。

4.1.2 EDVAC 報告：存儲程序架構的出生證明#

1945 年 6 月 30 日，《First Draft of a Report on the EDVAC》以馮·紐曼單獨署名發布（實為 ENIAC 團隊 Eckert、Mauchly 等的共同成果，署名之爭成為計算機史著名公案）。核心範式：

1. 指令與數據同存於記憶體——程序可被當作數據修改；
2. 二進制、電子存儲、序列執行五大單元（算術、控制、記憶、輸入、輸出）。

「馮·紐曼架構」自此刻成為 80 年來計算機的默認形態（哈佛架構為其變體）。

4.1.3 蒙特卡洛方法：與排序同源的統計演算法#

馮·紐曼與 Ulam、Metropolis 在洛斯阿拉莫斯以隨機抽樣解中子輸運問題（1946–47），命名為蒙特卡洛（Metropolis 取名）。偽亂數生成器「中平方法」（middle-square）亦出於馮·紐曼——演算法家族自此有了「以隨機換確定性」的支系（直通第 7 章馬可夫鏈）。

4.1.4 前因後果#

• 前因：3 章戰時計算需求＋ENIAC 的工程經驗＋數理邏輯傳統。
• 事件：1945 EDVAC 報告、1945 歸併排序程式、1946 蒙特卡洛。
• 後果：計算機與演算法正式合流；4.2 賽局理論與 4.3 Dijkstra 將分別把「策略」與「路徑」數學化。

下一節：4.2 賽局理論