# 演算法推理：選教材，並證明最佳化答案 — 學習任務單

[學習指南](https://unireadinglist.com/zh-tw/guides/algorithmic-reasoning/)

[課程主題: 演算法](https://unireadinglist.com/zh-tw/subjects/computer-science/#course-algorithms)

來源核驗日期: 2026-11-04

學習路線與例題編輯責任：University Reading List 編輯專案。

適合已學基礎程式設計、遞迴、資料結構和離散數學的大學讀者。Erickson明確假定這些準備，免費不等於零基礎程式書。下列排程資料、任務與答案為本站創作，不是出版社原題或工作場景實證。

## 選擇你的起點

- [ ] 會寫程式，但難以解釋正確性
  能使用歸納法和基本資料結構後，以Erickson免費主線練習；先寫不變量或遞迴式，再轉成程式。

- [ ] 課程指定CLRS
  依第四版指定章節與虛擬碼約定學習。先選設計章節，不把全書廣度當成逐頁讀完的義務。

- [ ] 難以辨認問題模型
  用Skiena整理問題類型和候選方法，再回到證明型解釋；實作故事不能自動證明正確性。

## 三本書如何取捨

### Algorithms

Jeff Erickson · 1 · 2019
免費證明與設計主線

適合何時選擇: 已有歸納基礎，願意自己寫反例、論證和遞迴式。
何時另選路線: 還需首次學習堆疊、雜湊表或程式語法。
建議閱讀範圍: 2019版第1–4章，然後選讀第5–8章圖論。
限制與取捨: 作者列出省略的先修資料結構，也不應讀者要求提供解答。免費正文不等於公開答案庫。

#### 選書前試做

讀第3–4章後，用下方五任務說明最早結束規則為何可能不能最大化報酬。
檢查標準: 列出貪婪方案及報酬更高的可行方案，核對ID；不能用任務個數取代報酬目標。

你的筆記:

________________________________

[官方免費閱讀](https://jeffe.cs.illinois.edu/teaching/algorithms/)

[書目資訊與取得方式](https://unireadinglist.com/zh-tw/subjects/computer-science/algorithms-erickson/)

### 演算法導論

Thomas H. Cormen et al. · 4 · 2022
範圍廣的第四版參考

適合何時選擇: 課程指定CLRS，或需跨方法一致的虛擬碼。
何時另選路線: 只需短導論，且尚不能選閱讀範圍或確認先修。
建議閱讀範圍: 在第四版定位Dynamic Programming和Greedy Algorithms，按需回看分析與資料結構，以手中目錄為準。
限制與取捨: 2022年所選精裝ISBN為9780262046305。教員受限資料不是自學者的公開解答權利，紙本標識也不含所有數位產品。

#### 選書前試做

先用文字定義最佳化子問題，再說明最優後續決策可忽略哪些資訊。
檢查標準: 狀態定義應決定選項與基底；認得公式外形不等於證明最佳子結構。

你的筆記:

________________________________

ISBN: 978-0-262-04630-5

[書目資訊與取得方式](https://unireadinglist.com/zh-tw/subjects/computer-science/introduction-to-algorithms/)

### 演算法設計手冊

Steven S. Skiena · 3 · 2020
建模與實作伴讀

適合何時選擇: 需要把應用敘述轉成組合問題並比較實作方向。
何時另選路線: 希望只憑問題目錄或社群答案取代證明。
建議閱讀範圍: 第三版實用設計部分，尤其第10章動態規劃；明確建模後再查目錄。
限制與取捨: 作者站點的解答Wiki不保證社群答案正確。把它當成待檢查的論證，而非裁決。

#### 選書前試做

將同一預約問題寫成生活敘述與帶權區間模型，列明相容條件和目標。
檢查標準: 每個現實條件要進入模型或明確排除；熟悉的名稱不能讓限制消失。

你的筆記:

________________________________

ISBN: 9783030542559

[書目資訊與取得方式](https://unireadinglist.com/zh-tw/subjects/computer-science/algorithm-design-manual/)

## 檢查先修準備

### 可行與最優有何不同？

你的筆記:

________________________________

### 遞迴式為何需要歸納思路？

你的筆記:

________________________________

### 時間複雜度要交代什麼？

你的筆記:

________________________________

## 六步學習與具體成果

- [ ] 先寫模型

建議閱讀範圍: Erickson第0章與Skiena建模討論。

動手產出: 寫清固定起訖、半開區間、報酬、單資源及總報酬目標。

檢查標準: 基本模型允許結束後立即接續，不含路程或準備時間。

你的筆記:

________________________________

- [ ] 反駁未證明的捷徑

建議閱讀範圍: Erickson第4章與CLRS貪婪法。

動手產出: 依最早結束執行，再找報酬更高的可行反例。

檢查標準: 展示所選ID；反例否定特定普遍主張，不代表所有貪婪法失敗。

你的筆記:

________________________________

- [ ] 定義狀態

建議閱讀範圍: Erickson第3章與CLRS動態規劃。

動手產出: 依結束排序，用完整句子解釋V(j)、p(j)。

檢查標準: V(j)限前j任務；p(j)是相容的最後前任務，沒有則為0。

你的筆記:

________________________________

- [ ] 計算並說明表格

建議閱讀範圍: 同一動態規劃範圍。

動手產出: 逐行比較兩選項，記錄前驅並還原方案。

檢查標準: 最優解不是不含j，就是含j及相容前綴最優解；說明分類完整。

你的筆記:

________________________________

- [ ] 改變一項限制

建議閱讀範圍: Skiena第10章與變式。

動手產出: 加入規定間隔，重算相容性後再用遞迴式。

檢查標準: 即使報酬與式子外形不變，p陣列改變仍可能使舊解不可行。

你的筆記:

________________________________

- [ ] 提交可檢核的成果

建議閱讀範圍: 回到最弱步驟對應教材。

動手產出: 提交模型、反例、表格、還原、複雜度和邊界檢驗。

檢查標準: 他人能重算報酬與可行性；一次小程式計時不是漸近分析。

你的筆記:

________________________________

## 原創例題與解析: 原創例題：最早結束不會最大化報酬

五個虛構任務的(開始,結束,報酬)為a=(0,3,5)、b=(3,5,4)、c=(0,5,12)、d=(5,7,3)、e=(4,8,11)。一份資源只能執行不重疊任務。求最大報酬並比較最早結束法。

前提假設: 採半開區間，允許結束後立即接續；時刻固定、不可拆分、非負報酬相加。無準備間隔、路程或不確定性。同結束時刻排b再c，改變表次序而不改最優值。

你的筆記:

________________________________

## 改變假設，再做一題: 變式：任務之間必須保留間隔

保留任務與報酬，但相鄰被選任務間至少留2個時間單位。最後任務後不需間隔，時刻不可移動。

你的筆記:

________________________________

## 進入下一階段之前

- 能明確說明目標與全部相容規則。
- 能解釋遞迴式並還原可行方案。
- 能改一項假設，指出須改的資料或論證。

## 答案與解釋

### 可行與最優有何不同？

可行是滿足全部限制；最優要與所有可行候選比較目標值。一個看似好的方案不能取代一般論證。

### 遞迴式為何需要歸納思路？

它連接已解的小問題與目前最優解，必須說明分類涵蓋所有可能。

### 時間複雜度要交代什麼？

定義n、輸入表示與所數操作；排序、前驅、填表和還原各自計成本。

### 原創例題：最早結束不會最大化報酬

1. 最早結束選a、b、d，得5+4+3=12；可行的a、e得16，所以該規則不能一般地解帶權目標。
2. 順序a、b、c、d、e的p=\[0,1,0,3,1\]。V(0)=0，V(j)=max(V(j−1),reward(j)+V(p(j)))，分別表示不選與選j。
3. V=\[0,5,9,12,15,16\]。末行選e，回到前驅a，11+5=16。
4. 排序和二分搜尋前驅可用O(n log n)，填表與還原O(n)，儲存O(n)。有限資料檢驗與一般論證應區分。

最大值16由a與e取得；三任務貪婪方案得12。個數與報酬是不同目標。

檢驗結果: 獨立列舉32個子集並排除不相容者，應得同一最優值。還原後仍須查端點，不只相信表值。

### 改變假設，再做一題: 變式：任務之間必須保留間隔

1. 相容條件為finish(i)+2≤start(j)，p=\[0,0,0,1,0\]。a可接d，卻不能接b或e。
2. 新V=\[0,5,5,12,12,12\]。c單獨得12；舊a、e因3+2\>4不可行。

新最優值是c單獨的12。保留遞迴式並重建相容資料；從舊報酬扣固定費用是別的模型。

檢驗結果: 依新條件重列舉；單一任務不需末尾間隔。舊最優值是放寬限制後的上界，不是此處的可行答案。

## 常見誤區

### 把虛擬碼當證明

本例程式算對，不表示對所有輸入正確。區分有限測試與一般論證。

### 以名稱取代模型

準備時間可能破壞熟悉的歸約；先說明排除的條件。

### 只計部分複雜度

不能忽略排序或平方級前驅掃描，再稱全實作線性；上界須對應實作。

## 來源與版次核驗

- [Jeff Erickson: 2019 edition, prerequisites and chapter files](https://jeffe.cs.illinois.edu/teaching/algorithms/)
  著者資料核實2019版、免費正文、先修與章序；試做和資料由本站創作。

- [MIT Press: Introduction to Algorithms, fourth edition](https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/)
  出版社確認第四版、2022年與紙本/電子不同標識；不承諾受限教員資料。

- [Springer: The Algorithm Design Manual, third edition](https://link.springer.com/book/10.1007/978-3-030-54256-6)
  出版社支持實用設計和參考範圍；選書判斷不是學習效果實測。

- [Author-hosted third-edition chapter and solution index](https://www.algorist.com/algowiki/)
  作者站點確認動態規劃位置並說明社群答案未獲認證。

這些是本站建議的學習活動，並非大學官方作業，也不代表對每本書逐頁通讀。

[編輯與選書方法](https://unireadinglist.com/zh-tw/editorial/)