平成 24 年度

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

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

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

ペ ー ジ

問題数

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

1

1問

線

学

2

1問

学

3

2問

形

解

代

数

析

情

報

数

学

4

2問

応

用

数

学

5

1問

デ ー タ ベ ー ス 工 学

6

1問

選択方法

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

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

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

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

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

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

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

I 二分木を利用した二分探索法で用いられる木は，二分探索木と呼ばれる．二分探索
木に関する以下の問いに答えよ．（配点 50 点）

問 1 二分探索木を用いた探索アルゴリズムを，ノードの値として整数値を持つ二分探索木から，ある整数値のノードを探索する場合の例を用いて説明せよ．
問 2 二分探索木での探索にかかわる最悪の計算コストと木の高さには，正比例の関係があるので，木の高さは低く保つのが望ましい．なぜ，探索にかかわる最悪の計算コストが木の高さと正比例の関係にあるのか，例を挙げてその理由を説明せよ．
問 3 二分探索木は順序木 (ordered tree) であり，順序木が持つ順序に関する性質を用いて，効率的な探索を実現している．どのような順序木の順序に関する性
質で，効率的な探索を実現しているのか，その理由を答えよ．
問 4 無順序木 (unordered tree) と半順序木 (partial ordered tree) は，二分探索木に適さない．二分探索木に適さない理由を，それぞれ示せ．

アルゴリズムとデータ構造の問題は，このページで終りである．
— 1 —線形代数学I 次の 3 × 3 行列 A について, 以下の問いに答えよ. （配点 50 点）
A

 1 0 0 = 
 0 2 1 



0 1 2

問 1 行列 A の固有値と固有ベクトルをすべて求めよ.
問 2 行列 A を対角化せよ.
問 3 An (n = 2, 3, 4, · · ·) を求めよ.

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

解析学

I f (x) = ex cos x の n 次導関数 f (n) (x) (n = 1, 2, 3, · · ·) が次式で与えられることを，
数学的帰納法を用いて示せ．（配点 25 点）
(

f
(

II

lim

1+

問1

lim

n→∞

1
n

(

問2

lim

n→∞

nπ
e cos x +
4

)

n/2 x

(x) = 2)n

= e を用いて，以下の極限値を求めよ．（配点 25 点）

(
n→∞

(n)

1+

1
3n

1−

1
n2

)n

)n

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

I 以下の問いに答えよ．（配点 25 点）
問 1 命題 p と命題 q について，以下の 2 つの関係式∼ (p ∧ q) = (∼ p) ∨ (∼ q)と∼ (p ∨ q) = (∼ p) ∧ (∼ q)

が，それぞれ成り立つことを，真理値表を用いて示せ．さらに，これら関係式
を何というか答えよ．ただし，∼ r は命題 r の否定を表す．
問 2 集合 A のすべての部分集合からなる集合を， A のベキ集合とよび， P(A)で表す．A = {1, 2, 3, 4} のとき，P(A) の要素をすべて示し，P(A) の要素の数を求めよ．
問 3 自然数の集合 N = {1, 2, 3, · · ·} と正の偶数の集合 E = {2, 4, 6, · · ·} が対等であることを示せ．

II 次の重み付き隣接行列 A で与えられる無向グラフ G について，以下の問いに答えよ．（配点 25 点） 0 1 5 3  1 0 3 6 



A=


 5 3 0 2 

3 6 2 0
問 1 グラフ G を描け．
問 2 グラフ G の全域木を 1 つ描け．
問 3 グラフ G の 2 つの異なる最小全域木を，クルスカル (Kruskal) のアルゴリズ
ムを利用して求め，それらを描け．

情報数学の問題は，このページで終りである．
— 4 —応 用 数 学

I 未知関数 x = x(t), y = y(t) に対する連立微分方程式
 ẋ = −x ẏ = x − 2y（ただし，˙ は変数 t に関する微分とする）

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

問 1 この連立微分方程式を解け．
問 2 問 1 で求めた解軌道のうち，始点 (x(0), y(0)) が (−2, 2) であるものを xy-平
面に描け．
(

問 3 問 1 で求めた解軌道のうち，始点 (x(0), y(0)) が

3
3
,−
2
4

)

xy-平面に描け．

応用数学の問題は，このページで終りである．
— 5 —であるものを

データベース工学

