高雄醫學大學 115 年 《計算機概論與程式設計》

核心觀念

直接對映快取（direct-mapped cache）的 32 位元記憶體位址，通常分為：

$$\text{Tag} \mid \text{Index} \mid \text{Offset}$$

三個欄位的功能如下：

• Offset：指出資料位於一個 cache block 內的哪一個位元組。
• Index：指出資料要放入哪一條 cache line。
• Tag：辨識目前 cache line 中所存的記憶體區塊是否為目標區塊。

位址總位元數滿足：

$$\text{Tag bits}+\text{Index bits}+\text{Offset bits}=32$$

---

解題方法

1. 計算 Offset 位元數

題目說明記憶體為 byte-addressable，且每個 block 大小為 64 bytes。

因此，區塊內需要辨識 64 個不同的位元組位置：

$$\text{Offset bits}=\log_2 64=6$$

2. 計算 Index 位元數

Cache 共有 16 條 cache lines。直接對映快取中，每個記憶體區塊會依照 Index 對應至其中一條 cache line。

因此：

$$\text{Index bits}=\log_2 16=4$$

3. 計算 Tag 位元數

32 位元位址扣除 Offset 與 Index：

核心觀念

本題考 Banker’s Algorithm（銀行家演算法） 的資源請求判定與安全性檢查。

每個行程尚需的資源量為：

$$Need = Maximum - Allocation$$

系統接受某行程的請求，必須依序符合：

1. 請求量不得超過該行程的尚需量：
   $Request_i \leq Need_i$
2. 請求量不得超過目前可用資源：
   $Request_i \leq Available$
3. 暫時核准後，系統仍須存在一個安全序列，使所有行程都能完成。

---

解題方法

1. 計算各行程的 Need

Process	Allocation	Maximum	Need
$P_0$	$(2,0,1)$	$(4,2,2)$	$(2,2,1)$
$P_1$	$(3,1,2)$	$(5,3,3)$	$(2,2,1)$
$P_2$	$(1,2,0)$	$(3,3,2)$	$(2,1,2)$

目前：

$$Available=(2,1,2)$$

判斷請求時，先檢查請求是否小於等於 $Need$ 與 $Available$，再進行安全性檢查。

---

選項分析

（A）$P_0$ requests $(1,1,0)$

先檢查基本條件：

$$(1,1,0)\leq Need_0=(2,2,1)$$

符合；但核准後：

$$Available'=(2,1,2)-(1,1,0)=(1,0,2)$$ $$Allocation_0'=(2,0,1)+(1,1,0)=(3,1,1)$$ $$Need_0'=(4,2,2)-(3,1,1)=(1,1,1)$$

進行安全性檢查，令：

$$Work=(1,0,2)$$

各行程的 Need 為：

• $P_0$：$(1,1,1)$，其 $B$ 類資源需要 $1$，但 $Work_B=0$，無法完成。
• $P_1$：$(2,2,1)$，無法完成。
• $P_2$：$(2,1,2)$，無法完成。

沒有任何行程可以先完成，因此不存在安全序列，核准後會進入不安全狀態。

故（A）錯誤。

---

（B）$P_1$ requests $(2,2,1)$

此請求雖然符合：

$$(2,2,1)\leq Need_1=(2,2,1)$$

但目前可用資源為：

$$Available=(2,1,2)$$

其中 $B$ 類資源請求 $2$，但目前只有 $1$：

$$2>1$$

因此系統目前無法立即提供此請求。

故（B）錯誤。

---

（C）$P_2$ requests $(2,1,2)$

先檢查：

$$(2,1,2)\leq Need_2=(2,1,2)$$

且：

$$(2,1,2)\leq Available=(2,1,2)$$

兩項條件皆符合。

暫時核准後：

$$Available'=(2,1,2)-(2,1,2)=(0,0,0)$$ $$Allocation_2'=(1,2,0)+(2,1,2)=(3,3,2)$$

此時：

$$Need_2'=(3,3,2)-(3,3,2)=(0,0,0)$$

令：

$$Work=(0,0,0)$$

核心觀念

本題考查 CNN（Convolutional Neural Network，卷積神經網路）與 Transformer 在「輸入特徵擷取方式」上的差異。

• CNN 使用卷積運算，以固定大小的卷積核在輸入資料上滑動，擷取鄰近位置的局部特徵，例如影像中的邊緣、紋理與形狀。
• Transformer 使用 Self-Attention（自注意力機制），計算輸入中不同位置彼此的關聯，因此能直接建模較長距離甚至全域性的關係。

CNN 的核心特色是「局部性」與「權重共享」；Transformer 的核心特色是「位置間的關聯建模」。

解題方法

判斷關鍵在於辨識兩種模型的主要特徵擷取機制：

1. 題目提到「convolution」與「local spatial patterns」時，對應 CNN。
2. 題目提到「self-attention」與「global relationships」時，對應 Transformer。
3. 再排除將兩者說成完全相同、需要人工設計濾波器，或限制其只能處理單一資料類型的錯誤敘述。

因此，符合正確差異的敘述是「CNN 擷取局部空間模式，而 Transformer 透過自注意力建模全域關係」。

選項分析

(A) CNNs rely on global attention mechanisms, while Transformers use fixed-size convolutional filters.

錯誤。敘述將兩者的機制對調。

• CNN 主要使用固定大小的卷積核擷取局部特徵，並非依賴全域注意力。
• Transformer 主要使用 Self-Attention，並非以固定大小的卷積濾波器作為核心特徵擷取方式。

(B) CNNs and Transformers extract features in identical ways but differ only in training speed.

錯誤。CNN 與 Transformer 的特徵擷取方式並不相同。

• CNN 透過卷積運算處理局部鄰域。
• Transformer 透過自注意力計算不同位置之間的依賴關係。

兩者除了訓練速度外，在模型結構、資訊互動範圍與特徵擷取方式上都有重要差異。

核心觀念

本題考查物聯網（Internet of Things, IoT）常用通訊協定 MQTT（Message Queuing Telemetry Transport）的設計特色。

MQTT 的核心特點包括：

• 採用 發布／訂閱（publish/subscribe）模型。
• 透過 **訊息代理伺服器（broker）**轉送訊息。
• 適合頻寬有限、裝置運算能力弱、電力受限的環境。
• 訊息封包標頭小、通訊負擔低。
• 通常建立在 TCP/IP 之上，並可透過 QoS（Quality of Service）機制提供不同程度的傳遞可靠性。

MQTT 的基本架構如下：

1. 發布者（publisher）將訊息發布至某個主題（topic）。
2. 訂閱者（subscriber）訂閱感興趣的主題。
3. Broker 接收訊息，再轉送給所有符合訂閱條件的訂閱者。

例如，溫度感測器可以發布：

topic: home/room1/temperature
message: 26.5

空調控制器只要訂閱該主題，就能接收溫度資料，而不需要直接知道感測器的位置或網路位址。

---

解題方法

判斷 MQTT 的關鍵，可從三個方向切入：

1. 是否適合 IoT 裝置的低頻寬、低功耗環境？
2. 是否採用發布／訂閱架構？
3. 是否屬於應用層通訊協定，而非取代 TCP/IP 的底層網路協定？

只要選項同時符合「低頻寬、低功耗」與「publish/subscribe」，即符合 MQTT 的典型特徵。

因此正確敘述為：

