108 年 國立臺灣大學工程科學及海洋工程學系碩士班丁組《計算機概論（A）》

核心觀念

本題考查「圓形霍夫轉換（Circular Hough Transform）」。

圓的方程式為：

$$(x-a)^2+(y-b)^2=r^2$$

其中：

• $(a,b)$：圓心
• $r$：半徑
• 題目要求 $100\le r\le300$

對影像中的每個邊界點 $(x,y)$，若假設半徑為 $r$，該點所對應的圓心必位於：

$$a=x-r\cos\theta,\qquad b=y-r\sin\theta$$

將所有邊界點對各種半徑產生的圓心位置累積投票，投票數最高的位置即為候選圓心。

本題影像大小為 $1000\times1000$，白色像素值為 $1$，黑色像素值為 $0$。先找出白色區域與黑色背景交界的邊界，再進行圓形霍夫轉換。

解題方法

1. 擷取圓形邊界

若白色像素的上、下、左、右鄰居中至少有一個黑色像素，便將它視為邊界點。

這樣可以排除圓內部大量不必要的像素，使計算量由整張影像的像素數量降為邊界點數量。

2. 估計邊界方向

在邊界點計算影像梯度：

$$g_x=I(x+1,y)-I(x-1,y)$$ $$g_y=I(x,y+1)-I(x,y-1)$$

梯度方向近似為圓的半徑方向。將單位方向向量記為：

$$\mathbf n=\frac{(g_x,g_y)}{\sqrt{g_x^2+g_y^2}}$$

因此半徑為 $r$ 時，圓心候選為：

$$(a,b)=(x,y)+r\mathbf n$$

以及

$$(a,b)=(x,y)-r\mathbf n$$

同時使用正、負兩個方向，可避免受到梯度方向朝內或朝外的影響。

3. 累積投票

對每個半徑 $r=100,101,\ldots,300$，建立一個 $1000\times1000$ 的投票陣列 accumulator。

每個邊界點針對目前半徑投票給兩個圓心候選位置：

(x + r * nx, y + r * ny)
(x - r * nx, y - r * ny)

實際座標四捨五入為整數，落在影像範圍內才進行投票。

4. 找出局部最大值

同一個圓會在附近產生許多高票數位置，因此不能單純列出所有超過門檻的點。

處理方式如下：

1. 只保留投票數超過門檻的點。
2. 只保留局部最大值。
3. 依投票數由高至低排序。
4. 若新候選圓與已接受的圓心距離太近、半徑也相近，則視為同一個圓並刪除。

Python 程式

本題要求找出兩個字串的最長共同子序列（Longest Common Subsequence, LCS），並輸出該子序列及其長度。這是動態規劃（Dynamic Programming, DP）的經典問題。

核心觀念： 動態規劃。

解題思路：

我們定義一個二維陣列 dp[i][j]，表示字串 str1 的前 i 個字元和字串 str2 的前 j 個字元之間的最長共同子序列的長度。

1. 狀態轉移方程：

   • 如果 str1[i-1] == str2[j-1]（注意：字串索引從 0 開始，DP 陣列索引從 1 開始，所以這裡比較的是第 i 個字元和第 j 個字元，對應字串索引為 i-1 和 j-1），表示這兩個字元相同，那麼它們可以構成 LCS 的一部分。此時，LCS 的長度為前 i-1 個字元和前 j-1 個字元的 LCS 長度加 1。
     dp[i][j] = dp[i-1][j-1] + 1
   • 如果 str1[i-1] != str2[j-1]，表示這兩個字元不同，那麼 LCS 的長度取決於以下兩種情況中的較大值：
     • str1 的前 i-1 個字元與 str2 的前 j 個字元的 LCS 長度 (dp[i-1][j])。
     • str1 的前 i 個字元與 str2 的前 j-1 個字元的 LCS 長度 (dp[i][j-1])。
       dp[i][j] = max(dp[i-1][j], dp[i][j-1])