I データベースでは各種データアクセス要求に対応するため，様々なデータ構造が用いられている．ここでは，データベースのインデックス作成に用いられるハッシュテーブルと B-tree について，以下の問いに答えよ．なお，インデックス用には B-tree
を変形した B+ -tree が用いられることもある．どちらについて回答してもよいが，両者の差を議論するときは，どちらのデータ構造に関する説明か明記すること．（配点 50 点）

問 1 インデックス作成にハッシュテーブルを用いた場合と比較して，B-tree を用いる方が優れている点を一つ答えよ．
問 2 インデックス作成に B-tree を用いた場合と比較して，ハッシュテーブルを用いる方が優れている点を一つ答えよ．
問 3 key-value ストアとは，key (キー) と value (値) のペアからなるデータ構造であり，クラウド・コンピューティングの要素技術として使われている．key-value
ストアでは，キーを指定して値を読み書きするという操作が行われる．key-value
ストアの実装では，ハッシュテーブルが用いられていることが多い．その理由を説明せよ．

データベース工学の問題は，このページで終りである．
— 6 —平成 24 年度

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

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

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

工

知

ペ ー ジ

問題数

1

1問

能

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

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

2

1問

線

学

3

1問

学

4

2問

左の 7 科目のうちから 3 科

学

5

2問

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

形 式言語 と オ ー ト マトン

6

1問

ディジタル論理回路

7〜 8

1問

9

1問

形

解
情

認

代

数

析
報

知

数

心

理

学

さい．

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

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

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

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

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

人 工 知 能I 狩人と狼というパズルを考える．このパズルの条件は以下の通りである．
条件 1 最初，三人の狩人と三匹の狼が，南北に流れる川の西岸にいる．また，一艘の舟も最初は西岸にある．狩人あるいは狼が川を (西岸から東岸へ，あるいは東岸から西岸へ) 渡るには舟を使う．
条件 2 最後に三人の狩人と三匹の狼のすべてを東岸に渡らせることを目標とする．
条件 3 狩人の数より狼の数が多くなると狩人は食べられてしまう．
条件 4 舟は一艘しかなく，最大で，一度に二人あるいは一人と一匹あるいは二匹しか乗れない．
条件 5 狩人も狼も単独で舟を漕げるものとする (誰も乗っていないと舟は動かない)．
この条件で狩人が狼に食べられることなく，すべての狩人と狼を西岸から東岸に渡らせるにはどうしたらよいか．このパズルを状態空間探索問題として解くことを考える．狩人が西岸に x 人いて，狼が西岸に y 匹いて，舟が西岸にある状態を(x, y, 西) と表わすことにする．同様に，狩人が西岸に x 人いて，狼が西岸に y 匹いて，舟が東岸にある状態を (x, y, 東) と表すことにする (x は西岸にいる狩人の数を，y は西岸にいる狼の数を常に記述していることに注意せよ)．以下の問いに答えよ．
（配点 50 点）

問 1 初期状態と目標状態を表現せよ．
問 2 (x, y, z) という状態 (z は西あるいは東) に対して狩人が食べられない条件を式で表せ．
問 3 状態に適用可能な作用素を列挙せよ．
問 4 この状態空間探索問題の解を求めよ．途中経過も記述すること．ただし解が複数存在する場合はそのうちの一つを求めればよい．

人工知能の問題は，このページで終りである．
— 1 —アルゴリズムとデータ構造

I 二分木を利用した二分探索法で用いられる木は，二分探索木と呼ばれる．二分探索
木に関する以下の問いに答えよ．（配点 50 点）

問 1 二分探索木を用いた探索アルゴリズムを，ノードの値として整数値を持つ二分探索木から，ある整数値のノードを探索する場合の例を用いて説明せよ．
問 2 二分探索木での探索にかかわる最悪の計算コストと木の高さには，正比例の関係があるので，木の高さは低く保つのが望ましい．なぜ，探索にかかわる最悪の計算コストが木の高さと正比例の関係にあるのか，例を挙げてその理由を説明せよ．
問 3 二分探索木は順序木 (ordered tree) であり，順序木が持つ順序に関する性質を用いて，効率的な探索を実現している．どのような順序木の順序に関する性
質で，効率的な探索を実現しているのか，その理由を答えよ．
問 4 無順序木 (unordered tree) と半順序木 (partial ordered tree) は，二分探索木に適さない．二分探索木に適さない理由を，それぞれ示せ．

