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

此題考驗對搜尋演算法中，啟發式函數 (Heuristic Function) 的設計以及搜尋樹 (Search Tree) 的建構能力。8-Puzzle 是一個經典的搜尋問題，通常用來評估不同搜尋演算法的效率。

啟發式函數設計 (Heuristic Method Design):

啟發式函數 $h(n)$ 的目的是評估從當前狀態 $n$ 到達目標狀態的「預估」成本。一個好的啟發式函數應該是「可接受的」(admissible)，也就是說，它預估的成本永遠不會高於實際到達目標所需的最小成本。對於 8-Puzzle，常見的啟發式函數有：

1. 錯位圖塊數 (Number of Misplaced Tiles): 計算有多少個圖塊不在其目標位置。

   • 優點：計算簡單，且是可接受的。
   • 缺點：對圖塊的位置資訊利用較少。

2. 曼哈頓距離 (Manhattan Distance): 計算每個圖塊從其當前位置移動到其目標位置所需的「曼哈頓距離」（即只能水平或垂直移動的步數總和）。

   • 優點：比錯位圖塊數更精確，利用了圖塊的實際位置資訊，通常能更快找到解。也是可接受的。
   • 缺點：計算相對複雜一點。

我們選擇 曼哈頓距離 作為啟發式函數，因為它通常能提供更好的搜尋效率。

計算曼哈頓距離的步驟：
對於每個不在目標位置的圖塊，計算它從當前位置到目標位置所需的水平移動步數加上垂直移動步數。將所有圖塊的曼哈頓距離加總，即為該狀態的曼哈頓距離啟發式值。

目標狀態圖塊位置：

• 1: (0,0)
• 2: (0,1)
• 3: (0,2)
• 4: (1,0)
• 5: (1,1)
• 6: (1,2)
• 7: (2,0)
• 8: (2,1)
• 空白: (1,2) (在這個範例中，目標狀態的空白在 (1,2) 位置，但通常題目會給定一個明確的目標狀態，此處題目給的目標狀態圖塊順序似乎與常見的 8-puzzle 不同，請以題目給的目標狀態為準。)

題目給的目標狀態圖塊位置：

• 1: (0,0)
• 2: (0,1)
• 3: (0,2)
• 4: (1,2)
• 5: (1,1)
• 6: (2,0)
• 7: (2,1)
• 8: (2,2)
• 空白: (1,0)

初始狀態分析 (Initial State):

• 圖塊 4: 當前 (0,0)，目標 (1,2)。曼哈頓距離 = |0-1| + |0-2| = 1 + 2 = 3
• 圖塊 1: 當前 (0,1)，目標 (0,0)。曼哈頓距離 = |0-0| + |1-0| = 0 + 1 = 1
• 圖塊 3: 當前 (0,2)，目標 (0,2)。曼哈頓距離 = 0
• 圖塊 7: 當前 (1,0)，目標 (2,1)。曼哈頓距離 = |1-2| + |0-1| = 1 + 1 = 2
• 圖塊 2: 當前 (1,1)，目標 (0,1)。曼哈頓距離 = |1-0| + |1-1| = 1 + 0 = 1
• 圖塊 6: 當前 (1,2)，目標 (1,2)。曼哈頓距離 = 0
• 圖塊 5: 當前 (2,0)，目標 (1,1)。曼哈頓距離 = |2-1| + |0-1| = 1 + 1 = 2
• 圖塊 8: 當前 (2,1)，目標 (2,2)。曼哈頓距離 = |2-2| + |1-2| = 0 + 1 = 1
• 空白: 當前 (2,2)，目標 (1,0)。(空白格的移動也計入，但通常我們計算圖塊的曼哈頓距離，空白格的移動是隱含的。)

初始狀態的曼哈頓距離啟發式值 $h(\text{initial}) = 3 + 1 + 0 + 2 + 1 + 0 + 2 + 1 = 10$