It is optimized for low-bandwidth, low-power communication using a publish/subscribe model.

---

選項分析

(A) It is a high-bandwidth protocol designed for video streaming.

錯誤。

MQTT 並非為高頻寬影音串流設計。它的設計目標是讓感測器、嵌入式裝置等資源受限設備，以較小的通訊負擔傳送資料。

影音串流通常需要高頻寬、低延遲與持續大量資料傳輸，常見技術包括串流媒體協定與影音編碼機制，這不是 MQTT 的主要用途。

---

(B) It is mainly used for peer-to-peer file sharing.

錯誤。

MQTT 採用的是發布／訂閱模型，並透過 Broker 集中管理訊息，不是點對點（peer-to-peer）的檔案分享協定。

在 MQTT 中：

核心觀念

本題考查 IPv4 標頭的格式、欄位功能、TTL（Time To Live）、標頭檢查碼，以及 IPv4 位址空間。

判斷重點如下：

• IPv4 標頭長度以 32 位元（4 bytes）為單位。
• DSCP 用於差異化服務與封包優先權分類。
• TTL 用來限制資料報可經過的路由器數量。
• IPv4 標頭檢查碼只驗證「標頭」，不能用來重組分割後的完整封包。
• IPv4 位址欄位長度為 32 位元，因此理論位址數為 $2^{32}$。

---

解題方法

本題是單選題，直接逐一核對各敘述是否符合 IPv4 標頭定義即可。

其中最關鍵的是分辨：

1. IPv4 fragmentation 使用哪些欄位重組封包。
2. Header Checksum 的驗證範圍。
3. TTL 是「時間」概念，還是可用來限制封包通過的路由器數量。

---

選項分析

(A) IPv4 header is 4-byte aligned.

正確。

IPv4 標頭的基本長度為 20 bytes，若包含 Options，標頭長度必須以 32 位元為單位增加。標頭長度欄位 IHL（Internet Header Length）表示的是 32-bit words 數量：

$$\text{Header Length}=\text{IHL}\times 4\text{ bytes}$$

因此 IPv4 標頭長度必定是 4 bytes 的整數倍，例如：

• IHL = 5：$5\times4=20$ bytes
• IHL = 6：$6\times4=24$ bytes
• IHL = 15：$15\times4=60$ bytes

所以「IPv4 標頭為 4-byte aligned」正確。

---

(B) Differentiated Services Code Point (DSCP) is used for specifying differentiated services.

正確。

DSCP 位於 IPv4 標頭原本的 ToS（Type of Service）欄位，現稱 DS Field。DSCP 佔 6 bits，用來標示封包應接受的差異化服務，例如：

• 優先轉送
• 流量分類
• 延遲、可靠度或頻寬需求
• QoS（Quality of Service）處理方式

因此 DSCP 確實用於指定差異化服務。

---

(C) The IPv4 TTL is an upper bound of routers that an IP datagram can pass.

正確。

TTL 欄位的主要目的，是防止封包因路由迴圈而在網路中無限循環。每經過一個路由器，TTL 至少會減少 1；當 TTL 減至 0 時，路由器會丟棄該封包。

若初始 TTL 為 $T_0$，封包經過 $n$ 個路由器後，通常可表示為：

$$T_{\text{final}}=T_0-n$$

要能繼續轉送，必須滿足：

$$T_{\text{final}}>0$$

因此可通過的路由器數量受到初始 TTL 的上限限制，通常可視為：

$$n\leq T_0$$

校方釋疑指出，TTL 是「封包可通過之路由器數量的上界」；即使處理延遲造成 TTL 一次減少超過 1，最後的 TTL 仍會小於初始 TTL，不會使封包通過的路由器數超過初始 TTL 所形成的上限。因此依官方說明，(C) 應判定為正確。

核心觀念

本題比較「單向鏈結串列（singly linked list）」與「陣列（array）」在不同操作下的時間複雜度。

1. 單向鏈結串列

每個節點通常包含資料與下一個節點的指標：

[node data | next] -> [node data | next] -> ...

若已經知道欲處理的節點位置，修改其 next 指標只需固定次數的操作，因此可達到 $O(1)$。

2. 陣列

陣列元素儲存在連續記憶體中。若在中間刪除一個元素，後方元素必須向前搬移，以維持連續排列，因此通常需要移動 $O(n)$ 個元素。

3. 複雜度中的 $n$

$n$ 表示資料結構中元素的數量。時間複雜度描述的是資料規模增大時，操作所需時間如何成長。

---

解題方法

逐一判斷各選項所描述的操作：

1. 是否需要走訪節點尋找位置？
2. 是否需要搬移大量元素？
3. 是否只需修改少數指標？
4. 題目是否使用了「always」等絕對字眼？

本題關鍵在於：

• 單向鏈結串列的中間節點若已知，刪除可局部完成，為 $O(1)$。
• 陣列刪除中間元素後，後方元素必須搬移，為 $O(n)$。

---

選項分析

(A) 正確

Deleting an element from the middle of a linked list, when the node is already known, takes $O(1)$, while deleting from the middle of an array takes $O(n)$.

此敘述符合本題設定，故正確。

單向鏈結串列

假設欲刪除的節點為 p，且 p 位於中間，因此一定存在下一個節點。依照 CLRS 所採用的單向鏈結串列操作概念，可將後繼節點的資料複製到目前節點，再讓目前節點跳過後繼節點：

p->data = p->next->data;
p->next = p->next->next;

逐步分析：

1. 讀取 p->next->data：$O(1)$
2. 將資料寫入 p->data：$O(1)$
3. 修改 p->next：$O(1)$

總操作次數為固定數量，因此：

$$T(n)=O(1)$$

這種作法的重點是「邏輯刪除」。節點 p 的記憶體位置仍存在，但其內容被後繼節點取代，後繼節點則從鏈結關係中移除。若實作語言需要手動釋放記憶體，釋放被跳過的節點仍是固定時間操作，不影響 $O(1)$ 的時間複雜度。

校方釋疑公告亦明確指出，題目特別限定「middle」，排除了尾節點的例外情形；在節點已知且位於中間的前提下，透過複製後繼節點資料並調整指標，即可完成 $O(1)$ 的邏輯刪除。

陣列

假設陣列如下：

[10, 20, 30, 40, 50, 60]

刪除中間元素 30 後，必須將後方元素往前搬移：

[10, 20, 40, 50, 60]

至少需要搬移：

40 -> 30 的位置
50 -> 40 的位置
60 -> 50 的位置

若刪除位置靠近前方，可能需要搬移接近 $n$ 個元素，因此最壞時間複雜度為：

$$T(n)=O(n)$$

所以 (A) 正確。

---

(B) 錯誤

Inserting an element at the beginning of a linked list takes $O(n)$, while inserting at the beginning of an array takes $O(1)$.

實際情況正好相反。

單向鏈結串列開頭插入

只需讓新節點指向原本的第一個節點，再更新頭指標：

newNode->next = head;
head = newNode;

只涉及固定次數的指標操作，因此：

$$T(n)=O(1)$$

陣列開頭插入

為了騰出第一個位置，原有元素必須全部向後移動：

原陣列：[10, 20, 30, 40]
插入 5：[5, 10, 20, 30, 40]

最多需要移動 $n$ 個元素，因此：

$$T(n)=O(n)$$

故 (B) 將兩者複雜度完全顛倒，錯誤。

---

(C) 錯誤

