平成 23 年度

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

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

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

ペ ー ジ

問題数

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

1

1問

線

学

2

2問

学

3

2問

形

解

代

数

析

情

報

数

学

4

2問

応

用

数

学

5

2問

デ ー タ ベ ー ス 工 学

6

1問

選択方法

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

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

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

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

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

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

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

I ２分探索木 (Binary Search Tree) について，以下の問いに答えよ．（配点 50 点）
問 1 次に示す整数データの並びを，左から順に入力することで生成される２分探索木を，図示せよ．ただし，２分探索木の各ノードでの大小関係は，左部分
木 < ノード < 右部分木 であるとし，整数データは丸で囲んで示すこと．

データ：

７，−５，−２，２，１５，−１，１０

問 2 問 1 で生成した２分探索木に，ある整数データが含まれているかどうかを探索する場合，最大何回の比較が必要かを，理由とともに答えよ．
問 3 ある７個の異なる整数データによって生成された２分探索木が，各ノードにおいて左部分木と右部分木に同じノード数を持つものとする．この２分探索木
を図示せよ．ただし図 1 の例の書き方に従い，ノードに数値等は記入せず，すべて○であらわすこと．

図 1 ２分探索木の図示の例
問 4 N 個の異なる整数データによって生成された２分探索木が，各ノードにおいて左部分木と右部分木に同じノード数を持つ場合に，ある整数データが含まれているかを探索する計算量（時間計算量）を示せ．
問 5 問 1 の２分探索木を「左優先の通りがけ順による深さ優先探索」で探索した結果を，左から順に列挙せよ．また，この探索方法で得られる数値列の特徴を答えよ．

アルゴリズムとデータ構造の問題は，このページで終りである．
— 1 —線形代数学I R2 から R3 への線形写像 f を，3 × 2 行列，




 1

A=
 1


1 

0



−1 

2



を用いて，f (x) = Ax (x ∈ R2 ) で与える．以下の問いに答えよ．（配点 25 点）

問 1 線形写像 f の核を求めよ．
問 2 線形写像 f の像の基底として，{t (1, 1, 0), t (1, −1, 2)} がとれることを示せ．
ただし，t は転置操作を表す．

II 2 次の正方実行列 A が (A − I)(A + I) = O を満たすとする．ここで O は零行列，Iは単位行列とする．このとき A をすべて求めよ．（配点 25 点）

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

解析学

I a1 = 2, an+1 =an 2
2an − 3(n = 1, 2, · · ·) を満たす数列 {an } について，以下の問いに答えよ．（配点 25 点）

問 1 bn = 1 −を示せ．

3とする．このとき，bn+1 = bn 2 (n = 1, 2, · · ·) が成り立つことan

問 2 2 以上の n に対して，an+1 < an が成り立つことを示せ．
問3

lim an を求めよ．

n→∞

)

