计算机导论——计算思维和应用技术

本书分为3部分： 第1部分为计算工具，主要讨论计算工具和技术特征以及程序语言和软件开发； 第2部分为计算思维，主要介绍计算思维和人工智能、算法基础和数据结构； 第3部分为计算技术，讨论信息编码和逻辑运算、硬件结构和操作系统、网络通信和信息安全、应用技术和学科特征。

本书是高等学校计算机课程入门教材，主要面向理工科专业学生。教材在保持学科广度的同时，兼顾到不同专业领域计算机应用技术的讨论。本书力图使学生对计算机科学有一个总体了解，并希望在这个基础上了解和掌握计算思维的方法，并与专业课程结合，努力理解和解决各自专业领域的问题。

目录

第1部分计 算 工 具

第1章计算工具和技术特征

1.1计算机的发展

1.1.1早期的计算工具

1.1.2中世纪的计算机

1.1.3现代计算机发展

1.1.4微型计算机发展

1.2计算机的类型

1.2.1类型与特点

1.2.2大型计算机

1.2.3微型计算机

1.2.4嵌入式计算机

1.3计算机的特征

1.3.1计算机技术特征

1.3.2软件特征与类型

1.3.3计算机人机界面

1.3.4计算机技术指标

1.4计算机新技术

1.4.1物联网技术发展

1.4.2云计算技术发展

1.4.3大数据技术发展

1.4.4计算社会学发展

1.4.5志愿者计算项目

习题1

第2章程序语言和软件开发

2.1程序语言特征

2.1.1程序语言的演化

2.1.2程序语言的类型

2.1.3入门级编程语言

2.1.4编程环境与平台

2.1.5程序解释与编译

2.2程序基本结构

2.2.1C程序结构

2.2.2数据类型

2.2.3关键字

2.2.4表达式

2.2.5控制结构

2.3程序语言介绍

2.3.1面向对象编程语言Java

2.3.2动态程序设计语言Python

2.3.3数据统计编程语言R

2.3.4逻辑推理编程语言Prolog

2.3.5并行编程接口规范MPI

2.4软件开发方法

2.4.1编程语言评估

2.4.2软件工程特征

2.4.3程序设计原则

2.4.4软件测试方法

2.4.5软件开发模型

习题2

第2部分计 算 思 维

第3章计算思维和人工智能

3.1计算思维

3.1.1计算思维的特征

3.1.2数学思维的概念

3.1.3工程思维的概念

3.1.4计算机解题方法

3.1.5数学模型的构建

3.2建模案例

3.2.1囚徒困境： 博弈策略建模

3.2.2机器翻译： 统计语言建模

3.2.3平均收入： 安全计算建模

3.2.4网页搜索： 布尔检索建模

3.2.5生命游戏： 细胞自动机建模

3.3解题方法

3.3.1枚举法

3.3.2分治法

3.3.3贪心法

3.3.4动态规划

3.3.5筛法求素数

3.3.6随机化算法

3.4图灵机与人工智能

3.4.1图灵机的结构与原理

3.4.2不完备性与可计算性

3.4.3停机问题与NP问题

3.4.4图灵测试与人工智能

3.4.5人工智能研究与应用

习题3

第4章算法基础和数据结构

4.1算法的特征

4.1.1算法的定义

4.1.2算法的表示

4.1.3算法的评估

4.1.4算法复杂度

4.2递归与迭代

4.2.1递归算法思想

4.2.2迭代算法思想

4.2.3递归与迭代的区别

4.2.4递归与迭代的应用

4.3排序与查找

4.3.1冒泡排序

4.3.2插入排序

4.3.3快速排序

4.3.4二分查找

4.3.5索引查找

4.4数据结构

4.4.1基本概念

4.4.2线性结构

4.4.3树形结构

4.4.4图形结构

4.4.5文件结构

习题4

第3部分计 算 技 术

第5章信息编码和逻辑运算

5.1数值信息编码

5.1.1二进制编码特征

5.1.2不同数制的转换

5.1.3二进制整数编码

5.1.4二进制小数编码

5.1.5二进制补码运算

5.2非数值信息编码