搜尋樹建構 (Search Tree):

搜尋樹的根節點是初始狀態。每個節點代表一個遊戲狀態，邊代表一個合法的移動（將圖塊移入空白格）。我們可以使用 A* 搜尋演算法來建構搜尋樹，其中節點的評估值 $f(n) = g(n) + h(n)$，其中 $g(n)$ 是從初始狀態到節點 $n$ 的實際成本（移動步數），$h(n)$ 是啟發式估計成本。

由於題目要求「設計一個啟發式方法和一個搜尋樹」，通常只需要展示搜尋樹的局部結構，說明如何從初始狀態開始展開。

搜尋樹的表示：

• 根節點: 初始狀態 (4,1,3; 7,2,6; 5,8,_)，$g=0, h=10, f=10$。
• 展開根節點： 考慮所有可以移動到空白格的圖塊。空白格在 (2,2)。
  • 移動圖塊 6 (右上)：狀態 (4,1,3; 7,2,_,; 5,8,6)。

此題考驗對深度優先搜尋 (Depth-First Search, DFS) 演算法的理解與應用，以及如何表示搜尋過程中的樹狀結構。

核心觀念：
深度優先搜尋是一種圖形或樹形結構的遍歷演算法。它從起始節點開始，沿著某條路徑盡可能深地探索，直到達到葉節點或無法再前進為止。然後，它回溯到最近的未訪問節點，並從那裡開始探索另一條路徑。

問題分析：
題目提供了一個圖形結構，其中標示了「Start A C」和「Finish」。我們需要將這個圖形視為一個搜尋空間，並繪製出 DFS 遍歷過程所產生的搜尋樹，同時展示 DFS 的路徑。

繪製搜尋樹和展示 DFS：

DFS 的搜尋樹通常是隱含的，我們透過展示 DFS 的遍歷順序來體現。 DFS 會優先探索當前節點的「最左側」或「第一個」子節點。

假設的 DFS 遍歷順序：
從 Start A 開始。假設 A 有兩個分支，我們首先探索 A 的第一個分支。

1. Start A: 假設 A 的第一個子節點是 B。
2. A -> B: B 有子節點 F 和 M。DFS 會優先探索 F。
3. B -> F: F 有子節點 G 和 E。DFS 會優先探索 G。
4. F -> G: G 沒有子節點。DFS 回溯到 F。
5. F (再次): 探索 F 的下一個子節點 E。
6. F -> E: E 有子節點 D, H, J。DFS 會優先探索 D。
7. E -> D: D 有子節點 L, P。DFS 會優先探索 L。
8. D -> L: L 沒有子節點。DFS 回溯到 D。
9. D (再次): 探索 D 的下一個子節點 P。
10. D -> P: P 沒有子節點。DFS 回溯到 E。
11. E (再次): 探索 E 的下一個子節點 H。
12. E -> H: H 沒有子節點。DFS 回溯到 E。
13. E (再次): 探索 E 的下一個子節點 J。
14. E -> J: J 沒有子節點。DFS 回溯到 B。
15. B (再次): 探索 B 的下一個子節點 M。
16. B -> M: M 有子節點 Q, K, N。DFS 會優先探索 Q。
17. M -> Q: Q 沒有子節點。DFS 回溯到 M。
18. M (再次): 探索 M 的下一個子節點 K。
19. M -> K: K 沒有子節點。DFS 回溯到 M。
20. M (再次): 探索 M 的下一個子節點 N。
21. M -> N: N 沒有子節點。DFS 回溯到 A。
22. A (再次): 探索 A 的下一個子節點 C。

此題主要考查對無損壓縮 (Lossless Compression) 技術的理解，特別是三種常見的無損壓縮演算法：Run-length Encoding (RLE)、Huffman Coding 和 Lempel-Ziv (LZ) Encoding。題目要求分別解釋這三種方法，並提供範例。

