![Cover Image for アッカーマン関数の計算過程を表示する (その↑) / DDRの足運び最適化問題を解く](https://res.cloudinary.com/purucloud/image/upload/c_limit,w_3840/f_auto/q_auto/v1720845752/blog/cover/productCover/techfest7_cover.webp?_a=BAVFB+DW0)
アッカーマン関数の計算過程を表示する (その↑) / DDRの足運び最適化問題を解く
だいたい4分で読めます
概要
技術書典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にて公開しています。
詳細はこちらでご覧ください。
何ページかプレビューを載せていますので、ご参考ください。