付録

目次

1. 附録A：学習ロードマップ(詳細版)
2. 附録B：コードで学ぶ例題集
3. 附録C：2026年の推奨学習リソース
4. 附録D：技術面接の CS 基礎チェックリスト
5. 附録E：よくある質問(FAQ)
6. 附録F：2025-2026 年の CS トレンド
7. 附録G：実践トラブルシューティング入門
8. 附録H：理論的補完 — 計算理論の基礎

附録A：学習ロードマップ(詳細版)

A.1 段階別ロードマップ

【図31】CS 学習ロードマップ：

A.2 Lv.1 基礎(3ヶ月)

目標： 「プログラムが動く仕組み」の初歩を理解する

学ぶ内容：

• 2進数、文字コード(Unicode、UTF-8)
• 基本アルゴリズム(線形探索、二分探索、基本ソート)
• 基本データ構造(配列、連結リスト、スタック、キュー、ハッシュ)
• Big-O 記法
• 1つの言語を「動かせる」レベルまで(Python / JavaScript / Rust / Go / Java)

推奨リソース：

• 『プログラミングの基礎』浅井健一 — アルゴリズム思考
• Python 公式チュートリアル — 無料
• CS50x (Harvard) — Harvard の伝説的入門講座、日本語字幕あり
• Project Euler — 数学×プログラミング問題集

A.3 Lv.2 中級(6ヶ月)

目標： OS・ネットワーク・DB の全体像を理解する

学ぶ内容：

• プロセス・スレッド・メモリ・システムコール
• TCP/IP、HTTP、DNS、TLS
• RDB の設計、SQL、トランザクション
• 並行処理の落とし穴、ロック、冪等性
• 計算量を意識したコーディング

推奨リソース：

• Tanenbaum『モダンオペレーティングシステム』第 4 版
• 『マスタリング TCP/IP 入門編』竹下隆史ら
• 『達人に学ぶ SQL 徹底指南書』ミック
• MIT 6.006 Introduction to Algorithms
• CMU 15-213 Introduction to Computer Systems

A.4 Lv.3 上級(1年以上)

目標： 大規模システムを設計・運用できる基礎力

学ぶ内容：

• 分散システム(CAP、合意、一貫性モデル)
• Linux カーネル基礎、eBPF、パフォーマンス分析
• コンテナ、Kubernetes、マイクロサービス
• セキュリティ設計、暗号、脅威モデリング
• クエリ最適化、実行計画、MVCC

推奨リソース：

• Martin Kleppmann『Designing Data-Intensive Applications』(DDIA)
• Brendan Gregg『Systems Performance』2nd Edition
• Arpaci-Dusseau『Operating Systems: Three Easy Pieces (OSTEP)』(無料 PDF)
• Stanford CS144 Computer Networking — 現行の公式コースページ。TCP を自作する課題で有名
• MIT 6.5840 Distributed Systems — Raft 実装(formerly 6.824)

A.5 Lv.4 専門化

目標： 特定分野を深く掘る

選択肢：

• OS/カーネル：Linux カーネル、Rust for Linux、形式検証 seL4
• コンパイラ：LLVM、Rust、MLIR、型システム
• DB 内部：Postgres、RocksDB、CockroachDB、クエリ最適化
• ML システム：TensorFlow、PyTorch、CUDA、分散学習
• 暗号：楕円曲線、ゼロ知識証明、耐量子暗号
• 形式手法：Coq、Isabelle、TLA+、モデル検査
• ネットワーク：カーネルバイパス、XDP、DPDK、5G コア

A.6 つまずきやすいポイントと対策

附録B：コードで学ぶ例題集

B.1 二分探索

def binary_search(arr, target):
    """ソート済み配列 arr から target のインデックスを返す。なければ -1。"""
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

# 計算量 $O(\log n)$
assert binary_search([1, 3, 5, 7, 9, 11], 7) == 3
assert binary_search([1, 3, 5, 7, 9, 11], 4) == -1

B.2 マージソート

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(a, b):
    result, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result.extend(a[i:]); result.extend(b[j:])
    return result

# 計算量 $O(n \log n)$、安定ソート
assert merge_sort([5, 2, 8, 1, 9, 3]) == [1, 2, 3, 5, 8, 9]

B.3 ハッシュテーブルの素朴な実装

