授業ノート | 極地平面

すべての記事を最小化

すべての記事を展開

拍手みたいなもの

押すことにより、作者に活を入れることができます。

SNS

>Mixi(最近サボリ中)

>Pixiv(少し絵を置いてる)

>デジタルトキワ荘(ROM専)

リンク

問題6 データ構造とアルゴリズム - H20年広島大学工学研究科院試情報専攻専門科目1

(1)あるアルゴリズムが、入力サイズnの問題に対して、最悪時間計算量がO(nlogn)である場合、これが、このアルゴリズムの性能に関して何を表しているかを説明せよ。

(2)n個のデータを昇順でソートしたい。この問題に対する最悪時間計算量O(nlogn)のアルゴリズムを1つ示せ。アルゴリズムの概要がわかる疑似コードや図を使って説明せよ。具体例を挙げて説明したい場合は、例として「8, 2, 3, 5, 7, 1, 9, 6」の8個の整数が入力であると仮定した例でソート手順を説明してもよい。

(3)(2)のアルゴリズムの最悪計算時間がO(nlogn)であることを証明せよ。

プログラムがO(nlogn)の計算時間を要するとは、どのようなデータが与えられても最悪nlognに比例する計算時間で、計算が終了することを意味している。

例えば、要素数が4から8になると、計算時間は24/4=6倍になることになる。

O(nlogn)で終了するソートアルゴリズムには、ヒープソートやマージソート、クイックソートなどが存在する。

ヒープソートは、親が2つの子より小さい値になるように2分探索木を作成してソートする方法である。木を構成するには、配列から一つずつ要素を取り出し、木に追加する。このままでは、探索木にならないので、追加した要素とその親を比較して、追加した要素の方が小さければ交換する。この動作を追加するたび、親の方が小さいか、根に達するまで行えば、定義したような2分探索木ができる。

取り出す際は、根から要素を取り出せばよいが、根を取ると探索木が壊れてしまうため、最後の要素を根として持ってきて、子の小さい方と比べてみて小さければ交換する動作を、子より小さいか、葉に達するまで行う。

こうして、根を取りだして配列の後に追加し、木を再形成することを繰り返せば、ソートされた状態で要素が並ぶことがわかる。

マージソートは、一度配列を最小(要素数1)配列に分割し、そのあと配列を2つずつ全体が1つの配列になるまで結合(マージ)を繰り返す方法である。マージする際、両配列の前から見ていき、小さい方を新しい配列に追加していくことで、新たに作られた配列はソートされた状態になる。

これを例に当てはめてみる。

1.要素数最小の配列を作る。([8],[2],[3],[5],[7],[1],[9],[6])

2.配列を2つずつ上記の方法で結合する。([2,8],[3,5],[1,7],[6,9])

3.配列を2つずつ上記の方法で結合する。([2,3,5,8],[1,6,7,9])

4.配列を2つずつ上記の方法で結合する。([1,2,3,5,6,7,8,9])

5.配列が1つになったので終了。

クイックソートは、しきい値を利用して配列をそれ未満とそれ以上の2つに分け、その2つを同様の方法で分割することを、分割できなくなるまで繰り返す方法である。しきい値を決める方法にはランダムに決定したり、先頭の値を使うなどいろいろな方法があり、計算時間を左右する。

しきい値が決定すると、配列の左側からはしきい値以上の値を探し、右側からはしきい値未満の値を探す。見つかれば、しきい値以上の値と未満の値を交換する。これを両側からの探索がぶつかるまで続け、その位置で配列を分ける。

こうして分けられた配列に対して、同じことを交換する要素が互いに見つからなくなるまで繰り返せばよい。

これを例に当てはめてみる。

1.ここではしきい値は先頭の値とする。([【8】,2,3,5,7,1,9,6])

2.8>=8、6<8より交換。([6,2,3,5,7,1,9,8])

3.1の要素でぶつかるので1を境に分割。([6,2,3,5,7,1],[9,8])

4.同様のことを繰り返せば最終的にソートされた配列が得られる。([1,2,3,5],[6],[7],[8],[9])

(3)(2)のアルゴリズムの最悪計算時間がO(nlogn)であることを証明せよ。

ヒープソートは、要素の値を読み込んで、親との大小を比較する。要素数がnならば、2分探索木なので、ヒープを構成するための計算時間はO(nlogn)である。また、読み込むときも1つ読み込んではヒープを再構成するので、読み込みの計算時間もO(nlogn)である。よって、全体として計算時間はO(nlogn)である。

マージソートでは、2つの配列を結合するのを繰り返す。そのため、結合の回数はlognに比例する。また、結合するときに、順に配列の要素を最大n回読み込むため、全体の計算時間はO(nlogn)である。

