アルゴリズム思考術 問題解決の最強ツール
早川書房
著者：ブライアン・クリスチャン
著者：トム・グリフィス
訳者：田沢恭子
目次
はじめに 人の暮らしのアルゴリズム
1 最適停止「見る」のをやめるタイミング
秘書問題／三七パーセントはどこから？／恋人にジャンプ／よいものを見逃さない──完全情報／売却のタイミング／駐車のタイミング／やめるタイミング／人生は停止問題に満ちている
2 探索と活用 最も新しいものと最もすばらしいもの
探索と活用／残り時間を見極める／勝てばキープ／ギッティンズ指数／後悔と楽観／オンラインのバンディット／臨床試験を試験する／世界は変わる／探索と・・・・・／・・・・・活用
3 ソート 秩序を生み出す
ソートの悦び／ソートの苦しみ／ビッグＯ──最悪の事態の尺度／二乗時間──バブルソートと挿入ソート／二乗時間の壁を破る──分けて征服／比較を超えて──対数時間を出し抜く／ソートは検索の事前対策／ソートとスポーツ／あえて非効率に──ノイズと頑健性／戦いの末に──力関係の序列／戦いではなくレースを
4 キャッシュ さっさと忘れよう
メモリー 階層／追い出しと千里眼／図書館を裏返す／近所のクラウド／家庭内のキャッシュ／整理と山積み／忘却曲線／経験の暴虐
5 スケジューリング 最初のものを最初に
時間の使い方が学問となる／納期を守る／仕事を片づける／問題を選ぶ／優先度逆転と先行制約／行く手を阻むもの／すべてを捨てる──割り込みと不確実性／割り込みはタダではない──コンテキストスイッチ／スラッシング／割り込み軽減
6 ベイズの法則 未来を予想する
ベイズ牧師と後ろ向き推論／ラプラスの法則／ベイズの法則と事前信念／コペルニクス原理／ベイズとコペルニクスの邂逅／現実世界の事前確率と・・・・・／・・・・・その予想ルール／スモールデータと直感／予想が予想者について明かすこと／複製技術時代の事前確率
7 オーバーフィッティング 過ぎたるは及ばざるがごとし
複雑性に対する申し立て／データの偶像崇拝／オーバーフィッティングはいたるところに／オーバーフィッティングを見つけ出す──クロス確認／オーバーフィッティングと闘うには──複雑さにペナルティーを与える／ヒューリスティックの利点／過去の重み／思考を抑えるべきとき
8 緩和法 大目に見よう
最適化の難しさ／困難さを定義する／ただ緩和せよ／数えきれないほどたくさんのグレーの色調──連続緩和／ペナルティーを受け入れる──ラグランジュ緩和／緩和法の習得
9 ランダム性 偶然に任せるべきとき
サンプリング／乱択アルゴリズム／サンプリング礼讃／エラーのトレードオフ／山、谷、わな／極大値を脱する／焼きなまし法／ランダム性、進化、創造性
10 ネットワーキング どうつながるか
パケット交換／確認応答／指数バックオフ──寛容のアルゴリズム／流れ制御と渋滞回避／あいづち──言語における流れ制御／バッファーブロート──遅延が問題だ／遅れるよりはやらないほうがまし
11 ゲーム理論 他者の心
再帰／均衡の達成／支配戦略、よかれ悪しかれ／ 共有地の悲劇／メカニズムデザイン──ゲームのやり方を変える／進化によるメカニズムデザイン／情報カスケード──バブルの悲劇的な合理性／汝自身の ために計算 せよ
結論 計算の負担を軽くする
謝辞
訳者あとがき
原注
参考文献