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

選擇排序法的核心觀念是在每一輪的排序中，找出未排序部分的最小（或最大）元素，然後將其與未排序部分的起始元素交換。

時間複雜度分析：

選擇排序法需要進行 $n-1$ 輪比較與交換。

• 第一輪： 需比較 $n-1$ 次，找出最小元素，然後交換。
• 第二輪： 需比較 $n-2$ 次，找出第二小元素，然後交換。
• 第三輪： 需比較 $n-3$ 次，找出第三小元素，然後交換。
• ...
• 第 $n-1$ 輪： 需比較 1 次，找出第 $n-1$ 小元素，然後交換。

總共的比較次數為：
$(n-1) + (n-2) + (n-3) + ... + 1$

這是一個等差數列的求和，其公式為 $\frac{k(k+1)}{2}$，其中 $k = n-1$。

TCP（Transmission Control Protocol）中的 Fast Retransmission（快速重傳）是一種用於提高 TCP 傳輸效率的機制，尤其是在發生封包遺失時。

用途：
Fast Retransmission 的主要用途是減少封包遺失後，接收端等待 Timer 到期才通知傳送端重傳封包的時間，從而更快地恢復傳輸。

優點：

1. 減少延遲： 傳統的 TCP 傳輸在封包遺失後，會等待一個重傳定時器（Retransmission Timer, RTO）到期後才進行重傳。Fast Retransmission 可以在 Timer 到期之前就觸發重傳，顯著縮短了封包遺失後的恢復時間，降低了傳輸延遲。
2. 提高吞吐量： 透過更快速地補償遺失的封包，可以讓傳送端的發送窗口（Send Window）保持更活躍的狀態，減少空閒時間，從而提高整體資料傳輸的吞吐量。

運作原理：

Fast Retransmission 的運作依賴於 TCP 的確認應答（Acknowledgement, ACK）機制，特別是重複 ACK（Duplicate ACK）。

1. 接收端收到失序封包： 當接收端收到一個封包（例如封包 Seq=100）但它期待的下一個封包（例如 Seq=90）尚未收到時，接收端不會緩衝這個失序的封包。相反，它會立即發送一個 ACK 封包給傳送端，用來確認它已經成功收到的最後一個連續封包。

本題主要在考察對 IPv4 CIDR（Classless Inter-Domain Routing）表示法、網路位址、廣播位址、子網路劃分（Subnetting）的概念。

a. 所代表之意義為何？(4%)

CIDR 表示法 /16 表示網路位址部分佔 16 位元。IPv4 位址總共 32 位元。
192.168.0.0/16 的意義是：

• 網路位址： 192.168.0.0
• 網路位址長度： 16 位元（前 16 位元屬於網路部分）。
• 主機位址長度： $32 - 16 = 16$ 位元（後 16 位元屬於主機部分）。
• IP 位址範圍： 192.168.0.0 到 192.168.255.255。
  • 192.168.0.0 是網路位址。
  • 192.168.255.255 是廣播位址。
  • 實際可用的主機位址範圍為 192.168.0.1 到 192.168.255.254。

b. 其主要用途通常為何？(4%)

192.168.0.0/16 屬於 IPv4 的私有 IP 位址空間（RFC 1918）。私有 IP 位址不能在公共網際網路中直接路由，只能在內部網路（如家庭網路、公司內部網路）使用。
其主要用途是：

• 內部網路通訊： 提供給組織或家庭內部設備使用，用於互相連線和通訊。
• 節省公有 IP 位址： 透過 NAT（Network Address Translation）技術，多個私有 IP 位址可以透過一個公有 IP 位址連接到網際網路，有效節省了 IPv4 公有位址的稀缺性。

c. 倘若欲將此網段切割成約 60 個子網段，請問應該如何進行？(4%)

要切割成約 60 個子網段，我們需要從主機位址部分借用位元來作為新的子網路位元。
目前的主機位址有 16 位元。
若借用 $k$ 位元作為子網路位元，則可以切割出 $2^k$ 個子網段。
我們需要 $2^k \ge 60$。

• 如果 $k=5$，則 $2^5 = 32$ 個子網段（不足）。
• 如果 $k=6$，則 $2^6 = 64$ 個子網段（足夠）。
  因此，我們需要從原有的 16 位元主機位址中借用 6 位元作為子網路位元。

本題主要在考察程式語言的編譯與直譯兩種執行模式的差異，以及 JavaScript 的特性與應用。

