『問題解決力を鍛える アルゴリズムとデータ構造』学習メモ
Ch01 what's algorithm
- algorithm: 問題を解くための方法、手順
- binary searchとlinear search
- どんなケースも同じやり方で答えを導ける
- Depth-First Search(DFS)
- とりあえず突き進むを行き詰るまで繰り返す
- 探索順序を工夫すると劇的な性能差になるのが魅力。
- Breadth-First Search(BFS)
- 出発点に近いところから順に探索
- 何かを達成するための最小手順を知るために使える
- DFS, BFSとも、グラフ上の探索と考えると見通しがよくなる
matching
- 2 category間のつながりの問題
- internet広告配信、レコメンドシステム、マッチングアプリ、シフトスケジューリングなどで使える
- 2 category間のつながりの問題
章末問題
- 1.4: 九九で2桁の和が6になるものに目をつけるといいのかもしれない
- 1.6: BFS。地図上の最短経路を求める。
Ch02 計算量とオーダー記法
- 調べるべき組み合わせをマトリックスで考える→ 図2.3
- 一般的なパソコンで1秒間に処理できる計算ステップの回数: 109
- 各オーダーでの入力サイズと計算ステップ回数の関係→ 表2.2
- 指数時間: O(N!), O(2N)
- 多項式時間: Ndの定数倍で上から抑えられるもの
- 定数時間: O(1)
- 計算量: 以降は最悪計算時間量を指す
- ランダウのO記法の詳細
- オメガ、シータ
- 章末問題
Ch03 設計技法(1): 全探索
- 意義
- 線形探索
- 全ての基礎となる重要なアルゴリズム。
- 多量のデータから特定のデータを探し出す。
- 条件を満たすものの場所も求める
- 最小値を求める
- ペアの全探索
- 組み合わせの全探索
- N個の整数からなる集合の部分集合は2N通りある
- 部分集合に整数の二進法表現を用いる。
- code3.5, 表3.2 bit演算で判定する
- 1 << i: 二進法表現で右からi桁目のみが0であるような値を表す(最も右を0桁目とする)。
まとめ
- 全探索は、解きたい問題に対して、考えられるすべての可能性を調べ上げることで解決する手法
- すべての基礎となる重要なもの。
章末問題
- 3.3
- worst, second（変数の名前づけについて）
- 共にINFで初期化で〇
- 3.4
- max, minを求めればOK
- 3.5
- それぞれの値を2で何回割れるか求める。
- なんかor演算でも行けたりしないかな
- 3.6
- z = N - x - yでok
- 3.7
- bitでプラスの位置を表せば〇
- 3.3
Ch04 設計技法(2): 再帰と分割統治法
- 様々な問題に対して、簡潔かつ明快なアルゴリズムを記述できる。
- 再帰関数のテンプレート: basecaseでreturn。その他は再帰。
- basecaseに対する処理が重要。
- 引数がbasecaseに近づくようにする。
- 再帰の例
- ユークリッドの互除法
- フィボナッチ数列
- 呼び出しの流れ: 図4.2
- → メモ化, キャッシュ
- 再帰関数を用いる全探索
- 部分和問題
- N番目について場合分け: 図4.4, code4.9
- メモ化
- 部分和問題
- 分割統治法
- まとめ
- 章末問題
- 4.1 basecaseと、basecaseに近づく処理を考える。
- 4.3 三項間漸化式を特性方程式を用いて解く。等比数列を作る。
- 4.4 T(N)についての漸化式を考える。フィボナッチ数列と同様の増加。-51/2の方は0に収束する。
- 4.5
- 753それぞれの有無を判定するフラグを使う。フラグは二進法表現が〇。
- 753だけ使えるのをちゃんと読む。753いずれかを付け足していくことで列挙できる。
- counterは共有する。
- 4.6 メモ化。再帰の前で計算済みか確認。計算済みならメモをreturn。
Ch05 設計技法(3): 動的計画法
- 動的計画法
- 例題
- Frog 問題
- グラフの問題としてとらえる。
- 過程をメモの値に集約
- 部分構造最適性: 元の問題の最適性を考えるときに、小さな部分問題についても最適性が要請される
- → このような構造を利用して最適値を順に決定していく手法が、動的計画法
- Frog 問題
- 動的計画法に関連する諸概念
- ナップサック問題
- 動的計画法以外にも解法がある。
- 動的計画法の部分問題の作り方の基本的なパターン: N個の対象物{0,1,...,N-1}に関する問題に対して、最初のi個の対象物{0,1,...,i-1}に関する問題を部分問題として考える。
- 各段階においていくつかの選択肢が存在するという状況は、動的計画法を有効に適用できそうだということを示す。
- 考えたテーブル設計でうまく遷移が作れなかった場合に、添え字を付け加えることで遷移が成立するようにする作業がよくある。
- 添え字を追加する作業: 選択肢をまとめ上げる粒度を細かくすることに対応。
- 動的計画法: 考えられる場合をグループごとにまとめるイメージの手法。グループの個数とグループ間の遷移の個数が最終的な計算量。
- 選ぶときと選ばないときの遷移を式にする。
- 図5-10: テーブル更新の様子。選ばなかった場合の同じウェイトの値と比較している。
- 編集距離
- 応用: diff command, spell checker, 空間認識・画像認識・音声認識などのパターンマッチング, バイオインフォマティクス(系列アラインメント)
- テーブル定義: dp[i][j]←Sの最初のi文字分と、Tの最初のj文字分との間の編集距離
- 編集距離: 対応を作る/ 最小コスト弾性マッチング問題: マッチさせる
- 区間分割の仕方を最適化
- まとめ
- 動的計画法は多くの問題に有効
- テーブルの設計パターンは意外と少ない。
- 固有の問題に対して、大局的なパターンと、その問題に固有の事情とを分けて考えられるようになることが大事。
- 章末問題
- 全体として: 値の定義と、chmax/ chminによって、ループ間の比較は必要なくなる。
- 5.1 a,b,cについて添え字を加えると、chmax(dp[i+1][k], dp[i][j] + a[i][k])と表すことができる。
- ↑ a[i],b[i],c[i]とも添え字でまとめてしまうと1行で書くことができる。
- chmaxは選択肢の数分呼ぶ。次のdpの値を選択肢の数分だけ比較して最大にする。
- 5.2 dpには値ではなくboolを入れればOK
- 5.3 5.2と同じ
- 5.4 boolではなく個数を値として持たせる
- 5.5 毎回のa[i]について、Wを超えない範囲で足し続けてよい。
- ただし、Wに対してループしているので、1度足せばよい。
- 同じi(またはi+1)内で遷移できるパターン
- 5.6 値で最後の整数の使用回数の最小値を保持する
- 5.7 dpに文字数を入れる。i, jのとき、S[i], T[j]はカウントされていないため、これらが一致するかどうかで増えるか決まる。
- 5.8 各区間の平均値は別で求める必要あり。
- 5.9 （以降解答なし）start, endが必要だが、endは要素数で表せる。dp[要素数（終了位置）][開始位置]のテーブルを持つ。
- chmin(dp[i][j], dp[i-s][j] + dp[i][j+s])で求められそう。sは区切りで、要素数の分だけ1つずつ繰り返し試す。
Ch06 設計技法(4): 二分探索法
- 配列の二分探索
- 配列がソート済みであることが必要。
- O(logN)
- C++のstd::lower_bound()
- 値keyが属する区間を特定
- 一般化した二分探索法
- 各整数xに対してtrue/falseの2値で判定される条件Pが与えられていて、ある整数l. r(l < r)が存在して、以下が成立しているとする。
- P(l) = false
- P(r) = true
- ある整数M(l < M <= r)が存在して、x<Mなるxに対してP(x) = falseであり、x>=Mなるxに対してP(x) = trueである。
- このとき、D = r - lとして、二分探索法はMをO(logD)の計算量で求めることができるアルゴリズムといえる。
- leftは常にfalse側、rightは常にtrue側
- プログラムのデバッグでも使っている考え方
- （整数ではなく）実数上の二分探索法(二分法ともいう)も可能。求めたい精度によって終了条件を規定する。
- 各整数xに対してtrue/falseの2値で判定される条件Pが与えられていて、ある整数l. r(l < r)が存在して、以下が成立しているとする。
- さらに一般化した二分探索法
- 応用例(1): 年齢当てゲーム
- 応用例(2): std::lower_bound()の活用例
- ペア和のK以上の中での最小値
- a[i]を固定して、bについて二分探索。O(NlogN)。
- ペア和のK以上の中での最小値
- 応用例(3): 最適化問題を判定問題に
- 「～という条件を満たす最小値を求めよ」→「xが条件を満たすかどうかを判定せよ」。
- 最大値の最小化。
- 「N個すべての値をx以下にできるかどうかを判定してください。」
- 応用例(4): medianを求める
- median: 小さい順に(N-1)/2番目の値のこと
- 「N個の非負整数a[0],..,a[N-1]のうち、x未満の整数が(N-1)/2個あるかどうかを判定してください。」
- まとめ
- 二分探索法をより汎用性の高い手法として捉える。
- 特に、最適化問題を判定問題に帰着させる考え方は、実用的にも有力な手法
- 二分探索法をより汎用性の高い手法として捉える。
- 章末問題
- 6.1 まずはソートが必要。あとは、a[i]より大きいことを条件として、right, leftの範囲を絞って要素が1つになるよう、二分探索をすればOK。
- 6.2 3つ配列があるときは、真ん中を固定することで、ループを1重で済ませられる。あとはただの二分探索。
- 6.3 O(N3logN)までしかできなかった。4組のときは、2組ずつ処理することでN2のオーダーで処理できる。
- 6.4 条件の関数をまず書く。条件に渡すのは、二分探索でのmid。条件判定によって左端か右端にmidを入れる。
- 条件は、midに対して指定の処理が可能かどうかのみ。
- 最小値の最大化。ソート+二分探索。
- Mはただ与えられた値に過ぎない。
- https://hcpc-hokudai.github.io/archive/algorithm_binary_search_001.pdf
- 6.5 2重の二分探索。a[0]b[0]..a[N-1]b[N-1]の中間を条件に渡し、さらにa[0]..a[N-1]のループ中で、それぞれb[0]..b[N-1]について二分探索をする。(確認していないけどたぶんあってると思う)
- 6.6 さらに一般化した二分探索法（ある実数区間において連続な関数f(x)が与えられ、二分探索法（二分法）によって、f(x)=0を満たす実数x(l\<x\<r)のうち1つを、いくらでも高い精度で求めることができる。）の例。
- sinとかなんか計算は言語に任せてしまえばよい。関数の連続性が重要。
- すべての解ではなく、ある範囲の1つの解を求めたいときに二分探索法を使える。
- 6.7 累積和を使うように思うが、分からない。問題の内容も少し違うような。
Ch07 設計技法(5): 貪欲法
- 貪欲法とは
- 1step先のことのみを考えて、最善の選択を繰り返す方法論。
- 後先を考えず、その場での最善を選択することを繰り返す方法論。
- 1step先のことのみを考えて、最善の選択を繰り返す方法論。
- 貪欲法が最適解を導くとは限らない
- 貪欲法によって最適解が導ける問題は、その構造自体によい性質が内包されている可能性が高い。
- e.g. 最小全域木問題
- ﾏﾄﾛｲﾄﾞ性、離散凸性
- 貪欲法パターン(1): 交換しても悪化しない
- 最適化問題は、「探索範囲を予め絞れないか」の考察がきわめて有効
- f(x') >= f(x)が成立する、ある性質Pを満たすx'を、xを変形して得る。
- 最適化問題は、「探索範囲を予め絞れないか」の考察がきわめて有効
- 貪欲法パターン(2): 現在がよいほど未来もよい
- 貪欲法が成立するための単調性
- Multiple Array
- 後ろから1ステップずつ考えればよい。
- まとめ
- 貪欲法：「後先のことを考えず、次のステップのことのみを考えた場合の最善の選択を繰り返す」
- 問題の構造に関する考察のポイント
- 探索範囲を絞ることで、現実的な計算時間で全探索が可能になる
- 意思決定の順序をある基準にそって固定してよいことがわかるので、その順序に沿ったDPによって最適解が求められる
- 問題の構造をしっかり考察したうえで、その構造を活かしたアルゴリズムを設計することの面白さ
- 章末問題
- 7.1 a[0]..a[N-1]について繰り返す。その中で、b[0]..b[N-1]に対して二分探索でよさそう。
- 7.2 青の点のx座標を常に最小を選ぶことで、y座標についてのみ考えれば済むようになる。y座標のmaxとなる点rAは、rが選ばれなかった場合や、よりy座標が小さいrA'に対して常に交換できる。そのため、貪欲法を使用できる。
- 別のものを使うか、使わなかった場合に対してかならず交換できるとき、貪欲法を使用できる。
- 7.3 締め切り順にソート。あとは各締め切りを使った時間の合計と比較していけばokと思う。
Ch08 データ構造(1): 配列、連結リスト、ハッシュテーブル
- データ構造を学ぶ意義
- data structure: データの持ち方
- クエリ: データ構造に値を挿入して管理したり、データ構造から所望の値を取り出したりするような要求
- 挿入、削除、含むか判定
- どのようなデータ構造を用いるかによって、計算時間に大きな差が生じる: 表8.1
- 配列
- 連結リスト
- 〇: 挿入、削除
- × : ランダムアクセス×
- 各要素をポインタでつなげる
- ダミーノード: 番兵
- 自己参照構造体を用いる。自分自身の型へのポインタをメンバに持つ構造体のこと。
- 連結リストの挿入操作と削除操作
- 挿入の実装
- 削除の実装
- 双方向連結リスト
- 配列と連結リストの比較
- 連結リストは限られた場面で大きな力。
- 連結リストは、単体ではなく、様々なデータ構造の部品として活用されることが多い。
- 要素xの検索処理は、いずれもO(N)
- → ハッシュテーブル: 平均的にO(1)で検索
- → 平衡二分探索木: O(logN)で検索
- ハッシュテーブルは、「i番目の要素」や「次の要素」といった、各要素間の順序に関する情報を持たないデータ構造であることに注意が必要。
- ハッシュテーブル
- T[x]: データ構造中に値xが存在するかを表す値（true/false）
- バケットを汎用化したものがハッシュテーブル。
- 整数とは限らない一般的なデータ集合Sの各要素に対し、0 <= h(x) < Mを満たす整数h(x)に対応させる。
- 完全ハッシュ関数を設計し、配列Tを用意することで、「挿入」「削除」「検索」といったクエリそれぞれをO(1)で実行できる。
- O(M)のメモリ容量を必要とする
- 文字列の集合に対するハッシュ関数: ローリングハッシュ
- ハッシュの衝突対策
- 各ハッシュ値ごとに連結リストを作成する
- ハッシュテーブルの計算量
- 単純一様ハッシュの仮定
- ハッシュテーブルの各要素にアクセスする計算量は、平均的にO(1+N/M)となる。
- α = N/M: 負荷率
- α = 1/2程度とすれば、十分にO(1)の計算量を達成できる
- ハッシュテーブルの各要素にアクセスする計算量は、平均的にO(1+N/M)となる。
- 単純一様ハッシュの仮定
- C++, Pythonにおけるハッシュテーブル
- std::unordered_set, set
- set(C++)は、いずれのクエリもO(logN)で十分高速。平衡二分探索木の一種である赤黒木を用いて実現されている
- 連想配列
- まとめ
- 配列、連結リスト、ハッシュテーブルについて、「挿入」「削除」「検索」といったクエリに対するパフォーマンスを比較
- 処理したいクエリに応じて、適切なデータ構造を用いることが肝要。→ 表8.5
- 章末問題
- 8.5 ハッシュテーブルを使えばいけると思う
- 8.7 片方はハッシュテーブルを使って、もう片方でループ。K - b[i] = a[j]となるaがあるかどうかハッシュテーブルで判定する
Ch09 データ構造(2): スタックとキュー
- stack, queueの概念
- stack, queueの動作と実装
- いずれも配列を用いて簡単に実現
- queueはメモリ管理を効率よく行いながら実装することが大変 → 実践的にはstd::queueの使用が〇
- stackの動作と実装
- top(: 最後に挿入された要素の添え字の次の添え字) を用いる
- 「スタックに格納されている要素数」も表す
- top(: 最後に挿入された要素の添え字の次の添え字) を用いる
- queueの動作と実装
- 両端が開いている
- リングバッファ
- まとめ
- stack, queueは、コンピュータサイエンス全域で登場する基本的な考え方。
- 重要な応用例: グラフ探索。DFSやBFSという重要なグラフ探索技法を設計できる。
- 章末問題
- https://qiita.com/drken/items/6a95b57d2e374a3d3292
- 9.3 (をスタックに入れて、)でpopすればよさそう。
- 9.2 被演算子をpush, 演算子でpop
Ch10 データ構造(3): グラフと木
- グラフ: 対象物の関係性を数理的に表すもの
- 連結でサイクルを持たないものは木
- 木の形状を用いたデータ構造として有用なものを見る
- グラフ
- グラフの考え方
- 対象物の関係性を表す
- 対象物を〇(頂点、vertex)、対象物間の関係を線(辺、edge)で表す
- グラフの描画は一意ではない
- グラフGを、頂点の集合Vと、辺の集合Eの組として定義する
- G = (V, E)
- 各辺e ∈ E を2つの頂点vi, vj ∈ Vの組と定義して、e = (vi, vj)と表す
- 隣接(adjacent): 辺eで結ばれていること。隣接した両端は端点(end)という。
- 接続(incident): 辺eは両endに接続しているという。
- 重み付きグラフ: 各辺eに実数値または整数値をとる重みが付随したグラフ
- 多重辺: 複数本の辺が同一頂点間を結ぶ
- 自己ループ: 両endが同じとなる辺e
- 単純グラフ: 多重辺も自己ループも持たないグラフ
- 有向グラフと無向グラフ
- 有向グラフ: 一方通行の道路といったものをモデル化するのに有効
- (vi, vj)と(vj, vi)を区別する
- 有向グラフ: 一方通行の道路といったものをモデル化するのに有効
- ウォーク、サイクル、パス
- いずれも部分グラフ(subgraph)の一種であり、重要
- ウォーク(walk): sからtへと隣接する頂点をたどっていくことで到達できるとき、s-t walk（s-t路）という。
- s: 始点、t: 終点
- サイクル(閉路): 始点と終点が同じウォーク
- パス(道): 同じ頂点を2度以上通らないウォーク
- 有向グラフにおいては、始点から終点への方向に沿っている必要がある
- 長さ: 重み付きグラフでは、それらに含まれる辺の重みの総和。重みなしグラフでは辺の本数。
- 連結性
- 連結: 無向グラフGの任意の2頂点s, tに対してs-tパスが存在するとき、Gは連結であるという。
- 図10-7: 2つのグラフではなく、全体で1つの連結でないグラフが描かれている
- 連結成分: Gを構成するそれぞれの連結グラフ
- 連結とは限らないグラフに関する問題を解くときに、まず連結グラフに対する結果を求めてから、それを各連結成分に対して適用するとうまくいくことが多々ある。
- e.g. 二部グラフ判定
- グラフの考え方
- グラフを用いる定式化の例
- グラフは非常に強力な数理科学的ツール
- グラフを用いてモデル化することで、グラフに関する問題として捉えなおすことができる
- 対象物をグラフを用いて定式化する
- ソーシャルネットワーク
- small world現象
- コミュニティの検出、影響力の高い人を検出、ネットワークの情報伝播力を解析
- 交通ネットワーク
- 道路: 交差点がグラフの頂点、鉄道: 駅が頂点
- 各頂点間の長さは平均的に大きい
- 平面的。平面グラフ: どの2本の辺も交差しないように平面上に描くことができる
- ゲームの局面遷移
- グラフの探索で、必勝法がわかる
- タスクの依存関係
- タスクの依存関係をグラフとして整理→適切なタスク順序を決定、クリティカルパスを求める
- グラフの実装
- コンピュータ上でグラフを扱うためのデータの持ち方、データ構造
- 隣接リスト表現と隣接行列表現。隣接リスト表現を扱う
- ↑効率よいアルゴリズムを設計できることが多々あるため
- 隣接リスト表現と隣接行列表現。隣接リスト表現を扱う
- 隣接リスト表現
- 各頂点について、辺でつながる頂点をリストアップ
- G[v]がvの隣接頂点を表す
- 入力
- N(頂点数) M(辺数) と、各辺が渡される
- コンピュータ上でグラフを扱うためのデータの持ち方、データ構造
- 重み付きグラフの実装
- 重み付きの辺を表す構造体Edgeを用意
- G[v]がvに接続している辺の集合を表す
- 最短路問題に使う
- 木
- 無向グラフG=(V, E)が木である: Gが連結で、かつサイクルを持たない
- 根付き木(rooted tree) ←→ 根なし木(unrooted tree)
- 特定の1つの頂点を根(root)
- 頂点に接続している辺が1本のみのもの: 葉(leaf)
- 親、子、兄弟
- 部分木と、木の高さ
- 部分木のroot以外の頂点を子孫
- 根付き木上の2頂点のパスはただ1つに決まる(根なしも同様)
- 根とvを結ぶパスの長さ: vの深さ。根の深さは0
- 根付き木の各頂点の深さの最大値: 木の高さ
- 順序木と二分木
- 根付き木の構造を用いて、多彩なデータ構造を考えられる
- ヒープ、二分探索木、Union-Find
- 順序木と二分木
- 根付き木において、各頂点vの子頂点の順序を考慮するとき、特に順序木という
- 兄と弟を区別
- 表現方法
- 親頂点へのポインタ、｛各子頂点へのポインタを格納した可変長配列/ 「第1子」を表す頂点へのポインタ、「次の弟」を表す頂点へのポインタ｝
- すべての頂点に対して高々k個の子頂点しか持たないものをk分木という
- 二分木において、左側の子頂点を根とした部分木を左部分木、右は右部分木
- 二分木は、計算量解析において好都合な形状→様々なデータ構造において二分木の構造を採用
- ヒープ、二分探索木
- 根付き木において、各頂点vの子頂点の順序を考慮するとき、特に順序木という
- 強平衡二分木
- 根付き木の構造を持つデータ構造は、多くの場面で、各クエリを処理する計算量がO(h)(hは木の高さ) → 高さをできるだけ抑える
- → 強平衡二分木: 二分木であり、すべての葉の深さが高々1しか違わないもの
- 頂点数をNとして、高さがO(logN)
- すべての葉の深さが等しい二分木: 完全二分木
- 根付き木の構造を用いて、多彩なデータ構造を考えられる
- 二分木を用いるデータ構造の例(1): ヒープ
- 正確には二分ヒープを扱う
- ヒープとは
- 各頂点vがキーと呼ばれる値key[v]を持つ二分木であり、以下を満たすもの
- 頂点vの親頂点をpとしたとき、key[p] >= key[v]が成立する
- 木の高さをhとしたとき、木の深さh-1以下の部分については、完全二分木を形成している
- 木の高さをhとしたとき、木の深さhの部分については、頂点が左詰めされている
- → ヒープは特に強平衡二分木となっている → 様々なクエリをO(logN)で処理できる
- 挿入、最大値の取得、最大値の削除が〇
- 値の検索は× → 平衡二分探索木を使う
- 各頂点vがキーと呼ばれる値key[v]を持つ二分木であり、以下を満たすもの
- ヒープの実現方法
- 配列を用いて実現
- ヒープの深さdの各頂点を配列の2d-1,...,2d+1-2番目に対応
- 関係性
- 配列中の添字がkである頂点の左右の子頂点の、配列中の添字がそれぞれ2k+1, 2k+2
- 配列中の添字がkである頂点の親頂点の、配列中の添字が[(k-1)/2]
- ヒープのクエリ処理
- 挿入
- 挿入した値をキー値にもつ頂点とその親である頂点との間でヒープの条件を満たした状態になるまでキー値の交換を繰り返す
- 削除
- 最後尾の頂点を根に持ってくる。その後は挿入と同様、ヒープの条件を満たすまで子の大きい値と交換していく。
- 挿入
- ヒープの実装例
- O(N)時間でヒープの構築ができる
- 二分木を用いるデータ構造の例(2): 二分探索木
- 各頂点vがキーと呼ばれる値key[v]を持つ二分木であり、以下を満たすもの
- 任意の頂点vに対し、vの左部分木に含まれるすべての頂点v'に対して、key[v]>=key[v']が成立し、vの右部分木に含まれるすべての頂点v'に対して、key[v]<=key[v']が成立する
- いずれのクエリ処理も、木の高さ分の計算量
- 平衡二分探索木にすることで、O(logN)でクエリを処理できる。ヒープの機能の1つである最大値を取得する処理もO(logN)となる。
- 実際はO記法で省略される定数部分が大きいので、ヒープで足りればヒープが簡便で〇
- 各頂点vがキーと呼ばれる値key[v]を持つ二分木であり、以下を満たすもの
- まとめ
- グラフは、対象物の関係性を表すことができる強力な数理科学的ツール
- グラフとして定式化して、問題を見通す
- 特殊なグラフとしての木
- 順序木は、連結リストの構造をより豊かにしたもの
- → ヒープや二分探索木などの多彩なデータ構造を設計
- 章末問題
- 10.5 サイクルを持たないのが木
Ch11 データ構造(4): Union-Find
- グループ分けを効率的に管理するデータ構造
- 根付き木の構造を用いる
- Union-Findとは
- グループ分けを管理するデータ構造
- 以下のクエリを高速に処理する
- issame(x, y): 要素x, yが同じグループに属するかどうか調べる
- unite(x, y): 要素xを含むグループと、要素yを含むグループとを併合する
- Union-Findの仕組み
- 1つ1つのグループが根付き木を構成するようにして実現
- ヒープや二分探索木とは異なり、二分木である必要はない
- root(x)
- 要素xを含むグループ（根付き木）の根を返す
- O(h)
- issame(), unite()を実現
- Union-Findの計算量を削減する工夫
- union by size(or union by rank)
- 経路圧縮
- 実際上はO(1)とみなせる
- union by size
- 頂点数の小さい方の根付き木を、大きい方に併合する
- → 各根付き木の高さをO(logN)で抑えられる
- 頂点xの深さが1増加するときは、頂点xを含む根付き木の頂点数も2倍以上になる
- サイズの小さいほうのデータ構造を大きいほうに併合するという手法は、データ構造を併合する場面で一般的に使える
- 経路圧縮
- xから上へと進んでいって根に到達するまで経路中の各頂点に対し、その親を根に張り替える
- Union-Findの実装
- 構造体として実装
- par, siz
- Union-Findの応用: グラフの連結成分の個数
- 連結成分をグループとして扱う
- root(x) == xを満たすxを数える
- O(|E|α(|V|))
- まとめ
- Union-Findはグループ分けを効率的に管理するデータ構造
- シンプルな実現方法、奥が深い
- 適用範囲が広い
- グラフに関する問題は、Union-Findによっても解くことができる
- クラスカル法の高速化のためにも使う
- 章末問題
- 11.1 各辺でループ。各辺のみつながないUnion-Findで、連結成分の個数が2つになればその辺が橋となる
- 11.2 https://drken1215.hatenablog.com/entry/2019/03/03/224600
- グラフのクエリ問題で辺を削除するのはとても扱いづらい
- 辺を追加すると読み替える
- 求める値が異なる
- issame(a, b)=trueだったらcontinue, falseなら連結成分の個数が減る
- グループ分けの問題なので、Union-Findが使える
- 11.3 道路についてと鉄道についてそれぞれのUnion-Findを持つ
- サイズを求めればそれぞれのみで行ける頂点の個数が分かる
- 11.4 重み付きUnion-Findを使う
- https://qiita.com/drken/items/cce6fc5c579051e64fab#abc-087-d-people-on-a-line
- 直接つなげるのではなく、連結成分同士をつなげる
- rootまでの重みを持つ。差が重みになる
- 差が合わなかったらfalse、マージし切れたら（連結し切れたら）〇
Ch12 ソート
- 分割統治法、ヒープなどのデータ構造、乱択アルゴリズムの考え方など、さまざまなアルゴリズム技法を学ぶことができる題材
- ソートアルゴリズムに用いられるアルゴリズム技法を学ぶ
- ソートとは
- 与えられたデータの列を、所定の順序に従って整列
- 実用上とても重要な処理
- 前処理としても使われる
- 実用的にも理論的にも重要な処理 → 多数のアルゴリズムがある
- ソートアルゴリズムの良し悪し
- in-place性と安定性
- どのソートアルゴリズムがよいか
- ほとんどの場面で、各言語の標準ライブラリを用いれば十分
- ソートの使いどころの習熟が重要
- 挿入ソート
- マージソート
- 動作と実装
- 計算量と性質
- O(NlogN)
- not in-place
- → 組込系など、ソフトウェアの移植性を重視しつつアルゴリズムを常に高速に動作させたい場合には採用されにくい
- ただし、必要なメモリ容量は入力受け取りに要するメモリ容量の高々定数倍なので、問題ない場面も多い
- 安定〇
- 計算量解析の詳細
- クイックソート
- ヒープソート
- ソートの計算量の下界
- 比較ソートアルゴリズム: ソート順序が入力要素の比較にのみ基づいて決定される
- 最悪の場合は、Ω(NlogN)回の比較が必要
- 2h >= N!から求めていく
- 比較ソートアルゴリズム: ソート順序が入力要素の比較にのみ基づいて決定される
- バケットソート
- まとめ
- 章末問題
- 12.1 インデックスと値の組を配列で持つ。値でソート。ソート後のインデックスを入れる。元のインデックスでソート。
- ソートする。それぞれの値で二分探索する。どちらもO(NlogN)。
- 12.2 金額と本数の組を配列で持つ。金額でソートして足していけばOK。
- 12.5 http://www.dais.is.tohoku.ac.jp/~shioura/teaching/ad11/ad11-06.pdf
- たぶんこれ
- 軸要素の選び方を工夫することで、次の反復での要素数を3/4n以下とできる
- 12.6 もう1回同じ問題に当たったら考えよう
- 12.1 インデックスと値の組を配列で持つ。値でソート。ソート後のインデックスを入れる。元のインデックスでソート。
Ch13 グラフ(1): グラフ探索
- グラフ探索を学ぶ意義
- あらゆるグラフアルゴリズムの基礎
- 単にグラフに関する問題を解決できるだけでなく、さまざまな対象物に対する探索を見通しよく扱えるようになる
- ウォーク、サイクル、パスや連結性も自在に扱える
- DFS,BFS
- グラフ探索の基本形
- 問題設定: グラフ上の代表的な1つの頂点s∈Vを指定して、sから辺をたどって到達できる各頂点を探索する
- stack(DFS), queue(BFS)を用いて実現
- todo, seenを管理する
- seen[x] = trueならばその頂点xを飛ばすのが重要
- グラフ探索の基本形
- 再帰関数を用いるDFS
- 簡潔に実装できる
- 再帰関数を用いることで、「行きがけ順」「帰りがけ順」という重要な概念も明快なものになる
- 「行きがけ順」と「帰りがけ順」
- 最短路アルゴリズムとしてのBFS
- DFS, BFSの計算量
- グラフG=(V, E)に対するアルゴリズムの計算量を述べるときは、通常は、頂点数|V|, 変数|E|の2つを入力サイズとする
- 密グラフ: |E|=θ(|V|^2)
- e.g. 完全グラフ: すべての頂点間に辺があるような単純グラフ
- 疎グラフ: |E|=O(|V|)
- e.g. 各頂点について接続している辺の本数が高々k本であるようなグラフ
- DFS, BFSとも、O(|V| + |E|)
- グラフを入力として受け取るのと同等の計算量で探索可能
- グラフ探索例(1): s-tパスを求める
- 頂点sを始点としたグラフ探索。その過程で頂点tを訪問したかどうかを調べることで解ける
- グラフ探索例(2): 二部グラフ判定
- 二部グラフ: グラフを左右のカテゴリに分割して、同じカテゴリ内の頂点間には辺がない状態にできること
- 白に隣接した頂点はすべて黒に塗る。逆も同じ。
- 両端点が同色であるような辺が検出されたら、二部グラフでないことが確定する ←→ 探索が終了すれば二部グラフ
- グラフ探索例(3): トポロジカルソート
- グラフ探索例(4): 木上の動的計画法
- 根なし木に対しても便宜的に根をどれか1つ決めて根付き木とすることで、しばしば見通しが良くなる
- 木に根を指定することで、「系統樹」としての構造が生まれる
- ある1つの頂点を決めて根にすることで形成される根付き木の形状を求める問題を考える
- 各頂点vに対して以下の値を求める
- 頂点vの深さ
- 頂点vを根とした部分木のサイズ（部分木に含まれる頂点数）
- 子情報をまとめる処理のため、BFSよりDFS
- 木がサイクルを持たないことを利用して、実装を簡潔にする
- 根なし木を根付き木としたときの各頂点の深さを求める
- 部分木サイズの漸化式
- subtree_size[v] = 1 + Σc:(vの子頂点)subtree_size[c]
- 1は頂点v自身
- 頂点vの各子頂点cに対してsubtree_size[c]が確定している必要がある
- → 帰りがけ時に実行する必要がある
- 子頂点についての情報を用いて、親頂点についての情報を更新する: DPを木に対して適用
- O(|V|)
- 各頂点vに対して以下の値を求める
- 各頂点の深さ: 行きがけ時に求めた
- 各頂点を根としたときの部分木のサイズ: 帰りがけ時に求めた
- 行きがけ順を意識した処理は「親頂点についての情報を子頂点に配る」のに適していて、帰りがけ順を意識した処理は「子頂点の情報を集めて親頂点の情報を更新する」のに適している
- 根なし木に対しても便宜的に根をどれか1つ決めて根付き木とすることで、しばしば見通しが良くなる
- まとめ
- 章末問題
- 13.6 https://qiita.com/drken/items/a803d4fc4a727e02f7ba#4-6-%E3%82%B5%E3%82%A4%E3%82%AF%E3%83%AB%E6%A4%9C%E5%87%BA
- 与えられたグラフがサイクルを含むということは、ある頂点 v に対して、頂点 v から出発した探索が、v から行くことのできる全頂点の探索を終えるよりも先に (すなわち帰りがけの状態になる前に)、v に戻って来てしまうということ
- 13.6 https://qiita.com/drken/items/a803d4fc4a727e02f7ba#4-6-%E3%82%B5%E3%82%A4%E3%82%AF%E3%83%AB%E6%A4%9C%E5%87%BA
Ch14 グラフ(2): 最短路問題
- グラフの各辺に重みがある場合の最短路問題に対する解法を見る
- → 現実世界の問題への応用範囲が飛躍的に広がる
- DPや貪欲法の応用がある
- 最短路問題とは
- グラフ上で長さが最小の路（ウォーク）を求める問題
- l(e): 各辺の重み
- l(W): 路W(walk)の長さ
- l(C): 閉路(cycle)Cの長さ
- l(P): 道P(path)の長さ
- カーナビや鉄道の乗換案内サービスという応用が広いだけでなく、理論的にも重要な問題
- 重み付き有向グラフ
- 一般性が高い考察対象
- 単一始点最短路問題
- 各頂点への最短路を重ね合わせると頂点s(=0)を根とした根付き木になる
- 負辺と負閉路
- 負閉路はいくらでも路長を小さくできる
- 負閉路を持たないか、始点から負閉路に到達できない、または負閉路から頂点vに到達できない場合は、最短路を求められる
- 最短路問題の整理
- 緩和
- DAG上の最短路問題: 動的計画法
- DAGにおける緩和処理の順序のポイント
- 各辺e=(u, v)に対して緩和処理を実施するときには、頂点uに対するd[u]が真の最短路長に収束している
- ↑ トポロジカルソートで担保。緩和すべき辺の順序を明らかにできる
- DAGにおける緩和処理の順序のポイント
- 単一始点最短路問題: ベルマン・フォード法
- 有効閉路を含む有向グラフに対しても最短路を求めることのできるアルゴリズムを考える
- もし始点sから到達できる負閉路が存在するならばその旨を報告し、負閉路が存在しないならば各頂点vへの最短路を求めるアルゴリズム
- 辺の重みがすべて非負であることが保証されている場合は、ダイクストラ法が〇
- アイディア
- 「各辺に対して一通り緩和する（順序は不問）」という操作を、最短路長推定値d[v]が更新されなくなるまで反復する
- 高々|V|-1回の反復で、d[v]の値が真の最短路長d[v]に収束する
- → 各辺に対する緩和をO(|V|)回反復するため、O(|V||E|)
- |V|回目の反復時にある辺e=(u, v)が存在して、辺eに関する緩和によってd[v]の値が更新されるとき、始点sから到達可能な負閉路がある
- 実装
- 更新が発生しなければ反復を打ち切る
- 正当性
- 路を道にしても長さは減少しない
- 単一始点最短路問題: ダイクストラ法
- すべての辺が非負であることが分かっている場合には、より効率的
- 2種類のダイクストラ法
- 実現するためのデータ構造として何を用いるかによって、計算量が変わる
- 単純に実装した場合の、計算量O(|V|^2)の方法
- ヒープを用いる場合の、計算量O(|E|log|V|)の方法
- 密グラフでは前者が〇、疎グラフでは後者が〇
- 実現するためのデータ構造として何を用いるかによって、計算量が変わる
- 単純なダイクストラ法
- 貪欲法に基づいたアルゴリズム
- 各辺が非負と分かっている場合は、最短路長推定値d[v]を動的に更新していく過程で、緩和を行うべき頂点順序が自動的に決まる構造になる
- 「すでに最短路が求められていることが確定している頂点の集合S」を管理する
- 「まだSに含まれていない頂点vのうち、d[v]の値が最小の頂点」に着目(始点とする頂点を探す)
- → 頂点vをSに挿入し、頂点vを始点とする各辺について緩和
- 直感的なイメージ
- 「各節点を左から順にひもをピンと張っていく動作」をアルゴリズムとして実現したもの
- 右手のつまみを選び、節点vとほかの節点間のひもをピンと張っていく
- 正当性
- 数学的帰納法で示す
- 疎グラフの場合: ヒープを用いた高速化
- 疎グラフであればO(|V|log|V|)
- ダイクストラ法の高速化を目指す部分
- 使用済みでない頂点vのうち、d[v]の値が最小の頂点vを求める部分
- ヒープの各要素
- 使用済みでない頂点v
- その頂点vにおけるd[v]
- 更新後のd[v]の値を新たにヒープに挿入する
- 古いd[v]はごみとして残るだけなので問題ない
- ヒープサイズは高々|E|
- 最良優先探索
- 取り出したdよりdist[v]が小さいときは、(d, v)はごみ
- https://cpprefjp.github.io/reference/queue/priority_queue.html
- 要素の型、内部コンテナ、昇順降順を指定する
- 全点対間最短路問題: フロイド・ワーシャル法
- 参考: ポテンシャルと差分制約系
- ポテンシャル: 各節点間がピンと張られているとは限らない場合において、各節点の位置関係としてあり得るもの
- 各頂点vに対して値p[v]が定まっているとき、任意の辺e=(u, v)に対して、p[v]-p[u]<=l(e)を満たすようなp
- 最短路問題の最適性の証拠
- ポテンシャル: 各節点間がピンと張られているとは限らない場合において、各節点の位置関係としてあり得るもの
- まとめ
- グラフ上の最短路を求める問題の解放として、古典的によく知られているものをまとめた章。
- DP、貪欲法、グラフ探索、ヒープなどの、アルゴリズム設計技法・データ構造が活躍
- 最短路問題は実用上重要な問題なだけでなく、理論的に重要な位置づけ
- 章末問題
- 14.1 トポロジカルソート→DP
- 14.2 https://drken1215.hatenablog.com/entry/2019/02/16/075900
- 14.3 https://drken1215.hatenablog.com/entry/2019/07/01/111500
- 頂点vを(v, 0), (v, 1), (v, 2)に拡張する
- 14.4 https://betrue12.hateblo.jp/entry/2018/12/08/000020
- 0-1BFS.両端に挿入できるキューを使う．
- 14.5 http://fluffyowl.hatenablog.com/entry/2017/11/07/194832
- https://img.atcoder.jp/arc084/editorial.pdf
- 全ての正整数は，1から始めて，以下の2つの操作の繰り返しで作れる
- 1足す．各桁の和は1増える．
- 10倍する．各桁の和は変わらない．
- 各頂点をmodKで同一視することで，頂点を0からK-1のK個で考えることができる．
- 1から0への最短路を求める．
- 0-1BFSを用いる
- modKで0の集合 = Kの倍数の集合
Ch15 グラフ(3): 最小全域木問題
- ネットワーク設計において基本的な問題の1つ
- いくつかの通信拠点をすべて通信用ケーブルでつなぎ，すべての建物間で通信できるようにしたいとする．これを最小コストで実現する方法を問う問題．
- クラスカル法で解く．
- 貪欲法に基づく．
- 構造自体によい性質が内包されている．
- きわめて深淵で美しい理論が背後にある問題．
- 貪欲法に基づく．
- 最小全域木問題とは
- w(e): グラフの各辺の重み
- Gの部分グラフであって木であるもののうち，Gの全頂点をつなぐものを全域木(T)と呼ぶ．
- w(T): 重みは，w(e)の総和．
- 最小全域木問題とは，重みが最小の全域木を求める問題．
- 最小の長さのケーブルで全地点を接続する問題．
- クラスカル法
- クラスカル法の実装
- グラフGの各辺を，辺の重みが小さい順にソート．
- Union-Findを用いることで，効率的に実現．
- 開始時点では，Union-Findの各頂点が単独で別々のグループを形成している状態とする．
- 新たな辺e=(u,v)を追加するとき，Union-Find上の点u',v'について，unite(u',v')を実施する
- サイクルが形成されてしまうかどうかを，u'とv'が同じグループに属するかで判定できる
- O(|E|log|V|)
- 全域木の構造
- クラスカル法の正当性
- 最小全域木の最適性条件
- 局所最適解
- 全域木間での辺の交換
- 連結な重み付きグラフG=(V,E)において，2つの相異なる全域木をS,Tとする.Sには含まれるがTには含まれないeを1つとる．このとき，Tに含まれるがSには含まれない辺fが存在して，S'=S-e+fも全域木となる．
- S,eに関する基本カットセットと，T,eに関する基本サイクルにともに含まれる辺のうちeでない辺がf．
- → SをS’とすることでTに近づく
- w(S)>=w(S')>=w(S'')>=...>=s(T)
- ここまでの議論はﾏﾄﾛｲﾄﾞに一般化できる．
- ﾏﾄﾛｲﾄﾞ: 離散的な凸集合を表すもの
- ﾏﾄﾛｲﾄﾞの概念をさらに拡張したM凸集合を考えることもできる．
- → 離散凸解析
- まとめ
- 章末問題
Ch16 グラフ(4): ネットワークフロー
- ネットワークフロー理論: 「きれいに解ける」問題の代表
- ネットワークフローを学ぶ意義
- 「効率よく多項式時間で解ける問題」を象徴する存在．
- 興味深い性質や構造がある．
- 多彩な応用
- 連結度，二部マッチング，プロジェクト選択
- ある程度の制約条件までは表現できる柔軟性もある．
- ネットワークフローで解ける問題を見逃すのはもったいない．
- 最大流問題と最小カット問題を見る．
- グラフの連結度
- 最大流問題において，各辺の容量を1とした特殊なケース．
- 辺連結度
- 頂点sから頂点tに対して互いに辺を共有しないs-tパスの本数の最大値が，グラフの2頂点s,tに関する辺連結度．
- グラフネットワークの頑健性を評価するもの．
- 互いに辺を共有しないこと: 辺素(edge-disjoint).
- カットセットの辺の本数: カットの容量→辺連結度になる．
- 最小カット問題
- (辺の容量が1の場合)有向グラフG=(V,E)と2頂点s,t∈Vが与えられる．s-tカットのうち，容量が最小のものを求める．
- 辺連結度に関する問題の弱双対性
- 辺素なs-tパスの最大本数<=s-tカットの最小容量．
- 任意のs-tカットを考えて，c(S,T)>=kであることを見る．
- 意味(s-tカットの容量がちょうどkのとき)
- 辺素なs-tパスの最大本数=k
- s-tカットの最小容量=k
- → 辺連結度に関する問題の強双対性
- 辺素なs-tパスの最大本数=s-tカットの最小容量
- 辺連結度を求める問題と最小カット問題は双対
- 辺連結度を求めるアルゴリズムと強双対性の証明
- フォード・ファルカーソン法を，各辺の容量が1のグラフに対して適用したものを見る
- 「s-tパスを追加でとれるならとる」という処理を繰り返す，という貪欲法に基づいたアルゴリズムによって求められる．
- 残余グラフを考える
- 残余グラフ: s-tパスをとったとき，パス上の各辺に対して逆向きの辺を張りなおしたグラフ
- 2頂点s-t間の辺連結度を求めるアルゴリズム
- パスの本数を表す変数をf(←0)と初期化する．
- 残余グラフG'をもとのグラフGで初期化する．
- while G'において，s-tパスPが存在するならば:
- f++
- G'をPに関する残余グラフに更新
- fが求める連結度
- 図16-6: k本の辺素なs-tパスを得るとき，容量kのカットを構成できることを示す．
- →c(S,T)=k
- kが最大でもO(|V|)であり，各反復においてs-tパスを見つける処理はO(|E|)→全体でO(|V||E|)
- 最大流問題と最小カット問題
- 各辺eが容量c(e)をもつ一般の場合の最大流問題を考える
- 各辺eに対して流量を表す値x(e)があって，以下の条件を満たすとき，xをフロー(許容フロー)という．
- 任意の辺eに対して，0<=x(e)<=c(e).
- 任意のs,t以外の頂点vにおいて，vに入る辺eに対するx(e)の総和と，vから出ていく辺eに対するx(e)との総和が等しい．
- 各辺eに対するx(e)を辺eの流量
- 頂点sから出ていく辺eに対するx(e)の総和を，フローxの総流量
- 総流量が最大のフローを最大フロー
- 最大フローを求める問題を最大流問題
- フローの性質
- 辺素: 容量が1の辺に2以上の流量を流せないことを意味する
- 任意のカット(S,T)に対し，SからTへ出ていく各辺eの流量x(e)の総和から，TからSへ入ってくる各辺eの流量x(e)の総和を引いた値が，フローxの総流量に一致する．
- どこを観察しても流量が一定
- 最小カット問題との双対性
- c(S,T): s-tカット(S,T)に含まれる辺eの容量c(e)の総和(s-tカット(S,T)の容量)．
- 最小カット問題
- 容量つき有向グラフG=(V,E)と2頂点s,t∈Vが与えられる．s-tカットのうち，容量が最小のものを求める．
- 最大流最小カット定理
- 最大フローの総流量=s-tカットの最小容量
- 「残余グラフ上で見つけたs-tパス上にフローを流せるだけ流す」という処理を，残余グラフ上にs-tパスがなくなるまで繰り返すことで証明する．
- フォード・ファルカーソン法というアルゴリズム
- フォード・ファルカーソン法
- 残余グラフでは，uからvへはc(e)-x(e)の容量を持つ辺を張る
- vからuへはc(e')+x(e')の容量の辺を張る
- 残余グラフ上のs-tパスPを1つ見つけて，Pに含まれる辺の容量の最小値fのフローをP上に流す．
- 最大流を求めるフォード・ファルカーソン法
- フロー流量を表す変数FをF←0で初期化
- 残余グラフG'を元のグラフGで初期化
- while 残余グラフG'においてs-tパスPが存在するならば:
- fをパスP上の各辺の容量の最小値
- F+=f
- パスP上に大きさfのフローを流す
- 残余グラフG'を更新
- Fが求める最大流量
- 証明は辺連結度と同様
- O(F|E|)
- フォード・ファルカーソン法の実装
- 難所:各辺e=(u,v)に対して，逆向きの辺e'=(v,u)を取得できるようにする
- グラフGの入力受け取り時に，辺e=(u,v)を，配列G[u]の最後尾に挿入するときに，同時に配列G[v]に対しても，容量0の逆辺e'=(v,u)を最後尾に挿入する．「e'がG[v]のなかで何番目の要素に相当するかを示す変数rev」を辺eにもたせ，同様の変数をe'にも持たせる．
- 辺e=(u,v)の逆辺はG[v][e.rev]と表せる
- 難所:各辺e=(u,v)に対して，逆向きの辺e'=(v,u)を取得できるようにする
- 応用例(1): 二部マッチング
- 新たに頂点s,tを用意してグラフネットワークを作ることで，最大流問題に帰着させられる．
- 応用例(2): 点連結度
- 辺連結度: 「ネットワークの破壊は「辺」で発生する」という辺故障モデルでネットワークの耐故障性を評価
- 点連結度: 「ネットワークの破壊は「頂点」で発生する」という点故障モデルでネットワークの耐故障性を評価
- 点素: 2本のパスが点素であるとは，頂点を共有しないこと
- 点素なs-tパスの最大本数と，s-t間を分断するために破壊する必要のある頂点数の最小値とが等しいという強双対性．この値を点連結度．
- 各頂点vを2頂点vin, voutに分裂させることで，辺連結度を求める問題に帰着
- 応用例(3): プロジェクト選択問題
- プロジェクト選択問題で考慮する制約条件
- u番目のボタンを押すならば，v番目のボタンを押さなければならない．
- この制約下で得られる総利得を最大にする問題を考える．
- 露天採鉱問題
- コストを最小化する問題に読み替える
- プロジェクト選択を，カットに帰着するアイディア
- {s,t.0,1}を頂点集合に持つグラフであって，以下の条件を満たすものを構成したい
- ボタン0,1をともに押すときのコストが，S={s,0,1},T=V-Sのカットの容量に一致
- ボタン0のみ→S={s,0}
- ボタン1のみ→S={s,1}
- ボタンをともに押さない→S={s}
- →図16.19
- このグラフ上で最小カット問題を解くことで，ボタンの押し方の最適解を求められる．
- {s,t.0,1}を頂点集合に持つグラフであって，以下の条件を満たすものを構成したい
- N個のボタンとM個の制約条件に対しても自然に拡張できる．
- プロジェクト選択問題で考慮する制約条件
- まとめ
- 章末問題
- 16.1 M頂点の先に頂点tを設定し，最小のs-tカットを求める．
- 16.2 https://drken1215.hatenablog.com/entry/2019/02/15/190700
- s-t間の最短路それぞれについて，距離を1伸ばす必要がある．
- 最短路が複数ありうるため，1つの辺を伸ばせばよいということではない．
- それぞれのカットの容量が，最短路を1伸ばすためのコストとなる．
- → 最小カット問題を解けばよい．
- 16.3 https://jag-icpc.org/?plugin=attach&refer=2014%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9C%B0%E5%8C%BA%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=F.pdf
- 最大流を流した後の残余グラフを考える．
- 残余グラフで使っていないすべての辺について，sから行ける頂点集合Xにvが含まれ，tから行ける頂点集合Yにuが含まれているか調べて，カウントする．
- 16.4 互いに素でないカード間に辺を張り，s,tを用意して最大流問題に帰着させればよさそう．
- 16.5 https://qiita.com/drken/items/7f98315b56c95a6181a4
- 最大安定集合問題
- 点被覆と安定集合の関係
- 一般の無向グラフにおいて，点被覆の補集合は安定集合をなし，安定集合の補集合は点被覆をなす．
- 最小辺被覆と最大マッチングの関係
- 孤立点のない一般の無向グラフで最大マッチングが得られているとする．マッチングの端点となっていない頂点それぞれにつき1本ずつ枝を追加すると，それが最小辺被覆となる．
- https://drken1215.hatenablog.com/entry/2019/06/17/221400
- https://www.slideshare.net/drken1215/ss-86894312
- 最小点被覆の補集合は最大安定集合
- 補助グラフを作る
- マッチング枝は右から左，それ以外は左から右
- 左側の頂点のうち，マッチングの端点でない頂点を赤く塗る
- 赤く塗った頂点から矢印の向きに進んでいって到達できる頂点を赤く塗る
- 左側の白い頂点と右側の赤い頂点が最小点被覆
- 上記のように，二部マッチング，最小点被覆を求めて，その補集合が答え
- 16.6 https://img.atcoder.jp/arc085/editorial.pdf
- 最小カット問題の解法は，以下のような問題を解くことができる
- 変数q[s],q[t],q[1],...,q[v]を考える
- 罰金条件(x,y,z)がたくさん与えられる．q[x]=0,q[y]=1なら罰金z円．
- 変数に0,1のどちらかを割り当て，罰金を最小化する．a[s]=0,a[t]=1は固定．
- 変数が頂点，罰金条件が辺
- まず，iを壊してjを壊さないケースについて，(i,j,∞)を追加する．
- a[i]<=0→(S,i,-a[i]), a[i]>0→(i,T,a[i])
- 左と右それぞれに罰金の辺を張る．
- 左は処理をする頂点，右は処理をしない頂点の集合を作るための辺となる．
- 処理をした場合の集合と処理をしない場合の集合の2つを作った時の，最小カットを求める．
- https://betrue12.hateblo.jp/entry/2019/07/05/012450
- 最小カット問題の解法は，以下のような問題を解くことができる
Ch17 PとNP
- 問題の難しさの測り方
- PとNP
- 判定問題と最適化問題
- P, NPは判定問題の集合
- クラスP: 多項式時間アルゴリズムが存在する判定問題の全体
- 安定集合問題
- 無向グラフG=(V,E)において，頂点集合の部分集合S⊂Vが安定集合であるとは，Sのどの2頂点も辺で結ばれないこと．
- 正の整数kが与えられたとき，サイズがk以上の安定集合が存在するかどうか判定する．
- ハミルトンサイクル問題
- 有向グラフG=(V,E)において，各頂点をちょうど1度ずつ含むサイクル．
- グラフGがハミルトンサイクルを持つか判定する．
- クラスNP: 判定問題の答えがYesである場合において，そのYesである証拠が存在して，それをYesであることを多項式時間で検証できるもの．
- PはNPに属する．
- P⊂NP⊂EXP
- EXP: 指数時間アルゴリズムで解ける問題のクラス
- P≠NP予想
- NPに属するがPに属さないという問題が見つかっていない．
- NP完全
- 多項式時間帰着の例
- 点被覆問題
- 部分和問題
- NP困難
- 停止性問題
- NPに属さないがNP困難
- コンピュータプログラムPと，そのプログラムへの入力Iが与えられる．Iを入力としてPを実行したとき，Pが有限時間で停止するかどうかを判定する．
- まとめ
- 現実に解決できそうもない難問Xと出くわしたときは，知られているNP困難問題Yをどれか1つ持ってきて，YをXに帰着できないか考えることが有効．
- 章末問題
- (メモなし)
Ch18 難問対策
- NP困難問題との対峙
- 個別な入力ケースに対しては，現実的な時間で解を導ける可能性がある．
- 特殊ケースで解ける場合
- 貪欲法
- 局所探索と焼きなまし法
- 近傍: 「ほんの少し変更を加えたもの」
- 局所最適解が全体の最適解とは限らない．
- → 焼きなまし法．f(x)の値が改善されないような近傍への移行も確率的に許す．
- 温度と呼ばれるパラメータでその確率を制御する．
- 分岐限定法
- 枝刈り
- 「これから探索しようとしているノード以降がそれまでの最良解Lより良い解を導く可能性がない」と判断できたら，そのノード以下の探索を打ち切る．
- 理論的な計算量は下げないが，現実世界の実際の問題に対しては極めて高速に動作することが多々ある．
- 整数計画問題への定式化
- 近似アルゴリズム
- まとめ
- 章末問題
『コンピュータネットワーク 第5版』 第1章(以降は未書き起こし)
ch01 序論
- computer network: 単一の技術で相互接続された自律的コンピュータ（複数）として扱う。
- 分散システム: ユーザには単一の均一なシステムに見える。単一のモデル、パラダイムを持つ。ネットワークで実現される。ネットワークとの違いは、ハードウェアではなくソフトウェアにある。
- 例: www
1.1 computer networkの目的
- 資源シェアリング
- VPN
- クラサバモデル
- 例: ウェブアプリケーション
- 2つのプロセスがかかわる
- 通信媒体、communication medium
- IP telephone, VoIP
- desktop sharing
- e-commerce
internet accessがconnectivityを与える
P2P vs クラサバ
- 例: メール
- instant messaging
- social network
- IPTV
- ubiquitous computing
- 測定・通信
- Radio Frequency IDentification(RFID): 無線自動識別 → IoT
- 受動チップ（電池なし）
- internetへの接続がモバイル化を可能にする
- 固定/移動無線
- texting, SMS
- GPS
- m-commerce
- NFC: Near Field Communication
- sensor network
- socail problem
1.2 network hardware
- 伝送技術
- broadcast, point-to-point
- radio network
- address fieldで全ての宛先を指定
- multicast: すべてではなく一部
- point-to-point
- unicast
- best-way-search
- broadcast, point-to-point
- 規模
- Personal Area Network ~ Inter Network → 惑星間Inter Network
- PAN
- bluetooth
- master-slave
- bluetooth
- Local Area Network(LAN)
- Metropolitan Area Network(MAN)
- cable TV systemから
- WiMAX
- Wide Area Network(WAN)
- 1つの国や大陸
- subnetがホスト間でメッセージを送る。
- 伝送回線、交換要素(switch)
- switch: 2本以上の伝送回線の接続に特化したコンピュータ。ルータなど
- 伝送回線、交換要素(switch)
- subnet: 通信回線とルータの集合 ←→ network address の subnetとは違う
- WANでは、ホストとサブネットは別々の人が所有・運用
- 多くのWANはinternetworks(複数のnetwork)から構成される。ルータは異なるnetwork 技術をつなぐ。
- subnetにはLAN全体も接続〇
- VPN
- 資源の柔軟な再利用
- Network Service Provider: NSP
- Internet Service Provider: ISP
- このsubnetがISP network
- routing algorithm, 転送algorithm
- 衛星network: 本質的にbroadcast system
- 携帯のnetwork
- 相互接続した異なるnetworkの集合: internetwork
- Internet(世界規模の1つの特定のinternet)
- ISP networkを用いる
- subnet: network operatorが所有する回線やルータの集合
- network: 単一のテクノロジーで相互接続されたコンピュータの集合
- internetwork: networkの異なる部分を異なる組織が担う or 用いている技術が異なる
- 2つ以上のnetworkをつなげ、hardware, software両方の観点から必要な変換を提供: gateway
- router: network層でパケットを交換するgateway
1.3 network software
- network softwareは高度に構造化
- layer, level: encapsulation
- protocol: あるマシンの第n layerが、他のマシンの第n layerと会話するときの規則や習慣を第n layer protocol
- peer: 異なるコンピュータ上で対応するlayerを構成する主体。プロトコルを用いて互いに通信し合うもの
- 第1層の下に、実際に通信する物理媒体(physical medium)がある
- IF: 隣り合った層の間。層間のIFを明確に定めることが、network設計の最重要考慮点の1つ
- 層とprotocolの組み合わせ: network architectureと呼ぶ
- protocol stack: あるシステムで用いることができる層ごとに1つずつあるprotocolのリスト
- network architecture, protocol stack, protocolそのものが主題となる
- 多層通信の類推
- 各層のprotocolは完全に独立
- 各プロセスは、自分のピアだけへの情報を付加できる
- e.g. header @第3,4 layer, trailer@第2 layer
- 各layerの設計課題
- error detection/ correction + routing: 信頼性
- protocol 階層化: networkの進化を支援
- 送受信識別: addressing @下位層、 naming @上位層
- internetworking: 異なるnetwork technologyは異なる制限を持つ
- scalable @大network
- 資源割り当て
- 統計的多重化
- フローコントロール: 受信側から送信側へのフィードバック
- congestion: 定員超過
- サービス品質: realtime配送など
- 秘密性
- 認証、完全性（messageの不正な変更を防ぐ) by cipher
- connection指向サービスとconnectionless サービス
- connection指向: 管のように振る舞う。
- 交渉。例: 回線(circuit)。固定的な帯域のような資源を伴うconnection
- connection less: ← 郵便システムのよう。
- packet: network layer のmessage
- 蓄積交換/cut-through交換
- packet: network layer のmessage
- 高信頼connection指向の例: ファイル転送
- 境界あり：message列（本）/ 境界なし：byte-stream（映画）
- 低信頼（=確認通知） connectionless サービス（電報のよう）
- データグラムサービス
- e.g. VoIP
- 確認通知データグラム → 信頼性要
- e.g. ケータイのテキストメッセージ
- request-reply service
- e.g. クラサバモデルの通信の実現
- connection指向: 管のように振る舞う。
- サービスの一覧
- Ethernetは高信頼通信なし
- サービス・primitive(操作)
- service ←→ protocol: 1つの層の中の同位entity間で交換されるpacketやmessageなどのformatの意味を決める規則の集合
- サービスは、サービスにアクセスするユーザープロセスから利用できるprimitiveの集合として定義できる
- primitive（の集合）は、システムコール。サービスの性質に依存。
- e.g. LISTEN, CONNECT, ..., DISCONNECT
- e.g. クラサバでのrequest-replyのやりとり with acknowledged datagram
- client, server間のやり取りの図がある
- 第k+1 layerは第k layerの提供するサービスを使う。第k layer 間はプロトコルを共有。
- →サービスとプロトコルは完全に分離
- service: object
- protocol: implement
1.4 参照モデル
- OSI(Open System間 Interconnection) 参照モデル
- 各layerのサービスやプロトコルは指定していないので、network architectureとはいえない
- 7層である理由
- 物理layer: 1のbitが反対にも1で確実に受信されることが重要
- datalink layer: 送信側が入力データをデータ・フレームに分割。受信側は各フレームを正しく受信したことをacknowledged frameを送り返して確認
- 役割: 生の伝送設備を未検出の伝送誤りのない回線と見える回線に変換
- 媒体アクセス制御(medium access control)副層
- network layer: subnetの動作をcontrol。送信元から宛先へパケットをどのような経路で通すか決定。異質なnetworkの相互接続のための問題解決。ブロードキャストでは、network layerはないか単純なもののみ。
- transport layer: 送信元から宛先へデータを送るという意味で、真のe2e layer
- 第1～第3 layerは数珠つなぎ。第4～第7はe2e。
- session layer: 対話control, token management（2者が同一の重要な操作を同時に行わないようにする）。同期など（長い伝送にチェックポイント。中断ポイントからリスタート）。
- presentation layer: 転送される情報の文法や意味を取り扱う。（交換するデータ構造を定義。回線上で用いる標準の符号化方式も定義する）。中小データ構造を管理して、より高レベルのデータ構造を定義、交換したりできるようにする。
- application layer: 利用者から一般に必要とされるいろいろなprotocolを含む。
- e.g. HTTP。ブラウザはHTTPでページの名前をサーバに送る。
- TCP/IP参照モデル
- 送信元と宛先のマシンが無事ならconnectionに影響がない
- ファイル転送
- リアルタイム音声転送などの要求
- link layer
- internet layer: network layerに対応
- internet protocol(IP)とinternet control message protocol(ICMP)を定めている
- IP packetを行先に配達する役割
- ルーティング、congestion回避が問題
- transport layer
- application layer
- OSI: modelそのもの
- TCP/IP: protocol
- application layer
- transport layer
- network layer
- link layer
- physical layer
- OSIとTCP/IPの比較
- OSIの中心概念: service/ interface/ protocol
- connection指向/ connectionlessへのサポートの違い
- OSI modelとprotocolの批評
1.5 networkの例
- internet
- ARPANET
- NSFNET
- wwwの出現で爆発的に大きくなった
- internetのarchitecture
- 従来の異なるnetworkが用いられていた用途に対して、1つのnetworkが用いられる電気通信の収束
- → 激変の推進力
- internet access/ connectivityをISPから買う
- Internet eXchange Point(IXP)で、ISPはトラフィックを交換するためにnetworkを接続する
- 接続したISPは互いにピアしているという
- 小さなISPがtransit(より遠くのISP)にお金を払う
- tier 1のISP: e.g. AT&T, Sprint
- data center with Server farm
- 従来の異なるnetworkが用いられていた用途に対して、1つのnetworkが用いられる電気通信の収束
- 「Internetにある」の条件
intranet: 内部networkをinternetと同じ技術で相互接続
第3世代モバイルフォン network
- Advanced Mobile telePhone System(AMPS): 第1世代
- Global System for Mobile Communications(GSM): 第2世代
- Wideband Code Division Multiple Access(WCDMA)とも呼ばれるUniversal Mobile Telecommunication System(UMTS): 第3世代の3Gシステム
- 希少資源: 無線スペクトル
- cellular network
- となりのセル間で周波数再利用という良い再利用をする。
- → network容量増大
- cellular network
- UMTSのarchitecture
- UMTSのnetwork内で、Public Switched Telephone Network(PSTN)のような回線交換core network上にconnectionを設定する
- General Packet Radio Service(GPRS) @ data service
- cellular 基地局の経路変更: handover: soft/ handoff: hard
- Home Subscriber Server(HSS) in core networkが、一夜認証・許可に用いるprofile 情報を知っている
- Subscriber Identity Module(SIM)カードが、セキュリティの基盤+不正防止+正当なnetworkへの交信のチェック
- privacy: SIMカード上の暗号キーが伝送を暗号化
- Long Term Evolution(LTE): 4G technology, WiMAX
- 希少資源: 無線スペクトル
- 1.5.3 無線LAN: 802.11(俗にいうWi-Fi)
- Industrial, Scientific, and Medical(ISM)帯
- 902~928 MHz, 2/4 ~ 2.5 GHz, 5.725~5.825Ghzなどの、免許不要の周波数帯
- codeless phoneや電子レンジなどと競合するのはこのため。
- AP(Access Point) = base station(基地局)
- 有線networkとconnection
- or client間がAPなしに交信〇 = ad hoc network
- multipath fading
- 無線は本質的に放送型の媒体
- 同時に送った複数の伝送が衝突して受信の干渉するという問題がある
- ←→ CSMA(Carrier Sense Multiple Access)方式: 実用上うまく動く
- 移動性の問題
- ↑ APをもった複数セルを接続する分配システムを構成
- 同時に送った複数の伝送が衝突して受信の干渉するという問題がある
- Security
- RFIDとセンサーnetwork
- Radio Frequency IDentification
- 〇passive RFID ←→ △active RFID
- Ultra-High Frequency RFID(UHF RFID)
- 902~928MHz
- backscatter: 反射をひろう
- High Frequency RFID(HF RFID)
- 13.56MHz, 範囲1m以下 ← backscatterではないため。
- Low Frequency RFID(LF RFID)
- 範囲内の複数タグを読み取るという問題
- Security: password(弱い)。タグのメモリがウイルスになる。
- sensor network
- multihop network
- Industrial, Scientific, and Medical(ISM)帯
1.6 networkの標準化
目的: 異なるコンピュータが通信 + 製品市場を拡大
- → 大量生産、製造規模の経済性、より良い実装、価格低下と普及
標準: 相互運用性に何が必要か定義する。
- WiFi Alliance
de facto: from the fact
- de jure; by law
- de facto → de jureに発展
- 3GPP(Third Generation Partnership Project): 団体間の連携
- 国営電気通信企業: PTT(Post, Telegraph & Telephone administration)
- 民営化。自由化。競争。
- ITU(International Telecommunication Union)
- 国際標準はISO(International Organization for Standardization)で作成・出版されている。
- ISOのITU-Tの構成員。
- CD(Committee Draft: 委員会草案)
- DIS(Draft International Standard)
- IS(International Standard)
- DIS(Draft International Standard)
- CD(Committee Draft: 委員会草案)
- ISOのITU-Tの構成員。
- NIST(National Institute of Standards and Technology): 米国商務省の一部
- IEEE(Institute of Electrical and Electonics Engineers)
- Internet の標準
- 「大まかな合意と走るコード：
- 委員会: IAB(Internet Activities Board) @ ARPANET
- Activities → Architecture
- RFC(Request For Comments)での情報伝達
- IRTF(Internet Research Task Force) + IETF(Internet Engineering Task Force)
- Internet Society(学会)が作成
- Proposed standard ← RFC
- → Draft Standard
- → Internet Standard
- → Draft Standard
- World Wide Web Consortium(W3C) @Web
1.7 メートル法の単位
- m: ミリ。μ: マイクロ。
- 1より大きいと大文字
- B: byte, b: bit
- K: 210 @ memory
1.8 本書の概要
- 原理と実践
- architectureの観点に限定
1.9 まとめ
- （メモなし）
『継続的デリバリー』 第15章 学習メモ
継続的デリバリーの管理の概観
1.はじめに
継続的デリバリーにおける、継続的デリバリーの管理についての調査記録です。
継続的デリバリーの中での、継続的デリバリーの管理についての概観を記載します。
『継続的デリバリー 信頼できるソフトウェアリリースのためのビルド・テスト・デプロイメントの自動化』の第15章に対応します。
2.概要・目的
継続的デリバリーの管理の観点は以下の通り。
- 継続的デリバリーはソフトウェアビジネスを前進させるための新しいパラダイム
- コーポレートガバナンス（適合性）とビジネスガバナンス（パフォーマンス・業績）の対立
- デプロイメントパイプラインの作用
- コーポレートガバナンスのための透過性
- ビジネスガバナンスのためのフィードバック
- インクリメンタルなデリバリー
- 自動化による信頼性の向上
- 素早く信頼できるリリース
- リスクやコストの削減
3.対応概要
構成管理とリリース管理のためのステータスモデルは以下を示す。
- プロジェクトの検証の方法、検証のための観点
ソフトウェアデリバリーのライフサイクルの観点は以下の通り。
- 発見期
- ステークホルダーの特定
- 開始期
- 問題解決をステークホルダー間で共有
- 構築期
- 最もシンプルなストーリーに対して、以下を実証
- バージョン管理
- CIでのテスト
- 手動テスト
- 環境へのデプロイ
- 最もシンプルなストーリーに対して、以下を実証
- 開発・リリース期
- イテレーティブでインクリメンタルなプロセスの規範の適用とそれによる作用
- 運用期
- 開発・リリース期と同じく、新たな機能の追加でも、分析・開発・テスト・リリースのプロセスとする
- データ管理のみ異なる
4.対応詳細
(1)リスク管理プロセス
リスク管理プロセスの観点は以下の通り。
(2)デリバリーによくある問題
デリバリーによくある問題として以下が挙げられる。
- 頻度の低いデプロイメント・バグのあるデプロイメント
- 貧弱な品質
- 管理が貧弱なCIプロセス
- 貧弱な構成管理
(3)コンプライアンスと監査
デプロイメントパイプラインの規制への準拠の観点は以下の通り。
- 自動化
- トレーサビリティ
- 観察・分析の共有
- 変更の管理
- 承認プロセス
5.影響・作用
管理作業により、ソフトウェアのデリバリーを効率的に行いつつリスク管理も適切に行い、規制制度にも準拠できる。
6.おわりに
以上が、継続的デリバリーの中での、継続的デリバリーの管理についての概観です。
7.参考文献
『継続的デリバリー 信頼できるソフトウェアリリースのためのビルド・テスト・デプロイメントの自動化』 第15章 継続的デリバリーを管理する
『継続的デリバリー』 第14章 学習メモ
バージョン管理の概観
1.はじめに
継続的デリバリーにおける、バージョン管理についての調査記録です。
継続的デリバリーの中での、バージョン管理についての概観を記載します。
『継続的デリバリー 信頼できるソフトウェアリリースのためのビルド・テスト・デプロイメントの自動化』の第14章に対応します。
2.概要・目的
バージョン管理は、すべての変更の履歴を管理し、複数チームで開発するアプリケーション全体のコードベースを管理する。
3.背景
リビジョンとは、ディレクトリ群の中にある変更されたファイルのセットで構成されたもの。チェンジセットとも言う。 各リビジョンにはリポジトリ内の全ファイルの、ある特定の時点のスナップショットが含まれている。 リビジョン管理システムの歴史についての観点は以下の通り。
- CVSにあった問題
- SVNによる解決
- 商用のバージョン管理システム
- 〇楽観的ロック/×悲観的ロック
- 衝突の解消
4.対応概要
(1)ブランチとマージ
ブランチとマージの分析の観点は以下の通り。
- コードラインポリシー
- マージの問題
- リリースブランチ以外を作らないことの作用→CI
(2)メインラインでの開発
メインライン上での開発の観点は以下の通り。
- 高速フィードバックによりほぼ常にリリース可能な状態。
- メインライン上での開発のCIへの作用
- 不要ブランチの回避
- 抽象化によるブランチパターンの適用
5.対応詳細
(1)分散バージョン管理システム
分散バージョン管理システムの観点は以下の通り。
- 分散バージョン管理システムの作用
- コミット権のボトルネックの解消
- 分散バージョン管理システムの歴史
- 分散バージョン管理システムのCIへの対応
- 企業環境にも対応するための多くの機能を持つ
- 分散バージョン管理システムの使い方と作用
(2)ストリームベースのバージョン管理システム
ストリームベースのバージョン管理システムの観点は以下の通り。
- 「継承」が可能
- 問題：CI・CDへの違反
- Gitなどの分散バージョン管理システムで解決可能
- 静的ビューと動的ビュー
- 問題：速度とロールバック
(3)ブランチ
ブランチの観点は以下の通り。
- リリース用のブランチが解決する問題
- フィーチャーブランチのCIに対する問題と対応
- オープンソースソフトウェアで十分に制約を満たしたときのみ機能する
- チームブランチ≒フィーチャーブランチ
- 以下のような条件が揃って初めて、疎結合なコンポーネントへの移行に使える
- 分散バージョン管理システムの機能
- インクリメンタルな開発
- カプセル化
- 以下のような条件が揃って初めて、疎結合なコンポーネントへの移行に使える
6.影響・作用
バージョン管理のパターンがデプロイメントパイプラインの設計の重要なポイントとなる。
バージョン管理によって素早くローリスクなリリースが可能となる。
7.おわりに
以上が、継続的デリバリーの中での、コミットステージについての概観です。
8.参考文献
『継続的デリバリー 信頼できるソフトウェアリリースのためのビルド・テスト・デプロイメントの自動化』 第14章 高度なバージョン管理
『継続的デリバリー』 第13章 学習メモ
コンポーネントや依存関係の管理の概観
1.はじめに
継続的デリバリーにおける、コンポーネントや依存関係の管理についての調査記録です。
継続的デリバリーの中での、コンポーネントや依存関係の管理についての概観を記載します。
『継続的デリバリー 信頼できるソフトウェアリリースのためのビルド・テスト・デプロイメントの自動化』の第13章に対応します。
2.概要・目的
コンポーネントベースのシステムは以下の特徴を持つ。
- いくつかの部品に分割できる
- 明確に定義された振る舞いを持つ、同じAPIを持つ別のコンポーネントで代替可能
- 他のコンポーネントと最小限のやりとりをする
- カプセル化がされており、一枚岩のシステムの対極である
コンポーネントベースの設計により、以下の恩恵を得られる。
コンポーネントや依存関係を管理することで、以下の、ビルドシステムにおける3つの自由を得られる。
- デプロイメントパイプライン
- ブランチ
- コンポーネント
3.対応概要
アプリケーションをリリース可能な状態に保つための観点は以下の通り。
- メインラインでの開発
- メインラインで開発しながら常にリリース可能にするための解決策
- 新機能は完成するまで隠す
- すべての変更はインクリメンタルに行い、個々の変更をリリース可能な状態にする
- 抽象化によるブランチで、大規模な変更をコードベースに加える
- 変更の頻度が異なる部分をコンポーネント化して、アプリケーションから切り離す
4.対応詳細
(1)依存関係の管理
依存関係の管理の観点は以下の通り。
- コンポーネントとライブラリの区別
- ライブラリ：通常めったに更新されない
- コンポーネント：ソフトウェアの部品としてアプリケーションが依存しているもので、自分たち（または同一組織のチーム）が頻繁に更新する。
- ビルド時の依存関係と実行時の依存関係の区別
- ビルド時：アプリケーションをコンパイルし（必要なら）リンクするときにあらわれるもの
- 実行時：アプリケーションを実行して通常の機能を実行するときにあらわれるもの
- 依存地獄
- ライブラリの管理
- ライブラリのバージョン管理の方法と問題
- ビルドの再現性
- 自前の成果物リポジトリ
- 宣言的な依存管理の自作
(2)コンポーネント
コンポーネントの観点は以下の通り。
- コードベースをコンポーネントに分割
- コンポーネントのパイプライン化
- パイプラインの分割が解決する問題
- 並列パイプラインの方法と欠点
- パイプラインの分割が解決する問題
- インテグレーションパイプライン
- 高速フィードバック
- 各パイプラインからの可視性
- 組み合わせたときの問題
(3)依存グラフの管理
依存グラフの管理の観点は以下の通り。
- 依存関係のバージョン管理
- 無閉路有向グラフ
依存グラフの作成
- ひし形依存の問題
- 高速フィードバックのための解決策
- 依存グラフをパイプライン化
- 可視性のための解決策
- コンポーネント分割によるリリースブランチ許容の例外
- ビルドのタイミング
- コンポーネント更新の判断基準
- 新バージョンの統合作業を継続的に行い、素早いフィードバックを得る
- コンポーネント更新の判断基準
- 依存グラフへの状態の追加
- 浅い依存グラフと後方互換性による依存関係の単純化
- 循環依存
(4)バイナリの管理
バイナリの管理の観点は以下の通り。
- 成果物リポジトリ
- 再生成可能なもののみ格納し、削除を可能にする
- ハッシュの保持
- バイナリとソースの紐づけ
- インデックスファイルの追加
(5)Mavenでの依存関係の解決例
Mavenでの依存関係の解決例での観点は以下の通り。
- 依存関係のキャッシュ
- 成果物の保存
- バージョンの指定
- スコープの指定
- 依存関係の重複排除
5.影響・作用
インクリメンタルな変更とメインラインへのチェックイン、またはアプリケーション自体をコンポーネントに分割することで、素早いフィードバックを得られる。
6.おわりに
以上が、継続的デリバリーの中での、コンポーネントや依存関係の管理についての概観です。
7.参考文献
『継続的デリバリー 信頼できるソフトウェアリリースのためのビルド・テスト・デプロイメントの自動化』 第13章 コンポーネントや依存関係を管理する
『継続的デリバリー』 第12章 学習メモ
データ管理の概観
1.はじめに
継続的デリバリーにおける、データ管理についての調査記録です。
継続的デリバリーの中での、データ管理についての概観を記載します。
『継続的デリバリー 信頼できるソフトウェアリリースのためのビルド・テスト・デプロイメントの自動化』の第12章に対応します。
2.概要・目的
データを管理するとき、テストやデプロイメントのプロセスでいくつか問題が生じる。その理由は以下の2点である。
- データの量
- アプリケーションのデータとシステムの他の部分とではライフサイクルが異なる
データの構造や内容を変更する必要がある場合の問題に対応する。
混乱を最小化し、アプリケーションやデプロイメント処理の信頼性を最大化する仕組みのために、DBの移行プロセスを自動化する。
自動化した内容はスクリプトにして自動デプロイメントプロセスに組み込む。
3.対応概要
(1)DBのスクリプト処理
DBのスクリプト処理の観点は以下の通り。
- 初期化スクリプト、初期化の手順
- DBのバージョン管理
(2)データの管理とデプロイメントパイプライン
各テストステージにおけるデータの観点は以下の通り。
- コミットテストステージ
- テストヘルパーやフィクスチャによるデータ作成の再利用
- 受入テストステージ
- データの分類
- テストケース作成の再利用
- データへの依存の最小化
- アプリケーションのAPIの使用の作用
- キャパシティテストステージなど
- 受入テストのインタラクションを記録し、キャパシティテストなど以後のテストに使用する
- 手動テスト
- 空の状態で立ち上げるか、カスタマイズしたデータ群の使用がよい
4.対応詳細
(1)DBのロールバックとゼロダウンタイムリリース
DBのロールバックとゼロダウンタイムリリースの観点は以下の通り。
(2)テストデータ管理
テストデータの管理の観点は以下の通り。
- テストデータ管理の要件・機能
- パフォーマンス
- テストの分離
- ユニットテストにおけるDB
- テストとデータの関連の整理
5.影響・作用
以上の対応により、完全に自動化したプロセスでDBの作成やマイグレーションを行えるようにする。
6.おわりに
以上が、継続的デリバリーの中での、データの管理についての概観です。
7.参考文献
『継続的デリバリー 信頼できるソフトウェアリリースのためのビルド・テスト・デプロイメントの自動化』 第12章 データを管理する
『継続的デリバリー』 第11章 学習メモ
基盤と環境の管理のための概観
1.はじめに
継続的デリバリーにおける、基盤と環境の管理についての調査記録です。
継続的デリバリーの中での、基盤と環境の管理のための概観を記載します。
『継続的デリバリー 信頼できるソフトウェアリリースのためのビルド・テスト・デプロイメントの自動化』の第11章に対応します。
2.概要・目的
目標は、すべてのテスト環境を本番環境と同様の方法で扱うこと。
環境とは、アプリケーションの動作や設定に必要となるすべてのリソースのこと。
環境は、以下の特性を持つものである。
- 環境を構成するサーバのハードウェア構成、およびサーバが接続するネットワーク基盤
- OSやミドルウェアの設定が、アプリケーションの動作のために必要
包括的な手法ですべての基盤を管理するための原則は以下の3点である。
- 基盤に要求される状態は、バージョン管理された設定で指定する
- 基盤は要求された状態に自動的に持ち込む（自動化）
- 基盤の状態を監視する
デプロイのリスクを軽減するために管理すべき項目は以下の通り。
- OSおよびその設定
- MW（ミドルウェア）スタックおよびその設定
- 基盤管理用ソフトウェア
- 外部の統合ポイント
- ネットワーク基盤
- アプリケーション開発チームと基盤管理チームの関係
また、基本原則として、テスト環境は本番環境にできるだけ近づけ、環境の問題を早期発見する。
これにより、あいまいで再現性の低い設定や統合時の問題を早期発見できる。
3.問題・要求
運用上の要求についての観点は以下の通り。
- MTBF,MTTR,SLA
- 文書化と監査
- 異常発生警告
- エラーは1か所にまとめてログを残す。深刻度も記録する
- 監視方法もアプリケーションの機能として扱う
- 業務継続性
- デプロイメントシステムの技術の決定
4.対応概要
基盤のモデリング・管理についての観点は以下の通り。
- 構成情報の準備や管理の自動化
- 自動化しやすい技術の選択。以下は自動化のための観点
- 基盤のプロビジョニング
- 基盤を構成する様々なソフトウェアのデプロイメントや設定
- プロビジョニングや設定を済ませた基盤の管理
- 必要となるマルチユーザアプリケーションの設定
- OS
- ミドルウェア
- DB
- ユーザ
- アプリケーションのデプロイメント
- メッセージの登録
- バージョン管理の対象。デプロイメントパイプラインへの入力
- OSのインストール定義
- データセンター自動化ツール
- 基盤の設定
- 基盤管理のためのスクリプト
- 基盤の変更後のデプロイメントパイプライン
- 依存の規則
- 変更の共有と個別のパイプライン
5.対応詳細
(1)基盤へのアクセス制御
基盤へのアクセス制御の観点は以下の通り。
(2)サーバのプロビジョニングと設定の管理
サーバのプロビジョニングと設定の管理の観点は以下の通り。
- プロビジョニングの手順
- 進行中のサーバ管理
(3)ミドルウェアの構成管理
ミドルウェアの構成管理の観点は以下の通り。
- Webサーバ・メッセージングシステム・商用パッケージソフトウェアなどのミドルウェアは以下の3点で構成される
- バイナリ
- 設定
- データ
- 以下のいずれかの方法で設定を管理
- PuppetやSCCMなどでOSと同様に管理
- OSのパッケージ管理システムでパッケージを作成
- 設定をスクリプトで管理できるミドルウェアを使い、デプロイメントや設定を自動化
- 製品が持つ自動化された設定オプションの調査
- 設定APIの使用
- より良いソリューションを探す
(4)基盤サービスの管理
基盤サービスの管理の観点は以下の通り。
- ネットワーク基盤の設定のバージョン管理
- ネットワーク監視システムの使用
- アプリケーションでのネットワークについてのログの記録
- スモークテスト
- ネットワークトポロジーを本番環境に合わせる
- 問題の調査のためのフォレンジックツール
- マルチホームシステムにおけるNICの分離と管理
(5)仮想化
仮想化の観点は以下の通り。
- 仮想化の作用
- 新しい環境の保守やプロビジョニングの容易さ
- 非機能要件のテストの容易さ
- テストの並列実行
- 仮想環境管理の方法
- データセンター自動化ツールの使用
- 仮想化技術のデプロイメントパイプラインへの適用
- ビルドシステム・リリース管理システムによる仮想マシンテンプレートセットの記録
- ベースラインイメージの保持
- 並列化したテスト
- マルチプラットフォーム対応
- 自動キャパシティテストの高速化
- 仮想ネットワーク
(6)クラウドコンピューティング
クラウドコンピューティングの観点は以下の通り。
- 利点と分類
- クラウド基盤における以下への対応と限界
- セキュリティ
- コンプライアンス
- サービスレベル
- プラットフォームのクラウド化の作用と制約
- クラウドコンピューティングの分析と批判
(7)基盤やアプリケーションの監視
基盤やアプリケーションの監視の観点は以下の通り。
- 以下の項目への作用
- ビジネス
- 運用
- プロジェクト
- 以下の機能が必要となる
- 収集
- 保持
- 可視化
- 通知
- 収集の対象とツール
- ログの出力
- 表示するレベルの設定
- 運用チームのための機能
- 網羅性と可読性
- 可視化
- テストファーストの監視
6.影響・作用・まとめ
コストの分析して戦略を適用することで、アプリケーションを使い続ける間ずっと手動で環境を管理するよりもコストを削減できる。
サードパーティ製品の評価には、自動化した構成管理への適応性を観点とする。
7.おわりに
以上が、継続的デリバリーの中での、コミットステージについての概観です。
8.参考文献
『継続的デリバリー 信頼できるソフトウェアリリースのためのビルド・テスト・デプロイメントの自動化』 第11章 基盤と環境を管理する
