平成 20 年度

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

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

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

形

代

解

数

析

情

報

数

ペ ー ジ

問題数

選択方法

学

1

1問

左の２科目のすべてを

学

2

1問

解答してください．

学

3

1問

微

分

方

程

式

4

1問

左の５科目のうちから

応

用

解

析

学

5

1問

２科目を選択し，解答

確

率

論・統

計

学

6

1問

してください．

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

7〜 8

1問

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

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

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

線形代数学

I 行列 A と B が次のように与えられているとする．


A=

a 1 a


 ,

1 a 1





 1 a 
B=
 a 1 


1 a



ここで，a は実数とする．このとき，以下の問いに答えよ．（配点 50 点）

問 1 行列の積 AB と BA をそれぞれ求めよ．
問 2 AB が正則であるための a の条件を求めよ．
問 3 任意の a に対して BA が正則でないことを示せ．

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

解析学

I 閉区間 [0, 1] 上の関数列 {fn (x)}n=0,1,2,··· を以下のように定める．f0 (x) を [0, 1] 上で値 1 をとる定数関数とし，fn (x) (n = 1, 2, 3, · · ·) を漸化式
∫ x

fn+1 (x) = 1 +

0

fn (t)dt(0 ≤ x ≤ 1, n = 0, 1, 2, · · ·)(1)で定義する．以下の問いに答えよ．（配点 50 点）

問 1 漸化式 (1) から，f1 (x), f2 (x), f3 (x) を求めよ．
問 2 一般項 fn (x) を求めよ．
問 3 [0, 1] の各点 x において， lim fn (x) = f (x) が成り立つような f (x) を書け．
n→∞

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

I 以下の問いに答えよ．（配点 50 点）
問 1 X, Y を空でない集合とする．写像 f : X → Y において，すべての x1 , x2 ∈ X
に対して，もし x1 =\ x2 ならば f (x1 ) =\ f (x2 ) が成り立つ．

(1-1) 上記の文章は，単射，全射，全単射のどれを定義したものか答えよ．
(1-2) その写像の具体例を図または式で示せ．

問 2 次の写像が 1m
全射であるか，また， 2m
単射であるか，を判定せよ．その際，と 2m両方に答えよ．
1m(2-1) X = {x1 , x2 , x3 , x4 , x5 } , Y = {y1 , y2 , y3 , y4 }
f (x1 ) = y2 , f (x2 ) = y1 , f (x3 ) = y2 , f (x4 ) = y4 , f (x5 ) = y4(2-2) X = {x1 , x2 , x3 , x4 , x5 } , Y = {y1 , y2 , y3 , y4 , y5 }f (x1 ) = y4 , f (x2 ) = y5 , f (x3 ) = y3 , f (x4 ) = y2 , f (x5 ) = y1

問 3 X, Y , Z, W を空でない集合とする．このとき，写像 f : X → Y ,g : Y → Z, h : Z → W に対して，写像の合成の結合律 (h · g) · f ＝ h · (g · f )が成り立つことを証明せよ．

情報数学の問題は，このページで終りである．
— 3 —微分方程式I 未知関数 y = y(x) に対する微分方程式y′ =−x + 3yx + 2y（ただし，′ は変数 x に関する微分とする）

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

問 1 z(x) =

1
a

y(x)
と変換することによって (1) はx(

2az + ba−b+az 2 + bz + c
az 2 + bz + c)

z′ = −

1xとなる．このとき、定数 a, b, c を求めよ．
問 2 問 1 の微分方程式を z に関して解くことにより，(1) の解を求めよ．

微分方程式の問題は，このページで終りである．
— 4 —

(1)

応用解析学π2について次の問いに答えよ．（配点 50 点点）
3
問 1 [−π, π] において f (x) のフーリエ級数を求めよ．

I f (x) = x2 −問 2 問 1 で求めたフーリエ級数は [−π, π] で収束することを示せ．
問 3 f (x) のフーリエ級数を g(x) とする．等式 f (x) = g(x) が [−π, π] で成立することを認めて，級数

