# 阪大 情報科学研究科 情報数理学専攻 専門科目（情報数理学） 2021年度 院試 過去問 解答例・解説

> 阪大 情報科学研究科 情報数理学専攻 専門科目（情報数理学） 2021年度の院試過去問、4項目の解説。テーマは重積分と極座標、留数定理。大問1問の途中式・最終答を無料公開。解答PDFは6年分収録で3,200円。問題本文は非収録。

- Web版: https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-and-physical-sciences/2021
- 解答・解説PDF: https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-and-physical-sciences（税込3,200円、6年分を収録）
- 最終更新: 2026-11-16
- 公式の過去問: https://www.ist.osaka-u.ac.jp/japanese/examinees/admission/past-exam.php（専攻・科目別に掲載（情報基礎数学は2005〜2026年度、情報数理・生物情報は2022〜2026年度など）、公式の解答例: 解答例の掲載なし）
- 問題本文は収録していません。公式の問題と照らして読んでください。
- 大問ごとの解説は無料公開です。途中式と最終答は、ここに載っている大問を除き解答PDFに収録しています。

## 第1問 — 情報基礎

### 解説

**転倒数を見ると評価回数まで分かる**

この整列法は、左へ戻りながら隣接転倒を1つずつ解消する gnome sort 型の手続きである。交換回数だけなら転倒数そのものだが、条件式の評価回数は「前進した回数」も必要になる。$i$ の増減を収支で見ると、真の回数と交換回数の関係が一気に決まる。

**べき乗の回数は下位ビットで決まる**

平方は2進表記の桁数から決まり、追加で $a$ を掛ける回数は、最上位を除いた1ビットの数で決まる。$a^{15}$ の例では通常の平方反復より、加法鎖をうまく選ぶ方が少ない乗算で済む。

**行列の対角和の意味**

$(A^3)_{ii}$ は頂点 $i$ から出発して3歩で $i$ に戻る歩道の数である。単純無向グラフで長さ3の閉歩道が存在するのは三角形を回るときであり、1つの三角形は6通りに数えられる。この対応を書ければ、最大値・最小辺数の議論は三角形の数え上げに帰着できる。

### 解答

1. 整列アルゴリズム

- 配列を $1$ 始まりで表す。if文の条件式が評価される直前の $(i,A)$ は、順に

$$
\begin{array}{c|c}
i & A\\ \hline
0 & (2,6,1,3,8)\\
1 & (2,6,1,3,8)\\
2 & (2,6,1,3,8)\\
1 & (2,1,6,3,8)\\
0 & (1,2,6,3,8)\\
1 & (1,2,6,3,8)\\
2 & (1,2,6,3,8)\\
3 & (1,2,6,3,8)\\
2 & (1,2,3,6,8)\\
3 & (1,2,3,6,8)\\
4 & (1,2,3,6,8)
\end{array}
$$

である。最後に $i=5$ となって while ループを抜ける。
- このアルゴリズムで隣接交換が起こるたびに、配列の転倒数はちょうど1だけ減る。初期配列の転倒数を $S$ とすると、交換回数は $S$ 回である。
条件式が真になった反復では $i$ が1増え、偽になった反復では交換後に $i$ が1減る。初期値は $i=0$、終了時は $i=N$ だから、真になった回数を $U$ とすると

$$
U-S=N,\qquad U=N+S
$$

である。条件式の評価回数は真偽を合わせて

$$
T=N+2S
$$

である。
転倒数の最小値は $0$、最大値は逆順配列での $N(N-1)/2$ なので

$$
T_{\min}(N)=N,\qquad
  T_{\max}(N)=N^2
$$

である。
- 相異なる $N$ 個の実数がランダム順序で格納されているとする。各組 $(p,q)$, $pA[q]$ となる確率は $1/2$ である。したがって転倒数 $S$ の期待値は

$$
\mathbb{E}[S]
  =\binom{N}{2}\frac12
  =\frac{N(N-1)}4
$$

である。よって

$$
T_{\mathrm{ave}}(N)
  =N+2\mathbb{E}[S]
  =N+\frac{N(N-1)}2
  =\frac{N(N+1)}2
$$

となる。

2. べき乗計算

- $a^5$ では再帰呼び出しが

$$
5\to 2\to 1
$$

と進む。$n=2$ の段で1回の平方、$n=5$ の段で平方1回と奇数補正の乗算1回が行われるので、乗算回数は

$$
3
$$

である。
- $n$ の2進表記を

$$
n=(b_kb_{k-1}\cdots b_0)_2,\qquad b_k=1
$$

とする。再帰で $n$ を2で割っていくと、基底 $1$ に達するまでの非基底段は $k$ 段ある。各段で平方の乗算が1回ずつ行われるので、平方による乗算回数は $k$ 回である。
さらに、各段の現在値が奇数なら $a$ を掛ける。この奇数判定は、最上位ビットだけになった最後の $1$ では実行されないため、寄与するのは下位ビット $b_0,\ldots,b_{k-1}$ である。したがって乗算回数は

$$
k+\sum_{j=0}^{k-1} b_j
$$

である。
- 上のアルゴリズムで $a^{15}$ を求めると、$15=(1111)_2$ なので乗算回数は

$$
3+(1+1+1)=6
$$

である。より少ない方法として、例えば