5.2.1英文字符编码

5.2.2中文字符编码

5.2.3国际字符编码

5.2.4声音的数字化

5.2.5图像的数字化

5.3压缩与纠错编码

5.3.1信息量的度量

5.3.2无损压缩编码

5.3.3有损压缩技术

5.3.4信号纠错编码

5.4逻辑运算与应用

5.4.1基本逻辑运算

5.4.2命题逻辑演算

5.4.3谓词逻辑演算

5.4.4逻辑运算应用

习题5

第6章硬件结构和操作系统

6.1计算机系统结构

6.1.1冯·诺依曼结构

6.1.2计算机集群结构

6.1.3集群分布式计算Hadoop

6.1.4网格分布式计算BOINC

6.1.5新型计算机研究

6.2计算机工作原理

6.2.1层次模型

6.2.2数据存储

6.2.3数据传输

6.2.4数据运算

6.2.5指令系统

6.3计算机硬件系统

6.3.1主机结构

6.3.2CPU部件

6.3.3主板部件

6.3.4存储设备

6.3.5集成电路

6.4计算机操作系统

6.4.1操作系统类型

6.4.2微机操作系统Windows

6.4.3网络操作系统Linux

6.4.4手机操作系统Android

6.4.5操作系统功能

6.4.6程序执行过程

6.4.7系统引导过程

习题6

第7章网络通信和信息安全

7.1网络原理

7.1.1网络基本类型

7.1.2网络通信协议

7.1.3网络体系结构

7.1.4网络通信技术

7.1.5无线网络技术

7.2网络服务

7.2.1服务模型

7.2.2网络地址

7.2.3域名系统

7.2.4因特网服务

7.2.5HTML语言

7.3安全防护

7.3.1安全问题

7.3.2黑客攻击

7.3.3安全体系

7.3.4隔离技术

7.3.5防火墙技术

7.4信息加密

7.4.1加密原理

7.4.2RSA加密

7.4.3密码破解

7.4.4数字认证

7.4.5安全计算

习题7

第8章应用技术和学科特征

8.1数据库技术应用

8.1.1数据库的组成

8.1.2数据库的操作

8.1.3SQL语言特征

8.1.4NoSQL数据库

8.1.5嵌入式数据库SQLite

8.2图形处理技术

8.2.1三维图形技术

8.2.2动画工作原理

8.2.3数字图像处理

8.2.4信息的可视化

8.3常用应用软件

8.3.1常用办公软件Office

8.3.2图像处理软件Photoshop

8.3.3网站设计软件Dreamweaver

8.3.4系统仿真软件MATLAB

8.4学科特征和职业规范

8.4.1学科基本特征

8.4.2学科经典问题

8.4.3知识产权保护

8.4.4职业道德规范

8.4.5职业卫生健康

习题8

参考文献

附录A常用数学符号和英文缩写读音

计算思维通过广义的计算来描述各类自然过程和社会过程，从而解决各个学科的问题。本章主要从“复杂性、抽象、数学建模、仿真、可计算性”等计算思维概念，讨论各种问题的建模方法、基本算法思想以及人工智能等内容。

3.1计算思维

3.1.1计算思维的特征

理论科学、实验科学和计算科学作为科学发现的三大支柱，推动着人类文明进步和科技发展。与三大科学方法对应的是三大科学思维： 理论思维、实验思维和计算思维。

1. 计算工具与思维方式的相互影响

计算机科学家迪科斯彻(Edsger Wybe Dijkstra)说过： “我们使用的工具影响着我们的思维方式和思维习惯，从而也将深刻地影响着我们的思维能力。”计算的发展也影响着人类的思维方式，从最早的结绳计数，发展到目前的电子计算机，人类思维方式发生了相应的改变。如计算生物学改变着生物学家的思维方式； 计算机博弈论改变着经济学家的思维方式； 计算社会科学改变着社会学家的思维方式； 量子计算改变着物理学家的思维方式。计算思维已成为利用计算机求解问题的一个基本思维方法。

2. 计算思维的定义

