115 年 國立成功大學數據科學研究所《計算機概論（含資料結構）》

一、核心觀念

本題涵蓋數據科學與資訊工程核心四大領域觀念：

1. 演算法與時間複雜度分析：Big-$O$ 漸進符號之定義、漸進上界與實際執行時間及輸入規模 $n$ 之關係。
2. 資料結構：
   • 單向鏈結串列（Singly Linked List）節點刪除演算法及前驅節點指標依賴性。
   • 二元堆積（Binary Heap）之偏序性（Partial Order）與中序走訪（In-order Traversal）特性。
   • 廣度優先搜尋（BFS）於無權重圖（Unweighted Graph）中求最短路徑之原理。
   • 雜湊表（Hash Table）採用鏈結法（Separate Chaining）時碰撞（Collision）之最差時間複雜度。
3. 作業系統：
   • 虛擬記憶體（Virtual Memory）之頁錯誤（Page Fault）處理流程與位址空間限制。
   • CPU 排程演算法（Round-Robin vs. SJF）之優化目標（平均等待時間與響應時間）。
   • 上下文切換（Context Switch）保存與還原進程/執行緒狀態之機制。
4. 機器學習與資料科學：
   • K-means 分群法中群集中心（Centroid）之數學定義（算術平均值）。
   • 模型複雜度、特徵數量及樹深度對過擬合（Overfitting）與泛化能力（Generalization）之影響。
   • 高度不平衡資料集（Imbalanced Datasets）之評估指標陷阱。
   • 主成分分析（PCA）解決共線性（Multicollinearity）與降維原理。
   • 交叉熵損失函數（Cross-Entropy Loss）在二元與多元分類之定義。
   • 梯度下降法（Gradient Descent）中學習率（Learning Rate）對收斂性與發散性之影響。

---

二、解題方法

1. 嚴格依據定義：
   • 利用 Big-$O$ 數學定義證明漸進上界：$f(n) = O(g(n)) \iff \exists\, c > 0, n_0 \ge 0$ 使得對所有 $n \ge n_0$，$f(n) \le c \cdot g(n)$。
   • 區分二元搜尋樹（BST）的全排序與二元堆積（Binary Heap）的偏序關係（僅保證 Parent 與 Child 之相對大小）。
2. 尋找反例（Counterexamples）判定命題：
   • 針對敘述中含有極端限定詞（如 always, every, only, never）之選項（如 b, c, h, i, j, k, l, o, q, r），只要能構建出合理的極端情況或反例，即可確定該命題為 False。
3. 區分機器學習觀念：
   • 嚴格劃分「訓練集效能（Training Performance）」與「測試集/未看過資料效能（Test/Unseen Performance）」。
   • 分清 K-means（中心為算術平均點）與 K-medoids（中心為實際資料點）之差別。

---

三、選項分析

(a) If an algorithm runs in $3n + 100$ steps, its time complexity is $O(n)$.

• 判定：True
• 詳細說明：根據 Big-$O$ 漸進上界的數學定義，若存在常數 $c > 0$ 與 $n_0 \ge 0$，使得對所有 $n \ge n_0$，皆滿足 $f(n) \le c \cdot g(n)$，則 $f(n) = O(g(n))$。當執行步數 $f(n) = 3n + 100$ 時，若選擇 $c = 4$ 且 $n_0 = 100$，對所有 $n \ge 100$，均有 $3n + 100 \le 4n$ 成立。在漸進分析中，忽略低階項（$100$）與常數係數（$3$），其時間複雜度確定為 $O(n)$。

(b) If algorithm A is $O(n\log n)$ and algorithm B is $O(n^2)$, then A is faster for every input size $n$.

• 判定：False
• 詳細說明：Big-$O$ 描述的是當輸入規模 $n \to \infty$ 時的漸進趨勢（Asymptotic Behavior），並不保證在所有 $n$ 值下演算法 A 都快於 B。原因有二：
  1. 隱藏常數與低階項影響：若演算法 A 的實際執行步數為 $f_A(n) = 1000 n \log_2 n$，演算法 B 為 $f_B(n) = n^2$，當 $n = 2$ 時，$f_A(2) = 2000$，而 $f_B(2) = 4$，此時演算法 B 比 A 更快。
  2. 小型輸入規模：在小型資料集（Small $n$）情況下，漸進複雜度較低的演算法常因較高的初始化開銷或係數而慢於高複雜度演算法。
• 正確敘述/理由：演算法 A 僅在輸入規模 $n$ 足夠大（$n \ge n_0$）時才會快於演算法 B；在小資料集或考量常數因子時，演算法 B 可能更快。

(c) Deleting a node from a singly linked list is always $O(1)$ if you are given only a pointer to the node to delete.

