計算理論とアルゴリズム

1チューリング完全性

なぜ JavaScript と Python と Lisp が「同じこと」を計算できるのか？ 答えは「チューリング完全」だから。

チューリングマシンとは

1936年、アラン・チューリングが論文『計算可能数について』で提示した抽象機械。無限のテープと読み書きヘッドと状態だけで、計算可能なすべての関数を表現できる。

「チューリング完全」の意味

ある言語/システムが チューリングマシンと同じ計算能力を持つとき、それは「チューリング完全」と呼ばれる。すなわち、原理的に 計算可能なものは何でも計算できる。

つまり「言語選び」は 何ができるかではなく どう書きやすいか・どう速いか・誰が読めるかの選択である。

2停止性問題（Halting Problem）

「あるプログラムが永遠にループするか、いつか止まるか」を判定するプログラムは 原理的に作れない。これは数学的に証明されている。

なぜ作れないのか（背理法）

もし「Halt(P, x)」という、プログラム P と入力 x が停止するなら true を返す関数があったとする。次の意地悪なプログラムを考える:

function Naughty(p) {
  if (Halt(p, p)) {
    while(true) {} // 永遠ループ
  } else {
    return; // 即座に停止
  }
}

Naughty(Naughty); // ← これは停止する？しない？

Naughty(Naughty) が 停止すると仮定 → Halt が true → 永遠ループ → 停止しない。矛盾。
Naughty(Naughty) が 停止しないと仮定 → Halt が false → 即座に停止。矛盾。

よって Halt は存在しない。Q.E.D.（証明終了）

実用上の意味

• 完璧な静的解析ツールは作れない（コンパイラが警告を取りこぼすのは、原理上正しい）
• 完璧なウイルス検出ツールは作れない（任意のコードの挙動を予測する問題と等価）
• 完璧な型システムでも、実行を完全予測はできない

3Big-O 記法 — 計算量の表し方

同じ問題でも、アルゴリズムによって速度が 100万倍違う。Big-O はその違いを表す共通語。

定義

意訳: 入力サイズ n が大きくなったとき、最終的に g(n) の定数倍以下に収まる。定数とサブ項は無視する。

主要な複雑度（速い順）

実例: 配列に値が含まれるか調べる

for (let x of arr) {
  if (x === target) return true;
}
return false;

let lo=0, hi=arr.length-1;
while(lo<=hi) {
  const mid=(lo+hi)>>1;
  if(arr[mid]===target) return true;
  if(arr[mid]
n=10⁹でも30回程度
    

4複雑性クラス — P vs NP問題

100万ドルの懸賞金がかかった、計算機科学最大の未解決問題。

主要クラス

NP完全問題の例

• 巡回セールスマン: 全都市を最短で回る
• SAT問題: 論理式を真にする変数割当があるか
• 部分集合和: 合計が指定値になる部分集合があるか
• グラフ彩色: 隣接ノードが違う色になる最少色数
• ナップサック: 重量制限内で価値最大化

これらは現実世界（物流、暗号、設計、スケジュール）に大量に存在。完全解は無理なので近似アルゴリズム・ヒューリスティック・SAT solverが活躍する。

5主要アルゴリズム30選

名前を聞いたら反応できる必修アルゴリズム。Knuth『TAOCP』の入口。

ソート

• バブルソート O(n²) — 教育用、実用しない
• 挿入ソート O(n²) — 小データやほぼソート済みで速い
• マージソート O(n log n) — 安定ソート、外部ソートの定番
• クイックソート 平均 O(n log n) / 最悪 O(n²) — 実用最速、JS/Python標準は変種
• ヒープソート O(n log n) — 場所効率、優先度キューの基礎
• 基数ソート O(nk) — 整数・文字列で線形
• Timsort O(n log n) — Python・Java標準。実データに強い

探索

• 線形探索 O(n)
• 二分探索 O(log n) — 要ソート
• ハッシュテーブル 平均 O(1) — 万能
• 二分探索木 平均 O(log n)
• B木 / B+木 O(log n) — DBインデックスの心臓

グラフ

• 幅優先探索 (BFS) O(V+E) — 最短経路（重みなし）
• 深さ優先探索 (DFS) O(V+E) — トポロジカルソート、強連結成分
• ダイクストラ法 O(E log V) — 最短経路（正の重み）
• ベルマン・フォード O(VE) — 負の重みOK
• A*探索 — ヒューリスティック付き、ゲームAIの定番
• Union-Find (素集合) ほぼ O(1) — 連結判定

動的計画法 (DP)

• フィボナッチ DP O(n) — 入門
• 編集距離 (Levenshtein) O(nm) — スペルチェック・DNA比較
• 最長共通部分列 (LCS) O(nm) — diff の心臓
• ナップサック DP O(nW) — 最適化問題の定番

文字列

• KMP 法 O(n+m) — 文字列マッチング
• Rabin-Karp ハッシュ — 平均 O(n+m)
• Aho-Corasick — 複数パターン同時マッチ
• Suffix Array / Tree — 全文検索エンジンの基盤

暗号・数学

• ユークリッドの互除法 O(log n) — 最大公約数
• エラトステネスの篩 O(n log log n) — 素数列挙
• 高速指数演算 O(log n) — RSAの基礎
• FFT (高速フーリエ変換) O(n log n) — 信号処理・畳み込み

6言語別パフォーマンス感覚

同じことをやらせたとき、言語によって 100倍以上差が出る。Carmackの世界観。

素朴ベンチマーク（C基準）

※あくまで素朴な目安。実際は実装・最適化・問題内容で大きく変動。Pythonでも NumPy/PyTorch 経由なら C 速度。重要なのは 「ホットスポット」を見つけて適切な言語/ライブラリを使うこと。

選び方の指針

7設計パターンの基本

GoF (Gang of Four) パターン入門。再発見し続けてきた「形」の名前。

生成パターン

• Singleton — クラスのインスタンスを1つだけ（多用は危険）
• Factory — オブジェクト生成を別関数に切り出す
• Builder — 複雑なオブジェクトを段階的に組み立てる

構造パターン

• Adapter — 互換性のないインターフェースをつなぐ
• Decorator — オブジェクトに機能を動的に追加
• Facade — 複雑な内部を簡単な窓口で隠す
• Proxy — 別オブジェクトの代理を立てる（キャッシュ、認証）

振る舞いパターン

• Observer — 変化を監視して通知（イベント、Pub/Sub）
• Strategy — アルゴリズムを差し替え可能に
• Iterator — コレクションの走査を抽象化
• Command — 操作をオブジェクト化（Undo/Redo）
• State — 状態によって振る舞いを変える

関数型パターン

• map / filter / reduce — 命令型ループの上位互換
• Functor — map できるもの
• Monad — チェイン可能な計算（Promise、Optional）
• Memoization — 関数の結果をキャッシュ
• Currying — 引数を1つずつ受け取る形に変換