平成 19 年度

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

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

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

ペ ー ジ

問題数

選択方法

学

1

2問

左の２科目のすべてを

学

2

1問

解答してください．

学

3

1問

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

4

1問

左の５科目のうちから

微

分

方

程

式

5

1問

２科目を選択し，解答

応

用

解

析

学

6

1問

してください．

確

率

論・統

計

学

7

1問

線

形

代

解

数

析

情

報

数

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

4．解答欄内には 問題番号（I，II など）を，問いなどがある場合には問いの番号（問1 など）も記入してから解答を始めてください．
5．計算または下書き用紙 3 枚と下書き用原稿用紙 1 枚が解答用紙と一緒にあります．
6．試験中に問題冊子の印刷不明瞭，ページの落丁・乱丁および解答用紙の汚れ等に気がついた場合は，静かに手を上げて監督員に知らせてください．

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

線形代数学

I 実ベクトル空間 R2 の正規直交基底 e1 , e2 を




1
1
e1 = √   ,
2
1





−1
1

e2 = √ 
2
1で与えるとき，以下の問いに答えよ．ただし，R2 のベクトル u に対して uT は uの転置ベクトルを表す．（配点 35 点）

問 1 eT1 e2 の値を求めよ．
問 2 ２つの行列 e1 eT1 , e2 eT2 を求めよ．
問 3 問２で求めた行列 e1 eT1 を P1 ，e2 eT2 を P2 で表すとき，R2 の任意のベクトル v に対して

v = P1 v + P2 vが成立することを示せ．

II Q2 = Q をみたす２次実対称行列 Q の固有値をすべて求めよ．ただし，Q は零行
列でも単位行列でもないとする．（配点 15 点）

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

解析学

I 以下の問いに答えよ．（配点 50 点）
問1

lim t2 e−t を求めよ．

t→∞

問 2 0 ≤ x ≤ 1 で定義された関数列 {fn (x)} を fn (x) = n2 xe−nx で定めるとき，

f (x) = lim fn (x) を求めよ．
n→∞

問3

∫ 1

∫ 1

n→∞ 0

0

lim

fn (x)dx =\f (x)dx を示せ．

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

I 以下の問いに答えよ．（配点 50 点）
問 1 実数全体の集合 R に対して，２つの写像 f : R → R と g : R → R を次のように定義する．

f (x) = 2x,g(x) = x2 + 1

このとき，合成写像 f ◦ g と合成写像 g ◦ f は等しくないことを示せ．
問 2 ２つの写像 f : A → B と g : B → C があるとき，単射の定義の対偶，すな
わち，「a, b ∈ A に対して， f (a) = f (b) ならば a = b である」を用いて，合成
写像 g ◦ f : A → C が単射ならば f も単射であることを示せ．
問 3 ２つの写像 f : A → B と g : B → C があるとき，合成写像 g ◦ f が単射でも，g は単射とは限らないことを，A = {a, b, c},

B = {1, 2, 3, 4, 5},

C = {α, β, γ}とした場合に示せ．

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

I アルゴリズムを考える場合によく用いられる再帰法に関して，以下の問いに答えよ．
ただし，プログラムを記述する問いの解答には，C 言語または Java 言語を用いて記述せよ．（配点 50 点）

問 1 どのような問題を解く場合に，再帰法のアルゴリズムが利用できるか，その理由，再帰法を用いる利点を含めて 200 字程度で述べよ．
問 2 ２分木が，すべてのノードに対して• その左部分木のノードのキー値はそのキー値より小さく• その右部分木のノードのキー値はそのキー値より大きいという条件を満たす時，２分探索木と呼ぶ．２分探索木を用いる場合のデータ
構造を，C 言語であれば構造体，Java 言語であればクラスを用いて記述せよ．
ノードには，キー値として整数型のデータが１つ格納されているものとする．
問 3 問 2 で記述したデータ構造で作られた２分探索木から，整数型のデータを引数とし，そのデータと同じ大きさのデータを持つノードを再帰的に探索する関数を記述せよ．ただし，• 引数は整数型データ１つ• 同じ大きさのデータを持つノードが検出された場合，“Find Node” という文字列を標準出力に表示して終了，• 同じ大きさのデータを持つノードが検出されなかった場合，“No Node” という文字列を標準出力に表示して終了，• 戻り値は問わないとする．

アルゴリズムとデータ構造の問題は，このページで終りである．
— 4 —微分方程式I 時間 t の未知関数 x = x(t), y = y(t) に対する連立微分方程式
 ẋ = 2x − 2y ẏ = 2x + 2yについて，以下の問いに答えよ．ただし， ˙ は t についての１階微分演算を表す．
