大学计算机基础 第三版

第1章 计算思维与计算机概论 20世纪人类*重大的成就之一就是计算机的发明和计算技术的应用及发展。自1946年美国的莫奇利和埃克特发明**台电子管计算机以来，仅仅经历了70多年的时间，以计算机技术为代表的信息技术都得到飞速的发展。大数据、云计算、互联网、移动互联网、物联网这些名词已经越来越频繁地进入人们的日常生活，并对整个人类社会结构和运行秩序产生了深刻的影响，同时也对人们分析问题、解决问题的科学思维模式产生了深刻的影响。计算思维成为并列于实证思维和逻辑思维的第三种科学思维模式。本章主要介绍计算思维与计算机基础。 1.1 计算思维 1.1.1 什么是计算思维 “用望远镜观测太空已经过时”，这句话虽然过于绝对，但也不无道理——对于信息时代的大多数天文研究者来说，现在研究的**步不是“看到”，而是“计算”。如今，天文学家已经更多利用网络来调度观测，远程控制位于沙漠或偏远地区的望远镜，下载相关的观察结果，然后利用计算机进行分析。 随着信息技术的快速发展，我们进入了大数据时代，获取数据、处理数据的能力有了极大的提高，我们就可以脱离大家认为*严谨的逻辑思维和实证思维方法，而采用观察的方法来研究问题，获取知识。特别是在人文科学和社会科学等无法采用实验方法研究的领域，通过观察设备(如传感器、摄像头等)作用于各种自然现象、社会活动和人类行为，产生了大量的数据，分析和处理这些数据，并且进行归纳和提炼。与古代仅仅依靠人的感官来观察现象相比，现在依靠传感器来观察现象，数据的密度、广度、准确性和一致性已经不能同日而语了。美国总统信息技术咨询委员会(PITAC)在《计算科学：确保美国竞争力》一文中提出：“虽然计算本身也是一门学科，但是其具有促进其他学科发展的作用。21世纪科学上*重要、经济上*有前途的研究前沿都有可能通过熟练掌握先进的计算技术和运用计算科技而得到解决”。 计算思维，在许多专家学者眼中，是人类应具有的第三种思维。相比于实证思维(观察与归纳)、逻辑思维(推理和演绎)，计算思维(设计与构造)关注的是人类思维中有关可行性、可构造性和可评价性的部分。 美国卡内基梅隆大学周以真(Jeannette M. Wing)教授2006年在美国 ACM通信期刊上首次提出了计算思维的定义。根据周以真教授对计算思维的定义，计算思维是运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等涵盖了计算机科学之广度的一系列思维活动。计算思维*根本的内容即其本质是抽象(Abstraction)和自动化(Automation)。计算思维中的抽象超越物理的时空观并完全用符号表示，其中数字抽象只是一类特例。 计算思维建立在计算过程的能力和限制之上，由人通过机器执行，其计算方法和模型使人们敢于去处理那些原本无法由个人独立完成的问题求解和系统设计。周以真教授对计算思维定义的详细表述体现在以下几个方面。 (1)计算思维是通过约简、嵌入、转化和仿真等方法，把一个看来困难的问题重新阐释成一个我们知道问题怎样解决的思维方法。 (2)计算思维是一种递归思维，是一种并行处理方法，可以把代码翻译成数据，又能把数据翻译成代码，是一种多维分析推广的类型检查方法。 (3)计算思维是一种采用抽象和分解来控制庞杂的任务或进行巨大复杂系统设计的方法，是一种基于关注点分离(Separation of Concerns)的方法，简称SOC方法。 (4)计算思维是一种选择合适的方式去陈述一个问题，或对一个问题的相关方面建模，使其易于处理的思维方法。 (5)计算思维是按照预防、保护及通过冗余、容错、纠错的方式，并从*坏情况进行系统恢复的一种思维方法。 (6)计算思维是利用启发式推理寻求解答，即在不确定情况下的规划、学习和调度的思维方法。 (7)计算思维是利用海量数据来加快计算，在实践和空间之间，在处理能力和存储容量之间进行折中的思维方法。周以真教授指出计算思维具有以下几个方面的特征。 (1)计算思维是概念化，不是程序化。计算机科学并不仅仅是设计程序，还要求能够在抽象的多个层次上思维。 (2)计算思维是根本的，不是刻板的技能。根本技能是每一个人为了在现代社会中发挥职能所必须掌握的。刻板技能意味着机械的重复。具有讽刺意味的是，当计算机像人类一样思考之后，思维可就真的变成机械的了。 (3)计算思维是人的，不是计算机的思维方式。计算思维是人类求解问题的一条途径，但绝非要使人类像计算机那样地思考。计算机枯燥且沉闷，人类聪颖且富有想象力。人类赋予计算机激情，配置了计算设备，我们就能用自己的智慧去解决那些在计算时代之前不敢尝试的问题，实现“只有想不到，没有做不到”的境界。 (4)计算思维是数学和工程思维的互补与融合。和所有学科的形式化基础都是建筑在数学之上一样，计算机科学在本质上也来源于数学思维。由于人类建造的计算机系统是一个能够与实际世界互动的系统，计算机科学在本质上来源于工程思维。由于基本的计算机系统受到的限制，迫使计算机科学家必须进行计算性思考，不能只是单纯地进行数学思考，而要开拓视野，用构建虚拟世界的自由来使人类能够设计出超物理世界的各种系统。 (5)计算思维是思想，不是人造物。计算思维不是以物理形式到处呈现并时时刻刻触及人们生活的软硬件等人造物，而是设计制造软硬件中包含的思想，是计算这一概念用于求解问题、管理日常生活以及与他人交流互动的思想。 (6)计算思维面向所有的人、所有的地方。周以真教授指出：当计算思维真正融入人类活动的整体以致不再表现为一种显式之哲学的时候，它将成为一种现实。 2009年7月，李国杰院士对周以真教授提出的“计算思维”定义进行了进一步的阐述：计算思维是科学运用计算科学的基础概念和基本理论去设计系统、解决问题以及理解人类行为，通过合适的方式去表述一个问题，对这个问题的相关方面进行建模，寻求并运用*有效的方法去解决问题。 事实上，计算思维已渗透到每个人的生活之中，成为每个人日常语言的一部分。例如：当你早晨准备去教室上课时，需要把当天课程相关的东西放进背包，这就是预置和缓存；当你丢失物品时，一般需要你回忆上次使用它的时间和地点，这就是回推；当你在“双十一”淘宝购物节购物时，要怎样不超过预算又能拿到*低折扣，这就是在线算法；当你在地铁站购票时，应当去排哪个队，这就是多服务器系统的性能模型；当停电时，为什么你的电话仍然可用，这就是失败的无关性和设计的冗余性等。在当今的知识信息社会中，计算思维代表着一种普遍的认识和一类普适的技能，是“信息环境下的人”*基础、*普遍、*实用和*不可或缺的基础思维方式。沃尔夫勒姆(Wolfram)在《一种新科学》一书中指出：自然界的本质是计算。可以这样说，计算思维作为一种用来解决所有可计算问题的力量，可以帮助“信息环境下的人”对各类问题进行抽象和自动化，从而求解问题。 1.1.2 计算思维与计算机 计算思维以抽象和自动化为手段，着眼于问题求解和系统实现，是人类改造世界的*基本的思维模式。计算机的出现强化了计算思维的意义和作用：理论与实践的过程变成了实际可以操作实现的过程；实现了从想法到产品整个过程的自动化、精确化和可控化；实现了自然现象与人类社会行为的模拟；实现了海量信息的处理分析、复杂装置与系统的设计、大型工程组织等，大大拓展了人类认知世界和求解问题的能力和范围。 计算思维源于数学思维和工程思维的融合，它涉及的*基本问题是“什么是可计算的”。而计算机学科是研究计算机的设计、制造和应用(包括利用计算机进行信息获取、表示、存储、处理、控制)的理论、方法和技术的学科，其研究核心是描述(抽象)和变化信息的算法过程，包括其理论、分析、设计、效率分析、实现和应用系统。计算机科学是计算的学问——什么是可计算的，怎样去计算。计算机科学在本质上源自数学思维，因为像所有的科学一样，它的形式化解析基础筑于数学之上。计算机科学又从本质上源自工程思维，因为我们建造的是能够与实际世界互动的系统。从计算思维和计算机学科的概念、特点来看，两者之间存在着高度的契合性。 计算思维与计算机之间存在相辅相成、相互促进的关系。 首先，计算机促进计算思维的研究与发展，计算机对信息的处理速度快、记忆力强的特点，使得原本只能理论上实现的过程，变成实际可行的实现过程。 其次，计算思维研究推动计算机的发展，在对计算思维的广泛、深入研究过程中，逐步揭示出一些属于计算思维的特点，计算思维与理论思维、验证思维的差异越来越明晰。计算思维的内容得到不断地丰富与发展。从思维的角度来说，计算科学主要研究计算思维的概念、方法和内容，并发展成为解决问题的一种思维方式，极大地推动了计算思维的发展。 李国杰院士认为：“20世纪后半叶是以技术创新和信息技术发明为标志的时代，预计21世纪的上半叶将会兴起一场以高性能计算和仿真、智能科学、网络科学、计算思维为特征的信息科技革命，信息科学的突破很可能会使21世纪下半叶出现一场新的信息技术革命”。 1.1.3 应用计算思维求解问题的一般过程 国际教育技术协会(International Society for Technology in Education，ISTE)和计算机科学教师协会(Computer Science Teachers Association，CSTA)指出计算思维是一个用来解决问题的过程，该过程包括以下六个步骤。 (1)制定问题，能够使用外界工具(如计算机和其他工具等)来解决这个问题。 (2)组织和分析数据，要符合逻辑。 (3)通过抽象(如模型、仿真等)重现数据。 (4)通过一系列有序的步骤也就是算法思想，支持自动化的解决方案。 (5)识别、分析和实施可能的解决方案，找到*有效的方案，并且有效结合这些步骤和资源。 (6)将该问题的求解过程进行推广并移植到更广泛的问题中。 这里以大家比较熟悉的测谎问题为例，说明计算思维在解决问题中的应用。 【例1-1】 到底谁说真话？谁说谎话？郭靖说：萧峰在说谎；萧峰说：张无忌在说谎；张无忌说：郭靖和萧峰都在说谎。已知三人中只有一人说真话。根据以上的陈述，现在要问到底谁说真话？这是一个非常典型的逻辑推理题，初看上去与计算没有关系。事实上可以利用穷举法求解，即把逻辑推理的叙述性命题数学化，再用计算机程序的自动化，把每一种可能情况中，满足条件的情况输出，就可求得命题的解，解题步骤详述如下。 (1)可以考虑每个人是否说真话，用一个表达式来表示。设A、B、C分别代表郭靖、萧峰和张无忌，各自取值为0(或False)时表示说的是假话，取值为1(或 True)时表示说的是真话。再用S代表说真话计数器，每当有说真话时，S就加1。如果A、B、C三人中只有一人说真话(A+B+C=1)并且S的值为1，说明满足命题给定的前提条件。此时可得出结论，即输出 A、B、C各自的值。其中值为1(或 True)的就是说真话的人。 (2)应用上一步的抽象规则数字化方法描述事实。 ①**句话，郭靖说：“萧峰在说谎”。 用数学式子表示为 B==0(或 B==False)； 同时也表达了如果郭靖说的是真话，则 B==0(或 B==False)表达式成立。 ②第二句话，萧峰说：“张无忌在说谎”中的“张无忌在说谎”。 用数学式子表示为 C==0(或 C==False)； 同时也表达了如果萧峰说的是真话，则 C==0(或 C==False)表达式成立。 ③第三句话，张无忌说：“郭靖和萧峰都在说谎”。“郭靖和萧峰都在说谎”用数学式子表示为 A==0 And B==0(或 A==False And B=