112 年 國立臺灣大學生醫電子與資訊學研究所丙組《計算機概論（B）》

這是一道名詞解釋題，主要考察考生對計算機領域中一些重要概念的理解程度。以下是各名詞的解釋：

1. XaaS (Anything as a Service)：
   XaaS 是一種雲端運算服務的總稱，代表「萬物皆服務」。它涵蓋了各種可以透過網路提供的服務，打破了傳統軟體、平台或基礎設施的限制。核心概念是將資源或功能以服務的形式提供給使用者，使用者無需關心底層的硬體或軟體維護，只需透過訂閱或按使用量付費即可。常見的 XaaS 包括：

   • SaaS (Software as a Service)：軟體即服務，如 Google Workspace, Microsoft 365。
   • PaaS (Platform as a Service)：平台即服務，如 Heroku, Google App Engine。
   • IaaS (Infrastructure as a Service)：基礎設施即服務，如 AWS EC2, Azure Virtual Machines。
   • DBaaS (Database as a Service)：資料庫即服務。
   • 等等。

2. NFT (Non-Fungible Token)：
   NFT，中文稱為「非同質化代幣」，是一種儲存在區塊鏈上的獨特數位資產。與比特幣等「同質化代幣」（Fungible Token）不同，每個 NFT 都是獨一無二的，不可互相替換。這使得 NFT 能夠代表和驗證數位藝術品、收藏品、音樂、遊戲道具、虛擬土地等獨特資產的所有權。區塊鏈技術確保了 NFT 的稀缺性、可追溯性和不可篡改性。

3. Crowdsourcing (群眾外包)：
   Crowdsourcing 是一種將傳統上由特定員工或承包商執行的任務，外包給一個龐大、未定義的群眾（通常是透過網際網路）來完成的模式。它可以是眾包資金（Crowdfunding）、眾包知識（如 Wikipedia）、眾包設計，或是眾包數據標註等。其優勢在於可以利用集體智慧、降低成本、提高效率，並能接觸到更廣泛的技能和創意。

4. 5G：
   5G 是第五代行動通訊技術（Fifth Generation Mobile Network）。相較於前幾代技術（如 4G LTE），5G 提供了更快的傳輸速度（Gbps 等級）、更低的延遲（毫秒級）以及更大的網路容量（支援更多設備連接）。這使得 5G 不僅能提升智慧型手機的用戶體驗，更能支援物聯網（IoT）、自動駕駛、遠距醫療、擴增實境/虛擬實境（AR/VR）等需要高速、低延遲和大規模連接的應用。

此題主要考驗考生對二進位轉換以及 IEEE 754 單倍精準浮點數表示法的掌握。

核心觀念：

• 十進位轉二進位：整數部分採用除二取餘法，小數部分採用乘二取整法。
• IEEE 754 單倍精準數：將一個二進位浮點數表示為 $S \times 2^E \times M$ 的形式，其中 S 是符號位，E 是指數，M 是尾數。單倍精準數（32 位元）的結構為：1 位元符號 (S) + 8 位元指數 (E) + 23 位元尾數 (M)。指數部分需要進行偏差（bias）處理。

(a) 十進位數 2023.625 轉成二進位數

我們將整數部分和小數部分分開轉換。

整數部分 2023：
使用除以 2 取餘數法：
$2023 \div 2 = 1011$ ... 餘 1
$1011 \div 2 = 505$ ... 餘 1
$505 \div 2 = 252$ ... 餘 1
$252 \div 2 = 126$ ... 餘 0
$126 \div 2 = 63$ ... 餘 0
$63 \div 2 = 31$ ... 餘 1
$31 \div 2 = 15$ ... 餘 1
$15 \div 2 = 7$ ... 餘 1
$7 \div 2 = 3$ ... 餘 1
$3 \div 2 = 1$ ... 餘 1
$1 \div 2 = 0$ ... 餘 1

將餘數由下往上讀取，得到整數部分的二進位表示為：$11111100111_2$。

小數部分 0.625：
使用乘以 2 取整數部分法：
$0.625 \times 2 = 1.25$ ... 取 1
$0.25 \times 2 = 0.5$ ... 取 0
$0.5 \times 2 = 1.0$ ... 取 1

將取出的整數部分由上往下讀取，得到小數部分的二進位表示為：$0.101_2$。

將整數和小數部分合併，得到十進位數 2023.625 的二進位表示為：$11111100111.101_2$。

(b) 轉換成 IEEE 754 單倍精準數 (32 位元)