（配点 50 点）
問 1 一般解 (x(t), y(t)) を求めよ．
問 2 問１で得た解が x-y 平面に描く軌道のうち，初期時刻 t = 0 で (1, 0) から出発するものを求め，その概形を描け．

微分方程式の問題は，このページで終りである．
— 5 —応用解析学I 以下の問いに答えよ．（配点 50 点）
問 1 関数 f (x) = | sin x| のフーリエ級数を求めよ．
問2

1
1
1
1
+
+
+ ··· =
を示せ．
1·3
3·5
5·7
2

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

I 試験 A の成績が平均 µ，分散 σ2 の正規分布 N (µ, σ 2 ) に従うものとするとき，以下の問いに答えよ．また、連続確率変数 X が標準正規分布に従うとき，P (0 ≤X ≤ 1.64) = 0.4500, P (0 ≤ X ≤ 1.96) = 0.4750, P (0 ≤ X ≤ 2.33) = 0.4900,
P (0 ≤ X ≤ 2.58) = 0.4950 となる性質を，必要に応じて用いよ． （配点 50 点）
問 1 N (1, 0.1) の正規分布に従う母集団から，10 個の標本 X1 , X2 , · · · , X10 を無作
10
1 ∑為抽出した場合の標本平均 X =Xi は，確率変数と見なせる．この連
10 i=1
続確率変数 X の平均値と分散を求めよ．
問 2 N (µ, σ 2 ) の正規分布に従う母集団から，n 個の標本 X1 , X2 , · · · , Xn を無作為抽出した場合の標本平均が従う確率分布（確率密度関数）を示せ．
問 3 試験 A の受験者から 5 名を無作為抽出すると，それぞれの受験者の成績は

59, 63, 71, 78, 89 点であった．また，試験 A の成績の母分散が σ 2 = 245 であると分かっている．このとき，母平均 µ の 99% 信頼区間の上限と下限を求めよ．

確率論・統計学の問題は，このページで終りである．
— 7 —平成 19 年度

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

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

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

ペ ー ジ

問題数

選択方法

能

1

1問

左の１科目に解答してください．

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

2

1問

形式言語とオートマトン

3〜 4

1問

学

5

1問

ク

ス

6

1問

数

学

7

2問

学

8

1問

学

9 〜 11

2問

人

工

情

報

ロ

ボ

線

形

解
認

知

数

テ

ィ
代
析

知

心

理

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

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

4．解答欄内には 問題番号（I，II など）を，問いなどがある場合には問いの番号（問1 など）も記入してから解答を始めてください．
5．計算または下書き用紙 3 枚と下書き用原稿用紙 1 枚が解答用紙と一緒にあります．
6．試験中に問題冊子の印刷不明瞭，ページの落丁・乱丁および解答用紙の汚れ等に気がついた場合は，静かに手を上げて監督員に知らせてください．

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

人 工 知 能

I 次に示す記述に基づいて以下の問いに答えよ．（配点 50 点）
3 目並べのゲームを考える．このゲームでは，3 × 3 の盤面が与えられる．黒石，
白石を持つプレイヤーが黒の先手で交互に盤面のマスに石を置いていく．先に，縦，横，斜めに 3 つ連続して石を並べた方が勝ちになる．双方が 3 つ連続して並べられずに盤面が埋まれば引き分けである．このゲームについて，B(n) を n 個の黒石だ
けがあって白石が 0 個であるような縦，横，斜め方向の石の列の個数の和とする．
同様に W (n) を n 個の白石だけがある石の列の個数の和と定義する．たとえば，中央に黒石が 1 個置いてあるだけの局面では，B(1) = 4, B(2) = 0, B(3) = 0, W (1) =0, W (2) = 0, W (3) = 0 となる．また，B(3) = 1 かつ W (3) = 0 であるような局面
は黒石を持った方の勝ちになる．ここでは以下の評価関数 f を用いることにする．

f = 3B(2) + B(1) − (3W (2) + W (1))
問 1 どこにも石が置いていない初期状態から深さ 2 までの完全なゲーム木を書きなさい (深さ 2 の状態では，1 つの黒石と 1 つの白石が盤上に存在するものとす
る)．ただし，その際に対称性を考慮しなさい．深さ 1 では 3 通りの局面，深さ

2 では 12 通りの局面が存在するはずである．
問 2 問 1 で作成したゲーム木の深さ 2 のすべての局面に上記の評価関数を用いて計算した評価値を記入しなさい．
問 3 問 2 で作成したゲーム木にミニマックス (Minimax) アルゴリズムを適用して深さ 1 と深さ 0 の局面の評価値を記入しなさい．その結果を用いて黒の一手目を選びなさい (ゲーム木に選んだ手を太線で記入しなさい)．

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

I アルゴリズムを考える場合によく用いられる再帰法に関して，以下の問いに答えよ．
ただし，プログラムを記述する問いの解答には，C 言語または Java 言語を用いて記述せよ．（配点 50 点）

