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

行列を $$A=\begin{pmatrix}0.8&0.3\\0.2&0.7\end{pmatrix} = \begin{pmatrix}4/5&3/10\\1/5&7/10\end{pmatrix}$$ とおく。固有値は $$\det(A-\lambda I) = \begin{vmatrix} 0.8-\lambda&0.3\\ 0.2&0.7-\lambda \end{vmatrix} = \lambda^2-1.5\lambda+0.5$$ の解である。したがって $$\lambda_1=1,\qquad \lambda_2=\frac{1}{2}$$ である。

$\lambda_1=1$ に対しては $$(A-I)\boldsymbol{s}_1=0$$ より $-0.2s_{1y}+0.3s_{1z}=0$ なので、例えば $$\boldsymbol{s}_1=\begin{pmatrix}3\\2\end{pmatrix}$$ を取れる。$\lambda_2=1/2$ に対しては $$\left(A-\frac12 I\right)\boldsymbol{s}_2=0$$ より $s_{2y}+s_{2z}=0$ なので、例えば $$\boldsymbol{s}_2=\begin{pmatrix}1\\-1\end{pmatrix}$$ を取れる。よって固有ベクトル行列を $$S=\begin{pmatrix}3&1\\2&-1\end{pmatrix}$$ とすればよい。

このとき $$AS = \begin{pmatrix} A\boldsymbol{s}_1&A\boldsymbol{s}_2 \end{pmatrix} = \begin{pmatrix} \lambda_1\boldsymbol{s}_1&\lambda_2\boldsymbol{s}_2 \end{pmatrix} = S \begin{pmatrix} \lambda_1&0\\0&\lambda_2 \end{pmatrix}.$$ $S$ は正則なので、左から $S^{-1}$ を掛ければ $$S^{-1}AS= \begin{pmatrix} \lambda_1&0\\0&\lambda_2 \end{pmatrix}$$ が示される。

$q=(1/2)^k$ とおく。$S^{-1}$ は $$S^{-1}= \begin{pmatrix} 1/5&1/5\\ 2/5&-3/5 \end{pmatrix}$$ であるから、 $$\begin{aligned} A^k &=S \begin{pmatrix} 1&0\\0&q \end{pmatrix} S^{-1}\\ &= \begin{pmatrix} \frac{3+2q}{5}&\frac{3-3q}{5}\\ \frac{2-2q}{5}&\frac{2+3q}{5} \end{pmatrix}. \end{aligned}$$ 初期値を $$\boldsymbol{u}_0=\begin{pmatrix}y_0\\z_0\end{pmatrix}$$ とすると $$\begin{pmatrix}y_k\\z_k\end{pmatrix}=A^k\boldsymbol{u}_0$$ である。$k\to\infty$ では $q\to0$ なので、 $$y_k\to \frac35(y_0+z_0),\qquad z_k\to \frac25(y_0+z_0).$$

含意 $A\to B$ は、$A$ が真で $B$ が偽のときだけ偽であり、それ以外では真である。この規則で各式を分類する。

$$\begin{array}{c|c|l} \text{式} & \text{分類} & \text{理由}\\ \hline \neg(\neg P)\to P & \text{恒真} & \neg\neg P\equiv P\text{ なので }P\to P\\ P\to(P\land Q) & \text{どちらでもない} & P=\mathrm{T},Q=\mathrm{F}\text{ で偽、他では真の場合がある}\\ P\to(P\lor Q) & \text{恒真} & P\text{ が真なら }P\lor Q\text{ も真}\\ \neg P\to(P\land Q) & \text{どちらでもない} & P=\mathrm{F}\text{ で偽、}P=\mathrm{T}\text{ で真}\\ (P\to Q)\to(Q\to P) & \text{どちらでもない} & P=\mathrm{F},Q=\mathrm{T}\text{ で偽、他では真の場合がある}\\ P\to\neg P & \text{どちらでもない} & P=\mathrm{T}\text{ で偽、}P=\mathrm{F}\text{ で真}\\ \neg P\to P & \text{どちらでもない} & P=\mathrm{F}\text{ で偽、}P=\mathrm{T}\text{ で真} \end{array}$$