IEEE 754 單倍精準數的格式為：
符號位 (S)：1 位元
指數 (E)：8 位元 (需加上偏差值 127)
尾數 (M)：23 位元 (隱含一個前導的 1)

首先，我們需要將二進位數 $11111100111.101_2$ 轉換為科學記號形式：$1.M' \times 2^E$。
將小數點向左移動，直到小數點前只有一個 1。

這是一道關於位元運算（特別是 XOR）的題目，重點在於理解 XOR 的性質以及連續運算。

核心觀念：

• XOR 運算 (Exclusive OR)：
  • $0 \oplus 0 = 0$
  • $0 \oplus 1 = 1$
  • $1 \oplus 0 = 1$
  • $1 \oplus 1 = 0$
    XOR 運算的特性是：當兩個輸入位元不同時，結果為 1；當兩個輸入位元相同時，結果為 0。
• XOR 的性質：
  • 交換律：$A \oplus B = B \oplus A$
  • 結合律：$A \oplus (B \oplus C) = (A \oplus B) \oplus C$
  • 恆等律：$A \oplus 0 = A$
  • 自反律：$A \oplus A = 0$
  • 逆元律：$A \oplus B = C \implies A \oplus C = B$ 且 $B \oplus C = A$

(a) DATA 與 MASK 以 XOR 運算後的結果

給定的 DATA 是 $10010110_2$，MASK 是 $00111100_2$。
我們對應位元進行 XOR 運算：

$10010110$ (DATA)
$\oplus 00111100$ (MASK)

$10101010$ (Result)

逐位計算：
$1 \oplus 0 = 1$
$0 \oplus 0 = 0$
$0 \oplus 1 = 1$
$1 \oplus 1 = 0$
$0 \oplus 1 = 1$
$1 \oplus 1 = 0$
$1 \oplus 0 = 1$
$0 \oplus 0 = 0$

這是一道關於作業系統 CPU 排程演算法的題目，要求解釋「最短工作先處理 (Shortest Job First, SJF)」的運作方式及其優缺點。

核心觀念：

• CPU 排班 (CPU Scheduling)：作業系統為了有效利用 CPU 資源，決定哪個就緒的行程（process）可以獲得 CPU 的使用權，以及使用多久。
• SJF (Shortest Job First)：一種 CPU 排班演算法，其核心思想是選擇就緒佇列（ready queue）中預期執行時間最短的行程來優先執行。

運作方式：

SJF 演算法有兩種主要實現方式：

1. 非搶佔式 SJF (Non-preemptive SJF)：
   一旦一個行程開始在 CPU 上執行，它會一直執行直到其完成為止，即使在此期間有其他預期執行時間更短的行程進入就緒佇列。當 CPU 空閒時，排程器會從所有就緒的行程中選擇預期執行時間最短的那個來執行。

2. 搶佔式 SJF (Preemptive SJF)：
   也稱為「最短剩餘時間優先 (Shortest Remaining Time First, SRTF)」。當一個新行程進入就緒佇列，並且它的預期執行時間比當前正在 CPU 上執行的行程的剩餘執行時間還要短時，系統會剝奪（preempt）當前行程的 CPU 使用權，將 CPU 分配給這個新到達的行程。如果沒有新行程到達，或者新行程的預期執行時間大於或等於當前行程的剩餘時間，則當前行程繼續執行。

優點：

1. 平均等待時間最短 (Optimal for Average Waiting Time)：
   理論上，SJF 演算法（特別是搶佔式版本 SRTF）可以達到最小的平均等待時間。因為它總是優先處理那些執行時間短的任務，使得這些任務能夠更快地完成並離開系統，從而減少了整體系統中行程的平均等待時間。

這是一道關於密碼學中金鑰交換演算法的題目，要求解釋 Diffie-Hellman 演算法如何實現安全金鑰交換。

核心觀念：

• Diffie-Hellman 金鑰交換演算法：一種由 Whitfield Diffie 和 Martin Hellman 在 1976 年提出的公開金鑰交換協定，允許兩個在不安全通訊頻道上的使用者，協商出一個共享的秘密金鑰，而無需事先共享任何秘密。
• 公開金鑰密碼學 (Public-key Cryptography)：一種密碼系統，其中每個使用者擁有一對金鑰：一個公開金鑰（public key），可以公開發布；一個私密金鑰（private key），必須保密。
• 數學基礎：Diffie-Hellman 演算法基於模數運算（modular arithmetic）和離散對數問題（discrete logarithm problem）的困難性。離散對數問題是指，給定一個質數 $p$、一個生成元 $g$ 和 $g^x \pmod p$ 的值，難以求出 $x$。

演算法說明與舉例：

