オンラインアルゴリズムとストリームアルゴリズム
オンラインアルゴリズムとストリームアルゴリズム (アルゴリズム・サイエンスシリーズ―数理技法編)
共立出版
編者：杉原厚吉、室田一雄、山下雅史、渡辺治
著者：徳山豪
シリーズの序
まえがき
目次
第1章 はじめに
1.1 未来への最善の備えとオンライン問題
1.1.1 未知情報と不完全情報の処理
1.1.2 読者へのガイド
第2章 オンラインアルゴリズムの基本理論
2.1 オンライン問題の例
2.1.1 レンタルスキー問題
2.1.2 データの整理とオンライン問題
2.2 リストアクセス問題
2.2.1 アルゴリズムの比較手法とその評価
2.2.2 競合比による解析
2.2.3 No-Action,Transpose,Frequent-Countの競合比
2.2.4 Move-to-Frontの競合比の解析
2.3 ページング問題
2.3.1 ページングとキャッシング
2.3.2 ページングのアルゴリズム
2.3.3 アルゴリズムの競合比の評価
2.4 乱択アルゴリズムの設計
2.4.1 乱択アルゴリズムの設計
2.4.2 ページングにおける乱択アルゴリズ
2.4.3 乱択アルゴリズムの下界の証明
2.4.4 リストアクセス問題における乱択アルゴリズム
2.5 Yaoのミニマックス原理
2.6 歴史的背景と関連する話題
2.6.1 償却時間複雑度と競合比解析
2.6.2 Beladyのアノマリの例
第3章 いろいろなオンライン問題
3.1 ロードバランス問題
3.1.1 同一マシンモデルでのロードバランス
3.1.2 異なった性能のマシンでのロードバランス
3.2 オンライン構築問題とシュタイナー木
3.3 電子取引における送金問題
3.4 歴史的背景と関連する話題
第4章 オンライン学習モデル
4.1 学習を考慮したオンラインアルゴリズム
4.1.1 重み付き多数決戦略とその解析
4.1.2 数値を答えるモデル
4.1.3 情報理論的な見方と精度の改良
4.2 スペシャリストモデル
4.2.1 スペシャリスト多数決アルゴリズムの解析
4.3 スペシャリストモデルの適用法
4.3.1 制限の付いた混合戦略との比較
4.3.2 決定木での応用
4.4 歴史的背景と関連する話題
4.4.1 学習能力を増幅するアルゴリズムAdaBoost
第5章 確率的最適化におけるアルゴリズム
5.1 確率的最適化とは
5.2 確率歴最適化による2段階オンライン構築問題
5.2.1 シュタイナー木問題での確率的最適化
5.2.2 一般的な枠組み
5.3 確率的線形計画法を用いたアルゴリズム設計
5.3.1 楕円体法と確率的線形計画法
5.4 歴史的背景と関連する話題
第6章 ストリームアルゴリズム
6.1 ストリームアルゴリズム
6.1.1 「そろばん」でできる計算
6.1.2 「そろばん」ではできない計算
6.2 ストリーム処理における近似アルゴリズム
6.2.1 頻出データの抽出
6.3 データの種類のカウント
6.3.1 ハッシュ関数
6.3.2 IDカウントのアルゴリズム
6.3.3 頻度表の作成アルゴリズムとデータベース管理
6.3.4 多次元データの分布推定と計算幾何学
6.4 頻度モーメントの計算の難しさと通信複雑度
6.5 時間窓モデルでのストリームアルゴリズム
6.5.1 時間窓モデルでの最大値と最小値の計算
6.5.2 小さいメモリサイズで作動するアルゴリズムの設計
6.5.3 多次元データの直径の計算
6.6 歴史的背景と関連する話題
6.6.1 データマイニングにおけるAprioriアルゴリズム
6.6.2 ストリームとインターネット、そして通信複雑度
おわりに
参考文献
索引