平成 29 年度

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

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

1．試験開始の合図があるまで，この問題冊子を開かないでください．
2．出題科目およびページは，下表のとおりです．解答冊子を提出してください．
出 題 科 目

ペ ー ジ

問題数

基

礎

数

学

1

2問

情

報

数

学

2

1問

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

3〜 4

1問

デ ー タ ベ ー ス 工 学

5

1問

注

意

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

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

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

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

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

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

基 礎 数 学

I 関数 f (x) = e−x2 について，以下の問いに答えよ．（配点 25 点）d2
df (x) ≥ 0 となる x の範囲および
f (x) ≥ 0 となる x の範囲をそれぞ
dx
dx2
れ求めよ．

問1

f (x) − (1 + ax2 )が収束するような実数 a の値とそのときの極限x→0x4
値を求めよ．

問2

極限 lim

問 2 で求めた a の値を用いて g(x) = 1 + ax2 とする．f (x) と g(x) の大小関
∫ 1/2
11f (x)dx ≥係を利用してが成り立つことを示せ．
24
0

問3

II n を 1 以上の整数とする．n 次正方行列 A および写像 f (x) = Ax (x ∈ Rn ) について，以下の問いに答えよ．（配点 25 点）
問1

A2 = A をみたすとき，行列 A の固有値としてとりうる値をすべて求めよ．

問2

A2 = A かつ t A = −A をみたすとき，行列 A を求めよ．ただし，t A は A の転置行列とする．
問3

n = 2 のとき，A2 = O をみたす行列 A を求めよ．また，そのときの写像 fの核 Ker(f ) と像 Im(f ) を求めよ．

基礎数学の問題は，このページで終りである．
— 1 —情 報 数 学

I n 個 (n > 2) の節点 x1 , x2 , · · ·, xn からなる単純無向グラフ G の隣接行列を A とし，
Ak の (i, j) 成分を (Ak )ij とする．ただし，ループを認めないものとする．また，長さ 3 の閉路をなす G の部分グラフの節点集合を G に含まれる三角形と呼ぶ．以下の問いに答えよ．（配点 50 点）
問1

グラフ G の隣接行列 A が以下で与えられるとき，節点 xℓ から節点 xℓ へ至る

長さ 3 の経路の数を各節点についてそれぞれ求めよ．


 0 1 1 0  1 0 1 1  1 1 0 0 





A=

0 1 0 0
問2

グラフ G に含まれる三角形の個数を A を用いて表せ．

問3(A)ij および (A2 )ij のどちらも 0 でないような i, j が存在するとき，グラフ Gに含まれる三角形が少なくとも 1 つ存在することを示せ．

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

I 4 種類の品物がそれぞれ十分な個数用意されているとき，容量が C の一つのカバ
ンに，容量 C を超えない範囲で，品物を詰めることを考える．カバンに同じ品物を複数個詰めてもよい．このとき，以下の問いに答えよ．ただし，品物の番号，名前，価値，体積を，それぞれ i, Ni , Pi , Si と表記し，番号は，体積の小さい順に，

1 から 4 までの整数が振られているものとする．さらに，価値，体積，容量は非負の整数で与えられるものとする．（配点 50 点）

問1

カバンの容量が C = 10 であり，品物の一覧が表 1 で与えられているとき，カバンに詰めた品物の価値の総和が最大になる品物の組み合わせを，品物の名前と個数で答えよ．さらに，そのときのカバンに詰めた品物の価値の総和も答
えよ．
表1
番号 i
名前 Ni
価値 Pi
体積 Si

問2

1
FUN1
8
3

2
FUN2
9
5

3
FUN3
12
7

4
FUN4
15
8

容量 C のカバンに詰めた品物の価値の総和が最大 (最大価値) になる品物の組み合わせを求めるために，容量 C 以下のすべての容量 (j = 1, 2, · · · , C) のカバンを一つずつ用意し，各容量 j のカバンの最大価値 (Vj4 ) となる品物の組み合わせを，以下の手順 1 から手順 4 を実行して求めることにする．問 1 の問題に対して，以下の手順 1 から手順 4 を実行した場合に得られる最大価値 (Vji )を求めよ．ただし，j = 1, 2, · · · , 10，i = 1, · · · , 4 とする．解答は，表 2 の空欄を埋めたものを解答用紙に書くこと．
表2

j
Vj1

1
0

Vj2

0

Vj3

0

Vj4

0

2

3

4

5

— 3 —

6

7

8

9

10

手順 1

i = 1 として，品物 N1 だけを詰めた場合の各容量 j(= 1, 2,· · ·,C) のカバンの最大価値 (Vj1 ) を求め，それぞれのカバンに詰めた品物のリスト

