《大学计算机基础》课件+第1章――自学完整版(2014_10_9)【OK】

大学计算机基础—第1章自学版北京航空航天大学计算机学院2课程目录第6章求解显示，交互（2学时）求解效率，优化和限制（4学时）第5章求解的工程思维，规范（2学时）第7章问题的描述，数据及数据结构（6学时）第3章计算机与计算思维（4学时）第1章第2章问题的抽象与建模（4学时）问题的求解，算法及实现（4学时）第4章3第1章计算机与计算思维1.3为什么计算机能够计算1.6计算机模型与计算思维（自学）1.2理论思维，实验思维和计算思维1.1从图灵测试看思维1.4计算机的理论模型与物理实现1.5计算思维主要思维方法的案例4本课件说明说明：本课件为《大学计算机基础》第1章中关于计算机基础知识的详细课件供同学们自学和参考51.6计算机模型与计算思维1.6.1图灵机模型1.6.2现代计算机模型1.6.3计算机之逻辑基础1.6.4信息在计算机中的表示1.6.5现代计算机系统1.6.1图灵机模型计算机之所以能够计算，或者具备智能，其思维类比于人脑：语言单元—神经元单元—数字及其编码语言的关系—神经元的链接—数据结构、数据关系思维—神经元网络的自动链接—数据的模型和算法感知和动作—肢体和器官—计算机的输入和输出我们如果能有一台机器，可以存储，可以运算，可以输入输出，那么，就可以具备计算的能力我们来看看这个抽象的过程-图灵机模型6图灵其人图灵其人阿兰·麦席森·图灵（AlanMathisonTuring,1912~1954)，出生于英国伦敦，19岁入剑桥皇家学院，22岁当选为皇家学会会员英国数学家、逻辑学家、密码学家，计算机逻辑的奠基者，提出了“图灵机（TuringMachine）”和“图灵测试”等重要概念1937年，提出了图灵机模型，这是图灵对人类的最大贡献1950年，发表了划时代的文章“机器能思考吗?”,成为了人工智能的开山之作被誉为“计算机科学之父”和“人工智能之父”计算机界于1966年设立了最高荣誉奖：ACM图灵奖7图灵机缘起什么是计算？一个问题：1900年，德国数学家希尔伯特提出“23个数学难题”中，逻辑的完备性问题，即是否所有数学问题原则上都可解一篇文章：1937年，图灵发表“论可计算数及其在判定问题中的应用”(OnComputableNumbersWithanApplicationtotheEntscheidungsProblem)图灵给“可计算性”下了一个严格的数学定义，并提出著名的“图灵机”的设想——可解的问题是能够用图灵机的自动机理论模型表达的问题一个大神：图灵，1912-1954一个模型：可计算模型8图灵机模型图灵的基本思想是用机器来模拟人们用纸笔进行数学计算的过程（１）根据计算需求在纸上写下相应的公式或符号；（2）根据眼睛看到的符号，在脑中思考相应的计算方法；（3）在纸上写上或擦除某个符号；（4）把视线从纸的一个位置移动到另一个位置；（5）转到第（2）步，重复以上步骤，直到认为计算停止为止在每个阶段，人要决定下一步的动作，依赖于（a）人当前所关注的纸上某个位置的符号（b）人当前思维的状态为了模拟人的这种数学计算过程，图灵构造出一台假想的机器——图灵机9图灵机模型的组成图灵机模型由3个部件组成无穷纸带（符号集合）两端可无限延长，纸带被分为一系列均匀的方格，每个方格中可填写一个来自有限字母表的符号读写头（读、改写、左移、右移）有穷控制器（有限状态机）拥有预定的有限个互不相同的状态，并能根据输入改变自身的状态；可控制读写头工作10FinitecontrollerX1BB...X2XnXi带（tape）单元格（cell）带符（tapesymbol）有穷控制器读写头图灵机模型是如何抽象的？图灵机模型是如何抽象的？将所有具体的输入、输出、转换细节抛弃，定义一个五元组图灵机是一个五元组（K，∑，δ，s，H），其中：K是有穷（有限）个状态的集合；∑是字母表，即符号的集合；s∈K，是初始状态；H∈K，是停机状态的集合，当控制器内部状态为停机状态时图灵机结束计算；δ是转移函数，即控制器的规则集合。11图灵机的工作原理：计算“x+1”的图灵机图灵机的工作原理图灵机的计算：由控制器控制执行的一系列动作图灵机从纸带上的某个起始点出发，动作完全由初始状态和指令组决定其计算结果是从图灵机停止时纸带上的信息得到的12【例1】计算“x+1”的图灵机目标：利用二进制设计一个专门计算“x+1”的图灵机，要求计算完成时，读写头回归原位x由0、1串组成，“*”为x的分隔符、界定符（当纸带上有多个数时，用*将它们隔开）计算“x+1”的图灵机—首先进行抽象确定图灵机五元组的内容状态集合K：{start，add，carry，noncarry，overflow，return，halt}字母表∑：{0，1，*}初始状态s：start停机状态集合H：{halt}规则集合δ规则：如果A那么B，形式化表示为：A→B13图灵机控制器的规则：（控制器当前状态，读写头当前位置的符号）→(读写头写入新符号，读写头移动动作指示，控制器新状态)规则集合δ14123456、789步骤“5＋1”的计算过程（1）初始状态15第1步完成后状态第1步：“5＋1”的计算过程（2）16第3步完成后状态第2步：加1，新符号变成0第2步完成后状态加上进位，新符号变成1第3步：“5＋1”的计算过程（3）17第5步完成后状态第4步完成后状态**110return第4步：第5步：……“5＋1”的计算过程（4）18第9步：停机（停止计算）**110halt运算结果第8步完成后状态停机状态课后练习给出计算“7+1”的图灵机运算过程，列出每一步的指令和指令完成后的状态19通用图灵机图灵机本质是进行字符串的处理图灵机输入是一个字符串图灵机输出也是一个字符串如果将图灵机的有限个内部状态与读写头的有限个动作用字符串表示那么每条转换规则也可以用一个字符串表示（当前状态，当前符号，新符号，动作，新状态）图灵机可以由一个较长字符串完全表示——通用图灵机满足这样一个有穷规则有限状态的可以对字符串处理的机器，就是计算机；而可描述成这样的科学问题，就是可以计算的；而其具体实现，则是冯·诺伊曼机。20通用图灵机实现“5+1”计算（1）【例2】通用图灵机实现“5+1”计算21编码方案通用图灵机实现“5+1”计算（2）223带通用图灵机M图灵机输入字符串：00100001000000010010（对应*101*）图灵机的所有规则，每个规则20位字符（当前状态，当前符号，新符号，动作，新状态）当前状态：0101对应start状态利用编码描述的规则：01010010001000110110通用图灵机实现计算的过程23开始扫描第三条带获得当前状态S扫描第一条带获得当前符号C扫描第二条带查找规则串（Si，Ci，Cn，A，Sn）Si==SCi==C（Si，Ci，A，Sn）即转换规则（当前状态，当前符号，新符号，动作，新状态）否Si==结束状态？是否S=SnC=Cn根据A对第一条带执行相应动作是END发现了什么？——计算过程与具体的编码方案和规则都不相关！意味着什么？——程序可以重复执行图灵机的思想图灵机的思想图灵机不是具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算装置，用来计算所有能想象得到的可计算函数。基本思想是用机器来模拟人们用纸笔进行数学运算的过程24…10001110110011010110001…0110101由“程序”控制输入“转换”为输出输入输出程序通用机器所谓计算就是计算者（人或机器）对一条两端可无限延长的纸带上的一串0或1，执行指令一步一步地改变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程图灵机的计算：由控制器控制执行的一系列动作图灵机的思想（Cont.）图灵机的思想是数据、指令、程序及程序/指令自动执行的基本思想25输入被制成一串0和1的纸带，送入机器中----数据。如00010000100011…机器可对输入纸带执行的基本动作包括：“翻转0为1”，或“翻转1为0”,“左移一位”,“右移一位”，“停止”对基本动作的控制----指令，机器是按照指令的控制选择执行哪一个动作，指令也可以用0和1来表示：01表示“翻转0为1”(当输入为1时不变)，10表示“翻转1为0”(当输入0时不变),11表示“前移一位”,00表示“停止”输入如何变为输出的控制可以用指令编写一个程序来完成,如：011110110111011100…机器能够读取程序，按程序中的指令顺序读取指令，读一条指令执行一条指令。由此实现自动计算图灵机蕴含的计算思想图灵机蕴含的计算思想（1）程序也是数据“x+1”图灵机功能是固定的，相当于一个程序通用图灵机的功能根据编码方案（主要是规则集合）的不同而变化存储程序和程序控制M图灵机进一步展示了程序和其输入可以先保存到存储带上，M就按程序一步一步运行直到给出结果，结果也保存在存储带上（2）通用图灵机的所有规则构成指令集指令指示了操作的对象（当前符号）指令指示了待实施的操作（改写符号，移动读写头）28图灵机蕴含的计算思想（Cont.）（3）通用图灵机模型是计算机的计算能力的极限因为，根据丘奇-图灵论题（Church-Turingthesis）：不能用图灵机完成的计算任务是不可计算的邱奇-图灵论题认为，如果某种方法（算法）可进行运算，那么该运算也可被图灵机执行（也可被递归定义的函数或λ函数执行）（4）计算机系统应该有:存储器（相当于存储带）中央处理器（控制器及其状态），并且其字母表可以仅有0和1两个符号为了能将数据保存到存储器并将计算结果从存储器送出来展示给用户，计算机系统还应该有输入设备和输出设备如键盘、鼠标、显示器和打印机等29冯·诺依曼机对图灵机的实现301944年，冯·诺依曼参与ENIAC研究小组1945年，在ENIAC基础上，冯·诺依曼等人提出了EDVAC设计方案,计算机的组成包括：运算器、控制器、存储器、输入和输出设备311.6.2现代计算机模型1.6.2.1冯·诺伊曼计算机的基本思想1.6.2.2冯·诺伊曼计算机的组成及其特点1.6.2.3冯·诺伊曼计算机的局限性1.6.2.4冯·诺伊曼计算机的改进---探索新的计算模型自学重点32需要思考的若干问题请带着以下问题学习本节内容（1）冯·诺依曼机的基本思想是什么？冯·诺依曼机有哪些特点？（2）冯·诺依曼机包括哪五大部件？其作用分别是什么？为什么计算机能够像人一样进行加减乘除各种算术运算，甚至能够进行各种逻辑运算？为什么计算机能够自动工作？（3）以存储器为中心的结构与以运算器为中心的结构有何不同？（4）冯·诺伊曼计算机的局限性表现在哪几个方面？这几十年以来，人们是如何努力改进冯·诺伊曼计算机，探索新的计算模型的？331.6.2.1冯·诺伊曼计算机的基本思想冯·诺伊曼其人约翰·冯·诺依曼（JohnVonNeuman，1903－1957）美藉匈牙利人，20世纪最重要的数学家之一，在现代计算机、博弈论和核武器等诸多领域内有杰出建树的最伟大的科学全才之一“电子计算机之父”，“博弈论之父”布达佩斯数学博士。先后执教于柏林大学和汉堡大学。历任普林斯顿大学、普林斯顿高级研究所教授，美国数学会主席，美国原子能委员会会员。美国全国科学院院士34冯·诺伊曼思想的提出关于ENIAC1946年2月14日，世界第二台电子计算机ENIAC（ElectronicNumericalIntegratorAndCalculator，电子数字积分计算机）（音译埃尼阿克）在美国宾夕法尼亚大学诞生研制小组：埃克特、约翰·莫克利、赫尔曼·戈尔斯坦、亚瑟·博克斯17468只电子管，每秒5000次加法运算或400次乘法运算，运算速度是继电器计算机的1000倍并具有按事先编好的程序自动执行算术运算、逻辑运算和存储数据的功能体重30吨，占地