編譯式程式語言（Compiled Language）：
指在程式執行前，整個原始碼會由一個稱為「編譯器」（Compiler）的程式，一次性地將其轉換成目標電腦硬體可以直接執行的機器碼（Machine Code）或中間碼（Intermediate Code）。編譯完成後，會產生一個獨立的可執行檔。

• 優點： 執行速度通常較快，因為程式碼已經被翻譯成機器可以理解的形式；可以在編譯階段發現較多的語法錯誤。
• 缺點： 編譯過程需要時間；跨平台性較差，通常需要為不同的作業系統和架構重新編譯。
• 範例： C, C++, Java (編譯成位元組碼，再由 JVM 直譯或 JIT 編譯), Go, Rust。

直譯式程式語言（Interpreted Language）：
指程式碼在執行時，由一個稱為「直譯器」（Interpreter）的程式，逐行（或逐個語句）地讀取原始碼，並將其轉換成機器碼後立即執行。不需要預先產生可執行檔。

• 優點： 開發快速，修改後可立即執行，通常具有較好的跨平台性（只要有對應的直譯器即可）；更易於除錯。
• 缺點： 執行速度通常較編譯式語言慢，因為每次執行都需要直譯；錯誤可能在執行時才被發現。
• 範例： Python, Ruby, PHP, JavaScript (早期)。

兩者差異總結：

特性	編譯式程式語言	直譯式程式語言
執行方式	預先編譯成機器碼或中間碼	執行時逐行直譯為機器碼並執行
執行速度	通常較快	通常較慢
跨平台性	較差，需為不同平台重新編譯	較好，只要有直譯器即可運行
除錯	編譯階段可發現較多錯誤，執行時錯誤較少	錯誤可能在執行時才暴露，除錯相對直接
開發週期	編譯步驟較長	修改後可立即執行，開發週期較短
輸出	可執行檔	原始碼（需搭配直譯器）

JavaScript 屬於何種？

JavaScript 傳統上被認為是直譯式語言。然而，現代的 JavaScript 引擎（如 V8，用於 Chrome 和 Node.js）採用了**即時編譯（Just-In-Time Compilation, JIT）*

本題主要考察對 IEEE 754 單倍精準浮點數表示法的理解，特別是指數部分的偏移（Bias）處理及其原因，以及採用該標準的整體意義。

IEEE 754 單倍精準數（Single Precision）格式：
一個 32 位元的浮點數，結構如下：

• Sign bit (S)： 1 位元，表示數字的符號（0 為正，1 為負）。
• Exponent (E)： 8 位元，表示指數。
• Fraction (F)： 23 位元，表示尾數（mantissa）的小數部分。

為何需要過剩 127（Excess 127）處理？

IEEE 754 標準規定，儲存在指數欄位（8 位元）的數字並非真實的指數值，而是經過「偏移（Bias）」處理後的值。對於單倍精準數，這個偏移值是 127。
也就是說，儲存在指數欄位的值 $E_{stored}$ 與真實指數值 $E_{real}$ 的關係是：
$E_{stored} = E_{real} + 127$
或者
$E_{real} = E_{stored} - 127$

原因：

1. 表示正負指數： 8 位元的指數欄位可以表示 $2^8 = 256$ 種不同的值（從 00000000 到 11111111）。如果直接使用有號數表示，例如用最高位元作為符號位，那麼就只能表示負指數或正指數，而無法同時表示正負指數。
2. 簡化比較： 將指數值加上一個固定的偏移量（Bias），使得所有指數值都變成非負數。這樣，在進行浮點數比較時，可以直接比較指數欄位的值，而無需額外處理符號。例如，比較 $1.0 \times 10^2$ 和 $5.0 \times 10^1$ 時，若指數直接儲存，則需要比較 $2$ 和 $1$。但如果儲存的是 $2+127=129$ 和 $1+127=128$，則可以直接比較 $129 > 128$。這大大簡化了硬體設計和數值比較邏輯。
3. 保留特殊值： 偏移量 127 使得 8 位元指數欄位的範圍（0 到 255）可以涵蓋絕大多數所需的指數範圍，同時也為表示特殊值（如無限大、NaN、零）保留了特定的指數值（全 0 和全 1）。

本題考察 SQL 的聚合函數（Aggregate Functions）、子查詢（Subqueries）或窗口函數（Window Functions）的使用，以及計算差異和排序。

假設 employee 表格結構如下：

