108 年 國立臺灣大學生醫電子與資訊學研究所丙組《計算機概論（B）》

本題為名詞解釋題，共 22 個名詞，每題 2 分，總計 44 分。需解釋名詞的內容、目的、應用，並舉例。若為縮寫需寫出全名。

以下為各名詞的解釋：

(1) NFC (Near Field Communication)
內容：一種短距離無線通訊技術，允許在兩台裝置之間進行資料交換，通常距離在 4 公分以內。
目的：提供一種方便、安全的方式進行非接觸式資料傳輸，例如行動支付、門禁識別、資料分享等。
應用：行動支付（如 Apple Pay, Google Pay）、悠遊卡、門禁卡、藍牙配對的快速啟動、智慧家電控制。
舉例：使用手機 NFC 功能靠近支援的感應器，即可完成付款。

(2) virtual memory
內容：一種記憶體管理技術，利用硬碟空間作為主記憶體（RAM）的擴充，讓程式感覺擁有比實際 RAM 更大的記憶體空間。
目的：克服實體記憶體不足的問題，允許執行更多或更大的程式，並提高系統的穩定性。
應用：作業系統中常見的功能，用於載入和執行應用程式。
舉例：當系統記憶體不足時，作業系統會將暫時不使用的記憶體區塊寫入硬碟的交換分區 (swap partition)，需要時再讀回。

(3) semaphore
內容：一種同步原語（synchronization primitive），用於控制多個執行緒（thread）或程序（process）對共享資源的存取。它是一個整數變數，通過兩個原子操作 P (wait) 和 V (signal) 來控制。
目的：防止競爭條件（race condition）的發生，確保共享資源的唯一存取，協調執行緒間的合作。
應用：在多執行緒或多程序環境中，用於保護共享資料結構、控制資源的分配、實現執行緒間的同步。
舉例：一個計數信號量（counting semaphore）可以限制同時訪問某個資源的執行緒數量。例如，有 N 個印表機，則信號量初始值設為 N，每次有執行緒申請印表機時 P 操作，釋放時 V 操作。

(4) multi-threading
內容：一種執行模型，允許一個程式（或程序）同時執行多個執行緒（thread）。執行緒是程序內部的最小執行單位，共享程序的記憶體空間。
目的：提高程式的響應速度和效率，特別是在 I/O 密集型任務或需要並行處理的場景下。
應用：網頁瀏覽器（處理 UI、下載、渲染）、遊戲（處理 AI、物理模擬、圖形渲染）、伺服器（處理多個客戶端請求）。
舉例：一個網頁瀏覽器可以同時下載多個圖片，同時渲染頁面，同時響應使用者的點擊操作。

(5) DMA (Direct Memory Access)
內容：一種硬體技術，允許周邊設備（如硬碟、網路卡、顯示卡）直接讀寫主記憶體（RAM），而無需 CPU 的參與。
目的：減輕 CPU 的負擔，提高資料傳輸的效率和系統的整體效能。
應用：高速資料傳輸，如硬碟讀寫、網路封包傳輸、顯示卡繪圖資料傳輸。
舉例：當從硬碟讀取大量資料時，DMA 控制器可以直接將資料從硬碟傳輸到記憶體，CPU 則可以同時執行其他任務。

(6) deep learning
內容：機器學習的一個分支，使用具有多個隱藏層的深度神經網路（deep neural networks）來學習資料中的複雜模式。
目的：從大量的非結構化資料（如圖像、聲音、文字）中自動學習特徵，並進行預測或分類。
應用：圖像識別、語音識別、自然語言處理、推薦系統、自動駕駛。
舉例：人臉辨識系統，透過深度學習模型分析大量人臉圖像，學習辨識不同人臉的特徵。

(7) artificial intelligence (AI)
內容：研究、開發能夠模擬人類智慧行為的計算機系統。這包括學習、解決問題、感知、理解語言等能力。
目的：創建能夠執行通常需要人類智慧才能完成的任務的系統。
應用：語音助理（Siri, Alexa）、推薦系統、自動駕駛汽車、醫療診斷輔助、遊戲 AI。
舉例：AlphaGo 擊敗世界圍棋冠軍，展示了 AI 在複雜策略遊戲中的強大能力。

(8) convolutional neural network (CNN)
內容：一種特殊的神經網路，特別擅長處理具有網格狀拓撲結構的資料，如圖像。它使用卷積層（convolutional layers）來自動學習空間層級特徵。
目的：有效提取圖像中的特徵，用於圖像識別、物件偵測等任務。
應用：圖像分類、人臉辨識、醫學影像分析、自動駕駛中的環境感知。
舉例：辨識一張圖片是貓還是狗。

(9) CPU (Central Processing Unit)
內容：計算機的核心處理器，負責執行程式指令、進行算術和邏輯運算、控制其他硬體組件的操作。
目的：作為計算機的大腦，執行所有計算和控制任務。
應用：所有計算機系統（個人電腦、伺服器、手機、嵌入式設備）的中央處理單元。
舉例：Intel Core i7 或 AMD Ryzen 9 都是 CPU 的例子。