核心觀念

本題考查資料隱私保護中的 $k$-anonymity（$k$-匿名性）。

$k$-匿名性的核心要求是：在資料集公開前，針對能辨識個人的特徵，例如年齡、性別、郵遞區號、職業等「準識別資訊」（quasi-identifiers）進行概括化或抑制，使每筆資料至少能與其他 $k-1$ 筆資料具有相同的準識別資訊組合。

因此，每一個由準識別資訊形成的等價類別（equivalence class）至少包含 $k$ 筆紀錄。對外部觀察者而言，該筆紀錄最多只能被縮小到 $k$ 個候選人，難以直接判定其對應的真實個人。

例如，若資料表經處理後，某一組資料如下：

年齡區間	性別	郵遞區號	疾病
20–29	男	800	A
20–29	男	800	B
20–29	男	800	C

這三筆紀錄的準識別資訊完全相同，形成大小為 $3$ 的等價類別，因此符合 $3$-anonymity。

解題方法

判斷本題的關鍵，是找出選項中是否描述「每筆紀錄至少與 $k-1$ 筆其他紀錄無法區分」。

$k$-匿名性的定義可表示為：

$$\text{每個等價類別的大小} \geq k$$

也就是每筆紀錄必須至少和另外 $k-1$ 筆紀錄，在指定的識別屬性上相同或不可區分。符合此定義的敘述為選項 (B)。

選項分析

(A) Encrypting sensitive data using strong cryptographic algorithms

錯誤。此選項描述的是資料加密（encryption），利用密碼學演算法將資料轉換成未授權者無法直接理解的形式。加密主要保護資料在儲存或傳輸過程中的機密性；$k$-匿名性則是透過降低資料的可辨識程度，使多筆紀錄在準識別資訊上無法區分，兩者是不同的隱私保護方法。

(B) Ensuring each record is indistinguishable from at least $k-1$ other records based on certain identifying attributes

正確。此選項完整描述 $k$-匿名性的定義：每筆紀錄根據特定識別屬性，至少要與其他 $k-1$ 筆紀錄不可區分，形成至少包含 $k$ 筆資料的等價類別。

核心觀念

本題考查關聯規則（association rule）的四個常用衡量指標：

• Support（支持度）
• Confidence（信賴度）
• Lift（提升度）
• Conviction（確信度）

已知：

• 交易總數：$1{,}000{,}000$
• $X$ 出現於 $12{,}000$ 筆交易
• $Y$ 出現於 $15{,}000$ 筆交易
• $X\cup Y$ 同時出現於 $9{,}000$ 筆交易

先換算支持度：

$$\operatorname{support}(X)=\frac{12{,}000}{1{,}000{,}000}=0.012$$ $$\operatorname{support}(Y)=\frac{15{,}000}{1{,}000{,}000}=0.015$$ $$\operatorname{support}(X\cup Y)=\frac{9{,}000}{1{,}000{,}000}=0.009$$

---

解題方法

對規則 $X\to Y$：

1. Confidence

信賴度表示：在已出現 $X$ 的交易中，同時出現 $Y$ 的比例。

$$\operatorname{confidence}(X\to Y) = \frac{\operatorname{support}(X\cup Y)} {\operatorname{support}(X)}$$

代入數值：

$$\operatorname{confidence}(X\to Y) = \frac{0.009}{0.012} = \frac{9{,}000}{12{,}000} = 0.75$$

因此選項（A）正確。

2. Lift

提升度用來衡量 $X$ 與 $Y$ 是否具有關聯：

$$\operatorname{lift}(X\to Y) = \frac{\operatorname{confidence}(X\to Y)} {\operatorname{support}(Y)}$$ $$\operatorname{lift}(X\to Y) = \frac{0.75}{0.015} = 50$$

因為 $50>1$，表示同時出現 $X$ 與 $Y$ 的情況，遠高於兩者獨立時的預期。

3. Conviction

確信度定義為：

$$\operatorname{conviction}(X\to Y) = \frac{1-\operatorname{support}(Y)} {1-\operatorname{confidence}(X\to Y)}$$ $$\operatorname{conviction}(X\to Y) = \frac{1-0.015}{1-0.75} = \frac{0.985}{0.25} = 3.94$$

因此 conviction 大於 $1$。

---

選項分析

（A）The confidence of the rule $X\to Y$ is 0.75.

正確。

$$\operatorname{confidence}(X\to Y) = \frac{9{,}000}{12{,}000} = 0.75$$

核心觀念

本題考查管線化處理器（pipelined processor）中的三類危障（hazard）：

1. 結構危障（structural hazard）：多個指令同時需要同一項硬體資源。
2. 資料危障（data hazard）：目前指令需要使用前一指令尚未完成產生的資料。
3. 控制危障（control hazard）：處理器尚未確定程式的下一個執行位址，常發生於分支或跳躍指令。

控制危障的核心原因是：分支指令的執行結果會決定下一條要擷取的指令，但管線必須提前進行 instruction fetch，因此可能擷取到錯誤路徑上的指令。

---

解題方法

判斷各選項所描述的問題類型，再與 control hazard 的定義比對。

若處理器遇到條件分支，例如：

if (x == 0)
 goto L1;
else
 goto L2;

在分支條件尚未計算完成前，處理器不知道下一步應該：

• 擷取 L1 的指令；
• 擷取 L2 的指令；
• 繼續執行分支指令後方的順序指令。

此時管線可能先擷取錯誤路徑的指令。待分支結果確定後，錯誤擷取的指令必須被清除（flush），並改從正確位址重新擷取，造成管線停頓與效能損失。這就是控制危障。

因此，最直接造成 control hazard 的情況是：

處理器遇到結果尚未確定的分支指令。

---

選項分析

(A) Two instructions require the same hardware resource at the same time.

兩個指令在同一時間需要相同硬體資源，例如：

• 兩個指令同時需要唯一的記憶體存取單元；
• 兩個指令同時需要同一個算術邏輯單元；
• 同一個暫存器檔案寫入埠不足。

這會造成結構危障（structural hazard），而非控制危障。

因此，(A) 錯誤。

---

(B) An instruction depends on the result of a previous instruction.

目前指令依賴前一指令尚未完成的結果，例如：

ADD R1, R2, R3
SUB R4, R1, R5

SUB 必須使用 ADD 寫入 R1 的結果。若 ADD 尚未完成，SUB 便可能讀不到正確資料。

這屬於資料危障（data hazard），常見形式包括：

核心觀念

本題考查作業系統中的同步機制，重點是區分：

• Mutex lock（互斥鎖）：確保同一時間最多只有一個執行緒或行程進入臨界區（critical section）。
• Binary semaphore（二元信號量）：信號量值通常為 $0$ 或 $1$，可用於互斥，但不一定具備互斥鎖的所有語意。
• Counting semaphore（計數型信號量）：初始值代表同時可使用共享資源的數量上限。

信號量通常透過兩個不可分割的原子操作管理：

• wait、P：嘗試取得資源，信號量減 $1$；若資源不足，行程阻塞。
• signal、V：釋放資源，信號量加 $1$，並喚醒等待中的行程。

若計數型信號量初始值為 $N$，在正確執行 wait 與 signal 的前提下，最多允許 $N$ 個行程同時取得資源。

---

解題方法

判斷各選項時，依序檢查下列三個關鍵性質：