次に、$R$ が $S$ の論理的帰結であるとは、$S$ を充足するすべての解釈が $R$ も充足することである。これは論理式 $S\to R$ が恒真であることと同じである。

(a) は誤りである。例えば $R=S=P$ とすれば、$R$ は $S$ の論理的帰結である。しかし $P=\mathrm{F}$ の解釈では $R\lor S=P$ は偽であり、恒真ではない。

(b) は正しい。$\neg S\lor R$ は $S\to R$ と同値である。$R$ が $S$ の論理的帰結なら、$S$ が真の解釈では $R$ も真であり、$S$ が偽の解釈では $\neg S$ が真である。したがってすべての解釈で $\neg S\lor R$ は真である。

(c) は正しい。$R$ が $S$ の論理的帰結なら、$S$ が真で $R$ が偽となる解釈は存在しない。したがって $\neg R\land S$ を真にする解釈はなく、この式は恒偽である。

最後に、任意の解釈が $R\land(R\to S)$ を充足すると仮定する。このとき $R$ は真であり、同時に $R\to S$ も真である。含意 $R\to S$ が真で、前件 $R$ が真であるから、後件 $S$ も真でなければならない。よって、$R\land(R\to S)$ を充足するすべての解釈は $S$ を充足する。定義より、$S$ は $R\land(R\to S)$ の論理的帰結である。

若者にだけ聞こえやすいモスキート音とは、およそ十数 kHz 以上の高周波音である。加齢により高域の聴力が低下するため、若年者には聞こえやすく、中高年には聞こえにくい。店舗前などで若者の滞留を抑える装置や、若者向けの着信音に利用された。

フーリエ変換対を $$x(t)=\int_{-\infty}^{\infty}X(f)e^{j2\pi ft}\,df$$ と定めているので、逆に $$X(f)=\int_{-\infty}^{\infty}x(t)e^{-j2\pi ft}\,dt$$ である。

$x_e(-t)=x_e(t)$ を満たす関数を偶関数、$x_o(-t)=-x_o(t)$ を満たす関数を奇関数という。任意の信号は $$x_e(t)=\frac{x(t)+x(-t)}{2},\qquad x_o(t)=\frac{x(t)-x(-t)}{2}$$ により偶成分と奇成分へ分けられる。図から読み取れる階段状信号について、端点の値は積分や図示には影響しないので無視すると、 $$x_e(t)= \begin{cases} 0,& |t|>2,\\ -1,& 1<|t|<2,\\ -1/2,& 0<|t|<1, \end{cases}$$ であり、 $$x_o(t)= \begin{cases} 0,& |t|>2,\\ 1,& -2<t<-1,\\ 3/2,& -1<t<0,\\ -3/2,& 0<t<1,\\ -1,& 1<t<2 \end{cases}$$ である。

$x_e(t)$ が実偶関数のとき、オイラーの公式より $$X_e(f)=\int x_e(t)\cos(2\pi ft)\,dt -j\int x_e(t)\sin(2\pi ft)\,dt$$ である。$x_e(t)\sin(2\pi ft)$ は奇関数なので積分が0となり、$X_e(f)$ は実数値の偶関数になる。一方、$x_o(t)$ が実奇関数のとき、$x_o(t)\cos(2\pi ft)$ は奇関数なので実部が0となり、$X_o(f)$ は純虚数の奇関数になる。

不規則信号 $x_r(t)$ の自己相関関数は、広義定常過程として扱うなら $$\varphi_r(\tau)=E[x_r(t)x_r(t+\tau)]$$ で定義される。時間平均で書く場合は $$\varphi_r(\tau)= \lim_{T_0\to\infty}\frac{1}{2T_0} \int_{-T_0}^{T_0}x_r(t)x_r(t+\tau)\,dt$$ である。周期 $T$ の周期信号 $x_p(t)$ については $$\varphi_p(\tau)=\frac{1}{T}\int_{t_0}^{t_0+T}x_p(t)x_p(t+\tau)\,dt$$ で定義でき、積分区間の始点 $t_0$ は任意である。

