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

Author

zephyr

Description

Ordered binary trees are trees in which each node has at most two ordered children. Below, denotes the set of all the ordered binary trees with leaves. Let denote the depth of node in an ordered binary tree , i.e., the number of edges on the path from the root to .

For a sequence of positive real numbers, we define and by:

For an ordered binary tree , we define by:

where is the -th leaf from left in .

Answer the following questions.

(1) Give the tree that has the smallest value of in case .

(2) Show that holds for any ordered binary tree with leaves .

(3) Assume that range over the set of positive real numbers so that . Show that is maximized when for any sequence of positive real numbers.

(4) Show that any ordered binary tree satisfies for any sequence of positive real numbers.

---

有序二叉树是指每个节点最多有两个有序子节点的树。下面， 表示具有 叶节点的所有有序二叉树的集合。设 表示有序二叉树 中节点 的深度，即从根到 的路径上的边数。

对于一个由 个正实数组成的序列 ，我们定义 和 如下：

对于一个有序二叉树 ，我们定义 如下：

其中 是 中从左数的第 个叶节点。

回答以下问题。

(1) 给出在 情况下 中 最小的树 。

(2) 证明对于任何有叶节点 的有序二叉树 ， 成立。

(3) 假设 在正实数范围内变化，并且满足 。证明对于任何由 个正实数组成的序列 ，当 时， 取得最大值。

(4) 证明对于任何有序二叉树 ，对于任何由 个正实数组成的序列 ，。

Kai

(1)

To minimize , 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 .

Steps to construct the tree:

1. Start by pairing the two smallest weights, which are both .
2. Combine these to form a subtree with a combined weight of .
3. Now, we have weights .
4. Next, combine the two smallest remaining weights, which are both .
5. Combine these to form a subtree with a combined weight of .
6. Finally, combine the two subtrees 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:

• , depth
• , depth
• , depth
• , depth

Now, we calculate :

Thus, the tree that minimizes has the above structure.

(2)

To prove the inequality using mathematical induction, we need to follow these steps:

1. Base Case
2. Inductive Step

Base Case: For (a tree with only one leaf), the depth of the only leaf is 0.

Thus, the base case holds.

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

Now, we need to prove that the inequality holds for an ordered binary tree with leaves.

1. Consider an ordered binary tree with leaves.
2. Let's denote the depth of the leaves in this tree by .

When we add an additional leaf to a tree with leaves to form a tree with leaves, we must split one of the existing leaves into two children. This operation increases the depth of the affected leaf by 1 and adds a new leaf with the same depth.

Suppose we split the leaf (where ) into two new leaves and , both at depth .

Thus, we need to show:

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

In the new tree:

Since :

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

By induction, the inequality holds for all .

(3)

To maximize under the constraint , we use the method of Lagrange multipliers.

Define the Lagrangian:

Take the partial derivatives and set them to zero:

Using the constraint :

Thus, the maximizing is:

(4)

To show that , we need to use the definitions of and and employ some fundamental principles of information theory and entropy.

Recall:

We start by rewriting in a more convenient form:

Since , we get:

Next, consider the following inequality derived from Jensen's inequality for the concave function :

This simplifies to:

Since , we get:

So:

The weighted path length can be understood using Kraft's inequality, which relates the depths of leaves in a binary tree to probabilities that sum up to 1. Let be the probability associated with the -th leaf. According to Kraft's inequality:

We multiply both sides by :

Using the fact that :

Now, we apply the definition of entropy:

Using Gibbs' inequality, we know that:

Multiplying both sides by :

Substituting into the inequality:

Thus, we have shown that for any ordered binary tree and any sequence of 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