1. Mutex 是否保證「同一時間只能有一個」執行者進入臨界區。
2. Counting semaphore 的初始值是否代表可同時使用的資源數量。
3. Mutex 或 semaphore 是否本身保證避免死結（deadlock）與公平排程（fairness）。

其中，只有描述「計數型信號量可依初始值限制並行存取數量」的選項符合定義。

---

選項分析

(A) A mutex allows multiple processes to enter a critical section simultaneously as long as they release the lock quickly.

錯誤。

Mutex 的核心功能就是互斥。當某一行程持有 mutex 時，其他行程必須等待，即使持有者很快釋放鎖，也不會允許多個行程同時進入臨界區。

「很快釋放」只會影響等待時間，不會改變 mutex 的互斥性質。正確敘述應為：

Mutex 同一時間最多允許一個行程進入臨界區。

---

(B) A counting semaphore can allow a limited number of processes to access a shared resource concurrently, based on its initial value.

正確。

計數型信號量的初始值可代表可用資源的數量。若設定：

$$S=N$$

則最多允許 $N$ 個行程同時取得資源。

每個行程進入資源區前執行一次 wait(S)：

$$S \leftarrow S-1$$

離開後執行一次 signal(S)：

$$S \leftarrow S+1$$

核心觀念

本題考查循環神經網路（Recurrent Neural Network, RNN）的「梯度消失」（vanishing gradient）及其典型改良架構。

標準 RNN 在時間步 $t$ 的隱藏狀態通常表示為：

$$\mathbf{h}_t=\phi\left(\mathbf{W}_{hh}\mathbf{h}_{t-1}+\mathbf{W}_{xh}\mathbf{x}_t+\mathbf{b}\right)$$

訓練時使用時間序列反向傳播（Backpropagation Through Time, BPTT）。若要將較後面時間點的誤差傳回較早時間點，梯度會連續乘上許多項：

$$\frac{\partial \mathcal{L}}{\partial \mathbf{h}_k} = \frac{\partial \mathcal{L}}{\partial \mathbf{h}_T} \prod_{t=k+1}^{T} \frac{\partial \mathbf{h}_t}{\partial \mathbf{h}_{t-1}}$$

其中每一項大致包含遞迴權重矩陣 $\mathbf{W}_{hh}$ 與啟動函數導數。當這些乘積的大小長期小於 $1$，梯度會隨時間步數增加而快速趨近於 $0$，形成梯度消失；若乘積大於 $1$，則會形成梯度爆炸。

---

解題方法

判斷本題的關鍵，是找出「能從架構上改善長期梯度傳遞」的選項。

LSTM（Long Short-Term Memory）在標準 RNN 上加入：

• 遺忘閘（forget gate）
• 輸入閘（input gate）
• 輸出閘（output gate）
• 細胞狀態（cell state）

LSTM 的細胞狀態更新式為：

$$\mathbf{c}_t = \mathbf{f}_t\odot\mathbf{c}_{t-1} + \mathbf{i}_t\odot\widetilde{\mathbf{c}}_t$$

其中 $\odot$ 表示逐元素相乘。細胞狀態具有「加法式」資訊傳遞路徑，因此梯度可以沿著細胞狀態較穩定地傳遞；遺忘閘也能學習保留或捨棄資訊，降低長期依賴所造成的梯度消失。

因此，LSTM 是針對標準 RNN 梯度消失問題所設計的典型架構改良。

---

選項分析

(A) Increasing the learning rate

提高學習率只會改變參數更新的步幅：

$$\theta \leftarrow \theta-\eta\nabla_\theta\mathcal{L}$$

核心觀念

本題考查 Network Function Virtualization（NFV，網路功能虛擬化）的定義與主要目的。

傳統網路服務通常由專用硬體設備提供，例如：

• 防火牆（Firewall）
• 入侵偵測系統（IDS）
• 負載平衡器（Load Balancer）
• 網路位址轉換器（NAT）
• 虛擬私人網路閘道器（VPN Gateway）

NFV 的核心作法，是將這些原本依賴專用硬體的網路功能，改以軟體形式執行在一般伺服器、虛擬機器或容器上。這些虛擬化的網路功能稱為 Virtual Network Functions（VNFs）。

因此，NFV 可降低對專用硬體的依賴，提升部署彈性，也能依據流量需求動態增加或減少資源。

解題方法

判斷 NFV 的關鍵，在於掌握「虛擬化網路功能」這個核心詞組：

$$\text{專用硬體網路設備功能} \quad\longrightarrow\quad \text{軟體化、虛擬化的網路服務}$$

題目問的是 NFV 的 primary function，應選擇直接描述上述轉換的選項。

選項（B）指出 NFV 將傳統上運行於專用硬體設備的網路服務虛擬化，完整符合 NFV 的定義。

選項分析

（A）It centralizes routing decisions into a single hardware controller.

錯誤。

此敘述較接近對集中式控制架構或 Software-Defined Networking（SDN）的片面描述。SDN 著重於將控制平面與資料平面分離，並可由集中式或邏輯集中式控制器管理網路設備。

NFV 的重點不是把路由決策集中到單一硬體控制器，也不限定使用硬體控制器。NFV 著重的是將網路服務功能軟體化與虛擬化。

（B）It virtualizes network services that traditionally run on dedicated hardware devices.

正確。

NFV 將防火牆、負載平衡、NAT、VPN 等傳統專用硬體功能，轉換為可在一般運算平台上執行的軟體網路功能。

其主要效益包括：

• 降低專用硬體設備的採購與維護成本
• 加快網路服務部署速度
• 依需求彈性擴充或縮減資源
• 讓網路功能能以軟體方式升級與管理

這正是 NFV 的主要功能。

核心觀念

本題考查加權圖的最短路徑，以及 Dijkstra’s algorithm 的操作流程。

• adjacency matrix 中的數值代表兩個節點間的邊權重。
• $\infty$ 表示兩節點間沒有直接連線。
• 矩陣上下三角對稱，表示本題為無向圖。
• Dijkstra 演算法適用於所有邊權重皆為非負數的圖。
• 每次選取目前「尚未確定、暫定距離最小」的節點，將其視為已確定，並更新相鄰節點的暫定距離。

要求的是從節點 $0$ 到節點 $2$ 的最短距離。

---

解題方法與逐步追蹤

初始設定：

$$d(0)=0,\qquad d(1)=d(2)=d(3)=\infty$$

其中 $d(x)$ 表示目前已知從節點 $0$ 到節點 $x$ 的最短暫定距離。

Dijkstra 的核心更新公式為：

$$d(v)\leftarrow \min\bigl(d(v),d(u)+w(u,v)\bigr)$$

其中 $u$ 是目前選出的節點，$w(u,v)$ 是邊 $(u,v)$ 的權重。

第一步：選取節點 $0$

節點 $0$ 是起點，距離為 $0$。由節點 $0$ 出發：

• 到節點 $1$：$0+4=4$
• 到節點 $3$：$0+2=2$
• 到節點 $2$：沒有直接邊，仍為 $\infty$

更新後：

$$d(0)=0,\quad d(1)=4,\quad d(2)=\infty,\quad d(3)=2$$

此時確定節點 $0$。

第二步：選取節點 $3$

尚未確定的節點中，暫定距離最小的是節點 $3$，其距離為 $2$。

由節點 $3$ 出發，節點 $3$ 與節點 $2$ 的邊權重為 $1$：