• 判定：False
• 詳細說明：給定單向鏈結串列中指向待刪除節點 $P$ 的指標：
  1. 若 $P$ 非尾節點（Tail Node）：可將後繼節點（$P.next$）的值複製到 $P$，再將 $P.next$ 刪除，此操作為 $O(1)$。
  2. 若 $P$ 為尾節點（Tail Node）：由於單向鏈結串列沒有指向前驅節點（Predecessor）的指標，無法直接更新前驅節點的 $next$ 為 NULL。必須從 Head 節點重新走訪至尾節點的前驅，需要 $O(n)$ 時間。
• 正確敘述/理由：若待刪除節點為單向鏈結串列的尾節點（Tail Node），無法在不走訪串列的情況下更新前驅指標，在最差情況下時間複雜度為 $O(n)$，並非「總是」$O(1)$。

(d) A binary heap provides a partial order, not a fully sorted structure.

• 判定：True
• 詳細說明：二元堆積（Binary Heap）僅滿足堆積性質（Heap Property）。以最大堆積（Max-Heap）為例，任何父節點的值均大於等於其子節點的值。這在「祖先與子孫」之間建立了偏序關係（Partial Order）；但在「同階層的節點」或「不同分支之間的節點」則無定義順序。因此，二元堆積並非全排序結構（Fully Sorted Structure）。

(e) An in-order traversal of a binary heap returns elements in sorted order.

• 判定：False
• 詳細說明：只有二元搜尋樹（Binary Search Tree, BST）的中序走訪（In-order Traversal）才會依遞增順序輸出元素。二元堆積（Binary Heap）僅維持父子節點間的相對大小關係，左右子樹之間沒有大小順序關係。對二元堆積進行中序走訪無法獲得排序好的序列（要取得排序結果需進行 Heap Sort 或連續執行 Extract-Min / Extract-Max）。
• 正確敘述/理由：二元堆積的中序走訪不會返回排序好的元素序列；二元搜尋樹（BST）的中序走訪才會返回排序好的元素。

(f) BFS on an unweighted graph finds shortest paths measured by number of edges.

• 判定：True
• 詳細說明：廣度優先搜尋（Breadth-First Search, BFS）是以層級（Level-by-level）方式向外擴展。在無權重圖（Unweighted Graph，可視為所有邊權重均為 $1$）中，BFS 保證第一次造訪某個節點時所經過的邊數（Edges count）即為從起點到該節點的最少邊數（即最短路徑長度）。

(g) A hash table with separate chaining can have $O(n)$ worst-case lookup time.

• 判定：True
• 詳細說明：在採用鏈結法（Separate Chaining）處理碰撞的雜湊表中，若雜湊函數品質佳，平均搜尋時間為 $O(1)$。但在最差情況下（Worst Case），若所有 $n$ 個鍵值（Keys）全部發生碰撞並被映射到同一個桶位（Bucket/Slot），該 Slot 上的單向鏈結串列長度將達到 $n$。此時尋找特定元素需線性走訪該鏈結串列，搜尋時間複雜度為 $O(n)$。

(h) A page fault always means the program is incorrect and must be terminated.

• 判定：False
• 詳細說明：頁錯誤（Page Fault）是虛擬記憶體管理中的正常作業系統中斷機制。當程式存取的虛擬頁面（Virtual Page）目前不在實體記憶體（RAM）中時，硬體 MMU 會觸發 Page Fault，作業系統接管後從次級儲存裝置（如 SSD/Hard Disk）將缺失的頁面載入實體記憶體，並更新頁表（Page Table），最後重新執行引發 Page Fault 的指令。此過程對程式而言是完全透明且正常的。
• 正確敘述/理由：Page Fault 是虛擬記憶體分頁機制的正常現象，作業系統載入所需頁面後會恢復程式執行；只有非法記憶體存取（如 Segmentation Fault / Invalid Page Fault）才會導致程式異常終止。

(i) Round-robin scheduling always minimizes average waiting time.

• 判定：False
• 詳細說明：在作業系統 CPU 排程中，能保證最小化平均等待時間（Average Waiting Time）的排程演算法是最短工作優先（Shortest Job First, SJF）或最短剩餘時間優先（Shortest Remaining Time First, SRTF）。輪轉排程（Round-Robin, RR）的設計目標是為了提高時分共享系統的響應時間（Response Time）與公平性，其平均等待時間通常高於 SJF，且過小的時間切片（Time Quantum）會引發頻繁的上下文切換開銷。
• 正確敘述/理由：最小化平均等待時間的排程演算法為 Shortest Job First (SJF) / SRTF，而非 Round-Robin。

核心觀念

本題結合了圖形表示法（Graph Representations）、**單源最短路徑演算法（Single-Source Shortest Path, SSSP）以及狀態擴展／分層圖最短路徑（State-Space Graph / Layered Graph）**的核心概念。

