院試過去問 2005年度専門科目数理のバックアップ(No.10)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
院試過去問 2005年度専門科目数理へ行く。
- 1 (2008-08-10 (日) 12:03:22)
- 2 (2008-08-10 (日) 13:05:39)
- 3 (2008-08-10 (日) 19:03:54)
- 4 (2008-08-11 (月) 18:44:19)
- 5 (2008-08-11 (月) 22:37:19)
- 6 (2008-08-12 (火) 20:55:40)
- 7 (2008-08-13 (水) 01:20:43)
- 8 (2008-08-13 (水) 12:34:54)
- 9 (2008-08-23 (土) 23:46:08)
- 10 (2008-08-24 (日) 17:29:10)
- 11 (2010-02-26 (金) 00:04:14)

院試勉強会

http://www.i.u-tokyo.ac.jp/edu/course/mi/admission.shtml
http://www.i.u-tokyo.ac.jp/edu/course/mi/pdf/2005suuri-j.pdf

第1問
時間の関数に関する微分方程式
を考える．ただし，は正の定数とする．
- (1)方程式(*)が，次の二つの保存量を持つことを示せ．
  - 微分して0になることを示せばよい．
    $\begin{align*}\frac{dL}{dt}&=2\left(y_1\frac{dy_1}{dt}+y_2\frac{dy_2}{dt}+y_3\frac{dy_3}{dt}\right)\\&=2\left(\frac{y_1y_3}{I_3}-\frac{y_1y_2}{I_2}-\frac{y_2y_3}{I_3}+\frac{y_2y_1}{I_1}+\frac{y_3y_2}{I_2}-\frac{y_3y_1}{I_1}\right)=0\end{align*}$
    $\begin{align*}\frac{dK}{dt}&=\frac{y_1}{I_1}\frac{dy_1}{dt}+\frac{y_2}{I_2}\frac{dy_2}{dt}+\frac{y_3}{I_3}\frac{dy_3}{dt}\\&=\frac{y_1y_3}{I_1I_3}-\frac{y_1y_2}{I_1I_2}-\frac{y_2y_3}{I_2I_3}+\frac{y_2y_1}{I_2I_1}+\frac{y_3y_2}{I_3I_2}-\frac{y_3y_1}{I_3I_1}=0\end{align*}$
- 一般に，時間の関数 $\bm{z}=(z_1,z_2,\dots,z_m)^{\top}$ に関する微分方程式
  $\begin{align*}\frac{d\bm{z}}{dt}=\bm{f}(\bm{z})\tag{**}\end{align*}$
  に対して，差分方程式
  $\begin{align*}\frac{\bm{z}^{(n+1)-\bm{z}^{(n)}}}{h}=\bm{f}\left(\frac{\bm{z}^{(n+1)+\bm{z}^{(n)}}}{2}\right)\end{align*}$
  を陰的中点則による離散化方程式という．ここで，は時間の離散化幅を表し， $\bm{z}^{(n)}$ は $\bm{z}(nh)$ の近似である．
- (2)方程式(*)を陰的中点則で離散化した方程式においても， (1)のが保存量であることを示せ．
  - (3)より明らか.
- (3)方程式(**)において2次形式（ただし，は対称行列）が保存量であるとき，陰的中点則による離散化方程式においても，が保存量であることを示せ．
  - $\bm{z}^{\top}C\bm{z}$ が保存量であるので，
    $\begin{align*}\frac{d}{dt}(\bm{z}^{\top}C\bm{z})=2\bm{z}^{\top}Cf(\bm{z}).\end{align*}$
    $\bm{z}$ に $\frac{\bm{z}^{(n+1)}+\bm{z}^{(n)}}{2}$ を代入して，
    $2\frac{\bm{z}^{(n+1)}+\bm{z}^{(n)}}{2}C\bm{f}\left(\frac{\bm{z}^{(n+1)}+\bm{z}^{(n)}}{2}\right)=(\bm{z}^{(n+1)}+\bm{z}^{(n)})C\left(\frac{\bm{z}^{(n+1)}-\bm{z}^{(n)}}{h}\right)=0$
    これを，倍して展開すれば，は対称行列なので，
    $(\bm{z}^{(n+1)})^{\top}C z^{(n+1)}=(\bm{z}^{(n)})^{\top}C z^{(n)}.$

第2問
平面からへの滑らかな写像を以下のように表す．

