京都大学 情報学研究科 知能情報学専攻 2022年8月実施 情報学基礎 F2-1

Author

Isidore, 祭音Myyura

Description

設問1

自然数 \(n\) の関数 \(f(n)\) に対するビッグオー記法 \(f(n)=O(g(n))\) を考える。 ここで、\(g(n)\) は自然数 \(n\) の関数である。以下に示す各 \(f(n)\) について、最も簡潔な形を持つ \(g(n)\) を答えよ。

(1) \(f(n) = 5 \log n + 2(\log n)^3 + 3n^3\)

(2) \(f(n) = n\log n + 10n^2 + 100n\)

(3) \(f(n) = 4n! + 2n^n + 8n \log n\)

設問2

スタックマシンを用いて計算式 \(((5-3)*2) + ((7-4)/(2+1))\) の値を求めることを考える。 ここで、「+」は加算、「-」は減算、「*」は乗算、「/」は除算を表す。 このとき、以下の問いに答えよ。

(1) 上記の計算式に対応する構文木を図示せよ。

(2) 上記の計算式に対応する逆ポーランド記法を示せ。

(3) 構文木を走査することで逆ポーランド記法出力する疑似コードを示せ。但し、再起呼び出しを用いるとこ。

(4) 上記の計算式の値を得るまでのスタックの変化を図示せよ。

設問3

互いに異なる \(n\) 個の正の整数の集合 \(A = \{a_1, a_2, \ldots, a_n}\) と非負の整数 \(s\) を考える。 正の整数 \(i \ (\leq n)\) および非負の整数 \(j \ (\leq s)\) について、\(d(i,j)\) は、\(A_i = \{a_1, a_2, \ldots, a_i\}\) の部分集合 \(A'_i\) であって、\(\sum_{a \in A'_i} a = j\) を満たすものの数を表すものとする。

(1) \(A = \{10, 3, 6, 13, 11, 4\}\) とする。\(d(4,16)\) と \(d(6,20)\)、また、それぞれに対して等式を満たす部分集合を全て求めよ。

(2) \(d(i,j)\) を、\(\{d(i-1,k)\}_{0 \leq k \leq j}\) のうちのいくつかを用いて表せ。但し、便宜上 \(d(0, 0)=1\), \(d(0,1)=0\), \(d(0,2)=0\), \(\ldots\), \(d(0,j)=0\) とする。

Kai

設問1

• (1) \(g(n) = n^3\)
• (2) \(g(n) = n^2\)
• (3) \(g(n) = n^n\)

設問2

(1)

(2)

\[ 5\;3-2*7\;4-2\;1+/+ \]

(3)

The answer is a Postorder Traversal for a binary tree:

outputRPN(node):
    if node->left_child is not Null then:
        outputRPN(node->left_child)
    if node->right_child is not Null then:
        outputRPN(node->right_child)
    output(node->value)

(4)

5
5 3
2
2 2
4
4 7
4 7 4
4 3
4 3 2
4 3 2 1
4 3 3
4 1
5

設問3

(1)

By definition we need to find subsets \(A'_4\) of \(A_4=\{10, 3, 6, 13\}\) that satisfy \(\sum_{a \in A'_4} a = 16\). Therefore, the answer is

\[ d(4,16) = 2, A'_4=\{10, 6\}, \{3, 13\} \]

Similarly, we have

\[ d(6, 20) = 3, A'_6=\{10, 6, 4\}, \{3, 13, 4\}, \{3, 6, 11\} \]

(2)

\[ d(i,j) = \begin{cases} d(i-1,j) + d(i-1,j-a_{i})&(a_{i}\leq j)\\ d(i-1,j)&(a_{i}>j) \end{cases} \]