最新认识计算机学科ppt模版课件

L/O/G/O 认识计认识计算机学科 内内容概概要 1 1 2 2 计算机学科的根本问题 计算机学科的科学问题 计算机学科的根本问题 什么是计算机学科 什么是计算 计算机学科的定义 什么是计算 图灵(Alan Turing):所为计算就是计算者(人 或机器)对一条可以无限延长的工作带上的符 号串执行命令，一步一步地改变工作带上的 符号串，经过有限步骤，最后得到一个满足 预先规定的符号串的变换过程。 图灵的研究成果是：可计算性=图灵可计算 性 图灵机：图灵机：Turing machineTuring machine finite state auto machine finite state auto machine computing 构造一个识别符号串anbn（n1）的 图灵机 基本思想：使读写头往返移动，每往返移 动一次，就成对地对输入符号串左端的 一个a和右端的一个b匹配并做标记x。如 果恰好把输入符号串的所有符号都做了 标记，说明左端的符号a和右端的符号b的 个数相等；否则，说明左端的符号a和右 端的符号b的个数不相等，或者符号a和b 交替出现。 用图灵模型来计算 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 程序 假定n2，输入符号串 aabb 用图灵模型来计算 控 制 器 工作 带带 B a a b b B 指令 机器状态态 当前读 到的字符 当前写 入的字符 读写头的动作 R:右移L:左移H:不动 下一机器状态 读写头 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头 程序 字母表：a, b, B 用图灵模型来计算 控 制 器 工作 带带 B a a b b B 读写头扫描到符号a， 则继续往右走 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头 程序 用图灵模型来计算 控 制 器 工作 带带 B a a b b B 读写头扫描到符号a， 则继续往右走 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头 程序 用图灵模型来计算 控 制 器 工作 带带 B a a b b B 读写头扫描到符号b， 将当前单元写入字符x， 并使读写头往左走， 转移到状态q1。 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头 程序 用图灵模型来计算 控 制 器 工作 带带 B a a x b B 读写头扫描到符号b， 将当前单元写入字符x， 并使读写头往左走， 转移到状态q1。 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头 程序 用图灵模型来计算 控 制 器 工作 带带 B a a x b B 读写头扫描到符号a， 则把a改为标记x， 并使读写头往右走， 转移到状态q2 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头 程序 用图灵模型来计算 控 制 器 工作 带带 B a x x b B 读写头扫描到符号a， 则把a改为标记x， 并使读写头往右走， 转移到状态q2 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头 程序 用图灵模型来计算 控 制 器 工作 带带 B a x x b B 读写头扫描到标记x， 则继续往右走 (q2, b x L q1) (q2, B B L q3) (q3, x x L q3) (q3, a a H qN) (q3, B B H q4) 读写头 程序 用图灵模型来计算 控 制 器 工作 带带 B a x x b B 若读写头扫描到符号b， 则把b改为标记x， 并使读写头往左走， 转移到状态q1 读写头 程序 用图灵模型来计算 控 制 器 工作 带带 B a x x x B 若读写头扫描到符号b， 则把b改为标记x， 并使读写头往左走， 转移到状态q1 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头 程序 用图灵模型来计算 控 制 器 工作 带带 B a x x x B 读写头扫描到标记x， 则继续往左走 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头 程序 用图灵模型来计算 控 制 器 工作 带带 B a x x x B 读写头扫描到符号a， 则把a改为标记x， 并使读写头往右走， 转移到状态q2； (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头 程序 用图灵模型来计算 控 制 器 工作 带带 B x x x x B 读写头扫描到标记x， 则继续往右走 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头 程序 用图灵模型来计算 控 制 器 工作 带带 B x x x x B 读写头扫描到标记x， 则继续往右走 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头 程序 用图灵模型来计算 控 制 器 工作 带带 B x x x x B 读写头扫描到标记x， 则继续往右走 (q0, a a R q0) (q0, b x L q1) (q1, x x L q1) (q1, a x R q2) (q1, B B H qN) (q2, x x R q2) 读写头 程序 用图灵模型来计算 控 制 器 工作 带带 B x x x x B 读写头扫描到空白符B， 说明符号b已处理完毕， 则把状态改为q3， 并使读写头往左走 (q2, b x L q1) (q2, B B L q3) (q3, x x L q3) (q3, a a H qN) (q3, B B H q4) 读写头 程序 用图灵模型来计算 控 制 器 工作 带带 B x x x x B 读写头扫描到空白符B， 说明符号b已处理完毕， 则把状态改为q3， 并使读写头往左走 (q2, b x L q1) (q2, B B L q3) (q3, x x L q3) (q3, a a H qN) (q3, B B H q4) 读写头 程序 用图灵模型来计算 控 制 器 工作 带带 B x x x x B 读写头扫描到标记x， 则继续往左走 (q2, b x L q1) (q2, B B L q3) (q3, x x L q3) (q3, a a H qN) (q3, B B H q4) 读写头 程序 用图灵模型来计算 控 制 器 工作 带带 B x x x x B 读写头扫描到标记x， 则继续往左走 (q2, b x L q1) (q2, B B L q3) (q3, x x L q3) (q3, a a H qN) (q3, B B H q4) 读写头 程序 用图灵模型来计算 控 制 器 工作 带带 B x x x x B 读写头扫描到标记x， 则继续往左走 (q2, b x L q1) (q2, B B L q3) (q3, x x L q3) (q3, a a H qN) (q3, B B H q4) 读写头 程序 用图灵模型来计算 控 制 器 工作 带带 B x x x x B 读写头扫描到空白符B， 说明符号a和b已成对标记， 转移到状态q4， 达到接受状态。 (q2, b x L q1) (q2, B B L q3) (q3, x x L q3) (q3, a a H qN) (q3, B B H q4) 图灵机反映的是一种具有能行性的用数学 方法精确定义的计算模型 而现代计算机正是这种模型的具体实现 科学与学科 科学是关于自然、社会和思维的发展与变 化规律的知识体系，是由人类在生产活动和 社会活动中产生和发展的，是人类实践经验 的结晶。 科学是逐步发展起来的 科学的发展需要某种特殊的方法 科学在不断超越中永无止境地发展 科学与学科 学科本身具有二重含义： 指知识体系或学术分类，含义较广； 指为培养人才而设立的教学科目。 科学与学科 科学研究是以问题为基础的，学科是在科 学发展中不断分化和整合而形成和发展的， 是科学研究发展成熟的产物。 科学研究发展成熟而成为一个独立学科的 标志是：必须有独立的研究内容、成熟的研 究方法、规范的学科体制。 计算机学科的定义 计算机学科是对描述和变换信息的算法过 程，包括对其理论、分析、设计、效率、实 现和应用等进行的系统研究。它来源于对算 法理论、数理逻辑、计算模型、自动计算机 器的研究，并与存储式电子计算机的发明一 起形成于20世纪40年代初期。 计算机学科的特点 计算机学科包括科学和技术两个方面。 科学侧重于研究现象、揭示规律； 技术则侧重于研制计算机、研究使用计算机进行 信息处理的方法与技术手段。 科学是技术的依据，技术是科学的体现。 二者高度融合是计算机科学与技术学科的突出特 点。 计算机学科是一门科学性与工程性并重的学科， 表现为理论和实践紧密结合的特征。 计算机学科的特点 科学：关于自然、社会和思维的发展与变 化规律的知识体系，其核心是发现。 技术：根据实践经验和科学原理而发展形 成的各种工艺操作方法、技能和技巧，其核 心是发明。 工程：将科学原理应用到生产实践中，是 某种形式的科学应用，其核心是建造 什么是科学问题 科学问题是指一定时代的科学认识主体，在已 完成的科学知识和科学实践的基础上，提出的需 要解决且有可能解决的问题，它包含一定的求解 目标和应答域，但尚无确定的答案。科学问题具 有如下主要特征： （1）时代性 （2）混沌性 （3）可解决性 （4）可变异性 （5）可待解性 科学问题的提出和解决是任何一个学科持续发展 的动力。 计算机学科的科学问题 1. 计算的平台与环境问题 核心：计算问题的能行性 2. 计算过程的能行操作与效率问题 核心：算法及算法分析 3. 计算的正确性问题 核心：各种语言的语义 上述基本问题普遍出现在学科的各个分支 学科和研究方向之中，是学科研究与发展中经 常面对而又必须解决的科学问题。 计算机学科的经典问题 经典问题是指那些反映学科某一方面 内在规律和本质内容的典型问题。 经典问题往往以深入浅出的形式表达 学科深奥的科学规律和本质内容，在学 科研究中常常用来辅助说明思想、原理 、方法和技术。 1968年，计算机科学家狄杰 斯特拉首次提出了GOTO语句 是有害的。 1974年，计算机科学家克努 斯发表论文带有GOTO语句 的结构化程序设计作了较全 面而公正的论述。 面条程序示例 GOTO语句问题与程序设计方法学 GOTO语句问题与程序设计方法学 滥用GOTO语句是有害的，完全禁止 也是不明智的，在不破坏程序良好结构的 前提下，有限制地使用GOTO语句，有可 能使程序更清晰、效率更高。 关于“GOTO语句”问题的争论直接 导致了一个新的学科分支领域程序 设计方法学的产生，它是一个对程序的 性质及其设计的理论和方法进行研究的 学科。 哥尼斯堡七桥问题与图论 东东区 北区 岛岛区 南区 C A D B 哥尼斯堡七桥问题：是否能 在一次步行中穿越全部的七 座桥后回到起点，且每座桥 只经过一次。 哥尼斯堡七桥问题与图论 欧拉回路的判定规则： （1）如果通奇数桥的地方多于两个，则不 存在欧拉回路； （2）如果只有两个地方通奇数桥，可以从 这两个地方之一出发，找到欧拉回路； （3）如果没有一个地方是通奇数桥的，则 无论从哪里出发，都能找到欧拉回路。 C A D B 哈密顿回路问题 哈密顿回路：要 求从一个城市出 发，经过每个城 市恰好一次，然 后回到出发城市 。 19 8 3 14 1 20 2 13 15 4 5 67 9 10 11 12 16 17 18 哈密顿回路问题 美国图论数学家奥勒在1960年给出了一个图是哈 密尔顿图的充分条件：对于顶点个数大于2的图，如 果图中任意两点度的和大于或等于顶点总数，那这 个图一定是哈密尔顿图。 寻找哈密顿路径是一个典型的NP-完全问题。后 来人们也证明了，找一条哈密顿路的近似比为常数 的近似算法也是NP-完全的。 从图中的任意一点出发，路途中经过图中每一个 结点当且仅当一次，则成为哈密顿回路。 哲学家共餐问题与进程同步 哲学家的生活进程可表示为： （1）思考问题； （2）饿了停止思考，左手拿起一只筷 子（如果左侧哲学家已持有它，则等 待）； （3）右手拿起一只筷子（如果右侧哲 学家已持有它，则等待）； （4）进餐； （5）放下左手筷子； （6）放下右手筷子； （7）重新回到状态（1）思考问题； 哲学家共餐问题与进程同步 程序并发执行时进程同步的两个关键问题死锁和饥饿 ： （1）按哲学家的生活进程，当所有的哲学家都同时拿起左 手筷子时，则所有哲学家都将拿不到右手筷子，并处于等 待状态，那么，哲学家都将无法进餐，最终饿死。 （2）将哲学家的生活进程修改为当拿不到右手筷子时，就 放下左手筷子。但是，可能在一个瞬间，所有的哲学家都 同时拿起左手筷子，则自然拿不到右手筷子，于是都同时 放下左手筷子，等一会，又同时拿起左手筷子，如此重复 下去，则所有的哲学家都将无法进餐。 汉诺塔问题与计算复杂性 汉诺塔问题：在世界刚被创建的时候有一座钻石 宝塔（塔A），其上有64个金碟。所有碟子按从 大到小的次序从塔底堆放至塔顶。紧挨着这座塔 有另外两个钻石宝塔（塔B和塔C）。从世界创 始之日起，婆罗门的牧师们就一直在试图把塔A 上的碟子移动到塔C上去，其间借助于塔B的帮 助。每次只能移动一个碟子，任何时候都不能把 一个碟子放在比它小的碟子上面。当牧师们完成 任务时，世界末日也就到了。 汉诺塔问题与计算复杂性 B AB C ABC A A CA BC (a ) (b ) (c ) (d ) 汉诺塔问题与计算复杂性 n个碟子的汉诺汉诺 塔问题问题 需要移动动的碟子数是n-1个 碟子的汉诺汉诺 塔问题问题 需要移动动的碟子数的2倍再加1 。因此： 用C语言对该问题的求解算法进行描述 hanoi(int n,char left,char middle,char right) 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个碟子的汉诺塔问题，需要移动的碟子 数为： 2641 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问题与组合爆炸 8 ab dc 2 35 7 1 否 18 adcba