令和 6 年度

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

A 日程
情報アーキテクチャ・高度 ICT 領域

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

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

ペ ー ジ

問題数

基

礎

数

学

1

2問

情

報

数

学

2

1問

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

4〜 6

1問

デ ー タ ベ ー ス 工 学

7〜 8

1問

注

意

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

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

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

5．解答用紙には，科目名，問題番号（I，II など），問いの番号（問 1 など）が記入されているので，選択する科目の解答用紙を用いてください．

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

8．試験終了後，監督員の指示に従って，解答冊子の表紙と 4 科目分の解答用紙を袋に入れてください．4 科目分の解答用紙が入っていない場合，入っていない科目の点数
は 0 点となります．

9．問題冊子と計算／下書き用紙は持ち帰ってください．

基 礎 数 学

I n を自然数とする．正方行列




 １
A=
 1
n

1

n 

1

とするとき， lim An を求めよ．（配点 25 点）n→∞

II 以下の問いに答えよ．（配点 25 点）
問 1 x は正の実数とする．

f (x) = xsin xを微分せよ．
問 2 t = tanxと変数変換し，次の定積分の値を求めよ．
2
∫

π
2

0

1
dx
1 + sin x

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

I n 個 (n ≥ 2) の要素からなる節点集合 Vn ={vi |i は n 以下の自然数 } と，無向辺の集合 En ⊂ {(vi , vj )|vi , vj ∈ Vn , i =\ j} による連結な単純無向グラフを G(Vn , En ) とする．以下の問いに答えよ．（配点 50 点）
問 1 n = 4 のとき，互いに同型でない連結 2 部グラフ G(V4 , E4 ) を全て示せ．
問 2 完全 2 部グラフとなるグラフ G(Vn , En ) が何通りあるか n を用いて表せ．ただし，互いに同型なグラフも異なるグラフとみなす．
問 3 完全 2 部グラフ K3,3 の隣接行列を一つ示し，その隣接行列を用いて長さ 3 の閉路が存在しないことを示せ．
問 4 命題を以下のように定める．
命題：グラフ G(Vn , En ) のある閉路の長さが奇数であるならば，グラフ G(Vn , En )は 2 部グラフでない
この命題の対偶を「偶数」という言葉を用いて表し，命題が真であることを示せ．

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

I 長さ n の文字列 s から長さ m のパターン文字列 p （ただし n > m とする）が最初に出現する位置を求める文字列検索の C 言語を用いたプログラムについて，以下の問いに答えよ．（配点 50 点）
問 1 単純な方法として，下記の線形探索の関数 search を記述した．この関数は，
長さ n の文字列 s，長さ m のパターン文字列 p を受け取り，まず s の先頭のm 文字を最初の照合範囲として選ぶ．そして，照合範囲の文字列と p を先頭から順に比較し，一致しなければ照合範囲を 1 文字後ろにずらすという処理を，p と同一の文字列が見つかるか s の終端に到達するまで最大 n−m+1 回くり返す．

（1） プログラム中の空欄（ア）〜（ウ）に入る適切な式をそれぞれ答えよ．
（2） search("JUST_FOR_FUN", "FUN") を実行したとき，9 行目と 10 行目はそれぞれ何回実行されるかを答えよ．

— 4 —問 2 問 1 の関数 search において，s が p を含まない場合の時間計算量を考える．
（1） s が同一の文字 'A' の並び，すなわち s[0]=s[1]=· · ·=s[n-1]= 'A' であるとき，関数の時間計算量が最良，最悪となる p の例として，長さ m=4であるものをそれぞれ一つ答えよ．
（2） 最良時間計算量，最悪時間計算量として適当なものをそれぞれオーダー記
法で答えよ．
問 3 検索の最良時間計算量を改善するために，パターンを末尾から比較することを考える．たとえば，文字列 s が "JUST_FOR_FUN"，パターン文字列 p が"FUN" の場合，次のように照合範囲を移動することができる．


