113 年 國立政治大學資訊管理學系碩士班資管組《計算機概論》

核心觀念

• Waterfall（瀑布模型）：線性、階段式開發。每一階段需完成既定的成果（需求、設計、實作、測試、維護），且在完成前不會進入下一階段。里程碑清楚、變更成本高、客戶介入有限。
• Agile（敏捷開發）：迭代式、增量式開發。以 短衝（Sprint） 為單位交付可運作的軟體，強調客戶與團隊的持續合作、快速回饋與適應變化。文件化較精簡，重視「可運作的軟體」而非完整文件。

解題方法

1. 先確認每個選項描述的特性是否符合 Waterfall 或 Agile 的核心特徵。
2. 逐一比對：
   • 里程碑與階段完成條件 → Waterfall。
   • 客戶高參與度與隨時調整 → Agile。
   • 多元平行設計的需求 → 需要頻繁整合，較適合迭代式（Agile）而非純序列式（Waterfall）。
   • 團隊成員是否需全程投入或可在不同階段切換工作 → Agile 彈性較高，Waterfall 多為專案期間固定分工。
   • 文件與測試的依賴程度 → Agile 偏向輕量文件，測試是持續自動化的一環，但不以「謹慎文件」為主要保證。

選項分析

• A：Waterfall development sets clear milestones in each stage and moves to the next stage only after the goal of the current stage is fulfilled.
  符合瀑布模型的基本流程，正確。

• B：Waterfall development appreciates a high degree of customer involvement so that the project outcome can be adjusted in a timely manner.

此題考察對統一建模語言 (UML) 中不同圖表和概念的理解。

• A) Sequence diagram shows the interaction between objects in a system by modeling messages exchanged between them over time.
  Sequence Diagram 確實是用來展示物件之間在時間軸上的訊息交換，強調訊息的順序。此敘述正確。

• B) Activity diagram shows the workflow of a system by modeling activities, actions, and control flows.
  Activity Diagram 用於表示系統中的業務流程、工作流程或操作流程，展示活動、決策點和控制流。此敘述正確。

• C) Use case diagram shows the functionality of a system by modeling actors, use cases, and their relationships.
  Use Case Diagram 用來描繪系統的功能（Use Cases）以及與系統互動的外部實體（Actors）及其關係，從使用者角度描述系統的功能。此敘述正確。

• **D) Composition represents a "has-a" relationship, while Aggregation represents an "is-part-of" relationship between the aggregated object and the aggr

此題考察對 SQL 和 NoSQL 資料庫的理解，包含其結構、設計理念、應用場景及權衡。

• A) SQL is based on a structured query language with a fixed schema, while NoSQL is schema-less and can store unstructured data.
  SQL (Structured Query Language) 資料庫（即關聯式資料庫）的核心特徵是使用結構化的資料模型，具有預定義的固定綱要 (schema)。NoSQL (Not Only SQL) 資料庫則種類繁多，其中許多是無綱要 (schema-less) 或具有彈性綱要，並且能夠儲存非結構化或半結構化資料。此敘述正確。

• B) NoSQL is designed to handle distributed data stores, making them a common choice for cloud storage and big data applications.
  許多 NoSQL 資料庫（如 Cassandra, MongoDB 的分片功能）在設計上就考慮了分散式架構，易於水平擴展，非常適合處理 PB 級的資料，因此成為雲端儲存和巨量資料應用的首選。此敘述正確。

• C) Database normalization (i.e. 1NF, 2NF, 3NF, and 4NF) typically does not apply to NoSQL databases.
  資料庫正規化（Normalization）是為了減少資料冗餘和提高資料完整性而設計的一系列規則，主要適用於結構化資料模型。

核心觀念
本題測試對 網路協定的功能與所在層次 的理解。須掌握的概念包括：

協定	功能說明	所屬層級 (OSI / TCP‑IP)
OSPF (Open Shortest Path First)	Link‑state 路由演算法，使用「成本」(cost) 衡量連結權重，透過 Dijkstra 計算最短路徑。	網路層 (Network)
ARP (Address Resolution Protocol)	依據目的 IP 位址在同一乙太網路上查找對應的 MAC 位址，屬於 資料連結層 (Link Layer)；在 TCP‑IP 四層模型中歸於 網路介面層。	資料連結層 / 網路介面層
ICMP (Internet Control Message Protocol)	用於傳送錯誤訊息、網路診斷 (eg. ping、Traceroute)；不參與「會話」或「傳輸」的建立與管理。	網路層 (Network)
HTTP/2	在單一 TCP 連線上實現 多路復用 (multiplexing) 與 頭部壓縮，減少連線數量與延遲。	應用層 (Application)
SSL/TLS	為應用層協定提供端點到端點的加密與驗證，位於 傳輸層之上（常被視為會話/表示層）。	傳輸層之上（Session / Presentation）

解題方法

1. 判斷每個敘述的功能描述是否正確。
2. 判斷所在層次是否與標準模型相符。
3. 只要有任一要素錯誤，即視為該選項錯誤。
4. 逐一比對五個選項的組合，找出與「唯一正確」敘述相符的答案。

選項分析

