東京大学 情報理工学系研究科 コンピュータ科学専攻 2021年2月実施 問題1

标签：

• Tokyo-University
• Optimal-Alphabetic-Binary-Tree
• Kraft-Inequality-for-Binary-Trees
• Entropy-Lower-Bound-on-Weighted-External-Path-Length

Author

zephyr, 祭音Myyura

Description

Ordered binary trees are trees in which each node has at most two ordered children. Below, $\mathbf{T_n}$ denotes the set of all the ordered binary trees with $n$ leaves. Let $\mathrm{d_T}(v)$ denote the depth of node $v$ in an ordered binary tree $T$, i.e., the number of edges on the path from the root to $v$.

For a sequence $\mathbf{P} = (c_1, c_2, \ldots, c_n)$ of $n$ positive real numbers, we define $\mathbf{S_P}$ and $\mathbf{H_P}$ by:

$$\mathbf{S_P} = \sum_{i=1}^{n} c_i, \quad \mathbf{H_P} = - \sum_{i=1}^{n} (c_i \cdot \log_2(c_i/\mathbf{S_P})).$$

For an ordered binary tree $T \in \mathbf{T_n}$, we define $\mathbf{W_P}(T)$ by:

$$\mathbf{W_P}(T) = \sum_{i=1}^{n} (c_i \cdot \mathrm{d_T}(v_i)),$$

where $v_i$ is the $i$-th leaf from left in $T$.

Answer the following questions.

(1) Give the tree $T \in \mathbf{T_4}$ that has the smallest value of $\mathbf{W_P}(T)$ in case $\mathbf{P} = (4, 2, 1, 1)$.

(2) Show that $\sum_{i=1}^{n} 2^{-\mathrm{d_T}(v_i)} \leq 1$ holds for any ordered binary tree $T \in \mathbf{T_n}$ with leaves $v_1, v_2, \ldots, v_n$.

(3) Assume that $x_1, x_2, \ldots, x_n$ range over the set of positive real numbers so that $\sum_{i=1}^{n} x_i = 1$. Show that $\sum_{i=1}^{n} (c_i \cdot \log_2 x_i)$ is maximized when $x_i = c_i/\mathbf{S_P}$ for any sequence $\mathbf{P} = (c_1, c_2, \ldots, c_n)$ of $n$ positive real numbers.

(4) Show that any ordered binary tree $T \in \mathbf{T_n}$ satisfies $\mathbf{W_P}(T) \geq \mathbf{H_P}$ for any sequence $\mathbf{P} = (c_1, c_2, \ldots, c_n)$ of $n$ positive real numbers.

---

有序二叉树是指每个节点最多有两个有序子节点的树。下面，$\mathbf{T_n}$ 表示具有 $n$ 叶节点的所有有序二叉树的集合。设 $\mathrm{d_T}(v)$ 表示有序二叉树 $T$ 中节点 $v$ 的深度，即从根到 $v$ 的路径上的边数。

对于一个由 $n$ 个正实数组成的序列 $\mathbf{P} = (c_1, c_2, \ldots, c_n)$，我们定义 $\mathbf{S_P}$ 和 $\mathbf{H_P}$ 如下：

$$\mathbf{S_P} = \sum_{i=1}^{n} c_i, \quad \mathbf{H_P} = - \sum_{i=1}^{n} (c_i \cdot \log_2(c_i/\mathbf{S_P})).$$

对于一个有序二叉树 $T \in \mathbf{T_n}$，我们定义 $\mathbf{W_P}(T)$ 如下：

$$\mathbf{W_P}(T) = \sum_{i=1}^{n} (c_i \cdot \mathrm{d_T}(v_i)),$$

其中 $v_i$ 是 $T$ 中从左数的第 $i$ 个叶节点。

回答以下问题。

(1) 给出在 $\mathbf{P} = (4, 2, 1, 1)$ 情况下 $\mathbf{T_4}$ 中 $\mathbf{W_P}(T)$ 最小的树 $T$。

(2) 证明对于任何有叶节点 $v_1, v_2, \ldots, v_n$ 的有序二叉树 $T \in \mathbf{T_n}$，$\sum_{i=1}^{n} 2^{-\mathrm{d_T}(v_i)} \leq 1$ 成立。

(3) 假设 $x_1, x_2, \ldots, x_n$ 在正实数范围内变化，并且满足 $\sum_{i=1}^{n} x_i = 1$。证明对于任何由 $n$ 个正实数组成的序列 $\mathbf{P} = (c_1, c_2, \ldots, c_n)$，当 $x_i = c_i/\mathbf{S_P}$ 时，$\sum_{i=1}^{n} (c_i \cdot \log_2 x_i)$ 取得最大值。

(4) 证明对于任何有序二叉树 $T \in \mathbf{T_n}$，对于任何由 $n$ 个正实数组成的序列 $\mathbf{P} = (c_1, c_2, \ldots, c_n)$，$\mathbf{W_P}(T) \geq \mathbf{H_P}$。

题目描述