アルゴリズムとデータ構造の問題は，このページで終りである．
— 2 —線形代数学I 次の 3 × 3 行列 A について, 以下の問いに答えよ. （配点 50 点）
A

 1 0 0 = 
 0 2 1 



0 1 2

問 1 行列 A の固有値と固有ベクトルをすべて求めよ.
問 2 行列 A を対角化せよ.
問 3 An (n = 2, 3, 4, · · ·) を求めよ.

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

解析学

I f (x) = ex cos x の n 次導関数 f (n) (x) (n = 1, 2, 3, · · ·) が次式で与えられることを，
数学的帰納法を用いて示せ．（配点 25 点）
(

f
(

II

lim

1+

問1

lim

n→∞

1
n

(

問2

lim

n→∞

nπ
e cos x +
4

)

n/2 x

(x) = 2)n

= e を用いて，以下の極限値を求めよ．（配点 25 点）

(
n→∞

(n)

1+

1
3n

1−

1
n2

)n

)n

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

I 以下の問いに答えよ．（配点 25 点）
問 1 命題 p と命題 q について，以下の 2 つの関係式∼ (p ∧ q) = (∼ p) ∨ (∼ q)と∼ (p ∨ q) = (∼ p) ∧ (∼ q)

が，それぞれ成り立つことを，真理値表を用いて示せ．さらに，これら関係式
を何というか答えよ．ただし，∼ r は命題 r の否定を表す．
問 2 集合 A のすべての部分集合からなる集合を， A のベキ集合とよび， P(A)で表す．A = {1, 2, 3, 4} のとき，P(A) の要素をすべて示し，P(A) の要素の数を求めよ．
問 3 自然数の集合 N = {1, 2, 3, · · ·} と正の偶数の集合 E = {2, 4, 6, · · ·} が対等であることを示せ．

II 次の重み付き隣接行列 A で与えられる無向グラフ G について，以下の問いに答えよ．（配点 25 点） 0 1 5 3  1 0 3 6 



A=


 5 3 0 2 

3 6 2 0
問 1 グラフ G を描け．
問 2 グラフ G の全域木を 1 つ描け．
問 3 グラフ G の 2 つの異なる最小全域木を，クルスカル (Kruskal) のアルゴリズ
ムを利用して求め，それらを描け．

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

I Σ1 = {‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’}, Σ = Σ1 ∪ {‘+’, ‘=’} とする．ここで，‘0’から ‘9’ は 0 から 9 のそれぞれの数字を，‘+’ はプラス記号，‘=’ はイコール記号を表すものとする．このとき，以下の問いに答えよ．（配点 50 点）

問 1 数字のアルファベットを Σ1 とする．整数とは数字または，整数と数字の連接と定義する．このとき，整数である入力列のみを受理する Σ1 上の有限オー
トマトンの状態遷移図を示せ．
問 2 問 1 で定義した整数に対応する正規表現を示せ．
問 3 問 1 で定義した整数に対して，以下の二つの条件を同時に満たす場合にのみ受理する Σ 上の有限オートマトンの状態遷移図を示せ．
条件 1 入力が，「整数, ‘+’, 整数, ‘=’」が連接した列である
条件 2 入力中の二つの整数の 10 進数としての和が偶数である
ただし，各整数の入力は上位桁から順に並んでおり，上位桁の冗長な ‘0’ を許すものとする．

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

I 1 から 4 の目を持つ電子サイコロを作成する．電子サイコロは，表示器として図 1 に示すような配置の 5 個の LED(以下 LED1 , · · · , LED5 とする) を用い，サイコロの目の表現を図 2 に示す．また，この電子サイコロは，ボタンを押しているとき (S = 1)
はサイコロの目が変化し，ボタンを離しているとき (S = 0) はサイコロの目が変化しないものとする．このとき，以下の問いに答えよ．（配点 50 点）

