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

此題考驗對 Hamming distance 及 error correction 的理解。Hamming distance 用於衡量兩個字串之間的差異，在 error correction 中，它能幫助我們判斷接收到的資料最接近哪個預設的碼字。

首先，我們需要計算接收到的碼字 010100 與表中各個 Symbol 的 Hamming distance。Hamming distance 是兩個等長字串之間，對應位置上不同字元的個數。

接收碼字：010100

Symbol D 的碼字：011100
計算 Hamming distance(010100, 011100):

• 位置 0: 0 vs 0 (相同)
• 位置 1: 1 vs 1 (相同)
• 位置 2: 0 vs 1 (不同)
• 位置 3: 1 vs 1 (相同)
• 位置 4: 0 vs 0 (相同)
• 位置 5: 0 vs 0 (相同)
  Hamming distance = 1

此題在考驗對網路傳輸速率、影像解析度、色彩深度、幀率與網路順暢度之間的關係的理解。

首先，計算傳輸 8K 影片所需的理論頻寬：

• 解析度：8K 意味著 $7680 \times 4320$ 畫素。
• 色彩深度：真彩 (24-bit) 表示每個畫素需要 24 bits。
• 幀率：120 fps (frames per second)。

總傳輸速率 (bits per second) = $\text{解析度} \times \text{色彩深度} \times \text{幀率}$
= $(7680 \times 4320) \times 24 \text{ bits/pixel} \times 120 \text{ frames/second}$
= $33177600 \times 24 \times 120 \text{ bits/second}$
= $796262400 \times 120 \text{ bits/second}$
= $9555148800 \text{ bits/second}$

將其轉換為 Gbps (Gigabits per second)，其中 1 Gbps = $10^9$ bps。

此題考驗對作業系統中時間分時 (time-sharing) 和程序切換 (context switch) 機制的理解。

時間分時 (Time-Sharing) / 多工 (Multitasking)：
在分時多工的作業系統中，CPU 的使用時間被分割成很小的時間片 (time slice)。多個程序 (processes) 可以輪流使用 CPU，每個程序獲得一個短暫的時間片來執行。這樣做可以讓使用者感覺到多個程序同時在運行，提高系統的互動性和效率。

程序切換 (Context Switch)：
當一個程序的時間片用完，或者有更高優先權的程序需要執行，或者程序因為 I/O 操作而暫停時，作業系統就需要進行程序切換。程序切換的過程稱為 context switch，它包含以下幾個步驟：

1. 保存當前程序的狀態：作業系統需要將當前正在 CPU 上執行的程序的 CPU 暫存器 (registers) 的值、程式計數器 (program counter, PC)、堆疊指標 (stack pointer, SP) 等資訊，保存到該程序的 Process Control Block (PCB) 中。這就是所謂的「上下文 (context)」。

此題考驗對比特幣 P2P 網路特性及其安全性與參與者數量的關係的理解。

比特幣 P2P 網路：
比特幣採用分散式的點對點 (Peer-to-Peer, P2P) 網路架構，沒有中央伺服器。每個節點 (node) 都直接與其他節點連接，共享交易訊息和區塊鏈數據。這使得網路更加健壯，不易被單點故障或攻擊癱瘓。

安全性與參與者數量：
在 P2P 網路中，參與者數量的增加通常會提高網路的安全性，而不是降低。原因如下：

1. 分散性增強：節點越多，網路越分散，攻擊者要控制網路的難度就越大。

此題考驗對 Dijkstra 演算法的時間複雜度及其原因的理解。

Dijkstra 演算法：
Dijkstra 演算法是一種用於尋找帶有非負權重的單源最短路徑問題的演算法。它通過一個優先級佇列 (priority queue) 來維護待處理節點，並逐步擴展已知最短路徑的節點集合。

時間複雜度分析：
Dijkstra 演算法的時間複雜度取決於優先級佇列的實現方式以及圖的表示方式（鄰接矩陣或鄰接串列）。

1. 使用鄰接串列 (Adjacency List) 和二元堆 (Binary Heap) 作為優先級佇列：

   • 圖的表示：鄰接串列，其空間複雜度為 $O(|V| + |E|)$。
   • 優先級佇列操作：
     • 插入節點 (Initialization): $|V|$ 次，每次 $O(\log |V|)$，總計 $O(|V| \log |V|)$。
     • 提取最小節點 (Extract-Min): $|V|$ 次，每次 $O(\log |V|)$，總計 $O(|V| \log |V|)$。
     • 減小鍵值 (Decrease-Key): $|E|$ 次，每次 $O(\log |V|)$，總計 $O(|E| \log |V|)$。
   • 總體時間複雜度：$O(|V| \log |V| + |E| \log |V|) = O((|V| + |E|) \log |V|)$。
   • 如果圖是稀疏的 (E 遠小於 $V^2$)，則為 $O(|E| \log |V|)$。

