アッカーマン関数の計算過程を表示する (その↑) / DDRの足運び最適化問題を解く

概要

技術書典7にて、「アッカーマン関数の計算過程を表示する (その↑) / DDRの足運び最適化問題を解く」という本を頒布しました。

アッカーマン関数を題材にし、巨大なデータや再帰関数との戦い方、Rustプロジェクトの進め方を扱っています。成果物として巨大な計算過程が得られるので、眺めてうっとりすることが可能です。

また、DDRというゲームを題材に、最適な足運びを導出する組み合わせ最適化問題をDPで解いています。

二部構成になっており、第一部は私esplo、第二部はmatonによる執筆です。

表紙

表紙は「寿司 虚空編」「めしにしましょう」などでお馴染み、小林銅蟲先生（Twitter:@doom_k, Pixiv Fanbox）描き下ろしです。なお、この本は「寿司 虚空編」に感銘を受けて作られました。

素敵な表紙

詳細

本書の第一部はアッカーマン関数の計算過程を題材に、Rustプロジェクトの進め方や再帰関数との戦い方、巨大なデータの扱いについて見てゆきます。
続く第二部はDance Dance Revolutionというゲームを題材に、シーケンスに対して優れた足運びを割り当てる組み合わせ最適化問題（エネルギー最小化問題）について取り組んでいます。

いずれも、単純に考えるとメモリに乗り切らなかったり、計算が終わらないような問題を如何に効率よく捌くか、というお題に取り組んでいます。

こんな人におすすめ

巨大なデータが好きな人、Rustに入門したい人、巨大数が好きな人、競技プログラマー、DDRをやっている人などにおすすめです。

目次

第I部 アッカーマン関数の計算過程を表示する(その↑)

• 第1章 はじめに
  • 1.1 本稿で得られるもの
  • 1.2 前提知識
  • 1.3 あると望ましい性質
  • 1.4 コード全文の参照先
• 第2章 アッカーマン関数とは?
  • 2.1 アッカーマン関数の概要
  • 2.2 A(4,2)の世界
  • 2.3 結局何なのか
  • 2.4 もっと知る
• 第3章 アッカーマン関数の計算
  • 3.1 アッカーマン関数をプログラムに落とし込む
  • 3.2 A(4,n)の世界を計算してみよう
  • 3.3 A(4,2)を計算したければ
  • 3.4 ここまでのまとめ
• 第4章 計算過程を表示する
  • 4.1 本稿の成果物
  • 4.2 ナイーブな実装
  • 4.3 メモ化で速くする
  • 4.4 データ構造を工夫した実装
  • 4.5 まとめ
• 第5章 次回予告
  • 5.1 必要リソースの予測
  • 5.2 ボトルネックの分析
  • 5.3 より大きな計算過程を表示するためのアイデア
• 第6章 あとがき

第II部 DDR 足運びコスト最小化問題を解く

• 第7章 はじめに
• 第8章 準備: 本稿で用いる用語
• 第9章 定式化
  • 9.1 コストの導入
  • 9.2 コスト関数の定義
  • 9.3 探索問題としての定式化
• 第10章 解法
  • 10.1 計算用配列の構築
  • 10.2 コスト最小要素の探索
  • 10.3 コスト最小足運びの抽出
• 第11章 議論
  • 11.1 無視してきた概念
  • 11.2 定式化における課題
• 第12章 おわりに

購入

Boothにて公開しています。
詳細はこちらでご覧ください。
何ページかプレビューを載せていますので、ご参考ください。

https://esplo.booth.pm/items/1575590