平成 21 年度

大学院博士 (前期) 課程入学者選抜学力試験
複雑系情報科学領域

専 門 科 目
［120 分］注 意 事 項

1．試験開始の合図があるまで，この問題冊子を開かないでください．
2．出題科目およびページと科目の選択方法は，下表のとおりです．下記の指示に従って解答した４科目の解答用紙のみを提出してください．なお，ページ番号のついていない紙は下書き用紙です．
出 題 科 目
線形

代解

数

析情報

数

ペ ー ジ

問題数

選択方法

学

11問

左の必須科目２科目すべて

学

21問

学

31問

微分

方程式

41問

応用解析

学

5

1問

確率論・統計学

6

1問

アルゴリズムとデータ構造

71問を解答してください．

左の５科目のうちから２科目を選択し，解答してくだ
さい．

3．解答用紙は 8 枚に分かれているので，１科目に２枚の解答用紙を用いてください．
必須科目については指定された解答用紙を用いてください．解答に用いなかった解答用紙も含め，すべての解答用紙の所定欄に科目名，受験番号と氏名をはっきりと記入してください．

4．解答冊子の表紙の所定欄に受験番号と氏名をはっきりと記入してください．さらに，選択した科目名の先頭に○印を記入してください．

5．解答欄内に指定された問題番号（I，II など），問いの番号（問 1 など）が明記されていない場合には，問題番号，問いの番号を記入してから解答を始めてください．

6．計算または下書き用紙 4 枚が解答用紙と一緒にあります．
7．試験中に問題冊子の印刷不明瞭，ページの落丁・乱丁および解答用紙の汚れ等に気がついた場合は，静かに手を上げて監督員に知らせてください．

8．試験終了後，問題冊子および下書き用紙は持ち帰ってください．
9．問題ごとに配点が記されています．

線形代数学
I 2 次実行列 A = 

1−1−2−2 に関する以下の問いに答えよ．ただし，AT は A の転置行列を表わす．（配点 50 点）

問 1 AT A を計算せよ．
問 2 行列 AT A の固有値をすべて求めよ．
問 3 問 2 で求めた固有値のうち，値の小さい方 λ1 に対応する固有ベクトル v 1 と値の大きい方 λ2 に対応する固有ベクトル v 2 を求めよ．ただし，v 1 と v 2 の大きさは共に 1 とし，列ベクトルとして表わせ．
問 4 問 3 で求めた v 1 と v 2 を並べて得られる 2 次実行列 V = (v 1 v 2 ) と，AT A √の固有値から作られる対角行列 D = 

λ10√0 を考える．このとき，λ2A−1 DV を計算せよ．

線形代数学の問題は，このページで終りである．
— 1 —

解析学

I つぎの定積分 I について，以下の問いに答えよ．（配点 50 点）∫ log 2I =01(ex + e−x )2dx

問 1 変換 ex = t によって，I の積分変数を x から t に変更せよ．
問 2 定積分 I の値を求めよ．

解析学の問題は，このページで終りである．
— 2 —情 報 数 学

I 無向グラフ G に対し，線グラフ L(G) をつぎの (a) と (b) により定める．このとき，以下の問いに答えよ．（配点 50 点）（a） G の辺に対応させて，L(G) の頂点を定める．
（b） G の二つの辺が，ある頂点を端点として共有するとき，その G の二つの辺に対応する L(G) の頂点を辺でつなぐ．

問 1 図 1 で与えるグラフ G に対する線グラフ L(G) を描け．
問 2 図 1 のグラフ G の隣接行列は図 2 のように与えられる．問 1 で求めた L(G)の隣接行列を求めよ．
問 3 問 1 で求めた L(G) の線グラフ L (L(G)) を描き，その隣接行列を求めよ．

図 1 グラフ G



0 1 0 1 0
1 0 1 0 10 1 0 1 01 0 1 0 00 1 0 0 0

図 2 グラフ G の隣接行列

