108 年 國立中央警察大學資訊管理研究所《計算機概論》

本題主要在探討人工智慧 (Artificial Intelligence, AI) 的兩種不同層次定義：強 AI 與弱 AI。

核心觀念：
人工智慧的發展歷程中，對於 AI 的目標與能力有不同的看法，主要分為強 AI 和弱 AI 兩種觀點。

詳解：

(一) 何謂強人工智慧 (Strong Artificial Intelligence)? 何謂弱人工智慧 (Weak Artificial Intelligence)? 請舉例說明之。

• 強人工智慧 (Strong Artificial Intelligence, SAI)
  • 定義： 強 AI 指的是一種能夠真正理解、思考、學習，並擁有意識、情感、自我認知能力的機器。它不僅僅是模擬人類的行為，而是能夠「像」人類一樣去思考和感知。強 AI 的目標是創造出一個具有人類智慧水平的通用人工智能，能夠在任何智力任務上與人類匹敵，甚至超越。
  • 重點： 擁有真正的「心智」(mind)，能夠進行推理、解決問題、學習、計畫，並具備意識和理解能力。
  • 舉例： 目前不存在真正意義上的強 AI。但可以想像的例子包括：
    • 電影《機械公敵》(I, Robot) 中的 VIKI，它展現出高度的理解、推理、決策能力，甚至有自己的「意志」。
    • 電影《雲端情人》(Her) 中的 Samantha，她能夠與人類進行深入的情感交流、學習、成長，並展現出意識。
    • 科幻小說或電影中，那些能夠像人類一樣進行複雜對話、產生情感、進行哲學思考的機器人或電腦程式。

本題探討人工智慧中，搜尋演算法的應用，要求說明三種搜尋方法及其優缺點。

核心觀念：
搜尋是人工智慧中解決問題的基礎技術之一，特別是對於狀態空間搜尋問題。選擇合適的搜尋演算法對於效率和可行性至關重要。

詳解：

(二) 在人工智慧的技術中,搜尋(Searching)的技巧是很重要的一環,請舉例說明3種搜尋方法及其優缺點。

搜尋演算法用於在一個狀態空間中尋找從起始狀態到目標狀態的路徑。常見的搜尋方法可以分為兩大類：無資訊搜尋 (Uninformed Search) 和有資訊搜尋 (Informed Search)。

以下介紹三種常見的搜尋方法及其優缺點：

1. 廣度優先搜尋 (Breadth-First Search, BFS)

   • 方法： 是一種無資訊搜尋演算法。它以層層遞進的方式展開搜尋樹，先檢查所有離根節點一層的節點，然後是兩層的節點，依此類推。它使用佇列 (Queue) 來儲存待處理的節點。
   • 優點：
     • 找到最短路徑： 如果存在路徑，BFS 必定能找到最淺（即最短）的路徑（以邊數計算）。
     • 完備性 (Completeness)： 如果目標節點存在，BFS 必定能找到它（在有限狀態空間中）。
   • 缺點：
     • 時間複雜度高： 在狀態空間較大的情況下，BFS 需要探索大量的節點，時間複雜度可能非常高，達到 $O(b^d)$，其中 $b$ 是分支因子 (branching factor)，$d$ 是目標節點的深度。
     • 空間複雜度高： BFS 需要儲存每一層的所有節點，其空間複雜度也可能非常高，達到 $O(b^d)$。對於深度很大的問題，記憶體消耗會非常大。
   • 舉例： 在迷宮中尋找最短路徑，BFS 會先探索所有一步可達的格子，然後是兩步可達的格子，直到找到出口。

2. 深度優先搜尋 (Depth-First Search, DFS)

   • 方法： 也是一種無資訊搜尋演算法。它沿著一條路徑盡可能深地搜尋，直到無法再深入或找到目標節點。如果走到死路，則回溯 (backtrack) 到上一個節點，然後探索另一條分支。它通常使用堆疊 (Stack) 來實現（或透過遞迴實現）。
   • 優點：
     • 空間效率高： 相較於 BFS，DFS 的空間複雜度較低，通常為 $O(bm)$，其中 $m$ 是最大深度。對於深度很大的問題，DFS 在記憶體需求上更具優勢。

本題要求說明三種人工智慧中常見的知識庫表示法及其優缺點。

核心觀念：
知識表示 (Knowledge Representation) 是 AI 的核心問題之一。如何有效地將現實世界的知識儲存、組織和推理，是構建智能系統的關鍵。

詳解：