2. 初始條件：

   • 當 i = 0 或 j = 0 時，表示其中一個字串為空，LCS 的長度為 0。
   • dp[0][j] = 0 對於所有 j。
   • dp[i][0] = 0 對於所有 i。

3. 計算 LCS 長度：

   • 建立一個大小為 (len1 + 1) x (len2 + 1) 的 DP 陣列，其中 len1 和 len2 分別是 str1 和 str2 的長度。
   • 根據上述狀態轉移方程填滿 DP 陣列。
   • 最終的 LCS 長度為 dp[len1][len2]。

4. 重建 LCS 字串：

   • 在計算出 LCS 長度後，我們可以從 dp[len1][len2] 開始，回溯 DP 陣列來重建 LCS 字串。
   • 從 (i, j) = (len1, len2) 開始：
     • 如果 str1[i-1] == str2[j-1]，說明這個字元是 LCS 的一部分。將 str1[i-1] (或 str2[j-1]) 添加到 LCS 字串的前面，然後移動到 (i-1, j-1)。
     • 如果 str1[i-1] != str2[j-1]，則比較 dp[i-1][j] 和 dp[i][j-1]。
       • 如果 dp[i-1][j] > dp[i][j-1]，說明 LCS 是來自 str1 的前 i-1 個字元和 str2 的前 j 個字元，所以移動到 (i-1, j)。
       • 否則（dp[i][j-1] >= dp[i-1][j]），說明 LCS 是來自 str1 的前 i 個字元和 str2 的前 j-1 個字元，所以移動到 (i, j-1)。
   • 重複這個過程，直到 i 或 j 變為 0。
   • 由於我們是從後往前構建 LCS 字串，最後需要將其反轉。

程式碼實現 (Python)：

核心觀念

Armstrong number（阿姆斯壯數）是指一個有 $n$ 位數的整數，其各位數字的 $n$ 次方總和等於原數：

$$x=d_1^n+d_2^n+\cdots+d_n^n$$

其中 $d_1,d_2,\ldots,d_n$ 為整數 $x$ 的各位數字。

例如：

• $153$ 是三位數，且

$$1^3+5^3+3^3=1+125+27=153$$

• $1634$ 是四位數，且

$$1^4+6^4+3^4+4^4=1634$$

題目要求列出 $1$ 到 $1{,}000{,}000$ 之間所有符合條件的數字，因此必須：

1. 逐一檢查範圍內的整數。
2. 計算該數的位數 $n$。
3. 取出每一位數字。
4. 計算各位數字的 $n$ 次方總和。
5. 比較總和是否等於原數。

解題方法

對每個整數 $x$，先保留原始數值，再使用整數除法與取餘數逐位拆解：

• temp % 10 取得最右側數字。
• temp // 10 移除最右側數字。
• 重複執行直到 temp 變成 $0$。

若原數為 $x$，位數為 $n$，則判斷式為：

$$\sum \left(\text{每一位數字}\right)^n=x$$

位數可透過字串長度取得，程式邏輯清楚且適合本題範圍。

關鍵程式碼（Python）

def is_armstrong(number):
    # 計算 number 的位數
    digits = len(str(number))

    total = 0
    temp = number

    # 逐位取出數字並計算 digits 次方
    while temp > 0:
        digit = temp % 10
        total += digit ** digits
        temp //= 10

    return total == number


for number in range(1, 1_000_001):
    if is_armstrong(number):
        print(number)

程式執行流程

以 $153$ 為例：

本題考查插入排序（Insertion Sort）的相關知識，包括程式碼實現、時間複雜度分析以及其在特定情況下的優勢。

核心觀念： 排序演算法，插入排序。

Part (a): Insertion Sort 程式碼實現

插入排序的基本思想是：將待排序的數組分成已排序和未排序兩部分，每次從未排序部分取出一個元素，插入到已排序部分的正確位置，直到所有元素都插入到已排序部分。

思路：