2. 使用鄰接串列 (Adjacency List) 和費氏堆 (Fibonacci Heap) 作為優先級佇列：

   • 提取最小節點 (Extract-Min): $|V|$ 次，每次攤銷 (amortized) $O(\log |V|)$，總計 $O(|V| \log |V|)$。

此題考驗對程式語言中傳遞參數時的「傳值」(pass by value) 和「傳址/傳參考」(pass by reference) 的效率與安全性的比較。

傳值 (Pass by Value)：
當參數以傳值方式傳遞時，函數接收的是參數的「副本」。原始變數的值不會被函數修改。

• 效率：對於大型資料結構（如陣列、結構體），複製整個資料結構需要較多的時間和記憶體空間，效率較低。
• 安全性：原始資料是安全的，因為函數無法直接修改它。

傳址/傳參考 (Pass by Reference)：
當參數以傳址或傳參考方式傳遞時，函數接收的是參數的「記憶體位址」或「參考」。函數可以直接操作原始資料。

核心觀念

本題考查**軟體工程（Software Engineering）中的軟體開發生命週期（Software Development Life Cycle, SDLC）**與經典開發方法論——**瀑布模型（Waterfall Model）**的核心特徵。

1. 傳統 SDLC 階段劃分：
   經典軟體開發包含：需求分析（Requirement Analysis） $\rightarrow$ 系統設計（System Design） $\rightarrow$ 實作與編碼（Implementation / Coding） $\rightarrow$ 測試（Testing） $\rightarrow$ 部署與維護（Deployment & Maintenance）。
2. 瀑布模型（Waterfall Model / Linear-Sequential Model）：
   由 Winston Royce 於 1970 年提出的經典線性循序模型。其最大特徵為文件驅動（Document-driven）與嚴格的階段先後順序（Strict Phase-gate）。在瀑布模型中，前一個階段的輸出（Output）即為下一個階段的輸入（Input），每個階段必須完成既定的查核點（Milestones）並產出完整的文件（如需求規格說明書 SRS），經簽核凍結（Freeze）後才可進入下一階段。

---

解題方法

分析題目敘述之條件與邏輯鏈：

1. 生命週期順序檢驗：
   題目列出「Requirement Analysis $\rightarrow$ Design $\rightarrow$ Implementation $\rightarrow$ Testing」，此為經典 SDLC 之標準線性順序，定義無誤。
2. 階段相依性與文件要求檢驗：
   題目指出「要求所有的 requirement specification 文件必須要在 design 階段之前完成」，這符合瀑布模型的「階段不重疊（Non-overlapping phases）」與「前期需求完全凍結」原則。
3. 結論匹配：
   具備上述「強迫前一階段文件完全產出並定案，方能啟動下一階段」特徵的開發方法，即為瀑布模型（Waterfall Model）。

---

題意逐段分析

核心觀念

本題測驗關聯式資料庫（Relational Database）中 SQL 外部合併（Outer Join） 的對稱性與集合論等價性：

1. LEFT JOIN（左外部合併）：以左側資料表為主體，保留左表所有符合條件的紀錄（Rows）；若右表有對應匹配者則合併，無匹配者補以 NULL。
2. RIGHT JOIN（右外部合併）：以右側資料表為主體，保留右表所有符合條件的紀錄；若左表有對應匹配者則合併，無匹配者補以 NULL。
3. 對偶性（Duality）：
   對於任意兩資料表 $A$ 與 $B$ 及連接條件 $P$：
   $A \text{ RIGHT JOIN } B \text{ ON } P \equiv B \text{ LEFT JOIN } A \text{ ON } P$
   兩者在語意上均代表「保留資料表 $B$ 的所有紀錄，並將符合條件 $P$ 的資料表 $A$ 紀錄合併進來；若 $A$ 無匹配則補 NULL」。

---

解題方法

比對題目的兩個 SQL 查詢語法：

• 語法一：SELECT * FROM T1 RIGHT JOIN T2 ON T1.ID=T2.ID;
• 語法二：SELECT * FROM T2 LEFT JOIN T1 ON T1.ID=T2.ID;