周期 $T$、パルス幅 $\tau_w$、振幅 $A$ の周期方形パルス列では、自己相関は周期 $T$ を持つ三角形状になる。$0<\tau_w<T/2$ とし、 $$\Delta(\tau)=\min_{m\in\mathbb{Z}}|\tau-mT|$$ とおけば $$\varphi_p(\tau)= \begin{cases} \dfrac{A^2}{T}(\tau_w-\Delta(\tau)),&0\le \Delta(\tau)\le \tau_w,\\ 0,&\tau_w<\Delta(\tau)\le T/2 \end{cases}$$ である。ピーク値は $\varphi_p(0)=A^2\tau_w/T$ である。

左向きを正とする。自動車Bに働く力は駆動力 $f$ であり、摩擦は無視するので、運動方程式は $$m\frac{dv}{dt}=f.$$ フィードバック則 $f=k(r-v)$ を代入すると $$m\frac{dv}{dt}=k(r-v)$$ である。

初期値を0としてラプラス変換すると $$msV(s)=k\{R(s)-V(s)\}$$ である。したがって $$(ms+k)V(s)=kR(s)$$ となり、速度入力 $r$ から速度出力 $v$ までの伝達関数は $$G(s)=\frac{V(s)}{R(s)}=\frac{k}{ms+k}$$ である。

極は $$s=-\frac{k}{m}$$ である。質量 $m>0$ なので、安定条件は $$k>0$$ である。

安定な場合に、自動車Aが静止状態から一定速度 $V$ で動き始めるとする。入力は $r(t)=Vu(t)$ であり、定常値は最終値定理から $$\lim_{t\to\infty}v(t) = \lim_{s\to0}s\frac{k}{ms+k}\frac{V}{s} =V$$ である。したがって最終的には同じ速度で追従する。時間応答としては $$v(t)=V\left(1-e^{-kt/m}\right)$$ である。

次に $$r(t)=r_0+a\sin\omega t$$ とする。定常状態では、直流成分 $r_0$ はゲイン1で追従する。振動成分については、周波数応答 $$G(j\omega)=\frac{k}{k+jm\omega}$$ の大きさを掛ければよい。したがって自動車Bの振動成分の振幅 $b$ は $$b=a|G(j\omega)| =a\frac{k}{\sqrt{k^2+(m\omega)^2}}$$ である。$k>0$ なら $$0\le b\le a$$ であり、$\omega>0$ では $b<a$ である。つまりBの速度変動はAの速度変動より小さくなり、位相も遅れる。

半径 $R$、中心角 $\theta$ の円上の点 $P$ は $$P(\theta)= \begin{pmatrix} R\cos\theta\\ R\sin\theta \end{pmatrix}$$ で表される。

円弧長を $S$ とすると $$S=R\theta,\qquad \theta=\frac{S}{R}$$ であるから、 $$P(S)= \begin{pmatrix} R\cos(S/R)\\ R\sin(S/R) \end{pmatrix}$$ である。

弧長 $S$ による接線ベクトル、すなわち単位接線ベクトルは $$\boldsymbol{T}(S)=\frac{dP}{dS} = \begin{pmatrix} -\sin(S/R)\\ \cos(S/R) \end{pmatrix} = \begin{pmatrix} -\sin\theta\\ \cos\theta \end{pmatrix}.$$ 曲率ベクトルは $$\frac{d\boldsymbol{T}}{dS} = -\frac1R \begin{pmatrix} \cos\theta\\ \sin\theta \end{pmatrix}$$ であり、その大きさは $$\kappa=\left\|\frac{d\boldsymbol{T}}{dS}\right\|=\frac1R$$ である。直線では接線ベクトルが変化しないので、曲率は0である。

曲面上の点で、法線を含む平面で曲面を切ったときに得られる法曲率の最大値と最小値を主曲率 $\kappa_1,\kappa_2$ という。ガウス曲率と平均曲率は $$K=\kappa_1\kappa_2,\qquad H=\frac{\kappa_1+\kappa_2}{2}$$ で定義される。