1. 圖形儲存結構與空間複雜度：

   • 鄰接串列（Adjacency List）：適合稀疏圖（Sparse Graph），記錄各頂點的相鄰節點，空間複雜度為 $O(|V| + |E|)$。
   • 鄰接矩陣（Adjacency Matrix）：適合稠密圖（Dense Graph），以二維陣列儲存所有點對間的邊權重，空間複雜度為 $O(|V|^2)$。

2. 乘積最大化轉換為最短路徑：

   • 最大化路徑可靠度乘積 $\max \prod r(u,v)$ 等價於最小化其負對數總和 $\min \sum -\log r(u,v)$。
   • 由於 $r(u,v) \in (0, 1]$，邊權重 $c(u, v) = -\log r(u, v) \ge 0$，因此所有邊的權重皆為非負實數，適用 Dijkstra 演算法。

3. 邊權重歸零（折價券問題）的狀態擴展：

   • 「最多／恰好使用一次優惠使某條邊權重歸零」屬於動態規劃與最短路徑結合的經典問題，可透過**狀態擴展（State Expansion / 分層圖）或雙向兩次 Dijkstra（Two-pass Dijkstra）**在多項式時間內求解。

---

解題方法

(a) 稀疏圖與稠密圖的資料結構比較與選擇

1. 稀疏圖（Sparse Graph，即 $|E| \ll |V|^2$）：

   • 推薦結構：鄰接串列（Adjacency List）。
   • 空間複雜度：$O(|V| + |E|)$。
   • 適用時機：當圖中邊數遠少於 $|V|^2$（例如道路網、地鐵網中每個路口連接的道路數量有限，$|E| = O(|V|)$）。使用鄰接串列可節省大量記憶體，且走訪單一頂點的所有鄰居僅需 $O(\deg(v))$ 時間。

2. 稠密圖（Dense Graph，即 $|E| \approx |V|^2$）：

   • 推薦結構：鄰接矩陣（Adjacency Matrix）。
   • 空間複雜度：$O(|V|^2)$。
   • 適用時機：當圖中邊數極多（接近完全圖）時。鄰接矩陣能在 $O(1)$ 時間內判定或存取任意兩點間是否存在邊與其權重，陣列在記憶體中連續分布也具備較佳的快取區域性（Cache Locality）。

---

(b) 最短路徑演算法選擇、時間複雜度與 BFS 不適用的原因

1. 選擇之演算法：

   • 使用 Dijkstra 演算法（搭配 Min-Heap / 優先佇列）。
   • 原因：可靠度 $r(u,v) \in (0, 1]$，經過轉換後 $c(u,v) = -\log r(u,v) \ge 0$。因為圖中不存在負權重邊（No negative edge weights），Dijkstra 演算法具備貪婪選擇性質（Greedy Choice Property），可保證求得全域最佳解。

2. 時間複雜度：

   • 使用二元堆積（Binary Min-Heap）：
     $O((|V| + |E|) \log |V|)$
   • 若使用費氏堆積（Fibonacci Heap）：
     $O(|E| + |V| \log |V|)$

3. 為什麼標準 BFS（廣度優先搜尋）不適用：

   • BFS 的核心假設：BFS 僅適用於無權重圖（Unweighted Graph）或所有邊權重皆相同的圖。BFS 是依照「邊的數量（Hop count）」層層向外搜尋。
   • 權重差異導致錯誤：本題轉換後的邊權重 $c(u,v) \ge 0$ 為任意非負實數。邊數較少的路徑，其總成本不一定較小（可能經過一條可靠度極低的邊导致累計 cost 極大）；反之，邊數較多的路徑可能全部由高可靠度的邊組成，總成本反而較低。BFS 會優先挑選「邊數最少」而非「總權重最小」的路徑，因此無法求得正確的最短路徑。

---

(c) 「使用一次折價券使單邊成本歸零」的演算法設計與複雜度

本題可採用以下兩種簡潔且標準的演算法概念之一：

方法一：狀態擴展／分層圖 Dijkstra（State-Space Graph Dijkstra）

1. 核心概念：

   • 將每個頂點 $u$ 擴展為兩種狀態 $(u, k)$，其中 $k \in \{0, 1\}$：
     • $k = 0$：表示從起點 $s$ 到目前節點 $u$ 的路徑上尚未使用折價券。
     • $k = 1$：表示從起點 $s$ 到目前節點 $u$ 的路徑上已經使用過折價券。

2. 邊的建立（轉移關係）：

   • 不使用折價券的普通移動：
     • 對於原圖中的每條邊 $(u, v)$，在層內建立邊：
       $(u, 0) \xrightarrow{c(u,v)} (v, 0)$

核心觀念

本題考查作業系統（Operating System）的檔案系統 I/O 快取機制與資料持久性（Data Persistence / I/O Buffering）。

寫入資料至檔案系統涉及三個關鍵層級：

