東京農工大学工学府博士前期課程 モデル問題例 その２（知能情報システム工学専攻）
本問題は、東京農工大学工学府博士前期課程・知能情報システム工学専攻（2023 年度新設予定）の専門科目のモデル問題例です。本専攻への受験を検討している方に、試験問題の「出題形式(問題数等)」や「出題範囲 (分野・科目等)」などをイメージしてもらうために作成しました。
注意：本問題の無断転載・無断使用はご遠慮ください。

問【注意】１～６のうち 3 問を選び解答せよ。

題

用紙

１
以下の文章で示されたソートのアルゴリズム X について考える。ただし、ソートすべき n 個の要素は int 型配列 a の a[0], a[1], ..., a[n-1]に格納されているものとし、アルゴリズム
X はそれらの要素を小さい順に並べかえるものとする。
アルゴリズム X
a[0], a[1], ..., a[n-1]の最小値を選び、a[0]の要素と交換する（ただし、最小値が複数存在する場合は添字が小さい方の要素を選ぶものとする．以下同様）
a[1], a[2], ..., a[n-1]の最小値を選び、a[1]の要素と交換する
a[2], a[3], ..., a[n-1]の最小値を選び、a[2]の要素と交換する
・・・
これを最後まで繰り返す〔１〕 アルゴリズム X を C 言語の関数として記述せよ。関数の名前は sortX とし、関数 sortX
は配列 a および整数 n を受け取り、戻り値（返り値）は返さない関数とせよ。

〔２〕ソートすべき要素の個数を n としたとき、アルゴリズム X の最悪時間計算量と平均時間計算量をオーダーで示せ。ただし答えのみでよい。

〔３〕アルゴリズム X が安定なソートならばその理由を、そうでないならば反例を述べよ。

２頂点集合 V、枝集合 E からなる無向グラフ G = (V, E) に対して、以下の問いに答えよ。ただし、Gは、並行枝や自己閉路をもたないものとする。また、|V| は頂点数、|E| は枝数を表すものとする。
〔１〕G が木であるとき、|V| と |E| の間に成り立つ等式を示せ。ただし、答えのみでよい。
〔２〕G が森であるとき、|V| と |E| の間に不等式 |V| > |E| が成り立つことを証明せよ。
〔３〕V の部分集合 F に対して、F に属する全頂点を G から開放除去すると、残りのグラフに閉路が存在しなくなるとき、F をフィードバック頂点集合という。G が次数 d ( 2)の正則グラフであると仮定する。このとき、F、V、E に関して以下の不等式が成り立つことを証明せよ。
|F| > (|E| – |V|) / (d – 1)
ただし、無向グラフのある頂点の次数とは、その頂点に接続する枝の本数である。また、無向グラフの全頂点の次数が等しく d であるとき、そのグラフを次数 d の正則グラフという。さらに、無向グラフの頂点を開放除去するとは、そのグラフからその頂点とその頂点に接続するすべての枝を除去することを意味する。

３
図３－１に示すようなエミッタ接地１段増幅回路において、入力信号電圧𝒗𝒊 を印加し、出力信号電圧𝒗𝑶を得る場合、以下の各問いに答えよ。ただし、各コンデンサの容量値はすべて充分大きく、それらのインピーダンスは０と仮定できるものとする。

図３－１（１）上図増幅回路内に使用されている、 R1, R 2, RL , RE , C1, C 2, CE 各回路素子の役割をそれぞれ述べよ。
（２）図中に示した①～⑦の各点において、交流的に同電位となる点の組を全て挙げよ。
（３）図で使用しているトランジスタのエミッタ接地 h パラメータ (hie, hre, hfe, hoe)を用い、上図増幅回路の小信号等価回路を示せ。
ただし、エミッタ接地ｈパラメータを用いたトランジスタの小信号入出力の関係は以下に示すものとする。

v iv1  hiei1  hrev 2i 2  hfei1  hoev 2（,はそれぞれ交流電圧および交流電流、添え字の1 はトランジスタ自体の入力、 2 はトランジスタ自体からの出力を表す。）（４）図の増幅回路の電圧増幅率 Av を（３）で示した等価回路から導出せよ。
ただし近似として hre  hoe  0 とし、電圧増幅率vo
Av viと定義されるものとする。

Av は

４
図４－１は，半導体を用いたトランジスタの原理的な動作について説明した概要図である．ここでは，長さが L の真性半導体を用意し，両端には金属のオーミックコンタクト電極（電極 1，電極2）を形成している．いま，半導体のエネルギーギャップ以上のエネルギーを持つ光をパルス状に瞬間的に照射することで，その光が半導体に吸収され，Ne 個の電子と正孔が対になって発生したと仮定する．また，ここでは簡単のため，正孔は移動度がゼロであって動かないと仮定する．電極 1 を接地して電極 2 に正の電圧 V0 を印加しているので，光照射によって発生した過剰な電子は V0 により電極 2 へ移動し，電流 I0 が発生する．光照射がない場合には，電流 I0 は無視できるほど小さいとしてよい．