選項	內容	正誤判斷與說明
A	*OSPF 是一種路由協定，使用路徑成本指標計算 IP 網路內資料封包的最短路徑。

核心觀念
本題測驗對資安常見概念的正確認知，涉及以下定義：

1. Rootkit：惡意軟體或工具，目的在於隱蔽自身或其他惡意程式，繞過系統安全機制，常用於持續性入侵。
2. Zero‑Day Attack：利用「尚未有可用修補程式」的漏洞發動攻擊，漏洞可能已被公開披露但仍未有修補程式，或尚未被廠商或安全社群發現。
3. Post‑Quantum Cryptography (PQC)：在傳統（古典）計算框架下設計的密碼演算法，抵抗量子電腦對現有演算法（如 RSA、ECC）的破解能力，而不是利用量子力學本身。
4. Social Engineering：透過心理操控或社交手段，誘使目標泄漏機密資訊或執行不當操作的攻擊方式。
5. Two‑Factor Authentication (2FA)：結合「知識因素」＋「所有因素」或「所有因素」＋「固有因素」的雙重驗證機制，主要加強認證安全，常被描述為能減少「Man‑in‑the‑Middle (MITM)」攻擊的成功率。

---

解題方法
此為多選題，檢驗每個敘述是否符合上述正式定義。解題步驟：

1. 依序閱讀每個選項，對照資安教科書或資訊安全標準（如 NIST、ISO/IEC 27001）中對相關概念的說明。
2. 判斷敘述的關鍵詞是否與正式定義相符或出現概念混淆。
3. 只要敘述中任何一部分與正確定義不符，即判為錯誤。
4. 最後根據正確選項組合對照題目提供的選項組合，選出唯一符合的答案。

---

選項分析

項目	敘述	正確性	解析
A	A rootkit is a set of specialized tools for system administrators to manage and monitor system security.	❌	Rootkit 是用於隱匿惡意行為、繞過或破壞安全機制的工具，而非系統管理員的合法管理工具。

此題考察對 OSI 模型及其與 TCP/IP 模型比較的理解。

• A) IEEE 802 standards (like 802.3 (Ethernet) and 802.11 (Wi-Fi)) operate at the Network layer.
  IEEE 802 標準，如 802.3 (Ethernet) 和 802.11 (Wi-Fi)，定義了區域網路（LAN）的物理層 (Physical Layer) 和資料鏈結層 (Data Link Layer) 的規範。它們工作在 OSI 模型的低兩層，而非網路層 (Network Layer)。此敘述錯誤。

• B) TCP is a connection-oriented transmission protocol operating in the Session layer.
  TCP (Transmission Control Protocol) 是一個面向連接的傳輸協定，提供可靠的資料傳輸服務。它工作在 OSI 模型的傳輸層 (Transport Layer)，而非會話層 (Session Layer)。此敘述錯誤。

• C) Protocols such as HTTP, FTP, and SMTP operate in the Application layer.
  HTTP (Hypertext Transfer Protocol)、FTP (File Transfer Protocol) 和 SMTP (Simple Mail Transfer Protocol) 都是常見的應用層協定，用於支援各種網路應用程式的功能。此敘述正確。

• D) TCP/IP is a simplified version of OSI by removing three layers from the latter model.
  OSI 模型有七層：Physical, Data Link, Network, Transport, Session, Presentation, Application。

此題考察對雲端運算服務模型 (IaaS, PaaS, SaaS) 的理解，包括它們的定義、特點、使用方式和整合效益。

• A) IaaS is the original form of cloud computing and is offered by almost all major cloud service providers nowadays.
  IaaS (Infrastructure as a Service) 是一種雲端服務模型，提供虛擬化的計算資源，如伺服器、儲存和網路。雖然 IaaS 是雲端運算的重要組成部分，但它並非「原始形式」。雲端運算的發展是一個漸進的過程，早期可能更多是 SaaS 或 PaaS 的雛形。而且，雖然 IaaS 是主流，但並非「所有」主要雲端服務提供商都只提供 IaaS。此敘述不夠準確，甚至可能錯誤。

• B) SaaS provides a cloud-hosted development environment for running and managing application software in a centralized location.
  SaaS (Software as a Service) 提供的是「軟體應用程式」本身，使用者透過網路存取，通常是通過瀏覽器。它不是一個開發環境。提供雲端開發環境的是 PaaS (Platform as a Service)。此敘述錯誤。

• C) Users often interact with IaaS through application programming interfaces (APIs), and access PaaS and SaaS through graphical user interfaces (GUIs).

  • IaaS 的管理和自動化通常透過 API 進行，例如 AWS EC2 API, Azure Resource Manager API。雖然也有 GUI 管理工具，但 API 是實現大規模自動化和整合的關鍵。
  • PaaS 通常提供一個開發和部署平台的環境，用戶可以透過 API 或 GUI 來管理和部署應用程式。
  • SaaS 的使用者通常是終端用戶，他們主要透過 GUI（如網頁介面）來使用軟體。
    此敘述將 IaaS 與 API 關聯，PaaS 和 SaaS 與 GUI 關聯。

核心觀念
本題考查開源授權條款的核心權利與限制，必須清楚了解四大常見授權的主要特點：