問 1 この電子サイコロの状態遷移図を作図せよ．
問 2 問 1 で示した状態遷移を行う論理回路を，D フリップフロップを用いて作成するとき，D フリップフロップの最少個数を答えよ．
問 3 サイコロの状態を表すのに用いる D フリップフロップの i ビット目の出力をQi ，入力を Di としたとき，各 D フリップフロップの入力 D1 , · · · , Dn を，ボタンの状態 S と各フリップフロップの出力 Q1 , · · · , Qn を用いた論理式で表せ．ただし，n は問 2 で答えた数とし，i は 1 から n までの整数，1 番目の D フリップ
フロップが最下位ビット，n 番目の D フリップフロップが最上位ビットを表すものとする．
問 4 LED1 , · · · , LED5 と D フリップフロップの出力 Q1 , · · · , Qn の関係を真理値表で表せ．ただし，LED が点灯しているときを 1，消灯しているときを 0 とする．
問 5 問 4 の結果を論理式で表せ．

— 7 —

LED1

LED2
LED5

LED3

LED4

図 1 LED の配置図

1䛾┠

3䛾┠

2䛾┠

4䛾┠

Ⅼⅉ
ᾘⅉ
図 2 LED の点灯パターン

ディジタル論理回路の問題は，このページで終りである．
— 8 —認知心理学I 人は，個別の要素（情報）をそのままではなく，まとまりをもった全体（ゲシュタルト）として知覚している．
「ゲシュタルトの法則」は，各要素の関係性にもとづくまとまり方の特徴を示している．以下の問いに答えよ．（配点 50 点）

問 1 図 1 は，ゲシュタルトの法則の一部を説明するものである．図中のとイ

アにあてはまる適切な語句を答えよ．

図1

問 2 「よい連続の法則」について，図を示して説明せよ．
問 3 ゲシュタルトの法則は，ヒューマンインタフェースにどのように役に立つのか，具体的な例をあげて説明せよ（図や絵などを描いてもよい）．

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

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

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

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

ペ ー ジ

問題数

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

1

1問

線

学

2

1問

学

3

2問

学

4

2問

形 式言語 と オートマトン

5

1問

ソフトウェア設計論

6〜 7

2問

ディジタル論理回路

8〜 9

1問

デ ー タ ベ ー ス 工 学

10

1問

形

解
情

代

数

析
報

数

選択方法

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

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

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

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

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

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

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

I 二分木を利用した二分探索法で用いられる木は，二分探索木と呼ばれる．二分探索
木に関する以下の問いに答えよ．（配点 50 点）

問 1 二分探索木を用いた探索アルゴリズムを，ノードの値として整数値を持つ二分探索木から，ある整数値のノードを探索する場合の例を用いて説明せよ．
問 2 二分探索木での探索にかかわる最悪の計算コストと木の高さには，正比例の関係があるので，木の高さは低く保つのが望ましい．なぜ，探索にかかわる最悪の計算コストが木の高さと正比例の関係にあるのか，例を挙げてその理由を説明せよ．
問 3 二分探索木は順序木 (ordered tree) であり，順序木が持つ順序に関する性質を用いて，効率的な探索を実現している．どのような順序木の順序に関する性
質で，効率的な探索を実現しているのか，その理由を答えよ．
問 4 無順序木 (unordered tree) と半順序木 (partial ordered tree) は，二分探索木に適さない．二分探索木に適さない理由を，それぞれ示せ．

アルゴリズムとデータ構造の問題は，このページで終りである．
— 1 —線形代数学I 次の 3 × 3 行列 A について, 以下の問いに答えよ. （配点 50 点）
A

 1 0 0 = 
 0 2 1 



0 1 2

問 1 行列 A の固有値と固有ベクトルをすべて求めよ.
問 2 行列 A を対角化せよ.
問 3 An (n = 2, 3, 4, · · ·) を求めよ.

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

解析学

I f (x) = ex cos x の n 次導関数 f (n) (x) (n = 1, 2, 3, · · ·) が次式で与えられることを，
数学的帰納法を用いて示せ．（配点 25 点）
(

f
(

II

lim

1+

問1

lim

n→∞

1
n

(

問2

lim

n→∞

nπ
e cos x +
4

)

n/2 x

(x) = 2)n

= e を用いて，以下の極限値を求めよ．（配点 25 点）

(
n→∞

(n)

1+

1
3n

1−

1
n2

)n

)n

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

I 以下の問いに答えよ．（配点 25 点）
問 1 命題 p と命題 q について，以下の 2 つの関係式∼ (p ∧ q) = (∼ p) ∨ (∼ q)と∼ (p ∨ q) = (∼ p) ∧ (∼ q)