ID	Name	Department	PhoneNumber	Salary
1	Alice	Sales	123-4567	50000
2	Bob	IT	876-5432	60000
3	Charlie	Sales	111-2222	55000
4	David	IT	333-4444	70000

目標：
輸出三欄：

1. 員工姓名 (Name)
2. 員工薪水與平均薪水的絕對差異 (ABS(Salary - AVG(Salary)))
3. 員工薪水與最高薪水的絕對差異 (ABS(Salary - MAX(Salary)))
   最後依 ID 排序。

方法一：使用子查詢

我們需要計算平均薪水和最高薪水。這可以使用子查詢來實現。

SELECT
    e.Name,
    ABS(e.Salary - (SELECT AVG(Salary) FROM employee)) AS SalaryVsAvgDiff,
    ABS(e.Salary - (SELECT MAX(Salary) FROM employee)) AS SalaryVsMaxDiff
FROM
    employee e
ORDER BY
    e.ID;

解釋：

• SELECT e.Name: 選擇員工的姓名。
• ABS(e.Salary - (SELECT AVG(Salary) FROM employee)) AS SalaryVsAvgDiff:
  • (SELECT AVG(Salary) FROM employee): 這是第一個子查詢，用於計算 employee 表中所有員工的平均薪水。
  • e.Salary - (subquery): 計算該員工的薪水與平均薪水之間的差值。
  • ABS(...): 使用 ABS() 函數取絕對值，確保差異是正數。
  • AS SalaryVsAvgDiff: 為此計算結果欄位命名。
• ABS(e.Salary - (SELECT MAX(Salary) FROM employee)) AS SalaryVsMaxDiff:

本題分為兩個部分：首先解釋 IaaS, PaaS, SaaS 的概念，其次是結合雲端運算與生成式 AI 的策略性看法。

IaaS, PaaS, SaaS 的概念：

這三個是雲端運算提供的不同服務模型，它們在抽象層級和使用者責任上有所不同。可以想像成租賃的層級：

1. IaaS (Infrastructure as a Service) - 基礎設施即服務：

   • 概念： 提供最基礎的 IT 基礎設施，包括伺服器（虛擬機）、儲存、網路資源。使用者租用這些資源，自行管理作業系統、中間件、應用程式和數據。
   • 類比： 租賃一塊土地和一些建築材料，你可以自己蓋房子（作業系統）、裝潢（應用程式）。
   • 責任劃分： 雲端供應商負責底層硬體（伺服器、網路、儲存），使用者負責作業系統往上的一切。
   • 範例： Amazon EC2, Google Compute Engine, Microsoft Azure Virtual Machines。

2. PaaS (Platform as a Service) - 平台即服務：

   • 概念： 在 IaaS 的基礎上，提供了一個開發和部署應用程式的平台。使用者不需要管理作業系統和底層基礎設施，只需專注於開發、部署和管理自己的應用程式。平台通常包含作業系統、資料庫、開發工具、中間件等。
   • 類比： 租賃一個已經蓋好、有水電系統的毛胚屋，你只需要進行室內裝潢（應用程式）和入住。
   • 責任劃分： 供應商負責硬體、作業系統、中間件；使用者負責應用程式和數據。
   • 範例： Google App Engine, Heroku, AWS Elastic Beanstalk, Microsoft Azure App Service。

3. SaaS (Software as a Service) - 軟體即服務：

   • 概念： 直接提供可供使用者使用的軟體應用程式。使用者只需透過網路存取軟體，無需關心任何底層基礎設施、平台或軟體本身的維護。
   • 類比： 直接租用一個已經裝潢好、家具齊全的公寓，你只需要搬進去住。
   • 責任劃分： 供應商負責所有層級（硬體、平台、軟體、數據管理）；使用者只需使用軟體。
   • 範例： Gmail, Microsoft 365, Salesforce, Dropbox。

新創公司 CTO 對雲端運算與生成式 AI 的綜整看法：

身為新創公司 CTO，我會將雲端運算視為我們快速成長和創新的基石，而生成式 AI 則是我們創造差異化競爭優勢和顛覆性產品的關鍵引擎。

1. 雲端運算作為賦能者：
   • 敏捷性與彈性： 雲端（尤其是 IaaS 和 PaaS）提供了按需擴展的基礎設施。新創公司初期資源有限，無需預先投入大量資本購買硬體，可根據業務發展靈活調整計算、儲存和網路資源，快速迭代產品。