假設有兩個朋友，Alice 和 Bob，他們想在一個公開場合（例如一個有許多人可以聽到的房間）協商一個秘密金鑰。有一個潛在的竊聽者 Eve 在場。

步驟 1：公開參數的建立 (Agreement on Public Parameters)

Alice 和 Bob 首先需要協商兩個公開的參數：

• 一個大質數 $p$。
• 一個生成元 $g$，它是模 $p$ 的一個原根（primitive root）。

這兩個值是公開的，Eve 也可以知道。
例如，我們使用一組較小的數字來演示：

• $p = 23$ (一個質數)
• $g = 5$ (一個生成元，因為 $5^1, 5^2, ..., 5^{22}$ 模 23 會產生 1 到 22 的所有值)

Eve 知道 $p=23$ 和 $g=5$。

步驟 2：各自產生私密金鑰 (Generate Private Keys)

Alice 和 Bob 各自獨立地選擇一個隨機的私密整數。

• Alice 選擇她的私密金鑰 $a$。
• Bob 選擇他的私密金鑰 $b$。

這兩個私密金鑰必須是秘密，Eve 不能得知。
例如：

• Alice 選擇私密金鑰 $a = 6$。
• Bob 選擇私密金鑰 $b = 15$。

Eve 不知道 $a=6$ 或 $b=15$。

步驟 3：計算並交換公開金鑰 (Compute and Exchange Public Keys)

Alice 和 Bob 使用他們的私密金鑰和公開參數來計算他們各自的公開金鑰。

• Alice 計算她的公開金鑰 $A = g^a \pmod p$。
• Bob 計算他的公開金鑰 $B = g^b \pmod p$。

然後，他們將各自計算出的公開金鑰 $A$ 和 $B$ 傳送給對方。這些公開金鑰也是公開的，Eve 可以截獲。
例如：

• Alice 計算 $A = 5^6 \pmod{23}$。
  $5^1 = 5$
  $5^2 = 25 \equiv 2 \pmod{23}$
  $5^3 \equiv 5 \times 2 = 10 \pmod{23}$
  $5^4 \equiv 10 \times 5 = 50 \equiv 4 \pmod{23}$
  $5^5 \equiv 4 \times 5 = 20 \equiv -3 \pmod{23}$
  $5^6 \equiv 20 \times 5 = 100 \equiv 8 \pmod{23}$
  所以 Alice 的公開金鑰是 $A = 8$。

• Bob 計算 $B = 5^{15} \pmod{23}$。
  $5^{10} = (5^5)^2 \equiv (-3)^2 = 9 \pmod{23}$
  $5^{15} = 5^{10} \times 5^5 \equiv 9 \times (-3) = -27 \equiv -27 + 23 \times 2 = -27 + 46 = 19 \pmod{23}$
  所以 Bob 的公開金鑰是 $B = 19$。

Alice 和 Bob 互相傳送 $A=8$ 和 $B=19$。Eve 知道 $A=8$ 和 $B=19$。

步驟 4：協商共享秘密金鑰 (Generate Shared Secret Key)

Alice 和 Bob 分別接收對方的公開金鑰，然後使用自己的私密金鑰和對方的公開金鑰來計算共享的秘密金鑰。

• Alice 使用她的私密金鑰 $a$ 和 Bob 的公開金鑰 $B$ 來計算：
  $S_{Alice} = B^a \pmod p = (g^b)^a \pmod p = g^{ba} \pmod p$

這是一道關於比較不同函數增長率的題目，重點在於理解多項式函數和指數函數的增長速度，並在給定數值下進行計算和排序。

核心觀念：

• 函數的計算與比較：根據給定的變數值，計算各個函數的輸出。
• 函數的增長率：
  • 常數函數（例如 1000）增長率最低。
  • 線性函數（例如 $1000n$）增長率次之。
  • 多項式函數（例如 $1000m^2$ 或 $n^3$）的增長率取決於指數，指數越高，增長越快。
  • 指數函數（例如 $2^n$）的增長率通常是最高的，遠超任何多項式函數。

計算與比較：