が，それぞれ成り立つことを，真理値表を用いて示せ．さらに，これら関係式
を何というか答えよ．ただし，∼ r は命題 r の否定を表す．
問 2 集合 A のすべての部分集合からなる集合を， A のベキ集合とよび， P(A)で表す．A = {1, 2, 3, 4} のとき，P(A) の要素をすべて示し，P(A) の要素の数を求めよ．
問 3 自然数の集合 N = {1, 2, 3, · · ·} と正の偶数の集合 E = {2, 4, 6, · · ·} が対等であることを示せ．

II 次の重み付き隣接行列 A で与えられる無向グラフ G について，以下の問いに答えよ．（配点 25 点） 0 1 5 3  1 0 3 6 



A=


 5 3 0 2 

3 6 2 0
問 1 グラフ G を描け．
問 2 グラフ G の全域木を 1 つ描け．
問 3 グラフ G の 2 つの異なる最小全域木を，クルスカル (Kruskal) のアルゴリズ
ムを利用して求め，それらを描け．

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

I Σ1 = {‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’}, Σ = Σ1 ∪ {‘+’, ‘=’} とする．ここで，‘0’から ‘9’ は 0 から 9 のそれぞれの数字を，‘+’ はプラス記号，‘=’ はイコール記号を表すものとする．このとき，以下の問いに答えよ．（配点 50 点）

問 1 数字のアルファベットを Σ1 とする．整数とは数字または，整数と数字の連接と定義する．このとき，整数である入力列のみを受理する Σ1 上の有限オー
トマトンの状態遷移図を示せ．
問 2 問 1 で定義した整数に対応する正規表現を示せ．
問 3 問 1 で定義した整数に対して，以下の二つの条件を同時に満たす場合にのみ受理する Σ 上の有限オートマトンの状態遷移図を示せ．
条件 1 入力が，「整数, ‘+’, 整数, ‘=’」が連接した列である
条件 2 入力中の二つの整数の 10 進数としての和が偶数である
ただし，各整数の入力は上位桁から順に並んでおり，上位桁の冗長な ‘0’ を許すものとする．

形式言語とオートマトンの問題は，このページで終りである．
— 5 —ソフトウェア設計論

I ソフトウェア開発では目的に応じて様々な種類のテストが行われる．テストは目的や実行主体などにより，以下の (1)〜(1) のように分類することができる．(1)〜(1)の各々について，正しい記述を 1〜1 の選択肢からすべて選べ (複数回答重複可)．
（配点 20 点）(i) システムテスト(ii) 単体テスト・結合テスト(iii) 受け入れテスト (承認テスト)
選択肢:a. 開発チームのテスト担当者が行うのが一般的である．
b. 顧客側の担当者が主体となって行うのが一般的である．
c. 開発チームの実装担当者が行うのが一般的である．
d. 設計仕様に基づいて行われる．
e. 要求仕様に基づいて行われる．
f. 実装フェーズで行われる．
g. テストフェーズで行われる．

— 6 —II 図 1 は，あるリスニング試験用の音声再生装置の動作を，UML の記法によって記述したステートマシン図であり，図中の遷移規則は次の形式で記述している．
イベント名 [条件式]/動作
ただし，イベント名，条件式，動作が存在しないときはいずれも省略されることがあり，条件式が省略される場合は前後の [ ] も省略され，動作が省略される場合はその前の / も省略される．この装置にはリスニング試験用の問題が 10 問入っており，所定の順番にしか再生できない．PLAY ボタンを押すと問題の再生が始まり，1問分の再生が終わると一時停止状態になる．リスニング試験の都合上，使用者は問題の途中で一時停止したり，同じ問題を再生し直したりすることはできない．以下の問いに答えよ．（配点 30 点）

問 1 図 1 に現れる track という属性が，現在再生中または次に再生する問題番号を示している．この属性の初期値および全問再生終了したときの値をそれぞれ答えよ．
問 2 一時停止状態にあるとき，使用者が PLAY ボタンを押せば次の問題が再生されるためには，図 1 の空欄 (a) にどのような遷移規則を記述したらよいか．
問 3 問題再生中に使用者が NEXT ボタンを押すと，再生中の問題を飛ばしてすぐに次の問題が再生されるようにしたい．図 1 に状態遷移を一つだけ追加してその動作を表すためには，どのような状態遷移を追加したらよいか．遷移元状態，
遷移先状態，遷移規則を答えよ．
Pause

