2021W

Problem 1

Ordered binary trees are trees in which each node has at most two ordered children. Below, ${\mathbf{T}}_{\mathbf{n}}$ denotes the set of all the ordered binary trees with $n$ leaves. Let ${\mathrm{d}}_{\mathrm{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,\dots ,c_n)$ of $n$ positive real numbers, we define ${\mathbf{S}}_{\mathbf{P}}$ and ${\mathbf{H}}_{\mathbf{P}}$ by:

$${\mathbf{S}}_{\mathbf{P}}=\sum _{i=1}^n{c}_i,{\mathbf{H}}_{\mathbf{P}}=-\sum _{i=1}^n(c_i\cdot {\log }_2(c_i/{\mathbf{S}}_{\mathbf{P}})).$$

For an ordered binary tree $T\in {\mathbf{T}}_{\mathbf{n}}$, we define ${\mathbf{W}}_{\mathbf{P}}(T)$ by:

$${\mathbf{W}}_{\mathbf{P}}(T)=\sum _{i=1}^n(c_i\cdot {\mathrm{d}}_{\mathrm{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}}_{\mathbf{P}}(T)$ in case $\mathbf{P}=(4,2,1,1)$.

2. Show that ${\sum }_{i=1}^n{2}^{-{\mathrm{d}}_{\mathrm{r}}(v_i)}\le 1$ holds for any ordered binary tree $T\in {\mathbf{T}}_{\mathbf{n}}$ with leaves $v_1,v_2,\dots ,v_n$.

3. Assume that $x_1,x_2,\dots ,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}}_{\mathbf{P}}$ for any sequence $\mathbf{P}=(c_1,c_2,\dots ,c_n)$ of $n$ positive real numbers.

4. Show that any ordered binary tree $T\in {\mathbf{T}}_{\mathbf{n}}$ satisfies ${\mathbf{W}}_{\mathbf{P}}(T)\ge {\mathbf{H}}_{\mathbf{P}}$ for any sequence $\mathbf{P}=(c_1,c_2,\dots ,c_n)$ of $n$ positive real numbers.

---

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

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

$${\mathbf{S}}_{\mathbf{P}}=\sum _{i=1}^n{c}_i,{\mathbf{H}}_{\mathbf{P}}=-\sum _{i=1}^n(c_i\cdot {\log }_2(c_i/{\mathbf{S}}_{\mathbf{P}})).$$

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

$${\mathbf{W}}_{\mathbf{P}}(T)=\sum _{i=1}^n(c_i\cdot {\mathrm{d}}_{\mathrm{T}}(v_i)),$$

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

回答以下问题。

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

2. 证明对于任何有叶节点 $v_1,v_2,\dots ,v_n$ 的有序二叉树 $T\in {\mathbf{T}}_{\mathbf{n}}$，${\sum }_{i=1}^n{2}^{-{\mathrm{d}}_{\mathrm{r}}(v_i)}\le 1$ 成立。 ·

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

4. 证明对于任何有序二叉树 $T\in {\mathbf{T}}_{\mathbf{n}}$，对于任何由 $n$ 个正实数组成的序列 $\mathbf{P}=(c_1,c_2,\dots ,c_n)$，${\mathbf{W}}_{\mathbf{P}}(T)\ge {\mathbf{H}}_{\mathbf{P}}$。

---

Problem 2

Answer the following questions on digital circuits.

1. Design and depict a circuit equivalent to XOR (exclusive OR) gate by using at most five 2-input NAND gates.

2. Design and depict a 1-bit full-adder by using only two 2-input XOR gates and three 2-input NAND gates.

3. Design and depict a 4-bit adder circuit by using four 1-bit full-adders. You may use 2-input NAND gates, 2-input NOR gates, and NOT gates, if necessary. Indicate also the critical path of the 4-bit adder circuit.