有序二叉树的每个结点至多有两个有次序的子结点。记 $T_n$ 为具有 $n$ 个叶结点的所有有序二叉树的集合，$d_T(v)$ 为结点 $v$ 在树 $T$ 中的深度，即根到 $v$ 的路径所含边数。对 $n$ 个正数组成的序列 $P=(c_1,\ldots,c_n)$，定义

$$S_P=\sum_{i=1}^n c_i,\qquad H_P=-\sum_{i=1}^n c_i\log_2(c_i/S_P).$$

对 $T\in T_n$，若 $v_i$ 是从左到右第 $i$ 个叶结点，定义

$$W_P(T)=\sum_{i=1}^n c_i\,d_T(v_i).$$

回答下列问题。

（1）当 $P=(4,2,1,1)$ 时，给出使 $W_P(T)$ 最小的 $T\in T_4$。

（2）证明对任意具有叶结点 $v_1,\ldots,v_n$ 的 $T\in T_n$，

$$\sum_{i=1}^n2^{-d_T(v_i)}\le1.$$

（3）令正数 $x_1,\ldots,x_n$ 满足 $\sum_i x_i=1$。证明对任意正数序列 $P=(c_1,\ldots,c_n)$，当 $x_i=c_i/S_P$ 时，

$$\sum_{i=1}^n c_i\log_2x_i$$

达到最大值。

（4）证明对任意正数序列 $P$ 和任意 $T\in T_n$， $W_P(T)\ge H_P$。

Kai

(1)

To minimize $\mathbf{W_P}(T)$, we should construct a tree that resembles a Huffman tree, where the most frequent items (with the highest weights) are located at shallower depths. Here, the weights are $(4, 2, 1, 1)$.

Steps to construct the tree:

1. Start by pairing the two smallest weights, which are both $1$.
2. Combine these to form a subtree with a combined weight of $2$.
3. Now, we have weights $(4, 2, 2)$.
4. Next, combine the two smallest remaining weights, which are both $2$.
5. Combine these to form a subtree with a combined weight of $4$.
6. Finally, combine the two subtrees $(4, 4)$ to form the complete tree.

The resulting tree structure is:

      O
     / \
    4   O
       / \
      2   O
         / \
        1   1

Thus, the depth of each leaf in the tree is:

• $c_1 = 4$, depth $\mathrm{d_T}(v_1) = 1$
• $c_2 = 2$, depth $\mathrm{d_T}(v_2) = 2$
• $c_3 = 1$, depth $\mathrm{d_T}(v_3) = 3$
• $c_4 = 1$, depth $\mathrm{d_T}(v_4) = 3$

Now, we calculate $\mathbf{W_P}(T)$:

$$\mathbf{W_P}(T) = 4 \cdot 1 + 2 \cdot 2 + 1 \cdot 3 + 1 \cdot 3 = 4 + 4 + 3 + 3 = 14$$

Thus, the tree $T$ that minimizes $\mathbf{W_P}(T)$ has the above structure.

(2)

To prove the inequality $\sum_{i=1}^{n} 2^{-\mathrm{d_T}(v_i)} \leq 1$ using mathematical induction, we need to follow these steps:

1. Base Case
2. Inductive Step

First contract every node having exactly one child. This only decreases the depths of its descendant leaves, so it can only increase the sum. It therefore suffices to prove the result for full ordered binary trees, in which every internal node has two children.

Base Case: For $n = 1$ (a tree with only one leaf), the depth of the only leaf $v_1$ is 0.

$$\sum_{i=1}^{1} 2^{-\mathrm{d_T}(v_i)} = 2^{-\mathrm{d_T}(v_1)} = 2^0 = 1$$

Thus, the base case holds.

Inductive Step: Assume that for any full ordered binary tree with $k$ leaves, the inequality holds:

$$\sum_{i=1}^{k} 2^{-\mathrm{d_T}(v_i)} \leq 1$$

Now, we need to prove that the inequality holds for a full ordered binary tree with $k+1$ leaves.

1. Consider a full ordered binary tree with $k+1$ leaves.
2. Let's denote the depth of the leaves in this tree by $\mathrm{d_T}(v_1), \mathrm{d_T}(v_2), \ldots, \mathrm{d_T}(v_{k+1})$.

Every full tree with $k+1$ leaves contains two sibling leaves. Contracting such a pair produces a full tree with $k$ leaves; conversely, the original tree is obtained by splitting that contracted leaf into two children.

Suppose we split the leaf $v_j$ (where $\mathrm{d_T}(v_j) = d$) into two new leaves $v_j'$ and $v_{k+1}$, both at depth $d+1$.

Thus, we need to show:

$$\sum_{i=1}^{k} 2^{-\mathrm{d_T}(v_i)}-2^{-d} + 2^{-(d+1)} + 2^{-(d+1)} \leq 1$$

By the inductive hypothesis, for the original tree with $k$ leaves:

$$\sum_{i=1}^{k} 2^{-\mathrm{d_T}(v_i)} \leq 1$$

In the new tree:

$$\sum_{i=1}^{k} 2^{-\mathrm{d_T}(v_i)} - 2^{-d} + 2^{-(d+1)} + 2^{-(d+1)}$$

