跳到正文

CSCI3160

算法設計及分析

正確性與分治、攤還分析與隨機化分析、動態規劃、貪心算法與擬陣、最短路徑、網絡流與匹配,以及 NP 完全性。

9 章 · 45 節EN · 繁 · 简
我的課程筆記

你的進度

0/ 45 節已標記完成

下一節: 正確性、成本模型與分治

完成記錄儲存在此瀏覽器中。

這門課在網上

CSCI3160 筆記裏的內容

定理卡
111
定義
84
反例
61
概念視角
30
思想史
1
證明透視
53

有思想史的節

這些思想史還沒有放上時間線。

這門課的概念視角還沒有記錄到網上。

在知識圖譜中打開這門課

數字只算這門課 45 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。

在網上定理卡 111 · 定義 84 · 反例 61 · 概念視角 30 · 思想史 1 · 證明透視 53

這些思想史還沒有放上時間線。

這門課的概念視角還沒有記錄到網上。

在知識圖譜中打開這門課

數字只算這門課 45 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。

第 1 章 · 12 節

正確性與分治

正確性與分治

定理 25 · 定義 19反例 15視角 9證明透視 13

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 1.1

    正確性、成本模型與分治

    證明迭代及遞歸算法的正確性,分清輸入大小與時間界,並推導合併排序的遞推式。

  2. 1.2

    二進制計數器與攤還分析

    以總計數及勢能證明操作序列上界,並處理循環溢出與混合操作的限制。

  3. 1.3

    用二分搜尋定位可行性邊界

    證明單調謂詞的邊界搜尋,再結合經證明的貪心判定,最小化連續分塊的最大負載。

  4. 1.4

    帶漸近代價項的主定理

    證明三種常見的遞歸情形,以及正則性條件的作用。

  5. 1.5

    分治遞推式的遞歸樹

    透過逐層求和,推導冪型附加代價遞推式的三種情形。

  6. 1.6

    Karatsuba 乘法

    推導三次乘積的乘法,並分析取整後的遞歸規模。

  7. 1.7

    快速傅立葉變換與卷積

    推導基二蝴蝶運算、逆變換,以及以補零實作的多項式乘法。

  8. 1.8

    比較排序的下界

    證明決策樹下界,並區分比較排序與計數排序。

  9. 1.9

    隨機化快速排序的期望比較次數

    利用鍵對指示變量推導快速排序期望比較次數的精確值。

  10. 1.10

    最壞情況線性時間選擇

    以五元組中位數選取主元,並證明線性比較次數上界。

  11. 1.11

    隨機選擇與期望線性工作量

    利用平衡主元階段證明快速選擇的期望線性界。

  12. 1.12

    動態陣列的攤銷分析

    以聚合論證與勢能論證界定陣列倍增的成本。

第 2 章 · 11 節

動態規劃與貪心算法

動態規劃與貪心算法

定理 24 · 定義 18反例 15視角 10證明透視 12

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 2.1

    最長公共子序列

    推導前綴動態規劃,並重構一個最優公共子序列。

  2. 2.2

    矩陣鏈動態規劃

    推導、計算並重構矩陣乘積的最優括號化方式。

  3. 2.3

    貪心選擇與動態規劃

    用交換論證證明區間排程,推導加權區間及背包遞推式,並解釋狀態設計與解的重建。

  4. 2.4

    最長遞增子序列:狀態、末尾值與重構

    證明嚴格遞增子序列的二次動態規劃及二分搜尋法,並重構真正的解。

  5. 2.5

    閱讀加權排程的運算軌跡

    用六個工作的例子比較前驅前綴與回溯選擇。

  6. 2.6

    單機排程與相鄰交換

    推導按到期日和處理時間權重比排序的規則,理解為甚麼排程目標一變,貪心證明也必須改變。

  7. 2.7

    霍夫曼編碼與貪心交換論證

    證明在二元前綴碼中合併兩個最小權重的做法是最優的。

  8. 2.8

    擬陣上的貪心優化

    利用擴充性質與基交換證明加權貪心定理。

  9. 2.9

    背包問題:分數貪心與零一動態規劃

    證明分數背包的密度規則,推導零一背包狀態,並還原所選物件。

  10. 2.10

    編輯距離與動態規劃

    推導編輯距離的遞推式,並還原一個最優的編輯序列。

  11. 2.11

    最優二叉搜尋樹

    利用區間動態規劃處理成功搜尋與失敗搜尋的成本。

第 3 章 · 10 節

圖與網絡流

圖與網絡流

