1.1计算思维概述1.5.ppt

1、1第一节第一节 计算思维概述计算思维概述补充讲义下载地址：http:/ Turing）1936年提出年提出用机器实现逻辑代码的执行，以模拟各种计算和逻辑思用机器实现逻辑代码的执行，以模拟各种计算和逻辑思维过程维过程图灵机图灵机纸带纸带存储器存储器读写头读写头输入输出装置输入输出装置有限状态控制器有限状态控制器控制器、运算器、寄存器控制器、运算器、寄存器状态、转移函数状态、转移函数计算机语言计算机语言纸带上的信息纸带上的信息程序程序代码存储、计算机语言、编译代码存储、计算机语言、编译图灵奖介绍图灵奖介绍101.2 计算工具的发展和电子计算机的诞生计算工具的发展和电子计算机的诞生1.手工计算工具n

2、算筹n纳皮尔筹 n计算尺n算盘112.机械式计算工具机械式计算工具n盘式计算机n莱布尼茨计算机n巴贝奇的差分机和分析机12n巴贝奇的差分机和分析机 把多项式数值表的复杂算式转化为差分运算，用简单的加法代替平方运算。差分机结构和功能差分机结构和功能三个寄存器三个寄存器每个寄存器六位（每个寄存器六位（10万）万）自动计算自动计算分析机结构和功能分析机结构和功能存储器存储器运算室运算室操作控制器操作控制器条件转移条件转移卡片输入卡片输入打印、制版、卡片打印、制版、卡片133.电子计算机的诞生电子计算机的诞生n1945年年底n“电子数值积分机和计算机”（Electronic Numerical Int

3、egrator and Computer）,简称ENIAC。n标志人类计算工具历史性变革的巨型机器宣告峻工。n正式的揭幕典礼于1946年2月15日举行，这一天被人们认为是ENIAC的诞生日。14nENIAC的最大特点就是采用电子线路来执行算术运算、逻辑运算和储存信息nENIAC有如下的缺陷：l第一第一,它按照十进制工作而非二进制它按照十进制工作而非二进制l第二第二,它最初是为弹道计算而设计的专用计算机它最初是为弹道计算而设计的专用计算机l第三第三,它的存储容量太小它的存储容量太小,至多只能存至多只能存20个字长个字长10位位的十进制数的十进制数15EDVACn在ENIAC还没有完成时，1944

4、年，它的设计者们就开始了新的计算机的设计n1945年，冯诺依曼提给出了“EDVAC报告的第一份草案”(First Draft of a Report on the EDVAC)。确定了新机器有五个构成部分：l运算器、运算器、l控制器、控制器、l存储器、存储器、l输入和输出装置输入和输出装置n这一结构被称为冯诺依曼结构，有此结构的计算机统称为冯诺依曼计算机。l提出：程序存储与程序运行的思想提出：程序存储与程序运行的思想16冯冯.诺依曼结构诺依曼结构n现代计算机的体系结构命令和数据以二进制的形式存储在存储器中命令和数据以二进制的形式存储在存储器中五大模块五大模块17nEDVAC的方案有两个非常重大

5、的改进：l一是为了充分发挥电子元件的高速度而采用了二进一是为了充分发挥电子元件的高速度而采用了二进制；制；l二是实现了存储程序二是实现了存储程序,可以自动地从一个程序指令可以自动地从一个程序指令执行到下一个程序指令执行到下一个程序指令,其作业顺序可以通过一种其作业顺序可以通过一种称为称为“条件转移条件转移”的指令而自动完成。的指令而自动完成。n冯诺依曼计算机也存在局限性l存储器和中央处理器之间的通路太狭窄存储器和中央处理器之间的通路太狭窄l串行顺序处理的工作机制串行顺序处理的工作机制18计算机的发展计算机的发展nENIAC诞生以来，随着组成逻辑电路的电子元件的发展，将电子计算机的发展划分为：l

6、第一代电子管时代，第一代电子管时代，l第二代晶体管时代，第二代晶体管时代，l第三代集成电路时代，第三代集成电路时代，l第四代超大规模集成电路时代。第四代超大规模集成电路时代。n以后的发展l量子计算机量子计算机l生物计算机生物计算机n如今，计算机从体积上趋于小型化，性能上趋于巨型化，功能上趋于网络化、智能化和综合化。科学思维科学思维(1)(1)科学就是整理事实，从中发现规律，作出结论（达尔文）科学就是整理事实，从中发现规律，作出结论（达尔文）(2)(2)理论科学、实验科学和计算科学理论科学、实验科学和计算科学作为科学发现三大支柱，正作为科学发现三大支柱，正推动着人文明进步和科技发展。推动着人文明

7、进步和科技发展。(3)(3)一般而论，三种科学对应着三种思维：一般而论，三种科学对应着三种思维：n理论科学理论科学 理论思维：理论思维：理论思维又叫推理思维，以推理和演绎为理论思维又叫推理思维，以推理和演绎为特征，以数学学科为代表。特征，以数学学科为代表。n实验科学实验科学 实验思维：实验思维：实验思维又叫实证思维，以观察和总结自实验思维又叫实证思维，以观察和总结自然规律为特征，以物理学科为代表。然规律为特征，以物理学科为代表。n计算科学计算科学 计算思维：计算思维：计算思维又叫构造思维，以设计和构造为特征，以计算机学科为代表计算思维又叫构造思维，以设计和构造为特征，以计算机学科为代表。计算思

