信息時代的計算機科學(xué)理論

第1章 引言
第2章 高維空間
2.1 高維空間的性質(zhì)
2.2 高維球體
2.2.1 高維空間的球體和立方體
2.2.2 單位球體的體積和表面積
2.2.3 體積在赤道附近
2.2.4 體積在一個狹窄的環(huán)內(nèi)
2.2.5 表面積在赤道附近
2.3 其他立方體的體積
2.4 在球體表面隨機生成均勻分布的點
2.5 高維中的高斯分布
2.6 尾概率的界限
2.7 隨機投影和Johnson-Lindenstrauss定理
文獻(xiàn)標(biāo)記
練習(xí)
第3章 隨機圖
3.1 G（n，p）模型
3.1.1 度數(shù)分布
3.1.2 圖G（n，d／n）中的三角形
3.2 相變
3.3 巨型分支
3.4 分支過程
3.5 回路和全連通
3.5.1 回路的出現(xiàn)
3.5.2 全連通性
3.5.3 直徑O（lnn）的閾值
3.6 單調(diào)性的相變
3.7 CNF可滿足性的相變
3.8 隨機圖的非均勻模型和成長模型
3.8.1 非均勻模型
3.8.2 給定度數(shù)分布的隨機圖中的巨型分支
3.9 增長模型
3.9.1 無優(yōu)先連接的增長模型
3.9.2 具有優(yōu)先連接的增長模型
3.1 0小世界效應(yīng)圖
文獻(xiàn)標(biāo)記
練習(xí)
第4章 奇異值分解（SVD）
4.1 奇異向量
4.2 奇異值分解（SVD）
4.3 最佳k階逼近
4.4 計算奇異值分解的冪方法
4.5 奇異值分解的應(yīng)用
4.5.1 主元分析
4.5.2 球形正態(tài)混合的聚類分析
4.5.3 應(yīng)用SVD于一個離散優(yōu)化問題
4.5.4 譜分解
4.5.5 奇異向量和文件評級
文獻(xiàn)注記
練習(xí)
第5章 隨機行走和Markov鏈
5.1 平穩(wěn)分布
5.2 電路網(wǎng)絡(luò)和隨機行走
5.3 具有單位邊權(quán)重的無向圖上的隨機行走
5.4 歐幾里得空間中的隨機行走
5.5 作為Markov鏈的萬維網(wǎng)
5.6 Markov鏈MonteCarlo方法
5.6.1 Metropolis-Hastings算法
5.6.2 Gibbs取樣
5.7 無向圖上隨機行走的收斂性
文獻(xiàn)注記
練習(xí)
第6章 學(xué)習(xí)及VC維
6.1 學(xué)習(xí)
6.2 線性分類器、感知器算法、邊緣
6.3 非線性分類器、支持向量機、核
6.4 強與弱學(xué)習(xí)一推進(jìn)
6.5 預(yù)測中所需樣本個數(shù)VC維
6.6 Vapnik-Chervonenkis（VC）維
6.6.1 集合系統(tǒng)及其VC維實例
6.6.2 粉碎函數(shù)
6.6.3 有界VC維集合系統(tǒng)的粉碎函數(shù)
6.6.4 交集系統(tǒng)
6.7 VC定理
文獻(xiàn)注記
練習(xí)
第7章 海量數(shù)據(jù)問題的算法
7.1 數(shù)據(jù)流的頻數(shù)距
7.1.1 在一個數(shù)據(jù)流中不同元素的個數(shù)
7.1.2 計算給定元素出現(xiàn)的次數(shù)
7.1.3 統(tǒng)計高頻元素
7.1.4 二階矩
7.2 大矩陣概要
7.2.1 利用抽樣的矩陣乘法
7.2.2 利用行和列的取樣近似矩陣
7.3 文件概要
練習(xí)
第8章 聚類
8.1 若干聚類的例子
8.2 一個簡單的k聚類貪婪算法
8.3 k均值聚類的Lloyd算法
8.4 通過奇異值分解的有意義聚類
8.5 基于稀疏削減的遞歸聚類
8.6 核方法
8.7 凝聚聚類
8.8 社區(qū)，密集的子矩陣
8.9 流方法
8.10 線性規(guī)劃
8.11 不檢查全圖地尋找本地群集
8.12聚類公理
8.12.1 不可能的結(jié)果
8.12.2 可滿足集公理
練習(xí)
第9章 圖模型和信念傳播
9.1 貝葉斯網(wǎng)絡(luò)（信念網(wǎng)絡(luò)）
9.2 馬爾可夫隨機場
9.3 因子圖
9.4 樹算法
9.5 消息傳遞算法
9.6 單環(huán)圖
9.7 單回路網(wǎng)絡(luò)的信念更新
9.8 最大權(quán)重匹配
9.9 警告?zhèn)鞑?br />9.10 變量之間的相關(guān)性
練習(xí)
第10章 其他主題
10.1 排名
10.2 野兔投票系統(tǒng)
10.3 壓縮傳感和稀疏向量
10.3.1 稀疏向量的唯一重建
10.3.2 精確重建性
10.3.3 受限的等距屬性
10.4 應(yīng)用
10.4.1 在一些坐標(biāo)基下的稀疏向量
10.4.2 一種表示方法不可能在時域和頻域上同時稀疏
10.4.3 生物
10.4.4 尋找重疊團(tuán)或團(tuán)體
10.4.5 低秩矩陣
練習(xí)
附錄
附錄1 漸近符號
附錄2 有用的不等式
附錄3 級數(shù)求和
附錄4 概率
附錄5 母函數(shù)
附錄6 特征值與特征向量
附錄7 其他內(nèi)容
練習(xí)
參考文獻(xiàn)
索引