1. 使用者空間緩衝區（User-Space Buffer / Standard I/O Buffer）：應用程式層級維護於 RAM 的緩衝區（例如 C 語言 stdio 函式庫中 FILE 結構體的內部 Buffer）。
2. 作業系統頁面快取（OS Page Cache / Kernel Buffer Cache）：作業系統核心（Kernel）維護於 RAM 的檔案頁面快取。
3. 實體磁碟（Disk / Non-Volatile Storage）：如 SSD 或 HDD 等非揮發性儲存介面。

斷電（Power Loss）的影響：主記憶體（RAM）屬於揮發性介面，電源中斷後資料會立即丟失；唯有成功寫入實體磁碟的資料才能在系統重啟後保留。

---

解題方法

(a) 三種寫入層級之差異與資料丟失原因分析

應用程式執行寫入操作時，資料的傳輸流程如下：
$\text{User-Space Buffer} \xrightarrow{\text{System Call (write)}} \text{OS Page Cache} \xrightarrow{\text{Async Flush / Sync}} \text{Disk}$

1. 使用者空間緩衝區（User-Space Buffer）：
   • 機制：當程式呼叫高階 I/O API（如 C 的 fprintf() 或 Python 的 print()）時，資料會先累積在進程本身的記憶體空間中，尚未觸發系統呼叫（System Call）。
   • 特性：存取速度極快，但僅存在於該應用進程內。進程崩潰（Crash）或系統斷電時資料皆會丟失。
2. 作業系統頁面快取（OS Page Cache）：
   • 機制：發出 write() 系統呼叫後，資料會從 User-Space 複製到作業系統核心的記憶體區（Kernel RAM）。此時對應用程式而言寫入操作已完成，系統呼叫即回傳成功（故程式會印出 "Saved!"）。
   • 特性：資料此時仍存放在揮發性的 RAM 中。作業系統基於效能考量採用「延遲寫回策略（Write-Back Policy / Lazy Flush）」，由背景執行緒（如 flusher / pdflush）在稍後非同步地將髒頁（Dirty Pages）刷入磁碟。
3. 實體磁碟（Disk）：
   • 機制：資料由 Block Device Driver 寫入非揮發性儲存裝置（SSD/HDD）。
   • 特性：屬於持久化儲存（Persistent Storage），電源中斷後資料依然保留。

資料「消失」的原因：
程式印出 "Saved!" 僅表示資料已成功複製到 User-Space Buffer 或 OS Page Cache（write() 系統呼叫已順利回傳）。作業系統為了優化 I/O 效能，尚未立即將這些 Dirty Pages 寫回實體磁碟（Disk）。由於 RAM 屬於揮發性介面，若在此時間視窗內遭遇突發斷電，保存在記憶體中的資料便會完全消失。

---

(b) 兩種提升 Crash-Resilience（抗崩潰能力）的方法與其 Trade-off

1. 方法一：顯式同步刷盤（Explicit Flushing & Syncing via fflush() + fsync()）
   • 作法：每次寫入關鍵 Log 後，先呼叫 fflush() 將資料從 User-Space Buffer 清空並發送系統呼叫，隨後呼叫 fsync(fd) 強制 Kernel 將 OS Page Cache 中該檔案的 Dirty Pages 立即寫入實體磁碟。
   • Trade-off（權衡）：
     • 優點：提供極高的資料持久性（Durability）與強一致性，保證斷電不遺失已提交的日誌。
     • 缺點：將非同步寫入轉為同步阻塞 I/O（Synchronous I/O），程式必須等待慢速的磁碟寫入完成，會顯著降低系統吞吐量（Throughput）並增加回應延遲（Latency）。

核心觀念

本題旨在考驗作業系統（Operating System）中 CPU / Job 排程演算法的性能指標評估，包含**平均等待時間（Average Waiting Time, AWT）與公平性（Fairness / Resource Allocation Rate）**的權衡，以及如何設計排程器解決混合工作負載（Mixed Workloads：包含短任務與長任務）的實用問題。

1. FCFS (First-Come First-Served)：

   • 非搶佔式（Non-preemptive）排程。
   • 公平性：絕對公平，嚴格按照到達順序執行，保證無飢餓現象（Starvation-free）。
   • 平均等待時間：若長任務（2 小時）比短任務（2 分鐘）先到達，會引發護衛效應（Convoy Effect），導致後續所有短任務皆須等待極長時間，拉高總體的平均等待時間。

2. SJF (Shortest Job First)：

   • 優先執行預估執行時間（Burst Time）最短的任務。
   • 平均等待時間：在數學上已被證明，對於給定的一組任務，SJF 可提供最小的平均等待時間（Minimum Average Waiting Time）。
   • 公平性：極不公平。若短任務持續進入系統，長任務將會被無限期推遲，導致飢餓現象（Starvation）。