“计算思维”是美国卡内基梅隆大学(CMU)周以真(Jeannette M. Wing)教授提出的一种理论。周以真教授认为： 计算思维是运用计算机科学的基础概念去求解问题、设计系统和理解人类行为，它涵盖了计算机科学的一系列思维活动。

国际教育技术协会(ISTE)和计算机科学教师协会(CSTA)2011年给计算思维做了一个具可操作性的定义，即计算思维是一个问题解决的过程，该过程包括以下特点：

(1) 拟定问题，并能够利用计算机和其他工具的帮助来解决问题；

(2) 要符合逻辑地组织和分析数据；

(3) 通过抽象，如模型、仿真等，再现数据；

(4) 通过算法思想(一系列有序的步骤)，支持自动化的解决方案；

(5) 分析可能的解决方案，找到最有效的方案，并且有效地应用这些方案和资源；

(6) 将该问题的求解过程进行推广，并移植到更广泛的问题中。

3. 计算思维的特征

周以真教授在《计算思维》论文中，提出了以下计算思维的基本特征。

计算思维是人的，不是计算机的思维方式。计算思维是人类求解问题的思维方法，而不是要使人类像计算机那样思考。

计算思维是数学思维和工程思维的相互融合。计算机科学本质上来源于数学思维，但是受计算设备的限制，迫使计算机科学家必须进行工程思考，不能只是数学思考。

计算思维建立在计算过程的能力和限制之上。需要考虑哪些事情人类比计算机做得好？哪些事情计算机比人类做得好？最根本的问题是： 什么是可计算的？

为了有效地求解一个问题，我们可能要进一步问： 一个近似解是否就够了呢？是否允许漏报和误报？计算思维就是通过简化、转换和仿真等方法，把一个看起来困难的问题，重新阐释成一个我们知道怎样解决的问题。

计算思维采用抽象和分解的方法，将一个庞杂的任务分解成一个适合计算机处理的问题。计算思维是选择合适的方式对问题进行建模，使它易于处理。在我们不必理解系统每一个细节的情况下，就能够安全地使用或调整一个大型的复杂系统。

根据以上周以真教授的分析可以看到： 计算思维以设计和构造为特征。计算思维是运用计算机科学的基本概念，进行问题求解、系统设计的一系列思维活动。

3.1.2数学思维的概念

计算思维包含哪些最基本的概念？目前专家们尚无统一的意见。一般来说，计算思维包含数学思维和工程思维两个部分。数学思维的基本概念有复杂性、抽象、模型、算法、数据结构、可计算性、一致性和完备性等。

1. 复杂性

大问题的复杂性包括二义性(如语义理解等)、不确定性(如哲学家就餐问题、混沌问题等)、关联(如操作系统死锁问题、大学教师排课问题等)、指数爆炸(如汉诺塔问题、旅行商问题等)、悖论(如罗素理发师悖论、图灵停机问题等)等概念。计算机科学家迪科斯彻曾经指出“编程的艺术就是处理复杂性的艺术”。

第2版前言

“计算机导论”是理工科专业学生的一门计算机基础课程，课程通过全面介绍计算机科学技术基础知识，揭示计算学科的特色，介绍该学科各分支的主要知识。教材在第1版的基础上进行了全面修订，改变的主要方面，一是全面采用Python语言进行案例示范，二是增强了学科领域和技术开发方面的内容，三是描述语言更加严谨。

写作目标

本教材编写原则是： 学习基础知识，开阔专业视野。教材始终贯穿以下主线。

(1) 计算无所不在。教材尽量从商业领域、社会科学领域、日常生活中选取不同的案例来讨论计算的普遍性。例如，囚徒困境问题、热门检索词排名、平均工资计算问题等，都从不同侧面讨论了计算的普遍性。

(2) 强调计算思维。计算思维是一种解决问题的方法和思路，教材强调利用计算思维的方法讨论和分析问题。例如在数学建模讨论中，着重讲解利用计算思维进行建模的方法，而不是数学模型的理论推导和技术实现细节。教材尽量通过大量的图表和案例讲解计算机科学的基础知识。利用计算思维分析问题的主线在程序设计、信息编码、体系结构、操作系统、网络通信、信息安全等内容中反复体现。

