急2021年度10月期入学／2022年度4月期入学
京都大学大学院情報学研究科
修士課程知能情報学専攻入学者選抜試験問題（情報学基礎）2021年7月31日9:00,...,_,11:00【注意】1.
問題冊子はこの表紙を含めて11 枚ある。
2.
試験開始の合図があるまで中を見てはいけない。
3.
囀開始後、枚数を鵬訊、落丁または印刷の不鮮明なものがあれば直ちに申し出ること。
4.
問題は日本語と英語の両方で出題されている。すべて解答しなさい。
ーFl-1,Fl-2
線形代数、微分積分 …… … …… ……… •1-4ペ ジ
アルゴリズムとデータ構造••……………•5-10ペー ジ
F2-l,F2-2
5.
6.

特に指定のない限り、日本語または英語で解答すること。
解答用紙に記載されている注意事項についても留意すること。
The Japanese version of this document is the prevailing and authoritative version;
the English translation be low is provided for reference only

October 2021 Admissions / April 2022 Admissions
Entrance Examination for Master's Program
Department of Intelligence Science and Technology
Graduate School of Informatics, Kyoto University(Fundamentals of Informatics)
July31, 2021
9:00 -11:00
NOTES
1.
This is the Question Booklet in 11 pages including this front cover.
2.
Do not open the booklet until you are instructed to start.
After the examination has started, check the number ofpages and notify proctors(professors) immediately ifyou
3.
find missing pages or unclear printings.
4.
Questions are written in Japanese and English. Answer all the questions.
Fl-1,Fl-2
Linear Algebra, Calculus·…………… …••Pages 1 to 4
F2-l,F2-2
Algorithms and Data Structures ………… •Pages 5 to 10
Write your answer in Japanese or English, unless otherwise specified.
5.
Read carefully the notes on the Answer Sheets as well.
6.

＆｀

修士課程

情報学基礎

l問題番号| F1-1 |【線形代数、 微分積分】

Fl-1 、 Fl-2、 F2-l、 F2-2 それぞれ別の 解答用紙を用いて解答すること。
設問1以下で定義される実行列AとB、および実数ベクトルXに関して、 以下の問いに答
えよここで、II叫はXの長さを表す。
A=(J -1)

B=(� �)x=(：、�)llxll > o(1) 心を求めよ。

(2) A-1を求めよ。
(3) Al5 を求めよ。

II(4) lim ll(AB）丘 を求めよ。ここで、nは自然数とする。
n→ OO

設問2 m x n (m >n)の実行列Aと以下で定義される行列BとCを考える。 ここで、Tは転置を表すもの とする。また、内積〈a, b 〉を以下で定義する。ここで、aと b はl次元ベクト
ル、ak、はaのK番目の要素、似はbのK番目の要素とする。
B=ATA

C=AAT

〈a, b 〉＝こ叫kk=l以下の問いに答えよ。必要であれば、実対称行列に関する以下の性質を使用せよ。
。実対称行列の固有値は全て実数である。
。実対称行列のどの固有値に 対しても、実ベクトルからなる固有ベクトルをとることができる。
(1) B と C がともに実対称行列であることを示せ。
(2) Bの 全ての固有値が非負であることを示せ。

(3) 実対称行列は直交行列で対角化できる。 B を対角化する直交行列の列ベクトルはいずれもBの固有ベクトルである。これらのうち正の固有値入i，入に対応する1]［il有ベクトルをPi,J

11Pjとし 、qiとqjをqi= i'f=A--i=f==Apjで与えられるベクトルとする。
''J:'piとqj=O - '1:J.J):;｛゜Aqi,qjがCの固有ベクトルであって対応する固有値はそれぞれ心朽であること、および〈qi,qり＝1(i#j）であることを示せ。また、Pi= 」-A況であることを示せ。
/(i = j)Master's
Question
Fundamentals[Linear Algebra, Calculus]
F1-l
ProgramofInformatics
I Number
Question is tra11slated in English in the section below: this translation is given for reference onl),|F2-L and F2-2.

Use one answer sheet for each of F1-1

Q.1 Answer the following questions about real matrices A and B、and a real vector x defined asfollows, where llxll denotes the length of a入A=(1) Calculate A3 .

(J -�)

