院試hub

東京大学 院試 過去問 解答例

東大 情報理工学系研究科 数理情報学専攻 数理情報学 2024年度 院試 過去問 解答例・解説(全5問)

全5問。テーマタグは3件(一様収束・最尤推定・特異値分解)。

最終更新:

収録5年度分の解答PDF:東京大学 情報理工学系研究科 数理情報学専攻 数理情報学(¥3,200・紙面見本あり)

このページで公開
解説5問と大問1問の途中式・最終答(全5問)
解答PDFに収録
途中式と最終答(最終答つき5問)
問題本文
非収録

東大 数理情報学 2024年度 院試 過去問の出題内容(全5問)

大問主題解説の小見出し最終答
第1問直交Procrustes問題採点上の注意あり
第2問加速勾配法のエネルギー評価—あり
第3問一方向三角多項式による近似採点上の注意あり
第4問指数分布と到着回数—あり
第5問制約付きスケジューリング採点上の注意あり

この年度の解説には採点上の注意3件・典型ミス2件が付いています。

2024年度の出題テーマと、同じテーマを出した他大学・他年度

この年度は3問に3テーマが出ています。

前年度(2023年度)との違い

大問数
2023年度 5問 → 2024年度 5問
2024年度で新しく出たテーマ
一様収束・最尤推定・特異値分解
2023年度のページを見る

第1問 — 直交Procrustes問題

方針

直交制約つきの最小二乗では、長さを保つ変換であることを利用して、定数項と相関項に分ける。 残るのは相関 tr⁡(PXY⊤)\operatorname{tr}(PXY^\top) の最大化であり、特異値分解で左特異ベクトルと右特異ベクトルをそろえればよい。

採点上の注意

P=UV⊤P=UV^\top と書くと向きが逆になる。実際に Q=V⊤PUQ=V^\top PU と置いて Q=IQ=I を代入すると、P=VU⊤P=VU^\top であることが確認できる。 この向きは答案中で一度トレースの巡回性を使って確認しておくと安全である。

直交Procrustes問題の途中式・最終答をPDFで見る

第2問 — 加速勾配法のエネルギー評価

方針

この問題は、係数が不自然に見えても、エネルギーを微分または差分にかけた瞬間に 内積項が消えるように設計されている。計算では αk=2hk+h+2\alpha_k=2hk+h+2 と ak=(hk+1)2a_k=(hk+1)^2 を置くと、打ち消しの構造が見やすい。

典型ミス

離散版で δ+∥v(k)−x∗∥2=2(v(k)−x∗)⊤δ+v(k)+⋯\delta^+\|v^{(k)}-x^*\|^2=2(v^{(k)}-x^*)^\top\delta^+v^{(k)}+\cdots のように左端点で展開すると、問題で必要な式と符号がずれる。今回の恒等式は 右端点 v(k+1)v^{(k+1)} を使うことで、余りが −h∥δ+v(k)∥2-h\|\delta^+v^{(k)}\|^2 になり、単調性を強める形になる。

加速勾配法のエネルギー評価の途中式・最終答をPDFで見る

第3問 — 一方向三角多項式による近似

方針

n−3n^{-3} で関数が近似できるという仮定は、微分すると nn 倍されても ∑n−2\sum n^{-2} が残る、という強さを持っている。この「差を微分しても総和可能」という点が本質である。

採点上の注意

導関数の一様収束だけでは、元の関数の極限が何であるかを結びつける一文が不足しやすい。 今回は tn→ft_n\to f も一様に成り立つので、積分表示に極限を入れるのが最も短く確実である。

解答

(1)

三角不等式より ∥tn+1−tn∥∞≤∥tn+1−f∥∞+∥f−tn∥∞. \|t_{n+1}-t_n\|_\infty \le \|t_{n+1}-f\|_\infty+\|f-t_n\|_\infty . 仮定を代入して ∥tn+1−tn∥∞≤c(n+1)3+cn3≤2cn3 \|t_{n+1}-t_n\|_\infty \le \frac{c}{(n+1)^3}+\frac{c}{n^3} \le \frac{2c}{n^3} を得る。

(2)

