111 年 國立成功大學生物醫學工程學系碩士班乙組《計算機概論》

本題主要在考察計算機網路、物件導向程式設計（OOP）以及資料壓縮等基礎觀念。

(a) Application Layer, Data-link Layer and Network Layer

這三個名詞是 OSI 模型（Open Systems Interconnection model）或 TCP/IP 模型中的網路層級。OSI 模型是一個七層的架構，而 TCP/IP 模型則簡化為四或五層。這裡描述的是 OSI 模型中的前三層（從上往下數）。

• Application Layer (應用層)：這是最頂層，直接與使用者應用程式互動。它提供了網路服務給應用程式，例如網頁瀏覽（HTTP）、檔案傳輸（FTP）、電子郵件（SMTP）等。此層的協議處理使用者與網路之間的介面。
• Data-link Layer (資料連結層)：位於實體層（Physical Layer）之上，網路層之下。它的主要職責是提供節點到節點（node-to-node）的可靠資料傳輸。它將來自網路層的資料封包（packets）分割成較小的訊框（frames），並在傳輸時加入錯誤偵測和糾正機制，以及 MAC 位址（Media Access Control address）來識別網路上的設備。常見的協定有 Ethernet、PPP 等。
• Network Layer (網路層)：位於資料連結層之上，傳輸層之下。它的主要功能是負責將資料封包從來源主機傳送到目的主機，可能需要經過多個中間路由器。此層處理邏輯定址（logical addressing），例如 IP 位址（IP address），並決定資料封包的最佳傳輸路徑（routing）。常見的協定有 IP（Internet Protocol）。

(b) Abstraction and Inheritance of OOP (Object-Oriented Programming)

Abstraction（抽象）和 Inheritance（繼承）是物件導向程式設計（OOP）的兩個核心概念。

本題考察對虛擬記憶體基本概念的理解，特別是在沒有分頁（paging）或分段（segmentation）機制下的限制。

題目描述的作業系統使用了虛擬記憶體，但有兩個關鍵限制：

1. 整個程式必須在實體記憶體中執行：這意味著雖然有虛擬記憶體（10 GB），但程式的全部內容在運行時必須完全載入到實體記憶體（4 GB）中。
2. 沒有分頁或分段（without paging or segmentation）：這表示作業系統無法將程式的一部分放在記憶體，另一部分放在硬碟（swap space），然後在需要時進行交換。所有程式的執行代碼和數據都必須一次性載入。

基於這些限制，我們可以得出以下結論：

• 實體記憶體大小：4 GB
• 程式大小：100 MB

首先，我們需要計算有多少個 100 MB 的程式可以同時載入到 4 GB 的實體記憶體中。
我們需要統一單位。1 GB = 1024 MB。
所以，實體記憶體大小 = $4 \text{ GB} \times 1024 \text{ MB/GB} = 4096 \text{ MB}$。

同時執行的程式數量 = $\frac{\text{實體記憶體大小}}{\text{單一程式大小}}$
同時執行的程式數量 = $\frac{4096 \text{ MB}}{100 \text{ MB}} = 40.96$

由於程式數量必須是整數，最多只能運行 40 個完整的程式。

接下來，計算有多少記憶體被使用，以及有多少記憶體（或硬碟空間，因為虛擬記憶體的概念）未使用。

• 已使用的記憶體：$40 \text{ 個程式} \times 100 \text{ MB/程式} = 4000 \text{ MB}$。
• 剩餘的實體記憶體：$4096 \text{ MB} - 4000 \text{ MB} = 96 \text{ MB}$。

關於「硬碟（disk）」的部分：

題目提到「虛擬記憶體是 10 GB」，而「實體記憶體是 4 GB」。在典型的虛擬記憶體系統中，當實體記憶體不足時，未使用的部分會被儲存在硬碟上的交換空間（swap space）。

核心觀念

Selection sort（選擇排序）的作法是：

1. 將序列分成「已排序子串列」與「未排序子串列」。
2. 每一回合從未排序子串列找出最小值。
3. 將該最小值與未排序子串列的第一個元素交換。
4. 已排序區域向右擴大一格，重複上述步驟。