Lj (カバンに入れた個数分の品物名を明記) を作成する．ただし，カバンに品物が入っていない場合，最大価値 Vj1 は 0，品物のリスト Lj は空とする．
手順 2

i = 2 として，品物 N1 に品物 N2 を加えた二つの品物を組み合わせてカバンに詰めた場合の各容量 j(= 1, 2, · · · , C) のカバンの最大価値 (Vj2 ) とカバンに詰めた品物のリスト Lj を，最大値更新手順 1 と最大値更新手順

2 を実行して更新する．
手順 3

i = 3 として，品物 N1 と品物 N2 に，さらに品物 N3 を加えた三つの品物を組み合わせてカバンに詰めた場合の各容量 j(= 1, 2, · · · , C) のカバンの最大価値 (Vj3 ) とカバンに詰めた品物のリスト Lj を，最大値更新手順 1と最大値更新手順 2 を実行して更新する．
手順 4

i = 4 として，品物 N1 ，品物 N2 ，品物 N3 に，さらに品物 N4 を加えた四つの品物を組み合わせてカバンに詰めた場合の各容量 j(= 1, 2, · · · , C)のカバンの最大価値 (Vj4 ) とカバンに詰めた品物のリスト Lj を，最大値更新手順 1 と最大値更新手順 2 を実行して更新すると，容量 C のカバンの最大価値を求める手順は終了する．
最大値更新手順 1

すべてのカバンに対して，Vji = Vji−1 を実行する．

最大値更新手順 2

すべてのカバンに対して，容量 j が小さいカバンから大きiいカバンへ順に，j − Si ≥ 0 でかつ ，Pi + Vj−S
が現在の容量 j のカバンのii
最大価値 Vji より大きければ，Vji を Pi + Vj−Sに更新し，品物のリスト Ljiを Lj−Si に Ni を一つ加えたものに更新する．ただし，V0k = 0 (k = 1, · · · , 4)とする．

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

I データベースでのトランザクション処理について，以下の問いに答えよ．
（配点 50 点）

問1

トランザクション処理の例として，銀行口座の処理を考える．ある口座の残高が 100 万円であり，20 万円を入金するトランザクション T1 と，10 万円を引き出すトランザクション T2 を考える．二つのトランザクションを同時実行するとき，T1 による更新が T2 によって損なわれてしまう場合のスケジュールと口座の残高の変化を答えよ．
問2

複数のトランザクションを同時実行するとき，異常が発生しないように制御する方法としてロックがある．問 1 の二つのトランザクションをロックにより制御するにはどうしたらよいか．ロックの順番が分かるようにスケジュールを答えよ．
問3

ロックを用いたトランザクション処理では，デッドロックが発生することが問題になる．デッドロックが発生すると何が問題かを説明せよ．
問4

デッドロック対策の例を一つ挙げ，詳しく説明せよ．

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

大学院博士 (前期) 課程入学者選抜学力試験
高度 ICT 領域

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

1．試験開始の合図があるまで，この問題冊子を開かないでください．
2．出題科目およびページは，下表のとおりです．解答冊子を提出してください．
出 題 科 目

ペ ー ジ

問題数

基

礎

数

学

1

2問

情

報

数

学

2

1問

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

3〜 4

1問

デ ー タ ベ ー ス 工 学

5

1問

注

意

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

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

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

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

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

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

基 礎 数 学

I 関数 f (x) = e−x2 について，以下の問いに答えよ．（配点 25 点）d2
df (x) ≥ 0 となる x の範囲および
f (x) ≥ 0 となる x の範囲をそれぞ
dx
dx2
れ求めよ．

問1

f (x) − (1 + ax2 )が収束するような実数 a の値とそのときの極限x→0x4
値を求めよ．

問2

極限 lim

問 2 で求めた a の値を用いて g(x) = 1 + ax2 とする．f (x) と g(x) の大小関
∫ 1/2
11f (x)dx ≥係を利用してが成り立つことを示せ．
24
0

問3

II n を 1 以上の整数とする．n 次正方行列 A および写像 f (x) = Ax (x ∈ Rn ) について，以下の問いに答えよ．（配点 25 点）
問1

A2 = A をみたすとき，行列 A の固有値としてとりうる値をすべて求めよ．

問2

A2 = A かつ t A = −A をみたすとき，行列 A を求めよ．ただし，t A は A の転置行列とする．
問3

n = 2 のとき，A2 = O をみたす行列 A を求めよ．また，そのときの写像 fの核 Ker(f ) と像 Im(f ) を求めよ．

基礎数学の問題は，このページで終りである．
— 1 —情 報 数 学