光照射

電極 1Ne電極 2正孔（移動度＝ゼロ）++++τe
NeI0V0τte--L-Nex
電子（移動度＝μe）

図４－１(1) 半導体の長さ L と印加電圧 V0 より半導体内部の平均電界 E = V0 / L としたとき，電子の走行時
間 τte を求めよ．ただし，電子の移動度を μe とし，電子の平均的な移動距離は半導体の長さ L としてよい．
(2) Ne 個の過剰な電子は，電子の走行時間 τte で半導体から掃き出されて，新しい電子が電極 1 から半導体内へ補充されることになる．この時の外部端子に流れる電流 I0 を求めよ．
(3) 電極 2 から見ると，(2)の I0 は，光照射により生成された Ne 個の電子が，Ne 個の正孔と再結合して消滅するまで流れ続けることになる．いま，電子と正孔の再結合時間を τe とし，電極 2 に取り出される電子の総数を Nex 個とした時の I0 を求めよ．
(4) 上の(2), (3)の関係より，光照射により生成された Ne 個の電子と，外部に取り出された電子の総数 Nex 個の関係を，β ( = τe / τte ) を用いて示せ．なお，このときの β は，光利得と呼ばれる．
(5) μe = 1000 cm2/V･s, V0 = 10 V, L = 100 µm, τe = 10 μs とした時，電子の走行時間 τte 〔s〕と β を求めよ．
(6) 上の(1)～(5)から，図４－１に示すトランジスタの原理的な動作における「増幅」の意味について述べよ．

５以下の問いに答えよ．ただし，論理変数 p, q 間の演算の記号は，AND: p･q または pq，OR: p+q，NOT: p̅，EOR (排他的論理和): p⊕q とする．また，最も簡単な積和形とは，積項数が最小の積和形の中でリテラル数（入力信号の総数）が最小のものとする．
答えのみ答案用紙の指定欄に書くこと．
〔１〕4 変数の関数𝑋 = (𝐴 ⊕ 𝐵 ⊕ 𝐶 ⊕ 𝐷) ⋅ 𝐵̅ ⋅ 𝐶を積和標準形（加法標準形）に変換せよ．
〔２〕最も少数の 2 入力 NAND のみを用いて𝑋 = 𝐴 + 𝐵 ⋅ 𝐶̅ を実現する回路を書け．
〔３〕図５－１の状態遷移図で表される順序回路について以下の問いに答えよ．
（１）状態遷移表を書け．ただし，FF の状態が𝑄0 , 𝑄1 , 𝑄2のときの状態名を𝑄0 𝑄1 𝑄2 とする．
（２）次の状態𝑄0 ′, 𝑄1 ′, 𝑄2 ′を表す関数（状態遷移関数）と，出力 Z を表す関数（出力関数）を，最も簡単な積和形で求めよ．

図５－１

６以下の問いに答えよ。「答えのみでよい」と書かれていない限り、途中の計算過程も示すこと。
〔１〕𝑎 を実数とする。確率変数 𝑋 の分散を 𝑉[𝑋] で表すとき、𝑉[𝑎𝑋] を 𝑎 と 𝑉[𝑋] を用いて表せ。ただし、確率変数 𝑋 の期待値を 𝐸[𝑋] で表すとき、実数 𝑎 と 𝑏 に対して 𝐸[𝑎𝑋 + 𝑏] =𝑎𝐸[𝑋] + 𝑏 が成り立つことは既知としてよい。
〔２〕投げると確率 𝑝 で表が、確率 1 − 𝑝 で裏が出るコインがある。このコインを 𝑛 回投げるとき、表が出る回数を 𝑌 とする。確率変数 𝑌 の期待値と分散を求めよ。ただし答えのみでよい。
〔３〕投げると確率 1/2 で表が、確率 1/2 で裏が出るコインがある。このコインを 40000 回投げる
とき、表が出る回数が 𝑘 回以下になる確率は 95％であるという。𝑘 の値を概算で求めよ。ただし、標準正規分布 N(0, 1) の確率密度関数
12𝑓(𝑧) =𝑒 −𝑧 /2√2𝜋に対し、+1.64∫+1.96𝑓(𝑧) 𝑑𝑧≈

0.90,−1.64が成り立つことを用いてよい。

∫−1.96+2.58𝑓(𝑧) 𝑑𝑧≈0.95,∫−2.58𝑓(𝑧) 𝑑𝑧 ≈ 0.99