清华大学：《计算科学导论》课程教学资源（PPT课件讲稿）第二章 计算模型与计算机体系结构

计算模型与计算机体系结构 理论计算机 ■冯诺依曼型计算机 计算机网终 ■新型计算机 计算机发展反思:动力:社会需求 目标:追求新型计算模型,制造先进计算机 条件:理论指导,技术支持

计算模型与计算机体系结构 ◼理论计算机 ◼冯.诺依曼型计算机 ◼计算机网络 ◼新型计算机 ◼计算机发展反思:动力:社会需求; 目标:追求新型计算模型,制造先进计算机; 条件:理论指导,技术支持

理论计算机 布尔代数 数理逻辑与哥德尔定理 计算模型与图灵机 ■可计算性:在有限步骤内可完成 图灵机可计算性。 计算复杂性 返回

理论计算机 ◼布尔代数 ◼数理逻辑与哥德尔定理 ◼计算模型与图灵机 ◼可计算性：在有限步骤内可完成。 图灵机可计算性。 ◼计算复杂性 返回

计算复杂性 ■算法的概念 几个例子 算法的评价 证比求易问题 相似性原理 ■对偶性原理 ■NP完全性问题 返

计算复杂性 ◼ 算法的概念 ◼ 几个例子 ◼ 算法的评价 ◼ 证比求易问题 ◼ 相似性原理 ◼ 对偶性原理 ◼ NP完全性问题 返回

几个例子 计算“x+1”的图灵机 选择排序问题:将3、74、23、89、22、99、65、109、55、 45十个数按从小到大的顺序排列。步骤: 1、取未排序的数中的第一个数,假设它是其中最小的数 2、将它依次与其后的数相比较,若发现某个数更小,则 目前为止发现的最小数是该数,并假设它是最小数,重复 2直到比较到最后一个数,此时,假设的最小数就是未 序的数中的最小数。 3、将该最小数与未排序的数中的第1个数交换位置。回到 1,直到所有数都排序。 执行该步骤1-3,产生以下的排序过程:

几个例子 ◼ 计算“x+1”的图灵机 ◼ 选择排序问题：将3、74、23、89、22、99、65、109、55、 45十个数按从小到大的顺序排列。步骤： 1、取未排序的数中的第一个数，假设它是其中最小的数。 2、将它依次与其后的数相比较，若发现某个数更小，则 目前为止发现的最小数是该数，并假设它是最小数，重复 2直到比较到最后一个数，此时，假设的最小数就是未排 序的数中的最小数。 3、将该最小数与未排序的数中的第1个数交换位置。回到 1，直到所有数都排序。 执行该步骤1-3，产生以下的排序过程： 返回

选择排序过程 第1遍:3、74、23、89、22、99、65、109、55、45 第2遍:3、22、23、89、74、99、65、109、55、45 第3遍:3、22、23、89、74、99、65、109、55、45 第4遍:3、22、23、45、74、99、65、109、55、89 第5遍:3、22、23、45、55、99、65、109、74、89 第6遍:3、22、23、45、55、65、99、109、74、89 第7遍:3、22、23、45、55、65、74、109、99、89 第8遍:3、22、23、45、55、65、74、89、99、109 第9遍:3、22、23、45、55、65、74、89、99、109 返回

选择排序过程 第1遍：3、74、23、89、22、99、65、109、55、45 第2遍：3、22、23、89、74、99、65、109、55、45 第3遍：3、22、23、89、74、99、65、109、55、45 第4遍：3、22、23、45、74、99、65、109、55、89 第5遍：3、22、23、45、55、99、65、109、74、89 第6遍：3、22、23、45、55、65、99、109、74、89 第7遍：3、22、23、45、55、65、74、109、99、89 第8遍：3、22、23、45、55、65、74、89、99、109 第9遍：3、22、23、45、55、65、74、89、99、109 返回

算法的评价 算的算种 法的复性:是对算法计算所需的时间和空间 漆的时间复杂性:是对算法计算所需时间的 度 漆的空间复杂性:是对算法计算所需空间的 种度量。 复杂性度量函数:算法在求解一类问题的过程中 随回题规模大小变 起的算法中抽象的基本运 算执行的次数或存储空间 变化规律。 例如:f(n)=2n2+3n+1=O(m2),读作n2阶,其中,n为 问题规模。 返回

