114 年 國立中正大學資訊管理學系碩士班乙組《計算機概論》

本題主要考察學生對於傳統人工智慧（AI）與現代AI技術的理解，以及如何將這些技術應用於實際商業情境。

傳統 AI 技術應用

• 核心觀念： 傳統 AI 技術，如規則式推論、案例式推理、資料探勘（關聯規則、循序模式）等，旨在模擬人類的決策過程和知識推理能力。
• 應用範例： 推薦系統 (Recommendation System)。
• 說明：
  • 技術選擇： 推薦系統常採用「關聯規則」或「循序模式」等資料探勘技術。例如，電商平台會分析使用者的購物歷史、瀏覽行為，找出哪些商品經常被一起購買（關聯規則），或是使用者在購買某商品後，常接著購買另一種商品（循序模式）。
  • 為何採用： 這些技術能夠從大量的交易數據中挖掘出隱藏的商品間的關聯性，幫助商家了解消費者的購物習慣，進而向消費者推薦他們可能感興趣的商品。這能有效提升顧客體驗、增加銷售額，並促進交叉銷售（cross-selling）和向上銷售（up-selling）。例如，亞馬遜的「購買此商品的顧客也購買了...」功能，就是一個典型的關聯規則應用。

現代 AI 技術應用

本題要求說明四個資訊科學領域（資料倉儲、資料結構、資料探勘、大數據）各自的核心關注點與目標。

• a. 資料倉儲 (Data Warehousing)

  • 核心關注點： 整合來自不同來源、異質的營運資料，建立一個主題導向、整合性、時間相關、且非揮發性的資料集合，以支援管理決策。
  • 目標： 提供一個可靠、一致的資料來源，供報表製作、線上分析處理 (OLAP)、商業智慧 (BI) 工具使用，以協助企業進行決策分析，洞察營運狀況、趨勢和潛在問題。

• b. 資料結構 (Data Structure)

  • 核心關注點： 研究資料在電腦中組織、管理和儲存的方式，以及這些組織方式如何影響資料的存取效率和操作的效能。
  • 目標： 設計和選擇最適合特定問題的資料結構，以優化演算法的執行時間（時間複雜度）和空間使用量（空間複雜度），從而提高程式的效率和效能。

本題旨在考察學生對系統分析中常見的 UML (Unified Modeling Language) 圖示及其用途的理解。

• a. Use Case Diagram (用例圖)

  • 目標： 描述系統的功能需求，展示系統與外部參與者 (Actors) 之間的互動，以及系統提供的服務。
  • 適用領域： 需求分析階段，用來釐清系統的功能邊界、使用者角色和系統提供的核心服務。

• b. Class Diagram (類別圖)

  • 目標： 描繪系統的靜態結構，展示系統中的類別 (Classes)、它們的屬性 (Attributes)、操作 (Operations) 以及類別之間的關係（如關聯、繼承、聚合、組合）。
  • 適用領域： 設計階段，用於建立系統的物件導向模型，定義系統的藍圖。

• c. Entity-Relationship Diagram (ERD, 實體關係圖)

  • 目標： 描繪資料庫的邏輯結構，展示系統中需要儲存的實體 (Entities)、實體的屬性 (Attributes) 以及實體之間的關係 (Relationships)。
  • 適用領域： 資料庫設計階段，用於概念層和邏輯層的資料模型建立。

• d. Collaboration Diagram (互動圖/協同圖，現多稱為 Communication Diagram)

  • 目標： 描繪物件之間如何透過訊息傳遞來共同完成一個任務，強調物件之間的互動順序和訊息流。
  • 適用領域： 設計階段，用於理解物件如何協同工作，特別是關注訊息的傳遞路徑和時序。

本題要求針對四種基本資料結構（堆疊、鏈結串列、優先權佇列、二元搜尋樹），各舉一個應用實例，並解釋為何該應用選擇使用該特定資料結構。