定理 24 · 定義 23反例 15視角 4證明透視 13

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 3.1

    最大流與最小割

    利用殘量網絡證明最優性並計算最大流。

  2. 3.2

    從不變量理解圖算法

    明確圖、權重與數據結構假設,證明遍歷、生成樹及最短路徑算法。

  3. 3.3

    二分圖匹配、Hall 條件與頂點覆蓋證書

    利用交替路徑構造最優性證書,並證明 Hall 定理。

  4. 3.4

    有向無環圖中的拓撲序與最短路徑

    證明拓撲排序,以及無環圖中容許負邊權的線性時間最短路徑算法。

  5. 3.5

    強連通分量

    證明兩遍掃描分量算法背後的完成時間次序。

  6. 3.6

    以動態規劃求全源最短路徑

    在明確的假設下推導 Floyd–Warshall 遞推式及其原地更新。

  7. 3.7

    Prim 最小生成樹算法

    證明不斷生長的樹的不變量,並核算二元堆積操作的成本。

  8. 3.8

    不相交集合森林與按大小合併

    證明按大小合併的樹高為對數級,並將此結構應用於 Kruskal 算法。

  9. 3.9

    最短增廣路徑與多項式時間網絡流

    利用殘量距離證明 Edmonds–Karp 增廣次數上界。

  10. 3.10

    二分圖匹配與 Hall 證書

    尋找增廣路徑,並推導匹配證書、覆蓋證書與 Hall 證書。

第 4 章 · 6 節

歸約與 NP 完全性

歸約與 NP 完全性

定理 13 · 定義 15反例 6視角 5思想史 1證明透視 7

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 4.1

    多項式歸約與 NP 完全性

    區分驗證與搜尋,證明歸約方向,並完整構造從 3-SAT 到團及頂點覆蓋的歸約。

  2. 4.2

    從布爾公式到 3-SAT

    構造邏輯閘子句與長子句鏈,證明精確的賦值擴張性質,並從明確聲明的 SAT 起點推導 3-SAT 完全性。

  3. 4.3

    由 3-SAT 至三著色的歸約

    構造並驗證三著色問題的顯式子句構件。

  4. 4.4

    由 3-SAT 到子集和問題的歸約

    以無進位的十進制數位列編碼變量選擇與子句滿足性。

  5. 4.5

    哈密頓路徑、哈密頓圈與旅行推銷員歸約

    在不同圖模型之間變換哈密頓見證,並比較度量旅行推銷員與任意成本旅行推銷員的巡迴成本。

  6. 4.6

    近似算法:頂點覆蓋與集合覆蓋

    定義近似比,證明極大匹配給出頂點覆蓋的二近似,並證明貪心集合覆蓋的調和數保證。

第 5 章 · 1 節

前綴碼

貪心合併與最優帶權二元碼。

定理 4 · 定義 2反例 2視角 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 5.1

    霍夫曼編碼與貪心交換

    證明二元前綴碼的最小兩權重合併法則。

第 6 章 · 1 節

擬陣與貪心算法

以增廣性證明加權貪心定理。

定理 2 · 定義 1反例 2證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 6.1

    為何加權貪心法適用於擬陣的基

    利用前綴秩證明最大權基定理,並區分基與任意獨立集。

第 7 章 · 2 節

最短路徑

以邊數上限證明鬆弛,並辨識相關的負環。

定理 10 · 定義 4反例 3證明透視 3

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 7.1

    Bellman–Ford:鬆弛、邊數上限與負環

    由限制邊數的遞推式推導最短路徑鬆弛,證明原地更新算法,並分清可達負環與不影響查詢的負環。

  2. 7.2

    Dijkstra 算法:已確定頂點與惰性優先隊列

    證明非負邊權下的貪心步驟,處理過時堆記錄與零權平手,並在有向多重圖中按邊識別碼重建路徑。

第 8 章 · 1 節

動態規劃:重構

重構最長公共子序列,並明確計算時間與空間開銷。

定理 6 · 定義 1反例 1視角 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 8.1

    最長公共子序列:前綴不變量與節省空間的重建

    證明 LCS 遞推、重建最優序列、維持滾動行不變量,並以明確記憶體成本推導分治重建。

第 9 章 · 1 節

分治應用

幾何分治與排序不變量。

定理 3 · 定義 1反例 2證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 9.1

    最近點對:帶狀區域的裝填、y 次序與精確距離平方

    證明只比較其後七個鄰點的合併步驟,在遞歸中保留 y 排序,並在不用浮點距離比較下返回可核實的最近點對。

Vercel 瀏覽統計與公開頁面效能量度均須分別取得同意,兩者均非使用網站的必要條件。

網站功能儲存(按需使用)

安全、登入及你選擇的偏好會按需使用儲存,與可選統計分開處理。

撤回會停止後續統計;需要卸載已載入的統計程式時,頁面會重新載入。已傳送的資料不會因此刪除。

查看 Cookie 與儲存詳情