東大 学際情報学府 学際情報学専攻 先端表現情報学コース 専門科目 2012年度 院試 過去問 解答例・解説（全5問）

誤差ベクトルを $$\varepsilon=A\boldsymbol{x}-\boldsymbol{b},\qquad \boldsymbol{x}=\begin{pmatrix}c\\v\end{pmatrix}$$ とおく。微分をとると $$d\varepsilon=A\,d\boldsymbol{x}$$ であるから、ヤコビアンを列ベクトルに対する微分として書けば $$\frac{\partial\varepsilon}{\partial\boldsymbol{x}}=A,\qquad \frac{\partial\varepsilon^{T}}{\partial\boldsymbol{x}}=A^{T}$$ である。

最小化する量はノルムそのものではなく二乗ノルムで考えてよい。すなわち $$J(\boldsymbol{x})=\|\varepsilon\|^2 =(A\boldsymbol{x}-\boldsymbol{b})^T(A\boldsymbol{x}-\boldsymbol{b})$$ を最小化する。勾配は $$\frac{\partial J}{\partial\boldsymbol{x}} =2A^T(A\boldsymbol{x}-\boldsymbol{b})$$ なので、停留条件は $$A^TA\boldsymbol{x}=A^T\boldsymbol{b}$$ である。この解が一意に定まるためには、$A$ の2本の列が一次独立、すなわち $$\operatorname{rank}A=2$$ であればよい。このとき $A^TA$ は正則であり、 $$\boldsymbol{x}=(A^TA)^{-1}A^T\boldsymbol{b}$$ と求まる。

与えられた測定値について $$A= \begin{pmatrix} 1&-1\\ 1&0\\ 1&1\\ 1&2 \end{pmatrix},\qquad \boldsymbol{b}= \begin{pmatrix}1\\0\\-2\\-4\end{pmatrix}$$ である。したがって $$A^TA= \begin{pmatrix} 4&2\\ 2&6 \end{pmatrix},\qquad A^T\boldsymbol{b}= \begin{pmatrix} -5\\-11 \end{pmatrix}.$$ 正規方程式 $$\begin{pmatrix} 4&2\\ 2&6 \end{pmatrix} \begin{pmatrix}c\\v\end{pmatrix} = \begin{pmatrix}-5\\-11\end{pmatrix}$$ を解くと $$c=-\frac{2}{5},\qquad v=-\frac{17}{10}$$ である。よって最小二乗直線は $$y=-\frac{2}{5}-\frac{17}{10}t$$ である。

前半のアルゴリズムは、整列済み部分列に次の要素を後ろから挿入する挿入ソートである。$k$ 回目の挿入では、最大で $k$ 回、最小で1回の比較を行う。

最も計算量が少ないのは、各段階で新しく挿入する値が整列済み部分列の最大値より大きい場合である。つまり、重複を考えないなら入力がすでに小さい順に並んでいる場合である。このとき各 $k$ で1回の比較で挿入位置が決まるので、比較回数は $$\sum_{k=1}^{n-1}1=n-1$$ であり、計算量は $O(n)$ である。

最も計算量が多いのは、各段階で新しく挿入する値が整列済み部分列のどの値よりも小さい場合である。つまり、入力が大きい順に並んでいる場合である。このとき $k$ 回目には $k$ 回の比較が必要なので、 $$\sum_{k=1}^{n-1}k=\frac{n(n-1)}{2}$$ となり、計算量は $O(n^2)$ である。

後半のアルゴリズムは、列を二分してそれぞれを再帰的に整列し、最後に併合するマージソートである。併合に要する比較・代入の計算量を $an+b$ と表せば、$n>2$ で $$T(n)=2T\left(\frac{n}{2}\right)+an+b$$ と書ける。基底条件は、例えば $T(2)=c$ とおけばよい。

$n=2^m$ とおく。漸化式を展開すると $$\begin{aligned} T(n) &=2T(n/2)+an+b\\ &=4T(n/4)+2an+3b\\ &\,\,\vdots\\ &=2^{m-1}T(2)+(m-1)an+(2^{m-1}-1)b. \end{aligned}$$ $m=\log_2 n$ かつ $2^{m-1}=n/2$ なので、支配項は $an\log_2 n$ である。したがって $$T(n)=O(n\log n)$$ である。

時不変線形システムとは、線形性と時不変性をともに満たすシステムである。入力 $x_1,x_2$ に対する出力をそれぞれ $y_1,y_2$ とすると、任意の定数 $\alpha,\beta$ について入力 $\alpha x_1+\beta x_2$ に対する出力が $\alpha y_1+\beta y_2$ になることが線形性である。また、入力を時間だけ遅らせたとき、出力も同じ時間だけ遅れることが時不変性である。