分析切入點：

1. 主表確認：
   • 語法一使用 T1 RIGHT JOIN T2，代表主表為右側的 T2（T2 所有紀錄全數保留）。
   • 語法二使用 T2 LEFT JOIN T1，代表主表為左側的 T2（T2 所有紀錄全數保留）。
2. 連接條件：
   • 兩者皆為等值連接 ON T1.ID=T2.ID（等號具交換律，即 $T1.ID = T2.ID \iff T2.ID = T1.ID$）。
3. 投影範圍與欄列順序：
   • 兩者皆使用 SELECT *，選取兩表所有欄位。

此題考驗對卷積神經網路 (CNN) 和循環神經網路 (RNN) 在處理資料模式 (pattern) 上的核心差異的理解。

卷積神經網路 (Convolutional Neural Network, CNN)：

• 核心概念：CNN 的主要特點是使用「卷積層 (convolutional layers)」。卷積層通過滑動一個小的「濾波器 (filter)」或「卷積核 (kernel)」在輸入資料（例如圖像）上，來提取局部特徵。
• 局部區域模式 (Local Pattern)：濾波器一次只掃描輸入資料的一小部分區域。它能夠有效地捕捉這些局部區域內的空間結構或模式，例如圖像中的邊緣、紋理、形狀等。
• 權重共享 (Weight Sharing)：同一個濾波器會在整個輸入資料上滑動，這意味著它學習到的特徵檢測器可以應用於輸入資料的任何地方。
• 應用：CNN 在圖像識別、電腦視覺等任務中表現出色，因為這些任務中的特徵通常是局部且具有空間相關性的。

此題考驗對神經網路中 Dropout 和 ReLU 激活函數的理解。

Dropout Layer：

• 目的：Dropout 是一種防止神經網路「過度擬合 (overfitting)」的正規化技術。過度擬合發生在模型對訓練資料學習得太好，以至於對未見過的測試資料表現不佳。
• 機制：在訓練過程中，Dropout 會隨機地「關閉 (drop out)」一部分神經元（及其連接），使其在當前迭代中不參與前向傳播和後向傳播。每次迭代都會隨機選擇不同的神經元被關閉。
• 效果：這迫使網路學習更魯棒 (robust) 的特徵，減少神經元之間的協同依賴性，因為任何一個神經元都不能過度依賴其他特定的神經元。相當於訓練多個共享權重的不同子網路。
• 題目敘述：「使用 dropout layer 的理由是避免 overfitting。」 正確。

整流線性單位激發函數 (ReLU, Rectified Linear Unit)：

• 定義：ReLU 函數的定義為 $f(x) = \max(0, x)$。
• 作用：它是一個非線性激活函數。

此題考驗對 RISC (Reduced Instruction Set Computer) 和 CISC (Complex Instruction Set Computer) 這兩種 CPU 設計理念的理解，以及它們的優劣勢。

CISC (Complex Instruction Set Computer) 設計理念：

• 目標：設計指令集，讓單一指令能夠執行複雜的多步驟操作。目標是盡可能減少程式師或編譯器需要編寫的指令數量，使程式碼更精簡。
• 特點：
  • 指令集龐大且複雜：包含許多不同類型的指令，有些指令非常複雜，可以一次完成多個操作（如記憶體讀取、算術運算、記憶體寫入）。
  • 變長指令碼：指令的長度不固定，需要更複雜的硬體來解碼。
  • 多種定址模式：支援多種複雜的記憶體定址方式。
  • 微程式碼 (Microcode)：複雜指令通常由一系列更簡單的微指令 (micro-instructions) 組成，由硬體解釋執行。
• 代表：Intel x86 架構（如 Intel Core 系列、AMD Ryzen 系列）是典型的 CISC 架構。

RISC (Reduced Instruction Set Computer) 設計理念：

• 目標：設計一套精簡、簡單、高效的指令集。目標是讓每條指令都能在一個時鐘週期內執行完畢（理想情況下），並簡化 CPU 硬體的設計，提高執行速度。
• 特點：
  • 指令集精簡：指令數量少，且每條指令的功能都相對簡單。
  • 固定長度指令碼：所有指令長度相同，方便硬體解碼和流水線處理。
  • 簡單定址模式：定址模式較少且簡單。
  • 載入/儲存架構 (Load/Store Architecture)：只有 LOAD 和 STORE 指令可以存取記憶體，所有的算術和邏輯運算都必須在 CPU 暫存器 (registers) 上進行。
  • 大量暫存器：為了減少記憶體存取，提供更多的通用暫存器。
  • 硬體實現：盡量使用硬體直接實現指令，減少或不使用微程式碼。
