跳到正文

CSCI4240

進階算法:隨機與近似

集中不等式、隨機捨入與線性規劃鬆弛、隨機漫步、局部搜尋、零和博弈、數據流與雜湊,以及半正定規劃。

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

你的進度

0/ 34 節已標記完成

下一節: 最大割的局部搜尋

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

這門課在網上

CSCI4240 筆記裏的內容

定理卡
74
定義
52
反例
36
概念視角
17
思想史
0
證明透視
40

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

在知識圖譜中打開這門課

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

在網上定理卡 74 · 定義 52 · 反例 36 · 概念視角 17 · 證明透視 40

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

在知識圖譜中打開這門課

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

第 2 章 · 2 節

零和博弈

混合策略與最優性證書。

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

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

  1. 2.1

    有限零和博弈中的混合策略

    利用線性規劃對偶解釋有限博弈中的最優隨機化。

  2. 2.2

    多人博弈中的無遺憾策略

    利用完全資訊乘法權重法構造近似粗相關均衡。

第 3 章 · 4 節

集中不等式

獨立指示變量的乘法尾界。

定理 9反例 5視角 2證明透視 6

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

  1. 3.1

    獨立指示變量的 Chernoff 界

    推導乘性尾界,並將其應用於抽樣與稀疏計數。

  2. 3.2

    集中不等式與獨立重複

    證明馬爾可夫和切比雪夫不等式,並分析獨立重複。

  3. 3.3

    球入箱問題中的最大負載

    利用一階矩與二階矩證明最大負載的上界與下界。

  4. 3.4

    生日碰撞與二階矩

    分析碰撞概率,以及其背後的獨立性假設。

第 4 章 · 5 節

隨機捨入

集合覆蓋的隨機捨入與修補。

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

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

  1. 4.1

    集合覆蓋的隨機捨入

    把分數覆蓋轉化為可行覆蓋,並界定其期望成本。

  2. 4.2

    為甚麼線性規劃對偶是精確的

    透過投影不等式並追蹤非負證書來證明強對偶性。

  3. 4.3

    集合覆蓋:收費、線性鬆弛與原始—對偶證書

    證明調和貪心與頻率捨入保證,並在構造覆蓋時同步建立可行對偶下界。

  4. 4.4

    度量旅行推銷員問題的近似算法

    利用生成樹、歐拉(Euler)迴路與度量捷徑(shortcutting)來界定巡迴路線的成本。

  5. 4.5

    背包問題的完全多項式時間近似方案

    對利潤進行縮放,並求解最小重量動態規劃,從而得到明確的近似保證。

第 5 章 · 4 節

隨機漫步

利用譜界放大成功概率。

定理 10 · 定義 8反例 4視角 2證明透視 5

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

  1. 5.1

    隨機漫步放大

    利用絕對譜界限控制對壞集合的重複造訪概率。

  2. 5.2

    隨機漫步與譜混合

    利用正則圖的特徵值界定隨機漫步的收斂速度。

  3. 5.3

    2-SAT 的隨機漫步搜尋

    利用距離勢函數,界定隨機化可滿足賦值搜尋的期望時間。

  4. 5.4

    平穩分佈與懶惰漫步

    證明有限馬爾可夫(Markov)鏈平穩分佈的存在性,以及基於耦合的收斂結果。

第 6 章 · 7 節

條件期望

以條件期望去隨機化 Max-2SAT 保證。

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

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

  1. 6.1

    Max-2SAT 與條件期望

    把隨機賦值的期望轉化為確定性保證。

  2. 6.2

    最小割的隨機收縮算法

    證明隨機收縮算法的成功概率,並透過重複運行放大該概率。

  3. 6.3

    透過隨機取值進行多項式恆等檢驗

    證明 Schwartz–Zippel 界,並將其應用於二分圖完美匹配。

  4. 6.4

    矩陣乘積的隨機化驗證

    利用隨機向量以單側錯誤驗證矩陣乘積。

  5. 6.5

    Lovász 局部引理

    證明局部引理,並利用稀疏的依賴關係說明所有壞事件可以同時被避免。

  6. 6.6

    隨機割與條件期望

    用隨機劃分證明好割存在,並以條件期望去隨機化。

  7. 6.7

    隨機賦值與 MAX-SAT 近似

    分析帶權子句的滿足情況,並以條件期望法將隨機算法去隨機化。

第 7 章 · 6 節

線上決策

滑雪租賃的競爭分析。

定理 14 · 定義 17反例 7證明透視 7

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

  1. 7.1

    線上決策與租滑雪裝備問題

    證明確定性競爭保證及與之匹配的下界。

  2. 7.2

    線上租買:競爭比與隨機購買閾值

    比較離散模型與連續時間競爭比,並提供附解練習。

  3. 7.3

    線上分頁與競爭分析

    分析分頁問題中的標記階段與對抗性請求。

  4. 7.4

    LRU 分頁的精確競爭界

    利用按存取新近程度加權的勢函數,證明最近最少使用(LRU)分頁算法是 k-競爭的。

  5. 7.5

    線上分頁的隨機化標記算法

    利用調和和,在不經意對手下界定隨機分頁算法的期望成本。

  6. 7.6

    相同機器上的列表排程

    利用負載下界與最長工作下界,證明一個緊的完工時間保證。

第 8 章 · 1 節

隨機覆蓋

期望等待時間與高概率覆蓋。

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

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

  1. 8.1

    集齊種類:期望與尾部界

    分析隨機停止時間與覆蓋尾部界。

第 9 章 · 1 節

數據流抽樣

均勻水塘抽樣與有限母體估計。

定理 1反例 1證明透視 1

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

  1. 9.1

    水塘抽樣與估計數據流比例

    證明未知長度數據流的均勻抽樣不變式,並推導有限母體誤差界。

第 10 章 · 2 節

雜湊與草圖

雜湊與草圖

定理 4反例 2視角 2證明透視 2

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

  1. 10.1

    兩兩獨立的二元雜湊

    構造一個仿射雜湊族,並分析基於碰撞的保證。

  2. 10.2

    用於頻率估計的 Count–Min 草圖

    利用兩兩獨立雜湊與獨立重複來界定碰撞誤差。

第 11 章 · 1 節

半正定規劃

半正定規劃

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

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

  1. 11.1

    最大割向量與隨機超平面

    推導半正定鬆弛,證明角度分離概率,並得到精確的期望近似常數。

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

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

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

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

查看 Cookie 與儲存詳情