4. Consider a 4-bit clock-synchronous up-down binary counter circuit. The circuit has a 1-bit input CLK for the clocking. The circuit also has a 1-bit input X and a 4-bit output Y. The circuit counts a number from 0 to 15, and outputs the counter value to the output Y. When the input X is ‘1’, the counter value is incremented by one for each positive clock edge. Otherwise, the counter value is decremented by one for each positive clock edge. The circuit allows overflows, i.e. the next counter value is 0 when the current counter value is 15 and the input X is ‘1’, and the next counter value is 15 when the current counter value is 0 and the input X is ‘0’. Assume that the circuit satisfies the setup-time and hold-time constraints. Design and depict the 4-bit clock-synchronous up-down binary counter circuit. You may use 1-bit full-adders, D-flip-flops, 2-input NAND gates, 2-input NOR gates, and NOT gates, if necessary.

---

回答以下关于数字电路的问题。

1. 设计并描绘一个等效于 XOR（异或）门的电路，最多使用五个 2 输入 NAND 门。

2. 设计并描绘一个 1 位全加器，仅使用两个 2 输入 XOR 门和三个 2 输入 NAND 门。

3. 设计并描绘一个 4 位加法器电路，使用四个 1 位全加器。可以使用 2 输入 NAND 门、2 输入 NOR 门和 NOT 门（如有必要）。同时标明 4 位加法器电路的关键路径。

4. 考虑一个 4 位时钟同步上下计数二进制计数器电路。电路有一个用于时钟的 1 位输入 CLK。电路还有一个 1 位输入 X 和一个 4 位输出 Y。电路计数从 0 到 15，并将计数值输出到输出 Y。当输入 X 为 ‘1’ 时，计数值在每个正时钟边沿递增 1。否则，计数值在每个正时钟边沿递减 1。电路允许溢出，即当当前计数值为 15 且输入 X 为 ‘1’ 时，下一个计数值为 0，当当前计数值为 0 且输入 X 为 ‘0’ 时，下一个计数值为 15。假设电路满足设置时间和保持时间约束。设计并描绘这个 4 位时钟同步上下计数二进制计数器电路。可以使用 1 位全加器、D 触发器、2 输入 NAND 门、2 输入 NOR 门和 NOT 门（如有必要）。

---

Problem 3

Let $\Sigma$ be the set $\{a,b\}$ of letters. Given two languages $L_1,L_2\subseteq {\Sigma }^{\ast }$, we define $L_1◃L_2$ by:

$$L_1◃L_2=\{w\in {\Sigma }^{\ast }\mid \exists v\in L_1\text{ such that }vw\in L_2\}.$$

For example, if $L_1=\{ab,bb\}$ and $L_2=\{aa,abb,bbab\}$, then

$$L_1◃L_2=\{b,ab\}.$$

For a finite automaton $\mathbf{A}$, we write $\mathbf{L}(\mathbf{A})$ for the language accepted by $\mathbf{A}$.

Answer the following questions.

1. Let $L_3=\{aa,b,bb\}$ and $L_4=\{a,b,ab,bb,aaa,bbab\}$. Give the set $L_3◃L_4$.

2. Let $L_5$ and $L_6$ be the languages expressed by the regular expressions $(a^{\ast }b{)}^{\ast }$ and $(abba{)}^{\ast }$, respectively. Express $L_5◃L_6$ by using a regular expression.

3. Let ${\mathbf{A}}_1=(Q_1,\Sigma ,{\delta }_1,q_1,0,F_1)$ and ${\mathbf{A}}_2=(Q_2,\Sigma ,{\delta }_2,q_2,0,F_2)$ be deterministic finite automata. Here, $Q_i,{\delta }_i,q_i,0,$ and $F_i$ are the set of states, the transition function, the initial state, and the set of final states of ${\mathbf{A}}_{\mathbf{i}}$ ($i\in \{1,2\}$), respectively. Assume that the transition functions ${\delta }_i:Q_i\times \Sigma \to Q_i$ ($i\in \{1,2\}$) are total. Give a non-deterministic finite automaton that accepts $\mathbf{L}({\mathbf{A}}_1)◃\mathbf{L}({\mathbf{A}}_2)$, with a brief explanation. You may use $ϵ$-transitions.

