中正 114 年資管所 計算機概論 參考答案

(一) 傳統 AI：Association Rule Mining，用於零售業 Market Basket Analysis（買了 X 的人也買了 Y）。理由：交易紀錄不需標記即可探勘；Apriori 能有效找出 Frequent Itemset；規則可解釋，可直接用於陳列與促銷。

(二) 現代 AI：Transformer-based Large Language Model，用於 ChatGPT 等對話式生成服務。理由：Self-Attention 能捕捉長距離上下文；運算可平行化，能在超大語料上預訓練；預訓練加微調可泛化到多種任務。

a. Data warehousing：以 ETL 整合異質來源，建立主題導向的大型資料庫；目標是支援 OLAP 與決策。

b. Data structure：資料在電腦中的組織、儲存與存取方式；目標是提升演算法的時間與空間效率。

c. Data mining：從大量資料挖掘隱藏樣式與規則；目標是支援預測與決策。

d. Big data：處理 Volume、Velocity、Variety 特性的巨量資料；目標是以分散式運算擷取商業洞察。

a. Use case diagram：描述 actor 與系統互動，界定功能需求；用於需求分析初期。

b. Class diagram：描述類別的屬性、方法與關係；用於系統設計的靜態結構塑模。

c. ER diagram：描述 entity、relationship 與屬性；用於資料庫概念設計。

d. Collaboration diagram：描述物件為完成功能交換的訊息與連結；用於動態互動塑模。

e. State-transition diagram：描述單一物件受事件觸發的狀態轉換；用於狀態變化明顯的物件。

f. Deployment diagram：描述軟體元件部署在哪些硬體節點及其連接；用於實體架構規劃。

g. CRC diagram：以卡片記錄類別的責任與協作對象；用於 OOAD 早期分配類別職責。

瀏覽器的「上一頁」：造訪新頁面時 push，按上一頁時 pop 出最近造訪的頁面，符合 LIFO。

音樂播放清單：常在中間插入、刪除歌曲，Linked List 已知位置時只改指標 $O(1)$，Array 需搬移 $O(n)$；Doubly Linked List 可 $O(1)$ 切換上一首、下一首。

CPU 排程：依優先權而非到達順序服務；以 Binary Heap 實作，Insert 與 Extract-Max 皆 $O(\log n)$，可隨時取出優先權最高的工作。

資料庫索引：平衡時搜尋、插入、刪除皆 $O(\log n)$，且中序走訪可依序輸出全部資料。

a. Greedy method：每一步選當下最好的選項，不回頭。

b. Dynamic programming：拆成重疊子問題，以表格記錄子問題的解避免重算，由小組合出大。

c. Divide and conquer：切成互不重疊的子問題，遞迴求解後合併。

d. Prune and search：每輪以線性時間剪掉固定比例的候選資料，再對剩下部分遞迴搜尋，$T(n)=T(\alpha n)+O(n)=O(n)$。

a. Recovery：系統當機、斷電或媒體損壞後重新啟動時，依 log 執行 redo／undo 還原到一致狀態。

b. Concurrency control：多筆交易同時存取同一筆資料時，避免 lost update、dirty read 等問題。

c. Checkpoint：定期把已異動的緩衝頁寫回磁碟，縮短復原時間。

d. Roll-back：單一交易出錯、死結被選為犧牲者或主動放棄時，撤銷其已做的異動。

a. call-by-value：caller 複製值傳入；called 只改區域副本，不影響原變數。

b. call-by-address：caller 傳位址；called 以位址直接讀寫原變數。

c. call-by-in-out：caller 複製值傳入；called 操作副本，返回時再把值複製回原變數。

d. call-by-name：caller 傳未求值的運算式；called 每次用到參數時重新求值。

e. call-by-reference：caller 傳變數的參考（別名）；called 直接操作原變數。

CISC 優點：指令豐富，單一指令可完成複雜運算，目的碼小。缺點：指令長度不一、解碼複雜，難以管線化。

RISC 優點：指令精簡、長度固定，易管線化，電路簡單、時脈高。缺點：目的碼較大，需較多暫存器與較好的編譯器。

轉向 RISC 的原因：記憶體變便宜，省記憶體不再重要；管線化、超純量等技術更適合 RISC；行動裝置重視低功耗；編譯器最佳化已成熟。

應用一：唯讀資料存取（唯讀資料庫查詢、共享唯讀檔案），資源可同時共享，消除 (a) mutual exclusion。

應用二：執行前一次取得所有資源（批次作業預先宣告資源），取不齊就不持有，消除 (b) hold and wait。

c（DHCP）→ d（ARP）→ a（DNS）→ e（BGP）→ b（Three-way handshaking）→ f（HTTP）