B=(��)

X= (:�)佃11 > o(2) Calculate A-1.
(3) Calculate A旦(4) Calculate lilll ||（AB) 1) 叫 I, where n is a natural number.
n→ OO

Q.2 Let A be an m x n (m > n) real matrix. Let B and C be matrices defined as follows. Here, T
denotes the matrix transpose. We define an inner product〈a,b〉 as follows, where a and b are
l-dimensional vectors, a,.、 is the k-th element of a, and b,.. is the k-th element of b.
B =AT A

C=AAT〈a,b〉=＼ 叫k｀J

k=lAnswer the following questions. Use the following properties of a real symmetric matrix, ifneeded.
。All eigenvalues of a real symmetric matrix are real.

• For any eigenvalue of a real symmetric matrix, we can choose an eigenvector to be a realvector.

(1)Prove that both matrices B and C are real symmetric matrices.
(2)Prove that all the eigenvalues of B are non-negative.

(3) A real symmetric matrix can be diagonalized using an orthogonal matrix. All column vectorsof an orthogonal matrix with which B is diagonalized are eigenvectors of B. Among theseeigenvectors, let Pi and Pj be eigenvectors corresponding to positive eigenvalues入and心respectively, and let qi and % be vectors given by qi = �APi and qj = -if=Apj.

喜/Prove that qi and qj are eigenvectors of C corresponding to eigenvalues /\ and心respectively,and that〈Oi、q] ＝｛°l(tヂ．］）Prove also that Pi - *バqか(i =．7）
喜修士課程情報学基礎【線形代数、微分積分】

I問題番号| F1—2 |Fl-I、Fl-2、 F2-1、 F2-2それぞれ別の解答用紙を用いて解答すること。
設問1 以下の問いに答えよ。
(1)以下の関数について、 導関数をyのみを用いて表せ。 また、その導関数の値域を示せ。
A)y= f(x) = 1+exp(-X)B)y = f(x) = exp(x)+exp(-x)
exp(x)-exp(-x)(2)丑＋炉ー1=0及び〇:S x,y:S 1の条件の下、f(x,y)＝企＋2炉の極値を求めよ。
設問2 地面に直立した半径1［叫の円筒がある。 ヤギの首に長さ吋叫の伸び縮みしないヒモが結び付けられている。 このヒモのもう 一 端は円筒表面の一 点（首と同じ高さ）に結び付けられている。
(1)円筒の中心軸を原点とし、 ヒモの結び付けられている円筒上の点を(-1,0)とする2次元座標系を地面上で考えたとき、 Xミーl,y 2: 0において、 ヤギがヒモをたるませずに立っているときの2次元座標をx軸からの角度0を用いて表せ。
(2)このヤギがヒモをたるませずに円筒周りを 一周したとき、その総移動距離を求めよ。
(3)このヤギが歩き回れる地面の面積を求めよ。

3te［Linear Algebra, Calculus]：;：
ndf□i悶ば：r ;;悶；Question
LJ需芯：ビ戸
is translated in English in the section below; this translation is given for reference only.
Use one answer sheet for each of Fl-1, Fl-2, F2-1, and F2-2 .
Q.1Answer the following questions.

(1) Express the derivative function for each of the following functions using only y and show

the range of the derivative function.
A) y = f(x) = l+exp(- x)exp(x)-exp(-x)
B) y = f （叫＝ exp(X)＋exp(-X)(2) Compute the extrema of f(x,y)＝砂＋ 2炉when丑＋炉ー1 = 0 and O ::::; x,y ::::; 1.
Q.2

A cylinder of l[m] radius is erected perpendicularly on the ground. A goat is on a leashof 1r[m] that neither stretches nor compresses. The other end of the leash is tied to a surface

point of the cylinder at the same height.

(1) Consider a two-dimensional coordinate frame with its origin at the center axis of thecylinder and where the point of attachment of the leash on the cylinder is (-1, 0). Using angle
0 from the x axis, express the 2D coordinates of the goat when she is standing without any

slack to the leash for x �ー1,y � 0.

(2) Derive the total distance the goat would travel when going around the cylinder once without

any slack to the leash.

(3) Derive the total area of the ground the goat can cover.

4修士課程情報学基礎【アルゴリズムとデ ー タ構造】—