以下では外向き法線を採用する。円筒側面では、軸方向の法曲率は0であり、円周方向の曲率ベクトルは中心軸方向、つまり外向き法線と逆向きである。したがって $$\kappa_{\mathrm{circ}}=-\frac1R,\qquad \kappa_{\mathrm{axis}}=0.$$ よって最大曲率は $0$、最小曲率は $-1/R$ である。

半径 $R$ の球面では、どの接線方向に切っても半径 $R$ の大円と同じ曲率をもつ。外向き法線に対し曲率ベクトルは中心方向で逆向きなので $$\kappa_1=\kappa_2=-\frac1R$$ である。したがって $$K=\kappa_1\kappa_2=\frac1{R^2}, \qquad H=\frac{\kappa_1+\kappa_2}{2}=-\frac1R.$$

3本の棒を、移動元を $from$、移動先を $to$、補助棒を $work$ と書く。$N$ 枚を $from$ から $to$ へ移す再帰的手順は次の通りである。

1. $N=0$ なら何もしない。$N=1$ なら1枚を $from$ から $to$ へ移動する手順を出力して終了する。

2. $N>1$ なら、上の $N-1$ 枚を $from$ から $work$ へ、$to$ を補助棒として再帰的に移す。

3. 残った最大の円盤を $from$ から $to$ へ移動する手順を出力する。

4. $work$ に退避した $N-1$ 枚を $work$ から $to$ へ、$from$ を補助棒として再帰的に移す。

C言語では、例えば次のように書ける。

最小移動回数を $M(N)$ とする。最大円盤をAからBへ移すには、その上の $N-1$ 枚を一度Cへ退避し、最大円盤を1回動かし、さらに $N-1$ 枚をCからBへ移す必要がある。したがって $$M(N)=2M(N-1)+1,\qquad M(1)=1$$ である。これを解くと $$M(N)=2^N-1$$ となる。よって $$M(10)=2^{10}-1=1023$$ である。

最後の再帰関数は、再帰呼び出しの後に追加の処理をせず直ちに戻る末尾再帰である。したがって、再帰呼び出しを「引数を更新して先頭へ戻るループ」に置き換えられる。

ここで、$S$ の中にある return はそのまま関数 F からの復帰として働く。$S$ が復帰しなかった場合だけ、次の再帰呼び出しに相当する $(a,b)$ を新しい $(x,y)$ としてループを続ける。

割り込み処理とは、実行中のプログラムとは別に発生した事象、またはCPU内部で検出された例外に応じて、現在の実行状態を保存し、あらかじめ定められた割り込み処理ルーチンへ制御を移す処理である。処理後は保存していたプログラムカウンタやレジスタなどを復元し、元の処理へ戻る。

サブルーチンは、プログラム中の命令によって明示的に呼び出される。これに対して割り込みは、入出力完了、タイマ、外部信号、例外などにより非同期または予期しないタイミングで発生する。したがって割り込みでは、実行中の文脈を壊さないように退避・復元、優先順位、マスク、割り込み禁止区間などを考える必要がある。

与えられた命令列では、主にデータハザードが問題になる。例えば、メモリから値をロードした直後に、そのロード先レジスタを加算命令が読むと、ロード結果がまだレジスタに書き戻されていない可能性がある。これはRAWハザードである。同様に、2回目のロードと加算の間にもロード・ユースのRAWハザードがある。また、加算結果を直後のストアが使う場合、ストアデータへのフォワーディングがないパイプラインではここもRAWハザードになる。

典型的な5段パイプラインで「ロード直後の1命令だけを空ければよい」と仮定すると、独立なロードを前に出し、レジスタ名を変えることで次のように修正できる。

2つ目の LOAD と最初の ADD の間に、独立な LOAD R4 S0(16) を挿入しているため、R2 のロード結果が利用可能になる。また、Eを R4 に読み込むことで、Cを保持する R2 を上書きしない。2つ目の加算では、LOAD R4 S0(16) から十分な命令間隔が空いているので、R4 のロード・ユースハザードも避けられる。

もし対象CPUが加算結果から直後のストアへのフォワーディングを持たないなら、加算とストアの間にも NOP を入れるか、独立命令を挟む必要がある。その場合は例えば次のように保守的に書ける。