(三) 請說明3種人工智慧的知識庫表示法及其優缺點。

知識庫是 AI 系統中儲存知識的部分，其表示法的選擇直接影響系統的推理能力和效率。以下介紹三種常見的知識庫表示法：

1. 產生式規則 (Production Rules)

   • 表示法： 以「如果 P，則 Q」的條件-動作 (IF-THEN) 形式來表示知識。P 是條件 (antecedent)，Q 是動作 (consequent)。當 P 為真時，系統執行 Q。
   • 結構： 由一個規則庫 (Rule Base) 和一個知識庫 (Working Memory) 組成。推理引擎 (Inference Engine) 負責匹配規則的條件並執行動作。
   • 優點：
     • 易於理解和修改： 規則的 IF-THEN 結構直觀，符合人類的思考方式，易於專家添加、修改或刪除規則。
     • 適合處理過程性知識： 非常適合表示如何做某事的知識（程序性知識），如診斷、控制等。
     • 模組化： 每個規則可以相對獨立，便於維護。
   • 缺點：
     • 難以表示結構化知識： 對於複雜的物件、類別、屬性關係等結構性知識，產生式規則表示起來可能顯得笨拙和冗長。
     • 衝突解決困難： 當多個規則的條件同時滿足時，需要一個衝突解決策略 (conflict resolution strategy)，這可能很複雜。
     • 效率問題： 在大型規則庫中，尋找匹配的規則可能需要大量時間。
   • 舉例：
     • IF (病人發燒 AND 病人咳嗽) THEN (建議病人去看醫生)。
     • IF (汽車引擎無法啟動 AND 電瓶燈亮) THEN (檢查電瓶)。

2. 語意網路 (Semantic Networks)

   • 表示法： 使用節點 (Nodes) 表示概念或物件，使用連接節點的弧 (Arcs) 或連結 (Links) 表示概念之間的關係。這是一種圖形化的知識表示方法。
   • 結構： 節點代表實體（如：狗、動物、約翰、紅色），弧代表關係（如：is-a, has-a, color-of）。
   • 優點：
     • 直觀易懂： 圖形化的表示方式非常直觀，易於人類理解概念之間的關聯。
     • 適合表示結構化知識： 非常適合表示物件、屬性、類別層次（is-a 關係）以及實體之間的關聯。

本題主要探討演算法的基本概念及其應具備的關鍵特性。

核心觀念：
演算法是解決問題的藍圖，其定義和特性是計算機科學的基礎。

詳解：

(一) 何謂演算法 (Algorithm)? 請說明演算法應具備哪些特性。

• 演算法 (Algorithm) 的定義：
  演算法是一系列明確、有限、有序的指令或規則，用於解決特定問題或執行特定任務。它描述了如何從輸入 (input) 轉換到輸出 (output) 的計算過程。簡單來說，演算法就是解決問題的步驟。

• 演算法應具備的特性：
  一個好的演算法通常應具備以下五個基本特性：

  1. 輸入 (Input)： 演算法可以有零個或多個輸入。這些輸入是演算法處理的數據或資訊，在演算法開始執行之前就已經被指定。
  2. 輸出 (Output)： 演算法必須有一個或多個輸出。這些輸出與輸入有關，是演算法執行後產生的結果，並且與演算法的目標相一致。

本題主要在釐清內部排序與外部排序這兩種資料排序 (Sorting) 的基本分類。

核心觀念：
排序演算法的選擇，很大程度上取決於資料的儲存位置和大小。內部排序和外部排序就是基於此區分。

詳解：

(二) 何謂內部排序 (Internal Sort)? 何謂外部排序 (External Sort)? 請說明之。

在電腦科學中，排序是將一個資料集合（如陣列或列表）中的元素，按照某種預定義的順序（升序或降序）重新排列的操作。根據資料是儲存在主記憶體 (RAM) 中還是輔助儲存裝置 (如硬碟) 中，排序演算法可以分為內部排序和外部排序。

1. 內部排序 (Internal Sort)
   • 定義： 內部排序是指資料集合能完全載入到主記憶體 (RAM) 中進行排序的演算法。也就是說，在排序過程中，所有需要處理的資料都在電腦的 RAM 中，不需要與輔助儲存裝置進行頻繁的讀寫交換。
   • 適用情況： 當待排序資料量不大，可以輕鬆放入主記憶體時使用。
   • 常見演算法：
     • 氣泡排序 (Bubble Sort)
     • 選擇排序 (Selection Sort)
     • 插入排序 (Insertion Sort)
     • 快速排序 (Quick Sort)
     • 合併排序 (Merge Sort)
     • 堆積排序 (Heap Sort)
     • 希爾排序 (Shell Sort)
   • 優點： 由於主記憶體存取速度遠高於輔助儲存裝置，內部排序通常效率較高。
   • 缺點： 僅適用於資料量不超過主記憶體容量的情況。