を満たすを不動点という．また，不動点における写像の固有値の絶対値がすべて1より小さいとき漸近安定，そうでないとき不安定であるという．
- (1)ヤコビ行列の行列式を横軸，トレースを縦軸とする平面において,不動点が漸近安定である領域を図示せよ．
  - 簡単のため行列式を，トレースをと書くことにする．すると，固有値 $\lambda$ は $f(\lambda)=\lambda^2-t \lambda+d=0$ を満たす．
    判別式 $t^2-4d\ge 0$ のとき， $-1<t/2<1,\ f(1)> 0,\ f(-1)> 0$ ．
    判別式のとき， $|\lambda_1|=|\lambda_2|,\ |d|=|\lambda_1\lambda_2|=|\lambda|< 1$ ．
    よって，の三角形の内部が求める領域．
- (2)であるとき，写像をエノン写像という．エノン写像の不動点を求めよ．また，求めた不動点の安定性とパラメータの値とtの関係を調べて，その結果をを横軸，縦軸とするパラメータ平面上に図示せよ．
  - 不動点は，
    $\begin{align*}\bar{x}&=-a\bar{x}^2+\bar{y}+1\\\bar{y}&=b\bar{x}\end{align*}$
    を満たすので，これを解いて
    $\begin{align*}\bar{x}&=\frac{b-1\pm\sqrt{(1-b)^2+4a}}{2a},\\\bar{y}&=b\frac{b-1\pm\sqrt{(1-b)^2+4a}}{2a}.\end{align*}$
    $\begin{align*}J=\begin{pmatrix}-2a\bar{x}&1\\b&0\end{pmatrix}\end{align*}$
    これより，
    $\begin{align*}\mathrm{tr} J&=-2a\bar{x}=1-b\pm\sqrt{(1-b)^2+4a}\\\det J&=-b\end{align*}$
    これが，(1)で求めた三角形の領域に入れば良い．とおくと， , $b'> |b'\pm\sqrt{b'^2+4a}|=\pm b'+\sqrt{b'^2+4a}$ ．
    不動点は実なので $b'^2+4a\ge 0$
    複号が＋のときは， $0>\sqrt{b'^2+4a}$ となり漸近安定領域はない．
    －のときは， $2b'>\sqrt{b'^2+4a},\ 3(1-b)^2>4a$ ．
    これと $a,b\ne 0$ を条件とすればよい.
- (3)エノン写像を，非線型写像，線型写像，および線型写像の合成によって
  
  と表すとき，を具体的に求めよ．また，であるとき，長方形領域がが順次変換された領域を図示するとともに，その面積を求めよ．
  - $\begin{align*}\begin{pmatrix}-ax^2+y+1\\ bx\end{pmatrix}&=\begin{pmatrix}0&1\\1&0\end{pmatrix}\begin{pmatrix}b&0\\0&1\end{pmatrix}T_1\begin{pmatrix}x\\y\end{pmatrix}\\&=\begin{pmatrix}0&1\\ b&0\end{pmatrix}T_1\begin{pmatrix}x\\y\end{pmatrix}\end{align*}$
    より，
    $\begin{align*}T_1\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}x\\-ax^2+y+1\end{pmatrix}.\end{align*}$
    これより，は $\begin{align*}\left\{\left.\begin{pmatrix}x\\-1.4x^2+y+1\end{pmatrix}\right|-1\le x\le 1,\ -0.1\le y\le 0.1\right\}\end{align*}$ なので，面積は $(1-(-1))\times(0.1-(-0.1))=0.4$ ．
    は軸方向に倍したものなので，面積は $0.4\times 0.3=0.12$ ．
    は軸軸を入れ替えたものなので，面積は．
- (4)エノン写像がからの上への1対1写像であることを示せ．
  - 逆写像は $\begin{align*}\begin{pmatrix}x/b\\ay^2/b^2-1+x\end{pmatrix}\end{align*}$ であり，どちらも全域で定義されていることは明らかなので，1対1社増となっている．

第3問
ある物体の重さを測定する実験を2回行って得られる観測値をとし，その標本平均をとする．測定の誤差は独立に平均0，分散1の正規分布に従うものとする．
- (1)とおく．ととの同時確率分布を求めよ．
  - 確率密度関数をそれぞれ $f_{X_1},f_{X_2},f_{\bar{X}},f_Y$ などとおくことにすると，
    $\begin{align*}f_{X_1}(x)&=\frac{1}{\sqrt{2\pi}}e^{-(x-\mu)^2/2}\\f_{X_2}(x)&=\frac{1}{\sqrt{2\pi}}e^{-(x-\mu)^2/2}\\f_{X_1X_2}(x_1,x_2)&=\frac{1}{2\pi}e^{-((x_1-\mu)^2+(x_2-\mu)^2)/2}\end{align*}$
    これを $\bar{X},Y$ に変数変換すると，
    $\begin{align*}f_{\bar{X}Y}(\bar{x},y)&=\frac{1}{2\pi}e^{-((\bar{x}+y-\mu)^2+(\bar{x}-y-\mu)^2)/2}\cdot 2\\&=\frac{1}{\pi}e^{-(\bar{x}-\mu)^2-y^2}\\f_{\bar{X}}&=\frac{1}{\sqrt{\pi}}e^{-(\bar{x}-\mu)^2}\\f_{Y}&=\frac{1}{\sqrt{\pi}}e^{-y^2}\end{align*}$
- (2)標本平均が与えられたもとでのの条件付期待値を求めよ．また，の期待値と分散を求めよ．
  - $\begin{align*}f_{X_1|\bar{X}}(x_1,\bar{x})&=\frac{f_{X_1\bar{X}}(x_1,\bar{x})}{f_{\bar{X}}(\bar{x})}\\&=\frac{f_{\bar{X}Y}(\bar{x},x_1-\bar{x})}{f_{\bar{X}}(\bar{x})}\\&=\frac{f_{\bar{X}}(\bar{x})f_{Y}(x_1-\bar{x})}{f_{\bar{X}}(\bar{x})}\\&=f_{Y}(x_1-\bar{x})\\&=\frac{1}{\sqrt{\pi}}e^{-(x_1-\bar{x})^2}\end{align*}$
    これより， $E[X_1|\bar{X}]=\bar{x}$ ．
    また， $f_{\bar{X}}(\bar{x})=\frac{1}{\sqrt{\pi}}e^{-(\bar{x}-\mu)^2}$ なので，平均 $\mu$ 分散である．
- (3)の関数を考える．が与えられたもとでのの条件付期待値はに依存しないの関数であることを示せ．
  - $E[f(X_1,X_2)|\bar{X}]=\int_{-\infty}^{\infty}f(\bar{x}+y,\bar{x}-y)f_Y(y)dy$ と書けるので， $\mu$ に依存しない $\bar{X}$ の関数である．
- (4)がの不偏推定量であるとき，はの不偏推定量となることを示せ．また，の分散はの分散以下であることを示せ．
  - が $\mu$ の不偏推定量であるので，
    $\begin{align*}\int_{-\infty}^{\infty}f(x_1,x_2)\frac{1}{2\pi}e^{-((x_1-\mu)^2+(x_2-\mu)^2)/2}dx_1dx_2=\mu.\end{align*}$
    よって，
    $\begin{align*}E[E[f(X_1,X_2)|\bar{X}]]&=E[\int_{-\infty}^{\infty}f(\bar{x}+y,\bar{x}-y)\frac{1}{\sqrt{\pi}}e^{-y^2}dy]\\&=\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}f(\bar{x}+y,\bar{x}-y)\frac{1}{\sqrt{\pi}}e^{-y^2}\frac{1}{\sqrt{\pi}}e^{-(\bar{x}-\mu)^2}d\bar{x}dy\\&=\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}f(x_1,x_2)\frac{1}{2\pi}e^{-(x-\mu)^2-(x_2-\mu)^2}dx_1dx_2=\mu.\end{align*}$
    上と同様の議論によりがなりたつので（繰り返しの公式），
    $\newcommand{\Var}{\mathrm{Var}}\begin{align*}\Var[f(X_1,X_2)]-\Var[E[f(X_1,X_2)|\bar{X}]]&=(E[f^2(X_1,X_2)]^2-\mu^2)-(E[E[f(X_1,X_2)|\bar{X}]^2]-\mu^2)\\&=E[E[f^2(X_1,X_2)|\bar{X}]^2]-E[E[f(X_1,X_2)|\bar{X})]^2]\\&=E[E[f^2(X_1,X_2)|\bar{X}]^2-E[f(X_1,X_2)|\bar{X}]^2]\\&=E[\Var[f(X_1,X_2)|\bar{X}]]\ge 0.\end{align*}$
