111 年 國立成功大學製造資訊與系統研究所丙組《計算機概論》

本題主要在測試考生對於計算機概論中兩個重要概念的理解程度，分別是嵌入式系統與基因演算法。

(a) 嵌入式系統 (Embedded System)

核心觀念： 嵌入式系統是一種專門設計用於執行特定功能，且通常內嵌於較大系統中的計算機系統。

詳解：
嵌入式系統是一種專用目的的計算機系統，它被設計來執行單一或有限數量的任務，並且通常是某個更大系統的一部分。與通用計算機（如個人電腦）不同，嵌入式系統通常具有高度的整合性、低功耗、實時性要求以及固定的軟硬體配置。它們廣泛應用於各種設備中，例如：

• 消費電子： 智慧型手機、數位電視、DVD播放器、微波爐、洗衣機。
• 汽車： 引擎控制單元 (ECU)、防鎖煞車系統 (ABS)、導航系統。
• 工業控制： 生產線自動化設備、機器人、監控系統。
• 醫療設備： 心臟起搏器、血糖儀、醫療影像設備。
• 通訊設備： 路由器、交換機、基地台。

嵌入式系統的關鍵特徵包括：

• 專用性： 為特定應用而設計。
• 資源受限： 通常具有有限的處理能力、記憶體和儲存空間。
• 實時性： 許多嵌入式系統需要嚴格的時間限制來響應事件。
• 高可靠性： 經常在嚴苛的環境下運行，需要高度穩定性。
• 硬體/軟體整合： 軟體通常緊密耦合於特定的硬體。

【答案】 嵌入式系統是一種為執行特定功能而設計的計算機系統，通常內嵌於更大的設備中，具有資源受限、實時性、高可靠性等特點，廣泛應用於各種電子設備和自動化系統。

(b) 基因演算法 (Genetic Algorithm, GA)

核心觀念： 基因演算法是一種受自然選擇和遺傳學啟發的啟發式搜尋演算法，用於尋找優化問題的最佳或近似最佳解。

本題主要測試考生對於並行處理、網路通訊以及資源受限系統的設計能力，特別是在嵌入式系統（Raspberry Pi）上實現即時數據收集與傳輸。

核心觀念： 使用多執行緒或多進程來實現並行處理，以提高數據收集和傳輸的效率，並考慮到嵌入式系統的穩定性和資源限制。

詳解：

題目要求設計一個應用程式，在一個四核心的 Raspberry Pi (RPi) 上，從設備收集數據，並將數據即時傳輸到遠端伺服器的 REST API。RPi 的每個核心每秒能收集 A 筆數據記錄。為了保持系統穩定，數據不儲存在 RPi 的本地儲存中，而是即時傳輸。我們需要編寫類似 Python 的偽代碼，並描述其限制。

設計思路：

由於 RPi 有四個核心，並且需要同時進行數據收集和數據傳輸，我們可以利用多執行緒 (multithreading) 或多進程 (multiprocessing) 來實現並行處理。由於是 Python-like 偽代碼，我們可以使用類似 threading 或 multiprocessing 的概念。

1. 數據收集 (Data Collection)： 每個核心負責從設備收集數據。由於每個核心可以處理 A 筆數據/秒，總共可以處理 4A 筆數據/秒。
2. 數據傳輸 (Data Transmission)： 數據收集後需要即時傳輸到遠端 REST API。網路傳輸是一個 I/O 密集型操作，可能會阻塞 CPU。因此，數據傳輸應該與數據收集分開進行，以便不影響收集的效率。
3. 緩衝區 (Buffer)： 為了解耦數據收集和數據傳輸，以及處理兩者之間的速率差異，我們可以使用一個共享的緩衝區（例如一個佇列）。收集執行緒將數據放入緩衝區，傳輸執行緒從緩衝區取出數據並傳輸。

Python-like 偽代碼：

我們將使用類似 Python 的 threading 和 queue 模組來實現。

核心觀念

本題評量資料庫系統（Database Systems）的核心設計流程，包含兩個主要部分：