I n 個 (n > 2) の節点 x1 , x2 , · · ·, xn からなる単純無向グラフ G の隣接行列を A とし，
Ak の (i, j) 成分を (Ak )ij とする．ただし，ループを認めないものとする．また，長さ 3 の閉路をなす G の部分グラフの節点集合を G に含まれる三角形と呼ぶ．以下の問いに答えよ．（配点 50 点）
問1

グラフ G の隣接行列 A が以下で与えられるとき，節点 xℓ から節点 xℓ へ至る

長さ 3 の経路の数を各節点についてそれぞれ求めよ．


 0 1 1 0  1 0 1 1  1 1 0 0 





A=

0 1 0 0
問2

グラフ G に含まれる三角形の個数を A を用いて表せ．

問3(A)ij および (A2 )ij のどちらも 0 でないような i, j が存在するとき，グラフ Gに含まれる三角形が少なくとも 1 つ存在することを示せ．

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

I 4 種類の品物がそれぞれ十分な個数用意されているとき，容量が C の一つのカバ
ンに，容量 C を超えない範囲で，品物を詰めることを考える．カバンに同じ品物を複数個詰めてもよい．このとき，以下の問いに答えよ．ただし，品物の番号，名前，価値，体積を，それぞれ i, Ni , Pi , Si と表記し，番号は，体積の小さい順に，

1 から 4 までの整数が振られているものとする．さらに，価値，体積，容量は非負の整数で与えられるものとする．（配点 50 点）

問1

カバンの容量が C = 10 であり，品物の一覧が表 1 で与えられているとき，カバンに詰めた品物の価値の総和が最大になる品物の組み合わせを，品物の名前と個数で答えよ．さらに，そのときのカバンに詰めた品物の価値の総和も答
えよ．
表1
番号 i
名前 Ni
価値 Pi
体積 Si

問2

1
FUN1
8
3

2
FUN2
9
5

3
FUN3
12
7

4
FUN4
15
8

容量 C のカバンに詰めた品物の価値の総和が最大 (最大価値) になる品物の組み合わせを求めるために，容量 C 以下のすべての容量 (j = 1, 2, · · · , C) のカバンを一つずつ用意し，各容量 j のカバンの最大価値 (Vj4 ) となる品物の組み合わせを，以下の手順 1 から手順 4 を実行して求めることにする．問 1 の問題に対して，以下の手順 1 から手順 4 を実行した場合に得られる最大価値 (Vji )を求めよ．ただし，j = 1, 2, · · · , 10，i = 1, · · · , 4 とする．解答は，表 2 の空欄を埋めたものを解答用紙に書くこと．
表2

j
Vj1

1
0

Vj2

0

Vj3

0

Vj4

0

2

3

4

5

— 3 —

6

7

8

9

10

手順 1

i = 1 として，品物 N1 だけを詰めた場合の各容量 j(= 1, 2,· · ·,C) のカバンの最大価値 (Vj1 ) を求め，それぞれのカバンに詰めた品物のリスト

Lj (カバンに入れた個数分の品物名を明記) を作成する．ただし，カバンに品物が入っていない場合，最大価値 Vj1 は 0，品物のリスト Lj は空とする．
手順 2

i = 2 として，品物 N1 に品物 N2 を加えた二つの品物を組み合わせてカバンに詰めた場合の各容量 j(= 1, 2, · · · , C) のカバンの最大価値 (Vj2 ) とカバンに詰めた品物のリスト Lj を，最大値更新手順 1 と最大値更新手順

2 を実行して更新する．
手順 3

i = 3 として，品物 N1 と品物 N2 に，さらに品物 N3 を加えた三つの品物を組み合わせてカバンに詰めた場合の各容量 j(= 1, 2, · · · , C) のカバンの最大価値 (Vj3 ) とカバンに詰めた品物のリスト Lj を，最大値更新手順 1と最大値更新手順 2 を実行して更新する．
手順 4

i = 4 として，品物 N1 ，品物 N2 ，品物 N3 に，さらに品物 N4 を加えた四つの品物を組み合わせてカバンに詰めた場合の各容量 j(= 1, 2, · · · , C)のカバンの最大価値 (Vj4 ) とカバンに詰めた品物のリスト Lj を，最大値更新手順 1 と最大値更新手順 2 を実行して更新すると，容量 C のカバンの最大価値を求める手順は終了する．
最大値更新手順 1

すべてのカバンに対して，Vji = Vji−1 を実行する．

最大値更新手順 2

