計算アルゴリズム論第5回

XENO @xenophobia__

今日ってこっちでいいの？ #計算アルゴリズム論

XENO @xenophobia__

Shortest Path Queries #計算アルゴリズム論

ネクタイ @carbon_twelve

枝長が1の巨大なグラフの任意の2点間の最短距離を求める #計算アルゴリズム論

ネクタイ @carbon_twelve

前処理したデータを用いる #計算アルゴリズム論

ネクタイ @carbon_twelve

またTOP500 #計算アルゴリズム論

XENO @xenophobia__

Minor #計算アルゴリズム論

ネクタイ @carbon_twelve

当然のごとくスーパーコンピュータ #計算アルゴリズム論

XENO @xenophobia__

懐かしい話だ #計算アルゴリズム論

ネクタイ @carbon_twelve

GRAPH 500 #計算アルゴリズム論

ネクタイ @carbon_twelve

幅優先探索を超巨大なグラフ上で行うようなことを競う #計算アルゴリズム論

ネクタイ @carbon_twelve

graphのminor #計算アルゴリズム論

ネクタイ @carbon_twelve

枝のdeletionとcontractionの操作 #計算アルゴリズム論

XENO @xenophobia__

ぐちゅ #計算アルゴリズム論

ネクタイ @carbon_twelve

平面的グラフの必要十分条件 #計算アルゴリズム論

XENO @xenophobia__

Graph Minor Theorem：minorに関して閉じたgraphのclassは、有限個のforbidden minorにとって特徴づけられる #計算アルゴリズム論

ネクタイ @carbon_twelve

minor operationについて #計算アルゴリズム論

ネクタイ @carbon_twelve

関数f(x_1, x_2, x_3) : (bool, bool, bool) -> boolを表す完全二分木 #計算アルゴリズム論

ネクタイ @carbon_twelve

f(x_1, x_2, x_3) = x_1x_2(not x_3) + x_1(not x_2)x_3 + (not x_1)x_2x_3 #計算アルゴリズム論

ネクタイ @carbon_twelve

arityがnである論理関数は2^2^n個ある #計算アルゴリズム論

ネクタイ @carbon_twelve

シャノンの定理：ほとんどの関数の（連言あるいは選言）標準形は指数爆発する #計算アルゴリズム論

ネクタイ @carbon_twelve

BDDへ変換 #計算アルゴリズム論

ネクタイ @carbon_twelve

ものすごく小さくなった #計算アルゴリズム論

ネクタイ @carbon_twelve

BDD(Binary Decision Diagram) #計算アルゴリズム論

XENO @xenophobia__

BDD：なるべく同じ構造を共有するように変換 #計算アルゴリズム論

ネクタイ @carbon_twelve

Google scholar #計算アルゴリズム論