3. 反應速度與公平性的折衷（Trade-off）：

   • 實務排程系統無法預先精確得知任務的真正執行時間（Burst Time），且必須兼顧短任務的低回應時間（Responsiveness）與長任務的不飢餓性（Fairness）。

---

解題方法

(a) FCFS 與 SJF 之比較

• 平均等待時間（Average Waiting Time, AWT）：
  $\text{AWT}_{\text{SJF}} < \text{AWT}_{\text{FCFS}}$

  • SJF：優先讓執行時間為 $2\text{ min}$ 的短任務優先執行並迅速離開系統。由於短任務的等待時間被大幅壓縮，整體系統的 $\text{AWT}$ 達到理論上的最小值。
  • FCFS：若 $2\text{ hr}$ 的長任務先到達，所有後續到達的短任務皆必須等待 $2\text{ hr}$ 才能開始執行。此即護衛效應（Convoy Effect），會使得系統平均等待時間劇烈飆升。

• 公平性（Fairness）與飢餓現象（Starvation）：
  $\text{Fairness}_{\text{FCFS}} > \text{Fairness}_{\text{SJF}}$

  • FCFS：遵循 FIFO 原則，每個任務最終都能獲得 CPU 資源，保證不發生 Starvation，在資源分配時效上具備極佳的公平性。
  • SJF：當系統有連續不斷的短任務流入時，長任務會一直處於佇列後方無法獲得執行機會，面臨無限期延遲的 Starvation 困境，造成使用者感到「排程不公」。

---

(b) 兼顧回應時間與公平性的實務排程設計

在混合短任務（2 分鐘）與長任務（2 小時）的真實環境中，最佳的實務設計為採用 多層回饋佇列排程（Multi-Level Feedback Queue, MLFQ），並配合 老化機制（Aging）。

MLFQ 系統設計與運作流程：

1. 多級佇列結構：系統設定多個不同優先權等級的佇列（如 $Q_0, Q_1, \dots, Q_k$），優先權由高至低，各佇列採用輪轉排程（Round-Robin, RR），且高優先權佇列配給較短的時間片（Time Quantum $q$），低優先權佇列配給較長的時間片。
2. 快速響應短任務（模仿 SJF / 保障 Responsiveness）：
   • 所有新進任務一律先放入最高優先權佇列 $Q_0$（時間片極小，如 $q = 10\text{ ms}$）。
   • 短任務（2 分鐘）通常可在前幾輪時間片內迅速執行完畢離開系統，獲得極佳的互動回應速度。
3. 動態懲罰與降級長任務：

核心觀念

本題旨在考驗作業系統與併發程式設計（Concurrency）中**死鎖（Deadlock）**的成因與預防機制。

1. 死鎖（Deadlock）：指兩個或多個程序（Process/Thread）在執行過程中，因爭奪資源而造成一種互相等待的現象，若無外力作用，這些程序都將無法推進下去。
2. 死鎖發生的四大必要條件（Coffman Conditions）：
   • 互斥（Mutual Exclusion）：資源一次只能被一個程序使用。
   • 持有並等待（Hold and Wait）：程序已持有至少一個資源，但又申請其他被持有的資源。
   • 不可搶佔（No Preemption）：資源只能由持有的程序自願釋放，不能被強制剝奪。
   • 循環等待（Circular Wait）：存在一個程序等待鏈 $\{P_0, P_1, \dots, P_n\}$，$P_0$ 等待 $P_1$ 持有的資源，$P_1$ 等待 $P_2$ 持有的資源，……，$P_n$ 等待 $P_0$ 持有的資源。
3. 資源鎖定順序原則（Lock Ordering / Resource Hierarchy）：這是一種死鎖預防（Deadlock Prevention）策略，透過強迫所有程序按照相同的全局順序獲取資源，徹底打破「循環等待」條件。

---

解題方法

1. 分析併發行為與競爭條件（Race Condition）：
   • Worker 1 請求資源順序：$\text{Lock A} \rightarrow \text{Lock B}$
   • Worker 2 請求資源順序：$\text{Lock B} \rightarrow \text{Lock A}$
   • 由於兩者獲取鎖的順序相反（Order Inversion），當 CPU 進行上下文切換（Context Switch）導致交錯執行（Interleaving）時，即可能引發問題。
2. 建構等待圖（Wait-For Graph）：
   • Worker 1 取得 Lock A 後等待 Lock B（Worker 1 $\rightarrow$ Lock B $\rightarrow$ Worker 2）。
   • Worker 2 取得 Lock B 後等待 Lock A（Worker 2 $\rightarrow$ Lock A $\rightarrow$ Worker 1）。
   • 形成環路（Cycle），滿足循環等待條件，導致系統永久凍結。
3. 提出修復方案：
   • 破壞 Coffman 四大條件中最容易控制的「循環等待」條件。
   • 統一所有 Worker 獲取 Lock 的順序即可排除死鎖。

---

子題詳解