情報数学の問題は，このページで終りである．
— 3 —微分方程式I 実数値関数 x = x(t), y = y(t) に対する連立微分方程式
 ẋ = −3x + 5y ẏ = −x − y（ただし，˙ は変数 t に関する微分とする）

について，以下の問いに答えよ．（配点 50 点）

問 1 x は定数係数の微分方程式 ẍ + aẋ + bx = 0 を満たすことがわかる．その定数 a, b を求めよ．
問 2 連立微分方程式の一般解を求めよ．
問 3 (x, y) 平面上で原点を通らない解 (x(t), y(t)) は，t → ∞ のときどのように振舞うか．その様子を次の⃝1⃝2⃝3 の中から一つ選び，その理由も述べよ．

⃝1 原点から限りなく遠ざかる⃝
2 原点に限りなく近づく⃝
3 原点を囲む閉曲線上を動く

微分方程式の問題は，このページで終りである．
— 4 —応用解析学I 関数 f (t) の Fourier 変換 F (ω) を次式で定義する．このとき，以下の問いに答えよ．
F (ω) =
ただし，i =√

∫ ∞−∞f (t) e−iωt dt−1 とする． （配点 50 点）

問 1 関数 f (t) をつぎのように定義するときの F (ω) を求めよ．

f (t) =

 e−ct sin ω0 t(t ≥ 0) 0(t < 0)

ただし，c と ω0 は実定数で，0 < c < ω0 を満たすとする．
問 2 問 1 で求めた F (ω) に対し，|F (ω)|2 が最大となるときの ω 2 の値を求めよ．

応用解析学の問題は，このページで終りである．
— 5 —確率論・統計学

I 確率変数 X が二項分布
n!
pk (1 − p)n−kk! (n − k)!

P (X = k) =(k = 0, 1, 2, · · · , n)に従うとする．確率変数 X の関数 f (X) の平均 E[f (X)] を

E [f (X)] =n∑

f (k) P (X = k)k=0で与えるとき, 以下の問いに答えよ. ただし，n ≥ 3， p は 0 < p < 1 の定数とする．（配点 50 点）

問 1 確率変数 X の平均値と分散を求めよ.
問 2 確率変数 X のモーメント母関数 φ(ξ) ≡ E[eξX ] を求めよ.
問 3 確率変数 X 3 の平均値を求めよ.

確率論・統計学の問題は，このページで終りである．
— 6 —アルゴリズムとデータ構造

I 以下の問いに答えよ．（配点 50 点）
問 1 サイズ n の整数配列に，n 個の異なる整数値が昇順にソートされて格納されているものとする．この配列の中から，ある整数値 x に等しい要素を探し出す「2 分探索 (Binary Search)」アルゴリズムを，日本語で記述せよ．
問 2 問 1 で記述した 2 分探索アルゴリズムの「要素比較回数」に関する計算量を，O(オーダ) 記法を用いて，導出過程も含めて示せ．
問 3 「計算困難」な問題とはどのようなものか，「計算量」の観点から述べよ．

アルゴリズムとデータ構造の問題は，このページで終りである．
— 7 —平成 21 年度大学院博士 (前期) 課程入学者選抜学力試験
知能情報科学領域

専 門 科 目
［120 分］注 意 事 項

1．試験開始の合図があるまで，この問題冊子を開かないでください．
2．出題科目およびページと科目の選択方法は，下表のとおりです．下記の指示に従って解答した４科目の解答用紙のみを提出してください．なお，ページ番号のついていない紙は下書き用紙です．
出 題 科 目人

工知

ペ ー ジ

問題数

11問

能選択方法
左の必須科目を解答してください．

線形

代学

21問

学

3

1問

アルゴリズムとデータ構造

4

1問

左の７科目のうちから３科

形 式言語 と オ ー ト マトン

5

1問目を選択し，解答してくだ

情学

61問

クス

7〜 81問

理学

91問

解数

析報ロボ

認知数

テ

ィ心さい．