クイックソートは、厳密にはO(nlogn)ではない。すべてソートされた状態ではO(n)であるし、要素数1の分割を繰り返すような最悪の入力の場合はO(n*n)である。しかし、配列をほぼ半割できるようなしきい値を選ぶことができれば、配列を分割する回数はlognに比例するようになる。そして、分割位置を決定するために要素を最大n回見るため、全体の計算時間はO(nlogn)となる。

このようにばらつきはあるが、平均的な場合としてO(nlogn)になることが知られている。

科目名 : H20年広島大学工学研究科院試情報専攻専門科目1 | 更新日時 : 2010年08月29日 16時16分46秒

問題4 線形計画法 - H20年広島大学工学研究科院試情報専攻専門科目1

$x_1-3x_2+x_3+3x_4+x_5=8 \\ 2x_1+2x_2+2x_3+6x_4-x_5=16 \\ 3x_1+4x_2+4x_3-9x_4+2x_5=26$

(1) $\blue (x_1, x_2, x_3, x_4, x_5)=(6, 0, 2, 0, 0)$ は、上記の連立1次方程式の一つの解であることを示せ。

与えられた式にそれぞれ代入すると、

6 + 2 = 8

12 + 4 = 16

18 + 8 = 26

よって、 $(x_1, x_2, x_3, x_4, x_5)=(6, 0, 2, 0, 0)$ は解の一つであるといえる。

(2)次の線形問題（LP問題)を解け。

$\blue x_1-3x_2+x_3+3x_4+x_5=8 \\ 2x_1+2x_2+2x_3+6x_4-x_5=16 \\ 3x_1+3x_2+4x_3-9x_4+2x_5=26 \\ x_1, x_2, x_3, x_4, x_5>0$

なる条件の下で、 $\blue f=8x_1+24x_2+16x_3-80x_4+5x_5$ を最大にせよ。

fを最大化するには、-fを最小化すればよい。

ここでは、2段階シンプレックス法を用いる。

	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	定数
$\lambda _1$	1	-3	1	3	1	8
$\lambda _2$	2	2	2	6	-1	16
$\lambda _3$	3	4	[4]	-9	2	26
-f	-8	-24	-16	80	-5	0
-w	-6	-3	-7	0	-2	-50

$\lambda _1$	1/4	-4		[21/4]	1/2	3/2
$\lambda _2$	1/2			21/2	-2	3
$x_3$	3/4	1	1	-9/4	1/2	13/2
-f	4	-8		44	3	104
-w	-3/4	4	0	-63/4	3/2	-9/2

$x_4$	1/21	-16/21		1	-2/21	2/7
$\lambda _2$		[8]			-3	0
$x_3$	6/7	-5/7	1		2/7	50/7
-f	40/21	536/21			151/21	640/7
-w	0	-8	0	0	3	0

$x_4$	1/21			1	-8/21	2/7
$x_2$		1			-3/8	0
$x_3$	6/7		1		1/56	50/7
-f	40/21				352/21	640/7
-w	0	0	0	0	0	0

よって、 $(x_1, x_2, x_3, x_4, x_5)$ =(0, 0, 50/7, 2/7, 0)のとき、fは最大値640/7をとる。

(ちなみに)

この問題は、普通のシンプレックス法では、解くことができない。

理由は、シンプレックス法は原点から、実行可能領域を辿って、最適解を探していく方法であるため、今回の問題のように、原点が実行可能領域に含まれない問題は解けない。

そのため、2段階法によって、まずはスタート地点を決めて、そのあとシンプレックス法によって、最適解を探していく必要がある。

今回は、たまたま実行可能領域が点なので、スタート地点が最適解であったわけだが...

科目名 : H20年広島大学工学研究科院試情報専攻専門科目1 | 更新日時 : 2010年08月29日 16時06分29秒

問題3 確率論 - H20年広島大学工学研究科院試情報専攻専門科目1

確率変数 $N_1$ と $N_2$ が以下の確率関数をもつポアソン分布に従う。

$P(N_1=k)=\frac{\lambda _{1}^{k}}{k!}e^{-\lambda _1}, \lambda _1>0, k=0, 1, 2, ...$

$P(N_2=k)=\frac{\lambda _{2}^{k}}{k!}e^{-\lambda _2}, \lambda _2>0, k=0, 1, 2, ...$

(1)平均 $\blue E[N_1]$ および確率母関数 $\blue E[Z^{N_1}]$ を求めよ。

$E[N_1]=\sum_{k=0}^{\infty}k\frac{\lambda _1^k}{k!}e^{-\lambda _1}$

k=0のとき、 $k\frac{\lambda _1^k}{k!}=0$ より、