問 1 どのような問題を解く場合に，再帰法のアルゴリズムが利用できるか，その理由，再帰法を用いる利点を含めて 200 字程度で述べよ．
問 2 ２分木が，すべてのノードに対して• その左部分木のノードのキー値はそのキー値より小さく• その右部分木のノードのキー値はそのキー値より大きいという条件を満たす時，２分探索木と呼ぶ．２分探索木を用いる場合のデータ
構造を，C 言語であれば構造体，Java 言語であればクラスを用いて記述せよ．
ノードには，キー値として整数型のデータが１つ格納されているものとする．
問 3 問 2 で記述したデータ構造で作られた２分探索木から，整数型のデータを引数とし，そのデータと同じ大きさのデータを持つノードを再帰的に探索する関数を記述せよ．ただし，• 引数は整数型データ１つ，• 同じ大きさのデータを持つノードが検出された場合，“Find Node” という文字列を標準出力に表示して終了，• 同じ大きさのデータを持つノードが検出されなかった場合，“No Node” という文字列を標準出力に表示して終了，• 戻り値は問わないとする．

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

I 次に示す記述に基づいて以下の問いに答えよ．（配点 50 点）
一般的なショッピング Web サイトでは，利用者は商品のリストが表示されたページで購入したい商品を選択し，仮想的なショッピングカートに入れることを繰り返し，最後に支払い (チェックアウト) ページでクレジットカード情報を入力し，その時点でショッピングカートに入っている商品の購入手続きを完了するという手順で買い物を行うことができる．このようなショッピング Web サイトのページ遷移は有限状態オートマトンとみなすことができる．
今，以下のようなショッピング Web サイトを考える．

(i) 買物はトップページにアクセスすることで開始する．
(ii) トップページでユーザ ID とパスワードを入力して「ログイン」ボタンをクリックする．ログインに成功すると商品選択ページに遷移する．ログインに失敗した場合はトップページにもどる．

(iii) 商品選択ページでは，購入する商品を選択し，「カートに入れる」ボタンをクリックしてカートに入れることができる．これは複数回繰返すことができる．

(iv) 商品選択ページで「チェックアウト」ボタンをクリックすると，支払いページに遷移する．

(v) 支払いページでクレジットカード情報を入力し，「購入する」ボタンをクリック
する．成功すると購入完了ページに遷移し，失敗すると支払ページにもどる．

(vi) トップページ以外のすべてのページに「ログアウト」ボタンがあり，クリック
すると，トップページに遷移する．

— 3 —問 1 トップページ (q0 ) と商品選択ページ (q1 ) の間のページ遷移を状態遷移図で表すと図 1 のようになる．ここで，この場合に受理される語 (入力記号列) を二つ挙げよ．

図 1: 状態遷移図

凡例:

a: 有効なユーザ ID とパスワードの組が入力され，「ログイン」ボタンがクリッ
クされた

b: 無効なユーザ ID とパスワードの組が入力され，「ログイン」ボタンがクリッ
クされた

c: 「ログアウト」ボタンがクリックされた
問 2 図 1 の状態遷移図を元にして，(i) ∼ (vi) のすべての要件を満たす Web サ
イトの状態遷移図を作成せよ．なお，ページを遷移させる動作は適当な記号(a, b, c, . . .，ただし，同じ動作は同じ記号を用いること) で表し，その動作を凡例として示すこと．ただし，問 1 ですでに示している a, b, c の凡例は省略して良い．
問 3 問 2 で作成した状態遷移図で表わされる有限状態オートマトンによって受理される言語を正規表現で示せ．ただし，商品の購入が正常に完了する前に「ログアウト」ボタンをクリックしてトップページにもどる場合は除くこと．

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

I 以下の問いに答えよ．（配点 50 点）
問 1 実数全体の集合 R に対して，２つの写像 f : R → R と g : R → R を次のように定義する．

f (x) = 2x,g(x) = x2 + 1

このとき，合成写像 f ◦ g と合成写像 g ◦ f は等しくないことを示せ．
問 2 ２つの写像 f : A → B と g : B → C があるとき，単射の定義の対偶，すな
わち，「a, b ∈ A に対して， f (a) = f (b) ならば a = b である」を用いて，合成
写像 g ◦ f : A → C が単射ならば f も単射であることを示せ．
問 3 ２つの写像 f : A → B と g : B → C があるとき，合成写像 g ◦ f が単射でも，g は単射とは限らないことを，A = {a, b, c},

B = {1, 2, 3, 4, 5},

C = {α, β, γ}とした場合に示せ．

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