4. Answer whether the following statement is true:

“For every context-free language $L$ and regular language $R$, $L◃R$ is a regular language.”

Also, give a proof sketch if the answer is yes, and give a counterexample if the answer is no.

---

设 $\Sigma$ 为字母集合 $\{a,b\}$。给定两个语言 $L_1,L_2\subseteq {\Sigma }^{\ast }$，我们定义 $L_1◃L_2$ 如下：

$$L_1◃L_2=\{w\in {\Sigma }^{\ast }\mid \exists v\in L_1\text{ such that }vw\in L_2\}。$$

例如，如果 $L_1=\{ab,bb\}$ 且 $L_2=\{aa,abb,bbab\}$，则

$$L_1◃L_2=\{b,ab\}。$$

对于一个有限自动机 $\mathbf{A}$，我们用 $\mathbf{L}(\mathbf{A})$ 表示 $\mathbf{A}$ 接受的语言。回答以下问题。

1. 设 $L_3=\{aa,b,bb\}$ 和 $L_4=\{a,b,ab,bb,aaa,bbab\}$。给出集合 $L_3◃L_4$。

2. 设 $L_5$ 和 $L_6$ 分别由正则表达式 $(a^{\ast }b{)}^{\ast }$ 和 $(abba{)}^{\ast }$ 表示。用正则表达式表示 $L_5◃L_6$。

3. 设 ${\mathbf{A}}_1=(Q_1,\Sigma ,{\delta }_1,q_1,0,F_1)$ 和 ${\mathbf{A}}_2=(Q_2,\Sigma ,{\delta }_2,q_2,0,F_2)$ 为确定性有限自动机。这里，$Q_i,{\delta }_i,q_i,0,$ 和 $F_i$ 是 ${\mathbf{A}}_{\mathbf{i}}$ 的状态集合、转换函数、初态和终态集合（$i\in \{1,2\}$）。假设转换函数 ${\delta }_i:Q_i\times \Sigma \to Q_i$（$i\in \{1,2\}$）是全函数。给出一个非确定性有限自动机，该自动机接受 $\mathbf{L}({\mathbf{A}}_1)◃\mathbf{L}({\mathbf{A}}_2)$，并简要解释。你可以使用 $ϵ$-转换。

4. 回答以下陈述是否正确：

“对于每个上下文无关语言 $L$ 和正则语言 $R$，$L◃R$ 是正则语言。”

如果答案是肯定的，请给出证明草图；如果答案是否定的，请给出反例。

---

Problem 4

Let $n$ and $d$ ($n<d$) be natural numbers and $\mathbb{R}$ be the set of real numbers. Denote by $\top$ the transposition operator of a vector and a matrix. Define the inner product of two column vectors ${\mathbf{x}}_1,{\mathbf{x}}_2\in {\mathbb{R}}^d$ as ${{\mathbf{x}}_1}^{\top }{\mathbf{x}}_2\in \mathbb{R}$. Let $\mathbf{w}=(w_1,w_2,\dots ,w_d{)}^{\top }\in {\mathbb{R}}^d$ be a $d$-dimensional column vector, $\mathbf{X}\in {\mathbb{R}}^{n\times d}$ an $n\times d$ matrix where $\mathbf{X}{\mathbf{X}}^{\top }$ is invertible, and $\mathbf{y}\in {\mathbb{R}}^n$ an $n$-dimensional column vector. Consider solving the following optimization problem by using the Lagrange multipliers method:

$$\underset{\mathbf{w}}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2\text{subject to}\mathbf{y}=\mathbf{Xw},$$

where $\Vert \mathbf{w}\Vert =\sqrt{w_1^2+w_2^2+\dots +w_d^2}$. The Lagrange function is given by

$$L(\mathbf{w},\mathbf{\mu })=\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+{\mathbf{\mu }}^{\top }(\mathbf{y}-\mathbf{Xw}),$$

