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

第1問 情報基礎
指数時間と擬多項式時間
単純な列挙や再帰では、選ぶ・選ばないの分岐が 回続くため、基本的に 個の候補を調べる。動的計画法は、和の値 を状態に含めることで重複計算を消す。計算量 は入力値 の大きさに依存するため、ビット長に対する多項式時間ではなく、擬多項式時間である。
答案で落としやすい点
再帰の計算量を としてしまう誤りが多い。 は1ずつ減るが、各段で呼び出しが2本に分かれるので、再帰木全体の節点数を見る必要がある。一方、動的計画法では同じ を一度だけ計算するため、表の要素数がそのまま計算量になる。
2. 強平衡二分木と整列
- 通常の整列木として用いる二分木、すなわち内部頂点が左右の子を持つ二分木を考える。高さを とする。すべての葉の深さの差が1以下なので、葉は深さ または にしか現れない。したがって、深さ の頂点はすべて内部頂点であり、少なくとも 個の頂点が存在する。よって であり、 が従う。
- 強平衡二分木を二分探索木として用い、数を1個ずつ挿入する。各頂点では、挿入する値を頂点の値と比較し、小さければ左、大きければ右へ進む。木の高さが なので、1回の挿入は 時間でできる。 個すべてを挿入した後、左部分木、頂点、右部分木の順に中間順走査を行うと昇順の列が得られる。 したがって、挿入全体が 、走査が であり、全体の計算量は である。
高さ評価の考え方
高さが大きいのに頂点数が少ない木は、細長い鎖のような形をしている。しかし葉の深さがほぼそろうという条件は、そのような鎖を許さない。高い葉が1つあるなら、浅い段の枝分かれも一定程度存在するため、頂点数は高さに対して指数的に増える。
整列で使う性質
二分探索木による整列では、探索経路の長さが性能を決める。平衡性がなければ高さが になり、挿入が全体で になる。強平衡性により高さが対数に抑えられるため、比較ソートとして標準的な が得られる。
3. 有向グラフの最短路
- 始点から到達可能な負閉路があり、その負閉路から頂点 へ到達できるとき、 から への経路の途中でその閉路を何度でも回れる。閉路を1周するたびに経路長はさらに小さくなるので、最小値は有限の値として定まらない。 すべての頂点への最短距離を同時に考えるなら、始点から到達可能な負閉路が存在する場合が問題である。負閉路の影響を受ける頂点では、距離を 方向へいくらでも小さくできる。
- 辺の長さに負の値があり得る場合は、Bellman--Ford 法を用いる。まず と初期化する。次に、すべての辺 について なら と更新する操作を、 回繰り返す。負閉路がなければ、最短路は高々 本の辺からなる単純路として取れるため、この時点ですべての最短距離が得られる。 計算量は、各反復で全辺を見るので である。さらに1回全辺を調べて更新可能な辺が残っていれば、到達可能な負閉路を検出できる。
- 負の長さの辺がない場合は、Dijkstra 法を用いる。未確定頂点のうち暫定距離 が最小の頂点を選び、その頂点を確定する。非負辺では、未確定頂点を経由してその距離を後から小さくすることができないため、この貪欲な確定が正しい。 優先度付きキューを用いれば、各頂点の取り出しと各辺の緩和により で実行できる。単純な配列で最小頂点を探す実装では である。
負閉路の意味
負の辺があるだけでは最短距離が壊れるとは限らない。問題になるのは、合計長が負の閉路である。閉路なので何度でも通れ、通るたびに経路長を下げられる。このとき「最小の経路」は存在せず、距離は有限値として定まらない。
Bellman--Ford と Dijkstra の違い
Bellman--Ford 法は全辺の緩和を繰り返すため遅いが、負辺に対応でき、負閉路検出もできる。Dijkstra 法は最小暫定距離の頂点を順に確定する高速な方法だが、その正しさは辺長が非負であることに依存している。
解答
- すべての選び方を列挙する場合、各 について「選ぶ」「選ばない」の2通りがあるので、候補は 個である。各候補の和を最初から計算すれば1候補あたり 時間であり、全体は である。途中で和を更新しながら列挙しても、指数個の候補を調べる点は変わらないので、支配的には 個の状態を扱う。
- 再帰関数は、 のとき高々2個の再帰呼び出しを行い、 が1ずつ減る。重複する部分問題を記録していないため、同じ が何度も再計算される。 最悪の場合、短絡評価で早く終了せず、深さ の二分再帰木をほぼすべて探索する。したがって呼び出し回数は であり、各呼び出しの処理を定数時間とみなすと計算量は である。
- 動的計画法では、 を「先頭 個からいくつか選んで和を にできるか」を表す値とする。 を使わない場合と使う場合を分けると である。したがって空欄は次のように埋めればよい。 表の大きさは で、各成分を定数時間で計算できる。したがって計算量は である。
最終答
全列挙は 、単純再帰は最悪 、動的計画法は を用いて 。
高さは なので 。二分探索木として挿入し中間順走査すれば、整列は 。
最短距離が有限に定まらない典型例は到達可能な負閉路がある場合。一般には Bellman--Ford 法で 、非負辺なら Dijkstra 法で 。
第2問 数理基礎
自由変数と双対制約
主問題の変数に非負制約があるかどうかで、双対側の制約の形が変わる。非負変数に対応する双対制約は不等式だが、自由変数に対応する制約は等式である。また、等式制約に対応する双対変数は符号制約を持たない。
最適値の示し方
「実行可能解で値が0になる」だけでは、最小値が0であることは示せない。0より小さい実行可能解がないことを示す必要がある。本問では、同じ値0を持つ双対実行可能解を作るのが最も短い。弱双対性により下界0が出るので、主問題の実行可能値0と合わせて最適性が確定する。
2. 指数分布と条件付き分布
- は独立で平均1の指数分布なので、密度は で である。 の密度は畳み込みにより であり、 では である。これは形状母数2、率1のガンマ分布である。
- 確率分布の再生性とは、同じ種類の分布に従う独立な確率変数の和が、再び同じ種類の分布族に属する性質である。例えば正規分布や、同じ率を持つガンマ分布族はこの性質を持つ。 指数分布どうしの和は上で見たように密度 のガンマ分布になり、指数分布そのものではない。したがって、指数分布だけを1母数分布族として見れば再生性はない。ただし、指数分布を形状母数1のガンマ分布と見れば、ガンマ分布族の中では再生性がある。
- で同時密度は である。したがって である。ゆえに、条件付き分布は区間 上の一様分布である。
和の密度は畳み込み
独立な連続確率変数の和では、密度を畳み込む。指数分布の場合、積 が に依存しないため、積分区間の長さ だけが残る。このため密度は になる。
条件付き密度の直観
和 が固定されると、 で決まる。指数分布の同時密度は、この直線上で一定になる。したがって、 は から までどこにあっても同じ重みを持ち、一様分布になる。
3. 逐次推定量
- は定数であり、 である。したがって である。これが任意の に対して に等しいためには でなければならない。
- (1)より である。 が不偏である条件は である。 は独立で分散 なので である。 として最小化すると となる。
- (2)より で、分散は である。不偏条件は であり、独立性から とおいて最小化すると なので である。
- 帰納的に、 が の標本平均で、分散が であるとする。不偏条件は であり、 は過去の標本と独立なので として最小化すると を得る。このとき であり、分散は で最小になる。
不偏条件は係数和を見る
過去の推定量が不偏なら、その期待値は である。新しい標本 の期待値も なので、線形結合が不偏である条件は係数の和が1になることに尽きる。ただし初期値 は任意の に対して不偏ではないため、最初だけ が必要になる。
分散最小化の意味
独立な不偏推定量を線形結合するとき、分散が小さい推定量ほど大きい重みを持たせるのが最適である。 個の平均は分散 、新しい観測は分散 なので、既存平均に 、新標本に の重みを与えると、ちょうど全標本の平均になる。
第3問 数学解析
高階でも特性方程式でよい
係数が定数で右辺が の線形方程式なので、 を代入すれば が得られる。根は重複しないため、各根に対応する指数関数を一つずつ取れば基底になる。
実数値解の書き方
複素根をそのまま並べると複素数値解に見える。実数値関数を求める問題では、共役根 の線形結合を、実部と虚部に対応する2つの実解へ直すのが標準的である。
2. 複素平面上の閉曲線と留数
- とおくと 部分分数分解により 曲線の回転数を と書くと 図および曲線の通り方から、原点の周りの回転数は 、点 の周りの回転数は である。したがって
積分を閉曲線積分として読む
被積分関数は を含むので、 という置換により複素平面上の閉曲線積分になる。あとは極 が曲線に対して何回巻かれているかだけを数えればよい。
符号の確認
部分分数分解の符号を誤ると答えが逆になる。 なので、原点の寄与は 、点 の寄与は である。回転数が なら、合計は となる。
3. フーリエ変換と積分
フーリエ変換を で定める。
- 与えられた三角形型関数は と書ける。畳み込み定理より である。 では極限値として とする。
- (1)の式を で積分する。フーリエ反転公式から、連続点 で である。、また は偶関数なので したがって
- Parseval の等式を用いると 右辺の積分は である。一方 よって であり、偶関数性から を得る。
三角形関数は畳み込み
直接積分でも計算できるが、三角形型関数を区間の指示関数の畳み込みと見ると一気に簡単になる。矩形関数のフーリエ変換は であり、畳み込みはフーリエ変換側で積になる。
積分値の取り出し方
は反転公式で の積分から取り出せる。 は の2乗に現れるため、Parseval の等式を使うのが自然である。フーリエ変換の規約によって の位置が変わるので、最初に規約を書くことが重要である。
第4問 情報物理
傾いた板は微小コンデンサーの並列
電位差は板全体で同じなので、場所ごとに間隔の違う微小コンデンサーが並列につながっていると考える。したがって容量は を面積方向に積分する。平均間隔を単に として代入すると、対数が出る効果を落としてしまう。
電池接続時の力の符号
電池につながっている場合、機械的な力はコンデンサー単体のエネルギーだけでなく、電池とのエネルギー授受を含む有効エネルギーで判断する。容量が増える向きに電場は仕事をするため、静電的な一般化力は となる。外力の符号は「電場の力と同じ向きに引くのか、準静的に支えるのか」という取り方で変わるので、答案では向きの約束を明記するのが安全である。
2. マイケルソン・モーリー実験
- エーテルに対して装置が速度 で動くと仮定する。運動方向の腕では、往路の光速は装置から見て 、復路は なので 運動方向に垂直な腕では、鏡に戻るために光は横方向成分 で進む必要があるので 共通部分の時間は差に効かない。したがって では である。
- 振動数は なので、時間差 に対応する位相差は したがって近似的には である。
- 観測面に現れる干渉縞を観測する。装置を90度回転すると、運動方向に平行な腕と垂直な腕が入れ替わるため、予想される時間差の符号が反転する。したがって、エーテル風が存在すれば干渉縞が移動するはずであり、その縞の移動量から位相差を測定できる。
- 予想された位相差が検出されなかったことは、光速が地球の運動方向に依存するという静止エーテル仮説を支持しない。実験結果は、真空中の光速が慣性系や伝播方向によらず同じであるという考え方、すなわち特殊相対性理論の基本的な仮定と整合する。
平行腕と垂直腕で時間が違う理由
エーテル仮説では、装置が媒質中を動くため、運動方向の往復では追い風・向かい風の効果が出る。垂直方向では、鏡が横へ動く分だけ斜めに進む必要があり、有効な垂直成分が になる。この2つを比べるのが本問の計算である。
観測量は絶対位相より縞の移動
干渉計で直接測るのは位相差そのものではなく、位相差が変わったときの干渉縞の移動である。装置を回転させると予想位相差が変化するので、縞の移動があるかどうかを精密に見る。検出されなかったことが、歴史的に重要なヌル結果である。
3. フラウンホーファー回折
- 光学的変位とは、光波を表す振動量である。電磁波として見れば電場ベクトルまたは磁場ベクトルの一成分を表す複素振幅と考えればよい。実際に観測される光強度は、複素振幅の絶対値の2乗に比例する。
- である。 が十分大きく、開口の大きさが観測距離に比べて小さいとき、 のうち、開口内で変化する2次項 を無視する。 とおくと一次近似により である。ただし である。したがって となり、観測点によらない係数 を比例定数に吸収すれば を得る。
- (2)の式は、開口面上の光学的変位 の2次元フーリエ変換である。観測方向を表す変数 によって振幅が決まるので、遠方のスクリーン上の明暗分布は開口関数のフーリエ変換の絶対値2乗になる。これはフラウンホーファー回折であり、開口の形が遠方回折像を決める。
- 開口は半径 の円形開口である。 とおく。極座標を用いると、振幅は円対称となり である。したがって光強度は の形になる。中央に強い明るい円盤があり、その外側に暗環と明環が交互に現れる Airy パターンである。
遠方近似の役割
距離 が十分大きいと、開口内の点による距離差は観測方向への射影で近似できる。これにより位相が となり、開口上の積分がそのままフーリエ変換になる。
円形開口の像
円形開口は回転対称なので、回折像も中心からの距離だけで決まる。2次元フーリエ変換を極座標で計算すると Bessel 関数 が現れる。中央の明るい領域と周囲のリングは、有限な円形開口を通った光が干渉することで生じる。
年度別の解答例
2023年度の出題内容
同じテーマを出した他大学・他年度
前年度(2022年度)との違い
大阪大学の他の解答PDF
院試対策ガイド
大阪大学の公式過去問
- 公開年度範囲
- 専攻・科目別に掲載(情報基礎数学は2005〜2026年度、情報数理・生物情報は2022〜2026年度など)
- 公式の解答例
- 解答例の掲載なし
- 英語の扱い
- 2027年4月一般は情報基礎数学のみ90分の独自英語。情報科学専攻は2024年7月以降のTOEIC公開スコア、提出困難ならTOEFL。IP・ITP不可。