同構：編程中的數學

劉新宇，亞馬遜中國研發中心研發經理，負責分佈式倉儲物流系統的開發。1999年和2002年在清華大學自動化系分別獲得學士和碩士學位。長期專註於函數式基礎算法，著有《算法新解》一書（2017年出版）

第1章 數字
1.1 數的誕生
1.2 皮亞諾自然數公理
1.3 自然數和計算機程序
1.4 自然數的結構
1.5 自然數的同構
1.6 形式與結構
第2章 遞歸
2.1 萬物皆數
2.2 歐幾里得算法
2.2.1 歐幾里得和《幾何原本》
2.2.2 歐幾里得算法概述
2.2.3 擴展歐幾里得算法
2.2.4 歐幾里得算法的意義
2.3 λ演算
2.3.1 表達式化簡
2.3.2 λ抽象
2.3.3 λ變換規則
2.4 遞歸的定義
2.5 λ演算的意義
2.6 更多的遞歸結構
2.7 遞歸的形式與結構
2.8 附錄：倒水趣題完整程序
第3章 對稱
3.1 什麽是對稱
3.2 群
3.2.1 群的定義
3.2.2 幺半群與半群
3.2.3 群的性質
3.2.4 置換群
3.2.5 群與對稱
3.2.6 旋轉對稱與循環群
3.2.7 分圓方程
3.2.8 子群
3.2.9 拉格朗日定理
3.3 環與域
3.3.1 環的定義
3.3.2 除環和域
3.4 伽羅瓦理論
3.4.1 擴域
3.4.2 從牛頓、拉格朗日到伽羅瓦
3.4.3 自同構和伽羅瓦群
3.4.4 伽羅瓦基本定理
3.4.5 可解性
3.5 附錄：伽羅瓦群
第4章 範疇
4.1 範疇概述
4.1.1 範疇的例子
4.1.2 箭頭≠函數
4.2 函子
4.2.1 函子的定義
4.2.2 函子的例子
4.3 積與和
4.3.1 積與和的定義
4.3.2 積與和的性質
4.3.3 積與和作為函子
4.4 自然變換
4.4.1 自然變換的例子
4.4.2 自然同構
4.5 數據類型
4.5.1 起始對象和終止對象
4.5.2 冪
4.5.3 笛卡兒閉和對象算術
4.5.4 多項式函子
4.5.5 F-代數
4.6 小結
4.7 擴展閱讀
4.8 附錄：例子代碼
第5章 融合
5.1 疊加-構建的融合
5.1.1 列表的疊加操作
5.1.2 疊加-構建融合律
5.1.3 列表的構建形式
5.1.4 使用融合律化簡
5.1.5 類型限制
5.1.6 用範疇論推導融合律
5.2 巧算100
5.2.1 窮舉法
5.2.2 改進
5.3 小結和擴展閱讀
5.4 附錄：巧算100問題的代碼
第6章 無窮
6.1 無窮概念的提出
6.1.1 無窮的哲學
6.1.2 窮竭法與微積分
6.2 潛無窮與編程
6.3 實無窮的思考
6.3.1 無窮王國的花園
6.3.2 一一對應與無窮集合
6.3.3 可數無窮與不可數無窮
6.3.4 戴德金分割
6.3.5 超限數和連續統假設
6.4 無窮與藝術
6.5 附錄：例子代碼
6.6 附錄：康托爾定理的證明
6.7 附錄：巴赫《音樂的奉獻》無限上升的卡農
第7章 悖論
7.1 計算的邊界
7.2 羅素悖論
7.3 數學基礎的分歧
7.3.1 邏輯主義
7.3.2 直覺主義
7.3.3 形式主義
7.3.4 公理集合論
7.4 哥德爾不完全性定理
7.5 不完全性定理的證明
7.5.1 構建形式系統
7.5.2 哥德爾配數
7.5.3 構造自我指涉
7.6 萬能的程序與對角線證明
7.7 尾聲
附錄
加法交換律的證明
積與和的唯一性
集合的笛卡兒積和不相交並集構成積與和的證明
參考答案
參考文獻