《认识计算机学科》PPT课件.pptVIP

认识计算机学科 内容概要 计算机学科的根本问题 计算机学科的科学问题 计算机学科的根本问题 什么是计算机学科 什么是计算计算机学科的定义 什么是计算 图灵 AlanTuring 所为计算就是计算者 人或机器 对一条可以无限延长的工作带上的符号串执行命令 一步一步地改变工作带上的符号串 经过有限步骤 最后得到一个满足预先规定的符号串的变换过程 图灵的研究成果是 可计算性 图灵可计算性 图灵机 Turingmachinefinitestateautomachine 构造一个识别符号串 anbn n 1 的图灵机基本思想 使读写头往返移动 每往返移动一次 就成对地对输入符号串 左端的一个a和右端的一个b匹配并做标记x 如果恰好把输入符号串 的所有符号都做了标记 说明左端的符号a和右端的符号b的个数相等 否则 说明左端的符号a和右端的符号b的个数不相等 或者符号a和b交替出现 用图灵模型来计算 q0 aaRq0 q0 bxLq1 q1 xxLq1 q1 axRq2 q1 BBHqN q2 xxRq2 程序 假定n 2 输入符号串 aabb 用图灵模型来计算 控制器 工作带 BaabbB 读写头 q0 aaRq0 q0 bxLq1 q1 xxLq1 q1 axRq2 q1 BBHqN q2 xxRq2 读写头 程序 字母表 a b B 用图灵模型来计算 控制器 工作带 BaabbB 读写头扫描到符号a 则继续往右走 q0 aaRq0 q0 bxLq1 q1 xxLq1 q1 axRq2 q1 BBHqN q2 xxRq2 读写头 程序 用图灵模型来计算 控制器 工作带 BaabbB 读写头扫描到符号a 则继续往右走 q0 aaRq0 q0 bxLq1 q1 xxLq1 q1 axRq2 q1 BBHqN q2 xxRq2 读写头 程序 用图灵模型来计算 控制器 工作带 BaabbB 读写头扫描到符号b 将当前单元写入字符x 并使读写头往左走 转移到状态q1 q0 aaRq0 q0 bxLq1 q1 xxLq1 q1 axRq2 q1 BBHqN q2 xxRq2 读写头 程序 用图灵模型来计算 控制器 工作带 BaaxbB 读写头扫描到符号b 将当前单元写入字符x 并使读写头往左走 转移到状态q1 q0 aaRq0 q0 bxLq1 q1 xxLq1 q1 axRq2 q1 BBHqN q2 xxRq2 读写头 程序 用图灵模型来计算 控制器 工作带 BaaxbB 读写头扫描到符号a 则把a改为标记x 并使读写头往右走 转移到状态q2 q0 aaRq0 q0 bxLq1 q1 xxLq1 q1 axRq2 q1 BBHqN q2 xxRq2 读写头 程序 用图灵模型来计算 控制器 工作带 BaxxbB 读写头扫描到符号a 则把a改为标记x 并使读写头往右走 转移到状态q2 q0 aaRq0 q0 bxLq1 q1 xxLq1 q1 axRq2 q1 BBHqN q2 xxRq2 读写头 程序 用图灵模型来计算 控制器 工作带 BaxxbB 读写头扫描到标记x 则继续往右走 q2 bxLq1 q2 BBLq3 q3 xxLq3 q3 aaHqN q3 BBHq4 读写头 程序 用图灵模型来计算 控制器 工作带 BaxxbB 若读写头扫描到符号b 则把b改为标记x 并使读写头往左走 转移到状态q1 读写头 程序 用图灵模型来计算 控制器 工作带 BaxxxB 若读写头扫描到符号b 则把b改为标记x 并使读写头往左走 转移到状态q1 q0 aaRq0 q0 bxLq1 q1 xxLq1 q1 axRq2 q1 BBHqN q2 xxRq2 读写头 程序 用图灵模型来计算 控制器 工作带 BaxxxB 读写头扫描到标记x 则继续往左走 q0 aaRq0 q0 bxLq1 q1 xxLq1 q1 axRq2 q1 BBHqN q2 xxRq2 读写头 程序 用图灵模型来计算 控制器 工作带 BaxxxB 读写头扫描到符号a 则把a改为标记x 并使读写头往右走 转移到状态q2 q0 aaRq0 q0 bxLq1 q1 xxLq1 q1 axRq2 q1 BBHqN q2 xxRq2 读写头 程序 用图灵模型来计算 控制器 工作带 BxxxxB 读写头扫描到标记x 则继续往右走 q0 aaRq0 q0 bxLq1 q1 xxLq1 q1 axRq2 q1 BBHqN q2 xxRq2 读写头 程序 用图灵模型来计算 控制器 工作带 BxxxxB 读写头扫描到标记x 则继续往右走 q0 aaRq0 q0 bxLq1 q1 xxLq1 q1 axRq2 q1 BBHqN q2 xxRq2 读写头 程序 用图灵模型来计算 控制器 工作带 BxxxxB 读写头扫描到标记x 则继续往右走 q0 aaRq0 q0 bxLq1 q1 xxLq1 q1 axRq2 q1 BBHqN q2 xxRq2 读写头 程序 用图灵模型来计算 控制器 工作带 BxxxxB 读写头扫描到空白符B 说明符号b已处理完毕 则把状态改为q3 并使读写头往左走 q2 bxLq1 q2 BBLq3 q3 xxLq3 q3 aaHqN q3 BBHq4 读写头 程序 用图灵模型来计算 控制器 工作带 BxxxxB 读写头扫描到空白符B 说明符号b已处理完毕 则把状态改为q3 并使读写头往左走 q2 bxLq1 q2 BBLq3 q3 xxLq3 q3 aaHqN q3 BBHq4 读写头 程序 用图灵模型来计算 控制器 工作带 BxxxxB 读写头扫描到标记x 则继续往左走 q2 bxLq1 q2 BBLq3 q3 xxLq3 q3 aaHqN q3 BBHq4 读写头 程序 用图灵模型来计算 控制器 工作带 BxxxxB 读写头扫描到标记x 则继续往左走 q2 bxLq1 q2 BBLq3 q3 xxLq3 q3 aaHqN q3 BBHq4 读写头 程序 用图灵模型来计算 控制器 工作带 BxxxxB 读写头扫描到标记x 则继续往左走 q2 bxLq1 q2 BBLq3 q3 xxLq3 q3 aaHqN q3 BBHq4 读写头 程序 用图灵模型来计算 控制器 工作带 BxxxxB 读写头扫描到空白符B 说明符号a和b已成对标记 转移到状态q4 达到接受状态 q2 bxLq1 q2 BBLq3 q3 xxLq3 q3 aaHqN q3 BBHq4 图灵机反映的是一种具有能行性的用数学方法精确定义的计算模型而现代计算机正是这种模型的具体实现 科学与学科 科学是关于自然 社会和思维的发展与变化规律的知识体系 是由人类在生产活动和社会活动中产生和发展的 是人类实践经验的结晶 科学是逐步发展起来的科学的发展需要某种特殊的方法科学在不断超越中永无止境地发展 科学与学科 学科本身具有二重含义 指知识体系或学术分类 含义较广 指为培养人才而设立的教学科目 科学与学科 科学研究是以问题为基础的 学科是在科学发展中不断分化和整合而形成和发展的 是科学研究发展成熟的产物 科学研究发展成熟而成为一个独立学科的标志是 必须有独立的研究内容 成熟的研究方法 规范的学科体制 计算机学科的定义 计算机学科是对描述和变换信息的算法过程 包括对其理论 分析 设计 效率 实现和应用等进行的系统研究 它来源于对算法理论 数理逻辑 计算模型 自动计算机器的研究 并与存储式电子计算机的发明一起形成于20世纪40年代初期 计算机学科的特点 计算机学科包括科学和技术两个方面 科学侧重于研究现象 揭示规律 技术则侧重于研制计算机 研究使用计算机进行信息处理的方法与技术手段 科学是技术的依据 技术是科学的体现 二者高度融合是计算机科学与技术学科的突出特点 计算机学科是一门科学性与工程性并重的学科 表现为理论和实践紧密结合的特征 计算机学科的特点 科学 关于自然 社会和思维的发展与变化规律的知识体系 其核心是发现 技术 根据实践经验和科学原理而发展形成的各种工艺操作方法 技能和技巧 其核心是发明 工程 将科学原理应用到生产实践中 是某种形式的科学应用 其核心是建造 什么是科学问题 科学问题是指一定时代的科学认识主体 在已完成的科学知识和科学实践的基础上 提出的需要解决且有可能解决的问题 它包含一定的求解目标和应答域 但尚无确定的答案 科学问题具有如下主要特征 1 时代性 2 混沌性 3 可解决性 4 可变异性 5 可待解性科学问题的提出和解决是任何一个学科持续发展的动力 计算机学科的科学问题 1 计算的平台与环境问题核心 计算问题的能行性2 计算过程的能行操作与效率问题核心 算法及算法分析3 计算的正确性问题核心 各种语言的语义上述基本问题普遍出现在学科的各个分支学科和研究方向之中 是学科研究与发展中经常面对而又必须解决的科学问题 计算机学科的经典问题 经典问题是指那些反映学科某一方面内在规律和本质内容的典型问题 经典问题往往以深入浅出的形式表达学科深奥的科学规律和本质内容 在学科研究中常常用来辅助说明思想 原理 方法和技术 1968年 计算机科学家狄杰斯特拉首次提出了GOTO语句是有害的 1974年 计算机科学家克努斯发表论文 带有GOTO语句的结构化程序设计 作了较全面而公正的论述 面条程序示例 GOTO语句问题与程序设计方法学 GOTO语句问题与程序设计方法学 滥用GOTO语句是有害的 完全禁止也是不明智的 在不破坏程序良好结构的前提下 有限制地使用GOTO语句 有可能使程序更清晰 效率更高 关于 GOTO语句 问题的争论直接导致了一个新的学科分支领域 程序设计方法学的产生 它是一个对程序的性质及其设计的理论和方法进行研究的学科 哥尼斯堡七桥问题与图论 哥尼斯堡七桥问题 是否能在一次步行中穿越全部的七座桥后回到起点 且每座桥只经过一次 哥尼斯堡七桥问题与图论 欧拉回路的判定规则 1 如果通奇数桥的地方多于两个 则不存在欧拉回路 2 如果只有两个地方通奇数桥 可以从这两个地方之一出发 找到欧拉回路 3 如果没有一个地方是通奇数桥的 则无论从哪里出发 都能找到欧拉回路 哈密顿回路问题 哈密顿回路 要求从一个城市出发 经过每个城市恰好一次 然后回到出发城市 哈密顿回路问题 美国图论数学家奥勒在1960年给出了一个图是哈密尔顿图的充分条件 对于顶点个数大于2的图 如果图中任意两点度的和大于或等于顶点总数 那这个图一定是哈密尔顿图 寻找哈密顿路径是一个典型的NP 完全问题 后来人们也证明了 找一条哈密顿路的近似比为常数的近似算法也是NP 完全的 从图中的任意一点出发 路途中经过图中每一个结点当且仅当一次 则成为哈密顿回路 哲学家共餐问题与进程同步 哲学家的生活进程可表示为 1 思考问题 2 饿了停止思考 左手拿起一只筷子 如果左侧哲学家已持有它 则等待 3 右手拿起一只筷子 如果右侧哲学家已持有它 则等待 4 进餐 5 放下左手筷子 6 放下右手筷子 7 重新回到状态 1 思考问题 哲学家共餐问题与进程同步 程序并发执行时进程同步的两个关键问题 死锁和饥饿 1 按哲学家的生活进程 当所有的哲学家都同时拿起左手筷子时 则所有哲学家都将拿不到右手筷子 并处于等待状态 那么 哲学家都将无法进餐 最终饿死 2 将哲学家的生活进程修改为当拿不到右手筷子时 就放下左手筷子 但是 可能在一个瞬间 所有的哲学家都同时拿起左手筷子 则自然拿不到右手筷子 于是都同时放下左手筷子 等一会 又同时拿起左手筷子 如此重复下去 则所有的哲学家都将无法进餐 汉诺塔问题与计算复杂性 汉诺塔问题 在世界刚被创建的时候有一座钻石宝塔 塔A 其上有64个金碟 所有碟子按从大到小的次序从塔底堆放至塔顶 紧挨着这座塔有另外两个钻石宝塔 塔B和塔C 从世界创始之日起 婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去 其间借助于塔B的帮助 每次只能移动一个碟子 任何时候都不能把一个碟子放在比它小的碟子上面 当牧师们完成任务时 世界末日也就到了 汉诺塔问题与计算复杂性 汉诺塔问题与计算复杂性 n个碟子的汉诺塔问题需要移动的碟子数是n 1个碟子的汉诺塔问题需要移动的碟子数的2倍再加1 因此 用C语言对该问题的求解算法进行描述 hanoi intn charleft charmiddle charright if n 1 move 1 one three else hanoi n 1 left right middle move 1 left right hanoi n 1 middle left right 汉诺塔问题与计算复杂性 64个碟子的汉诺塔问题 需要移动的碟子数为 264 1 18 446 744 073 709 551 615如果每秒移动一次 一年有31 536 000秒 则僧侣们一刻不停地来回移动 也需要花费5849亿年的时间 假定计算机以每秒1000万个碟子的速度进行移动 则需要花费58 490年的时间 证比求易问题与NP完全问题 在计算复杂性领域中 一般认为求解一个问题往往比较困难 但验证一个问题相对来说就比较容易 证比求易 求大整数S 49 770 428 644 836 899的因子是个难解问题 但是验证a 223 092 871是不是大整数S的因子却很容易 求一个线性方程组的解可能很困难 但是验证一组解是否是方程组的解却很容易 证比求易问题与NP完全问题 在计算复杂性领域中 将所有可以在多项式时间内求解的问题称为P类问题 而将所有可以在多项式时间内验证的问题称为NP类问题 P NP是否成立是计算科学和当代数学研究中最大的悬而未决的问题之一 20世纪70年代初 库克在证明了NP类中某些问题的复杂性与整个NP类的复杂性有关 当这些问题中的任何一个存在多项式时间算法 则所有这些NP类问题都是在多项式时间内可解决的 这些问题称为NP完全问题 TSP问题与组合爆炸 TSP问题 又称货郎担问题 邮递员问题 售货员问题 是数学家克克曼于19世纪初提出的一个数学问题 是指旅行家要旅行n个城市然后回到出发城市 要求各个城市经历且仅经历一次 并要求所走的路程最短 由于TSP问题有着貌似简单的表述 重要的应用 以及和其他NP完全问题的重要关系 它在近200年的时间里强烈地吸引着计算机科学工作者 TSP问题与组合爆炸 10城市的TSP问题有大约180 000个可能解 20城