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

与えられた4本の列ベクトルを $$a_1=\begin{bmatrix}1\\1\\1\\1\end{bmatrix},\quad a_2=\begin{bmatrix}1\\1\\-3\\-3\end{bmatrix},\quad a_3=\begin{bmatrix}1\\-1\\1\\-1\end{bmatrix},\quad a_4=\begin{bmatrix}0\\-2\\2\\4\end{bmatrix}$$ とする。

1. $$\|a_1\|=\sqrt{1+1+1+1}=2$$ より $$q_1=\frac{1}{2}\begin{bmatrix}1\\1\\1\\1\end{bmatrix}.$$ また $$q_1^{\mathsf T}a_2=\frac{1+1-3-3}{2}=-2$$ なので $$a_2-(q_1^{\mathsf T}a_2)q_1 =a_2+2q_1 =\begin{bmatrix}2\\2\\-2\\-2\end{bmatrix}$$ であり、そのノルムは4である。したがって $$q_2=\frac{1}{2}\begin{bmatrix}1\\1\\-1\\-1\end{bmatrix}.$$

2. $a_3$ はすでに $q_1,q_2$ と直交している。実際に $$q_1^{\mathsf T}a_3=0,\qquad q_2^{\mathsf T}a_3=0$$ であり、$\|a_3\|=2$ だから $$q_3=\frac{1}{2}\begin{bmatrix}1\\-1\\1\\-1\end{bmatrix}.$$ 次に $$q_1^{\mathsf T}a_4=2,\qquad q_2^{\mathsf T}a_4=-4,\qquad q_3^{\mathsf T}a_4=0$$ である。よって $$a_4-2q_1-(-4)q_2-0q_3 =\begin{bmatrix}1\\-1\\-1\\1\end{bmatrix}$$ となり、ノルムは2である。したがって $$q_4=\frac{1}{2}\begin{bmatrix}1\\-1\\-1\\1\end{bmatrix}.$$

3. $Q=[q_1\ q_2\ q_3\ q_4]$ とすれば $R=Q^{\mathsf T}A$ である。計算すると $$R= \begin{bmatrix} 2&-2&0&2\\ 0&4&0&-4\\ 0&0&2&0\\ 0&0&0&2 \end{bmatrix}.$$ したがって $$A=QR,\qquad Q=\frac{1}{2} \begin{bmatrix} 1&1&1&1\\ 1&1&-1&-1\\ 1&-1&1&-1\\ 1&-1&-1&1 \end{bmatrix}$$ である。

4. $B=Q_BR_B$、$Q_B^{\mathsf T}Q_B=I$ とする。誤差平方は $$E^2=\|b-Bx\|^2=\|b-Q_BR_Bx\|^2$$ である。$Q_BQ_B^{\mathsf T}$ は $Q_B$ の列空間への直交射影なので、 $$b=Q_BQ_B^{\mathsf T}b+(I-Q_BQ_B^{\mathsf T})b$$ と直交分解できる。したがって $$b-Q_BR_Bx =Q_B(Q_B^{\mathsf T}b-R_Bx)+(I-Q_BQ_B^{\mathsf T})b$$ であり、2つの項は直交する。よって $$E^2 =\|Q_B(Q_B^{\mathsf T}b-R_Bx)\|^2 +\|(I-Q_BQ_B^{\mathsf T})b\|^2.$$ $Q_B$ の列は正規直交なので第1項は $$\|Q_B^{\mathsf T}b-R_Bx\|^2$$ に等しい。第2項は $x$ に依存しないため、最小化には第1項を0にすればよい。したがって $$R_Bx=Q_B^{\mathsf T}b$$ を解けば最小二乗解となり、 $$x=R_B^{-1}Q_B^{\mathsf T}b$$ を得る。

1. 配列では、先頭から $k$ 番目の要素は添字計算で直接読めるため get は $O(1)$ である。一方、先頭に挿入するには既存要素を後ろへずらす必要があり insert は $O(n)$ である。連結リストでは、$k$ 番目へ到達するまでポインタをたどるため get は $O(n)$、先頭挿入は新しい節点の next を旧先頭に向け、先頭ポインタを更新するだけなので $O(1)$ である。

2. 順序付き連結リストで常に昇順に保つ方法Aでは、insert 時に挿入位置を探すため $O(n)$、deletemin は先頭を削除するだけなので $O(1)$ である。挿入時に何もしない方法Bでは、insert は先頭に加えれば $O(1)$、deletemin は全要素から最小値を探して削除するため $O(n)$ である。

3. insert と deletemin を効率よく行う代表的なデータ構造は優先度付きキューであり、典型的には二分ヒープで実現する。二分ヒープでは insert は末尾に追加して親方向へ交換するため $O(\log n)$、deletemin は根の最小値を取り出し、末尾要素を根へ移して子方向へ交換するため $O(\log n)$ である。

4. 集合を連結リストで表し、重複を許さない insert を行う場合、まず同じ要素が存在するか member と同じ探索を行う必要がある。したがって member は $O(n)$、insert も探索が支配して $O(n)$ である。存在しないことが分かった後の先頭挿入自体は $O(1)$ である。

5. 順序関係を使わずに insert と member を効率化する代表的なデータ構造はハッシュ表である。要素 $x$ からハッシュ値 $h(x)$ を計算して格納先のバケットを決める。member では同じバケット内だけを調べ、insert では存在確認後にそのバケットへ追加する。ハッシュが適切で衝突が平均的に少なければ、member と insert は期待 $O(1)$ である。ただし、衝突が極端に多い最悪の場合は $O(n)$ になり得る。