題目特別要求使用一個 subalgorithm，因此需將「尋找未排序子串列中的最小整數」獨立寫成子演算法。

假設輸入陣列為 $A[1 \dots n]$，採用由小到大排序。

---

解題方法

在第 $i$ 回合開始時：

• $A[1 \dots i-1]$ 已完成排序；
• $A[i \dots n]$ 尚未排序；
• 從 $A[i \dots n]$ 找出最小元素的位置；
• 將它與 $A[i]$ 交換。

當 $i$ 從 $1$ 執行到 $n-1$ 時，最後一個元素自然會位於正確位置，因此不需再處理第 $n$ 個位置。

---

子演算法：尋找最小元素的位置

子演算法接收陣列 $A$、搜尋起點 $first$ 與搜尋終點 $last$，回傳最小元素的索引。

Subalgorithm FindSmallestIndex(A, first, last)
    minIndex ← first

    for j ← first + 1 to last do
        if A[j] < A[minIndex] then
            minIndex ← j
        end if
    end for

    return minIndex
End Subalgorithm

子演算法說明

• 先假設 $A[first]$ 是最小值。
• 依序檢查 $A[first+1]$ 到 $A[last]$。
• 若發現更小的元素，就更新 $minIndex$。
• 掃描結束時，$minIndex$ 即為最小元素的位置。

使用嚴格小於號 $<$ 時，遇到相同元素不會更新索引，這可避免不必要的交換。

---

Selection Sort 主演算法

Algorithm SelectionSort(A, n)
    for i ← 1 to n - 1 do
        minIndex ← FindSmallestIndex(A, i, n)

        if minIndex ≠ i then
            swap A[i] and A[minIndex]
        end if
    end for
End Algorithm

其中：

swap A[i] and A[minIndex]

可展開為：

temp ← A[i]
A[i] ← A[minIndex]
A[minIndex] ← temp

---

正確性說明

以迴圈不變量說明：

在第 $i$ 回合開始前，$A[1 \dots i-1]$ 已經按照非遞減順序排列，且其中每個元素都不大於未排序區域 $A[i \dots n]$ 的元素。

第 $i$ 回合中，FindSmallestIndex 會找出 $A[i \dots n]$ 的最小元素，並將它交換至 $A[i]$。因此：

本題要求設計一個結合人工智慧（AI）、無線傳輸，用於偵測違反防疫規定行為或促進感染控制的系統，並解釋其原理、資料傳輸與安全機制。這是一個跨領域的應用題，需要結合計算機視覺、機器學習、無線通訊和資訊安全知識。

核心觀念：

1. AI 於行為偵測：利用電腦視覺（Computer Vision）和機器學習（Machine Learning）技術，分析影像或感測器數據，識別特定行為模式。
2. 無線傳輸：將收集到的數據或偵測結果，透過無線網路傳輸到後端伺服器進行進一步處理或通知。
3. 防疫應用：將技術應用於監測群眾是否遵守防疫規定，例如戴口罩、保持社交距離。
4. 資料安全：確保傳輸中的資料不被竊取或篡改，以及儲存的資料受到保護。

建議方法：基於電腦視覺的行為偵測系統

1. 操作原理 (Operating Principle)

• 資料收集：
  • 在公共場所（如車站、商場、辦公室入口、學校）部署攝影機。這些攝影機將持續捕捉人流的影像。
  • 攝影機可以配備紅外線感測器，用於非接觸式體溫量測。