すべてのカバンに対して，容量 j が小さいカバンから大きiいカバンへ順に，j − Si ≥ 0 でかつ ，Pi + Vj−S
が現在の容量 j のカバンのii
最大価値 Vji より大きければ，Vji を Pi + Vj−Sに更新し，品物のリスト Ljiを Lj−Si に Ni を一つ加えたものに更新する．ただし，V0k = 0 (k = 1, · · · , 4)とする．

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

I データベースでのトランザクション処理について，以下の問いに答えよ．
（配点 50 点）

問1

トランザクション処理の例として，銀行口座の処理を考える．ある口座の残高が 100 万円であり，20 万円を入金するトランザクション T1 と，10 万円を引き出すトランザクション T2 を考える．二つのトランザクションを同時実行するとき，T1 による更新が T2 によって損なわれてしまう場合のスケジュールと口座の残高の変化を答えよ．
問2

複数のトランザクションを同時実行するとき，異常が発生しないように制御する方法としてロックがある．問 1 の二つのトランザクションをロックにより制御するにはどうしたらよいか．ロックの順番が分かるようにスケジュールを答えよ．
問3

ロックを用いたトランザクション処理では，デッドロックが発生することが問題になる．デッドロックが発生すると何が問題かを説明せよ．
問4

デッドロック対策の例を一つ挙げ，詳しく説明せよ．

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

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

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

1．試験開始の合図があるまで，この問題冊子を開かないでください．
2．出題科目およびページは，下表のとおりです．解答冊子を提出してください．
出 題 科 目
情

報

認

知

デ

ザ

ペ ー ジ

問題数

イ

ン

1

1問

理

学

2

1問

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

3

1問

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

4〜 5

1問

心

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

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

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

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

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

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

情報デザインI 「歩きスマホ」とは，歩きながらスマートフォンを使う行為である．歩きながら画面に集中してしまうと前方や左右に視線が配られず，事故につながりかねないため，その行為の危険性が指摘されている．以下の問いに答えよ．（配点 50 点）

問 1 「歩きスマホ禁止」を意味するピクトグラムを三つ提案し，それらの意図をそれぞれ 100 字以内で記述せよ．
問2

問１で挙げた三つの案のなかから最良のものを一つ選び，その理由を 150 字以内で記述せよ．

情報デザインの問題は，このページで終りである．
— 1 —認知心理学I 以下の問いに答えよ．（配点 50 点）
問1

Atkinson と Shiﬀrin (1968) のマルチ・ストアモデルでは，感覚記憶の次に転送される記憶を短期記憶と長期記憶に分けた．さらに，このマルチ・ストアモ
デルでは，貯蔵されるデータの内容と情報を貯蔵する構造の二つを区別した．
マルチ・ストアモデルによる感覚記憶，短期記憶，長期記憶の特徴をそれぞれ

150 字以内で記述せよ．
問2

マルチ・ストアモデルとは対照的に，Craik と Lockhart (1972) は，情報の符号化に注目した処理水準モデルを提唱し，高い記憶成績が生み出される過程を説明した．どのような認知的処理をすると高い記憶成績につながるのか，ある情報を記憶する場面の例を挙げ，処理水準モデルに基づいて，250 字以内で記
述せよ．
引用文献：

Atkinson, R. C., & Shiﬀrin, R. M. (1968). Human memory: A proposed system
and its control processes. In K. W. Spence & J. T. Spence (Eds.), The psychologyof learning and motivation, Vol. 2. New York: Academic Press, pp. 89-195.
Craik, F. I. M., & Lockhart, R. S. (1972). Levels of processing: A framework formemory research. Journal of Verbal Learning and Verbal Behavior, 11, pp. 671-684.

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

I 井上（2008）は，ヒューマンインタフェースを生理的・認知的・感性的インタフェー
スの 3 種類に分類した．飲み物の自動販売機を例として，以下の問いに答えよ．
（配点 50 点）

問1

効果的な生理的インタフェースの事例，認知的インタフェースの事例，そして感性的インタフェースの事例をそれぞれ二つずつ挙げよ．図を用いてもよい．
問2

感性的インタフェースの定義を 150 字以内で記述せよ．

参考文献：
井上勝雄（2008）．魅力的なインタフェースをデザインする，工業調査会，pp. 19-21.

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

I 4 種類の品物がそれぞれ十分な個数用意されているとき，容量が C の一つのカバ
ンに，容量 C を超えない範囲で，品物を詰めることを考える．カバンに同じ品物を複数個詰めてもよい．このとき，以下の問いに答えよ．ただし，品物の番号，名前，価値，体積を，それぞれ i, Ni , Pi , Si と表記し，番号は，体積の小さい順に，

