阪大 情報科学研究科 情報数理学専攻 専門科目(情報数理学) 2022年度 院試 過去問 解答例・解説
- 大学
- 大阪大学
- 研究科・専攻
- 情報科学研究科 情報数理学専攻
- 科目
- 専門科目(情報数理学)
- 年度
- 2022年度
解説は全問、途中式と最終答は大問1問を無料で公開しています。PDFの収録範囲は商品ページで確認できます。問題本文は含みません。

第1問 情報基礎
中央の配列で分解する
条件 は、 を固定すると左側の候補数と右側の候補数の積に分解できる。アルゴリズムBはこの分解を使って、三つ組を直接列挙する代わりに個数だけを足し上げている。
なぜ二分探索で十分か
`sort` 後の配列では、条件 を満たす部分は先頭から連続し、 を満たす部分は末尾側に連続する。この境界位置だけを見つければ個数が分かるため、全要素を数える必要がない。
2. 符号付き和の判定
- で となるかを調べる。これは、 とする添字集合を とおくと すなわち となる部分集合があるかを調べる問題である。 したがって、全体和 が奇数なら直ちに「なし」と判定する。 が偶数のとき、目標値 に対する部分和問題として動的計画法を用いる。 とし、 を「先頭 個の整数からいくつか選んで和 を作れるか」とする。初期条件を とし、 で更新する。ただし の項は false とみなす。最後に が true なら「あり」、false なら「なし」と答える。
- 上の動的計画法では、表の大きさは であり、各成分は定数時間で計算できる。したがって時間計算量は である。入力整数の大きさを値そのものとして測ると擬多項式時間である。
- 判定問題DがNPに属することを示すには、証拠を多項式時間で検証できればよい。証拠として符号列 を与える。この長さは で入力長に対して多項式である。検証者は各 が または であることを確認し、和 を計算して かどうかを調べる。これは 回の加算と乗算で済むので、多項式時間である。よって判定問題DはNPに属する。
符号問題は分割問題
を付ける整数と を付ける整数に分けると、両群の和が等しいかを問う形になる。したがって、全体和が奇数ならそもそも不可能であり、偶数なら半分の和を作れるかを調べればよい。
NP所属で示すこと
NPに属することは「速く解ける」ことではない。解候補が与えられたとき、それが正しいことを速く確認できることを示す。ここでは符号列を受け取り、和が0かどうかを計算するだけでよい。
3. 連結無向グラフの直径・半径・次数
- 図のグラフでは、最長の最短距離は例えば と の間で達成され、長さは である。したがって直径は である。 各頂点から最も遠い頂点までの距離を調べると、 からはすべての頂点へ距離 以下で到達できる。一方、他の頂点では最大距離が少なくとも になる。よって中心は であり、半径は である。最大次数は、 が と接続しているので である。
- 成り立つ。中心を とし、直径を実現する2頂点を とする。中心の定義から である。三角不等式より なので である。また、半径はある頂点から他の頂点までの距離の最大値であり、直径は任意の2頂点間距離の最大値なので、任意の頂点の離心度は 以下である。したがって である。以上より が成り立つ。
- 成り立つ。中心からの幅優先探索を考えると、距離0の層は1個、距離1の層は高々 個、距離 の層は、親へ戻る辺を除いて高々 個である。したがって である。この右辺は なら 以下である。 の連結グラフは高々2頂点なので、 または で直接確認できる。よって任意の連結グラフについて が成り立つ。
中心は平均的に近い頂点ではない
中心は、他の頂点までの距離の平均ではなく、最大距離を最小にする頂点である。したがって全頂点への距離を見て、最も遠い頂点までの距離だけを比較する。
半径と直径の関係
は定義から直ちに分かる。 は中心を経由する道で直径を実現する2頂点を結ぶ、という三角不等式の使い方が核心である。
最大次数による頂点数評価
中心から幅優先探索木を伸ばすと、距離1では高々 個、距離2以降では親へ戻る辺を除いて高々 本ずつ枝分かれする。このため精密な上界は であり、 を用いた和はそれより粗いが扱いやすい上界である。
解答
- アルゴリズムAは、添字の三つ組 のうち を満たすものの個数を数えている。三重ループで 個の組を調べ、各組で行う比較と加算は定数時間であるから、時間計算量は である。
- を中央の値として固定すると、条件を満たす の個数は であり、条件を満たす の個数は である。これらは独立に選べるので、その に対する三つ組の個数は である。したがって空欄は とすればよい。
- 配列が昇順に整列済みなので、 は二分探索で求める。具体的には、 を満たす最後の位置、または となる最初の位置を二分探索する。返す値は である要素の個数である。同様に、 は となる最初の位置を二分探索し、そこから末尾までの要素数を返す。 いずれも探索範囲を各反復で半分にできるため 時間で実行できる。アルゴリズムBでは整列に 、各 に対して二分探索を2回行う部分に かかるので、全体は である。
最終答
Aは を満たす三つ組の個数を数え、計算量は 。Bの空欄は 。整列後の `less` と `greater` を二分探索で実装すれば、Bは 。
部分集合和 に帰着し、動的計画法で 時間。符号列を証拠として和を検証できるためNPに属する。
図のグラフは直径 、中心 、半径 、最大次数 。一般に は成り立つ。最大次数 と半径 からは幅優先探索で と評価できる。
第2問 数理基礎
尤度比順に選ぶ
は「状態 のときに と判定する確率」と読める。 の下での期待値を 以下に抑えながら の下での期待値を最大にするので、効率 が高い状態から採用するのが自然である。
双対の意味
双対変数 は制約 の価格である。 を固定すると、 が正の状態だけが採用される。これは比 がしきい値 を超える状態を選ぶという形で、(2) の解と対応している。
2. 超立方体内の2点間距離
, とする。各座標について は独立な 上一様分布である。
- とおく。 の密度は である。したがって であり、 なので である。
- の期待値は上で求めた通り である。また なので
- であり、各項は独立同分布である。したがって であり、 である。
- は独立同分布な確率変数 の標本平均である。大数の法則により に確率収束する。さらに中心極限定理より である。したがって が大きいとき、 は近似的に に従い、極限では に集中する。
1次元の差から始める
高次元距離の2乗は座標ごとの差の2乗の和である。したがって、まず1次元で の分布を求め、独立な和として期待値と分散を足し上げるのが最短である。
距離の集中
高次元では、距離の2乗を次元で割った量が平均値 の近くに集中する。これは高次元立方体内のランダムな2点間距離が、次元で正規化するとほぼ一定になることを意味する。
3. 3変数二値分布の最尤推定
- 対数尤度は である。例えば で微分すると ここで であるから を得る。 についても同様に なので、与えられた式が従う。
- 最尤推定では尤度方程式から、モデルの期待値が標本平均に一致する。与えられた度数から また
- である。二値変数では が成り立てば、残りの組合せの確率も周辺確率から決まるため独立である。よって と は独立である。 同様に なので、 と も独立である。
- とおく。上で求めた1次・2次モーメントから各同時確率は と表せる。 このモデルには3体相互作用項がないので、対数確率の3次交互作用は0である。すなわち であり、 が成り立つ。上の表を代入すると 非負性から であり、この範囲の解は である。したがって
指数型分布族の最尤方程式
指数型分布族では、自然パラメータで微分すると「観測された十分統計量の合計」から「モデルの期待値に を掛けたもの」を引いた形になる。最尤点ではこれが0になるため、十分統計量の経験平均とモデル平均が一致する。
二値変数の独立性
0/1変数では、、 である。したがって積率の等式 は、1になる事象どうしの積の確率が積に分解することを意味し、二値の場合は独立性そのものになる。
3体項がないことの使い方
1次と2次の期待値だけでは一般には は決まらない。しかし本問のモデルは2体相互作用までしか持たないため、対数線形モデルの3次交互作用が0という追加条件が入る。これが最後の方程式になり、三重積の期待値を決める。
第3問 数学解析
複素数化で一変数にする
係数行列 は、複素数 に対する掛け算 に対応する。外力も と書けるため、連立方程式を一つの複素一次方程式として解ける。
軌跡の読み取り
初期値0の解は である。角度は とともに増え、半径は から へ単調に増える。したがって単なる円運動ではなく、単位円を極限円とする螺旋である。
2. パラメータ付き定積分
を用いる。標準積分 を使うと、, に対して したがって
偶関数のフーリエ変換
の余弦変換は指数関数 になる。 を に直すと、この公式をそのまま使える。 なので減衰因子は である。
3. Haar型関数系
- 各 は値が なので である。また とする。 が一定である各小区間を、 はさらに等分して正負を同じ長さだけ取る。したがってその小区間上の積分は0であり、全体でも である。さらに定数関数 と各 の内積も、正の部分と負の部分の長さが等しいため0である。よって は正規直交系である。
- 正規直交系への最小二乗近似では、係数は内積で与えられる。したがって である。これは、誤差 が近似空間の各基底関数に直交するという正規方程式から従う。
- のとき また は長さ の小区間ごとに符号を交互に変える。1周期の長さを とすると、その前半と後半の寄与の差は であり、周期は 個ある。よって である。
直交性は正負の打ち消し
高い番号の関数は、低い番号の関数が一定である区間の中で正負を同じ長さだけ取る。そのため積を積分すると必ず打ち消し合う。この構造を言葉で説明できれば、細かい図を完全に描けなくても得点しやすい。
最小二乗係数は射影
正規直交系では、最小二乗近似の係数は単に内積である。基底が直交しているため、連立方程式を解く必要がなく、各係数が独立に決まる。
第4問 情報物理
divの右辺の違い
電場側には電荷密度が現れるが、磁場側は0である。この非対称性は、通常の電磁気学では磁気単極子を仮定しないことを表している。磁力線が閉曲線として描かれる理由もこの点にある。
波動方程式の導出
回転をもう一度取って、 の恒等式を使うのが定石である。自由空間では なので勾配項が消え、ラプラシアンと時間2階微分だけが残る。
2. 透明薄膜の反射
- 入射振幅を とする。薄膜表面で直接反射する光の振幅は である。薄膜内へ透過し、底面で1回反射して空気中に戻る光は、透過、反射、逆向き透過を1回ずつ受け、さらに1往復分の位相差を持つので である。
- 空気中に戻る反射光の総振幅は、薄膜内での繰り返し反射の等比級数で したがって ストークスの関係 , を用いると となる。振幅反射率を実数として扱えば、強度は である。
- のとき、分子は である。無反射となるには であればよい。したがって が条件である。
- 垂直入射で である。 より となり、整理して を得る。したがって である。 薄膜中の波長を とすると、1往復による位相差は である。無反射条件 から である。最も薄い膜は である。
等比級数として見る
薄膜内で1往復するたびに、振幅は 倍される。したがって多重反射は等比級数で和を取れる。直接反射の項と、薄膜内に入ってから戻る項を分けると符号を間違えにくい。
反射を消す二つの条件
無反射には、2つの反射波の大きさがそろうことと、位相が反対になることが必要である。屈折率条件 が大きさをそろえ、膜厚条件 が位相を反対にする。
3. 自然界で見られる色
- 花火の色は主に炎色反応による。金属原子や金属イオンが加熱されると、電子が高いエネルギー準位へ励起される。その電子が低い準位へ戻るとき、準位差に対応する波長の光を放出する。ストロンチウムは赤、バリウムは緑、銅は青緑など、元素ごとに準位構造が異なるため、固有の発光色が現れる。
- シャボン玉の色は薄膜干渉による。膜の表面で反射した光と、膜の裏面で反射して戻ってきた光が重ね合わさる。膜厚や屈折率によって光路差が変わり、ある波長は強め合い、別の波長は弱め合う。膜厚が場所によって少しずつ違うため、見る位置や時間に応じて虹色の模様が変化する。
- 牛乳が白く見える主因は散乱である。牛乳中には脂肪球やカゼインミセルなど、可視光の波長と同程度の粒子が多数分散している。入射光はこれらの粒子で多方向に散乱され、特定の波長だけでなく可視域の広い波長が混ざって目に届く。そのため透明ではなく白濁して見える。
発光・干渉・散乱を区別する
花火は物質が自ら光を出す発光、シャボン玉は同じ光が重なって強弱を作る干渉、牛乳は外から来た光が粒子で散らされる散乱である。現象名だけでなく、色が選ばれる物理的理由まで書くと答案として強い。
年度別の解答例
2022年度の出題内容
同じテーマを出した他大学・他年度
前年度(2021年度)との違い
大阪大学の他の解答PDF
院試対策ガイド
大阪大学の公式過去問
- 公開年度範囲
- 専攻・科目別に掲載(情報基礎数学は2005〜2026年度、情報数理・生物情報は2022〜2026年度など)
- 公式の解答例
- 解答例の掲載なし
- 英語の扱い
- 2027年4月一般は情報基礎数学のみ90分の独自英語。情報科学専攻は2024年7月以降のTOEIC公開スコア、提出困難ならTOEFL。IP・ITP不可。