最初の照合範囲は s の先頭の "JUS" である．照合範囲の文字列と，p の末尾から比較を行う．'N' と 'S' が一致しないことから，照合範囲の文字列はp とは異なることがわかる．'S' が p に含まれていないことから，照合範
囲を 3 文字進められる．


2 番目の照合範囲は "T_F" となる．照合範囲の末尾にある 'F' と p の末尾の 'N' が一致しないことから，照合範囲の文字列は p とは異なることがわ
かる．p の先頭が 'F' であることから，次の照合範囲は 2 文字進めて，p の
先頭の 'F' を "T_F" の末尾の 'F' に合わせられる．

このように，照合範囲の末尾の文字 c に応じて照合範囲を進める文字数が関数

shift(c, p) で求められるとする．shift(c, p) の値は， p に含まれる文字が c と一致する場合はその位置を c に合わせるための文字数であり，それ以外の文字の場合は（p が c と一致することはないため）p の長さ m となる．たとえば p が "FUN" である場合は，以下のようになる．


shift('F', "FUN")=2



shift('U', "FUN")=1



shift(それ以外の文字, "FUN")=3

この考えをもとに関数 search2 を記述した．ただし，空欄 (ア)，(イ) の内容
はプログラム 1 の (ア)，(イ) とそれぞれ同じ式が入ることとする．

— 5 —この関数において，shift(c, p) は定数時間であるとして，文字列 s が p を含まない場合の時間計算量を考える．

(1) s が n 個の 'A' の並びである場合に，関数 search2 の時間計算量が最良，最悪となるような p の例として，長さ m=4 であるようなものをそれぞれ一つ答
えよ．

(2) 最良時間計算量，最悪時間計算量として適当なものをそれぞれオーダー記
法で答えよ．

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

I 次の文章を読み，以下の問いに答えよ．（配点 50 点）
表 1 は，ある会社の発注記録である．発注記録には，「発注番号」，「発注日」，発注
先の「社名」と「住所」と「電話番号」，「商品名」とその商品の「発注数」と「単価」が書かれている．ここで，「発注番号」，「社名」，「商品名」はそれぞれ一意に識別可能とし，各「商品名」に対応する「単価」は，「社名」や「発注数」，「発注日」に関係なく一定とする．また，ひとつの発注番号に対して商品名は，たかだか一回
しかあらわれないものとする．

発注番号

発注日

社名

表1
住所
電話番号

2200012022/4/2

甲社

港町

11-2233

2200022022/4/2

乙社

白鳥町

22-1000

2200032022/5/10 甲社

港町

11-2233

商品名

発注数

単価

AAA
BBB
CCC
DDD
BBB
AAA

100
50
1000
250
10
200

10
170
2
5
170
10

表 1 を関係データベースで管理するために，正規化を行う．表 1 を第 1 正規形に正規化すると表 2 のようになる．

発注番号

発注日

社名

表2
住所
電話番号

220001
220001
220001
2200022200022200032022/4/2
2022/4/2
2022/4/2
2022/4/2
2022/4/2
2022/5/10

甲社
甲社
甲社
乙社
乙社
甲社

港町
港町
港町
白鳥町
白鳥町
港町

— 7 —

11-2233
11-2233
11-2233
22-1000
22-1000
11-2233

商品名

発注数

単価

AAA
BBB
CCC
DDD
BBB
AAA

100
50
1000
250
10
200

10
170
2
5
170
10

問 1 表 2 の各行について，発注金額（発注数と単価の積）を求めたい．表 2 の名前を「発注記録 1NF」として，「発注番号」，「商品名」，「発注数」，「単価」，「発注金額」を出力する SQL 文を答えよ．
問 2 表 2 の候補キーを一つ示せ．
問 3 表 2 を，第 2 正規形に正規化する．その際に満たすべき条件を説明せよ．また，正規化された表を示せ．ただし，解答する表は，第 3 正規形の条件を満たさないものとする．
問 4 問 3 で作成した表を，第 3 正規形に正規化する．その際に満たすべき条件を説明せよ．また，正規化された表を示せ．ただし，解答には，問 3 から変更した表のみを示してもよい．

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

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