1. 標本化とは、連続時間または連続空間の信号を一定間隔ごとに測定し、離散的な標本列に変換する処理である。量子化とは、各標本の連続的な振幅値を、有限個の代表値またはビット列に丸める処理である。標本化は軸の離散化、量子化は値の離散化である。

2. アナログ信号に標本化周波数 $f_s$ の半分を超える周波数成分が含まれると、標本化後に低周波成分へ折り返して現れる。これはエイリアシングであり、標本化後には本来の低周波成分と折り返し成分を区別できない。したがってA/D変換の前に帯域制限フィルタ、通常は低域通過のアンチエイリアスフィルタを入れ、ナイキスト周波数 $f_s/2$ より高い成分を十分に減衰させる必要がある。

3. デジタルカメラでの標本化は、レンズが作る連続的な光学像をイメージセンサ上の画素格子で空間的に測る処理である。各画素は一定面積に入った光を電荷や電圧として蓄積する。量子化は、そのアナログ電圧をA/D変換器で例えば10 bit、12 bit、14 bitなどの有限階調へ変換する処理である。

4. 階調数を変更して減らす処理は、画素値の候補数を少なくするため不可逆であり、滑らかな濃淡に段差が出るポスタリゼーションやバンディングを生じさせる。特に階調数を大きく減らすほど画質劣化が目立つ。

   ハフマン符号化は、出現頻度の高い記号に短い符号、低い記号に長い符号を割り当てる可変長符号である。画素値や変換係数をそのまま可逆符号化する限り、復号後の値は元と一致するため画質は劣化しない。ただし、前段に量子化などの不可逆処理があれば、その劣化は残る。

1. レイノルズ数は $$Re=\frac{\rho UL}{\mu}=\frac{UL}{\nu}$$ で定義される。ここで $U$ は代表速度、$L$ は代表長さ、$\rho$ は密度、$\mu$ は粘性係数、$\nu$ は動粘性係数である。物理的には、慣性力と粘性力の比を表す無次元数であり、同じ形状の流れで $Re$ が等しければ粘性の効き方が相似になる。

   レイノルズ数が小さいと粘性の影響が強く、流れは層流的で滑らかになりやすい。レイノルズ数が大きくなると慣性力が支配的になり、境界層は薄くなり、はく離、渦、乱流が生じやすくなる。管内流や物体まわりの流れでは、臨界的な値を超えると層流から乱流への遷移が起こる。

2. マッハ数は $$Ma=\frac{U}{a}$$ で定義される。ここで $a$ は音速である。物理的には、流れの速度が圧力変化や密度変化の伝播速度である音速に対してどれだけ大きいかを表す。$Ma$ が小さいと密度変化は小さく、非圧縮性流れとして近似しやすい。

   マッハ数が増加すると圧縮性の影響が無視できなくなる。亜音速では圧力変化が上流にも伝わるが、$Ma$ が1に近づくと局所的な音速到達やチョークが問題になる。超音速では情報が上流へ伝わりにくくなり、衝撃波や膨張波を伴う流れになる。

1. 1. 排気ガスによる大気汚染は、道路沿道、交差点、渋滞区間など発生源近くで濃度が高くなりやすい。時間的には朝夕ピーク、低速走行、冷間始動時に悪化し、風向や大気安定度にも左右される。対策は排出ガス規制、触媒・後処理装置、低公害車、交通流円滑化、沿道の土地利用配慮である。

   2. 騒音・振動は道路からの距離とともに減衰するが、大型車、速度、舗装状態、橋梁や高架構造に強く影響される。時間的には夜間の暗騒音が小さい時間帯で問題化しやすく、瞬間的な大型車通過も影響する。対策は遮音壁、低騒音舗装、速度管理、大型車の経路・時間規制、舗装や構造物の維持管理である。

   3. エネルギー消費と二酸化炭素排出は、沿道だけでなく地球規模の環境影響として累積的に効く。時間的には総走行台キロ、渋滞、加減速の多さ、車両効率、燃料種に依存する。対策は燃費改善、EV・HEVの導入、公共交通や物流効率化への転換、TDM、エコドライブ、再生可能エネルギー利用である。

2. LCAの観点では、EVは走行時に排気ガスを出さず、沿道大気汚染と騒音を減らしやすい。回生ブレーキにより都市内のエネルギー効率も高く、電源が低炭素化するほど温室効果ガス削減効果が大きくなる。一方で、電池製造には多くのエネルギーと希少金属が必要であり、採掘、製造、輸送、廃棄・リサイクル段階の環境負荷がある。電力が化石燃料中心なら、排出が走行地点から発電所へ移るだけになり得る。車両重量増によるタイヤ摩耗粉じんや道路負荷も考慮する必要がある。

3. EV、HEV、PHVが増えると、燃料消費量に連動するガソリン税・軽油引取税などの税収が減る。一方、道路の維持補修費は走行距離、車両重量、老朽化に応じて発生し、燃料消費が少ない車も道路を利用する。したがって、従来の燃料課税だけに依存すると受益と負担がずれ、維持財源が不足する。解決策としては、走行距離課金、重量や道路損傷度に応じた課金、混雑課金、EV充電への一定課金、一般財源との組合せが考えられる。導入時にはプライバシー、地方部利用者、物流コストへの配慮も必要である。