• 代表：ARM 架構（如 Apple M1, Qualcomm Snapdragon, Apple A 系列）、MIPS、RISC-V。

各自優劣：

CISC 的優點：

1. 程式碼密度高：由於指令功能強大，可以用較少的指令完成任務，使程式碼體積較小。
2. 開發效率 (較早期)：在早期，編寫組合語言時，CISC 的複雜指令可以減少程式師的工作量。

此題考驗對 TCP 協定中三次握手 (three-way handshake) 的狀態轉換 (finite state machine) 的理解，特別是 SYN_SENT 和 SYN_RCVD 狀態下的異常處理。

TCP 三次握手回顧：
TCP 的三次握手用於建立一個可靠的連接。

1. Client -> Server: Client 發送 SYN (synchronize) 封包，進入 SYN_SENT 狀態。
2. Server -> Client: Server 收到 SYN 後，如果同意建立連接，則回傳 SYN-ACK (synchronize-acknowledge) 封包，進入 SYN_RCVD 狀態。
3. Client -> Server: Client 收到 SYN-ACK 後，再發送 ACK (acknowledge) 封包，進入 ESTABLISHED 狀態。Server 收到 ACK 後，也進入 ESTABLISHED 狀態。

圖示說明 (根據常見 TCP FSM)：
圖中顯示了 client 和 server 在 TCP 連接建立過程中的部分狀態轉移。

• Client 端：
  • CLOSED (初始狀態) -> LISTEN (server) 或 SYN_SENT (client)
  • SYN_SENT 狀態：表示 client 已發送 SYN，正在等待 server 的回應。
• Server 端：
  • LISTEN (初始狀態)
  • SYN_RCVD 狀態：表示 server 已收到 client 的 SYN，並已回傳 SYN-ACK，正在等待 client 的 ACK。

(a) 當 client 位於 SYN_SENT 狀態時,若收到 server 回傳 SYN 事件,請問該 client 應當如何處置?

在 TCP 三次握手中，Client 發送 SYN 後進入 SYN_SENT 狀態，它期望收到 Server 回傳的 SYN-ACK。
題目說「收到 server 回傳 SYN 事件」。這表示 Server 雖然回傳了 SYN，但沒有回傳 ACK (即不是 SYN-ACK)。這是一個非標準的、異常的接收。
在 RFC 793 中，當 client 在 SYN_SENT 狀態下收到一個 SYN 封包時，它應該：

1. 回傳一個 SYN-ACK：這表示 client 收到 server 的 SYN，並確認了 server 的 SYN。
2. 更新其 TCB (Transmission Control Block)：可能需要記錄 server 的 SYN 資訊。
3. 保持在 SYN_SENT 狀態：等待 server 的 ACK。

更精確的解釋 (根據 RFC 793)：
當 client 在 SYN_SENT 狀態下收到一個 SYN 封包 (來自 server)：

• 如果這個 SYN 封包包含一個 ACK 欄位，並且這個 ACK 欄位是有效的（即 ACK 了 client 發送的 SYN），那麼 client 應該回傳一個 ACK (而不是 SYN-ACK)。
• 如果這個 SYN 封包不包含有效的 ACK，那麼 client 應該回傳一個 SYN-ACK。

題目中說「收到 server 回傳 SYN 事件」，這句話的理解是關鍵。

• 理解一：Server 只回傳了一個 SYN，沒有 ACK。這時 client 應該回傳 SYN-ACK，並維持 SYN_SENT。

此題考驗對機器學習中損失函數 (Loss Function) 的基本概念，以及兩種常見損失函數 MSE 和 Cross Entropy 的定義、意涵與適用情境。

損失函數 (Loss Function)：

• 定義：損失函數，又稱為成本函數 (Cost Function) 或誤差函數 (Error Function)，是機器學習模型中用來衡量模型預測結果與真實標籤 (ground truth) 之間差異的函數。它量化了模型在給定訓練樣本上的「錯誤程度」。
• 意涵：
  • 指導模型優化：損失函數的目標是最小化。在模型訓練過程中，優化演算法（如梯度下降）會根據損失函數的梯度來調整模型的參數（權重和偏差），目的是找到使損失函數值最小的參數組合。
  • 評估模型性能：損失函數的值越高，表示模型的預測越不準確；值越低，表示模型的預測越接近真實值，性能越好。
  • 區分模型類型：不同的機器學習任務（如迴歸、分類）通常會使用不同類型的損失函數。

