九工大 情報工学府 専門科目（知能情報工学） 2025年度 院試 解答例・解説

個数問題は自由度を数える

二項関係の個数は、各順序対を入れるかどうかの自由度で数える。対称性や反対称性は、非対角成分を1個ずつではなく、 unordered pair ごとの選択に変える条件だと考えると整理しやすい。

関係の性質は同値変形から入る

$R_1$ は見た目は $x,y$ の式だが、実際には $x$ の偶奇だけで決まる。$R_2$ は「積が3の冪」という条件なので、各因子も3の冪でなければならない。このように条件を短く言い換えてから性質判定に進むと、反例を探す時間が短くなる。

正規言語の判定

有限オートマトンは有限個の状態しか持てない。剰余や偶奇のような有限情報は覚えられるが、任意長のコピーや個数差そのものは覚えられない。この切り分けが問題3のほぼ全体を決める。

継承まわりの見方

Sorter は共通のデータ保持、表示、交換処理を提供し、実際のソート方法だけをサブクラスに任せる構造である。この設計では、親クラス側の performSort を抽象メソッドにし、各サブクラスで具体的なソート手順を書くのが自然である。

中央値コード

中央値は最大でも最小でもない値である。条件式では $$x_1\le x_2\le x_3 \quad\text{または}\quad x_3\le x_2\le x_1$$ なら $x_2$ が中央値、同様に $x_3$ が中央にある2通りを判定する。どちらでもなければ $x_1$ が中央値なので、初期値の pv=x1 をそのまま使える。

出力追跡のコツ

ASorter は右側から確定していく選択ソート型の動きである。内側ループで data[i] より小さい要素を見つけるたびに交換するため、各外側ループ終了時点で末尾側に小さい値が集まる。

BSorter はスタックで処理区間を持つ非再帰クイックソートである。表示は各区間の分割が終わった直後に行われるので、ピボット選択と左右の添字更新を1ステップずつ追う必要がある。空欄の直前までをすべて埋めようとせず、指定された回の配列だけを丁寧に追跡するとミスが減る。