2011CCF学科前沿讲习班信息时代之数学基础主讲学者：图灵奖获得者JohnE.Hopcroft教授，Cornell大学学术主任：殷建平教授国防科技大学时间地点：2011年1月9日－13日，湖南长沙讲习班邀请图灵奖获得者美国Cornell大学JohnE.Hopcroft教授讲授信息时代若干前沿研究领域的数学基础，讲课内容对于理解网络时代产生的计算问题具有重要的理论价值，同时也是模式识别、机器学习、计算机视觉、图象处理、数据挖掘等领域的重要理论基础。讲习班采用学与练相结合的方式，每天由JohnE.Hopcroft教授讲授3小时，每小时讲授之后为2小时练习。通过结业考核者将获得由JohnE.Hopcroft教授亲笔签名的结业证书。JohnE.Hopcroft教授简介：JohnE.Hopcroft教授于1961年在Seattle大学获得学士学位，于1962和1964年在Stanford大学分别获得硕士和博士学位。现为美国Cornell大学计算机科学系教授，曾任该系主任和工学院院长。他是美国科学院NationalAcademyofSciences和美国工程院NationalAcademyofEngineering的成员，ACM、IEEE、美国艺术与科学院AAAS、美国科学进步协会和工业与应用数学协会SIAM的Fellow。2008年获ACM杰出教育家奖。1986年获计算机领域最高奖ACM图灵奖。讲课内容：1Highdimensionaldata1.1Thehighdimensionalsphere1.1.1Theshpereandcubeinhigherdimensions1.1.2Volumeoftheunitsphere1.1.3Thevolumeisneartheequator1.1.4Thevolumeisinanarrowannulus1.1.5Thesurfaceareaisneartheequator1.2Generatingpointsuniformlyatrandomonasphere1.3Gaussiansinhighdimension1.4Therandomprojectiontheoremandthenearestneighborproblem2RandomGraphs2.1TheG(n,p)model2.1.1Degreedistribution2.1.2ExistenceoftrianglesinG(n,d/n)2.1.3Phasetransitions2.1.4Phasetransitionsformonotonicproperties2.1.5PhasetransitionforCNF-sat2.1.6Theemerginggraph2.1.7TheGiantcomponent2.2Nonuniformandgrowthmodelsofrandomgraphs2.2.1Nonuniformmodels2.2.2Molloy/Reed2.3Growthmodels2.3.1Growthmodelwithoutpreferentialattachment2.3.2AGrowthModelwithPreferentialAttachment3SingularValueDecomposition(SVD)3.1Singularvectors3.2Singularvaluedecomposition(SVD)3.3Bestrankkapproximations3.4AlgorithmforcomputingtheSingularValueDecomposition3.5ApplicationsofSingularValueDecompostion3.5.1PrincipalComponentAnalysis3.5.2ClusteringaMixtureofSphericalGaussians3.5.3AnApplicationofSVDtoaDiscreteOptimizationProblem3.5.4SVDasaCompressionAlgorithm4RandomWalksonGraphs4.1Electricalnetworksandrandomwalks4.2Randomwalksonundirectedgraphs4.3RandomwalksinEuclideanspace4.4Randomwalksondirectedgraphs4.5FiniteMarkovprocesses4.6MarkovChainMonteCarlo5LearningandVC-dimension5.1Learni