平成 24 年度

大学院博士 (前期) 課程入学者選抜学力試験
二次募集

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

1．試験開始の合図があるまで，この問題冊子を開かないでください．
2．指示があるまで，解答冊子は開かないでください．解答冊子は領域ごとに用意されています．必ず，受験しようとする領域の解答冊子に解答してください．

3．各領域の出題科目およびページは，下表のとおりです．領域ごとに下表で指示する 3 科目すべてを解答し，解答した解答冊子を提出してください．
領域

出 題 科 目

ペ ー ジ

問題数

析 CS

1

1問

学 CS

2

1問

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

3〜 4

1問

能 II

5

1問

学 II

6

1問

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

7〜 8

1問

形式 言語 とオ ー ト マ ト ン MA

91問

線学 MA

101問

ディジ タ ル 論 理 回 路 MA

11 〜 12

1問

ン MD

13

1問

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

14

1問

メ ディア デ ザ イ ン 基 礎 MD

15 〜 16

1問

基複雑系情報科学領域

線

礎形

人
知能情報科学領域

情報アーキテクチャ領域

メディアデザイン領域

代

工線

情解

形

報

知代

形

代

デ数

数

数

ザイ

4．解答冊子の表紙と各解答用紙の所定欄に，受験番号と氏名をはっきりと記入してください．

5．解答用紙の解答欄内に，問いの番号（問 1 など）を記入してから解答を始めてください．

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

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

基 礎 解 析 CS

I 以下の問いに答えよ．(配点 50 点)
d2 xdx+3+ 2x = 0 において，初期条件 x(0) = 0，2dtdtdx(0) = 1 をみたす解 x(t) を求めよ．
dt

問 1 2 階常微分方程式

問 2 t > 0 において微分可能，かつ t ≥ 0 で有界な関数 f (t) のラプラス変換を，L[f ](s) =∫ ∞f (t)e−st dt0で与える．ただし，s は広義積分が収束するような範囲で考える．問 1 で求めた x(t) のラプラス変換 L[x](s) を求めよ．

基礎解析 CS の問題は，このページで終りである．
— 1 —線 形 代 数 学 CS


I 行列 A = 0 −110 について，以下の問いに答えよ．（配点 50 点）

問 1 A のすべての固有値と，それらに対する固有ベクトルを求めよ．
問 2 n を自然数とするとき，An の一般項を求めよ．ただし，A1 = A とする．

線形代数学 CS の問題は，このページで終りである．
— 2 —アルゴリズムとデータ構造 CS

I 整列アルゴリズムには様々なものが提案されている．代表的なものにバブルソートとマージソートがある．バブルソート，マージソートに関する次の文章を読み，以下の問いに答えよ．（配点 50 点）

バブルソートによる昇順整列のアルゴリズム（i） データ列の末尾から順に調べていき，もし，隣り合う二つの要素の前の要素が後の要素より大きければ，それらを入れ換える.
（ii） 一度も入れ換えを行うことなく先頭まで調べ終わったら，ソートを終了する．
そうでないなら，再び末尾に戻って（i）を繰り返す．

マージソートによる昇順整列アルゴリズム
マージソートするデータ列の長さは 2 のべき乗であるとする．
（i） データ列を同じ長さの二つの部分列 a,b に分割する．
（ii） 部分列 a,b をそれぞれマージソートする．
（iii） 整列済みになった部分列 a,b をマージする．
（ii）で部分列を整列する際に，(i)〜(iii) の手順を再帰的に適用する．再帰的に適用し，部分列の要素数が 1 になるまで分割した後，マージを行う．

昇順にマージするアルゴリズム
二つの昇順に整列されたデータ列を a,b とし，初期状態は要素が空であるデータ列を c とする．
（i） データ列 a とデータ列 b の先頭の要素を比較して，そのうち小さい要素を列から取り除いてデータ列 c の末尾に追加する．
（ii） （i）をデータ列 a かデータ列 b のどちらか一方の要素がなくなるまで繰り返す．
（iii） 最後に，残された要素をすべて同じ順でデータ列 c の末尾に追加する．

— 3 —問 1 バブルソートのアルゴリズムに従い，次のデータ列を昇順に整列する過程を入れ換え操作が分かるように示せ．ただし，操作例のように入れ換え前のデー
タ列の入れ換える二つの要素に下線を引き，入れ換え箇所を明記すること．
データ列：（5 8 1 6 7 3 2 4）
操作例：
（1 4 3 2） ⇒ （1 4 2 3）
問 2 マージのアルゴリズムに従い，次の二つの昇順整列済みデータ列（a,b）を昇順整列済みの一つのデータ列（c）にまとめる過程を示せ．ただし，それぞれの過程でデータ列のどのデータに注目しているのか分かるように，操作例にならって示せ．また，解答は a,b,c の初期状態である () ←（1 5 6 8）
（2 3 4 7）から始めること．
データ列 a：（1 5 6 8）
データ列 b：（2 3 4 7）
操作例：() ← (14) (23) ⇒ (1) ← (4)(23)
問 3 マージソートのアルゴリズムに従い，次のデータ列を整列する過程を示せ．
ただし，操作例にならって各操作が分割なのか，マージなのかを示すこと．
データ列：（5 8 1 6 7 3 2 4）
操作例：分割 (8 1) ⇒ マージ (8)(1) ⇒ (1 8)

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