1−11(−1)n−1
+
−
·
·
·
+
+ ···
22 32
n2

の値を求めよ．

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

I 確率変数 Xi (i = 1, 2, · · ·) は互いに独立であるが，それぞれ平均値 µi ，分散 σi2 の正規分布 N (µi , σi2 )N (µi , σi2 ) =((xi − µi )2
√
exp −
2σi2
2πσ 2
1

)

i

に従うものとするとき，以下の問いに答えよ．（配点 50 点）

問1

X=

5
∑

Xi とするとき，X の平均値と分散を求めよ．

i=1問 2 問 1 の X が従う確率分布（密度関数）を示せ．
問 3 下記に挙げた (1) から (5) の五つの統計学に関連した語句の中から一つを選び，選択した語句を示した上で，その語句の意味と，それが統計学においてどのような役割を果たすかを説明せよ．
語句(1) 無作為抽出 (2) 標本分布 (3) 区間推定 (4) 帰無仮説 (5) 不偏推定量

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

I 指定された順序に従って，数値を値として持つ二分探索木を構成する手順があるものとする．二分探索木は，構成時のデータ中の数値の順により異なる形をとる．二分探索木の形はたとえば，１，２，３，４の順に数値を与えると，図１のようにな
り，３，１，２，４の順に数値を与えると，図２のような形になる．

1
2
3
4
図 1:

3
4

1
2

図 2:

以下の問いに答えよ．（配点 50 点）
問 1 節点をひとつも持たない初期状態から初めて，それぞれ以下の３つのデータを追加したときに，それぞれの入力が完了した段階で出来上がる二分探索木を図示せよ．

• データ１：１，３，５，８，２• データ２：６，４，９，２，１• データ３：７，５，１０，１，４，２問 2 問 1 の解となる二分探索木をコピーした上で，これらの三つの二分探索木に対して数値６を探索させる場合の探索経路の順序を書き加えよ．

— 7 —問 3 それぞれの二分探索木を幅優先探索（横型探索）でノードを辿るものとする．
問 1 の解となる三つの二分木に対し，辿られる順にノードの値を列挙せよ．ただし，同一レベルにあるノードは左から順に列挙するものとする．
問 4 それぞれの二分探索木を深さ優先探索（縦型探索）でノードを辿るものとす
る．問 1 の解となる三つの二分木に対し，辿られる順にノードの値を列挙せよ．
ただし，同一レベルにあるノードは左から順に列挙するものとする．

アルゴリズムとデータ構造の問題は，このページで終りである．
— 8 —平成 20 年度

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

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

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

ペ ー ジ

問題数

選択方法

能

1

1問

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

学

2

1問

学

3

1問

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

4〜 5

1問

形式言語とオートマトン

6〜 7

1問

学

8

1問

ク

ス

9

1問

理

学

10

1問

人
線

工
形

知
代

解

数

析

情

報

ロ

ボ

認

知

数

テ

ィ
心

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

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

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

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

人 工 知 能I 以下の図において初期状態は S で目標状態は G とし，S から G への経路を探索する問題を考える．ヒューリステック関数としてマンハッタン距離を用いることにする．ただし (x1, y1) と (x2, y2) のマンハッタン距離は |x1 − x2| + |y1 − y2| である．また，コストの見積りが同じ値の場合は，アルファベットが若いノードを優先するものとする．以下の問いに答えよ．（配点 50 点）

問 1 この問題においてマンハッタン距離が楽観的（許容的）ヒューリステックであることを示しなさい．
問 2 この問題を山登り法で解きなさい．解の経路と総コストを示しなさい．
問 3 この問題を最良優先探索で解きなさい．解の経路と総コストを示しなさい．
問 4 この問題を A＊ アルゴリズムで解きなさい．解の経路と総コストを示しな
さい．

(0, 3)F (1, 3)dG(3, 3)