- (5)十分統計量とはどのような概念か，また，どのような性質をもつか，を簡単に説明せよ．
  - 十分統計量とは，パラメータ $\theta$ を持つモデルに対し，その統計量を与えたときの条件付確率分布が $\theta$ によらないことを言う．
    （なに書けばいいのかわかりません）

第4問
個の次元ベクトルと，その添え字の集合の部分集合に対して

と定義する．ただし，はの転置を表し，はに含まれない要素の集合を表す．
- としたとき，の部分集合でが非空となるものを全て書き出せ．
  - 全ての場合通りを考える．
    $\begin{align*}C(K)&\ni \begin{pmatrix}-1\\-2\end{pmatrix}&C(\emptyset)\ni\begin{pmatrix}1\\2\end{pmatrix}\\C(\{1\})&\ni\begin{pmatrix}-1\\2\end{pmatrix}&C(\{2,3\})&\ni\begin{pmatrix}1\\-2\end{pmatrix}\\C(\{3\})&\ni\begin{pmatrix}1\\0\end{pmatrix}&C(\{1,2\})&\ni\begin{pmatrix}-1\\0\end{pmatrix}\end{align*}$
    ところが， $C(\{2\}),C(\{1,3\})$ については，
    $\begin{align*}x_1&\lessgtr 0\tag{1}\\x_1+x_2&\gtrless 0\tag{2}\\-x_1+x_2&\lessgtr 0\tag{3}\end{align*}$
    であるが， $2\times \mathrm{(1)}+\mathrm{(3)}$ より， $x_1+x_2\lessgtr 0$ なので(2)と矛盾するのでは空となる．