I マニピュレータ（腕型のロボット）において，図 1 のように直線運動する関節を直動関節と呼ぶ．マニピュレータが 2 つの直動関節により構成され，それぞれが 1 つの DC モータにより駆動されるとき，次の各問いに答えよ．ただし，マニピュレー
タの機構は，ある関節を駆動するモータが他の関節の変位に影響を与えないように構成されているものとする．また，i (i = 1, 2) 番目の関節の変位とモータの回転角度は，連続時間 t の関数としてそれぞれ ri (t), θi (t) と表され，ri (t) と θi (t) の関係は比例定数を Ki として ri (t) = Ki θi (t) と表されるものとする．（配点 50 点）

¾ ri

図1

-

直動関節の運動

問 1 i (i = 1, 2) 番目のモータに関して次の運動方程式が成り立つ場合，入力を電圧，出力を回転角度とする伝達関数 Gi を求めよ．ただし，ei (t) はモータへの入力電圧を表し，µi , γi はモータ固有の定数である．また，初期値は，時刻 t = 0
において ei (0) = 0, θi (0) = 0 として与えられるものとする．

d2 θi (t)dθi (t)= −µi+ γi ei (t)2dtdt
問 2 G1 を積分と定数倍の要素から成るブロック線図で示せ．
問 3 問 2 のブロック線図を基に，1 番目のモータに関する状態方程式を求めこれを示せ．また，状態変数が何を表すかを説明せよ．ただし，状態変数が複数ある場合は xj (t)(j = 1, 2, ...) と表し，出力に一番近いものを x1 (t) とせよ．
問 4 入力を [e1 (t), e2 (t)]T ，出力を [r1 (t), r2 (t)]T として，このマニピュレータのシ
ステム方程式を示せ．なお，T は転置を表すものとする．

ロ ボ テ ィ ク スの問題は，このページで終りである．
— 6 —線形代数学I 実ベクトル空間 R2 の正規直交基底 e1 , e2 を




1
1
e1 = √   ,
2
1





−1
1

e2 = √ 
2
1で与えるとき，以下の問いに答えよ．ただし，R2 のベクトル u に対して uT は uの転置ベクトルを表す．（配点 35 点）

問 1 eT1 e2 の値を求めよ．
問 2 ２つの行列 e1 eT1 , e2 eT2 を求めよ．
問 3 問２で求めた行列 e1 eT1 を P1 ，e2 eT2 を P2 で表すとき，R2 の任意のベクトル v に対して

v = P1 v + P2 vが成立することを示せ．

II Q2 = Q をみたす２次実対称行列 Q の固有値をすべて求めよ．ただし，Q は零行
列でも単位行列でもないとする．（配点 15 点）

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

解析学

I 以下の問いに答えよ．（配点 50 点）
問1

lim t2 e−t を求めよ．

t→∞

問 2 0 ≤ x ≤ 1 で定義された関数列 {fn (x)} を fn (x) = n2 xe−nx で定めるとき，

f (x) = lim fn (x) を求めよ．
n→∞

問3

∫ 1

∫ 1

n→∞ 0

0

lim

fn (x)dx =\f (x)dx を示せ．

解析学の問題は，このページで終りである．
— 8 —認知心理学I 図 1(a) はポンゾ錯視といわれる錯視図形であり，物理的には同じ長さの二つの線分が枠の存在で違った長さに見える錯視をひきおこす．図 1(a) の錯視図形を実空間の中に埋め込んだのが図 1(b) である．このとき，以下の問いに答えよ．（配点 30 点）

(a)

(b)
図１

(Coren, S. and Girgus, J. S. (Seeing is deceiving : the psychology of visual illusions.
Hillsdale, N.J. : Lawrence Erlbaum Associates, 1978.) を基に，Coren, S., Ward, L.
M., and Enns, J. T. (Sensation and perception. 4th ed. Fort Worth, TX : Harcourt
Brace College Publishers, 1994.) が作成した図から引用した．)
問 1 図 1(a) の錯視図形について，2 本の水平線分の長さの見え方を述べよ．
問 2 図 1(a) の錯視図形では，2 本の水平線分が物理的に等しい長さであることを「客観的正答」とし，違った長さに見える人間の知覚を「錯視」ということは自然である．一方，図 1(b) の風景画では，客観的正答が単純には決められない．
その理由を述べよ．
問 3 錯視の成立メカニズムに関して，3 次元の現実世界の安定した性質に関する— 9 —知識を脳が無意識的に用いるからだとする説がある．ポンゾ錯視にこの説を適用して，錯視成立のメカニズムを説明せよ．

— 10 —

II

