京都大学情報学研究科知能情報学専攻 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$ とする。

题目描述

对下列 $f(n)$ $f (n)$ ，给出最简洁的渐近上界 $g(n)$ $g (n)$ 使 $f(n)=O(g(n))$ $f (n) = O (g (n))$ ：
1. $5\log n+2(\log n)^3+3n^3$ ；
2. $n\log n+10n^2+100n$ ；
3. $4n!+2n^n+8n\log n$ 。
用栈机器计算 $((5-3)*2)+((7-4)/(2+1))$ $((5 - 3) * 2) + ((7 - 4) / (2 + 1))$ 。
1. 画表达式树；
2. 写逆波兰式；
3. 写出递归遍历表达式树并输出逆波兰式的伪代码；
4. 图示直到求值完成的栈变化。
设 $A=\{a_1,\ldots,a_n\}$ $A = {a_{1}, \dots, a_{n}}$ 为互异正整数集， $s\ge0$ $s \geq 0$ 。令 $d(i,j)$ $d (i, j)$ 为 $A_i=\{a_1,\ldots,a_i\}$ $A_{i} = {a_{1}, \dots, a_{i}}$ 中元素和为 $j$ $j$ 的子集个数。
1. 对 $A=\{10,3,6,13,11,4\}$ ，求 $d(4,16)$ 、 $d(6,20)$ ，并列出相应全部子集。
2. 用若干 $d(i-1,k)$ 表示 $d(i,j)$ ；约定 $d(0,0)=1$ 、 $d(0,j)=0$ （ $j>0$ ）。

Kai

設問1

(1) $g(n) = n^3$
(2) $g(n) = n^2$
(3) $g(n) = n^n$

設問2

(1)

expression-tree

(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)

設問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}

Author​

Description​

設問1​

設問2​

設問3​

题目描述​

Kai​

設問1​

設問2​

(1)​

(2)​

(3)​

(4)​