• a. Stack (堆疊)

  • 應用： 函數呼叫的執行（Function Call Stack）。
  • 為何採用： 函數呼叫遵循「後進先出」(LIFO - Last-In, First-Out) 的原則。當一個函數 A 呼叫函數 B 時，函數 A 的執行狀態（如局部變數、返回位址）被壓入堆疊（push）。當函數 B 執行完畢返回時，其狀態從堆疊頂部彈出（pop），系統便能恢復到函數 A 的執行環境。堆疊的 LIFO 特性完美匹配了函數調用與返回的順序要求。

• b. Linked List (鏈結串列)

  • 應用： 實作一個動態大小的列表，例如網頁瀏覽器的「上一頁」和「下一頁」功能。
  • 為何採用： 鏈結串列可以在不重新分配記憶體或移動大量元素的情況下，方便地進行插入和刪除操作。對於瀏覽器歷史記錄，使用者可以在任何位置插入或刪除一個頁面（例如，從歷史記錄中移除某頁），鏈結串列的節點之間通過指標連接，使得插入和刪除操作的時間複雜度為 $O(1)$（若已知節點位置），這比陣列（需要移動元素，時間複雜度為 $O(n)$）更有效率。

本題旨在考察學生對四種基本演算法設計方法的理解，包括它們的核心思想和設計哲學。

• a. Greedy Method (貪婪法)

  • 哲學/概念： 在每一步選擇中，都採取在當前狀態下最好或最優的選擇，而不去考慮這個選擇對未來是否會產生更優的結果。它總是做出局部最优解，期望通過一系列局部最优解能達到全局最优解。
  • 關鍵特點： 局部最優、不回溯、通常較快。

• b. Dynamic Programming (動態規劃)

  • 哲學/概念： 將一個複雜問題分解為更小的、重疊的子問題，然後逐個解決這些子問題。它會儲存子問題的解，避免重複計算，從而獲得全局最优解。
  • 關鍵特點： 最優子結構（Optimal Substructure）和重疊子問題（Overlapping Subproblems）。通常通過自底向上（bottom-up）或自頂向下（top-down with memoization）的方式實現。

本題要求說明資料庫系統中四個重要機制（恢復、併發控制、檢查點、回滾）各自適用或需要的狀況。

• a. Recovery (恢復)

  • 應用/需要狀況： 當資料庫系統發生故障（如硬體故障、軟體崩潰、電源中斷）後，需要將資料庫恢復到一個一致、有效的狀態。
  • 說明： 恢復機制是為了保證資料的持久性。它利用日誌（Log）記錄的交易操作信息，在系統重新啟動後，可以重做（Redo）已提交但未寫入磁碟的修改，或撤銷（Undo）未提交交易的修改，從而恢復到故障發生前或一個穩定的狀態。

• b. Concurrency Control (併發控制)

  • 應用/需要狀況： 當多個交易（Transactions）同時存取和修改資料庫中的相同數據時，為了防止數據不一致（如讀到未提交的數據、寫入的數據被覆蓋），需要併發控制機制。
  • 說明： 併發控制技術（如鎖定機制、時間戳記排序、多版本並發控制 MVCC）確保了交易的隔離性 (Isolation)，使得即使多個交易同時執行，其效果也如同它們是串行執行一樣，從而維護了資料庫的正確性。

本題旨在考察學生對不同參數傳遞機制的理解，特別是它們在呼叫者 (caller) 和被呼叫者 (called) 端的操作或影響。

• a. Call-by-Value (傳值呼叫)

  • 呼叫者 (Caller) 操作： 呼叫者將變數的值複製一份傳遞給被呼叫者。
  • 被呼叫者 (Called) 操作： 被呼叫者接收到的是值的一個副本。在被呼叫者內部對參數進行的任何修改，都不會影響到呼叫者中的原始變數。
  • 核心： 傳遞的是值的副本，修改獨立。