3．解答用紙は 8 枚に分かれているので，１科目に２枚の解答用紙を用いてください．
必須科目については指定された解答用紙を用いてください．解答に用いなかった解答用紙も含め，すべての解答用紙の所定欄に科目名，受験番号と氏名をはっきりと記入してください．

4．解答冊子の表紙の所定欄に受験番号と氏名をはっきりと記入してください．さらに，選択した科目名の先頭に○印を記入してください．

5．解答欄内に指定された問題番号（I，II など），問いの番号（問 1 など）が明記されていない場合には，問題番号，問いの番号を記入してから解答を始めてください．

6．計算または下書き用紙 3 枚と下書き用原稿用紙 1 枚が解答用紙と一緒にあります．
7．試験中に問題冊子の印刷不明瞭，ページの落丁・乱丁および解答用紙の汚れ等に気がついた場合は，静かに手を上げて監督員に知らせてください．

8．試験終了後，問題冊子および下書き用紙は持ち帰ってください．
9．問題ごとに配点が記されています．

人 工 知 能

I 図 1 の S を初期状態とし，G を目標状態とする．コストは距離とする．楽観的なヒューリスティック関数 h′ は G との間のマンハッタン距離とする．なお，(x1 , y1 )と (x2 , y2 ) のマンハッタン距離は |x1 − x2 | + |y1 − y2 | である．また探索の途中で二つの状態の見積もりコストが等しいときはアルファベット順の早い方を優先する．
このとき，以下の問いに答えよ．（配点 50 点）(0,4)

F(2,4)

G(4,4)

H(6,4)

B(4,0)

C(6,0)

E(2,3)

D(2,2)(0,2)

S(0,0)

A(2,0)

図 1 探索空間

問 1 h′ が楽観的とはどういう意味なのか説明せよ．
問 2 最良優先探索を使ったときの解ルートとコストを求めよ．ただし，求める経過も必ず明記せよ．
問 3 A∗ アルゴリズムを使ったときの解ルートとコストを求よ．ただし，求める経過も必ず明記せよ．

人工知能の問題は，このページで終りである．
— 1 —線形代数学I 2 次実行列 A = 

1−1−2−2 に関する以下の問いに答えよ．ただし，AT は A の転置行列を表わす．（配点 50 点）

問 1 AT A を計算せよ．
問 2 行列 AT A の固有値をすべて求めよ．
問 3 問 2 で求めた固有値のうち，値の小さい方 λ1 に対応する固有ベクトル v 1 と値の大きい方 λ2 に対応する固有ベクトル v 2 を求めよ．ただし，v 1 と v 2 の大きさは共に 1 とし，列ベクトルとして表わせ．
問 4 問 3 で求めた v 1 と v 2 を並べて得られる 2 次実行列 V = (v 1 v 2 ) と，AT A √の固有値から作られる対角行列 D = 

λ10√0 を考える．このとき，

λ2A−1 DV を計算せよ．

線形代数学の問題は，このページで終りである．
— 2 —解析学

I つぎの定積分 I について，以下の問いに答えよ．（配点 50 点）∫ log 2

I =01
(ex + e−x )2dx

問 1 変換 ex = t によって，I の積分変数を x から t に変更せよ．
問 2 定積分 I の値を求めよ．

解析学の問題は，このページで終りである．
— 3 —アルゴリズムとデータ構造

I 以下の問いに答えよ．（配点 50 点）
問 1 サイズ n の整数配列に，n 個の異なる整数値が昇順にソートされて格納されているものとする．この配列の中から，ある整数値 x に等しい要素を探し出す「2 分探索 (Binary Search)」アルゴリズムを，日本語で記述せよ．
問 2 問 1 で記述した 2 分探索アルゴリズムの「要素比較回数」に関する計算量を，O(オーダ) 記法を用いて，導出過程も含めて示せ．
問 3 「計算困難」な問題とはどのようなものか，「計算量」の観点から述べよ．

アルゴリズムとデータ構造の問題は，このページで終りである．
— 4 —形式言語とオートマトン