$$d(2)=\min(\infty,d(3)+1) =\min(\infty,2+1) =3$$

更新後：

$$d(0)=0,\quad d(1)=4,\quad d(2)=3,\quad d(3)=2$$

此時確定節點 $3$。

第三步：選取節點 $2$

剩餘節點中，節點 $2$ 的暫定距離為 $3$，小於節點 $1$ 的 $4$，因此確定節點 $2$。

一旦目的節點 $2$ 被確定，其最短距離即為：

$$\boxed{3}$$

對應的最短路徑為：

$$0\rightarrow 3\rightarrow 2$$

路徑總權重：

$$w(0,3)+w(3,2)=2+1=3$$

---

關鍵伪程式碼

核心觀念

本題考查遞迴（recursion）的兩個必要組成：

1. 基底條件（base case）：停止遞迴的條件。
2. 遞迴呼叫（recursive call）：將問題縮小，逐步接近基底條件。

計算 $1$ 到 $n$ 的總和可表示為：

$$S(n)= \begin{cases} 1, & n=1\\ n+S(n-1), & n>1 \end{cases}$$

因此，每次遞迴都必須把參數由 $n$ 減少為 $n-1$。

---

原程式的錯誤

原程式如下：

def sum_to_n(n):
 if n == 1: # base case
 return 1
 else:
 return n + sum_to_n(n)

錯誤位於：

sum_to_n(n)

遞迴呼叫時參數仍然是 $n$，沒有逐步減少。

例如執行 sum_to_n(3)：

sum_to_n(3)
= 3 + sum_to_n(3)
= 3 + 3 + sum_to_n(3)
= 3 + 3 + 3 + sum_to_n(3)
...

由於參數永遠是 $3$，永遠不會達到 n == 1，最後會造成無限遞迴，並引發 Python 的 RecursionError。

---

解題方法與正確程式碼

當目前要計算 $1$ 到 $n$ 的總和時，可以先取出 $n$，再加上 $1$ 到 $n-1$ 的總和：

$$S(n)=n+S(n-1)$$

所以應將遞迴呼叫改為 sum_to_n(n-1)：

def sum_to_n(n):
 if n == 1: # base case
 return 1
 else:
 return n + sum_to_n(n - 1)

---

逐步追蹤（Trace）

以 sum_to_n(4) 為例：

sum_to_n(4)
= 4 + sum_to_n(3)
= 4 + 3 + sum_to_n(2)
= 4 + 3 + 2 + sum_to_n(1)
= 4 + 3 + 2 + 1
= 10

函式返回的順序如下：

sum_to_n(1) = 1
sum_to_n(2) = 2 + 1 = 3
sum_to_n(3) = 3 + 3 = 6
sum_to_n(4) = 4 + 6 = 10

因此，程式正確計算出：

$$1+2+3+4=10$$

---

選項分析

(A) Change sum_to_n(n) to sum_to_n(n-1) in the recursive call

正確。

改成：

return n + sum_to_n(n - 1)

核心觀念

本題考查「雜湊（hashing）」與「加密（encryption）」的用途差異。

雜湊函數會將任意長度的輸入資料，經由固定的計算程序轉換成摘要值（hash value 或 digest）。其主要特性包括：

• 單向性（one-way）：由原文計算雜湊值容易，但無法有效率地由雜湊值還原原文。
• 固定長度輸出：多數密碼學雜湊函數會產生固定長度的摘要，例如 SHA-256 產生 $256$ 位元的輸出。
• 不需要共享密鑰：一般雜湊函數本身不使用密鑰。
• 可處理各種形式的資料：不只限於文字，也可以處理圖片、檔案、程式或任意位元資料。

相對地，資料加密的目的是讓資料在需要時能夠由合法持有者解密還原，因此加密演算法必須具有可逆性，通常搭配金鑰使用：

$$\text{明文} \xrightarrow{\text{加密}} \text{密文} \xrightarrow{\text{解密}} \text{明文}$$

雜湊則是：

$$\text{資料} \xrightarrow{\text{雜湊}} \text{摘要值}$$

摘要值的設計目的不是還原原始資料，而是用來進行完整性驗證、密碼儲存或資料指紋比對。

解題方法

題幹問：「為什麼 hashing 不適合用來加密日後需要恢復的資料？」

關鍵在於辨認「需要恢復」代表必須能從處理後的結果取得原始資料。因此，適合此用途的技術應該是可逆的加密；而雜湊函數具有單向性，無法有效反推輸入。

因此，直接選擇描述「雜湊不可逆」的選項：

$$\boxed{\text{Hash functions are one-way functions and cannot be reversed.}}$$

選項分析

(A) Hash functions are computationally expensive to compute.

錯誤。

雜湊函數通常設計成可以快速計算。雖然不同雜湊演算法的計算成本可能不同，但「計算昂貴」不是雜湊不適合資料恢復的根本原因。

真正的問題是：即使已經快速算出雜湊值，也不能由雜湊值有效還原原始資料。

---

(B) Hash functions generate variable-length outputs.

錯誤。

密碼學雜湊函數通常會產生固定長度的輸出。例如：

• SHA-256：輸出 $256$ 位元
• SHA-512：輸出 $512$ 位元
• MD5：輸出 $128$ 位元

核心觀念

本題考查四類常見資料探勘與機器學習演算法：

• Apriori：關聯規則探勘，利用支持度的反單調性質篩選頻繁項目集。
• $k$-means：分群演算法，透過反覆更新群中心與分配群組來最小化群內平方誤差。
• 決策樹：利用資訊增益、增益率等不純度指標選擇切割屬性。
• DBSCAN：以密度為基礎的分群方法，不需事先指定群數。
• PCA：非監督式降維方法，尋找能保留最大變異的方向。

---

解題方法

判斷這類敘述時，應逐一核對：

1. 演算法的學習類型：監督式或非監督式。
2. 演算法的核心目標函數或評估指標。
3. 是否需要事先指定群數或其他參數。
4. 演算法的搜尋策略與保證性質。
5. 演算法適用的資料型態與群集形狀。

其中，若選項同時混合正確與錯誤的演算法特徵，通常關鍵錯誤會出現在「搜尋策略」、「最佳化保證」、「是否需要指定參數」或「監督／非監督」等字眼。

---

選項分析

(A) Apriori 使用深度優先搜尋，並以資訊增益刪除候選項目集

此敘述錯誤。

Apriori 採用的是逐層、廣度優先的候選項目集生成方式，而非深度優先搜尋。其流程大致如下：

1. 找出頻繁 $1$-項目集 $L_1$。
2. 由 $L_k$ 產生候選 $(k+1)$-項目集 $C_{k+1}$。
3. 計算候選項目集的支持度。
4. 刪除支持度低於門檻的候選項目集。
5. 重複上述步驟。

Apriori 的核心依據是頻繁項目集的反單調性質：

若某個項目集不是頻繁項目集，則包含它的任何超集合也不會是頻繁項目集。

其形式為：

$$X \notin \text{Frequent} \Rightarrow \forall Y \supseteq X,\; Y \notin \text{Frequent}$$

因此，Apriori 是根據**支持度（support）**進行剪枝，而非使用資訊增益（information gain）。資訊增益主要用於決策樹的屬性選擇。

Apriori 的候選項目集數量在最壞情況下可能呈指數成長，若共有 $m$ 個不同項目，所有非空項目集最多有：

$$2^m-1$$