発達研究に関する以下の問いに答えよ．（配点 20 点）
問 1 12 才から 15 才の生徒に対し，記憶検査を行い，年齢とともに検査結果がどのように変化するのかを調べるとする．同じ生徒を数年にわたって何度も検査する縦断的方法と，異なった年齢集団を選んで検査を行い，結果を比較する横断的方法がある．2 つの方法を比較してそれぞれの利点を述べよ．
問 2 ヒトの乳児には，見慣れた刺激より新奇な刺激を長く観察するということが知られている．このことを用いて，言葉がまだ話せない乳児がいつごろから丸い図形と四角い図形が弁別できるのかを調べる方法を述べよ．

認知心理学の問題は，このページで終りである．
— 11 —

平成 19 年度

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

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

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

ペ ー ジ

問題数

学

1

2問

学

2

1問

左の８科目のうちから

学

3

1問

４科目を選択し，解答

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

4

1問

形式言語とオートマトン

5〜 6

1問

ディジ タ ル 論 理 回 路

71問

デ ー タ ベ ー ス 工 学

81問

ソ フ ト ウェア 方 法 論

9 〜 11

1問

線

形

解
情

代

数

析
報

数

選択方法

してください．

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

4．解答欄内には 問題番号（I，II など）を，問いなどがある場合には問いの番号（問1 など）も記入してから解答を始めてください．
5．計算または下書き用紙 3 枚と下書き用原稿用紙 1 枚が解答用紙と一緒にあります．
6．試験中に問題冊子の印刷不明瞭，ページの落丁・乱丁および解答用紙の汚れ等に気がついた場合は，静かに手を上げて監督員に知らせてください．

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

線形代数学

I 実ベクトル空間 R2 の正規直交基底 e1 , e2 を




1
1
e1 = √   ,
2
1





−1
1

e2 = √ 
2
1で与えるとき，以下の問いに答えよ．ただし，R2 のベクトル u に対して uT は uの転置ベクトルを表す．（配点 35 点）

問 1 eT1 e2 の値を求めよ．
問 2 ２つの行列 e1 eT1 , e2 eT2 を求めよ．
問 3 問２で求めた行列 e1 eT1 を P1 ，e2 eT2 を P2 で表すとき，R2 の任意のベクトル v に対して

v = P1 v + P2 vが成立することを示せ．

II Q2 = Q をみたす２次実対称行列 Q の固有値をすべて求めよ．ただし，Q は零行
列でも単位行列でもないとする．（配点 15 点）

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

解析学

I 以下の問いに答えよ．（配点 50 点）
問1

lim t2 e−t を求めよ．

t→∞

問 2 0 ≤ x ≤ 1 で定義された関数列 {fn (x)} を fn (x) = n2 xe−nx で定めるとき，

f (x) = lim fn (x) を求めよ．
n→∞

問3

∫ 1

∫ 1

n→∞ 0

0

lim

fn (x)dx =\f (x)dx を示せ．

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

I 以下の問いに答えよ．（配点 50 点）
問 1 実数全体の集合 R に対して，２つの写像 f : R → R と g : R → R を次のように定義する．

f (x) = 2x,g(x) = x2 + 1

このとき，合成写像 f ◦ g と合成写像 g ◦ f は等しくないことを示せ．
問 2 ２つの写像 f : A → B と g : B → C があるとき，単射の定義の対偶，すな
わち，「a, b ∈ A に対して， f (a) = f (b) ならば a = b である」を用いて，合成
写像 g ◦ f : A → C が単射ならば f も単射であることを示せ．
問 3 ２つの写像 f : A → B と g : B → C があるとき，合成写像 g ◦ f が単射でも，g は単射とは限らないことを，A = {a, b, c},

B = {1, 2, 3, 4, 5},

C = {α, β, γ}とした場合に示せ．

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

I アルゴリズムを考える場合によく用いられる再帰法に関して，以下の問いに答えよ．
ただし，プログラムを記述する問いの解答には，C 言語または Java 言語を用いて記述せよ．（配点 50 点）

問 1 どのような問題を解く場合に，再帰法のアルゴリズムが利用できるか，その理由，再帰法を用いる利点を含めて 200 字程度で述べよ．
問 2 ２分木が，すべてのノードに対して• その左部分木のノードのキー値はそのキー値より小さく• その右部分木のノードのキー値はそのキー値より大きいという条件を満たす時，２分探索木と呼ぶ．２分探索木を用いる場合のデータ
構造を，C 言語であれば構造体，Java 言語であればクラスを用いて記述せよ．
ノードには，キー値として整数型のデータが１つ格納されているものとする．
問 3 問 2 で記述したデータ構造で作られた２分探索木から，整数型のデータを引数とし，そのデータと同じ大きさのデータを持つノードを再帰的に探索する関数を記述せよ．ただし，• 引数は整数型データ１つ，• 同じ大きさのデータを持つノードが検出された場合，“Find Node” という文字列を標準出力に表示して終了，• 同じ大きさのデータを持つノードが検出されなかった場合，“No Node” という文字列を標準出力に表示して終了，• 戻り値は問わないとする．

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

