计算思维导论05-问题求解的基本思维

计算机与计算思维导论第六讲计算思维之问题求解思想第六讲计算思维之问题求解思想•主题一探讨问题求解过程•主题二相关知识的认识与了解•主题三关于算法的理解•主题四算法策略大搜罗•主题五几个经典案例的算法实现主题一探讨问题求解过程•计算思维问题求解综述•问题求解案例•问题求解框架•随着社会的发展与科技的进步，出于对问题计算时间和复杂度等多方面因素的考量，现实世界中的很多问题需要借助计算机帮我们计算！•可是，我们知道，现代计算机的工作原理是存储程序和程序控制，也就是说，现代计算机只能对可计算性问题进行计算，但是具体怎么计算，计算机却不知道，这需要人来告诉计算机。

•人与计算机的对话沟通方式就是通过程序控制指令。

•可是，这程序指令应该怎么写才能让计算机“心领神会”并“游刃有余”地完成预期的计算呢？这其中涉及到程序指令的语法和算法。

–简单地说，语法是具体书写程序指令的格式约束规则；–算法是解决问题的具体方法步骤，而算法又是建构在问题求解的数学模型和数据结构等诸多知识之上。

–数学模型是指经过分析抽象的建模过程将具体问题转化为形式化、符号化和公式化的数学语言描述；–数据结构是指计算机对数据进行存储、组织和操作运算的方式。

•那么，运用计算思维理念去求解问题和我们日常求解问题的过程有什么不同？运用计算思维进行问题求解过程都涉及到哪些环节和因素？–计算思维=数学建模？–计算思维=算法？–计算思维=数据结构？–计算思维=编程序？•事实上，单一的划等号都不能全面精确地定位计算机思维。

如果一定要用一个公式表述计算思维，那么可以说：–计算思维≈人的思维+数学建模+数据结构+计算算法+程序设计！人的思维数学建模数据结构计算算法程序设计•我们关注的是从一个在看似平常或看似纷繁的事物或事件中能够洞析和发现问题，并提出问题到抽象归纳出解决问题的算法直至最终解决问题的整个思想过程！而这个过程正是计算思维的问题求解思想的全过程。

主题一探讨问题求解过程•计算思维问题求解综述•问题求解案例•问题求解框架问题求解案例•首先，让我们从一个具体的问题出发–了解和认识运用计算思维理念去求解问题相比我们常规下求解问题的思考过程有什么不同？–以及运用计算思维进行问题求解过程都涉及到哪些环节和因素？•有三根相邻的柱子，假设标号分别为A、B、C，其中A柱子从下到上按金字塔状依次叠放了N个不同大小的圆盘，现要把A柱子上的所有圆盘一次一个地移动到C柱子上，移动的过程中可以借助B柱子做中转，并且每根柱子上的圆盘必须始终保持上小下大的叠放顺序。

第1章引论本章要点：1.什么是计算；2.计算机科学与计算科学的区别；3.来自计算机发展史的启示；4.计算机应用；5.计算机发展趋势。

1.1 什么是计算？简单计算，如我们从幼儿就开始学习和训练的算术运算，如“3 + 2 = 5”“3 2 = 6”等，是指“数据”在“运算符”的操作下，按“规则”进行的数据变换。

我们不断学习和训练的是各种运算符的“规则”及其组合应用，目的是通过计算得到正确的结果。

广义地讲，一个函数如“”把x变成了f(x)就可认为是一次计算，在高中及大学阶段我们不断学习各种计算“规则”并应用这些规则来求解各种问题，得到正确的计算结果。

如对数与指数、微分与积分等。

“规则”可以学习与掌握，但应用“规则”进行计算则可能超出了人的计算能力，即人知道规则但却没有办法得到计算结果。

如何解决呢？一种办法是研究复杂计算的各种简化的等效计算方法(数学)使人可以计算，另一种办法是设计一些简单的规则，让机械来重复的执行完成计算，即考虑能否用机械来代替人按照“规则”自动计算。

例如：能否机械地判断方程“a1x1b1+a2x2b2+…+a n x n b n = c”是否有整数解?”，即机械地证明一个命题是否有解? 是否正确?类似的上述问题，促进了计算机科学和计算科学的诞生和发展，促进了人们思考：◆什么能够被有效地自动计算？现实世界需要计算的问题是很多的，哪些问题是可以自动计算的，哪些问题是可以在有限时间有限空间内自动计算的？这就出现了计算及计算复杂性问题。

以现实世界的各种思维模式为启发，寻找求解复杂问题的有效规则，就出现了算法及算法设计与分析问题。

例如观察人的思维模式而提出的遗传算法、观察蚂蚁行动的规律而提出的蚁群算法等。

◆如何低成本、高效地实现自动计算？如何构建一个高效的计算系统：计算机器的构建问题和软件系统的构建问题。

◆如何方便有效地利用计算系统进行计算？利用已有计算系统，面向各行各业的计算问题求解。

什么能、且如何被有效地自动计算问题就是计算学科的科学家不断在研究和解决的问题。

计算思维一.计算思维的定义计算思维就是运用计算机科学的基础概念进行问题求解、系统设计、以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。

进一步地定义为:1.通过约简、嵌入、转化与仿真等方法,把一个瞧来困难的问题重新阐释成一个我们知道问题怎样解决的方法;2.就是一种递归思维,就是一种并行处理,就是一种把代码译成数据又能把数据译成代码,就是一种多维分析推广的类型检查方法;3.就是一种采用抽象与分解来控制庞杂的任务或进行巨大复杂系统设计的方法,就是基于关注分离的方法(S oc方法);4.就是一种选择合适的方式去陈述一个问题,或对一个问题的相关方面建模使其易于处理的思维方法;5.就是按照预防、保护及通过冗余、容错、纠错的方式,并从最坏情况进行系统恢复的一种思维方法;6.就是利用启发式推理寻求解答,也即在不确定情况下的规划、学习与调度的思维方法;7.就是利用海量数据来加快计算,在时间与空间之间,在处理能力与存储容量之间进行折衷的思维方法。

计算思维吸取了问题解决所采用的一般数学思维方法,现实世界中巨大复杂系统的设计与评估的一般工程思维方法,以及复杂性、智能、心理、人类行为的理解等的一般科学思维方法。

二.计算思维的深层次理解1.计算思维的优点计算思维建立在计算过程的能力与限制之上,由人由机器执行。

计算方法与模型使我们敢于去处理那些原本无法由个人独立完成的问题求解与系统设计。

2.计算思维的内容计算思维最根本的内容,即其本质(Essence)就是抽象(Abstraction)与自动化(Automation)。

计算思维中的抽象完全超越物理的时空观,并完全用符号来表示,其中,数字抽象只就是一类特例。

与数学与物理科学相比,计算思维中的抽象显得更为丰富,也更为复杂。

数学抽象的最大特点就是抛开现实事物的物理、化学与生物学等特性,而仅保留其量的关系与空间的形式,而计算思维中的抽象却不仅仅如此。

操作模式计算思维建立在计算过程的能力与限制之上,由人由机器执行。

计算思维导论考试重点高等教育出版社第一章计算思维基础知识一计算科学与计算学科1计算科学又称科学计算，它是一种与数学模型构建、定量分析方法以及利用计算机来分析和解决科学问题的研究领域。

2利用计算科学对其他学科中的问题进行计算模拟以及其他形式的计算而形成的诸如计算物理，计算化学、计算生物等学科统称为计算学科。

计算学科是对描述和变换信息的算法过程进行系统的研究，它包括算法过程的理论、分析、设计、效率分析、；实现和应用等。

二科学思维科学思维通常是指理性认识及其过程，经过感性阶段获得大量材料，通过整理和改造，形成概念、判断和推理，以及反映事物的本质和规律。

三科学思维的分类1理论思维又称逻辑思维，是指通过抽象概括，建立描述事物本质的的概念，应用科学的方法探寻概念概念之间联系的一种思维方法。

2实验思维又称实证思维，是通过观察和实验获取自然规律法则的一种思维方法。

3计算思维又称构造思维，是指从具体的的算法设计规范入手，通过算法过程的构造与实施来解决给定问题的一种思维方法。

四计算思维的定义计算思维是运用计算机科学的基础概念去求解问题、设计系统和理解人类行为的涵盖了计算机科学之广度的一系列思维活动。

五计算思维的特征1概念化不是程序化2根本的，不是刻板的技能3是人的，不是计算机的思维方式。

4数学和工程思维的互补与融合5是思想，不是人造物6面向所有人，所有地方六计算思维的本质抽象和自动化第二章计算理论与计算模型一计算理论是关于计算和计算机械的数学理论，它研究计算的过程与功效。

计算理论主要包括算法与算法学、计算复杂性理论、可计算性理论、自动机理论和形式语言理论等。

二可计算性理论是研究计算的一般性质的数学理论。

可计算理论的中心课题就是将算法这一直观概念精确化，建立计算的数学模型，研究哪些是可计算的，哪些是不可计算的，以此揭示计算的实质。

三停机问题p29理解四冯诺依曼机1冯诺依曼机的模型p372冯诺依曼机的工作原理冯诺依曼机的主要思想是存储程序和程序控制，其工作原理是：程序由指令组成，并和数据一起存放在存储器中，计算机一经启动，就能按照程序指定的逻辑顺序把指令从存储器中读取并逐条执行，自动完成指令规定的操作。

计算思维1. 计算思维是什么？1982年诺贝尔物理奖得主肯尼斯·威尔逊在他的获奖演讲中提到计算在他的⼯作中扮演的重要⾓⾊，他认为计算是所有科学的研究范式之⼀，区别于理论和实验，所有的学科都⾯临算法化的“巨⼤挑战”。

所有涉及⾃然和社会现象的研究都需要借助计算，使⽤计算模型做出新发现和推进学科发展。

他的⼯作和对于计算⽅法的⼤⼒推荐，激发了⼈们对于计算科学的认识和重视。

2006年，美国卡内基·梅隆⼤学的周以真（Jeannette M. Wing）教授，为了帮助⼈们更好地认识机器智能的不解之谜，发表了题为 Computational Thinking的⽂章，提出了⼀种建⽴在计算机处理能⼒及其局限性基础之上的思维⽅式——计算思维。

她认为，计算思维就是运⽤计算机科学的基础概念进⾏问题求解、系统设计，以及⼈类⾏为理解等涵盖计算机科学之⼴度的⼀系列思维活动，能为问题的有效解决提供⼀系列的观点和⽅法，它可以更好地加深⼈们对计算本质以及计算机求解问题的理解，⽽且还能克服“知识鸿沟”，便于计算机科学家与其他领域专家交流[2]。

2007年，周以真教授在卡内基·梅隆⼤学成⽴了计算思维研究中⼼，并修订了该⼤学⼀年级学⽣的课程，籍此培养该校⾮计算机专业学⽣的计算思维能⼒。

2008年，周以真进⼀步指出计算思维是⼀种分析思维，在问题解决的不同阶段会⽤到数学思维，在设计和评价复杂系统时会⽤到⼯程思维，在理解概念时会⽤到科学思维。

可以看出，计算思维是多种思维的综合应⽤。

计算思维不是要让⼈类像计算机那样思考，⽽是要培养有效使⽤计算解决复杂问题所必需的⼀组⼼智⼯具集。

美国计算机协会( ACM) 2008 年在对CC2001( CS2001) 的中期审查报告《CS2001 Interrim Review》(草案)中明确将“计算思维”与“计算机导论”课程绑定在⼀起，并要求该课程讲授计算思维的本质。

此外，卡内基·梅隆⼤学在美国国家科学基⾦会( NSF) 的⽀持下，设计了⼀门全新的包含计算机和计算思维基本概念的课程。