H(5, 3)ddd E(1, 2)

d D(1, 1)(0, 1)ddddS(0, 0)A(1, 0)B(3, 0)C(5, 0)

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

I 行列 A と B が次のように与えられているとする．


A=

a 1 a


 ,

1 a 1





 1 a 
B=
 a 1 


1 a



ここで，a は実数とする．このとき，以下の問いに答えよ．（配点 50 点）

問 1 行列の積 AB と BA をそれぞれ求めよ．
問 2 AB が正則であるための a の条件を求めよ．
問 3 任意の a に対して BA が正則でないことを示せ．

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

解析学

I 閉区間 [0, 1] 上の関数列 {fn (x)}n=0,1,2,··· を以下のように定める．f0 (x) を [0, 1] 上で値 1 をとる定数関数とし，fn (x) (n = 1, 2, 3, · · ·) を漸化式
∫ x

fn+1 (x) = 1 +

0

fn (t)dt(0 ≤ x ≤ 1, n = 0, 1, 2, · · ·)(1)で定義する．以下の問いに答えよ．（配点 50 点）

問 1 漸化式 (1) から，f1 (x), f2 (x), f3 (x) を求めよ．
問 2 一般項 fn (x) を求めよ．
問 3 [0, 1] の各点 x において， lim fn (x) = f (x) が成り立つような f (x) を書け．
n→∞

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

I 指定された順序に従って，数値を値として持つ二分探索木を構成する手順があるものとする．二分探索木は，構成時のデータ中の数値の順により異なる形をとる．二分探索木の形はたとえば，１，２，３，４の順に数値を与えると，図１のようにな
り，３，１，２，４の順に数値を与えると，図２のような形になる．

1
2
3
4
図 1:

3
4

1
2

図 2:

以下の問いに答えよ．（配点 50 点）
問 1 節点をひとつも持たない初期状態から初めて，それぞれ以下の３つのデータを追加したときに，それぞれの入力が完了した段階で出来上がる二分探索木を図示せよ．

• データ１：１，３，５，８，２• データ２：６，４，９，２，１• データ３：７，５，１０，１，４，２問 2 問 1 の解となる二分探索木をコピーした上で，これらの三つの二分探索木に対して数値６を探索させる場合の探索経路の順序を書き加えよ．

— 4 —問 3 それぞれの二分探索木を幅優先探索（横型探索）でノードを辿るものとする．
問 1 の解となる三つの二分木に対し，辿られる順にノードの値を列挙せよ．ただし，同一レベルにあるノードは左から順に列挙するものとする．
問 4 それぞれの二分探索木を深さ優先探索（縦型探索）でノードを辿るものとす
る．問 1 の解となる三つの二分木に対し，辿られる順にノードの値を列挙せよ．
ただし，同一レベルにあるノードは左から順に列挙するものとする．

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

I 図 1 に示す格子状に配置したセル群 (cellular automata) を考える．各セルは {0, 1}の２つの状態をとることができる．状態 1 を黒のセルで表わし，状態 0 を白のセルで表わす．時間 t における格子上の (i, j) にあるセルの状態を Si,j (t) とし，セル(i, j) の近傍関数 Hi,j (t) を式 (1) とする．
j

-

i
´
´
´
+́´

?

´
´
´

´ セル (i, j)

図 1: Cellular automata

Hi,j (t) = Si,j−1 (t) + Si,j+1 (t) + Si−1,j (t) + Si+1,j (t)(1)

時間に対するセルの状態遷移は式 (2) に従う．状態遷移関数 F を図 2 に示す．

Si,j (t + 1) = F (Si,j (t), Hi,j (t))

図 2: 状態遷移図

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

— 6 —

(2)

問 1 時刻 t において，cellular automata が図 3 に示す状態を取るとする．

a) Hi,j (t), Hi+2,j (t) と Hi,j−1 (t) の値を求めよ．
b) Si,j (t + 1) と Si+1,j (t + 1) の値を求めよ．

