院試過去問 2002年度専門科目数理のバックアップ(No.8) - PukiWiki

[ トップ ] [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ] [ リンク元 ]

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
院試過去問 2002年度専門科目数理へ行く。
- 1 (2008-08-10 (日) 00:37:49)
- 2 (2008-08-10 (日) 03:28:04)
- 3 (2008-08-10 (日) 06:52:29)
- 4 (2008-08-10 (日) 19:20:46)
- 5 (2008-08-11 (月) 15:58:06)
- 6 (2008-08-11 (月) 23:36:38)
- 7 (2008-08-12 (火) 03:30:09)
- 8 (2008-08-14 (木) 03:24:34)
- 9 (2008-08-14 (木) 11:49:37)

院試勉強会

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

第一問 †

を互いに独立な上の一様乱数とする。
に対し、
に対し、と定義する。
- (1)の確率密度関数と期待値を求めよ。
  - 累積分布は、 $0\leq z\leq 1$ に対して、
    $F(z) = P[Z_c < z] = P\left[\left(X \geq c \wedge X < z\right)\vee (X < c \wedge Y < z)\right] = \max(z-c,0) + cz$ なので、
    確率密度は $f(z)=F'(z)=\left\{\begin{matrix}1+c,&(\mathrm{for}\ z>c)\\c&(\mathrm{else})\end{matrix}\right.$
    期待値は、 $E[Z_c]=\int_c^1 z(1+c)dz+\int_0^c zcdz = \frac{1+c-c^2}{2}$
- (2)を最大にするの値、と、を求めよ。
  - $\frac{d}{dc}E[Z_c] = \frac{1-2c}{2}$ 、
    $c^* = \frac{1}{2}$
    $E[Z_{c^*}]=\frac{5}{8}$
- (3)任意のに対して、となることを示せ。
  - が可測であることは仮定しておく。
    $P[Z_A<z]=|A\cap [0,z]|+z(1-|A|)$
    微分不可能な点が高々可算個なら、その点を除外して積分すれば
    $E[Z_A]=\int_0^1 z\frac{d}{dz}P[Z_A<z]dz=1-\int_0^1 P[Z_A<z]dz = \frac{1+|A|}{2} - \int_0^1 |A\cap [0,z]|dz$
    式の形から、 $|A|$ が同じなら集合の要素を右によせたほうがの値が大きくなりそうなので、
    $\tilde{A}=[|A|,1]$ と置いて、 $E[Z_{\tilde{A}}]-E[Z_A] \geq 0$ を示す。
    $\begin{align*}E[Z_{\tilde{A}}]-E[Z_A] &= \int_0^1 |A\cap [0,z]|dz - \int_0^1 \max (|A|-z,0)dz\\ &= \int_0^1 |A\cap [0,z]|dz-\frac{|A|^2}{2}\\ &\geq \frac{|A|^2}{2}-\frac{|A|^2}{2} \\ &= 0\end{align*}$
    ここで、 $|A\cap [0,1]| = |A|$ 、 $|A\cap [0,z]| \geq |A|+(z-1)$ を使った。
    の形のときにが最大になるのはのときなので、
    $E[Z_{c^*}] \geq E[Z_{\tilde{A}}] \geq E[Z_A]$
    が可算個の区間の和集合として書けないときでも、
    可測でさえあれば可算個の区間でを覆って
    を評価して極限をとれば $E[Z_A] = \frac{1+|A|}{2} - \int_0^1 |A\cap [0,z]|dz$ がきっと出てくるはず。
    可測ですらないときには手のつけようがない。

第二問 †

凸錐について、
- (1)の形状はどのようなものか答えよ。
  - 円錐。軸との角度は45度で、軸正の方向にのびている。原点含む。
- (2)任意のベクトルについて、
  を示せ。
  - 対偶、 $x\in S_n \iff \forall y\in S_n. x^\top y \geq 0$ を示す。
    $\forall (x_0,x),(y_0,y)\in S_n$ について、
    $(x_0,x)^\top (y_0,y) = x_0 y_0 + x^\top y \geq |x||y|+x^\top y \geq 0$ なので、
    $\Rightarrow$ は成立。
    ある $(x_0,x)\in\mathbb{R}^{1+n}$ について、
    $\forall (y_0,y)\in S_n. (x_0,x)^\top (y_0,y) = x_0 y_0 + x^\top y \geq 0$ が成立するとき、
    と選べば、 $x_0\geq 0$
    と選べば、 $x_0 |x| - |x|^2 \geq 0$ が得られるので、
    $x_0 \geq |x|$ が成立し、 $(x_0,x)\in S_n$ 。
    これで与式は示された。
- (3)に対して、
  についての凸2次計画
  のKKT条件を書け。
  - $\lambda\in\mathbb{R}^m,\ \lambda\geq 0$
    $\left\{\frac{\partial}{\partial z_\mu}\left(|z|^2 - \lambda^\top (Az-b)\right)\right\}_{z=\bar{z}}=2\bar{z}^\top - \lambda^\top A =0$
    $\lambda^\top (A\bar{z}-b)=0$
- (4)について、
  を仮定する。
  を使って、を示せ。
  - (2)を使う。
    $\forall (r,x)\in X_r$ に対して、
    存在が仮定された $y\geq 0,\ y^\top b>r|A^\top y|$ を満たすを使えば、
    $y^\top A x \geq y^\top b>r|A^\top y|,\ |A^\top y|r+(-y^\top A)x < 0$ が成立。
    $(|A^\top y|,-y^\top A)\in S_n$ は(2)の条件を満たしているので、
    $(r,x)\notin S_n$ となり、 $S_n \cap X_r = \emptyset$
    ベクトルのタテヨコの食い違いは気にしちゃいけません。