• AI 影像分析 (電腦視覺與機器學習)：
  • 人臉偵測與口罩偵測：AI 模型（如基於卷積神經網路 CNN 的模型，例如 YOLO, SSD, Faster R-CNN 等）首先偵測影像中的人臉。接著，針對偵測到的人臉，模型會判斷是否佩戴了口罩。這可以透過訓練模型識別口罩的特徵來實現。
  • 社交距離偵測：透過偵測影像中不同人物的頭部或身體中心點，計算他們之間的距離。如果距離小於預設的安全閾值（例如 1.5 或 2 公尺），則判定為違反社交距離規定。這通常需要進行深度估計或利用已知攝像機參數進行 2D 投影分析。
  • 體溫異常偵測：若攝影機配備紅外線功能，AI 模型可以從熱影像中提取體溫數據，並與正常體溫範圍進行比較。若體溫超出預設上限，則標記為異常。
  • 行為識別：更進階的 AI 模型可以學習偵測其他違反防疫規定的行為，例如在不適當的場合聚集、不正確的洗手動作等。
• 事件觸發與通知：
  • 當 AI 系統偵測到違反規定（如未戴口罩、距離過近、體溫過高等）的行為時，會產生一個「事件」。
  • 這些事件會被記錄下來，並根據預設規則觸發相應的操作，例如：
    • 向現場工作人員發送警報通知。
    • 向違反規定的個人發送提示訊息（若系統有與個人身份綁定）。
    • 將異常數據記錄到資料庫，用於後續的統計分析和管理。

2. 資料傳輸 (Data Transmission)

• 無線傳輸模式：
  • Wi-Fi：攝影機和感測器可以連接到現有的 Wi-Fi 網路，將數據發送到本地網路或雲端伺服器。
  • 蜂巢式網路 (4G/5G)：對於沒有 Wi-Fi 覆蓋的區域，可以使用 SIM 卡透過 4G 或 5G 網路進行傳輸。5G 的低延遲和高頻寬特性尤其適合即時影像串流和大量數據傳輸。
  • 藍牙 (Bluetooth) / 低功耗藍牙 (BLE)：適用於較小範圍內的設備連接，例如將體溫計等穿戴式裝置的數據傳輸到附近的閘道器（gateway）。
  • LoRa / NB-IoT：對於低功耗、長距離、小數據量的傳輸需求，這些物聯網（IoT）專用無線技術也是可行的選項。
• 傳輸內容：
  • 原始影像/影片串流：直接將攝影機拍攝的影像串流傳輸到後端伺服器進行 AI 分析。

本題要求撰寫一個 C++ 函式，名為 smaller，它接受兩個輸入值 A 和 B，並將它們中較小的值傳遞給一個名為 S 的輸出參數。這個函式應該能夠讓主程式（main program）獲取到較小的值。

核心觀念：

• 函式定義：如何在 C++ 中定義一個函式，包括返回類型、函式名稱、參數列表。
• 參數傳遞：
  • 傳值 (Pass by Value)：函式接收參數的副本。對參數的修改不會影響到原始變數。
  • 傳址 (Pass by Reference)：函式接收參數的記憶體地址。對參數的修改會直接影響到原始變數。
  • 傳指標 (Pass by Pointer)：函式接收參數的指標（記憶體地址）。通過指標可以間接訪問和修改原始變數。
• 條件判斷：使用 if 語句來比較 A 和 B 的大小。

函式設計考量：

題目要求 S 是「輸出值」，並且「被傳遞到主程式」。這意味著 S 必須能夠被 smaller 函式修改，並且主程式能夠讀取到這個修改後的值。最適合實現這一點的參數傳遞方式是「傳址」（pass by reference）或「傳指標」（pass by pointer）。傳址在 C++ 中通常更為簡潔和常用。

方法一：使用傳址 (Pass by Reference)

這種方法最符合「S 將被傳遞到主程式」的意圖，因為 S 在主程式中已經存在，而函式修改的是這個主程式中的 S。

#include <iostream> // For input/output operations in main, if needed for testing

// Function to find the smaller of two values and store it in S
// A and B are input values
// S is an output parameter passed by reference
void smaller(int A, int B, int& S) {
    if (A < B) {
        S = A; // Assign A to S if A is smaller
    } else {
        S = B; // Assign B to S if B is smaller or equal to A
    }
}

