114 年 國立臺灣大學圖書資訊系碩士班乙組《電子計算機概論》

核心觀念

這題在考有號整數的二補數表示法，以及它為何適合電腦執行整數加減。對固定寬度的 $n$ 位元資料，二補數將每種位元組合解讀為一個有號整數。

若位元由左至右記為 $b_{n-1}b_{n-2}\cdots b_0$，其值為：

$$-b_{n-1}2^{n-1}+\sum_{i=0}^{n-2}b_i2^i$$

最高位元的權重為負，其餘位元的權重與一般二進位相同。因此，$n$ 位元二補數的表示範圍是：

$$-2^{n-1}\ \text{至}\ 2^{n-1}-1$$

解題方法與二補數特性

從「如何表示負數」與「硬體如何執行加減」兩個角度說明，即可回答二補數普遍使用的原因：

• 正數與零沿用一般二進位表示：非負數的二補數表示與普通二進位相同。例如，使用 8 位元時，$5$ 表示為 00000101。

• 負數以取反後加一表示：要將正數 $x$ 編碼為 $-x$，先將 $x$ 的各位元反相，再加 $1$。例如，8 位元的 $5$ 是 00000101，逐位反相後為 11111010，加 $1$ 得 11111011，即 $-5$。

• 加法器可同時處理正數與負數：硬體不需要為負數另設一套加法規則。以上述 8 位元數值為例，$5+(-5)$ 可直接以二進位相加：

  $$\texttt{00000101}+\texttt{11111011} =\texttt{1 00000000}$$

  固定保留 8 位元並丟棄最左側的進位後，結果為 00000000，即 $0$。

• 減法可轉成加法：因為 $-B$ 可由 $B$ 的二補數取得，故 $A-B$ 可用 $A+(-B)$ 計算。處理器可以重用加法器，簡化算術電路。

• 零只有一種表示：二補數沒有獨立的「負零」編碼。

本題要求使用快速排序（Quick Sort）演算法對給定數列進行排序，並詳細解釋過程。

核心觀念：
快速排序是一種分治（Divide and Conquer）演算法。它的基本思想是選擇一個「基準點」（pivot），然後將數列分割成兩個子數列：一個是所有小於基準點的元素，另一個是所有大於基準點的元素。然後遞迴地對這兩個子數列進行快速排序，直到整個數列排序完成。

給定數列：
[55, 77, 22, 66, 11, 44, 88, 33]

選擇基準點 (Pivot) 的策略：
這裡我們採用最常見的策略之一：選擇數列的最後一個元素作為基準點。

排序步驟詳解：

第一輪排序 (Partition 1)：

1. 數列：[55, 77, 22, 66, 11, 44, 88, 33]
2. 選擇基準點 (Pivot)：選最後一個元素 33。
3. 分割 (Partitioning)：

   • 我們需要將數列分成兩部分：小於 33 的元素放在左邊，大於 33 的元素放在右邊。

   • 從數列的開頭開始掃描。

   • 掃描過程（以 Lomuto partition scheme 為例，從左到右）：

     • i 指向目前已處理部分（小於 pivot）的下一個位置。初始 i = 0。
     • j 掃描整個數列。
     • 當 arr[j] < pivot 時，交換 arr[i] 和 arr[j]，然後 i++。

   • 執行細節：

     • 數列：[55, 77, 22, 66, 11, 44, 88, 33]，Pivot = 33，i = 0
     • j=0, arr[0]=55. 55 >= 33. 不交換。
     • j=1, arr[1]=77. 77 >= 33. 不交換。
     • j=2, arr[2]=22. 22 < 33. 交換 arr[i] (55) 和 arr[j] (22). 數列變為 [22, 77, 55, 66, 11, 44, 88, 33]. i++. i=1.
     • j=3, arr[3]=66. 66 >= 33. 不交換。
     • j=4, arr[4]=11. 11 < 33. 交換 arr[i] (77) 和 arr[j] (11). 數列變為 [22, 11, 55, 66, 77, 44, 88, 33]. i++. i=2.
     • j=5, arr[5]=44. 44 >= 33. 不交換。
     • j=6, arr[6]=88. 88 >= 33. 不交換。
     • j=7, arr[7]=33. 這是 pivot，我們通常在迴圈結束後才將 pivot 放到正確位置。

   • 迴圈結束後，將 pivot (33) 與 arr[i] (55) 交換。

   • 結果：[22, 11, 33, 66, 77, 44, 88, 55] (此處以 Hoare partition scheme 為例，pivot 33 位於 index 2，左邊 22, 11 < 33，右邊 66, 77, 44, 88 > 33)

   • 註：不同的 partition scheme (如 Lomuto 或 Hoare) 在 pivot 的最終位置和分割方式上略有差異，但核心思想相同。這裡我們假設 pivot 33 最終被放置在 index 2 的位置。

