计算模型与计算机体系结构 理论计算机 ■冯诺依曼型计算机 计算机网终 ■新型计算机 计算机发展反思:动力:社会需求 目标:追求新型计算模型,制造先进计算机 条件:理论指导,技术支持
计算模型与计算机体系结构 ◼理论计算机 ◼冯.诺依曼型计算机 ◼计算机网络 ◼新型计算机 ◼计算机发展反思:动力:社会需求; 目标:追求新型计算模型,制造先进计算机; 条件:理论指导,技术支持
理论计算机 布尔代数 数理逻辑与哥德尔定理 计算模型与图灵机 ■可计算性:在有限步骤内可完成 图灵机可计算性。 计算复杂性 返回
理论计算机 ◼布尔代数 ◼数理逻辑与哥德尔定理 ◼计算模型与图灵机 ◼可计算性：在有限步骤内可完成。 图灵机可计算性。 ◼计算复杂性 返回
计算复杂性 ■算法的概念 几个例子 算法的评价 证比求易问题 相似性原理 ■对偶性原理 ■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 返回