计算机与计算思维.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,大家好,*,1,第一大班：经济,1114,讲课：周一,7,、,8,节 周四,1,、,2,节,上机：周四,9,、,10,节（,19,：,0021,：,00,）,第二大班,:,经济,1518,讲课：周一,5,、,6,节 周四,5,、,6,节,上机：周四,7,、,8,节,机器安排,大家好,2,教师：贾应智,E-Mail:ying.zhi.,交作业服务器：,用户名：,student,口令：,ctec,大家好,3,第,1,章 计算机与计算思维,大学计算机基础,大家好,4,本章提要,计算意义与计算思维,计算科学方法概论,可计算性与计算过程,计算思维的跨学科交融,计算机学科的核心概念与问题求解,计算思维的技能,科学思维,逻辑思维,算法思维,效率思维,创新思维,伦理思维,大家好,5,计算思维（Computational thinking,CT）由美国 Carnegie Mellon 大学计算机科学教授周以真女士于2006年提出,她认为，计算思维是运用计算机科学的基础概念进行,问题求解,、,系统设计,、以及,人类行为理解,等涵盖计算机科学之广度的一系列,思维活动,计算思维代表着,一种普遍的态度,和,一类普适的技能,，每一个人都应热心于它的学习和运用,大家好,6,是,概念化的抽象思维而,不只是,程序设计,是,基本的而,不是,死记硬背的技能,是,人的而,不是,计算机的思维方式,是,数学和工程思维的互补与融合,是,思想而,不是,人造品,面向,所有的人和所有地方,关注依旧亟待理解和解决的智力上极有挑战性并且引人入胜的科学问题,计算思维,的,特征,大家好,7,Computation 是可用,数学表示,的任何形式的信息处理的概念，它包括简单的计算和人的思维（human thinking）,所以，计算思维无论是由人或机器执行，都是建立在计算处理的,能力和限制,之上的,Computing 意味着任何面向目标的需要、受益于和创造,计算机的活动,包括,用于广泛目的的软件和硬件系统的设计、建造；,各种信息的处理、规范和管理；,用计算机开展的科研活动；,使计算机系统具有智能行为；,创建和使用通信和娱乐媒体；,寻找和收集与任何目的有关的信息等,Computation vs.Computing,大家好,8,本章涉及的“计算”包含了computation和computing的内容,对于计算机基础学习而言，了解,计算思维的宏观特性,，对于个人专业发展具有重要意义,计算思维的宏观结构,大家好,9,通过网络可以求解的问题,信息查询,交流与沟通,资源的发布与共享,计算思维的网络化,大家好,10,移动通信与地理信息系统的结合，产生了新的计算模式：,与位置有关的计算,利用,GPS,定位，可以找到周边的服务设施,通过移动信号基站，发现客户所需要的服务：天气、旅游、购物等,计算思维的移动化,移动通讯设备的广泛应用，催生了诸多新型的商业应用模式,大家好,11,计算思维的信息化促进了政务、商务、教育和社会的信息化,小学校园的门禁系统与移动通信结合，产生学生在校、离校信息服务,信用卡消费信息与移动通信和因特网结合，产生实时消费报告和无纸化账单报告,校园一卡通,计算思维的信息化,大家好,12,中国经济发展正在向服务型经济转型,计算机科学与技术及信息技术则是现代服务型经济发展的根本保障,Software as a service(SaaS),和服务计算（,service computing,）正在引起关注,计算思维的服务化,云计算模型示意,大家好,13,计算思维的智能化促进了交通管理的智能化、业务流程的智能化、电子服务的智能化,电子服务和社会生活的智能化的需求反过来促进计算思维智能化的进一步发展,计算思维的智能化,智能化能够缓解交通拥堵？,大家好,14,计算思维从计算理论、计算技术、计算工程、计算工具、计算服务和计算应用的转化就是计算思维的工程化,计算思维的工程化促进了诸如计算机、手机、平板电脑等计算工具和系统的发展，后者反过来促进了计算思维的工程化,计算思维的工程化,大家好,15,计算思维的人性化促进了人机交互的人性化、计算工具的人性化和社会的进步,计算和信息技术对人类产生的负面影响同样不可小视,信息社会中的“,宅人,”,数码相机,vs.,胶片工业,数字印刷,vs.,铅字印刷,计算思维的人性化,人性化设计 笔记本电脑支架,大家好,16,层次化源于社会组织和分工,计算思维的层次包括计算理论思维、计算技术思维、计算工程思维、计算工具思维、计算服务思维和计算应用思维六个层次思维组成,它们分别对应计算理论、计算技术、计算工程、计算工具、计算服务和计算应用,每个层次上的思维都至少包含许多不同的思维过程、思维模式和思维规律,计算思维的层次化,大家好,17,结构化源于软件开发的结构化系统分析、结构化设计和结构化程序设计,重要的案例,计算机体系结构,多核CPU,GPGPU（通用图形处理器）,网络体系结构,ISO/OSI 参考模型,TCP/IP模型,计算思维的结构化,Intel Core 2 Duo Processor,大家好,18,计算思维源于并服务于由计算理论、计算技术、计算工程、计算工具、计算服务和计算应用构成的计算思维生存周期,这一生存周期以计算理论为始点，以计算应用为终点,计算思维的过程化,大家好,19,计算意义与计算思维,小结,“计算思维”是面向所有的人，所有学科的，应当具有普适性，但这种普适的内部是有差异的,计算机科学是新兴学科，其内容日新月异，以及人的智力水于有高低之分，人们已掌握的计算机知识各有差异，不同人的计算思维具有很大差别，因此,计算思维具有层次性,只要具有思维品质中的独创性，就能创造性地解决问题,不同层次上的计算机思维均可得到,同质性的发展,大家好,20,科学界一般认为，科学方法分为理论、实验和计算三大类,与三大科学方法相对的是三大科学思维，理论思维以数学为基础，实验思维以物理等学科为基础，计算思维以计算机科学为基础,大家好,21,理论源于数学，理论思维支撑着所有的学科领域。正如数学一样，定义是理论思维的灵魂，定理和证明则是它的精髓,公理化方法是最重要的理论思维方法，科学界一般认为，公理化方法是世界科学技术革命推动的源头。,理论思维,大家好,22,实验思维方法可以分为以下三个步骤：,先提取出从现象中获得的直观认识的主要部分，用最简单的数学形式表示出来，以建立量的概念；,再由此试用数学方法导出另一易于实验证实的数量关系；,然后通过实验证实这种数量关系,对于实验思维来说，最为重要的事情就是设计、制造实验仪器和追求理想的实验环境,实验思维,大家好,23,计算思维最根本的内容，即其本质是抽象（,Abstraction,）与自动化（,Automation,）,计算思维中的抽象完全超越物理的时空观，并完全用符号来表示，其中，数字抽象只是其中的一类特例,计算思维中的抽象最终是要能够利用机器的一步步自动执行。为了确保机器的自动化，就需要在抽象的过程中进行精确和严格的符号标记和建模,还要求计算机系统或软件系统生产厂家能够向公众提供各种不同抽象层次之间的翻译工具,计算思维,大家好,24,计算机科学在本质上源自数学思维，因为像所有的科学一样，它的形式化基础建筑于数学之上,计算机科学又从本质上源自工程思维，因为我们建造的是能够与实际世界互动的系统，基本计算设备的限制迫使计算机科学家必须计算性地思考，而不能只是数学性地思考,构建虚拟世界的自由使我们能够超越物理世界的各种系统,数学和工程思维的互补与融合很好的体现在抽象、理论和设计三个学科形态（或过程）上,计算机科学,的“源”与“流”,大家好,25,计算理论是研究使用计算机解决计算问题的数学理论,有三个核心领域：自动机理论、可计算性理论和计算的复杂性理论,自动机将离散数学系统的构造，作用和关系作为研究对象的数学理论（描述通用计算机计算能力的,图灵机模型,）,可计算性理论,的中心问题是建立计算的数学模型，进而研究哪些是可计算的，哪些是不可计算的,计算的复杂性理论,研究算法的时间复杂性和空间复杂性,大家好,26,计算机学科的方法论有三个过程：抽象、理论和自动化设计及实现,最根本的问题在于：问题如何进行描述？哪些部分能够被自动化？如何进行自动化描述？,建立物理符号系统并对其实施等价变换是计算机学科进行问题描述和求解的重要手段。,“可行性”所要求的“形式化”及其“离散特征”使得数学成为重要的工具,而计算模型无论从方法还是工具等方面，都表现出它在计算机上科学中的重要作用（参见1.3节）,计算机学科的方法论,的三个过程,大家好,27,科学：,关于自然、社会和思维的发展与变化规律的知识体系，其核心是,发现,技术：,根据实践经验和科学原理而发展形成的各种工艺操作方法、技能和技巧，其核心是,发明,工程：,将科学原理应用到生产实践中，是某种形式的科学应用，其核心是,建造,现代科技工作者的素养,我们所使用的工具影响着我们的思维方式和思维习惯，从而也将深刻地影响着我们的思维能力,Edsger Dijkstra,大家好,28,霍夫曼编码使用,变长编码表,对源符号（如文件中的字母）进行编码,变长编码表通过评估来源符号出现概率的方法得到的，概率高的字母用较短的编码，出现概率低的则用较长的编码,使编码之后的字符串的平均长度、期望值,降低,，从而达到,无损压缩数据的目的,四个状态的霍夫曼编码过程,大家好,29,设信号源为,X=,、,a,、,e,、,I,、,m,、,t,、,c,、,h,、,r,。,对应的概率为,p=0.22,、,0.22,、,0.14,、,0.07,、,0.07,、,0.07,、,0.07,、,0.07,、,0.07,试给出该信源的霍夫曼编码方案。,解：,若传送一个串字符串“,I am a teacher”,，共,14,个字符。若用,ASCII,传送，每个字符,8,位，共需,112,位。该字符串中有,9,个不同的符号，至少需要,4,位二进制才能表示，这样传送该字符串也要,56,位。若用计算的,Huffman,编码，只需要,42,位。,霍夫曼编码举例,大家好,30,霍夫曼编码过程,可以得到：,a,的编码,00 e,的编码,111 I,的编码,1101 m,的编码,1100,t,的编码,1011 c,的编码,1010 h,的编码,1001 r,的编码,1000,原字符串（二进制）长度：,=112,（,148,）位,Huffman,编码长度：,=42,位,（,01 00 111 1101 1100 1011 1010 1001 1000,）,大家好,31,在数论中，,反运算,的问题往往是极难求解的，或者说极难计算的,离散对数和整数因式分解问题就属于困难的计算数论问题,如果给出两个素数p和q，要求两者的乘积，即使p和q很大，那计算它们的乘积仍然是可行的,但反过来，给出N，要求p和q就,极为困难,了,利用反计算的难度，对数据进行加密，是现代密码学的基础,计算机通讯中的公开密钥加密算法，就是利用了数论的这个原理,大家好,32,密钥举例：,在马丁,加德纳的,数学游戏,一书中，报告了,1977,年由,RSA,（,Rivest,shamir,和,Adleman,）悬赏,100,美元求解对一个密钥的破解问题。给出一对整数（,e,N,）作为公开钥，,e=9007,，,N,是一个随机的,129,位数,1143816257578888676692357799761466126184293578978358778543541,经过它加密后得到的密文,C,是,9686964771482957431987469512258962899451557815154,问,C,加密前的明文是什么？,大家好,33,问题结论,这个问题在,1994,年,4,月,2,日，即相隔了,17,年之后由迪里克,阿特金斯（,Derek Atkins,），迈克尔,克拉弗（,Michael Graff,）和阿尔金,K,廉斯特拉（,Arjen KLenstra,），帕尔,雷兰德（,Panl Leyland,）解出，他们对上述的,N,成功地进行因式分解，它的两素因子是：,34953387843990820577,和,3276995499619881976429679919433,在得到了,p,和,q,后，从密文计算明文的障碍就被克服了，这个明文是,2518010705,它是：,THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE,（这些魔术般的词是鱼鹰,。）,大家好,34,生物信息学是一门新兴交叉学科，其发展的标志便是大量生命科学数据的快速积累以及为处理这些复杂数据而设计的新算法的不断涌现,最常用的数据结构主要包括四种类型：,1)字符串结构，表示DNA，RNA和氨基酸序列；,2)树结构，表示各种生物有机体的系统进化树；,3)三维空间点和连接集合结构，表示蛋白质的三维结构；,4)图结构，表示代谢和信号传导通路,大家好,35,计算科学中许多仿生计算算法都是受到生物学中群体行为的启发而模仿设计出来的,例如，计算科学中的神经网络算法、遗传算法、演化算法、蚁群算法、协同进化算法、粒子群算法、生物免疫算法以及突现计算算法等,计算机病毒的概念与行为也是模仿自然界中的生物病毒行为提出来的，同样具有潜伏性、流行性、传播性、自复制性、变异性和适应性等特点,大家好,36,计算机学科的核心概念是ACM/IEEE-CS制定的CC1991报告首次提出的，是具有普遍性、持久性的重要思想、原则和方法，核心概念具有如下基本特征：,（1）在学科及各分支学科中普遍出现；,（2）在理论、抽象和设计的各个层面上都有很多示例；,（3）在理论上具有可延展和变形的作用，在技术上有高度的独立性,大家好,37,通过将一个对象（或事物）与其某种属性相联系，从而使抽象的概念具体化的过程,将一个进程与一个处理机、一个变量与其类型或值分别联系起来,这种联系的建立，实际上就是建立了某种约束,在数据库中的不同表之间建立,“关系”和参照完整性,，就是用约束关系来保证数据的完整性。,CS,核心概念,-,绑定（,Binding,）,大家好,38,指随着问题规模的增长使问题的复杂性呈非线性增加的效应,这种非线性增加的效应是区分和选择各种现有方法和技术的重要因素,几十万考生的高考成绩排序，须认真选择排序算法,气候变暖对全球经济的影响，仿真与模拟,CS,核心概念,-,大问题的复杂性,（,Complexity of Large Problems,）,大家好,39,对一个想法或问题进行形式化、特征化、可视化思维的方法,数据流图和E-R图等都属于概念模型，而逻辑理论、开关理论和计算理论中的模型大都属于形式模型,UML,，统一建模语言是软件工程中的重要工具和方法,CS,核心概念,-,概念和形式模型（,Conceptual and Format Models,）,大家好,40,一致性包括用于形式说明的一组公理的一致性、事实和理论的一致性，以及一种语言或接口设计的内部一致性,例如，由于计算机资源的部署原因，服务器的,网络地址,可能发生变化，但由于用户访问的是,域名地址,，只要保证正确的映射关系，网络地址的变化不会影响用户访问，这就是一致性在发挥作用,CS,核心概念,-,一致性和完备性（,Consistency and Completeness,），,大家好,41,关于时间、空间、人力和财力等资源消耗的度量,在计算机,软,硬,件的设计中，要充分考虑某种预期果达到的效率，以及一个给定的实现过程较之替代的实现过程的效率,例如，原用于图形显示的图形处理器（GPU），现广泛应用于数据密集型的高性能计算场合（GPGPU，通用图形处理器），而这种应用可以大大节省高性能处理中的成本和能源消耗,CS,核心概念,-,效率（,Efficiency,）,大家好,42,指系统的结构、状态、特征、行为和功能等随着时间的推移而发生的更改,从CLI（命令行界面）到GUI（图形用户界面），是计算机应用方式演化的里程碑；,而浏览器的出现，结束了桌面系统一统天下的局面,最容易使用户,受到困扰,的是软件,无止境的演化,，从而预见和适应计算机系统的演化,CS,核心概念,-,演化（,Evolution,）,大家好,43,所谓科学思维最基本的内容是,没有证据就不要求急于下结论,：遵循科学的方法来建立新的知识,无论这些知识只是对日常生活中的现象，或是学科的前沿发现,大家好,44,逻辑思维是从已知的些微（但非常重要的）信息中推导出尽可能多的信息，而不要轻易下结论,新的信息收集必须按照确定的规程，你不能仅仅因为幸运的而走对路,计算思维的技能,-,逻辑思维,数独问题求解,大家好,45,有些问题是一次性的，但解决这些问题的方案，则可以不断发展,在同类问题一再出现时，算法思维就可以介入。没有必要重新每次从头思考，而是采用每次都行之有效的解决方案,囚徒困境（prisoners dilemma,）是博弈论的非零和博弈中具代表性的例子，反映个人最佳选择并非团体最佳选择,虽然困境本身只属模型性质，但现实中的价格竞争、环境保护等方面，也会频繁出现类似情况,计算思维的技能,-,算法思维,大家好,46,算法思维案例：囚徒困境,两个罪犯准备抢劫银行，但作案前失手被擒。警方怀疑他们意图抢劫，苦干证据只够起诉非法持有枪械，于是将其分开审讯。,为离间双方，警方分别对两人说：,若都保持沉默,(“,合作,”,),，则一同入狱,1,年,；,若是互相检举,(,互相“,背叛,”,),，则一同入狱,5,年,若你认罪并检举对方,(“,背叛,”对方,),，他保持沉默，他入人狱,10,年,，你可以,获释,(,反之亦然,),结果两人都选择了,招供（最希望的结果）。,大家好,47,情况分析,孤立地看，这是最符合个体利益的,“,理性,”,选择。以,A,为例：若,B,招供，,A,自己招供获刑,5,年，不招供获刑,10,年；若,B,不招供，自己,招供,可以免刑，不招供获刑,1,年。两种情况下，选择,招供,都更有利，事实上却比两人都拒不招供的结果糟。,由囚徒困境可知，,公共生活中，如果每个人都从眼前利益、个人利益出发，结果会对整体的利益,(,间接对个人的利益,),造成伤害。,大家好,48,为解决“囚徒困境”难题，美国曾组织竞赛，要求参赛者根据“重复囚徒困境”,(,双方不止一次相遇，“背叛”可能在以后遭到报复,),来设计程序。,将程序输入计算机反复互相博弈，以最终得分评估优劣,(,双方合作各得,3,分；双方背叛各得,1,分；一方合作一方背叛，合作方得,0,分，背叛方得,5,分,),；,有些程序采用“,随机,”对策；,有些采用“,永远背叛,”对策；,有些采用“,永远合作,”对策；,结果，加拿大多伦多大学的,阿纳托尔,拉帕波特,教授的“,一报还一报,”策略夺得了最高分。,大家好,49,我方在第一次相遇时选择“合作”，之后就采取对方上一次的选择。这意味着：,在对方每一次背叛后，我方就“,以牙还牙,”，也背叛一次；,对方每一次合作后，我方就“,以德报德,”一次；,论语,宪问,中，有人问孔子：“以德报怨，何如,?”,孔子反问：“何以报德,?,以直报怨，以德报德。,该策略,有别于“善良”的“永远合作”或“邪恶”的“永远背叛”对策，及对方一旦“不忠”，我方就不再给机会，长久对抗的策略,。,大家好,50,如果你选择“,永远背叛,”策略，你或许会在第一局拿到最高分，但之后的各局可能都只能拿到低分，最后虽然可能“,战胜,”不少对手，但由于总分很低，最终难逃被淘汰出局的命运。,所以除非很难与对方再次相遇，不用担心其日后的反应，才可选择对抗与背叛；,而在,长期互动、博弈,的关系中，“,一报还一报,”是最佳策略：,它是善意的，从不首先背叛；它不迂腐，不管过去相处多好，仍然对背叛有反应；它是宽容的，不因一次背叛而选择玉石俱焚,。,大家好,51,计算机科学家效率观念有非常精确的定义，通用的方式是讨论如何尽量减少使用的资源来完成任务,可减少资源各有不同，但最重要的往往是,时间,重要的是寻找某种途径，保证能够任务完成而且使用尽可能少的步骤,计算思维的技能,-,效率思维,红绿球的换位游戏，如何使完成步骤最少？,大家好,52,计算机科学家是进行系统集成的专家,不只是应用今天的技术，而且还创造明天的技术,什么是当今世界的10名大的创新？互联网，手机，个人计算机，光纤，电子邮件，卫星导航系统，记忆存储磁盘，数码相机和RFID标签,计算机科学家则将它们组合在一起，构建新的系统并满足社会的需求,“,需要发掘用户需要但无从表达的需求,乔布斯,”,实际上是创造用户的需求,计算思维的技能,-,创新思维,大家好,53,任何新技术都是一把双刃剑,+现代计算机系统的成是带来对数字信息进行分析、处理和共享的便利,-也存在大量负面的影响,例如，如何处理创建电子商务客户联机档案的便利性与隐私问题之间的平衡，是当代信息系统引发的伦理问题之一,计算思维的技能,-,伦理思维,大家好,54,弄清事实,界定冲突或困境并识别有关的更高序列上的价值理念,确定利益相关者,理性的选择解决方案,确认解决方案可能带来的后果,伦理分析过程,大家好,55,计算思维是在计算学科与其他学科思想方法的交互中发展的，比如许多算法的思想来源于人类对特定学科研究对象的认识，又反过来作用于这些学科和更多学科的发展,从计算思维的内涵上讲，它阐述计算的基本思想和方法，究其根源这些思想和方法均来自人类的共同智慧，不但有助于计算学科中问题的求解，也与人类在其他领域工作和生活中解决问题的方法相通,本章小结,大家好,56,周以真计算思维中国计算机学会通讯J.2007，3(11),王飞跃从计算思维到计算文化J中国计算机学会通讯2007，3(11),董荣胜计算机科学导论思想与方法M高等教育出版社，2007,董荣胜，古天龙计算机科学与技术方法论M人民邮电出版社，2002,张晓如，张再跃.再谈计算机思维J.计算机教育 2010,董荣胜，古天龙计算思维与计算机方法论J计算机科学，2009，36(1)：14,王树林，黄德双，骆嘉伟，“计算科学与生命科学的相互交融与相互启示，”计算机科学J，2008年11月专辑,vol.35,no.11,pp.31-35.,孙兆豪,孙俊卿,郭喜凤.论计算思维和计算机思维 BS/OL,程向前等.计算机应用基础2011 M.中国人民大学出版社 2010,参考文献：,大家好,结束,大家好,57,