1. 實體關聯模型（Entity-Relationship Model, ER Model）之建構：
   • 實體型態（Entity Sets）：辨認系統中的強實體（Strong Entity）與弱實體（Weak Entity）。
   • 屬性特性（Attributes）：辨識單值屬性、多值屬性（Multivalued Attributes，如多支電話）、主鍵（Primary Key）及局部鍵（Partial Key / Discriminator）。
   • 關聯型態（Relationship Sets）：
     • 基數比限制（Cardinality Constraints）：一對一（$1:1$）、一對多（$1:N$）、多對多（$M:N$）。
     • 參與限制（Participation Constraints）：部分參與（Partial Participation）與完全參與（Total Participation）。
     • 關聯度數（Degree of Relationship）：二元關聯（Binary Relationship）與三元關聯（Ternary Relationship）。
2. ER 圖轉關聯綱要（Relational Schema Mapping）：
   • 強實體與弱實體的表格轉換規則。
   • 多值屬性必須獨立成表的正規化原則（以符合 1NF）。
   • 一對多關聯（以「外來鍵 Foreign Key」置於 $N$ 端）與多對多／多元關聯（獨立成表並以參與實體之主鍵組成複合主鍵）的轉換規範。

---

解題方法

(a) ER 圖設計與語意分析

1. 實體集與屬性分析：

   • Doctor（強實體）：
     • 主鍵：$\underline{\text{badgeId}}$。
     • 屬性：$\text{name}$。
     • 多值屬性：$\{\text{mobilePhone}\}$（雙橢圓表示）。
   • Office（強實體）：
     • 主鍵：$\underline{\text{officeID}}$。
     • 屬性：$\text{address}$。
     • 多值屬性：$\{\text{phone}\}$（雙橢圓表示）。
   • ExamRoom（弱實體）：
     • 題目敘述「An exam room can be identified by its room number, and the office that it is in」，說明診間無法單獨以診間號碼識別，必須依附於診所，因此為弱實體（雙矩形表示）。
     • 局部鍵（Partial Key）：$\dashuline{\text{roomNo}}$（虛底線）。
     • 識別關聯（Identifying Relationship）：$\text{Contains}$（雙菱形表示，從 ExamRoom 到 Contains 為雙線代表完全參與）。
   • Patient（強實體）：
     • 主鍵：$\underline{\text{SSN}}$。
     • 屬性：$\text{name}$, $\text{phone}$。

2. 關聯集分析與限制：

   • 管理關聯（Manages）：
     • 參與實體：$\text{Doctor}$ 與 $\text{Office}$。
     • 基數比：一位醫生可管理多間診所（$1:N$），一間診所最多由一位醫生管理（$\text{at most one}$，即 $0$ 或 $1$）。因此為 $\text{Doctor}(1) : \text{Office}(N)$。
     • 參與度：診所「may be managed by at most one」，非所有診所都有管理者，為部分參與（單線）；非所有醫生都有管理診所，為部分參與（單線）。
   • 診所包含診間關聯（Contains）：
     • 參與實體：$\text{Office}(1)$ 與 $\text{ExamRoom}(N)$。
     • 一間診所包含一個或多個診間；弱實體 $\text{ExamRoom}$ 存在必定依附於 $\text{Office}$（Total Participation，雙線）。
   • 看診諮詢關聯（Consultation）：
     • 題目描述「When a patient visits an office, he or she has a consultation with a doctor in an examination room. The start time and the end time need to be recorded...」。
     • 涉及 $\text{Patient}$、$\text{Doctor}$、$\text{ExamRoom}$ 三者在特定診所與診間進行的活動，故建構為三元關聯（Ternary Relationship）：$\text{Consultation}$。
     • 關聯屬性：$\text{startTime}$, $\text{endTime}$。
     • 限制：病人、醫生、診間皆可參與多次不同時段的諮詢，基數為 $M:N:P$。

3. ER 圖繪製（陳氏標記法 Chen's Notation）：

      (name)   (badgeId)   ((mobilePhone))
         \        |          /
          \       |         /
        +--------------------+
        |       Doctor       |
        +--------------------+
          | 1             | M
          |               |
     (Manages)            |
          | N             |
+--------------------+    |
|       Office       |    |
+--------------------+    |
  | 1    |        \       |
  |      |         \      |
  |   (address)  ((phone))|
  |                       |
(Contains)                |      (startTime) (endTime)
  ||                      |           \        /
  || N                    |            \      /
+====================+    |          [Consultation]
|      ExamRoom      |----|----------------/      \
+====================+ M  |                        \
      |                   |                         \ P
 (roomNo)                 \--------------------------+
                                                     |
                                            +--------------------+
                                            |      Patient       |
                                            +--------------------+
                                                  /   |   \
                                             (SSN) (name) (phone)