´+́´ セル (i, j)
´
´
´

図 3:

問 2 時刻 t = 0 において，cellular automata が以下の図 4 に示す状態をとる場合，t = 1 と t = 2 の cellular automata の状態を図示せよ．

図 4:

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

I 以下の問いに答えよ．（配点 50 点）
問 1 X, Y を空でない集合とする．写像 f : X → Y において，すべての x1 , x2 ∈ X
に対して，もし x1 =\ x2 ならば f (x1 ) =\ f (x2 ) が成り立つ．

(1-1) 上記の文章は，単射，全射，全単射のどれを定義したものか答えよ．
(1-2) その写像の具体例を図または式で示せ．

問 2 次の写像が 1m
全射であるか，また， 2m
単射であるか，を判定せよ．その際，と 2m両方に答えよ．
1m(2-1) X = {x1 , x2 , x3 , x4 , x5 } , Y = {y1 , y2 , y3 , y4 }
f (x1 ) = y2 , f (x2 ) = y1 , f (x3 ) = y2 , f (x4 ) = y4 , f (x5 ) = y4(2-2) X = {x1 , x2 , x3 , x4 , x5 } , Y = {y1 , y2 , y3 , y4 , y5 }f (x1 ) = y4 , f (x2 ) = y5 , f (x3 ) = y3 , f (x4 ) = y2 , f (x5 ) = y1

問 3 X, Y , Z, W を空でない集合とする．このとき，写像 f : X → Y ,g : Y → Z, h : Z → W に対して，写像の合成の結合律 (h · g) · f ＝ h · (g · f )が成り立つことを証明せよ．

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

I 図 1 は，車輪型移動ロボットの車輪のモデル図である．ここでは，半径 r の車輪
が DC モータによって駆動され，モータの回転が減速比 n で車輪に伝達されるものとする．このとき，モータと車輪の回転角度は，連続時間 t の関数としてそれぞれ

θm (t), θw (t) と表され，時刻 t = 0 において θm (0) = 0, θw (0) = 0 であるものとする．
また，θm (t) = nθw (t) の関係が成り立ち，モータの運動方程式は，モータに与える
トルクの指令値 um (t) に対して J θ̈m (t) + Dθ̇m (t) = um (t) として与えられるものとする．ただし，J は慣性モーメント，D は粘性摩擦係数を表し，それぞれモータお
よび車輪を考慮したものが用いられているものとする．（配点 50 点）

v(t)
¾

車輪

´
s
µ

´
´r

θw (t)aモータsθm (t)µ

図 1: 車輪のモデル図
この車輪の制御に関して次の各問いに答えよ．
問 1 図 1 に示すような車輪の接線方向の速度 v(t) を θm (t) により表せ．
問 2 入力を um (t)，出力を v(t) として図 1 に示す車輪のモデルをブロック線図により表せ．
問 3 目標速度を vd (t) とし，I 制御により v(t) を vd (t) に一致させる制御系のブロック線図を示せ．ただし，I 制御のゲインを KI とする．また，入力を vd (t)，出力を v(t) として制御系全体の伝達関数を示せ．

ロ ボ テ ィ ク スの問題は，このページで終りである．
— 9 —認知心理学

I スクリプトとは，認知科学事典（日本認知科学会,2004）によると，日常経験する典型的な場面をモデル化してそこに生ずる事象列を形式化した知識である．下に挙げるのはレストランのスクリプトの例である．
レストランに行く
料理を注文する料理が来たらそれを食べる
代金を払って出てくる
以下の問いに答えよ．（配点 50 点）

問 1 世界を旅慣れている人が持つレストランのスクリプトと，外国を旅行したことのない人が持つレストランのスクリプトにはどのような違いがあるのか，具体的な場面を想定して説明せよ．
問 2 旅慣れている人の例を使ってスクリプトが形成されるプロセスを説明せよ．

[参考文献]

日本認知科学会

編 (2004)

デジタル

認知科学事典

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

共立出版