(a) 凍結的原因與等待故事（Wait-for Story）

• 最可能的凍結原因：死鎖（Deadlock）。

• Wait-for 情境故事（Wait-for Story）：

  假設 Worker 1 與 Worker 2 同時開始執行：

  1. Worker 1 率先成功取得 Lock A（特徵儲存區的鎖）。
  2. 此時 CPU 切換執行權，Worker 2 隨後成功取得 Lock B（模型快取的鎖）。

核心觀念
本題考查計算機概論、作業系統（Operating Systems）與資料科學／機器學習（Data Science & Machine Learning）基礎中四對核心概念的定義與差異判別：

1. Precision vs. Recall：模型評估指標（Evaluation Metrics）與混淆矩陣（Confusion Matrix）的應用。
2. Process vs. Thread：作業系統資源分配單位與 CPU 排程執行單位的區隔。
3. Overfitting vs. Underfitting：機器學習模型泛化能力（Generalization Ability）與偏差-變異數權衡（Bias-Variance Tradeoff）。
4. Preemptive Scheduling vs. Non-preemptive Scheduling：作業系統 CPU 排程機制中控制權轉移的方式。

---

解題方法
針對名詞比較型題目（Describe the differences），最佳解題切入點為**「明確定義 + 數學公式／運作機制 + 對比表格 + 應用場景」**。作答時先分別闡述兩者觀念，最後附上對比摘要，能確保答題完整並取得滿分。

---

選項分析

(a) Precision（精確率）vs. Recall（召回率）

• Precision（精確率）：

  • 定義：在模型所有**預測為正例（Positive）**的樣本中，實際上有多少比例真正為正例。
  • 計算公式：
    $\text{Precision} = \frac{\text{TP}}{\text{TP} + \text{FP}}$
    其中 $\text{TP}$ 為真正例（True Positive），$\text{FP}$ 為偽正例（False Positive）。
  • 著重點：「預測精準度」，旨在避免誤判（False Positive）。
  • 應用場景：垃圾郵件過濾（若將正常重要郵件誤判為垃圾郵件，代價極高）。

• Recall（召回率 / 敏感度 Sensitivity）：

  • 定義：在所有**實際為正例（Positive）**的樣本中，模型成功抓出（正確預測）了多少比例。
  • 計算公式：
    $\text{Recall} = \frac{\text{TP}}{\text{TP} + \text{FN}}$
    其中 $\text{FN}$ 為偽負例（False Negative）。
  • 著重點：「涵蓋完整度」，旨在避免漏抓（False Negative）。
  • 應用場景：癌症篩檢、金融詐欺偵測（若漏診癌症或漏抓詐欺，會造成嚴重損害）。

比較項目	Precision（精確率）	Recall（召回率）
公式分母	$\text{TP} + \text{FP}$（預測正例總數）	$\text{TP} + \text{FN}$（實際正例總數）
核心目標	寧缺勿濫，確保預測出的正例都很準	寧可錯殺不可放過，確保實際正例都被抓出
防止代價	防止誤判（False Positive）	防止漏抓（False Negative）

---

(b) Process（程序）vs. Thread（執行緒）

• Process（程序）：

  • 定義：作業系統進行資源分配與管理的基本單位。
  • 記憶體空間：每個 Process 擁有獨立且互相隔離的地址空間（Address Space），包含獨立的 Code、Data、Heap 與 Stack 段。
  • 切換與通訊開銷：Process 間的上下文切換（Context Switch）需重載虛擬記憶體頁表（Page Table），開銷較大；Process 間通訊（IPC）必須透過 OS 核心機制（如 Pipe、Socket、Shared Memory）。

• Thread（執行緒）：

  • 定義：CPU 排程與執行的基本單位（又稱輕量級程序 Lightweight Process）。
  • 記憶體空間：同屬一個 Process 的多個 Thread 會共用該 Process 的地址空間、Code 段、Data 段、Heap 及開啟的檔案資源；但每個 Thread 擁有獨立的 Program Counter (PC)、暫存器集合（Registers）與 Stack。
  • 切換與通訊開銷：Thread 間的上下文切換無需更換頁表，開銷極小；Thread 間可直接讀寫共享記憶體進行通訊。

比較項目	Process（程序）	Thread（執行緒）
本質角色	資源分配的基本單位	CPU 排程執行的基本單位
記憶體獨立性	各 Process 間完全隔離獨立	同一 Process 內之 Thread 共用 Heap/Data 段，僅 Stack 獨立
切換開銷	高（需切換頁表與快取）	低（僅需保存暫存器與 Stack 指針）
安全性／影響	一個 Process 當掉不影響其他 Process	一個 Thread 發生非法存取崩潰，可能導致整個 Process 崩潰

---

(c) Overfitting（過度擬合）vs. Underfitting（擬合不足）

