京大 情報学研究科 システム科学コース 2021年度 院試 解答例・解説

任意の初期値という条件

初期値を限定しないので，固有空間のどの成分も現れ得る。したがって絶対値が $1$ を超える固有値はもちろん不可であり，$-1$ も一般には振動を生むため不可である。一方で固有値 $1$ は定数成分として残るだけなので許される。

近似多項式は直交射影

最小化すべき量は $\|e^x-h\|^2$ である。有限次元内積空間では，誤差がすべての基底方向に直交することが最小条件になる。正規直交基底を作っておくと，係数が単に $\langle e^x,e_j\rangle$ で与えられる。

発散の原因は上端の $1/(1-w)$

$\alpha=-1$ では $w=1$ に近づくほど $(1-w)^{-1}$ が効く。一方，$\beta>0$ があるため $z$ 積分は有限の正の値へ落ち着く。したがって全体は $\log M$ 程度に増大し，その対数が $\log\log M$ になる。

球へ直して考える

楕円体の問題は $x/a,y/b,z/c$ に直すと単位球の問題になる。切断楕円の中心は，単位球では原点から切断平面へ下ろした垂線の足であり，そこから元の座標へ戻せばよい。

XNOR は偶数性を保つ

二つのブロックがともに偶数，またはともに奇数であれば，合わせた $1$ の個数は偶数である。したがって二入力 XNOR を木状に接続すれば，多入力の偶数パリティ判定になる。

不完全定義では重なった併合を許す

完全定義の状態最小化と異なり，不完全定義機械では互換集合が重なってよい。重要なのは，各併合で生じる次状態の集合が，選んだ互換集合のどれかに含まれることである。本問では $ABCD$ の含意として $CF,DE,EF$ が出るため，この4集合をまとめて使う。

周期関数の留数和は境界積分で見る

二周期が実線形独立なら基本平行四辺形が作れる。向かい合う辺は周期だけ平行移動したものなので，周期性により境界積分が相殺する。ここから留数和がゼロであることが直ちに出る。

像の面積も境界積分に戻す

写像後の曲線を直接描かなくても，面積公式に $w=f(z)$ を代入すればよい。円周上では $\overline z=r^2/z$ が使えるため，$\overline{f(z)}$ も $z$ の有理関数として扱える。

$g$ は次の空き位置を表す

このアルゴリズムは，値ごとの最終配置区間をあらかじめ作り，区間外の要素を本来の区間へ巡回的に押し出す。比較を使わず，配列要素をほぼ一度ずつ動かすので線形時間になるが，押し出しの順序は元の順序を保たない。

下界を達成する系列を示す

最短性は総仕事量からの下界だけでは不十分で，その下界を実現するスケジュールを併せて示す必要がある。本問では総仕事量29コア時から下界8が出て，実際に8スロットの系列が構成できる。

条件付き後も指数分布が残る

指数分布では $X>d$ を条件にしても，超過分 $X-d$ は同じ率 $\theta$ の指数分布に従う。この無記憶性により，設問(3)(4)は設問(1)(2)の $X$ を $Y-d$ に置き換えた形になる。

無相関と独立は別

無相関は一次の積率だけの条件である。$Y=X^2$ のように完全に $X$ から決まる変数でも，対称性により $E[X^3]=0$ となって共分散が消えることがある。

図から読む量を式に落とす

ベクトル軌跡の負の実軸交点はゲイン余裕と安定限界を直接決める。実数摂動 $\delta$ は軌跡の水平移動なので，最も左へ動く $\delta=-0.25$ が最悪ケースになる。