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

本題考查網路學中的基本名詞定義。

觀念解析：

• Bandwidth (頻寬)：在網路通訊中，頻寬是指在單位時間內，網路能夠傳輸的資料量上限。它通常以位元每秒 (bits per second, bps) 或其倍數（如 Mbps, Gbps）來衡量。簡單來說，頻寬決定了網路連線的「寬度」，越寬表示能同時傳送的資料越多、越快。

選項分析：

• (a) Data transfer speed (資料傳輸速率)：這是對頻寬最直接的描述。頻寬決定了最大資料傳輸速率。

本題考查資料庫正規化（Database Normalization）中的第三正規化 (3NF) 的主要目標。

觀念解析：
資料庫正規化是設計關聯式資料庫時，用來組織資料以減少資料冗餘 (data redundancy) 和提高資料完整性 (data integrity) 的過程。正規化的主要目標是將表格分解成較小的、結構良好的表格，並定義表格之間的關係。

• 第一正規化 (1NF)：確保表格中的所有屬性都是原子性的 (atomic)，且沒有重複的群組。
• 第二正規化 (2NF)：在 1NF 的基礎上，要求所有非主鍵屬性 (non-key attributes) 完全函數依賴於主鍵 (primary key)，而非部分函數依賴。
• 第三正規化 (3NF)：在 2NF 的基礎上，要求所有非主鍵屬性不得傳遞依賴 (transitively dependent) 於主鍵。也就是說，非主鍵屬性之間不能有函數依賴關係。

本題考查設計高擴展性 (highly scalable) 網頁應用程式時，哪些因素是「最不」需要關注的。

觀念解析：
高擴展性意味著應用程式能夠在使用者數量或資料量增加時，透過增加資源（硬體或軟體）來維持效能。設計可擴展的網頁應用程式需要考慮多個層面，包括資料儲存、請求分流、效能優化等。

選項分析：

• (a) Database sharding (資料庫分片)：當單一資料庫無法處理大量讀寫請求時，將資料分散到多個資料庫（分片）是提高擴展性的常見方法。這絕對是設計高擴展性系統時需要考慮的。
• (b) Load balancing (負載平衡)：將進入的網路流量或處理請求的任務，分配到多個伺服器上，以避免單一伺服器過載，是提高系統可用性和擴展性的關鍵技術。這也是高擴展性設計的重要考量。
• (c) Choosing a relational database (選擇關聯式資料庫)：關聯式資料庫（如 MySQL, PostgreSQL）在處理結構化資料和複雜查詢方面表現出色，但當面臨極大規模的讀寫請求或需要極高吞吐量時，它們的擴展性可能不如 NoSQL 資料庫。雖然關聯式資料庫仍可擴展（例如透過主從複製、讀寫分離、分片等），但相較於其他選項，在「極致」高擴展性的場景下，它本身可能不如專為擴展性設計的資料庫（如某些 NoSQL 資料庫）那樣「內建」擴展性。也就是說，選擇關聯式資料庫本身可能是一個限制，或者說，在追求極致擴展時，需要仔細考慮其擴展策略，甚至可能需要考慮其他類型的資料庫。因此，它「可能」是相對較不直接的擴展性手段，或說，它本身可能是一個需要被「克服」的挑戰，而不是一個「解決方案」。
• (d) Caching frequently accessed data (快取經常存取之資料)：快取是減輕資料庫和後端伺服器負載、提高回應速度的關鍵技術，對於高擴展性應用程式至關重要。

本題考查 IP 位址 (IP address) 的主要用途。

觀念解析：
IP 位址是網際網路協定 (Internet Protocol) 中用來識別網路上的裝置的位址。它類似於現實世界中的住家地址或電話號碼，用於在網路中定位和尋找裝置。

選項分析：

• (a) To identify a website's content. (識別網站內容)：網站內容通常由域名 (domain name) 來識別，IP 位址是域名解析後的結果，用於找到存放網站的伺服器。IP 位址本身不直接識別內容。

本題考查作業系統 (Operating System, OS) 的核心角色。

觀念解析：
作業系統是電腦系統中最基本、最重要的軟體。它負責管理電腦的所有硬體和軟體資源，並為使用者和應用程式提供一個統一、方便的介面。

選項分析：

• (a) To directly control hardware devices. (直接控制硬體裝置)：作業系統透過驅動程式 (device drivers) 來間接控制硬體，而不是直接控制。驅動程式是硬體和作業系統之間的橋樑。
• (b) To provide an interface between the user and hardware, and manage system resources. (提供使用者與硬體之間的介面，並管理系統資源)：這是作業系統最全面的描述。

