東大 情報理工学系研究科 創造情報学専攻 創造情報学 専門科目 2022年度 院試 解答例・解説

方針

この問題は，変数ごとに「次の1単位を入れたときの増分」が並んでいると見ると整理しやすい。 非増加性がある場合は，各列の上から順にしか選べないという制約付きで，大きな増分を $r$ 個 取ればよい。非増加性がない場合は，局所的に良い1単位を選んでも後で大きな増分が現れる可能性 があるため，合計量を状態に持つ動的計画法が必要になる。

交換証明の意味

最適性条件の左辺は「いま1単位足すなら得られる最大の利得」，右辺は「いま1単位抜くなら失う 最小の利得」である。左辺が右辺を上回るなら，抜いて足すだけで改善できる。逆に左辺が右辺以下 なら，どの実行可能解へ移るにも，足して得る利得が抜いて失う量を超えられない。

採点上の注意

貪欲法の正当性を「いつも最大を選んでいるから」と書くだけでは不十分である。各 $d_i(a)$ が 非増加であるため，選んだ増分より後ろの増分が大きくならない，という点を明示してはじめて 交換証明または最適性条件につながる。

方針

方式1の本質は stop-and-wait である。1個のデータパケットを送った後，対応するACKが戻るまで 次を送れないため，短いパケットでも往復伝搬遅延が支配的になる。長距離で方式1が極端に遅いのは， 帯域が低いからだけでなく，送信機会を往復時間ごとに1回しか使えないからである。

ウィンドウサイズの意味

方式2では，帯域だけでなく帯域遅延積が重要になる。経路中に常時 $R\,T_{\mathrm{rt}}$ bits 程度のデータを置けなければ，受信側は $R$ bits/sec で受け取り続けられない。64 KiBの窓は 近距離なら大きいが，500 msec級の遅延では小さく，帯域が余っていても速度が出ない。

採点上の注意

転送時間の式では，片方向のデータ送信時間だけでなく，ACKの戻り時間も入れる。特に $m_2/B_i$ と戻り方向の伝搬遅延を落とすと，方式1の速度を過大評価する。また，動画配信では 1接続のウィンドウ制約と，複数接続の総帯域制約を分けて確認する。

方針

用語説明では，定義だけでなく「どの問題を解くために使うか」を添えると答案が強くなる。 擬似逆行列は線形方程式と最小二乗，RNNは系列データ，KLダイバージェンスは分布のずれ， ホモグラフィーは画像中の平面対応，というように対応する応用を明確にするとよい。

数式を入れる効果

4行から8行程度の説明では，長い歴史的説明よりも，代表式を1つ示す方が採点者に理解を伝えやすい。 ただし式だけでは不十分で，擬似逆行列なら「最小二乗」，KLなら「非対称で距離ではない」， ホモグラフィーなら「同次座標とスカラー倍の同一視」まで書くと概念の範囲がはっきりする。

典型ミス

KLダイバージェンスを通常の距離と書く，RNNが単に深い全結合ネットワークだと説明する， 擬似逆行列を正則行列の逆行列だけに限定する，ホモグラフィーを任意の3次元変換と混同する， といった答案は減点されやすい。対象，数式，性質，応用を一つずつ入れると安定する。