I アルファベットを Σ = {a, b} とする．図 1 の非決定性有限オートマトン A について，以下の問いに答えよ．（配点 50 点）

aaa, bq0q

1ba, bqb2

図 1 非決定性有限オートマトン A

問 1 次の (1) から (4) の語の中からオートマトン A が受理するものを選べ．ここで，xR は x を逆順にした記号列を表す．

(1) bbb(2) abaabb(3) (bab)2(4) (bba)(baa)R

問 2 オートマトン A が受理する言語を表す正規表現を示せ．
問 3 オートマトン A と等価な決定性有限オートマトンを求めよ．
問 4 オートマトン A と等価な正規文法を示せ．

形式言語とオートマトンの問題は，このページで終りである．
— 5 —情 報 数 学

I 無向グラフ G に対し，線グラフ L(G) をつぎの (a) と (b) により定める．このとき，以下の問いに答えよ．（配点 50 点）（a） G の辺に対応させて，L(G) の頂点を定める．
（b） G の二つの辺が，ある頂点を端点として共有するとき，その G の二つの辺に対応する L(G) の頂点を辺でつなぐ．

問 1 図 1 で与えるグラフ G に対する線グラフ L(G) を描け．
問 2 図 1 のグラフ G の隣接行列は図 2 のように与えられる．問 1 で求めた L(G)の隣接行列を求めよ．
問 3 問 1 で求めた L(G) の線グラフ L (L(G)) を描き，その隣接行列を求めよ．

図 1 グラフ G

0 1 0 1 0
1 0 1 0 10 1 0 1 0
1 0 1 0 00 1 0 0 0


図 2 グラフ G の隣接行列

情報数学の問題は，このページで終りである．
— 6 —ロ ボ ティク ス

I 図 1 は直線上を移動するロボットのモデルである．本体は一様な剛体とみなすことができ，車輪は本体に比べて十分に軽くその質量は無視できるものと仮定する．

lG

θ

l
N

mgu
図1

G:

倒立振子重心

I:

倒立振子の重心周りの慣性モーメントm:

倒立振子の質量

g:

重力加速度

N:

床からの抗力l:

重心から倒立振子の端までの距離u:

倒立振子の下部に水平方向に加えられる力θ:

倒立振子の重心周りの回転角度

倒立振子

いま，ロボットが直立した状態を θ = 0 としてこれを初期状態とし，このロボットを倒立振子と見なしてモデル化したところ，重心 G まわりの回転に関する運動方程式として次式を得た．

Id2 θ(t)= mglθ(t) + lu(t)dt2ただし，u および θ は，連続時間 t の関数としてそれぞれ u(t), θ(t) と表し，u(t)は図中の左方向を正とした．また，θ(t) は図中の時計回りを正とし，その変化は微小であるものと仮定した．
このロボットが転倒しないよう制御する場合について，以下のそれぞれの問いに答えよ．（配点 50 点）— 7 —問 1 入力を u(t)，出力を θ(t) とし，このロボットの伝達関数を求めよ．ただし，u(t), θ(t) をラプラス変換したものは，それぞれ U (s), Θ(s) と表すものとする．
問 2 角度の目標値を θd (t) とし，ロボットへの入力を次式とした場合の制御系のブロック線図を示せ．

u(t) = K1 (θd (t) − θ(t))
さらに，この制御系全体の伝達関数を求めよ．
問 3 角度の目標値を θd (t) とし，ロボットへの入力を次式とした場合の制御系のブロック線図を示せ．

u(t) = K1 (θd (t) − θ(t)) − K2dθ(t)dtさらに，この制御系全体の伝達関数を求めよ．
問 4 ロボットの制御系を問 2 のものから問 3 のものに変更した場合，制御に関して改善される点を述べよ．

ロ ボ テ ィ ク スの問題は，このページで終りである．
— 8 —認知心理学I 認知心理学では，人間の記憶を，短期記憶 (short-term memory) と長期記憶 (longterm memory) に分けて考えている．人間の記憶を短期記憶と長期記憶に分ける認知心理学的な根拠，もしくは認知神経心理学的な根拠のどちらか一つを 400 字程度で述べよ．（配点 50 点）