class HashMap:
    def __init__(self, size=16):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    def _hash(self, key):
        return hash(key) % self.size

    def put(self, key, value):
        bucket = self.buckets[self._hash(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key):
        bucket = self.buckets[self._hash(key)]
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(key)

m = HashMap()
m.put("apple", 100); m.put("banana", 200)
assert m.get("apple") == 100

B.4 BFS と DFS

from collections import deque

def bfs(graph, start):
    visited, queue = {start}, deque([start])
    order = []
    while queue:
        v = queue.popleft()
        order.append(v)
        for nb in graph.get(v, []):
            if nb not in visited:
                visited.add(nb)
                queue.append(nb)
    return order

def dfs(graph, start, visited=None, order=None):
    if visited is None: visited, order = set(), []
    visited.add(start); order.append(start)
    for nb in graph.get(start, []):
        if nb not in visited:
            dfs(graph, nb, visited, order)
    return order

g = {1: [2, 3], 2: [4], 3: [4, 5], 4: [], 5: []}
print(bfs(g, 1))  # [1, 2, 3, 4, 5]
print(dfs(g, 1))  # [1, 2, 4, 3, 5]

B.5 Dijkstra 最短経路

import heapq

def dijkstra(graph, start):
    dist = {v: float('inf') for v in graph}
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

g = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}
print(dijkstra(g, 'A'))  # {'A': 0, 'B': 1, 'C': 3, 'D': 4}

B.6 並行性：ロックとレースコンディション

import threading

# 危ない例：ロックなし
counter = 0
def incr_unsafe():
    global counter
    for _ in range(100000):
        counter += 1

threads = [threading.Thread(target=incr_unsafe) for _ in range(4)]
for t in threads: t.start()
for t in threads: t.join()
print(counter)  # 400000 にならないことが多い(GIL でも ++ は非アトミック)

# 安全：ロック使用
counter = 0
lock = threading.Lock()
def incr_safe():
    global counter
    for _ in range(100000):
        with lock:
            counter += 1

threads = [threading.Thread(target=incr_safe) for _ in range(4)]
for t in threads: t.start()
for t in threads: t.join()
print(counter)  # 400000

B.7 並行性：プロデューサ・コンシューマ

import threading, queue, time

q = queue.Queue(maxsize=10)

def producer():
    for i in range(20):
        q.put(i)
        print(f"Produced {i}")
        time.sleep(0.05)
    q.put(None)  # 終了シグナル

def consumer():
    while True:
        item = q.get()
        if item is None: break
        print(f"Consumed {item}")
        time.sleep(0.1)

threading.Thread(target=producer).start()
threading.Thread(target=consumer).start()

B.8 SQL 基本パターン

-- 外部キーで関係を守る
CREATE TABLE authors (id INT PRIMARY KEY, name TEXT NOT NULL);
CREATE TABLE books (
  id INT PRIMARY KEY,
  title TEXT NOT NULL,
  author_id INT NOT NULL REFERENCES authors(id)
);

-- インデックス
CREATE INDEX idx_books_author ON books(author_id);

-- JOIN
SELECT b.title, a.name
FROM books b
JOIN authors a ON b.author_id = a.id
WHERE a.name LIKE '%太郎'
ORDER BY b.title;

-- トランザクション
BEGIN;
UPDATE accounts SET balance = balance - 1000 WHERE id = 1;
UPDATE accounts SET balance = balance + 1000 WHERE id = 2;
COMMIT;

-- EXPLAIN で実行計画確認
EXPLAIN ANALYZE
SELECT * FROM orders WHERE user_id = 42 AND created_at > NOW() - INTERVAL '7 days';

B.9 HTTP サーバ(最小)

# Python 3 標準ライブラリだけで動く HTTP サーバ
from http.server import BaseHTTPRequestHandler, HTTPServer

class Handler(BaseHTTPRequestHandler):
    def do_GET(self):
        self.send_response(200)
        self.send_header('Content-Type', 'application/json; charset=utf-8')
        self.end_headers()
        self.wfile.write(b'{"message": "hello"}')

server = HTTPServer(('0.0.0.0', 8080), Handler)
print("Listening on :8080")
server.serve_forever()

B.10 ハッシュ関数でファイル整合性確認

import hashlib

def sha256_of(path):
    h = hashlib.sha256()
    with open(path, 'rb') as f:
        for chunk in iter(lambda: f.read(1 << 20), b''):
            h.update(chunk)
    return h.hexdigest()