/*
// Example of how to use this function in main:
int main() {
    int num1 = 10;
    int num2 = 5;
    int result; // This is S

    smaller(num1, num2, result); // Call the function

    std::cout << "The smaller value is: " << result << std::endl; // Output will be 5

    num1 = 20;
    num2 = 30;
    smaller(num1, num2, result);
    std::cout << "The smaller value is: " << result << std::endl; // Output will be 20

    return 0;
}
*/

解釋：

• void smaller(int A, int B, int& S)：
  • void 表示此函式不返回任何值（結果通過參數 S 傳回）。
  • int A, int B：A 和 B 是輸入參數，以傳值方式傳遞。它們的原始值在 main 函式中不會被 smaller 函式改變。
  • int& S：S 是輸出參數，以「傳址」（pass by reference）方式傳遞。& 符號表示 S 是對另一個 int 變數的引用。在 main 函式中，當我們呼叫 smaller(num1, num2, result) 時，S 就會指向 main 中的 result 變數。因此，在 smaller 函式內部對 S 的任何修改，都會直接改變 main 中的 result 變數。
• if (A < B)：比較 A 和 B 的值。
• S = A; 或 S = B;：將較小的值賦給 S。由於 S 是傳址，這會修改 main 中對應的變數。

方法二：使用傳指標 (Pass by Pointer)

這是另一種常見的方式來實現輸出參數。

本題要求繪製一個使用鏈結串列（Linked List）結構來儲存學生記錄的圖示，其中每個學生記錄包含 id、name 和 grade 三個欄位。

核心觀念：

• 鏈結串列 (Linked List)：一種線性資料結構，其中元素（節點）並非儲存在連續的記憶體位置，而是透過指標（或稱鏈結）串聯起來。每個節點通常包含兩部分：資料（data）和指向下一個節點的指標（next pointer）。
• 節點結構 (Node Structure)：鏈結串列的基本單元。對於本題，每個節點代表一個學生記錄，其資料部分應包含 id、name 和 grade。
• 圖示繪製：清晰地展示節點的結構以及它們如何透過指標連接。

節點結構設計：

對於一個學生記錄，我們需要一個節點（Node）來儲存其資訊。該節點結構應包含：

1. Data Part：
   • id (例如：整數或字串)
   • name (字串)
   • grade (例如：浮點數或整數)
2. Next Pointer：指向下一個學生記錄節點的指標。

圖示繪製：

我們可以用方塊來表示節點。每個方塊可以被分割成兩個主要區域：左邊或上面是資料欄位 (id, name, grade)，右邊或下面是 next 指標。鏈結串列的開頭通常有一個指向第一個節點的指標，稱為 head。鏈結串列的最後一個節點的 next 指標會指向 NULL (或 nullptr)，表示鏈結的結束。

以下是圖示的文字描述和簡易表示：

+-------+------+-------+     +-------+------+-------+     +-------+------+-------+
|       |      |       | --> |       |      |       | --> |       |      |       | --> NULL
|  id   | name | grade |     |  id   | name | grade |     |  id   | name | grade |
|       |      |       |     |       |      |       |     |       |      |       |
+-------+------+-------+     +-------+------+-------+     +-------+------+-------+
  Node 1        Node 2        Node 3

更詳細的節點內部結構表示：

+-------+-----------------+-------+----------+
|       |                 |       |          |
|  id   |      name       | grade |  next    |
|       |                 |       |          |
+-------+-----------------+-------+----------+

文字說明圖示：

1. head 指標：

   • 在圖的開頭，有一個標示為 head 的指標，它指向第一個節點（Node 1）。
   • head --> [Node 1]

2. 第一個節點 (Node 1)：

   • 包含學生 1 的 id、name 和 grade。
   • 其 next 指標指向第二個節點（Node 2）。
   • [ Node 1 {id, name, grade} ] --> [ Node 2 ]

3. 第二個節點 (Node 2)：

   • 包含學生 2 的 id、name 和 grade。
   • 其 next 指標指向第三個節點（Node 3）。
   • [ Node 2 {id, name, grade} ] --> [ Node 3 ]