Since $2^{-(d+1)} + 2^{-(d+1)} = 2^{-d}$:

$$\sum_{i=1}^{k+1} 2^{-\mathrm{d_T}(v_i)} = \sum_{i=1}^{k} 2^{-\mathrm{d_T}(v_i)} \leq 1$$

Thus, the inequality holds after adding a new leaf and increasing the depth of the original leaf.

By induction, the inequality $\sum_{i=1}^{n} 2^{-\mathrm{d_T}(v_i)} \leq 1$ holds for all $n$.

(3)

To maximize $\sum_{i=1}^{n} (c_i \cdot \log_2 x_i)$ under the constraint $\sum_{i=1}^{n} x_i = 1$, we use the method of Lagrange multipliers.

Define the Lagrangian:

$$\mathcal{L}(x_1, \ldots, x_n, \lambda) = \sum_{i=1}^{n} (c_i \cdot \log_2 x_i) + \lambda \left( 1 - \sum_{i=1}^{n} x_i \right)$$

Take the partial derivatives and set them to zero:

$$\frac{\partial \mathcal{L}}{\partial x_i} = \frac{c_i}{x_i \ln 2} - \lambda = 0 \quad \Rightarrow \quad x_i = \frac{c_i}{\lambda \ln 2}$$

Using the constraint $\sum_{i=1}^{n} x_i = 1$:

$$\sum_{i=1}^{n} \frac{c_i}{\lambda \ln 2} = 1 \quad \Rightarrow \quad \lambda \ln 2 = \mathbf{S_P} \quad \Rightarrow \quad \lambda = \frac{\mathbf{S_P}}{\ln 2}$$

Thus, the maximizing $x_i$ is:

$$x_i = \frac{c_i}{\mathbf{S_P}}$$

Moreover, $\partial^2\mathcal L/\partial x_i^2=-c_i/(x_i^2\ln 2)<0$. Hence the objective is strictly concave on the constraint set, so this stationary point is the unique global maximum.

(4)

To show that $\mathbf{W_P}(T) \geq \mathbf{H_P}$, we need to use the definitions of $\mathbf{W_P}(T)$ and $\mathbf{H_P}$ and employ some fundamental principles of information theory and entropy.

Recall:

$$\mathbf{W_P}(T) = \sum_{i=1}^{n} (c_i \cdot \mathrm{d_T}(v_i))$$

$$\mathbf{H_P} = - \sum_{i=1}^{n} \left( c_i \cdot \log_2 \left(\frac{c_i}{\mathbf{S_P}}\right) \right)$$

We start by rewriting $\mathbf{H_P}$ in a more convenient form:

$$\mathbf{H_P} = \sum_{i=1}^{n} c_i \cdot \left( \log_2(\mathbf{S_P}) - \log_2(c_i) \right) = \log_2(\mathbf{S_P}) \cdot \sum_{i=1}^{n} c_i - \sum_{i=1}^{n} (c_i \cdot \log_2(c_i))$$

Since $\sum_{i=1}^{n} c_i = \mathbf{S_P}$, we get:

$$\mathbf{H_P} = \mathbf{S_P} \cdot \log_2(\mathbf{S_P}) - \sum_{i=1}^{n} (c_i \cdot \log_2(c_i))$$

Let

$$K=\sum_{i=1}^{n}2^{-\mathrm{d_T}(v_i)}\leq1, \qquad x_i=\frac{2^{-\mathrm{d_T}(v_i)}}{K}.$$

Then $x_i>0$ and $\sum_i x_i=1$. By question (3),

$$\sum_{i=1}^{n}c_i\log_2x_i \leq \sum_{i=1}^{n}c_i\log_2\frac{c_i}{\mathbf{S_P}} =-\mathbf{H_P}.$$

On the other hand,

$$\sum_{i=1}^{n}c_i\log_2x_i =-\mathbf{W_P}(T)-\mathbf{S_P}\log_2K \geq-\mathbf{W_P}(T),$$

because $K\leq1$. Therefore $-\mathbf{W_P}(T)\leq-\mathbf{H_P}$, or

$$\mathbf{W_P}(T)\geq\mathbf{H_P}.$$

Thus, we have shown that $\mathbf{W_P}(T) \geq \mathbf{H_P}$ for any ordered binary tree $T \in \mathbf{T_n}$ and any sequence $\mathbf{P} = (c_1, c_2, \ldots, c_n)$ of $n$ positive real numbers.

Knowledge

有序二叉树 哈夫曼树 信息论 拉格朗日乘数法 数学归纳法

重点词汇

• Ordered binary tree 有序二叉树
• Huffman tree 哈夫曼树
• Depth 深度
• Lagrange multipliers 拉格朗日乘子
• Entropy 熵
• Lagrange multiplier 拉格朗日乘数
• Jensen's inequality 詹森不等式
• Gibbs' inequality 吉布斯不等式
• Kraft's inequality 克拉夫特不等式

参考资料

1. Introduction to Algorithms, Chapter 16: Greedy Algorithms
2. Information Theory, Inference, and Learning Algorithms, David J.C. MacKay