[[院試勉強会]]

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

**第一問 [#rf8606ca]
-&imgtex(\(X,Y\));を互いに独立な&imgtex(\([0,1]\));上の一様乱数とする。~
&imgtex(\(0<c<1\));に対し、&imgtex(\[Z_c = \left\{\begin{matrix}X,&(\mathrm{for}\ X\geq c)\\Y,& (\mathrm{else})\end{matrix}\right.\]);~
&imgtex(\(A\subseteq [0,1]\));に対し、&imgtex(\[Z_A = \left\{\begin{matrix}X,&(\mathrm{for}\ X\in A)\\Y,& (\mathrm{else})\end{matrix}\right.\]);と定義する。
-- (1)&imgtex(\(Z_c\));の確率密度関数と期待値を求めよ。
--- 累積分布は、&imgtex(\(0\leq z\leq 1\));に対して、~
&imgtex(\[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\]);なので、~
確率密度は&imgtex(\(f(z)=F'(z)=\left\{\begin{matrix}1+c,&(\mathrm{for}\ z>c)\\c&(\mathrm{else})\end{matrix}\right.\));~
期待値は、&imgtex(\[E[Z_c]=\int_c^1 z(1+c)dz+\int_0^c zcdz = \frac{1+c-c^2}{2}\]);
-- (2)&imgtex(\[E[Z_c]\]);を最大にする&imgtex(\(c\));の値、&imgtex(\(c^*\));と、&imgtex(\[E[Z_{c^*}]\]);を求めよ。
--- &imgtex(\[\frac{d}{dc}E[Z_c] = \frac{1-2c}{2}\]);、~
&imgtex(\[c^* = \frac{1}{2}\]);~
&imgtex(\[E[Z_{c^*}]=\frac{5}{8}\]);~
-- (3)任意の&imgtex(\[A\]);に対して、&imgtex(\[E[Z_{c^*}]\geq E[Z_A]\]);となることを示せ。
--- &imgtex(\[A\]);が可測であることは仮定しておく。~
&imgtex(\[P[Z_A<z]=|A\cap [0,z]|+z(1-|A|)\]);~
微分不可能な点が高々可算個なら、その点を除外して積分すれば~
&imgtex(\[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\]);~
式の形から、&imgtex(\(|A|\));が同じなら集合の要素を右によせたほうが&imgtex(\[E[Z_A]\]);の値が大きくなりそうなので、~
&imgtex(\[\tilde{A}=[|A|,1]\]);と置いて、&imgtex(\[E[Z_{\tilde{A}}]-E[Z_A] \geq 0\]);を示す。~
&imgtex(\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*});~
ここで、&imgtex(\[|A\cap [0,1]| = |A|\]);、&imgtex(\[|A\cap [0,z]| \geq |A|+(z-1)\]);を使った。~
&imgtex(\[A=[c,1]\]);の形のときに&imgtex(\[E[Z_A]\]);が最大になるのは&imgtex(\[c=c^*\]);のときなので、~
&imgtex(\[E[Z_{c^*}] \geq E[Z_{\tilde{A}}] \geq E[Z_A]\]);~
&imgtex(\[A\]);が可算個の区間の和集合として書けないときでも、~
可測でさえあれば可算個の区間で&imgtex(\[A,[0,1]-A\]);を覆って~
&imgtex(\[E[Z_A]\]);を評価して極限をとれば&imgtex(\[E[Z_A] = \frac{1+|A|}{2} - \int_0^1 |A\cap [0,z]|dz\]);がきっと出てくるはず。~
可測ですらないときには手のつけようがない。
** 第二問 [#z5485f6d]
-凸錐&imgtex(\[S_n=\left\{(x_0,x)\in\mathbb{R}^{1+n}|\ x_0 \geq |x|\right\}\]);について、~
-- (1)&imgtex(\[S_2\]);の形状はどのようなものか答えよ。
--- 円錐。軸との角度は45度で、&imgtex(\[x_0\]);軸正の方向にのびている。原点含む。
-- (2)任意のベクトル&imgtex(\[x\in\mathbb{R}^{n+1}\]);について、~
&imgtex(\[x\notin S_n \iff \exists y\in S_n. x^\top y<0\]);を示せ。
--- 対偶、&imgtex(\[x\in S_n \iff \forall y\in S_n. x^\top y \geq 0\]);を示す。~
&imgtex(\[\forall (x_0,x),(y_0,y)\in S_n\]);について、~
&imgtex(\[(x_0,x)^\top (y_0,y) = x_0 y_0 + x^\top y \geq |x||y|+x^\top y \geq 0\]);なので、~
&imgtex(\[\Rightarrow\]);は成立。~
ある&imgtex(\[(x_0,x)\in\mathbb{R}^{1+n}\]);について、~
&imgtex(\[\forall (y_0,y)\in S_n. (x_0,x)^\top (y_0,y) = x_0 y_0 + x^\top y \geq 0\]);が成立するとき、~
&imgtex(\[y_0>0,y=0\]);と選べば、&imgtex(\[x_0\geq 0\]);~
&imgtex(\[y_0 = |x|,y=-x\]);と選べば、&imgtex(\[x_0 |x| - |x|^2 \geq 0\]);が得られるので、~
&imgtex(\[x_0 \geq |x|\]);が成立し、&imgtex(\[(x_0,x)\in S_n\]);。~
これで与式は示された。
-- (3)&imgtex(\[A\in\mathbb{R}^{m\times n},b\in\mathbb{R}^m\]);に対して、~
&imgtex(\[z\in\mathbb{R}^n\]);についての凸2次計画~
&imgtex(\[\min.\ |z|^2\ s.t.\ Az\geq b\]);のKKT条件を書け。
--- &imgtex(\[\lambda\in\mathbb{R}^m,\ \lambda\geq 0\]);~
&imgtex(\[\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\]);~
&imgtex(\[\lambda^\top (A\bar{z}-b)=0\]);~
-- (4)&imgtex(\[X_r=\{(x_0,x)\in\mathbb{R}^{1+n}|Ax\geq b,x_0=r\}\]);について、~
&imgtex(\[\exists y\geq 0.\ y^\top b > r|A^\top y|\]);を仮定する。~
&imgtex(\[(|A^\top y|,-y^\top A)\in S_n\]);を使って、&imgtex(\[S_n \cap X_r = \emptyset\]);を示せ。
--- (2)を使う。~
&imgtex(\[\forall (r,x)\in X_r\]);に対して、~
存在が仮定された&imgtex(\[y\geq 0,\ y^\top b>r|A^\top y|\]);を満たす&imgtex(\[y\]);を使えば、~
&imgtex(\[y^\top A x \geq y^\top b>r|A^\top y|,\ |A^\top y|r+(-y^\top A)x < 0\]);が成立。~
&imgtex(\[(|A^\top y|,-y^\top A)\in S_n\]);は(2)の条件を満たしているので、~
&imgtex(\[(r,x)\notin S_n\]);となり、&imgtex(\[S_n \cap X_r = \emptyset\]);~
ベクトルのタテヨコの食い違いは気にしちゃいけません。
-- (5)&imgtex(\[r>0, X_r\neq\emptyset\]);とする。~
&imgtex(\[S_n\cap X_r =\emptyset \Rightarrow \exists y\geq 0. y^\top b>r|A^\top y|\]);を示せ。
--- &imgtex(\[X_r\]);は空でない閉集合なので、十分大きな&imgtex(\[R>0\]);に対して~
&imgtex(\[\tilde{X}_r = \{x\in X_r | |x|\leq R\}\]);と置けば有界閉。~
連続関数&imgtex(\[x\in \tilde{X}_r \mapsto \frac{1}{2}|x|^2\]);には最小値が存在する。~
この最小値は定義域を&imgtex(\[\tilde{X}_r\]);に狭めなくても最小値になっている。
最小値を与える&imgtex(\[\bar{x}\in X_r\]);にはKKT条件が成立しているので、~
&imgtex(\[y\geq 0\]);~
&imgtex(\[\PDiff{}{x}\left\{\frac{1}{2}|x|^2-y^\top (Ax-b)\right\}=x^\top - y^\top A = 0\]);~
&imgtex(\[y^\top (Ax-b)=0\]);を満たす&imgtex(\[y\]);が存在する。~
~
一方、&imgtex(\[S_n\cap X_r =\emptyset\]);ならば、&imgtex(\[\forall (r,x)\in X_r.\]);について~
&imgtex(\[(r,x)\notin S_n\]);つまり&imgtex(\[r<|x|\]);が成立する。~
これを使うと、上の&imgtex(\[y\]);は~
&imgtex(\[r|A^\top y|=r|x|<|x|^2=(y^\top A)x \leq y^\top b \]);から、~
目的の条件を満たしている。
** 第三問 [#ic6acadd]
-以下の等式を証明せよ。~
&imgtex(\[\lim_{n\to\infty}\int_0^1\cdots\int_0^1\frac{n}{\sum_{k=1}^n x_k}dx_1\cdots dx_n = 2\]);
--- 確率的に解いてみる。あんまり厳密じゃないかも。~
&imgtex(\[X_i,\ i=1,2,\cdots\]);を&imgtex(\[[0,1]\]);の独立な一様乱数、~
&imgtex(\[Z_n = \frac{1}{n}\sum_{i=1}^n X_i\]);とすると、~
&imgtex(\[\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]\]);と書ける。~
&imgtex(\[Z_n\]);の分布は中心極限定理から、平均&imgtex(\[\frac{1}{2}\]);、分散&imgtex(\[\frac{1}{12n}\]);の正規分布に近づくので、~
&imgtex(\[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に飛ばす極限はδ関数の分布になるので、~
さらに&imgtex(\[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問 [#k516f65e]
-半径&imgtex($R$);の円柱の側面に沿って，
水平面と&imgtex($\alpha$);の角度をもち，
幅が&imgtex($D$);の滑り台を作りたい．
--(1)&imgtex($P$);の&imgtex($(x,y,z)$);座標を&imgtex($s$);を用いて表せ．
---&imgtex(\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)曲線&imgtex($l$);の曲率半径&imgtex($R'$);を求めよ．
---&imgtex($\frac{1}{R'}=\sqrt{\left(\frac{d^2x}{dt^2}\right)^2+\left(\frac{d^2y}{dt^2}\right)^2+\left(\frac{d^2z}{dt^2}\right)^2}$);なので，~
&imgtex(\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*});~
よって，&imgtex($R'=\frac{R}{\cos^2\alpha}$);
--(3)線分&imgtex($\overline{PS}$);上で&imgtex($P$);から距離&imgtex($u$);だけ離れた点を&imgtex($Q$);とする．
&imgtex($P$);が&imgtex($l$);に沿って距離&imgtex($s$);だけ動いたとき,
&imgtex($Q$);が動く距離&imgtex($t$);を求めよ．
---&imgtex($t=\sqrt{(s\sin\alpha)^2+\left(s\cos\alpha\frac{R+u}{R}\right)}$);．
--(4)Pが内側の円弧状を延長&imgtex($s$);だけ動くとき，
&imgtex($Q'$);が動く距離&imgtex($t'$);を求めよ．
---&imgtex($t'=s\frac{R'+u}{R'}$);．
--(5)&imgtex($P$);から&imgtex($u$);だけ外側へ離れた点&imgtex($Q$);での鉄板の厚みと点&imgtex($P$);における鉄板の厚みとの比を求めよ．
---&imgtex($t'/t$);
----
**第5問 [#t87f86e6]
-初期状態が空であるスタックを用いて数字列を置換することを考える．
「スタックに，先頭の数字を入れる．」と「スタックから一つ取り出して印字する．」
の二つの操作があり，それぞれの操作を&imgtex($S$);と&imgtex($X$);で表す．
-(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．出力は全部の数字をする必要はないみたい．（(3-i)参照）
1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321．出力は全部の数字をする必要はないみたい．（(3-i)参照）
-(2)数字列12..nを数字列&imgtex($p_1p_2\dots p_n$);に，スタックを用いて置換できるための必要十分条件は，&imgtex($p_j<p_k<p_i$);を満たす添え字&imgtex($i<j<k$);が存在しないことであることを証明せよ．
--Sを開き括弧(，Xを閉じ括弧)と書くことにすると，操作列は正しい括弧の対応のとれた
&imgtex($n$);この括弧として表せる．
また出力される数字&imgtex($p_k$);は&imgtex($k$);個目の閉じ括弧に対応する開き括弧が何番目の開き括弧であるのかということになる．~
ここで&imgtex($p_j<p_k<p_i$);を満たす&imgtex($i<j<k$);が存在しないということは括弧の対応がとれていることを意味するので，これは必要十分条件となっている．
-(3)
--(i)操作列を数字列12..nに作用させて出力される数字列を求める問題．
---単にシミュレートするだけ．時間計算量は&imgtex($O(m)$);，空間計算量は&imgtex($O(m)$);．プログラムは&ref(H14_MMI_5_1.java);．サンプルインプットは&ref(input1.txt);．
--(ii)数字列12..nを&imgtex($p_1p_2\dots p_n$);に置換する操作列を生成する問題．
---次に出力するべき数字がスタックの一番上ならば出力，そうでなければプッシュすればよい．時間計算量は&imgtex($O(n)$);，空間計算量は&imgtex($O(n)$);．プログラムは&ref(H14_MMI_5_2.java);．サンプルインプットは&ref(input2.txt);．~


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



------
コメント
#comment
トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS