计算机与计算思维

计算机与计算思维第1页/共55页2本章提要计算意义与计算思维计算科学方法概论可计算性与计算过程计算思维的跨学科交融计算机学科的核心概念与问题求解计算思维的技能科学思维逻辑思维算法思维效率思维创新思维伦理思维第2页/共55页3计算思维（Computationalthinking,CT）由美国

CarnegieMellon大学计算机科学教授周以真女士于2006年提出她认为，计算思维是运用计算机科学的基础概念进行问题求解、系统设计、以及人类行为理解等涵盖计算机科学之广度的一系列思维活动计算思维代表着一种普遍的态度和一类普适的技能，每一个人都应热心于它的学习和运用第3页/共55页4是概念化的抽象思维而不只是程序设计是基本的而不是死记硬背的技能是人的而不是计算机的思维方式是数学和工程思维的互补与融合是思想而不是人造品面向所有的人和所有地方关注依旧亟待理解和解决的智力上极有挑战性并且引人入胜的科学问题计算思维的特征第4页/共55页5Computation是可用数学表示的任何形式的信息处理的概念，它包括简单的计算和人的思维（humanthinking）所以，计算思维无论是由人或机器执行，都是建立在计算处理的能力和限制之上的Computing意味着任何面向目标的需要、受益于和创造计算机的活动,包括用于广泛目的的软件和硬件系统的设计、建造；各种信息的处理、规范和管理；用计算机开展的科研活动；使计算机系统具有智能行为；创建和使用通信和娱乐媒体；寻找和收集与任何目的有关的信息等Computationvs.Computing第5页/共55页6本章涉及的“计算”包含了computation和computing的内容对于计算机基础学习而言，了解计算思维的宏观特性，对于个人专业发展具有重要意义计算思维的宏观结构第6页/共55页7通过网络可以求解的问题信息查询交流与沟通资源的发布与共享计算思维的网络化第7页/共55页8移动通信与地理信息系统的结合，产生了新的计算模式：与位置有关的计算利用GPS定位，可以找到周边的服务设施通过移动信号基站，发现客户所需要的服务：天气、旅游、购物等计算思维的移动化移动通讯设备的广泛应用，催生了诸多新型的商业应用模式第8页/共55页9计算思维的信息化促进了政务、商务、教育和社会的信息化小学校园的门禁系统与移动通信结合，产生学生在校、离校信息服务信用卡消费信息与移动通信和因特网结合，产生实时消费报告和无纸化账单报告校园一卡通计算思维的信息化第9页/共55页10中国经济发展正在向服务型经济转型计算机科学与技术及信息技术则是现代服务型经济发展的根本保障Softwareasaservice(SaaS)和服务计算（servicecomputing）正在引起关注计算思维的服务化云计算模型示意第10页/共55页11计算思维的智能化促进了交通管理的智能化、业务流程的智能化、电子服务的智能化电子服务和社会生活的智能化的需求反过来促进计算思维智能化的进一步发展计算思维的智能化智能化能够缓解交通拥堵？第11页/共55页12计算思维从计算理论、计算技术、计算工程、计算工具、计算服务和计算应用的转化就是计算思维的工程化计算思维的工程化促进了诸如计算机、手机、平板电脑等计算工具和系统的发展，后者反过来促进了计算思维的工程化计算思维的工程化第12页/共55页13计算思维的人性化促进了人－机交互的人性化、计算工具的人性化和社会的进步计算和信息技术对人类产生的负面影响同样不可小视信息社会中的“宅人”数码相机vs.胶片工业数字印刷vs.铅字印刷计算思维的人性化人性化设计笔记本电脑支架第13页/共55页14层次化源于社会组织和分工计算思维的层次包括计算理论思维、计算技术思维、计算工程思维、计算工具思维、计算服务思维和计算应用思维六个层次思维组成它们分别对应计算理论、计算技术、计算工程、计算工具、计算服务和计算应用每个层次上的思维都至少包含许多不同的思维过程、思维模式和思维规律计算思维的层次化第14页/共55页15结构化源于软件开发的结构化系统分析、结构化设计和结构化程序设计重要的案例计算机体系结构多核CPUGPGPU（通用图形处理器）网络体系结构ISO/OSI参考模型TCP/IP模型计算思维的结构化IntelCore2DuoProcessor第15页/共55页16计算思维源于并服务于由计算理论、计算技术、计算工程、计算工具、计算服务和计算应用构成的计算思维生存周期这一生存周期以计算理论为始点，以计算应用为终点计算思维的过程化理论技术工程工具服务应用第16页/共55页17计算意义与计算思维小结“计算思维”是面向所有的人，所有学科的，应当具有普适性，但这种普适的内部是有差异的计算机科学是新兴学科，其内容日新月异，以及人的智力水于有高低之分，人们已掌握的计算机知识各有差异，不同人的计算思维具有很大差别，因此计算思维具有层次性只要具有思维品质中的独创性，就能创造性地解决问题不同层次上的计算机思维均可得到同质性的发展第17页/共55页18科学界一般认为，科学方法分为理论、实验和计算三大类与三大科学方法相对的是三大科学思维，理论思维以数学为基础，实验思维以物理等学科为基础，计算思维以计算机科学为基础第18页/共55页19理论源于数学，理论思维支撑着所有的学科领域。正如数学一样，定义是理论思维的灵魂，定理和证明则是它的精髓公理化方法是最重要的理论思维方法，科学界一般认为，公理化方法是世界科学技术革命推动的源头。理论思维第19页/共55页20实验思维方法可以分为以下三个步骤：①先提取出从现象中获得的直观认识的主要部分，用最简单的数学形式表示出来，以建立量的概念；②再由此试用数学方法导出另一易于实验证实的数量关系；③然后通过实验证实这种数量关系对于实验思维来说，最为重要的事情就是设计、制造实验仪器和追求理想的实验环境实验思维第20页/共55页21计算思维最根本的内容，即其本质是抽象（Abstraction）与自动化（Automation）计算思维中的抽象完全超越物理的时空观，并完全用符号来表示，其中，数字抽象只是其中的一类特例计算思维中的抽象最终是要能够利用机器的一步步自动执行。为了确保机器的自动化，就需要在抽象的过程中进行精确和严格的符号标记和建模还要求计算机系统或软件系统生产厂家能够向公众提供各种不同抽象层次之间的翻译工具计算思维第21页/共55页22计算机科学在本质上源自数学思维，因为像所有的科学一样，它的形式化基础建筑于数学之上计算机科学又从本质上源自工程思维，因为我们建造的是能够与实际世界互动的系统，基本计算设备的限制迫使计算机科学家必须计算性地思考，而不能只是数学性地思考构建虚拟世界的自由使我们能够超越物理世界的各种系统数学和工程思维的互补与融合很好的体现在抽象、理论和设计三个学科形态（或过程）上计算机科学的“源”与“流”第22页/共55页23计算理论是研究使用计算机解决计算问题的数学理论有三个核心领域：自动机理论、可计算性理论和计算的复杂性理论自动机将离散数学系统的构造，作用和关系作为研究对象的数学理论（描述通用计算机计算能力的图灵机模型）可计算性理论的中心问题是建立计算的数学模型，进而研究哪些是可计算的，哪些是不可计算的计算的复杂性理论研究算法的时间复杂性和空间复杂性第23页/共55页24计算机学科的方法论有三个过程：抽象、理论和自动化设计及实现最根本的问题在于：问题如何进行描述？哪些部分能够被自动化？如何进行自动化描述？建立物理符号系统并对其实施等价变换是计算机学科进行问题描述和求解的重要手段。“可行性”所要求的“形式化”及其“离散特征”使得数学成为重要的工具而计算模型无论从方法还是工具等方面，都表现出它在计算机上科学中的重要作用（参见1.3节）计算机学科的方法论的三个过程第24页/共55页25科学：关于自然、社会和思维的发展与变化规律的知识体系，其核心是发现技术：根据实践经验和科学原理而发展形成的各种工艺操作方法、技能和技巧，其核心是发明工程：将科学原理应用到生产实践中，是某种形式的科学应用，其核心是建造现代科技工作者的素养我们所使用的工具影响着我们的思维方式和思维习惯，从而也将深刻地影响着我们的思维能力

EdsgerDijkstra第25页/共55页26霍夫曼编码使用变长编码表对源符号（如文件中的字母）进行编码变长编码表通过评估来源符号出现概率的方法得到的，概率高的字母用较短的编码，出现概率低的则用较长的编码使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的四个状态的霍夫曼编码过程第26页/共55页27设信号源为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},试给出该信源的霍夫曼编码方案。解：若传送一个串字符串“Iamateacher”，共14个字符。若用ASCII传送，每个字符8位，共需112位。该字符串中有9个不同的符号，至少需要4位二进制才能表示，这样传送该字符串也要56位。若用计算的Huffman编码，只需要42位。霍夫曼编码举例︺第27页/共55页28霍夫曼编码过程

可以得到：

a的编码00e的编码111I的编码1101m的编码1100t的编码1011c的编码1010h的编码1001r的编码1000原字符串（二进制）长度：=112（14×8）位Huffman编码长度：=42位（0100111110111001011101010011000）第28页/共55页29在数论中，反运算的问题往往是极难求解的，或者说极难计算的离散对数和整数因式分解问题就属于困难的计算数论问题如果给出两个素数p和q，要求两者的乘积，即使p和q很大，那计算它们的乘积仍然是可行的但反过来，给出N，要求p和q就极为困难了利用反计算的难度，对数据进行加密，是现代密码学的基础计算机通讯中的公开密钥加密算法，就是利用了数论的这个原理第29页/共55页30密钥举例：在马丁•加德纳的《数学游戏》一书中，报告了1977年由RSA（Rivest,shamir和Adleman）悬赏100美元求解对一个密钥的破解问题。给出一对整数（e,N）作为公开钥，e=9007，N是一个随机的129位数1143816257578888676692357799761466120102182967212423625625618429357069352457338978305971235639587058989075147599290026878543541经过它加密后得到的密文C是9686961375462206147714092225435588290575999112457431987469512093081629822514570835693147662288398962801339905518299451557815154问C加密前的明文是什么？第30页/共55页31问题结论这个问题在1994年4月2日，即相隔了17年之后由迪里克•阿特金斯（DerekAtkins），迈克尔•克拉弗（MichaelGraff）和阿尔金•K•廉斯特拉（ArjenK•Lenstra），帕尔•雷兰德（PanlLeyland）解出，他们对上述的N成功地进行因式分解，它的两素因子是：

3490529510847650949147849619903898133417764638493387843990820577

和

3276913299326670954996198819083446143177642967991941539798288533在得到了p和q后，从密文计算明文的障碍就被克服了，这个明文是20080500130070903002315180419000118050019172105011309190800151919090618010705它是：THEMAGICWORDSARESQUEAMISHOSSIFRAGE（这些魔术般的词是鱼鹰。）第31页/共55页32生物信息学是一门新兴交叉学科，其发展的标志便是大量生命科学数据的快速积累以及为处理这些复杂数据而设计的新算法的不断涌现最常用的数据结构主要包括四种类型：1)字符串结构，表示DNA，RNA和氨基酸序列；2)树结构，表示各种生物有机体的系统进化树；3)三维空间点和连接集合结构，表示蛋白质的三维结构；4)图结构，表示代谢和信号传导通路第32页/共55页33计算科学中许多仿生计算算法都是受到生物学中群体行为的启发而模仿设计出来的例如，计算科学中的神经网络算法、遗传算法、演化算法、蚁群算法、协同进化算法、粒子群算法、生物免疫算法以及突现计算算法等计算机病毒的概念与行为也是模仿自然界中的生物病毒行为提出来的，同样具有潜伏性、流行性、传播性、自复制性、变异性和适应性等特点第33页/共55页34计算机学科的核心概念是ACM/IEEE-CS制定的CC1991报告首次提出的，是具有普遍性、持久性的重要思想、原则和方法，核心概念具有如下基本特征：（1）在学科及各分支学科中普遍出现；（2）在理论、抽象和设计的各个层面上都有很多示例；（3）在理论上具有可延展和变形的作用，在技术上有高度的独立性第34页/共55页35通过将一个对象（或事物）与其某种属性相联系，从而使抽象的概念具体化的过程将一个进程与一个处理机、一个变量与其类型或值分别联系起来这种联系的建立，实际上就是建立了某种约束在数据库中的不同表之间建立“关系”和参照完整性，就是用约束关系来保证数据的完整性。CS核心概念-绑定（Binding）第35页/共55页36指随着问题规模的增长使问题的复杂性呈非线性增加的效应这种非线性增加的效应是区分和选择各种现有方法和技术的重要因素几十万考生的高考成绩排序，须认真选择排序算法气候变暖对全球经济的影响，仿真与模拟CS核心概念-大问题的复杂性

（ComplexityofLargeProblems）第36页/共55页37对一个想法或问题进行形式化、特征化、可视化思维的方法数据流图和E-R图等都属于概念模型，而逻辑理论、开关理论和计算理论中的模型大都属于形式模型UML，统一建模语言是软件工程中的重要工具和方法CS核心概念-概念和形式模型（ConceptualandFormatModels）第37页/共55页38一致性包括用于形式说明的一组公理的一致性、事实和理论的一致性，以及一种语言或接口设计的内部一致性例如，由于计算机资源的部署原因，服务器的网络地址可能发生变化，但由于用户访问的是域名地址，只要保证正确的映射关系，网络地址的变化不会影响用户访问，这就是一致性在发挥作用CS核心概念-一致性和完备性（ConsistencyandCompleteness），第38页/共55页39关于时间、空间、人力和财力等资源消耗的度量在计算机软硬件的设计中，要充分考虑某种预期果达到的效率，以及一个给定的实现过程较之替代的实现过程的效率例如，原用于图形显示的图形处理器（GPU），现广泛应用于数据密集型的高性能计算场合（GPGPU，通用图形处理器），而这种应用可以大大节省高性能处理中的成本和能源消耗CS核心概念-效率（Efficiency）第39页/共55页40指系统的结构、状态、特征、行为和功能等随着时间的推移而发生的更改从CLI（命令行界面）到GUI（图形用户界面），是计算机应用方式演化的里程碑；而浏览器的出现，结束了桌面系统一统天下的局面最容易使用户受到困扰的是软件无止境的演化，从而预见和适应计算机系统的演化CS核心概念-演化（Evolution）第40页/共55页41所谓科学思维最基本的内容是没有证据就不要求急于下结论：遵循科学的方法来建立新的知识无论这些知识只是对日常生活中的现象，或是学科的前沿发现第41页/共55页42逻辑思维是从已知的些微（但非常重要的）信息中推导出尽可能多的信息，而不要轻易下结论新的信息收集必须按照确定的规程，你不能仅仅因为幸运的而走对路计算思维的技能-逻辑思维数独问题求解第42页/共55页43有些问题是一次性的，但解决这些问题的方案，则可以不断发展在同类问题一再出现时，算法思维就可以介入。没有必要重新每次从头思考，而是采用每次都行之有效的解决方案囚徒困境（prisoner'sdilemma）是博弈论的非零和博弈中具代表性的例子，反映个人最佳选择并非团体最佳选择虽然困境本身只属模型性质，但现实中的价格竞争、环境保护等方面，也会频繁出现类似情况计算思维的技能-算法思维第43页/共55页44算法思维案例：囚徒困境

两个罪犯准备抢劫银行，但作案前失手被擒。警方怀疑他们意图抢劫，苦干证据只够起诉非法持有枪械，于是将其分开审讯。为离间双方，警方分别对两人说：若都保持沉默(“合作”)，则一同入狱1年；若是互相检举(互相“背叛”)，则一同入狱5年若你认罪并检举对方(“背叛”对方)，他保持沉默，他入人狱10年，你可以获释(反之亦然)

结果两人都选择了招供（最希望的结果）。第44页/共55页45情况分析

孤立地看，这是最符合个体利益的“理性”选择。以A为例：若B招供，A自己招供获刑5年，不招供获刑10年；若B不招供，自己招供可以免刑，不招供获刑1年。两种情况下，选择招供都更有利，事实上却比两人都拒不招供的结果糟。由囚徒困境可知，公共生活中，如果每个人都从眼前利益、个人利益出发，结果会对整体的利益(间接对个人的利益)造成伤害。第45页/共55页46

为解决“囚徒困境”难题，美国曾组织竞赛，要求参赛者根据“重复囚徒困境”(双方不止一次相遇，“背叛”可能在以后遭到报复)来设计程序。将程序输入计算机反复互相博弈，以最终得分评估优劣(双方合作各得3分；双方背叛各得1分；一方合作一方背叛，合作方得0分，背叛方得5分)；有些程序采用“随机”对策；有些采用“永远背叛”对策；有些采用“永远合作”对策；结果，加拿大多伦多大学的阿纳托尔·拉帕波特教授的“一报还一报”策略夺得了最高分。第46页/共55页47

我方在第一次相遇时选择“合作”，之后就采取对方上一次的选择。这意味着：在对方每一次背叛后，我方就“以牙还牙”，也背叛一次；对方每一次合作后，我方就“以德报德”一次；《论语·宪问》中，有人问孔子：“以德报怨，何如?”孔子反问：“何以报德?以直报怨，以德报德。该策略有别于“善良”的“永远合作”或“邪恶”的“永远背叛”对策，及对方一旦“不忠”，我方就不再给机会，长久对抗的策略。第47页/共55页48

如果你选择“永远背叛”策略，你或许会在第一局拿到最高分，但之后的各局可能都只能拿到低分，最后虽然可能“战胜”不少对手，但由于总分很低，最终难逃被淘汰出局的命运。所以除非很难与对方再次相遇，不用担心其日后的反应，才可选择对抗与背叛；而在长期互动、博弈的关系中，“一报还一报”是最佳策略：它是善意的，从不首先背叛；它不迂腐，不管过去相处多好，仍然对背叛有反应；它是宽容的，不因一次背叛而选择玉石俱焚。第48页/共55页49计算机科学家效率观念有非常精确的定义，通用的方式是讨论如何尽量减少使用的资源来完成任务可减少资源各有不同，但最重要的往往是'时间‘重要的是寻找某种途径，保证能够任务完成而且使用尽可能少的步骤计算思维的技能-效率思维红绿球的换位游戏，如何使完成步骤最少？第49页/共55页50计算机科学家是进行系统集成的专家不只是应用今天的技术，而且还创造明天的技术什么是当今世界的10名大的创新？互联网，手机，个人计算机，光纤，电子邮件，卫星导航系统，记忆存储磁盘，