什么是计算-北京大学数学科学学院.pdfVIP

计算概论 （什么是 “计算”-2） 裘宗燕 北京大学数学学院信息科学系 2015, 春季 计算概论（Python程序设计） 裘宗燕，2015/5/11//-1- 现实的计算  问题：现实中的计算机真的等价于通用图灵机吗？  两个重要不同点：  图灵机有无穷长的存储带，现实计算机的存储器是有穷的  图灵机没有时间概念，而实际计算机操作需要时间。无论一 次操作多快，大量操作累计可能超过任何给定时间  这两个问题是本质性的，与所有计算问题有关，因为 在每个计算问题的求解过程中都需要存储相关的数据 每个计算问题都要通过一系列操作完成，操作需要时间  这些问题为计算领域提出了新的研究课题： 数据存储量和操作时间将怎样影响计算？怎样思考/理解能用实 际计算机（或其他计算工具）解决的问题和计算的局限性？ 计算概论（Python程序设计） 裘宗燕，2015/5/11//-2- 问题，实例，算法  为抽象地研究现实的计算问题，假定 计算中的数据存储有一种基本单元，每个单元只能保存固定 的一点有限数据（一个单位的空间） 计算中的一次操作要消耗一个单位的时间  考虑计算问题时，需要区分三个概念  问题：一个问题W 是一个需要解决的需求（需用计算求解）， 如求实数的平方根，找出大于整数m 的第一个素数等  问题实例：问题W 的一个实例w 是该问题的一个具体例子， 如求2.0 的平方根，找出大于1010 的第一个素数 算法：解决问题W 的一个算法A ，是能求解W 的所有实例 的一个计算过程的严格描述。对W 的实例w ，实施算法A 描述的计算过程能得到所需结果。如平方根算法能求出2.0 的平方根，求素数算法能得到大于1010 的第一个素数 计算概论（Python程序设计） 裘宗燕，2015/5/11//-3- 算法设计与分析  用计算机解决问题，需要开发解决问题的方法（算法）。解决重 要问题的算法不仅具有理论价值，也有实际价值。例如： google 的网络检索算法，有效利用大量计算机，ranking  高安全和高效率的加密解密算法  算法是计算机领域最重要的研究课题（遍及所有研究/应用领域） 两件工作：总结/发现需要解决的问题，开发相关的高效算法  人们也考查算法的设计与分析工作，总结算法研究的经验 总结出一批设计算法的重要模式（思路） 分析具体算法的性质，主要是时间和空间开销  算法设计是创造性工作，需要人的智慧，不能自动化 算法设计：从问题的说明性描述到解决问题的过程性描述 计算概论（Python程序设计） 裘宗燕，2015/5/11//-4- 算法的复杂性（复杂性）  对解决某个具体计算问题W 的具体算法A 考虑A 计算中的存储开销和时间开销 算法A 应该能处理问题Q 的任一个实例，具体实例的规模不 同，具体计算的实际开销与实例的规模有关  为反映问题实例的具体规模对计算代价的影响，我们把一个算法 的计算（时间和空间）代价定义为问题实例规模的函数 可能有一些问题，其时间（或空间）开销函数随规模扩大增长 得很快，另一些问题的开销函数增长较慢 用函数关系反映计算的性质，实际上是描述一种增长趋势。这 两个函数关系称为算法的时间代价和空间代价  但不同实际机器的操作执行速度、存储单元大小都可能不同。理 论研究应该抽象，应排除具体机器的非普遍性特征，反映问题的 共性和本质 计算概论（Python程