《刘卫国全套配套课件大基第4版第1章计算与计算思维》由会员分享，可在线阅读，更多相关《刘卫国全套配套课件大基第4版第1章计算与计算思维（43页珍藏版）》请在金锄头文库上搜索。
1、第1章 计算与计算思维, 计算是指数学运算，即数据在运算符的作用下按照一定的计算规则进行的数据运算。 计算是指较复杂的运算。 当待求解的问题变得复杂而用传统数学方法无法求出精确解时，这时只能利用一种先进的计算工具来取代人工计算，这种计算工具就是电子计算机。,1.1 计算及计算工具的发展历程,1.1.1 什么是计算, 计算是指符号变换。 可以更广义地理解计算，即计算是一种符号变换，即从一个符号串按照一定的规则变换成另一个符号串的过程。,计算机符号变换所得到的输出结果，除了取决于输入数据外，还取决于程序，即程序不同，完成的数据处理方法不同，得到的结果也不同。,求最大值,求和,1.1.2 早期的计算
2、工具,远古的人们用石头、刻痕、手指或绳结来计数，本身也包含了计算的概念，石头、手指或绳结都是古人用过的“计算机”。 后来，许多国家的人们用“筹码”来改进计算工具，其中要数中国的算筹最有名气。商周时代问世的算筹，实际上是一种竹制、木制或骨制的小棍。古人在地面或盘子里反复摆弄这些小棍，通过移动来进行计算，从此出现了“运筹”这个词，运筹就是计算。,欧洲人发明的算筹与中国的算筹不尽相同，欧洲的算筹是根据“格子乘法”的原理制成。1617年，英国数学家约翰纳皮尔（John Napier）把格子乘法表中可能出现的结果，印刻在一些狭长条的算筹上，利用算筹的摆放来进行乘、除或其他运算。纳皮尔算筹在很长一段时间里
3、，是欧洲人主要的计算工具。,（a） （b） （c） “格子乘法”原理,算筹在使用中，一旦遇到复杂运算常弄得繁杂混乱，让人感到不便，于是中国又发明了一种新式的“计算机”算盘。先后都出现过不同形式的算盘，只有中国的珠算盘一直沿用至今。它利用进位制记数，通过拨动算珠进行运算：上珠每珠当五，下珠每珠当一，每一档可当作一个数位。打算盘必须记住一套口诀，口诀相当于算盘的“软件”。算盘本身还可以存储数字，使用起来的确很方便，它帮助中国古代数学家取得了不少重大的科技成果，在人类计算工具史上具有重要的地位。,18世纪末，以发明蒸汽机闻名于世的瓦特，成功地制出了第一把名副其实的计算尺。瓦特原来就是一位仪表匠，他的
4、蒸汽机工厂投产后，需要迅速计算蒸汽机的功率和气缸体积。瓦特设计的计算尺，在尺座上多了一个滑标，用来“存储”计算的中间结果，这种滑标很长时间一直被后人所沿用。1850年以后，对数计算尺迅速发展，成了工程师们必不可少的随身携带的“计算机”，直到20世纪五、六十年代，它仍然是代表工科大学生身份的一种标志。,1.1.3 电子计算机的产生,1机械计算机 从17世纪到19世纪中期长达200多年的时间里，一批杰出的科学家相继进行了机械计算机的研制，其中的代表人物有帕斯卡（Blaise Pascal）、莱布尼茨（Gottfried Leibniz）和巴贝奇（Charles Babbage）。,帕斯卡,莱布尼茨
5、,巴贝奇,1642年，法国数学家帕斯卡采用与钟表类似的齿轮传动装置，制成了最早的十进制加法机。 德国著名的数学家莱布尼兹于1673年发明了乘法机，这是第一台可以运行完整的四则运算的计算机。,十进制加法机,莱布尼茨乘法机,英国数学家巴贝奇在1822年发明差分机，专门用于航海和天文计算。这是最早采用寄存器（齿轮式装置）来存储数据的计算机，体现了早期程序设计思想的萌芽。1834年，巴贝奇设计了一种程序控制的通用分析机。,差分机,通用分析机,2机电计算机 1938年，德国科学家祖思（Konrad Zuse）制造出一台纯机械结构的Z-1计算机，这是第一台采用二进制的计算机。 1944年，美国科学家艾肯（
6、Howard Aiken）在IBM公司（International Business Machine）的支持下，研制成功机电计算机MARK-。,Z-1计算机,MARK-I,3.萌芽期的电子计算机 1939年，阿塔纳索夫（John V. Atanasoff）和他的学生贝瑞（Clifford E. Berry）还设计并试制数字电子计算机的样机“ABC计算机”（Atanasoff- Berry Computer），但未能完工。ABC计算机是计算机发展史上的一个里程碑，有些科学史学家认为，如果ABC 机当时能正式制造出来，那将是世界上第一台电子数字计算机。,4电子计算机的诞生 1946年 2月15日是
7、计算机发展史上值得纪念的一个日子。这一天在美国宾夕法尼亚大学莫尔学院举行了人类历史上第一台通用数字电子计算机的揭幕典礼。这台机器名为“电子数字积分计算机”（Electronic Numerical Integrator and Calculator，ENIAC）是世界上第一台真正意义上的通用电子数字计算机。它的问世，标志着人类计算工具发生了历史性的变革，人类从此进入了电子计算机的新时代。,世界上第一台电子计算机ENIAC,1.2 计算的自动化,1.2.1 图灵与图灵机 1936年，图灵在其“论可计算数及其在判断问题中的应用”一文中，构造出一台完全属于想象中的“计算机”，数学家们把它称为图灵机（
8、Turing Machine）。图灵机是一种抽象的计算模型，不是一种具体的机器，但是这种模型可制造一种十分简单但运算能力极强的计算装置，用来计算所有能想象得到的可计算函数。,1图灵机的组成 图灵的基本思想是用虚拟的机器来模拟人们用笔和纸进行数学运算的过程，他把这样的过程看作下列两种简单的动作：一是在纸上写上或擦除某个符号；二是把注意力从纸的一个位置移动到另一个位置。在每个阶段，人要决定下一步的动作，依赖于此人当前所关注的纸上某个位置的符号和此人当前思维的状态。,2图灵机的工作过程 图灵机在执行一个任务时，将输入写在一条无限长的纸带上，读写头从指定的开始状态出发，读出纸带方格的符号，根据控制规则
9、表一步一步地动作，直到进入某个停机状态而停机，这时纸带上的内容就是输出结果。只要改变图灵机的控制规则表，它就可以完成任何其他的任务。,下面以计算x+1的图灵机为例，分析图灵机的工作过程。图灵机的转换规则如表所示。, 将原始数据x以二进制的形式写在无限长的纸带上，并假定读写头开始位于右边第一个方格，如图1-9（a）所示。 读到的方格符号为1，所以该方格中写入0，读写头向左移动一位，同时图灵机进入P状态，如图1-9（b）所示。 处于P状态时，读写头读到0，所以该方格改写为1，同时图灵机进入G状态，立即停机，如图1-9（c）所示。此时记录在无限长的纸带上的结果为100110，即x=38。,（a）初始
10、状态,（b）P状态,（c）结束状态,1.2.2 冯诺伊曼体系结构 1945年，匈牙利裔美籍科学家冯诺伊曼在共同讨论的基础上起草了存储程序通用电子计算机方案电子离散变量自动计算机（Electronic Discrete Variable Automatic Computer，EDVAC）方案。,长达101页的EDVAC方案是计算机发展史上的一个划时代的文献。由于这一方案提出了现代计算机的基本体系结构，从而奠定了现代计算机的发展基础。,1.2.3 现代计算机的发展,第一代计算机的主要特征是采用电子管作为计算机的逻辑元件，其主存储器采用磁鼓、磁芯，外存储器采用磁带、纸带、卡片等。存储容量只有几千字节
11、、运算速度为每秒几千次。主要使用机器语言编写程序。这一代的计算机体积大、价格高、维修困难，使用也不方便，只在军事或科学研究部门使用，主要用于科学计算。,1第1代电子计算机（1946年1958年） 1946年，ENIAC的问世开创了计算机发展的新纪元。EDVAC设计方案，为现代计算机的发展奠定了基石，从此计算机进入现代阶段。1952年，EDVAC正式投入运行。,2第2代电子计算机（1958年1964年） 1958年，计算机进入了使用晶体管为主要元件的第二代。 第一台使用晶体管线路的计算机，是在1954年由美国贝尔（Bell）实验室研制的TRADIC计算机，在其中装了800个晶体管。,第二代计算机
12、全部采用晶体管作为逻辑元件，其主存储器使用磁芯，外存储器使用磁带、磁盘。在软件方面开始使用FORTRAN、COBOL、ALGOL等高级语言。这一代计算机不仅用于科学计算，还用于数据处理和事务处理及工业控制。相对第一代计算机，这一代计算机的运算速度更高、体积更小、功能更强。,3第3代电子计算机（1964年1970年） 1958年，美国物理学家基尔比（Jack Kilby）和诺伊斯（Robert Noyce）同时发明集成电路。集成电路的问世促使计算机的更新换代。,第三代计算机是以中、小规模集成电路为逻辑元件，其主存储器开始逐渐采用半导体元件，存储容量可达几兆字节，运算速度可达每秒几十万至几百万次。
13、体积进一步变小、成本进一步降低，同时性能进一步提高。在软件方面，操作系统开始使用，使计算机的功能越来越强。正是从第三代计算机时代起，计算机进入普及阶段，广泛应用于数据处理、过程控制、 教育等各个方面。,4第4代电子计算机（1971年至今） 在20世纪70年代初期，随着大规模集成电路（Large Scale Integration，LSI）和超大规模集成电路（Very Large Scale Integration，VLSI）的应用，电子计算机迅速发展到第四代。在第四代计算机的发展过程中，一个值得注意的发展趋势是计算机微型化、巨型化、多媒体化和网络化。,4第4代电子计算机（1971年至今） 高性
14、能计算机的诞生也是第四代计算机的一个引人注目的成就。1975年，美国CRAY公司研制成功巨型计算机CRAY-，实现了当时的超高速每秒1亿次运算。,4第4代电子计算机（1971年至今） 我国在超级计算机研制方面取得了重大成就，先后研制成功了“银河”系列、“天河”系列、“曙光”系列、“神威”系列、“深腾”系列超级计算机。国际TOP 500组织（http:/www.top500.org）每半年公布一次全球超级计算机500强排行榜。2016年6月，完全采用中国设计和制造的处理器的“神威太湖之光”计算机荣登榜首，成为全球运行速度最快的超级计算机。 在过去六届TOP500榜单上，我国超级计算机“天河二号”
15、一直名列榜首。“神威太湖之光” 是全球首个突破10亿亿次的超级计算机。,4第4代电子计算机（1971年至今） 随着微电子、计算机和数字化声像技术的发展，多媒体技术也得到了迅速发展，逐步形成了集文字、图形、图像、声音于一体的多媒体计算机系统。 计算机与通信技术的结合使计算机应用从单机走向网络，由独立网络走向互联网络。此外，让计算机具有推理、学习、联想等智能行为，是人们追求的目标。 与计算机硬件系统的发展想适应，计算机软件也得到了飞速发展。操作系统功能不断完善，各种开发工具与开发技术不断涌现，各种应用软件更是层出不穷。软件业已成为现代工业的一部分。,1.2.4 未来新型计算机,1光子计算机 光子计
16、算机利用光束取代电子进行数据运算、传输和存储。在光子计算机中，不同波长的光代表不同的数据，可以对复杂度高、计算量大的任务实现快速的并行处理。 1990年，美国贝尔实验室宣布研制出世界上第一台光子计算机。目前，光子计算机的许多关键技术已取得重大突破。然而，要想短期内使光子计算机实用化还有困难。,2生物计算机 生物计算机是以生物界处理问题的方式为模型的计算机。生物系统的信息处理过程是基于生物分子的计算和通信过程，因此生物计算又常称为生物分子计算，其主要特点是极大规模并行处理及分布式存储。经过特殊培养后制成的生物芯片可作为一种新型高速计算机的集成电路。,3量子计算机 量子计算机是指利用量子相干叠加原理，理论上具有超快的并行计算和模拟能力的计算机。如果现在传统计算机的速度是自行车，量子计算机的速度就好比飞机。例如，一台操纵50个微观粒子的量子计算机，对特定问题的处理能力可超过目前最快的“神威太湖之光”超级计算机。,1.3.1 计算机与信息技术 信息技术（Information Technolog