授權	主要條款	是否允許商業使用	是否必須隨發行公開原始碼	是否授予專利權	是否包含商標使用授權
GPL（v2/v3）	Copyleft（傳染性），保證使用者取得完整源碼	允許（但必須同樣以 GPL 釋出）	必須（發行時必須提供或提供取得方式）	v3 含專利授予，v2 無明文授予	不授予
MIT	簡短許可，只要求保留版權聲明與授權條款	允許（無限制）	不必（除非自行提供）	不授予（無專利條款）	不授予
Apache 2.0	包含專利授予條款，明確禁止使用貢獻者的商標	允許（同 MIT）	不必（除非自行提供）	授予（貢獻者授予使用者全球、永久、免版稅的專利許可）	禁止（未授予商標使用權）

解題方法
依據上述條款逐一驗證每個選項的敘述是否與授權條件相符，採用逐條比對的方式：

1. 判斷敘述是否完整描述該授權的必備條件或限制。
2. 若敘述涉及「必須」或「允許」的關鍵字，務必對照授權條文的規定。
3. 只要有任何與官方條款不符的部份，即視為錯誤。

選項分析

選項	敘述內容	正確與否	判斷依據
A	If the software uses GPL‑licensed code, it must disclose source code when it is distributed.	正確	GPL 的 copyleft 要求，發行衍生作品時必須同時提供完整的源碼（或提供取得源碼的方式）。

此題考察對 CAP 定理的理解，包括其組成部分、含義以及在分散式資料庫中的應用。

• A) "C" means "Consistency", which guarantees that the nodes will have the same copies of a replicated data item in various transactions.
  CAP 定理中的 C 指的是強一致性 (Consistency)，它保證所有節點在任何時刻都能讀取到最新的寫入資料。這意味著，在任何給定的時間點，所有節點上的資料副本都是相同的。此敘述正確。

• B) "A" means "Atomicity", which guarantees that each transaction is a single unit that either succeeds completely or fails completely.
  CAP 定理中的 A 指的是可用性 (Availability)，它保證系統中的每個請求都能在有限的時間內得到響應。而 Atomicity (原子性) 是 ACID 四個屬性之一，它保證一個事務（transaction）是不可分割的執行單元，要麼全部成功，要麼全部失敗。此敘述錯誤。

• C) "P" means "Partition tolerance", which guarantees that the system can continue operating even if the network fails and the nodes form disconnected partitions.
  CAP 定理中的 P 指的是分割容錯性 (Partition Tolerance)，它保證系統在網路發生分割（partition）時，仍然能夠繼續運行。即使節點之間無法通訊，系統的某些部分（或全部）仍然可用。此敘述正確。

• D) Distributed databases like MongoDB and Cassandra tend to prioritize "C" and "P" at the cost of sacrificing "A".
  CAP 定理指出，在分散式系統中，一致性 (C)、可用性 (A) 和分割容錯性 (P) 三者最多只能同時滿足兩個。
  MongoDB 和 Cassandra 都是設計來處理大規模分散式環境的，因此它們必須具備分割容錯性 (P)。
  在 P 存在的情況下，系統必須在 C 和 A 之間做出選擇。
  Cassandra 預設是 AP 系統（可用性和分割容錯性），但也提供不同的一致性級別，可以權衡到 C。
  MongoDB 在分片（sharded）部署時，預設是 AP 系統，但其讀取操作可以配置為讀取 primary，以獲得更強的一致性（接近 CP）。

此題考察對 4G 和 5G 技術的優缺點及其應用的理解。

• A) 5G enables applications such as VR, AR, and IoT due to its high data rates and low latency.
  5G 的三大特點是增強行動寬頻 (eMBB)、海量物聯網 (mMTC) 和超可靠低延遲通訊 (URLLC)。高數據速率 (high data rates) 和低延遲 (low latency) 是 5G 的關鍵優勢，這使得 VR (虛擬實境)、AR (擴增實境) 和大規模物聯網 (IoT) 等對網路要求極高的應用得以實現。此敘述正確。

• B) 5G deployment requires a denser network of cells than 4G, which can lead to higher infrastructure costs and more complex network maintenance.
  5G，特別是使用毫米波 (mmWave) 頻段時，訊號傳輸距離較短，穿透性較差。因此，為了提供廣泛的覆蓋和穩定的連接，需要部署更多、更密集的基地台（cell），這會顯著增加基礎設施成本和網路維護的複雜度。此敘述正確。

• C) 4G networks tend to be more energy-efficient than 5G networks because the latter's higher data rates and lower latency need more power.

此題要求解釋三個網路診斷命令的功能，並說明其使用情境。

1. ifconfig (或 ipconfig 在 Windows)

• 功能 (Functionality): ifconfig (Interface Configuration) 命令用於顯示和設定網路介面的 IP 位址、子網路遮罩、預設閘道、MAC 位址以及啟用/停用網路介面等資訊。在 Linux/macOS 系統中，ip addr 是較新的替代命令，功能類似。
• 使用情境 (Situation):
  • 確認本機 IP 位址： 當你需要知道電腦的 IP 位址、子網路遮罩等網路配置資訊時，尤其是在需要靜態 IP 設定或進行網路連線疑難排解時。
  • 檢查網路介面狀態： 查看網路介面是否啟用 (up/down)，以及其 MAC 位址。
  • 臨時修改 IP 位址： 在測試環境或特定設定下，可能需要臨時更改本機的 IP 位址。

