UOOC_Ch01分解.ppt

* 三、国王的婚姻 1.4 计算学科的典型问题 国王：艾述(喜爱数学) 宰相：孔唤石(数学家) 公主：秋碧贞楠(邻国) 公主：求出48770428644836899的一个真因子 国王：2,3,4,┅,30000多数据(一天) 公主：验证一下，223092871 宰相：将全国百姓按自然数的顺序编号，百姓用自己的编号去除公主的数，谁除尽来领赏。 童话说明：①国王本人计算(串行算法，时间复杂性) ②全国百姓计算(并行算法，空间复杂性) * 四、旅行商问题 旅行商问题(TSP)的描述：一位商人去n个城市推销货物，所有城市走一遍后，再回到起点，问如何事先确定好一条最短的路线，使其旅行的费用最少。 1.4 计算学科的典型问题 路径ABCDA的总距离是：4+2+4+2=12 路径ABDCA的总距离是：4+6+4+6=20 路径ACBDA的总距离是：6+2+6+2=16 路径ACDBA的总距离是：6+4+6+4=20 路径ADCBA的总距离是：2+4+2+4=12 路径ADBCA的总距离是：2+6+2+6=16 * 城市数目为4时，组合路径数为6 城市数目为n时，组合路径数为(n-1)! 当城市数目不多时要找到最短距离的路线并不难，但随着城市数目的不断增大，组合路线数将呈指数级数规律急剧增长，以至到达无法计算的地步，这就是所谓的组合爆炸问题。 1.4 计算学科的典型问题 假如城市的数目增为20个，组合路径数则为 (20-1)！≈1.216×1017 若计算机以每秒检索1000万条路线的速度计算，也需要花上386年的时间。 * 本章小结 计算机的基本概念（定义、分类、特点、应用） 数制之间的相互转换（重点） 原码、反码和补码　（重点） ASCII码、汉字编码 （重点） 多媒体信息编码 计算机工作原理 计算学科的典型问题通过排序问题、汉诺塔问题、国王的婚姻、旅行商问题来说明人所固有的能力与局限性、计算机的计算能力与局限性，以及问题到底有多复杂。 《大学计算机》 第一章 计算机基础知识 《大学计算机》 第一章 计算机基础知识 计算机是一种能对各种信息进行高速处理的工具或电子机器，是20世纪人类最伟大的科技发明之一。人类历史上以往所创造的任何工具或机器都是人类器官的延伸，用于弥补人类体力劳动的不足。例如：一切交通工具都是人腿的延伸，一切机床或工具都是人手的延伸，望远镜、显微镜和电视是人眼的延伸，电话、无线电和卫星通信又是人耳的延伸。而计算机是人类思维器官——大脑的延伸。由于大脑是指挥人体各器官的中枢，因此计算机的问世极大地提高和扩充了人类脑力劳动的效能，开辟了人类智力解放的新纪元。 对上述定义要强调两点： ①不要单纯从字面上理解“计算机”一词。要知道它不仅仅是个计算工具，还应更深刻认识到它是一个信息处理机。有了这一认识，才可能理解计算机为什么能在现代信息社会中掀起一场新技术革命。 ②计算机虽然称为“机”，但是它不同于其它任何机器，它具有存储功能，能存储程序，无需人工直接干预，按程序的引导自动存取和处理数据，输出人们所期望的信息。这也是“计算机”与“计算器”的本质区别。 《大学计算机》 第一章 计算机基础知识 计算机按用途又可分为专用计算机和通用计算机。专用与通用计算机在其效率、速度、配置、结构复杂程度、造价和适应性等方面是有区别的。 专用计算机针对某类问题能显示出最有效、最快速和最经济的特性，但它的适应性较差，不适于其它方面的应用。我们在导弹和火箭上使用的计算机很大部分就是专用计算机。这些东西就是再先进，你也不能用它来玩游戏。 通用计算机适应性很强，应用面很广，但其运行效率、速度和经济性依据不同的应用对象会受到不同程度的影响。 通用计算机按其规模、速度和功能等又可分为巨型机、大型机、中型机、小型机、微型机及单片机。这些类型之间的基本区别通常在于其体积大小、结构复杂程度、功率消耗、性能指标、数据存储容量、指令系统和设备、软件配置等的不同。 一般来说，巨型计算机的运算速度很高，可达每秒执行几亿条指令，数据存储容量很大，规模大结构复杂，价格昂贵，主要用于大型科学计算。它也是衡量一国科学实力的重要标志之一。 单片计算机则只由一片集成电路制成，其体积小，重量轻，结构十分简单，性能介于巨型机和单片机之间的就是大型机、中型机、小型机和微型机。它们的性能指标和结构规模则相应的依次递减。 《大学计算机》 第一章 计算机基础知识 计算机按用途又可分为专用计算机和通用计算机。专用与通用计算机在其效率、速度、配置、结构复杂程度、造价和适应性等方面是有区别的。 专用计算机针对某类问题能显示出最有效、最快速和最经济的特性