(註：圖中 [] 為實體，[[]] 為弱實體，() 為單值屬性，(()) 為多值屬性，__ 為主鍵，-- 為局部鍵，|| 代表完全參與 Total Participation)

---

(b) 關聯綱要轉換（Relational Schema Mapping）

遵循 ER 轉換至關聯綱要之標準演算法：

1. 強實體轉換：
   • $\text{Doctor}(\underline{\text{badgeId}}, \text{name})$

核心觀念

本題考查二次多項式迴歸（quadratic polynomial regression）與最小平方法（least squares）。

題目中的模型可解讀為：

$$\hat y=Ct^2+Dt+E$$

雖然模型對 $t$ 是二次式，但對未知係數 $C,D,E$ 仍是線性的，因此屬於「線性迴歸模型」。

對每一筆資料 $(t_i,y_i)$，預測誤差為：

$$e_i=y_i-(Ct_i^2+Dt_i+E)$$

最小平方法的目標，是使所有平方誤差總和最小：

$$S(C,D,E)=\sum_{i=1}^{n}\left[y_i-(Ct_i^2+Dt_i+E)\right]^2$$

令 $S$ 分別對 $C,D,E$ 偏微分並設為零，即可得到正規方程式（normal equations）。

---

解題方法

(a) 求最佳擬合係數

資料如下：

$t$	0	1	2	3	4
$y$	600	580	570	610	620

建立設計矩陣：

$$X= \begin{bmatrix} 0^2&0&1\\ 1^2&1&1\\ 2^2&2&1\\ 3^2&3&1\\ 4^2&4&1 \end{bmatrix} = \begin{bmatrix} 0&0&1\\ 1&1&1\\ 4&2&1\\ 9&3&1\\ 16&4&1 \end{bmatrix}$$

係數向量為：

$$\boldsymbol{\beta}= \begin{bmatrix} C\\D\\E \end{bmatrix}$$

最小平方法的矩陣解為：

$$\boldsymbol{\beta}=(X^TX)^{-1}X^T\boldsymbol y$$

先計算所需總和：

$$\sum t=10,\qquad \sum t^2=30,\qquad \sum t^3=100,\qquad \sum t^4=354$$ $$\sum y=2980,\qquad \sum ty=6030,\qquad \sum t^2y=18270$$

因此正規方程式為：

$$354C+100D+30E=18270$$ $$100C+30D+10E=6030$$ $$30C+10D+5E=2980$$

由第三式：

$$E=596-6C-2D$$

代入第二式：

$$100C+30D+10(596-6C-2D)=6030$$ $$4C+D=7$$

代入第一式：

$$354C+100D+30(596-6C-2D)=18270$$ $$87C+20D=195$$

由 $D=7-4C$，得：

$$87C+20(7-4C)=195$$ $$7C=55$$ $$C=\frac{55}{7}$$ $$D=7-4\left(\frac{55}{7}\right)=-\frac{171}{7}$$ $$E=596-6\left(\frac{55}{7}\right)-2\left(-\frac{171}{7}\right) =\frac{4184}{7}$$

所以最佳擬合模型為：

$$\boxed{\hat y=\frac{55}{7}t^2-\frac{171}{7}t+\frac{4184}{7}}$$

Python-like pseudo code 如下：

本題要求分析 Part (a) 中求解係數的計算複雜度。

核心觀念： 計算複雜度通常用大 O 符號 (Big O notation) 來表示，關注演算法隨著輸入規模增長而增長的趨勢。在線性回歸中，輸入規模通常是指數據點的數量 $n$。

詳解：

在 Part (a) 中，我們採用了最小平方法來求解係數 $D$ 和 $E$。
偽代碼中的主要計算步驟包括：

1. 數據預處理： 計算 $y' = y + t^2$。這需要遍歷所有 $n$ 個數據點，對每個點進行一次平方和一次加法。

   • 計算 $t^2$ 對於每個點：$O(n)$ 次乘法。
   • 計算 $y + t^2$ 對於每個點：$O(n)$ 次加法。
   • 總體：$O(n)$。

