《資訊時代的計算機科學理論（英文版）》是2013年6月3日上海交通大學出版社出版的圖書，作者是（美）約翰·霍普克羅夫特 拉文德蘭·坎。
基本介紹
- 書名：資訊時代的計算機科學理論（英文版）
- 作者：（美）約翰·霍普克羅夫特 拉文德蘭·坎
- 出版社：上海交通大學出版社
- 出版時間：2013年6月3日
- 頁數：404 頁
- 定價：35 元
- 開本：T16開
- ISBN：978-7-313-09609-8
- 版次：1
- 字數：620千字
內容簡介,作者簡介,目錄,
內容簡介
本書是上海交通大學致遠教材系列之一，由國際著名計算機科學家約翰·霍普克羅夫特教授和拉文德蘭·坎南教授編寫。本書包含了高維空間、隨機圖、奇異值分解、隨機行走和馬爾可夫鏈、學習算法和VC維、大規模數據問題的算法、聚類、圖形模型和置信傳播等主要內容，書後有附錄及索引。從第2章開始，每章後面均附有適量的練習題。
本書可作為計算機及相關專業高年級本科生或研究生的教材，也可供相關專業技術人員參考。
作者簡介
John Hopcroft為圖靈獎獲得者。
Ravindran Kannan is a principal researcher with Microsoft Research Labs located in India
目錄
Contents
1 Introduction 6
2 High-Dimensional Space 7
2.1 Properties of High-Dimensional Space . 9
2.2 The High-Dimensional Sphere . 10
2.2.1 The Sphere and the Cube in Higher Dimensions . 10
2.2.2 Volume and Surface Area of the Unit Sphere . 11
2.2.3 The Volume is Near the Equator . 14
2.2.4 The Volume is in a Narrow Annulus 16
2.2.5 The Surface Area is Near the Equator 16
2.3 The High-Dimensional Cube and Chernoff Bounds 18
2.4 Volumes of Other Solids 23
2.5 Generating Points Uniformly at Random on the surface of a Sphere 24
2.6 Gaussians in High Dimension . 25
2.7 Random Projection and the Johnson-Lindenstrauss Theorem 31
2.8 Bibliographic Notes . 34
2.9 Exercises . 35
3 Random Graphs 46
3.1 The G(n; p) Model . 46
3.1.1 Degree Distribution . 46
3.1.2 Existence of Triangles in G(n; d=n) 51
3.1.3 Phase Transitions 52
3.1.4 Phase Transitions for Monotone Properties 62
3.1.5 Phase Transitions for CNF-sat . 65
3.1.6 The Emerging Graph 69
3.1.7 The Giant Component . 72
3.2 Branching Processes 80
3.3 Nonuniform and Growth Models of Random Graphs . 85
3.3.1 Nonuniform Models . 85
3.3.2 Giant Component in Random Graphs with Given Degree Distribution 86
3.4 Growth Models . 87
3.4.1 Growth Model Without Preferential Attachment . 87
3.4.2 A Growth Model With Preferential Attachment . 94
3.5 Small World Graphs 95
3.6 Bibliographic Notes . 100
3.7 Exercises . 101
4 Singular Value Decomposition (SVD) 110
4.1 Singular Vectors . 111
4.2 Singular Value Decomposition (SVD) . 115
4.3 Best Rank k Approximations . 116
1
4.4 Power Method for Computing the Singular Value Decomposition 118
4.5 Applications of Singular Value Decomposition 122
4.5.1 Principal Component Analysis . 122
4.5.2 Clustering a Mixture of Spherical Gaussians . 123
4.5.3 An Application of SVD to a Discrete Optimization Problem 127
4.5.4 SVD as a Compression Algorithm . 130
4.5.5 Spectral Decomposition 130
4.5.6 Singular Vectors and ranking documents . 131
4.6 Bibliographic Notes . 133
4.7 Exercises . 134
5 Markov Chains 142
5.1 Stationary Distribution . 143
5.2 Electrical Networks and Random Walks 144
5.3 Random Walks on Undirected Graphs . 148
5.4 Random Walks in Euclidean Space 155
5.5 Random Walks on Directed Graphs 158
5.6 Finite Markov Processes 158
5.7 Markov Chain Monte Carlo 163
5.7.1 Time Reversibility . 164
5.7.2 Metropolis-Hasting Algorithm . 165
5.7.3 Gibbs Sampling . 166
5.8 Convergence to Steady State 167
5.8.1 Using Minimum Escape Probability to Prove Convergence . 173
5.9 Bibliographic Notes . 175
5.10 Exercises . 176
6 Learning and VC-dimension 183
6.1 Learning . 183
6.2 Linear Separators, the Perceptron Algorithm, and Margins . 184
6.3 Nonlinear Separators, Support Vector Machines, and Kernels 189
6.4 Strong and Weak Learning - Boosting . 194
6.5 Number of Examples Needed for Prediction: VC-Dimension 196
6.6 Vapnik-Chervonenkis or VC-Dimension 199
6.6.1 Examples of Set Systems and Their VC-Dimension . 199
6.6.2 The Shatter Function . 202
6.6.3 Shatter Function for Set Systems of Bounded VC-Dimension . 204
6.6.4 Intersection Systems 205
6.7 The VC Theorem 206
6.8 Priors and Bayesian Learning . 209
6.9 Bibliographic Notes . 210
6.10 Exercises . 211
2
7 Algorithms for Massive Data Problems 217
7.1 Frequency Moments of Data Streams . 217
7.1.1 Number of Distinct Elements in a Data Stream . 218
7.1.2 Counting the Number of Occurrences of a Given Element221
7.1.3 Counting Frequent Elements 222
7.1.4 The Second Moment 224
7.2 Sketch of a Large Matrix 227
7.2.1 Matrix Multiplication Using Sampling 229
7.2.2 Approximating a Matrix with a Sample of Rows and Columns . 231
7.3 Sketches of Documents . 233
7.4 Exercises . 236
8 Clustering 240
8.1 Some Clustering Examples . 240
8.2 A Simple Greedy Algorithm for k-clustering . 242
8.3 Lloyd's Algorithm for k-means Clustering . 243
8.4 Meaningful Clustering via Singular Value Decomposition 245
8.5 Recursive Clustering based on Sparse Cuts 250
8.6 Kernel Methods . 254
8.7 Agglomerative Clustering 256
8.8 Communities, Dense Submatrices . 258
8.9 Flow Methods 260
8.10 Linear Programming Formulation . 263
8.11 Finding a Local Cluster Without Examining the Whole graph . 264
8.12 Statistical Clustering 270
8.13 Axioms for Clustering . 270
8.13.1 An Impossibility Result 270
8.13.2 A Satisfiable Set of Axioms 276
8.14 Exercises . 278
9 Graphical Models and Belief Propagation 283
9.1 Bayesian Networks . 283
9.2 Markov Random Fields . 284
9.3 Factor Graphs 286
9.4 Tree Algorithms . 286
9.5 Message Passing Algorithm 287
9.6 Graphs with a Single Cycle 290
9.7 Belief Update in Networks with a Single Loop 292
9.8 Graphs with Multiple Loops 293
9.9 Clustering by Message Passing . 294
9.10 Maximum Weight Matching 296
9.11 Warning Propagation 300
9.12 Correlation Between Variables . 301
3
9.13 Exercises . 305
10 Other Topics 307
10.1 Rankings . 307
10.2 Hare System for Voting . 309
10.3 Compressed Sensing and Sparse Vectors . 310
10.3.1 Unique Reconstruction of a Sparse Vector 311
10.3.2 The Exact Reconstruction Property 313
10.3.3 Restricted Isometry Property . 314
10.4 Applications . 316
10.4.1 Sparse Vector in Some Coordinate Basis . 316
10.4.2 A Representation Cannot be Sparse in Both Time and Frequency
Domains . 316
10.4.3 Biological 319
10.4.4 Finding Overlapping Cliques or Communities 320
10.4.5 Low Rank Matrices . 321
10.5 Exercises . 322
11 Appendix 325
11.1 Asymptotic Notation 325
11.2 Useful Inequalities . 326
11.3 Sums of Series 333
11.4 Probability . 337
11.4.1 Sample Space, Events, Independence . 338
11.4.2 Variance . 340
11.4.3 Covariance 341
11.4.4 Variance of Sum of Independent Random Variables . 341
11.4.5 Sum of independent random variables, Central Limit Theorem . 341
11.4.6 Median . 342
11.4.7 Unbiased estimators 342
11.4.8 Probability Distributions 344
11.4.9 Tail Bounds . 353
11.4.10 Chernf Bounds: Bounding of Large Deviations . 354
11.4.11Holding's Inequality . 358
11.5 Generating Functions . 359
11.5.1 Generating Functions for Sequences Depened by Recurrence Relationships
. 361
11.5.2 Exponential Generating Function . 363
11.6 Eigenvalues and Eigenvectors . 369
11.6.1 Eigenvalues and Eigenvectors . 369
11.6.2 Symmetric Matrices 370
11.6.3 Extremal Properties of Eigenvalues 372
11.6.4 Eigenvalues of the Sum of Two Symmetric Matrices . 374
4
11.6.5 Separator Theorem . 375
11.6.6 Norms 375
11.6.7 Important Norms and Their Properties 377
11.6.8 Linear Algebra . 380
11.7 Miscellaneous 386
11.7.1 Variational Methods 388
11.7.2 Hash Functions . 389
11.7.3 Sperner's Lemma 390
Index 391
5