1. MSE (Mean Square Error) - 平均平方誤差：

• 概念：MSE 是最常用於迴歸問題的損失函數。它計算的是預測值與真實值之間差值的平方的平均值。
  • 對於一個樣本，誤差為 $e_i = y_i - \hat{y}_i$，其中 $y_i$ 是真實值，$\hat{y}_i$ 是模型預測值。
  • MSE 定義為：$\text{MSE} = \frac{1}{N} \sum_{i=1}^{N} (y_i - \hat{y}_i)^2$
    其中 $N$ 是樣本數量。
• 意涵：
  • 對大誤差敏感：由於差值被平方，MSE 對較大的誤差給予更高的權重。這意味著模型會被「懲罰」更大的錯誤。
  • 平滑且可微分：MSE 是一個連續且處處可微分的函數，這使得它非常適合用於基於梯度下降的優化方法。
  • 單位問題：MSE 的單位是真實值單位的平方，這有時不便於直接解釋。
• 適用時機：
  • 迴歸問題 (Regression Problems)：當目標變數是連續數值時，例如預測房價、氣溫、股票價格等。
  • 對大誤差的容忍度較低時：如果模型預測結果與真實值之間較大的偏差需要被嚴格懲罰，MSE 是一個好的選擇。

2. Cross Entropy (交叉熵)：

• 概念：交叉熵通常用於分類問題。它衡量的是兩個機率分佈之間的差異。在機器學習中，它通常用來比較模型預測的機率分佈與真實的機率分佈（通常是 one-hot 編碼的標籤）。
  • 對於二元分類 (Binary Classification)，二元交叉熵 (Binary Cross-Entropy, BCE) 為：
    $\text{BCE} = -\frac{1}{N} \sum_{i=1}^{N} [y_i \log(\hat{y}_i) + (1 - y_i) \log(1 - \hat{y}_i)]$
    其中 $y_i \in \{0, 1\}$ 是真實標籤，$\hat{y}_i$ 是模型預測為類別 1 的機率 (通常由 sigmoid 函數輸出)。
  • 對於多元分類 (Multi-class Classification)，分類交叉熵 (Categorical Cross-Entropy) 為：
    $\text{CCE} = -\frac{1}{N} \sum_{i=1}^{N} \sum_{c=1}^{C} y_{i,c} \log(\hat{y}_{i,c})$
    其中 $C$ 是類別數量，$y_{i,c}$ 是真實標籤（one-hot 編碼，表示樣本 $i$ 是否屬於類別 $c$），$\hat{y}_{i,c}$ 是模型預測樣本 $i$ 屬於類別 $c$ 的機率（通常由 softmax 函數輸出）。
• 意涵：
  • 衡量機率分佈的差異：交叉熵的值越小，表示預測的機率分佈越接近真實分佈。

此題考驗對 ARP (Address Resolution Protocol) 的理解，特別是 ARP request 的作用以及收到 request 後的回應機制。

封包分析：
從提供的封包資訊，我們可以確定這是一個 ARP (Address Resolution Protocol) 的封包，具體來說是一個 ARP request。

• Ethernet II Header：
  • Src: Google_6e:ad:d5 (MAC Address)：封包發送者的 MAC 位址。
  • Dst: Broadcast (ff:ff:ff:ff:ff:ff)：封包目標是廣播位址，意味著這個封包會被網路上的所有設備接收。
  • Type: ARP (0x0806)：指示上層協定是 ARP。
• ARP Header：
  • Opcode: request (1)：表明這是 ARP 請求。
  • Sender MAC address: Google_6e:ad:d5：發送 ARP request 的設備的 MAC 位址。
  • Sender IP address: 192.168.1.113：發送 ARP request 的設備的 IP 位址。
  • Target MAC address: 00:00:00:00:00:00：目標 MAC 位址。在 ARP request 中，這個欄位通常是全零，因為發送者不知道目標的 MAC 位址。
  • Target IP address: 192.168.1.106：發送 ARP request 所查詢的目標 IP 位址。