4. 遞迴呼叫：
   • 對左子數列 [22, 11] 進行排序。
   • 對右子數列 [66, 77, 44, 88, 55] 進行排序。

本題主要探討 UDP (User Datagram Protocol) 的「無連接」特性以及它如何判斷停止傳輸封包，並從 ICMP (Internet Control Message Protocol) 的角度來解釋。

核心觀念：

• 無連接 (Connection-less)：指通訊雙方在傳送資料前，不需要像 TCP 那樣先建立一個邏輯連接。資料包（Datagram）被獨立地發送，每個資料包都包含完整的目的地位址和埠號。
• UDP 的特性：UDP 是一種盡力而為（best-effort）的協議，它不保證資料傳輸的可靠性、順序性或流量控制。它只負責將應用層的資料封裝成 UDP 資料包，然後交給底層的 IP 協議進行傳輸。
• ICMP 的作用：ICMP 主要用於網路診斷和錯誤報告，它不是用來傳輸應用資料的，而是用來傳達控制訊息的。

Part 1: 什麼是 'connection-less' (無連接)？

「無連接」意味著：

1. 無需預先建立連接：發送方和接收方之間不需要進行「三次握手」（three-way handshake）來建立一個穩定的、端對端的連接。應用程式可以直接開始發送 UDP 資料包。
2. 獨立傳輸：每個 UDP 資料包都是一個獨立的單元，被單獨路由和傳輸。它們之間沒有順序的依賴關係，並且可能以不同的路徑到達目的地，甚至可能丟失、重複或亂序。
3. 無狀態 (Stateless)：UDP 協議本身不維護連接狀態。發送方和接收方不需要記錄關於連接的任何信息，例如序列號、確認號或窗口大小。
4. 開銷小：由於沒有連接建立和維護的額外開銷，UDP 的協議頭非常簡潔，傳輸效率較高。

Part 2: UDP 如何決定何時停止傳輸封包？從 ICMP 的角度解釋。

UDP 本身並不「主動」決定何時停止傳輸封包。UDP 的設計哲學是將可靠性、流量控制和連接管理等複雜功能留給應用層處理，或者依賴於底層協議。UDP 傳輸的停止，通常是由以下幾種情況觸發的，其中 ICMP 在某些情況下會發揮作用：

1. 應用程式停止傳輸：

   • 這是最直接的原因。當應用程式不再有資料需要發送時，它就會停止調用 UDP 發送函數，UDP 也就停止發送封包。UDP 協議本身沒有定時器來決定何時停止。

2. 目的地無法到達 (ICMP Destination Unreachable)：

   • 當 UDP 資料包在傳輸過程中，如果網路設備（如路由器）發現該資料包無法到達目的地（例如，目的主機不存在，或者沒有監聽該埠號的應用程式），它可能會生成一個 ICMP 訊息，例如「Destination Unreachable」。
   • 這個 ICMP 訊息會被發送回給源主機。

本題探討 TCP (Transmission Control Protocol) 中的兩個重要窗口機制：流量控制窗口 (Flow Control Window) 和擁塞控制窗口 (Congestion Control Window)，以及它們之間的相互關係。

核心觀念：

• TCP 的可靠性：TCP 是一個面向連接、可靠的傳輸協議。它通過序列號、確認應答、重傳機制以及窗口機制來保證資料的可靠傳輸。
• 流量控制 (Flow Control)：防止發送方發送資料的速度超過接收方的處理能力，避免接收方緩衝區溢出。
• 擁塞控制 (Congestion Control)：防止發送方發送的資料量超過網路的容量，避免網路擁塞，從而提高整個網路的吞吐量和穩定性。

Part 1: 流量控制窗口 (Flow Control Window)

• 功能：流量控制窗口的大小由接收方決定。接收方在 TCP 連接建立時（或在後續的 ACK 封包中）會告知發送方自己接收緩衝區的可用空間大小。這個值被稱為「接收窗口大小」（Receiver Window, rwnd）。
• 目的：確保發送方不會發送過多的數據，以免填滿接收方的緩衝區，導致數據丟失。
• 工作方式：發送方在發送數據時，其發送的數據量不能超過 rwnd。當接收方收到數據並處理後，會釋放緩衝區空間，並通過 ACK 封包更新 rwnd 的值。

Part 2: 擁塞控制窗口 (Congestion Control Window)

