計算困難問題に対するアルゴリズム理論 第二章 担当:森部 議事録:日下部 「数学の基礎」 グラフ理論 グラフはグラフの頂点Vと、辺E(u, v)の集合  二頂点(u, v)の間に辺が存在するかは、隣接行列で表現(ダイクストラの情報源に)  有向グラフ…向きを考慮、uからvへは行けるが、vからuへは行けない、など  重みづけグラフ…辺の間に重みづけ(コスト、所要時間など) ブール値  ブール論理…ブール値、1(真)と0(偽)からなる  乗法∧、加法∨、含意⇒、排他的論理和○+、等価⇔など  ブール関数…1か0を表すa, b, …に対して、1か0を返す関数f(a, b, …)  ブール関数を加法で表す(完全加法標準形)、乗法で表す(完全乗法標準形)  ブール関数のボックス内をネットワークで表す…ブランチングプログラム 「アルゴリズム理論の基礎」 最適化問題…入力、制約、コスト関数、ゴール(コスト関数をどうするか?max, min, ...) 計算量…計算機に左右されないもの O表記法…一番影響を受ける値を計算量として代表させる  f=3*n^2+n+500なら計算量はO(n^2)  ソートで見ると、  バブルソート法…隣り合う要素を比較して、大小の順番が逆であれば、入れ替えるという方法。O(n^2)  ヒープソート法…二分木の構造を使う。全てのノードは下の二つのノードより大きいようにヒープを作る。 ヒープを再構成しながら最大値を更新する。O(nlogn) アルゴリズム設計技法(の中の動的計画法)  対象となる問題を複数の問題に分割し、部分問題の計算結果を記録しながら解いていく  例:最短経路問題  初期コストはc(u, v)…UVがつながっている ∞…つながってない 0…同じ点  UV間において、点kを経由した方がコストを抑えられるとき、コストを更新する 質疑応答(敬称略) 今泉:ブール関数とかブール値って結局どうやって使うのか? 若林:完全乗法によって、引数を節の論理積として表せる。 節だけ考えることで、計算量を抑えるアルゴリズムがある。 (同じく理論輪読会で発表した若林さんの資料を参照) 浦田:非常に基礎的な理論なので、どう使われるか以前の問題では。 柳沼:そもそもアルゴリズムは、イエスかノーを入力してイエスかノーを出力するので、 ブール演算は必要不可欠。また、コンピュータ自体が0か1かで動くので、 コンピュータの作動もブールに還元される。