算法的评价 ◼ 算法的复杂性：是对算法计算所需的时间和空间 的一种度量。 ◼ 算法的时间复杂性：是对算法计算所需时间的一 种度量。 ◼ 算法的空间复杂性：是对算法计算所需空间的一 种度量。 ◼ 复杂性度量函数：算法在求解一类问题的过程中 随问题规模大小变化引起的算法中抽象的基本运 算执行的次数或存储空间量的变化规律。 ◼ 例如：f (n)=2n2+3n+1=O(n2 ),读作n 2阶,其中，n为 问题规模。 返回

证比求易问题 个中国人问题,洪加威,1980 国王:艾述,宰相:孔唤石,公主:秋碧贞楠 求数8770428644836899的一个真因子。 证明23092871是8770428644836899的一个真因子。 问题规模17位,小因子不超过9位 顺序算法与并行算法 对偶性原理:在并行计算模型上,计算的时间与空间可 以互换。 相似性原理:所有合理的、功能足够强的计算模型不仅 可以相互模拟计算,而且它们相互模拟时,同时使用本质 相同的并行时间,本质上相同的空间,本质上相同的顺 序时间

证比求易问题 ◼ 三个中国人问题，洪加威，1980 国王：艾述，宰相：孔唤石，公主：秋碧贞楠 求数8770428644836899的一个真因子。 证明23092871是8770428644836899的一个真因子。 问题规模17位，小因子不超过9位 顺序算法与并行算法 ◼ 对偶性原理：在并行计算模型上，计算的时间与空间可 以互换。 ◼ 相似性原理：所有合理的、功能足够强的计算模型不仅 可以相互模拟计算，而且它们相互模拟时，同时使用本质 上相同的并行时间，本质上相同的空间，本质上相同的顺 序时间。 返回

NP完全性问题 ■难解型问题:没有多项式时间复杂性算法的问题。 ■P类问题:存在图灵机可计算的多项式时间复杂性 算法的问题。 NP问题:存在非确定图灵机可计算的多项式时间 复杂性算法的问题 NP完全性问题:NP问题中若有一个问题找到了 多项式时间复杂性算法,这个类中的其它问题也 可找到多项式时间复杂性算法,则P=NP。返回

NP完全性问题 ◼ 难解型问题：没有多项式时间复杂性算法的问题。 ◼ P类问题：存在图灵机可计算的多项式时间复杂性 算法的问题。 ◼ NP问题：存在非确定图灵机可计算的多项式时间 复杂性算法的问题。 ◼ NP完全性问题：NP问题中若有一个问题找到了 多项式时间复杂性算法，这个类中的其它问题也 可找到多项式时间复杂性算法，则P=NP。 返回

算法的概念 算法 有穷规则的集合,其中之规则确定了 个解决某二特定类型问题的运算序列。此 算法的规则序列须满是如下五个重要条件 1、有穷性:算法必须总是在执行有穷步之后结束; 2、确定性:算法的每一个步骤必须是确切地定乂 的 3、输入:算法有零个或多个输入 4、输出:算法有一个或多个输出; 5:能行性:算法中有待执行的运算和操作必须是 相当基本的

算法的概念 ◼ 算法：一个有穷规则的集合，其中之规则确定了 一个解决某一特定类型问题的运算序列。此外， 算法的规则序列须满足如下五个重要条件： 1、有穷性：算法必须总是在执行有穷步之后结束； 2、确定性：算法的每一个步骤必须是确切地定义 的； 3、输入：算法有零个或多个输入； 4、输出：算法有一个或多个输出； 5：能行性：算法中有待执行的运算和操作必须是 相当基本的。 返回

布尔代数 布尔,G. Boole,19世纪,英国,自学成才 集合代数:集合、集合的运算与性质 集合A,A的补集A’,空集Φ,全集1,属于∈,相 并 集合与命题 布尔代数实现了从一组逻辑公理出发,依靠代数 演篁来推导逻辑定律或定理,用数学的方法来研 究人的思维结构。 语义推导与语法推导 布尔代数、数字逻辑与电子计算机 返回

布尔代数 ◼ 布尔，G. Boole,19世纪，英国，自学成才 ◼ 集合代数：集合、集合的运算与性质 集合A，A的补集A’，空集Ф，全集1，属于，相 等=，包含，交，并 ◼ 集合与命题 ◼ 布尔代数实现了从一组逻辑公理出发，依靠代数 演算来推导逻辑定律或定理，用数学的方法来研 究人的思维结构。 ◼ 语义推导与语法推导 ◼ 布尔代数、数字逻辑与电子计算机 返回