未知の時不変線形システムのインパルス応答 $h$ は、理想的にはインパルス $\delta$ を入力し、その出力を測定すれば得られる。実際の測定では有限幅の短いパルス、最大長系列、チャープ信号などを入力し、入出力の相関や逆フィルタ処理によって $h$ を推定する。離散時間なら $$y[n]=\sum_m h[m]x[n-m]$$ であるから、既知入力 $x$ と出力 $y$ から畳み込み方程式を解く方法でもよい。

周波数応答は、インパルス応答のフーリエ変換として $$H(\omega)=\mathcal{F}\{h(t)\}$$ または離散時間では $$H(e^{j\omega})=\sum_n h[n]e^{-j\omega n}$$ により求められる。実験的には周波数を変えた正弦波を入力し、定常状態の出力振幅比と位相差を測定する。あるいは入力 $X(\omega)$ と出力 $Y(\omega)$ を測って $$H(\omega)=\frac{Y(\omega)}{X(\omega)}$$ と求める。ただし $X(\omega)=0$ となる周波数では直接の割り算はできない。

2つの情報源 $A,B$ の相互情報量は、一方を観測することによって他方の不確かさがどれだけ減るかを表す量である。離散確率変数として書けば $$I(A;B)=\sum_{a,b}p(a,b)\log\frac{p(a,b)}{p(a)p(b)} =H(A)-H(A|B) =H(B)-H(B|A)$$ である。独立なら $I(A;B)=0$、完全に対応していれば、より小さい方のエントロピーまで大きくなり得る。

通信系では、送信信号を $A$、受信信号を $B$ とすると、相互情報量は受信信号から送信信号について得られる情報量である。雑音、減衰、歪み、干渉、帯域制限、量子化、符号化方式、変調方式、送信信号の確率分布などが相互情報量を変える。一般に $$0\le I(A;B)\le \min\{H(A),H(B)\}$$ であり、通信路が送信信号と無関係な出力しか与えない場合は0、無雑音で一対一に復元できる場合は $H(A)$ に達する。

応力とは、物体内部のある断面に作用する内力を、その断面積で割った量である。断面に垂直な荷重 $P$ が断面積 $A$ に作用するとき、平均垂直応力は $$\sigma=\frac{P}{A}$$ で表される。断面に沿う方向の力を考える場合はせん断応力となる。

棒の変形前の長さを $h_0$、変形後の長さを $h$ とすると、微小変形における工学的な垂直ひずみは $$\varepsilon=\frac{h-h_0}{h_0}$$ である。引張であれば $h>h_0$ なので正、圧縮であれば負である。

軟鋼の引張試験で得られる典型的な応力ひずみ線図は、初期の直線的な弾性域、上降伏点・下降伏点、降伏棚、加工硬化による応力上昇、最大応力、くびれを伴う破断へと進む。

引張強さは、引張試験中に記録された最大荷重を試験前の断面積で割った最大の工学応力である。応力ひずみ線図では、加工硬化後に到達する山の頂点に対応する。

弾性域では、荷重を除けば変形はほぼ元に戻る。特に比例限度内ではフックの法則 $$\sigma=E\varepsilon$$ が成り立ち、この比例係数 $E$ が弾性率である。塑性域では、降伏後に永久ひずみが残る。降伏とは、応力の増加が小さくても塑性変形が進み始める現象であり、軟鋼では明瞭な降伏点や降伏棚として現れやすい。

黄時間は、青表示から赤表示へ移る前に、交差点へ接近中の車両へ停止準備を促すための時間である。同時に、停止線直前にいて安全に停止できない車両が交差点内へ進入し、通過を完了する余地を与える。

全赤時間は、すべての流入方向を赤にして、すでに交差点内に入った車両や歩行者を交差領域から退出させるための時間である。次の現示の交通流と前の現示の残留交通流が交錯しないようにする安全余裕である。

黄時間や全赤時間が短すぎると、停止できない車両が赤信号で交差点に入る、交差点内に残った車両と次現示の車両が衝突する、急停止による追突が起こるといった危険が増える。黄時間が長すぎると、運転者が黄信号でも進入できると期待して速度を上げる、赤への切り替わりが読みにくくなる、交差点の処理容量が下がる。全赤時間が長すぎると、有効青時間が減って遅れ時間と待ち行列が増え、信号遵守の意欲も下がりやすい。

スマートグリッドとは、電力網に通信・計測・制御技術を組み込み、発電、蓄電、需要、送配電を双方向に調整する電力システムである。太陽光や風力などの分散型電源、蓄電池、電気自動車、需要応答を統合し、需給の安定化と効率化を図る。

都市防災上は、災害時に停電範囲を検知して復旧を早められること、分散電源や蓄電池を用いて病院・避難所・通信設備などへ優先的に給電できること、地域マイクログリッドとして系統から切り離して運転できることが利点である。さらに、需要を抑制して非常時の電力を重要負荷へ回す、電気自動車を移動型蓄電池として使う、再生可能エネルギーを地域内で活用する、といった運用が可能になる。