2. nslookup (Name Server Lookup)

• 功能 (Functionality): nslookup 命令用於查詢 DNS (Domain Name System) 伺服器，以將網域名稱（如 www.google.com）解析為 IP 位址，或反之（將 IP 位址解析為網域名稱）。它還可以查詢 DNS 記錄的各種資訊，如 A 記錄 (IPv4 地址)、AAAA 記錄 (IPv6 地址)、MX 記錄 (郵件伺服器)、NS 記錄 (名稱伺服器) 等。
• 使用情境 (Situation):
  • 確認網域名稱解析是否正常： 當你無法訪問某個網站時，可以用 nslookup 檢查該網域名稱是否能正確解析到 IP 位址。
  • 查找特定網域名稱的 IP 位址： 需要知道某個服務（如網站、郵件伺服器）的 IP 位址時。

此題考察機器學習中「資料不平衡」(Data Imbalance) 的問題，包括其造成的影響、模型表現的指標，以及解決方法。

資料不平衡是指在分類問題中，不同類別的樣本數量差異巨大，導致模型在訓練時偏向於數量較多的類別（多數類），而對數量較少的類別（少數類）的預測能力較差。

1. What problems would data imbalance cause in supervised machine learning?

資料不平衡會導致以下問題：

• 模型偏見 (Model Bias): 學習演算法在訓練時，會傾向於最小化整體誤差，而多數類別的龐大樣本量會「淹沒」少數類別的誤差。這使得模型學習到大多數樣本的特徵，而忽略了少數樣本的特徵，導致模型對少數類別的預測能力極差。
• 評估指標誤導 (Misleading Evaluation Metrics): 傳統的分類評估指標，如準確率 (Accuracy)，在資料不平衡的場景下會產生誤導。例如，如果一個二分類問題中，99% 的樣本屬於類別 A，1% 屬於類別 B。一個將所有樣本都預測為類別 A 的模型，其準確率也能達到 99%，但它完全無法識別出類別 B，這是一個非常糟糕的模型。
• 預測結果不準確 (Inaccurate Predictions): 尤其是在對少數類別的預測至關重要時（例如，疾病診斷、詐欺檢測、故障預警），模型由於缺乏對少數類別的足夠學習，會做出大量錯誤的預測，導致嚴重的後果。

2. What characteristics of a trained model indicate possibly imbalanced training data?

以下模型表現特徵可能表明訓練資料存在不平衡：

• 極高的準確率 (Very High Accuracy) 但混淆矩陣 (Confusion Matrix) 顯示少數類別的預測極差： 如前所述，一個模型可能因為預測所有樣本為多數類而獲得很高的準確率，但其混淆矩陣會顯示少數類別的召回率 (Recall) 或精確率 (Precision) 非常低。
• 低召回率 (Low Recall) / 低敏感度 (Low Sensitivity) / 低真陽性率 (Low True Positive Rate) 對於少數類別： 召回率衡量的是模型能夠正確識別出所有真實少數類別樣本的比例。如果少數類別的召回率很低，說明模型錯過了大量真實的少數類別樣本（假陰性多）。
• 低精確率 (Low Precision) / 低陽性預測值 (Low Positive Predictive Value) 對於少數類別： 精確率衡量的是模型預測為少數類別的樣本中，有多少是真正屬於少數類別的。如果少數類別的精確率低，說明模型將很多多數類別的樣本誤判為少數類別（假陽性多）。
• F1 分數 (F1-Score) 非常低（尤其是針對少數類別的 F1 分數）： F1 分數是精確率和召回率的調和平均數，它能更全面地反映模型的性能。如果少數類別的 F1 分數很低，說明模型在少數類別的預測上表現不佳。
• ROC 曲線 (Receiver Operating Characteristic Curve) 下的面積 (AUC - Area Under the Curve) 可能很高，但 Precision-Recall 曲線下的面積 (AUC-PR) 很低： ROC 曲線在類別分佈極度不平衡時可能表現良好，但 Precision-Recall 曲線更能反映模型在處理不平衡資料時的性能。

3. How do you mitigate the problems caused by imbalanced data?

緩解資料不平衡問題的方法主要有以下幾類：

• 資料層面的方法 (Data-Level Approaches):
  • 過採樣 (Oversampling):
    • 隨機過採樣 (Random Oversampling): 隨機複製少數類別的樣本，直到其數量與多數類別相當。缺點是可能導致模型過擬合（overfitting）。

此題考察 Java 中集合框架 (Collections Framework) 的使用，特別是 List 介面的不同實現類別以及 Map 結構的差異。

1. List 介面的不同實現類別的使用情境：

List 介面代表一個有序的元素集合，允許重複元素，並提供按索引訪問元素的方法。主要實現類別有 ArrayList, LinkedList, 和 Vector。