print(sha256_of('/tmp/test.bin'))

附録C：2026年の推奨学習リソース

C.1 MOOC(無料オンライン講義)

• Harvard CS50x — 定番の総合入門。教材公開が安定しており、独学の出発点に向く
• MIT 6.006 Introduction to Algorithms — アルゴリズムの決定版
• MIT 6.S081 Operating Systems — xv6 で自作 OS
• MIT 6.824 Distributed Systems — Raft 実装
• CMU 15-213 Computer Systems — CSAPP 教科書対応
• CMU 15-445 Database Systems — DB 内部の決定版
• Stanford CS144 Computer Networking — TCP を C++ で自作
• Stanford CS106B Programming Abstractions — データ構造・再帰・抽象化の導線として優秀
• Berkeley CS61A Structure and Interpretation of Computer Programs — Scheme/Python で SICP
• Berkeley CS61B Data Structures — Java でのデータ構造
• Coursera - Algorithms by Princeton — Robert Sedgewick

C.2 教科書(紙／電子)

初級：

• CS50x のテキスト相当(Harvard 公式)
• 『アルゴリズム図鑑』石田保輝(入門用ビジュアル)
• 『プログラマのための論理パズル』Dennis Shasha

中級：

• 『モダンオペレーティングシステム 第4版』Tanenbaum
• 『データベースシステム概念 第7版』Silberschatz
• 『マスタリング TCP/IP 入門編』竹下隆史
• 『達人に学ぶ SQL 徹底指南書』ミック
• 『リーダブルコード』Boswell & Foucher

上級(英語教科書が多い)：

• 『Designing Data-Intensive Applications』(DDIA) Martin Kleppmann — 分散システム必読
• 『Systems Performance (2nd Ed.)』 Brendan Gregg — 性能工学の集大成
• 『Operating Systems: Three Easy Pieces (OSTEP)』 Arpaci-Dusseau — 無料 PDF
• 『Computer Systems: A Programmer’s Perspective (CSAPP)』 Bryant & O’Hallaron
• 『The Art of Multiprocessor Programming』 Herlihy & Shavit — 並行プログラミングの聖典
• 『Introduction to Algorithms (CLRS)』 Cormen et al. — アルゴリズム百科事典
• 『Database Internals』 Alex Petrov — B-tree から LSM まで
• 『Understanding Distributed Systems』 Roberto Vitillo — 短くて読みやすい
• 『Site Reliability Engineering』 Beyer et al. — Google の SRE 哲学(無料)

C.3 インタラクティブ学習サイト

• LeetCode — コーディング面接対策
• AtCoder — 日本の競技プログラミング
• Codeforces — 世界的なコンテスト
• HackerRank — 会社との接続強い
• Brilliant — CS の離散数学とアルゴリズム
• Execute Program — 対話型で Git、SQL、JS を学ぶ

C.4 日本語コミュニティ・学習サイト

• Qiita — エンジニア記事
• Zenn — 品質重視の技術記事
• 情報処理推進機構 (IPA) — 基本情報技術者・応用情報技術者試験
• paiza — 日本語のコーディング練習
• AtCoder — 競技プログラミング(日本最大)

C.5 動画・YouTube

• Computerphile — Brady Haran、CS の人気解説
• 3Blue1Brown — 数学と CS の視覚化
• Ben Eater — ブレッドボードでの自作コンピュータ
• Fireship — 最新技術を短く
• GeeksforGeeks — CS 基礎の定番サイト

C.6 ポッドキャスト・ブログ

• Brendan Gregg’s Blog — 性能工学
• Martin Fowler’s Blog — 設計論
• High Scalability — 大規模システム事例
• The Morning Paper — 論文要約(休刊だがアーカイブ貴重)
• ACM Queue — 実務寄り CS
• LWN.net — Linux カーネル深掘り
• Software Engineering Daily — 技術ポッドキャスト

附録D：技術面接の CS 基礎チェックリスト

D.1 アルゴリズムとデータ構造(必須)

1. 配列と連結リストの違いを、計算量の観点から述べよ。
2. ハッシュテーブルの衝突時の処理方法を 2 つ挙げよ。
3. 二分探索木の最悪計算量はなぜ $O(n)$ になりうるか。
4. クイックソートとマージソートの利点と欠点を比較せよ。
5. 動的計画法とメモ化の違いは？
6. BFS と DFS の使い分けは？
7. ダイクストラ法が負の辺で動かない理由は？
8. ヒープを使って Top-K 要素を求める方法は？

