) 2014年4月8日

情報システム基礎論２：第 1 回 (担当： 古賀)
2014 年 4 月 8 日
1
授業内容
データ構造とアルゴリズムの中で、探索アルゴリズムについて集中的に講義する。紹介するアルゴリズム
の中に確率的アルゴリズムを含むので、最初に確率についても講義する。
• 第 2 回: 確率：Markov の不等式と Chebyshev の不等式
• 第 3 回以降: 探索アルゴリズム
– ランダムサンプリングを用いた数値集合からの要素探索
– 1 次元データの探索アルゴリズム: Splay 木、Skip list – 多次元データの探索アルゴリズム: kd-木
– 類似検索アルゴリズム: バケット法、Locality-Sensitive Hashing, Min-Hash – 構造を持つデータ (文字列、木、グラフ) の類似度：Graph カーネル
– 分散データ探索アルゴリズム: Chord
– Web ページ検索: PageRank アルゴリズム
授業の進め方: レジュメを配布＋板書。レジュメに沿って授業を進める。レジュメは電子的にアクセス可能。
成績評価: 学期末の試験によって成績評価を実施する。また、テストが出来なかった場合の救済措置とし
てレポート課題も課す。学期末試験を受験していないものは不合格とするので注意すること。逆にレポー
ト課題を提出していなくても学期末試験の成績が良ければ合格となる．
• レポート課題: プログラミング課題
• 学期末試験: 確率論及び探索アルゴリズムの動きを問う
2
探索アルゴリズム
探索とはデータ群 D から「条件を満たすデータを探す」こと。学部のデータ構造とアルゴリズムの授業
では
• D: 数字の集合
• 探索対象: 数字 x を見つける。例：
「学生証番号をキーとして検索」
x=3
Where?
D={9,4,6,8,2,12,5,7,3}
現実の探索はもっと多岐に渡る。
1
• 数値データの検索: D の中で最も大きなデータは？
• 多次元データの検索
– 類似検索： D の中で x にもっとも似たデータは? 例：
「背格好が似ている人は？」
• 多次元ベクトルとして簡単に表現できないデータの類似探索。例: 文字列、木、グラフ
• ウェブページの検索： キーワード検索＋ランキング
• データベースの分散化： P2P ネットワークでのファイル検索
3
確率的アルゴリズム
確率的アルゴリズムとは、簡単にいうと乱数を使用するアルゴリズムのことである。
例 1: HTTP コネクションを複数の web server に負荷分散させる。
• 決定的アルゴリズム： 現在 1 番負荷の低い server にコネクションを割り当てる。各サーバの負荷状
況を把握しておく必要がある.
• 確率的アルゴリズム： ランダムに web server 選択。
Web
Server
Network
load balance
server
Web
Server
Web
Server
これを抽象化すると、m 個のボールを n 個の箱にランダムに入れるという問題になる。
• 一番多く入った箱にはいくつのボールが入るか？
• m がいくつ以上であれば空箱がなくなるか？
→ m ≥ 2n ln n であれば、1 − n1 の確率で空箱はない。つまり、平均を大きく下回る箱がない。
実装が簡単で実用上、決定的アルゴリズムと遜色ない精度を達成するのが確率的アルゴリズムの魅力。
2