学生版 社会人版
JA EN
ホーム › 計算アルゴリズム

◇ FIELD

計算アルゴリズム

計算量という物差しから、探索・動的計画法・行列計算・並列化まで。AIの下で実際に動いている計算の作法。

0章 19基礎 4論文解説 0動かす

この巻は ①教科書 → ②基礎 → ③論文解説 → ④ラボ の順に進むと、前提を飛ばさずに読めます。

② 基礎

前提知識を置かずに、その分野の考え方を組み立てる記事。ジャンル順に並べています。

計算量と評価

オーダー記法・時間と空間のトレードオフ・実測との乖離

  1. 計算量を1から理解する — オーダー記法は何を測っているのか 無料
  2. 計算量と実測が食い違うとき — キャッシュ・分岐・メモリ帯域 ★ 会員
  3. 乱択アルゴリズム — サイコロを振ると速くなる不思議 ★ 会員
  4. NP完全を1から — 「解けない」ではなく「検証は速い」 無料
  5. 近似アルゴリズム — 厳密を諦めて保証を取る ★ 会員

データ構造

配列・木・ハッシュ・ヒープ。どれを選ぶと何が速くなるのか

  1. データ構造の選び方 — 配列・ハッシュ・木・ヒープ 無料
  2. キャッシュに優しいコード — 同じO(n)で10倍差がつく理由 ★ 会員
  3. B木とLSM木 — データベースの心臓 ★ 会員

探索と最適化

全探索・貪欲法・動的計画法・分枝限定・近似

  1. 動的計画法を1から解説 — 部分問題を覚えておくということ ★ 会員
  2. 線形計画を1から — 最適化の王道 ★ 会員
  3. 焼きなましと遺伝的アルゴリズム — 厳密に解けない時の実務 ★ 会員

数値計算

行列積・分解・FFT・反復法。AIの計算はほぼここに帰着する

  1. 行列積のコスト — AIの計算はほぼここに帰着する ★ 会員
  2. 数値の落とし穴 — 桁落ち・丸め・logsumexp ★ 会員
  3. 自動微分の仕組み — PyTorchの魔法を1から 無料
  4. 連立方程式の解き方 — 直接法と反復法 ★ 会員
  5. 【実装】自動微分を自作する — 100行のミニPyTorch ★ 会員

並列・分散

並列化の限界・GPUの実行モデル・分散学習の通信

  1. GPUはなぜ速いのか — 実行モデルと並列化の限界 ★ 会員
  2. 分散学習を1から — データ並列・モデル並列・通信がボトルネックになるとき ★ 会員
  3. 並行処理を1から — ロック・アトミック・メモリモデル ★ 会員

③ 論文解説

元の論文を読んで書いた解説。各記事に論文ページとPDFへのリンクを付けています。

  1. 確率的データ構造 — 数えずに数える ★ 会員 "doi:10.1145/362686.362692
  2. FFTを1から理解する — なぜ畳み込みが掛け算になるのか ★ 会員 "doi:10.1090/S0025-5718-1965-0178586-1
  3. グラフアルゴリズムを1から — 最短経路とその応用 ★ 会員 arXiv:1603.09320
  4. ハッシュと近傍探索 — ベクトル検索の下地 ★ 会員 arXiv:1603.09320