再生終了 [track<10]/track=track+1(a)/track=1
Stop

PLAY

Play

再生終了 [track==10]End

図 1 リスニング試験用音声再生装置のステートマシン図

ソフトウェア設計論の問題は，このページで終りである．
— 7 —ディジタル論理回路

I 1 から 4 の目を持つ電子サイコロを作成する．電子サイコロは，表示器として図 1 に示すような配置の 5 個の LED(以下 LED1 , · · · , LED5 とする) を用い，サイコロの目の表現を図 2 に示す．また，この電子サイコロは，ボタンを押しているとき (S = 1)
はサイコロの目が変化し，ボタンを離しているとき (S = 0) はサイコロの目が変化しないものとする．このとき，以下の問いに答えよ．（配点 50 点）

問 1 この電子サイコロの状態遷移図を作図せよ．
問 2 問 1 で示した状態遷移を行う論理回路を，D フリップフロップを用いて作成するとき，D フリップフロップの最少個数を答えよ．
問 3 サイコロの状態を表すのに用いる D フリップフロップの i ビット目の出力をQi ，入力を Di としたとき，各 D フリップフロップの入力 D1 , · · · , Dn を，ボタンの状態 S と各フリップフロップの出力 Q1 , · · · , Qn を用いた論理式で表せ．ただし，n は問 2 で答えた数とし，i は 1 から n までの整数，1 番目の D フリップ
フロップが最下位ビット，n 番目の D フリップフロップが最上位ビットを表すものとする．
問 4 LED1 , · · · , LED5 と D フリップフロップの出力 Q1 , · · · , Qn の関係を真理値表で表せ．ただし，LED が点灯しているときを 1，消灯しているときを 0 とする．
問 5 問 4 の結果を論理式で表せ．

— 8 —

LED1

LED2
LED5

LED3

LED4

図 1 LED の配置図

1䛾┠

3䛾┠

2䛾┠

4䛾┠

Ⅼⅉ
ᾘⅉ
図 2 LED の点灯パターン

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

I データベースでは各種データアクセス要求に対応するため，様々なデータ構造が用いられている．ここでは，データベースのインデックス作成に用いられるハッシュテーブルと B-tree について，以下の問いに答えよ．なお，インデックス用には B-tree
を変形した B+ -tree が用いられることもある．どちらについて回答してもよいが，両者の差を議論するときは，どちらのデータ構造に関する説明か明記すること．（配点 50 点）

問 1 インデックス作成にハッシュテーブルを用いた場合と比較して，B-tree を用いる方が優れている点を一つ答えよ．
問 2 インデックス作成に B-tree を用いた場合と比較して，ハッシュテーブルを用いる方が優れている点を一つ答えよ．
問 3 key-value ストアとは，key (キー) と value (値) のペアからなるデータ構造であり，クラウド・コンピューティングの要素技術として使われている．key-value
ストアでは，キーを指定して値を読み書きするという操作が行われる．key-value
ストアの実装では，ハッシュテーブルが用いられていることが多い．その理由を説明せよ．

データベース工学の問題は，このページで終りである．
— 10 —

平成 24 年度

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

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

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

ペ ー ジ

問題数

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

1

1問

情

報

認

知

デ

ザ

選択方法

イ

ン

2

1問

左の 5 科目のうちから 4 科

理

学

3

1問

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

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

4

2問

さい．

メディアデザイン基礎

5〜 6

1問

心

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

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

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

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

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

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

I 二分木を利用した二分探索法で用いられる木は，二分探索木と呼ばれる．二分探索
木に関する以下の問いに答えよ．（配点 50 点）

問 1 二分探索木を用いた探索アルゴリズムを，ノードの値として整数値を持つ二分探索木から，ある整数値のノードを探索する場合の例を用いて説明せよ．
問 2 二分探索木での探索にかかわる最悪の計算コストと木の高さには，正比例の関係があるので，木の高さは低く保つのが望ましい．なぜ，探索にかかわる最悪の計算コストが木の高さと正比例の関係にあるのか，例を挙げてその理由を説明せよ．
問 3 二分探索木は順序木 (ordered tree) であり，順序木が持つ順序に関する性質を用いて，効率的な探索を実現している．どのような順序木の順序に関する性
質で，効率的な探索を実現しているのか，その理由を答えよ．
問 4 無順序木 (unordered tree) と半順序木 (partial ordered tree) は，二分探索木に適さない．二分探索木に適さない理由を，それぞれ示せ．

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