1. 假設數組的前 i 個元素（索引 0 到 i-1）已經排序好。
2. 取出第 i 個元素（current_element）。
3. 將 current_element 與已排序部分的元素從後往前比較。
4. 如果 current_element 小於已排序部分的元素，則將該已排序元素向後移動一位，為 current_element 騰出空間。
5. 重複步驟 4，直到找到一個比 current_element 小或等於的元素，或者到達已排序部分的開頭。
6. 將 current_element 插入到正確的位置。
7. 重複步驟 2-6，直到所有元素都排序完成。

程式碼實現 (Python)：

def insertion_sort(arr: list[int]) -> list[int]:
    """
    Sorts an array of integers in ascending order using Insertion Sort.

    Args:
        arr: The list of integers to sort.

    Returns:
        The sorted list.
    """
    n = len(arr)
    # Traverse through 1 to n-1 (the second element to the last)
    for i in range(1, n):
        current_element = arr[i]
        j = i - 1  # Start comparing with the element before current_element

        # Move elements of arr[0..i-1], that are greater than current_element,
        # to one position ahead of their current position
        while j >= 0 and current_element < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        
        # Place the current_element at its correct position in the sorted subarray
        arr[j + 1] = current_element
        
    return arr

# Example usage:
# arr = [12, 11, 13, 5, 6]
# sorted_arr = insertion_sort(arr)
# print("Sorted array is:", sorted_arr) # Expected: [5, 6, 11, 12, 13]

Part (b): Time Complexities

本題為名詞解釋題，涵蓋作業系統（死結）、電腦架構（I/O、RISC vs CISC、虛擬記憶體）、以及電腦組織（浮點數表示）等多個計算機科學領域的基礎概念。

a. 死結 (Deadlock)

• 定義： 死結是指在一組進程（或線程）中，每個進程都無限期地等待另一個進程釋放它所持有的資源，而該進程又在等待其他進程釋放資源，從而導致所有進程都無法繼續執行。這形成了一個循環等待的僵局。

• 必要條件 (Coffman conditions)： 發生死結的四個必要條件是：

  1. 互斥 (Mutual Exclusion)： 至少有一種資源必須是非共享的，即一次只能被一個進程使用。
  2. 持有並等待 (Hold and Wait)： 一個進程至少持有一個資源，並且正在等待獲取其他進程當前持有的額外資源。
  3. 非搶占 (No Preemption)： 資源不能被強制從持有它的進程中搶占；資源只能在持有它的進程主動釋放後才能被其他進程獲取。
  4. 循環等待 (Circular Wait)： 存在一個進程集合 $\{P_0, P_1, ..., P_n\}$，其中 $P_0$ 在等待 $P_1$ 持有的資源，$P_1$ 在等待 $P_2$ 持有的資源，...，$P_{n-1}$ 在等待 $P_n$ 持有的資源，而 $P_n$ 在等待 $P_0$ 持有的資源。

• 處理死結的方法：

  1. 死結預防 (Deadlock Prevention)： 確保死結的四個必要條件之一不成立。
     • 破壞互斥： 不適用於所有資源（例如，列印機必須是互斥的）。
     • 破壞持有並等待： 要求進程在開始執行前一次性申請所有需要的資源；或者，如果進程持有資源時需要新資源，則必須先釋放所有已持有的資源。
     • 破壞非搶占： 如果一個進程請求的資源不可用，則釋放它目前持有的所有資源。
     • 破壞循環等待： 對資源進行排序，要求進程按順序申請資源（例如，總是先申請編號較小的資源，再申請編號較大的資源）。
  2. 死結避免 (Deadlock Avoidance)： 在資源分配時，通過算法（如銀行家算法 Banker's Algorithm）來動態地檢查資源分配是否會導致死結，如果會，則不進行分配。
  3. 死結檢測與恢復 (Deadlock Detection and Recovery)：
     • 檢測： 系統定期運行死結檢測算法（如通過資源分配圖）。
     • 恢復：
       • 終止進程： 終止一個或多個進程，直到死結被解除。
       • 資源搶占： 從一個或多個進程中搶占資源，並將其分配給其他進程，直到死結被解除。這需要選擇合適的進程和資源，並考慮回滾機制。