(10) GPU (Graphics Processing Unit)
內容：專門設計用於處理圖形和影像的處理器。它具有大量的處理核心，擅長並行處理大量簡單的運算。
目的：加速圖形渲染、影片處理，近年來也廣泛應用於科學計算和機器學習。
應用：遊戲、影片編輯、3D 建模、深度學習訓練。

死結（deadlock）是指在多個程序或執行緒同時運行時，因為相互等待資源而導致的僵局。要發生死結，必須同時滿足以下四個必要條件：

1. 互斥（Mutual Exclusion）: 至少有一個資源是不能被同時共享的，必須一次只能由一個程序使用。如果有多個程序都想使用同一個資源，則必須等待前一個使用該資源的程序釋放它。

   • 說明: 這是死結發生的基本前提。如果所有資源都可以被無限次共享，就不會有等待的情況，自然也不會有死結。例如，印表機通常是互斥資源。

2. 持有並等待（Hold and Wait）: 一個程序至少持有一種資源，但同時又在等待被其他程序持有的、它所需的另一種資源。

   • 說明: 程序在持有現有資源的情況下，又去請求其他資源，如果這個請求導致了等待，並且其他程序也持有資源並等待，就可能形成死結。例如，程序 A 持有資源 R1，並在等待資源 R2；程序 B 持有資源 R2，並在等待資源 R1。

作業系統（Operating System, OS）扮演著管理計算機硬體和軟體資源的角色，並為使用者和應用程式提供一個介面。其主要功能涵蓋以下幾個方面，列出其中至少四項：

1. 程序管理（Process Management）:

   • 說明: 作業系統負責創建、終止、暫停和恢復程序（或稱為行程，process）。它還需要管理程序之間的通信（IPC, Inter-Process Communication）和同步，以防止競爭條件和死結。
   • 核心任務: 程序調度（決定哪個程序獲得 CPU 時間）、程序間通信、同步與互斥。

2. 記憶體管理（Memory Management）:

   • 說明: 作業系統負責分配和回收主記憶體（RAM）給各個程序。它需要追蹤哪些記憶體區域已被使用，哪些是空閒的，並確保程序不會存取到不屬於自己的記憶體空間。
   • 核心任務: 記憶體分配、記憶體回收、虛擬記憶體管理（如分頁 paging 和分段 segmentation）、記憶體保護。

3. 檔案系統管理（File System Management）:

   • 說明: 作業系統提供了一個結構化的方式來組織、儲存、檢索和管理儲存在輔助儲存設備（如硬碟）上的檔案。

Call by value (傳值呼叫) 和 Call by address (傳址呼叫) 是兩種不同的函數（或方法）參數傳遞機制，它們的主要區別在於傳遞給函數的是參數的「值」還是參數的「位址」。

1. Call by value (傳值呼叫):

   • 機制: 當函數被呼叫時，實參（actual argument）的值會被複製一份，然後將這個複製的值傳遞給形參（formal parameter）。
   • 影響: 在函數內部，形參是實參的一個獨立副本。對形參的任何修改（例如重新賦值、改變其內容）都不會影響到函數外部的實參。
   • 優點: 確保了實參的原始值不會被意外修改，增加了程式的安全性。
   • 缺點: 如果傳遞的是大型資料結構，複製操作可能會消耗較多的記憶體和處理時間。
   • 常見語言: C, C++, Java (對於基本型別)。

   範例 (C 語言):

   void increment(int x) { // x 是形參，是實參的副本
       x = x + 1; // 修改的是 x 的副本
       printf("Inside function: x = %d\n", x);
   }
   
   int main() {
       int a = 5; // a 是實參
       printf("Before function call: a = %d\n", a);
       increment(a); // 傳遞 a 的值
       printf("After function call: a = %d\n", a); // a 的值不會改變
       return 0;
   }
   // 輸出:
   // Before function call: a = 5
   // Inside function: x = 6
   // After function call: a = 5
   

軟體生命週期（Software Life Cycle, SLC）是指一個軟體從概念形成到最終退役所經歷的整個過程。通常可以劃分為以下五個主要階段：

1. 規劃與可行性分析（Planning and Feasibility Study）:

   • 目的: 在投入大量資源開發前，確定軟體專案是否可行，並對其進行初步的規劃。
   • 活動:
     • 定義專案目標和範圍。
     • 進行市場分析、技術可行性分析、經濟可行性分析。
     • 評估風險。
     • 制定初步的專案計劃，包括時間表、預算和資源需求。
   • 產出: 可行性報告、初步專案計劃。

2. 需求分析（Requirements Analysis）:

   • 目的: 深入了解和記錄使用者對軟體系統的具體需求，明確軟體應具備的功能和性能。
   • 活動:
     • 與客戶、使用者溝通，收集需求。
     • 分析、整理、歸納需求，區分功能性需求（Software functional requirements）和非功能性需求（Software non-functional requirements，如性能、安全性、可用性）。
     • 編寫需求規格說明書（SRS, Software Requirements Specification）。
   • 產出: 需求規格說明書 (SRS)。