• ArrayList:

  • 內部結構： 基於動態陣列 (dynamic array) 實現。
  • 效能特點：
    • 存取 (Access)： 依索引存取元素非常快，時間複雜度為 $O(1)$，因為可以直接計算記憶體位址。
    • 插入/刪除 (Insertion/Deletion)： 在列表的中間或開頭插入或刪除元素較慢，時間複雜度為 $O(n)$，因為需要移動後續元素來填補或騰出空間。在列表的末尾添加元素通常較快（平均 $O(1)$，但可能觸發陣列擴容）。
  • 使用情境：
    • 當需要頻繁地依索引存取元素時。
    • 當列表的大小相對穩定，或主要在末尾進行添加/刪除操作時。
    • 需要一個執行緒不安全但效能較高的 List 實現時。

• LinkedList:

  • 內部結構： 基於雙向鏈結串列 (doubly linked list) 實現。每個節點包含資料、前一個節點的指標和下一個節點的指標。
  • 效能特點：
    • 存取 (Access)： 依索引存取元素較慢，時間複雜度為 $O(n)$，因為需要從頭或尾部開始遍歷。
    • 插入/刪除 (Insertion/Deletion)： 在列表的開頭、末尾或任意位置（如果已知該節點）進行插入和刪除操作非常快，時間複雜度為 $O(1)$，因為只需要修改前後節點的指標。
  • 使用情境：
    • 當需要頻繁地在列表的開頭或末尾進行添加/刪除操作時（例如，作為佇列 Queue 或堆疊 Stack 使用）。
    • 當需要頻繁地在列表的中間進行插入/刪除操作，並且能夠快速定位到目標位置時。
    • 需要一個執行緒不安全但對插入/刪除操作敏感的 List 實現時。

• Vector:

  • 內部結構： 與 ArrayList 類似，也是基於動態陣列實現。
  • 效能特點：
    • 執行緒安全 (Thread-Safe)： Vector 的所有方法都進行了同步 (synchronized)，這使得它在多執行緒環境下是安全的，但同時也帶來了效能損耗（同步開銷）。
    • 陣列擴容： 預設情況下，當容量不足時，Vector 會將其容量增加一倍。ArrayList 預設是擴容 50%。
  • 使用情境：
    • 當需要一個執行緒安全的 List 實現時。
    • 在需要頻繁依索引存取元素，且同時需要執行緒安全時。
    • 注意： 在現代 Java 開發中，除非有明確的執行緒安全需求，否則通常推薦使用 ArrayList，並通過 Collections.synchronizedList() 方法來獲得執行緒安全。Vector 被認為是較舊的類別，效能相對較差。

總結：

• 頻繁存取 (index-based access) → ArrayList
• 頻繁插入/刪除 (especially at ends) → LinkedList
• 需要執行緒安全 (Thread-safe) → Vector (或 Collections.synchronizedList(new ArrayList<>()))

2. HashMap 與 TreeMap 的差異與選擇：

此題要求解釋「機器學習偏差」(Machine Learning Bias) 的概念。

機器學習偏差 (Machine Learning Bias)

機器學習偏差是指機器學習模型在進行預測時，其結果與某些敏感特徵（如性別、種族、年齡、宗教信仰、社會經濟地位等）之間產生了不應有的、不公平的關聯。即使這些敏感特徵在訓練資料中與目標變數（需要預測的結果）沒有真實的因果關係，或者這種關聯應該被忽略，模型仍然會學習到並利用這種關聯來做出預測。

偏差的來源：

1. 訓練資料中的偏差 (Bias in Training Data):

   • 歷史偏差 (Historical Bias): 訓練資料可能反映了現實世界中存在的歷史性或社會性的不公平現象。例如，歷史上的招聘資料可能顯示某些職業主要由男性擔任，模型學習到這種模式後，在招聘預測時可能偏向男性。
   • 測量偏差 (Measurement Bias): 資料收集或標記過程中的偏差。例如，對某些群體的行為進行測量的方式可能與對其他群體不同。
   • 抽樣偏差 (Sampling Bias): 訓練資料的採樣方式未能代表真實世界的總體分佈，導致某些群體被過度或不足地代表。
   • 標籤偏差 (Label Bias): 標記資料的人可能無意中將其自身的偏見帶入到標籤中。

2. 演算法本身的偏差 (Algorithmic Bias):

   • 某些演算法的設計或參數設置可能會無意中放大訓練資料中的偏差。例如，過於簡化的模型可能無法捕捉複雜的非線性關係，而被迫依賴於一些簡化的、帶有偏差的關聯。

此題要求列舉監督式機器學習中偏差的兩個典型來源/原因。

監督式機器學習中的偏差 (Bias) 指的是模型在預測時，系統性地、不公平地偏向某些群體或特徵。其來源多樣，以下是兩個典型的來源：

1. 訓練資料中的歷史偏差 (Historical Bias in Training Data):