I 次に示す記述に基づいて以下の問いに答えよ．（配点 50 点）
一般的なショッピング Web サイトでは，利用者は商品のリストが表示されたページで購入したい商品を選択し，仮想的なショッピングカートに入れることを繰り返し，最後に支払い (チェックアウト) ページでクレジットカード情報を入力し，その時点でショッピングカートに入っている商品の購入手続きを完了するという手順で買い物を行うことができる．このようなショッピング Web サイトのページ遷移は有限状態オートマトンとみなすことができる．
今，以下のようなショッピング Web サイトを考える．

(i) 買物はトップページにアクセスすることで開始する．
(ii) トップページでユーザ ID とパスワードを入力して「ログイン」ボタンをクリックする．ログインに成功すると商品選択ページに遷移する．ログインに失敗した場合はトップページにもどる．

(iii) 商品選択ページでは，購入する商品を選択し，「カートに入れる」ボタンをクリックしてカートに入れることができる．これは複数回繰返すことができる．

(iv) 商品選択ページで「チェックアウト」ボタンをクリックすると，支払いページに遷移する．

(v) 支払いページでクレジットカード情報を入力し，「購入する」ボタンをクリック
する．成功すると購入完了ページに遷移し，失敗すると支払ページにもどる．

(vi) トップページ以外のすべてのページに「ログアウト」ボタンがあり，クリック
すると，トップページに遷移する．

— 5 —問 1 トップページ (q0 ) と商品選択ページ (q1 ) の間のページ遷移を状態遷移図で表すと図 1 のようになる．ここで，この場合に受理される語 (入力記号列) を二つ挙げよ．

図 1: 状態遷移図

凡例:

a: 有効なユーザ ID とパスワードの組が入力され，「ログイン」ボタンがクリッ
クされた

b: 無効なユーザ ID とパスワードの組が入力され，「ログイン」ボタンがクリッ
クされた

c: 「ログアウト」ボタンがクリックされた
問 2 図 1 の状態遷移図を元にして，(i) ∼ (vi) のすべての要件を満たす Web サ
イトの状態遷移図を作成せよ．なお，ページを遷移させる動作は適当な記号(a, b, c, . . .，ただし，同じ動作は同じ記号を用いること) で表し，その動作を凡例として示すこと．ただし，問 1 ですでに示している a, b, c の凡例は省略して良い．
問 3 問 2 で作成した状態遷移図で表わされる有限状態オートマトンによって受理される言語を正規表現で示せ．ただし，商品の購入が正常に完了する前に「ログアウト」ボタンをクリックしてトップページにもどる場合は除くこと．

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

I 2 桁の 2 進数 A = a1 a0 , B = b1 b0 の大小を比較して, A > B のときには X = 1,
Y = 0 を, A < B のときには X = 0, Y = 1 を, A = B のときには X = Y = 1 を,それぞれ出力する論理回路を設計したい. このとき以下の問いに答えよ.
（配点 50 点）

問 1 X, Y の真理値表を作成せよ.
問 2 X, Y の論理式を簡単化し, その論理回路を作図せよ.

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

I 大学の授業の履修状況をデータベースで管理するために，必要な項目を検討することにした．管理しようとしているデータの一例を次に示す．
授業データ(データベース工学, 1111, 山田, 523, 金曜日 1 限, 2 単位, 3 年前期)
(ソフトウェア方法論, 1112, 中村, 425, 水曜日 5 限, 2 単位, 3 年前期)
(人工知能, 1113, 斎藤, 725, 月曜日 3 限, 2 単位, 2 年前期)
学生データ

(相川, 1201001, 1111, 1112)(伊藤, 1201002, 1111, 1112, 1113)(井上, 1201003, 1113)
まず，データから以下のようなリレーションを考えることにする．
リレーション授業(科目名，授業コード，担当教員，講義場所，講義日時，習得単位，開講時期)
リレーション学生(氏名，学籍番号，授業コード，授業コード，...)
同じ科目名でも担当教員や講義場所，講義日時が違う場合を区別するために，授業コードを決めることにした．また，学生は複数の授業を履修できるため，複数の授業コードを扱えるようにしたい．
リレーション授業およびリレーション学生を正規化してデータベースに格納する手順を考えたとき，以下の問いに答えよ．（配点 50 点）

問 1 リレーション授業で，主キーはどれであるか答えよ．
問 2 リレーション学生では，履修している科目数分だけ授業コードを格納する必要がある．このままではデータベースに格納できないので，複数の授業コード
をデータベースに格納するにはどのような正規化を行えばよいか答えよ．
問 3 データベースに格納するためにリレーション授業とリレーション学生を整理して，データベーステーブルを設計せよ．

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

