理論計算機科学教科書
本書は、離散数学の基礎を持つ読者が、理論計算機科学を「章ごとの断片知識」ではなく、集合・論理 → 計算可能性・複雑性 → データ構造・グラフ・論理 → 情報理論・暗号・並行計算という流れで体系的に学ぶための日本語教材です。
この本の約束
- 定義・定理・証明の読み方を身につけ、理論計算機科学の主要領域を一冊で俯瞰できるようにする
- 実務メモ・練習問題・付録を通じて、理論が実装や設計判断にどう接続するかを見失わないようにする
- 研究室配属前後の学習、講義の補助教材、実務者の再学習に耐える「地図」と「戻り先」を提供する
想定読者
- 第一読者: 情報系学部3〜4年生、または大学院初年度で、離散数学と基本的なプログラミング経験がある読者
- 第二読者: 実務経験はあるが、計算可能性・複雑性・形式言語・情報理論を体系で学び直したいソフトウェアエンジニア
非対象読者
- 集合・論理・関数・証明の基礎をまだ持っておらず、補強しながら読む準備がない読者
- 競技プログラミングの即効テクニックや面接対策だけを短時間で得たい読者
- 暗号理論や並行計算だけを専門書レベルで深掘りしたい読者
この本で得られること
- 計算可能性・複雑性・形式言語・アルゴリズム解析・情報理論・暗号・並行計算の位置づけを相互関係ごと説明できる
- 抽象的な定義や定理を、具体例・証明スケッチ・反例候補と結びつけて読み解ける
- 実装や設計の議論で、計算量・不可能性・モデルの仮定を踏まえて話せるようになる
読み方の最短コース
- 通読コース:
はじめに → 前提知識 → 第1章〜第12章 → 付録C。体系的に学び切りたい読者向け - 講義補助コース:
第1章〜第3章 → 講義対象章 → 付録A/C。大学講義や輪読の補助教材として使う読者向け - 実務者の拾い読み:
前提知識 → 第6章・第7章・第8章 → 必要に応じて第4章・第5章・第10章〜第12章。業務に関係する理論から入りたい読者向け - 再学習コース:
本書の目的と構成 → 前提知識の自己診断 → 苦手章の再読 → 付録C/F。学び直しや抜け漏れ補完向け
はじめに
前提知識
- 必要: 集合・論理・関数・帰納法・漸近記法・基本的なプログラミング
- 推奨: 離散数学、データ構造とアルゴリズム、確率、線形代数
- あると楽: 数論、抽象代数、形式言語の既習、英語論文への抵抗の少なさ
所要時間
- 通読: 約5.5〜8.5時間（本文量ベースの概算。コードブロック除外、400〜600文字/分で換算）
- 演習・付録・参考文献まで含めた学習時間は、講義利用か自習利用かで大きく変動する。
ライセンス
本書は CC BY-NC-SA 4.0 で公開されています。商用利用は別途契約が必要です。
目次
Part I: 数学的基礎（第1〜3章）
Part II: 計算理論（第4〜6章）
Part III: 高度なトピック（第7〜9章）
Part IV: 応用理論（第10〜12章）
付録
その他
著者: ITDO Inc.
バージョン: 1.1.2
最終更新: 2026-03-13