資訊處理 92 年演算法考古題（共 4 題）
資料來源：考選部歷屆試題｜法律人 LawPlayer 整理
https://lawplayer.com/exam/information-processing/92-%E6%BC%94%E7%AE%97%E6%B3%95

第 1 題
已知甲電腦在input size 為1000 時，執行A、B、C 三個演算法都需要1 分鐘，
A、B、C 三個演算法的Time Complexity 分別為a n、b n2、c 10n（a、b、c 為常
數，n 為input size）。假設乙電腦的執行速度比甲電腦快10000 倍，請問對於A、
B、C 三個演算法，乙電腦在1 分鐘內可以解的input size 最大是多少？（24 分）

第 2 題
請證明利用Greedy Approach 來解Fractional Knapsack Problem 可以得到最佳解。
（15 分）
請設計一個Dynamic Programming 的演算法來解0-1。Knapsack Problem（須加上
適當的說明來解釋你的設計），並分析該演算法的Time Complexity。（15 分）

第 3 題
請簡述NP 與NP-Complete 的定義。（6 分）
請簡述Cook’s Theorem 的內容（不須證明），並說明其對研究NP-Complete 重要
性。（10 分）
要如何才能證明P=NP 或P≠NP？請分別說明。（10 分）
請問Sorting Problem 是不是NP？請說明原因。 （10 分）

第 4 題
請簡述何謂Pseudo-Polynomial-Time Algorithm？（10 分）

題目為考試當年公告版本，實務標準請以現行規範為準。