A 日程
メディアデザイン領域

専 門 科 目［90 分］
注 意 事 項1． 試験開始の合図があるまで，この問題冊子を開かないでください．
2． 出題科目およびページは，下表のとおりです．問題ごとに配点が記されています．
出 題 科 目

ペ ー ジ

問題数

ン

1〜 2

1問

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

3

1問

認

学

4

1問

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

6〜 8

1問

情

報

デ

知

ザ

心

イ

理

注

意

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

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

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

5． 解答用紙には，科目名，問題番号（I，II など），問いの番号（問 1 など）が記入されているので，選択する科目の解答用紙を用いてください．

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

8． 試験終了後，監督員の指示に従って，解答冊子の表紙と 4 科目分の解答用紙を袋に入れてください．4 科目分の解答用紙が入っていない場合，入っていない科目の点
数は 0 点となります．

9． 問題冊子と計算／下書き用紙，下書き用原稿用紙は持ち帰ってください．

情報デザインI 次の文章を読んで，以下の問いに答えよ．（配点 50 点）
図 1 は，○△大学が開催するオープンキャンパスの告知について，市内の駅や図書館などの公共施設に設置されているサイネージ画面に表示するものである．画面は図 1 左側のように画面下半分には○△大学の風景画像が表示され，上半分に文字や図を表示する仕様となっており，表示する情報アイテムが右側の（A）から（L）である．
同大学は市内ではある程度認知度はあるものの同市内には複数の大学が存在している．多くの高校生に来てほしいと思っているが，最近は無料配布物目当ての参加者も増えており，ちゃんと進学を考えている生徒に来てほしいと思っている．以上の事柄を前提に，以下の問いに答えよ．

図 1 サイネージ（左）と, 文字や図の表示情報アイテム（右）— 1 —問 1 図 1 右側の表示情報アイテムの中で，文字情報である（A）から（J）について，情報の重要性を考え分類し，解答記述例のように，重要性が高いものを上として記号で解答欄へ記述し重要度の異なる部分を横線で区別せよ．また，そのように分類した理由を 120 文字以上 150 文字以内で述べよ．
解答記述例

問 2 サイネージの表示は，全部で４つのコマがあり合計で 15 秒である．それぞれの表示時間と１つのコマで同時に表示できる情報アイテムの数が決まっている（図 2）．この仕様に沿って，図 1 右側の表示情報アイテムの中から各コマに表示させる情報を選択し解答欄に記載せよ．ただし同じ表示情報アイテムは最大２回までしか使用できないものとする．表示の際の文字は改行しても良いが，文字自体のデザインはしなくて良い．また，各コマごとの設計意図を合計 150
文字以上 180 文字以内で説明せよ．

図 2 サイネージの表示仕様

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

I フォーカスグループインタビューについて，以下の問いに答えよ．（配点 50 点）
問 1 フォーカスグループインタビューの調査手法をわかりやすく説明せよ．
問 2 フォーカスグループインタビューとデプスインタビューを比較した場合において，フォーカスグループインタビューの長所と短所をそれぞれ 2 点ずつわか
りやすく説明せよ．

ヒューマンインタフェースの問題は，このページで終りである．
— 3 —認知心理学I 認識と文化の関係について書かれた文章を読み，以下の問いに答えよ．（配点 50 点）
人間の思考や認識は，その育った文化や環境と密接に関係することがよく知られている．1960 年代中ごろには，米国ペンシルベニア大学で「文化指標プロジェクト」
として，メディアによる視聴者の思考や認識への影響の調査が開始された．そこでは，ドラマやアニメの主要登場人物の人口学的構成が，多くの点で現実の人口学的構成と隔たりがあることが示された．さらに，これらのメディアとの長期間にわたる接触や，親や教師などの持つバイアスによって，個人の中にステレオタイプが形成され，キャリア選択への影響があることも明らかになってきている．このような状況から，近年，成長過程にある子どもたちの思考や認識に影響を与える米国の多国籍マスメディア・エンターテイメント複合企業であるディズニーは，映画制作の際にこのバイアスを修正していこうと，主人公の設定を変化させていることが複数のメディアで報じられた．
問 1 「ドラマやアニメの主要登場人物の人口学的構成が，多くの点で現実の人口学的構成との隔たりがある」とはどのようなことか，例を２つあげ，それぞれ

50 字から 100 字で説明せよ．
問 2 「将来のキャリアへの影響」とはどのようなことか，ジェンダー・ステレオタイプの観点から，例を１つあげて 50 字から 200 字で説明せよ．
問 3 「主人公の設定を変化させている」とはどのようなことか，説明せよ．さらに，ドラマやアニメ，映画に存在するバイアスを修正するために，具体的に考えられることを例としてあげつつ，あなたの考えを 150 字から 200 字で述べよ．
なお，この例はディズニー作品に限らない．

参考文献：
萩原滋 (2010) 「第 18 章 メディア情報と社会認識」箱田裕司ほか（編）『認知心理学』有斐閣

認知心理学の問題は，このページで終りである．
— 4 —(このページは白紙である)— 5 —アルゴリズムとデータ構造

I 長さ n の文字列 s から長さ m のパターン文字列 p （ただし n > m とする）が最初に出現する位置を求める文字列検索の C 言語を用いたプログラムについて，以下の問いに答えよ．（配点 50 点）
問 1 単純な方法として，下記の線形探索の関数 search を記述した．この関数は，
長さ n の文字列 s，長さ m のパターン文字列 p を受け取り，まず s の先頭のm 文字を最初の照合範囲として選ぶ．そして，照合範囲の文字列と p を先頭から順に比較し，一致しなければ照合範囲を 1 文字後ろにずらすという処理を，p と同一の文字列が見つかるか s の終端に到達するまで最大 n−m+1 回くり返す．

（1） プログラム中の空欄（ア）〜（ウ）に入る適切な式をそれぞれ答えよ．
（2） search("JUST_FOR_FUN", "FUN") を実行したとき，9 行目と 10 行目はそれぞれ何回実行されるかを答えよ．

— 6 —問 2 問 1 の関数 search において，s が p を含まない場合の時間計算量を考える．
（1） s が同一の文字 'A' の並び，すなわち s[0]=s[1]=· · ·=s[n-1]= 'A' であるとき，関数の時間計算量が最良，最悪となる p の例として，長さ m=4であるものをそれぞれ一つ答えよ．
（2） 最良時間計算量，最悪時間計算量として適当なものをそれぞれオーダー記
法で答えよ．
問 3 検索の最良時間計算量を改善するために，パターンを末尾から比較することを考える．たとえば，文字列 s が "JUST_FOR_FUN"，パターン文字列 p が"FUN" の場合，次のように照合範囲を移動することができる．


最初の照合範囲は s の先頭の "JUS" である．照合範囲の文字列と，p の末尾から比較を行う．'N' と 'S' が一致しないことから，照合範囲の文字列はp とは異なることがわかる．'S' が p に含まれていないことから，照合範
囲を 3 文字進められる．


2 番目の照合範囲は "T_F" となる．照合範囲の末尾にある 'F' と p の末尾の 'N' が一致しないことから，照合範囲の文字列は p とは異なることがわ
かる．p の先頭が 'F' であることから，次の照合範囲は 2 文字進めて，p の
先頭の 'F' を "T_F" の末尾の 'F' に合わせられる．

このように，照合範囲の末尾の文字 c に応じて照合範囲を進める文字数が関数

shift(c, p) で求められるとする．shift(c, p) の値は， p に含まれる文字が c と一致する場合はその位置を c に合わせるための文字数であり，それ以外の文字の場合は（p が c と一致することはないため）p の長さ m となる．たとえば p が "FUN" である場合は，以下のようになる．


shift('F', "FUN")=2



shift('U', "FUN")=1



shift(それ以外の文字, "FUN")=3

この考えをもとに関数 search2 を記述した．ただし，空欄 (ア)，(イ) の内容
はプログラム 1 の (ア)，(イ) とそれぞれ同じ式が入ることとする．

— 7 —この関数において，shift(c, p) は定数時間であるとして，文字列 s が p を含まない場合の時間計算量を考える．

(1) s が n 個の 'A' の並びである場合に，関数 search2 の時間計算量が最良，最悪となるような p の例として，長さ m=4 であるようなものをそれぞれ一つ答
えよ．

(2) 最良時間計算量，最悪時間計算量として適当なものをそれぞれオーダー記
法で答えよ．

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

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

A 日程
複雑系情報科学領域

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

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

ペ ー ジ

問題数

基

礎

数

学

1

2問

情

報

数

学

2

1問

応

用

数

学

3

1問

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

4〜 6

1問

注

意

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

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

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

5．解答用紙には，科目名，問題番号（I，II など），問いの番号（問 1 など）が記入されているので，選択する科目の解答用紙を用いてください．

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

8．試験終了後，監督員の指示に従って，解答冊子の表紙と 4 科目分の解答用紙を袋に入れてください．4 科目分の解答用紙が入っていない場合，入っていない科目の点数
は 0 点となります．

9．問題冊子と計算／下書き用紙は持ち帰ってください．

基 礎 数 学

I n を自然数とする．正方行列




 １
A=
 1
n

1

n 

1

とするとき， lim An を求めよ．（配点 25 点）n→∞

II 以下の問いに答えよ．（配点 25 点）
問 1 x は正の実数とする．

f (x) = xsin xを微分せよ．
問 2 t = tanxと変数変換し，次の定積分の値を求めよ．
2
∫

π
2

0

1
dx
1 + sin x

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

I n 個 (n ≥ 2) の要素からなる節点集合 Vn ={vi |i は n 以下の自然数 } と，無向辺の集合 En ⊂ {(vi , vj )|vi , vj ∈ Vn , i =\ j} による連結な単純無向グラフを G(Vn , En ) とする．以下の問いに答えよ．（配点 50 点）
問 1 n = 4 のとき，互いに同型でない連結 2 部グラフ G(V4 , E4 ) を全て示せ．
問 2 完全 2 部グラフとなるグラフ G(Vn , En ) が何通りあるか n を用いて表せ．ただし，互いに同型なグラフも異なるグラフとみなす．
問 3 完全 2 部グラフ K3,3 の隣接行列を一つ示し，その隣接行列を用いて長さ 3 の閉路が存在しないことを示せ．
問 4 命題を以下のように定める．
命題：グラフ G(Vn , En ) のある閉路の長さが奇数であるならば，グラフ G(Vn , En )は 2 部グラフでない
この命題の対偶を「偶数」という言葉を用いて表し，命題が真であることを示せ．

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

I n 個の確率変数 X1 , X2 , · · · , Xn が互いに独立かつ同一なガンマ分布 Ga( 12 , 2) に従うとき，各確率変数 Xi (i = 1, 2, · · · , n) の確率密度関数 fXi (x) はfXi (x) =





√

1
x
− 12
exp(− ) (x > 0)x
1
2
2Γ( 2 )
0(x ≤ 0)と書ける．ただし，Γ(z) はガンマ関数である．なお，実数 α, β > 0 に対し，必要なら次の関係式を用いてよい．
∫ 1
0tα−1 (1 − t)β−1 dt =Γ(α)Γ(β)Γ(α + β)以下の問いに答えよ．（配点 50 点）
問 1 確率変数 Y2 = X1 + X2 の確率密度関数 fY2 (y) を求めよ．
問 2 確率変数 Y3 = X1 + X2 + X3 の確率密度関数 fY3 (y) を求めよ．
問 3 数学的帰納法を用いて，確率変数 Yn = X1 + X2 + · · · + Xn の確率密度関数

fYn (y) を求めよ．

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