where $\mathbf{\mu }\in {\mathbb{R}}^n$ is the Lagrange multipliers.

Let ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ be positive real values. The sets of column vectors $\{{\mathbf{u}}_{\mathbf{i}}\in {\mathbb{R}}^n{\}}_{i=1}^n$ and $\{{\mathbf{v}}_{\mathbf{j}}\in {\mathbb{R}}^d{\}}_{j=1}^d$ form an orthonormal basis of ${\mathbb{R}}^n$ and ${\mathbb{R}}^d$, respectively; that is, they are all unit vectors and orthogonal to each other. Suppose that the singular value decomposition of $\mathbf{X}$ is

$$\mathbf{X}=\mathbf{U\Lambda }{\mathbf{V}}^{\top },$$

where $\mathbf{U}$ is an $n\times n$ matrix, $\mathbf{\Lambda }$ is an $n\times d$ matrix, and $\mathbf{V}$ is a $d\times d$ matrix given by

$$\mathbf{U}=({\mathbf{u}}_1,{\mathbf{u}}_2,\dots ,{\mathbf{u}}_{\mathbf{n}}),\mathbf{\Lambda }=\left(\begin{array}{ccccc}{\lambda }_1& 0& \cdots & 0& 0\\ 0& {\lambda }_2& \cdots & 0& 0\\ 0& 0& \ddots & 0& 0\\ 0& 0& \cdots & {\lambda }_n& 0\end{array}\right),{\mathbf{V}}^{\top }=\left(\begin{array}{c}{{\mathbf{v}}_1}^{\top }\\ {{\mathbf{v}}_2}^{\top }\\ ⋮\\ {{\mathbf{v}}_{\mathbf{d}}}^{\top }\end{array}\right).$$

Moreover, define

$${\mathbf{X}}^{-}=\mathbf{V}({\mathbf{\Lambda }}^{-}){\mathbf{U}}^{\top },\text{where}{\mathbf{\Lambda }}^{-}=\left(\begin{array}{ccccc}\frac{1}{{\lambda }_1}& 0& \cdots & 0& 0\\ 0& \frac{1}{{\lambda }_2}& \cdots & 0& 0\\ 0& 0& \ddots & 0& 0\\ 0& 0& \cdots & \frac{1}{{\lambda }_n}& 0\end{array}\right).$$

Answer the following questions. Describe not only an answer but also the derivation process.

1. Express $\mathbf{X}{\mathbf{X}}^{-}\mathbf{X}$ using only $\mathbf{X}$.

2. Express $\mathbf{X}{\mathbf{X}}^{\top }$ using only $\mathbf{U}$ and ${\lambda }_i$ ($i=1,\dots ,n$).

3. Suppose we wish to express the stationary points of $L(\mathbf{w},\mathbf{\mu })$ in the form of $\mathbf{w}=\mathbf{Ay}$ and $\mathbf{\mu }=\mathbf{By}$. Express the matrices $\mathbf{A}\in {\mathbb{R}}^{d\times n}$ and $\mathbf{B}\in {\mathbb{R}}^{n\times n}$ using only $\mathbf{X}$.

4. Express $\mathbf{A}$ in question (3) using only ${\mathbf{X}}^{-}$.

---

设 $n$ 和 $d$ ($n<d$) 为自然数，$\mathbb{R}$ 为实数集。记 $\top$ 为向量和矩阵的转置算子。定义两个列向量 ${\mathbf{x}}_1,{\mathbf{x}}_2\in {\mathbb{R}}^d$ 的内积为 ${{\mathbf{x}}_1}^{\top }{\mathbf{x}}_2\in \mathbb{R}$。设 $\mathbf{w}=(w_1,w_2,\dots ,w_d{)}^{\top }\in {\mathbb{R}}^d$ 为一个 $d$ 维列向量，$\mathbf{X}\in {\mathbb{R}}^{n\times d}$ 是一个 $n\times d$ 矩阵，其中 $\mathbf{X}{\mathbf{X}}^{\top }$ 可逆，$\mathbf{y}\in {\mathbb{R}}^n$ 是一个 $n$ 维列向量。考虑使用拉格朗日乘子法求解以下优化问题：

