920660-大学计算机教材配套课件-DJ7--计算与计算学科-v2

大学计算机第2页大学计算机基础第一章基于计算机的问题求解第二章计算机信息数字化基础第三章计算机的工作原理与硬件体系结构第四章计算机软件平台第五章计算机网络平台第六章数据处理与数据库第七章计算与计算科学第八章算法与程序设计第九章实用软件第十章计算机科学前沿技术第3页第七章计算与计算科学问题导入:邱奇-图灵论题的焦点是什么？如果解决问题的算法无法构建，则表明该问题一定是不可解的；任何在算法上可计算的问题同样可由图灵机计算——所有计算或算法都可以由一台图灵机来执行。计算思维是人的思维，而不是计算机的思维第4页7.1计算的本质7.2关于计算学科7.3普适计算及其应用第1章基于计算机的问题求解第七章计算与计算科学第5页7.1计算的本质7.1.1什么是计算1.关于计算计算是构建在一套公理体系上的、不断向上演化的规则。比如我们日常的四则运算，它的公理体系应该是由三部分组成：数字、基本运算符、组合规则。那么，抽象地描述计算应该是：基于规则的符号集合的变换过程，即从一个按规则组织的符号集合开始，再按照既定的规则一步步地改变这些符号集合，经过有限步骤之后得到一个确定的结果。第6页2.计算的分类计算理论的研究，侧重于从数学角度证明表达能力和正确性，比较典型的图灵机、lambda演算、pi演算这些都属于这个范畴；计算模型的研究，侧重于对真实系统的建模和刻画，比如冯诺伊曼模型、BSP模型、LogP模型等等。在计算这个问题上的两种范式7.1计算的本质第7页3.计算的本质在图灵机中，计算就是计算者对一条无限长的纸带上的符号串执行指令，一步一步地改变纸带上某个位置的符号，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。这个模型的关键是形式化方法。用“纸带符号串→控制有限步骤→读/写头→结果”这一形式表述计算过程的本质。7.1计算的本质第8页以计算机下棋为例：一个简单的井字棋盘如图7-1所示，计算机的计算主要是建立在一个状态空间树（博奕树）的搜索方式上。计算机需要操作的数据对象是每走一步棋后形成的新的棋盘状态（格局）。图7-1井子棋示意图图7-2计算解释器解释器棋盘状态行动决策7.1计算的本质第9页不同的解释器对应着不同的计算模型，比如我们常说的符号计算和数值计算，其实就是指我们输入的数据是数值或是符号，然后各自对应一个自己的解释器，通过不同的计算模型得出各自需要的结果。它们是不同的计算模型，但是本质都是相同的：计算过程符号化。对各种不同计算的实现，首先是人的计算思维活动，是计算的过程化、形式化思维活动的表达，体现为算法、程序或软件。计算的本质就是通过演化产生新的信息7.1计算的本质第10页7.1.2可计算与不可计算1.什么问题不可计算图灵论题一个可计算问题是“当且仅当它在图灵机上经过有限步骤之后可以得到正确的结果”根据这一论题，通常人们把所面临的问题分为可计算问题与不可计算问题两大类7.1计算的本质第11页那么什么问题不可计算？例如，一直被关注的图灵“停机问题”就是不可计算的，因为他无法用数学的方式证明，这是不可计算的典型问题。事实上，如果该问题可计算，那么编译程序就可以在运行程序之前判断该程序是否存在死循环。而实际中死循环程序和一个只是“运行很慢”的程序是无法得以明确区分的。证明一个问题不可计算：证明它如果可以计算，那么停机问题就可以计算7.1计算的本质第12页首先，判定一个程序是否会停机，是指：对于其的任意一个输入，可判定其是否停机。那么假定这样的图灵机存在，设为H。其工作过程不妨设为：若对于任意一个程序M可停机则输出1，反之输出0（由于其是可判定的）。那么可以构造另一程序D，其工作过程为：以H输出为输入，若输入为1则不停机，反之停机。由于H可判定所有程序，那么其也可判定D，若其判定D输入1时不停机，则其输出0，而由于D的定义知它是可停机的，反之亦然。故停机问题无算法解。7.1计算的本质第13页2.问题的可计算判断“能行过程”：针对所要解决的问题是否存在能行方法，以此来判断可计算问题是否实际可解。无论是数学还是工程，解决问题的过程就是问题状态发生变化的过程。如果我们以参数形式来描述问题状态，那么解决问题的过程就可以看作是一个参数变化的过程，如表7-1所示。这个过程中如果输入参数和输出参数的对应关系是明确的，则说明这个过程是能行的，也就是说这个问题是可计算的。过程时间问题状态参数形式开始初始状态输入参数结束结果状态输出结果表7-1解决问题的参数变化过程7.1计算的本质第14页例7-1设m和n是两个正整数，且mn。求m和n的最大公因子的欧几里得算法，可以通过下列过程表示:步骤1：以n除m得余数r.//求余数步骤2：若r=0,则输出答案n，过程终止;否则转到步骤3.//判断余数是否为0步骤3：把m的值变为n,n的值变为r，重复上述步骤.//变换参数值输入参数为正整数m和n，每一个步骤描述明确，都可以通过一些可实现的基本运算（或判断）完成，经过有穷步骤之后终止。这是一个能行过程，说明求m和n的最大公约数的问题是可计算的。7.1计算的本质第15页[情景问题7-1]在宇宙的另一个国度，如果那里的人不是只说真话就是只说谎话。那么，要设计一个什么样的问题才能明确判断一个人是说真话还是谎话呢？7.1计算的本质第16页7.1.3计算复杂性1.三大数学难题世界近代三大数学难题即“三大数学猜想”：费马猜想、四色猜想和哥德巴赫猜想。以上三个问题的共同点就是：题面简单易懂，但内涵深邃无比，困扰了一代代的数学家。这就是计算复杂性的问题。7.1计算的本质第17页2.计算复杂性对于数学和计算机应用学科来说，平常我们关心的是计算机需要花多长时间去解决一个问题，即：可计算且能在有限时间有解。换言之，这个问题有多复杂？可计算未必能有完全解。因为这里的可计算问题仅仅是来自于理论思维上的可计算，图灵机模型中的“有限步骤”是一个过于宽松的限制，它甚至包括了需要计算好几百年才能完成的那些问题。实际上对可计算问题可否实际计算还需要判断其复杂性。如果一个问题的最好算法需要100年才能够完成计算过程，那你认为这个问题是可计算的吗？为什么？7.1计算的本质第18页20世纪70年代，库克（StephenCook）将可计算问题进一步分为实际可解和实际不可解：一个问题是实际可计算的当且仅当它能够在图灵机上经过多项式步骤得到正确结果（易解性等同于多项式时间可计算性）。这就是著名的库克论题，它界定了计算机的实际计算能力限度。超过这个限度的问题一般被认为是难解问题。其中一个典型的难解问题就是汉诺塔问题。图7-3汉诺塔问题7.1计算的本质第19页[练习与思考7-1]尝试设计一个计算过程，确定你今年的年龄是否是素数。考虑一下你的解决方法的效率。这个问题是一个难解的问题吗？为什么？7.1计算的本质第20页7.1计算的本质7.2关于计算学科7.3普适计算及其应用第1章基于计算机的问题求解第七章计算与计算科学第21页7.2关于计算学科7.2.1计算学科的根本问题凡是与“能行性”有关的讨论，所处理的大都是离散型问题，即很难处理连续型对象的问题。能行性这个计算学科的根本问题，决定了计算机本身的结构和它处理的对象都是离散型的。甚至许多连续型的问题也必须在转化为离散型问题以后才能被计算机处理。例如计算定积分就是把它变成离散量再用分段求和的方法来处理的。“计算作为一门学科”(Computingasadiscipline)，1985年ACM和IEEE-CS联合发表。第22页7.2关于计算学科第23页7.2.2计算学科与计算机学科的区别传统的计算机学科是指与计算机相关的科学与技术，是研究计算机的设计、制造，以及用其进行信息获取、表示、存储、处理控制等的理论、原则、方法和技术的学科，应该包括科学和技术两方面。计算机科学侧重研究现象、揭示规律；而计算机技术则侧重于研制计算机以及研究使用计算机进行处理的方法和手段。“计算学科是将来讨论计算机科学工程的基础……”7.2关于计算学科第24页7.2.3计算学科的三大过程—理论、抽象与设计1.理论理论根植于数学。如算法和数据结构的分支领域包含复杂性理论和图理论。•特征化研究的对象（定义）；•假设它们之间可能的联系（定理）；•判断它们联系的真实性（证据）；•解释结果。理论过程发展的四个步骤：7.2关于计算学科第25页2.抽象•针对问题，应用理论提出假设；•建立模型并进行预测；•设计实验并收集数据；•分析结果总结归纳。抽象过程发展的四个步骤：抽象即建模，根植于实验科学的方法论。抽象就是把事物的特点从具体问题实例里面抽取出来，形成一套适合所有实例的框架。是从个别到一般，从现象到本质的认知过程和思维方法。7.2关于计算学科第26页3.设计•陈述需求；•建立规格陈述说明；•设计构建系统；•对系统的测试与分析系统。设计方法的四个步骤：设计根植于工程，并用于系统或设备的开发，实现给定的任务。设计作为变革、控制和利用自然界的手段，必须以对自然规律的认识（科学形态或经验形态的认识）为前提。设计要达到目的，必须创造出相应的人工系统和人工条件，还必须认识自然规律在这些人工系统和人工条件下的具体表现形式。7.2关于计算学科第27页理论是数学的基石，数学家认为科学进步是以扎实的数学为基础的抽象（建模）是自然科学的基石，科学家认为只有通过形式化假设和遵循系统建模过程去验证才能取得科学进步设计是工程的基石，工程师认为通过提出问题、按设计过程构建系统来解决问题，才能取得科学进步。理论、抽象、设计三者盘根错节，是计算学科不可或缺的环境，也是计算机科学的基础和方法依据。7.2关于计算学科第28页[练习与思考7-2]1)请查找一下你所学的专业课中与计算机学科相关的课程有哪些？具体在什么方面会用到？用计算、程序还是软件？举例说明。2)请查找一下国外在你专业方面排名前十名的高校中，他们在课程设置上，就计算机科学与你专业的融合方面有哪些不同？说说自己的认识。7.2关于计算学科第29页7.1计算的本质7.2关于计算学科7.3普适计算及其应用第1章基于计算机的问题求解第七章计算与计算科学第30页7.3普适计算及其应用1.普适计算的特点普适计算的概念源于1988年美国Xerox（施乐）公司PARC研究中心的一系列研究计划，又称为“无处不在的计算”。普适计算的创始人MarkWeiser说：“只有当机器进入人们生活环境而不是强迫人们进入机器世界时，机器的使用才能像林中漫步一样新鲜有趣。”所以普适计算追求的是：人可以和计算环境更好地融为一体，人们能够在任何时间、任何地点、以任何方式进行信息的获取与处理。第31页2.普适计算的研究内容普适计算需要从多个方面进行突破研究，最终构建一个普适计算的体系结构。这些方面包括：普适计算设备：包括传统计算机设备、移动数字设备及智能电子设备等，共同协作搜集传递信息，对环境命令进行响应并完成相关动作。普适网络系统软件：保持用户在普适计算环境中的自然感。人机交互和觉察上下文：普适计算环境中需要对人机交互上下文环境足够警觉，才能够在不打扰用户的前提下觉察到人机交互的需求，及时、主动地提供服务。7.3普适计算及其应用第32页3.一个普适计算应用实例在美国华盛顿湖的东岸，有一幢名为Bighouse的大房子，又被称作是“未来之屋”，比尔盖茨就曾住在这座广为人知的房屋里。图7-4盖茨“未来之屋”客厅7.3普适计算及其应用第33页[练习与思考7-3]本节中提到，普适计算的一个重要特点是能够在不打扰用户前提下觉察到人机交互的需求，进而及时、主动提供服务。这种特征其实已经可以在今天的某些高科技产品中初见端倪，试举出几例，并说明人机交互上下文是如何被觉察并加以判断的。7.3普适计算及其应用第34页小结计算本质计算的概念计算的分类计算的形式化本质可计算性计算复杂性计算学科与计算机学科的异同普适计算