• Overfitting（過度擬合）：
  • 定義：模型對於訓練資料（Training Data）學習過度，連資料中的雜訊（Noise）與特例都記了下來，導致對訓練集表現極佳，但泛化到新測試集（Testing Data）時表現極差。

核心觀念

本題結合了無權重無向圖（Undirected Unweighted Graph）的核心遍歷演算法與連通性分析，考查點涵蓋三大圖論觀念：

1. 廣度優先搜尋（Breadth-First Search, BFS）：

   • 運作機制以先進先出佇列（Queue）為核心。在無權重圖上，BFS 自然形成「最短路徑樹」（Shortest Path Tree），每一層拜訪的節點皆代表與起點具相同邊數距離（Distance / Level）的點。
   • 當相鄰節點有多個選擇時，若題目指定照字母順序（alphabetical order）走訪，佇列入列順序必須嚴格按照字典順序。

2. 割點與關鍵節點（Cut Vertex / Articulation Point / $s$-$t$ Separator）：

   • 定義：若在圖 $G$ 中移除某一節點 $v$（及其相連邊）後，使得起點 $s$ 無法到達終點 $t$，則 $v$ 即為 $s \to t$ 的關鍵節點（$s$-$t$ Cut Vertex）。
   • 結構特徵：若從起點 $s$ 到終點 $t$ 存在兩條或兩條以上「頂點互斥（除了起終點外無其他共享頂點）」的路徑（Internally Vertex-Disjoint Paths），則除了 $s$ 與 $t$ 本身之外，不可能存在任何單一關鍵節點。

3. 最短路徑邊縮減（Diameter / Shortest Path Reduction）：

   • 兩點 $u, v$ 間的最短距離 $\text{dist}(u, v) = 2$，代表存在某一中間節點 $w$，使得 $(u, w)$ 與 $(w, v)$ 皆為圖中存在的邊。
   • 若欲加入一條新邊 $(x, y)$ 使得 $\text{dist}(A, H) = 2$，則該新邊的兩端點必定有一個能接駁起點 $A$（距離為 0 或 1），另一個端點能接駁終點 $H$（距離為 0 或 1）。

---

解題方法與詳細推導

給定無向圖 $G = (V, E)$，頂點集合 $V = \{A, B, C, D, E, F, G, H\}$。
邊集合 $E$ 的鄰接關係如下：

• $A: \{B, C\}$
• $B: \{A, D, E\}$
• $C: \{A, F\}$
• $D: \{B, G\}$
• $E: \{B, F\}$
• $F: \{C, E, H\}$
• $G: \{D, H\}$
• $H: \{F, G\}$

---

(a) BFS 走訪順序與各點距離推導

使用 Queue $Q$ 進行 BFS，起點為 $A$。距離記為 $\text{dist}$，走訪時相鄰節點按字母順序檢查：

1. 初始狀態：

   • 將 $A$ 加入 $Q$，$\text{dist}(A) = 0$。
   • 拜訪順序清單：$[A]$。
   • $Q = [A]$。

2. 處理 $A$（$\text{dist} = 0$）：

   • $A$ 出列。
   • 檢查 $A$ 的鄰居：按字母順序為 $B, C$。
   • 兩者皆未拜訪，設 $\text{dist}(B) = 1$、$\text{dist}(C) = 1$。
   • 加入 $Q$：$Q = [B, C]$。
   • 目前走訪清單：$[A, B, C]$。

3. 處理 $B$（$\text{dist} = 1$）：

   • $B$ 出列。
   • 檢查 $B$ 的鄰居：$A$（已拜訪）、$D$（未拜訪）、$E$（未拜訪）。
   • 依字母順序將 $D, E$ 設為 $\text{dist}(D) = 2$、$\text{dist}(E) = 2$。
   • 加入 $Q$：$Q = [C, D, E]$。
   • 目前走訪清單：$[A, B, C, D, E]$。

4. 處理 $C$（$\text{dist} = 1$）：

   • $C$ 出列。
   • 檢查 $C$ 的鄰居：$A$（已拜訪）、$F$（未拜訪）。
   • 設 $\text{dist}(F) = 2$。
   • 加入 $Q$：$Q = [D, E, F]$。
   • 目前走訪清單：$[A, B, C, D, E, F]$。

5. 處理 $D$（$\text{dist} = 2$）：

   • $D$ 出列。
   • 檢查 $D$ 的鄰居：$B$（已拜訪）、$G$（未拜訪）。
   • 設 $\text{dist}(G) = 3$。
   • 加入 $Q$：$Q = [E, F, G]$。
   • 目前走訪清單：$[A, B, C, D, E, F, G]$。

6. 處理 $E$（$\text{dist} = 2$）：

   • $E$ 出列。
   • 檢查 $E$ 的鄰居：$B$（已拜訪）、$F$（已拜訪）。
   • 無新節點入列。
   • $Q = [F, G]$。