平成 20 年度

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

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

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

ペ ー ジ

問題数

学

1

1問

学

2

1問

左の８科目のうちから

学

3

1問

４科目を選択し，解答

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

4〜 5

1問

形式言語とオートマトン

6〜 7

1問

ディジ タ ル 論 理 回 路

81問

デ ー タ ベ ー ス 工 学

91問

ソ フ ト ウェア 方 法 論

10 〜 12

1問

線

形

解
情

代

数

析
報

数

選択方法

してください．

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

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

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

線形代数学

I 行列 A と B が次のように与えられているとする．


A=

a 1 a


 ,

1 a 1





 1 a 
B=
 a 1 


1 a



ここで，a は実数とする．このとき，以下の問いに答えよ．（配点 50 点）

問 1 行列の積 AB と BA をそれぞれ求めよ．
問 2 AB が正則であるための a の条件を求めよ．
問 3 任意の a に対して BA が正則でないことを示せ．

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

解析学

I 閉区間 [0, 1] 上の関数列 {fn (x)}n=0,1,2,··· を以下のように定める．f0 (x) を [0, 1] 上で値 1 をとる定数関数とし，fn (x) (n = 1, 2, 3, · · ·) を漸化式
∫ x

fn+1 (x) = 1 +

0

fn (t)dt(0 ≤ x ≤ 1, n = 0, 1, 2, · · ·)(1)で定義する．以下の問いに答えよ．（配点 50 点）

問 1 漸化式 (1) から，f1 (x), f2 (x), f3 (x) を求めよ．
問 2 一般項 fn (x) を求めよ．
問 3 [0, 1] の各点 x において， lim fn (x) = f (x) が成り立つような f (x) を書け．
n→∞

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

I 以下の問いに答えよ．（配点 50 点）
問 1 X, Y を空でない集合とする．写像 f : X → Y において，すべての x1 , x2 ∈ X
に対して，もし x1 =\ x2 ならば f (x1 ) =\ f (x2 ) が成り立つ．

(1-1) 上記の文章は，単射，全射，全単射のどれを定義したものか答えよ．
(1-2) その写像の具体例を図または式で示せ．

問 2 次の写像が 1m
全射であるか，また， 2m
単射であるか，を判定せよ．その際，と 2m両方に答えよ．
1m(2-1) X = {x1 , x2 , x3 , x4 , x5 } , Y = {y1 , y2 , y3 , y4 }
f (x1 ) = y2 , f (x2 ) = y1 , f (x3 ) = y2 , f (x4 ) = y4 , f (x5 ) = y4(2-2) X = {x1 , x2 , x3 , x4 , x5 } , Y = {y1 , y2 , y3 , y4 , y5 }f (x1 ) = y4 , f (x2 ) = y5 , f (x3 ) = y3 , f (x4 ) = y2 , f (x5 ) = y1

問 3 X, Y , Z, W を空でない集合とする．このとき，写像 f : X → Y ,g : Y → Z, h : Z → W に対して，写像の合成の結合律 (h · g) · f ＝ h · (g · f )が成り立つことを証明せよ．

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

I 指定された順序に従って，数値を値として持つ二分探索木を構成する手順があるものとする．二分探索木は，構成時のデータ中の数値の順により異なる形をとる．二分探索木の形はたとえば，１，２，３，４の順に数値を与えると，図１のようにな
り，３，１，２，４の順に数値を与えると，図２のような形になる．

1
2
3
4
図 1:

3
4

1
2

図 2:

以下の問いに答えよ．（配点 50 点）
問 1 節点をひとつも持たない初期状態から初めて，それぞれ以下の３つのデータを追加したときに，それぞれの入力が完了した段階で出来上がる二分探索木を図示せよ．

• データ１：１，３，５，８，２• データ２：６，４，９，２，１• データ３：７，５，１０，１，４，２問 2 問 1 の解となる二分探索木をコピーした上で，これらの三つの二分探索木に対して数値６を探索させる場合の探索経路の順序を書き加えよ．