ARP Request 的用處：
ARP (Address Resolution Protocol) 的主要目的是將 IP 位址解析 (resolve) 成對應的 MAC 位址。在區域網路 (LAN) 中，設備之間通信需要知道對方的 MAC 位址才能傳送 Ethernet 幀。
當一個設備 (sender, 192.168.1.113) 需要向另一個設備 (target, 192.168.1.106) 發送 IP 封包時，但它不知道目標 IP 位址 192.168.1.106 對應的 MAC 位址，它就會發送一個 ARP Request。
這個 ARP Request 的內容是：「請問，IP 位址是 192.168.1.106 的設備，你的 MAC 位址是多少？我的 IP 位址是 192.168.1.113，我的 MAC 位址是 Google_6e:ad:d5。」
由於 ARP Request 是廣播發送的，網路上的所有設備都會收到這個封包。

應如何回應該封包：
當網路上的設備收到這個 ARP Request 時，它們會檢查封包中的 Target IP address：

1. 檢查自身 IP 位址：每個設備都會將 ARP Request 中的 Target IP address (192.168.1.106) 與自己的 IP 位址進行比較。
2. 回應者：
   • 如果設備的 IP 位址與 Target IP address 相符 (即 IP 位址是 192.168.1.106 的設備)：
     • 這個設備會知道有人在找它。
     • 它會製作一個 ARP Response 封包。

此題考驗對推薦系統中三個核心挑戰的理解：冷啟動、探索-利用困境、稀疏性，並要求提出基於人工智慧的解決方案。

1. 冷啟動 (Cold Start) 問題：

• 定義：當系統中出現新的使用者 (user) 或新的物品 (item) 時，推薦系統缺乏足夠的歷史互動數據來進行準確的推薦。

  • 使用者冷啟動 (User Cold Start)：新使用者加入系統，系統不知道其偏好。
  • 物品冷啟動 (Item Cold Start)：新物品加入系統，沒有使用者與之互動過，系統難以將其推薦給合適的使用者。

• 意涵：系統無法為新使用者提供個性化推薦，也無法將新物品有效推廣給潛在使用者，這會影響使用者體驗和物品的曝光度。

• 基於 AI 的解決方案：

  1. 內容推薦 (Content-Based Filtering)：
     • 原理：利用物品的「內容資訊」(如物品的屬性、標籤、描述、類別等) 和使用者的「內容偏好」(如使用者過去喜歡的物品的屬性)。
     • 做法：對於新物品，可以根據其內容屬性，直接推薦給具有相似偏好的現有使用者。對於新使用者，可以先詢問其對某些物品屬性的偏好，或根據其註冊時填寫的個人資訊（如年齡、性別、興趣標籤）來構建初始的使用者偏好模型。
     • AI 應用：NLP 技術（如 TF-IDF, Word Embeddings, BERT）用於理解物品描述和使用者查詢；圖像識別技術用於分析物品圖片。
  2. 混合方法 (Hybrid Approaches)：
     • 原理：結合內容推薦和協同過濾 (Collaborative Filtering) 的優點。
     • 做法：
       • 對於新使用者/物品，優先使用內容推薦。
       • 隨著互動數據的積累，逐漸過渡到或融合協同過濾的推薦。
       • 可以利用矩陣分解 (Matrix Factorization) 等技術，將內容特徵嵌入到潛在因子模型中，以緩解冷啟動問題。例如，使用因子分解機 (Factorization Machines, FM) 或神經協同過濾 (Neural Collaborative Filtering, NCF)，將物品的內容特徵作為額外輸入。
  3. 基於知識圖譜 (Knowledge Graph) 的推薦：
     • 原理：利用知識圖譜中豐富的實體和關係信息。
     • 做法：將物品和使用者與知識圖譜中的節點連接起來，通過圖嵌入 (Graph Embedding) 技術（如 TransE, GNNs）來學習物品和使用者的表示，即使是新物品或使用者，只要能連接到知識圖譜，也能獲得一定的表示，從而進行推薦。
  4. 主動學習 (Active Learning)：
     • 原理：系統主動向使用者提出問題，以最有效的方式獲取使用者偏好信息。
     • 做法：例如，在使用者首次登錄時，展示一些代表性的物品，讓使用者進行評價或選擇，從而快速建立其偏好模型。

2. 探索-利用困境 (Exploration-Exploitation Dilemma)：

• 定義：推薦系統在「利用」現有知識提供最可能受使用者歡迎的推薦（利用已知的優質物品）和「探索」新的、可能更優但尚未被發現的物品（發現新的潛在優質物品）之間面臨的權衡。