- (2) とする．が非空となるの個数をと書きを動かしたときのその最大値をとする．の値を求めよ．また，をの関数として表せ．
  - $\bm{a}_i^{\top}\bm{x}\gtrless 0$ は原点を通る平面で空間を切った半分を表すので，は原点を通る枚の平面で空間を分割したときの空間の数の最大値になる．
    よって，1枚増えるごとに空間の増え方が2増えるので， $r_1=2,\ r_2=4,\ r_3=8,\ r_4=14,\ r_5=22.$
    $r_k=r_{k-1}+2(k-1)=\dots =r_1+\sum_{i=1}^{k-1}2i=2+2\frac{k(k-1)}{2}=k^2-k+2.$
- (3)任意のに対してが非空であるならば，は線型独立であることを示せ．
  - 背理法で示す． $\bm{a}_1,\bm{a}_2,\dots,\bm{a}_k$ が線型独立ではないとする．すると一般性を失わず，あるが存在して， $a_k=\sum_{i=1}^{k-1}w_ia_i$ と表せたとしてよい．すると， $\bm{x}^{\top}\bm{a}_k=\sum_{i=1}^{k-1}w_i \bm{x}\bm{a}_i$ となる．ここで， $w_i\ge 0$ ならば $\bm{a}_i\not\in　L$ ，ならば $\bm{a}_i\in L$ とし， $\bm{a}_k\not\in L$ とすれば右辺は正，左辺は負となり任意のが非空であることに矛盾．よって題意は示された．
- が線型独立であるならば，任意のに対してが非空であることを示せ．
  - $\{\bm{x}\bm{a}_1,\bm{x}\bm{a}_2,\dots,\bm{x}\bm{a}_k\}$ の値を任意に変えることができるので明らか．

c.f. http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%82%A2%E3%83%AC%E3%83%B3%E3%82%B8%E3%83%A1%E3%83%B3%E3%83%88

第5問
とを正整数とし，はに比べて十分小さいとする．を個のシンボルの集合とする．大きさの1次元配列のそれぞれの要素には， 1つのシンボルが格納されている．配列の中には個のシンボルが全て現れ，さらに同じシンボルはその全てが連続して現れる．このとき，全ての変化位置個を求める時間複雑度より小さいアルゴリズムを構成し，そのアルゴリズムの振る舞いと正しさを説明するとともに，その時間複雑度を評価せよ．
- 少々無駄があるが，要請を満たす説明のしやすいアルゴリズムを採用する．
- のシンボルを調べ，そのシンボルの切れ目をバイナリサーチで探索する．この時間計算量は $O(\log n)$ である．
  ここで， $a[k_{m-1}]\ne a[n],\ a[k_{m-1}+1]=a[n]$ だとすると，の0から $k_{m-1}$ までの配列に対して同様の操作をすればよい．
  これを回繰り返すので，時間複雑度は $O(m\log n)$ である．
- それぞれのシンボルの探索を同時にやるようにすれば $O(m\log(n/m))$ になると思うが時間計算量の見積もりが難しい．

1-1 どちらもy1y2y3のになるはずです…これくらいあとから読む人でも分かるでしょ -- tako? 2008-08-23 (土) 23:46:08
4-(2)ですが、nの値は関係ないのでしょうか？関係ある気がするんですが…例えばn=1でaiが+,+,-の数だった時、L={1,2}かL={3}しかないですよね。おおすじは間違っているように見えないので、もうちょっと何か考えないといけない気がします。 -- tako? 2008-08-24 (日) 15:53:57
m log(n/m)もm(log n - log m)でm log nにはならない？同時にやったり、過去に探索した結果を使えば、もちろん有意にはやいですけど。 -- tako? 2008-08-24 (日) 16:24:52
4-(2)はn=3なので3次元の平面分割になってます．5は $O(m\log(n/m))=O((1-\alpha)m\log n)$ なので...オーダーは一緒でしたね． -- yambi? 2008-08-24 (日) 17:28:14

院試過去問 2005年度 専門科目 数理 のバックアップ(No.10)

院試過去問 2005年度専門科目数理のバックアップ(No.10)