认识计算机学科.ppt
《认识计算机学科.ppt》由会员分享,可在线阅读,更多相关《认识计算机学科.ppt(59页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、L/O/G/O 认识计认识计算机算机算机算机学学学学科科科科内容概要内容概要内容概要内容概要1 12 2计算机学科的根本问题计算机学科的根本问题计算机学科的根本问题计算机学科的根本问题计算机学科的科学问题计算机学科的科学问题计算机学科的科学问题计算机学科的科学问题计算机学科的根本问题计算机学科的根本问题计算机学科的根本问题计算机学科的根本问题什么是计算机学科什么是计算机学科什么是计算机学科什么是计算机学科什么是计算 计算机学科的定义什么是计算什么是计算什么是计算什么是计算图灵(Alan Turing):所为计算就是计算者(人或机器)对一条可以无限延长的工作带上的符号串执行命令,一步一步地改变工
2、作带上的符号串,经过有限步骤,最后得到一个满足预先规定的符号串的变换过程。图灵的研究成果是:可计算性=图灵可计算性图灵机:Turing machine finite state auto machinecomputing构造一个识别符号串anbn(n1)的图灵机基本思想:使读写头往返移动,每往返移动一次,就成对地对输入符号串左端的一个a和右端的一个b匹配并做标记x。如果恰好把输入符号串的所有符号都做了标记,说明左端的符号a和右端的符号b的个数相等;否则,说明左端的符号a和右端的符号b的个数不相等,或者符号a和b交替出现。用图灵模型来计算用图灵模型来计算用图灵模型来计算用图灵模型来计算(q0,a
3、 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)(
4、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 q
5、0)(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)读写头读写头程序程序用图灵模型来计算用图灵
6、模型来计算用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带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,并使读写头往右走,并使
7、读写头往右走,转移到状态转移到状态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
8、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 读写头读写头
9、程序程序用图灵模型来计算用图灵模型来计算用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带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
10、,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)读写头读写头程序程序用图灵模型来计算
11、用图灵模型来计算用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带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 q
12、2)(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已处理完毕
13、,已处理完毕,则把状态改为则把状态改为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
14、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)(
15、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已成对标记,已成对标记,转移到状态转
16、移到状态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)图灵机反映的是一种具有能行性的用数学方法精确定义的计算模型而现代计算机正是这种模型的具体实现科学与学科科学与学科科学与学科科学与学科科学是关于自然、社会和思维的发展与变化规律的知识体系,是由人类在生产活动和社会活动中产生和发展的,是人类实践经验的结晶。科学是逐步发展起来的科学的发展需要某种特殊的方法科学在不断超越中永无止境地发展科学与学科科学与学科科学与学科科学与学科学科本身具有二重含义:指知识体系或学术分类,含义较广;指为
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 认识 计算机 学科
限制150内