- (5)とする。
  を示せ。
  - は空でない閉集合なので、十分大きなに対して
    $\tilde{X}_r = \{x\in X_r | |x|\leq R\}$ と置けば有界閉。
    連続関数 $x\in \tilde{X}_r \mapsto \frac{1}{2}|x|^2$ には最小値が存在する。
    この最小値は定義域を $\tilde{X}_r$ に狭めなくても最小値になっている。最小値を与える $\bar{x}\in X_r$ にはKKT条件が成立しているので、
    $y\geq 0$
    $\PDiff{}{x}\left\{\frac{1}{2}|x|^2-y^\top (Ax-b)\right\}=x^\top - y^\top A = 0$
    $y^\top (Ax-b)=0$ を満たすが存在する。
    
    一方、 $S_n\cap X_r =\emptyset$ ならば、 $\forall (r,x)\in X_r.$ について
    $(r,x)\notin S_n$ つまりが成立する。
    これを使うと、上のは
    $r|A^\top y|=r|x|<|x|^2=(y^\top A)x \leq y^\top b$ から、
    目的の条件を満たしている。

第三問 †

以下の等式を証明せよ。
- 確率的に解いてみる。あんまり厳密じゃないかも。
  $X_i,\ i=1,2,\cdots$ をの独立な一様乱数、
  $Z_n = \frac{1}{n}\sum_{i=1}^n X_i$ とすると、
  $\int_0^1\cdots\int_0^1\frac{n}{\sum_{k=1}^n x_k}dx_1\cdots dx_n = E\left[\frac{1}{Z_n}\right]$ と書ける。
  の分布は中心極限定理から、平均 $\frac{1}{2}$ 、分散 $\frac{1}{12n}$ の正規分布に近づくので、
  $E\left[\frac{1}{Z_n}\right] \to \int_{-\infty}^{\infty}\frac{1}{z_n}\sqrt{\frac{12n}{2\pi}}\exp\left(-\frac{12n}{2}\left(z_n-\frac{1}{2}\right)^2\right)dz_n\ (n\to\infty)$
  正規分布の分散を0に飛ばす極限はδ関数の分布になるので、
  さらに $E\left[\frac{1}{Z_n}\right] \to \int_{-\infty}^{\infty}\frac{1}{z}\delta\left(z-\frac{1}{2}\right)dz \to 2$
  これで与式が示された気分になれる。

第4問 †

半径の円柱の側面に沿って，水平面との角度をもち，幅がの滑り台を作りたい．
- (1)の座標をを用いて表せ．
  - $\begin{align*}(x,y,z)=\left(R\cos\left(\frac{s\cos\alpha}{R}\right),R\sin\left(\frac{s\cos\alpha}{R}\right),s\sin\alpha\right)\end{align*}$
- (2)曲線の曲率半径を求めよ．
  - $\frac{1}{R'}=\sqrt{\left(\frac{d^2x}{dt^2}\right)^2+\left(\frac{d^2y}{dt^2}\right)^2+\left(\frac{d^2z}{dz^2}\right)^2}$ なので，
    $\begin{align*}\frac{1}{R'}=\sqrt{\frac{\cos^2\alpha}{R^2}\cos^2\left(\frac{s\cos\alpha}{R}\right)+\frac{\cos^2\alpha}{R^2}\sin^2\left(\frac{s\cos\alpha}{R}\right)+0}=\frac{\cos^2\alpha}{R}.\end{align*}$
    よって， $R'=\frac{R}{\cos^2\alpha}$
- (3)線分上でから距離だけ離れた点をとする．がに沿って距離だけ動いたとき, が動く距離を求めよ．
  - $t=\sqrt{(s\sin\alpha)^2+\left(s\cos\alpha\frac{R+u}{R}\right)}$ ．
- (4)Pが内側の円弧状を延長だけ動くとき，が動く距離を求めよ．
  - $t'=s\frac{R'+u}{R'}$ ．
- (5)からだけ外側へ離れた点での鉄板の厚みと点における鉄板の厚みとの比を求めよ．

第5問 †

初期状態が空であるスタックを用いて数字列を置換することを考える．「スタックに，先頭の数字を入れる．」と「スタックから一つ取り出して印字する．」の二つの操作があり，それぞれの操作をとで表す．
(1)数字列1234からスタックを用いて置換できる数字列を全て列挙せよ．
- 1,2,3,4,12,13,14,23,24,34,123,124,132,134,142,143,234,243, 1234,1243,1324,1432,2134,2314,2341,2431,3214,3241,3421,4321の13通り．
(2)数字列12..nを数字列に，スタックを用いて置換できるための必要十分条件は，を満たす添え字が存在しないことであることを証明せよ．
- Sを開き括弧(，Xを閉じ括弧)と書くことにすると，操作列は正しい括弧の対応のとれたこの括弧として表せる．また出力される数字は個目の閉じ括弧に対応する開き括弧が何番目の開き括弧であるのかということになる．
  ここでを満たすが存在しないということは括弧の対応がとれていることを意味するので，これは必要十分条件となっている．
(3)
- (i)操作列を数字列12..nに作用させて出力される数字列を求める問題．
  - 単にシミュレートするだけ．時間計算量は，空間計算量は．プログラムはH14_MMI_5_1.java．サンプルインプットはinput1.txt．
- (ii)数字列12..nをに置換する操作列を生成する問題．
  - 次に出力するべき数字がスタックの一番上ならば出力，そうでなければプッシュすればよい．時間計算量は，空間計算量は．プログラムはH14_MMI_5_2.java．サンプルインプットはinput2.txt．

てか，プログラムを書けってどういうこと？

コメント