I 図 1 に示す大陸は六つの州からなるものとする．この地図を「隣接している州は違う色で塗る」という条件のもとで，赤, 青, 緑の三色で塗り分けることを考える．以下の問いに答えよ．（配点 50 点）
州 ={WA, NT, SA, Q, NSW, V}
色 ={ 赤, 青, 緑 }

NT

Q

SANSW
V

WA

図 1 大陸地図

問 1 この問題を制約充足問題としてとらえたときの制約を定式化せよ．
問 2 制約充足問題として解け．解く過程も記すこと．なお，解が複数存在する場合はそのうちの一つを示せばよい．

人工知能 II の問題は，このページで終りである．
— 5 —線 形 代 数 学 II
I 行列 A = 0 −110 について，以下の問いに答えよ．（配点 50 点）

問 1 A のすべての固有値と，それらに対する固有ベクトルを求めよ．
問 2 n を自然数とするとき，An の一般項を求めよ．ただし，A1 = A とする．

線形代数学 II の問題は，このページで終りである．
— 6 —アルゴリズムとデータ構造 II

I 整列アルゴリズムには様々なものが提案されている．代表的なものにバブルソートとマージソートがある．バブルソート，マージソートに関する次の文章を読み，以下の問いに答えよ．（配点 50 点）

バブルソートによる昇順整列のアルゴリズム（i） データ列の末尾から順に調べていき，もし，隣り合う二つの要素の前の要素が後の要素より大きければ，それらを入れ換える.
（ii） 一度も入れ換えを行うことなく先頭まで調べ終わったら，ソートを終了する．
そうでないなら，再び末尾に戻って（i）を繰り返す．

マージソートによる昇順整列アルゴリズム
マージソートするデータ列の長さは 2 のべき乗であるとする．
（i） データ列を同じ長さの二つの部分列 a,b に分割する．
（ii） 部分列 a,b をそれぞれマージソートする．
（iii） 整列済みになった部分列 a,b をマージする．
（ii）で部分列を整列する際に，(i)〜(iii) の手順を再帰的に適用する．再帰的に適用し，部分列の要素数が 1 になるまで分割した後，マージを行う．

昇順にマージするアルゴリズム
二つの昇順に整列されたデータ列を a,b とし，初期状態は要素が空であるデータ列を c とする．
（i） データ列 a とデータ列 b の先頭の要素を比較して，そのうち小さい要素を列から取り除いてデータ列 c の末尾に追加する．
（ii） （i）をデータ列 a かデータ列 b のどちらか一方の要素がなくなるまで繰り返す．
（iii） 最後に，残された要素をすべて同じ順でデータ列 c の末尾に追加する．

— 7 —

問 1 バブルソートのアルゴリズムに従い，次のデータ列を昇順に整列する過程を入れ換え操作が分かるように示せ．ただし，操作例のように入れ換え前のデータ列の入れ換える二つの要素に下線を引き，入れ換え箇所を明記すること．
データ列：（5 8 1 6 7 3 2 4）
操作例：
（1 4 3 2） ⇒ （1 4 2 3）
問 2 マージのアルゴリズムに従い，次の二つの昇順整列済みデータ列（a,b）を昇順整列済みの一つのデータ列（c）にまとめる過程を示せ．ただし，それぞれの過程でデータ列のどのデータに注目しているのか分かるように，操作例にならって示せ．また，解答は a,b,c の初期状態である () ←（1 5 6 8）
（2 3 4 7）から始めること．
データ列 a：（1 5 6 8）
データ列 b：（2 3 4 7）
操作例：() ← (14) (23) ⇒ (1) ← (4)(23)
問 3 マージソートのアルゴリズムに従い，次のデータ列を整列する過程を示せ．
ただし，操作例にならって各操作が分割なのか，マージなのかを示すこと．
データ列：（5 8 1 6 7 3 2 4）
操作例：分割 (8 1) ⇒ マージ (8)(1) ⇒ (1 8)

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

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

問 1 オートマトン A で受理される語，受理されない語を二つずつあげよ．
問 2 オートマトン A が受理する言語を表す正規表現を示せ．
問 3 オートマトン A と等価な決定性有限オートマトンを求めよ．

㻜㻘㻝q0

㻝

q1

㻜㻘㻝

q2

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

形式言語とオートマトン MA の問題は，このページで終りである．
— 9 —線 形 代 数 学 MA
I 行列 A = 0 −110 について，以下の問いに答えよ．（配点 50 点）

問 1 A のすべての固有値と，それらに対する固有ベクトルを求めよ．
問 2 n を自然数とするとき，An の一般項を求めよ．ただし，A1 = A とする．

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

ディジタル論理回路 MA