(3) 广度优先的知识框架。不同专业的学生如果想融入目前的信息化社会，需要具备宽泛的计算机背景知识和利用计算思维解决问题的能力。教材提供了对计算机科学领域的全面技术剖析，介绍了在社会各领域利用计算思维解决问题的不同案例。教材对计算机专业的讨论范围很广泛，目的是让学生在研究树木之前，能够先看一看森林的概貌，以后走到蜿蜒小路时不至于会迷路。

主要内容

全书包含3部分，主要内容如下：

第1部分为计算工具，主要讨论计算机技术发展历程和程序语言结构，这一部分介绍了计算技术的历史发展阶段、计算机的基本类型和技术特征、计算机新技术的发展方向，以及程序的基本结构、常用编程语言、并行程序设计方法、软件开发方法等。

第2部分为计算思维，主要介绍计算思维的基本概念和算法思想，从不同角度介绍了数学建模的案例、计算机解题的主要方法、图灵机与可计算性、人工智能，以及常用算法等。

第3部分为计算技术，主要讨论计算机主要技术和工作原理，介绍信息编码的基本方法、数理逻辑、计算机硬件基本结构、操作系统主要功能和结构、网络通信基本原理、信息安全防护和加密技术，以及数据库技术、图形处理技术、常用应用软件、计算学科特征、专业人员职业道德、计算机使用中的卫生保健知识等。

几点说明

(1) 内容编排。尽管本书有自己的结构体系，但各个主题在很大程度上是相对独立的，而且各个章节内容的多少也刻意保持了大致相同。教师完全可以根据不同专业教学的要求，重新调整讲授内容和讲授顺序。在教材编写中，本书大致遵循每章讨论1~2个专业领域、2~4个技术主题。在内容编排中，教材对一些理论性问题尽量用图、表、案例的形式加以说明，试图帮助读者加深对所述内容的理解。

(2) 一家之言。在教材编写中，作者力图以严肃认真的态度进行分析与讨论，但是不免会掺杂一些作者不成熟的看法与意见。例如，计算机类型的划分、第一台电子计算机的发明、对冯·诺依曼(Van Nenmann)计算机结构的阐述等内容，可能与目前的主流技术观点有所不同。这都是作者一些不成熟的看法，是一家之言，期望专家学者们批评指正。

(3) 教学建议。在进行课程教学时，建议对讨论的问题不要拘泥于计算机专业领域，而是需要更多地加入与计算思维相关的经济学、生物学、医学、物理学等内容和案例，让学生在感受到计算思维无处不在的同时，领悟到计算机求解各类问题的方法。建议理论课讲授基本原理和概念，实验课则落实怎么做。

(4) 编程语言。教材对算法说明和程序实现采用Python作为主要描述语言，由于教材并没有详细介绍程序设计的语法规则和设计技巧，因此教材中的程序案例都进行了详细的注释，这些注释的目的是说明算法思想或语法规则。在工程实际中，程序注释不需要说明语法规则，而是告诉别人你的意图和想法，增强程序的易读性和可维护性。

(5) 英文缩写。书中涉及的英文缩写名词较多，为了避免烦琐，便于阅读，本书对大部分容易理解的英语缩写名词只注释中文词义，如CPU(中央处理单元)； 对于容易引起误解的外国人名以及英文缩写等，一般随书注释英文全称和中文说明，如ABC(AtanasoffBerry Computer，阿塔纳索夫贝瑞计算机)等。

本教材由易建勋编著，参加编写工作的还有邓江沙、唐良荣、廖寿丰、刘珺、周玮、范丰仙、甘文等老师。因特网技术资料给作者提供了极大帮助，非常感谢这些作者。

坦率地说，教材中不可避免地带有作者的个人见解，因为作者从事技术开发和教学工作多年，可能有意无意地会抬高工程技术领域，而忽视计算机科学的其他分支。尽管我们非常认真努力地写作，但水平有限，书中难免有疏漏之处，恳请各位同仁和广大读者给予批评指正。您可以通过电子邮件地址（Email： yjxcs@163.com）与作者进行联系。

易建勋

2017年5月20日