I オブジェクト指向を利用したソフトウェア開発の分析，設計フェーズでは，UML(Uniﬁed Modeling Language) のいくつかの図 (diagram) が用いられる．今，以下の要件を満たす書籍検索 Web サイトを設計するものとする．

• キーワードを入力して書籍を検索することができる．
• 登録ユーザは自分のお気に入りキーワードリストを持つことができ，専用ページで内容を編集することができる．

• 管理者は登録ユーザの登録情報を更新することができる．
この要件に基づき，最初にユースケース図を作成し，次に「書籍を検索する」機能のクラス設計を行うものとする．クラス設計ではクラス間の構造と動作をそれぞれ明確にするために，クラス図とシーケンス図を作成することにする．図 1〜3 は，それらの作成途中の図である．
この時点で，書籍を検索する機能に関するアプリケーションの動作を以下のように想定している．検索を行う Search クラスでは，ユーザが入力した検索キーワー
ド文字列を QueryWords クラスによって保持し，全角の英数記号が含まれていれば半角に直す (正規化)．そして，正規化された文字列をデータベースとの仲介を行う

DataAccess クラスに渡す．DataAccess クラスでは検索キーワードを用いてデータ
ベースから該当する書籍を検索し，検索結果を適当なクラスに格納して Search ク
ラスに返す．
以上の設計過程について以下の問いに答えよ．（配点 50 点）

図 1: ユースケース図— 9 —QueryWords
DataAccesssearch_result(a)Search(b)db_accessquery_string
normalized_string

(c)

Book

0..*

(d)
(e)
(f)
isbn

図 2: クラス図

Searchnew(query_string)(g)(h)

new( (i) )DataAccess(j)db_searchnew( (k) )(l)

図 3: シーケンス図— 10 —(l)問 1 図 1 のユースケース図を完成させよ．
問 2 図 3 のシーケンス図と対応するように図 2 のクラス図の (a)〜(f) を埋めよ．
なお，シーケンス図では記述を省略しているクラスもある．
問 3 図 2 のクラス図と対応するように図 3 のシーケンス図の (g)〜(l) を埋めよ．
なお，new はクラスのコンストラクタ (生成関数) の呼び出しを表現しており，( ) の中にはコンストラクタに引数として渡す変数の名前が入る．

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

平成 19 年度

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

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

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

知

情

報

心

ペ ー ジ

問題数

選択方法

理

学

1〜 3

2問

イ

ン

4

1問

左の５科目のうちからヒューマンインタフェース

5

1問

４科目を選択し，解答

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

6

1問

してください．

メ ディア デ ザ イ ン 基 礎

7〜 9

2問

デ

ザ

3．解答用紙は 9 枚に分かれています．指定された科目の解答用紙を用いてください．
「情報デザイン」の科目を選択する場合には，３枚目の解答用紙を用いてください．
それ以外の科目では， １科目に２枚の解答用紙を用いてください．解答に用いなかった解答用紙も含め，すべての解答用紙の所定欄に受験番号と氏名をはっきりと記入
してください．

4．解答用紙表紙の表に選択した科目を◯で記してください．
5．解答欄内には 問題番号（I，II など）を，問いなどがある場合には問いの番号（問1 など）も記入してから解答を始めてください．
6．計算または下書き用紙 3 枚と下書き用原稿用紙 1 枚が解答用紙と一緒にあります．
7．試験中に問題冊子の印刷不明瞭，ページの落丁・乱丁および解答用紙の汚れ等に気がついた場合は，静かに手を上げて監督員に知らせてください．

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

認知心理学I 図 1(a) はポンゾ錯視といわれる錯視図形であり，物理的には同じ長さの二つの線分が枠の存在で違った長さに見える錯視をひきおこす．図 1(a) の錯視図形を実空間の中に埋め込んだのが図 1(b) である．このとき，以下の問いに答えよ．（配点 30 点）

(a)

(b)
図１

(Coren, S. and Girgus, J. S. (Seeing is deceiving : the psychology of visual illusions.
Hillsdale, N.J. : Lawrence Erlbaum Associates, 1978.) を基に，Coren, S., Ward, L.
M., and Enns, J. T. (Sensation and perception. 4th ed. Fort Worth, TX : Harcourt
Brace College Publishers, 1994.) が作成した図から引用した．)
問 1 図 1(a) の錯視図形について，2 本の水平線分の長さの見え方を述べよ．
問 2 図 1(a) の錯視図形では，2 本の水平線分が物理的に等しい長さであることを「客観的正答」とし，違った長さに見える人間の知覚を「錯視」ということは自然である．一方，図 1(b) の風景画では，客観的正答が単純には決められない．
その理由を述べよ．
問 3 錯視の成立メカニズムに関して，3 次元の現実世界の安定した性質に関する— 1 —知識を脳が無意識的に用いるからだとする説がある．ポンゾ錯視にこの説を適用して，錯視成立のメカニズムを説明せよ．