• 意涵：

  • 過度利用：可能導致推薦列表變得單調乏味，錯過使用者可能感興趣的新物品，使用戶感到厭倦。
  • 過度探索：可能導致推薦列表充斥著使用者不感興趣的物品，降低推薦的準確性和用戶滿意度。

• 意涵：需要在短期回報（利用已知）和長期回報（發現潛在更好的推薦）之間取得平衡。

• 基於 AI 的解決方案：

  1. 多臂老虎機 (Multi-Armed Bandit, MAB)：
     • 原理：將推薦問題建模為一個賭場的多臂老虎機遊戲。每個「臂」代表一個推薦選項（物品），每次拉動一個臂（推薦一個物品）會獲得一個回報（如點擊、購買）。目標是在有限次數內最大化總回報。
     • 演算法：
       • Epsilon-Greedy：以概率 $\epsilon$ 進行探索（隨機選擇一個物品），以概率 $1-\epsilon$ 進行利用（選擇當前認為最好的物品）。
       • Upper Confidence Bound (UCB)：選擇一個同時考慮了物品的預期回報和不確定性（探索程度）的指標最高的物品。
       • Thompson Sampling：基於貝葉斯方法，根據物品的回報分佈進行抽樣，選擇抽樣值最高的物品。
     • AI 應用：MAB 演算法是解決探索-利用困境的經典方法，廣泛應用於 A/B 測試、廣告投放、內容推薦等場景。
  2. 基於深度學習的強化學習 (Deep Reinforcement Learning, DRL)：
     • 原理：將推薦過程視為一個馬爾可夫決策過程 (Markov Decision Process, MDP)，推薦系統作為一個智能體 (agent)，通過與環境（使用者）互動來學習推薦策略。
     • 做法：DRL 模型（如 DQN, Actor-Critic）可以學習到更複雜、更動態的推薦策略，能夠根據使用者即時的反應和上下文來決定是進行探索還是利用。
  3. 上下文感知推薦 (Context-Aware Recommendation)：
     • 原理：結合使用者的當前上下文信息（如時間、地點、設備、當前活動等）來調整探索與利用的比例。
     • 做法：在某些情況下（如使用者首次使用某功能），可以增加探索；在其他情況下（如使用者明確表達某種偏好），可以增加利用。

3. 稀疏性 (Sparsity) 問題：

• 定義：在推薦系統的互動數據矩陣（通常是使用者-物品互動矩陣）中，絕大多數的條目是空的（即使用者沒有與該物品互動過），只有少數條目包含實際的互動數據（如評分、點擊、購買）。

• 意涵：

  • 協同過濾的挑戰：基於協同過濾的方法（如基於鄰域的方法、矩陣分解）在處理稀疏數據時效果會顯著下降，因為很難找到足夠相似的使用者或物品。
  • 模型訓練困難：訓練數據的稀疏性會導致模型難以學習到準確的使用者偏好和物品特徵。

• 意涵：數據的稀疏性是推薦系統面臨的最根本的挑戰之一。

• 基於 AI 的解決方案：

  1. 內容推薦 (Content-Based Filtering)：
     • 原理：如前所述，內容推薦不直接依賴使用者之間的互動，而是依賴物品的屬性。因此，即使物品互動數據稀疏，只要有豐富的物品內容資訊，內容推薦仍然可以工作。

此題與考卷第二頁的第四題是同一題，只是配分不同。因此，詳解可以參考第四題的詳解。

簡要說明：
這個封包是一個 ARP Request。

• 用處：它的用處是讓 IP 位址為 192.168.1.113 的設備查詢 IP 位址為 192.168.1.106 的設備的 MAC 位址，以便在區域網路中進行 IP 通信。

此題考驗對雜湊函數 (Hash Function) 的特性，特別是 SHA-256 的輸出分佈，以及概率計算的理解。

SHA-256 雜湊函數的特性：

• 輸入：任意大小的資料。
• 輸出：固定長度的 256 位元雜湊值，其值域為 $[0, 2^{256}-1]$。
• 理想雜湊函數的假設：
  • 抗碰撞性 (Collision Resistance)：很難找到兩個不同的輸入 $x_1, x_2$ 使得 $H(x_1) = H(x_2)$。
  • 原像抗性 (Pre-image Resistance)：給定一個雜湊值 $h$，很難找到一個輸入 $x$ 使得 $H(x) = h$。
  • 第二原像抗性 (Second Pre-image Resistance)：給定一個輸入 $x_1$，很難找到另一個輸入 $x_2 \ne x_1$ 使得 $H(x_1) = H(x_2)$。
  • 均勻分佈 (Uniform Distribution)：理想情況下，雜湊函數的輸出應該在整個輸出空間中均勻分佈。也就是說，對於輸出空間中的任何一個值，被雜湊到的機率應該是相等的。

