跳到正文

CSCI3190

離散數學及算法導論

邏輯、集合與關係,計數與離散概率,數論與字串算法,圖算法、排序、算法設計及 NP 完全性。

11 章 · 29 節EN · 繁 · 简
我的課程筆記

你的進度

0/ 29 節已標記完成

下一節: 容斥原理與滿射計數

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

這門課在網上

CSCI3190 筆記裏的內容

定理卡
90
定義
70
反例
34
概念視角
17
思想史
1
證明透視
33

有思想史的節

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

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

在知識圖譜中打開這門課

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

在網上定理卡 90 · 定義 70 · 反例 34 · 概念視角 17 · 思想史 1 · 證明透視 33

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

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

在知識圖譜中打開這門課

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

第 1 章 · 5 節

計數

計數

定理 14 · 定義 11反例 4視角 2證明透視 5

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

  1. 1.1

    容斥原理與滿射計數

    逐一追蹤對象的貢獻,處理互相重疊的例外。

  2. 1.2

    在對稱下計算構型

    證明不動點數目的平均公式,並計算二進制循環字串。

  3. 1.3

    函數計數、子集選取與遞歸樹的閱讀

    區分有序分配與子集,證明鴿籠原理,定義漸近界,並透過各層求和推導平衡遞推式的成本。

  4. 1.4

    集合劃分、滿射與斯特林遞推

    區分組的標籤與元素歸屬,證明斯特林數和滿射的計數公式,並用經過論證的動態規劃計算精確答案。

  5. 1.5

    離散概率、期望與線性性

    定義有限概率空間、隨機變量與期望,證明期望的線性性與 Markov 不等式,並用指示變量分析隨機化算法。

第 3 章 · 2 節

算法設計

算法設計

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

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

  1. 3.1

    貪心選擇、分治與動態規劃

    以排程與合併排序比較算法設計原則。

  2. 3.2

    取整子問題與主遞歸界

    證明整數上取整與下取整遞歸的分治工作量界,計入葉子並區分幾何級數的各種情形,並在恰為冪的輸入上推導對數型代價的臨界閾值。

第 4 章 · 5 節

圖算法

生成樹、連通性、最短行走及拓撲次序。

定理 16 · 定義 10反例 6證明透視 5

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

  1. 4.1

    Kruskal 算法與割的交換論證

    構造最小生成樹,並證明每條貪心選邊都可屬於一棵最優樹。

  2. 4.2

    Bellman–Ford 與可達負環

    推導邊數受限的最短行走,並找出因負環而無下界的距離。

  3. 4.3

    拓撲次序與有向環證書

    證明以隊列求拓撲次序的算法,並構造有向環見證。

  4. 4.4

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

    維護不斷合併的連通分量,並用倍增證明對數界。

  5. 4.5

    圖的遍歷、最短路徑與生成樹

    透過前沿不變量證明 BFS 與 Dijkstra 算法的正確性,推導最小生成樹的割性質,並區分三種不同的優化目標。

第 5 章 · 3 節

整數算術

整數算術

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

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

  1. 5.1

    最大公因數、模逆元與快速冪

    證明歐幾里得算法、線性同餘與重複平方法。

  2. 5.2

    通用雜湊與固定鍵碰撞界

    證明有限域上雜湊族的碰撞界,並將其應用於鏈結法及隨機重試。

  3. 5.3

    傅立葉蝴蝶運算與多項式卷積

    推導離散傅立葉(Fourier)變換及其分治求值方法,並說明計算一般卷積所需的補零。

第 6 章 · 3 節

字串算法

前綴回退與精確匹配。

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

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

  1. 6.1

    前綴函數與重疊字串匹配

    推導 KMP 回退、證明線性掃描,並保留重疊出現的位置。

  2. 6.2

    編輯距離與最優對齊

    推導編輯距離的前綴動態規劃,證明其正確性並重構最優編輯序列。

  3. 6.3

    以滾動多項式指紋搜尋字串

    推導滾動更新與有限域碰撞界,明確說明核對和輸入假設。

第 8 章 · 2 節

排序算法

排序算法

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

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

  1. 8.1

    逆序對、隨機化快速排序與穩定基數排序

    以逆序對分析插入排序,推導隨機化快速排序的期望比較次數,並在明確的鍵模型下證明穩定計數排序與基數排序。

  2. 8.2

    二元堆、線性建堆與堆排序

    證明下沉(sift-down)的正確性,透過對各節點高度求和證明由下而上建堆的線性時間界,並證明原地堆排序,同時區分堆序、穩定性與優先隊列的記憶體配置成本。

第 9 章 · 1 節

數論算法

數論算法

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

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

  1. 9.1

    中國剩餘定理與合數見證

    保持 CRT 合併不變量,證明試除法與強合數判據,並區分合數見證和未經證明的質數結論。

第 10 章 · 1 節

多項式算法

快速 Fourier 求值與係數卷積。

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

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

  1. 10.1

    FFT 與多項式卷積

    推導基二 Fourier 求值及反變換,並在沒有循環混疊下相乘多項式。

第 11 章 · 1 節

歐幾里得算法與同餘

把歐幾里得證書延伸至模方程及相容的非互質餘數系統。

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

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

  1. 11.1

    歐幾里得不變量與同餘證書

    把歐幾里得證書延伸至模方程及相容的非互質餘數系統。

第 12 章 · 5 節

邏輯、集合與關係

邏輯、集合與關係

定理 18 · 定義 26反例 9視角 4證明透視 7

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

  1. 12.1

    命題等價、範式與歸結

    構造有限布爾公式的範式,用歸結消去變量,並區分等價與可滿足性等價。

  2. 12.2

    謂詞邏輯、見證的依賴與有限模型檢驗

    準確理解變量作用域,說明量詞證明規則的條件,並區分給定有限結構上的求值與所有結構上的有效性。

  3. 12.3

    邏輯、計數與算法不變量

    運用量詞語句、歸納法、雙射與容斥原理證明離散命題,並驗證一個計數算法。

  4. 12.4

    集合、像、原像與複合映射

    逐元素證明集合恆等式,區分像與原像,並在有限集及空集條件下正確構造逆映射。

  5. 12.5

    關係、等價類與偏序

    用劃分理解等價關係,並用有限偏序描述依賴關係。

第 13 章 · 1 節

複雜度與 NP 完全性

複雜度與 NP 完全性

定理 3反例 1證明透視 1

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

  1. 13.1

    證書、歸約與 NP 完全性

    定義帶多項式見證長度界的高效驗證,證明圖問題之間的歸約,並在兩個邏輯方向上構造從子句到團的歸約。

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

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

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

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

查看 Cookie 與儲存詳情