D.2 OS

9. プロセスとスレッドの違いは？
10. 仮想メモリがなぜ必要か？
11. コンテキストスイッチで何が起きるか？
12. デッドロックの 4 条件を述べよ。
13. fork() と exec() の役割は？
14. ページフォルトが常に異常ではない理由は？
15. システムコールとライブラリ関数の違いは？

D.3 ネットワーク

16. TCP と UDP の違いを 3 点以上述べよ。
17. https://example.com を開くまでに何が起きるか、順を追って説明せよ。
18. DNS の役割と、木構造であることの意味は？
19. TLS は何を守るか？ 3 つ挙げよ。
20. HTTP/1.1 → HTTP/2 → HTTP/3 の進化は何を改善しているか？
21. NAT は何をするか？

D.4 データベース

22. 主キーと一意制約の違いは？
23. インデックスを作ると何が遅くなるか？
24. EXPLAIN で何を確認するか？
25. ACID の各要素が意味するものは？
26. トランザクション分離レベルの違いは？(Read Committed / Repeatable Read / Serializable)
27. MVCC の利点は？
28. N+1 クエリ問題とは？

D.5 並行性・分散

29. レースコンディションとは？ 回避方法は？
30. デッドロックの回避方法を 3 つ挙げよ。
31. CAP 定理の意味と、実システムでの選択は？
32. 冪等性とは？ なぜ分散で重要か？
33. スレッドとコルーチンの違いは？
34. Mutex とセマフォの違いは？

D.6 セキュリティ

35. 認証と認可の違いは？
36. SQL インジェクションの原理と対策は？
37. CSRF と XSS の違いと対策は？
38. なぜパスワードを平文で保存してはいけないか？
39. HTTPS は何をどう守っているか？
40. 最小権限の原則とは？

D.7 コンピュータアーキテクチャ

41. レジスタ・キャッシュ・メモリ・ストレージの速度差は？
42. キャッシュヒット率を上げる工夫は？
43. パイプラインと分岐予測の関係は？
44. SIMD とは？ どのような場面で効くか？
45. CPU アーキテクチャ(x86-64、ARM64、RISC-V)の違いは？

D.8 思考力(システム設計)

46. URL 短縮サービスを設計せよ(データ量、QPS、DB スキーマ)
47. Twitter のタイムラインを設計せよ(Pull モデル vs Push モデル)
48. 1 億件の中から上位 100 件を取る方法は？
49. スパムメール分類システムを設計せよ
50. 画像アップロードサービスの耐障害性を高めるには？

附録E：よくある質問(FAQ)

E.1 「プログラミングができれば CS は要らない？」

A：いいえ。 コードは書けても、遅いコードを速くする、大規模化に耐える設計をする、障害を切り分ける、セキュリティを担保する、といった判断には CS 知識が必須です。LLM 時代では、コード生成はできても「判断の正しさ」を支える土台として CS の価値はむしろ上がっています。

E.2 「数学が苦手でも大丈夫？」

A：ある程度は大丈夫、ただし最低限は必要。 必要な数学は、

• 離散数学：集合、論理、グラフ、再帰
• 確率：ベイズの定理、期待値
• 線形代数：行列演算(ML や 3D 処理をやるなら必須)
• 対数と指数：Big-O の感覚

程度です。微分積分は(ML・物理シミュレーション以外では)あまり使いません。

E.3 「最初に学ぶ言語は何がいい？」

A：用途による。

• CS 基礎を学びたい：Python(構文がシンプル、速度問題が出るまで気にならない)
• Web 開発：JavaScript/TypeScript
• システム寄り：C、C++、Rust、Go
• 統計・データ分析：Python、R
• 組み込み：C、Rust
• モバイル：Swift(iOS)、Kotlin(Android)

2 つ目以降は、異なるパラダイム(Haskell の純関数、Rust の所有権)を選ぶと視野が広がります。

E.4 「情報系大学に行かなくても CS は学べる？」

A：はい、完全に可能。 MIT、CMU、Stanford、Harvard の講義が無料で公開されており、独学でも体系的に学べます。ただし：

