-
xhl_kogitsune
- 1929
- 0
- 0
- 0
-
- いいね！0
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
O(n)-spaceだと、Range Mean QueryはO(1)-querytime, Range Median QueryはO(log(n))-time位, Range Mode QueryはO(sqrt(n)loglog(n))が既存 #air_STACS
2012-03-01 23:14:21
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
おーう、なるほど > RModeQのまだ読んでた。 #air_STACS
2012-03-01 23:28:41
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
n要素の配列をs=sqrt(n)くらいの区間n/s個に分割して、I番目の区間からJ番目の区間まででのmodeを前計算しておく(O((n/s)^2)-space = O(n) space). #air_STACS
2012-03-01 23:30:44
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
それと、値vのi番目の出現がQ[v][i] で引けるような配列Q (長さ合計はO(n)になる)と、元配列のx番目の要素の値がQ[B[x]]内で何番目かを示す配列B'[x](長さO(n))を用意する #air_STACS
2012-03-01 23:32:46
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
で、区間B[i,j]にB[i]がq個以上あるかは、Q[B[i]][B'[i]+q-1]<=jか否か(<=ならある)でO(1)で調べられる #air_STACS
2012-03-01 23:33:42
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
で、区間B[i,j]のうち、最初にs要素ずつのサブ区間分割したサブ区間が丸々入っている部分と、その前後に分けて、 #air_STACS
2012-03-01 23:34:35
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
中央に関しては前処理で得た連続サブ区間のmodeテーブル引いて、mode候補とその頻度を得る #air_STACS
2012-03-01 23:35:06
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
端区間は長さ高々O(s) = O(sqrt(n))なので端からmodeかどうか検査していく。連続サブ区間modeテーブル引いた奴に関しても端区間の出現回数をlinear scanして足せばO(sqrt(n))-timeでB[i,j]全体の頻度が出る #air_STACS
2012-03-01 23:36:17
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
んで、端区間の各要素B[x]ごとに、現在の候補よりも頻度が高いかをさっき書いたO(1)の方法で確かめて、YESならQ[B[x]]上のlinear scanで頻度を計算する #air_STACS
2012-03-01 23:37:39
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
linear scanだけど、1要素検査するごとに頻度候補の値が1増える。頻度はO(sqrt(n))以上は増えない(それ以上増えるとその値が中間の連続サブ区間のmodeになっているはず)ので、全体の計算時間もO(sqrt(n)) #air_STACS
2012-03-01 23:38:56
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
…というのが First Algorithm: O(sqrt(n))-time だったのだ! なんか論文読みやすいしちゃんと適切に記号定義しなかったからたぶん私の日本語は分かりにくいと思う。4つアルゴリズムが書いてあって最後のがO(sqrt(n/logn)) #air_STACS
2012-03-01 23:39:55
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
The Limits of Decidability for First-Order Logic on CPDA Graphs
2012-03-02 03:21:12
kinaba
@kinaba
#air_STACS https://t.co/kZeZQeh2 こういうラインの話で、オーダーn "unsafe" 高階文法に対応する高階オートマトンの作るグラフ構造で一階述語論理がn≧3から決定不能になるそうな。証明はPCPをエンコード。
2012-03-01 23:06:46
kinaba
@kinaba
#air_STACS PCPというのは http://t.co/8qIhWCNC この難しいゲームのことです（再掲）（3度目）。"unsafe" のここでの意味は、高階関数の引数がオーダの高い順に並んでない事。(a->a)->a->aはsafeだがa->(a->a)->aはダメ
2012-03-01 23:09:46
kinaba
@kinaba
#air_STACS この辺の高階なんちゃら（文法、スタック、パターンマッチ、ユニフィケーション、etc etc）が3とか4とか5とか中途半端なレベルから決定不能に化ける現象の名前が必要
2012-03-01 23:11:04
Kenta Oono
@delta2323_
帰宅．#air_STACS を見ている．次はこれを見るというのであっていますでしょうか？：laying Mastermind With Constant-Size Memory
2012-03-01 23:19:33
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
Playing Mastermind With Constant-Size Memory: 2色n穴のMastermindはΘ(n/log n)が証明済だが、実は過去1回分のquery-answerのみのメモリでもΘ(n/log n) (ｷﾘｯ #air_STACS
2012-03-01 23:52:40
Takuya Akiba
@iwiwi
#air_STACS 定数色の n 個穴の Mastermind． Θ(n / log n) 回の質問で正解できることが知られていたが，実は質問と答えを定数個しか記憶できないようにしても同じらしい． お，おう…
2012-03-01 23:26:26
kinaba
@kinaba
#air_STACS Mastermind の論文は前に読んだやつだ。ヒット＆ブローするのに直前の問答1回しか問答を記憶できない奇病にかかってしまった人が、自分の全ての記憶を1回の問答にビット単位で押し込めることで明日の自分に伝える、涙なしには読めない感動巨編です。
2012-03-01 23:25:50
Takayuki Kihara
@tri_iro
なんか #air_STACS というハッシュタグがちらちら見えて気になった。これ面白そう→ The Determinacy of Context-Free Games http://t.co/uQ8ZYFCY
2012-03-02 00:27:21
kinaba
@kinaba
#air_STACS arXivにあった版を読んでる。large cardinal と game の determinacy がでてきてZFCから独立という話になってる。これは @ikegami__ さんじゃない方のイケガミダイスケ君を召還したい...
2012-03-01 23:35:32