院試過去問 2008年度 専門科目 数理
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
] [
リンク元
]
開始行:
[[院試勉強会]]
http://www.i.u-tokyo.ac.jp/edu/course/mi/admission.shtml~
http://www.i.u-tokyo.ac.jp/edu/course/mi/pdf/2008suuri-j....
**第一問 [#df49e074]
Krylov subspace~
&imgtex(\(A\in\mathbb{C}^{n\times n},b\in\mathbb{C}^n\));...
&imgtex(\(\{b,Ab,\cdots,A^{k-1}b\}\));の張る部分空間を&im...
-- (1)&imgtex(\(W_k \subseteq W_{k+1}\));を示せ。
--- 自明…~
&imgtex(\[\forall v=\sum_{i=0}^{k-1}a_{i}A^{i}b \in W_k\]...
&imgtex(\(a_k=0\));ととれば、&imgtex(\[v=\sum_{i=0}^{k}a_...
-- (2)&imgtex(\(W_k=W_{k+1}\Rightarrow W_{k+1}=W_{k+2}\))...
--- &imgtex(\(A^{k}b\in W_k \Rightarrow A^{k+1}b\in W_{k+...
&imgtex(\(A^{k}b\in W_k\));ならば、ある&imgtex(\[\{a_i\}_...
&imgtex(\[A^{k}b=\sum_{i=0}^{k-1}a_{i}A^{i}b\]);が成立。~
よって&imgtex(\[A^{k+1}b=\sum_{i=1}^{k}a_{i-1}A^{i}b \in ...
-- (3)&imgtex(\(d_{k+1}-d_k \geq d_{k+2}-d_{k+1}\));を示...
--- 自明…？~
&imgtex(\(A^{k}b\in W_k\));のとき、&imgtex(\(W_k=W_{k+1}=...
そうでないとき、&imgtex(\(W_{k+1}\));は&imgtex(\(W_k\));...
&imgtex(\(d_{k+1}-d_{k}=1\));、右辺も同様に高々1なので、...
-- (4)任意の&imgtex(\(\lambda\));に対して、&imgtex(\(W_k(...
--- 帰納法を使う。~
まず、&imgtex(\(W_1(A-\lambda I,b)=W_1(A,b)\));は成立して...
&imgtex(\(W_k(A-\lambda I,b)=W_k(A,b)\));が成立しているな...
&imgtex(\(A^{k-1}b\in W_{k}(A-\lambda I,b)\));~
&imgtex(\((A-\lambda I)A^{k-1}b\in W_{k+1}(A-\lambda I,b)...
&imgtex(\(A^{k}b = (A-\lambda I)A^{k-1}b+\lambda A^{k-1}b...
ついでに&imgtex(\((A-\lambda I)^{k}b\));は&imgtex(\(A^{i}...
&imgtex(\((A-\lambda I)^{k}b\in W_{k+1}(A-\lambda I,b)\));~
よって&imgtex(\(W_{k+1}(A-\lambda I,b)=W_{k+1}(A,b)\));が...
以上から、帰納的に任意の&imgtex(\(k\));について、&imgtex(...
。
-- (5)&imgtex(\[A=\begin{pmatrix}\alpha&1&0\\0&\alpha&1\\...
&imgtex(\(d_3=3\));となるための&imgtex(\(\alpha,b\));の必...
--- (4)を使うと、対角に定数を足す分だけ調整できるので、&i...
さらに、一般性を失なうことなく&imgtex(\(\alpha=0\));とし...
&imgtex(\(\{b,Ab,A^2b\}\));が線型独立ならば&imgtex(\(d_3=...
&imgtex(\begin{align*}|b\ Ab\ A^2b|=\left|\begin{matrix}b...
が非ゼロであればよい．
よって，&imgtex(\(b_3\ne 0\));が&imgtex($d_3=3$);となる必...
-- (6)&imgtex(\[A=\begin{pmatrix}\alpha&1&0&0&0\\0&\alpha...
&imgtex(\(d_5=5\));となるための&imgtex(\(\alpha,\beta,b\)...
--- (4)より，&imgtex(\[A=\begin{pmatrix}0&1&0&0&0\\0&0&1&...
と変形できる。~
&imgtex(\(\det\left(b,Ab,A^{2}b,A^{3}b,A^{4}b\right)\neq ...
&imgtex(\(\tilde{A}=\begin{pmatrix}\beta-\alpha&1\\0&\bet...
&imgtex(\(\det\begin{pmatrix}b_1&b_2&b_3&&\\b_2&b_3&0&&\\...
よって、&imgtex(\(b_{3}b_{5}(\alpha-\beta)\neq 0\));が必...
**第二問 [#accc1ca0]
力学系l~
&imgtex(\[\frac{d}{dt}\begin{pmatrix}p(t)\\q(t)\\r(t)\end...
について、
&imgtex(\(p(0),q(0),r(0)>0\));かつ&imgtex(\(p(0)+q(0)+r(0...
-- &imgtex(\(p(t)+q(t)+r(t)=1\));、&imgtex(\(p(t)q(t)r(t)...
&imgtex(\(0<p(t),q(t),r(t)<1\));を示せ。
--- &imgtex(\[\frac{d}{dt}\left(p(t)+q(t)+r(t)\right)=0\]...
&imgtex(\[\frac{d}{dt}\left(p(t)q(t)r(t)\right)=0\]);とな...
&imgtex(\[p(0)+q(0)+r(0)=1\]);なので、&imgtex(\[p(t)+q(t)...
&imgtex(\[p(t)q(t)r(t)\neq 0\]);だから&imgtex(\(p,q,r\));...
&imgtex(\[p(t),q(t),r(t)\]);は連続で、初期値は正だから任...
また、&imgtex(\[p(t)=1-q(t)-r(t)<1\]);も成立。
-- (2)&imgtex(\(\dot{p}(t)>0\));となるための&imgtex(\((p,...
&imgtex(\(\dot{q}(t)>0\));となるための&imgtex(\((p,q)\));...
--- &imgtex(\(\dot{p}=p(q-r)=p(2q+p-1)>0 \iff q > \frac{1...
&imgtex(\(\dot{q}=q(r-p)=q(1-2p-q)>0 \iff q < 1-2p\));
--- 実際には&imgtex($p>0, q>0, p+q<1$);の領域でもなければ...
-- (3) 不動点を求めよ．また，浮動点でないときの運動の概形...
--- 不動点は&imgtex($\dot{p}=\dot{q}=\dot{r}=0$);のときな...
--- 図は不動点の周りを&imgtex($p>0, q>0, p+q<1$);を満たし...
&ref(名称未設定.png);
-- Euler法で&imgtex(\[\frac{1}{h}\begin{pmatrix}p_{n+1}-p...
-- (4) &imgtex($h$);を十分小さくとれば，いかなる初期値に...
--- &imgtex(\begin{align*}p_{n+1}+q_{n+1}+r_{n+1}=p_n+q_n...
帰納法で証明する．~
&imgtex($n=0$);での成立は(1)で述べた通りである．~
&imgtex($n+1$);のとき，(**)より&imgtex($|q_n-r_n|\le 1-p_...
&imgtex(\begin{align*}p_{n+1}&=p_n+hp_n(q_n-r_n)\\&\ge p_...
である．これより，&imgtex($h\le 1$);であれば，&imgtex($p_...
同様にして，&imgtex($q_{n+1},r_{n+1}>0$);である．
ここで，&imgtex($p_{n+1}+q_{n+1}+r_{n+1}=1$);なので，
&imgtex($0<p_{n+1},q_{n+1},r_{n+1}<1$);．~
よって，数学的帰納法により題意は示せれた．
--(5) 初期値が定常解でないとき，刻み幅&imgtex($h$);を十分...
&imgtex($I_n=I(p_n,q_n,r_n)$);は&imgtex($n$);に関して狭義...
---&imgtex($a=h(q_n-r_n), b=h(r_n-p_n)$);とし，&imgtex($h...
このとき，&imgtex($|a+b|<1$);であることに注意すると，~
&imgtex(\begin{align*}I_{n+1}&=I_n(1+a)(1+b)(1-a-b)\\&=I_...
よって，&imgtex($I_n$);は狭義単調減少．
---&imgtex($I_n$);は狭義単調減少であるから，(3)の閉曲線を...
**第3問 [#nda8a6d8]
Markov Chain~
&imgtex($Q^{(n)}(j,k)=P(X(n)=k| X(0)=j)$);~
&imgtex($f^{(n)}(j,k)=P(X(n)=k|X(0)=j)*\prod_{1\le l< n}P...
&imgtex($\bar{Q}_{jk}(z)=\sum_{n=1}^{\infty} Q^{(n)}(j,k)...
&imgtex($\bar{f}_{jk}(z)=\sum_{n=0}^{\infty}f^{(n)}(j,k)z...
と定義する．
--(1) &imgtex($\bar{Q}_{jk}=\delta_{jk}+\bar{f}_{jk}(z) ...
--- &imgtex($n=0$);のとき，&imgtex($Q^{(0)}(j,k)=\delta_{...
&imgtex($n>0$);のとき，&imgtex($Q^{(n)}(j,k)=\sum_{s=0}^n...
&imgtex(\begin{align*}\bar{Q}_{jk}(z)&=\sum_{n=0}^{\infty...
--(2) 状態&imgtex($j$);が再帰的であるとき，&imgtex($\bar{...
---&imgtex($\bar{f}_{jj}(1)=\sum_{n=0}^{\infty}f^{(n)}(j,...
有限ステップで状態&imgtex($j$);に戻ってくる確率を表してい...
よって，&imgtex($\bar{f}_{jj}(1)=1$);であることが，状態&i...
--(3) 条件~
&imgtex(\[\sum_{n=0}^{\infty}Q^{(n)}(j,j)=\infty\]);~
は状態&imgtex($j$);が再帰的であるための必要十分条件である...
--- &imgtex($\sum_{n=0}^{\infty}Q^{(n)}(j,j)=\bar{Q}_{jj}...
また(1)より，&imgtex($(1-\bar{f}_{jj}(1))\bar{Q}_{jj}(1)=...
これより，&imgtex($\bar{Q}_{jj}(1)=\infty$);であることが&...
--(4)&imgtex(\begin{align*}Q^{(1)}(j,k)&=\begin{cases}p&(...
で定義される1次元ランダムウォークを考える．このとき，&img...
--- &imgtex(\begin{align*}Q^{(2n)}(0,0)&= {2n \choose n}p...
であるから，~
&imgtex(\begin{align*}\bar{Q}_{00}(z)&=\sum_{n=0}^{\infty...
--- &imgtex(\begin{align*}Q^{(2n+1)}(1,0)&= {2n+1 \choose...
よって，~
&imgtex(\begin{align*}\bar{Q}_{10}(z)&=\sum_{n=0}^{\infty...
---&imgtex($\bar{Q}_{10}(z)=\bar{f}_{10}\bar{Q}_{00}(z)$)...
&imgtex(\begin{align*}\bar{f}_{10}(z)=\frac{\bar{Q}_{10}(...
(カタラン数を使えば直接求めることができるはず...)
-- 各頂点が次数&imgtex($d$);の木グラフにおけるランダムウ...
各頂点から隣合う頂点に等確率で移動するとするとき，枝数で...
---確率&imgtex($1/d$);で1離れ，&imgtex($(1-d)/d$);で1近づ...
--(5)の&imgtex($X(n):n=0,1,2,\dots$);について&imgtex($\ba...
状態&imgtex($0\in S$);が再帰的でないことを示せ．
--- &imgtex($\bar{f}_{00}(z)$);は(4)の意味での&imgtex($\b...
よって，&imgtex($\bar{f}_{00}(1)=\frac{1}{2p}\left(1-\sqr...
**第四問 [#o2f75002]
空間図形~
時刻&imgtex($t_1$);に日本のある場所から空を見上げたら，遠...
その視点における北極星とPの臨み角は&imgtex($\alpha$);であ...
同じ夜の&imgtex($t_1+t_2$);に同じ場所からもう一度空を見上...
星Aと頂Pの臨み角は&imgtex($\beta$);で，一方，人工衛星Bは...
さらに時刻&imgtex($t_1+2t_2$);でも，人工衛星BはPと同じ位...
人工衛星Bは地球の自転軸と&imgtex($\theta$);をなす平面を角...
--(1)経過時間&imgtex($t_2$);を求めよ．
---&imgtex($\alpha=0$);であったり，明るい星Aが月や太陽や...
天動説を採用し，北極星を中心にAが&imgtex($\phi$);回転した...
これより，地球と北極星の距離を&imgtex($r$);とすると，
&imgtex($2r\tan\alpha\sin(\phi/2)=2r\sec\alpha\sin(\beta/...
すなわち，&imgtex($\phi=2\arcsin\left(\frac{\sin(\beta/2)...
よって，&imgtex($t_2=\arcsin\left(\frac{\sin(\beta/2)}{\s...
--(2)人工衛星Bの大円軌道に関して考え得る&imgtex($(\theta,...
---山の頂を眺める視線は地球の自転と共に地軸に対して回転対...
人工衛星は地球の中心から等距離を飛ぶので，この図形と地球...
このような3点を通る円はC以外には存在しないので，人工衛星...
ここで，Cの中心が地球の中心に一致するためには&imgtex($\th...
&imgtex($\omega=2\pi\left(\frac{1}{t_2}\pm t_2\right) (\t...
ただし例外として~
&imgtex($\beta=0, \omega=\infty, \theta=\frac{\pi}{2}-\al...
&imgtex($\alpha=0, \beta=0, \omega=\text{any}, \theta=\fr...
がある．
**第五問 [#j49a8fd1]
無向2部グラフ&imgtex(\(G=(V^+\cup V^-,E)\));について、~
最大マッチングを考える。
-- (1)以下のアルゴリズムが必ずしも最大マッチングを与えな...
例を挙げて示せ。~
&imgtex(\begin{align*}&M:=\emptyset\\&\mathrm{forall}\ e ...
--- &imgtex(\(V^+=\{0,1\},\ V^-=\{2,3\},\ E=\{\{1,2\},\{0...
&imgtex(\(\{1,2\},\{0,2\},\{1,3\}\));の順に枝が選ばれたら...
得られるマッチングは&imgtex(\(\{\{1,2\}\}\));であり、最大...
--(2) &imgtex($M_1,M_2$);を&imgtex(G);の2つのマッチングと...
&imgtex($M_1$);と&imgtex($M_2$);の対称差&imgtex($M_1\bigt...
---どの頂点からも高々2本の枝がでているので，いくつかの互...
--(3) &imgtex($M_1$);を&imgtex($G$);のマッチング，
&imgtex($M_2$);を&imgtex($G$);の最大マッチングとする．
このとき，(2)で定義された&imgtex($G'$);を用いて，
&imgtex($M_1$);が最大であるための必要十分条件を書け．
---&imgtex($G'$);に現れる全てのパスが偶数長であることであ...
なぜならば，もし奇数長のパスが存在すればそれを用いてマッ...
--(4)&imgtex($G$);のマッチング&imgtex($M_1$);に属する枝を...
&imgtex($M_1$);に属さない枝を&imgtex($V^+$);側から&imgtex...
この&imgtex($\vec{G}$);を用い，&imgtex($M_1$);が最大マッ...
---&imgtex($M_1\bigtriangleup(M_1\bigtriangleup M_2)=M_2$...
&imgtex($M_1\bigtriangleup M_2$);は互いに素なパスの集合で...
&imgtex($M$);が最大マッチングであるなら始点と終点が&imgte...
逆に最大マッチングでないならあるパスが存在して始点と終点...
よって，始点と終点が&imgtex($M$);でカバーされていないよう...
--(5) (4)の結果を利用して，最大マッチングを求めるアルゴリ...
---&imgtex($M=\emptyset$);とする．~
(4)のグラフを作り始点と終点が&imgtex($M$);でカバーされて...
マッチングの数は&imgtex($min(|V^+|,|V^-|)$);で抑えられる...
----
とりあえず完成しました．~
誤植や計算間違い，誤植，誤植などがありましたら修正お願い...
~
- 2-(2)微修正 -- [[tako]] &new{2008-08-22 (金) 18:47:01};
//#comment
終了行:
[[院試勉強会]]
http://www.i.u-tokyo.ac.jp/edu/course/mi/admission.shtml~
http://www.i.u-tokyo.ac.jp/edu/course/mi/pdf/2008suuri-j....
**第一問 [#df49e074]
Krylov subspace~
&imgtex(\(A\in\mathbb{C}^{n\times n},b\in\mathbb{C}^n\));...
&imgtex(\(\{b,Ab,\cdots,A^{k-1}b\}\));の張る部分空間を&im...
-- (1)&imgtex(\(W_k \subseteq W_{k+1}\));を示せ。
--- 自明…~
&imgtex(\[\forall v=\sum_{i=0}^{k-1}a_{i}A^{i}b \in W_k\]...
&imgtex(\(a_k=0\));ととれば、&imgtex(\[v=\sum_{i=0}^{k}a_...
-- (2)&imgtex(\(W_k=W_{k+1}\Rightarrow W_{k+1}=W_{k+2}\))...
--- &imgtex(\(A^{k}b\in W_k \Rightarrow A^{k+1}b\in W_{k+...
&imgtex(\(A^{k}b\in W_k\));ならば、ある&imgtex(\[\{a_i\}_...
&imgtex(\[A^{k}b=\sum_{i=0}^{k-1}a_{i}A^{i}b\]);が成立。~
よって&imgtex(\[A^{k+1}b=\sum_{i=1}^{k}a_{i-1}A^{i}b \in ...
-- (3)&imgtex(\(d_{k+1}-d_k \geq d_{k+2}-d_{k+1}\));を示...
--- 自明…？~
&imgtex(\(A^{k}b\in W_k\));のとき、&imgtex(\(W_k=W_{k+1}=...
そうでないとき、&imgtex(\(W_{k+1}\));は&imgtex(\(W_k\));...
&imgtex(\(d_{k+1}-d_{k}=1\));、右辺も同様に高々1なので、...
-- (4)任意の&imgtex(\(\lambda\));に対して、&imgtex(\(W_k(...
--- 帰納法を使う。~
まず、&imgtex(\(W_1(A-\lambda I,b)=W_1(A,b)\));は成立して...
&imgtex(\(W_k(A-\lambda I,b)=W_k(A,b)\));が成立しているな...
&imgtex(\(A^{k-1}b\in W_{k}(A-\lambda I,b)\));~
&imgtex(\((A-\lambda I)A^{k-1}b\in W_{k+1}(A-\lambda I,b)...
&imgtex(\(A^{k}b = (A-\lambda I)A^{k-1}b+\lambda A^{k-1}b...
ついでに&imgtex(\((A-\lambda I)^{k}b\));は&imgtex(\(A^{i}...
&imgtex(\((A-\lambda I)^{k}b\in W_{k+1}(A-\lambda I,b)\));~
よって&imgtex(\(W_{k+1}(A-\lambda I,b)=W_{k+1}(A,b)\));が...
以上から、帰納的に任意の&imgtex(\(k\));について、&imgtex(...
。
-- (5)&imgtex(\[A=\begin{pmatrix}\alpha&1&0\\0&\alpha&1\\...
&imgtex(\(d_3=3\));となるための&imgtex(\(\alpha,b\));の必...
--- (4)を使うと、対角に定数を足す分だけ調整できるので、&i...
さらに、一般性を失なうことなく&imgtex(\(\alpha=0\));とし...
&imgtex(\(\{b,Ab,A^2b\}\));が線型独立ならば&imgtex(\(d_3=...
&imgtex(\begin{align*}|b\ Ab\ A^2b|=\left|\begin{matrix}b...
が非ゼロであればよい．
よって，&imgtex(\(b_3\ne 0\));が&imgtex($d_3=3$);となる必...
-- (6)&imgtex(\[A=\begin{pmatrix}\alpha&1&0&0&0\\0&\alpha...
&imgtex(\(d_5=5\));となるための&imgtex(\(\alpha,\beta,b\)...
--- (4)より，&imgtex(\[A=\begin{pmatrix}0&1&0&0&0\\0&0&1&...
と変形できる。~
&imgtex(\(\det\left(b,Ab,A^{2}b,A^{3}b,A^{4}b\right)\neq ...
&imgtex(\(\tilde{A}=\begin{pmatrix}\beta-\alpha&1\\0&\bet...
&imgtex(\(\det\begin{pmatrix}b_1&b_2&b_3&&\\b_2&b_3&0&&\\...
よって、&imgtex(\(b_{3}b_{5}(\alpha-\beta)\neq 0\));が必...
**第二問 [#accc1ca0]
力学系l~
&imgtex(\[\frac{d}{dt}\begin{pmatrix}p(t)\\q(t)\\r(t)\end...
について、
&imgtex(\(p(0),q(0),r(0)>0\));かつ&imgtex(\(p(0)+q(0)+r(0...
-- &imgtex(\(p(t)+q(t)+r(t)=1\));、&imgtex(\(p(t)q(t)r(t)...
&imgtex(\(0<p(t),q(t),r(t)<1\));を示せ。
--- &imgtex(\[\frac{d}{dt}\left(p(t)+q(t)+r(t)\right)=0\]...
&imgtex(\[\frac{d}{dt}\left(p(t)q(t)r(t)\right)=0\]);とな...
&imgtex(\[p(0)+q(0)+r(0)=1\]);なので、&imgtex(\[p(t)+q(t)...
&imgtex(\[p(t)q(t)r(t)\neq 0\]);だから&imgtex(\(p,q,r\));...
&imgtex(\[p(t),q(t),r(t)\]);は連続で、初期値は正だから任...
また、&imgtex(\[p(t)=1-q(t)-r(t)<1\]);も成立。
-- (2)&imgtex(\(\dot{p}(t)>0\));となるための&imgtex(\((p,...
&imgtex(\(\dot{q}(t)>0\));となるための&imgtex(\((p,q)\));...
--- &imgtex(\(\dot{p}=p(q-r)=p(2q+p-1)>0 \iff q > \frac{1...
&imgtex(\(\dot{q}=q(r-p)=q(1-2p-q)>0 \iff q < 1-2p\));
--- 実際には&imgtex($p>0, q>0, p+q<1$);の領域でもなければ...
-- (3) 不動点を求めよ．また，浮動点でないときの運動の概形...
--- 不動点は&imgtex($\dot{p}=\dot{q}=\dot{r}=0$);のときな...
--- 図は不動点の周りを&imgtex($p>0, q>0, p+q<1$);を満たし...
&ref(名称未設定.png);
-- Euler法で&imgtex(\[\frac{1}{h}\begin{pmatrix}p_{n+1}-p...
-- (4) &imgtex($h$);を十分小さくとれば，いかなる初期値に...
--- &imgtex(\begin{align*}p_{n+1}+q_{n+1}+r_{n+1}=p_n+q_n...
帰納法で証明する．~
&imgtex($n=0$);での成立は(1)で述べた通りである．~
&imgtex($n+1$);のとき，(**)より&imgtex($|q_n-r_n|\le 1-p_...
&imgtex(\begin{align*}p_{n+1}&=p_n+hp_n(q_n-r_n)\\&\ge p_...
である．これより，&imgtex($h\le 1$);であれば，&imgtex($p_...
同様にして，&imgtex($q_{n+1},r_{n+1}>0$);である．
ここで，&imgtex($p_{n+1}+q_{n+1}+r_{n+1}=1$);なので，
&imgtex($0<p_{n+1},q_{n+1},r_{n+1}<1$);．~
よって，数学的帰納法により題意は示せれた．
--(5) 初期値が定常解でないとき，刻み幅&imgtex($h$);を十分...
&imgtex($I_n=I(p_n,q_n,r_n)$);は&imgtex($n$);に関して狭義...
---&imgtex($a=h(q_n-r_n), b=h(r_n-p_n)$);とし，&imgtex($h...
このとき，&imgtex($|a+b|<1$);であることに注意すると，~
&imgtex(\begin{align*}I_{n+1}&=I_n(1+a)(1+b)(1-a-b)\\&=I_...
よって，&imgtex($I_n$);は狭義単調減少．
---&imgtex($I_n$);は狭義単調減少であるから，(3)の閉曲線を...
**第3問 [#nda8a6d8]
Markov Chain~
&imgtex($Q^{(n)}(j,k)=P(X(n)=k| X(0)=j)$);~
&imgtex($f^{(n)}(j,k)=P(X(n)=k|X(0)=j)*\prod_{1\le l< n}P...
&imgtex($\bar{Q}_{jk}(z)=\sum_{n=1}^{\infty} Q^{(n)}(j,k)...
&imgtex($\bar{f}_{jk}(z)=\sum_{n=0}^{\infty}f^{(n)}(j,k)z...
と定義する．
--(1) &imgtex($\bar{Q}_{jk}=\delta_{jk}+\bar{f}_{jk}(z) ...
--- &imgtex($n=0$);のとき，&imgtex($Q^{(0)}(j,k)=\delta_{...
&imgtex($n>0$);のとき，&imgtex($Q^{(n)}(j,k)=\sum_{s=0}^n...
&imgtex(\begin{align*}\bar{Q}_{jk}(z)&=\sum_{n=0}^{\infty...
--(2) 状態&imgtex($j$);が再帰的であるとき，&imgtex($\bar{...
---&imgtex($\bar{f}_{jj}(1)=\sum_{n=0}^{\infty}f^{(n)}(j,...
有限ステップで状態&imgtex($j$);に戻ってくる確率を表してい...
よって，&imgtex($\bar{f}_{jj}(1)=1$);であることが，状態&i...
--(3) 条件~
&imgtex(\[\sum_{n=0}^{\infty}Q^{(n)}(j,j)=\infty\]);~
は状態&imgtex($j$);が再帰的であるための必要十分条件である...
--- &imgtex($\sum_{n=0}^{\infty}Q^{(n)}(j,j)=\bar{Q}_{jj}...
また(1)より，&imgtex($(1-\bar{f}_{jj}(1))\bar{Q}_{jj}(1)=...
これより，&imgtex($\bar{Q}_{jj}(1)=\infty$);であることが&...
--(4)&imgtex(\begin{align*}Q^{(1)}(j,k)&=\begin{cases}p&(...
で定義される1次元ランダムウォークを考える．このとき，&img...
--- &imgtex(\begin{align*}Q^{(2n)}(0,0)&= {2n \choose n}p...
であるから，~
&imgtex(\begin{align*}\bar{Q}_{00}(z)&=\sum_{n=0}^{\infty...
--- &imgtex(\begin{align*}Q^{(2n+1)}(1,0)&= {2n+1 \choose...
よって，~
&imgtex(\begin{align*}\bar{Q}_{10}(z)&=\sum_{n=0}^{\infty...
---&imgtex($\bar{Q}_{10}(z)=\bar{f}_{10}\bar{Q}_{00}(z)$)...
&imgtex(\begin{align*}\bar{f}_{10}(z)=\frac{\bar{Q}_{10}(...
(カタラン数を使えば直接求めることができるはず...)
-- 各頂点が次数&imgtex($d$);の木グラフにおけるランダムウ...
各頂点から隣合う頂点に等確率で移動するとするとき，枝数で...
---確率&imgtex($1/d$);で1離れ，&imgtex($(1-d)/d$);で1近づ...
--(5)の&imgtex($X(n):n=0,1,2,\dots$);について&imgtex($\ba...
状態&imgtex($0\in S$);が再帰的でないことを示せ．
--- &imgtex($\bar{f}_{00}(z)$);は(4)の意味での&imgtex($\b...
よって，&imgtex($\bar{f}_{00}(1)=\frac{1}{2p}\left(1-\sqr...
**第四問 [#o2f75002]
空間図形~
時刻&imgtex($t_1$);に日本のある場所から空を見上げたら，遠...
その視点における北極星とPの臨み角は&imgtex($\alpha$);であ...
同じ夜の&imgtex($t_1+t_2$);に同じ場所からもう一度空を見上...
星Aと頂Pの臨み角は&imgtex($\beta$);で，一方，人工衛星Bは...
さらに時刻&imgtex($t_1+2t_2$);でも，人工衛星BはPと同じ位...
人工衛星Bは地球の自転軸と&imgtex($\theta$);をなす平面を角...
--(1)経過時間&imgtex($t_2$);を求めよ．
---&imgtex($\alpha=0$);であったり，明るい星Aが月や太陽や...
天動説を採用し，北極星を中心にAが&imgtex($\phi$);回転した...
これより，地球と北極星の距離を&imgtex($r$);とすると，
&imgtex($2r\tan\alpha\sin(\phi/2)=2r\sec\alpha\sin(\beta/...
すなわち，&imgtex($\phi=2\arcsin\left(\frac{\sin(\beta/2)...
よって，&imgtex($t_2=\arcsin\left(\frac{\sin(\beta/2)}{\s...
--(2)人工衛星Bの大円軌道に関して考え得る&imgtex($(\theta,...
---山の頂を眺める視線は地球の自転と共に地軸に対して回転対...
人工衛星は地球の中心から等距離を飛ぶので，この図形と地球...
このような3点を通る円はC以外には存在しないので，人工衛星...
ここで，Cの中心が地球の中心に一致するためには&imgtex($\th...
&imgtex($\omega=2\pi\left(\frac{1}{t_2}\pm t_2\right) (\t...
ただし例外として~
&imgtex($\beta=0, \omega=\infty, \theta=\frac{\pi}{2}-\al...
&imgtex($\alpha=0, \beta=0, \omega=\text{any}, \theta=\fr...
がある．
**第五問 [#j49a8fd1]
無向2部グラフ&imgtex(\(G=(V^+\cup V^-,E)\));について、~
最大マッチングを考える。
-- (1)以下のアルゴリズムが必ずしも最大マッチングを与えな...
例を挙げて示せ。~
&imgtex(\begin{align*}&M:=\emptyset\\&\mathrm{forall}\ e ...
--- &imgtex(\(V^+=\{0,1\},\ V^-=\{2,3\},\ E=\{\{1,2\},\{0...
&imgtex(\(\{1,2\},\{0,2\},\{1,3\}\));の順に枝が選ばれたら...
得られるマッチングは&imgtex(\(\{\{1,2\}\}\));であり、最大...
--(2) &imgtex($M_1,M_2$);を&imgtex(G);の2つのマッチングと...
&imgtex($M_1$);と&imgtex($M_2$);の対称差&imgtex($M_1\bigt...
---どの頂点からも高々2本の枝がでているので，いくつかの互...
--(3) &imgtex($M_1$);を&imgtex($G$);のマッチング，
&imgtex($M_2$);を&imgtex($G$);の最大マッチングとする．
このとき，(2)で定義された&imgtex($G'$);を用いて，
&imgtex($M_1$);が最大であるための必要十分条件を書け．
---&imgtex($G'$);に現れる全てのパスが偶数長であることであ...
なぜならば，もし奇数長のパスが存在すればそれを用いてマッ...
--(4)&imgtex($G$);のマッチング&imgtex($M_1$);に属する枝を...
&imgtex($M_1$);に属さない枝を&imgtex($V^+$);側から&imgtex...
この&imgtex($\vec{G}$);を用い，&imgtex($M_1$);が最大マッ...
---&imgtex($M_1\bigtriangleup(M_1\bigtriangleup M_2)=M_2$...
&imgtex($M_1\bigtriangleup M_2$);は互いに素なパスの集合で...
&imgtex($M$);が最大マッチングであるなら始点と終点が&imgte...
逆に最大マッチングでないならあるパスが存在して始点と終点...
よって，始点と終点が&imgtex($M$);でカバーされていないよう...
--(5) (4)の結果を利用して，最大マッチングを求めるアルゴリ...
---&imgtex($M=\emptyset$);とする．~
(4)のグラフを作り始点と終点が&imgtex($M$);でカバーされて...
マッチングの数は&imgtex($min(|V^+|,|V^-|)$);で抑えられる...
----
とりあえず完成しました．~
誤植や計算間違い，誤植，誤植などがありましたら修正お願い...
~
- 2-(2)微修正 -- [[tako]] &new{2008-08-22 (金) 18:47:01};
//#comment
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