• b. Call-by-Address (傳址呼叫，通常指傳遞記憶體位址)

  • 呼叫者 (Caller) 操作： 呼叫者將變數的記憶體位址複製一份傳遞給被呼叫者。
  • 被呼叫者 (Called) 操作： 被呼叫者接收到的是變數的記憶體位址。通過這個位址，被呼叫者可以直接存取和修改呼叫者中的原始變數。
  • 核心： 傳遞的是位址，修改直接影響原變數。

• c. Call-by-In-Out (傳入傳出呼叫)

  • 呼叫者 (Caller) 操作： 呼叫者將變數的值傳遞給被呼叫者。
  • 被呼叫者 (Called) 操作： 被呼叫者接收到變數的值，並可能對其進行修改。當被呼叫者執行結束返回時，修改後的值會傳回給呼叫者，覆蓋掉原始變數。
  • 核心： 初始傳入值，結束時傳出修改後的值。它結合了傳值和傳址的某些特性，但通常是先傳值，然後在結束時再傳回（可能通過傳址或複製）。某些語言（如 Pascal）直接支援此模式。

• d. Call-by-Name (傳名呼叫)

  • 呼叫者 (Caller) 操作： 呼叫者傳遞的是參數的「名稱」或「表示式」。

本題旨在考察學生對 CISC 和 RISC 這兩種指令集架構的理解，包括它們的優缺點以及發展趨勢。

CISC (Complex Instruction Set Computer) - 複雜指令集計算機

• 哲學： 設計盡可能多的、功能強大的指令，使得單條指令能夠完成複雜的任務（例如，從記憶體讀取數據、進行運算、再寫回記憶體，可以由一條指令完成）。目標是減少程式的長度，降低對記憶體頻寬的需求。
• 優點 (Pros)：
  • 程式碼密度高： 單條指令可以完成複雜操作，減少了程式的總指令數和總字節數，理論上可以減少記憶體佔用和存取次數。
  • 開發便利性（早期）： 組合語言編寫相對容易，因為指令集更接近高級語言的語法。
• 缺點 (Cons)：
  • 指令複雜度高： 指令集龐大，每條指令的微架構實現複雜，導致設計和製造困難。
  • 執行時間不確定： 不同指令需要不同的執行週期，這使得處理器難以進行精確的流水線 (Pipelining) 操作，影響執行效率。
  • 硬體開銷大： 需要複雜的解碼器和控制單元。
  • 編譯器負擔重： 編譯器需要花費更多精力來優化和選擇使用哪些複雜指令。

RISC (Reduced Instruction Set Computer) - 精簡指令集計算機

• 哲學： 設計一個精簡、固定長度、簡單的指令集，每條指令只執行一個基本操作。複雜的操作需要通過多條簡單指令組合來完成。目標是簡化硬體設計，提高指令的執行速度和流水線效率。
• 優點 (Pros)：
  • 指令執行速度快： 指令簡單、固定長度，易於解碼和流水線化，大多數指令可以在一個時鐘週期內完成。
  • 硬體設計簡單： 控制單元簡單，設計和製造更容易，功耗也相對較低。
  • 編譯器優化能力強： 編譯器可以更有效地對簡單指令進行重排和優化，充分利用流水線。

核心觀念
死結（deadlock）指的是一組程序因互相等待而無法繼續前進的狀況。根據 Coffman 等人提出的四個必要條件，同時存在下才會發生死結：

1. Mutual exclusion（互斥）：資源一次只能被一個程序使用。
2. Hold and wait（保持與等待）：已持有某些資源，同時向系統請求其他資源。
3. No preemption（不可搶奪）：已分配的資源只能由持有者自行釋放，系統無法強制收回。
4. Circular wait（循環等待）：存在資源的循環等待鏈，例如 $P_1$ 等 $R_2$、$P_2$ 等 $R_1$。