• 功能：擁塞控制窗口的大小由發送方根據對網路狀況的估計來動態調整。它反映了發送方認為網路能夠承受的數據量。
• 目的：防止發送方發送過多的數據，導致網路路由器和交換機之間的鏈路發生擁塞，造成數據包丟失，從而影響整個網路的性能。
• 工作方式：發送方維護一個擁塞窗口大小 (cwnd)。cwnd 的值會根據網路的反應（如 ACK 的到達速率、丟包事件）來動態增減。例如，當收到 ACK 時，cwnd 可能會增加（如慢啟動和擁塞避免階段）；當檢測到丟包時，cwnd 會顯著減小（如擁塞窗口減半）。

Part 3: 滑動窗口 (Sliding Window)

本題探討在關係型資料庫的資料建模中，「反正規化」（Denormalization）的需求、原因及其影響。

核心觀念：

• 正規化 (Normalization)：正規化是關係型資料庫設計中一個關鍵的過程，旨在減少資料冗餘、提高資料一致性，並簡化資料庫的結構。它通過將大型表分解為更小的、結構良好的表，並定義表之間的關係來實現。常見的正規化形式有第一正規化 (1NF)、第二正規化 (2NF)、第三正規化 (3NF) 等。
• 反正規化 (Denormalization)：與正規化相反，反正規化是故意引入資料冗餘，通過合併表或增加派生欄位來優化查詢性能，尤其是在讀取密集型（read-heavy）的應用場景下。

Part 1: 進行「反正規化」的需求與原因

儘管正規化是良好的資料庫設計實踐，但在某些情況下，過度正規化（即將資料庫正規化到非常高的範式，如 4NF 或 5NF）可能會導致查詢性能下降。這主要體現在：

1. 減少 JOIN 操作的數量：

   • 高度正規化的資料庫通常將資訊分散在多個表中。為了檢索一個完整的記錄（例如，顯示一個訂單的所有詳細信息，包括客戶姓名、產品名稱等），需要執行大量的 JOIN 操作。
   • JOIN 操作在執行時計算成本很高，尤其是在處理大型資料集時，會顯著減慢查詢速度。
   • 反正規化通過將相關資訊合併到一個表中，可以減少或消除這些昂貴的 JOIN 操作。

2. 提高讀取性能 (Read Performance)：

   • 許多應用程式，特別是報表系統、資料分析工具和前端顯示，主要是進行讀取操作。
   • 對於這些讀取密集型的場景，查詢速度是首要考量。通過反正規化，將經常一起被查詢的資料放在同一個表中，可以顯著加快資料檢索的速度。

3. 簡化查詢語句：

   • 減少 JOIN 操作也意味著查詢語句會更簡單、更容易編寫和理解。

4. 為資料倉儲 (Data Warehouse) 和商業智慧 (BI) 優化：

   • 在資料倉儲環境中，通常會採用星型模型（Star Schema）或雪花模型（Snowflake Schema），這些模型本身就是反正規化的體現。

核心觀念

本題的核心在於測驗考生對關聯式資料庫管理系統（RDBMS）之實體關聯設計與關聯代數（Relational Algebra）查詢運算機制的理解程度。主要涵蓋以下兩大概念：

1. 實體關聯模型（ER Model）與關聯綱要設計（Relational Schema Design）：
   • 實體（Entity / Table） 與 關聯（Relationship） 在概念模型轉換為邏輯模型時的角色。
   • 建立關聯的系統目的：資料完整性（Data Integrity）、降低資料冗餘（Data Redundancy）、避免資料異常（Anomalies）、反映領域邏輯（Business Semantics）。
2. 基底表（Base Table）與衍生表（Derived Table）的本質差異：
   • 基底表：持久化儲存在磁碟中且具備綱要定義的實體表。
   • 衍生表：由子查詢（Subquery）、視圖（View）或共用資料表表達式（CTE, Common Table Expression）在執行期（Runtime）動態產生的暫存結果集（Ephemeral Result Set）。
   • 關聯（Constraint / Schema Level） 與 連接（Join / Query Level） 的層次區隔：關聯屬於 DDL 綱要層級的外鍵約束（Foreign Key Constraint），而連接屬於 DQL 關聯代數的二元運算（Binary Operation）。

---

解題方法

第一部分：資料庫建模者在實體（資料表）間建立關聯的主要原因

在關聯式資料庫中，資料庫建模者（Database Modeler）通常會透過**主鍵（Primary Key, PK）與外鍵（Foreign Key, FK）**在各資料表之間建立明確的關聯（Relationships），其核心原因如下：

1. 反映真實世界的實體互動與業務邏輯（Modeling Real-world Semantics & Business Rules）：

   • 真實世界的實體並非各自孤立，而是存在一對一（$1:1$）、一對多（$1:N$）或多對多（$M:N$）的互動（例如：「學生選修課程」、「顧客建立訂單」）。
   • 建立關聯能將現實業務規則精確抽象化並映射至資料庫結構中。

