跳到正文

MATH3250

離散數學

證明方法、計數、遞歸與生成函數、整數算法、圖論方法、偏序及算法設計,附證明、例題及習題解答。

7 章 · 26 節EN · 繁 · 简
我的課程筆記

你的進度

0/ 26 節已標記完成

下一節: 1.1 量詞、歸納法與反例

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

這門課在網上

MATH3250 筆記裏的內容

定理卡
77
定義
39
反例
27
概念視角
25
思想史
1
證明透視
27

有思想史的節

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

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

在知識圖譜中打開這門課

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

在網上定理卡 77 · 定義 39 · 反例 27 · 概念視角 25 · 思想史 1 · 證明透視 27

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

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

在知識圖譜中打開這門課

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

第 1 章 · 2 節

證明方法

翻譯精確的陳述,否定量詞,並透過最小反例論證普通歸納法與強歸納法。

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

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

  1. 1.1

    量詞、歸納法與反例

    翻譯精確的陳述,否定量詞,並透過最小反例論證普通歸納法與強歸納法。

  2. 1.2

    關係、等價類與良定義映射

    證明等價關係與集合劃分的對應,理解函數的纖維,並判斷用代表元給出的公式能否定義商集上的函數。

第 2 章 · 11 節

計數

選擇正確的計數模型,證明容斥原理,並計算錯位排列與滿射的個數。

定理 37 · 定義 15反例 13視角 11證明透視 11

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

  1. 2.1

    雙射、容斥原理與滿射

    選擇正確的計數模型,證明容斥原理,並計算錯位排列與滿射的個數。

  2. 2.2

    單調子序列與鴿巢原理

    用成對的子序列長度證明精確的有限界。

  3. 2.3

    依賴圖與局部引理

    透過條件迴避界證明有限非對稱局部引理,導出一個對稱判準,並將其應用於稀疏重疊的超圖著色與可滿足性問題,同時點明其中的聯合獨立性假設。

  4. 2.4

    計數中的選擇、分類與原像纖維

    從互不相交分類與原像纖維推導加法和乘法法則,並區分選擇過程與它所描述的對象。

  5. 2.5

    二項式係數與組合恆等式

    從子集計數定義二項式係數,探討階乘公式、對稱性、帕斯卡(Pascal)法則、交換環上的二項式定理,以及由雙射和雙重計數證明的恆等式。

  6. 2.6

    鴿巢原理與單調子序列

    證明尖銳的佔用量界,用前綴和餘數尋找可整除的連續段,並透過終點長度標記證明遞增或遞減子序列的精確保證。

  7. 2.7

    集合劃分、斯特靈數與貝爾數總和

    計數集合劃分與置換的輪換,證明它們的遞推式與生成函數,並解釋冪與下降階乘之間的斯特靈逆變換。

  8. 2.8

    反射法、投票路徑與卡特蘭結構

    透過可逆的反射證明弱與嚴格投票路徑的計數,推導卡特蘭數的閉式及形式二次母函數,並構造有序樹和多邊形三角剖分的雙射。

  9. 2.9

    整數分拆、Ferrers 共軛與 Durfee 方陣

    證明分拆的共軛、形式母函數乘積、奇部分拆與相異部分拆的等價性以及 Durfee 分解,並給出恰好若干部分的限制,以及一個有嚴格依據的係數表算法。

  10. 2.10

    群作用、項鏈與本原週期

    透過穩定子證明軌道計數公式,推導旋轉與反射公式,並藉莫比烏斯反演把字的本原週期聯繫起來,而無需除以大小不一的軌道。

  11. 2.11

    Ramsey 數及其基本界

    用歸納法證明兩色 Ramsey 定理,推出二項式上界,確定 R(3,3)=6,並證明對角 Ramsey 數的計數下界。

第 3 章 · 2 節

遞歸與生成函數

由組合分解推導遞推關係,並用形式冪級數求解。

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

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

  1. 3.1

    遞推關係與形式生成函數

    由組合分解推導遞推關係,並用形式冪級數求解。

  2. 3.6

    動態規劃:選擇、次序與重建

    推導精確的 0–1 背包和最少硬幣遞推,證明計算次序並恢復解。

第 4 章 · 2 節

整數算法

證明兩個整數算法的正確性與終止性,並將算術運算次數與位元複雜度區分開來。

定理 5 · 定義 3反例 2視角 2思想史 1證明透視 2

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

  1. 4.1

    歐幾里得不變式與二進制冪運算

    證明兩個整數算法的正確性與終止性,並將算術運算次數與位元複雜度區分開來。

  2. 4.2

    線性同餘與相容的餘數方程組

    證明線性同餘的完整解類、非互質情形下構造性的中國剩餘定理合併方法以及兩兩相容判準,並給出精確的代表元、週期和模為一的邊界情形。

第 5 章 · 5 節

圖論方法

證明樹的等價刻劃,以及廣度優先搜尋在有限無權圖上求最短路徑的正確性。

定理 14 · 定義 8反例 4視角 5證明透視 6

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

  1. 5.1

    樹與廣度優先搜尋

    證明樹的等價刻劃,以及廣度優先搜尋在有限無權圖上求最短路徑的正確性。

  2. 5.2

    歐拉跡與萬有循環詞

    證明有向歐拉(Euler)跡的判別準則,以及線性時間的圖操作拼接算法,再透過重疊圖構造最優的萬有循環詞與萬有線性詞,並給出精確的邊界情形與輸出規模條件。

  3. 5.3

    頂點著色與貪心界

    用合法著色表達衝突,證明貪心上界並識別二分圖。

  4. 5.4

    最小生成森林與貪心交換

    證明割與圈交換規則、Kruskal 與 Prim 算法,以及可獨立檢查的最優性條件。

  5. 5.5

    非負權最短路與距離證書

    證明 Dijkstra 的最小標號定案原則,恢復最短路徑,並用邊不等式及無圈前驅證書獨立核驗距離。

第 6 章 · 3 節

偏序

整理有限偏序,對其下集上的求和進行反演,並由同一個關聯代數論證導出布爾格反演與因數反演。

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

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

  1. 6.1

    偏序、線性擴張與 Möbius 反演

    整理有限偏序,對其下集上的求和進行反演,並由同一個關聯代數論證導出布爾(Boole)格反演與因數反演。

  2. 6.2

    鏈、反鏈與 Dilworth 定理

    透過二分圖匹配證明有限偏序集的鏈—反鏈劃分定理,構造最優證書,並區分比較圖與哈塞(Hasse)圖。

  3. 6.3

    Sperner 定理、LYM 不等式與子集上影

    透過計數極大布爾(Boole)鏈證明 LYM 不等式與 Sperner 的最優反鏈上界,並分析上影以及中間層的取等情形。

第 8 章 · 1 節

算法設計

用交換論證和不變量證明算法選擇的正確性。

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

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

  1. 8.1

    貪心選擇、交換與區間調度

    透過交換及始終不落後的不變量證明最早結束區間調度,明確端點約定,並反駁其他看似合理的選擇規則。

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

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

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

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

查看 Cookie 與儲存詳情