I 長さ n の文字列 s から長さ m のパターン文字列 p （ただし n > m とする）が最初に出現する位置を求める文字列検索の C 言語を用いたプログラムについて，以下の問いに答えよ．（配点 50 点）
問 1 単純な方法として，下記の線形探索の関数 search を記述した．この関数は，
長さ n の文字列 s，長さ m のパターン文字列 p を受け取り，まず s の先頭のm 文字を最初の照合範囲として選ぶ．そして，照合範囲の文字列と p を先頭から順に比較し，一致しなければ照合範囲を 1 文字後ろにずらすという処理を，p と同一の文字列が見つかるか s の終端に到達するまで最大 n−m+1 回くり返す．

（1） プログラム中の空欄（ア）〜（ウ）に入る適切な式をそれぞれ答えよ．
（2） search("JUST_FOR_FUN", "FUN") を実行したとき，9 行目と 10 行目はそれぞれ何回実行されるかを答えよ．

— 4 —問 2 問 1 の関数 search において，s が p を含まない場合の時間計算量を考える．
（1） s が同一の文字 'A' の並び，すなわち s[0]=s[1]=· · ·=s[n-1]= 'A' であるとき，関数の時間計算量が最良，最悪となる p の例として，長さ m=4であるものをそれぞれ一つ答えよ．
（2） 最良時間計算量，最悪時間計算量として適当なものをそれぞれオーダー記
法で答えよ．
問 3 検索の最良時間計算量を改善するために，パターンを末尾から比較することを考える．たとえば，文字列 s が "JUST_FOR_FUN"，パターン文字列 p が"FUN" の場合，次のように照合範囲を移動することができる．


最初の照合範囲は s の先頭の "JUS" である．照合範囲の文字列と，p の末尾から比較を行う．'N' と 'S' が一致しないことから，照合範囲の文字列はp とは異なることがわかる．'S' が p に含まれていないことから，照合範
囲を 3 文字進められる．


2 番目の照合範囲は "T_F" となる．照合範囲の末尾にある 'F' と p の末尾の 'N' が一致しないことから，照合範囲の文字列は p とは異なることがわ
かる．p の先頭が 'F' であることから，次の照合範囲は 2 文字進めて，p の
先頭の 'F' を "T_F" の末尾の 'F' に合わせられる．

このように，照合範囲の末尾の文字 c に応じて照合範囲を進める文字数が関数

shift(c, p) で求められるとする．shift(c, p) の値は， p に含まれる文字が c と一致する場合はその位置を c に合わせるための文字数であり，それ以外の文字の場合は（p が c と一致することはないため）p の長さ m となる．たとえば p が "FUN" である場合は，以下のようになる．


shift('F', "FUN")=2



shift('U', "FUN")=1



shift(それ以外の文字, "FUN")=3

この考えをもとに関数 search2 を記述した．ただし，空欄 (ア)，(イ) の内容
はプログラム 1 の (ア)，(イ) とそれぞれ同じ式が入ることとする．

— 5 —この関数において，shift(c, p) は定数時間であるとして，文字列 s が p を含まない場合の時間計算量を考える．

(1) s が n 個の 'A' の並びである場合に，関数 search2 の時間計算量が最良，最悪となるような p の例として，長さ m=4 であるようなものをそれぞれ一つ答
えよ．

(2) 最良時間計算量，最悪時間計算量として適当なものをそれぞれオーダー記
法で答えよ．

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

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

A 日程
知能情報科学領域

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

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

ペ ー ジ

問題数

基

礎

数

学

1

2問

情

報

数

学

2

1問

人

工

知

能

3〜 5

1問

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

6〜 8

1問

注

意

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

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

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

5．解答用紙には，科目名，問題番号（I，II など），問いの番号（問 1 など）が記入されているので，選択する科目の解答用紙を用いてください．

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

8．試験終了後，監督員の指示に従って，解答冊子の表紙と 4 科目分の解答用紙を袋に入れてください．4 科目分の解答用紙が入っていない場合，入っていない科目の点数
は 0 点となります．

9．問題冊子と計算／下書き用紙は持ち帰ってください．

