大学计算机 理论篇 第1章 计算思维

《大学计算机——理论篇》授课实验理论篇第1章计算思维和信息素养（2学时）应用篇Windows实验（第1次，共2次）理论篇第2章计算思维与计算机（2学时）应用篇Windows实验（第2次，共2次）应用篇第2章Word（第一个2学时，共4学时）设计电子报纸应用篇Word实验（第1次，共2次）应用篇第2章Word（第二个2学时，共4学时）论文排版应用篇Word实验（第2次，共2次）理论篇第3章计算思维与算法（4学时）毕业论文排版（第1,2次，共4次）理论篇第4章计算思维与数据的组织管理（4学时）毕业论文排版（第3,4次，共4次）理论篇第5章算法的实现——程序设计（第一个2学时,共4学时）应用篇计算机网络实验（共1次）理论篇第5章算法的实现——程序设计（第二个2学时,共4学时）应用篇C语言实验（共1次）应用篇第3章Excel（第一个2学时，共4学时）应用篇Excel实验（第1次，共2次）应用篇第3章Excel（第二个2学时，共4学时）应用篇Excel实验（第2次，共2次）应用篇第4,5章PowerPointVisio（2学时）应用篇PowerPoint实验（共1次）机动从本书的所有内容（包括讲过的章）中选（2学时）应用篇Visio实验（共1次）合计28学时合计28学时授课顺序及其与实验的对应关系（应用篇仅2015级用，以后仅《计算机文化基础》课程用）2024/8/181考勤10%实验报告和大作业30%期末考试（理论篇）60%

课程考核《大学计算机——理论篇》第1章计算思维和信息素养2024/8/182

讲课重点是理论篇杜忠友《大学计算机——理论篇》第1章计算思维和信息素养1234计算思维(重点)信息技术计算机文化信息素养本章讲授2学时2024/8/183计算思维要学会计算思维!如何用计算机解决这些实际问题？我们生活在人类社会最高端的计算机时代、信息时代我们要学会：用计算机解决所学专业领域、学习和日常生活中的实际问题什么是计算思维？12024/8/1842024/8/185科学思维:是在科学活动中,建立在科学知识基础之上的思维,是思维的科学化。

具有:客观性、精确性、可检验性、可预见性、普适性等特点。科技创新的三大支柱：理论思维、实验思维、计算思维计算思维什么是计算思维(Computationalthinking)？计算思维是运用计算机科学的基础概念进行问题求解、

系统设计以及人类行为理解

等涵盖计算机科学之广度的

一系列思维活动。12024/8/186计算思维运用计算机科学的基础概念求解问题设计系统理解人类行为例如例如例如方程求解例如ax2+bx+c=0定理证明例如四色定理表达式求值说谎问题求解……设计Windows7、WordAutoCADFlash、Photoshop游戏软件……求解问题的行为：分析问题、建立数学模型构造算法和数据结构编写程序调试运行。其他行为……12024/8/187什么是计算思维？计算思维运用计算机科学的基础概念求解问题人要适应计算机，要将问题转化为计算机能够处理的形式

意味着:12024/8/188计算思维例如一个说谎问题：有甲、乙、丙三人，每人或者说真话，或者说假话。甲说：“乙说假话。”乙说：“甲和丙是同一种人。”问甲、乙、丙三人谁说真话，谁说假话？人是怎么解答的？答：进行逻辑推理⑴先假定甲说真话,那么①甲说:”乙说假话。”就是真的,则乙说假话。②乙说:”甲和丙是同一种人。”则甲和丙不是同一种人。得到:丙说假话。③因此,结果为:甲说真话,乙说假话,

丙说假话。⑵再假定甲说假话,那么①甲说:”乙说假话。”就是假的,则乙说真话。②乙说:”甲和丙是同一种人。”则甲和丙是同一种人。得到:丙说假话。③因此,结果为:甲说假话,

乙说真话，

丙说假话。12024/8/189运用计算机科学的概念求解问题意味着：要将问题转化为计算机能够处理的形式计算思维这里用变量a、b、c表示甲、乙、丙三人说话的真假，当变量值为1时表示此人说真话,变量值为0时表示说假话。①甲说:”乙说假话。”这有两种可能:甲说的是真话,而乙确实说假话,即:a==1且b==0或者甲说的是假话，而乙说真话，即：a==0且b==1由此可得逻辑表达式：(a==1且b==0)或(a==0且b==1)②乙说:”甲和丙是同一种人。”这有两种可能:乙说真话,而甲和丙确是同一种人,即:b==1且a==c或者乙说的是假话,而甲和丙不是同一种人,即:b==0且a≠c。由此可得逻辑表达式：(b==1且a==c)或(b==0且a≠c)计算机怎么解答？答：不是像人这样推理。是用穷举法测试。分析问题建立模型计算机这个处理的过程现在不会不要紧，知道思路即可。穷举法以后还要学习。1例如一个说谎问题：有甲、乙、丙三人，每人或者说真话，或者说假话。甲说：“乙说假话。”乙说：“甲和丙是同一种人。”问甲、乙、丙三人谁说真话，谁说假话？2024/8/1810运用计算机科学的概念求解问题意味着：要将问题转化为计算机能够处理的形式计算思维①和②两个逻辑表达式要同时成立（因为应满足的条件都要满足）,最终得到确定谁说真话的逻辑表达式((a==1且b==0)或(a==0且b==1))且((b==1且a==c)或(b==0且a≠c))穷举每个人说真话或说假话的各种情况,用上述表达式逐个测试,使上述表达式的值为1(成立,真)的情况就是正确的结果。分析问题建立模型计算机怎么解答？答：不是像人这样推理。是用穷举法测试。1例如一个说谎问题：有甲、乙、丙三人，每人或者说真话，或者说假话。甲说：“乙说假话。”乙说：“甲和丙是同一种人。”问甲、乙、丙三人谁说真话，谁说假话？2024/8/1811运用计算机科学的概念求解问题意味着：要将问题转化为计算机能够处理的形式计算思维数学模型是：((a==1且b==0)或(a==0且b==1))且((b==1且a==c)或(b==0且a≠c))0≤a≤1,0≤b≤1,0≤c≤1（a,b,c是整数）分析问题建立模型计算机怎么解答？答：不是像人这样推理。是用穷举法测试。1例如一个说谎问题：有甲、乙、丙三人，每人或者说真话，或者说假话。甲说：“乙说假话。”乙说：“甲和丙是同一种人。”问甲、乙、丙三人谁说真话，谁说假话？2024/8/1812运用计算机科学的概念求解问题意味着：要将问题转化为计算机能够处理的形式计算思维构造算法计算机怎么解答？答：不是像人这样推理。是用穷举法测试。1例如一个说谎问题：有甲、乙、丙三人，每人或者说真话，或者说假话。甲说：“乙说假话。”乙说：“甲和丙是同一种人。”问甲、乙、丙三人谁说真话，谁说假话？2024/8/1813运用计算机科学的概念求解问题意味着：要将问题转化为计算机能够处理的形式计算思维编写程序调试运行结果是：a=1,b=0,c=0a=0,b=1,c=0与人的逻辑推理结果相同。这就是将问题转化为计算机能够处理的形式。因此，要学习计算思维。计算机怎么解答？答：不是像人这样推理。是用穷举法测试。1例如一个说谎问题：有甲、乙、丙三人，每人或者说真话，或者说假话。甲说：“乙说假话。”乙说：“甲和丙是同一种人。”问甲、乙、丙三人谁说真话，谁说假话？2024/8/1814运用计算机科学的概念求解问题意味着：要将问题转化为计算机能够处理的形式计算思维科学思维理论思维实验思维方程求解定理证明表达式求值……设计和构造算法，让计算机自动求解……计算思维推理和演绎数学归纳物理观察总结自然规律F=maI=U/R……自动求解计算机12024/8/1815计算思维是三大科学思维之一计算思维12024/8/1816理论思维、实验思维和计算思维构成了科技创新的三大支柱计算思维计算思维的本质自动化抽象抽出问题的本质特征例如:对说谎问题建立数学模型的过程例如:哥尼斯堡七桥问题12024/8/1817计算思维计算思维的本质自动化抽象自动化就是机械地一步步地自动执行。例如:计算机的开机就是自动执行的。例如:执行一段事先编写的排序程序,对指定数据的排序就能迅速地自动完成,不必人们再加干预。抽出问题的本质特征例如:对说谎问题建立数学模型的过程例如:哥尼斯堡七桥问题为了确保自动执行，就需要进行抽象建立数学模型，构造算法和编写程序。12024/8/1818计算思维计算思维的特征1234是概念化，不是程序化是根本的技能，不是刻板的技能是人的思维，不是计算机的思维是思想，不是物品5是数学和工程思维的互补与融合

计算思维要求能够像计算机科学家那样在抽象的多个层次上思维，强调概念和思想（例如说谎问题的穷举思想），而不只是计算机编程。

计算机科学不只是关于计算机，就像音乐不只是关于麦克风一样。12024/8/1819计算思维计算思维的特征2是概念化，不是程序化是根本的技能，不是刻板的技能是人的思维，不是计算机的思维是思想，不是物品5是数学和工程思维的互补与融合

根本的技能就像（阅）读、写（作）和（做）算（术）一样是基本的技能，是每个人为了在现代社会中发挥职能所必须掌握的。

要能灵活运用，举一反三。

刻板的技能意味着简单机械的重复，缺乏创新性，换个题目就不会做了。11342024/8/1820计算思维计算思维的特征2是概念化，不是程序化是根本的技能，不是刻板的技能是人的思维，不是计算机的思维是思想，不是物品5是数学和工程思维的互补与融合

计算思维是人类求解问题的一条途径，是人的思维方式，不是计算机的思维方式。

计算机之所以能求解问题，是因为人将计算思维赋予计算机，计算机按人设计的程序去执行；

同时，借助计算机，人类就能用自己的智慧去解决那些在计算机产生之前难以解决的问题(例如四色定理的证明)。11342024/8/1821计算思维计算思维的特征2是概念化，不是程序化是根本的技能，不是刻板的技能是人的思维，不是计算机的思维是思想，不是物品5是数学和工程思维的互补与融合

计算思维不是软件、硬件等人造物品，而是设计和制造软件、硬件中的思想，是计算这一概念用于求解问题、管理日常生活以及与他人交流和互动的思想。

而且，计算思维要用于所有的人，所有的地方。11342024/8/1822计算思维计算思维的特征2是概念化，不是程序化是根本的技能，不是刻板的技能是人的思维，不是计算机的思维是思想，不是物品5是数学和工程思维的互补与融合

计算思维既要以数学为基础（例如说谎问题的数学模型用到数学知识），

又要考虑工程上是否可行（考虑计算机的存储空间和计算速度是否允许。例如汉诺塔问题，计算速度不允许）。

11342024/8/1823计算思维计算思维的基本方法周以真归纳了七大类方法,高度概括,比较抽象.本课程学习下列方法（算法）穷举法迭代法递归法分治法贪心法分解集成(封装)查找算法排序算法……12024/8/1824计算思维1例如：用Word进行文档编辑——需要分析问题、设计编辑流程例如：利用百度搜索引擎查找资料——需要分析问题、制定检索策略例如：设计一个动画——需要建模和仿真例如：设计一个数据库——需要抽象和分解例如：Windows——抽象和分解为各种功能，再集成、组合为复杂的系统，来控制庞杂的任务等等。2024/8/1825我们已经运用了基本的、低级的计算思维(只是我们没有意识到运用了计算思维)：计算思维1我们还需要学会

高级别的计算思维学会：用计算思维和计算机求解所学专业领域、学习和日常生活中的实际问题2024/8/1826计算思维学习算法为了能用计算思维和计算机求解实际问题数据组织程序设计12024/8/1827计算思维1图灵分析了人的计算过程，将计算归结为最简单、最基本、最确定的操作动作，从而用一种简单的方法来描述直观上具有机械性的基本计算程序，

使任何机械（能行）的程序都可归约为这些动作，

实现了计算的自动进行。2024/8/1828与计算思维有关的图灵机计算思维1图灵机一条无限长的纸带一个状态寄存器一套控制规则一个读写头

控制规则根据当前机器所处的状态及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。

如此，经过有限步后机器在停机控制指令的控制下停止移动，最后纸带上的内容就是计算结果。2024/8/1829与计算思维有关的图灵机计算思维1一条控制规则→一条指令整套规则→指令集计算所执行的规则→程序纸带→存储器移动函数→运算器读写头→磁盘驱动器执行控制规则的控制器→控制器输入不同的程序→使机器做不同的动作1.将人具备的知识技能和由五官感知周围环境获得的一切看成输入集合2.将人作出的一言一行看成输出集合3.将人脑（保存脑中所有神经细胞的状态）看成状态寄存器4.将人对外界所作出的反应（一言一行）看成执行了一套复杂的控制规则人也抽象为图灵机等价于计算机进行任何计算1.改变状态集、符号集和控制规则，图灵机就能模拟人类所能进行的任何计算过程。2.状态集、符号集越扩大，控制规则越复杂，图灵机的功能就越强。2024/8/1830图灵机可以：与计算思维有关的图灵机计算思维1数值计算：加减乘除、乘方开方、指数函数、对数函数、幂函数、微积分等。非数值计算：数据排序、大小写字母互相转换、中英文互译、用异或进行密码加密和解密、图像反色显示、图像雾化、音频视频处理、推理、证明等。

图灵通过构造图灵机，形式化地阐述了计算的本质：

任何计算，在本质上都可以还原为计算者（人或机器）对一条两端可无限延长的纸带上的一串0、1进行变换，最后得到一个满足预先规定的符号串的过程。什么是计算？计算的本质是：基于规则的符号串变换，即完成从输入到输出的映射（x→f(x)）。计算的外延计算的本质计算的过程2024/8/1831与计算思维有关的计算计算思维1

图灵机可计算的函数就是可计算的（可以理解为有算法的函数就是可计算的）

图灵机不能计算的函数是不可计算的

在20世纪以前，人们普遍认为所有问题都是有算法的，都是可计算的，至少是一切数学命题都存在算法。

但直到20世纪初期，许多问题虽然进行了长期的研究，仍然找不到算法。什么是可计算的？什么是不可计算的？有许多问题不可计算：1.对于任意多个未知数的整系数不定方程，不能给出一个算法，使得借助于它，通过有限次运算，可以判定该方程有无整数解。2.边长为1的正方形的对角线的长在整数范围内不可计算。……(有：哥德尔的不完整性定理)什么可计算？结论所有问题都可计算？2024/8/1832与计算思维有关的可计算理论计算思维1什么是可计算的？什么是不可计算的？通俗地讲，什么是可计算的？1.人能求解，即有方法2.并能转化为计算机处理的形式，即有算法3.且算法的时间复杂性和空间复杂性不大例如哥德巴赫猜想目前不可计算！因为提不出证明的方法哥德巴赫猜想：任何大于等于6的偶数都是2个奇素数之和。例如：6=3+3,8=3+5,10=5+5,12=5+7,14=7+7……有限的验证不能作为证明！例如“为我做一个好吃的汉堡包”，目前不可计算！因为不能转化为计算机处理的形式。没有算法！例如汉诺塔问题和旅行商问题无法计算。时间复杂性太大，需要计算许多世纪或许多亿年！不可等待！2024/8/1833与计算思维有关的可计算理论计算思维计算思维的若干成果计算力学计算物理学计算化学计算经济学计算哲学计算语言学……1自动编排：编辑各种词表、索引、词典，建立语料库、术语数据库等。相当成熟自动分析：机器翻译——书面翻译(东方快车、百度翻译等)、语音翻译。试验阶段自动研究：根据计算机内存储的信息，借助统计、比较、类推等手段，得出自己

推断的结论。目前还不成熟。2024/8/1834计算思维计算思维能力的培养计算思维符合信息时代使用计算机的大方向1我们不能仅满足于使用Windows、Word、Excel、Flash、Photoshop等现成软件这些软件的功能被限定,使用它,难以超出这些功能，难以造就创新能力,难以培养创造型、创新型人才计算思维能够使人提出创造性地解决各专业、学习和日常生活中实际问题的方案计算思维可以建设创新型国家2024/8/1835计算思维计算思维能力的培养1美国已将计算思维纳入各个领域和各门课程，