本大題考查計算機科學和資訊技術中的基本名詞與概念。

1. 觀念解析：尋找減少檔案或訊號表示所需資料量的方法。
   答案：Compression (壓縮)
   說明：資料壓縮技術（如 ZIP, GZIP）透過移除冗餘或不重要的資訊來減少檔案大小，以節省儲存空間或加快傳輸速度。

2. 觀念解析：尋找遵循「後進先出」原則的資料結構。
   答案：Stack (堆疊)
   說明：堆疊是一種線性資料結構，其操作遵循 LIFO 原則。最後加入的元素會最先被移除。例如，函式呼叫堆疊。

3. 觀念解析：尋找節點之間互相連接的網路拓撲。
   答案：Mesh (網狀)
   說明：網狀拓撲 (Mesh Topology) 中，網路中的每一個節點都至少與其他一個節點直接連接，在全連接網狀拓撲中，每個節點都直接連接到所有其他節點。

4. 觀念解析：尋找斷電後會遺失資料的記憶體類型。
   答案：Volatile (揮發性)
   說明：揮發性記憶體（如 DRAM，即我們常說的 RAM）在失去電力後會清除其儲存的資訊。非揮發性記憶體（如 ROM, Flash Memory）則不會。

5. 觀念解析：尋找電腦中最小的資料單位。
   答案：Bit (位元)
   說明：位元 (bit) 是二進位數字，是電腦中最小的資訊單位，只能是 0 或 1。8 個位元組成一個位元組 (byte)。

6. 觀念解析：尋找構成全球資訊網 (World Wide Web) 的基礎協定。
   答案：HTTP (Hypertext Transfer Protocol)
   說明：HTTP 是用於在網際網路上的網頁伺服器和瀏覽器之間傳輸超文字文件（網頁）的應用層協定。它是 WWW 的基礎。

本大題為申論題，涵蓋分散式系統、資料結構、人工智慧倫理、網路協定、計算架構等領域。以下為各題的詳解。

---

1. Explain CAP (Consistency, Availability, Partition Tolerance) Theorem and discuss its trade-offs. (10%)

核心觀念： CAP 定理是分散式系統設計中的一個基本約束，指出在網路分區 (Partition Tolerance) 的情況下，系統無法同時滿足一致性 (Consistency) 和可用性 (Availability)。

詳解：

CAP 定理 (CAP Theorem)