I 図 1 のような自動車だけが通る変則交差点がある．この交差点には R（赤：止まれ）と G（青：進め）のみからなる信号が四か所に設置されており，進行方向 1A と進
行方向 1B には常に同じ色の信号を表示する信号 1A と 1B が設置されている（以下まとめて信号 1 とよぶ）．また進行方向 2 と進行方向 3 にはそれぞれ信号 2 と信号3 が設置されている．この交差点を以下のルールにしたがって交通整理する信号機制御システムをつくりたい．同期式順序回路を使ってこのシステムを設計するもの
として，以下の問いに答えよ．（配点 50 点）㐍⾜᪉ྥ3
ಙྕ1AR G㐍⾜᪉ྥ1ARG

ಙྕ2RG

R Gಙྕ3㐍⾜᪉ྥ1B

ಙྕ1B
㐍⾜᪉ྥ2

図 1 変則交差点ルール（1） すべての信号は 1 クロック単位で状態を変更するものとし，1 クロック内では状態の変更を行わない．
（2） すべての信号は G あるいは R のどちらか一方の状態をとる．
（3） 信号 1，信号 2，および信号 3 の三つの信号のうち，ひとつだけを G にし，他は R にする．
（4） 初期状態では信号 1 を G とする．

— 11 —

（5） 入力 Reset が 1 のとき，つぎのクロック時には信号 1 を G にする．Reset が 0のときは，以下の 6, 7, 8 のルールに従う．
（6） 信号 1 が G の状態であるとき，次のクロック時には信号 2 を G にする．
（7） 信号 2 が G の状態であるとき，次のクロック時には信号 3 を G にする．
（8） 信号 3 が G の状態であるとき，次のクロック時には信号 1 を G にする．

問 1 この信号機制御システムの状態遷移図を作成せよ．ただし，S1 は信号 1 が Gの状態を，S2 は信号 2 が G の状態を，S3 は信号 3 が G の状態を，それぞれ表すものとする．入力信号は Reset のみである．また，出力信号は Y1 , Y2 , Y3 で，それぞれ信号 1，信号 2，信号 3 の信号の状態に対応し，1 のとき G を，0 のとき R を点灯させるものとする．
問 2 状態遷移図にフリップフロップの状態を割り当てよ．
問 3 D フリップフロップを用いるものとして，各フリップフロップへの入力の論理式，および出力 Y1 , Y2 , Y3 を与える論理式を求めよ．

ディジタル論理回路 MA の問題は，このページで終りである．
— 12 —

情報デザイン MD

I 遠くから列車を利用して函館を訪れる観光客が，列車の中で訪問地の楽しみ方を計画できる携帯電話サービスを提案せよ．携帯電話は，近未来のものを想定しても良い．解答は，以下の 4 項目について記述せよ．解答は，文章だけでなく絵や図などを用いて，具体的でわかりやすく表現せよ．
（配点 50 点）[記述する項目]項目 1 タイトル（コンセプトを端的に表現したもの）
項目 2 対象となるユーザの特性
項目 3 現状分析
項目 4 サービスの内容と携帯電話の操作方法

情報デザイン MD の問題は，このページで終りである．
— 13 —

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

I 人間中心設計プロセスは，1999 年に国際規格 (ISO 13407) となり，2000 年には日本工業規格（JIS Z 8530）になっている．このプロセスを図で表したものが，図 1 である [1]．以下の問いに答えよ．
（配点 50 点）

図1

人間中心設計プロセス

問 1 人間中心設計プロセスとウォーターフォールプロセスについて，それぞれの長所と短所を述べよ．
問 2 商品設計プロセスでは，仕様書作成段階と設計終了段階で用いられる評価方法が異なっている．これらの 2 つの段階で用いられる評価方法を，1 つずつ挙げ，それぞれの特徴を述べよ．

[1] 日本工業規格（JIS Z 8530）より転載．

ヒューマンインタフェース MD の問題は，このページで終りである．
— 14 —

メ ディア デ ザ イ ン 基 礎 MD

I 2 つのショッピングサイトのユーザビリティを評価するために実験を行った．実験参加者は 18 名で，サイト A と B の評価にそれぞれ 9 名ずつがランダムに割り当てられ，特定の商品を探して購入する課題を行った．課題終了後，「サイトの見やすさ」
を 10 点満点で評価してもらった．以下の問いに答えよ．
（配点 50 点）
問 1 サイト A の見やすさ得点の平均値は 5.89，サイト B の平均値は 7.78 であった．2 つのサイトの得点差を t 検定により明らかにしたい（両側検定，有意水準 1%）．以下の問いに答えよ．

(1) この検定における帰無仮説を述べよ．
(2) この検定における対立仮説を述べよ．
(3) サイト A と B の見やすさ得点から t 値を計算したところ，t = 3.24 であった．自由度（df）を求め，表 1 から有意差を判定して結論を述べよ．
問 2 ユーザビリティ評価においては，上記のような主観的評価だけでなく，さまざまな指標を分析すべきである．このような実験で測定可能な，ユーザビリティに関連する指標を 2 点挙げ，それぞれ簡潔に説明せよ．

— 15 —

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

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