• 疑問点を質問できる相手 を作る(コミュニティ、Discord、メンター)
• 手を動かす機会 を意識的に作る(Kaggle、競技プロ、個人開発)
• 他人のコードを読む機会 を作る(OSS コントリビュート)

E.5 「どのくらいで一通り学べる？」

A：覚悟しておくべき時間感覚：

• Lv.1 基礎：3-6ヶ月 / 週 10-20 時間
• Lv.2 中級：6ヶ月-1年
• Lv.3 上級：1-3年(実務経験とセット)
• 専門家レベル：一生学び続ける

大学 4 年間は Lv.2-3 に相当します。

E.6 「AI 時代、CS を学ぶ価値は？」

A：むしろ上がっています。 LLM はコードを書けますが、

• なぜそのコードが正しいか
• なぜそのアーキテクチャが適切か
• どこで性能がボトルネックになるか
• なぜこのセキュリティ対策が必要か

という判断をするには CS 基礎が不可欠です。LLM を「使いこなす」側にいるには、CS の土台が最強の武器になります。

E.7 「日本語と英語、どちらで学ぶ？」

A：最初は日本語、徐々に英語。 日本語教材は入門に優れていますが、最新情報(Linux カーネル、論文、RFC)は英語が圧倒的に多いです。Lv.2 以降は英語のドキュメントに慣れていくのが効率的です。

E.8 「就職・転職に直結する分野は？」

A：時代により変動しますが、2026 年時点では：

• クラウドインフラ(AWS、GCP、Azure、Kubernetes)：需要高
• データエンジニアリング・SRE：常時不足
• ML システム / MLOps：急成長
• セキュリティ(アプリ・インフラ両方)：慢性的不足
• Web/モバイル開発：飽和気味だが需要あり
• 低レイヤ(カーネル、コンパイラ、DB)：数は少ないが高給

附録F：2025-2026 年の CS トレンド

F.1 AI / LLM 時代の CS

• コード生成 AI(Copilot、Cursor、Claude Code) の実務統合が進み、CS 技術者の仕事の重心が「書く」から「レビュー・設計・評価」にシフト
• RAG(Retrieval-Augmented Generation)：外部文書を検索してから回答を組み立てる方式で、ベクトル DB(Pinecone、Milvus、pgvector)の重要性が急上昇
• Agentic AI：AI がツール呼び出しや複数ステップの実行まで担う形で、自律的タスク実行への関心が高まっている
• オンデバイス LLM：スマホ・PC で Gemini Nano、Apple Intelligence、Phi-3 などが動作

F.2 言語とランタイム

• Rust 2024 Edition：公式 Book でも $edition = "2024"$ 前提が明示され、システムプログラミング学習の有力選択肢
• Rust for Linux：Linux カーネルで Rust 利用が進み、メモリ安全性を重視する低レイヤ開発の象徴的事例
• WebAssembly(Wasm)：Wasm 3.0 と周辺仕様の整備が進み、ブラウザ外でも軽量実行形式として存在感が増している
• Python 3.13：free-threaded build が実験的に提供され、GIL なし実行の検証が続いている
• TypeScript：JavaScript を事実上置換
• Go：クラウドネイティブの標準
• Mojo：Python 互換の AI 向け高速言語(Chris Lattner)

F.3 クラウドとコンテナ

• Kubernetes：成熟、操作性ツール(ArgoCD、Backstage)が発達
• WASI(WebAssembly System Interface)と Component Model：Wasm をブラウザ外で動かすための実行基盤・部品接続の仕組みとして整備が進み、軽量な配布・実行モデルとして注目
• Serverless 2.0：MicroVM(Firecracker)、Edge Workers の普及
• マルチクラウド：単一ベンダーロックイン回避の流れ

F.4 ハードウェアとパフォーマンス

• Apple Silicon M4/M5：デスクトップ ARM の本格化
• NVIDIA Blackwell / Grace Hopper：AI 推論・学習に特化
• CXL 3.x(Compute Express Link)：高速接続を通じてメモリやアクセラレータを柔軟に共有する方向性が強まっている
• 量子コンピュータ：エラー訂正に大きな進展、実用化は先

F.5 セキュリティ