只要破除上述任一條件，即能 預防 死結的發生。

---

解題方法
題目要求列出 兩個 任何類別的應用程式，說明它們「不會」產生死結，並指出每個應用程式所消除的 Coffman 條件。解題步驟如下：

1. 選擇兩個具代表性的應用，保證在設計上必然違反至少一條必要條件。
2. 說明該應用的資源分配或執行機制，並明確指出是哪一條條件被消除。
3. 核對四條條件，確保未被列出的其他條件仍可能存在，但只要有一條被破除，死結即不會發生。

沒有計算或推導，只要描述清楚即可獲得滿分。

---

範例應用 1：單執行緒之嵌入式控制程式
說明
嵌入式系統（如微控制器的 ISR）通常僅有 單一執行緒，所有程式碼在同一時間只能由該執行緒執行。即使使用互斥鎖保護共享硬體（例如 UART），也不存在多個執行緒同時競爭資源的情形。

消除的條件

• Mutual exclusion：因系統僅有一個執行緒，資源不會被同時要求，實際上不存在互斥競爭。

本題要求按照時間順序，列出筆記型電腦從開機到成功存取 www.ccu.edu.tw 網站過程中，所需要或使用的網路通訊協定。

當筆記型電腦開機並連上網路（例如透過 Wi-Fi 或乙太網路），它需要一系列網路協定的協調才能完成與遠端伺服器的通訊。以下是大致的流程和涉及的協定順序：

1. DHCP Protocol (動態主機設定協定)：

   • 時機： 筆記型電腦剛連上網路時（例如，剛開機或剛連上 Wi-Fi）。
   • 作用： 筆記型電腦需要一個 IP 位址才能在網路上進行通訊。DHCP 協定用於自動為電腦分配一個 IP 位址、預設閘道 (Default Gateway) 的 IP 位址、DNS 伺服器的 IP 位址以及子網路遮罩 (Subnet Mask) 等網路組態資訊。
   • 這是第一步，因為沒有 IP 位址，電腦無法進行任何 IP 層級的通訊。

2. DNS Resolution (網域名稱解析)：

   • 時機： 在嘗試存取 www.ccu.edu.tw 時。
   • 作用： 網際網路上的主機是透過 IP 位址來識別的，但使用者通常使用易於記憶的網域名稱（如 www.ccu.edu.tw）。DNS 協定負責將網域名稱轉換為對應的 IP 位址。電腦會向其 DHCP 分配的 DNS 伺服器發送 DNS 查詢請求。
   • 這是第二步，因為需要知道伺服器的 IP 位址才能建立連線。

3. ARP Protocol (位址解析協定)：

   • 時機： 當電腦需要將封包傳送給同一區域網路 (LAN) 內的其他主機（包括預設閘道）時。
   • 作用： ARP 協定用於將 IP 位址（網路層位址）解析成對應的 MAC 位址（資料連結層位址）。電腦知道目標 IP 位址（可能是 DNS 解析出來的伺服器 IP，或是預設閘道的 IP），但它需要知道目標 MAC 位址才能在乙太網路框架中傳送封包。
   • 說明： 如果 www.ccu.edu.tw 的 IP 位址在同一個子網路，則會直接使用 ARP 解析該 IP 的 MAC。如果 IP 位址不在同一個子網路，則會先使用 ARP 解析預設閘道的 MAC 位址，然後將封包送往預設閘道。

4. Three-way Handshaking (TCP 三向交握)：

   • 時機： 在使用 TCP 協定（HTTP 預設使用 TCP）與遠端伺服器建立連線時。
   • 作用： TCP 是一個可靠的、面向連線的傳輸層協定。在傳輸資料之前，必須先透過三次訊息交換（SYN, SYN-ACK, ACK）來建立一個可靠的連線。
   • 這是建立 TCP 連線的標準過程，在傳送 HTTP 請求之前必須完成。