I 高齢者の生活を豊かにするための新しい携帯電話サービスを提案せよ．解答は，以下の 4 項目について記述せよ（図や絵などを描いてもよい）． （配点 50 点）[記述すべき項目]
項目 1 タイトル（コンセプトを端的に表現したもの）
項目 2 対象とするユーザの特性
項目 3 現状分析
項目 4 コンセプトとサービスイメージ

情報デザインの問題は，このページで終りである．
— 2 —認知心理学I 人は，個別の要素（情報）をそのままではなく，まとまりをもった全体（ゲシュタルト）として知覚している．
「ゲシュタルトの法則」は，各要素の関係性にもとづくまとまり方の特徴を示している．以下の問いに答えよ．（配点 50 点）

問 1 図 1 は，ゲシュタルトの法則の一部を説明するものである．図中のとイ

アにあてはまる適切な語句を答えよ．

図1

問 2 「よい連続の法則」について，図を示して説明せよ．
問 3 ゲシュタルトの法則は，ヒューマンインタフェースにどのように役に立つのか，具体的な例をあげて説明せよ（図や絵などを描いてもよい）．

認知心理学の問題は，このページで終りである．
— 3 —ヒューマンインタフェース

I ヒューマンエラーにおいて，「スリップ」は意図とは異なる行為を行ってしまうエラーであり，「ミステイク」は誤った知識や思い込みによって生じるエラーである．
例えば，エレベーターの操作パネルで 5 階のボタンを押すつもりが，うっかり 6 階を押してしまったというのは「スリップ」である．これに対して，行きたい店は 6階にあると思って 6 階でエレベーターを降りたが，実際には 5 階にあったというのは「ミステイク」である．以下の問いに答えよ．（配点 30 点）

問 1 スリップとミステイクのどちらかひとつを選び，そのエラーが起きやすい
ヒューマンインタフェースの例を図で示して，なぜエラーが起きやすいのかを説明せよ．
問 2 問 1 において示した例を，エラーが起きにくいデザインに修正した図を示して，なぜエラーが起きにくくなるのかを説明せよ．

II ヤコブ・ニールセンは，ユーザビリティの構成要素のひとつとして「記憶しやすさ」を挙げている ∗ ．
「記憶しやすさ」は使いやすさとどのように関係しているのかを説明せよ（図や絵などを描いてもよい）．（配点 20 点）∗ ニールセン, J. (1999). 篠原稔和 (監訳) 三好かおる (訳) ユーザビリティエンジニアリン

グ原論–ユーザーのためのインタフェースデザイン東京電機大学出版局（Nielsen, J. (1993).

Usability Engineering. Academic Press.）

ヒューマンインタフェースの問題は，このページで終りである．
— 4 —メデ ィ アデザイン基礎

I 2 つのショッピングサイトのユーザビリティを評価するために実験を行った．実験
参加者は 14 名で，サイト A と B の評価にそれぞれ 7 名ずつがランダムに割り当てられた．
実験参加者に提示した課題：友人の誕生日に日本酒をプレゼントしたい．あらかじめ特定の商品に決めているわけではなく，いろいろ見てから選びたい．予算は送料を含めて 5 千円，地域は東北地方，香りや旨みなどの特徴がはっきりしているもの，
有名すぎないもの，という条件で商品を探す．
以下の問いに答えよ．（配点 50 点）

問 1 課題試行時間の平均値は，A［9 分 18 秒］B［7 分 42 秒］であった．これらの平均値に差があるかどうかを，t 検定により明らかにしたい（両側検定，有意水準 5%）．t 値を計算したところ，t=2.984 であった．自由度 (df) を計算し，次ページの表 1 を用いて有意差を判定して，結論を述べよ．
問 2 このユーザビリティ評価実験では，ショッピングサイト（A ／ B）は「被験者間要因」であった．これを「被験者内要因」として実験を実施するのが適切ではない理由を述べよ．
問 3 この実験課題のような買い物を，より楽しくできるショッピングサイトをつくりたい．その際に工夫できることを 2 点挙げ，それぞれ説明せよ（図や絵などを描いてもよい）．

— 5 —表 1 t 分布表（両側検定専用）

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