# 名工大 工学研究科 情報工学系 2024年度 院試 過去問 解答例・解説

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

- Web版: https://inshihub.com/exam-solutions/nagoya-institute-of-technology/graduate-school-of-engineering/information-engineering/2024
- 解答・解説PDF: https://inshihub.com/exam-solutions/nagoya-institute-of-technology/graduate-school-of-engineering/information-engineering（税込2,580円、4年分を収録）
- 最終更新: 2026-11-15
- 公式の過去問: https://www.nitech.ac.jp/examination/in/test.html（2025〜2027年度、公式の解答例: 一部の年度・科目のみ公開）
- 問題本文は収録していません。公式の問題と照らして読んでください。
- 大問ごとの解説は無料公開です。途中式と最終答は、ここに載っている大問を除き解答PDFに収録しています。

## 第1問 — 計算機ソフトウェア

### 解説

TSP の2近似は、全域木を2重化したオイラー歩道を考えると見通しがよい。ショートカットで重みが増えない点に三角不等式を使う。

文法は、$S$ が初めの $a$ と末尾の $X$ を同時に増やし、$Y$ が中央の $b$ と末尾の $X$ を同時に増やす、と読むと生成形がすぐ分かる。

**採点の置き所**

TSP では、全探索の候補数、MST が下界になる理由、2近似の上界を別々に書くと部分点を拾いやすい。数値例では Kruskal 法で選んだ3辺の重み合計、近似巡回路の重み、最適巡回路の重みを混ぜずに示す。

**典型ミス**

文脈自由文法では、末尾の $a$ の個数が初めの $a$ と中央の $b$ の合計になる。$a^p b^q a^q$ と読んでしまうと、長さ8の列挙と非正規性の証明が両方ずれる。

### 解答

**I. 巡回路と木**

全探索では始点を固定しても巡回順は

$$
(n-1)!
$$

通りある。各候補の評価まで含めると計算量は $\Theta(n!)$ である。辺を重み順に並べる比較ソートは $\Omega(m\log m)$ を要する。

最小全域木の重みを $W$ とすると、どの巡回路から1辺を除いても全域木が得られるため、最適巡回路の重みは $W$ 以上である。一方、全域木の辺を往復して深さ優先順にたどり、すでに訪問した頂点を飛ばせば、三角不等式の下で重みは高々 $2W$ である。

4頂点例では Kruskal 法により辺重み $3,4,5$ を選び、

$$
W=12.
$$

深さ優先順の近似巡回路の一例は重み $21$、最適巡回路は重み $19$ である。

**II. 正規言語と文脈自由言語**

3文字目から末尾側の条件を満たす語は、末尾3文字のうち先頭2文字を指定する正規表現で

$$
(a\mid b)^*ba(a\mid b)
$$

と表せる。DFA は長さ3以下の接尾辞だけを状態として保持すればよい。

文法

$$
S\to aSX\mid aYX,\quad Y\to bYX\mid bX,\quad X\to a
$$

が生成する語は

$$
a^p b^q a^{p+q}\qquad(p,q\ge1)
$$

である。長さ8の語は $p+q=4$ なので

$$
abbbaaaa,\quad aabbaaaa,\quad aaabaaaa.
$$

この言語が正規であると仮定し、$a^pba^{p+1}$ の初めの $a$ の列をポンプすると、末尾の $a$ の個数との等式が壊れる。よって正規ではない。プッシュダウンオートマトンは、初めの $a$ と中央の $b$ に対して1個ずつ記号を積み、末尾の $a$ で1個ずつ取り除く構成でよい。

### 最終答

全探索は $(n-1)!$ 通り、Kruskal の重みは $12$、近似例は $21$、最適は $19$。文法の言語は $a^p b^q a^{p+q}$、長さ8は $abbbaaaa,aabbaaaa,aaabaaaa$。

## 第2問 — 計算機ハードウェア

### 解説

2の補数の範囲は $[-2^{n-1},2^{n-1}-1]$ である。演算前の値だけでなく演算結果もこの範囲に入る必要がある。

リングカウンタと Johnson カウンタは、初期状態による周期が違う。設計表では、D-FF の反転出力をそのまま使えるため NOT ゲートを数えない点に注意する。

**採点の置き所**

