2022W

Problem 1

For a matrix denoted by $\mathbf{M}$, we write ${\mathbf{M}}_{i:j,k:l}$ for the submatrix formed from the rows $i$ through $j$ and the columns from $k$ through $l$ of the matrix. We also denote ${\mathbf{M}}_{i:i,k:l}$ and ${\mathbf{M}}_{i:j,k:k}$ by ${\mathbf{M}}_{i,k:l}$ and ${\mathbf{M}}_{i:j,k}$, respectively. (Note that they are row and column vectors, respectively.)

Assume below that $\mathbf{A}$ is an $n\times n$ nonsingular matrix which can be LU factorized. In addition, assume that a positive integer $w$ exists such that all entries in the $k$-th sub- and super-diagonal of $\mathbf{A}$ are zero if $k>w$. Namely, if $|i-j|>w$, $A_{i,j}$ is zero.

We denote the LU factorization of $\mathbf{A}$ by $\mathbf{A}=\mathbf{LU}$, where $\mathbf{L}$ is a lower triangular matrix with unit diagonal elements, and $\mathbf{U}$ is an upper triangular matrix.

The following algorithm P computes $\mathbf{L}$ and $\mathbf{U}$ from the input $\mathbf{A}$ in-place in such a way that the strictly lower triangular part and the upper triangular part of $\mathbf{A}$ will be $\mathbf{L}$ and $\mathbf{U}$, respectively. In other words, $A_{i,j}$ will be $L_{i,j}$ for $i>j$, and $A_{i,j}$ will be $U_{i,j}$ for $i\le j$, when it terminates.

Algorithm P

for (k = 1; k < n; k = k + 1) {
    A[k+1:n,k] <- A[k+1:n,k] * (1 / A[k,k]);
    A[k+1:n,k+1:n] <- A[k+1:n,k+1:n] - A[k+1:n,k] * A[k,k+1:n];
}

Answer the following questions.

1. Compute the LU factorization of the following matrix.

$$\left(\begin{array}{cccc}1& 1& 0& 0\\ -1& 1& 1& 0\\ 0& -2& 2& 1\\ 0& 0& -3& 3\end{array}\right)$$

2. Prove that $L_{i,j}=0$ and $U_{i,j}=0$ if $|i-j|>w$.

3. Assume that $n\gg 1$, $w\ll n$, and $m\gg n$. We wish to solve a set of linear systems,

$$\mathbf{A}{\mathbf{x}}_i={\mathbf{b}}_i,i=1,2,\dots ,m,$$

where ${\mathbf{b}}_i(i=1,2,\dots ,m)$ are the constant vectors, and ${\mathbf{x}}_i(i=1,2,\dots ,m)$ are the unknown vectors. Explain the relative merits of the following methods (I) and (II) with respect to the amount of arithmetic operations.

(I) Compute ${\mathbf{A}}^{-1}$ first, and then compute each ${\mathbf{x}}_i$ as ${\mathbf{A}}^{-1}{\mathbf{b}}_i$.

(II) Compute the LU factorization of $\mathbf{A}$ first, and then solve $\mathbf{L}{\mathbf{y}}_i={\mathbf{b}}_i$ for ${\mathbf{y}}_i$. Solve $\mathbf{U}{\mathbf{x}}_i={\mathbf{y}}_i$ lastly.

---

对于矩阵 $\mathbf{M}$，我们写 ${\mathbf{M}}_{i:j,k:l}$ 表示从矩阵的第 $i$ 行到第 $j$ 行以及第 $k$ 列到第 $l$ 列构成的子矩阵。我们还将 ${\mathbf{M}}_{i:i,k:l}$ 和 ${\mathbf{M}}_{i:j,k:k}$ 分别表示为 ${\mathbf{M}}_{i,k:l}$ 和 ${\mathbf{M}}_{i:j,k}$。（注意它们分别是行向量和列向量。）

假设 $\mathbf{A}$ 是一个 $n\times n$ 的非奇异矩阵，可以进行 LU 分解。另外，假设存在一个正整数 $w$，使得当 $|i-j|>w$ 时，$\mathbf{A}$ 在第 $k$ 条下对角线和超对角线上的所有元素都为零。即，如果 $|i-j|>w$，则 $A_{i,j}$ 为零。

我们用 $\mathbf{A}=\mathbf{LU}$ 来表示 $\mathbf{A}$ 的 LU 分解，其中 $\mathbf{L}$ 是具有单位对角元素的下三角矩阵，$\mathbf{U}$ 是上三角矩阵。

下面的算法 P 从输入 $\mathbf{A}$ 中就地计算 $\mathbf{L}$ 和 $\mathbf{U}$，以这样的方式，$\mathbf{A}$ 的严格下三角部分和上三角部分将分别是 $\mathbf{L}$ 和 $\mathbf{U}$。换句话说，当它终止时，$A_{i,j}$ 将为 $L_{i,j}$（当 $i>j$）和 $U_{i,j}$（当 $i\le j$）。