b. 隔離 I/O (Isolated I/O) 與記憶體映射 I/O (Memory-Mapped I/O)

這兩種方式是 CPU 與周邊設備（I/O 設備）通信的兩種不同機制。

• 隔離 I/O (Isolated I/O / Port-Mapped I/O)：

  • 機制： 系統為 I/O 設備分配獨立的 I/O 地址空間，與主記憶體地址空間是分開的。
  • 指令： CPU 使用專門的 I/O 指令（如 IN 和 OUT 指令）來讀寫 I/O 設備的端口。
  • 地址空間： I/O 地址空間通常比記憶體地址空間小。
  • 優點： I/O 指令與記憶體訪問指令是獨立的，CPU 設計可以更清晰。
  • 缺點： 需要專門的 I/O 指令，可能不如記憶體訪問指令靈活；I/O 地址空間有限。
  • 常見於： x86 架構。

• 記憶體映射 I/O (Memory-Mapped I/O, MMIO)：

  • 機制： I/O 設備的控制寄存器和數據緩衝區被映射到主記憶體地址空間的某個範圍內。
  • 指令： CPU 使用與訪問記憶體相同的指令（如 MOV 指令）來讀寫 I/O 設備的寄存器。
  • 地址空間： I/O 設備佔用主記憶體的一部分地址空間。
  • 優點： 簡化了 CPU 指令集，所有記憶體訪問指令都可以用於 I/O；I/O 設備的地址空間可以擴展到記憶體地址空間的大小；更易於編譯器和高級語言處理。
  • 缺點： 減少了可用於主記憶體的地址空間；I/O 操作可能受記憶體緩衝、快取等影響，需要額外的處理。
  • 常見於： ARM 架構、PowerPC 架構以及現代處理器中的許多週邊。

主要區別：

• 地址空間： 隔離 I/O 有獨立的 I/O 地址空間；記憶體映射 I/O 使用主記憶體地址空間。
• CPU 指令： 隔離 I/O 使用專門的 I/O 指令；記憶體映射 I/O 使用標準的記憶體訪問指令。

c. 精簡指令集計算機 (RISC)

• 定義： RISC (Reduced Instruction Set Computer) 是一種計算機架構設計哲學，其目標是設計一個指令集，其中包含大量簡單、高效且執行速度快的指令。這些指令的執行時間通常是固定的（例如一個時鐘週期）。

• RISC 的特點：

  • 指令集小且簡單： 指令數量少，格式統一，長度固定。
  • 指令執行速度快： 大多數指令可以在一個時鐘週期內完成。
  • 大量使用暫存器 (Registers)： 為了減少對記憶體的訪問，RISC 架構通常擁有大量的通用暫存器。
  • 載入/儲存架構 (Load/Store Architecture)： 只有 LOAD 和 STORE 指令可以訪問記憶體，所有其他運算指令都在暫存器之間進行。
  • 硬體實現複雜度較低： 指令集簡單使得 CPU 設計更易於實現，可以將更多晶片面積用於暫存器或快取。

• CISC (Complex Instruction Set Computer)： 與 RISC 相反，CISC 擁有龐大且複雜的指令集，某些指令可以執行複雜的多步操作（如直接從記憶體讀取、運算、再寫回記憶體）。

• RISC 程式與 CISC 程式的長度比較：

  • CISC 程式通常會更短。 這是因為 CISC 指令集包含許多複雜的指令，一條 CISC 指令可以完成 RISC 中多條指令才能完成的工作。例如，CISC 可能有一條指令用於「從記憶體載入、加一、再儲存回記憶體」，而 RISC 則需要 LOAD、ADD、STORE 三條指令。

• RISC 程式為何能勝過 CISC 程式 (Why RISC outperforms CISC)：