115 年 國立成功大學資訊工程系碩士班《計算機數學》

Consider all simple (loop-free), undirected graphs on a set of $5$ distinct labeled vertices $V=\{1,2,3,4,5\}$. Every edge connects two distinct vertices, and multiple edges are not allowed. Assume that no vertex is isolated (i.e., every vertex has degree at least $1$).

A self-organizing ad-hoc satellite network consists of multiple satellites placed at arbitrary integer coordinates in 3-dimensional space. Each satellite is modeled as a point $A_i\in\mathbb{Z}^3$. A secure communication link may be established between satellites $A_i$ and $A_j$ only if the midpoint of the segment $A_iA_j$ also lies on an integer lattice point. Equivalently, all three coordinate-wise averages must be integers:
$\frac{x_i+x_j}{2},\ \frac{y_i+y_j}{2},\ \frac{z_i+z_j}{2}\in\mathbb{Z}.$

You are designing the firmware logic for a high-security electronic lock. The lock receives a stream of binary signals ($0$ or $1$) from a keypad. Draw the state transition diagrams for two different versions of the security protocol. Use the Moore Machine model for both versions. Specifically, use circles to represent states with labels $S_i$ where $i$ is the index starting from $0$, use arrows to represent transitions, use an arrow to point to the start state, and mark the "Unlock" state as double circles.

By factoring $A$ into $LU$, the LU decomposition allows solving $Ax=b$ by first solving $Ly=b$, followed by $Ux=y$, each requiring only a single triangular solve. Thus, computing $A=LU$ is crucial in large-scale computer engineering applications.

Algorithm 1. LU Decomposition Without Pivoting

Require: Matrix $A\in\mathbb{R}^{n\times n}$
Ensure: Lower triangular matrix $L$, upper triangular matrix $U$ such that $A=LU$

1. Initialize $L\leftarrow I_n,\ U\leftarrow 0_{n\times n}$.
2. For $k=1$ to $n$ do:
   1. For $j=k$ to $n$ do:
      $U_{k,j}\leftarrow A_{k,j}-\sum_{s=1}^{k-1}L_{k,s}\cdot U_{s,j}.$
   2. End for.
   3. For $i=k+1$ to $n$ do:
      $L_{i,k}\leftarrow\frac{1}{U_{k,k}}\left(A_{i,k}-\sum_{s=1}^{k-1}L_{i,s}\cdot U_{s,k}\right).$
   4. End for.
3. End for.
4. Return $(L,U)$.

Algorithm 2. Speed-Improved Block LU Decomposition

Require: Matrix $A\in\mathbb{R}^{n\times n}$, where $n$ is a power of $2$
Ensure: Matrices $L,U$ with $A=LU$

1. Function $\operatorname{SpeedImprovedBlockLU}(A)$:
2. Let $n\leftarrow$ size of $A$.
3. If $n=1$, then return $([1],[A_{11}])$.
4. Partition $A$ into blocks:
   $A=\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix}.$
5. $(L_{11},U_{11})\leftarrow\operatorname{SpeedImprovedBlockLU}(A_{11})$.
6. $U_{12}\leftarrow\operatorname{SISolve}(L_{11},A_{12},\mathrm{lower})$.
7. $L_{21}\leftarrow\operatorname{SISolve}(U_{11},A_{21},\mathrm{upper})$.
8. $S\leftarrow A_{22}-\operatorname{SIMultiply}(L_{21},U_{12})$.
9. $(L_{22},U_{22})\leftarrow\operatorname{SpeedImprovedBlockLU}(S)$.
10. Construct:
    $L=\begin{bmatrix}L_{11}&0\\L_{21}&L_{22}\end{bmatrix},\qquad U=\begin{bmatrix}U_{11}&U_{12}\\0&U_{22}\end{bmatrix}.$
11. Return $(L,U)$.
12. End function.

Algorithm 3. $\operatorname{SISolve}(T,B,\mathrm{type})$

1. If $n=1$, then return $B/T$.
2. Partition $T,B$ into blocks:
   $T=\begin{bmatrix}T_{11}&T_{12}\\T_{21}&T_{22}\end{bmatrix},\qquad B=\begin{bmatrix}B_1\\B_2\end{bmatrix}.$
3. If $\mathrm{type}=\mathrm{lower}$:
   $X_1\leftarrow\operatorname{SISolve}(T_{11},B_1),$
   $X_2\leftarrow\operatorname{SISolve}(T_{22},B_2-T_{21}X_1).$
4. Else:
   $X_2\leftarrow\operatorname{SISolve}(T_{22},B_2),$
   $X_1\leftarrow\operatorname{SISolve}(T_{11},B_1-T_{12}X_2).$
5. Return $\begin{bmatrix}X_1\\X_2\end{bmatrix}$.
6. End function.

Algorithm 4. $\operatorname{SIMultiply}(A,B)$

1. If $n=1$, then return $A\cdot B$.
2. Partition $A,B$ into blocks:
   $A=\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix},\qquad B=\begin{bmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{bmatrix}.$
3. Compute:
   $M_1\leftarrow(A_{11}+A_{22})(B_{11}+B_{22}),$
   $M_2\leftarrow(A_{21}+A_{22})B_{11},$
   $M_3\leftarrow A_{11}(B_{12}-B_{22}),$
   $M_4\leftarrow A_{22}(B_{21}-B_{11}),$
   $M_5\leftarrow(A_{11}+A_{12})B_{22},$
   $M_6\leftarrow(A_{21}-A_{11})(B_{11}+B_{12}),$
   $M_7\leftarrow(A_{12}-A_{22})(B_{21}+B_{22}).$
4. Compute:
   $C_{11}\leftarrow M_1+M_4-M_5+M_7,$
   $C_{12}\leftarrow M_3+M_5,$
   $C_{21}\leftarrow M_2+M_4,$
   $C_{22}\leftarrow M_1-M_2+M_3+M_6.$
5. Return $C=\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix}$.
6. End function.

Let $A\in\mathbb{R}^{m\times n}$ with $m>n$, and assume that $A$ is rank-deficient, i.e., $\operatorname{rank}(A)<n$. $A^\mathsf{T}A$ is positive semi-definite.