— 2 —

II

発達研究に関する以下の問いに答えよ．（配点 20 点）
問 1 12 才から 15 才の生徒に対し，記憶検査を行い，年齢とともに検査結果がどのように変化するのかを調べるとする．同じ生徒を数年にわたって何度も検査する縦断的方法と，異なった年齢集団を選んで検査を行い，結果を比較する横断的方法がある．2 つの方法を比較してそれぞれの利点を述べよ．
問 2 ヒトの乳児には，見慣れた刺激より新奇な刺激を長く観察するということが知られている．このことを用いて，言葉がまだ話せない乳児がいつごろから丸い図形と四角い図形が弁別できるのかを調べる方法を述べよ．

認知心理学の問題は，このページで終りである．
— 3 —情報デザインI 解答用紙の 12 コマの方眼を用いて，「やわらかさ」を連想させループ（繰り返し）するアニメーションを作成せよ．さらに，その制作意図を指定の欄に簡潔に記入せよ．（配点 50 点）
注意事項• □を■に塗りつぶすことで表現すること．
• 12 コマの方眼を 01∼12 の順番に総て使用すること．
• 塗りつぶす■の数の制限はない．

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

I 認知工学の産みの親である D.A. ノーマンは，人の行為にかかわる選択肢の数を制限するものとして，4 種類の「制約」を挙げている．以下の各制約について，具体例を図示し，150 字程度で説明せよ．（配点 50 点）

1. 物理的制約
2. 意味的制約
3. 文化的制約
4. 論理的制約

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

I アルゴリズムを考える場合によく用いられる再帰法に関して，以下の問いに答えよ．
ただし，プログラムを記述する問いの解答には，C 言語または Java 言語を用いて記述せよ．（配点 50 点）

問 1 どのような問題を解く場合に，再帰法のアルゴリズムが利用できるか，その理由，再帰法を用いる利点を含めて 200 字程度で述べよ．
問 2 ２分木が，すべてのノードに対して• その左部分木のノードのキー値はそのキー値より小さく• その右部分木のノードのキー値はそのキー値より大きいという条件を満たす時，２分探索木と呼ぶ．２分探索木を用いる場合のデータ
構造を，C 言語であれば構造体，Java 言語であればクラスを用いて記述せよ．
ノードには，キー値として整数型のデータが１つ格納されているものとする．
問 3 問 2 で記述したデータ構造で作られた２分探索木から，整数型のデータを引数とし，そのデータと同じ大きさのデータを持つノードを再帰的に探索する関数を記述せよ．ただし，• 引数は整数型データ１つ，• 同じ大きさのデータを持つノードが検出された場合，“Find Node” という文字列を標準出力に表示して終了，• 同じ大きさのデータを持つノードが検出されなかった場合，“No Node” という文字列を標準出力に表示して終了，• 戻り値は問わないとする．

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

I 6 人の被験者が，訓練を受ける前後にある課題を遂行してもらったところ，課題の成績は表 1 のようであった．t 検定により，訓練前後の成績の平均に統計的に有意な差があるかを検討するとする．検定は両側検定を行うものとする．以下の問いに答えよ．（配点 30 点）
表 1: 訓練を受ける前後の成績
訓練前

訓練後

被験者 1

7

11

被験者 2

8

12

被験者 3

8

13

被験者 4

7

6

被験者 5

6

7

被験者 6

5

10

問 1 この場合の帰無仮説は何か述べよ．
問 2 Di を被験者 i の訓練後の成績から訓練前の成績を引いた値，n を被験者数として，t 値は以下の公式で求めることができる．t 値を計算せよ．
n
X

t= v
u

Di

i=1

n
n
X
u X 2
u n
D
−
(
Di )2
i
u
t i=1
i=1

n−1
問 3 表 2 に示す t の表を利用し，この検定の t 値の 5% 臨界値を答えよ．
問 4 問 1∼ 問 3 の結果から，両側 5%の有意水準で，統計的に有意な差があるのか，あるとはいえないのかを答えよ．

— 7 —表 2: t の表
両側検定の有意水準

df

5%

1

12.706

2

4.303

3

3.182

4

2.776

5

2.571

6

2.447

7

2.365

8

2.306

9

2.262

10

2.228

11

2.201

12

2.179

13

2.160

14

2.145

— 8 —

II 製品の開発プロセスで行われるユーザビリティ（使いやすさ）の評価手法としては，多くの手法がある．それらから１つを選び，手法名とその特徴（長所・短所を含む）
を 300 字程度で簡潔に述べよ．（配点 20 点）

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