算法 P

for (k = 1; k < n; k = k + 1) {
    A[k+1:n,k] <- A[k+1:n,k] * (1 / A[k,k]);
    A[k+1:n,k+1:n] <- A[k+1:n,k+1:n] - A[k+1:n,k] * A[k,k+1:n];
}

回答以下问题。

1. 计算以下矩阵的 LU 分解。

$$\left(\begin{array}{cccc}1& 1& 0& 0\\ -1& 1& 1& 0\\ 0& -2& 2& 1\\ 0& 0& -3& 3\end{array}\right)$$

2. 证明 $L_{i,j}=0$ 和 $U_{i,j}=0$ 如果 $|i-j|>w$。

3. 假设 $n\gg 1$，$w\ll n$，并且 $m\gg n$。我们希望求解一组线性系统，

$$\mathbf{A}{\mathbf{x}}_i={\mathbf{b}}_i,i=1,2,\dots ,m,$$

其中 ${\mathbf{b}}_i(i=1,2,\dots ,m)$ 是常量向量，${\mathbf{x}}_i(i=1,2,\dots ,m)$ 是未知向量。解释以下方法 (I) 和 (II) 在算术运算量方面的相对优点。

(I) 首先计算 ${\mathbf{A}}^{-1}$，然后将每个 ${\mathbf{x}}_i$ 计算为 ${\mathbf{A}}^{-1}{\mathbf{b}}_i$。

(II) 首先计算 $\mathbf{A}$ 的 LU 分解，然后解 $\mathbf{L}{\mathbf{y}}_i={\mathbf{b}}_i$ 得到 ${\mathbf{y}}_i$。最后解 $\mathbf{U}{\mathbf{x}}_i={\mathbf{y}}_i$。

---

Problem 2

Let $G=(V,E)$ be a simple undirected graph with the vertex set $V=\{v_i\mid i=1,\dots ,n\}$ and edge set $E$. For an $n$-dimensional vector $\mathbf{x}=(x_1,\dots ,x_n)\in \{-1,+1{\}}^n$, define $f_G(\mathbf{x})$ by

$$f_G(\mathbf{x})=\sum _{(v_i,v_j)\in E}\frac{1-x_i{x}_j}{2}.$$

Answer the following questions.

1. For the case where $G$ is a complete graph $K_n$ of $n$ vertices, compute $a_n={\max }_{\mathbf{x}\in \{-1,+1{\}}^n}{f}_G(\mathbf{x})$.
2. Let $K_n$ and $a_n$ be those given in question (1). Let $b_n$ be the number of edges of $K_n$. Compute

$$\underset{n\to \infty }{\lim }\frac{a_n}{b_n}.$$

3. Let $G$ be an arbitrary simple undirected graph. When each $x_i$ takes a value of either $-1$ or $+1$ with probability $\frac{1}{2}$ independently, compute the expected value of $f_G(\mathbf{x})$. You may use the linearity of expectation.
4. Show that, for any simple undirected graph $G$, there exists some $\mathbf{x}\in \{-1,+1{\}}^n$ such that

$$f_G(\mathbf{x})\ge \frac{|E|}{2}.$$

Here, $|E|$ denotes the number of edges of $G$.

---

令 $G=(V,E)$ 为一个简单无向图，其顶点集为 $V=\{v_i\mid i=1,\dots ,n\}$，边集为 $E$。对于一个 $n$ 维向量 $\mathbf{x}=(x_1,\dots ,x_n)\in \{-1,+1{\}}^n$，定义 $f_G(\mathbf{x})$ 为

$$f_G(\mathbf{x})=\sum _{(v_i,v_j)\in E}\frac{1-x_i{x}_j}{2}.$$

回答以下问题。

1. 当 $G$ 是一个 $n$ 个顶点的完全图 $K_n$ 时，计算 $a_n={\max }_{\mathbf{x}\in \{-1,+1{\}}^n}{f}_G(\mathbf{x})$。
2. 令 $K_n$ 和 $a_n$ 为问题（1）中给出的。令 $b_n$ 为 $K_n$ 的边数。计算

$$\underset{n\to \infty }{\lim }\frac{a_n}{b_n}.$$

3. 令 $G$ 为任意一个简单无向图。当每个 $x_i$ 独立地以 $\frac{1}{2}$ 的概率取 $-1$ 或 $+1$ 时，计算 $f_G(\mathbf{x})$ 的期望值。你可以使用期望值的线性性。
4. 证明对于任意简单无向图 $G$，存在某个 $\mathbf{x}\in \{-1,+1{\}}^n$ 使得