核心觀念

氣泡排序是比較相鄰兩個元素的排序法。若左側元素大於右側元素，就交換兩者；一趟掃描後，未排序區間中的最大值會移到最右端，像氣泡逐步浮到頂端，因此稱為氣泡排序。

以下以由小到大排序為例。完成一趟後，右端已有一個元素就位，下一趟不必再比較該元素。

解題方法與演算法

從陣列左端開始，依序比較相鄰元素；若順序錯誤便交換。每趟比較範圍縮短一格，最多執行 $n-1$ 趟。

BubbleSort(A, n):
    for i = 0 to n - 2:
        swapped = false
        for j = 0 to n - 2 - i:
            if A[j] > A[j + 1]:
                swap(A[j], A[j + 1])
                swapped = true
        if swapped == false:
            break

swapped 用來記錄該趟是否發生交換。若整趟沒有交換，代表資料已排序完成，可提前停止。

排序範例

將陣列 $[5,1,4,2,8]$ 由小到大排序。

第 1 趟： 依序比較相鄰元素：

• 比較 $5$ 與 $1$，交換：$[1,5,4,2,8]$
• 比較 $5$ 與 $4$，交換：$[1,4,5,2,8]$
• 比較 $5$ 與 $2$，交換：$[1,4,2,5,8]$