CAP 定理，也稱為 Brewer 定理 (Brewer's Theorem)，是由 Eric Brewer 在 2000 年提出的。它指出，在一個分散式系統中，當發生網路分區 (Network Partition) 時，系統只能同時滿足以下三個特性中的最多兩個：

1. 一致性 (Consistency, C)：所有節點在同一時間讀取到相同的值。換句話說，任何一個讀取操作都會得到最近一次寫入操作的結果。
2. 可用性 (Availability, A)：每個非故障的節點都必須在有限的時間內回應所有請求，而不會發生錯誤。這意味著系統始終保持可服務狀態，即使部分節點故障。
3. 分區容錯性 (Partition Tolerance, P)：系統能夠在網路通訊發生中斷（即網路分區，Partition）時，繼續運作。網路分區是指系統中的一部分節點無法與其他節點通訊。

CAP 定理的含義與權衡 (Trade-offs)：

由於網路分區在分散式系統中幾乎是不可避免的（例如，網路延遲、路由器故障、節點離線等），因此 CAP 定理實際上告訴我們，在設計分散式系統時，我們必須在一致性 (C) 和可用性 (A) 之間做出權衡，因為分區容錯性 (P) 是必須具備的。

• CP 系統 (Consistency + Partition Tolerance)：

  • 權衡：犧牲可用性 (A)。
  • 解釋：當發生網路分區時，CP 系統會選擇放棄部分或全部節點的可用性，以確保所有存活節點的資料保持一致。例如，如果一個節點無法聯繫到大多數其他節點，它可能會拒絕寫入請求，或者暫停服務，直到網路恢復正常，以避免產生不一致的資料。
  • 應用場景：要求極高資料一致性的應用，如金融交易系統、銀行帳戶餘額查詢等。

• AP 系統 (Availability + Partition Tolerance)：

  • 權衡：犧牲一致性 (C)。
  • 解釋：當發生網路分區時，AP 系統會選擇繼續提供服務，即使這可能導致不同節點上的資料暫時不一致。系統可能會允許寫入操作到部分節點，並在網路恢復後，透過一些機制（如「最終一致性」或「向量時鐘」）來解決不一致的問題。
  • 應用場景：對可用性要求極高，可以容忍短暫資料不一致的應用，如社交媒體的訊息發布、線上購物車、日誌記錄等。

• CA 系統 (Consistency + Availability)：

  • 權衡：犧牲分區容錯性 (P)。
  • 解釋：這種系統假設網路永遠不會發生分區。在單一節點或無網路分區的環境下，CA 系統可以同時保證一致性和可用性。然而，在真實的分散式環境中，網路分區是無法避免的，因此 CA 系統在分散式場景下是不可行的。

總結：

CAP 定理是分散式系統設計中的關鍵考量。設計師必須根據應用程式的需求，在一致性、可用性和分區容錯性之間做出明智的選擇。在現代分散式系統中，由於網路分區的普遍性，設計師通常需要在 C 和 A 之間進行權衡，以構建出滿足特定需求的系統。

---

2. Describe methods used to resolve collisions in hash tables. (10%)

核心觀念： 雜湊表 (Hash Table) 在將鍵 (key) 映射到儲存位置時，可能會發生不同的鍵映射到同一個位置的現象，稱為雜湊碰撞 (Hash Collision)。解決碰撞是雜湊表設計的關鍵。

詳解：

雜湊表是一種透過雜湊函數 (hash function) 將鍵映射到儲存位置（稱為桶，bucket）的資料結構，以實現快速的插入、刪除和查找操作。當兩個或多個不同的鍵被雜湊到同一個桶時，就發生了雜湊碰撞。解決碰撞的方法主要有兩大類：開放定址法 (Open Addressing) 和鏈式定址法 (Separate Chaining)。

一、 開放定址法 (Open Addressing)

在開放定址法中，所有鍵都直接儲存在雜湊表中。當發生碰撞時，系統會尋找表中其他可用的空位來儲存該鍵。有多種探測 (probing) 策略來尋找空位：

1. 線性探測 (Linear Probing)：

   • 方法：如果雜湊函數計算出的位置 $h(k)$ 已被佔用，則依序檢查下一個位置 $h(k)+1, h(k)+2, \dots$ (模雜湊表大小)。
   • 公式：$h(k, i) = (h'(k) + i) \pmod{m}$，其中 $h'(k)$ 是原始雜湊函數，$i = 0, 1, 2, \dots, m-1$。
   • 缺點：容易產生「聚集」現象 (clustering)，即連續的已佔用槽位會形成一個塊，使得後續的插入和查找操作需要更長的探測序列。

2. 二次探測 (Quadratic Probing)：

   • 方法：如果位置 $h(k)$ 被佔用，則依序檢查 $h(k)+1^2, h(k)+2^2, h(k)+3^2, \dots$ (模雜湊表大小)。
   • 公式：$h(k, i) = (h'(k) + c_1 i + c_2 i^2) \pmod{m}$，其中 $c_1, c_2$ 是常數。
   • 優點：比線性探測更能分散探測路徑，減少聚集現象。
   • 缺點：可能無法探測到表中所有的空槽位，且仍然可能產生二次聚集。

3. 雙重雜湊 (Double Hashing)：

   • 方法：使用第二個雜湊函數 $h_2(k)$ 來決定探測的步長。如果位置 $h_1(k)$ 被佔用，則依序檢查 $h_1(k) + h_2(k), h_1(k) + 2h_2(k), h_1(k) + 3h_2(k), \dots$ (模雜湊表大小)。
   • 公式：$h(k, i) = (h_1(k) + i \cdot h_2(k)) \pmod{m}$。
   • 優點：能更有效地分散探測路徑，減少聚集現象，通常提供較好的效能。
   • 要求：$h_2(k)$ 必須永遠不能為 0，且 $h_2(k)$ 與雜湊表大小 $m$ 應互質，以確保能探測到所有槽位。

二、 鏈式定址法 (Separate Chaining)

在鏈式定址法中，雜湊表本身只儲存指向鏈結串列 (linked list) 的指標。每個桶都對應一個鏈結串列，用於儲存所有雜湊到該桶的鍵。

1. 方法：當發生碰撞時，新鍵被添加到對應桶的鏈結串列的頭部或尾部。
2. 優點：
   • 實現相對簡單。
   • 雜湊表不會「滿」，只要記憶體足夠，就可以不斷插入元素。
   • 刪除操作相對容易。
   • 對雜湊函數的要求比開放定址法低。
3. 缺點：
   • 需要額外的空間來儲存鏈結串列的節點和指標。
   • 如果雜湊函數設計不佳，導致所有鍵都雜湊到同一個桶，效能會退化為鏈結串列的查找，即 $O(n)$。

其他處理碰撞的考量：

• 重雜湊 (Rehashing)：當雜湊表的負載因子 (load factor, $\alpha = \frac{\text{元素數量}}{\text{桶數量}}$) 過高時，碰撞的機率會顯著增加，導致效能下降。此時，可以創建一個更大的雜湊表，並將所有現有元素重新雜湊到新表中。
• 選擇好的雜湊函數：一個好的雜湊函數應該能夠均勻地將鍵分散到所有桶中，以最小化碰撞的發生。

結論：

解決雜湊碰撞的方法主要有開放定址法（線性探測、二次探測、雙重雜湊）和鏈式定址法。開放定址法將所有元素存儲在雜湊表本身，而鏈式定址法則為每個桶維護一個鏈結串列。選擇哪種方法取決於對記憶體使用、插入/刪除/查找效能、實現複雜度以及預期負載因子的權衡。

---

3. Discuss the ethical considerations surrounding the development and deployment of Artificial Intelligence (AI) systems. (10%)

核心觀念： AI 技術的快速發展帶來了巨大的潛力，但也伴隨著一系列複雜的倫理問題，需要在開發和部署過程中仔細考量。

詳解：

人工智慧 (AI) 的發展和應用正以前所未有的速度改變著我們的社會。然而，隨著 AI 能力的增強，也引發了一系列深刻的倫理挑戰，這些挑戰需要開發者、決策者和社會大眾共同關注和解決。

主要的倫理考量包括：

1. 偏見與歧視 (Bias and Discrimination)：

   • 問題：AI 系統通常透過從數據中學習來做出決策。如果訓練數據本身包含社會偏見（例如，種族、性別、年齡歧視），AI 系統就會繼承並可能放大這些偏見，導致不公平的結果。例如，在招聘、貸款審批、刑事司法等領域，帶有偏見的 AI 可能會歧視特定群體。
   • 考量：需要確保訓練數據的多樣性和代表性，開發檢測和緩解偏見的演算法，並對 AI 系統的輸出進行審查。

2. 隱私權侵犯 (Privacy Invasion)：

   • 問題：許多 AI 應用（如人臉辨識、個人化推薦、語音助理）需要收集和處理大量的個人數據。這可能導致對個人隱私的過度侵犯，數據可能被濫用、洩露或用於監控。
   • 考量：需要實施嚴格的數據保護措施，遵守隱私法規（如 GDPR），採用差分隱私 (differential privacy) 等技術，並確保數據使用的透明度。

3. 問責制與責任歸屬 (Accountability and Responsibility)：

   • 問題：當 AI 系統犯錯或造成損害時（例如，自動駕駛汽車發生事故，醫療 AI 誤診），誰應該負責？是開發者、使用者、部署者，還是 AI 本身？AI 的決策過程有時難以解釋（「黑箱」問題），這使得追究責任更加困難。
   • 考量：需要建立清晰的責任框架，開發可解釋的 AI (Explainable AI, XAI) 技術，並對 AI 系統的行為進行監管。

4. 就業衝擊與經濟不平等 (Impact on Employment and Economic Inequality)：

   • 問題：AI 自動化可能取代大量現有工作，特別是重複性或低技能的工作，這可能導致大規模失業和加劇貧富差距。
   • 考量：需要考慮如何對勞動力進行再培訓，探索新的經濟模式（如普遍基本收入），並確保 AI 的好處能更廣泛地分享。

5. 自主性與決策權 (Autonomy and Decision-Making Power)：

   • 問題：隨著 AI 變得越來越自主，我們是否應該允許 AI 在關鍵領域（如軍事武器、醫療決策）做出獨立決策？這可能引發對人類控制權的擔憂。
   • 考量：需要設定 AI 的自主權限界限，確保人類始終保有最終的決策權，尤其是在涉及生命、倫理和重大社會影響的領域。

6. 安全與惡意使用 (Security and Malicious Use)：

   • 問題：AI 技術可能被用於惡意目的，例如製造更逼真的假訊息 (deepfakes)、開發自主武器、發動更複雜的網路攻擊、或進行大規模監控。
   • 考量：需要加強 AI 系統的安全性，開發對抗惡意使用的技術，並建立國際合作來規範 AI 的軍事和安全應用。

7. 人類價值與尊嚴 (Human Values and Dignity)：

   • 問題：AI 的廣泛應用（例如，情感伴侶機器人、用於監視的 AI）是否會損害人類的尊嚴、人際關係的價值，或使人類過度依賴技術？
   • 考量：需要確保 AI 的設計和使用是為了增強人類能力和福祉，而不是取代或貶低人類的價值。

結論：

AI 的倫理考量是複雜且多面向的。在開發和部署 AI 系統時，必須採取負責任的態度，積極識別和解決潛在的倫理風險，並努力確保 AI 技術的發展能夠造福全人類，而不是加劇社會問題。這需要技術專家、倫理學家、法律專家、政策制定者和公眾之間的持續對話與合作。

---

4. Explain CIDR (Classless Inter-Domain Routing) notation system and illustrate the meaning of 192.168.1.0/24. (10%)

核心觀念： CIDR 是一種 IP 位址表示法，用於更靈活地分配和路由 IP 位址，克服了傳統 IP 位址分級 (Classful) 系統的限制。

詳解：

CIDR (Classless Inter-Domain Routing) 符號系統

CIDR 是一種 IP 位址分配和路由的方法，它取代了傳統的基於類別 (Classful) 的 IP 位址分配方式。傳統方式（Class A, B, C）將 IP 位址劃分為固定大小的網路，導致 IP 位址資源浪費嚴重。CIDR 允許更靈活地劃分網路，將 IP 位址的網路位址 (Network ID) 和主機位址 (Host ID) 之間的劃分點進行任意設定，而不是固定在 8、16 或 24 位。

CIDR 的表示法是在 IP 位址後面加上一個斜線 (/)，然後跟一個數字。這個數字表示 IP 位址中，作為網路位址 (Network Address) 的位元數量。

IP 位址結構：
一個 IPv4 位址由 32 位元組成，通常表示為四個 8 位元的十進位數字（例如 192.168.1.1）。這 32 位元被劃分為網路位址和主機位址兩部分。

• 網路位址 (Network Address)：用於識別一個特定的網路。
• 主機位址 (Host Address)：用於在該網路內識別一個特定的裝置。

CIDR 表示法的意義：

IP 位址 / 位元數

• IP 位址：表示該網路中的一個 IP 位址（通常是網路位址本身，但也可以是網路中的任何一個 IP 位址）。
• / 位元數：表示 IP 位址的前面有多少位元是網路位址 (Network ID)。

剩餘的位元（32 - 位元數）則為主機位址 (Host ID)。

範例說明：192.168.1.0/24

• IP 位址：192.168.1.0
• /24：表示 IP 位址的前 24 位是網路位址。

詳細解析：

1. 二進位表示：

   • 192.168.1.0 的二進位表示是：
     11000000.10101000.00000001.00000000

2. 網路位址 (Network ID)：

   • CIDR 表示法 /24 意味著前 24 位是網路位址。
   • 11000000.10101000.00000001 (前 24 位)
   • 對應的十進位是 192.168.1。
   • 所以，192.168.1.0/24 代表網路位址是 192.168.1.0。

3. 主機位址 (Host ID)：

   • 剩餘的位元是主機位址。總共有 32 位元，減去 24 位網路位址，剩下 $32 - 24 = 8$ 位元作為主機位址。
   • 00000000 (後 8 位)
   • 這 8 位元可以組成 $2^8 = 256$ 種不同的組合。

4. 可用 IP 位址範圍：

   • 主機位址中，全 0 的組合 (00000000) 代表網路位址本身，通常用於識別網路。
   • 主機位址中，全 1 的組合 (11111111) 代表廣播位址 (Broadcast Address)，用於向該網路上的所有裝置發送訊息。
   • 因此，實際可分配給裝置使用的 IP 位址範圍是：
     • 最小 IP (網路位址 + 1)：192.168.1.00000001 (二進位) = 192.168.1.1 (十進位)
     • 最大 IP (廣播位址 - 1)：192.168.1.11111110 (二進位) = 192.168.1.254 (十進位)
   • 所以，192.168.1.0/24 這個 CIDR 符號代表一個網路，其網路位址是 192.168.1.0，廣播位址是 192.168.1.255，並且可以分配給裝置使用的 IP 位址範圍是 192.168.1.1 到 192.168.1.254。這個網路共有 $2^8 - 2 = 254$ 個可用的主機位址。

CIDR 的優勢：

• 彈性劃分：允許創建任意大小的子網路，更有效地利用 IP 位址空間。
• 減少路由表大小：通過將多個連續的 Class C 網路合併成一個更大的 CIDR 區塊（例如 192.168.0.0/22 可以包含 192.168.0.0/24, 192.168.1.0/24, 192.168.2.0/24, 192.168.3.0/24），路由器可以將其視為一個路由條目，從而減小路由表的規模，提高路由效率。

---

**5. Describe the key differences between TCP (Transmission Control Protocol) and UDP (