1 から 4 までの整数が振られているものとする．さらに，価値，体積，容量は非負の整数で与えられるものとする．（配点 50 点）

問1

カバンの容量が C = 10 であり，品物の一覧が表 1 で与えられているとき，カバンに詰めた品物の価値の総和が最大になる品物の組み合わせを，品物の名前と個数で答えよ．さらに，そのときのカバンに詰めた品物の価値の総和も答
えよ．
表1
番号 i
名前 Ni
価値 Pi
体積 Si

問2

1
FUN1
8
3

2
FUN2
9
5

3
FUN3
12
7

4
FUN4
15
8

容量 C のカバンに詰めた品物の価値の総和が最大 (最大価値) になる品物の組み合わせを求めるために，容量 C 以下のすべての容量 (j = 1, 2, · · · , C) のカバンを一つずつ用意し，各容量 j のカバンの最大価値 (Vj4 ) となる品物の組み合わせを，以下の手順 1 から手順 4 を実行して求めることにする．問 1 の問題に対して，以下の手順 1 から手順 4 を実行した場合に得られる最大価値 (Vji )を求めよ．ただし，j = 1, 2, · · · , 10，i = 1, · · · , 4 とする．解答は，表 2 の空欄を埋めたものを解答用紙に書くこと．
表2

j
Vj1

1
0

Vj2

0

Vj3

0

Vj4

0

2

3

4

5

— 4 —

6

7

8

9

10

手順 1

i = 1 として，品物 N1 だけを詰めた場合の各容量 j(= 1, 2,· · ·,C) のカバンの最大価値 (Vj1 ) を求め，それぞれのカバンに詰めた品物のリスト

Lj (カバンに入れた個数分の品物名を明記) を作成する．ただし，カバンに品物が入っていない場合，最大価値 Vj1 は 0，品物のリスト Lj は空とする．
手順 2

i = 2 として，品物 N1 に品物 N2 を加えた二つの品物を組み合わせてカバンに詰めた場合の各容量 j(= 1, 2, · · · , C) のカバンの最大価値 (Vj2 ) とカバンに詰めた品物のリスト Lj を，最大値更新手順 1 と最大値更新手順

2 を実行して更新する．
手順 3

i = 3 として，品物 N1 と品物 N2 に，さらに品物 N3 を加えた三つの品物を組み合わせてカバンに詰めた場合の各容量 j(= 1, 2, · · · , C) のカバンの最大価値 (Vj3 ) とカバンに詰めた品物のリスト Lj を，最大値更新手順 1と最大値更新手順 2 を実行して更新する．
手順 4

i = 4 として，品物 N1 ，品物 N2 ，品物 N3 に，さらに品物 N4 を加えた四つの品物を組み合わせてカバンに詰めた場合の各容量 j(= 1, 2, · · · , C)のカバンの最大価値 (Vj4 ) とカバンに詰めた品物のリスト Lj を，最大値更新手順 1 と最大値更新手順 2 を実行して更新すると，容量 C のカバンの最大価値を求める手順は終了する．
最大値更新手順 1

すべてのカバンに対して，Vji = Vji−1 を実行する．

最大値更新手順 2

すべてのカバンに対して，容量 j が小さいカバンから大きiいカバンへ順に，j − Si ≥ 0 でかつ ，Pi + Vj−S
が現在の容量 j のカバンのii
最大価値 Vji より大きければ，Vji を Pi + Vj−Sに更新し，品物のリスト Ljiを Lj−Si に Ni を一つ加えたものに更新する．ただし，V0k = 0 (k = 1, · · · , 4)とする．

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

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

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

1．試験開始の合図があるまで，この問題冊子を開かないでください．
2．出題科目およびページは，下表のとおりです．解答冊子を提出してください．
出 題 科 目

ペ ー ジ

問題数

基

礎

数

学

1

2問

情

報

数

学

2

1問

応

用

数

学

3

1問

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

4〜 5

1問

注

意

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

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

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

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

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

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

基 礎 数 学

I 関数 f (x) = e−x2 について，以下の問いに答えよ．（配点 25 点）d2
df (x) ≥ 0 となる x の範囲および
f (x) ≥ 0 となる x の範囲をそれぞ
dx
dx2
れ求めよ．

問1

f (x) − (1 + ax2 )が収束するような実数 a の値とそのときの極限x→0x4
値を求めよ．

問2

極限 lim

問 2 で求めた a の値を用いて g(x) = 1 + ax2 とする．f (x) と g(x) の大小関
∫ 1/2
11f (x)dx ≥係を利用してが成り立つことを示せ．
24
0

問3

II n を 1 以上の整数とする．n 次正方行列 A および写像 f (x) = Ax (x ∈ Rn ) について，以下の問いに答えよ．（配点 25 点）
問1