認知心理学の問題は，このページで終りである．
— 9 —平成 21 年度

大学院博士 (前期) 課程入学者選抜学力試験
情報アーキテクチャ領域

専 門 科 目
［120 分］注 意 事 項

1．試験開始の合図があるまで，この問題冊子を開かないでください．
2．出題科目およびページと科目の選択方法は，下表のとおりです．下記の指示に従って解答した４科目の解答用紙のみを提出してください．なお，ページ番号のついていない紙は下書き用紙です．
出 題 科 目

ペ ー ジ

問題数

学

11問

学

21問

学

31問

アルゴリズムとデータ構造

41問

形 式言語とオートマトン

51問

ディジ タ ル 論 理 回 路

6〜 7

1問

デ ー タ ベ ー ス 工 学

81問

ソ フ ト ウェア 設 計 論

9 〜 11

2問

線形解
情

代数

析報数

選択方法

左の８科目のうちから４科目を選択し，解答してくだ
さい．

3．解答用紙は 8 枚に分かれているので，１科目に２枚の解答用紙を用いてください．
解答に用いなかった解答用紙も含め，すべての解答用紙の所定欄に科目名，受験番号と氏名をはっきりと記入してください．

4．解答冊子の表紙の所定欄に受験番号と氏名をはっきりと記入してください．さらに，選択した科目名の先頭に○印を記入してください．

5．解答欄内に指定された問題番号（I，II など），問いの番号（問 1 など）が明記されていない場合には，問題番号，問いの番号を記入してから解答を始めてください．

6．計算または下書き用紙 4 枚が解答用紙と一緒にあります．
7．試験中に問題冊子の印刷不明瞭，ページの落丁・乱丁および解答用紙の汚れ等に気がついた場合は，静かに手を上げて監督員に知らせてください．

8．試験終了後，問題冊子および下書き用紙は持ち帰ってください．
9．問題ごとに配点が記されています．

線形代数学
I 2 次実行列 A = 

1−1−2−2 に関する以下の問いに答えよ．ただし，AT は A の転置行列を表わす．（配点 50 点）

問 1 AT A を計算せよ．
問 2 行列 AT A の固有値をすべて求めよ．
問 3 問 2 で求めた固有値のうち，値の小さい方 λ1 に対応する固有ベクトル v 1 と値の大きい方 λ2 に対応する固有ベクトル v 2 を求めよ．ただし，v 1 と v 2 の大きさは共に 1 とし，列ベクトルとして表わせ．
問 4 問 3 で求めた v 1 と v 2 を並べて得られる 2 次実行列 V = (v 1 v 2 ) と，AT A √の固有値から作られる対角行列 D = 

λ10√0 を考える．このとき，λ2A−1 DV を計算せよ．

線形代数学の問題は，このページで終りである．
— 1 —

解析学

I つぎの定積分 I について，以下の問いに答えよ．（配点 50 点）∫ log 2I =01(ex + e−x )2dx

問 1 変換 ex = t によって，I の積分変数を x から t に変更せよ．
問 2 定積分 I の値を求めよ．

解析学の問題は，このページで終りである．
— 2 —情 報 数 学

I 無向グラフ G に対し，線グラフ L(G) をつぎの (a) と (b) により定める．このとき，以下の問いに答えよ．（配点 50 点）（a） G の辺に対応させて，L(G) の頂点を定める．
（b） G の二つの辺が，ある頂点を端点として共有するとき，その G の二つの辺に対応する L(G) の頂点を辺でつなぐ．

問 1 図 1 で与えるグラフ G に対する線グラフ L(G) を描け．
問 2 図 1 のグラフ G の隣接行列は図 2 のように与えられる．問 1 で求めた L(G)の隣接行列を求めよ．
問 3 問 1 で求めた L(G) の線グラフ L (L(G)) を描き，その隣接行列を求めよ．