• 耐量子暗号：NIST は 2024 年に最初の 3 標準を公開し、2025 年も追加候補評価を継続。今は「実装と移行計画を始める時期」
• パスキー(FIDO2)：パスワード置換の普及
• Confidential Computing：CPU の保護領域やメモリ暗号化を使って、実行中のデータも守る考え方。TDX、SEV-SNP、CCA が主要クラウドで GA
• Supply Chain Security：SBOM(Software Bill of Materials: ソフトウェア部品表)や Sigstore(成果物署名と検証の仕組み)の普及

F.6 データ基盤

• Lakehouse アーキテクチャ(Delta Lake、Iceberg、Hudi)
• Polars：Pandas より高速なデータフレーム(Rust 製)
• DuckDB：組み込み SQL 分析、爆発的普及
• Vector DB：RAG 基盤として爆発的需要

附録G：実践トラブルシューティング入門

G.1 層を意識する

問題は必ずどこかの層で起きています。

アプリ層    — ロジックバグ、設定ミス
ライブラリ層 — バージョン違い、互換性
ランタイム層 — GC、メモリ
OS 層      — プロセス、ファイル、権限
ネットワーク — 遅延、パケロス、DNS
ハードウェア — ディスク、RAM、CPU

症状に対して「最も近い層」から順に切り分けます。

G.2 症状別の典型的な疑い

G.3 5 Why 分析

「なぜ？」を 5 回繰り返す。

例：「API が遅い」

1. なぜ遅い？ → DB クエリが遅い
2. なぜ？ → インデックスが効いていない
3. なぜ？ → WHERE 句の列が索引化されていない
4. なぜ？ → 設計時に考慮漏れ
5. なぜ？ → レビューで見落とした

→ 真因：レビュー基準に「検索列のインデックス確認」を追加。

G.4 再現性の大切さ

「バグが直った」と「症状が出なくなった」は違います。

• 再現手順を明文化する
• 最小再現コード(MVCE: Minimal, Verifiable, Complete Example)を作る
• 修正後、再度再現手順を走らせる

これがないと、同じ問題が別の場所で再発します。

G.5 ログ・メトリクス・トレース

観測性(Observability)の 3 本柱：

• ログ(Logs)：何が起きたか(文字列イベント)
• メトリクス(Metrics)：どれくらい起きたか(時系列数値)
• トレース(Traces)：1 リクエストの全経路(分散追跡)

2026 年の実務では、これらを統合して扱うための共通仕様である OpenTelemetry が広く使われています。

附録H：理論的補完 — 計算理論の基礎

H.1 計算可能性

• チューリングマシン：無限テープとヘッドで計算する抽象モデル
• チャーチ＝チューリングのテーゼ：「計算可能」= チューリングマシンで計算可能
• 停止問題：「任意のプログラムが停止するか判定する」アルゴリズムは存在しない(決定不能)

これは「どんなに高性能なコンピュータがあっても、原理的に解けない問題がある」という強い主張です。

H.2 計算複雑性

• P クラス：多項式時間で解ける問題
• NP クラス：多項式時間で検証できる問題
• P = NP 問題：P = NP か？(ミレニアム懸賞問題、未解決)
• NP 完全：NP の中で最も難しいクラス(SAT、巡回セールスマン等)
• NP 困難：NP 完全と同等以上

実用上は「これは NP 完全らしいから多項式解は無理、近似アルゴリズムで妥協」という判断が重要です。

H.3 ラムダ計算と関数型

ラムダ計算(λ計算、Church 1930年代)はチューリングマシンと同等の計算力を持つが、関数の抽象・適用のみから成る：

• 変数：x
• 抽象：λx.e(関数)
• 適用：(e1 e2)

すべての計算がこの 3 つで表現できることは驚くべき事実。Lisp、Haskell、ML、そして関数型プログラミング全般の理論的基盤。

H.4 型理論

• 単純型付き λ 計算
• 多相型(System F)
• 依存型：値に依存する型。Agda、Coq、Idris、Lean が採用
• 線形型：一度しか使えない変数。Rust の所有権の基盤の一部

H.5 オートマトンと言語

• 有限オートマトン：正規言語を認識(grep、lex)
• プッシュダウンオートマトン：文脈自由言語(構文解析)
• チューリングマシン：決定可能言語

コンパイラや正規表現が「なぜ動くか」の理論的基盤。

まとめ

付録は、本文の理解を支える補助資料をまとめた場所です。必要なときに個別に引きながら、学習順の整理、実例確認、背景知識の補完に役立ててください。