A2 = A をみたすとき，行列 A の固有値としてとりうる値をすべて求めよ．

問2

A2 = A かつ t A = −A をみたすとき，行列 A を求めよ．ただし，t A は A の転置行列とする．
問3

n = 2 のとき，A2 = O をみたす行列 A を求めよ．また，そのときの写像 fの核 Ker(f ) と像 Im(f ) を求めよ．

基礎数学の問題は，このページで終りである．
— 1 —情 報 数 学

I n 個 (n > 2) の節点 x1 , x2 , · · ·, xn からなる単純無向グラフ G の隣接行列を A とし，
Ak の (i, j) 成分を (Ak )ij とする．ただし，ループを認めないものとする．また，長さ 3 の閉路をなす G の部分グラフの節点集合を G に含まれる三角形と呼ぶ．以下の問いに答えよ．（配点 50 点）
問1

グラフ G の隣接行列 A が以下で与えられるとき，節点 xℓ から節点 xℓ へ至る

長さ 3 の経路の数を各節点についてそれぞれ求めよ．


 0 1 1 0  1 0 1 1  1 1 0 0 





A=

0 1 0 0
問2

グラフ G に含まれる三角形の個数を A を用いて表せ．

問3(A)ij および (A2 )ij のどちらも 0 でないような i, j が存在するとき，グラフ Gに含まれる三角形が少なくとも 1 つ存在することを示せ．

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

I 複素平面上の領域 D の各点 z = x + iy で微分可能な関数 w(z) = u(x, y) + iv(x, y)を考える．このとき，w を正則関数と呼び，u, v は以下の Cauchy-Riemann の関係
式をみたす．
















∂v
∂u
=
∂x
∂y
∂u
∂v
=−
∂y
∂x

ただし，u, v, x, y ∈ R, i =問1u, v は以下の式をみたすことを示せ．
















問2

√
−1 である．以下の問いに答えよ．（配点 50 点）

∂ 2u
∂2u
+
=0
∂x2
∂y 2
∂ 2v
∂2v
+
=0
∂x2
∂y 2

x = r cos θ, y = r sin θ と極座標変換するとき，Cauchy-Riemann の関係式は以下の式になることを示せ．














問3

1 ∂v
∂u
=
∂r
r ∂θ
∂v
1 ∂u
=−
∂r
r ∂θ

w の実部 u を以下のように与える．
u = x3 + axy 2

ただし，a は実数とする．w が正則関数になるような a の値を求めよ．さらに，v(1, 1) = 0 をみたす w の虚部 v を求めよ．

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

I 4 種類の品物がそれぞれ十分な個数用意されているとき，容量が C の一つのカバ
ンに，容量 C を超えない範囲で，品物を詰めることを考える．カバンに同じ品物を複数個詰めてもよい．このとき，以下の問いに答えよ．ただし，品物の番号，名前，価値，体積を，それぞれ i, Ni , Pi , Si と表記し，番号は，体積の小さい順に，

1 から 4 までの整数が振られているものとする．さらに，価値，体積，容量は非負の整数で与えられるものとする．（配点 50 点）

問1

カバンの容量が C = 10 であり，品物の一覧が表 1 で与えられているとき，カバンに詰めた品物の価値の総和が最大になる品物の組み合わせを，品物の名前と個数で答えよ．さらに，そのときのカバンに詰めた品物の価値の総和も答
えよ．
表1
番号 i
名前 Ni
価値 Pi
体積 Si

問2

1
FUN1
8
3

2
FUN2
9
5

3
FUN3
12
7

4
FUN4
15
8

容量 C のカバンに詰めた品物の価値の総和が最大 (最大価値) になる品物の組み合わせを求めるために，容量 C 以下のすべての容量 (j = 1, 2, · · · , C) のカバンを一つずつ用意し，各容量 j のカバンの最大価値 (Vj4 ) となる品物の組み合わせを，以下の手順 1 から手順 4 を実行して求めることにする．問 1 の問題に対して，以下の手順 1 から手順 4 を実行した場合に得られる最大価値 (Vji )を求めよ．ただし，j = 1, 2, · · · , 10，i = 1, · · · , 4 とする．解答は，表 2 の空欄を埋めたものを解答用紙に書くこと．
表2

j
Vj1

1
0

Vj2

0

Vj3

0

Vj4

0

2

3

4

5

— 4 —

6

7

8

9

10

手順 1

i = 1 として，品物 N1 だけを詰めた場合の各容量 j(= 1, 2,· · ·,C) のカバンの最大価値 (Vj1 ) を求め，それぞれのカバンに詰めた品物のリスト