図 1 グラフ G







0 1 0 1 0
1 0 1 0 10 1 0 1 01 0 1 0 00 1 0 0 0

図 2 グラフ G の隣接行列

情報数学の問題は，このページで終りである．
— 3 —アルゴリズムとデータ構造

I 以下の問いに答えよ．（配点 50 点）
問 1 サイズ n の整数配列に，n 個の異なる整数値が昇順にソートされて格納されているものとする．この配列の中から，ある整数値 x に等しい要素を探し出す「2 分探索 (Binary Search)」アルゴリズムを，日本語で記述せよ．
問 2 問 1 で記述した 2 分探索アルゴリズムの「要素比較回数」に関する計算量を，O(オーダ) 記法を用いて，導出過程も含めて示せ．
問 3 「計算困難」な問題とはどのようなものか，「計算量」の観点から述べよ．

アルゴリズムとデータ構造の問題は，このページで終りである．
— 4 —形式言語とオートマトン

I アルファベットを Σ = {a, b} とする．図 1 の非決定性有限オートマトン A について，以下の問いに答えよ．（配点 50 点）

aaa, bq0q

1ba, bqb2

図 1 非決定性有限オートマトン A

問 1 次の (1) から (4) の語の中からオートマトン A が受理するものを選べ．ここで，xR は x を逆順にした記号列を表す．

(1) bbb(2) abaabb(3) (bab)2(4) (bba)(baa)R

問 2 オートマトン A が受理する言語を表す正規表現を示せ．
問 3 オートマトン A と等価な決定性有限オートマトンを求めよ．
問 4 オートマトン A と等価な正規文法を示せ．

形式言語とオートマトンの問題は，このページで終りである．
— 5 —ディジタル論理回路

I 図 1 に示すように入力 A に対して，以下の三つの出力を持つ同期回路を設計する．
出力 Y 1 入力 A が 0 から 1 に変化した直後の 1 クロックの期間，1 を出力する．
出力 Y 2 入力 A が 1 となっている期間，クロックに同期して 1 を出力する．
出力 Y 3 入力 A が 1 から 0 に変化した直後の 1 クロックの期間，1 を出力する．
この同期回路を設計するために，以下の S1 から S4 の 4 状態を考える．
状態 S1 入力 A が継続して 0 の状態
状態 S2 入力 A が 0 から 1 に変化した状態
状態 S3 入力 A が継続して 1 の状態
状態 S4 入力 A が 1 から 0 に変化した状態
このとき，以下の問いに答えよ．（配点 50 点）

S1S2S3S3S3S4S1䜽䝻䝑䜽ධຊ㻌A
ฟຊ Y1
ฟຊ Y2
ฟຊ Y3

図 1 タイミングチャート— 6 —S2S4S1

問 1 状態遷移図を作図せよ．
問 2 状態 S1 から状態 S4 の 4 状態に対して 2 ビットの 2 進数を割り当てたい．状
態と 2 ビットの 2 進数の対応表を作成しなさい．ただし，2 ビットの数の上位のビットを Q1，下位のビットを Q0 とすること．
問 3 問 2 の対応表にしたがって，D フリップフロップを用いて入力 A と Q0, Q1の関係を表す論理回路の回路図を作図せよ．
問 4 問 3 の結果をもとに，Q0, Q1 と出力 Y 1, Y 2, Y 3 の関係を表す論理式を求めよ．

ディジタル論理回路の問題は，このページで終りである．
— 7 —データベース工学

I 次のような交通網の関係データベースを考える．このとき，以下の三つの問いに答えよ．（配点 50 点）
航空会社リレーション (Airlines) には，三つの属性（ 名前 (name)，国 (country)，飛行機の型 (plane type) ）がある. 空港リレーション (Airport) には，四つの属性（名前 (name)，国 (country)，フライト数 (number ﬂights)，経路 (routes)）がある.

