院試過去問 2005年度 専門科目 数理
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
] [
リンク元
]
開始行:
[[院試勉強会]]
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....
- 第1問~
時間&imgtex($t$);の関数&imgtex($y_1,y_2,y_3$);に関する微...
&imgtex(\begin{align*}\frac{d}{dt}\begin{pmatrix}y_1\\y_2...
を考える．ただし，&imgtex($I_1,I_2,I_3$);は正の定数とする．
--(1)方程式(*)が，次の二つの保存量を持つことを示せ．~
&imgtex(\begin{align*}L=y_1^2+y_2^2+y_3^2,\ K=\frac{1}{2}...
---微分して0になることを示せばよい．~
&imgtex(\begin{align*}\frac{dL}{dt}&=2\left(y_1\frac{dy_1...
&imgtex(\begin{align*}\frac{dK}{dt}&=\frac{y_1}{I_1}\frac...
--一般に，時間&imgtex($t$);の関数&imgtex($\bm{z}=(z_1,z_2...
&imgtex(\begin{align*}\frac{d\bm{z}}{dt}=\bm{f}(\bm{z})\t...
に対して，差分方程式~
&imgtex(\begin{align*}\frac{\bm{z}^{(n+1)-\bm{z}^{(n)}}}{...
を陰的中点則による離散化方程式という．
ここで，&imgtex($h>0$);は時間の離散化幅を表し，
&imgtex($\bm{z}^{(n)}$);は&imgtex($\bm{z}(nh)$);の近似で...
--(2)方程式(*)を陰的中点則で離散化した方程式においても，
(1)の&imgtex($L,K$);が保存量であることを示せ．
---(3)より明らか.
--(3)方程式(**)において2次形式&imgtex($\bm{z}^{\top}C\bm{...
陰的中点則による離散化方程式においても，
&imgtex($\bm{z}^{\top}C\bm{z}$);が保存量であることを示せ．
---&imgtex($\bm{z}^{\top}C\bm{z}$);が保存量であるので，~
&imgtex(\begin{align*}\frac{d}{dt}(\bm{z}^{\top}C\bm{z})=...
&imgtex($\bm{z}$);に&imgtex($\frac{\bm{z}^{(n+1)}+\bm{z}^...
&imgtex(\[2\frac{\bm{z}^{(n+1)}+\bm{z}^{(n)}}{2}C\bm{f}\l...
これを，&imgtex($h$);倍して展開すれば，&imgtex($C$);は対...
&imgtex(\[(\bm{z}^{(n+1)})^{\top}C z^{(n+1)}=(\bm{z}^{(n)...
----
-第2問~
平面&imgtex($\mathbb{R}^2$);から&imgtex($\mathbb{R}^2$);...
&imgtex(\begin{align*}T:\begin{pmatrix}x\\y\end{pmatrix}\...
&imgtex(\begin{align*}T\begin{pmatrix}\bar{x}\\ \bar{y}\e...
&imgtex(\begin{align*}\begin{pmatrix}\bar{x}\\ \bar{y}\en...
また，不動点&imgtex(\begin{align*}\bar{x}\\ \bar{y}\end{a...
そうでないとき不安定であるという．
--(1)ヤコビ行列&imgtex($J(\bar{x},\bar{y})$);の行列式&img...
---簡単のため行列式を&imgtex($d$);，トレースを&imgtex($t$...
すると，固有値&imgtex($\lambda$);は&imgtex($f(\lambda)=\l...
判別式&imgtex($t^2-4d\ge 0$);のとき，&imgtex($-1<t/2<1,\ ...
判別式&imgtex($t^2-4d< 0$);のとき，&imgtex($|\lambda_1|=|...
よって，&imgtex($d<1, d>|t|-1$);の三角形の内部が求める領...
--(2)&imgtex($f(x,y)=-ax^2+y+1,\ g(x,y)=bx$);であるとき，
写像&imgtex($T$);をエノン写像という．
エノン写像の不動点を求めよ．
また，求めた不動点の安定性とパラメータの値とtの関係を調べ...
---不動点は，~
&imgtex(\begin{align*}\bar{x}&=-a\bar{x}^2+\bar{y}+1\\\ba...
を満たすので，これを解いて~
&imgtex(\begin{align*}\bar{x}&=\frac{b-1\pm\sqrt{(1-b)^2+...
&imgtex(\begin{align*}J=\begin{pmatrix}-2a\bar{x}&1\\b&0\...
これより，~
&imgtex(\begin{align*}\mathrm{tr} J&=-2a\bar{x}=1-b\pm\sq...
これが，(1)で求めた三角形の領域に入れば良い．
&imgtex($1-b=b'$);とおくと，
&imgtex($0<b'<2$);,&imgtex($b'> |b'\pm\sqrt{b'^2+4a}|=\pm...
不動点は実なので&imgtex($b'^2+4a\ge 0$);~
複号が＋のときは，&imgtex($0>\sqrt{b'^2+4a}$);となり漸近...
－のときは，&imgtex($2b'>\sqrt{b'^2+4a},\ 3(1-b)^2>4a$);．~
これと&imgtex($a,b\ne 0$);を条件とすればよい.
--(3)エノン写像&imgtex($T$);を，非線型写像&imgtex($T_1$);...
&imgtex(\begin{align*}T\begin{pmatrix}x\\ y\end{pmatrix}=...
と表すとき，&imgtex(\begin{align*}T_1\begin{pmatrix}x\\y\...
また，&imgtex($a=1.4, b=0.3$);であるとき，長方形領域が&im...
その面積を求めよ．
--- ~
&imgtex(\begin{align*}\begin{pmatrix}-ax^2+y+1\\ bx\end{p...
より，~
&imgtex(\begin{align*}T_1\begin{pmatrix}x\\y\end{pmatrix}...
これより，&imgtex($T_1(A)$);は&imgtex(\begin{align*}\left...
&imgtex($T_2(T_1(A))$);は&imgtex($x$);軸方向に&imgtex($0....
&imgtex($T_3(T_2(T_1(A)))$);は&imgtex($x$);軸&imgtex($y$)...
--(4)エノン写像&imgtex($T$);が&imgtex($\mathrm{R}^2$);か...
---逆写像は&imgtex(\begin{align*}\begin{pmatrix}x/b\\ay^2...
----
- 第3問~
ある物体の重さ&imgtex($\mu$);を測定する実験を2回行って得...
その標本平均を&imgtex($\bar{X}=(X_1+X_2)/2$);とする．
測定の誤差&imgtex($X_1-\mu, X_2-\mu$);は独立に平均0，分散...
--(1)&imgtex($Y=(X_1-X_2)/2$);とおく．&imgtex($\bar{X}$);...
---確率密度関数をそれぞれ&imgtex($f_{X_1},f_{X_2},f_{\bar...
&imgtex(\begin{align*}f_{X_1}(x)&=\frac{1}{\sqrt{2\pi}}e^...
これを&imgtex($\bar{X},Y$);に変数変換すると，~
&imgtex(\begin{align*}f_{\bar{X}Y}(\bar{x},y)&=\frac{1}{2...
--(2)標本平均&imgtex($\bar{X}$);が与えられたもとでの&imgt...
また，&imgtex($E[X_1|\bar{X}]$);の期待値と分散を求めよ．
---
&imgtex(\begin{align*}f_{X_1|\bar{X}}(x_1,\bar{x})&=\frac...
これより，&imgtex($E[X_1|\bar{X}]=\bar{x}$);．~
また，&imgtex($f_{\bar{X}}(\bar{x})=\frac{1}{\sqrt{\pi}}e...
なので，平均&imgtex($\mu$);分散&imgtex($1/2$);である．
--(3)&imgtex($X_1,X_2$);の関数&imgtex($f(X_1,X_2)$);を考...
&imgtex($\bar{X}$);が与えられたもとでの&imgtex($f(X_1,X_2...
---&imgtex($E[f(X_1,X_2)|\bar{X}]=\int_{-\infty}^{\infty}...
--(4)&imgtex($f(X_1,X_2)$);が&imgtex($\mu$);の不偏推定量...
&imgtex($E[f(X_1,X_2)|\bar{X}]$);は&imgtex($\mu$);の不偏...
また，&imgtex($E[f(X_1,X_2)|\bar{X}]$);の分散は&imgtex($f...
---&imgtex($f(X_1,X_2)$);が&imgtex($\mu$);の不偏推定量で...
&imgtex(\begin{align*}\int_{-\infty}^{\infty}f(x_1,x_2)\f...
よって，~
&imgtex(\begin{align*}E[E[f(X_1,X_2)|\bar{X}]]&=E[\int_{-...
上と同様の議論により&imgtex($E[E[Y|X]]=E[Y]$);がなりたつ...
&imgtex(\newcommand{\Var}{\mathrm{Var}}\begin{align*}\Var...
--(5)十分統計量とはどのような概念か，また，どのような性質...
---十分統計量とは，パラメータ&imgtex($\theta$);を持つモデ...
（なに書けばいいのかわかりません）
----
-第4問~
&imgtex($k$);個の&imgtex($n$);次元ベクトル&imgtex($\bm{a}...
&imgtex(\[C(L)=\{\bm{x}\in\mathbb{R}^n|\bm{a}_i^{\top}\bm...
と定義する．ただし，&imgtex($\bm{a}_i^{\top}$);は&imgtex(...
--&imgtex($k=3, n=2, \bm{a}_1=\begin{pmatrix}1\\0\end{pma...
---全ての場合&imgtex($2^3=8$);通りを考える．~
&imgtex(\begin{align*}C(K)&\ni \begin{pmatrix}-1\\-2\end{...
ところが，&imgtex($C(\{2\}),C(\{1,3\})$);については，~
&imgtex(\begin{align*}x_1&\lessgtr 0\tag{1}\\x_1+x_2&\gtr...
であるが，&imgtex($2\times \mathrm{(1)}+\mathrm{(3)}$);よ...
--(2) &imgtex($n=3$);とする．
&imgtex($C(L)$);が非空となる&imgtex($L$);の個数を&imgtex(...
&imgtex($r_1,r_2,\dots ,r_5$);の値を求めよ．また，&imgtex...
---
//&imgtex($\bm{a}_k=\begin{pmatrix}1\\k\\k^2\end{pmatrix}...
&imgtex($\bm{a}_i^{\top}\bm{x}\gtrless 0$);は原点を通る平...
よって，1枚増えるごとに空間の増え方が2増えるので，&imgtex...
&imgtex($r_k=r_{k-1}+2(k-1)=\dots =r_1+\sum_{i=1}^{k-1}2i...
--(3)任意の&imgtex($L\subseteq K$);に対して&imgtex($C(L)$...
&imgtex($\{\bm{a}_1,\bm{a}_2,\dots,\bm{a}_k\}$);は線型独...
---背理法で示す．
&imgtex($\bm{a}_1,\bm{a}_2,\dots,\bm{a}_k$);が線型独立で...
すると，&imgtex($\bm{x}^{\top}\bm{a}_k=\sum_{i=1}^{k-1}w_...
--&imgtex($\{\bm{a}_1,\bm{a}_2,\dots,\bm{a}_k\}$);が線型...
---&imgtex($\{\bm{x}\bm{a}_1,\bm{x}\bm{a}_2,\dots,\bm{x}\...
c.f. http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%82%A2...
----
- 第5問~
&imgtex($m$);と&imgtex($n$);を正整数とし，
&imgtex($m$);は&imgtex($n$);に比べて十分小さいとする．
&imgtex($M$);を&imgtex($m$);個のシンボルの集合とする．
大きさ&imgtex($n$);の1次元配列&imgtex($a$);のそれぞれの要...
1つのシンボルが格納されている．
配列&imgtex($a$);の中には&imgtex($m$);個のシンボルが全て...
さらに同じシンボルはその全てが連続して現れる．
このとき，全ての変化位置&imgtex($m-1$);個を求める時間複雑...
その時間複雑度を評価せよ．
---少々無駄があるが，要請を満たす説明のしやすいアルゴリズ...
---&imgtex($a[n]$);のシンボルを調べ，そのシンボルの切れ目...
ここで，&imgtex($a[k_{m-1}]\ne a[n],\ a[k_{m-1}+1]=a[n]$)...
&imgtex($a$);の0から&imgtex($k_{m-1}$);までの配列に対して...
これを&imgtex($m-1$);回繰り返すので，時間複雑度は&imgtex(...
---それぞれのシンボルの探索を同時にやるようにすれば&imgte...
-----------------
コメント
- 1-1 どちらもy1y2y3のになるはずです…これくらいあとから読...
- 4-(2)ですが、nの値は関係ないのでしょうか？関係ある気が...
- m log(n/m)もm(log n - log m)でm log nにはならない？同時...
- 4-(2)はn=3なので3次元の平面分割になってます．5は&imgtex...
//#comment
終了行:
[[院試勉強会]]
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....
- 第1問~
時間&imgtex($t$);の関数&imgtex($y_1,y_2,y_3$);に関する微...
&imgtex(\begin{align*}\frac{d}{dt}\begin{pmatrix}y_1\\y_2...
を考える．ただし，&imgtex($I_1,I_2,I_3$);は正の定数とする．
--(1)方程式(*)が，次の二つの保存量を持つことを示せ．~
&imgtex(\begin{align*}L=y_1^2+y_2^2+y_3^2,\ K=\frac{1}{2}...
---微分して0になることを示せばよい．~
&imgtex(\begin{align*}\frac{dL}{dt}&=2\left(y_1\frac{dy_1...
&imgtex(\begin{align*}\frac{dK}{dt}&=\frac{y_1}{I_1}\frac...
--一般に，時間&imgtex($t$);の関数&imgtex($\bm{z}=(z_1,z_2...
&imgtex(\begin{align*}\frac{d\bm{z}}{dt}=\bm{f}(\bm{z})\t...
に対して，差分方程式~
&imgtex(\begin{align*}\frac{\bm{z}^{(n+1)-\bm{z}^{(n)}}}{...
を陰的中点則による離散化方程式という．
ここで，&imgtex($h>0$);は時間の離散化幅を表し，
&imgtex($\bm{z}^{(n)}$);は&imgtex($\bm{z}(nh)$);の近似で...
--(2)方程式(*)を陰的中点則で離散化した方程式においても，
(1)の&imgtex($L,K$);が保存量であることを示せ．
---(3)より明らか.
--(3)方程式(**)において2次形式&imgtex($\bm{z}^{\top}C\bm{...
陰的中点則による離散化方程式においても，
&imgtex($\bm{z}^{\top}C\bm{z}$);が保存量であることを示せ．
---&imgtex($\bm{z}^{\top}C\bm{z}$);が保存量であるので，~
&imgtex(\begin{align*}\frac{d}{dt}(\bm{z}^{\top}C\bm{z})=...
&imgtex($\bm{z}$);に&imgtex($\frac{\bm{z}^{(n+1)}+\bm{z}^...
&imgtex(\[2\frac{\bm{z}^{(n+1)}+\bm{z}^{(n)}}{2}C\bm{f}\l...
これを，&imgtex($h$);倍して展開すれば，&imgtex($C$);は対...
&imgtex(\[(\bm{z}^{(n+1)})^{\top}C z^{(n+1)}=(\bm{z}^{(n)...
----
-第2問~
平面&imgtex($\mathbb{R}^2$);から&imgtex($\mathbb{R}^2$);...
&imgtex(\begin{align*}T:\begin{pmatrix}x\\y\end{pmatrix}\...
&imgtex(\begin{align*}T\begin{pmatrix}\bar{x}\\ \bar{y}\e...
&imgtex(\begin{align*}\begin{pmatrix}\bar{x}\\ \bar{y}\en...
また，不動点&imgtex(\begin{align*}\bar{x}\\ \bar{y}\end{a...
そうでないとき不安定であるという．
--(1)ヤコビ行列&imgtex($J(\bar{x},\bar{y})$);の行列式&img...
---簡単のため行列式を&imgtex($d$);，トレースを&imgtex($t$...
すると，固有値&imgtex($\lambda$);は&imgtex($f(\lambda)=\l...
判別式&imgtex($t^2-4d\ge 0$);のとき，&imgtex($-1<t/2<1,\ ...
判別式&imgtex($t^2-4d< 0$);のとき，&imgtex($|\lambda_1|=|...
よって，&imgtex($d<1, d>|t|-1$);の三角形の内部が求める領...
--(2)&imgtex($f(x,y)=-ax^2+y+1,\ g(x,y)=bx$);であるとき，
写像&imgtex($T$);をエノン写像という．
エノン写像の不動点を求めよ．
また，求めた不動点の安定性とパラメータの値とtの関係を調べ...
---不動点は，~
&imgtex(\begin{align*}\bar{x}&=-a\bar{x}^2+\bar{y}+1\\\ba...
を満たすので，これを解いて~
&imgtex(\begin{align*}\bar{x}&=\frac{b-1\pm\sqrt{(1-b)^2+...
&imgtex(\begin{align*}J=\begin{pmatrix}-2a\bar{x}&1\\b&0\...
これより，~
&imgtex(\begin{align*}\mathrm{tr} J&=-2a\bar{x}=1-b\pm\sq...
これが，(1)で求めた三角形の領域に入れば良い．
&imgtex($1-b=b'$);とおくと，
&imgtex($0<b'<2$);,&imgtex($b'> |b'\pm\sqrt{b'^2+4a}|=\pm...
不動点は実なので&imgtex($b'^2+4a\ge 0$);~
複号が＋のときは，&imgtex($0>\sqrt{b'^2+4a}$);となり漸近...
－のときは，&imgtex($2b'>\sqrt{b'^2+4a},\ 3(1-b)^2>4a$);．~
これと&imgtex($a,b\ne 0$);を条件とすればよい.
--(3)エノン写像&imgtex($T$);を，非線型写像&imgtex($T_1$);...
&imgtex(\begin{align*}T\begin{pmatrix}x\\ y\end{pmatrix}=...
と表すとき，&imgtex(\begin{align*}T_1\begin{pmatrix}x\\y\...
また，&imgtex($a=1.4, b=0.3$);であるとき，長方形領域が&im...
その面積を求めよ．
--- ~
&imgtex(\begin{align*}\begin{pmatrix}-ax^2+y+1\\ bx\end{p...
より，~
&imgtex(\begin{align*}T_1\begin{pmatrix}x\\y\end{pmatrix}...
これより，&imgtex($T_1(A)$);は&imgtex(\begin{align*}\left...
&imgtex($T_2(T_1(A))$);は&imgtex($x$);軸方向に&imgtex($0....
&imgtex($T_3(T_2(T_1(A)))$);は&imgtex($x$);軸&imgtex($y$)...
--(4)エノン写像&imgtex($T$);が&imgtex($\mathrm{R}^2$);か...
---逆写像は&imgtex(\begin{align*}\begin{pmatrix}x/b\\ay^2...
----
- 第3問~
ある物体の重さ&imgtex($\mu$);を測定する実験を2回行って得...
その標本平均を&imgtex($\bar{X}=(X_1+X_2)/2$);とする．
測定の誤差&imgtex($X_1-\mu, X_2-\mu$);は独立に平均0，分散...
--(1)&imgtex($Y=(X_1-X_2)/2$);とおく．&imgtex($\bar{X}$);...
---確率密度関数をそれぞれ&imgtex($f_{X_1},f_{X_2},f_{\bar...
&imgtex(\begin{align*}f_{X_1}(x)&=\frac{1}{\sqrt{2\pi}}e^...
これを&imgtex($\bar{X},Y$);に変数変換すると，~
&imgtex(\begin{align*}f_{\bar{X}Y}(\bar{x},y)&=\frac{1}{2...
--(2)標本平均&imgtex($\bar{X}$);が与えられたもとでの&imgt...
また，&imgtex($E[X_1|\bar{X}]$);の期待値と分散を求めよ．
---
&imgtex(\begin{align*}f_{X_1|\bar{X}}(x_1,\bar{x})&=\frac...
これより，&imgtex($E[X_1|\bar{X}]=\bar{x}$);．~
また，&imgtex($f_{\bar{X}}(\bar{x})=\frac{1}{\sqrt{\pi}}e...
なので，平均&imgtex($\mu$);分散&imgtex($1/2$);である．
--(3)&imgtex($X_1,X_2$);の関数&imgtex($f(X_1,X_2)$);を考...
&imgtex($\bar{X}$);が与えられたもとでの&imgtex($f(X_1,X_2...
---&imgtex($E[f(X_1,X_2)|\bar{X}]=\int_{-\infty}^{\infty}...
--(4)&imgtex($f(X_1,X_2)$);が&imgtex($\mu$);の不偏推定量...
&imgtex($E[f(X_1,X_2)|\bar{X}]$);は&imgtex($\mu$);の不偏...
また，&imgtex($E[f(X_1,X_2)|\bar{X}]$);の分散は&imgtex($f...
---&imgtex($f(X_1,X_2)$);が&imgtex($\mu$);の不偏推定量で...
&imgtex(\begin{align*}\int_{-\infty}^{\infty}f(x_1,x_2)\f...
よって，~
&imgtex(\begin{align*}E[E[f(X_1,X_2)|\bar{X}]]&=E[\int_{-...
上と同様の議論により&imgtex($E[E[Y|X]]=E[Y]$);がなりたつ...
&imgtex(\newcommand{\Var}{\mathrm{Var}}\begin{align*}\Var...
--(5)十分統計量とはどのような概念か，また，どのような性質...
---十分統計量とは，パラメータ&imgtex($\theta$);を持つモデ...
（なに書けばいいのかわかりません）
----
-第4問~
&imgtex($k$);個の&imgtex($n$);次元ベクトル&imgtex($\bm{a}...
&imgtex(\[C(L)=\{\bm{x}\in\mathbb{R}^n|\bm{a}_i^{\top}\bm...
と定義する．ただし，&imgtex($\bm{a}_i^{\top}$);は&imgtex(...
--&imgtex($k=3, n=2, \bm{a}_1=\begin{pmatrix}1\\0\end{pma...
---全ての場合&imgtex($2^3=8$);通りを考える．~
&imgtex(\begin{align*}C(K)&\ni \begin{pmatrix}-1\\-2\end{...
ところが，&imgtex($C(\{2\}),C(\{1,3\})$);については，~
&imgtex(\begin{align*}x_1&\lessgtr 0\tag{1}\\x_1+x_2&\gtr...
であるが，&imgtex($2\times \mathrm{(1)}+\mathrm{(3)}$);よ...
--(2) &imgtex($n=3$);とする．
&imgtex($C(L)$);が非空となる&imgtex($L$);の個数を&imgtex(...
&imgtex($r_1,r_2,\dots ,r_5$);の値を求めよ．また，&imgtex...
---
//&imgtex($\bm{a}_k=\begin{pmatrix}1\\k\\k^2\end{pmatrix}...
&imgtex($\bm{a}_i^{\top}\bm{x}\gtrless 0$);は原点を通る平...
よって，1枚増えるごとに空間の増え方が2増えるので，&imgtex...
&imgtex($r_k=r_{k-1}+2(k-1)=\dots =r_1+\sum_{i=1}^{k-1}2i...
--(3)任意の&imgtex($L\subseteq K$);に対して&imgtex($C(L)$...
&imgtex($\{\bm{a}_1,\bm{a}_2,\dots,\bm{a}_k\}$);は線型独...
---背理法で示す．
&imgtex($\bm{a}_1,\bm{a}_2,\dots,\bm{a}_k$);が線型独立で...
すると，&imgtex($\bm{x}^{\top}\bm{a}_k=\sum_{i=1}^{k-1}w_...
--&imgtex($\{\bm{a}_1,\bm{a}_2,\dots,\bm{a}_k\}$);が線型...
---&imgtex($\{\bm{x}\bm{a}_1,\bm{x}\bm{a}_2,\dots,\bm{x}\...
c.f. http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%82%A2...
----
- 第5問~
&imgtex($m$);と&imgtex($n$);を正整数とし，
&imgtex($m$);は&imgtex($n$);に比べて十分小さいとする．
&imgtex($M$);を&imgtex($m$);個のシンボルの集合とする．
大きさ&imgtex($n$);の1次元配列&imgtex($a$);のそれぞれの要...
1つのシンボルが格納されている．
配列&imgtex($a$);の中には&imgtex($m$);個のシンボルが全て...
さらに同じシンボルはその全てが連続して現れる．
このとき，全ての変化位置&imgtex($m-1$);個を求める時間複雑...
その時間複雑度を評価せよ．
---少々無駄があるが，要請を満たす説明のしやすいアルゴリズ...
---&imgtex($a[n]$);のシンボルを調べ，そのシンボルの切れ目...
ここで，&imgtex($a[k_{m-1}]\ne a[n],\ a[k_{m-1}+1]=a[n]$)...
&imgtex($a$);の0から&imgtex($k_{m-1}$);までの配列に対して...
これを&imgtex($m-1$);回繰り返すので，時間複雑度は&imgtex(...
---それぞれのシンボルの探索を同時にやるようにすれば&imgte...
-----------------
コメント
- 1-1 どちらもy1y2y3のになるはずです…これくらいあとから読...
- 4-(2)ですが、nの値は関係ないのでしょうか？関係ある気が...
- m log(n/m)もm(log n - log m)でm log nにはならない？同時...
- 4-(2)はn=3なので3次元の平面分割になってます．5は&imgtex...
//#comment
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