Lj (カバンに入れた個数分の品物名を明記) を作成する．ただし，カバンに品物が入っていない場合，最大価値 Vj1 は 0，品物のリスト Lj は空とする．
手順 2

i = 2 として，品物 N1 に品物 N2 を加えた二つの品物を組み合わせてカバンに詰めた場合の各容量 j(= 1, 2, · · · , C) のカバンの最大価値 (Vj2 ) とカバンに詰めた品物のリスト Lj を，最大値更新手順 1 と最大値更新手順

2 を実行して更新する．
手順 3

i = 3 として，品物 N1 と品物 N2 に，さらに品物 N3 を加えた三つの品物を組み合わせてカバンに詰めた場合の各容量 j(= 1, 2, · · · , C) のカバンの最大価値 (Vj3 ) とカバンに詰めた品物のリスト Lj を，最大値更新手順 1と最大値更新手順 2 を実行して更新する．
手順 4

i = 4 として，品物 N1 ，品物 N2 ，品物 N3 に，さらに品物 N4 を加えた四つの品物を組み合わせてカバンに詰めた場合の各容量 j(= 1, 2, · · · , C)のカバンの最大価値 (Vj4 ) とカバンに詰めた品物のリスト Lj を，最大値更新手順 1 と最大値更新手順 2 を実行して更新すると，容量 C のカバンの最大価値を求める手順は終了する．
最大値更新手順 1

すべてのカバンに対して，Vji = Vji−1 を実行する．

最大値更新手順 2

すべてのカバンに対して，容量 j が小さいカバンから大きiいカバンへ順に，j − Si ≥ 0 でかつ ，Pi + Vj−S
が現在の容量 j のカバンのii
最大価値 Vji より大きければ，Vji を Pi + Vj−Sに更新し，品物のリスト Ljiを Lj−Si に Ni を一つ加えたものに更新する．ただし，V0k = 0 (k = 1, · · · , 4)とする．

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

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

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

1．試験開始の合図があるまで，この問題冊子を開かないでください．
2．出題科目およびページは，下表のとおりです．解答冊子を提出してください．
出 題 科 目

ペ ー ジ

問題数

基

礎

数

学

1

2問

情

報

数

学

2

1問

人

工

知

能

3

1問

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

4〜 5

1問

注

意

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

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

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

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

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

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

基 礎 数 学

I 関数 f (x) = e−x2 について，以下の問いに答えよ．（配点 25 点）d2
df (x) ≥ 0 となる x の範囲および
f (x) ≥ 0 となる x の範囲をそれぞ
dx
dx2
れ求めよ．

問1

f (x) − (1 + ax2 )が収束するような実数 a の値とそのときの極限x→0x4
値を求めよ．

問2

極限 lim

問 2 で求めた a の値を用いて g(x) = 1 + ax2 とする．f (x) と g(x) の大小関
∫ 1/2
11f (x)dx ≥係を利用してが成り立つことを示せ．
24
0

問3

II n を 1 以上の整数とする．n 次正方行列 A および写像 f (x) = Ax (x ∈ Rn ) について，以下の問いに答えよ．（配点 25 点）
問1

A2 = A をみたすとき，行列 A の固有値としてとりうる値をすべて求めよ．

問2

A2 = A かつ t A = −A をみたすとき，行列 A を求めよ．ただし，t A は A の転置行列とする．
問3

n = 2 のとき，A2 = O をみたす行列 A を求めよ．また，そのときの写像 fの核 Ker(f ) と像 Im(f ) を求めよ．

基礎数学の問題は，このページで終りである．
— 1 —情 報 数 学

I n 個 (n > 2) の節点 x1 , x2 , · · ·, xn からなる単純無向グラフ G の隣接行列を A とし，
Ak の (i, j) 成分を (Ak )ij とする．ただし，ループを認めないものとする．また，長さ 3 の閉路をなす G の部分グラフの節点集合を G に含まれる三角形と呼ぶ．以下の問いに答えよ．（配点 50 点）
問1

グラフ G の隣接行列 A が以下で与えられるとき，節点 xℓ から節点 xℓ へ至る

長さ 3 の経路の数を各節点についてそれぞれ求めよ．


 0 1 1 0  1 0 1 1  1 1 0 0 





A=

0 1 0 0
問2

グラフ G に含まれる三角形の個数を A を用いて表せ．

問3(A)ij および (A2 )ij のどちらも 0 でないような i, j が存在するとき，グラフ Gに含まれる三角形が少なくとも 1 つ存在することを示せ．

情報数学の問題は，このページで終りである．
— 2 —人 工 知 能

