作者：夏耘
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
计算思维基础试读：
前言
随着信息科学在电子商务、虚拟制造、高精尖数字设备、信息化医疗设备等领域得到越来越广泛的应用，本科生信息基础课程的要求也越来越高——要求已从单纯知识和技能的培养层面，提高到意识和思维的培养层面。
近年来，国内外对计算思维课程的讨论如火如荼，在高校设置计算思维课程体系的理论探究与实践也陆续出现。例如，由李国杰院士任组长的中国科学院信息领域战略研究组撰写的《中国至2050年信息科技发展路线图》中，对“计算思维”给予了足够的重视，认为计算思维的培育是克服“狭义工具论”的有效途径，是解决其他信息科技难题的基础。又如，国家自然科学基金委员会信息科学部二处处长刘克教授，强调了在大学中推进“计算思维”这一基本理念的必要性。
计算思维课程并非仅面向计算机科学专业，而是面向所有专业。例如，一个人主修英语或数学等，却能从事于各行各业的工作；计算机科学也一样，一个人主修计算机科学，同样能从事任何类型的工作。计算思维课程应当激发学生对计算机科学的兴趣，让学生热爱计算机科学并积极探索，传播计算机科学的快乐和力量，致力于使计算思维成为公众的常识，真正融入人类的一切活动中。
本书认为，计算主义创造可自动模型、建立捕获处理的模型，自动化依次操作每个步骤最终完成计算任务，在整个过程中，不需要人工完成每一步，但需要有使每一步成为可用和可能的计划。
本书还认为，思维是人脑对客观事物本质属性和内部规律的间接（在已有经验基础上，通过推理来认识事物）或概括（对一类事物共同本质特征和规律性联系的归纳）反映过程。
本书共包含7章。第1章计算机与计算思维由夏耘老师编写，第2章信息技术基础由黄春梅老师和程国曙老师编写，第3章问题求解由黄小瑜老师编写，第4章数据的组织与管理由刘丽霞老师编写，第5章算法设计由臧劲松老师编写，第6章算法分析与问题优化由杨赞老师编写，第7章综合案例由马立新老师编写。夏耘、黄小瑜老师负责全书的总体策划与统稿、定稿工作。本书提供有配套电子课件，需要者请自华信教育资源网（www.hxedu.com.cn）免费注册下载。
在本书的编写过程中，得到了其他高等学校（复旦大学、西安交通大学和同济大学）的关心、支持和帮助，他们在书稿的审阅中提出了宝贵的意见与建议，在此对于各位老师的帮助，以及有关专家、教师长期以来对我们工作的支持和关心，表示衷心感谢。
由于作者本身的水平有限，再加上写作时间仓促，不当之处在所难免，衷心希望读者给予批评指正。
编 者
2012年6月
第1章 计算机与计算思维
计算是整个自然科学的工具，也是人类的基本生存技能之一。我们从小就学习计算，计算帮助我们完成小学、中学、大学的学习任务。在工作中，我们通过计算完成课题研究、工程设计；要在计算机与电子等行业取得突破性的进展，也必须基于数值计算。现代学科门类繁多，涉及面广，每门学科都需要进行大量的计算。本章将通过计算的定义、计算与人的关系、计算如何影响思维等问题，向读者介绍计算思维的基本过程，从而开启计算思维之门。
1.1 计算机
1.1.1 什么是计算计算无处不在。为了高考，你可能没有离开过书桌，感觉饥饿时，会上网要一份外卖；高考结束后，成绩的查询是必需的：在得知成绩后，进入下一环节——查询各高校的最低录取成绩，查询录取名单，查询学校的学科、培养计划等。在上述情景描述中不难发现，当问题的“漆黑”遮住你的眼睛时，计算会成为你的第一拐杖，高速单击，带给你的是方向和思想。
计算可以分为基本计算、复合计算和基于计算模型的计算。基本计算包括：
① 数值计算，即加、减、乘、除、微分、积分等。
② 字符计算，包括并串（例如，在网上搜索时为了提高效率，往往需要将几个关键词组合在一起进行搜索，组合关键词的操作称为并串计算）、取串（例如，在身份证编号中提取出生年份的操作，称为取串计算）、找串（例如，文本编辑中对词的替换操作的第一步，就是在文本中找到与指定字符相同的字符，称为找串操作）等。
③ 图像计算，包括图像分割和图像压缩。图像分割指的是将数字图像细分为多个图像子区域（像素的集合，也称为超像素）的过程。图像分割的目的是简化或改变图像的表示形式，使得图像更容易理解和分析，它常用于卫星定位、医学影像分析、指纹识别。图像压缩是指图像的数据量非常大，为了有效地传输和存储图像，有必要压缩图像的数据量。随着现代通信技术的发展，要求传输的图像信息的种类和数据量越来越大，若对此不进行数据压缩，便难以推广应用，因为原始图像数据是高度相关的，存在很大的冗余。数据冗余造成比特数浪费，消除这些冗余可以节约码字，也就是达到了数据压缩的目的。除此之外，图像计算还包括图像解压等。
数学计算是建立在计算原理的理论基础之上的，而这个理论基础就是数学计算中的关系。在一个计算式中通常包括数据、算符及计算结果。因此，计算关系包括：数据与数据的关系、数据与计算符的关系、计算符与计算符的关系。
① 数据与数据的关系
在一个计算式中，随着数据的出现，便有了计算关系。然而，计算关系不仅指数据本身，还指数据的内在性质（例如，级数中的具体项）和物理位置（一幅图像中数据的显示或表示）。
② 数据与运算符的关系
例如，x+2y−3z是一个数学计算式，其中数据与运算符号的关系包括：运算符号对数据个数的需求关系、运算符号对数据的作用、运算法则等。我们可以将这些关系分成以下几类：
· 自然数据的关系。
· 人工数据的关系（例如，程序中的数据关系）。
· 自然数据的人工处理关系（例如，放大一幅图像的一部分）。
③ 运算符与运算符的关系
运算和运算符的关系包括以下两种：
· 相同运算符对不同数据产生的计算效果可以不同（例如，C++语言的重载、多态等）。
· 由低阶运算符的组合构建一个序列，并定义一个新计算符，形成了高阶的运算符，例如积分。
严格、确定和精确的计算称为硬计算。然而在处理现实生活中的许多问题时，硬计算并不适用。用不确定、不精确及不完全真值的容错来取得低代价的解决方案称为软计算，它模拟自然界中智能系统的生化过程（人的感知、脑结构、进化和免疫等）来有效处理日常工作。软计算包括以下几种计算模式：模糊逻辑、人工神经网络、遗传算法和混沌理论。这些模式是互补及相互配合的，因此在许多应用系统中组合使用。1.1.2 计算工具
在中国历史上，结绳计数和契刻计数的方法大约使用了几千年，到新石器时代的晚期，才逐渐地被数字符号和文字计数所代替。最晚到商朝时，我国古代已经有了比较完备的文字系统，同时也有了比较完备的文字计数系统。在商代的甲骨文中，已经有了一、二、三、四、五、六、七、八、九、十、百、千、万这13个计数单字，而有了这13个计数单字，就可以记录十万以内的任何自然数。
中国春秋时代就出现了“算筹”，根据史书的记载和考古发现，古代的算筹实际上是一根根同样长短和粗细的小棍子，一般长为13～14 cm，直径0.2～0.3 cm，多用竹子制成，也有用木头、兽骨、象牙、金属等材料制成的，大约270枚为一束，放在一个布袋里，系在腰部随身携带。需要计数和计算的时候，就把它们取出来，放在桌上、炕上或地上。算筹的出现年代已经不可考，但据史料推测，算筹最晚出现在春秋晚期战国初年（公元前722年—公元前221年），一直到算盘发明推广之前算筹都是中国最重要的计算工具。15世纪算筹得到了普遍应用，取代了算筹。算盘是在算筹基础上发明的，比算筹更加方便实用，算筹还把算法口诀化，从而加快了计算速度。
计算尺发明于1620—1630年，在约翰·纳皮尔发表对数概念后不久。牛津的埃德蒙·甘特（Edmund Gunter）发明了一种使用单个对数刻度的计算工具，当和另外的测量工具配合使用时，可以用来做乘除法。1630年，剑桥的William Oughtred发明了圆算尺。1632年，他组合两把甘特式计算尺，用手合起来成为可以视为现代计算尺的工具。1722年，Warner引入了二-十进刻度和三-十进刻度，1755年Everard导入倒数刻度；包含所有这些刻度的算尺通常称为“多相”算尺。第二次世界大战中，需要进行快速计算的轰炸者和航行者经常使用专用算尺。美国海军的一个办公室实际上设计了一个通用算尺“底盘”，它由一个铝主体和塑料游标组成，可以把赛璐珞卡片（两面印刷）插到里面以进行特定的计算。这个过程被用于计算射程、燃料使用和飞行器高度等很多其他目的。19世纪50年代—60年代，计算尺是工程师身份的象征，如同显微镜代表了医学行业一样。有些工程系的学生和工程师常把10英寸算尺别在腰带上，或者将一把10英寸或20英寸算尺安放在家中或办公室里做精确运算用（当然，非常精确的运算，计算尺就不行了，需要一本厚厚的8位对数表），而随身携带一把5英寸袖珍算尺。
4机械式计算机的构思是与计算尺同时出现的，是计算工具上的一大发明。席卡德最早构思出机械式计算机，他在给天文学家J·开普勒的信中描述了他发明的四则计算机，但并没有成功制成。而成功创制第一部能计算加减法的计算机的是B·帕斯卡。1671年，G·W·莱布尼茨发明了一种能做四则运算的手摇计算机，这种计算是长为1 m的大盒子。自此以后，经过人们在这方面多年的研究，特别是经过L·H·托马斯、W·奥德内尔等人的改良后，出现了多种多样的手摇计算机，并风行全世界。17世纪末，这种计算机传入中国，中国人制造了12位数手摇计算机，独创出一种算筹式手摇计算机，即一种能依照一定的“程序”自动控制的计算机。19世纪初，法国的J·M·雅卡尔发明了用穿孔卡片来控制的纺织机，1822年，英国的C·巴贝奇根据同一原理制成了一部能执行计算程序的差分机，并于1834年设计了一部完全程序控制的分析机，可惜碍于当时机械技术的限制而没有制成，但已包含了现代计算的基本思想和主要的组成部分。此后，由于电力技术有了很大的发展，电动式计算机便慢慢取代以人工为动力的计算机。1880年，美国的H·霍勒里斯与J·S·比林斯发明了电动穿孔卡片式计算机，能机械化地处理数据。后来他们更开创了第一家制造电子计算机的公司——国际商业机器公司（简称IBM）。
20世纪以来，电子技术与数学得到充分发展，电子技术的改进，为计算机提供了物质上的基础，而数学的发展对设计及研制新型的计算机有很大的帮助。
1941年，德国的楚泽采用继电器制成了第一部通用程序控制计算机，实现了100多年前巴贝奇的理想。1944年，美国的艾肯亦以同一方法制成了一台程序控制自动数字计算机。20世纪初，电子管的出现使计算机的改革有了新的发展，并由于第二次世界大战的迫切军事需要，美国宾夕法尼亚大学和有关单位在1946年制成了第一台数字电子计算机ENIAC。以使用电子管为特点的第一代电子计算机在20世纪40年末和50年代初获得重大发展。以晶体管代替电子管并增加浮点运算的第二代电计算机于20世纪50年代中期问世。1964年，IBM 360系统问世，它成为使用集成电路的第三代电子计算机的著名代表。1971年11月，Intel推出MCS-4微型计算机系统，标志着使用超大规模集成电路的第四代计算机开始出现。第五代电子计算机被称为智能计算机。进入20世纪80年代以来，日本、美国等发达国家开始研制第五代计算机（也称为智能计算机）。在系统设计上，第五代计算机应用人工智能方法和技术，系统地建造知识库管理系统和推理机，使得机器本身能根据存储的知识进行推理和判断。智能计算机已经成为一个动态发展的概念，它始终处于不断向前推进的计算机技术的前沿。人工智能的权威学者M·明斯基定义人工智能的任务是研究还没有解决的计算机问题。这一观点反映了人工智能与智能机研究有别于其他学科的显著特点。智能应用问题往往因没有确定的求解算法而采用搜索办法，一旦人们对某一问题掌握了足够丰富的知识，就可找到不需要搜索的确定型算法。在可以预见问题的行为与效果时，该问题一般就不再认为是一个智能问题。
神经计算机，又称第六代计算机，是模仿人的大脑的判断能力和适应能力，并具有可并行处理多种数据功能的神经网络计算机。与以逻辑处理为主的第五代计算机不同，它本身可以判断对象的性质与状态，并能采取相应的行动，而且可同时并行处理实时变化的大量数据，并引出结论。以往的信息处理系统只能处理条理清晰、经络分明的数据，而人的大脑却具有能处理支离破碎、含糊不清信息的灵活性，第六代电子计算机将具有类似人脑的智慧和灵活性。1.1.3 计算机的工作原理和用途
匈牙利数学家冯·诺依曼是美国国家高级科学顾问，他在1945年提出了《关于电子计算机逻辑设计的初步讨论》的报告，给出了一个全新的程序存储的通用计算机方案EDVAC。目前大部分计算机的设计思路仍在这个基础之上进行，也就是所谓的“冯·诺依曼计算机结构”。脱离这个基础所设计的各种计算机，往往称为“非冯·诺依曼计算机结构”。
计算机由存储器、运算器、控制器、输入设备与输出设备等五大部分组成，集成电路出现以后，往往把运算器和控制器制作在同一芯片中，称为中央处理器（CPU）。运算器、输入/输出设备、存储器的操作以及它们之间的联系都受控制器的控制。早期的计算机以控制器、运算器为机器的中心。
但由于计算机以控制器、运算器为中心，使得低速的输入/输出和快速的运算不得不互相等待，主要表现在快速中央处理在等待慢速的外围设备；又由于所有部件的操作由控制器集中控制会使控制器的负担过重，从而严重影响机器速度和设备利用率的提高。因此，很快将计算机改成了以主存储器为中心，让系统的输入/输出与CPU的运算并行，多种输入和输出并行。
计算机能做什么?玩游戏?QQ聊天?打字?看电影?听音乐?……如果你是这样认为的，那就是“大材小用”了。计算机具有高速运算、逻辑判断、大容量存储和快速存取等功能，这就决定了它在现代社会的各领域都成为越来越重要的工具。计算机的应用相当广泛，涉及科学研究、军事技术、工农业生产、文化教育、娱乐等各方面。按学科，计算机应用可分为如下五大类。（1）科学计算（或称为数值计算）
这是计算机最早的应用领域。从尖端科学到基础科学，从大型工程到一般工程，都离不开数值计算。例如，宇宙探测、气象预报、桥梁设计、飞机制造等，都会遇到大量的数值计算问题，这些问题计算量大、计算过程复杂。像著名的“四色定理”的证明，就是利用IBM 370系列的高端机计算了1200多个小时才获得证明的，如果用人工计算，日夜不停地工作，也要十几万年。20世纪20年代初，天气预报方程已基本建立，但只有在计算机出现以后数值天气预报才成为可能。而在使用并行计算机系统之前，由于受处理能力的限制，只能做到24小时天气预报。高性能计算是解决数值预报中大规模科学计算的必要手段。采用高性能计算技术，可以通过提高分辨率来提高预报精度。利用计算机进行化工模拟计算，加快了化工工艺流程从实验室到工业生产的转换过程。
航空航天工业中，高性能计算主要应用在科学计算、实时仿真、图像处理、人工智能、数据库建立和计算机辅助设计等方面。在当代飞行器的设计中，高性能计算和风洞实验、自由飞行一起，构成了获得飞行器气动力数据的三种手段。采用计算流体力学和计算气动力学方法可以缩短周期、降低费用，还可以改变参数、重复计算。对那些目前不能在特定的飞行状态下进行实验的未来飞行器来说，数值模拟方法可以减少其设计风险，并在风洞实验前迅速确定出有希望的设计方案。将性能最好的并行计算机装备在国家宇航局是美国等技术先进国家的惯例。（2）数据处理（信息管理）
这是目前计算机应用最为广泛的领域。数据处理包括数据采集、转换、存储、分类、组织、计算、检索等，例如人口统计、档案管理、银行业务、情报检索、企业管理、办公自动化、交通调度、市场预测等，都涉及大量的数据处理工作。（3）辅助工程
辅助工程是指利用计算机进行辅助设计、制造、测试（CAD/CAM/CAT），具体包括：① 用计算机辅助进行工程设计、产品制造、性能测试；② 办公自动化；③ 经济管理；④ 情报检索；⑤ 自动控制；⑥ 模式识别等。（4）生产自动化
生产自动化指利用计算机对工业生产过程中的某些信号自动进行检测，并把检测到的数据存入计算机，再根据需要对这些数据进行处理。（5）人工智能
人工智能指开发一些具有人类某些智能的应用系统，如计算机推理、智能学习系统、专家系统、机器人等。
1.2 计算机应用系统的计算模式
计算机应用系统中数据与应用（程序）的分布方式称为企业计算机应用系统的计算模式，有时也称为企业计算模式。自世界上第一台计算机诞生以来，计算机作为人类信息处理的工具已有半个多世纪，在这一发展过程中，计算机应用系统的模式发生了几次变革，它们分别是：单主机计算模式、分布式客户/服务器计算模式（Client/Server，C/S）和浏览器/服务器计算模式（Browser/Server，B/S）。1.2.1 单主机计算模式
1985年以前，计算机应用一般是单台计算机构成的单主机计算模式。主机计算模式又可细分为两个阶段：① 单主机计算模式的早期阶段，系统所用的操作系统为单用户操作系统，系统一般只有一个控制台，限单独应用，如劳资报表统计等。② 分时多用户操作系统的研制成功及计算机终端的普及，使早期的单机计算模式发展成为单主机-多终端的计算模式。在单主机-多终端的计算模式中，用户通过终端使用计算机，每个用户都感觉好像是在独自享用计算机的资源，但实际上主机是在分时轮流为每个终端用户服务。
单主机-多终端的计算模式在我国当时一般被称为“计算中心”，在单主机模式的阶段，计算机应用系统中已可实现多个应用（如物资管理和财务管理）的联系，但由于硬件结构的限制，只能将数据和应用（程序）集中放在主机上。因此，单主机-多终端计算模式有时也被称为“集中式的企业计算模式”。1.2.2 分布式客户/服务器计算模式
20世纪80年代，个人计算机的发展和局域网技术逐渐趋于成熟，使用户可以通过计算机网络共享计算机资源，计算机之间通过网络可协同完成某些数据处理工作。虽然个人计算机的资源有限，但在网络技术的支持下，应用程序不仅可利用本机资源，还可通过网络方便地共享其他计算机的资源，在这种背景下分布式客户/服务器（C/S）的计算模式形成了。
在客户/服务器模式中，网络中的计算机被分为两大类：一是用于向其他计算机提供各种服务（主要有数据库服务、打印服务等）的计算机，统称为服务器；二是享受服务器所提供的服务的计算机，称为客户机。
客户机一般由微机承担，运行客户应用程序。应用程序被分散地安装在每台客户机上，这是C/S模式应用系统的重要特征。部门级和企业级的计算机作为服务器运行服务器系统软件（如数据库服务器系统、文件服务器系统等），向客户机提供相应的服务。
在C/S模式中，数据库服务是最主要的服务，客户机将用户的数据处理请求通过客户机的应用程序发送到数据库服务器，数据库服务器分析用户请求，实施对数据库的访问与控制，并将处理结果返回给客户机。在这种模式下，网络上传送的只是数据处理请求和少量的结果数据，网络负担较小。
对于较复杂C/S模式的应用系统，数据库服务器一般情况下不只一个，而是按数据的逻辑归属和整个系统的地理安排可能有多个数据库服务器（如各子系统的数据库服务器及整个企业级数据库服务器等），企业的数据分布在不同的数据库服务器上，因此，C/S模式有时也称为分布式客户/服务器计算模式。
C/S模式是一种较成熟且应用广泛的企业计算模式，其客户端应用程序的开发工具也较多，这些开发工具分为两类：一类是针对某一种数据库管理系统的开发工具（如针对Oracle的Developer 2000），另一类是对大部分数据库系统都适用的前端开发工具（如PowerBuilder、Visual Basic、Visual C++、Delphi、C++Builder、Java等）。1.2.3 浏览器/服务器计算模式
浏览器/服务器（B/S）模式是在C/S模式的基础上发展而来的。导致B/S模式产生的原动力来自不断增大的业务规模和不断复杂化的业务处理请求，解决这个问题的方法是在传统C/S模式的基础上，由原来的两层结构（客户/服务器）变成三层结构。B/S模式具体结构为：浏览器/Web服务器/数据库服务器。在三层应用结构中，用户界面（客户端）负责处理用户的输入和输出（出于效率的考虑，它可能在向上传输用户的输入前进行合法性验证）。商业逻辑层负责建立数据库的连接，根据用户的请求生成访问数据库的SQL语句，并把结果返回给客户端。数据库层负责实际的数据库存储和检索，响应中间层的数据处理请求，并将结果返回给中间层。
B/S模式的系统以服务器为核心，程序处理和数据存储基本上都在服务器端完成，用户无须安装专门的客户端软件，只要通过网络中的计算机连接服务器，使用浏览器就可以进行事务处理，浏览器和服务器之间通过通信协议TCP/IP进行连接。浏览器发出数据请求，由Web服务器向后台取出数据并计算，将计算结果返回给浏览器。B/S模式具有易于升级、便于维护、客户端使用难度低、可移植性强、服务器与浏览器可处于不同的操作系统平台等特点，同时也受到灵活性差、应用模式简单等问题的制约。在早期的OA（办公自动化）系统中，B/S模式是被广泛应用的系统模式，一些MIS、ERP系统也采取这种模式。B/S模式系统主要的应用平台有Windows Server系列、Lotus Notes、Linux等，其采用的主要技术手段有Notes编程、ASP、Java等，同时使用COM+、ActiveX控件等技术。
尽管C/S结构相对于更早的文件服务器来说，有了很大的进步，但与B/S相比，缺点和不足是很明显的。（1）B/S比C/S的维护工作量大大减少
C/S结构的每个客户端都必须安装和配置软件。假如一个企业共有50个客户站点，使用一套C/S结构的软件，则当这套软件进行了哪怕很微小的改动后（如增加某个功能），系统维护员都必须进行这样的维护：将服务器更新到最新版本，将客户端原有的软件卸载，再安装新的版本，然后进行设置。最可怕的是，客户端的维护工作必须不折不扣地进行50次。若其中有部分客户端是在另外一个地方，则系统维护员还必须跑该处再进行卸载、安装、设置工作。若某客户端忘记进行这样的维护，则该客户端将会碰到版本不一致的问题而无法工作。而对于B/S结构，客户端不必安装及维护。若将前面企业的C/S结构的软件换成B/S结构的，软件升级后，系统维护员只要将服务器的软件升级到最新版本就行了。其他客户端，只要重新登录系统，使用的就已经是最新版本的软件。（2）B/S相对C/S能够降低总体拥有成本
C/S软件一般是采用两层结构的，而B/S软件采用的是三层结构。两层结构中，客户端接收用户的请求，客户端向数据库服务提出请求，数据库服务将数据提交给客户端，客户端将数据进行计算（可能涉及运算、汇总、统计等）并将结果呈现给用户。在三层结构中，客户端接收用户的请求，客户端向应用服务提出请求，应用服务从数据库服务中获得数据，应用服务将数据进行计算并将结果提交给客户端，客户端将结果呈现给用户。这两种结构的不同点是，两层结构中客户端参与运算，而三层结构中客户端并不参与运算，只是简单地接收用户的请求，显示最后的结果。由于三层结构中的客户端并不需要参与计算，所以对客户端的计算机配置要求是比较低的。另外，由于从应用服务到客户端只传递最终的结果，数据量较少，使用电话线也能够胜任。而采用C/S两层结构，使用电话线作为传输线路可能因为速度太慢而不能够接受。采用三层结构的B/S的配置可以提高服务器的配置，降低客户端的配置。这样，增加的只是一台服务器（应用服务和数据库服务可以放在同一台计算机中）的价格，而降低的却是几十台客户端机器的价格，起到了降低总体拥有成本的作用。
从技术发展趋势上看，B/S最终将取代C/S计算模式。但同时，网络计算模式很可能是B/S、C/S同时存在的混合计算模式。这种混合计算模式将逐渐推动商用计算机向两极化（高端和低端）和专业化方向发展。在混合计算模式的应用中，处于C/S模式下的商用计算机根据应用层次的不同，体现出高端和低端的两极化发展趋势；而处于B/S模式下的商用计算，因为仅仅作为网络浏览器，已经不再是一个纯粹的PC，而变成了一个专业化的计算工具。
1.3 新的计算模式
1.3.1 普适计算所谓普适计算（Pervasive Computing/Ubiquitous Computing），指的是无所不在的、随时随地可以进行计算的一种方式——无论何时何地，只要需要，就可以通过某种设备访问到所需的信息。
普适计算（又叫普及计算）的概念早在1999年就由IBM公司提出，它有两个特征，即间断连接、轻量计算（即计算资源相对有限），同时具有如下特性：① 无所不在特性（pervasive）：用户可以随地以各种接入手段进入同一信息世界；② 嵌入特性（embedded）：计算和通信能力存在于我们生活的世界中，用户能够感觉到它和作用于它；③ 游牧特性（nomadic）：用户和计算均可按需自由移动；④ 自适应特性（adaptable）：计算和通信服务可按用户需要和运行条件提供充分的灵活性和自主性；⑤ 永恒特性（eterna1）：系统在开启以后再也不会死机或需要重启。
普适计算所涉及的技术是：移动通信技术、小型计算设备制造技术、小型计算设备上的操作系统技术及软件技术等。普适计算技术的主要应用方向是：嵌入式技术（除笔记本电脑和台式计算机外的具有CPU且能进行一定的数据计算的电器，如手机、MP3等都是嵌入式技术研究的方向）、网络连接技术（包括3G、ADSL等网络连接技术）、基于Web的软件服务构架（即通过传统的B/S构架，提供各种服务）。
近年来普适计算的典型研究项目有：① 麻省理工学院（MIT）的Oxygen项目，其寓意是未来计算像氧气一样无处不在并可自由获取。该项目将固定计算设备和移动设备通过可自动配置的网络连接起来。系统采用了包括休眠环境的自动转换等8种环境驱动技术。② Microsoft公司的Easy Living研究项目。该项目致力于智能环境的体系开发，涉及中间件、几何世界建模、定位感知、服务描述等技术，其关键特点是机器视觉、多传感器的自动和半自动校准，以及独立于设备的通信。③ AT&T实验室和英国剑桥大学合作的研究项目Sentient Computing，该项目通过用户接口、传感器及建立资源数据等手段，为系统提供基于用户和位置的数据更新能力，系统可无缝扩展到整个建筑物。④ 卡内基·梅隆大学的Aura项目，该项目强调普适计算的中间件技术和应用设计，包括3个子项目：Darwin智能网络——Aura的核心；Coda分布式文件管理系统；Odyssey为资源自适应提供操作系统支持。该系统可容纳桌面、手持和可穿戴系统。
普适计算把计算和信息融入人们的生活空间，使人们生活的物理世界与在信息空间中的虚拟世界融合成为一个整体。人们生活在其中，可随时、随地得到信息访问和计算服务，从根本上改变了人们对信息技术的思考，也改变了人们整个生活和工作的方式。
普适计算是对计算模式的革新，对它的研究虽然才刚刚开始，但它已显示了巨大的生命力，并带来了深远的影响。普适计算的新思维极大地活跃了学术思想，推动了对新型计算模式的研究。在此方向上已出现了许多诸如平静计算（Calm Computing）、日常计算（Everyday Computing）、主动计算（Proactive Computing）等的新研究方向。1.3.2 网格计算
网格计算最近作为一种分布式计算体系结构日益流行，它非常适合企业计算的需求。很多领域都正在采用网格计算解决方案来解决自己关键的业务需求。例如，金融服务已经广泛地采用网格计算技术来解决风险管理和规避问题，自动化制造业使用网格解决方案来加速产品的开发和协作，石油公司大规模采用网格技术来加速石油勘探并提高成功采掘的概率。随着网格计算的不断成熟，该技术在其他领域技术的应用也会不断增加。
与Internet类似，学术机构在开发构成网格计算基础的第一代技术和架构时，也走在了最前面。很多机构，如Globus Alliance、China Grid和e-Science Grid，都是第一批开始孵化并培育网格解决方案使其不断成熟并适用于商业解决方案的地方。
网格诞生于那些非常需要进行协作的研究和学术社区。研究中非常重要的一个部分是分发知识的能力——共享大量信息和帮助创建这些数据的计算资源的效率越高，可以实现的协作质量就越好，协作级别也越广泛。
在商业领域也存在这样需要分发知识能力的一种类似情况。网格计算也可以解决这些需求，这是由于在Web服务标准的推动下，业务过程和事务的集成的重要性继续提高。
目前，网格计算从学术界基于标准技术的早期界定和开发中获益良多，这些标准可以满足商业业务所需要的更实际、更稳健的实现需求。网络技术现在正以比微处理发展速度更快的速度发展。为了利用网络的优点，人们需要另外一种更有效利用微处理器的方法。这个新观点改变了历史上网络与处理器成本之间的平衡。网格计算就是解决这种差距的手段，它通过将分布式资源绑定在一起构成一个单一的虚拟计算机，从而改变了资源之间的平衡。这个资源丰富的虚拟计算机以及应用程序加速所带来的优点（从几周变成几天，从几天变成几小时，从几小时变成几分钟，依此类推），为商业业务逻辑提供了一个诱人的前景（不过这也可能会需要在通信业务实践中做出重大的变化，以价格变化最为突出）。
通常，人们都会混淆网格计算与基于集群的计算这两个概念，但实际上这两个概念之间有一些重要的区别。需要说明的是，集群计算实际上不能真正地被视为一种分布式计算解决方案，但对于理解网格计算与集群计算之间的关系是很有用的。
网格是由异构资源组成的。集群计算主要关注的是计算资源，网格计算则对存储、网络和计算资源进行了集成。集群通常包含同种处理器和操作系统，网格则可以包含不同供应商提供的运行不同操作系统的机器。IBM、Platform Computing、Data Synapse和United Devices 提供的网格工作负载管理软件，都可以将工作负载分发到类型和配置不同的多种机器上。
网格本质上就是动态的。集群包含的处理器和资源的数量通常都是静态的，而在网格上，资源则可以动态出现。资源可以根据需要添加到网格中，或从网格中删除。
网格天生就是在本地网、城域网或广域网上进行分布的。通常，集群物理上都包含在一个位置的相同地方，而网格可以分布在任何地方。集群互连技术可以产生非常低的网络延时，如果集群距离很远，这可能会导致产生很多问题。
网格提供了增强的可扩展性。物理邻近和网络延时限制了集群地域分布的能力，由于这些动态特性，网格可以提供很好的高可扩展性。
例如，最近IBM、United Devices和多个生命科学合作者完成了一个设计用来研究治疗天花的药品的网格项目。这个网格包括大约200万台个人计算机。使用常见的方法，这个项目很可能需要几年的时间才能完成——但是在网格上它只需要6个月。设想一下如果网格上已经有2000万台PC会是什么情况。极端地说，天大的项目可以在分钟级内完成。
集群和网格计算是相互补充的。很多网格都在自己管理的资源中采用了集群。实际上，网格用户可能并不清楚他的工作负载是在一个远程的集群上执行的。尽管网格与集群之间存在很多区别，但是这些区别使它们构成了一个非常重要的关系，因为集群在网格中总有一席之地——特定的问题通常都需要一些紧耦合的处理器来解决。然而，随着网络功能和带宽的发展，以前采用集群计算很难解决的问题现在可以使用网格计算技术解决。理解网格固有的可扩展性和集群提供的紧耦合互连机制所带来的性能优势之间的平衡是非常重要的。
网格计算和云计算有相似之处，特别是计算的并行与合作的特点，但它们的区别也是明显的，具体如下。
① 网格计算的思路是聚合分布资源，支持虚拟组织，提供高层次的服务，例如分布协同科学研究等。而云计算的资源相对集中，主要以数据中心的形式提供底层资源的使用，并不强调虚拟组织（VO）的概念。
② 网格计算用聚合资源来支持挑战性的应用，这是初衷，因为高性能计算的资源不够用，要把分散的资源聚合起来。后来到了2004年以后，逐渐强调适应普遍的信息化应用，特别是在中国，做的网格跟国外不太一样，即强调支持信息化的应用。但云计算从一开始就支持广泛企业计算、Web应用，普适性更强。
③ 在对待异构性方面，二者理念上有所不同。网格计算用中间件屏蔽异构系统，力图使用户面向同样的环境，把困难留给中间件，让中间件完成任务。而云计算实际上承认异构，用镜像执行，或者提供服务的机制来解决异构性的问题。当然，不同的云计算系统还不太一样，像Google一般使用比较专用的自己的内部平台来支持。
④ 网格计算以作业形式使用，在一个阶段内完成作业产生数据。而云计算支持持久服务，用户可以利用云计算作为其部分IT基础设施，实现业务的托管和外包。
⑤ 网格计算更多地面向科研应用，商业模型不清晰。而云计算从诞生开始就是针对企业商业应用，商业模型比较清晰。
⑥ 云计算是以相对集中的资源，运行分散的应用（大量分散的应用在若干较大的中心执行）。而网格计算则是聚合分散的资源，支持大型集中式应用（一个大的应用分到多处执行）。但从根本上说，从应对Internet应用的特征而言，它们是一致的，即Internet情况下支持应用，解决异构性、资源共享等问题。1.3.3 云计算
网络电影是随着网络技术流媒体的应用走入我们生活的一个方面。实际上，在线影视系统不是完整的云计算，因为它还有相当一部分的计算工作要在用户本地的客户端上完成，但是，这类系统的点播等方面的工作是在服务器上完成的，而且这类系统的数据中心及存储量是巨大的。
QQ、MSN这类互联网即时通信系统的主要计算功能，也是在这类服务提供商的数据中心完成的。不过，这类系统不能算是完整的云计算，因为它们通常会有客户端，而且用户的身份认证等计算功能是在用户的客户端本地完成的。但是，这类系统对于后台数据中心的要求不逊于一些普通的云计算系统，而且在使用这类服务时，不会关注这类服务的计算平台在何处。
SaaS是Software-as-a-Service（软件即服务）的简称，它是一种通过Internet提供软件的模式。在此模式下，用户不用再购买软件，而改用向提供商租用基于Web的软件，来管理企业的经营活动，且无须对软件进行维护，服务提供商会全权管理和维护软件。SaaS软件被认为是云计算的典型应用之一，搜索引擎其实就是基于云计算的一种应用方式。在使用搜索引擎时，并不考虑搜索引擎的数据中心在哪里，是什么样的。事实上，搜索引擎的数据中心规模是相当庞大的，而对于用户来说，搜索引擎的数据中心是无从感知的。所以，搜索引擎就是公共云的一种应用方式。“云计算”理论和尝试已经有10多年。近10年来，从.NET架构到按需计算（On-demand Computing）、效能计算（Utility Computing）、软件即服务（Software as a Service）、平台即服务（Platform as a Service）等新理念、新模式，其实都可视为企业对“云计算”的各异解读或“云计算”发展的不同阶段。
云计算最早为Google、Amazon等其他扩建基础设施的大型互联网服务提供商所采用。于是产生了一种架构：大规模扩展，水平分布的系统资源，抽象为虚拟IT服务，并作为持续配置、合用的资源进行管理。这种架构模式被George Gilder在其2006年10月于Wired杂志上发表的文章The Information Factories中进行了详细介绍。Gilder所描写的服务器庄园在架构上与网格计算相似，但其中网格用于松散结合的技术计算应用程序，而这种新的云模式则应用于互联网服务。
狭义云计算指IT基础设施的交付和使用模式，即通过网络以按需、易扩展的方式获得所需资源；广义云计算指服务的交付和使用模式，即通过网络以按需、易扩展的方式获得所需服务。这种服务可以是IT和软件、互联网等，也可是其他服务。云计算的核心思想，是将大量用网络连接的计算资源统一管理和调度，构成一个计算资源池向用户提供按需服务。提供资源的网络被称为“云”。“云”中的资源在使用者看来是可以无限扩展的，并且可以随时获取，按需使用，随时扩展，按使用付费。云计算的产业按三级分层：云软件、云平台、云设备。
云计算的所涉及的关键技术如下。（1）数据存储技术
为保证高可用、高可靠和经济性，云计算采用分布式存储的方式来存储数据，采用冗余存储的方式来保证存储数据的可靠性，即为同一份数据存储多个副本。另外，云计算系统需要同时满足大量用户的需求，并行地为大量用户提供服务。因此，云计算的数据存储技术必须具有高吞吐率和高传输率的特点。目前，各IT厂商多采用GFS或HDFS的数据存储技术。（2）数据管理技术
云计算系统对大数据集进行处理、分析，向用户提供高效的服务。因此，首先，数据管理技术必须能够高效地管理大数据集；其次，如何在规模巨大的数据中找到特定的数据，也是云计算数据管理技术所必须要解决的问题。云计算的特点是对海量的数据存储、读取后进行大量的分析，数据的读操作频率远大于数据的更新频率，云中的数据管理是一种读优化的数据管理。因此，云系统的数据管理往往采用数据库领域中列存储的数据管理模式，将表按列划分后存储。例如，谷歌采用BigTable的数据管理技术。（3）编程模式
为了使用户能更轻松地享受云计算带来的服务，让用户能利用该编程模型编写简单的程序来实现特定目的。云计算上的编程模型必须十分简单，必须保证后台复杂的并行执行和任务调度向用户和编程人员透明。云计算采用类似MAP-Reduce的编程模式。现在所有IT厂商提出的“云”计划中采用的编程模型，都是基于MAP-Reduce的思想开发的编程工具。
如今，Amazon、Google、IBM、Microsoft和Yahoo等公司是云计算的先行者。云计算领域的众多成功公司还包括Salesforce、Facebook、YouTube、MySpace等。
① Amazon使用弹性计算云（EC2）和简单存储服务（S3）为企业提供计算和存储服务。收费的服务项目包括存储服务器、带宽、CPU资源及月租费。
② Google当数最大的云计算使用者。Google搜索引擎就建立在分布于200多个地点、超过100万台服务器的支撑之上，这些设施的数量正在迅猛增长。Google地球、地图、Gmail、Docs等也同样使用了这些基础设施。
③ IBM在2007年11月推出了“改变游戏规则”的“蓝云”计算平台，为客户带来即买即用的云计算平台。它包括一系列的自动化、自我管理和自我修复的虚拟化云计算软件，使来自全球的应用可以访问分布式的大型服务器池，使得数据中心在类似于互联网的环境下运行计算。
④ 微软紧跟云计算步伐，于2008年10月推出了Windows Azure操作系统。Azure（译为“蓝天”）是继Windows取代DOS之后，微软的又一次颠覆性转型——通过在互联网架构上打造新云计算平台，让Windows真正由PC延伸到“蓝天”上。
用户通过计算机、笔记本电脑、手机等方式接入数据中心，可体验每秒10万亿次的运算能力；云计算提供了可靠的数据存储中心；对用户端的设备要求最低，使用起来很方便；数据共享，它可以轻松实现不同设备间的数据与应用共享；云计算为我们使用网络提供了几乎无限多的可能。
按照部署方式和服务对象将云计算划分为公共云、私有云和混合云三大主要类型。
① 当云计算按其服务方式提供给公众用户时，称其为公共云。公共云是由第三方（供应商）提供的云计算服务。公共云尝试为用户提供无后顾之忧的各种各样的IT资源，无论是软件、应用程序基础结构，还是物理基础结构，云提供商都负责安装、管理、部署和维护。最终用户只要为其使用的资源付费即可，根本不存在利用率低这一问题，但是这要付出一些代价，这些服务通常根据“配置惯例”提供，即根据适应最常见使用的情形这一思想提供，如果资源由用户直接控制，则配置选项一般是这些资源的一个较小子集。
② 私有云或称专属云，是指为企业内提供云服务（IT资源）的数据中心，这些云在商业企业和其他团体组织防火墙之内，由本企业管理，不对外开放。私有云可提供公共云所具有的许多功能。与传统的数据中心相比，主要不同点是：云数据中心可以支持动态灵活的基础设施，降低IT架构的复杂度，使各种IT资源得以整合、标准化，并且可以通过自动化部署提供策略驱动的服务水平管理，使IT资源更加容易地满足业务需求变化。相对公共云而言，私有云的用户完全拥有云中心的整个设施，如中间件、服务器、网络和磁盘阵列等，可以控制哪些应用程序在哪里运行，并且可以决定允许哪些用户使用云计算服务。由于私有云的服务对象是企业内部员工，可以减少公共云中必须考虑的诸多限制，如带宽、安全和法律法规的遵从性等问题。重要的是，通过用户范围控制和网络限制等手段，私有云可以提供更多的安全和私密等专属性的保证。
③ 混合云是公共云和私有云的混合，这类云一般由企业创建，而管理职责由企业和公共云提供商共同负责。混合云利用既在公共空间又在私有空间中的服务，用户可以通过一种可控的方式部分拥有或部分与他人共享。当公司既需要公共云又要私有云服务时，选择混合云比较合适。从这个意义上说，企业、机构可以列出服务目标和需要，然后相应地从公共或私有云中获取。结构完好的混合云可以为安全、至关重要的流程（如接收客户资金支付）及辅助业务流程（如员工工资单流程）等提供服务。
在未来5年内，云计算服务平均年增幅达26%，是传统IT行业增长速度的6倍。IDC预测，中国云计算4年内将产生1.1万亿元的市场，数量巨大的网络用户，尤其是中小企业用户，为云计算在国内的发展提供了很好的用户基础。云计算将大幅度提升中小企业信息化水平和市场竞争力。（1）对企业的影响
① 商业模式的转变，IT公司的商业模式将从软/硬件产品销售变为软/硬件服务的提供。
② 大大降低信息化基础设施建投入和信息管理系统运行维护费用。
③ 云计算将扩大软/硬件应用的外延，改变软/硬件产品的应用模式。
④ 产业链影响，传统的软/硬件开发及销售将被软/硬件服务所替代。（2）对个人的影响
① 不再依赖某一台特定的计算机来访问及处理自己的数据。
② 不用维护自己的应用程序，不需要购买大量的本地存储空间，用户端负载降低、硬件设备简单。
③ 现代化生活影响，云计算服务将实现从计算机到手机、汽车、家电迁移，把所有的家用电器中的计算机芯片联网，那时人们在任何地方就能轻松控制家里的电器设备。1.3.4 人工智能
人工智能（Artificial Intelligence，AI）的定义可以分为两部分，即“人工”和“智能”。“人工”比较好理解，争议性也不大。有时我们会考虑什么是人力所能及制造的，或者人自身的智能程度有没有高到可以创造人工智能的地步等，但总的来说，“人工系统”就是通常意义下的人工系统。“智能”涉及其他诸如意识（consciousness）、自我（self）、思维（mind）（包括无意识的思维）等问题。人唯一了解的智能是人本身的智能，这是普遍认同的观点。但是人们对自身智能的理解都非常有限，对构成人的智能的必要元素也了解有限，所以就很难定义什么是“人工”制造的“智能”。因此，人工智能的研究往往涉及对人的智能本身的研究。其他关于动物或其他人造系统的智能也普遍被认为是人工智能相关的研究课题。
人工智能目前在计算机领域内得到了更加广泛的重视，并在机器人、经济政治决策、控制系统、仿真系统中得到应用。
人工智能学科研究的主要内容包括知识表示、自动推理和搜索方法、机器学习和知识获取、知识处理系统、自然语言理解、计算机视觉、智能机器人、自动程序设计等。
知识表示是人工智能的基本问题之一，推理和搜索都与表示方法密切相关。常用的知识表示方法有逻辑表示法、产生式表示法。例如，语义网络表示法和框架表示法等。
常识，自然为人们所关注，已提出多种方法，如非单调推理、定性推理就是从不同角度来表达常识和处理常识的。
问题求解中的自动推理是知识的使用过程，由于有多种知识表示方法，相应地有多种推理方法。推理过程一般可分为演绎推理和非演绎推理。谓词逻辑是演绎推理的基础。结构化表示下的继承性能推理是非演绎性的。由于知识处理的需要，近几年来提出了多种非演泽的推理方法，如连接机制推理、类比推理、基于示例的推理、反绎推理和受限推理等。
搜索是人工智能的一种问题求解方法，搜索策略决定着问题求解的一个推理步骤中知识被使用的优先关系，可分为无信息导引的盲目搜索和利用经验知识导引的启发式搜索。启发式知识常由启发式函数来表示，启发式知识利用得越充分，求解问题的搜索空间就越小。典型的启发式搜索方法有A*、AO*算法等。近几年，搜索方法的研究开始注意那些具有百万节点的超大规模的搜索问题。
机器学习是人工智能的另一重要课题。机器学习是指在一定的知识表示意义下获取新知识的过程。按照学习机制的不同，主要包括归纳学习、分析学习、连接机制学习和遗传学习等。
知识处理系统主要由知识库和推理机组成。知识库存储系统所需要的知识，当知识量较大而又有多种表示方法时，知识的合理组织与管理是重要的。推理机在问题求解时，规定使用知识的基本方法和策略，推理过程中为记录结果或通信需设数据库或采用黑板机制。如果在知识库中存储的是某一领域（如医疗诊断）的专家知识，则这样的知识系统称为专家系统。为适应复杂问题的求解需要，单一的专家系统向多主体的分布式人工智能系统发展，这时知识共享、主体间的协作、矛盾的出现和处理将是研究的关键问题。
人工智能的第一大成就是下棋程序。在下棋程序中应用的某些技术，如向前看几步，把困难的问题分解成一些较容易的子问题，发展成为搜索和问题归纳这样的人工智能基本技术。今天的计算机程序已能够达到下各种方盘棋和国际象棋锦标赛的水平。但是，尚未解决包括人类棋手具有但尚不能明确表达的能力，如国际象棋大师们洞察棋局的能力。另一个问题是涉及问题的原概念，在人工智能中称为问题表示的选择，人们常能找到某种思考问题的方法，从而使求解变易从而解决该问题。到目前为止，人工智能程序已能知道如何考虑它们要解决的问题，即搜索解答空间，寻找较优解答。
逻辑推理是人工智能研究最持久的领域之一，其中特别重要的是要找到一些方法，只把注意力集中在一个大型的数据库的有关事实上，留意可信的证明，并在出现新信息时适时修正这些证明即可（对数学中臆测的题，定理寻找一个证明或反证，不仅需要有根据假设进行演绎的能力，而且许多非形式的工作，包括医疗诊断和信息检索，都可以和定理证明问题一样加以形式化）。因此，在人工智能方法的研究中，定理证明是一个极其重要的论题。
自然语言的处理是人工智能技术应用于实际领域的典型范例，经过多年艰苦努力，这一领域已获得了大量令人注目的成果。目前该领域的主要课题是：计算机系统如何以主题和对话情境为基础，注重大量常识——世界知识和期望作用，生成和理解自然语言。这是一个极其复杂的编码和解码问题。
信息获取和精化技术已成为当代计算机科学与技术研究中迫切需要研究的课题，将人工智能技术应用于这一领域的研究是人工智能走向广泛实际应用的契机与突破口。
专家系统是目前人工智能中最活跃、最有成效的一个研究领域，它是一种具有特定领域内大量知识与经验的程序系统。近年来，在“专家系统”或“知识工程”的研究中已出现了成功和有效应用人工智能技术的趋势。人类专家由于具有丰富的知识，所以才能达到优异的解决问题能力。那么计算机程序如果能体现和应用这些知识，也应该能解决人类专家所解决的问题，而且能帮助人类专家发现推理过程中出现的差错，现在这一点已被证实。所在矿物勘测、化学分析、规划和医学诊断方面，专家系统已经达到了人类专家的水平。成功的例子如：PROSPECTOR系统（用于地质学的专家系统）发现了一个钼矿沉积，价值超过1亿美元。DENDRL系统的性能已超过一般专家的水平，可供数百人在化学结构分析方面使用。MY CIN系统可以对血液传染病的诊断治疗方案提供咨询意见，经正式鉴定结果，对患有细菌血液病、脑膜炎方面的诊断和提供治疗方案已超过了这方面的专家。
目前，绝大多数人工智能系统都是建立在物理符号系统假设之上的。在尚未出现能与物理符号系统假设相抗衡的新的人工智能理论之前，无论是从设计原理还是从已取得的实验结果来看，Soar在探讨智能行为的一般特征和人类认知的具体特征的艰难征途上，都取得了有特色的进展或成就，处在人工智能研究的前沿。
20世纪80年代，以纳维尔（Newell）为代表的研究学者总结了专家系统的成功经验，吸收了认知科学研究的最新成果，提出了作为通用智能基础的体系结构Soar。目前的Soar已经显示出强大的问题求解能力。在Soar中已实现了30多种搜索方法，实现了若干知识密集型任务（专家系统），如RI（用产生式规则表达知识，采用正向推理的控制结构，用OPSS语言写成）等。Rooks提出了人工智能的一种新的途径，认为无须概念或者说无须符号表示，智能系统的能力也可以
试读结束[说明：试读内容隐藏了图片]