因此其時間複雜度通常具有指數級最壞情況，空間複雜度也可能因候選集數量龐大而快速增加。

---

(B) $k$-means 因每次降低群內變異數，所以保證收斂至全域最佳解

此敘述錯誤。

$k$-means 的目標是最小化群內平方誤差，通常稱為 within-cluster sum of squares：

$$J=\sum_{i=1}^{k}\sum_{x\in C_i}\|x-\mu_i\|^2$$

其中：

• $C_i$ 為第 $i$ 個群集；
• $\mu_i$ 為第 $i$ 個群集的中心；
• $k$ 為群集數量。

每次迭代通常包含兩個步驟：

1. 分配步驟：將每筆資料分配給距離最近的群中心。
2. 更新步驟：重新計算每個群集的平均值作為新的群中心。

這兩個步驟會使目標函數不增加，因此演算法通常會收斂。然而，這只能保證收斂至某個局部最佳解或固定點，不能保證為全域最佳解。

結果高度依賴：

• 初始群中心；
• 群集數 $k$；
• 資料尺度；
• 距離函數。

因此實務上常使用 $k$-means++ 選擇較佳初始中心，或重複執行多次後選擇目標函數最小的結果。

若資料筆數為 $n$、群集數為 $k$、維度為 $d$、迭代次數為 $t$，常見時間複雜度約為：

$$O(nkdt)$$

空間複雜度約為：

$$O(n+kd)$$

其中 $O(n)$ 用於儲存資料的群組標籤，$O(kd)$ 用於儲存群中心。

---

(C) ID3 與 C4.5 使用不純度指標選擇屬性，並遞迴切割資料空間

此敘述正確。

決策樹演算法會在每個節點選擇適合的屬性進行切割，讓切割後的子節點更加純粹，並以遞迴方式建立樹狀模型。

1. ID3 與資訊增益

ID3 常使用熵（entropy）衡量資料的不純度：

$$H(S)=-\sum_{c}p_c\log_2p_c$$

其中 $p_c$ 是資料集中屬於類別 $c$ 的比例。

若以屬性 $A$ 切割資料，資訊增益為：

$$IG(S,A) = H(S) - \sum_{v\in Values(A)} \frac{|S_v|}{|S|}H(S_v)$$

其中：

• $S$ 為目前資料集；
• $S_v$ 為屬性 $A$ 取值為 $v$ 的子集合；
• $H(S)$ 為切割前熵；
• 切割後加權熵越小，資訊增益越大。

ID3 通常選擇資訊增益最大的屬性作為下一個切割屬性。

2. C4.5 與增益率

C4.5 改進 ID3，常使用增益率（gain ratio）：

$$GainRatio(S,A) = \frac{IG(S,A)}{SplitInfo(S,A)}$$

其中：

$$SplitInfo(S,A) = -\sum_{v} \frac{|S_v|}{|S|} \log_2 \frac{|S_v|}{|S|}$$

增益率可以降低資訊增益偏好「具有大量不同取值的屬性」之問題。

核心觀念

本題考查二元樹的三種走訪順序：

• In-order traversal（中序走訪）：左子樹 $\rightarrow$ 根節點 $\rightarrow$ 右子樹
• Post-order traversal（後序走訪）：左子樹 $\rightarrow$ 右子樹 $\rightarrow$ 根節點

若要使中序與後序序列完全相同，關鍵在於：

1. 節點不能出現在根節點之後的額外位置。
2. 每個節點的右子樹必須為空。
3. 樹的結構必須一路向左延伸，也就是 Left skewed binary tree（左斜二元樹）。

---

解題方法

以一棵左斜樹為例：

 A
 /
 B
 /
C

其中：

• $A$ 是根節點
• $B$ 是 $A$ 的左子節點
• $C$ 是 $B$ 的左子節點

中序走訪：

$$C \rightarrow B \rightarrow A$$

後序走訪：

$$C \rightarrow B \rightarrow A$$

因此，中序與後序序列完全相同。

一般而言，左斜樹的每個節點都沒有右子樹。對於每個節點而言，中序與後序都會先處理左子樹，最後處理根節點，因此兩種走訪順序一致。

---

選項分析

(A) Left skewed binary tree：正確

左斜樹的每個節點最多只有左子節點，沒有右子樹。

例如：

 A
 /
 B
 /
C

中序與後序皆為：

$$C \rightarrow B \rightarrow A$$

所以此選項符合題意。

---

(B) Right skewed binary tree：錯誤

右斜樹的每個節點最多只有右子節點，例如：

A
 \
 B
 \
 C

中序走訪為：

$$A \rightarrow B \rightarrow C$$

後序走訪為：

$$C \rightarrow B \rightarrow A$$

兩者順序相反，因此不符合題意。

---

(C) Complete binary tree：錯誤

Complete binary tree（完全二元樹）要求除了最後一層外，各層皆填滿，且最後一層的節點由左至右排列。

以最典型的三節點完全二元樹為例：

 A
 / \
 B C

中序走訪為：

$$B \rightarrow A \rightarrow C$$

後序走訪為：

核心觀念

本題考查虛擬記憶體（virtual memory）中的「頁面錯誤」（page fault）定義與處理機制。

作業系統會將行程的虛擬位址空間切分成固定大小的頁面（page），而實體記憶體則切分成頁框（page frame）。頁表（page table）記錄虛擬頁面目前是否位於實體記憶體中，以及其對應的實體頁框位置。

當處理器存取某個虛擬頁面時：

• 若該頁面已在實體記憶體中，便可直接完成位址轉換。
• 若該頁面不在實體記憶體中，處理器會觸發 page fault，由作業系統將該頁面從磁碟或其他後備儲存裝置載入實體記憶體，再重新執行被中斷的指令。

因此，page fault 的核心條件是：

$$\text{行程存取的頁面不在目前的實體記憶體中}$$

解題方法

判斷本題的關鍵，是辨認 page fault 的標準定義：

A page fault occurs when a process tries to access a page that is not currently in physical memory.

也就是「行程嘗試存取目前不在實體記憶體中的頁面」。

符合此定義的選項為 (B)。

典型處理流程如下：

1. 行程產生虛擬位址。
2. 處理器查詢頁表。
3. 頁表中的 present bit 或 valid bit 顯示該頁面不在實體記憶體。
4. 硬體觸發 page fault trap。
5. 作業系統找到該頁面在磁碟上的位置。
6. 找到可用頁框；若沒有可用頁框，先選擇頁面置換對象。
7. 將所需頁面載入實體記憶體。
8. 更新頁表。
9. 重新執行原本失敗的記憶體存取指令。

選項分析

(A) A page fault occurs when a page is modified but not written back to disk.

錯誤。

頁面被修改但尚未寫回磁碟，稱為「髒頁」（dirty page）。當作業系統要將髒頁置換出去時，必須先將其內容寫回磁碟，以免資料遺失。

「頁面被修改但尚未寫回磁碟」本身不代表 page fault。只有在行程存取的頁面不在實體記憶體時，才會發生 page fault。

(B) A page fault occurs when a process tries to access a page that is not currently in physical memory.

正確。

這正是 page fault 的標準定義。虛擬記憶體允許行程使用大於實體記憶體容量的位址空間，因此某些頁面可能暫時存放在磁碟中，而不在實體記憶體內。

核心觀念

本題考查 Edge Computing（邊緣運算） 在 AI 系統中的角色。