• 說明： 機器學習模型從歷史資料中學習模式。如果歷史資料反映了社會中長期存在的、不公平的歧視性實踐或價值觀，那麼模型就會學習並複製這些偏差。
• 例子：
  • 招聘： 如果一個公司過去幾十年招聘的工程師絕大多數是男性，那麼基於這些歷史數據訓練的招聘模型，可能會偏向於男性候選人，即使女性候選人同樣具備資格。
  • 犯罪預測： 如果歷史數據顯示某些種族或社群的犯罪率較高（可能由於社會經濟因素、執法偏差等原因），模型可能會將這些群體標記為高風險，導致不公平的刑事司法判決。

2. 測量偏差或標籤偏差 (Measurement Bias or Label Bias):

• 說明： 資料的收集、測量方式，或對資料進行標記（分類）的過程，可能因為主觀判斷、標準不一或工具限制，而引入系統性的偏差。

此題探討在機器學習中，移除敏感特徵（如性別）是否能保證模型的公平性。

Will this method work?
No, this method will likely not work to guarantee a fair model.

Why or why not?

儘管移除顯性的敏感特徵（如「gender」欄位）看起來是一個簡單直接的方法來消除模型對該特徵的直接依賴，但它通常不足以解決機器學習中的偏差問題。原因如下：

1. 代理特徵 (Proxy Features / Spurious Correlations):

   • 敏感特徵（如性別、種族）通常與其他非敏感特徵（如教育背景、居住地區、消費習慣、姓名等）之間存在高度的相關性。這些非敏感特徵可能無意中成為敏感特徵的「代理」(proxies)。
   • 即使移除了「gender」欄位，模型仍然可以透過學習這些與性別高度相關的特徵組合，間接推斷出性別資訊，並以此來影響預測結果。例如，某些名字（如 John vs. Mary）可能與性別高度相關，或者某些職業偏好、教育路徑的數據可能與性別相關。

2. 資料中的潛在偏差 (Underlying Bias in the Data):

   • 數據本身可能已經內嵌了與敏感特徵相關的歷史或社會偏差。即使移除該特徵，模型仍然可能學習到這些潛在的、與敏感特徵相關的模式，因為這些模式影響了其他特徵的取值和目標變數的標籤。

此題要求撰寫 SQL 查詢語句，以統計不同國家客戶的數量，並按數量降序排列。

SQL 語句：

SELECT
    Country,
    COUNT(CustomerID) AS CustomerCount
FROM
    Customers
GROUP BY
    Country
ORDER BY
    CustomerCount DESC;

解釋：

1. SELECT Country, COUNT(CustomerID) AS CustomerCount:
   • SELECT Country: 選取要顯示的欄位，即客戶所在的國家。
   • COUNT(CustomerID): 統計每個分組（國家）中 CustomerID 的數量。CustomerID 通常是客戶表的主鍵，用於唯一識別客戶，因此統計 CustomerID 的數量等同於統計客戶的數量。
   • AS CustomerCount: 為統計結果（客戶數量）指定一個別名 CustomerCount，以便在輸出中清晰顯示。

核心觀念

本題考查 SQL 的：

• JOIN：依照共同欄位 CustomerID 連結 Customers 與 Orders。
• 聚合函數 COUNT()：計算每位客戶的訂單數量。
• GROUP BY：按照客戶分組，使每位客戶產生一筆統計結果。
• LEFT JOIN：即使客戶尚未建立任何訂單，也能列出該客戶，訂單數顯示為 0。

CustomerID 是兩張表的關聯欄位，CustomerName 來自 Customers，訂單數則由 Orders 中符合相同 CustomerID 的資料筆數決定。

解題方法

先以 CustomerID 連結兩張表：

$$Customers.CustomerID = Orders.CustomerID$$

接著依照客戶分組，再計算每組的 OrderID 數量。完整 SQL 如下：

SELECT
    c.CustomerName AS Name,
    COUNT(o.OrderID) AS Count
FROM Customers AS c
LEFT JOIN Orders AS o
    ON c.CustomerID = o.CustomerID
GROUP BY
    c.CustomerID,
    c.CustomerName;

查詢流程

1. FROM Customers AS c
   以客戶表作為主要資料來源。

2. LEFT JOIN Orders AS o
   透過 CustomerID 找出每位客戶的訂單。

3. COUNT(o.OrderID)
   計算每位客戶的訂單編號數量。

4. GROUP BY c.CustomerID, c.CustomerName
   將同一位客戶的資料集中，產生一筆統計結果。

GROUP BY 同時放入 CustomerID 與 CustomerName，可避免不同客戶恰好使用相同姓名時被錯誤合併。

為何使用 COUNT(o.OrderID)

使用 LEFT JOIN 時，沒有訂單的客戶仍會保留一列，但該列的 o.OrderID 為 NULL。

• COUNT(o.OrderID) 不會計算 NULL，因此結果為 0。
• COUNT(*) 會計算由 LEFT JOIN 產生的那一列，可能把無訂單客戶錯誤計為 1。

此題要求撰寫 SQL 查詢語句，以統計不同國家客戶的數量，並按數量降序排列。

SQL 語句：

SELECT
    Country,
    COUNT(CustomerID) AS CustomerCount
FROM
    Customers
GROUP BY
    Country
ORDER BY
    CustomerCount DESC;

解釋：

