你的進度
0/ 29 節已標記完成
下一節: 容斥原理與滿射計數
完成記錄儲存在此瀏覽器中。
這門課在網上
CSCI3190 筆記裏的內容
數字只算這門課 29 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。
在網上定理卡 90 · 定義 70 · 反例 34 · 概念視角 17 · 思想史 1 · 證明透視 33
第 1 章 · 5 節
計數
計數
- 1.1
容斥原理與滿射計數
逐一追蹤對象的貢獻,處理互相重疊的例外。
- 1.2
在對稱下計算構型
證明不動點數目的平均公式,並計算二進制循環字串。
- 1.3
函數計數、子集選取與遞歸樹的閱讀
區分有序分配與子集,證明鴿籠原理,定義漸近界,並透過各層求和推導平衡遞推式的成本。
- 1.4
集合劃分、滿射與斯特林遞推
區分組的標籤與元素歸屬,證明斯特林數和滿射的計數公式,並用經過論證的動態規劃計算精確答案。
- 1.5
離散概率、期望與線性性
定義有限概率空間、隨機變量與期望,證明期望的線性性與 Markov 不等式,並用指示變量分析隨機化算法。
第 3 章 · 2 節
算法設計
算法設計
- 3.1
貪心選擇、分治與動態規劃
以排程與合併排序比較算法設計原則。
- 3.2
取整子問題與主遞歸界
證明整數上取整與下取整遞歸的分治工作量界,計入葉子並區分幾何級數的各種情形,並在恰為冪的輸入上推導對數型代價的臨界閾值。
第 4 章 · 5 節
圖算法
生成樹、連通性、最短行走及拓撲次序。
- 4.1
Kruskal 算法與割的交換論證
構造最小生成樹,並證明每條貪心選邊都可屬於一棵最優樹。
- 4.2
Bellman–Ford 與可達負環
推導邊數受限的最短行走,並找出因負環而無下界的距離。
- 4.3
拓撲次序與有向環證書
證明以隊列求拓撲次序的算法,並構造有向環見證。
- 4.4
不相交集合森林與按大小合併
維護不斷合併的連通分量,並用倍增證明對數界。
- 4.5
圖的遍歷、最短路徑與生成樹
透過前沿不變量證明 BFS 與 Dijkstra 算法的正確性,推導最小生成樹的割性質,並區分三種不同的優化目標。
第 5 章 · 3 節
整數算術
整數算術
- 5.1
最大公因數、模逆元與快速冪
證明歐幾里得算法、線性同餘與重複平方法。
- 5.2
通用雜湊與固定鍵碰撞界
證明有限域上雜湊族的碰撞界,並將其應用於鏈結法及隨機重試。
- 5.3
傅立葉蝴蝶運算與多項式卷積
推導離散傅立葉(Fourier)變換及其分治求值方法,並說明計算一般卷積所需的補零。
第 6 章 · 3 節
字串算法
前綴回退與精確匹配。
- 6.1
前綴函數與重疊字串匹配
推導 KMP 回退、證明線性掃描,並保留重疊出現的位置。
- 6.2
編輯距離與最優對齊
推導編輯距離的前綴動態規劃,證明其正確性並重構最優編輯序列。
- 6.3
以滾動多項式指紋搜尋字串
推導滾動更新與有限域碰撞界,明確說明核對和輸入假設。
第 8 章 · 2 節
排序算法
排序算法
- 8.1
逆序對、隨機化快速排序與穩定基數排序
以逆序對分析插入排序,推導隨機化快速排序的期望比較次數,並在明確的鍵模型下證明穩定計數排序與基數排序。
- 8.2
二元堆、線性建堆與堆排序
證明下沉(sift-down)的正確性,透過對各節點高度求和證明由下而上建堆的線性時間界,並證明原地堆排序,同時區分堆序、穩定性與優先隊列的記憶體配置成本。
第 9 章 · 1 節
數論算法
數論算法
- 9.1
中國剩餘定理與合數見證
保持 CRT 合併不變量,證明試除法與強合數判據,並區分合數見證和未經證明的質數結論。
第 10 章 · 1 節
多項式算法
快速 Fourier 求值與係數卷積。
- 10.1
FFT 與多項式卷積
推導基二 Fourier 求值及反變換,並在沒有循環混疊下相乘多項式。
第 11 章 · 1 節
歐幾里得算法與同餘
把歐幾里得證書延伸至模方程及相容的非互質餘數系統。
- 11.1
歐幾里得不變量與同餘證書
把歐幾里得證書延伸至模方程及相容的非互質餘數系統。
第 12 章 · 5 節
邏輯、集合與關係
邏輯、集合與關係
- 12.1
命題等價、範式與歸結
構造有限布爾公式的範式,用歸結消去變量,並區分等價與可滿足性等價。
- 12.2
謂詞邏輯、見證的依賴與有限模型檢驗
準確理解變量作用域,說明量詞證明規則的條件,並區分給定有限結構上的求值與所有結構上的有效性。
- 12.3
邏輯、計數與算法不變量
運用量詞語句、歸納法、雙射與容斥原理證明離散命題,並驗證一個計數算法。
- 12.4
集合、像、原像與複合映射
逐元素證明集合恆等式,區分像與原像,並在有限集及空集條件下正確構造逆映射。
- 12.5
關係、等價類與偏序
用劃分理解等價關係,並用有限偏序描述依賴關係。
第 13 章 · 1 節
複雜度與 NP 完全性
複雜度與 NP 完全性
- 13.1
證書、歸約與 NP 完全性
定義帶多項式見證長度界的高效驗證,證明圖問題之間的歸約,並在兩個邏輯方向上構造從子句到團的歸約。