信息时代的计算机科学理论 上海交通大学出版社 下载 pdf 百度网盘 epub 免费 2025 电子书 mobi 在线

《信息时代的计算机科学理论(英文版)》是交大致远教材系列之一，由约翰？霍普罗夫特编著。

《信息时代的计算机科学理论(英文版)》简介：

ComputerScienceTheoryfortheInformationAgecoversthecomputersciencetheorylikelytobeusefulinthenext40years,includinghigh-dimensionalspace,randomgraphs,singularvaluedecomposition.randomwalks,Markovchains,learningalgorithms,VC-dimension,algorithmsformassivedateproblems,clustering.Thebookalsocoversgraphicalmodelsandbeliefpropagation,rankingandvoting,sparsevectors,andcompressedsensing.

Thebookisintendedforeitheranundergraduateoragraduatetheorycourseincomputerscience.

Prof.JohnHopcroftisaworld-renownedscientistandanexpertoneducationincomputerscience.HewasawardedtheA.M.TuringAwardin1986forhiscontributionsintheoreticalcomputinganddatastructuredesign.Dr.RavindranKannanisaprincipalresearcherwithMicrosoftResearchLabslocatedinIndia.

1 Introduction

2 High-Dimensional Space

2.1 Properties of High-Dimensional Space

2.2 The High-Dimensional Sphere

2.2.1 The Sphere and the Cube in Higher Dimensions

2.2.2 Volume and Surface Area of the Unit Sphere

2.2.3 The Volume is Near the Equator

2.2.4 The Volume is in a Narrow Annulus

2.2.5 The Surface Area is Near the Equator

2.3 Volumes of Other Solids

2.4 Generating Points Uniformly at Random on the Surface of a Sphere

2.5 Gaussians in High Dimension

2.6 Bounds on Tail Probability

2.7 Random Projection and the Johnson-Lindenstrauss Theorem

2.8 Bibliographic Notes

2.9 Exercises

3 Random Graphs

3.1 TheG(n, p) Model

3.1.1 Degree Distribution

3.1.2 Existence of Triangles in G ( n, d

)

3.2 Phase Transitions

3.3 The Giant Component

3.4 Branching Processes

3.5 Cycles and Full Connectivity

3.5.1 Emergence of Cycles

3.5.2 Full Connectivity

3.5.3 Threshold for O (Inn) Diameter

3.6 Phase Transitions for Monotone Properties

3.7 Phase Transitions for CNF-sat

3.8 Nonuniform and Growth Models of Random Graphs

3.8.1 Nonuniform Models

3.8.2 Giant Component in Random Graphs with Given Degree Distribution ...

3.9 Growth Models

3.9.1 Growth Model Without Preferential Attachment

3.9.2 A Growth Model with Preferential Attachment

3.10 Small World Graphs

3.11 Bibliographic Notes

3.12 Exercises

4 Singular Value Decomposition (SVD)

4.1 Singular Vectors

4.2 Singular Value Decomposition (SVD)

4.3 Best Rank k Approximations

4.4 Power Method for Computing the Singular Value Decomposition

4.5 Applications of Singular Value Decomposition

4.5.1 Principal Component Analysis

4.5.2 Clustering a Mixture of Spherical Gaussians

4.5.3 An Application of SVD to a Discrete Optimization Problem

4.5.4 Spectral Decomposition

4.5.5 Singular Vectors and Ranking Documents

4.6 Bibliographic Notes

4.7 Exercises

5 Random Walks and Markov Chains

5.1 Stationary Distribution

5.2 Electrical Networks and Random Walks

5.3 Random Walks on Undirected Graphs with Unit Edge Weights

5.4 Random Walks in Euclidean Space

5.5 The Web as a Markov Chain

5.6 Markov Chain Monte Carlo

5.6.1 Metropolis-Hasting Algorithm

5.6.2 Gibbs Sampling

5.7 Convergence of Random Walks on Undirected Graphs

5.7.1 Using Normalized Conductance to Prove Convergence

5.8 Bibliographic Notes

5.9 Exercises

6 Learning and VC-Dimension

6.1 Learning

6.2 Linear Separators, the Perceptron Algorithm, and Margins

6.3 Nonlinear Separators, Support Vector Machines, and Kernels

6.4 Strong and Weak Learning-Boosting

6.5 Number of Examples Needed for Prediction: VC-Dimension

6.6 Vapnik-Chervonenkis or VC-Dimension

