第一章计算机科学研究概述.ppt

计算机科学研究概述 Lecture 3 第一节 计算机科学研究的历史背景 1.1 计算机科学源于欧美，诞生于20世纪40年代初。 在第一台电脑诞生以前 1.2 ACM和IEEE-CS Association for Computing Machinery Institute of Electrical and Electronics Engineers-Computer Society 1.3 《计算作为一门学科》的报告（Computing as a Discipline） CC1991 CC2001 世界上第一台计算机 ENINAC 1.4 计算学科中的典型问题 哥尼斯堡七桥问题 17世纪的东普鲁士有一座哥尼斯堡城，城中有一座奈佛夫岛，普雷格尔河的两条支流环绕其旁，并将整个城市分成北区、东区、南区和岛区4个区域，全城共有7座桥将4个城区相连起来。 通过这7座桥到各城区游玩，问题：寻找走遍这7座桥的路径，要求过每座桥只许走一次，最后又回到原出发点。 问题的抽象 1736年，大数学家列昂纳德·欧拉（L.Euler）发表了关于“哥尼斯堡七桥问题”的论文。 他抽象出问题最本质的东西，忽视问题非本质的东西（如桥的长度等），从而将哥尼斯堡七桥问题抽象为一个数学问题，即经过图中每边一次且仅一次的回路问题 欧拉回路 欧拉给出了哥尼斯堡七桥问题 的证明，还用数学方法给出了三条判定规则： 如果通奇数座桥的地方不止两个，满足要求的路线是找不到的。 如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路线。 如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路线都能实现。 图论的形成和发展 欧拉的论文为图论的形成奠定了基础。 图论已广泛地应用于 计算学科 运筹学 信息论 控制论等学科 图论已成为我们对现实问题进行抽象的一个强有力的数学工具。 图论在计算学科中的作用越来越大，图论本身也得到了充分的发展。 梵天塔问题 将64个直径大小不一的金盘子，按照从大到小的顺序依次套放在第一根柱子上，形成一座金塔，天神让庙里的僧侣们将第一根柱子上的64个盘子借助第二根柱子全部移到第三根柱子上，既将整个塔迁移，同时定下3条规则： 每次只能移动一个盘子； 盘子只能在三根柱子上来回移动，不能放在他处； 在移动过程中，三根柱子上的盘子必须始终保持大盘在下，小盘在上 Hanoi Tower 假定每秒移动一次，一年，则僧侣们一刻不停地来回搬动，也需要花费大约5849亿年的时间。 假定计算机以每秒1000万个盘子的速度进行搬迁，则需要花费大约58490年的时间。 理论上可以计算的问题，实际上并不一定能行，这属于算法复杂性方面的研究内容。 证比求易算法(1) 艾述国王向邻国秋碧贞楠公主求婚。公主出了一道题： 求出48 770 428 433 377 171的一个真因子。若国王能在一天之内求出答案，公主便接受他的求婚。 国王回去后立即开始逐个数地进行计算，他从早到晚，共算了三万多个数，最终还是没有结果。国王向公主求情，公主将答案相告：223 092 827是它的一个真因子。国王很快就验证了这个数确能除尽48 770 428 433 377 171。 证比求易算法(2) 国王立即回国，并向时任宰相的大数学家孔唤石求教，大数学家在仔细地思考后认为这个数为17位，则最小的一个真因子不会超过9位， 他给国王出了一个主意：按自然数的顺序给全国的老百姓每人编一个号发下去，等公主给出数目后，立即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即上报，赏金万两。 顺序算法和并行算法 国王最先使用的是一种顺序算法，其复杂性表现在时间方面， 后面由宰相提出的是一种并行算法，其复杂性表现在空间方面。 直觉上，我们认为顺序算法解决不了的问题完全可以用并行算法来解决，甚至会想，并行计算机系统求解问题的速度将随着处理器数目的不断增加而不断提高，从而解决难解性问题，其实这是一种误解。 当将一个问题分解到多个处理器上解决时，由于算法中不可避免地存在必须串行执行的操作，从而大大地限制了并行计算机系统的加速能力。 第二节 计算机科学研究的主领域 离散结构(DS) 程序设计基础(PF) 算法与复杂性(AL) 体系结构(AR) 操作系统(OS) 网络计算(NC) 程序设计语言(PL) 人－机交互(HC) 图形学和可视化计算(GV) 智能系统(IS) 信息管理(IM) 软件工程(SE) 社会和职业的问题(SP) 科学计算(CN) 2.1 离散结构（DS） 离散结构列为第一主领域的重要性:既属于学科理论形态方面的内容，又具有广泛的应用价值，为各分支领域提供了强有力的数学工具。 离散结构的主要内容包括集合论，数理逻辑，近世代数，图论和组合数学等。 2.2 程序设计基础（P