第2章 程序算法与图灵机模型
- 格式:ppt
- 大小:674.50 KB
- 文档页数:34
理解图灵机模型、计算机科学概念内涵,懂得存储程序及计算机的结构⾸先,图灵机模型是由英国数学家图灵提出的,图灵机模型理论是计算学科最核⼼的理论之⼀,它的出现为计算机设计指明了⽅向,在今天的学习中图灵机模型发挥着不可或缺的⽤处,是我们算法分析和程序语⾔设计的基础理论。
下⾯是它的定义:所谓的图灵机就是指⼀个抽象的机器,它有⼀条⽆限长的纸带,纸带分成了⼀个⼀个的⼩⽅格,每个⽅格有不同的颜⾊。
有⼀个机器头在纸带上移来移去。
机器头有⼀组内部状态,还有⼀些固定的程序。
在每个时刻,机器头都要从当前纸带上读⼊⼀个⽅格信息,然后结合⾃⼰的内部状态查找程序表,根据程序输出信息到纸带⽅格上,并转换⾃⼰的内部状态,然后进⾏移动。
然后,计算机科学概念的内涵较为⼴泛,计算机科学是⼀门包含各种各样与计算和信息处理相关主题的系统学科,可以肯定的是它是⼀门学科,⽽不仅仅是⼀门技术或者是⼀种⼯具。
计算机科学的基本思路涵盖从理论研究、模型抽象到⼯程设计三个⽅⾯。
有时公众会误以为计算机科学就是解决计算机问题的事业(⽐如信息技术),或者只是与使⽤计算机的经验有关,如玩游戏、上⽹或者⽂字处理。
其实计算机科学所关注的,不仅仅是去理解实现类似游戏、浏览器这些软件的程序的性质,更要通过现有的知识创造新的程序或者改进已有的程序,这才是我们计算机科学应该做的事情。
下⾯是计算机中储存程序的原理:“存储程序”原理,是将根据特定问题编写的程序存放在计算机存储器中,然后按存储器中的存储程序的⾸地址执⾏程序的第⼀条指令,以后就按照该程序的规定顺序执⾏其他指令,直⾄程序结束执⾏。
存储程序和程序控制原理的要点是,程序输⼊到计算机中,存储在内存储器中(存储原理),在运⾏时,控制器按地址顺序取出存放在内存储器中的指令(按地址顺序访问指令),然后分析指令,执⾏指令的功能,遇到转移指令时,则转移到转移地址,再按地址顺序访问指令(程序控制)。
计算机的结构主要分为五个部分:控制器,运算器,存储器,输⼊设备,输出设备。
计算机计算模型中的图灵机从计算机计算模型的角度来看,图灵机被认为是一种通用的计算模型,也是计算机科学研究的重要基础之一。
在本文中,我们将深入探讨图灵机的内部结构、运作原理,以及在计算机科学与人工智能研究中的应用。
一、图灵机的定义与内部结构图灵机是一种最简单、最有代表性的计算模型。
其定义由英国数学家阿兰·图灵提出,目的是为了探究哪些问题可以被自动机器解决,哪些问题不可以。
从宏观角度看,图灵机可以被视为一个运算器。
它包括一个无限长度的纸带,上面按照一定规律印有各种符号,一个读写头,可以在纸带上不停移动,并读取或写入符号,以及一个确定的有限自动机,遵循一定的规则对符号进行操作,并改变自动机的状态。
从微观角度看,图灵机可以被视为一个五元组(M, S, T, s0, F)。
其中,M表示状态集合,S表示符号集合,T表示转移函数,s0表示起始状态,F表示接受状态。
具体而言,自动机根据读取到的符号,通过转移函数来执行状态转移,并可以改写纸带上的符号。
当自动机的状态转换到F中的任意一个状态时,其判定为输入串被接受。
二、图灵机的运作原理图灵机的运作可以被大致分为两个阶段:读写头扫描纸带,自动机执行状态转移。
在程序开始运行时,自动机根据起始状态s0开始,读写头扫描到的符号会被送至转移函数T中计算状态转移,根据T中的定义,自动机可能完成以下四个操作之一:- 将读写头向左或右移动一格- 改写当前符号- 将自动机状态从M中的一种变为另一种- 停机在一个图灵机的运行中,自动机状态的变化不是唯一的。
事实上,任何一个有限自动机都可看作某个图灵机的子集,只是它转换后的操作相对简单罢了。
三、图灵机在计算机科学中的应用图灵机在计算机科学中的应用主要有以下两个方面:1.图灵完备性一个计算模型被称为图灵完备,当且仅当它可以在所有计算上都与图灵机等价。
因为图灵机是最简单、最有代表性的计算模型之一,许多计算机科学研究中的问题可以被转换成图灵机问题。
第1章单元测试l、世界上第一代计算机被叫做:答案:电子管计算机2、第一次数学危机源自对哪个问题的讨论答案:有些量无法用整数表达3、第二次数学危机源自对哪个问题的讨论?答案:微积分中的无穷小4、第三次数学危机源自对哪个问题的讨论?答案:集合定义的完备性5、图灵机模型的提出者是?答案:图灵6、十进制123对应的二进制表示是?答案:正确7、如下哪个是电子管的特点?答案:容易损坏,寿命短8、如下哪个是晶体管的特点?答案:主要原料是硅9、如下哪个是集成电路的特点?答案:体积小10、如下哪个是当前量子计算机的特点?答案:能进行并行运算11、导致CPU不能造得更大的主要原因是?答案:散热原因12、如下哪个部分不是冯诺伊曼计算机的组成部分?答案:读写头13、如下那种存储器的处理速度更快?答案:寄存器14、下列哪个关于CPU旨令集的说法是错误的?答案:指令集包含的指令数目越多,CPUi运算速度越快15、下列哪个关于程序执行的说法是错误的?答案:用高级语言编写的程序,不经过编译也能够运行第2章单元测试l、答题说明:请大冢到指定答题地址答题,提交代码并通过测试后,会得到通过码的下载地址,将文件下载下来用记事本打开即得到通过码,将通过码对应的选项选出即可。
题目1实现冒泡排序(程序抄写题)答题地址:<alianxi/18/</a> 请完全按照如下的程序书写代码,并在书写的过程中体会优秀的代码风格:答案:5ef83 68afl 63 74cabef8e5ae3ee3 9c43 74a3 6a4c52b4b560bc8fc 1Oca47 a66052、答题说明:请大冢到指定答题地址答题,提交代码并通过测试后,会得到通过码的下载地址,将文件下载下来用记事本打开即得到通过码,将通过码对应的选项选出即可。
题目2整数的个数答题地址:<alianxi/22/</a>答案:5ef8368afl 63 74cabef8e5ae3ee39c43 74a36a4c52b4b560bc8fc 1Oca47a6605第3章单元测试l、答题说明:请大冢到指定答题地址答题,提交代码并通过测试后,会得到通过码的下载地址,将文件下载下来用记事本打开即得到通过码,将通过码对应的选项选出即可。