$$
a^2=a\cdot a,\quad
  a^3=a^2\cdot a,\quad
  a^5=a^3\cdot a^2,\quad
  a^{10}=a^5\cdot a^5,\quad
  a^{15}=a^{10}\cdot a^5
$$

と計算すれば、乗算は5回で済む。

3. 隣接行列と三角形

- 単純無向グラフでは、$\operatorname{tr}(A^3)$ は長さ3の閉歩道の総数を数える。三角形1個は始点の選び方が3通り、向きが2通りあるので、$T(G)$ には $6$ と数えられる。
$G_1$ は四角形のみで三角形を含まないから

$$
T(G_1)=0
$$

である。$G_2$ は対角線によって2個の三角形を含むので

$$
T(G_2)=6\cdot2=12
$$

である。
- $T(G)>0$ であるためには少なくとも1個の三角形が必要である。三角形だけで辺は3本であり、残りの $N-3$ 頂点を連結に保って加えるには、木のように1本ずつ辺を追加すればよい。したがって辺数

$$
3+(N-3)=N
$$

で条件を満たせる。
一方、連結グラフが三角形を含むなら、その三角形の3辺に加えて、残り $N-3$ 頂点を三角形を含む成分へ接続するために少なくとも $N-3$ 本の辺が必要である。よって最小値は

$$
N
$$

である。
- $T(G)$ は三角形数の6倍である。三角形数を最大にするには、すべての3頂点の組が三角形になればよく、これは完全グラフ $K_N$ で達成される。したがって

$$
\max T(G)=6\binom{N}{3}
  =N(N-1)(N-2)
$$

である。

### 最終答

整列アルゴリズムの条件評価回数は $N+2S$。よって $T_{\min}(N)=N$, $T_{\max}(N)=N^2$, $T_{\mathrm{ave}}(N)=N(N+1)/2$。べき乗の乗算回数は $k+\sum_{j=0}^{k-1}b_j$。グラフでは $T(G)=6\times$三角形数なので、$T(G_1)=0$, $T(G_2)=12$, 条件を満たす連結グラフの最小辺数は $N$, 最大値は $N(N-1)(N-2)$。

## 第2問 — 数理基礎

### 解説

**線形計画のパラメータは凸包で読む**

$x_i$ は非負で和が1なので、各列ベクトルを混ぜる重みである。したがって実行可能な $(\alpha,\beta)$ は、行列計算を解くよりも、4点の凸包として見るのが最も早い。

**極座標ではなく傾きで変換する**

$T=Y/X$ は角度そのものではなく傾きである。右半円では $X>0$ なので $T$ は全実数を動く。ヤコビアン $s/(1+t^2)$ を落とすと密度の規格化が崩れる。

**対応のある検定**

同じ対象を2つの秤で測っているので、独立2標本ではなく差 $d_i=x_i-y_i$ の1標本検定として扱う。自由度は標本数5に対して $4$ であり、両側検定では表の上側確率 $0.025$ の列を使う。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-and-physical-sciences

## 第3問 — 数学解析

### 解説

**極が単位円の内外どちらにあるか**

複素積分では、$a$ の値によって極 $\pm ia$ が単位円の内側に入るかが変わる。$a>1$ の場合は外側の極を直接扱うのではなく、$z=0$ まわりの級数展開で留数を読むと、極限まで自然に計算できる。

**積分因子の決め方**

$\lambda$ が $xy$ だけの関数である、という指定を使うと完全性条件が常微分方程式に落ちる。この問題では $xP-yQ$ と $P_y-Q_x$ が同じ形になり、$\lambda'+\lambda=0$ が直ちに得られる。

**級数公式はParsevalで出す**

部分分数展開を使ってもよいが、この設問の流れではフーリエ係数を計算し、Parseval の等式を使うのが最短である。$a$ が整数でないため分母 $k+a$ が0にならない点も明記しておくと答案として安定する。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-and-physical-sciences

## 第4問 — 情報物理

### 解説

**双極子近似の有効範囲**

遠方近似では、電荷間隔 $d$ に比べて観測距離 $r$ が十分大きいことが必要である。このとき単極子項は $+q$ と $-q$ で打ち消し合い、最初に残る項が双極子モーメント $\mathbf{p}=qd\,\hat{\mathbf{z}}$ に比例する。

**非干渉光源では強度を積分する**

光源上の異なる点から出た光は位相関係がランダムなので、電場振幅を足してから二乗してはいけない。各点光源が作る二重ピンホール干渉の強度を、光源幅にわたって積分する。この平均化が $\sin\alpha/\alpha$ の因子を生み、光源が広がるほど縞が見えにくくなる。

**鮮明度と視直径**

鮮明度の零点は、広がった光源の両端からの寄与が干渉項を打ち消す条件を表す。最初の零点を使うと測定誤差に比較的強く、$D/r=\lambda/d$ という簡潔な形で光源の視直径を推定できる。

**発色の分類**

虹は分散と幾何光学、夕焼けは散乱、タマムシの羽は薄膜・多層構造による干渉で説明する。名称だけでなく、どの波長が強く届くか、または強め合うかまで書くと物理の答案になる。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-and-physical-sciences

---

出典: 院試hub（https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-and-physical-sciences/2021）。引用するときはWeb版のURLを示してください。