$E[N_1]=\sum _{k=0}^\infty k\frac{\lambda _1^k}{k!}e^{-\lambda _1}=\sum _{k=1}^\infty k\frac{\lambda _1^k}{k!}e^{-\lambda _1}=\lambda _1 e^{-\lambda _1} \sum _{k=1}^\infty \frac{\lambda _1^{k-1}}{(k-1)!}$

ここで、テイラー展開より

$e^\lambda = 1+\lambda + \frac{1}{2!}\lambda ^2 + \frac{1}{3!}\lambda ^3 +\cdots = \sum _{k=0}^\infty \frac{\lambda ^k}{k!}=\sum _{k=1}^\infty \frac{\lambda ^{k-1}}{(k-1)!}$

よって、 $E[N_1]=e^{-\lambda _1}\lambda _1 e^{\lambda _1}=\lambda _1 \rule{10}{10}$

$E[z^{N_1}]=\sum _{k=0}^\infty z^k\frac{\lambda _1^k}{k!}e^{-\lambda _1}=e^{-\lambda _1}\sum _{k=0}^\infty \frac{(z\lambda _1)^k}{k!}=e^{-\lambda _1}e^{z\lambda _1}=e^{(z-1)\lambda _1} \rule{10}{10}$

(2)確率関数 $\blue P(N_1+N_2=k)$ を求めよ。

$P(N_1+N_2=k)=\sum _{x=0}^k P(N_1=x)P(N_2=k-x)=\sum _{x=0}^k \frac{\lambda _1^x}{x!}e^{-\lambda _1}\frac{\lambda _2^{k-x}}{(k-x)!}e^{-\lambda _2} \\ =e^{-(\lambda _1+\lambda _2)}\sum _{x=0}^k \frac{\lambda _1^x \lambda _2^{k-x}}{x!(k-x)!}=e^{-(\lambda _1 +\lambda _2)}\sum _{x=0}^k \frac{k!}{x!(k-x)!}\frac{1}{k!}\lambda _1^x \lambda _2^{k-x}$

ここで、二項定理より

$\sum _{x=0}^k \frac{k!}{x!(k-x)!}\lambda _1^x \lambda _2^{k-x} = \sum _{x=0}^k \left( k \\ x \\ \right)\lambda _1^x \lambda _2^{k-x} = (\lambda _1 + \lambda _2)^k$

よって、 $P(N_1+N_2=k)=\frac{(\lambda _1+\lambda _2)^k}{k!} e^{-(\lambda _1+\lambda _2)} \rule{10}{10}$

(3)条件付き確率関数 $\blue P(N_1=k | N_1+N_2=n)$ を求めよ。

$P(N_1=k|N_1+N_2=n)=\frac{P(N_1=k|N_1+N_2=n)}{P(N_1+N_2=n)}=\frac{P(N_1=k)P(N_2=n-k)}{P(N_1+N_2=n)}$

ここで、

$P(N_1=k)=\frac{\lambda _1^k}{k!}e^{-\lambda _1}$

$P(N_2=n-k)=\frac{\lambda _2^{n-k}}{(n-k)!}e^{-\lambda _2}$

$P(N_1+N_2=n)=\frac{(\lambda _1+\lambda _2)^k}{k!}e^{-(\lambda _1+\lambda _2)}$

よって

$P(N_1=k|N_1+N_2=n)=\frac{n!}{k!(n-k)!}\frac{\lambda _1^k \lambda _2^{n-k}}{(\lambda _1+\lambda _2)^n} = \left( n \\ k \\ \right) \left( \frac{\lambda _1}{\lambda _1+\lambda _2} \right)^k \left(\frac{\lambda _2}{\lambda _1+\lambda _2}\right)^{n-k} \rule{10}{10}$

科目名 : H20年広島大学工学研究科院試情報専攻専門科目1 | 更新日時 : 2010年08月29日 15時22分19秒

問題1 線形代数 - H20年広島大学工学研究科院試情報専攻専門科目1

実数aは $a\geq -\frac{5}{4}$ を満たすとする。3次正方行列 $A=\left( \begin{array}{ccc}2&1&1 \\ 1&2&1 \\ a&1&2 \\ \end{array} \right)$ について、次に答えよ。

(1)a=1のとき、 $\blue U^{T}AU=D$ を満たす直行行列Uおよび対角行列Dを求めよ。ただし、 $\blue U^{T}$ はUの転置行列を表す。

$|\lambda E-A|=\left| \begin{array}{ccc} \lambda -2&-1&-1 \\ -1&\lambda -2&-1 \\ -1&-1&\lambda -2 \\ \end{array} \right| = \left| \begin{array}{ccc} \lambda -2&-1&-1 \\ -1&\lambda -2&-1 \\ 0&1-\lambda&\lambda -1 \\ \end{array} \right|$