我們需要計算四個函數在不同 $n$ 值下的結果，並進行排序。
四個函數是：$f_1(n) = 1000n$、$f_2(n) = 1000m^2$、$f_3(n) = n^3$、$f_4(n) = 2^n$。
題目中提到 $1000m^2$，但後續的計算和比較都是針對 $n$ 的，且沒有給出 $m$ 的值。通常這種情況下，如果沒有額外說明，我們會假設 $m$ 也與 $n$ 相關，或者題目可能漏掉了對 $m$ 的定義。
假設題目意圖是比較 $1000n, 1000n^2, n^3, 2^n$。 由於題目原文寫的是 $1000m^2$ 而非 $1000n^2$，且後續只問關於 $n$ 的大小關係，這是一個潛在的歧義。
如果嚴格按照題目原文，我們無法計算 $1000m^2$ 的值，因為 $m$ 未定義。
然而，考慮到這是計算機概論的考題，且後續比較都是以 $n$ 為變數，最合理的解釋是題目意圖比較的是 $1000n, 1000n^2, n^3, 2^n$。
我將基於這個合理推測進行解答。如果題目確實意圖是 $1000m^2$ 且 $m$ 是另一個獨立變數，則此題無法完整作答。
在此，我假設 $f_2(n) = 1000n^2$。

我們將計算以下四個函數：
$f_1(n) = 1000n$
$f_2(n) = 1000n^2$
$f_3(n) = n^3$
$f_4(n) = 2^n$

情況一：當 $n=1$ 時

• $f_1(1) = 1000 \times 1 = 1000$
• $f_2(1) = 1000 \times 1^2 = 1000 \times 1 = 1000$
• $f_3(1) = 1^3 = 1$
• $f_4(1) = 2^1 = 2$

在 $n=1$ 時，各值為：1000, 1000, 1, 2。
大小關係：
$f_3(1) = 1 < f_4(1) = 2 < f_1(1) = f_2(1) = 1000$
即：$n^3 < 2^n < 1000n = 1000n^2$

情況二：當 $n=100$ 時

• $f_1(100) = 1000 \times 100 = 100000 = 1 \times 10^5$
• $f_2(100) = 1000 \times 100^2 = 1000 \times 10000 = 10000000 = 1 \times 10^7$
• $f_3(100) = 100^3 = (10^2)^3 = 10^6$
• $f_4(100) = 2^{100}$
  我們知道 $2^{10} = 1024 \approx 10^3$。
  所以 $2^{100} = (2^{10})^{10} \approx (10^3)^{10} = 10^{30}$。
  更精確地，$2^{100} = (1.024 \times 10^3)^{10} \approx 1.267 \times 10^{30}$。

在 $n=100$ 時，各值約為：$10^5, 10^7, 10^6, 10^{30}$。
大小關係：
$f_1(100) = 10^5 < f_3(100) = 10^6 < f_2(100) = 10^7 < f_4(100) \approx 10^{30}$
即：$1000n < n^3 < 1000n^2 < 2^n$

情況三：當 $n=10000$ 時

這是一道演算法設計題目，要求編寫一個程式，找出數列中與平均值差距最小的數。

核心觀念：

1. 計算平均值：首先需要計算輸入數列的平均值。
2. 計算差值：遍歷數列，計算每個數與平均值的絕對差值。
3. 尋找最小值：在所有差值中，找出最小的那個差值。
4. 找出對應的數：找到與最小差值對應的原始數列中的數。如果有多個數與平均值的差值相同且都是最小，題目要求輸出「數列中所有與這個數的平均值相差最小的數」。這句話的理解有兩種可能：
   • 輸出其中一個即可。
   • 輸出所有符合條件的數。
     基於「數列中所有與這個數的平均值相差最小的數」的表述，更傾向於輸出所有符合條件的數。為了清晰，我們將輸出所有符合條件的數。

演算法設計：

1. 輸入：一個包含 $n$ 個數字的數列（例如，陣列或列表）。
2. 步驟 1：計算總和
   • 初始化一個變數 total_sum 為 0。
   • 遍歷數列中的每一個數，將其加到 total_sum。
3. 步驟 2：計算平均值
   • 如果數列為空（$n=0$），則無法計算平均值。需要處理這種邊界情況（例如，返回空列表或拋出錯誤）。
   • 否則，計算平均值 average = total_sum / n。
4. 步驟 3：計算最小差值並記錄對應數
   • 初始化一個變數 min_difference 為一個極大的正數（例如，浮點數的最大值）。
   • 創建一個列表 result_numbers 來儲存所有與平均值差距最小的數。
   • 遍歷數列中的每一個數 num：
     • 計算當前數與平均值的絕對差值：difference = abs(num - average)。
     • 比較差值：
       • 如果 difference < min_difference：
         • 這是一個新的最小差值。
         • 更新 min_difference = difference。
         • 清空 result_numbers 列表，並將當前數 num 加入 result_numbers。
       • 如果 difference == min_difference：
         • 這是一個與當前最小差值相等的差值。
         • 將當前數 num 加入 result_numbers。
5. 輸出：result_numbers 列表。

程式碼實現 (Python)：