アルゴリズム

アルゴリズム・サイエンス:出口からの超入門

アルゴリズム・サイエンスシリーズ
岩間一雄

共立出版

第1章 ウォームアップ,その1

  • 1.1 人事部長の悩み
  • 1.2 増加部分列と減少部分列
  • 1.3 最長の増加部分列を求めるアルゴリズム
  • 1.4 まとめと出典

第2章 ウォームアップ,その2

  • 2.1 共通テストの順位計算
  • 2.2 平均点も計算しよう
  • 2.3 まとめと出典

第3章 情報を漏らさない

  • 3.1 情報を漏らさないで投票する
  • 3.2 情報を漏らさないで証明する
  • 3.3 電話でじゃんけんをする
  • 3.4 まとめと出典

第4章 通信量を減らそう

  • 4.1 通信複雑さ
  • 4.2 中央値の計算
  • 4.3 グラフ問題の計算
  • 4.4 まとめと出典

第5章 乱数を利用する

  • 5.1 グラフの塗り分け問題
  • 5.2 グラフの支配集合
  • 5.3 グラフの最大カット
  • 5.4 平均からのずれ
  • 5.5 まとめと出典

第6章 オンラインアルゴリズム

  • 6.1 競合比解析
  • 6.2 線形リストの探索
  • 6.3 CNN問題
  • 6.4 まとめと出典

第7章 近似アルゴリズム

  • 7.1 ビン詰問題
  • 7.2 集合被覆問題
  • 7.3 分割問題
  • 7.4 まとめと出典

第8章 厳密アルゴリズム

  • 8.1 探索空間の矮小化
  • 8.2 3SATに対する局所探索法
  • 8.3 固定パラメータ容易性
  • 8.4 まとめと出典

第9章 幾何の計算

  • 9.1 コンビニの出店
  • 9.2 博物館の監視員
  • 9.3 まとめと出典

第10章 分散アルゴリズム

  • 10.1 リーダー選挙
  • 10.2 ウサギと猟師のゲーム
  • 10.3 まとめと出典

第11章 オークション

  • 11.1 正直なオークションと競合比
  • 11.2 競合比有界なアルゴリズム
  • 11.3 まとめと出典

第12章 ウェブクラブ

  • 12.1 PageRank
  • 12.2 確率行列
  • 12.3 PageRankの計算
  • 12.4 まとめと出典

第13章 利己的ルーティング

  • 13.1 プライスのパラドックス
  • 13.2 競合比の計算
  • 13.3 線形の遅れ関数
  • 13.4 まとめと出典

第14章 あとがきに代えて

  • 14.1 弾力性のあるアルゴリズム
  • 14.2 ネットワークコーディング
  • 14.3 まとめと出典