# Mathematics for Computer Science ## 概要 MIT の学部科目 *6.042J / 18.062J Mathematics for Computer Science* の教科書である。計算機科学で用いる数学的モデルと手法を、**証明(proof)を中核に据えて**解説する。著者らは「証明は真の理解のために不可欠である」という数学者としての信念を共有しており、加えて証明が計算機科学で果たす役割の増大 — ソフトウェアとハードウェアが常に正しく振る舞うことの保証は、いかなる量のテストによっても達成できない — を本書の動機に挙げている。(Source: [[Mathematics for Computer Science]] Part I 序論) 本書の特徴は、抽象的な数学を導入したあと必ず計算機科学の具体的な問題へ降ろす点にある。整列原理と帰納法は状態機械によるプログラム検証へ、数論は RSA 公開鍵暗号へ、グラフ理論は通信ネットワークのトポロジ設計と試験時間割の彩色へ、確率は乳がん検診の偽陽性と PageRank へ接続される。 ## 書誌情報 - **著者**: Eric Lehman(Google Inc.)、F. Thomson Leighton(MIT 数学科・CSAIL、Akamai Technologies)、Albert R. Meyer(MIT EECS・CSAIL) - **版**: revised Monday 18th May, 2015 - **ライセンス**: Creative Commons Attribution-ShareAlike 3.0(© 2015 Eric Lehman, F Tom Leighton, Albert R Meyer) - **構成**: 全 5 部・全 21 章(918 ページ)+ Bibliography・Glossary of Symbols・Index - **原本**: `.raw/books/mathematics-for-computer-science/` ## 構成と主要テーマ ### Part I: Proofs(第 1〜7 章) 数学的証明を「公理の集合から命題へ至る論理的演繹の連鎖」と定義し、その定義に含まれる 3 つの鍵概念 — 命題・論理的演繹・公理 — を順に展開する部である。序論は、司法における法的真理、ビジネスにおける権威的真理、物理学や生物学における科学的真理、統計学における確率的真理を並べたうえで、数学だけが持つ「証明」の特殊性を際立たせる。(Source: [[Mathematics for Computer Science]] Part I 序論) → [[@2015__MIT__Mathematics for Computer Science - Chapter 1 What is a Proof?]] — 命題・述語・公理的方法を導入し、含意・同値・場合分け・背理法という 4 つの基本的な証明パターンを提示する、本書全体の入口。 → [[@2015__MIT__Mathematics for Computer Science - Chapter 2 The Well Ordering Principle]] — 整列原理を「最小の反例」を取る証明テンプレートとして定式化し、素因数分解の存在証明に適用したうえで整列集合へ一般化する。 → [[@2015__MIT__Mathematics for Computer Science - Chapter 3 Logical Formulas]] — 命題論理と述語論理の記法・意味論を体系化し、標準形と SAT 問題、そして P 対 NP 問題へ至る。 → [[@2015__MIT__Mathematics for Computer Science - Chapter 4 Mathematical Data Types]] — 集合・列・関数・二項関係・有限濃度を定義し、Mapping Rule によって以降の章の土台を築く。 → [[@2015__MIT__Mathematics for Computer Science - Chapter 5 Induction]] — 通常の帰納法・強帰納法・整列原理が相互に翻訳可能であることを示し、Floyd の不変条件原理と状態機械によるプログラム検証の枠組みを確立する。 → [[@2015__MIT__Mathematics for Computer Science - Chapter 6 Recursive Data Types]] — 再帰的データ型を基底部と構成子部で定義し、構造的帰納法を括弧整合列・算術式・Ackermann 関数に適用する。 → [[@2015__MIT__Mathematics for Computer Science - Chapter 7 Infinite Sets]] — 有限濃度を無限へ拡張し、Cantor の対角線論法から停止性問題の決定不能性を導き、Russell のパラドックスを経て ZFC と公理的方法の限界に立ち返る。 ### Part II: Structures(第 8〜12 章) 構造を持つ対象を扱う部である。序論は、整数を「全整数の集合・基本演算の集合・素数のような重要な部分集合」という複数の異なる部分からなる構造として捉える視点を示し、そこからグラフ(ネットワーク)へ進む。コードを書くにせよ、最適化問題を解くにせよ、ネットワークを設計するにせよ、扱うのは構造である、というのが部の主張である。(Source: [[Mathematics for Computer Science]] Part II 序論) → [[@2015__MIT__Mathematics for Computer Science - Chapter 8 Number Theory]] — 整除性・最大公約数・素数・合同算術・Euler の定理を積み上げ、Alan Turing の逸話を軸に RSA 公開鍵暗号方式を構築する。 → [[@2015__MIT__Mathematics for Computer Science - Chapter 9 Directed graphs & Partial Orders]] — 有向グラフの語彙と DAG のスケジューリング理論を導入し、関係の性質を軸に半順序・全順序・積順序・同値関係へ一般化する。 → [[@2015__MIT__Mathematics for Computer Science - Chapter 10 Communication Networks]] — 完全二分木・2 次元アレイ・バタフライネット・Beneš ネットの 4 トポロジを、直径・スイッチ数・レイテンシ・輻輳の 4 指標で比較する。 → [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]] — 次数と握手補題から同型・二部マッチング・安定結婚問題・彩色・連結性・木と最小全域木までを扱い、本書のグラフ理論の主要語彙を確立する。 → [[@2015__MIT__Mathematics for Computer Science - Chapter 12 Planar Graphs]] — 平面グラフを平面描画と平面埋め込みの 2 通りで定義し、オイラーの公式から K5・K3,3 の非平面性・5-彩色定理・正多面体の分類・Kuratowski の特徴づけを導く。 ### Part III: Counting(第 13〜15 章) 数え上げの部である。序論は「5 種類あるドーナツから 1 ダース選ぶ方法の数」と「ちょうど 4 個の 1 を含む 16 ビット数の個数」がともに 1820 になることを引き合いに、直接数える以外の方法の必要性を示す。数え上げが計算機科学で重要な理由として、計算問題に要する時間と記憶領域の決定、パスワードと暗号鍵の空間の大きさ、そして確率論の基礎であることの 3 点を挙げている。(Source: [[Mathematics for Computer Science]] Part III 序論) → [[@2015__MIT__Mathematics for Computer Science - Chapter 13 Sums and Asymptotics]] — 年金の現在価値から出発し、積分限界法による和の近似、調和数、Stirling の公式、漸近記法の厳密な定義までを扱う、アルゴリズム解析の道具立て。 → [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] — 全単射の規則を起点に積・和・除法・部分集合の各規則を積み上げ、鳩の巣原理・包除原理・組合せ論的証明までを扱う Part III の中核。 → [[@2015__MIT__Mathematics for Computer Science - Chapter 15 Generating Functions]] — 母関数によって数列を代数的操作の対象へ翻訳し、数え上げ・部分分数分解・線形漸化式の解法を統一的に扱う。 ### Part IV: Probability(第 16〜20 章) 確率の部である。序論は確率を「最も重要でありながら最も理解されていない分野のひとつ」と位置づけ、乱択アルゴリズムやゲーム理論、情報理論と信号処理、暗号とデジタル著作権管理など計算機科学のほぼ全分野に確率が現れることを述べる。同時に「常識的直感はランダムな事象を含む問題ではまったく当てにならない」ことを繰り返し強調し、直感が破れる有名な問題を教材として選んでいる。(Source: [[Mathematics for Computer Science]] Part IV 序論) → [[@2015__MIT__Mathematics for Computer Science - Chapter 16 Events and Probability Spaces]] — モンティ・ホール問題と非推移的サイコロを題材に四段階法を導入し、確率空間・事象・確率関数を集合論の上に定式化する。 → [[@2015__MIT__Mathematics for Computer Science - Chapter 17 Conditional Probability]] — 条件付き確率と木図法の正当化、全確率の法則とベイズの規則(乳がん検診の陽性適中率が約 15% にとどまる例)、シンプソンのパラドックス、独立性と相互独立性を扱う。 → [[@2015__MIT__Mathematics for Computer Science - Chapter 18 Random Variables]] — 確率変数を標本空間上の関数として定義し、分布関数と代表的な分布、期待値とその線形性(独立性を要求しない点が核心)を導入する。 → [[@2015__MIT__Mathematics for Computer Science - Chapter 19 Deviation from the Mean]] — マルコフ・チェビシェフの不等式と分散の性質から、無作為抽出による推定、信頼水準と確率の区別、チェルノフ限界へ展開する。 → [[@2015__MIT__Mathematics for Computer Science - Chapter 20 Random Walks]] — 破産問題を 1 次元ランダムウォークとして解析し、わずかな不利さが破滅的に効くことを示したうえで、グラフ上のランダムウォークへ一般化して PageRank を定常分布として定義する。 ### Part V: Recurrences(第 21 章) 漸化式を単独で扱う部である。序論は、漸化式を「大きな問題を、簡単な基底の場合に達するまで段階的に小さな問題へ帰着させる」という計算機科学の広範な主題の一側面と位置づけ、この同じ発想が帰納法による証明と再帰アルゴリズムの双方の基礎にあることを指摘する。また、当てはめて検証する方法や展開して整理する方法が「非現実的なほど鮮やかな閃き」を要するのに対し、線形漸化式と分割統治漸化式の定型解法は計算が洞察に取って代わるという代償を伴う、と率直に述べている。(Source: [[Mathematics for Computer Science]] Part V 序論) → [[@2015__MIT__Mathematics for Computer Science - Chapter 21 Recurrences]] — ハノイの塔とマージソートを題材に漸化式の解法(推測と検証、展開と整理、特性方程式、Akra-Bazzi の公式)を体系化し、部分問題のサイズと個数が解の増大率を左右するという直感を養う、本書の締めくくり。 ## 影響と位置づけ MIT の 6.042J は計算機科学の学部課程における離散数学の標準的な入門科目であり、本書はその公式教科書として MIT OpenCourseWare を通じて広く公開されている。Creative Commons Attribution-ShareAlike 3.0 で提供されるため、教育目的での再配布と改変が認められている。 本書の構成上の特徴は、**証明技法を先に据え、そのうえで各分野を積む**点にある。多くの離散数学の教科書が題材ごとに章を並べるのに対し、本書は Part I 全体(7 章・230 ページ超)を証明の方法論に充てる。この配置は「証明はソフトウェアとハードウェアが常に正しく振る舞うことを保証する手段であり、それはいかなる量のテストによっても達成できない」という著者らの動機と対応している。(Source: [[Mathematics for Computer Science]] Part I 序論) ## 関連 - 著者: [[Eric Lehman]] / [[F. Thomson Leighton]] / [[Albert R. Meyer]] - 組織: [[MIT]] / [[MIT CSAIL]] / [[Akamai]] / [[Google]] - 本書に登場する人物: [[Euclid]] / [[Alan Turing]] / [[Georg Cantor]] / [[Bertrand Russell]] / [[Robert W. Floyd]] / [[Herman Chernoff]] - 主要概念: [[証明]] / [[整列原理]] / [[帰納法]] / [[有向グラフ]] / [[単純グラフ]] / [[数え上げ]] / [[確率空間]] / [[漸化式]] - 関連書籍: [[Mathematics for Machine Learning]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, CC BY-SA 3.0.