在沒有其他資訊的情況下，我們通常假設 SHA-256 是一個「偽隨機」函數，其輸出在定義域內是均勻分佈的。

(a) 試求出 SHA256(X) = 0 之機率。

• SHA-256 的輸出值域是 $[0, 2^{256}-1]$。這個範圍包含了 $2^{256}$ 個可能的整數值。
• 假設 SHA-256 輸出均勻分佈，那麼任何一個特定的輸出值（例如 0）被隨機選中的機率是：
  $P(\text{SHA256}(X) = 0) = \frac{1}{\text{輸出空間的大小}} = \frac{1}{2^{256}}$
• 這個機率非常非常小，這也是雜湊函數設計的目標之一，以確保其輸出難以預測。

(b) 試求出 SHA256(X) < T 之機率。$0 \le T \le 2^{256}-1$。

• 我們需要計算雜湊值落在區間 $[0, T-1]$ 的機率。
• 這個區間包含了 $T$ 個可能的整數值（從 0 到 $T-1$）。
• 假設 SHA-256 輸出均勻分佈，那麼 SHA256(X) 小於 T 的機率是：
  $P(\text{SHA256}(X) < T) = \frac{\text{區間內值的數量}}{\text{輸出空間的大小}} = \frac{T}{2^{256}}$
• 請注意，題目中的 $T$ 是指一個上限值，而我們計算的是小於 $T$ 的值的數量。如果 $T$ 是指區間的「長度」，則公式是正確的。如果 $T$ 是指區間的「上界」，那麼區間是 $[0, T-1]$，總共有 $T$ 個整數。
• 例如，如果 $T=1$，則 $P(\text{SHA256}(X) < 1) = P(\text{SHA256}(X) = 0) = \frac{1}{2^{256}}$。

核心觀念

本題考查兩個觀念：

1. 二進位中 1 的個數（population count）

   將每個非負整數轉成二進位，計算其中位元 1 的數量。例如：

   • $0=(0000)_2$，含有 $0$ 個 $1$
   • $5=(0101)_2$，含有 $2$ 個 $1$
   • $7=(0111)_2$，含有 $3$ 個 $1$

2. 多重排序鍵（multiple sorting keys）

   每個數字的排序鍵為：

   $\text{key}(x)=(\text{ones}(x),x)$

   依照字典序比較：

   • 先比較二進位中 $1$ 的個數，數量少者優先；
   • 若 $1$ 的個數相同，再比較十進位數值，數值小者優先。

因此，排序條件可寫成：

$$a \prec b \iff \bigl(\text{ones}(a)<\text{ones}(b)\bigr) \lor \bigl(\text{ones}(a)=\text{ones}(b)\land a<b\bigr)$$

---

解題方法

對陣列中的每個元素 $x$：

1. 計算 $x$ 的二進位表示中有幾個 $1$；
2. 將 $x$ 與計算結果組成一筆資料；
3. 依照 (1 的個數, 原數值) 由小到大排序；
4. 取出排序後的原數值，即為答案。

計算二進位中 1 的個數

可使用位元運算技巧：

$$x \mathbin{\&} (x-1)$$

此運算會將 $x$ 最右邊的那個 $1$ 清除。

例如：

$$12=(1100)_2$$ $$12\mathbin{\&}11 = 1100_2\mathbin{\&}1011_2 = 1000_2$$

每執行一次，便少掉一個 $1$。因此重複執行直到數值變成 $0$，執行次數就是二進位中 $1$ 的數量。

---

Pseudocode

FUNCTION countOnes(x):
    count ← 0

    WHILE x > 0:
        x ← x AND (x - 1)
        count ← count + 1

    RETURN count


FUNCTION sortByBinaryOnes(arr):
    records ← empty list

    FOR EACH x IN arr:
        ones ← countOnes(x)
        APPEND (ones, x) TO records

    SORT records BY:
        1. ones increasing
        2. x increasing

    result ← empty list

    FOR EACH record IN records:
        APPEND record.x TO result

    RETURN result

排序時的比較函式也可以明確寫成：