院試過去問 2004年度 専門科目 数理
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
] [
リンク元
]
開始行:
[[院試勉強会]]
http://www.i.u-tokyo.ac.jp/edu/course/mi/admission.shtml~
http://www.i.u-tokyo.ac.jp/edu/course/mi/pdf/2004suuri-j....
ところで，この解答を見てる人はどれぐらいいるのでしょうか...
解答に対してつっこみなどのコメントを下に残していただけれ...
----
- 第1問~
--(1)確率ベクトル&imgtex($\bm{p},\bm{q}$);と二重確率行列&...
&imgtex($H(\bm{q})\ge H(\bm{p})$);となることを示せ．
---&imgtex($\frac{d^2}{dx^2}\log x=-1/x^2<0$);なので，&im...
&imgtex(\begin{align*}H(\bm{q})&=-\sum_{i=1}^n q_i\log q_...
---[別解]&imgtex($g(x)=-x\log(x),0<x<1$);とすると、凸関数...
&imgtex(\[ g\left(\sum_{i}a_ix_i\right)\geq \sum_{i}a_ig(...
これを利用して~
&imgtex(\begin{align*} H(\bm q)& = \sum_{j=1}^ng(q_j) \\ ...
--(2)確率ベクトル&imgtex($\bm{p},\bm{q}$);と二重確率行列&...
が&imgtex($\bm{q}=\bm{p}A$);を満たすとき，
&imgtex($k=1,2,\dots,n$);に対して&imgtex($\sigma_k(\bm{q}...
---一般性を失わず&imgtex($p_1\ge p_2\ge \dots\ge p_n,\ q_...
&imgtex(\begin{align*}\sigma_{k}(\bm{q})&=\sum_{i=1}^k q_...
（最後の行はグリーディーにとったものである．）
--(3)確率ベクトル&imgtex($\bm{p},\bm{q}$);が&imgtex($k=1,...
&imgtex($\sigma_k(\bm{q})\le \sigma_k\bm{p}$);を満たすと...
&imgtex($\bm{q}=\bm{p}A$);である二重確率行列&imgtex($A$);...
---帰納法で証明する．
&imgtex($n=1$);のときは成立は明らか．
よって，&imgtex($n=m$);のときの成立を仮定して&imgtex($n=m...
一般性を失わず&imgtex($p_1\ge p_2\ge \dots\ge p_{m+1},\ q...
ここで，&imgtex($\bm{p}'=\{p_2+(1-a_{1,1}p_1),p_3,\dots,p...
この&imgtex($A'=(a'_{ij})$);を使い適当に変形して正規化す...
&imgtex($A$);は&imgtex($\bm{q}=\bm{p}A$);を満たす二重確率...
よって帰納法により題意は示された．
---[別解]
&imgtex($A,B$);が二重確率行列であるとき、&IMGTEX($AB$);も...
&imgtex($\sigma_k(\bm q)\leq \sigma_k(\bm p), k = 1,2,\ld...
&imgtex($\bm q'=(q_2,q_3,\ldots,q_n),\bm p' = \left((\bm ...
&imgtex(\[ q_1 = \left(\bm p A_n\right)_1,\ \sigma_k(\bm ...
を満たす二重確率行列&imgtex($A_n$);を見つけることができれ...
&imgtex(\[ A=A_n\begin{pmatrix} 1&0&\cdots&0\\ 0& &...
と目的の&imgtex($\bm q=\bm p A$);なる二重確率行列&imgtex(...
従って、示すべきは&imgtex($A_n$);の存在。
一般性を失うことなく&imgtex($q_1\geq q_2\geq \ldots\geq q...
ここで、&imgtex($\sigma_k(\bm q)\leq \sigma_k(\bm p)$);で...
&imgtex($p_n\leq q_1 \leq p_1$);が成立。そこで、&imgtex($...
&imgtex(\[ A_n= \begin{pmatrix} t&&1-t\\ &\dd...
とすればよい。(&imgtex($(A_n)_{11}=(A_n)_{kk}=t$);で他の...
実際、&imgtex($p_1\geq p_2\geq \ldots \geq p_{k-1}\geq q_...
&imgtex(\[ \sigma_m(\bm q ')\leq \sigma_m(\bm p'),\ k = 1...
また、&imgtex($m=k-1,k,\ldots,n-1$);については~
&imgtex(\[ \sum_{i=1}^m p'_i = \sum_{i=2}^{m-1}p_i + p_1 ...
であるから、&imgtex($\sigma_m(\bm q')\leq \sigma_m(\bm p'...
----
-第2問~
--実&imgtex($n$);次元空間&imgtex($\mathbb{R}^n$);において，
あるベクトル&imgtex($\bm{c}$);とある正定値対称行列&imgtex...
&imgtex($\{\bm{x}|(\bm{x}-\bm{c})^{\top}A(\bm{x}-\bm{c})\...
&imgtex($\bm{c}$);をその中心と呼ぶ．~
原点を中心とした楕円体&imgtex($E$);を原点を通る超平面&img...
&imgtex($K$);を含む体積最小の楕円体&imgtex($F$);の体積&im...
&imgtex($\rho=\mathrm{vol}(F)/\mathrm{vol}(E)$);とおく．
-(1)&imgtex($E,H,K$);が~
&imgtex(\begin{align*}E&=\{\bm{x}|\sum_{i=1}^n x_i^2\le 1...
の場合に，&imgtex($F$);の中心と&imgtex($\rho$);の値を求め...
--- &imgtex(\(F\));は&imgtex(\[x_n\]);軸対称。&imgtex(\[x...
この面への&imgtex(\(K\));の射影は、単位円の右半分。~
&imgtex(\(F\));の射影は&imgtex($(1,0),(0,1)$);を通り&imgt...
//&imgtex(\(F\));の射影はそれを含む面積最小の楕円となる。~
//&imgtex(\[(1,0),(0,1)\]);を通り、&imgtex(\[(r,0)\]);を...
//&imgtex(\[\pi\frac{(1-r)^2}{\sqrt{1-2r}}\]);。これは&im...
//&imgtex(\[\left(\frac{x-r}{1-r}\right)^2+\left(1-\left(...
//求める楕円体の中心は&imgtex(\[\left(0,\cdots,0,\frac{1}...
//体積は、単位超球を&imgtex(\[n-1\]);個の軸の分だけ&imgte...
//軸1つ分だけ&imgtex(\[1-r=\frac{2}{3}\]);倍したものなの...
//&imgtex(\[\rho = \frac{2}{3}\left(\frac{2}{\sqrt{6}}\ri...
これより，&imgtex($F$);の射影を&imgtex($\frac{x_1^2}{a^2}...
&imgtex(\begin{align*}\frac{1}{a^2}+\frac{c^2}{b^2}&=1\\\...
これを解いて，&imgtex($a^2=\frac{b^2}{2b-1}$);.~
また，&imgtex($\rho=a^{n-1}b$);が最小となるのは&imgtex($a...
&imgtex($b$);で微分すると，&imgtex(\[\left(\frac{b^2}{2b-...
以上より，~
&imgtex(\begin{align*}\rho=a^{n-1}b=\frac{n}{n+1}\cdot\le...
中心の座標は&imgtex(\[\begin{pmatrix}0&0&\dots&0&c\end{pm...
--(2)上で求めた&imgtex($\rho$);に関して，&imgtex($n\to\in...
&imgtex($\log\rho$);が0に収束することを示し，
さらに，その収束の速さを論ぜよ．
---&imgtex($\lim_{n\to\infty}\rho$);は，~
&imgtex(\begin{align*}\lim_{n\to\infty}\rho&=\frac{n}{n+1...
となるので，&imgtex($\lim_{n\to\infty}\log\rho\to 0$);．~
&imgtex(\[(n-1)\log\left(1+\frac{1}{n-1}\right)\simeq 1-\...
&imgtex(\[(n+1)\log\left(1-\frac{1}{n+1}\right)\simeq -1-...
これより，~
&imgtex(\begin{align*}\log\rho&=\frac{(n-1)}{2}\log\left(...
となるので，収束の速さは&imgtex($O(1/n)$);．
--(3)一般の場合の&imgtex($E,H$);に対して，
&imgtex($\rho$);が&imgtex($E,H$);に依らず，&imgtex($n$);...
---適当な1次変換をすることで原点を中心とした楕円体は原点...
----
-第3問~
--(1)平面上に平行な直線が等間隔に引かれている．
隣り合う2直線の間隔を1とする．
この平面状に長さ1の針をランダムに投げる．
針が直線群と交わる確率&imgtex($p$);を求めよ．
---すぐ下の直線から針の重心までの距離が&imgtex($d$);で直...
&imgtex(\begin{align*}\frac{\int_0^{\pi/2}\frac{\sin\thet...
--(2)針を&imgtex($n$);回投げ,針が直線群と交わった回数&img...
&imgtex($\sqrt{n}\left(\frac{X}{n}-p\right)$);の従う分布...
&imgtex($n\to\infty$);のときどのような分布に収束するか．
---2項分布なので，&imgtex($X$);の分散は&imgtex($np(1-p)$)...
よって，&imgtex($X/n$);の分散は&imgtex($p(1-p)/n$);．
また，中心極限定理より&imgtex($\sqrt{n}\left(\frac{X}{n}-...
--(3)1辺の長さが1の正&imgtex($m$);角形&imgtex($(m\ge 3)$)...
---期待値の線型性より，&imgtex($Y=m*\frac{2}{\pi}=\frac{2...
----
-第4問~
一般に，同じ大きさの正方行列&imgtex($P,Q$);に対して，
記号&imgtex($[P,Q]$);は，行列&imgtex($PQ-QP$);を表すもの...
同じ大きさの実対称行列&imgtex($U()t)$);に関する微分方程式...
&imgtex(\begin{align*}\frac{d}{dt}U(t)&=[A,U(t)BU(t)^{\to...
を考える．~
--(1)任意の&imgtex($t>0$);に対して&imgtex($U(t)^{\top}U(t...
---&imgtex($(U(t)BU(t)^{\top})^{\top}=(U(t)BU(t)^{\top})$...
&imgtex($P,Q$);が実対称行列のとき&imgtex($[P,Q]+[P,Q]^{\t...
&imgtex(\begin{align*}\frac{d}{dt}U(t)^{\top}U(t)&=\frac{...
なので，任意の&imgtex($t>0$);に対して&imgtex($U(t)=U(0)=I...
--(2)行列&imgtex($X(t)=U(t)BU(t)^{\top}$);は，任意の&imgt...
&imgtex(\begin{align*}\frac{d}{dt}\mathrm{Tr}(AX(t))=\mat...
を満たすことを示せ．
---&imgtex($\mathrm{Tr}(AB)=\mathrm{Tr}(BA)$);なので，~
&imgtex(\newcommand{\Tr}{\mathrm{Tr}}\begin{align*}\frac{...
--(3)任意の&imgtex($t>0$);に対して~
&imgtex(\begin{align*}\frac{d}{dt}\mathrm{Tr}(AX(t))\ge 0...
であり，&imgtex($t\to\infty$);の極限において~
&imgtex(\begin{align*}\frac{d}{dt}\mathrm{Tr}(AX(t))\to 0...
となることを示せ．
---
--(4)&imgtex($A$);が相異なる実数を対角要素とする対角行列...
&imgtex($t\to\infty$);の極限において&imgtex($X(t)$);が&im...
---&imgtex($\frac{d}{dt}\mathrm{Tr}(AX(t))=\mathrm{Tr}([A...
&imgtex(\begin{align*}\mathrm{Tr}([A,X(t)][A,X(t)]^{\top}...
ここで，&imgtex($A$);の対角成分は全て異なるので，
&imgtex($X(t)$);は対角行列に収束する．~
また&imgtex($U(t)$);は(1)より直交行列なので，
&imgtex($X(t)$);の固有値は&imgtex($B$);の固有値に等しい．
よって，&imgtex($X(t)$);は&imgtex($B$);の固有値を対角成分...
----
-第5問~
円周上に&imgtex($N$);個の点があるとする(&imgtex($N\ge 4$)...
その中の一つの点から初めて時計回りに順に
&imgtex($P_0,P_1,\dots,P_{N-1}$);とする．
円の中心を原点とする正規直交座標系における各点&imgtex($P_...
座標&imgtex($x_i,y_i$);がいずれも有理数であって，これらが...
次のそれぞれの問題に大して，&imgtex($N$);に関して線型時間...
--(1)&imgtex($P_0,P_1,\dots,P_{N-1}$);の中に直径の両端点...
---&imgtex($i=0,j=1,V=[]$);,flag=FALSEと初期化する．~
&imgtex($i==j$);または&imgtex($j\ge N$);ならば終了しflag...
角&imgtex($P_iO$);と&imgtex($P_iP_j$);の外積が正のときは&...
をインクリメント，負のときは&imgtex($i$);をインクリメント...
flag=TRUEとし，&imgtex($V$);を&imgtex($V=(P_i,P_j):V$);に...
毎回&imgtex($i,j$);のどちらかはインクリメントされるので時...
--(2)&imgtex($P_0,P_1,\dots,P_{N-1}$);の中の4点を頂点とす...
--- (1)のアルゴリズムを用いれば，円の直径の両端点となる2...
その集合の大きさが2以上であれば存在する．線型時間．
--(3)&imgtex($P_0,P_1,\dots,P_{N-1}$);の中の4点を頂点とす...
---(1)のアルゴリズムを走らせて，円の直径の両端点となる2点...
&imgtex($i=0,j=0,\mathrm{max}=0$);と初期化する．
&imgtex($F_iOF_j\le \pi/4< F_iOF_{(j+1)\%n}$);となるまで&...
というアルゴリズムを用いればよい．
----
コメント
- お客様の中で第2問が解けた方はいらっしゃいませんか． -- ...
- 第2問どころか、第1問も第5問も解けませんでした。泣いてい...
- 第2問で、ρがああなるのはなぜなんでしょうか?だれか御教授...
- &imgtex($\rho$);は単位球と楕円体の体積比なので，各軸方...
- 1-(2)のグリーディーってのがよくわからない…∑pjaj1＜p1∑aj...
- 各jについて&imgtex($\sum_{i=1}^k a_{ij}\le 1$);で，&img...
- 4-(2),(3)あたりですが、[A,X]って、転置すると負になると...
- あ、なるほど、各pについて、1に足りない分借りてくるみた...
- [A,X]=Cと表すことにする。&imgtex($ C^T=-C \Rightarrow c...
#comment
終了行:
[[院試勉強会]]
http://www.i.u-tokyo.ac.jp/edu/course/mi/admission.shtml~
http://www.i.u-tokyo.ac.jp/edu/course/mi/pdf/2004suuri-j....
ところで，この解答を見てる人はどれぐらいいるのでしょうか...
解答に対してつっこみなどのコメントを下に残していただけれ...
----
- 第1問~
--(1)確率ベクトル&imgtex($\bm{p},\bm{q}$);と二重確率行列&...
&imgtex($H(\bm{q})\ge H(\bm{p})$);となることを示せ．
---&imgtex($\frac{d^2}{dx^2}\log x=-1/x^2<0$);なので，&im...
&imgtex(\begin{align*}H(\bm{q})&=-\sum_{i=1}^n q_i\log q_...
---[別解]&imgtex($g(x)=-x\log(x),0<x<1$);とすると、凸関数...
&imgtex(\[ g\left(\sum_{i}a_ix_i\right)\geq \sum_{i}a_ig(...
これを利用して~
&imgtex(\begin{align*} H(\bm q)& = \sum_{j=1}^ng(q_j) \\ ...
--(2)確率ベクトル&imgtex($\bm{p},\bm{q}$);と二重確率行列&...
が&imgtex($\bm{q}=\bm{p}A$);を満たすとき，
&imgtex($k=1,2,\dots,n$);に対して&imgtex($\sigma_k(\bm{q}...
---一般性を失わず&imgtex($p_1\ge p_2\ge \dots\ge p_n,\ q_...
&imgtex(\begin{align*}\sigma_{k}(\bm{q})&=\sum_{i=1}^k q_...
（最後の行はグリーディーにとったものである．）
--(3)確率ベクトル&imgtex($\bm{p},\bm{q}$);が&imgtex($k=1,...
&imgtex($\sigma_k(\bm{q})\le \sigma_k\bm{p}$);を満たすと...
&imgtex($\bm{q}=\bm{p}A$);である二重確率行列&imgtex($A$);...
---帰納法で証明する．
&imgtex($n=1$);のときは成立は明らか．
よって，&imgtex($n=m$);のときの成立を仮定して&imgtex($n=m...
一般性を失わず&imgtex($p_1\ge p_2\ge \dots\ge p_{m+1},\ q...
ここで，&imgtex($\bm{p}'=\{p_2+(1-a_{1,1}p_1),p_3,\dots,p...
この&imgtex($A'=(a'_{ij})$);を使い適当に変形して正規化す...
&imgtex($A$);は&imgtex($\bm{q}=\bm{p}A$);を満たす二重確率...
よって帰納法により題意は示された．
---[別解]
&imgtex($A,B$);が二重確率行列であるとき、&IMGTEX($AB$);も...
&imgtex($\sigma_k(\bm q)\leq \sigma_k(\bm p), k = 1,2,\ld...
&imgtex($\bm q'=(q_2,q_3,\ldots,q_n),\bm p' = \left((\bm ...
&imgtex(\[ q_1 = \left(\bm p A_n\right)_1,\ \sigma_k(\bm ...
を満たす二重確率行列&imgtex($A_n$);を見つけることができれ...
&imgtex(\[ A=A_n\begin{pmatrix} 1&0&\cdots&0\\ 0& &...
と目的の&imgtex($\bm q=\bm p A$);なる二重確率行列&imgtex(...
従って、示すべきは&imgtex($A_n$);の存在。
一般性を失うことなく&imgtex($q_1\geq q_2\geq \ldots\geq q...
ここで、&imgtex($\sigma_k(\bm q)\leq \sigma_k(\bm p)$);で...
&imgtex($p_n\leq q_1 \leq p_1$);が成立。そこで、&imgtex($...
&imgtex(\[ A_n= \begin{pmatrix} t&&1-t\\ &\dd...
とすればよい。(&imgtex($(A_n)_{11}=(A_n)_{kk}=t$);で他の...
実際、&imgtex($p_1\geq p_2\geq \ldots \geq p_{k-1}\geq q_...
&imgtex(\[ \sigma_m(\bm q ')\leq \sigma_m(\bm p'),\ k = 1...
また、&imgtex($m=k-1,k,\ldots,n-1$);については~
&imgtex(\[ \sum_{i=1}^m p'_i = \sum_{i=2}^{m-1}p_i + p_1 ...
であるから、&imgtex($\sigma_m(\bm q')\leq \sigma_m(\bm p'...
----
-第2問~
--実&imgtex($n$);次元空間&imgtex($\mathbb{R}^n$);において，
あるベクトル&imgtex($\bm{c}$);とある正定値対称行列&imgtex...
&imgtex($\{\bm{x}|(\bm{x}-\bm{c})^{\top}A(\bm{x}-\bm{c})\...
&imgtex($\bm{c}$);をその中心と呼ぶ．~
原点を中心とした楕円体&imgtex($E$);を原点を通る超平面&img...
&imgtex($K$);を含む体積最小の楕円体&imgtex($F$);の体積&im...
&imgtex($\rho=\mathrm{vol}(F)/\mathrm{vol}(E)$);とおく．
-(1)&imgtex($E,H,K$);が~
&imgtex(\begin{align*}E&=\{\bm{x}|\sum_{i=1}^n x_i^2\le 1...
の場合に，&imgtex($F$);の中心と&imgtex($\rho$);の値を求め...
--- &imgtex(\(F\));は&imgtex(\[x_n\]);軸対称。&imgtex(\[x...
この面への&imgtex(\(K\));の射影は、単位円の右半分。~
&imgtex(\(F\));の射影は&imgtex($(1,0),(0,1)$);を通り&imgt...
//&imgtex(\(F\));の射影はそれを含む面積最小の楕円となる。~
//&imgtex(\[(1,0),(0,1)\]);を通り、&imgtex(\[(r,0)\]);を...
//&imgtex(\[\pi\frac{(1-r)^2}{\sqrt{1-2r}}\]);。これは&im...
//&imgtex(\[\left(\frac{x-r}{1-r}\right)^2+\left(1-\left(...
//求める楕円体の中心は&imgtex(\[\left(0,\cdots,0,\frac{1}...
//体積は、単位超球を&imgtex(\[n-1\]);個の軸の分だけ&imgte...
//軸1つ分だけ&imgtex(\[1-r=\frac{2}{3}\]);倍したものなの...
//&imgtex(\[\rho = \frac{2}{3}\left(\frac{2}{\sqrt{6}}\ri...
これより，&imgtex($F$);の射影を&imgtex($\frac{x_1^2}{a^2}...
&imgtex(\begin{align*}\frac{1}{a^2}+\frac{c^2}{b^2}&=1\\\...
これを解いて，&imgtex($a^2=\frac{b^2}{2b-1}$);.~
また，&imgtex($\rho=a^{n-1}b$);が最小となるのは&imgtex($a...
&imgtex($b$);で微分すると，&imgtex(\[\left(\frac{b^2}{2b-...
以上より，~
&imgtex(\begin{align*}\rho=a^{n-1}b=\frac{n}{n+1}\cdot\le...
中心の座標は&imgtex(\[\begin{pmatrix}0&0&\dots&0&c\end{pm...
--(2)上で求めた&imgtex($\rho$);に関して，&imgtex($n\to\in...
&imgtex($\log\rho$);が0に収束することを示し，
さらに，その収束の速さを論ぜよ．
---&imgtex($\lim_{n\to\infty}\rho$);は，~
&imgtex(\begin{align*}\lim_{n\to\infty}\rho&=\frac{n}{n+1...
となるので，&imgtex($\lim_{n\to\infty}\log\rho\to 0$);．~
&imgtex(\[(n-1)\log\left(1+\frac{1}{n-1}\right)\simeq 1-\...
&imgtex(\[(n+1)\log\left(1-\frac{1}{n+1}\right)\simeq -1-...
これより，~
&imgtex(\begin{align*}\log\rho&=\frac{(n-1)}{2}\log\left(...
となるので，収束の速さは&imgtex($O(1/n)$);．
--(3)一般の場合の&imgtex($E,H$);に対して，
&imgtex($\rho$);が&imgtex($E,H$);に依らず，&imgtex($n$);...
---適当な1次変換をすることで原点を中心とした楕円体は原点...
----
-第3問~
--(1)平面上に平行な直線が等間隔に引かれている．
隣り合う2直線の間隔を1とする．
この平面状に長さ1の針をランダムに投げる．
針が直線群と交わる確率&imgtex($p$);を求めよ．
---すぐ下の直線から針の重心までの距離が&imgtex($d$);で直...
&imgtex(\begin{align*}\frac{\int_0^{\pi/2}\frac{\sin\thet...
--(2)針を&imgtex($n$);回投げ,針が直線群と交わった回数&img...
&imgtex($\sqrt{n}\left(\frac{X}{n}-p\right)$);の従う分布...
&imgtex($n\to\infty$);のときどのような分布に収束するか．
---2項分布なので，&imgtex($X$);の分散は&imgtex($np(1-p)$)...
よって，&imgtex($X/n$);の分散は&imgtex($p(1-p)/n$);．
また，中心極限定理より&imgtex($\sqrt{n}\left(\frac{X}{n}-...
--(3)1辺の長さが1の正&imgtex($m$);角形&imgtex($(m\ge 3)$)...
---期待値の線型性より，&imgtex($Y=m*\frac{2}{\pi}=\frac{2...
----
-第4問~
一般に，同じ大きさの正方行列&imgtex($P,Q$);に対して，
記号&imgtex($[P,Q]$);は，行列&imgtex($PQ-QP$);を表すもの...
同じ大きさの実対称行列&imgtex($U()t)$);に関する微分方程式...
&imgtex(\begin{align*}\frac{d}{dt}U(t)&=[A,U(t)BU(t)^{\to...
を考える．~
--(1)任意の&imgtex($t>0$);に対して&imgtex($U(t)^{\top}U(t...
---&imgtex($(U(t)BU(t)^{\top})^{\top}=(U(t)BU(t)^{\top})$...
&imgtex($P,Q$);が実対称行列のとき&imgtex($[P,Q]+[P,Q]^{\t...
&imgtex(\begin{align*}\frac{d}{dt}U(t)^{\top}U(t)&=\frac{...
なので，任意の&imgtex($t>0$);に対して&imgtex($U(t)=U(0)=I...
--(2)行列&imgtex($X(t)=U(t)BU(t)^{\top}$);は，任意の&imgt...
&imgtex(\begin{align*}\frac{d}{dt}\mathrm{Tr}(AX(t))=\mat...
を満たすことを示せ．
---&imgtex($\mathrm{Tr}(AB)=\mathrm{Tr}(BA)$);なので，~
&imgtex(\newcommand{\Tr}{\mathrm{Tr}}\begin{align*}\frac{...
--(3)任意の&imgtex($t>0$);に対して~
&imgtex(\begin{align*}\frac{d}{dt}\mathrm{Tr}(AX(t))\ge 0...
であり，&imgtex($t\to\infty$);の極限において~
&imgtex(\begin{align*}\frac{d}{dt}\mathrm{Tr}(AX(t))\to 0...
となることを示せ．
---
--(4)&imgtex($A$);が相異なる実数を対角要素とする対角行列...
&imgtex($t\to\infty$);の極限において&imgtex($X(t)$);が&im...
---&imgtex($\frac{d}{dt}\mathrm{Tr}(AX(t))=\mathrm{Tr}([A...
&imgtex(\begin{align*}\mathrm{Tr}([A,X(t)][A,X(t)]^{\top}...
ここで，&imgtex($A$);の対角成分は全て異なるので，
&imgtex($X(t)$);は対角行列に収束する．~
また&imgtex($U(t)$);は(1)より直交行列なので，
&imgtex($X(t)$);の固有値は&imgtex($B$);の固有値に等しい．
よって，&imgtex($X(t)$);は&imgtex($B$);の固有値を対角成分...
----
-第5問~
円周上に&imgtex($N$);個の点があるとする(&imgtex($N\ge 4$)...
その中の一つの点から初めて時計回りに順に
&imgtex($P_0,P_1,\dots,P_{N-1}$);とする．
円の中心を原点とする正規直交座標系における各点&imgtex($P_...
座標&imgtex($x_i,y_i$);がいずれも有理数であって，これらが...
次のそれぞれの問題に大して，&imgtex($N$);に関して線型時間...
--(1)&imgtex($P_0,P_1,\dots,P_{N-1}$);の中に直径の両端点...
---&imgtex($i=0,j=1,V=[]$);,flag=FALSEと初期化する．~
&imgtex($i==j$);または&imgtex($j\ge N$);ならば終了しflag...
角&imgtex($P_iO$);と&imgtex($P_iP_j$);の外積が正のときは&...
をインクリメント，負のときは&imgtex($i$);をインクリメント...
flag=TRUEとし，&imgtex($V$);を&imgtex($V=(P_i,P_j):V$);に...
毎回&imgtex($i,j$);のどちらかはインクリメントされるので時...
--(2)&imgtex($P_0,P_1,\dots,P_{N-1}$);の中の4点を頂点とす...
--- (1)のアルゴリズムを用いれば，円の直径の両端点となる2...
その集合の大きさが2以上であれば存在する．線型時間．
--(3)&imgtex($P_0,P_1,\dots,P_{N-1}$);の中の4点を頂点とす...
---(1)のアルゴリズムを走らせて，円の直径の両端点となる2点...
&imgtex($i=0,j=0,\mathrm{max}=0$);と初期化する．
&imgtex($F_iOF_j\le \pi/4< F_iOF_{(j+1)\%n}$);となるまで&...
というアルゴリズムを用いればよい．
----
コメント
- お客様の中で第2問が解けた方はいらっしゃいませんか． -- ...
- 第2問どころか、第1問も第5問も解けませんでした。泣いてい...
- 第2問で、ρがああなるのはなぜなんでしょうか?だれか御教授...
- &imgtex($\rho$);は単位球と楕円体の体積比なので，各軸方...
- 1-(2)のグリーディーってのがよくわからない…∑pjaj1＜p1∑aj...
- 各jについて&imgtex($\sum_{i=1}^k a_{ij}\le 1$);で，&img...
- 4-(2),(3)あたりですが、[A,X]って、転置すると負になると...
- あ、なるほど、各pについて、1に足りない分借りてくるみた...
- [A,X]=Cと表すことにする。&imgtex($ C^T=-C \Rightarrow c...
#comment
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
