本書の目的と構成
この本の約束
本書は、理論計算機科学を次の3点で回収できるように設計しています。
- 理論の地図が手に入ること 集合・論理・形式言語・計算可能性・複雑性・アルゴリズム解析・情報理論・暗号・並行計算が、どの順序でつながっているかを一冊で俯瞰できます。
- 定義・定理・証明の読み方が身につくこと 本書は定義と定理を中心に進みます。単なる結果の暗記ではなく、「何を仮定し、何が言えて、どこが限界か」を読む練習を重視します。
- 理論と実装・研究の橋がかかること 実務メモ、練習問題、付録を通じて、理論がデータ構造・ネットワーク・暗号・並行計算の設計判断でどのように効くかを見失わないようにします。
対象読者
第一読者
- 情報系学部3〜4年生、または大学院初年度で、離散数学と基本的なプログラミング経験がある読者
- 講義ノートや断片的な知識を、一冊の流れとして整理したい読者
第二読者
- ソフトウェアエンジニア、研究開発職、技術リードで、理論計算機科学を体系で学び直したい読者
- 計算量、不可能性、モデルの仮定を踏まえて議論したい読者
非対象読者
- 集合・論理・関数・証明技法の基礎がまだなく、補強しながら読む準備がない読者
- 競技プログラミングや面接対策の即効性だけを求める読者
- 暗号理論や並行計算だけを専門書レベルで深掘りしたい読者
この本で得られること
- 理論計算機科学の主要領域の位置づけを、章間の依存関係とともに説明できる
- 抽象的な定義や定理を、具体例・反例候補・証明スケッチに落として理解できる
- 実装や設計の議論で、計算量・モデル・限界を踏まえて判断材料を整理できる
この本ではやらないこと
- すべての分野を専門書レベルまで掘り下げること
- 実装パターン集やフレームワーク解説として振ること
- 最新研究を網羅的にレビューすること
- 数学基礎がまったくない状態からの入門を一冊で完結させること
本書の構成
Part I: 数学的基礎（第1〜3章）
本書の土台です。記法、論理、証明、形式言語の基本をそろえ、後続章で前提として使う言葉を共有します。
- 入口ページ: Part I の狙いと読み方
- 第1章: 集合論、論理学、証明技法
- 第2章: 計算理論の基礎とチューリング機械
- 第3章: 形式言語とオートマトン理論
Part II: 計算理論（第4〜6章）
理論計算機科学の中核です。何が計算できるか、どこまで効率化できるか、アルゴリズムをどう数学的に読むかを扱います。
- 入口ページ: Part II の狙いと読み方
- 第4章: 計算可能性理論（決定可能性と還元可能性）
- 第5章: 計算複雑性理論
- 第6章: アルゴリズムの数学的解析
Part III: 高度なトピック（第7〜9章）
理論が具体的な計算モデルや構造にどう現れるかを見るパートです。実装や設計判断との距離が縮まります。
- 入口ページ: Part III の狙いと読み方
- 第7章: データ構造の理論
- 第8章: グラフ理論とネットワーク
- 第9章: 論理学と形式的手法
Part IV: 応用理論（第10〜12章）
特定領域へ展開するパートです。情報理論・暗号・並行計算を通じて、理論計算機科学の応用先を見渡します。
- 入口ページ: Part IV の狙いと読み方
- 第10章: 情報理論
- 第11章: 暗号理論の数学的基礎
- 第12章: 並行計算の理論
付録の使い方
付録は本文の後ろにある資料ではなく、学習の戻り先として使う想定です。
- 付録A: 記法や読み方で迷ったときに戻る
- 付録B: 第1・3・5・6・8章で、定義やアルゴリズムをコードに落としたときの挙動を確認する
- 付録C: 演習と証明の回収に使う
- 付録D: 用語の再確認に使う
- 付録E: 各章の理論がどのシステム設計・解析に現れるかを確認する
- 付録F: 各章を読み終えた直後に、到達目標を自己点検する
- 付録G: AI/ML と理論計算機科学の接点を、PAC 学習・VC 次元・最適化・情報理論の観点から見直す
- 付録H: 図版を後から探し直し、直観図・例示図の役割を確認する
- ダウンロードページ: Web版以外の提供状況と、現時点で可能なオフライン読書方法を確認する
本書は、理論計算機科学を一度で完全習得させる本ではありません。代わりに、「どこから読み始め、どこへ戻り、次に何を読むか」が分かる構造を提供することで、研究・講義・実務のそれぞれで再利用できる土台を目指します。