7. 處理 $F$（$\text{dist} = 2$）：

   • $F$ 出列。
   • 檢查 $F$ 的鄰居：$C$（已拜訪）、$E$（已拜訪）、$H$（未拜訪）。

核心觀念
本題考查數據科學與機器學習的核心基礎觀念，涵蓋四個重要主題：

1. 資料不平衡（Class Imbalance）：類別分布極端懸殊下的模型評估陷阱與解決策略。
2. 交叉驗證（Cross-Validation）：模型泛化能力評估機制及其在小數據集（Limited Data）下的價值。
3. 訓練誤差與測試誤差（Training Error vs. Test Error）：評估模型擬合狀況（Underfitting 與 Overfitting）的指標差異。
4. 預訓練與微調（Pretraining vs. Fine-tuning）：遷移學習（Transfer Learning）的兩階段訓練範式與實際應用。

---

解題方法與各小題詳細解析

(a) 資料不平衡、處理方式與 Accuracy 迷思

• 類別不平衡（Class Imbalance）定義：
  在分類問題中，不同類別的樣本數量存在極大差距（例如正例占 $1\%$，負例占 $99\%$）。常見於信用卡詐欺偵測、醫療診斷、設備故障預警等場景。
• 兩種簡單處理方式：
  1. 重採樣法（Resampling Methods）：
     • 過採樣（Oversampling）：增加少數類別的樣本數量，例如使用 SMOTE（Synthetic Minority Over-sampling Technique）合成新樣本。
     • 欠採樣（Undersampling）：減少多數類別的樣本數量，例如隨機剔除多數類別的樣本。
  2. 調整損失權重（Cost-Sensitive Learning / Class Weight Adjustment）：
     在訓練損失函數（Loss Function）中給予少數類別更高的懲罰權重（Penalty），強迫模型對少數類別的預測錯誤更加敏感。
• Accuracy 為何會產生誤導：
  準確率（Accuracy）公式定義為：
  $\text{Accuracy} = \frac{TP + TN}{TP + TN + FP + FN}$
  當資料極度不平衡時（如負例 $99\%$、正例 $1\%$），若模型採取盲目將所有樣本皆預測為多數類（Negative）的極端策略（Naive Classifier），其 Accuracy 仍高達 $99\%$。然而，該模型對關鍵少數類（Positive）的識別能力（Recall / Precision）實際上為 $0$。因此，Accuracy 無法真實反映模型在少數類別上的判斷品質。此時應改用 $F_1$-score、Precision-Recall AUC 或 ROC-AUC 作為評估指標。

---

(b) 交叉驗證及其在資料有限時的作用

• 交叉驗證（Cross-Validation, CV）定義：
  一種評估模型泛化能力的重採樣技術。最常見的 $K$-折交叉驗證（$K$-Fold Cross-Validation）是將整體資料隨機劃分為 $K$ 個大小相等的子集（Folds），輪流使用 $K-1$ 個子集作為訓練集（Training Set），剩餘 1 個子集作為驗證集（Validation Set），重複 $K$ 次後，取 $K$ 次驗證結果的平均值作為模型最終的效能評估指標。
• 資料有限時發揮作用的原因：
  1. 極大化資料利用率：避免傳統單次劃分（Train-Test Split）導致部分資料未被訓練到的浪費，確保每個樣本都有機會同時參與訓練與驗證。
  2. 降低估計方差（Variance）：單一劃分容易受隨機抽樣偏差影響；透過多次切分並計算平均值，能顯著減少採樣雜訊，給出更穩定且無偏的模型效能估算。

---

(c) 訓練誤差 vs. 測試誤差

• 訓練誤差（Training Error）：
  模型在「訓練集（Training Data）」上計算出的誤差或損失值。
  • 指示含意：代表模型擬合（Fitting）已知數據的能力。若訓練誤差過高，代表模型連訓練集的模式都無法掌握，存在欠擬合（Underfitting / High Bias）。

(a)
距離計算：

$$\begin{aligned} d(Q,A)&=\sqrt{(3-1)^2+(3-1)^2}= \sqrt{8}=2.828\\ d(Q,B)&=\sqrt{(3-2)^2+(3-1)^2}= \sqrt{5}=2.236\\ d(Q,C)&=\sqrt{(3-2)^2+(3-2)^2}= \sqrt{2}=1.414\\ d(Q,D)&=\sqrt{(3-4)^2+(3-4)^2}= \sqrt{2}=1.414\\ d(Q,E)&=\sqrt{(3-5)^2+(3-4)^2}= \sqrt{5}=2.236\\ d(Q,F)&=\sqrt{(3-4)^2+(3-5)^2}= \sqrt{5}=2.236 \end{aligned}$$

最近的三個鄰居：$C(-), D(+), B(-)$（若距離相同可任選，但結果不變）。
投票結果 $-$ 為多數 → 預測標記為 $-$。