你的進度
0/ 26 節已標記完成
下一節: 1.1 量詞、歸納法與反例
完成記錄儲存在此瀏覽器中。
這門課在網上
MATH3250 筆記裏的內容
數字只算這門課 26 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。
在網上定理卡 77 · 定義 39 · 反例 27 · 概念視角 25 · 思想史 1 · 證明透視 27
第 1 章 · 2 節
證明方法
翻譯精確的陳述,否定量詞,並透過最小反例論證普通歸納法與強歸納法。
- 1.1
量詞、歸納法與反例
翻譯精確的陳述,否定量詞,並透過最小反例論證普通歸納法與強歸納法。
- 1.2
關係、等價類與良定義映射
證明等價關係與集合劃分的對應,理解函數的纖維,並判斷用代表元給出的公式能否定義商集上的函數。
第 2 章 · 11 節
計數
選擇正確的計數模型,證明容斥原理,並計算錯位排列與滿射的個數。
- 2.1
雙射、容斥原理與滿射
選擇正確的計數模型,證明容斥原理,並計算錯位排列與滿射的個數。
- 2.2
單調子序列與鴿巢原理
用成對的子序列長度證明精確的有限界。
- 2.3
依賴圖與局部引理
透過條件迴避界證明有限非對稱局部引理,導出一個對稱判準,並將其應用於稀疏重疊的超圖著色與可滿足性問題,同時點明其中的聯合獨立性假設。
- 2.4
計數中的選擇、分類與原像纖維
從互不相交分類與原像纖維推導加法和乘法法則,並區分選擇過程與它所描述的對象。
- 2.5
二項式係數與組合恆等式
從子集計數定義二項式係數,探討階乘公式、對稱性、帕斯卡(Pascal)法則、交換環上的二項式定理,以及由雙射和雙重計數證明的恆等式。
- 2.6
鴿巢原理與單調子序列
證明尖銳的佔用量界,用前綴和餘數尋找可整除的連續段,並透過終點長度標記證明遞增或遞減子序列的精確保證。
- 2.7
集合劃分、斯特靈數與貝爾數總和
計數集合劃分與置換的輪換,證明它們的遞推式與生成函數,並解釋冪與下降階乘之間的斯特靈逆變換。
- 2.8
反射法、投票路徑與卡特蘭結構
透過可逆的反射證明弱與嚴格投票路徑的計數,推導卡特蘭數的閉式及形式二次母函數,並構造有序樹和多邊形三角剖分的雙射。
- 2.9
整數分拆、Ferrers 共軛與 Durfee 方陣
證明分拆的共軛、形式母函數乘積、奇部分拆與相異部分拆的等價性以及 Durfee 分解,並給出恰好若干部分的限制,以及一個有嚴格依據的係數表算法。
- 2.10
群作用、項鏈與本原週期
透過穩定子證明軌道計數公式,推導旋轉與反射公式,並藉莫比烏斯反演把字的本原週期聯繫起來,而無需除以大小不一的軌道。
- 2.11
Ramsey 數及其基本界
用歸納法證明兩色 Ramsey 定理,推出二項式上界,確定 R(3,3)=6,並證明對角 Ramsey 數的計數下界。
第 3 章 · 2 節
遞歸與生成函數
由組合分解推導遞推關係,並用形式冪級數求解。
- 3.1
遞推關係與形式生成函數
由組合分解推導遞推關係,並用形式冪級數求解。
- 3.6
動態規劃:選擇、次序與重建
推導精確的 0–1 背包和最少硬幣遞推,證明計算次序並恢復解。
第 4 章 · 2 節
整數算法
證明兩個整數算法的正確性與終止性,並將算術運算次數與位元複雜度區分開來。
- 4.1
歐幾里得不變式與二進制冪運算
證明兩個整數算法的正確性與終止性,並將算術運算次數與位元複雜度區分開來。
- 4.2
線性同餘與相容的餘數方程組
證明線性同餘的完整解類、非互質情形下構造性的中國剩餘定理合併方法以及兩兩相容判準,並給出精確的代表元、週期和模為一的邊界情形。
第 5 章 · 5 節
圖論方法
證明樹的等價刻劃,以及廣度優先搜尋在有限無權圖上求最短路徑的正確性。
- 5.1
樹與廣度優先搜尋
證明樹的等價刻劃,以及廣度優先搜尋在有限無權圖上求最短路徑的正確性。
- 5.2
歐拉跡與萬有循環詞
證明有向歐拉(Euler)跡的判別準則,以及線性時間的圖操作拼接算法,再透過重疊圖構造最優的萬有循環詞與萬有線性詞,並給出精確的邊界情形與輸出規模條件。
- 5.3
頂點著色與貪心界
用合法著色表達衝突,證明貪心上界並識別二分圖。
- 5.4
最小生成森林與貪心交換
證明割與圈交換規則、Kruskal 與 Prim 算法,以及可獨立檢查的最優性條件。
- 5.5
非負權最短路與距離證書
證明 Dijkstra 的最小標號定案原則,恢復最短路徑,並用邊不等式及無圈前驅證書獨立核驗距離。
第 6 章 · 3 節
偏序
整理有限偏序,對其下集上的求和進行反演,並由同一個關聯代數論證導出布爾格反演與因數反演。
- 6.1
偏序、線性擴張與 Möbius 反演
整理有限偏序,對其下集上的求和進行反演,並由同一個關聯代數論證導出布爾(Boole)格反演與因數反演。
- 6.2
鏈、反鏈與 Dilworth 定理
透過二分圖匹配證明有限偏序集的鏈—反鏈劃分定理,構造最優證書,並區分比較圖與哈塞(Hasse)圖。
- 6.3
Sperner 定理、LYM 不等式與子集上影
透過計數極大布爾(Boole)鏈證明 LYM 不等式與 Sperner 的最優反鏈上界,並分析上影以及中間層的取等情形。
第 8 章 · 1 節
算法設計
用交換論證和不變量證明算法選擇的正確性。
- 8.1
貪心選擇、交換與區間調度
透過交換及始終不落後的不變量證明最早結束區間調度,明確端點約定,並反駁其他看似合理的選擇規則。