你的進度
0/ 45 節已標記完成
下一節: 正確性、成本模型與分治
完成記錄儲存在此瀏覽器中。
這門課在網上
CSCI3160 筆記裏的內容
數字只算這門課 45 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。
在網上定理卡 111 · 定義 84 · 反例 61 · 概念視角 30 · 思想史 1 · 證明透視 53
第 1 章 · 12 節
正確性與分治
正確性與分治
- 1.1
正確性、成本模型與分治
證明迭代及遞歸算法的正確性,分清輸入大小與時間界,並推導合併排序的遞推式。
- 1.2
二進制計數器與攤還分析
以總計數及勢能證明操作序列上界,並處理循環溢出與混合操作的限制。
- 1.3
用二分搜尋定位可行性邊界
證明單調謂詞的邊界搜尋,再結合經證明的貪心判定,最小化連續分塊的最大負載。
- 1.4
帶漸近代價項的主定理
證明三種常見的遞歸情形,以及正則性條件的作用。
- 1.5
分治遞推式的遞歸樹
透過逐層求和,推導冪型附加代價遞推式的三種情形。
- 1.6
Karatsuba 乘法
推導三次乘積的乘法,並分析取整後的遞歸規模。
- 1.7
快速傅立葉變換與卷積
推導基二蝴蝶運算、逆變換,以及以補零實作的多項式乘法。
- 1.8
比較排序的下界
證明決策樹下界,並區分比較排序與計數排序。
- 1.9
隨機化快速排序的期望比較次數
利用鍵對指示變量推導快速排序期望比較次數的精確值。
- 1.10
最壞情況線性時間選擇
以五元組中位數選取主元,並證明線性比較次數上界。
- 1.11
隨機選擇與期望線性工作量
利用平衡主元階段證明快速選擇的期望線性界。
- 1.12
動態陣列的攤銷分析
以聚合論證與勢能論證界定陣列倍增的成本。
第 2 章 · 11 節
動態規劃與貪心算法
動態規劃與貪心算法
- 2.1
最長公共子序列
推導前綴動態規劃,並重構一個最優公共子序列。
- 2.2
矩陣鏈動態規劃
推導、計算並重構矩陣乘積的最優括號化方式。
- 2.3
貪心選擇與動態規劃
用交換論證證明區間排程,推導加權區間及背包遞推式,並解釋狀態設計與解的重建。
- 2.4
最長遞增子序列:狀態、末尾值與重構
證明嚴格遞增子序列的二次動態規劃及二分搜尋法,並重構真正的解。
- 2.5
閱讀加權排程的運算軌跡
用六個工作的例子比較前驅前綴與回溯選擇。
- 2.6
單機排程與相鄰交換
推導按到期日和處理時間權重比排序的規則,理解為甚麼排程目標一變,貪心證明也必須改變。
- 2.7
霍夫曼編碼與貪心交換論證
證明在二元前綴碼中合併兩個最小權重的做法是最優的。
- 2.8
擬陣上的貪心優化
利用擴充性質與基交換證明加權貪心定理。
- 2.9
背包問題:分數貪心與零一動態規劃
證明分數背包的密度規則,推導零一背包狀態,並還原所選物件。
- 2.10
編輯距離與動態規劃
推導編輯距離的遞推式,並還原一個最優的編輯序列。
- 2.11
最優二叉搜尋樹
利用區間動態規劃處理成功搜尋與失敗搜尋的成本。
第 3 章 · 10 節
圖與網絡流
圖與網絡流
- 3.1
最大流與最小割
利用殘量網絡證明最優性並計算最大流。
- 3.2
從不變量理解圖算法
明確圖、權重與數據結構假設,證明遍歷、生成樹及最短路徑算法。
- 3.3
二分圖匹配、Hall 條件與頂點覆蓋證書
利用交替路徑構造最優性證書,並證明 Hall 定理。
- 3.4
有向無環圖中的拓撲序與最短路徑
證明拓撲排序,以及無環圖中容許負邊權的線性時間最短路徑算法。
- 3.5
強連通分量
證明兩遍掃描分量算法背後的完成時間次序。
- 3.6
以動態規劃求全源最短路徑
在明確的假設下推導 Floyd–Warshall 遞推式及其原地更新。
- 3.7
Prim 最小生成樹算法
證明不斷生長的樹的不變量,並核算二元堆積操作的成本。
- 3.8
不相交集合森林與按大小合併
證明按大小合併的樹高為對數級,並將此結構應用於 Kruskal 算法。
- 3.9
最短增廣路徑與多項式時間網絡流
利用殘量距離證明 Edmonds–Karp 增廣次數上界。
- 3.10
二分圖匹配與 Hall 證書
尋找增廣路徑,並推導匹配證書、覆蓋證書與 Hall 證書。
第 4 章 · 6 節
歸約與 NP 完全性
歸約與 NP 完全性
- 4.1
多項式歸約與 NP 完全性
區分驗證與搜尋,證明歸約方向,並完整構造從 3-SAT 到團及頂點覆蓋的歸約。
- 4.2
從布爾公式到 3-SAT
構造邏輯閘子句與長子句鏈,證明精確的賦值擴張性質,並從明確聲明的 SAT 起點推導 3-SAT 完全性。
- 4.3
由 3-SAT 至三著色的歸約
構造並驗證三著色問題的顯式子句構件。
- 4.4
由 3-SAT 到子集和問題的歸約
以無進位的十進制數位列編碼變量選擇與子句滿足性。
- 4.5
哈密頓路徑、哈密頓圈與旅行推銷員歸約
在不同圖模型之間變換哈密頓見證,並比較度量旅行推銷員與任意成本旅行推銷員的巡迴成本。
- 4.6
近似算法:頂點覆蓋與集合覆蓋
定義近似比,證明極大匹配給出頂點覆蓋的二近似,並證明貪心集合覆蓋的調和數保證。
第 5 章 · 1 節
前綴碼
貪心合併與最優帶權二元碼。
- 5.1
霍夫曼編碼與貪心交換
證明二元前綴碼的最小兩權重合併法則。
第 6 章 · 1 節
擬陣與貪心算法
以增廣性證明加權貪心定理。
- 6.1
為何加權貪心法適用於擬陣的基
利用前綴秩證明最大權基定理,並區分基與任意獨立集。
第 7 章 · 2 節
最短路徑
以邊數上限證明鬆弛,並辨識相關的負環。
- 7.1
Bellman–Ford:鬆弛、邊數上限與負環
由限制邊數的遞推式推導最短路徑鬆弛,證明原地更新算法,並分清可達負環與不影響查詢的負環。
- 7.2
Dijkstra 算法:已確定頂點與惰性優先隊列
證明非負邊權下的貪心步驟,處理過時堆記錄與零權平手,並在有向多重圖中按邊識別碼重建路徑。
第 8 章 · 1 節
動態規劃:重構
重構最長公共子序列,並明確計算時間與空間開銷。
- 8.1
最長公共子序列:前綴不變量與節省空間的重建
證明 LCS 遞推、重建最優序列、維持滾動行不變量,並以明確記憶體成本推導分治重建。
第 9 章 · 1 節
分治應用
幾何分治與排序不變量。
- 9.1
最近點對:帶狀區域的裝填、y 次序與精確距離平方
證明只比較其後七個鄰點的合併步驟,在遞歸中保留 y 排序,並在不用浮點距離比較下返回可核實的最近點對。