4. 第三個節點 (Node 3)：

   • 包含學生 3 的 id、name 和 grade。
   • 其 next 指標指向 NULL (或 nullptr)，表示這是鏈結串列的最後一個節點。
   • [ Node 3 {id, name, grade} ] --> NULL

整合起來的圖示：

核心觀念

Binary search（二分搜尋）用於「已排序」的一維陣列。每次比較搜尋值 $x$ 與目前範圍的中間元素，排除不可能包含 $x$ 的一半範圍。

假設陣列 $A[0 \ldots N-1]$ 依遞增順序排列，搜尋範圍以：

• low：目前範圍左界
• high：目前範圍右界
• mid：目前範圍中間位置

表示。中間位置計算為：

$$mid = low + \left\lfloor \frac{high-low}{2} \right\rfloor$$

解題方法

每一輪依序處理：

1. 若 low > high，代表搜尋範圍已經空掉，陣列中不存在 $x$。

2. 計算中間位置 mid。

3. 若 $A[mid]=x$，搜尋成功，回傳 mid。

4. 若 $A[mid]<x$，因陣列遞增，mid 左側及 mid 本身都不可能是答案，令：

   low = mid + 1

5. 若 $A[mid]>x$，捨棄右側範圍，令：

   high = mid - 1

標準偽程式碼

BinarySearch(A, N, x):
    low ← 0
    high ← N - 1

    while low ≤ high:
        mid ← low + floor((high - low) / 2)

        if A[mid] = x:
            return mid

        else if A[mid] < x:
            low ← mid + 1

        else:
            high ← mid - 1

    return NOT_FOUND

本題考察非對稱式密碼學（Asymmetric-key Cryptography），也稱為公開金鑰密碼學（Public-key Cryptography），關於金鑰的使用以及其在處理大量訊息時的適用性。

核心觀念：

• 非對稱式密碼學：使用一對金鑰：一個公開金鑰（public key）和一個私有金鑰（private key）。這兩個金鑰是數學上相關聯的，但從一個金鑰無法輕易推算出另一個。
• 金鑰用途：
  • 加密 (Encryption)：通常使用接收者的公開金鑰來加密訊息。
  • 解密 (Decryption)：必須使用接收者的私有金鑰來解密用其公開金鑰加密的訊息。
  • 數位簽章 (Digital Signature)：
    • 簽署：使用寄件者的私有金鑰來「簽署」一份訊息（或其雜湊值），以驗證寄件者身份和訊息完整性。
    • 驗證：任何人都可以使用寄件者的公開金鑰來「驗證」該簽章。
• 效率與適用性：非對稱式密碼學的運算通常比對稱式密碼學（Symmetric-key Cryptography）複雜且耗時，因此在處理大量數據時效率較低。

回答問題：

1. 解密時使用哪個金鑰？
   在非對稱式密碼學中，如果訊息是使用接收者的公開金鑰進行加密的，那麼接收者必須使用自己的私有金鑰 (private key) 來進行解密。

   • 情境一：機密性 (Confidentiality)

     • 寄件者 A 想要傳送一個機密訊息給接收者 B。
     • A 使用 B 的公開金鑰加密訊息。
     • B 收到加密訊息後，使用自己的私有金鑰解密訊息。
     • 只有擁有 B 的私有金鑰的人才能解密。

   • 情境二：身份驗證與完整性 (Authentication & Integrity) - 數位簽章

     • 寄件者 A 想要證明訊息是他發出的且未被篡改。
     • A 使用自己的私有金鑰對訊息（通常是訊息的雜湊值）進行「簽章」。
     • 接收者 B 收到訊息和簽章後，使用 A 的公開金鑰來驗證簽章。
     • 如果驗證成功，則 B 可以確信訊息確實來自 A，且在傳輸過程中未被修改。

   因此，無論是為了確保機密性（解密加密訊息）還是驗證數位簽章（驗證簽章），解密或驗證過程都涉及到與「接收者」或「簽署者」的私有金鑰相關的操作（加密時用公開金鑰，解密時用私有金鑰；簽署時用私有金鑰，驗證時用公開金鑰）。