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

标签：

• Kyoto-University
• Algorithm-Complexity
• Expression-Tree
• Reverse-Polish-Notation
• Postorder-Tree-Traversal
• Stack
• Subset-Sum-Problem
• Counting-Subset-Sum-Dynamic-Programming

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}$$