(

π π
II 値域を − ,2 2とする逆正接関数 y = Tan−1 x について，以下の問いに答えよ．

（配点 25 点）

問1dx
を y だけの関数で表せ．
dy

問2

dy
を x だけの関数で表せ．
dx

問 3 広義積分∫ ∞0

Tan−1 xdx の値を求めよ．
1 + x2

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

I 集合 A = {a, b, c} において関係 R が次のように定義されている．
R = {(a, a), (a, c), (b, b), (b, c), (c, b), (c, c)}
以下の問いに答えよ．ただし，多重関係を許すとする．（配点 25 点）

問 1 R の関係行列および関係グラフを示せ．
問 2 R が反射律を満たすかどうか，理由とともに述べよ．
問 3 合成関係 R · R−1 の関係行列を示せ．ただし，R−1 は R の逆関係を表す．

II 以下の無向グラフ G1 , G2 について，以下の問いに答えよ．（配点 25 点）

問 1 G1 および G2 が平面グラフであるか否か，理由とともに述べよ．
問 2 問 1 において平面グラフとしたグラフについて，オイラーの定理が成り立つ
ことを確かめよ．
問 3 G1 および G2 がハミルトングラフであるか否か，理由とともに述べよ．

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

I 未知関数 y = y(x) に対する微分方程式

dy+ y = sin x の解で，初期条件 y(0) = 1
dx

を満たすものを求めよ．（配点 25 点）

II 区間 [−π, π] で定義された関数 f (x) = cos rx について，以下の問いに答えよ．ただし，r は整数ではない実数とする．（配点 25 点）
∫ π

問1

−π

f (x) cos kx dx を求めよ． ただし，k は整数とする．

問 2 f (x) を∞∑
1
f (x) =a0 +ak cos kx2
k=1とフーリエ余弦級数展開するとき， フーリエ係数 ak (k = 0, 1, 2, · · ·) を求めよ．
問 3 問 2 の結果を用いて，

π cot rπ =を示せ． ただし， cot x =

∞
∑
1
2r
+
2
2
r
k=1 r − k

1
である．
tan x

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

I 実体関連図と関係スキーマについて，以下の問いに答えよ．（配点 50 点）

問 1 以下の情報を含むデータベースの概念モデルを， 実体関連図で示せ．各実体集合間のＮ対Ｍ対応関係も明示せよ．
なお，このデータベースは携帯電話会社の問い合わせセンターの相談管理を表している．
実体集合に関する情報：（1） 携帯電話使用者に関する情報（お客様ＩＤ，氏名，住所，電話番号）（2） 相談報告書 (お客様ＩＤ，問題内容，発行日)（3） 専門社員に関する情報（社員番号，氏名，職務上の専門）（4） 調査報告書に関する情報（調査報告番号，発行日，調査結果，提案解
決法）
関連集合に関する情報：（1） 携帯電話使用者と相談報告書の間の，問い合わせに関する関連．ただし，一人の携帯電話使用者の一件の問い合わせに対し一つの相談報告書が対応する．
（2） 専門社員と相談報告書の間の，社員の任務担当に関する関連．ただし，ある専門社員は一つの相談報告書からのみ任務担当とされる．固有の属性として指示日をもつ．
（3） 相談報告書，専門社員，調査報告書の間の，調査に関する関連．ただし，一つの調査報告書を複数の専門社員が担当することもある．固有の属性として調査日をもつ．
問 2 その実体関連図から関係スキーマを書け．

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

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

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

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

工

知

能

ペ ー ジ

問題数

1〜 2

1問

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

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

3

1問

線

学

4

2問

学

5

2問

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

学

6

2問

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

形 式言語 と オ ー ト マトン

7

1問

ディジタル論理回路

8

1問

9 〜 10

1問

形

解
情

認

代

数

析
報

知

数

心

理

学

さい．

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

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

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

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

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

人 工 知 能

I 図 1 に示すミニ数独問題に関して以下の問いに答えよ．ただし，ミニ数独問題とは，
4 × 4 のマス目上に 1,2,3,4 の数字および空白が与えられた配置からスタートして，
空白に数字を埋めることによって，各行，各列，および左上，右上，左下，右下の2×2 の 4 マスのそれぞれがいずれも 1,2,3,4 の数字をひとつづつ持つように数字を配置する問題である．（配点 50 点）

1432
図 1 ミニ数独問題

N1

1

N2

N3

N4

N5

4

N6

3

N7

N8

N9

N10

N11

N12

2

図 2 制約充足のノード割り当て

問 1 図 1 のミニ数独問題を後戻り法で解いた時の探索木を書け．ただし，探索の順序は図 1 の上の行から下の行へ向けて，各行内では左から右に向けて進めることとし，深さ 3 までの探索木を示せ．
問 2 図 1 のミニ数独問題は，図 2 のように空白のマス目をノード N1 , . . . , N12 とする制約充足問題ととらえることができる．ノード Ni の候補値集合を Di とする．各ノードの値としては，まず 1 から 4 の数字のうち，同じ行，同じ列，同じ

4 マス内に既に与えられた数字とは異なる数字を候補とすることが出来る．この条件をノード制約とする．ノード制約を適用した後の D1 , D2 , D3 , D4 , D5 , D10をそれぞれ求めよ．

— 1 —問 3 図 1 のミニ数独問題を制約充足問題ととらえると，縦横方向に並んだ二つのノード間，および左上，右上，左下，右下の４マスそれぞれの同一マス内に含まれる二つのノード間には，互いの値が等しくないというアーク制約が想定される．制約ネットワークのアーク数はいくつになるか答えよ．
問 4 ノード N1 にアーク制約を適用した後の候補値集合 D1 を求めよ．
問 5 図 1 のミニ数独問題を制約充足アルゴリズムを用いて解け．アルゴリズムの概要と解を示すこと．

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

I ２分探索木 (Binary Search Tree) について，以下の問いに答えよ．（配点 50 点）
問 1 次に示す整数データの並びを，左から順に入力することで生成される２分探索木を，図示せよ．ただし，２分探索木の各ノードでの大小関係は，左部分
木 < ノード < 右部分木 であるとし，整数データは丸で囲んで示すこと．

データ：

７，−５，−２，２，１５，−１，１０

問 2 問 1 で生成した２分探索木に，ある整数データが含まれているかどうかを探索する場合，最大何回の比較が必要かを，理由とともに答えよ．
問 3 ある７個の異なる整数データによって生成された２分探索木が，各ノードにおいて左部分木と右部分木に同じノード数を持つものとする．この２分探索木
を図示せよ．ただし図 1 の例の書き方に従い，ノードに数値等は記入せず，すべて○であらわすこと．

図 1 ２分探索木の図示の例
問 4 N 個の異なる整数データによって生成された２分探索木が，各ノードにおいて左部分木と右部分木に同じノード数を持つ場合に，ある整数データが含まれているかを探索する計算量（時間計算量）を示せ．
問 5 問 1 の２分探索木を「左優先の通りがけ順による深さ優先探索」で探索した結果を，左から順に列挙せよ．また，この探索方法で得られる数値列の特徴を答えよ．

アルゴリズムとデータ構造の問題は，このページで終りである．
— 3 —線形代数学I R2 から R3 への線形写像 f を，3 × 2 行列，




 1

A=
 1


1 

0



−1 

2



を用いて，f (x) = Ax (x ∈ R2 ) で与える．以下の問いに答えよ．（配点 25 点）

問 1 線形写像 f の核を求めよ．
問 2 線形写像 f の像の基底として，{t (1, 1, 0), t (1, −1, 2)} がとれることを示せ．
ただし，t は転置操作を表す．

II 2 次の正方実行列 A が (A − I)(A + I) = O を満たすとする．ここで O は零行列，Iは単位行列とする．このとき A をすべて求めよ．（配点 25 点）

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

解析学

I a1 = 2, an+1 =an 2
2an − 3(n = 1, 2, · · ·) を満たす数列 {an } について，以下の問いに答えよ．（配点 25 点）

問 1 bn = 1 −を示せ．

3とする．このとき，bn+1 = bn 2 (n = 1, 2, · · ·) が成り立つことan

問 2 2 以上の n に対して，an+1 < an が成り立つことを示せ．
問3

lim an を求めよ．

n→∞

)