$$f_G(\mathbf{x})\ge \frac{|E|}{2}.$$

这里，$|E|$ 表示 $G$ 的边数。

---

Problem 3

Let $\Sigma =\{a,b\}$. Answer the following questions.

(1) Give a non-deterministic finite state automaton with 3 states that accepts the following language.

$$wba|w\in {\Sigma }^{\ast }$$

(2) Show the minimal deterministic finite state automaton that accepts the language given in question (1).

(3) Prove that the following language $L$ over $\Sigma$ is not regular. You may use the pumping lemma for regular languages.

$$L=\{w^{R}baw|w\in {\Sigma }^{\ast }\}$$

Here, $w^R$ denotes the reverse of $w$. For example, $(abb{)}^R=bba$.

(4) Is the language $L$ in question (3) a context-free language? If it is, construct a context-free grammar that generates $L$. If not, prove that $L$ is not a context-free language.

---

让 $\Sigma =\{a,b\}$。回答以下问题。

(1) 给出一个具有 3 个状态的非确定性有限状态自动机，该自动机接受以下语言。

$$wba|w\in {\Sigma }^{\ast }$$

(2) 展示接受问题 (1) 中给出的语言的最小确定性有限状态自动机。

(3) 证明以下语言 $L$ 在 $\Sigma$ 上不是正则的。你可以使用正则语言的泵引理。

$$L=\{w^{R}baw|w\in {\Sigma }^{\ast }\}$$

这里，$w^R$ 表示 $w$ 的反转。例如，$(abb{)}^R=bba$。

(4) 问题 (3) 中的语言 $L$ 是上下文无关语言吗？如果是，构造一个生成 $L$ 的上下文无关文法。如果不是，证明 $L$ 不是上下文无关语言。

---

Problem 4

Answer the following questions on digital circuits.

(1) Provide a Boolean expression of the output $D$ according to the following truth table. Design and depict a corresponding combinational circuit by using at most six 2-input NAND gates.

Truth table

$$\begin{array}{cccc}\text{Input}& & & \text{Output}\\ A& B& C& D\\ 0& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& 0\\ 0& 1& 1& 1\\ 1& 0& 0& 0\\ 1& 0& 1& 1\\ 1& 1& 0& 1\\ 1& 1& 1& 1\end{array}$$

(2) Depict the internal structure of a D-flip-flop, and explain how the D-flip-flop holds a 1-bit value.

(3) Consider a clock-synchronous sequential circuit with a 1-bit input $\mathbf{CLK}$, a 1-bit input $\mathbf{X}$, and a 1-bit output $\mathbf{Y}$, where the input $\mathbf{CLK}$ is used for the clocking. The output $\mathbf{Y}$ is ‘1’ when the number of ‘1’ in the input $\mathbf{X}$ values in the past three clock cycles (excluding the current clock cycle) is greater than the number of ‘0’. Otherwise, the output $\mathbf{Y}$ is ‘0’. The output $\mathbf{Y}$ may be any value during the initial three clock cycles after the circuit is powered on. Assume that the circuit satisfies the setup-time and hold-time constraints. Design and depict the circuit. You may use at most two D-flip-flops and an arbitrary number of 2-input AND gates, 2-input OR gates, and NOT gates, if necessary.

---

问题 4

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

(1) 根据以下真值表提供输出 $D$ 的布尔表达式。设计并使用最多六个 2 输入 NAND 门绘制相应的组合电路。

真值表

$$\begin{array}{cccc}\text{输入}& & & \text{输出}\\ A& B& C& D\\ 0& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& 0\\ 0& 1& 1& 1\\ 1& 0& 0& 0\\ 1& 0& 1& 1\\ 1& 1& 0& 1\\ 1& 1& 1& 1\end{array}$$

(2) 描述 D 触发器的内部结构，并解释 D 触发器如何保持 1 位值。

(3) 考虑一个时钟同步顺序电路，具有 1 位输入 $\mathbf{CLK}$、1 位输入 $\mathbf{X}$ 和 1 位输出 $\mathbf{Y}$，其中输入 $\mathbf{CLK}$ 用于时钟控制。当过去三个时钟周期内（不包括当前时钟周期）输入 $\mathbf{X}$ 的值中 ‘1’ 的数量多于 ‘0’ 的数量时，输出 $\mathbf{Y}$ 为 ‘1’。否则，输出 $\mathbf{Y}$ 为 ‘0’。电路上电后的初始三个时钟周期内，输出 $\mathbf{Y}$ 可以是任意值。假设电路满足建立时间和保持时间约束。设计并绘制电路。你可以使用最多两个 D 触发器和任意数量的 2 输入 AND 门、2 输入 OR 门和 NOT 门，如果需要的话。