ネットワークフロー Ford-Fulkersonのアルゴリズム とか 最小カット最大フローの原則 幅優先探索をしよう こんくらい アルゴリズムの設計法 分割統治法 動的計画法 グリーディ法 分枝限定法

7.5 2連結成分アルゴリズム どの1個の頂点を除去しても残りのグラフが連結であるようなグラフグラフを2連結なグラフに分割する。 関節点を見つけるアルゴリズム 深さ優先探索をして、順番をつける。 ある頂点の子孫全てが自分の先祖への逆辺を持っていなけれ…

7.4 最小スパニング木 連結な無向グラフの全ての頂点を含む部分グラフで木であるものをスパニング木という。 行列木定理 連結な無向グラフGのスパニング木の個数はL(G)*1の任意の対角要素に関する余因子の値に等しい。 重み付きグラフの重みを最も小さくする…

グラフの表現 隣接行列 接続リスト 隣接リスト n+1頂点の根付き木とn頂点の2分木の頂点の集合は1対1に対応する。 ダイクストラのアルゴリズム 最短路木を作ってやれば、最短路を求めることができる 作り方：Uからuを取り出したときに、その親との関係を保持…

ωn = 1の原始n乗根 n乗して初めて1になる数。 n=2:-1 n=3:(-1±√(3)i)/2 n=4:±i n=5:5個 離散フーリエ変換(Discrete Fourier Transform) 入力x=(x0,x1,x2,…,xn-1) 出力y=Ax Aはn次正方行列。 単純な計算を行うとO(n^2)となる。 たたみこみ(convolution) 例：…

5.2 正規表現によるパターンマッチング KMPのアルゴリズムを良くみると、入力が戻らない（1方向）である。 ⇒決定性有限オートマトンができるんじゃない？ マッチングオートマトンという。 本質的にはKMPアルゴリズムと同じもの マッチングオートマトンは正規…

ストリングマッチング 単純に考えると、n文字の文字列からm文字を探索するにはO(nm)の時間がかかる。 →KMPアルゴリズム・BMアルゴリズム：O(n+m)で実行できる KMPアルゴリズム 2DPDA：2方向決定性オートマトン 前後に動く＆スタックがある。 定理：RAMは2DPD…

ハッシュ法 ハッシュ＝切り刻む ハッシュドビーフのハッシュ

パシステント構造 領域を分割した構造。今自分がどの領域にいるかという問題（点位置決定問題）がお手軽に解ける。 何度も同様な質問が繰り返されるときに最適っぽい。 分割格子点がn個くらいあるとすると、すべての分割格子点で縦に分割した“スラブ”を2分探…

4.1 2分探索 検索・挿入・削除がO(logn)時間で実行される。 4.2 2分探索木 右の子 検索・挿入・削除は木の高さに比例する。 最悪の場合木の高さはn-1になる。 ランダムに要素を挿入すると… データの割り当てられている点の個数をn個として、これを内点と呼び…