邊緣運算是指：將資料處理、AI 推論或部分模型運算，放在接近資料產生位置的設備或節點上，例如：

• 感測器
• 智慧攝影機
• 手機
• 車載系統
• 工業閘道器
• 工廠內部伺服器

傳統雲端運算通常將資料傳送至遠端大型資料中心處理；邊緣運算則讓資料在靠近來源處先行處理，因此可以：

1. 降低資料往返雲端所需的延遲時間（latency）。
2. 提升即時 AI 推論的反應速度。
3. 減少大量原始資料上傳所造成的網路頻寬負擔。
4. 在網路不穩定時維持部分系統功能。
5. 增加資料隱私與安全性，因為部分原始資料不必離開現場。

邊緣運算並不代表完全取消雲端。實際 AI 系統常採用雲端與邊緣協同架構：雲端負責大型模型訓練、集中管理與長期分析，邊緣端負責即時資料處理與推論。

解題方法

判斷本題的關鍵，在於掌握 Edge Computing 的核心定義：

將運算工作移近資料產生的位置，以降低延遲並提升即時處理能力。

題目問的是 edge computing 在 AI-powered systems 中的「角色」。因此應尋找同時符合下列條件的選項：

• 資料在靠近來源的位置處理。
• 目的包含降低延遲。
• 有助於即時 AI 推論或反應。

只有選項 (E) 完整符合這三項條件。

選項分析

(A) Processing all AI workloads only in large centralized cloud data centers

將所有 AI 工作負載只放在大型集中式雲端資料中心，描述的是集中式雲端運算，而非邊緣運算。

邊緣運算的重點正是把部分運算移至靠近資料來源的位置。雲端仍可負責模型訓練與大量資料分析，但「all」與「only」表示所有工作都只能在雲端完成，與邊緣運算的概念相反。

因此 (A) 錯誤。

(B) Improving AI accuracy by training all models exclusively on historical datasets

此選項討論的是模型訓練資料與 AI 準確度，並非邊緣運算的核心功能。

邊緣運算主要改善的是：

• 推論延遲
• 即時反應速度
• 網路頻寬使用
• 資料傳輸需求

模型是否使用歷史資料訓練，與運算位置沒有直接等同關係。AI 模型也可使用即時資料、增量資料或其他訓練資料進行更新；「exclusive」表示只能使用歷史資料，過度絕對。

因此 (B) 錯誤。

核心觀念

本題考查 TCP Reno 的壅塞控制機制，重點包括：

• Slow Start
• Congestion Avoidance
• 三次重複 ACK
• Fast Recovery
• Timeout
• $cwnd$ 與 $ssthresh$ 的調整方式

TCP Reno 主要依據壅塞事件採取不同反應：

壅塞事件	Reno 的主要處理
建立連線初期	Slow Start，$cwnd$ 指數成長
$cwnd$ 達到 $ssthresh$	進入 Congestion Avoidance
收到三個 Duplicate ACK	Fast Retransmit + Fast Recovery
發生 Timeout	$cwnd$ 降至一個 Segment，重新 Slow Start

---

解題方法

判斷本題的關鍵，是區分兩種封包遺失偵測方式：

1. 三次重複 ACK：代表網路仍能持續傳送封包與回覆 ACK，通常視為較輕微的壅塞，TCP Reno 使用 Fast Recovery。
2. Timeout：代表可能有較嚴重的壅塞，TCP Reno 將 $cwnd$ 大幅降至 $1$ 個 Segment，重新進入 Slow Start。

TCP Reno 收到三次重複 ACK 時，典型處理為：

$$ssthresh=\frac{cwnd}{2}$$

進入 Fast Recovery 後，$cwnd$ 會暫時膨脹以反映重複 ACK；當收到新的 ACK、確認遺失封包已成功重傳時：

$$cwnd=ssthresh$$

接著進入 Congestion Avoidance，以線性方式增加 $cwnd$。

因此，「Fast Recovery 後將 $cwnd$ 降至一個 Segment」描述的是 Timeout 所採用的處理方式，並非 Reno 的標準 Fast Recovery 結束動作。

---

選項分析

(A) TCP Reno uses Slow Start to exponentially increase the congestion window at the beginning of a connection.

正確。

TCP Reno 在連線開始時通常先使用 Slow Start。每收到一個新的 ACK，$cwnd$ 增加約一個 MSS，因此一個 RTT 內，$cwnd$ 約會加倍，呈現指數成長：

$$1,\ 2,\ 4,\ 8,\ 16,\ldots$$

當 $cwnd$ 達到 $ssthresh$ 後，才轉入 Congestion Avoidance。

---

(B) TCP Reno switches to Congestion Avoidance once the congestion window ($cwnd$) reaches the slow-start threshold ($ssthresh$).

正確。

$ssthresh$ 是 Slow Start 與 Congestion Avoidance 的分界點：

• $cwnd < ssthresh$：使用 Slow Start。
• $cwnd \geq ssthresh$：進入 Congestion Avoidance。

核心觀念

本題考查經典五級 CPU pipeline：

1. IF（Instruction Fetch）：取出指令
2. ID（Instruction Decode）：指令解碼與讀取暫存器
3. EX（Execute）：執行運算或計算位址
4. MEM（Memory Access）：存取記憶體
5. WB（Write Back）：將結果寫回暫存器

Pipelining 的核心概念，是把一條指令的執行拆成多個階段，讓不同指令在同一時間分別處於不同階段。

例如：

時脈週期	指令 1	指令 2	指令 3
1	IF
2	ID	IF
3	EX	ID	IF
4	MEM	EX	ID
5	WB	MEM	EX
6		WB	MEM
7			WB

因此，pipeline 的主要效果是提升整體指令完成率，也就是 throughput，而非把單一指令的執行時間縮短到一個時脈週期以下。

---

解題方法

判斷 pipeline 題目時，先區分兩個概念：

• Latency：單一指令從開始到完成所需的時間。
• Throughput：單位時間內完成多少指令。

五級 pipeline 在理想情況下，第一條指令仍須經過約五個時脈週期才能完成；但 pipeline 填滿後，理想上每個時脈週期可完成一條指令。

若有 $n$ 條指令、每條指令均順利通過五級 pipeline，理想完成時間為：

$$5+(n-1)=n+4$$

但實際執行可能遇到：

• Structural hazard：硬體資源衝突
• Data hazard：指令間資料相依
• Control hazard：分支、跳躍造成的控制流程不確定

此時可能需要插入 stall，也可能利用 forwarding 降低等待時間。因此，最完整且正確的敘述是「提升整體 throughput，但 hazard 仍可能造成停頓，或需要 forwarding 處理」。

---

選項分析

(A) It reduces the latency of each individual instruction to less than one clock cycle.

錯誤。

Pipelining 主要提升的是整體 throughput，不會使單一指令的 latency 降到小於一個時脈週期。五級 pipeline 中，一條指令仍須依序通過 IF、ID、EX、MEM、WB 等階段，通常需要多個時脈週期才能完成。

---

(B) It increases the CPU clock frequency without any need for hazard handling.

錯誤。

將指令切分成多個階段，確實有助於縮短每個 pipeline stage 的組合邏輯延遲，因而可能提高 CPU clock frequency。然而，pipeline 仍會產生資料、結構與控制 hazard，必須透過 stall、forwarding、branch prediction 等機制處理。