1. SELECT Country, COUNT(CustomerID) AS CustomerCount:
   • SELECT Country: 選取要顯示的欄位，即客戶所在的國家。
   • COUNT(CustomerID): 統計每個分組（國家）中 CustomerID 的數量。CustomerID 通常是客戶表的主鍵，用於唯一識別客戶，因此統計 CustomerID 的數量等同於統計客戶的數量。
   • AS CustomerCount: 為統計結果（客戶數量）指定一個別名 CustomerCount，以便在輸出中清晰顯示。

核心觀念

本題考查 SQL 的：

• JOIN：依照共同欄位 CustomerID 連結 Customers 與 Orders。
• 聚合函數 COUNT()：計算每位客戶的訂單數量。
• GROUP BY：按照客戶分組，使每位客戶產生一筆統計結果。
• LEFT JOIN：即使客戶尚未建立任何訂單，也能列出該客戶，訂單數顯示為 0。

CustomerID 是兩張表的關聯欄位，CustomerName 來自 Customers，訂單數則由 Orders 中符合相同 CustomerID 的資料筆數決定。

解題方法

先以 CustomerID 連結兩張表：

$$Customers.CustomerID = Orders.CustomerID$$

接著依照客戶分組，再計算每組的 OrderID 數量。完整 SQL 如下：

SELECT
    c.CustomerName AS Name,
    COUNT(o.OrderID) AS Count
FROM Customers AS c
LEFT JOIN Orders AS o
    ON c.CustomerID = o.CustomerID
GROUP BY
    c.CustomerID,
    c.CustomerName;

查詢流程

1. FROM Customers AS c
   以客戶表作為主要資料來源。

2. LEFT JOIN Orders AS o
   透過 CustomerID 找出每位客戶的訂單。

3. COUNT(o.OrderID)
   計算每位客戶的訂單編號數量。

4. GROUP BY c.CustomerID, c.CustomerName
   將同一位客戶的資料集中，產生一筆統計結果。

GROUP BY 同時放入 CustomerID 與 CustomerName，可避免不同客戶恰好使用相同姓名時被錯誤合併。

為何使用 COUNT(o.OrderID)

使用 LEFT JOIN 時，沒有訂單的客戶仍會保留一列，但該列的 o.OrderID 為 NULL。

• COUNT(o.OrderID) 不會計算 NULL，因此結果為 0。
• COUNT(*) 會計算由 LEFT JOIN 產生的那一列，可能把無訂單客戶錯誤計為 1。

此題要求設計一個演算法，利用一個布林函數 $f(y)$ 來估計一個未知實數 $x$（其中 $1 \le x < \infty$），並要求估計的區間 $[low, high]$ 的長度不大於 $\epsilon$，且演算法呼叫 $f$ 的次數為 $O(\lg \frac{1}{\epsilon} + \lg x)$。

理解問題：

• 我們有一個黑箱函數 $f(y)$，它能告訴我們 $x \le y$ 是否為真。這是一個單調函數：當 $y$ 增加時，$f(y)$ 的值從 false 變為 true，且一旦變為 true，對於更大的 $y$ 值，它將保持為 true。
• 我們的目標是找到一個區間 $[low, high]$，使得 $low \le x \le high$，且 $high - low \le \epsilon$。
• 演算法的效率體現在呼叫 $f$ 的次數上。

演算法設計：

這個問題本質上是在一個無限的區間 $[1, \infty)$ 中尋找一個值 $x$，我們知道 $f(y)$ 在 $x$ 處會從 false 變為 true。這很像是在一個排序列表中尋找元素，但列表是無限的。

我們可以分兩步來設計演算法：

1. 尋找一個包含 $x$ 的初始區間 $[1, R]$。
2. 在該區間內進行精確搜尋，直到區間長度小於 $\epsilon$。

步驟 1：尋找初始區間 $[1, R]$

我們可以採用指數級增長的方式來尋找一個足夠大的 $R$，使得 $f(R)$ 為 true。

• 從 $y=1$ 開始。
• 如果 $f(1)$ 是 true，那麼 $x \le 1$。由於題目給定 $1 \le x$，這意味著 $x=1$。此時區間為 $[1, 1]$，長度為 0，滿足 $\epsilon$ 要求。
• 如果 $f(1)$ 是 false，嘗試 $y=2$。
• 如果 $f(2)$ 是 false，嘗試 $y=4$。
• 如果 $f(4)$ 是 false，嘗試 $y=8$。
• 一般地，我們嘗試 $y = 2^k$。我們不斷增加 $k$，直到找到一個 $k$ 使得 $f(2^k)$ 為 true。
• 設 $k_0$ 是第一個使得 $f(2^{k_0})$ 為 true 的整數。
• 那麼，我們就知道 $x$ 滿足 $2^{k_0-1} < x \le 2^{k_0}$（因為 $f(2^{k_0-1})$ 必須是 false）。
• 此時，我們得到了一個初始區間 $[2^{k_0-1}, 2^{k_0}]$，其長度為 $2^{k_0} - 2^{k_0-1} = 2^{k_0-1}$。

步驟 2：在初始區間內進行精確搜尋