• Airlines( name, country, plane type )• Airport( name, country, number ﬂights, routes )問 1 SQL 文で航空会社と空港で同じ国であるものを調べ，その空港の名前と航空会社の名前を出力せよ.
問 2 SQL 文で同じ飛行機の型を使う航空会社の名前を調べよ.
問 3 問 2 の解答を関係代数演算の言語を使って答えよ．
ただし，簡単にするために，Airlines( name, country, plane type ) を次のように書け．

Airlines( a1, a2, a3 )さらに，次の四つの基本演算を使うこと：リネーミング ( ρ ), 選択 ( σ ), 射影( π ), 直積 ( × )．

データベース工学の問題は，このページで終りである．
— 8 —ソフトウェア設計論

I ソフトウェア開発に関する以下の問いに答えよ．（配点 30 点）
問 1 ソフトウェア開発のプロセスはウォーターフォール型と繰り返し型の 2 種類に大別できる．繰り返し型プロセスには，インクリメンタル（漸増）型，イテレーティブ（反復）型，スパイラルモデルなどが含まれる．次の記述は，それらを対比した場合の特徴を表したものである．(a)〜(g) のそれぞれについてウォーターフォール型と繰り返し型のいずれの特徴を表したものかを示せ．
（a） 未知の要素が多いプロジェクトに適している（b） プロジェクトの進捗管理がしやすい（c） 工数を見積もりやすい（d） プロジェクト終盤で致命的な問題が発覚するようなリスクを低減しやすい（e） 分業がしやすい（f） プロセス全体の見通しがよくないためスケジュールが立てにくい（g） 顧客の要求の変化に追従しやすい
問 2 ソフトウェア開発における代表的なリスクとして，(1) 技術的リスク，(2) 人的リスクがある．いま，商品点数が 500 で 1 日に 1 万人規模のアクセスがある
ショッピング Web サイトのサーバ側のソフトウェア (Web アプリケーション)を 10 人のメンバーからなるチームで開発するものとする．この場合に最も重要と思われるリスクを (1) および (2) についてひとつずつ挙げ，それぞれについてどのような対策が考えられるかを述べよ．

— 9 —II 次の図 1 は UML の記法に基づいて記述したある装置のステートマシン図であり，図中の遷移規則は以下の形式に基づいて記述している．
イベント名 [条件式]/動作
ただし，イベント名，条件式，動作のいずれも省略されることがあり，条件式が省略される場合は前後の [ ] も省略され，動作が省略される場合はその前の / も省略される．

POWER /t = 20

OnOffSet

UP /t = t + 1POWER

@[ t > 30 || t < 10 ]Error

図 1 ある装置のステートマシン図

この装置には POWER ボタン，UP ボタン，DOWN ボタンの三つのボタンのみがあるものとして以下の問いに答えよ．（配点 20 点）— 10 —

問 1 図 1 のステートマシン図中に現れる属性ｔの初期値はいくつか答えよ．
問 2 図 1 のステートマシン図で表される装置の On/Oﬀ を切り替えるのは何ボタンか，そのボタン名を答えよ．
問 3 Set 状態にあるとき，DOWN ボタンが押されたら属性 t の値を 1 減らしたい．
図 1 の空欄⃝
1 にはどのような遷移規則を記述すればよいか答えよ．
問 4 装置を On にした後，どのようなボタン操作をすると Error 状態に達するか．

Error 状態に達する最短の操作列を一つ答えよ．
問 5 図 1 のステートマシン図に記述されている範囲内で，Error 状態に達した後，再び Set 状態に戻るためにはどのようなボタン操作をすればよいか答えよ．さらに，そのとき属性 t の値はいくつになって Set 状態に戻るのかも答えよ．

ソフトウェア設計論の問題は，このページで終りである．
— 11 —

平成 21 年度

大学院博士 (前期) 課程入学者選抜学力試験
メディアデザイン領域

専 門 科 目
［120 分］注 意 事 項