I 3 人の村人と 3 人の人狼が川の西岸にいて，3 人乗りのボートも西岸にある．いま川の西岸から東岸に全員が渡ろうとしている．ただし，川の西岸，東岸，ボートの上のいずれでも村人よりも人狼が多くなった場合，村人は人狼に食べられてしまう．
村人と人狼の全員が，無事にボートを使って川を渡る手順を考える．このとき，以下の問いに答えよ．（配点 50 点）

問1

この問題を状態空間探索問題と捉えて，初期状態，目標状態，作用素の集合

を書け．
問2

問 1 の状態空間探索問題を解き，目標状態に到達する状態の列を一つ書け．

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

I 4 種類の品物がそれぞれ十分な個数用意されているとき，容量が C の一つのカバ
ンに，容量 C を超えない範囲で，品物を詰めることを考える．カバンに同じ品物を複数個詰めてもよい．このとき，以下の問いに答えよ．ただし，品物の番号，名前，価値，体積を，それぞれ i, Ni , Pi , Si と表記し，番号は，体積の小さい順に，

1 から 4 までの整数が振られているものとする．さらに，価値，体積，容量は非負の整数で与えられるものとする．（配点 50 点）

問1

カバンの容量が C = 10 であり，品物の一覧が表 1 で与えられているとき，カバンに詰めた品物の価値の総和が最大になる品物の組み合わせを，品物の名前と個数で答えよ．さらに，そのときのカバンに詰めた品物の価値の総和も答
えよ．
表1
番号 i
名前 Ni
価値 Pi
体積 Si

問2

1
FUN1
8
3

2
FUN2
9
5

3
FUN3
12
7

4
FUN4
15
8

容量 C のカバンに詰めた品物の価値の総和が最大 (最大価値) になる品物の組み合わせを求めるために，容量 C 以下のすべての容量 (j = 1, 2, · · · , C) のカバンを一つずつ用意し，各容量 j のカバンの最大価値 (Vj4 ) となる品物の組み合わせを，以下の手順 1 から手順 4 を実行して求めることにする．問 1 の問題に対して，以下の手順 1 から手順 4 を実行した場合に得られる最大価値 (Vji )を求めよ．ただし，j = 1, 2, · · · , 10，i = 1, · · · , 4 とする．解答は，表 2 の空欄を埋めたものを解答用紙に書くこと．
表2

j
Vj1

1
0

Vj2

0

Vj3

0

Vj4

0

2

3

4

5

— 4 —

6

7

8

9

10

手順 1

i = 1 として，品物 N1 だけを詰めた場合の各容量 j(= 1, 2,· · ·,C) のカバンの最大価値 (Vj1 ) を求め，それぞれのカバンに詰めた品物のリスト

Lj (カバンに入れた個数分の品物名を明記) を作成する．ただし，カバンに品物が入っていない場合，最大価値 Vj1 は 0，品物のリスト Lj は空とする．
手順 2

i = 2 として，品物 N1 に品物 N2 を加えた二つの品物を組み合わせてカバンに詰めた場合の各容量 j(= 1, 2, · · · , C) のカバンの最大価値 (Vj2 ) とカバンに詰めた品物のリスト Lj を，最大値更新手順 1 と最大値更新手順

2 を実行して更新する．
手順 3

i = 3 として，品物 N1 と品物 N2 に，さらに品物 N3 を加えた三つの品物を組み合わせてカバンに詰めた場合の各容量 j(= 1, 2, · · · , C) のカバンの最大価値 (Vj3 ) とカバンに詰めた品物のリスト Lj を，最大値更新手順 1と最大値更新手順 2 を実行して更新する．
手順 4

i = 4 として，品物 N1 ，品物 N2 ，品物 N3 に，さらに品物 N4 を加えた四つの品物を組み合わせてカバンに詰めた場合の各容量 j(= 1, 2, · · · , C)のカバンの最大価値 (Vj4 ) とカバンに詰めた品物のリスト Lj を，最大値更新手順 1 と最大値更新手順 2 を実行して更新すると，容量 C のカバンの最大価値を求める手順は終了する．
最大値更新手順 1

すべてのカバンに対して，Vji = Vji−1 を実行する．

最大値更新手順 2

すべてのカバンに対して，容量 j が小さいカバンから大きiいカバンへ順に，j − Si ≥ 0 でかつ ，Pi + Vj−S
が現在の容量 j のカバンのii
最大価値 Vji より大きければ，Vji を Pi + Vj−Sに更新し，品物のリスト Ljiを Lj−Si に Ni を一つ加えたものに更新する．ただし，V0k = 0 (k = 1, · · · , 4)とする．

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