2. 計算總和： 遍歷所有 $n$ 個數據點，計算 $\sum t$, $\sum t^2$, $\sum y'$, $\sum t \cdot y'$。

   • 在循環中，我們執行：
     • 一次加法 (sum_t += t_val)
     • 一次乘法和一次加法 (sum_t_squared += t_val**2)
     • 一次加法 (sum_y_prime += y_prime_val)
     • 一次乘法和一次加法 (sum_t_y_prime += t_val * y_prime_val)
   • 這些都是常數時間的操作。對於 $n$ 個點，總共需要 $n$ 次這樣的循環。
   • 總體：$O(n)$。

3. 計算係數： 使用正規方程組的解法計算 $E$ 和 $D$。

   • 計算分母 denominator = n * sum_t_squared - sum_t**2：涉及幾次乘法、減法。常數時間 $O(1)$。
   • 計算分子和係數 $E$ 和 $D$：涉及幾次乘法、減法、除法。

核心觀念

本題的核心觀念為機器學習與迴歸分析中的**殘差（Residual，題目作 Residue）**定義與模型預測評估：

1. 殘差的數學定義：
   在統計學與迴歸模型（Regression Model）中，殘差定義為「實際觀察值（Actual/Observed Value）」與「模型預測值（Predicted Value）」之間的差值。在時間點 $t$ 的殘差 $e_t$ 計算公式為：
   $e_t = y_t - \hat{y}_t$
   其中：

   • $y_t$ 為時間點 $t$ 的真實值（Ground Truth）。本題在 $t = 5$ 時，$y_5 = 666$。
   • $\hat{y}_t = f(t)$ 為已訓練模型（Model）在輸入時間點 $t$ 時所輸出的預測股價。

2. 殘差方向性約定：
   依據標準統計學定義，殘差方向一律為 $\text{Actual} - \text{Predicted}$（真實值減去預測值）。若實際值高於預測值，殘差為正（Underestimation）；反之為負（Overestimation）。

---

解題方法

1. 變數與參數設定：

   • 設定時間變數：$t = 5$。
   • 設定真實股價：$y_{\text{actual}} = 666$。

2. 模型推論（Inference）：

   • 呼叫題組前小題所建立之預測模型物件（例如 model），將特徵 $t = 5$ 傳入預測函式，取得模型預測值 $\hat{y}$。

3. 計算殘差：

   • 將真實股價與預測股價相減：$\text{residue} = y_{\text{actual}} - \hat{y}$。

4. 偽代碼實作（Python-like Pseudo-code）：

核心觀念

本題考查 SQL 的分組聚合與查詢結果排序，涉及：

• WHERE：先篩選符合條件的資料列。
• GROUP BY：依出版社分組。
• COUNT(*)：計算每家出版社出版的書籍數量。
• AVG(Price)：計算每家出版社的平均書價。
• HAVING：篩選分組後的聚合結果。
• ORDER BY ... DESC：依書籍數量由多至少排序。
• FETCH FIRST 5 ROWS ONLY：取排序後的前五筆資料。

本題的條件順序是：

1. 只考慮出版年份晚於 2016 年的書。
2. 依 Publisher 分組。
3. 計算各出版社的書籍數量與平均價格。
4. 捨棄平均價格低於 550 的出版社。
5. 依書籍數量遞減排序。
6. 取前五家出版社。

解題方法

WHERE 必須放在 GROUP BY 前，用來先限制資料範圍；AVG(Price) 是分組後才能計算的聚合值，因此平均價格條件必須放在 HAVING，不能放在 WHERE。

SELECT
    Publisher,
    COUNT(*) AS BookCount
FROM Book
WHERE "Published Year" > 2016
GROUP BY Publisher
HAVING AVG(Price) >= 550
ORDER BY BookCount DESC
FETCH FIRST 5 ROWS ONLY;

若使用支援 LIMIT 的資料庫，也可寫成：

SELECT
    Publisher,
    COUNT(*) AS BookCount
FROM Book
WHERE "Published Year" > 2016
GROUP BY Publisher
HAVING AVG(Price) >= 550
ORDER BY BookCount DESC
LIMIT 5;

其中：

• "Published Year" > 2016：只保留 2017 年以後出版的書。
• GROUP BY Publisher：將書籍按照出版社分組。
• COUNT(*) AS BookCount：計算每個出版社符合年份條件的書籍數。
• HAVING AVG(Price) >= 550：保留平均書價至少為 550 的出版社。
• ORDER BY BookCount DESC：書籍數量最多的出版社排在前面。
• FETCH FIRST 5 ROWS ONLY 或 LIMIT 5：取前五家出版社。