— 4 —問 3 それぞれの二分探索木を幅優先探索（横型探索）でノードを辿るものとする．
問 1 の解となる三つの二分木に対し，辿られる順にノードの値を列挙せよ．ただし，同一レベルにあるノードは左から順に列挙するものとする．
問 4 それぞれの二分探索木を深さ優先探索（縦型探索）でノードを辿るものとす
る．問 1 の解となる三つの二分木に対し，辿られる順にノードの値を列挙せよ．
ただし，同一レベルにあるノードは左から順に列挙するものとする．

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

I 図 1 に示す格子状に配置したセル群 (cellular automata) を考える．各セルは {0, 1}の２つの状態をとることができる．状態 1 を黒のセルで表わし，状態 0 を白のセルで表わす．時間 t における格子上の (i, j) にあるセルの状態を Si,j (t) とし，セル(i, j) の近傍関数 Hi,j (t) を式 (1) とする．
j

-

i
´
´
´
+́´

?

´
´
´

´ セル (i, j)

図 1: Cellular automata

Hi,j (t) = Si,j−1 (t) + Si,j+1 (t) + Si−1,j (t) + Si+1,j (t)(1)

時間に対するセルの状態遷移は式 (2) に従う．状態遷移関数 F を図 2 に示す．

Si,j (t + 1) = F (Si,j (t), Hi,j (t))

図 2: 状態遷移図

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

— 6 —

(2)

問 1 時刻 t において，cellular automata が図 3 に示す状態を取るとする．

a) Hi,j (t), Hi+2,j (t) と Hi,j−1 (t) の値を求めよ．
b) Si,j (t + 1) と Si+1,j (t + 1) の値を求めよ．

´+́´ セル (i, j)
´
´
´

図 3:

問 2 時刻 t = 0 において，cellular automata が以下の図 4 に示す状態をとる場合，t = 1 と t = 2 の cellular automata の状態を図示せよ．

図 4:

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

I 図に示す状態遷移図について次の問いに答えよ．（配点 50 点）
問 1 x に入力系列 0, 0, 1, 1, 1, 1, 0, 0, 0, 0 が与えられたときの出力系列 y を求めよ．
ただし，初期状態を S0 とする．
問 2 この状態遷移図を実現する同期式順序回路を D フリップフロップを用いて設計せよ．回路図も記すこと．

"!#
!
%!$

$!%
!$

$!%
!"

%!%

!#

$!$

%!%

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

I 次のようなオークションの関係データベースを考える．このとき，以下のすべての問いに答えよ．（配点 50 点）
参加（会員 ID，会員名，経験年数）
物件（物件 ID，物件名，出品者，出品日，予約価格）
競売（会員 ID，物件 ID，入札価格，入札日）
なお，列（カラム）の下線は，その列が主キーであることを示す．
問 1 表名：参加を定義すると下記のようになる．この定義例を参考に残りの二つの表を定義せよ．その際，各列の列名とデータ型，および整合性制約（キー制
約，外部キー制約など）も指定せよ．

CREATE TABLE 参加 (会員 id varchar(5)会員名 nchar

not null primary key,varying(20),

経験年数 integer);
問 2 クエリ「（まだ）入札されていない物件の ID と物件名を出力せよ」を差集合
演算：EXCEPT を使った SQL で示すと次のようになる．このクエリを NOT

EXISTS” 述語を使って示せ．なお，EXISTS 述語は，
「副問合せの導出表が，空集合であるかどうかを評価する」というものである．

SELECT 物件 ID, 物件名

FROM

物件

EXCEPT
SELECT
WHERE

物件 ID，物件名

DISTINCT

FROM

物件，競売

物件．物件 ID ＝競売．物件 ID

ORDER BY

物件 ID；

問 3 クエリ “SELECT * FROM 物件 NATURAL JOIN 競売;” の計算と結果について，100 字程度で説明せよ．その際，“自然結合”，“等結合”，“導出表” という熟語を使用せよ．また，表名，列名は具体的に記述せよ．

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

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