3. 設計（Design）:

   • 目的: 根據需求規格說明書，設計軟體的架構、模組、介面和資料結構，為後續的編碼工作打下基礎。
   • 活動:
     • 概要設計（High-Level Design / Architectural Design）: 定義系統的整體架構、主要模組及其關係。
     • 詳細設計（Low-Level Design / Detailed Design）: 設計每個模組的內部邏輯、資料結構、演算法、介面細節。

網路拓撲（Network Topology）是指網路中節點（設備）和連接線的物理或邏輯佈局。以下是四種常見的網路拓撲：

1. 匯流排拓撲（Bus Topology）:

   • 結構: 所有節點都連接到一條共同的中央線（匯流排）。資料從一個節點發出後，會沿著匯流排傳播到所有其他節點，但只有目標節點會接收和處理。
   • 優點: 結構簡單，佈線容易，成本較低，易於添加新節點。
   • 缺點: 匯流排是單點故障（single point of failure），如果匯流排損壞，整個網路都會癱瘓。資料衝突（collision）的機率較高，網路效能會隨著節點數量的增加而下降。
   • 範例: 早期的乙太網路（Ethernet）常使用同軸電纜作為匯流排。

2. 星狀拓撲（Star Topology）:

   • 結構: 所有節點都獨立連接到一個中央設備，通常是集線器（hub）或交換器（switch）。
   • 優點: 易於安裝和配置。單個節點的故障不會影響其他節點。易於故障排除，因為可以隔離個別連接。
   • 缺點: 中央設備是單點故障，如果中央設備損壞，整個網路都會癱瘓。需要較多的線纜。
   • 範例: 大多數現代的區域網路（LAN）都採用星狀拓撲，例如使用乙太網路交換機連接電腦。

將帶分數 $9 \frac{3}{8}$ 轉換為二進位表示法，需要分別轉換整數部分和分數部分。

1. 整數部分轉換:
將十進位整數 9 轉換為二進位：
$9 \div 2 = 4$ 餘 $1$
$4 \div 2 = 2$ 餘 $0$
$2 \div 2 = 1$ 餘 $0$
$1 \div 2 = 0$ 餘 $1$
從下往上讀取餘數，得到二進位表示為 $1001_2$。

2. 分數部分轉換:
將十進位分數 $\frac{3}{8}$ 轉換為二進位。方法是連續乘以 2，取整數部分，直到小數部分為 0 或達到所需精度。

這是一個關於堆疊（Stack）資料結構操作的題目。堆疊是一種後進先出（LIFO, Last-In, First-Out）的資料結構。push(x) 操作將元素 x 放入堆疊頂部，pop() 操作則移除並傳回堆疊頂部的元素。

我們來一步步模擬堆疊的操作過程：

初始狀態：堆疊為空 []

1. push(9): 將 9 放入堆疊。
   堆疊：[9]

2. push(7): 將 7 放入堆疊。
   堆疊：[9, 7] (7 在頂部)

3. push(6): 將 6 放入堆疊。
   堆疊：[9, 7, 6] (6 在頂部)

4. pop(): 移除並傳回頂部元素 6。
   輸出：6
   堆疊：[9, 7]

5. pop(): 移除並傳回頂部元素 7。
   輸出：7
   堆疊：[9]

這題要求計算三種常見演算法在處理 $n$ 個項目時的時間複雜度（Computational Complexity）。時間複雜度通常用大 O 符號（Big O notation）表示，描述了演算法執行時間隨輸入規模 $n$ 增長的趨勢。

1. Binary Search (二元搜尋):

   • 前提: 二元搜尋適用於已排序的陣列或列表。
   • 工作原理: 在已排序的資料中，每次都檢查中間元素。如果目標值與中間元素相等，則搜尋成功。如果目標值小於中間元素，則在左半部繼續搜尋；如果目標值大於中間元素，則在右半部繼續搜尋。這個過程不斷將搜尋範圍縮小一半。
   • 時間複雜度:
     • 最佳情況（Best Case）: $O(1)$，當目標值恰好是中間元素時。
     • 平均情況（Average Case）: $O(\log n)$。
     • 最差情況（Worst Case）: $O(\log n)$，當目標值不在列表中，或位於搜尋過程的最後一步被找到時。
   • 解釋: 每次搜尋操作，搜尋範圍都會被縮小一半。搜尋範圍從 $n$ 縮小到 $n/2, n/4, ..., 1$ 所需的步驟數大約是 $\log_2 n$。

2. Quick Sort (快速排序):

   • 工作原理: 採用分治法（Divide and Conquer）。選擇一個「基準點」（pivot），將陣列分割成兩部分：小於基準點的元素放在左邊，大於基準點的元素放在右邊。然後遞迴地對左右兩部分進行排序。
   • 時間複雜度:
     • 最佳情況（Best Case）: $O(n \log n)$，當每次分割都恰好將陣列分成兩個大小相近的子陣列時。
     • 平均情況（Average Case）: $O(n \log n)$，這是 Quick Sort 最常見的表現。