核心觀念：
無損壓縮是指在壓縮過程中，數據的訊息可以完全恢復，不會有任何資訊損失。這對於醫療影像、文字文件等對精確度要求極高的數據尤為重要。

1. Run-length Encoding (RLE)

• 解釋： RLE 是一種簡單的無損壓縮技術，它透過將連續重複的相同字元或資料塊替換為該字元/資料塊及其重複次數來實現壓縮。當連續重複的資料較多時，RLE 效果較好。
• 適用場景： 適用於具有大量連續重複資料的數據，例如簡單的二值圖像、掃描線數據等。
• 範例：
  假設我們有一串字元：AAAAABBBCCDAAA
  使用 RLE 壓縮後，可以表示為：5A3B2C1D3A
  (這裡假設單一字元也用重複次數表示，例如 1D 表示 D 出現一次。更常見的 RLE 格式會區分字元和計數，例如 (A, 5), (B, 3), (C, 2), (D, 1), (A, 3) 或使用特定標記。)

2. Huffman Coding

• 解釋： Huffman Coding 是一種基於字元出現頻率的變長編碼技術。它為出現頻率較高的字元分配較短的編碼，為出現頻率較低的字元分配較長的編碼，從而達到整體壓縮的目的。它是一種統計編碼方法。

  • 建構過程：
    1. 統計數據中每個字元的出現頻率。
    2. 將每個字元及其頻率視為一個節點，放入優先佇列（最小堆）。
    3. 重複以下步驟直到佇列只剩一個節點：
       • 從佇列中取出兩個頻率最低的節點。
       • 創建一個新的父節點，其頻率是這兩個子節點頻率的總和。
       • 將這兩個節點作為新節點的左右子節點。
       • 將新節點放回佇列。
    4. 最終產生的樹稱為 Huffman 樹。
    5. 從根節點到葉節點（代表字元）的路徑，左分支通常標記為 '0'，右分支標記為 '1'（或反之），由此得到每個字元的二進位編碼。

• 適用場景： 適用於需要根據字元機率進行壓縮的場景，常見於文本壓縮、圖像壓縮（如 JPEG 的部分）等。

• 範例：
  假設我們有一段文本，字元及其頻率如下：
  A: 5
  B: 3
  C: 2
  D: 1

  步驟：

  1. 初始節點 (優先佇列)：(D, 1), (C, 2), (B, 3), (A, 5)
  2. 取出 (D, 1) 和 (C, 2)，合併為 (DC, 3)。佇列：(DC, 3), (B, 3), (A, 5)
  3. 取出 (DC, 3) 和 (B, 3)，合併為 (DCB, 6)。佇列：(A, 5), (DCB, 6)
  4. 取出 (A, 5) 和 (DCB, 6)，合併為 (ADC B, 11)。佇列：(ADCB, 11)

  Huffman 樹 (假設左為 0，右為 1)：
  (11)
  /
  (5)A (6)
  /
  (3)B (3)
  /
  (1)D (2)C

  編碼：
  A: 0
  B: 10
  C: 111
  D: 110

  壓縮後的數據：
  原始：AAAAABBBCCDAAA
  壓縮：000001010101111111100101010 (共 27 位元)

  原始數據總位元數： 14 個字元 * 8 位元/字元 = 112 位元 (假設 ASCII 編碼)

此題考查對堆疊 (Stack) 資料結構操作的理解，以及如何使用迴圈 (while loop) 和堆疊的基本操作 (push, pop) 來實現將一個堆疊的內容轉移到另一個堆疊。

核心觀念：
堆疊是一種後進先出 (LIFO - Last-In, First-Out) 的資料結構。push(item) 操作將 item 加入堆疊頂部，pop() 操作移除並回傳堆疊頂部的元素。

題目要求：
將堆疊 S1 的所有元素轉移到堆疊 S2，使得 S1 在操作後為空。

