第1章 计算机与计算思维概要

1大学计算机基础计算机学院计算机与计算思维第一章2联系方式：StaffRoom:计算机学院208室Telephone：82312196-2016（O）EMAIL:[e-mail]上机时间：第5-15周，周二第7-8节地点：教八楼6楼计算机学院机房3计算机的发展算盘中国唐代第一种手动式计数器计算尺1622年，英国WilliamOughtred（奥特瑞德）手动式、减、乘、除、指数和三角函数运算加法器1942年，法国BlaisePascal（帕斯卡）机械式，只能做加法计算器1673年，德国GottfriedLeibniz（莱布尼茨）机械式，加、减、乘、除和开方差分机1812年，英国CharlesBabbage（巴贝奇）分析机1834年，英国CharlesBabbage计算机1946年，宾夕法尼亚大学ENIAC4查尔斯.巴贝奇1812年差分机1834年分析机差分机和分析机（计算机的直系祖先）三部分组成：(1)由许多轮子组成的保存数据的存储库；(2)运算装置；(3)能对操作顺序进行控制，并选择所需处理的数据以及输出结果的装置。5计算机科学奠基人英国科学家阿兰·图灵电子计算机之父：美籍匈牙利数学家冯·诺依曼阿兰·图灵和冯·诺依曼美国计算机学会(ACM)1966年设立图灵奖主要贡献：•建立图灵机模型，奠定了可计算理论的基础提出图灵测试，阐述了机器智能的概念主要贡献：•与同事研制人类第二台计算机EDVAC•“存储程序”概念冯·诺依曼计算机•奠定了现代计算机体系结构和工作原理姚期智2000A.N.Kolmogorov1H.Poincare2D.Hilbert3VonNeumann5陈省身31Alan.Turing68华罗庚906电子计算机的问世1946年2月由宾州大学研制的ENIAC电子计算机时代的到来。ElectronicNumericalIntegratorAndCalculator电子数字积分计算机重达30吨占地250m2启动工耗150000瓦18000个电子管每秒5千次加减运算没有存储器采用十进制7国际TOP500组织6月23日公布了最新的全球超级计算机500强排行榜中国“天河二号”获全球超级计算机500强三连冠Top1“天河二号”中国（运算速度为每秒33.86千万亿次）（国防科大）Top2“泰坦”美国能源部下属橡树岭国家实验室（每秒17.59千万亿次）Top3“红杉”美国劳伦斯-利弗莫尔国家实验室（每秒17.17千万亿次）Top4“京”日本理化研究所（每秒10.51千万亿次）（富士通）Top5“米拉”美国阿尔贡国家实验室（每秒8.59千万亿次）LINPACK是线性系统软件包测试天河二号每秒5.49亿亿次双精度浮点运算峰值速度每秒3.39亿亿次Linpack测试性能系统存储总容量相当于600亿册每册10万字图书计算机对我们产生了什么影响？无处不在工作助手生活伙伴最直观的感受深刻影响着人们的思维方式影响着很多学科的研究和发展事实上81.1计算与计算科学1.1.1计算与数字化“计算不再只和计算机有关，它决定着我们的生存”------尼葛洛庞帝《数字化生存》该书成为了二十世纪九十年代纽约时报排行榜中的畅销书。9计算已经改变了科学家们的思考方式计算生物学改变着生物学家的思考方式；计算博弈理论改变着经济学家的思考方式；纳米计算改变着化学家的思考方式；计算物理学改变着物理学家的思考方式；数学机械化改变数学家的思考方式；社会计算改变着社会学家的思考方式等等。。。。。。。10什么是计算？计算的本质是基于规则的符号串变换，更广义的说，计算是基于规则的物理状态的变换。1+3+4这样的数学运算可以说是我们最容易认同的计算；而将一段中文文章翻译成英文也就是计算，因为其实质是在保持语义不变的前提下，将一串中文符号变换成对应的英文符号；任何给定一定的输入，经过处理和变换，得到期望的输出的过程都可以称为计算。11计算可以和广阔的专业领域结合，通过学科交叉与融合，迸发出前景广阔的研究空间。计算生物学应用数据分析及理论的方法、数学建模和计算机仿真技术，来研究生物学、行为学和社会群体系统。计算经济学运用计算思想分析和综合经济问题，进行问题分析、模型研究及决策，统计数据表明，计算思想在诺贝尔奖获奖理论中占到70%以上的比例。12计算物理学是一门新兴的边缘学科。利用计算机大存储量和快速计算的有利条件，将物理学、力学、天文学和工程中复杂的多因素相互作用过程，通过计算机来模拟。如原子弹的爆炸、火箭的发射，以及代替风洞进行高速飞行的模拟试验等。目前，实验物理学、理论物理学和计算物理学已经步入一个三强鼎立的时代。13社会计算学科根据社会科学理论，以计算技术为工具，研究人类社会的组成、关系、结构、层次、行为、运动等问题，研究社会媒体，促进社会人群的交流与合作。计算也在改变着人们的工作方式，数字化会议为分布于世界各地的公司提供远程会议支持，创造出天涯若比邻的工作场景。数字化制造使得在设备在没有制造出来之前，既可以通过仿真系统进行分析，通过虚拟装配进行模拟设备的装配，在对于效果满意之后再进行实际投产。141.1.2计算科学计算科学是研究计算技术的一门科学，它具有促进其他科学门类发展的重要作用。计算技术发展到当今，其特征日益体现出以下特点：计算手段的器械化，计算过程的形式化，计算执行的自动化，计算对象的泛在化。15计算过程的形式化是计算自动执行的前提。人们首先需要对于计算问题进行抽象，对其实现形式化的表示；其次，对于计算过程往往需要设计算法，并完成程序设计；最后由计算机进行程序运行而得到期望的处理结果。16应用计算科学处理问题时是可能有误差的，误差的来源：可能来自于模型也可能来自于计算工具。17计算科学的研究内容计算科学的研究内容：算法可计算性算法的实现问题。18算法是对计算机上执行的计算过程的具体描述。确定求解问题的算法是求解问题的关键步骤。19算法举例若m和n是两个正整数，并且m≥n时，求m和n的最大公因子的欧几里得算法可表示为：E1[求余数]以n除m得余数r。E2[余数为0吗?]若r=0，计算结束，n即为答案；否则转到步骤E3。E3[互换]把m的值变为n,n的值变为r，重复上述步骤。依照这三条规则指示的步骤，可计算出任何两个正整数的最大公因子。2021/*例：求两个正整数m和n的最大公约数及最小公倍数*/C语言实现#includestdio.hvoidmain(){intm,n,r,M,N;intintGreatComDiv,intLeaseComMul;//intGreatComDiv为最//大公约数，intLeaseComMul最小公倍数printf(请输入m和n的值:);scanf(%d%d,&m,&n);M=m;N=n;if((m=0)||(n=0)){printf(输入错误!请重新输入!\n);}r=m%n;22while(r!=0)/*利用辗除法，直到r为0为止*/{m=n;n=r;r=m%n;}intGreatComDiv=n;intLeaseComMul=M*N/intGreatComDiv;printf(m和n的最大公约数是:%d\n,intGreatComDiv);printf(m和n的最小公倍数是:%d\n,intLeaseComMul);}可以把计算过程看成执行这些步骤的序列。我们发现，计算过程是有穷的，而且计算的每一步都是能够机械实现的（机械性）。23可计算性是指一个实际问题是否可以使用计算机来解决一个可以使用计算机解决的问题应该被定义为“可以在有限步骤内被解决的问题”，故哥德巴赫猜想这样的问题是不属于“可计算问题”之列的，因为计算机没有办法给出数学意义上的证明。不能期待计算机能解决世界上所有的问题。241.2计算思维计算思维是运用计算机科学的基础概念进行问题求解、系统设计，以及人类行为理解的涵盖计算机科学之广度的一系列思维活动。计算思维的本质是抽象和自动化。如同所有人都具备“读、写、算”（简称3R）能力一样，计算思维已经成为必须具备的科学思维能力。251.2.1科学思维人类思维模式艺术思维宗教思维科学思维逻辑思维实证思维计算思维26科学思维模式大体上可以分为三种：1．以观察和归纳自然（包括人类社会活动）规律为特征的实证思维。2．以推理和演绎为特征的逻辑思维。3．以抽象化和自动化为特征的计算思维。27实证思维实证思维起源于物理学的研究，集大成者的代表是伽利略、开普勒和牛顿。开普勒是现代科学中第一个有意识地将自然观察总结成规律，并把这种规律表示出来。伽利略建立了现代实证主义的科学体系，强调通过观察和实验（实验是把自然现象单纯化，以保证可以仔细研究其中的一个局部）获取自然规律的法则。牛顿把观察、归纳和推理完美地结合起来，形成了现代科学大厦的整体框架。28实证思维要符合三点原则：第一是可以解释以往的实验现象；第二是逻辑上自洽，即不能自相矛盾；第三是能够预见新的现象。即思维结论必须经得起实验的验证。29逻辑思维逻辑思维的研究起源于希腊时期，集大成者是苏格拉底、柏拉图、亚里士多德，他们基本构建了现代逻辑学的体系。以后又经过众多逻辑学家的贡献，例如莱布尼茨、希尔伯特等，使得逻辑学成为人类科学思维的模式和工具。30逻辑思维也要符合一些原则：第一是有作为推理基础的公理集合；第二是有一个可靠和协调的推演系统（推演规则）。任何结论都要从公理集合出发，经过推演系统的合法推理，得出结论。31计算思维计算思维是人类科学思维中，以抽象化和自动化，或者说以形式化、程序化和机械化为特征的思维形式。计算思维也是与人类思维活动同步发展的思维模式，但是计算思维概念的明确和建立却经历了较长的时期。32计算思维中的抽象化与数学（逻辑思维）的抽象化有不同的含义。计算思维的抽象化不仅表现为研究对象的形式化表示，也隐含这种表示应具备有限性、程序性和机械性。因此，可以说形式化、程序化和机械化作为计算思维的特征。331.2.2计算思维计算思维的标志是有限性，确定性和机械性。计算思维表达结论的方式必须是一种有限的形式，（回想一下，数学中表示一个极限，是用一个自变量趋向于无穷来定义一个代数式的值，这种方式在计算思维中是不允许的）；语义必须是确定的，在理解上不会出现因人而异、因环境而异的歧义性；必须是一种机械的方式，可以通过机械的步骤来实现。这三种标志是计算思维区别于其他两种思维的关键。34应用计算思维对问题的处理方法是：通过问题的形式化表示，算法的构造，对于算法的执行而得到所期望的处理结果。35例1：在一个高考成绩列表s1,s2,…,sn中查找考号为10011087的学生的成绩。问题分析：如何利用计算机来完成这样一个任务？36把一个班级的学生信息存在计算机的存储器中，要求完成：用户从键盘上输入要查找的学生学号10011087，屏幕显示该学生的成绩。设计一个算法完成这个查找过程，那么这个算法的思想和人工查找是基本一致的，即逐个对比s1,s2,…,sn，如果其中某一个的学号值与key=10011087匹配，则查找成功，结束查找过程；如果所有的学号都不与key匹配，则说明没有要找的这个学生，称为查找失败，结束查找过程。37例2：在一个按照学号升序排列的班级花名册s1,s2,…,sn中查找学号为1001的学生。分析：如果设计一个算法，在一个按照学号有序序列中完成查找指定的学号1001，设待查找的学号为key，我们仍然可以利用例1中的算法实现。然而，如果利用学生信息存储的有序性这一特点，我们可以设计一个效率更高的查找方法，称为二分查找。38描述如下：Step1：设定三个变量，i，j，m，其中，i=1，j=n，m=（i+j）/2Step2：当i≤j成立时，重复执行以下步骤Step2.1如果key=s[m].no，结束查找过程，查找成功；Step2.2如果keys[m].no，j=m-1；Step2.3如果keys[m].no，i=m+1;Ste