核心觀念

本題考查有限體 $\mathrm{GF}(2^8)$ 中的多項式乘法。

在 $\mathrm{GF}(2)$ 中，係數只有 $0$ 與 $1$，且加法等同於 XOR：

$$1+1=0$$

每個 8 位元組可表示為一個最高次不超過 $7$ 的二元多項式。位元位置 $i$ 對應 $x^i$：

$$\texttt{0x13}=00010011_2=x^4+x+1$$ $$\texttt{0x04}=00000100_2=x^2$$

有限體中的乘法規則為：

$$a(x)b(x)\bmod m(x)$$

其中

$$m(x)=x^8+x+1$$

是不可約多項式。

---

解題方法

將兩個 byte 轉為多項式：

$$\texttt{0x13}\cdot\texttt{0x04} =(x^4+x+1)x^2$$

逐項相乘：

$$=x^6+x^3+x^2$$

此結果的最高次為 $6$，小於 $8$，因此不需要使用

$$x^8=x+1$$

進行模除約化。

再將

$$x^6+x^3+x^2$$

轉回 8 位元表示：

• $x^6$：$\texttt{0x40}$
• $x^3$：$\texttt{0x08}$
• $x^2$：$\texttt{0x04}$

因此：

$$\texttt{0x40}\oplus\texttt{0x08}\oplus\texttt{0x04} =\texttt{0x4C}$$

所以：

$$\boxed{\texttt{0x13}\otimes\texttt{0x04}=\texttt{0x4C}}$$

---

以程式演算法追蹤

常見的 GF(2^8) 乘法會使用 Russian Peasant Multiplication，並以 xtime 完成乘以 $x$ 的操作：

unsigned char xtime(unsigned char a) {
 if (a & 0x80)
 return (a << 1) ^ 0x03; // m(x) = x^8 + x + 1
 else
 return a << 1;
}

原因是：

$$x^8+x+1=0$$

在 $\mathrm{GF}(2)$ 中，減法與加法相同，因此：

$$x^8=x+1$$

當最高位為 $1$ 時，左移產生 $x^8$，需 XOR $\texttt{0x03}$，因為：

$$x+1=\texttt{0x03}$$

乘法追蹤如下：

迭代	a	b	b & 1	p
初始	0x13	0x04	—	0x00

核心觀念

在 supervised learning（監督式學習）中，資料通常分為：

• Training dataset（訓練集）：用來學習模型參數，例如神經網路的權重。
• Validation dataset（驗證集）：用來調整模型的 hyperparameters（超參數），並監測模型是否 overfitting（過度擬合）。
• Test dataset（測試集）：在模型與超參數都確定後，用來評估模型對未見資料的最終表現。

模型參數與超參數的差異如下：

• 模型參數（parameters）：由訓練資料自動學得，例如線性回歸的係數、神經網路的權重。
• 超參數（hyperparameters）：由使用者或模型選擇流程設定，例如 learning rate、樹的最大深度、正則化強度、神經網路層數。

驗證集的主要功能，是比較不同超參數設定下的模型表現，選出泛化能力較佳的模型，並觀察模型是否開始過度適應訓練資料。

例如，若模型在訓練集上的準確率持續上升，但驗證集上的準確率開始下降，表示模型可能正在 overfitting。

解題方法

判斷本題可依照資料集的用途切入：

1. 找出「調整模型設定」與「偵測過度擬合」相關的選項。
2. 區分 validation dataset 與 test dataset：

• Validation dataset 用於模型選擇與超參數調整。
• Test dataset 用於最後一次、較客觀的性能評估。

3. 因此，最符合驗證集主要用途的選項是：

$$\boxed{\text{Tune model hyperparameters and detect overfitting}}$$

選項分析

(A) To increase the size of the training data.

錯誤。

驗證集不是用來增加訓練資料大小。資料被分成訓練集與驗證集後，驗證集通常不直接參與模型參數的學習。

若將驗證集重新併入訓練集，確實可以增加最終訓練資料量，但這是模型選擇完成後可能採取的額外策略，不是建立驗證集的主要目的。

(B) To evaluate the final performance of the model.

錯誤。

評估模型最終性能主要是 test dataset 的用途。測試集必須在模型架構、超參數與訓練流程確定後使用，才能提供較客觀的泛化能力估計。

核心觀念

本題考查關聯式資料庫的函數相依（Functional Dependency）與第三正規化（Third Normal Form, 3NF）。

原始關係為：

$$Enrollment(StudentID, StudentName, CourseID, CourseName, InstructorName)$$

根據題目條件，可得到下列函數相依：

1. 每位學生只有一個姓名：

$$StudentID \rightarrow StudentName$$

2. 每門課程只有一個課名：

$$CourseID \rightarrow CourseName$$

3. 每門課程只有一位授課教師：

$$CourseID \rightarrow InstructorName$$

4. 一位學生可以修讀多門課，因此一筆選課紀錄必須由學生與課程共同決定。候選鍵為：

$$(StudentID, CourseID)$$

因為只有同時知道學生與課程，才能唯一識別一筆選課資料。

---

解題方法

原始關係的候選鍵是 $(StudentID, CourseID)$，但存在以下部分函數相依：

$$StudentID \rightarrow StudentName$$ $$CourseID \rightarrow CourseName, InstructorName$$

也就是說：

• $StudentName$ 只依賴 $StudentID$，不需要知道 $CourseID$。
• $CourseName$ 與 $InstructorName$ 只依賴 $CourseID$，不需要知道 $StudentID$。

這些都是非主屬性對複合鍵一部分的相依，會造成資料重複與更新異常，因此原始關係甚至未達第二正規化（2NF），當然也未達 3NF。

正規化時，應依照各個決定因素拆分：

學生資料：

$$Student(StudentID, StudentName)$$

課程資料：

$$Course(CourseID, CourseName, InstructorName)$$

學生與課程的多對多選課關係：

$$Enrollment(StudentID, CourseID)$$

在這三個關係中：

• $StudentID$ 是 $Student$ 的主鍵。
• $CourseID$ 是 $Course$ 的主鍵。
• $(StudentID, CourseID)$ 是 $Enrollment$ 的複合主鍵。

每個關係中的非主屬性都完全依賴其主鍵，且沒有非鍵屬性經由其他非鍵屬性傳遞決定，因此符合 3NF。

---

選項分析

(A) $Enrollment(StudentID, CourseID)$

錯誤。

此選項只保留學生與課程的選課關係，雖然它是正確的關聯表，但遺失了：

• $StudentName$
• $CourseName$
• $InstructorName$

因此無法完整表示原始關係的資料，不是完整且無損的 3NF 分解。

---

(B) $Enrollment(StudentID, StudentName, CourseID)$，$Course(CourseID, InstructorName)$

錯誤。

此選項有兩個主要問題：

第一，完全遺失 $CourseName$，無法保留原始關係的所有資訊。

第二，第一個關係仍存在：

$$StudentID \rightarrow StudentName$$

其候選鍵為 $(StudentID, CourseID)$，但 $StudentName$ 只依賴複合鍵的一部分 $StudentID$，因此仍有部分函數相依，未達 2NF，更不可能達到 3NF。

---

(C) $Student(StudentID, StudentName, CourseID)$，$Course(CourseID, CourseName, InstructorName)$

錯誤。

雖然課程關係：

$$Course(CourseID, CourseName, InstructorName)$$