解題思路：
由於堆疊是 LIFO 的，直接將 S1.pop() 的結果 S1.push() 到 S2，會導致 S2 的元素順序與 S1 原來的順序相反。如果題目要求 S2 的元素順序與 S1 原來的順序相同，則需要額外的步驟。但題目只要求「移動內容」，且 S1 為空，並沒有明確要求 S2 的順序，因此最簡單的做法就是直接逐個彈出 S1 並壓入 S2。

演算法設計：
我們需要一個迴圈來持續執行 pop 和 push 操作，直到 S1 為空為止。判斷堆疊是否為空的條件通常是檢查堆疊的大小或使用一個特定的 is_empty() 函數。

Pseudocode：

此題考驗不同進制數字之間的轉換能力，特別是轉換到八進制 (Octal, Base-8)。轉換過程需要手動進行，不能使用計算機。

核心觀念：

• 進制轉換基本方法：

  • 轉為十進制： 將數字按位權展開求和。例如，$(abc)_d = a \times d^2 + b \times d^1 + c \times d^0$。
  • 十進制轉其他進制： 整數部分用除法取餘法，小數部分用乘法取整法。
  • 其他進制之間轉換： 通常先轉換到十進制，再從十進制轉換到目標進制。但對於二進制、八進制、十六進制之間，可以直接進行分組轉換。

• 二進制 (Base-2) 與八進制 (Base-8) 的關係：
  $8 = 2^3$。因此，每個八進制位可以由 3 個二進制位表示。

  • 八進制轉二進制：將每個八進制數字轉換為 3 位二進制數。
  • 二進制轉八進制：從二進制小數點開始，向左和向右每 3 位二進制數為一組，轉換為一個八進制數字。不足 3 位時補 0。

• 十六進制 (Base-16) 與八進制 (Base-8) 的關係：
  通常先將十六進制轉為二進制，再將二進制轉為八進制。

  • 十六進制轉二進制：每個十六進制數字對應 4 位二進制數。
  • 二進制轉八進制：同上，每 3 位二進制數對應一個八進制數。

轉換過程：

1. (11.4)₁₀ 轉八進制 (Octal):

   • 整數部分 (11):
     $11 \div 8 = 1$ 餘 $3$
     $1 \div 8 = 0$ 餘 $1$
     從下往上讀，得到 $13₈$。
   • 小數部分 (0.4):
     $0.4 \times 8 = 3.2$ (取整數部分 3)
     $0.2 \times 8 = 1.6$ (取整數部分 1)
     $0.6 \times 8 = 4.8$ (取整數部分 4)
     $0.8 \times 8 = 6.4$ (取整數部分 6)
     ... (循環或達到精度要求)
     從上往下讀，得到 $0.3146...₈$。
   • 合併： $(11.4)_{10} = (13.3146...)₈$

2. (51A.C)₁₆ 轉八進制 (Octal):

   • 十六進制轉二進制：
     $5_{16} = 0101_2$
     $1_{16} = 0001_2$
     $A_{16} = 1010_2$

核心觀念

二元搜尋法（Binary Search）用於已排序的資料序列。每次比較目標值與中間元素：

• 若相等，表示找到目標，搜尋成功並終止。
• 若目標值較小，只搜尋左半部。
• 若目標值較大，只搜尋右半部。
• 若搜尋範圍縮小為空集合，表示目標不存在，搜尋失敗並終止。

設陣列為遞增排序的 $A[0 \dots n-1]$，搜尋範圍以兩個索引表示：

• low：搜尋範圍左界
• high：搜尋範圍右界
• mid：搜尋範圍中間位置

每次將搜尋範圍縮小約一半，因此時間複雜度為 $O(\log n)$。

解題方法

採用「閉區間」表示法，令目前搜尋範圍為：

初始時，整個陣列都是搜尋範圍：

只要搜尋範圍仍然非空，即 $low \leq high$，就計算中間索引：

接著比較 $A[mid]$ 與目標值 target：

1. 若 $A[mid] = target$
   目標已找到，回傳 mid 並結束演算法。