基 礎 数 学

I n を自然数とする．正方行列




 １
A=
 1
n

1

n 

1

とするとき， lim An を求めよ．（配点 25 点）n→∞

II 以下の問いに答えよ．（配点 25 点）
問 1 x は正の実数とする．

f (x) = xsin xを微分せよ．
問 2 t = tanxと変数変換し，次の定積分の値を求めよ．
2
∫

π
2

0

1
dx
1 + sin x

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

I n 個 (n ≥ 2) の要素からなる節点集合 Vn ={vi |i は n 以下の自然数 } と，無向辺の集合 En ⊂ {(vi , vj )|vi , vj ∈ Vn , i =\ j} による連結な単純無向グラフを G(Vn , En ) とする．以下の問いに答えよ．（配点 50 点）
問 1 n = 4 のとき，互いに同型でない連結 2 部グラフ G(V4 , E4 ) を全て示せ．
問 2 完全 2 部グラフとなるグラフ G(Vn , En ) が何通りあるか n を用いて表せ．ただし，互いに同型なグラフも異なるグラフとみなす．
問 3 完全 2 部グラフ K3,3 の隣接行列を一つ示し，その隣接行列を用いて長さ 3 の閉路が存在しないことを示せ．
問 4 命題を以下のように定める．
命題：グラフ G(Vn , En ) のある閉路の長さが奇数であるならば，グラフ G(Vn , En )は 2 部グラフでない
この命題の対偶を「偶数」という言葉を用いて表し，命題が真であることを示せ．

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

I 次の文章を読み，以下の問いに答えよ．（配点 50 点）
ボタンを押すと，異なる 3 種類のサイコロ D1 ，D2 ，D3 のいずれか 1 個を選択し，投げるロボットがある．1 回目にサイコロ Di が選択される確率は ρi とする．2 回目
以降，ロボットは直前に選択したサイコロを記憶していて，それに応じて次のサイコロを確率的に選択する．サイコロ Di が選択された後，次にサイコロ Dj が選択される遷移確率は aij とする．
ボタンを押して投げられたサイコロの出た目を観測する．この操作を何回かくり返す．サイコロの種類によって，投げたとき偶数あるいは奇数の目が出る確率は異なる．サイコロ Di を投げたとき，偶数の目が出る確率は bi1 とし，奇数の目が出る
確率は bi2 とする．
問 1 サイコロの遷移確率 aij を i 行 j 列の要素にもつ状態遷移行列 A が次で与えられている．

 0.1 0.4 0.5 



A=
 0.2 0.2 0.6 


0.3 0.6 0.1



図 1 は，2 回目以降のサイコロの選択に関する状態遷移図である．図中の（ア）∼（ケ）の遷移確率を解答欄の（ア）∼（ケ）に記入せよ．

図1

3 種類のサイコロの選択に関する状態遷移図— 3 —問 2 サイコロの出た目が偶数あるいは奇数になる確率 bik を要素にもつ確率行列

B が次で与えられている．


 0.8 0.2 



B=
 0.5 0.5 

0.3 0.7

1,2,3 行目がサイコロの種類 D1 ,D2 ,D3 にそれぞれ対応し，1 列目は偶数が出る
確率を，2 列目は奇数が出る確率を表す．

図2

1 回目にサイコロの目が偶数になる確率

図 2 は，初期状態においてロボットがサイコロを 1 個選択して投げて出た目を観測する操作と，その生起確率に関するトレリス表現である．トレリス表現に現れる各ノードの x にはサイコロ Di の選択される確率が入り，y にはそのとき指定された偶数
または奇数の目が出る確率が入る．図 2 では偶数が指定されている．1 回目に各サイコロが選択される確率が ρ1 = ρ2 = 0.3，ρ3 = 0.4 であるときの図中の（コ）∼（ソ）に対応する確率を解答欄の（コ）∼（ソ）に記入せよ．
これより，1 回目にいずれかのサイコロが選択されて出た目が偶数となる確率が求まる．その確率を解答欄の（タ）に記入せよ．

