院試hub

名大 情報学研究科 数理情報学 2019年8月実施 院試 過去問 解答例・解説

大学
名古屋大学
研究科・専攻
情報学研究科
科目
数理情報学
年度
2019年8月実施

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

名古屋大学 情報学研究科 数理情報学の解答PDF2020〜2026年度・6回

¥3,200

商品内容・見本・購入へ

第1問 線形代数学

直交化の見通し

[0,1][0,1] 上の多項式内積では、1, x−12, x2−x+161,\ x-\frac12,\ x^2-x+\frac16 はLegendre型の直交多項式になっている。正規化は要求されていないので、長さを 11 にそろえる必要はない。

表現行列の読み方

線形写像の表現行列は、各基底ベクトルの像を同じ基底で座標表示し、その座標を列に並べたものである。今回、直交基底を上の取り方にすると微分で g1↦0,g2↦g1,g3↦2g2 g_1\mapsto0,\qquad g_2\mapsto g_1,\qquad g_3\mapsto2g_2 となり、標準基底の場合と同じ形の行列が出る。これは偶然ではなく、低次から高次へ作ったモニック直交基底では、微分が次数を一つ下げるためである。

解答

以後 P2={a+bx+cx2∣a,b,c∈R},(f,g)=∫01f(x)g(x) dx P_2=\{a+bx+cx^2\mid a,b,c\in\mathbb{R}\}, \qquad (f,g)=\int_0^1 f(x)g(x)\,dx とおく。

  1. 任意の p,q∈P2p,q\in P_2 は p(x)=a+bx+cx2,q(x)=α+βx+γx2 p(x)=a+bx+cx^2,\qquad q(x)=\alpha+\beta x+\gamma x^2 と書ける。すると (p+q)(x)=(a+α)+(b+β)x+(c+γ)x2∈P2 (p+q)(x)=(a+\alpha)+(b+\beta)x+(c+\gamma)x^2\in P_2 であり、任意の λ∈R\lambda\in\mathbb{R} に対して (λp)(x)=λa+λb x+λc x2∈P2 (\lambda p)(x)=\lambda a+\lambda b\,x+\lambda c\,x^2\in P_2 である。したがって P2P_2 は通常の和と実数倍で閉じている。
  2. 任意の p∈P2p\in P_2 は一意に p(x)=a⋅1+b⋅x+c⋅x2 p(x)=a\cdot 1+b\cdot x+c\cdot x^2 と表せるので、{1,x,x2}\{1,x,x^2\} は P2P_2 を生成する。また a⋅1+b⋅x+c⋅x2=0 a\cdot 1+b\cdot x+c\cdot x^2=0 が恒等的に成り立つなら、多項式の係数比較により a=b=c=0a=b=c=0 である。よって一次独立でもあり、基底である。
  3. Gram--Schmidt法を、f1=1, f2=x, f3=x2f_1=1,\ f_2=x,\ f_3=x^2 の順に適用する。まず g1=f1=1. g_1=f_1=1. 次に g2=f2−(f2,g1)(g1,g1)g1=x−∫01x dx∫011 dx=x−12. g_2=f_2-\frac{(f_2,g_1)}{(g_1,g_1)}g_1 =x-\frac{\int_0^1 x\,dx}{\int_0^1 1\,dx} =x-\frac12. さらに (g2,g2)=∫01(x−12)2dx=112,(f3,g2)=∫01x2(x−12)dx=112. (g_2,g_2)=\int_0^1\left(x-\frac12\right)^2dx=\frac1{12}, \qquad (f_3,g_2)=\int_0^1x^2\left(x-\frac12\right)dx=\frac1{12}. したがって g3=f3−(f3,g1)(g1,g1)g1−(f3,g2)(g2,g2)g2=x2−13−(x−12)=x2−x+16. g_3=f_3-\frac{(f_3,g_1)}{(g_1,g_1)}g_1 -\frac{(f_3,g_2)}{(g_2,g_2)}g_2 =x^2-\frac13-\left(x-\frac12\right) =x^2-x+\frac16. 以上より B~={1, x−12, x2−x+16} \widetilde{B}=\left\{1,\ x-\frac12,\ x^2-x+\frac16\right\} は直交基底である。
  4. 微分演算子を D=d/dxD=d/dx と書く。p,q∈P2p,q\in P_2 と λ,μ∈R\lambda,\mu\in\mathbb{R} に対して D(λp+μq)=λDp+μDq D(\lambda p+\mu q)=\lambda Dp+\mu Dq が成り立つので、DD は線形写像である。 基底 B={1,x,x2}B=\{1,x,x^2\} では D(1)=0,D(x)=1,D(x2)=2x D(1)=0,\qquad D(x)=1,\qquad D(x^2)=2x であるから、列を各基底ベクトルの像の座標として並べると [D]B=(010002000). [D]_B= \begin{pmatrix} 0&1&0\\ 0&0&2\\ 0&0&0 \end{pmatrix}. 直交基底 B~={g1,g2,g3}\widetilde{B}=\{g_1,g_2,g_3\} については Dg1=0,Dg2=1=g1,Dg3=2x−1=2(x−12)=2g2. Dg_1=0,\qquad Dg_2=1=g_1,\qquad Dg_3=2x-1=2\left(x-\frac12\right)=2g_2. よって [D]B~=(010002000). [D]_{\widetilde{B}}= \begin{pmatrix} 0&1&0\\ 0&0&2\\ 0&0&0 \end{pmatrix}.