2. 若 $A[mid] > target$
   因為陣列已遞增排序，$mid$ 右側的元素都不小於 $A[mid]$，不可能是目標。因此捨棄右半部，更新：

   $$high = mid-1$$

3. 若 $A[mid] < target$
   $mid$ 左側的元素都不大於 $A[mid]$，不可能是目標。因此捨棄左半部，更新：

   $$low = mid+1$$

當 low > high 時，搜尋範圍已經變成空集合，代表陣列中沒有 target，回傳 NOT_FOUND。

Pseudocode

BinarySearch(A, n, target):
    low ← 0
    high ← n - 1

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

        if A[mid] = target:
            return mid              // 找到目標，終止

        else if A[mid] > target:
            high ← mid - 1           // 搜尋左半部

        else:
            low ← mid + 1            // 搜尋右半部

    return NOT_FOUND                 // 搜尋範圍為空，目標不存在

此題考查對作業系統中死鎖 (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$ 在等待 $P_0$ 佔有的資源。

預防死鎖的方法：
預防死鎖意味著在系統設計階段就阻止死鎖發生的四個必要條件中的至少一個。

1. 打破「互斥」條件：

   • 方法： 盡可能允許資源共享。
   • 討論： 對於某些資源（如印表機、CPU 核心），互斥是必要的，因此此方法不常用。對於可共享資源（如唯讀文件），則不存在互斥問題。
   • 範例： 假設一個資料庫的讀取操作可以同時進行，而寫入操作需要獨佔。如果系統設計成允許多個進程同時讀取，但寫入時必須等待所有讀取完成，則打破了對寫入操作的互斥性（雖然寫入本身仍是互斥的）。

2. 打破「佔有並等待」條件：

   • 方法： 要求進程在請求任何資源之前，一次性獲取所有它需要的資源。或者，如果一個進程已經佔有了一些資源，它就不能再請求其他資源；如果請求不到，它必須釋放已佔有的資源。
   • 討論： 這種方法可能導致資源利用率低下，因為進程可能會長時間佔有大量未使用的資源。
   • 範例： 一個進程需要 A 資源和 B 資源。
     • 策略一 (一次性獲取)： 進程必須同時請求 A 和 B。如果 A 可用但 B 不可用，進程就不能獲得 A，必須等待。
     • 策略二 (釋放已佔有)： 進程先獲取 A。然後請求 B。如果 B 不可用，則進程必須釋放 A，然後等待 B 可用後，再重新請求 A 和 B。

此題要求簡要解釋兩個重要的計算機科學概念：物件導向程式設計 (Object-Oriented Programming, OOP) 和開放系統互連模型 (Open Systems Interconnection model, OSI model)。

1. Object-Oriented Programming (OOP)

• 解釋： 物件導向程式設計 (OOP) 是一種程式設計範式，它將程式的設計圍繞著「物件」(Objects) 進行。物件是資料 (屬性/欄位) 和操作 (方法/函數) 的集合。OOP 的核心思想是將複雜的系統分解為互相協作的物件，從而提高程式碼的可重用性、可維護性和靈活性。
• 核心概念：
  • 類別 (Class): 物件的藍圖或模板，定義了物件的屬性和行為。
  • 物件 (Object): 類別的實例，擁有特定的屬性值並能執行類別定義的方法。
  • 封裝 (Encapsulation): 將資料和操作綁定在一起，並隱藏物件的內部實現細節，只暴露必要的介面。
  • 繼承 (Inheritance): 允許一個類別（子類別/衍生類別）繼承另一個類別（父類別/基底類別）的屬性和方法，從而實現程式碼的重用。
  • 多型 (Polymorphism): 允許不同類別的物件對相同的訊息做出不同的響應。常見形式有方法重載 (overloading) 和方法覆寫 (overriding)。
• 優點： 提高程式碼的可擴展性、可維護性、模組化，易於團隊協作。
• 範例：
  想像一個「汽車」類別。
  • 屬性： 品牌 (Brand), 型號 (Model), 顏色 (Color), 最高速度 (MaxSpeed)。
  • 方法： 啟動 (Start), 停止 (Stop), 加速 (Accelerate), 煞車 (Brake)。
    一個具體的「汽車」物件，例如 myCar，可能具有 Brand="Toyota", Model="Camry", Color="Red"，並且可以呼叫 myCar.Start() 方法。

此題考驗對數據傳輸速率計算的理解，涉及解析度 (resolution)、灰階深度 (grayscale depth)、影格率 (frame rate) 和傳輸速率 (transmission rate) 等概念。

核心觀念：

• 解析度 (Resolution): 圖像的寬度和高度，表示圖像包含的像素數量。
• 灰階深度 (Grayscale Depth): 每個像素可以表示的顏色級別數量，通常以位元 (bits) 為單位。16 位元意味著每個像素有 $2^{16}$ 種可能的灰階值。
• 影格率 (Frame Rate, fps): 每秒鐘顯示的圖像幀數。
• 傳輸速率 (Transmission Rate): 數據在單位時間內傳輸的量，通常以比特每秒 (bps) 或兆比特每秒 (Mbps) 為單位。

計算步驟：

1. 計算單張 X 光影像的總位元數：

   • 圖像解析度 = 寬度 × 高度 = $3056 \times 3808$ 像素
   • 每個像素的位元數 (灰階深度) = 16 bits
   • 單張影像的總位元數 = (解析度) × (灰階深度)
     = $(3056 \times 3808) \times 16$ bits

2. 計算每秒所需的總位元數 (即傳輸速率)：

   • 影格率 = 24 frames per second (fps)
   • 每秒總位元數 = (單張影像的總位元數) × (影格率)
     = $((3056 \times 3808) \times 16) \times 24$ bits/second

3. 將結果轉換為 Mbps (Mega bits per second)：

   • 1 Mbps = $10^6$ bits/second (在網路傳輸速率中，M 通常指 $10^6$，而不是 $2^{20}$)

此題考查對 CPU 排程演算法中「最短作業優先」(Shortest Job First, SJF) 的理解，包括其運作方式、優點與缺點。

核心觀念：
CPU 排程的目的是決定哪個就緒 (ready) 的程序 (process) 或執行緒 (thread) 應該獲得 CPU 使用權。SJF 是一種批次 (batch) 排程演算法，它選擇就緒佇列 (ready queue) 中預計執行時間最短的程序來執行。

Shortest Job First (SJF) 演算法：

• 解釋： SJF 是一種非搶佔式 (non-preemptive) 或搶佔式 (preemptive) 的 CPU 排程演算法。

  • 非搶佔式 SJF (Shortest Job Next, SJN): 當 CPU 空閒時，從就緒佇列中選擇預計執行時間最短的程序來執行。一旦程序開始執行，它會一直執行直到完成或主動釋放 CPU。
  • 搶佔式 SJF (Shortest Remaining Time First, SRTF): 如果一個新進來的程序，其預計執行時間比當前正在執行的程序的剩餘執行時間還要短，則系統會搶佔當前程序的 CPU，並將 CPU 分配給這個新程序。
    題目通常指的是非搶佔式 SJF，除非特別說明。

• 運作方式：

  1. 系統監控所有就緒程序的預計執行時間。
  2. 當 CPU 空閒時，選擇預計執行時間最短的程序。
  3. 該程序獲得 CPU 直到完成。

優點 (Advantages):

1. 平均等待時間最短： SJF 在理論上可以達到最小的平均等待時間 (average waiting time)。透過優先執行短作業，可以快速讓許多短作業完成，減少它們在佇列中等待的時間。
2. 平均週轉時間最短： 由於等待時間短，週轉時間 (turnaround time，從提交到完成的時間) 也會相應縮短。

缺點 (Disadvantages):