本題考查二進位補數 (Two's Complement) 表示法，以及如何用固定位元數來表示帶符號的十進位數。

核心觀念：
二進位補數表示法是電腦中表示帶符號整數的標準方法，它能簡化加法和減法運算。

詳解：

(一) Using 4 bits and two's complement representation, what is the binary representation of the following signed decimal values: +9 and -6.

在 4 位元 (bits) 的二進位補數表示法中，最高位元 (Most Significant Bit, MSB) 用於表示符號：0 表示正數，1 表示負數。

• 範圍： 4 位元的二進位補數表示法的可表示範圍是從 $-(2^{4-1})$ 到 $2^{4-1} - 1$，即從 $-2^3$ 到 $2^3 - 1$，也就是從 -8 到 +7。

• 正數表示： 正數的表示法與一般的二進位轉換相同，最高位元為 0。

• 負數表示： 負數的表示法是透過「取反加一」(One's Complement + 1) 的方式得到。

  1. 先將其絕對值轉換為二進位。
  2. 對該二進位數進行「位元反轉」(0 變 1, 1 變 0)，得到「一補數」(One's Complement)。
  3. 將一補數加 1，得到「二補數」(Two's Complement)。

1. 表示 +9 (Decimal) 在 4 bits:

• 首先，我們需要注意 4 位元的二進位補數表示法的最大正數是 +7 ($2^{4-1}-1$)。
• 因此，十進位數 +9 無法在 4 位元的二進位補數表示法中表示。
• 如果題目意圖是測試這個限制，那麼答案就是「無法表示」。
• 如果題目假設我們忽略這個限制，或者有其他解釋（例如：題目本身有誤），我們嘗試將 9 轉換為二進位，但其絕對值本身就需要至少 4 位元來表示 (1001)。

本題要求對給定的數字列表執行氣泡排序 (Bubble Sort)，並展示每次交換後的列表狀態。

核心觀念：
氣泡排序演算法的逐步執行過程，重點在於展示每次比較和交換後列表的變化。

詳解：

(二) For the following number list, perform a bubble sort, and show the list after each change.
List: [12, 9, 6, 3, 1, 5, 7]

氣泡排序的目標是通過重複比較相鄰的元素並在順序錯誤時交換它們，將最大的元素逐步「冒泡」到列表的末尾。我們將展示每次交換後的列表狀態。

初始列表： [12, 9, 6, 3, 1, 5, 7]

第一趟 (Pass 1): (比較並交換，直到最後一個元素)

• 比較 (12, 9) -> 交換 -> [9, 12, 6, 3, 1, 5, 7]
• 比較 (12, 6) -> 交換 -> [9, 6, 12, 3, 1, 5, 7]
• 比較 (12, 3) -> 交換 -> [9, 6, 3, 12, 1, 5, 7]
• 比較 (12, 1) -> 交換 -> [9, 6, 3, 1, 12, 5, 7]
• 比較 (12, 5) -> 交換 -> [9, 6, 3, 1, 5, 12, 7]
• 比較 (12, 7) -> 交換 -> [9, 6, 3, 1, 5, 7, 12]
  第一趟結束，最大的元素 12 已被冒泡到最後。
  列表狀態： [9, 6, 3, 1, 5, 7, 12]

第二趟 (Pass 2): (對前 6 個元素進行)

• 比較 (9, 6) -> 交換 -> [6, 9, 3, 1, 5, 7, 12]
• 比較 (9, 3) -> 交換 -> [6, 3, 9, 1, 5, 7, 12]
• 比較 (9, 1) -> 交換 -> [6, 3, 1, 9, 5, 7, 12]
• 比較 (9, 5) -> 交換 -> [6, 3, 1, 5, 9, 7, 12]
• 比較 (9, 7) -> 交換 -> [6, 3, 1, 5, 7, 9, 12]
  第二趟結束，第二大的元素 9 已被冒泡到倒數第二個位置。
  列表狀態： [6, 3, 1, 5, 7, 9, 12]

第三趟 (Pass 3): (對前 5 個元素進行)

• 比較 (6, 3) -> 交換 -> [3, 6, 1, 5, 7, 9, 12]
• 比較 (6, 1) -> 交換 -> [3, 1, 6, 5, 7, 9, 12]
• 比較 (6, 5) -> 交換 -> [3, 1, 5, 6, 7, 9, 12]
• 比較 (6, 7) -> 不交換 -> [3, 1, 5, 6, 7, 9, 12]
  第三趟結束，第三大的元素 7 已被冒泡到倒數第三個位置。
  列表狀態： [3, 1, 5, 6, 7, 9, 12]

第四趟 (Pass 4): (對前 4 個元素進行)

• 比較 (3, 1) -> 交換 -> [1, 3, 5, 6, 7, 9, 12]
• 比較 (3, 5) -> 不交換 -> [1, 3, 5, 6, 7, 9, 12]
• 比較 (5, 6) -> 不交換 -> [1, 3, 5, 6, 7, 9, 12]
  第四趟結束，第四大的元素 6 已被冒泡到倒數第四個位置。
  列表狀態： [1, 3, 5, 6, 7, 9, 12]

第五趟 (Pass 5): (對前 3 個元素進行)

• 比較 (1, 3) -> 不交換 -> [1, 3, 5, 6, 7, 9, 12]

本題探討網路通訊中的核心協定：TCP、UDP 和 IP，要求說明其全名、TCP 與 UDP 的差異，以及它們與 IP 的關係。

核心觀念：
TCP/IP 協定是網際網路的基礎，理解各協定的功能和層級關係對於網路通訊至關重要。

詳解：

四、電腦在執行網路通訊時會使用到許多不同的通訊協定(Protocols),請先說明 TCP、UDP 與 IP 的英文全名各為何?另外,請再說明 TCP 與 UDP 有何不同?它們與 IP 的關係又為何?

在網際網路的運作中，TCP、UDP 和 IP 是最基本且最重要的通訊協定。它們工作在網路模型的不同層級，共同協調資料的傳輸。

1. 英文全名：

• TCP： Transmission Control Protocol (傳輸控制協定)
• UDP： User Datagram Protocol (使用者資料報協定)
• IP： Internet Protocol (網際網路協定)

2. TCP 與 UDP 的不同：

TCP 和 UDP 都是運行在傳輸層 (Transport Layer) 的協定，它們的主要區別在於提供的服務品質和功能：

特性	TCP (Transmission Control Protocol)	UDP (User Datagram Protocol)
可靠性	可靠 (Reliable)：確保資料按順序、無遺失、無重複地送達。	不可靠 (Unreliable)：盡力傳送，不保證送達、順序或無重複。
連線導向	連線導向 (Connection-Oriented)：在傳送資料前，需要建立連線 (三次握手)。	無連線 (Connectionless)：無需建立連線，直接發送資料。
傳輸方式	位元流 (Stream-Oriented)：將資料視為連續的位元流。	資料報 (Datagram-Oriented)：將資料分割成獨立的資料報。
速度	相對較慢 (因建立連線、確認、重傳等額外開銷)。	相對較快 (開銷小)。
流量控制	有：防止發送方過快傳送資料，導致接收方無法處理。	無。
錯誤控制	有：透過確認應答 (ACK)、序號、重傳機制來確保資料正確性。	有 (僅基本的校驗和，可選)。