数値表現は、答だけでなく範囲判定の不等式を1つ添えると安全である。カウンタ設計では、現状態、次状態、入力値の表を先に作り、そこから論理式を簡単化した流れを残すと減点されにくい。

**典型ミス**

算術右シフトを論理右シフトとして扱うと負数の答が変わる。MIPS では添字をバイトアドレスに変換するため、要素数の加算とアドレスの4バイト加算を区別する。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/nagoya-institute-of-technology/graduate-school-of-engineering/information-engineering

## 第3問 — 情報数学

### 解説

加法雑音通信路では、入力を固定した条件付き出力分布は雑音分布の置換になる。容量は $Y$ を一様にできるかで決まり、今回は一様入力で達成できる。

グラフの推移閉包は、直接辺ではなく到達可能性で考える。反射閉包と推移閉包を混ぜないように分けて答える。

**採点の置き所**

通信路では $H(Y\mid X)$ を雑音分布のエントロピーとして求め、次に $H(Y)\le \log 3$ で上界を置き、最後に一様入力で達成できることを示す。この3段階が容量計算の答案になる。

**典型ミス**

反復符号の多数決では、正しい記号が2回以上出ればよい。3回すべて正しい場合だけを数えると $8/27$ で止まり、$20/27$ にならない。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/nagoya-institute-of-technology/graduate-school-of-engineering/information-engineering

## 第4問 — 微分積分・線形代数

### 解説

偏微分では、平方根の外側微分と分数の内側微分を分けるとよい。重積分は極座標にすると角度部分が $\pi$ として外に出る。

行列式は最後の列で展開すると、$a$ の項が各行から同符号で現れる。係数が $2,4,\ldots,2^{n-1}$ と足し上がるため閉じた形が得られる。

**採点の置き所**

接平面では、点の $z$ 座標、$f_x$、$f_y$ をそれぞれ明示してから平面式に代入する。行列式では $n=2$ の初期値と漸化式を両方書くと、一般式の根拠が明確になる。

**検算**

重積分の integrand は上半円板で正なので、答も正でなければならない。非自明解条件は $|A_n|=0$ と同値であり、$a=-1/(2^n-2)$ を代入すると一般式が0になることを確認できる。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/nagoya-institute-of-technology/graduate-school-of-engineering/information-engineering

## 第5問 — 数理科学1

### 解説

複素積分では、円内に入る極をまず判定する。$n=2$ だけは重極になるため、単純極の公式を使わない。

$x^2$ のフーリエ級数は偶関数であることを使うと半分になる。$x=\pi$ の代入と Parseval は、古典的な $\zeta(2),\zeta(4)$ の導出である。

**採点の置き所**

複素積分は、極の位置、極の位数、留数の3点を分けて書く。$n=1$ と $n=2$ だけ場合分けが必要になる理由を明示すると、一般式との混同を避けられる。

**典型ミス**

Parseval では $a_0^2$ の係数が $1/2$ になる。ここを落とすと $\sum 1/k^4$ の係数がずれるので、左辺の平均値積分と右辺の係数を同じ正規化で書く。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/nagoya-institute-of-technology/graduate-school-of-engineering/information-engineering

## 第6問 — 数理科学2

### 解説

補間の存在一意性は、Vandermonde 行列が正則かどうかに尽きる。行列式が0でない条件を、節点が互いに異なることとして言い換える。

比判定で $\rho=1$ となる例は、調和級数と $p=2$ の級数を並べるのが最も短い。どちらも比は1へ行くが収束性が異なる。

**採点の置き所**

補間では、3点を代入した連立方程式の解と、一般の Vandermonde 行列が正則である理由を別に示す。後半の級数では、比の極限、比較判定、項が0に近づかないことを問題ごとに使い分ける。

**典型ミス**

$\rho>1$ なら比判定で発散だが、$\rho=1$ では何も言えない。$\rho=1$ を発散条件として使う答案は、$1/n^2$ の反例で崩れる。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/nagoya-institute-of-technology/graduate-school-of-engineering/information-engineering

---

出典: 院試hub（https://inshihub.com/exam-solutions/nagoya-institute-of-technology/graduate-school-of-engineering/information-engineering/2024）。引用するときはWeb版のURLを示してください。