1．試験開始の合図があるまで，この問題冊子を開かないでください．
2．出題科目およびページと科目の選択方法は，下表のとおりです．下記の指示に従って解答した４科目の解答用紙のみを提出してください．なお，ページ番号のついていない紙は下書き用紙です．
出 題 科 目認

知情報

心ペ ー ジ

問題数

選択方法

理学

1

1問

イン

2

1問

左の５科目のうちから４科

ヒューマンインタフェース

3

1問目を選択し，解答してくだ

アルゴリズムとデータ構造

4

1問

さい．

メ ディア デ ザ イ ン 基 礎

51問

デザ

3．解答用紙は 7 枚に分かれているので，科目ごとに指定された解答用紙を用いてください．解答に用いなかった解答用紙も含め，すべての解答用紙の所定欄に受験番号と氏名をはっきりと記入してください．

4．解答冊子の表紙の所定欄に受験番号と氏名をはっきりと記入してください．さらに，選択した科目名の先頭に○印を記入してください．

5．解答欄内に指定された問題番号（I，II など），問いの番号（問 1 など）が明記されていない場合には，問題番号，問いの番号を記入してから解答を始めてください．

6．計算または下書き用紙 2 枚と下書き用原稿用紙 3 枚が解答用紙と一緒にあります．
7．試験中に問題冊子の印刷不明瞭，ページの落丁・乱丁および解答用紙の汚れ等に気がついた場合は，静かに手を上げて監督員に知らせてください．

8．試験終了後，問題冊子および下書き用紙は持ち帰ってください．
9．問題ごとに配点が記されています．

認知心理学

I 認知心理学では，人間の記憶を，短期記憶 (short-term memory) と長期記憶 (longterm memory) に分けて考えている．人間の記憶を短期記憶と長期記憶に分ける認知心理学的な根拠，もしくは認知神経心理学的な根拠のどちらか一つを 400 字程度で述べよ．（配点 50 点）

認知心理学の問題は，このページで終りである．
— 1 —情報デザインI 解答用紙の７×７マスの方眼１２コマを用いて，「はずむ」を連想させるループする（繰り返す）アニメーションを作成せよ．さらに，作成したアニメーションの制作意図を解答用紙の指定欄に簡潔に記入せよ．（配点 50 点）

アニメーション作成上の注意事項• □を■に塗りつぶすことで表現すること．
• アニメーションは，１コマ目から１２コマ目へ順に再生し，１２コマ目の次は１コマ目へ戻り，再度１コマ目から順に再生を繰り返すものして作成すること．

• １コマ目から１２コマ目の順に，全てのコマを使用すること．
• 各コマの□を■に塗りつぶす数に制限はないが，解答用紙に予め書かれている□の数以上の■を書かないこと．

情報デザインの問題は，このページで終りである．
— 2 —ヒューマンインタフェース

I 人間中心設計プロセス (Human Centred Design Process) と従来の設計プロセスの違いを，簡潔に 300 字程度で説明せよ．（配点 50 点）

ヒューマンインタフェースの問題は，このページで終りである．
— 3 —アルゴリズムとデータ構造

I 以下の問いに答えよ．（配点 50 点）
問 1 サイズ n の整数配列に，n 個の異なる整数値が昇順にソートされて格納されているものとする．この配列の中から，ある整数値 x に等しい要素を探し出す「2 分探索 (Binary Search)」アルゴリズムを，日本語で記述せよ．
問 2 問 1 で記述した 2 分探索アルゴリズムの「要素比較回数」に関する計算量を，O(オーダ) 記法を用いて，導出過程も含めて示せ．
問 3 「計算困難」な問題とはどのようなものか，「計算量」の観点から述べよ．

アルゴリズムとデータ構造の問題は，このページで終りである．
— 4 —メ ディア デ ザ イ ン 基 礎

I 設計仕様書が出来上がった段階で行われる評価方法に，認知的ウォークスルー法とヒューリスティク法がある．この二者の違いを簡潔に 300 字程度で説明せよ．（配点 50 点）

メディアデザイン基礎の問題は，このページで終りである．
— 5 —