現在我們有一個區間 $[L, R]$（其中 $L=2^{k_0-1}$，$R=2^{k_0}$），我們知道 $f(L)$ 是 false 且 $f(R)$ 是 true。我們需要在這個區間內找到 $low$ 和 $high$，使得 $low \le x \le high$ 且 $high - low \le \epsilon$。
這是一個標準的二分搜尋 (Binary Search) 問題。

• 二分搜尋過程：
  1. 設定 $low = L$，$high = R$。
  2. 當 $high - low > \epsilon$ 時，執行以下操作：
     a. 計算中點 $mid = low + (high - low) / 2$。
     b. 呼叫函數 $f(mid)$：
     * 如果 $f(mid)$ 為 true，表示 $x \le mid$。那麼 $x$ 可能在 $[low, mid]$ 這個區間內。我們更新 $high = mid$。
     * 如果 $f(mid)$ 為 false，表示 $x > mid$。那麼 $x$ 可能在 $[mid, high]$ 這個區間內。我們更新 $low = mid$。
  3. 迴圈結束時，$high - low \le \epsilon$，並且 $low \le x \le high$。

演算法總結：

1. 尋找上限 $R$：

   • 令 $y = 1$。
   • 當 $f(y)$ 為 false 時，將 $y$ 乘以 2 (即 $y = y \times 2$)。
   • 當 $f(y)$ 為 true 時，令 $R = y$，並令 $L = y / 2$。
   • （特例：如果 $f(1)$ 為 true，則 $x=1$，$low=1, high=1$，結束。）

2. 二分搜尋精煉區間：

   • 設定 $low = L$, $high = R$。
   • 當 $high - low > \epsilon$ 時：
     • $mid = low + (high - low) / 2$
     • 如果 $f(mid)$ 為 true，則 $high = mid$。
     • 否則，$low = mid$。
   • 返回 $low$ 和 $high$。

演算法呼叫 $f$ 次數的分析：

我們需要分析演算法在兩個階段呼叫 $f$ 的總次數。

階段 1：尋找初始區間 $[L, R]$

• 我們嘗試 $y=1, 2, 4, 8, \dots, 2^k$。
• 假設 $x$ 大約是 $X$（即 $1 \le x < \infty$，我們設一個上限 $X$ 來分析）。
• 我們需要找到最小的 $k_0$ 使得 $f(2^{k_0})$ 為 true，且 $2^{k_0} \ge x$。
• 這意味著 $2^{k_0-1} < x \le 2^{k_0}$。
• 我們嘗試的 $y$ 值是 $1, 2, 4, \dots, 2^{k_0}$。
• 我們呼叫 $f$ 的次數是 $k_0 + 1$。
• 由於 $2^{k_0-1} < x$，我們可以推斷 $k_0 - 1 < \log_2 x$，所以 $k_0 < \log_2 x + 1$。
• 因此，階段 1 呼叫 $f$ 的次數大約是 $O(\log x)$。

階段 2：二分搜尋精煉區間

• 我們有一個初始區間 $[L, R]$，其中 $L \approx x/2$ 且 $R \approx x$。區間長度為 $R-L \approx x/2$。
• 我們需要將區間長度縮小到 $\epsilon$。
• 每次二分搜尋，區間長度減半。
• 假設我們需要 $N$ 次迭代才能使區間長度小於等於 $\epsilon$。
• 初始區間長度為 $L_{init} = R - L \approx x/2$。
• 經過 $N$ 次迭代後，區間長度為 $L_{init} / 2^N \le \epsilon$。
• 所以，$2^N \ge L_{init} / \epsilon \approx (x/2) / \epsilon$。
• 取對數：$N \ge \log_2(L_{init} / \epsilon) = \log_2 L_{init} - \log_2 \epsilon$。
• $N \approx \log_2(x/2) - \log_2 \epsilon = \log_2 x - 1 - \log_2 \epsilon$。
• 每次迭代都呼叫一次 $f$。
• 因此，階段 2 呼叫 $f$ 的次數大約是 $O(\log x - \log \epsilon) = O(\log x + \log \frac{1}{\epsilon})$。

總呼叫次數：

總的呼叫次數是階段 1 的次數加上階段 2 的次數。
總次數 $\approx O(\log x) + O(\log x + \log \frac{1}{\epsilon}) = O(\log x + \log \frac{1}{\epsilon})$。

嚴謹證明 $\lg$ 的使用：
題目要求的是 $O(\lg \frac{1}{\epsilon} + \lg x)$，其中 $\lg$ 通常表示以 2 為底的對數。

階段 1：尋找初始區間

• 我們從 $y=1$ 開始，每次乘以 2，直到 $f(y)$ 為 true。
• 設 $k$ 是第一次使得 $f(2^k)$ 為 true 的整數。
• 那麼 $x \le 2^k$。
• 並且 $f(2^{k-1})$ 為 false，所以 $x > 2^{k-1}$。
• 我們呼叫了 $f$ $k+1$ 次（從 $f(1), f(2), \dots, f(2^k)$）。
• 因為 $x > 2^{k-1}$，所以 $k-1 < \log_2 x$，即 $k < \log_2 x + 1$。
• 所以階段 1 的呼叫次數是 $O(\log_2 x)$。