• ドアが開いているときに閉ボタンを押すとドアが閉まる• ドアが開いているときに 7 秒経過するとドアが閉まる• ドアが開いているときに開ボタンを押すとドアが開き続ける．
• ドアが閉じかけているときに開ボタンを押すとドアが開く．
• ドアが閉じているときに開ボタンを押すとドアが開く．
ただし，これら要件はエレベータがいずれかの階に停止している場合のみについて考えているものとする．
これらの要件に基づき，最初に，状態遷移を表現するステートチャート図 (ステー
トマシン図，状態図とも呼ばれる) を作成し，次に，エレベータ (かご) とドア，ボタンについてクラス図を作成してクラス設計を行うものとする．図 1 および図 2 は，それらの作成途中の図である．
以上の設計過程について以下の問いに答えよ．（配点 50 点）— 10 —

opening

closedopenedclosing

図 1: ステートチャート図

ElevatorCab

Door
(e)

currentposition
movedirection (g)
up
down
stop

(f)

state

(i)

(a)
(b)

OpenButtonlabel = “Open”(h)(k)
Button
(l)

label
(c)

(n)
(d)

CloseButtonlabel = “ Close ”
(j)

(m)

図 2: クラス図— 11 —

問 1 図 1 のステートチャート図を以下の手順で完成させよ．ただし，作成する図は，(1)∼(3) を通してひとつでよい．

(1) 要件を満たすには足りない遷移が二つある．それらを矢線として追加した完成版のステートチャート図を作成せよ．

(2) 遷移の中で，開ボタンまたは閉ボタンを押すというイベントにより遷移するものがある．それらを (1) で作成した図中に，open または close として追加せよ．

(3) 「7 秒経過すると」という条件を，現在の経過時間を表す変数を t として，「[条件] / アクション」という形式で図中に追加せよ．アクションは，条件が成立したときに行われる動作を意味する．また，この条件の追加が，閉ボタンを押したときにはただちにドアが閉まるという要件と矛盾しないよ
うに，「閉ボタンを押す」という条件と「7 秒経過すると」という条件を orでつなげて [ ] 内に記述すること．
問 2 図 2 のクラス図を完成させるために以下の問いに答えよ．

(1) 図 1 のステートチャート図と対応が取れるように，クラス表記の中の (a)∼(d)を記せ．ただし，(a)∼(d) は，それぞれ以下のような意味を持つものとするので，英語あるいはローマ字で適切な名前を付けること．

(a) および (b): ドアに対する操作(c): ボタンの状態(d): ボタンに対する操作(2) 図 2 のクラス図にはクラス間の関連の種類が示されていない． UML のクラス図では，集約 (aggregation) を「ひし形」，汎化 (generalization) を「三角形」で表わし，それぞれを関連を表わす線の端に描くことで表現する．
ひし形と三角形を描くべき場所をそれぞれ図中の (e)∼(n) ですべて示せ．

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

平成 20 年度

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

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

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

知

情

報

心

ペ ー ジ

問題数

選択方法

理

学

1

1問

イ

ン

2

1問

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

3

1問

４科目を選択し，解答

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

4〜 5

1問

してください．

メ ディア デ ザ イ ン 基 礎

6

2問

デ

ザ

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

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

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

認知心理学I スクリプトとは，認知科学事典（日本認知科学会,2004）によると，日常経験する典型的な場面をモデル化してそこに生ずる事象列を形式化した知識である．下に挙げるのはレストランのスクリプトの例である．
レストランに行く
料理を注文する料理が来たらそれを食べる
代金を払って出てくる
以下の問いに答えよ．（配点 50 点）

問 1 世界を旅慣れている人が持つレストランのスクリプトと，外国を旅行したことのない人が持つレストランのスクリプトにはどのような違いがあるのか，具体的な場面を想定して説明せよ．
問 2 旅慣れている人の例を使ってスクリプトが形成されるプロセスを説明せよ．