2. 維護參照完整性與資料一致性（Enforcing Referential Integrity & Data Consistency）：

   • 透過外鍵約束（Foreign Key Constraint），確保子表（Child Table）中的外鍵值必定存在於父表（Parent Table）的主鍵中，防止產生無效參照的「孤兒記錄（Orphan Records）」。
   • 支援串聯操作（Cascading Actions，如 ON DELETE CASCADE、ON UPDATE CASCADE），在父表資料異動時自動維護關聯資料的正確性。

3. 支援資料庫正規化並消除資料冗餘（Supporting Normalization & Minimizing Redundancy）：

   • 將大型萬能表（Universal Table）透過正規化理論（1NF 至 BCNF/3NF）分解為多個專屬實體表，各表僅儲存單一主題的資料。
   • 透過關聯機制重新串接各獨立實體，能徹底消除資料重複儲存，避免新增異常（Insertion Anomaly）、刪除異常（Deletion Anomaly）與更新異常（Update Anomaly）。

4. 提供結構化的查詢導引與最佳化基礎（Facilitating Logical Navigation & Query Optimization）：

   • 明確的關聯定義使資料庫查詢最佳化器（Query Optimizer）能利用鍵值與索引（Index）評估最佳存取路徑（Access Path）與連接策略（如 Nested-Loop Join、Hash Join、Merge Join），提升檢索效能。

---

第二部分：連接兩衍生表（Derived Tables）時，是否需要（以及能否）建立關聯？

本題探討近年來數據儲存技術的發展，特別是針對機器學習和 AI 所需的大量數據。要求定義和解釋 Data Lake 與 Data Warehouse，比較它們的差異，並提出個人觀點。

核心觀念：

• 數據儲存的演進：從傳統的結構化數據處理，到大數據時代的非結構化、半結構化數據處理，對數據儲存和分析的需求不斷變化。
• Data Lake (數據湖)：一個集中式儲存庫，能夠以原始格式儲存大量的結構化、半結構化和非結構化數據。
• Data Warehouse (數據倉庫)：一個經過設計、優化，用於報告和分析的結構化數據的集中式儲存庫。

Part 1: Data Lake (數據湖) 的定義與解釋

• 定義：Data Lake 是一個大規模的、中央化的數據儲存庫，它允許你以原始、未經過處理的格式儲存所有類型的數據，無論其來源如何。
• 解釋：
  • 儲存所有數據：Data Lake 的核心理念是「儲存一切」。它能夠儲存來自各種來源的數據，包括結構化數據（如資料庫中的表格）、半結構化數據（如 CSV、XML、JSON 文件）和非結構化數據（如文本文件、圖片、音頻、視頻、日誌文件）。
  • 原始格式 (Schema-on-Read)：數據在被儲存到 Data Lake 時，通常保持其原始格式，不做或僅做最少的轉換。數據的結構（Schema）是在讀取數據進行分析時才定義的（Schema-on-Read）。這意味著你可以先儲存數據，稍後再決定如何解釋和分析它。
  • 靈活性高，成本較低：由於不對數據進行大規模的預處理和轉換，Data Lake 的建立和擴展通常比 Data Warehouse 更具成本效益，尤其是在處理海量數據時。
  • 用途廣泛：非常適合用於數據探索、數據科學、機器學習、AI 模型訓練，以及需要處理多樣化數據源的場景。

Part 2: Data Warehouse (數據倉庫) 的定義與解釋

• 定義：Data Warehouse 是一個專門設計用於支持商業智慧（BI）活動和數據分析的數據儲存庫。它儲存的是經過轉換、清理和組織的數據，通常是結構化的。
• 解釋：
  • 結構化數據：Data Warehouse 主要儲存結構化數據，這些數據經過 ETL (Extract, Transform, Load) 或 ELT 過程的處理，使其符合預定義的數據模型（通常是星型模型或雪花模型）。
  • 經過處理與轉換 (Schema-on-Write)：數據在進入 Data Warehouse 之前，會經過嚴格的轉換和清理過程，以確保數據的質量、一致性和標準化。數據的結構（Schema）是在寫入數據庫時就已經定義好的（Schema-on-Write）。
  • 優化查詢性能：Data Warehouse 的設計目標是快速、高效地執行複雜的查詢和報表。其數據模型經過優化，以支持 OLAP (Online Analytical Processing) 操作。
  • 用途：主要用於商業報告、趨勢分析、決策支持、歷史數據查詢。

Part 3: Data Lake 與 Data Warehouse 的差異

特徵	Data Lake (數據湖)	Data Warehouse (數據倉庫)
數據類型	結構化、半結構化、非結構化 (所有類型)	主要為結構化數據
數據格式	原始格式、未經處理	經過轉換、清理、結構化的格式
Schema 定義	Schema-on-Read (讀取時定義)	Schema-on-Write (寫入時定義)