1問題番号| F2 1 |Fl -I、Fl —2、 F2-l 、 F2—2 それぞれ別の解答用紙を用いて 解答すること。
設問1 整数の集合 Aの要素の小さい方からK番目(k � 1) の要素の値を返す関数
SelectKth(A,k) を考える。例えば、A = {5,1,7 }およびk = 2の場合、SelectKth(A,k)
は5を出力する。 今、p := PivotSelect(A)はAに含まれる要素のうち 一 つをランダムに返す関数とし、(L,R) :=Partition(A,p)は集合Aをp以下の値で構成される集合Lとpより大きい値で構成される集合Rに分割する関数とする。例えば、A={5,l,7}およびp=5の場合、(L,R) :=Partition(A,p)のLおよびRはそれぞれ、L={5,1}、R={7} となる。
また、Remove(A,p)は集合Aから要素 pを削除する関数とする。例えば、A={5,l,7}およびp=7の場合、Remove(A,p)はAを{5,1}にする。!X I は集合Xの要素数とし、Aのすべての要素は異なるとする。
Algorithm 1SelectKth(A,k). Find the k-th smallest element in A.
function SelectKth(A, k):p := PivotSelect(A)(L,R) := Partition(A, p)if□己□ thenreturn p
end ififthenif!RI = 0 thenRemove(L,p)
end ifreturn SelectKth(L, �
end if［阿□if□阿□ thenreturn SelectKth(R,end if

邑〗(1)Algorithm 1はSelectKth 関数の疑似コ ー ドである。Algorithm Iの(a)-(e )を埋めよ。
(2) A
I I =nの場合のPartition(A,p)、Remove(L,p)、PivotSelect(A)の要素の比較回数をそれぞれO(n)、O(n)、および0(1) とする。Algorithm!の平均比較回数をオ ー ダ ー 表記で答えよ。
（次のペ ー ジに続く）

5

修士課程

情報学基礎

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

1問題番号| F2—1|

Fl-l、Fl-2 、 F2 -l、 F2—2 それぞれ別の 解答 用紙を用いて解答すること。
設問2 4つのリストを用いた外部 ハ ッシュ法につ いて以下の問いに答えよ。キ ーは0,1,2のいずれかの整数 が4つ並んだパター ンs終3S焚1,Bi E{01, ,2}で与えられる。また 以下において、modは割り算の余りを出力する演算子を示す。
(1) 表lは、ハ ッシュ関数（Li= l 3iーぶ） mod4を用いて、キ ー 0100, 1211を順に挿入した後のデータ構造を模式的に表している。この状態に追加で0010, 2101, 1222, 1111を順に挿入した後のデータ構造を表lに倣って図示せよ。

(2) k個の 要素で構成されるリストに、新たに要素を1つ 追加 するのに要する コストをck(cは正の 実定数）とする。 表2に示す確率分布に従って独立に生起する複数個のキ ーをハ ッシュ法を用いて順に挿入していくとき 、挿入コストの期待値が最小となるキ ーと ハ ッ
シュ値の対応付けをその理由とともに示せ。対応付けは表2における(a),(b),(c),(d)を埋める形で解答せよ。
(3)(2)で求めた対応付けを（ Li=la肉＋a歪1的＋a終3紅）mod4なる ハ ッシュ関数で実現するときのa1,a2心3,a4,a5心6を導出せよ。

表lインデックス
リスト

゜120100→1211

キー

表2
生起確率

ハ ッシュ値

0210

0.20

(b)

1101

0.15

10100

101031111

2101

0.10
0.15

0.25
0.15(a)゜(c)(d)

6

t er

1
[Algori thms nd Da t S tructur es]
df0=i悶�:悶；Question is:m�translated in English in the section below; this translation is given for reference only.
Sra; laa

Use one answer sheet for each of F l -IaF2-1, and F2—2.

Q.1 We consider a function SelectKth(A, k) which returns the k-th (k;::: 1) smallest element ina set A whose elements are integers. For example, in A= {5, 1, 7} and k = 2, SelectKth(A, k)

returns 5. Now, we define a function p := PivotSelect(A) which returns a random element of A,

and we define a function (L, R) := Partition(A, p) that divides a set A into a set Lconsisting ofelements less than or equal to p and a set R consisting of elements greater than JJ. For example,in A = {5, 1 , 7} with p = 5, Land R of (L, R) := Partition(A,p) are given as L= {5, l} andR = {7}, respectively. We also define a function Remove(A , p ) that removes the element p inthe set A. For example, in A= {5, 1, 7} with p= 7, Remove(A,JJ) changes A to {5, l}. Notethat we denote IX I as the number of elements in the set X, and assume all elements of the set A
are different.

Algorithm 1 SelectKth(A , k). Find the k-th smallest element in A.
function SelectKth(A, k):p := PivotSelect(A)(L, R) := Partition(A, p)
if

return pthenend ifif

□阿□ thenif IRI = 0 thenRemove(L,p)

end if，圧return SelectKth(Lend ifif

□阿□ thenreturn SelectKth(Rend if，尺り(1) AlgorithmI is a pseudo code of the SelectKth function. Fill (a)ー(e) in Algorithm I.
(2) For IAI = n, we assume that the number of element comparisons of Partition(A,p),Remove(L,p), and PivotSe!ect(A) are O(n), O(n), and 0(1), respectively. Answer the ex­pected number of comparisons in Algorithm I by big-0 notation.

(continued on the next page)7

—Master's
Question
Fundamentals[Algorithms and Data Structures]
F2 1
ProgramNumberof Informatics
Question is translated in English in the section below; this translation is givenfoi;,��Y-—

Use one answer sheet for each of F l-1, F l-2, F2-1, and F2 2.
Q.2 Answer the following questions about a hashing with 4 linked lists based on a separated
chaining method. A key is given as a sequence of 4 integer numbers s4s3s 焚1, Si E {O, 1, 2}.
mod indicates an operator that derives a remainder of division.
i 1(1) Consider a hash function;=1 3 - si) mod 4. Table 1 shows the data structure after（こkeys 0010 and 1211 are sequentially inserted to an empty state. Draw the data structure after
0010, 2101, 1222, and 1111 are additionally inserted in this order.
(2) Assume that it takes a cost ck for adding a new record to a list containing k records, where cis a positive constant. Consider sequentially inserting keys that independently occur following
the probability distribution shown in Table 2. Show the correspondences between keys andhash values that minimize the expected cost taken for inserting a key, and explain its reasons.
The con-espondences must be answered by filling (a), (b), (c) and (d) in Table 2.
(3) Derive a1, a2, a3, a4, a5, a5 in a hash function（こい a凶＋a5s1s2 + a5s3s4) mod 4 that

achieves the correspondences answered in the previous question.

゜indexI

Table 1
list
0100→1211

key

Table 2
probability hash value

0100

0.10(a)0210

0.20(b)

1010

0.15

゜2

1101

0.15

13

1111

0.25

(c)

2101

0.15

(d)

設問2 (Q.2) の小問(1)の英語版の本文中において、以下の誤植がありました。
（誤）0010 and 1211
（正）0100 and 1211
なお、日本語版には誤りはありませんでした。
The description of problem (1) of Q.2 in English contained the following
typographical error.
(Error) 0010 and 1211
(Correct) 0100 and 1211
The corresponding problem description in Japanese did not have anyerrors.

8

修士課程

情報学基礎

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

I問題番号| F2-2|

Fl-1、Fl-2、F2-1、F2-2それぞれ別の解答用紙を用い て解答すること。
ナップサック問題の入力は、非負整数の容量 cを持つナップサックと 、n個のアイテム釘，aか．．．，an からなる。各アイテムaiは正整数の重さ叫（::; c)と 正整数の価値Piを持つ。
アイテムの集合Sの合計重さと合計価値は、 それぞれSに含まれるアイテムの重さの総和 、 価値の総和と 定義する。ナップサックには、 合計重さc以下のアイテム集合を詰め込むことができる。ナップサックに詰め込むことのできるアイテム集合のうち合計価値が最大となるものをその入力に対する最適解 、 最適解の合計価値をその入力に対する最適値と呼ぶ。
n= 6, C = 10で、 アイテムが以下の表で与えられる入力をIとする。

（3:；／/ I 〗 1: I 〗 1 : I ; I

6:

設問1入力Iに対する最適値と 、 全ての最適解を答えよ。
設問2アイテムを単位重さ当たりの価値が大 きい順に「ナップサックに入れることができれば入れ 、 できなければ捨てる」という逐次処理をし、 最後にナップサックに入っているアイテム集合を出力するアルゴリズムを考える。 ただし、 単位重さ当たりの価値が同じアイテムが複数 あれば 、 価値の高いものを先に処理する。入力Iにこのアルゴリズムを適用させ た場合の出力を答えよ。
設問3 n :s; 4、c=10で、設問2のアルゴリズムが出力するアイテム集合の合計価値が最適値の5倍以上悪く（小さく）なる入力例を1つ示せ。ま た 、 最適解とアルゴリズムの出力を示すことにより 、 その答えが設問の要件を満たしていることを説明せよ。
設問4 1 S: i S: n, 0 :'S j :'S C を満たす整数i,jに対し、アイテムがa1,... ,aiでナップサック

容量がjである部分問題の最適値をOPT(i,j)とする。上記の入力Iに対してOPT(l,1)、OPT(2,4)、OPT(3,5)の値を答えよ。
設問5設問4で定義したOPT(i,j)をiやjの値が小さいものから順に計算していくアルゴリズムを考える。以下の問いに答えよ。なお本設問は、 上記の具体的な入力Iに対してではなく 一 般の入力に対する問いであるので注意すること。
(1 ) OPT(i, 0)の値を答えよ。
(2) OPT(l,j)の値を答えよ。
(3) i 2: 2, j 2: 1 とし、1 S: a S: i -1, 0 S: b S: jおよびa= i, 0 S: b :S j -lを満たす全てのa, b につい てOPT(a,b)が求まっているとする。この と きOPT(i,j)を求める
計算方法を答えよ。

，

ざMaster's
Fundamentals
Question[Algorithms and Data Structures]
ProgramofInformatics
い竺唖巴」戸
Question is translated in English in the section below; this translation is given for reference only.
Use one answer sheet for each of F l -1, F l ー2, F2- l , and F2—2.
An input of the knapsack problem consists of a knapsack with a nonnegative integer c, called
the capacity, and n items a1,a2,...,an . Each item ai has a positive integer Wi（::; c), called theweight, and a positive integer pゎcalled the profit. The total weight and the total profit of a set ofitems S are defined as the sum of the weights and the sum of the profits, respectively, of all theitems in S. A set of items whose total weight is at most c can be packed into the knapsack. A setof items with the maximum total profit that can be packed into the knapsack is called an optimal
solution of the input, and the total profit of an optimal solution is called the optimal value of theinput.

I〗 1: I ：I: I

Let I be the input with n = 6 and c = 10, where items are given in the following table.
3t:：：：p：〗 |6:

Q.1 Show the optimal value and all the optimal solutions of the input I.
Q.2 Consider the following algorithm: sequentially process items in a non-increasing order ofthe profit per unit weight. When processing an item, put it into the knapsack if possible, anddiscard it otherwise. Finally, output the set of items in the knapsack. If there are two or more
items with the same profit per unit weight, process the one with the largest profit first. Show theoutput when this algorithm is applied to the input I.
Q.3 Show an input with n :S 4 and c = 10, where the total profit of the output of the algorithm
defined in Q.2 is at least 5 times worse (smaller) than the optimal value. Also, explain why youranswer meets the condition of this question by showing an optimal solution and the output ofthe algorithm.
Q.4 For integers i and j such that 1さi :Sn and 0こj :S c, let OPT(i,j) be the optimal valueof the restricted input where items are a1,. .. ,ai and the capacity of the knapsack is j. Show
OPT(l,1), OPT(2,4), and OPT(3,5) for the above input I.
Q.5 Consider an algorithm that computes OPT(i,j) defined in Q.4 from those for smaller iand j. Answer the following questions. Note that these questions are not for the specific input I
defined above but for general inputs.
(1) Show OPT(i,O).
(2) Show OPT(l,j).
(3) Let i ?: 2 and j ?: 1, and assume that OPT(a,b) is already computed for all a and b suchthat 1 � a � i - l, 0 � b � j and a = i, 0 � b � j - l. Show how to compute
OPT(i,j).

10