[参考文献]

日本認知科学会

編 (2004)

デジタル

認知科学事典

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

共立出版

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

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

I D.A. ノーマンが提示した「行為の７段階モデル」は，ユーザの「心理的世界」と人工物やシステムの「物理的世界」の循環における認知プロセスをあらわしている．
例えば「電車に乗るために，券売機を使って乗車券や特急券などを購入する」場面
は，以下の７段階に分けられる．

(1) 目標の設定：電車に乗ろうと考えている段階(2) 操作意図の形成：券売機で乗車券や特急券などを購入しようと考えている段階(3) 操作系列の形成：券売機に対する具体的な操作プランをたてる段階(4) 操作の実行：プランにもとづき実際に券売機を操作する段階(5) 結果の知覚：操作によって生じた券売機の変化を知覚する段階(6) 結果の解釈：券売機の状態を理解・解釈しようとする段階(7) 結果の評価：当初の目標や意図が達成されたかどうかを確認・評価する段階(4) から (7) の段階において起こりうる問題とその解決法を，以下に示した (3) の解答例を参考にしながら，それぞれ 80 文字以内で簡潔に記述せよ．（配点 50 点）
解答例(3) 操作系列の形成
問題： 券売機のデザインや仕様，操作手順が大幅に変更されたため，どう操作すればよいのかわからない．
解決法： おおまかな操作手順があらかじめわかるように，券売機の画面や券売機
近くに表示を出す．おおまかな操作手順がわからなくても使えるように，券売機の画面に操作ガイダンスを表示する．

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

I 指定された順序に従って，数値を値として持つ二分探索木を構成する手順があるものとする．二分探索木は，構成時のデータ中の数値の順により異なる形をとる．二分探索木の形はたとえば，１，２，３，４の順に数値を与えると，図１のようにな
り，３，１，２，４の順に数値を与えると，図２のような形になる．

1
2
3
4
図 1:

3
4

1
2

図 2:

以下の問いに答えよ．（配点 50 点）
問 1 節点をひとつも持たない初期状態から初めて，それぞれ以下の３つのデータを追加したときに，それぞれの入力が完了した段階で出来上がる二分探索木を図示せよ．

• データ１：１，３，５，８，２• データ２：６，４，９，２，１• データ３：７，５，１０，１，４，２問 2 問 1 の解となる二分探索木をコピーした上で，これらの三つの二分探索木に対して数値６を探索させる場合の探索経路の順序を書き加えよ．

— 4 —問 3 それぞれの二分探索木を幅優先探索（横型探索）でノードを辿るものとする．
問 1 の解となる三つの二分木に対し，辿られる順にノードの値を列挙せよ．ただし，同一レベルにあるノードは左から順に列挙するものとする．
問 4 それぞれの二分探索木を深さ優先探索（縦型探索）でノードを辿るものとす
る．問 1 の解となる三つの二分木に対し，辿られる順にノードの値を列挙せよ．
ただし，同一レベルにあるノードは左から順に列挙するものとする．

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

I ユーザビリティ評価法には定量的評価法と定性的評価法の２種類があるが，それぞれ１つずつ代表的な評価法をあげ，それらの違いを簡潔に説明せよ．(300 文字程度)（配点 20 点）

II メディアデザインに関する実験や調査を行った際，得られたデータが偶然に得られたものか，そのメディアの影響（要因）であるのか，ということを確かめる必要がある．少なくとも，このようなデータを扱って偶然ではないということを科学的に証明するには何らかの根拠が必要である．その根拠を示すために統計学の「検定」という手法が役立つ．
以下の用語のうち 少なくとも３つを 利用しながら，検定を必要とする具体例をあげ，検定の手順を説明せよ．（配点 30 点）[説明に用いる用語]
帰無仮設，対立仮説，独立性，χ2 ，ｐ値，有意水準，自由度，ｔ検定，確率，分散

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