资源描述：
《计算机学科概论 第02章 认识计算机学科课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章认识计算机学科2.1什么是计算机学科2.2计算机学科的科学问题2.3计算机学科的经典问题2.4计算机学科的知识体系从字源上考察：计：从言从十，有数数或计数的含义；算：从竹从具，指计算工具。《现代汉语词典》对计算的定义：根据已知数通过数学方法求得未知数。什么是计算直观的计算：数的加减乘除；函数的微分、积分；微分方程的求解；定理的证明推导等等。计算的实质：从一个符号串f（输入）得出另一个符号串g（输出）。数学概念→普适概念什么是计算计算的例子从符号串“12+3”变换成符号串“15”——加法计算符号串“x2”变换成符号串“2x”—
2、—微分；f表示一组公理和推导规则，g是一个定理，那么从f到g的一系列变换——定理g的证明；符号串f代表一个英文句子，符号串g为含义相同的中文句子，那么从f到g的变换——英文翻译成中文；这些变换有什么共同点？为什么他们都叫做计算？图灵与巨人计算机图灵模型有限状态控制器工作带……一条无限长的工作带：工作带上的每个单元可以存放一个符号；所有允许出现的符号属于一个预先规定好的字母表。图灵模型有限状态控制器工作带……一个读写头：读写头可以左移一个单元、右移一个单元或者保持不动。图灵模型有限状态控制器工作带……一个控制器：控制器在每个时刻处于
3、一定的状态，当读写头从工作带上读出一个符号后，控制器就根据这个符号和当时的机器状态，指挥读写头进行读写或者移动，并决定是否改变机器状态。计算与可计算所谓计算就是计算者（人或机器）对一条可以无限延长的工作带上的符号串执行指令，一步一步地改变工作带上的符号串，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。什么样的任务才是可计算的任务？这是计算机科学必须要回答的一个最基本的问题。这是关系到计算机能做什么、不能做什么的根本问题。类比：什么样的衣服才是洗衣机可洗的？构造一个识别符号串ω＝anbn（n≥1）的图灵机基本思想：使读写
4、头往返移动，每往返移动一次，就成对地对输入符号串ω左端的一个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指令机器状态当前读到的字符当前写入的字符读写头的动作R:右移L:左移H
5、:不动下一机器状态读写头(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
6、,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)读写头程序
7、用图灵模型来计算控制器工作带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读写头扫描到标记
8、x，则继续往右走(q2,bxLq1)(q2,BBLq3)(q3,xxLq3)(q3,aaHqN)(q3,BBHq4)读写头程序用图灵模型来计算控制器工作带BaxxbB若读写头扫描到符号b，则把b改为标记x，并使读写头往左走，转移到状态q1读写头程序