$=(\lambda -2)(\lambda ^2-3\lambda +2+1-\lambda)-(-1)(1-\lambda +1-\lambda)=(\lambda -2)(\lambda -1)(\lambda -3)-2(\lambda -1) \\ =(\lambda -1)(\lambda ^2-5\lambda +6-2)=(\lambda -1)^2(\lambda -4)$

よって、Aの固有値 $\lambda =1, 4 \rule{10}{10}$

(i) $\lambda =1$ のとき

$\lambda E-A=\left( \begin{array}{ccc} -1&-1&-1 \\ -1&-1&-1 \\ -1&-1&-1 \\ \end{array} \right) \to \left( \begin{array}{ccc} 1&1&1 \\ 0&0&0 \\ 0&0&0 \\ \end{array} \right)$ より、固有ベクトル $v_1=c_1\left( \begin{array}{c} -1 \\ 0 \\ 1 \\ \end{array} \right) +c_2\left( \begin{array}{c} 0 \\ -1 \\ 1 \\ \end{array} \right)$

(ii) $\lambda =4$ のとき

$\lambda E-A=\left( \begin{array}{ccc} 2&-1&-1 \\ -1&2&-1 \\ -1&-1&2 \\ \end{array} \right) \to \left( \begin{array}{ccc} 0&-3&3 \\ 0&3&-3 \\ 1&1&-2 \\ \end{array} \right) \to \left( \begin{array}{ccc} 1&-&-1 \\ 0&1&-1 \\ 0&0&0 \\ \end{array} \right)$ より、固有ベクトル $v_2=c_3\left( \begin{array}{c} 1 \\ 1 \\ 1 \\ \end{array} \right)$

以上より、 $U=\left( \begin{array}{ccc} -1&0&1 \\ 0&-1&1 \\ 1&1&1 \\ \end{array} \right)$ のとき、 $D=U^TAU=\left( \begin{array}{ccc} 1&0&0 \\ 0&1&0 \\ 0&0&4 \\ \end{array} \right) \rule{10}{10}$

(2) $\blue a>-\frac{5}{4}$ のとき、 $\blue P^{-1}AP$ が対角行列となる正規行列Pが存在することを証明せよ。

$|\lambda E-A|=\left| \begin{array}{ccc} \lambda -2&-1&-1 \\ -1&\lambda -2&-1 \\ -1&-1&\lambda -2 \\ \end{array} \right| \\ =(\lambda -2)(\lambda ^2 -4\lambda +4-1)+(2-\lambda -1)+a(1+\lambda -2)=(\lambda -1)(\lambda ^2 -5\lambda +5-a)$

よって、固有値は $\lambda =1, \frac{5\pm \sqrt{5-4a}}{2}$ となる。

$\lambda ^2-5\lambda +5-a$ は $a>-\frac{5}{4}$ のとき、実数解を2つ持つため、そのとき固有値が2~3個存在することになる。

固有値が2個になるのは、 $\frac{5-\sqrt{5-4a}}{2}=1$ のときであるが、(1)よりそのときも正規行列Pが存在する。

次に、3つの異なる固有値を持つ場合であるが、

このとき、固有空間 $dimV(1)+dimV(\frac{5+\sqrt{5-4a}}{2})+dimV(\frac{5-\sqrt{5-4a}}{2})=1+1+1=3$ となるため、対角化可能である。

よって、 $a>-\frac{5}{4}$ ならば、 $P^{-1}AP$ が対角行列となるような正規行列Pが存在する。

(3) $\blue a=-\frac{5}{4}$ のとき、 $\blue Q^{-1}AQ$ が対角行列となる正規行列Qが存在しないことを証明せよ。

(2)より、 $a=-\frac{5}{4}$ のとき、固有値 $\lambda =1, \frac{5}{2}$ となる。

(i) $\lambda =1$ のとき

$\lambda E-A=\left( \begin{array}{ccc} -1&-1&-1 \\ -1&-1&-1 \\ -5/4&-1&-1 \\ \end{array} \right) \to \left( \begin{array}{ccc} 1&0&0 \\ 0&1&1 \\ 0&0&0 \\ \end{array} \right)$

(ii) $\lambda =\frac{5}{2}$ のとき

$\lambda E-A=\left( \begin{array}{ccc} 1/2&-1&-1 \\ -1&1/2&-1 \\ -5/4&-1&1/2 \\ \end{array} \right) \to \left( \begin{array}{ccc} 1&-2&-2 \\ -2&1&-2 \\ -5&-4&2 \\ \end{array} \right) \to \left( \begin{array}{ccc} 1&-2&-2 \\ 0&1&2 \\ 0&7&4 \\ \end{array} \right)$