工学类工学特论.doc

童梦无忧网 试管婴儿论坛

本文由defang168贡献
ppt文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。
アルゴリズム工学特論
定兼 邦彦 2006年11月1日
木構造のBP表現
木を括弧列で表現
– 内部節点: (……) – 葉:() :
1 2 4 5 6 1 2 3 4 5 6 7 8 9 10 11
2
3 7 9
8 10
11
2n+o(n) bits ? ノードは( の位置で表現
(()((()())())(()())())
可能な演算
○ は定数時間
親(への移動) 長男 次の兄弟 子孫の数 子の数 i 番目の子 深さ 深さ d の祖先 lca
BP ○ ○ ○ ○ O(子の数) O(i) ○ ○ ○
DFUDS ○ ○ ○ ○ ○ ○ ○ ○ ○
3
括弧列での操作
? ? ? rankp(P,i): P[1..i] 中のパタン p の数を返す selectp(P,i): P 中の i 番目の p の位置を返す findclose(P,i): P[i] の( と対応する )の位置を返す enclose(Pi): P[i] の( を囲む括弧の位置を返す
1 2 4 5 6 3 7 9 8 10 11 enclose findclose 7 8 9 10 11
1 2 3 4 5 6
P(()((()())())(()())())
rank()(P,10) = 3
4
木の巡回
? ? ? ? ?
2 4 5 6
P: 木の括弧列表現 ノードは( の位置で表されているとする root() = 1 parent(v) = enclose(P,v) firstchild(v) = v + 1 sibling(v) = findclose(P,v) + 1
1 3 7 9 8 10
5
enclose 11
findclose 7 8 9 10 11
1 2 3 4 5 6
(()((()())())(()())())
ノードの深さ
P’[i] = rank((P,i) ? rank)(P,i) とすると depth(v) = P’[v] ? P’はPから計算できる
1 2 4 5 6 3 7 9 8 10 11 1 2 3 4 5 6 7 8 9 10 11
P (()((()())())(()()))) P’ 1212343432321232321210
6
子孫の数 (部分木の大きさ)
v を根とする部分木の大きさは subtreesize(v) = (findclose(P,v)?v+1)/2
1 2 4 5 6 3 7 9 8 10
7
11
1 2 3 4 5 6
7
8 9 10
11
P (()((()())())(()())())
findcloseのデータ構造
括弧列を長さ B = ? log n のブロックに分割
– b(p): p のブロックの番号 – μ(p): p とマッチする括弧の位置 – 括弧 p が far ? b(p) ≠ b(μ(p))
far 開括弧 p が opening pioneer ? p の直前の far 開括弧 q に対し b(μ(p)) ≠ b(μ(q)) ? opening pioneerと対応する括弧の位置を0,1ベクト ルで表現
r ( q p ( (
μ(p) μ(q) μ(r)
) ) )
8
補題: ブロックの数を β とすると，opening pioneerの数は 2β?3 以下． 証明: 各ブロックをノード，(bp), b(μ(p)) を枝 とするグラフは外平面グラフ opening/closing pioneerは再びBPになる
β = n/B = 2n/log n ? BPの長さは O(n/log n)
再帰の深さは 2 で十分
9
findcloseのアルゴリズム
? ? ? ? ?
μ(p) = findclose(P,p) を求めるとき p が far でないなら μ(p) はテーブルから求まる
p の直前の pioneer p* を求める pioneerの括弧列を用いてμ(p*) を求める p がpioneerでないなら， b(μ(p)) = b(μ(p*)) pとp*の深さの差から，μ(p) の位置が決まる
p* p ( (
μ(p) μ(p*)
) )
10
enclose
π(p) = enclose(P,p) とする ? b(π(p)) = b(p) ならば π(p) は表引きで求まる ? b(π(p)) ≠ b(p) ならばそれらの括弧の位置を記憶
– 対応する括弧の位置も記憶 – 括弧が複数ある場合は一番外側だけ記憶
括弧を抜き出して再帰
(
(
(()))(
)
)
)
11
lcaの計算
lca = lowest common ancestor ? u = lca(v,w): v と w の共通の祖先 で最も根から遠いもの ? 定数時間で計算可
w
u
v
12
P’[i] = rank((P,i) ? rank)(P,i) とすると u = parent(RMQP’(v,w)+1) m = RMQP’(v,w): P’[v..w] 中の最小値の添字 (RMQ = Range Minimum Query) u
1 2 3 4 7
w
9
8 10
11
1 2 3 4 5 6
7
8 9 10
11
v
P (()((()())())(()())()) P’ 1212343432321232321210
u
v
mw
5 6
13
Range Minimum Query
問題 (RMQ) ? 入力: 配列 A[1,n] (前処理可), 区間 [i,j] ? [1,n] ? 出力: 部分配列 A[i,j] 中の最小値の添字 補題: 長さ n の配列に対するデータ構造のサイズ を s(n), 問い合わせ時間を t(n) とするとき，以下 の式を満たすデータ構造は O(n) 時間で作成可.
8n ? t (n) = O(1) + t ? ? lg n ? ? ? ? ? 8n ? s ( n) = 4n + s? ? lg n ? + o(n) ? ? ?
14
Cartesian Tree
配列 A[1,n] に対するCartesian treeとは
– 根ノード: A[1,n] の最小値 A[i] を格納 – 左部分木: A[1,i?1] に対するCartesian tree – 右部分木: A[i+1,n] に対するCartesian tree
A 143504537
0 1 3 4 5 4 5 7
15
3
Cartesian TreeとRMQの関係
RMQ(i,j) = lca(i,j)
A 143504537
0 1 3 4 5 4 5 7
16
3
Cartesian Treeの性質
補題: A[1,n?1] に対する木に A[n] を追加したとき， A[n] は根から最右葉までのパス上に存在する． 証明: A[n] は配列中で一番右の要素なので 左の子にはならない． 0
1 2 0 4 6 3 4 5 4 4 5 3 3 54 5 6
17
1 2
Cartesian Treeの作成
A[1,n?1] に対する木に A[n] を追加するとき ? A[n?1] から根までの要素と順に比較していく ? A[n] より小さい要素 x が現れたら，そこに挿入 ? x の右の子は A[n] の左の子にする
1 1 3 3 4 4 5
18
4 5
計算量
補題: Cartesian treeは O(n) 時間で構成可 証明: A[i] を挿入するときの比較回数を ci とすると， n 全体の計算量は O(c )
∑
i =1
i
Cartesian treeの最右パス上の各ノードは， A[i] の 挿入後にその左の子になるため，一度しか A[i] と 比較されない．よって，比較回数の和は n 以下． つまり計算量は O(n)．
19
Cartesian Treeの括弧列表現
A 143504537
0 1 3 4 3
4
5
5
7
((()((())()(())))()((()(())))()(())))
1 4 3 5 0 4 5 3 7
20
RMQのアルゴリズム
配列 A[1,n] をCartesian treeに変換 ? Cartesian treeを括弧列 P, 深さ列 P’ に変換 A[i,j] の最小値の位置 m を求めるとき ? i’ = select()(P,i), j’ = select()(P,j) ? P’[i’, j’] の最小値の位置を m’ とすると， m = rank()(P,m’)+1
21
P’でのRMQ
P’ を長さ w = (lg n)/2 のブロックに分割 ? 各ブロック中の最小値を配列 B で表す ? P’[i’, j’] の最小値は以下の３つのどれか
– i’ を含むブロック中の最小値 – j’ を含むブロック中の最小値 – これらのブロックの間での最小値 P (()((()())())(()())()) P’ 1212343432321232321210
B 1 3 2 1 1 0
22
計算量
P の長さ: 4n ? B の長さ: 4n/w = 8n/lg n ? 計算量 ? 8n ?
t (n) = O(1) + t ? ? lg n ? ? ? ? ? 8n ? s ( n) = 4n + s? ? lg n ? + o(n) ? ? ?
定理: RMQは 4n+o(n) ビットのデータ構造を 用いて定数時間で計算できる
23
Sparse Tableアルゴリズム
配列 B[1,m] の各区間[i,i+2k?1]について 最小値を求めM[i,k] に格納する.
( i = 1 ,……,m , k = 1 ,2, ??? ,lg m )
問い合わせ区間 [s,b] が与えられたとき
1. k = lg(b?s) とする 2. M[s, k] と M[b?2k+1, k] を比較し,小さいほうを解とし て出力する.
O(1) 時間，O(m lg2 m) bit 領域 ? B の長さが O(n/lg3 n) のときに用いる ?o(n) bit領域
24
定数時間selectアルゴリズム
長さ M の0,1ベクトル，N 個の要素が1
– N = O(M/lg M) – 2つの1の間の距離 ≤ (lg M)c (仮定) (仮定)
s = M/N, t = lg M/(2c lg lg M) ? 配列 A1: 1の位置を t 置きに格納
– (N lg M)/t = O(M lg lg M/lg M) bits
配列 A2: 1の間の距離を格納
– N ? c lg lg M = O(M lg lg M/lg M) bits
A2 の各値は c lg lg M bits ? t 個で (lg M)/2 bits ? テーブルを使って定数時間で和を計算可能 25
BPでのlca
深さ列 P’ を改めて作る必要なし ? 2n+o(n) ビットで計算できる (P自身)
26
更多资源
初二语文 初二英语 初二数学 初二物理 初二政治 初二历史 初二地理 初二生物

1