院試過去問 2006年度 専門科目 数理
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
] [
リンク元
]
開始行:
[[院試勉強会]]
http://www.i.u-tokyo.ac.jp/edu/course/mi/admission.shtml~
http://www.i.u-tokyo.ac.jp/edu/course/mi/pdf/2006suuri-j....
- 第一問~
&imgtex($n\times n$);正方行列&imgtex($C_n$);を以下のよう...
&imgtex(\begin{align*}C_n=\begin{pmatrix}1&1&0&\dots&0\\0...
--(1)&imgtex($n$);が偶数ならば，&imgtex($C_n$);は逆行列を...
---&imgtex($n$);が偶数ならば，~
&imgtex(\begin{align*}\begin{pmatrix}1&1&0&\dots&0\\0&1&1...
より逆行列を持たない．
--(2)&imgtex($n$);が奇数ならば，&imgtex($C_n$);の列ベクト...
---&imgtex($C_1=1$);．&imgtex($n$);が3以上の奇数のとき，~
&imgtex(\begin{align*}|C_{n}|&=\left|\begin{matrix}1&1&0&...
よって，線型独立である．
--(3)&imgtex($C_n$);が逆行列を持つならば,
&imgtex($2C_n^{-1}$);は整数行列であることを示せ．
---&imgtex($C_n$);は整数行列なので，余因子行列&imgtex($\t...
--(4)無向グラフ&imgtex($G$);の枝の部分集合で，対応する&im...
---(1)(2)より全域木に1本付け加えて奇数ループを一つつくれ...
よって，~
&imgtex($\{e_1,e_2,e_3,e_4,e_5\},\{e_1,e_2,e_3,e_4,e_6\},...
の4通り．
----
-第2問~
--実数の組&imgtex($(x_i,y_i)$);からなるデータに対して&img...
&imgtex($\beta_1,\beta_2$);の推定量&imgtex($\hat{\beta}_1...
&imgtex(\begin{align*}\bm{y}=\begin{pmatrix}y_1\\y_2\\\vd...
とおく．ただし，&imgtex($X$);の階数は2であるものとする．...
また，~
&imgtex(\begin{align*}X\hat{\bm{\beta}}=P\bm{y}\end{align...
を満たす，&imgtex($X$);により決まる&imgtex($n\times n$);...
---&imgtex($e=(\bm{y}-X\hat{\bm{\beta}})^{\top}(\bm{y}-X\...
&imgtex(\begin{align*}\frac{\partial e}{\partial \hat{\be...
が成立する．この連立方程式を解けば，~
&imgtex(\begin{align*}\hat{\beta}_1&=\frac{n\sum_{i=1}^n ...
これより，~
&imgtex(\begin{align*}P_{ij}=\frac{nx_ix_j-(\sum_{k=1}^n ...
&imgtex($P_{ij}=P_{ji}$);は明らか．~
&imgtex($(P^2)_{ij}=\sum_{k=0}^n P_{ik}P_{kj}=P_{ij}$);よ...
~
このように解くと&imgtex($P^2$);の計算で死ぬことになるので...
&imgtex($e=|\bm{y}-X\hat{\bm{\beta}}|^2$);を最小化するの...
さらに左から&imgtex($X$);を掛けると，&imgtex($X\hat{\beta...
これより，
&imgtex($P^2=X(X^{\top}X)^{-1}X^{\top}X(X^{\top}X)^{-1}X^...
&imgtex($P^{\top}=\{X(X^{\top}X)^{-1}X^{\top}\}^{\top}=(X...
--(2)(1)で考えた実数の組&imgtex($(x_i,y_i)$);からなるデー...
&imgtex(\begin{align*}\bm{y}=\begin{pmatrix}y_1\\y_2\\\vd...
とおく．ただし，&imgtex($Z$);の階数は3であるものとする．...
&imgtex(\begin{align*}Z\hat{\bm{\gamma}}=Q\bm{y}\end{alig...
を満たす&imgtex($Z$);により決まる&imgtex($n\times n$);行...
&imgtex(\[QP=PQ=P\]);~
が成立することを示せ．
---(1)と同様の議論により，~
&imgtex(\[Q=Z(Z^{\top}Z)^{-1}Z^{\top}\]);~
である．ここで，&imgtex(\[X=Z\begin{pmatrix}0&0\\1&0\\0&1...
であるから，~
&imgtex(\[P=ZW(X^{\top}X)^{-1}W^{\top}Z,Q=Z(Z^{\top}Z)^{-...
//&imgtex(\begin{align*}PQ&=X(X^{top}X)^{-1}X^{\top}Z(Z^{...
また，&imgtex($P=P^{\top}=(PQ)^{\top}=Q^{\top}P^{\top}=QP...
--(3) (1)で考えた実数の組&imgtex($(x_i,y_i)$);からなるデ...
&imgtex($y_1,\dots,y_n$);が互いに独立で，各&imgtex($y_i$)...
&imgtex(\[\hat{b}_1=\hat{\beta}_1,\ \hat{b}_2=\hat{\beta}...
が成立することを示せ．
---誤差の尤度は~
&imgtex(\begin{align*}L=\prod_{i=1}^n\frac{1}{\sqrt{2\pi\...
であり，対数をとると，~
&imgtex(\begin{align*}\log L=\sum_{i=1}^n\log \frac{1}{\s...
&imgtex($\hat{b}_1,\hat{b}_2$);で微分すると，~
&imgtex(\begin{align*}\sum_{i=1}^n(y_i-\hat{b}_1x-\hat{b}...
と(1)と同じ式が出てくるので，&imgtex($\hat{b}_1=\hat{\bet...
--(4)[[応用統計学]]の復習をせよ．
----
-第3問~
xy-平面状の2点&imgtex($P_1=(0,0),\ P_2=(a,0)\ (a>0)$);か...
&imgtex($P_1$);からの成長は速さ1，&imgtex($P_2$);からの成...
二つの結晶の成長はぶつかったところで止まり，速く成長する...
--(1)&imgtex($x\ge 0$);の領域にできる境界曲線&imgtex($r(\...
---3平方の定理より~
&imgtex($kr(\theta)=\sqrt{(a-r(\theta)\cos\theta)^2+(r(\t...
であるから，~
&imgtex(\[r(\theta)=\frac{-a\cos\theta+a\sqrt{\cos^2\thet...
--(2)極座標表示された一般の曲線&imgtex($(r(\theta),\theta...
---&imgtex(\begin{align*}\int \sqrt{dx^2+dy^2}&=\int\sqrt...
よって，&imgtex($\int_{\theta_1}^{\theta_2}\sqrt{r^2+r'(\...
--(3)&imgtex($x\le 0,y\ge 0$);の領域において，&imgtex($r(...
---&imgtex($kr(\theta)=a\sqrt{\frac{k^2}{k^2-1}}+\int_{\p...
--(4)&imgtex($r(\theta)=\alpha e^{\beta\theta}$);の形の関...
(3)で求めた方程式を満たすものを求めよ．
---(3)の式に代入して~
&imgtex(\[k\alpha e^{\beta\theta}=a\sqrt{\frac{k^2}{k^2-1...
これを解くと~
&imgtex(\[\alpha=\frac{a}{\sqrt{k^2-1}}e^{-\frac{\pi}{2\s...
----
-第4問~
次のようなニューロンモデルを考える．~
容量&imgtex($C$);のコンデンサ,抵抗値&imgtex($R$);の抵抗，
電流源&imgtex($I(t)$);からなる線型電気回路を考える．この...
&imgtex(\[C\frac{dV(t)}{dt}+\frac{V(t)}{R}=I(t)\]);~
となる．時刻&imgtex($T$);で&imgtex($V_{\mathrm{th}}(>0)$)...
--(1)&imgtex($I(t)$);をステップ電流とするときの&imgtex($V...
また放電が生じないための&imgtex($I_0$);の条件を求めよ．
さらに，放電を生じる場合，最初の放電時刻&imgtex($T$);を&i...
---与えられた微分方程式をラプラス変換すると，~
&imgtex($(CRs+1)\mathcal{L}[V]=\frac{RI_0}{s}$);~
これより，~
&imgtex(\begin{align*}V&=\mathcal{L}^{-1}\left[\frac{RI_0...
&imgtex($V(t)\to RI_0\ (t\to\infty)$);なので，放電を生じ...
また，放電を生じる場合，最初の放電時刻は&imgtex($V_{th}=I...
&imgtex(\[T=CR\log\frac{I_0R}{I_0R-V_{th}}.\]);
図は&imgtex($0$);から&imgtex($V_{th}/R$);に漸近していくも...
--(2)インパルス電流&imgtex($I(t)=\delta(t-T_0)$);を入れた...
---&imgtex($t'=t-T_0$);とおきラプラス変換すると，&imgtex(...
&imgtex(\begin{align*}V(t'+T_0)&=\mathcal{L}^{-1}\left[\f...
--(3)&imgtex($I(t)=\beta\sum_{j=1}^{\infty}\delta(t-jT_0)...
を入力する場合を考える．十分長い時間がたった後の定常状態...
その最大値と最小値を求めよ．また，放電を生じるための&imgt...
さらに，放電を生じる場合，最初の放電時刻&imgtex($T$);を求...
---最大値を&imgtex($M$);，最小値を&imgtex($m$);とする．す...
&imgtex(\begin{align*}M-m&=\frac{\beta}{C},\\m&=Me^{-\fra...
これより，~
&imgtex(\begin{align*}M=\frac{\beta}{C(1-e^{-\frac{T_0}{C...
放電を生じるのは&imgtex($M\ge V_{th}$);，すなわち，~
&imgtex(\[V_{th}\le \frac{\beta}{C(1-e^{-\frac{T_0}{CR}})...
&imgtex($n$);個目のインパルスが入ったときの電圧&imgtex($V...
&imgtex(\begin{align*}V_n&=V_{n-1}e^{-\frac{T_0}{CR}}+\fr...
と表せるので，~
&imgtex(\[V_n=\frac{\beta}{C}\frac{1-e^{-\frac{nT_0}{CR}}...
これが，初めて&imgtex($V_{th}$);を超えるときなので，~
&imgtex(\begin{align*}V_{th}&\gtreqless \frac{\beta}{C}\f...
よって，最初の放電時刻は~
&imgtex(\[T_0\left\lceil\frac{CR}{T_0}\log\frac{1}{1-\fra...
--(4) 電流源&imgtex($I(t)$);が微分方程式~
&imgtex(\[\frac{d^2 I(t)}{dt^2}+2\gamma\frac{dI(t)}{dt}+\...
に従うとき，初期条件&imgtex($I(0)=0,\ \frac{dI}{dt}(0)=K$...
次に，この&imgtex($I(t)$);を入力したときの&imgtex($V(t)$)...
---&imgtex($(D+\gamma)^2I(t)=0$);より，&imgtex($I(t)=C_1e...
&imgtex(\[I(t)=Kt e^{-\gamma t}.\]);~
また，&imgtex($C\frac{dV(t)}{dt}+\frac{V(t)}{R}=I(t)$);を...
&imgtex(\begin{align*}(CRs+1)\mathcal{L}[V]&=\frac{RK}{(s...
なので，&imgtex($\gamma=\frac{1}{CR}$);のときは~
&imgtex(\[V(t)=\frac{K}{C}\frac{t^2}{2}e^{-\gamma t}\]);...
&imgtex(\[V(t)=\frac{-RKt}{1-CR\gamma}e^{-\gamma t}-\frac...
----
-第5問~
コインを適当に組み合わせて，その額を支払うことを考える．~
--(1)コイン支払機に1両，2両，5両のコインが無限にあると仮...
任意の請求額&imgtex($N$);両に対して，貪欲アルゴリズムを適...
コインの支払い枚数が最小となることを示せ．
---2両を5枚出すより5両を2枚出す方が，1両を2枚出すより2両...
| |1|2|5|合計|
|1|1|0|0|1|
|2|0|1|0|1|
|3|1|1|0|2|
|4|0|2|0|2|
|5|0|0|1|1|
|6|1|0|1|2|
|7|0|1|1|2|
|8|1|1|1|3|
|9|0|2|1|3|
のように貪欲にやればうまくいくことが分かるので，題意は示...
--(2)コイン支払機に1両，4両，5両の3種類のコインのみがある...
貪欲アルゴリズムでは，コインの支払い枚数が必ずしも最小に...
--- 8両を支払う時，貪欲にやれば5両が1枚,1両が3枚と4枚も支...
--コイン支払機に1両，4両，5両の3種類のコインが無限にある...
任意の請求額&imgtex($N$);量の支払いに要するコインの最小枚...
---&imgtex($n$);両を支払うのに必要な最小枚数を&imgtex($a_...
&imgtex($a_0=0$);，&imgtex($a_n=\infty (n<0)$);として~
&imgtex(\begin{align*}a_n=\min(a_{n-1},a_{n-4},a_{n-5})+1...
によって，&imgtex($1$);から&imgtex($N$);までを埋めればよ...
(1)と同様の議論により&imgtex($1\times 1+4\times 4=17$);両...
--(4)合計額&imgtex($N$);両のコインをコイン支払機に入れる．
支払機に入れたコインの中で一番高額のものを&imgtex($m$);両...
&imgtex($j$);両コインの枚数を&imgtex($c_j$);とする．
このとき，合計額が&imgtex($N$);両以下の&imgtex($K$);回の...
&imgtex($m\le \lceil N/K\rceil$);であり，かつ~
&imgtex(\begin{align*}\sum_{j=1}^i jc_j\ge Ki\ (i=1,2,\do...
でなければならないことを示せ．
---&imgtex($\lfloor N/K \rfloor$);と&imgtex($\lceil N/K\r...
また，&imgtex($i$);両を&imgtex($K$);回払うためには，&imgt...
&imgtex(\[\sum_{j=1}^i jc_j\ge Ki.\]);~
--(5)(*)の条件が成立するときに，&imgtex($N$);両以下の任意...
貪欲アルゴリズムで支払いを行う．
その直後の支払機中で最も高額なコインの額を&imgtex($l$);両...
残っている&imgtex($j$);両のコインの枚数を&imgtex($d_j$);...
このとき，~
&imgtex(\[\sum_{j=1}^i jd_j\ge (K-1)i\ (i=1,2,\dots ,l-1)...
となることを示せ．
このことから，(*)が成立するときに，合計額が&imgtex($N$);...
---帰納法で示す．貪欲に&imgtex($l$);両まで支払ったとき，...
貪欲に&imgtex($s$);両まで払ったとき，&imgtex($\sum_{j=1}^...
1枚以上払うならば残りの支払額は&imgtex($s-2$);両以下なの...
&imgtex($s-1$);両を払わないとき，&imgtex($\sum_{j=1}^{s-2...
また，(*)が成立するとき合計額が&imgtex($N$);両以下の&imgt...
上での議論のように&imgtex($K=1$);のとき，すなわち&imgtex(...
任意の&imgtex($N$);両以下の請求額を支払うことができる．
さらに帰納法の仮定により，任意の&imgtex($M$);に対して，合...
--[(5)別解]
&imgtex($d_j\neq0$);を満たす添え字&imgtex($j$);を大きい順...
貪欲アルゴリズムの性質より~
&imgtex(\[ \sum_{j=1}^{l_i-1}j(c_j-d_j) \leq l_i-1\]);~
である。なぜなら&imgtex($d_{l_i}\neq 0$);より、&imgtex($l...
&imgtex($l_{i}$);両のコインはもう使えない状況である。つま...
&imgtex($1,2,\ldots,l_{i}-1$);両のコインで支払うべき額は&...
上式を用いて~
&imgtex(\begin{align*} \sum_{j=1}^{l_i-1}jd_j &\geq \sum_...
そして、&imgtex($l_i > l > l_{i+1}$);なる&imgtex($l$);に...
&imgtex(\[ \sum_{j=1}^{l-1} jd_j = \sum_{j=1}^{l_i-1}jd_j...
よって、&imgtex($m=l_i-1,l_i-2,\ldots,l_{i+1}$);については~
&imgtex(\[ \sum_{j=1}^{m}jd_j \geq (K-1)m\]);~
が示せた。同様の議論がどの&imgtex($i$);についても成立する...
&imgtex(\[ \sum_{j=1}^ijd_j \geq (K-1)i , \forall i = 1,2...
が示せた。
また、~
&imgtex(\[ K(l-1)\leq \sum_{j=1}^{l-1} jc_j< \sum_{j=1}^l...
より~
&imgtex(\[ l\leq \left\lceil \frac{\sum_{j=1}^ljd_j}{K-1}...
も成立。
-----------------
コメント~
-第3問の曲線の長さって、&imgtex($\int\sqrt{r^2+r'(\theta)...
-直しました． -- [[yambi]] &new{2008-08-10 (日) 02:34:01};
- いまさら感満載ですが、第4問の&imgtex($I(t)$);が違ってる...
- 直しました．また計算間違いしている可能性が高いのでその...
- 第３問ですが、(1)は結局余弦定理ですよね？ それで、計算...
- (4)同じくそう思います。typoかケアレスミスかな。直してお...
#comment
終了行:
[[院試勉強会]]
http://www.i.u-tokyo.ac.jp/edu/course/mi/admission.shtml~
http://www.i.u-tokyo.ac.jp/edu/course/mi/pdf/2006suuri-j....
- 第一問~
&imgtex($n\times n$);正方行列&imgtex($C_n$);を以下のよう...
&imgtex(\begin{align*}C_n=\begin{pmatrix}1&1&0&\dots&0\\0...
--(1)&imgtex($n$);が偶数ならば，&imgtex($C_n$);は逆行列を...
---&imgtex($n$);が偶数ならば，~
&imgtex(\begin{align*}\begin{pmatrix}1&1&0&\dots&0\\0&1&1...
より逆行列を持たない．
--(2)&imgtex($n$);が奇数ならば，&imgtex($C_n$);の列ベクト...
---&imgtex($C_1=1$);．&imgtex($n$);が3以上の奇数のとき，~
&imgtex(\begin{align*}|C_{n}|&=\left|\begin{matrix}1&1&0&...
よって，線型独立である．
--(3)&imgtex($C_n$);が逆行列を持つならば,
&imgtex($2C_n^{-1}$);は整数行列であることを示せ．
---&imgtex($C_n$);は整数行列なので，余因子行列&imgtex($\t...
--(4)無向グラフ&imgtex($G$);の枝の部分集合で，対応する&im...
---(1)(2)より全域木に1本付け加えて奇数ループを一つつくれ...
よって，~
&imgtex($\{e_1,e_2,e_3,e_4,e_5\},\{e_1,e_2,e_3,e_4,e_6\},...
の4通り．
----
-第2問~
--実数の組&imgtex($(x_i,y_i)$);からなるデータに対して&img...
&imgtex($\beta_1,\beta_2$);の推定量&imgtex($\hat{\beta}_1...
&imgtex(\begin{align*}\bm{y}=\begin{pmatrix}y_1\\y_2\\\vd...
とおく．ただし，&imgtex($X$);の階数は2であるものとする．...
また，~
&imgtex(\begin{align*}X\hat{\bm{\beta}}=P\bm{y}\end{align...
を満たす，&imgtex($X$);により決まる&imgtex($n\times n$);...
---&imgtex($e=(\bm{y}-X\hat{\bm{\beta}})^{\top}(\bm{y}-X\...
&imgtex(\begin{align*}\frac{\partial e}{\partial \hat{\be...
が成立する．この連立方程式を解けば，~
&imgtex(\begin{align*}\hat{\beta}_1&=\frac{n\sum_{i=1}^n ...
これより，~
&imgtex(\begin{align*}P_{ij}=\frac{nx_ix_j-(\sum_{k=1}^n ...
&imgtex($P_{ij}=P_{ji}$);は明らか．~
&imgtex($(P^2)_{ij}=\sum_{k=0}^n P_{ik}P_{kj}=P_{ij}$);よ...
~
このように解くと&imgtex($P^2$);の計算で死ぬことになるので...
&imgtex($e=|\bm{y}-X\hat{\bm{\beta}}|^2$);を最小化するの...
さらに左から&imgtex($X$);を掛けると，&imgtex($X\hat{\beta...
これより，
&imgtex($P^2=X(X^{\top}X)^{-1}X^{\top}X(X^{\top}X)^{-1}X^...
&imgtex($P^{\top}=\{X(X^{\top}X)^{-1}X^{\top}\}^{\top}=(X...
--(2)(1)で考えた実数の組&imgtex($(x_i,y_i)$);からなるデー...
&imgtex(\begin{align*}\bm{y}=\begin{pmatrix}y_1\\y_2\\\vd...
とおく．ただし，&imgtex($Z$);の階数は3であるものとする．...
&imgtex(\begin{align*}Z\hat{\bm{\gamma}}=Q\bm{y}\end{alig...
を満たす&imgtex($Z$);により決まる&imgtex($n\times n$);行...
&imgtex(\[QP=PQ=P\]);~
が成立することを示せ．
---(1)と同様の議論により，~
&imgtex(\[Q=Z(Z^{\top}Z)^{-1}Z^{\top}\]);~
である．ここで，&imgtex(\[X=Z\begin{pmatrix}0&0\\1&0\\0&1...
であるから，~
&imgtex(\[P=ZW(X^{\top}X)^{-1}W^{\top}Z,Q=Z(Z^{\top}Z)^{-...
//&imgtex(\begin{align*}PQ&=X(X^{top}X)^{-1}X^{\top}Z(Z^{...
また，&imgtex($P=P^{\top}=(PQ)^{\top}=Q^{\top}P^{\top}=QP...
--(3) (1)で考えた実数の組&imgtex($(x_i,y_i)$);からなるデ...
&imgtex($y_1,\dots,y_n$);が互いに独立で，各&imgtex($y_i$)...
&imgtex(\[\hat{b}_1=\hat{\beta}_1,\ \hat{b}_2=\hat{\beta}...
が成立することを示せ．
---誤差の尤度は~
&imgtex(\begin{align*}L=\prod_{i=1}^n\frac{1}{\sqrt{2\pi\...
であり，対数をとると，~
&imgtex(\begin{align*}\log L=\sum_{i=1}^n\log \frac{1}{\s...
&imgtex($\hat{b}_1,\hat{b}_2$);で微分すると，~
&imgtex(\begin{align*}\sum_{i=1}^n(y_i-\hat{b}_1x-\hat{b}...
と(1)と同じ式が出てくるので，&imgtex($\hat{b}_1=\hat{\bet...
--(4)[[応用統計学]]の復習をせよ．
----
-第3問~
xy-平面状の2点&imgtex($P_1=(0,0),\ P_2=(a,0)\ (a>0)$);か...
&imgtex($P_1$);からの成長は速さ1，&imgtex($P_2$);からの成...
二つの結晶の成長はぶつかったところで止まり，速く成長する...
--(1)&imgtex($x\ge 0$);の領域にできる境界曲線&imgtex($r(\...
---3平方の定理より~
&imgtex($kr(\theta)=\sqrt{(a-r(\theta)\cos\theta)^2+(r(\t...
であるから，~
&imgtex(\[r(\theta)=\frac{-a\cos\theta+a\sqrt{\cos^2\thet...
--(2)極座標表示された一般の曲線&imgtex($(r(\theta),\theta...
---&imgtex(\begin{align*}\int \sqrt{dx^2+dy^2}&=\int\sqrt...
よって，&imgtex($\int_{\theta_1}^{\theta_2}\sqrt{r^2+r'(\...
--(3)&imgtex($x\le 0,y\ge 0$);の領域において，&imgtex($r(...
---&imgtex($kr(\theta)=a\sqrt{\frac{k^2}{k^2-1}}+\int_{\p...
--(4)&imgtex($r(\theta)=\alpha e^{\beta\theta}$);の形の関...
(3)で求めた方程式を満たすものを求めよ．
---(3)の式に代入して~
&imgtex(\[k\alpha e^{\beta\theta}=a\sqrt{\frac{k^2}{k^2-1...
これを解くと~
&imgtex(\[\alpha=\frac{a}{\sqrt{k^2-1}}e^{-\frac{\pi}{2\s...
----
-第4問~
次のようなニューロンモデルを考える．~
容量&imgtex($C$);のコンデンサ,抵抗値&imgtex($R$);の抵抗，
電流源&imgtex($I(t)$);からなる線型電気回路を考える．この...
&imgtex(\[C\frac{dV(t)}{dt}+\frac{V(t)}{R}=I(t)\]);~
となる．時刻&imgtex($T$);で&imgtex($V_{\mathrm{th}}(>0)$)...
--(1)&imgtex($I(t)$);をステップ電流とするときの&imgtex($V...
また放電が生じないための&imgtex($I_0$);の条件を求めよ．
さらに，放電を生じる場合，最初の放電時刻&imgtex($T$);を&i...
---与えられた微分方程式をラプラス変換すると，~
&imgtex($(CRs+1)\mathcal{L}[V]=\frac{RI_0}{s}$);~
これより，~
&imgtex(\begin{align*}V&=\mathcal{L}^{-1}\left[\frac{RI_0...
&imgtex($V(t)\to RI_0\ (t\to\infty)$);なので，放電を生じ...
また，放電を生じる場合，最初の放電時刻は&imgtex($V_{th}=I...
&imgtex(\[T=CR\log\frac{I_0R}{I_0R-V_{th}}.\]);
図は&imgtex($0$);から&imgtex($V_{th}/R$);に漸近していくも...
--(2)インパルス電流&imgtex($I(t)=\delta(t-T_0)$);を入れた...
---&imgtex($t'=t-T_0$);とおきラプラス変換すると，&imgtex(...
&imgtex(\begin{align*}V(t'+T_0)&=\mathcal{L}^{-1}\left[\f...
--(3)&imgtex($I(t)=\beta\sum_{j=1}^{\infty}\delta(t-jT_0)...
を入力する場合を考える．十分長い時間がたった後の定常状態...
その最大値と最小値を求めよ．また，放電を生じるための&imgt...
さらに，放電を生じる場合，最初の放電時刻&imgtex($T$);を求...
---最大値を&imgtex($M$);，最小値を&imgtex($m$);とする．す...
&imgtex(\begin{align*}M-m&=\frac{\beta}{C},\\m&=Me^{-\fra...
これより，~
&imgtex(\begin{align*}M=\frac{\beta}{C(1-e^{-\frac{T_0}{C...
放電を生じるのは&imgtex($M\ge V_{th}$);，すなわち，~
&imgtex(\[V_{th}\le \frac{\beta}{C(1-e^{-\frac{T_0}{CR}})...
&imgtex($n$);個目のインパルスが入ったときの電圧&imgtex($V...
&imgtex(\begin{align*}V_n&=V_{n-1}e^{-\frac{T_0}{CR}}+\fr...
と表せるので，~
&imgtex(\[V_n=\frac{\beta}{C}\frac{1-e^{-\frac{nT_0}{CR}}...
これが，初めて&imgtex($V_{th}$);を超えるときなので，~
&imgtex(\begin{align*}V_{th}&\gtreqless \frac{\beta}{C}\f...
よって，最初の放電時刻は~
&imgtex(\[T_0\left\lceil\frac{CR}{T_0}\log\frac{1}{1-\fra...
--(4) 電流源&imgtex($I(t)$);が微分方程式~
&imgtex(\[\frac{d^2 I(t)}{dt^2}+2\gamma\frac{dI(t)}{dt}+\...
に従うとき，初期条件&imgtex($I(0)=0,\ \frac{dI}{dt}(0)=K$...
次に，この&imgtex($I(t)$);を入力したときの&imgtex($V(t)$)...
---&imgtex($(D+\gamma)^2I(t)=0$);より，&imgtex($I(t)=C_1e...
&imgtex(\[I(t)=Kt e^{-\gamma t}.\]);~
また，&imgtex($C\frac{dV(t)}{dt}+\frac{V(t)}{R}=I(t)$);を...
&imgtex(\begin{align*}(CRs+1)\mathcal{L}[V]&=\frac{RK}{(s...
なので，&imgtex($\gamma=\frac{1}{CR}$);のときは~
&imgtex(\[V(t)=\frac{K}{C}\frac{t^2}{2}e^{-\gamma t}\]);...
&imgtex(\[V(t)=\frac{-RKt}{1-CR\gamma}e^{-\gamma t}-\frac...
----
-第5問~
コインを適当に組み合わせて，その額を支払うことを考える．~
--(1)コイン支払機に1両，2両，5両のコインが無限にあると仮...
任意の請求額&imgtex($N$);両に対して，貪欲アルゴリズムを適...
コインの支払い枚数が最小となることを示せ．
---2両を5枚出すより5両を2枚出す方が，1両を2枚出すより2両...
| |1|2|5|合計|
|1|1|0|0|1|
|2|0|1|0|1|
|3|1|1|0|2|
|4|0|2|0|2|
|5|0|0|1|1|
|6|1|0|1|2|
|7|0|1|1|2|
|8|1|1|1|3|
|9|0|2|1|3|
のように貪欲にやればうまくいくことが分かるので，題意は示...
--(2)コイン支払機に1両，4両，5両の3種類のコインのみがある...
貪欲アルゴリズムでは，コインの支払い枚数が必ずしも最小に...
--- 8両を支払う時，貪欲にやれば5両が1枚,1両が3枚と4枚も支...
--コイン支払機に1両，4両，5両の3種類のコインが無限にある...
任意の請求額&imgtex($N$);量の支払いに要するコインの最小枚...
---&imgtex($n$);両を支払うのに必要な最小枚数を&imgtex($a_...
&imgtex($a_0=0$);，&imgtex($a_n=\infty (n<0)$);として~
&imgtex(\begin{align*}a_n=\min(a_{n-1},a_{n-4},a_{n-5})+1...
によって，&imgtex($1$);から&imgtex($N$);までを埋めればよ...
(1)と同様の議論により&imgtex($1\times 1+4\times 4=17$);両...
--(4)合計額&imgtex($N$);両のコインをコイン支払機に入れる．
支払機に入れたコインの中で一番高額のものを&imgtex($m$);両...
&imgtex($j$);両コインの枚数を&imgtex($c_j$);とする．
このとき，合計額が&imgtex($N$);両以下の&imgtex($K$);回の...
&imgtex($m\le \lceil N/K\rceil$);であり，かつ~
&imgtex(\begin{align*}\sum_{j=1}^i jc_j\ge Ki\ (i=1,2,\do...
でなければならないことを示せ．
---&imgtex($\lfloor N/K \rfloor$);と&imgtex($\lceil N/K\r...
また，&imgtex($i$);両を&imgtex($K$);回払うためには，&imgt...
&imgtex(\[\sum_{j=1}^i jc_j\ge Ki.\]);~
--(5)(*)の条件が成立するときに，&imgtex($N$);両以下の任意...
貪欲アルゴリズムで支払いを行う．
その直後の支払機中で最も高額なコインの額を&imgtex($l$);両...
残っている&imgtex($j$);両のコインの枚数を&imgtex($d_j$);...
このとき，~
&imgtex(\[\sum_{j=1}^i jd_j\ge (K-1)i\ (i=1,2,\dots ,l-1)...
となることを示せ．
このことから，(*)が成立するときに，合計額が&imgtex($N$);...
---帰納法で示す．貪欲に&imgtex($l$);両まで支払ったとき，...
貪欲に&imgtex($s$);両まで払ったとき，&imgtex($\sum_{j=1}^...
1枚以上払うならば残りの支払額は&imgtex($s-2$);両以下なの...
&imgtex($s-1$);両を払わないとき，&imgtex($\sum_{j=1}^{s-2...
また，(*)が成立するとき合計額が&imgtex($N$);両以下の&imgt...
上での議論のように&imgtex($K=1$);のとき，すなわち&imgtex(...
任意の&imgtex($N$);両以下の請求額を支払うことができる．
さらに帰納法の仮定により，任意の&imgtex($M$);に対して，合...
--[(5)別解]
&imgtex($d_j\neq0$);を満たす添え字&imgtex($j$);を大きい順...
貪欲アルゴリズムの性質より~
&imgtex(\[ \sum_{j=1}^{l_i-1}j(c_j-d_j) \leq l_i-1\]);~
である。なぜなら&imgtex($d_{l_i}\neq 0$);より、&imgtex($l...
&imgtex($l_{i}$);両のコインはもう使えない状況である。つま...
&imgtex($1,2,\ldots,l_{i}-1$);両のコインで支払うべき額は&...
上式を用いて~
&imgtex(\begin{align*} \sum_{j=1}^{l_i-1}jd_j &\geq \sum_...
そして、&imgtex($l_i > l > l_{i+1}$);なる&imgtex($l$);に...
&imgtex(\[ \sum_{j=1}^{l-1} jd_j = \sum_{j=1}^{l_i-1}jd_j...
よって、&imgtex($m=l_i-1,l_i-2,\ldots,l_{i+1}$);については~
&imgtex(\[ \sum_{j=1}^{m}jd_j \geq (K-1)m\]);~
が示せた。同様の議論がどの&imgtex($i$);についても成立する...
&imgtex(\[ \sum_{j=1}^ijd_j \geq (K-1)i , \forall i = 1,2...
が示せた。
また、~
&imgtex(\[ K(l-1)\leq \sum_{j=1}^{l-1} jc_j< \sum_{j=1}^l...
より~
&imgtex(\[ l\leq \left\lceil \frac{\sum_{j=1}^ljd_j}{K-1}...
も成立。
-----------------
コメント~
-第3問の曲線の長さって、&imgtex($\int\sqrt{r^2+r'(\theta)...
-直しました． -- [[yambi]] &new{2008-08-10 (日) 02:34:01};
- いまさら感満載ですが、第4問の&imgtex($I(t)$);が違ってる...
- 直しました．また計算間違いしている可能性が高いのでその...
- 第３問ですが、(1)は結局余弦定理ですよね？ それで、計算...
- (4)同じくそう思います。typoかケアレスミスかな。直してお...
#comment
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