$$\underset{\mathbf{w}}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2\text{subject to}\mathbf{y}=\mathbf{Xw},$$

其中 $\Vert \mathbf{w}\Vert =\sqrt{w_1^2+w_2^2+\dots +w_d^2}$。拉格朗日函数为

$$L(\mathbf{w},\mathbf{\mu })=\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+{\mathbf{\mu }}^{\top }(\mathbf{y}-\mathbf{Xw}),$$

其中 $\mathbf{\mu }\in {\mathbb{R}}^n$ 是拉格朗日乘子。

设 ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ 为正实数。列向量集合 $\{{\mathbf{u}}_{\mathbf{i}}\in {\mathbb{R}}^n{\}}_{i=1}^n$ 和 $\{{\mathbf{v}}_{\mathbf{j}}\in {\mathbb{R}}^d{\}}_{j=1}^d$ 分别构成 ${\mathbb{R}}^n$ 和 ${\mathbb{R}}^d$ 的正交基；即它们都是单位向量且彼此正交。假设 $\mathbf{X}$ 的奇异值分解为

$$\mathbf{X}=\mathbf{U\Lambda }{\mathbf{V}}^{\top },$$

其中 $\mathbf{U}$ 是一个 $n\times n$ 矩阵，$\mathbf{\Lambda }$ 是一个 $n\times d$ 矩阵，$\mathbf{V}$ 是一个 $d\times d$ 矩阵，给出如下

$$\mathbf{U}=({\mathbf{u}}_1,{\mathbf{u}}_2,\dots ,{\mathbf{u}}_{\mathbf{n}}),\mathbf{\Lambda }=\left(\begin{array}{ccccc}{\lambda }_1& 0& \cdots & 0& 0\\ 0& {\lambda }_2& \cdots & 0& 0\\ 0& 0& \ddots & 0& 0\\ 0& 0& \cdots & {\lambda }_n& 0\end{array}\right),{\mathbf{V}}^{\top }=\left(\begin{array}{c}{{\mathbf{v}}_1}^{\top }\\ {{\mathbf{v}}_2}^{\top }\\ ⋮\\ {{\mathbf{v}}_{\mathbf{d}}}^{\top }\end{array}\right).$$

此外，定义

$${\mathbf{X}}^{-}=\mathbf{V}({\mathbf{\Lambda }}^{-}){\mathbf{U}}^{\top },\text{其中}{\mathbf{\Lambda }}^{-}=\left(\begin{array}{ccccc}\frac{1}{{\lambda }_1}& 0& \cdots & 0& 0\\ 0& \frac{1}{{\lambda }_2}& \cdots & 0& 0\\ 0& 0& \ddots & 0& 0\\ 0& 0& \cdots & \frac{1}{{\lambda }_n}& 0\end{array}\right).$$

回答以下问题。描述答案的同时也要给出推导过程。

1. 使用仅 $\mathbf{X}$ 表示 $\mathbf{X}{\mathbf{X}}^{-}\mathbf{X}$。

2. 使用仅 $\mathbf{U}$ 和 ${\lambda }_i$ ($i=1,\dots ,n$) 表示 $\mathbf{X}{\mathbf{X}}^{\top }$。

3. 假设我们希望用 $\mathbf{w}=\mathbf{Ay}$ 和 $\mathbf{\mu }=\mathbf{By}$ 表示 $L(\mathbf{w},\mathbf{\mu })$ 的驻点。使用仅 $\mathbf{X}$ 表示矩阵 $\mathbf{A}\in {\mathbb{R}}^{d\times n}$ 和 $\mathbf{B}\in {\mathbb{R}}^{n\times n}$。

4. 使用仅 ${\mathbf{X}}^{-}$ 表示问题 (3) 中的 $\mathbf{A}$。