— 4 —問 3 問 2 の結果に続けて，1 回目にサイコロの出た目が偶数になり，2 回目にサイコロの出た目が奇数になる確率を求めたい．このとき，図 3 の（チ）∼（ニ）に対応する各サイコロが選択される確率と奇数の目が出る確率を求めて，解答欄の（チ）∼（ニ）に記入せよ．
これより，1 回目に出た目が偶数，2 回目に出た目が奇数になる確率を求め解答欄の（ヌ）に記入せよ．

図3

1 回目に出た目が偶数，2 回目に出た目が奇数になる確率

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

I 長さ n の文字列 s から長さ m のパターン文字列 p （ただし n > m とする）が最初に出現する位置を求める文字列検索の C 言語を用いたプログラムについて，以下の問いに答えよ．（配点 50 点）
問 1 単純な方法として，下記の線形探索の関数 search を記述した．この関数は，
長さ n の文字列 s，長さ m のパターン文字列 p を受け取り，まず s の先頭のm 文字を最初の照合範囲として選ぶ．そして，照合範囲の文字列と p を先頭から順に比較し，一致しなければ照合範囲を 1 文字後ろにずらすという処理を，p と同一の文字列が見つかるか s の終端に到達するまで最大 n−m+1 回くり返す．

（1） プログラム中の空欄（ア）〜（ウ）に入る適切な式をそれぞれ答えよ．
（2） search("JUST_FOR_FUN", "FUN") を実行したとき，9 行目と 10 行目はそれぞれ何回実行されるかを答えよ．

— 6 —問 2 問 1 の関数 search において，s が p を含まない場合の時間計算量を考える．
（1） s が同一の文字 'A' の並び，すなわち s[0]=s[1]=· · ·=s[n-1]= 'A' であるとき，関数の時間計算量が最良，最悪となる p の例として，長さ m=4であるものをそれぞれ一つ答えよ．
（2） 最良時間計算量，最悪時間計算量として適当なものをそれぞれオーダー記
法で答えよ．
問 3 検索の最良時間計算量を改善するために，パターンを末尾から比較することを考える．たとえば，文字列 s が "JUST_FOR_FUN"，パターン文字列 p が"FUN" の場合，次のように照合範囲を移動することができる．


最初の照合範囲は s の先頭の "JUS" である．照合範囲の文字列と，p の末尾から比較を行う．'N' と 'S' が一致しないことから，照合範囲の文字列はp とは異なることがわかる．'S' が p に含まれていないことから，照合範
囲を 3 文字進められる．


2 番目の照合範囲は "T_F" となる．照合範囲の末尾にある 'F' と p の末尾の 'N' が一致しないことから，照合範囲の文字列は p とは異なることがわ
かる．p の先頭が 'F' であることから，次の照合範囲は 2 文字進めて，p の
先頭の 'F' を "T_F" の末尾の 'F' に合わせられる．

このように，照合範囲の末尾の文字 c に応じて照合範囲を進める文字数が関数

shift(c, p) で求められるとする．shift(c, p) の値は， p に含まれる文字が c と一致する場合はその位置を c に合わせるための文字数であり，それ以外の文字の場合は（p が c と一致することはないため）p の長さ m となる．たとえば p が "FUN" である場合は，以下のようになる．


shift('F', "FUN")=2



shift('U', "FUN")=1



shift(それ以外の文字, "FUN")=3

この考えをもとに関数 search2 を記述した．ただし，空欄 (ア)，(イ) の内容
はプログラム 1 の (ア)，(イ) とそれぞれ同じ式が入ることとする．

— 7 —この関数において，shift(c, p) は定数時間であるとして，文字列 s が p を含まない場合の時間計算量を考える．

(1) s が n 個の 'A' の並びである場合に，関数 search2 の時間計算量が最良，最悪となるような p の例として，長さ m=4 であるようなものをそれぞれ一つ答
えよ．

(2) 最良時間計算量，最悪時間計算量として適当なものをそれぞれオーダー記
法で答えよ．

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