(

π π
II 値域を − ,2 2とする逆正接関数 y = Tan−1 x について，以下の問いに答えよ．

（配点 25 点）

問1dx
を y だけの関数で表せ．
dy

問2

dy
を x だけの関数で表せ．
dx

問 3 広義積分∫ ∞0

Tan−1 xdx の値を求めよ．
1 + x2

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

I 集合 A = {a, b, c} において関係 R が次のように定義されている．
R = {(a, a), (a, c), (b, b), (b, c), (c, b), (c, c)}
以下の問いに答えよ．ただし，多重関係を許すとする．（配点 25 点）

問 1 R の関係行列および関係グラフを示せ．
問 2 R が反射律を満たすかどうか，理由とともに述べよ．
問 3 合成関係 R · R−1 の関係行列を示せ．ただし，R−1 は R の逆関係を表す．

II 以下の無向グラフ G1 , G2 について，以下の問いに答えよ．（配点 25 点）

問 1 G1 および G2 が平面グラフであるか否か，理由とともに述べよ．
問 2 問 1 において平面グラフとしたグラフについて，オイラーの定理が成り立つ
ことを確かめよ．
問 3 G1 および G2 がハミルトングラフであるか否か，理由とともに述べよ．

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

I アルファベットを Σ = {0, 1} とする．このとき以下の問いに答えよ．(配点 50 点)
問 1 次の状態遷移図 (図 1) に対応する，空動作のある非決定性有限オートマトン(ε-nFA) を A とする．この ε-nFA A が受理する言語を表す正規表現を示せ．

0

ε

Q

P

ε

R

1
図 1 ε-nFA A の状態遷移図

問 2 次の正規表現が表す言語を受理する ε-nFA を示せ．

((1∗ 01∗ 0)∗ 1∗ ) + ((0∗ 10∗ 1)∗ 0∗ )問 3 問 1 の ε-nFA A に等価な決定性有限オートマトンを求めよ．

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

I 2 つの入力を持った 2 ビットのアップカウンタを設計する．このカウンタのクロッ
クが 0 から 1 に変化するときの動作を以下に示す．
（1） 入力 A が 0，入力 B が 0 の時は，カウンタの値を 0 にリセットする（2 ビット
とも 0 にする）．
（2） 入力 A が 0，入力 B が 1 の時は，バイナリコードカウンタ (表 1) として動作する．
（3） 入力 A が 1，入力 B が 0 の時は，グレイコードカウンタ (表 2) として動作する．
（4） 入力 A が 1，入力 B が 1 の時は，直前の値を保持する．
このとき，以下の問いに答えよ．（配点 50 点）

問 1 現在のカウンタの値を Q0 , Q1 ，次に取り得るカウンタの値を T0 ，T1 とする
とき，このカウンタの真理値表を求めなさい．ただし，Q0 , T0 が下位の桁を表すものとする．
問 2 状態遷移図を作図せよ．
問 3 D フリップフロップを用いてカウンタを実現するとき，下位桁の D フリップ
フロップの入力 D0 に関する論理式を答えなさい．
問 4 D フリップフロップを用いてカウンタを実現するとき，上位桁の D フリップ
フロップの入力 D1 に関する論理式を答えなさい．
表 1 バイナリコード

10 進数

表 2 グレイコード

2 進数

10 進数

上位桁

下位桁

0

0

0

1

0

2
3

2 進数
上位桁

下位桁

0

0

0

1

1

0

1

1

0

2

1

1

1

1

3

1

0

ディジタル論理回路の問題は，このページで終りである．
— 8 —認知心理学I 次の (A)，(B) は，4 枚カード問題と呼ばれるものの二つのバージョンである．これについて，以下の問いに答えよ．（配点 50 点）(A) の 4 枚カード問題
図 1 に示す 4 枚のカードには，全て片面に数が，もう一方の面にはローマ字が書いてある．
「もし，カードの片面にローマ字の母音が書いてあれば，裏面の数字は偶数である」というルールが成立しているかどうかを調べるためには，
最小限，どのカードをめくってみればよいでしょうか？

E

K

4

7

図 1 片面が数，もう一方の面にはローマ字が書かれたカード(B) の 4 枚カード問題
図 2 に示す 4 枚のカードには，4 人の人物の情報が書いてある．カードの片面にはその人物の年齢．もう一方の面にはその人が飲んでいるものが書いてある．
「もし飲んでいるものがビールならば，その人は 20 歳以上でなければならない」というルールが成立しているかどうかを調べるためには，最小限，どのカードをめくってみればよいでしょうか？

図 2 片面が人物の年齢，もう一方の面にはその人が飲んでいるものが書かれ
たカード

— 9 —

問 1 (A) と (B) の 4 枚カード問題は，論理的には同じ問題構造を持っている．そのことを示すために，(A) と (B) では何と何が対応しているのか，それぞれの対応する部分をすべて答えよ．
問 2 一般の大学生が (A) と (B) の問題を答えた場合，それぞれの問題の正答率がかなり違っていることが示されている．心理学的な研究において，その違いの原因となる理由がいくつか提出されている．今までに提出されている正答率の違いの原因についての説明はどのようなものか答えよ．ただし，解答には最低二つの説明を挙げること．

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

平成 23 年度

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

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

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

ペ ー ジ

問題数

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

1

1問

線

学

2

2問

学

3

2問

学

4

2問

形 式言語 と オートマトン

5

1問

ソフトウェア設計論

6〜 8

2問

ディジタル論理回路

9

1問

デ ー タ ベ ー ス 工 学

10

1問

形

解
情

代

数

析
報

数

選択方法

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

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

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

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

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

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

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

I ２分探索木 (Binary Search Tree) について，以下の問いに答えよ．（配点 50 点）
問 1 次に示す整数データの並びを，左から順に入力することで生成される２分探索木を，図示せよ．ただし，２分探索木の各ノードでの大小関係は，左部分
木 < ノード < 右部分木 であるとし，整数データは丸で囲んで示すこと．

データ：

７，−５，−２，２，１５，−１，１０

問 2 問 1 で生成した２分探索木に，ある整数データが含まれているかどうかを探索する場合，最大何回の比較が必要かを，理由とともに答えよ．
問 3 ある７個の異なる整数データによって生成された２分探索木が，各ノードにおいて左部分木と右部分木に同じノード数を持つものとする．この２分探索木
を図示せよ．ただし図 1 の例の書き方に従い，ノードに数値等は記入せず，すべて○であらわすこと．

図 1 ２分探索木の図示の例
問 4 N 個の異なる整数データによって生成された２分探索木が，各ノードにおいて左部分木と右部分木に同じノード数を持つ場合に，ある整数データが含まれているかを探索する計算量（時間計算量）を示せ．
問 5 問 1 の２分探索木を「左優先の通りがけ順による深さ優先探索」で探索した結果を，左から順に列挙せよ．また，この探索方法で得られる数値列の特徴を答えよ．

アルゴリズムとデータ構造の問題は，このページで終りである．
— 1 —線形代数学I R2 から R3 への線形写像 f を，3 × 2 行列，




 1

A=
 1


1 

0



−1 

2



を用いて，f (x) = Ax (x ∈ R2 ) で与える．以下の問いに答えよ．（配点 25 点）

問 1 線形写像 f の核を求めよ．
問 2 線形写像 f の像の基底として，{t (1, 1, 0), t (1, −1, 2)} がとれることを示せ．
ただし，t は転置操作を表す．

II 2 次の正方実行列 A が (A − I)(A + I) = O を満たすとする．ここで O は零行列，Iは単位行列とする．このとき A をすべて求めよ．（配点 25 点）

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

解析学

I a1 = 2, an+1 =an 2
2an − 3(n = 1, 2, · · ·) を満たす数列 {an } について，以下の問いに答えよ．（配点 25 点）

問 1 bn = 1 −を示せ．

3とする．このとき，bn+1 = bn 2 (n = 1, 2, · · ·) が成り立つことan

問 2 2 以上の n に対して，an+1 < an が成り立つことを示せ．
問3

lim an を求めよ．

n→∞

)