8、维的提出计算思维的提出 2006年，美国卡内基梅隆大学的Jeannette M.Wing（周以真）教授首先提出计算思维（Computational Thinking）的概念。定义：运用计算机科学的基础概念进行问题求解、系统设计、以及理解人类行为等的一系列思维活动。观点：源自数学思维和工程思维的计算机思维，与阅读、写作与算术能力一样，应成为人类的基本技能。强调：计算思维是“人的，不是计算机的思维”，“计算思维是人类求解问题的一条途径，但决非试图使人类像计算机那样去思考”。补充讲义201117 November 2010 her research notes：CT:What and Why?201

9、0,Jan Cuny,Larry Snyder,and Jeannette M.Wing,“Demystifying CT for Non-Computer Scientists,”work in progress.“CT is the thought processes involved in formulating problems and their solutions so that the solutions are represented in a form that can be effectively carried out by an information-processi

10、ng agent.”Informally,CT describes the mental activity in formulating a problem to admit a computational solution.The solution can be carried out by a human or machine,or more generally,by combinations of humans and machines.CT is used in the design and analysis of problems and their solutions,broadl

11、y interpreted.计算思维是与形式化问题及其解决方案相关的一个思维过程，其解决问题的表示形式应该能有效地被信息处理代理执行合理抽象 高效算法（算法思维角度）合理建模 高效实施（工程思维角度）NOTCT=Computing Computer literacy,i.e.,how to use Word and Excel or even Google Computer programming,i.e.,beyond Java Programming 101课程中的计算思维举例课程中的计算思维举例（1）计算机与信息社会计算机与信息社会 从算盘到计算机的发展过程从算盘到计算机的发展过程 是计

12、算思维内容不断拓展的过程（从口诀到使用规则）是计算思维内容不断拓展的过程（从口诀到使用规则）展示计算机的应用，培养计算思维的意识展示计算机的应用，培养计算思维的意识 了解计算机能做什么？只有想不到的，没有做不到的了解计算机能做什么？只有想不到的，没有做不到的（2 2）计算机系统）计算机系统 用抽象和分解来控制庞杂的任务和设计复杂的系统用抽象和分解来控制庞杂的任务和设计复杂的系统 Cache:Cache:预置和缓存的典型案例预置和缓存的典型案例 多核处理器：并行编程的典型案例多核处理器：并行编程的典型案例（3 3）数据在计算机中的表示）数据在计算机中的表示 计算机中表示问题的方法计算机中表示问题

13、的方法（4 4）操作系统基础）操作系统基础 计算思维解决了计算机自身问题的同时；计算思维解决了计算机自身问题的同时；也可解决各种应用问题。也可解决各种应用问题。（5 5）计算机网络基础与应用）计算机网络基础与应用 协议分层，域名体系：复杂问题的分解协议分层，域名体系：复杂问题的分解 奇偶校验，奇偶校验，csma/cd:csma/cd:冗余设计，系统恢复冗余设计，系统恢复 从买参考书、泡图书馆到网上求解问题答案，从买参考书、泡图书馆到网上求解问题答案，标准的计算思维方法标准的计算思维方法 从商店购物到网上购物，从开设实店到网上开从商店购物到网上购物，从开设实店到网上开店店（6 6）数据库技术基础

14、）数据库技术基础 设计一个数据库，本身就是抽象和分解的过程设计一个数据库，本身就是抽象和分解的过程课程中的计算思维举例计算思维与问题求解计算思维与问题求解计算思维求解问题的手段：计算思维求解问题的手段：抽象和自动化抽象和自动化。问题求解的步骤问题求解的步骤 问题抽象化的描述，问题抽象化的描述，问题表示问题表示(如何建立模型如何建立模型)寻找解决方案，寻找解决方案，问题求解（如何设计算法）问题求解（如何设计算法）计算机实现过程，计算机实现过程，效率（如何有效地求解）效率（如何有效地求解）现实问题的延伸现实问题的延伸 计算思维与问题求解计算思维与问题求解计算机问题求解与程序设计课程计算机问题求解与

15、程序设计课程(1)(1)学习程序设计方法是理解计算机的最好途径学习程序设计方法是理解计算机的最好途径。(2)(2)程序设计课程的内容也最能够体现语言级的程序设计课程的内容也最能够体现语言级的问题求解方法。是计算思维能力培养的重要内问题求解方法。是计算思维能力培养的重要内容。容。(3)(3)对大多数非计算机专业的学生而言，学习程对大多数非计算机专业的学生而言，学习程序设计的目的是学习计算机分析和解决问题的序设计的目的是学习计算机分析和解决问题的基本过程和思路。基本过程和思路。计算思维不仅仅是程序设计计算思维不仅仅是程序设计预置和缓存预置和缓存 小学生早晨去学校时，她把当天需要的东西放进小学生早晨去学校时，她把当天需要的东西放进背包；背包；回推回推 小男孩弄丢他的手套时，你建议他沿走过的路回小男孩弄丢他的手套时，你建议他沿走过的路回寻；寻；多服务器系统的性能模型多服务器系统的性能模型 在超市付账时你应当去排哪个队呢？在超市付账时你应当去排哪个队呢？失败的无关性和设计的冗余性失败的无关性和设计的冗余性 为什么停电时你的电话仍然可用？为什么停电时你的电话仍然可用？计算思维的应用领域计算思维的应用领域n生物学n脑科学n化学n经济学n文学n艺术n社会学n管理学补充讲义2011