院試hub

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

大学
東京大学
研究科・専攻
情報理工学系研究科 数理情報学専攻
科目
数理情報学
年度
2024年度

解説は全問、途中式と最終答は大問1問を無料で公開しています。PDFの収録範囲は商品ページで確認できます。問題本文は含みません。

東京大学 情報理工学系研究科 数理情報学専攻の解答PDF2021〜2026年度(6年度)

¥3,200

商品内容・見本・購入へ

第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 であることが確認できる。 この向きは答案中で一度トレースの巡回性を使って確認しておくと安全である。

第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 になり、単調性を強める形になる。

第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 である。

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

方針

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

採点上の注意

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

数理情報学の解答・解説PDF

2021〜2026年度(6年度) · ¥3,200

解答PDFの商品ページへ

年度別の解答例

  • 2026年度

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

  • 2025年度

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

  • 2024年度(このページ)

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

  • 2023年度

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

  • 2021年度

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

2024年度の出題内容

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

同じテーマを出した他大学・他年度

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

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

2023年度の解答例

東京大学の他の解答PDF

院試対策ガイド

東京大学の公式過去問

公開年度範囲
2020、2023〜2026(2021・2022年度はレポート課題を掲載)
公式の解答例
解答例の掲載なし
英語の扱い
外国語試験はTOEFLスコアを正式スコアとして利用。研究科によるTOEFL-ITPの実施なし。

東京大学の公式過去問PDF