(

π π
II 値域を − ,2 2とする逆正接関数 y = Tan−1 x について，以下の問いに答えよ．

（配点 25 点）

問1dx
を y だけの関数で表せ．
dy

問2

dy
を x だけの関数で表せ．
dx

問 3 広義積分∫ ∞0

Tan−1 xdx の値を求めよ．
1 + x2

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

I 集合 A = {a, b, c} において関係 R が次のように定義されている．
R = {(a, a), (a, c), (b, b), (b, c), (c, b), (c, c)}
以下の問いに答えよ．ただし，多重関係を許すとする．（配点 25 点）

問 1 R の関係行列および関係グラフを示せ．
問 2 R が反射律を満たすかどうか，理由とともに述べよ．
問 3 合成関係 R · R−1 の関係行列を示せ．ただし，R−1 は R の逆関係を表す．

II 以下の無向グラフ G1 , G2 について，以下の問いに答えよ．（配点 25 点）

問 1 G1 および G2 が平面グラフであるか否か，理由とともに述べよ．
問 2 問 1 において平面グラフとしたグラフについて，オイラーの定理が成り立つ
ことを確かめよ．
問 3 G1 および G2 がハミルトングラフであるか否か，理由とともに述べよ．

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

I アルファベットを Σ = {0, 1} とする．このとき以下の問いに答えよ．(配点 50 点)
問 1 次の状態遷移図 (図 1) に対応する，空動作のある非決定性有限オートマトン(ε-nFA) を A とする．この ε-nFA A が受理する言語を表す正規表現を示せ．

0

ε

Q

P

ε

R

1
図 1 ε-nFA A の状態遷移図

問 2 次の正規表現が表す言語を受理する ε-nFA を示せ．

((1∗ 01∗ 0)∗ 1∗ ) + ((0∗ 10∗ 1)∗ 0∗ )問 3 問 1 の ε-nFA A に等価な決定性有限オートマトンを求めよ．

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

I ソフトウェアに求められる要求は，機能要求と非機能要求に大別できる．機能要求は文字通り「機能」に対する要求であり，例えばユースケース記述や UML のユー
スケース図によって仕様が記述される．一方，非機能要求は，性能やセキュリティなど，定型的な記述が困難であり，文章の形で仕様が記述されるのが一般的である．
いま，商品点数が 500 点で 1 日に 1 万人規模のアクセスがあるショッピング Web サ
イトのサーバ側ソフトウェア (Web アプリケーション) の設計を考えるとして，以下の問いに答えよ．（配点 30 点）

問 1 この Web アプリケーションに求められる機能要求のうち，必要不可欠なものを 3 項目挙げよ．
問 2 上の問いで挙げた機能要求の一つについて，下記の例を参考にしてユース
ケース記述を作成せよ．なお，ユースケース記述は，(1) ユースケース名，(2)概要，(3) アクター，(4) 基本系列 (フロー) から構成されるものとし，各々を簡潔に記述すること．
例:（1） ショッピングカート内容の確認（2） ショッピングカートに入っている商品の種類と個数を確認する（3） 顧客（4） 1. アクターは，システムにショッピングカート内容の表示を要求する

2. システムは，ショッピングカートに入っているすべての商品の商品名と個数のリストを表示する

3. アクターは，内容を確認し，確認が完了したことをシステムに通知する
4. システムは，ショッピングカート内容の表示を終了し，直前に表示されていたページを表示する— 6 —II 図 1 は，ある大学の履修登録システムのクラスおよびクラス間の関係を，UML のクラス図の記法によって記述したものである．次の条件にしたがって以下の問いに答えよ．（配点 20 点）

条件 1 この大学の授業科目には教養科目と専門科目の 2 種類があり，教養科目は学生の所属コースに無関係であるが，専門科目は所属コースに応じて履修可否が異なる．
条件 2 どの授業科目も一人以上の教員が担当教員となるが，授業科目を一つも担当しない教員もいる．

問 1 図 1 中の

A

から

F

のそれぞれの空欄に入る語句として，最も適切なものを次の (a) から (h) の選択肢の中から一つ選び，記号で答えよ．
選択肢(a) 教養科目(b) 専門科目(c) 所属コース(d) 取得済単位数(e) 氏名(f) 科目名(g) 大学名(h) 授業を担当しない教員

問 2 図 1 中の

ア

，

イ

のそれぞれの空欄に入る多重度として，最も適切なものを次の (a) から (d) の選択肢の中から一つ選び，記号で答えよ．
選択肢(a) 0..1(b) 1(c) 1..*
(d) *

— 7 —

図 1 履修登録システムのクラス図

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

I 2 つの入力を持った 2 ビットのアップカウンタを設計する．このカウンタのクロッ
クが 0 から 1 に変化するときの動作を以下に示す．
（1） 入力 A が 0，入力 B が 0 の時は，カウンタの値を 0 にリセットする（2 ビット
とも 0 にする）．
（2） 入力 A が 0，入力 B が 1 の時は，バイナリコードカウンタ (表 1) として動作する．
（3） 入力 A が 1，入力 B が 0 の時は，グレイコードカウンタ (表 2) として動作する．
（4） 入力 A が 1，入力 B が 1 の時は，直前の値を保持する．
このとき，以下の問いに答えよ．（配点 50 点）

問 1 現在のカウンタの値を Q0 , Q1 ，次に取り得るカウンタの値を T0 ，T1 とする
とき，このカウンタの真理値表を求めなさい．ただし，Q0 , T0 が下位の桁を表すものとする．
問 2 状態遷移図を作図せよ．
問 3 D フリップフロップを用いてカウンタを実現するとき，下位桁の D フリップ
フロップの入力 D0 に関する論理式を答えなさい．
問 4 D フリップフロップを用いてカウンタを実現するとき，上位桁の D フリップ
フロップの入力 D1 に関する論理式を答えなさい．
表 1 バイナリコード

10 進数

表 2 グレイコード

2 進数

10 進数

上位桁

下位桁

0

0

0

1

0

2
3

2 進数
上位桁

下位桁

0

0

0

1

1

0

1

1

0

2

1

1

1

1

3

1

0

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

I 実体関連図と関係スキーマについて，以下の問いに答えよ．（配点 50 点）

問 1 以下の情報を含むデータベースの概念モデルを， 実体関連図で示せ．各実体集合間のＮ対Ｍ対応関係も明示せよ．
なお，このデータベースは携帯電話会社の問い合わせセンターの相談管理を表している．
実体集合に関する情報：（1） 携帯電話使用者に関する情報（お客様ＩＤ，氏名，住所，電話番号）（2） 相談報告書 (お客様ＩＤ，問題内容，発行日)（3） 専門社員に関する情報（社員番号，氏名，職務上の専門）（4） 調査報告書に関する情報（調査報告番号，発行日，調査結果，提案解
決法）
関連集合に関する情報：（1） 携帯電話使用者と相談報告書の間の，問い合わせに関する関連．ただし，一人の携帯電話使用者の一件の問い合わせに対し一つの相談報告書が対応する．
（2） 専門社員と相談報告書の間の，社員の任務担当に関する関連．ただし，ある専門社員は一つの相談報告書からのみ任務担当とされる．固有の属性として指示日をもつ．
（3） 相談報告書，専門社員，調査報告書の間の，調査に関する関連．ただし，一つの調査報告書を複数の専門社員が担当することもある．固有の属性として調査日をもつ．
問 2 その実体関連図から関係スキーマを書け．

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

平成 23 年度

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

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

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

ペ ー ジ

問題数

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

1

1問

情

報

認

知

デ

ザ

選択方法

イ

ン

2

1問

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

理

学

3〜 4

1問

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

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

5

1問

さい．

メディアデザイン基礎

6〜 8

1問

心

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

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

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

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

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

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

I ２分探索木 (Binary Search Tree) について，以下の問いに答えよ．（配点 50 点）
問 1 次に示す整数データの並びを，左から順に入力することで生成される２分探索木を，図示せよ．ただし，２分探索木の各ノードでの大小関係は，左部分
木 < ノード < 右部分木 であるとし，整数データは丸で囲んで示すこと．

データ：

７，−５，−２，２，１５，−１，１０

問 2 問 1 で生成した２分探索木に，ある整数データが含まれているかどうかを探索する場合，最大何回の比較が必要かを，理由とともに答えよ．
問 3 ある７個の異なる整数データによって生成された２分探索木が，各ノードにおいて左部分木と右部分木に同じノード数を持つものとする．この２分探索木
を図示せよ．ただし図 1 の例の書き方に従い，ノードに数値等は記入せず，すべて○であらわすこと．

図 1 ２分探索木の図示の例
問 4 N 個の異なる整数データによって生成された２分探索木が，各ノードにおいて左部分木と右部分木に同じノード数を持つ場合に，ある整数データが含まれているかを探索する計算量（時間計算量）を示せ．
問 5 問 1 の２分探索木を「左優先の通りがけ順による深さ優先探索」で探索した結果を，左から順に列挙せよ．また，この探索方法で得られる数値列の特徴を答えよ．

アルゴリズムとデータ構造の問題は，このページで終りである．
— 1 —情報デザインI 表１に示す函館管内主要品地域別輸出表のデータを基に，函館管内から輸出した品
目・地域・輸出額を解答用紙に分かりやすいダイアグラム (図解) で表現せよ．さらに，ダイアグラムの作成意図と解説を簡潔に述べよ．（配点 50 点）

表 1 函館管内主要品地域別輸出表
HH
HH
HH

HH
HH
HH 地域
アジア
HH
品目
HH

輸出額（単位：百万円）

オーストラリア

北米

中南米

ヨーロッパ

ロシア

魚介類

1,925

18

3

0

51

20

紙

類

1,451

17

193

0

125

0

機械類

9,739

2

3,955

3,595

4,977

896

自動車

42

0

0

0

0

340

船

9

0

0

3,576

0

61

舶

情報デザインの問題は，このページで終りである．
— 2 —認知心理学I 次の (A)，(B) は，4 枚カード問題と呼ばれるものの二つのバージョンである．これについて，以下の問いに答えよ．（配点 50 点）(A) の 4 枚カード問題
図 1 に示す 4 枚のカードには，全て片面に数が，もう一方の面にはローマ字が書いてある．
「もし，カードの片面にローマ字の母音が書いてあれば，裏面の数字は偶数である」というルールが成立しているかどうかを調べるためには，
最小限，どのカードをめくってみればよいでしょうか？

E

K

4

7

図 1 片面が数，もう一方の面にはローマ字が書かれたカード(B) の 4 枚カード問題
図 2 に示す 4 枚のカードには，4 人の人物の情報が書いてある．カードの片面にはその人物の年齢．もう一方の面にはその人が飲んでいるものが書いてある．
「もし飲んでいるものがビールならば，その人は 20 歳以上でなければならない」というルールが成立しているかどうかを調べるためには，最小限，どのカードをめくってみればよいでしょうか？

図 2 片面が人物の年齢，もう一方の面にはその人が飲んでいるものが書かれ
たカード

— 3 —

問 1 (A) と (B) の 4 枚カード問題は，論理的には同じ問題構造を持っている．そのことを示すために，(A) と (B) では何と何が対応しているのか，それぞれの対応する部分をすべて答えよ．
問 2 一般の大学生が (A) と (B) の問題を答えた場合，それぞれの問題の正答率がかなり違っていることが示されている．心理学的な研究において，その違いの原因となる理由がいくつか提出されている．今までに提出されている正答率の違いの原因についての説明はどのようなものか答えよ．ただし，解答には最低二つの説明を挙げること．

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

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

問 1 メンタルモデルについて，150 文字以内で説明せよ．
問 2 ユーザがメンタルモデルをうまく形成できない原因として考えられる，イン
タフェースの問題点をすべて挙げよ．

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

I 近年，外国人観光客が増加している．全国の自治体でも観光客を通じた地域振興を目指して，外国人観光客に注力する所が増えており，外国人観光客を巡る地域間競争は激しさを増している．また，観光客増加による急激な変化によって観光客にも受け入れ側にも色々な課題が発生している．従って，各観光地が今後の更なる観光の活性化を図るには，より工夫を凝らした外国人観光客の集客努力と受け入れ体制の整備を続けることが必要である．
資料１は函館の外国人宿泊数の推移に関するもの，資料２は外国人観光客に提供されているコンテンツの現状を抜粋したものである．これらの資料に基づいて現状の分析を行い，人間中心設計の手法に従って，外国人観光客に適したコンテンツ
サービスを提案せよ．（配点 50 点）

問 1 自分が着目した問題を示し，ユーザの視点からのその問題の分析結果を述べよ．
問 2 提案する外国人観光客に適したコンテンツサービスを利用するユーザ像を述べよ．
問 3 提案する外国人観光客に適したコンテンツサービスの概要を，文章，図，ス
ケッチを使って説明せよ．

— 6 —

資料 1
「函館空港国際線乗降客数」と「道南地方における外国人宿泊客数」の推移を比較すると，空港乗降客数がこのところ大幅に増加しているのに対して，外国人宿泊客数は小幅の増加に止まっている．これは管内に宿泊しない外国人観光客の割合が高まり，外国人観光客の間で函館が「通過型観光地」になりつつある可能性を示唆している（図１）．

著作権保護のため図１（（出典）函館空港ビルディング）は省略してあります

— 7 —

資料 2

訪日外国人の観光コンテンツに対する意識

著作権保護のため資料（平成１６年度国土施策創発調査「全国で提供されている観光コンテンツの現状と課題に関する調査報告書」，国土交通省近畿運輸局・京都府，平成１７年.

は省略してあります

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