最終答

B~={1, x−12, x2−x+16}\widetilde{B}=\{1,\ x-\frac12,\ x^2-x+\frac16\}、かつ微分演算子の表現行列は B,B~B,\widetilde{B} のいずれでも (010002000)\begin{pmatrix}0&1&0\\0&0&2\\0&0&0\end{pmatrix} である。

第2問 微分積分学

内点で最大を取るときの符号

最大値の議論では、右差分商と左差分商の向きが逆になる。左側では分母 −h-h が負になるため、不等号の向きを間違えないことが重要である。

積分の分母を見る

三次式の分母は、x=−1/4x=-1/4 が根であることに気づけば (4x+1)(x2+1) (4x+1)(x^2+1) に分かれる。二次因子 x2+1x^2+1 は実数上ではこれ以上一次因子に分解しないので、分子を Bx+CBx+C と置くのが標準形である。

球帯の面積

単位球では高さ方向の幅 hh の球帯面積が常に 2πh2\pi h になる。aa に依存しない点は、回転面の面積要素で r(z)r(z) と 1+r′(z)2\sqrt{1+r'(z)^2} がちょうど打ち消し合うことから確認できる。

第3問 離散数学

積公式の本質

nn と互いに素でない数は、nn の素因子の少なくとも一つで割り切れる数である。したがって、Euler関数の積公式は「素因子ごとに割り切れるものを除く」という包除原理そのものである。

Möbius関数が現れる理由

∏p∣n(1−1p) \prod_{p\mid n}\left(1-\frac1p\right) を展開すると、同じ素数を二度使う項は出ない。平方因子をもつ約数の係数が 00 になり、平方因子をもたない約数の符号だけが残るため、自然にMöbius関数になる。

乗法性の証明の型

互いに素な法に分ける問題では、中国剰余定理で剰余類を直積に分解するのが最も安全である。単に積公式から示してもよいが、剰余類の全単射を明示すると、なぜ個数が積になるかが明確になる。

第4問 グラフ理論

極大と最大の違い

極大は「これ以上一本も追加できない」という局所的な条件であり、最大は「辺数が最も多い」という大域的な条件である。上の M3M_3 は未被覆頂点が残るが、未被覆頂点同士を結ぶ利用可能な辺がないため極大である。一方、M4M_4 が存在するので M3M_3 は最大ではない。

Hall条件の使いどころ

最大でないことを示すには、Hall条件を破る部分集合を探すのが速い。この図では下側の三つの頂点が二つの頂点にしか接続していないため、全被覆は不可能である。

帰納法の二つのケース

Hall条件がすべての空でない真部分集合で厳しい場合は、任意の一辺を先に選んでも残りにHall条件が残る。等号を満たす部分集合がある場合は、その部分と補集合に分割してそれぞれ帰納法を適用する。この二分がHallの結婚定理の標準的な証明である。

第5問 数学基礎論I

有限個なら交差してよい

「ほとんど含まれる」は有限個の例外を許す関係である。有限個の集合に同時にほとんど含まれることは、例外集合の有限和を取ればよいので簡単に扱える。(3)はこの事実をそのまま使っている。

可算個では対角化が必要

可算個すべての条件を一度に満たすには、最初の nn 個の条件だけを第 nn 段階で満たすように区間を区切る。XiX_i をほとんど含む性質は、十分後の区間では必ず XiX_i が採用対象に入ることで保証される。YjY_j にほとんど含まれる性質は、十分後の区間では jj 番目までの制約がすべて有効になることで保証される。

第6問 数学基礎論II

否定の実現子集合

この実現可能性では、¬B\neg B は BB の実現子から ⊥\bot の実現子を作る関数である。しかし ⊥\bot の実現子は存在しない。したがって、BB に実現子が一つでもあれば ¬B\neg B は実現不能であり、BB に実現子がなければ任意の数が空虚に ¬B\neg B を実現する。

Σ1\Sigma_1 と探索

Σ1\Sigma_1 式は、計算可能に確認できる条件を満たす witness が存在する、という形である。真であれば総当たり探索がいつか止まる。この性質が、二重否定から実際の実現子を取り出す手続きの核になる。

一様排中律が強すぎる理由

A(n)∨¬A(n)A(n)\vee\neg A(n) をすべての nn について実現できる一つのプログラムがあると、選言のタグを見るだけで A(n)A(n) の真偽を判定できる。停止問題を A(n)A(n) に選ぶと、これは停止問題の決定可能性を意味してしまう。

第7問 量子力学

Pauli行列の反交換

この問題の中心は、Pauli行列が二乗して単位行列になり、異なるもの同士は反交換する点である。これにより (v⋅σ)2=I(\mathbf{v}\cdot\boldsymbol{\sigma})^2=I が一行で出る。

指数関数の扱い

A2=IA^2=I なら、AA の偶数乗は II、奇数乗は AA である。したがって行列指数関数は三角関数と同じ級数に分かれる。固有値分解を使わなくても、級数だけで十分に示せる。

分散の検算

ZZ の固有値は ±1\pm1 なので、任意の正規化状態で ⟨Z2⟩=1\langle Z^2\rangle=1 である。したがって分散は 1−⟨Z⟩21-\langle Z\rangle^2 に簡約される。t=0t=0 では初期状態が ZZ の固有状態なので分散は 00 になり、得られた式とも一致する。

第8問 アルゴリズム設計法

Big-Oで分かること

T1,T2T_1,T_2 が同じ上界 O(f)O(f) をもつことから言えるのは、和も O(f)O(f) であることまでである。差、比、相互の優劣は下界の情報がないため決まらない。

LISの標準解法

L[ℓ]L[\ell] は長さ ℓ\ell の候補のうち末尾が最も小さいものだけを残す。末尾が小さいほど後続の値をつなげやすいので、他の候補を捨てても最適性を失わない。これが二分探索による O(nlog⁡n)O(n\log n) 解法の不変条件である。

値域が小さい場合

値が定数種類しかないとき、二分探索よりも値ごとのDPが直接効く。狭義増加なので、値 vv に接続できるのは vv より小さい値で終わる列だけである。値域が定数であることを計算量に反映させるのがポイントである。

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

2020〜2026年度・6回 · ¥3,200

解答PDFの商品ページへ

年度別の解答例

  • 2026年度

    線形代数 / 微分積分 / 代数学

  • 2025年度

    線形代数 / 微分積分 / 代数学

  • 2024年度

    線形代数 / 微分積分 / 代数学

  • 2022年度

    第1科目・線形代数 / 第1科目・微分積分 / 第1科目・代数学

  • 2020年2月実施

    線形代数 / 微分積分 / 離散数学

  • 2019年8月実施(このページ)

    線形代数学 / 微分積分学 / 離散数学

2019年8月実施の出題内容

大問分野主題解説の小見出し最終答
第1問線形代数線形代数学直交化の見通し / 表現行列の読み方あり
第2問微分積分・解析微分積分学内点で最大を取るときの符号 / 積分の分母を見るあり
第3問—離散数学積公式の本質 / Möbius関数が現れる理由あり
第4問—グラフ理論極大と最大の違い / Hall条件の使いどころあり
第5問数学数学基礎論I有限個なら交差してよい / 可算個では対角化が必要あり
第6問数学数学基礎論II否定の実現子集合 / Σ_1 と探索あり
第7問—量子力学Pauli行列の反交換 / 指数関数の扱いあり
第8問情報アルゴリズム設計法Big-Oで分かること / LISの標準解法あり

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

名古屋大学の他の解答PDF

院試対策ガイド

名古屋大学の公式過去問

公開年度範囲
2023〜2026(博士前期課程)
公式の解答例
解答例の掲載なし
英語の扱い
2027年度夏はTOEIC L&R公開テスト・TOEFL iBT(Home Edition可)・IELTS・Duolingo。2024年4月1日以降の成績、2026年7月21日16時必着。コピー・印刷は所定の手書き記載と署名または捺印が必要。

名古屋大学の公式過去問PDF