tn+1−tnt_{n+1}-t_n は高々 n+1n+1 次の同じ型の三角多項式である。Bernstein の不等式を用いると、 ∥tn+1′−tn′∥∞≤(n+1)∥tn+1−tn∥∞≤2c(n+1)n3. \begin{aligned} \|t_{n+1}'-t_n'\|_\infty &\le (n+1)\|t_{n+1}-t_n\|_\infty \\ &\le \frac{2c(n+1)}{n^3}. \end{aligned} n≥1n\ge1 では (n+1)/n3≤2/n2(n+1)/n^3\le 2/n^2 だから ∥tn+1′−tn′∥∞≤4cn2. \|t_{n+1}'-t_n'\|_\infty\le \frac{4c}{n^2}. 右辺の級数は収束する。従って {tn′}\{t_n'\} は C[0,2π]C[0,2\pi] の一様ノルムで Cauchy 列である。C[0,2π]C[0,2\pi] は完備なので、ある連続関数 ss に一様収束する。

また各 tn′t_n' は 2π2\pi 周期的であるから、その一様極限 ss も 2π2\pi 周期的である。

(3)

仮定より tn→ft_n\to f は一様収束する。さらに (2) より tn′→st_n'\to s も一様収束する。 各 nn について tn(θ)−tn(0)=∫0θtn′(u) du(0≤θ≤2π) t_n(\theta)-t_n(0)=\int_0^\theta t_n'(u)\,du \qquad(0\le \theta\le 2\pi) が成り立つ。両辺で n→∞n\to\infty とすると、一様収束により f(θ)−f(0)=∫0θs(u) du f(\theta)-f(0)=\int_0^\theta s(u)\,du を得る。右辺は θ\theta について微分可能で、導関数は s(θ)s(\theta) である。従って f′(θ)=s(θ)(0<θ<2π). f'(\theta)=s(\theta)\qquad(0<\theta<2\pi). さらに ff と ss はともに 2π2\pi 周期的なので、この関係は端点をまたいで実数全体に拡張できる。 よって ff は R\mathbb{R} 上で微分可能である。

最終答

(1) ∥tn+1−tn∥∞≤2c/n3\|t_{n+1}-t_n\|_\infty\le2c/n^3。 (2) Bernstein の不等式から ∥tn+1′−tn′∥∞≤4c/n2\|t_{n+1}'-t_n'\|_\infty\le4c/n^2 となり、{tn′}\{t_n'\} は一様収束する。 (3) tn(θ)−tn(0)=∫0θtn′(u) dut_n(\theta)-t_n(0)=\int_0^\theta t_n'(u)\,du に極限を入れることで f(θ)−f(0)=∫0θs(u) duf(\theta)-f(0)=\int_0^\theta s(u)\,du を得るため、f′=sf'=s であり ff は微分可能である。

第4問 — 指数分布と到着回数

方針

指数分布の無記憶性から、最小値は「二つの時計の早い方」、差は「残った時計の待ち時間」と読める。 最後の NN は、指数待ち時間で構成される Poisson 過程の時刻 aa までの到着回数である。

典型ミス

Z−YZ-Y の率を 2λ2\lambda としてしまう誤りに注意する。二つのうち一つはすでに到着済みなので、 差の段階で動いている残りの待ち時間は一つだけであり、率は λ\lambda である。

指数分布と到着回数の途中式・最終答をPDFで見る

第5問 — 制約付きスケジューリング

方針

処理時間がそろっている場合は、数値的な負荷ではなく「何個載せるか」の問題になる。 許可機械制約は二部マッチングの容量付き版として扱うと自然である。

採点上の注意

(2) の近似比では、最後に最大負荷を作った仕事に注目するのが定石である。 貪欲法の選択規則から「割当直前の負荷はその時点の平均以下」といえ、平均負荷下界と最大仕事長下界の二つを 最適値 T∗T^* に結びつける。

制約付きスケジューリングの途中式・最終答をPDFで見る

東大 数理情報学 院試 過去問の収録5年度

  • 2026年度(全5問)

    半正定値錐への射影 / ガウス行列の集中 / 平面力学系の不変領域と爆発

  • 2025年度(全5問)

    半正定値行列の真偽判定 / 相分離モデルとエネルギー / 密度の平均と中央値

  • 2024年度(このページ・全5問)

    直交Procrustes問題 / 加速勾配法のエネルギー評価 / 一方向三角多項式による近似

  • 2023年度(全5問)

    指数核平均と連続極限 / Lotka--Volterra型方程式と安定性 / 複素積分による台形公式誤差

  • 2021年度(全3問)

    基礎概念:凸最適化と双対性 / 研究計画:分布ロバスト学習 / 社会課題論述:感染症対策