6.6.1 Examples of Set Systems and Their VC-Dimension

6.6.2 The Shatter Function

6.6.3 Shatter Function for Set Systems of Bounded VC-Dimension

6.6.4 Intersection Systems

6.7 The VC Theorem

6.8 Bibliographic Notes

6.9 Exercises

7 Algorithms for Massive Data Problems

7.1 Frequency Moments of Data Streams

7.1.1 Number of Distinct Elements in a Data Stream

7.1.2 Counting the Number of Occurrences of a Given Element

7.1.3 Counting Frequent Elements

7.1.4 The Second Moment

7.2 Sketch of a Large Matrix

7.2.1 Matrix Multiplication Using Sampling

7.2.2 Approximating a Matrix with a Sample of Rows and Columns ...

7.3 Sketches of Documents

7.4 Exercises

8 Clustering

8.1 Some Clustering Examples

8.2 A Simple Greedy Algorithm for k-clustering

8.3 Lloyd's Algorithm for k-means Clustering

8.4 Meaningful Clustering via Singular Value Decomposition

8.5 Recursive Clustering Based on Sparse Cuts

8.6 Kernel Methods

8.7 Agglomerative Clustering

8.8 Communities, Dense Submatrices

8.9 Flow Methods

8.10 Linear Programming Formulation

8.11 Finding a Local Cluster Without Examining the Whole Graph

8.12 Axioms for Clustering

8.12.1 An Impossibility Result

8.12.2 A Satisfiable Set of Axioms

8.13 Exercises

9 Graphical Models and Belief Propagation

9.1 Bayesian or Belief Networks

9.2 Markov Random Fields

9.3 Factor Graphs

9.4 Tree Algorithms

9.5 Message Passing Algorithm

9.6 Graphs with a Single Cycle

9.7 Belief Update in Networks with a Single Loop

9.8 Maximum Weight Matching

9.9 Warning Propagation

9.10 Correlation Between Variables

9.11 Exercises

10 Other Topics

10.1 Rankings

10.2 Hare System for Voting

10.3 Compressed Sensing and Sparse Vectors

10.3.1 Unique Reconstruction of a Sparse Vector

10.3.2 The Exact Reconstruction Property

10.3.3 Restricted Isometry Property

10.4 Applications

10.4.1 Sparse Vector in Some Coordinate Basis

10.4.2 A Representation Cannot be Sparse in Both Time and Frequency Domains

10.4.3 Biological

10.4.4 Finding Overlapping Cliques or Communities

10.4.5 Low Rank Matrices

10.5 Exercises

11 Appendix

11.1 Asymptotic Notation

11.2 Useful Inequalities

11.3 Sums of Series

11.4 Probability

11.4.1 Sample Space, Events, Independence

11.4.2 Variance

11.4.3 Variance of Sum of Independent Random Variables

11.4.4 Covariance

11.4.5 The Central Limit Theorem

11.4.6 Median

11.4.7 Unbiased Estimators

11.4.8 Probability Distributions

11.4.9 Maximum Likelihood Estimation MLE

11.4.10 Tail Bounds

11.4.11 Chernoff Bounds: Bounding of Large Deviations

11.4.12 Hoeffding's Inequality

11.5 Generating Functions

11.5.1 Generating Functions for Sequences Defined by Recurrence Relationships

11.5.2 Exponential Generating Function

11.6 Eigenvalues and Eigenvectors

11.6.1 Eigenvalues and Eigenvectors

11.6.2 Symmetric Matrices

11.6.3 Extremal Properties of Eigenvalues

11.6.4 Eigenvalues of the Sum of Two Symmetric Matrices

11.6.5 Norms

11.6.6 Important Norms and Their Properties

11.6.7 Linear Algebra

11.6.8 Distance Between Subspaces

11.7 Miscellaneous

11.7.1 Variational Methods

11.7.2 Hash Functions

11.7.3 Catalan Numbers

11.7.4 Sperner's Lemma

11.8 Exercises

Index

References

暂无相关内容，正在全力查找中

暂无出版社相关信息，正在全力查找中！

暂无相关书籍摘录，正在全力查找中！

在线阅读地址：信息时代的计算机科学理论 上海交通大学出版社在线阅读

在线听书地址：信息时代的计算机科学理论 上海交通大学出版社在线收听

在线购买地址：信息时代的计算机科学理论 上海交通大学出版社在线购买

暂无原文赏析，正在全力查找中！

暂无其它内容！