院試hub

名古屋工業大学 院試 過去問 解答例

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

全6問。情報2問。テーマタグは4件（重積分と極座標・留数定理・フーリエ級数）。

最終更新:

このページで公開
解説6問と大問1問の途中式・最終答（全6問）
解答PDFに収録
途中式と最終答（最終答つき6問）
問題本文
非収録

名工大 情報工学系 2024年度 院試 過去問の出題内容（全6問）

この6問の分野は情報2問です。

大問分野主題解説の小見出し最終答
第1問情報計算機ソフトウェア—あり
第2問情報計算機ハードウェア—あり
第3問—情報数学—あり
第4問—微分積分・線形代数—あり
第5問—数理科学1—あり
第6問—数理科学2—あり

この年度の解説には採点の置き所6件・典型ミス5件・検算1件が付いています。

2024年度の出題テーマと、同じテーマを出した他大学・他年度

この年度は3問に4テーマが出ています。

テーマこの年度全体の出題実績他大学の直近出題
重積分と極座標第4問23大学・142問
留数定理第5問18大学・126問
フーリエ級数第5問11大学・30問
正規表現・形式言語第1問10大学・30問

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

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

文法は、SS が初めの aa と末尾の XX を同時に増やし、YY が中央の bb と末尾の XX を同時に増やす、と読むと生成形がすぐ分かる。

採点の置き所

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

典型ミス

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

解答

I. 巡回路と木

全探索では始点を固定しても巡回順は (n−1)! (n-1)! 通りある。各候補の評価まで含めると計算量は Θ(n!)\Theta(n!) である。辺を重み順に並べる比較ソートは Ω(mlog⁡m)\Omega(m\log m) を要する。

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

4頂点例では Kruskal 法により辺重み 3,4,53,4,5 を選び、 W=12. W=12. 深さ優先順の近似巡回路の一例は重み 2121、最適巡回路は重み 1919 である。

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

3文字目から末尾側の条件を満たす語は、末尾3文字のうち先頭2文字を指定する正規表現で (a∣b)∗ba(a∣b) (a\mid b)^*ba(a\mid b) と表せる。DFA は長さ3以下の接尾辞だけを状態として保持すればよい。

文法 S→aSX∣aYX,Y→bYX∣bX,X→a S\to aSX\mid aYX,\quad Y\to bYX\mid bX,\quad X\to a が生成する語は apbqap+q(p,q≥1) a^p b^q a^{p+q}\qquad(p,q\ge1) である。長さ8の語は p+q=4p+q=4 なので abbbaaaa,aabbaaaa,aaabaaaa. abbbaaaa,\quad aabbaaaa,\quad aaabaaaa. この言語が正規であると仮定し、apbap+1a^pba^{p+1} の初めの aa の列をポンプすると、末尾の aa の個数との等式が壊れる。よって正規ではない。プッシュダウンオートマトンは、初めの aa と中央の bb に対して1個ずつ記号を積み、末尾の aa で1個ずつ取り除く構成でよい。

最終答

全探索は (n−1)!(n-1)! 通り、Kruskal の重みは 1212、近似例は 2121、最適は 1919。文法の言語は apbqap+qa^p b^q a^{p+q}、長さ8は abbbaaaa,aabbaaaa,aaabaaaaabbbaaaa,aabbaaaa,aaabaaaa。

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

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

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

採点の置き所

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

典型ミス

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

計算機ハードウェアの途中式・最終答をPDFで見る

第3問 — 情報数学

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

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

採点の置き所

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

典型ミス

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

情報数学の途中式・最終答をPDFで見る

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

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

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

採点の置き所

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

検算

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

微分積分・線形代数の途中式・最終答をPDFで見る

第5問 — 数理科学1

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

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

採点の置き所

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

典型ミス

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

数理科学1の途中式・最終答をPDFで見る

第6問 — 数理科学2

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

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

採点の置き所

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

典型ミス

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

数理科学2の途中式・最終答をPDFで見る

名工大 情報工学系 院試 過去問の収録3年度

  • 2026年度（全6問）

    計算機ソフトウェア ／ 計算機ハードウェア ／ 情報数学

  • 2025年度（全6問）

    計算機ソフトウェア ／ 計算機ハードウェア ／ 情報数学

  • 2024年度（このページ・全6問）

    計算機ソフトウェア ／ 計算機ハードウェア ／ 情報数学