计算机科学概论

第0章　绪论 1

0.1　计算 1

0.2　算法 3

0.3　计算机 5

0.4　计算机学科 7

0.5　小结 7

第一部分　计算机系统结构

第1章　计算机组成与结构 11

1.1　计算机的发展历史 11

1.1.1　第一代计算机 11

1.1.2　第二代计算机 12

1.1.3　第三代计算机 12

1.1.4　第四代计算机 13

1.1.5　第五代计算机 13

1.2　数据的表示与基本运算 14

1.2.1　进位计数制及其转换 14

1.2.2　数值数据的表示 16

1.2.3　非数值数据的表示 24

1.2.4　数据信息的校验 27

1.2.5　数据的基本运算 28

.1.3　计算机系统的基本组成 33

1.3.1　计算机系统的硬件组成 34

1.3.2　计算机系统的软件组成 39

1.3.3　计算机系统的工作过程 41

1.4　计算机的特点与性能指标 43

1.4.1　计算机的特点 43

1.4.2　计算机的性能指标 44

1.5　小结 46

习题 48

第2章　操作系统与网络 52

2.1　操作系统的定义 52

2.2　操作系统的演化 53

2.3　操作系统的组成 54

2.3.1　进程管理器 54

2.3.2　存储管理器 56

2.3.3　文件管理器 57

2.3.4　设备管理器 58

2.3.5　用户界面 58

2.4　主流操作系统 58

2.5　计算机网络 59

2.5.1　计算机网络基础 60

2.5.2　互联网 63

2.6　网络模型和协议 65

2.6.1　osi模型 66

2.6.2　tcp/ip协议族 67

2.7　小结 69

习题 70

第3章　计算机系统 72

3.1　计算机系统的分类 72

3.1.1　flynn分类法 72

3.1.2　冯式分类法 74

3.2　计算机系统设计技术 76

3.2.1　计算机系统设计的定量原理 76

3.2.2　计算机系统设计者的主要任务 79

3.2.3　计算机系统设计的主要方法 80

3.3　微机系统 81

3.3.1　微机系统的三个层次 81

3.3.2　intel微处理器 82

3.4　微机的主机系统 84

3.4.1　微机主板 84

3.4.2　微机总线 86

3.5　pc的分类 88

3.5.1　台式机 88

3.5.2　便携机（笔记本pc） 88

3.5.3　个人数字助理（pda） 89

3.5.4　手持计算机（hpc） 90

3.6　小结 91

习题 91

第二部分 计算机软件

第4章　算法 95

4.1　算法的概念 95

4.1.1　概述 95

4.1.2　算法定义 96

4.1.3　算法的性质 96

4.1.4　算法的结构 97

4.2　算法的表示 99

4.2.1　原语 99

4.2.2　流程图 99

4.2.3　伪码 101

4.3　基本算法 105

4.3.1　求和 105

4.3.2　求积 105

4.3.3　求最大和最小 106

4.3.4　排序 106

4.3.5　查找 107

4.4　算法效率 108

4.4.1　算法的规模 109

4.4.2　时间复杂度 109

4.4.3　空间复杂度 110

4.5　小结 111

习题 111

第5章　程序设计语言 113

5.1　程序设计语言的演化 113

5.1.1　机器语言 114

5.1.2　符号语言 114

5.1.3　高级语言 115

5.2　程序设计语言的类型 117

5.2.1　过程化语言 117

5.2.2　函数式语言 118

5.2.3　逻辑式语言 118

5.2.4　面向对象语言 119

5.2.5　专用语言 120

5.3　程序设计的基本概念 121

5.3.1　标识符 122

5.3.2　变量与数据类型 122

5.3.3　常量和文字 123

5.3.4　表达式和赋值语句 124

5.3.5　控制语句 126

5.3.6　注释 128

5.4　程序单元 129

5.4.1　过程 129

5.4.2　参数 130

5.4.3　函数 130

5.4.4　输入与输出 131

5.5　程序设计语言的执行 132

5.5.1　程序翻译 132

5.5.2　链接程序 133

5.5.3　集成开发环境 134

5.6　高级话题 135

5.6.1　面向对象程序设计 135

5.6.2　程序设计语言的发展趋势 137

5.7　小结 138

习题 139

第6章　软件工程 141

6.1　软件工程概论 141

6.2　软件生命周期 141

6.2.1　软件生命周期思想 142

6.2.2　软件生命周期阶段 142

6.2.3　软件生命周期模型 144

6.3　结构化方法 145

6.3.1　结构化分析 145

6.3.2　结构化设计 146

6.3.3　结构化编程 147

6.4　面向对象方法 147

6.4.1　uml语言 147

6.4.2　面向对象分析（ooa） 147

6.4.3　面向对象设计（ood） 149

6.4.4　面向对象编程（oop） 149

6.4.5　设计模式 149

6.5　软件项目管理 150

6.5.1　cmm软件规范 150

6.5.2　软件需求管理 151

6.5.3　软件计划管理 151

6.5.4　软件质量管理 151

6.5.5　软件配置管理 152

6.6　文档 152

6.6.1　系统文档 152

6.6.2　用户文档 153

6.7　小结 153

习题 153

第三部分 数据组织

第7章　数据结构 157

7.1　基本概念和术语 157

7.1.1　什么是数据结构 157

7.1.2　数据的逻辑结构 159

7.1.3　数据的存储结构 159

7.1.4　数据的运算 160

7.2　数组 160

7.2.1　一维数组的定义 160

7.2.2　二维数组 161

7.2.3　二维数组的存储方式 161

7.3　记录 162

7.3.1　记录的概念 162

7.3.2　访问记录 163

7.4　链表 163

7.4.1　链表的定义及特点 163

7.4.2　链表的结点结构 163

7.4.3　单链表运算 164

7.4.4　循环链表 166

7.4.5　双（向）链表 166

7.5　堆栈 166

7.5.1　堆栈的定义及基本概念 166

7.5.2　栈的实现 167

7.5.3　栈的操作 167

7.5.4　栈的应用 168

7.6　队列 169

7.6.1　队列的定义 169

7.6.2　队列的实现 169

7.6.3　队列的基本操作 170

7.6.4　队列的应用 171

7.7　树 171

7.7.1　树的概念 172

7.7.2　树结构的基本术语 172

7.7.3　二叉树的基本概念 173

7.7.4　特殊的二叉树 173

7.7.5　二叉树的实现 174

7.7.6　二叉树的遍历 175

7.7.7　二叉树的应用 176

7.8　图 176

7.8.1　图的定义和术语 177

7.8.2　图的实现 178

7.8.3　图的基本操作 179

7.8.4　图的应用 180

7.9　小结 181

习题 182

第8章 文件结构 184

8.1 文件系统的任务 184

8.2 文件 184

8.2.1 文件命名 184

8.2.2 文件类型 185

8.2.3 文件属性 186

8.2.4 文件存取 187

8.2.5 编程概念 187

8.3 文件结构 189

8.3.1 顺序文件 189

8.3.2 索引文件 191

8.3.3 散列文件 192

8.3.4 编程概念 195

8.4 小结 195

习题 196

第9章 数据库结构 198

9.1 概论 198

9.1.1 引言 198

9.1.2 数据库管理系统（dbms） 200

9.1.3 数据库的三层抽象模式 200

9.2 数据库模型 201

9.2.1 实体关系 201

9.2.2 数据库模型 202

9.3 关系数据库与sql 205

9.3.1 关系数据库的设计 205

9.3.2 关系的操作 207

9.3.3 结构化查询语言（sql） 209

9.4 数据库访问授权 211

9.4.1 数据库的权限 212

9.4.2 授权传递与回收 212

9.4.3 权限管理的sql语句 212

9.5 几个高级话题 214

9.5.1 并发控制与完整性协议 214

9.5.2 数据库系统的体系结构 216

9.5.3 数据库的新应用 217

9.6 小结 220

习题 221

第四部分 高级主题

第10章 人工智能 225

10.1人工智能概述 225

10.1.1 什么是人工智能 225

10.1.2 人工智能的研究途径 226

10.1.3 人工智能技术的应用 228

10.2 推理与搜索 231

10.2.1 产生式系统 232

10.2.2 搜索树 234

10.2.3 盲目搜索与启发式搜索 235

10.3 人工神经网络 239

10.3.1 基本概念 239

10.3.2 一个特殊的应用 241

10.3.3 联想记忆 244

10.4 遗传算法 246

10.4.1 遗传算法概要 246

10.4.2 遗传算法的运算过程 248

10.5 人工智能的发展趋势 249

10.6 小结 250

习题 250

第11章 计算理论 254

11.1 问题与计算 254

11.1.1 可计算理论 254

11.1.2 计算复杂性理论 255

11.1.3 计算理论中的数学基础 255

11.2 图灵机 259

11.2.1 图灵机的基本原理 259

11.2.2 图灵机的形式定义 260

11.2.3 图灵机的变种 261

11.3 不可计算问题 261

11.3.1 停机问题 262

11.3.2 停机问题的证明 262

11.4 问题的求解难度 263

11.4.1 算法的复杂度 263

11.4.2 p问题和np问题 264

11.5 密钥系统 265

11.5.1 密钥系统概述 265

11.5.2 背包加密算法 266

11.6 小结 267

习题 268

第12章 编译技术 269

12.1 编译简介 269

12.1.1 编译器 269

12.1.2 编译器的作用 270

12.2 与编译器相关的程序 271

12.2.1 解释程序 271

12.2.2 汇编程序与连接程序 271

12.2.3 装入程序 272

12.2.4 预处理器与编辑器 272

12.2.5 调试程序与描述器 272

12.2.6 项目管理程序 273

12.3 翻译步骤 273

12.3.1 扫描程序 274

12.3.2 语法分析程序 274

12.3.3 语义分析程序 275

12.3.4 源代码优化程序 275

12.3.5 代码生成器 276

12.3.6 目标代码优化程序 277

12.4 编译器中的主要数据结构 277

12.4.1 记号 277

12.4.2 语法树 278

12.4.3 符号表 278

12.4.4 常数表 278

12.4.5 中间代码和临时文件 278

12.5 编译器结构中的其他问题 279

12.5.1 分析和综合 279

12.5.2 前端和后端 279

12.5.3 遍 280

12.5.4 语言定义和编译器 280

12.5.5 编译器的选项和界面 281

12.5.6 出错处理 281

12.6 自举与移植 281

12.7 tiny样本语言与编译器 283

12.7.1 tiny语言 284

12.7.2 tiny编译器 284

12.7.3 tm机 285

12.8 小结 286

习题 287

第13章 通信概论 289

13.1 计算机与通信的关系 289

13.1.1 计算机需要通信 289

13.1.2 通信需要计算机 289

13.1.3 通信发展简史 290

13.2 信息的度量与传输 291

13.2.1 信息量 291

13.2.2 信息的传输速率 291

13.3 通信系统的组成及分类 292

13.3.1 通信系统的组成 292

13.3.2 通信系统的分类 292

13.3.3 通信系统的质量指标 293

13.4 信号的传输及处理 293

13.4.1 模拟信号和数字信号的相互转换 293

13.4.2 调制与解调 294

13.4.3 复用 294

13.5 编码与解码技术 295

13.5.1 检错与纠错 295

13.5.2 压缩与解压缩 295

13.5.3 加密与解密 297

13.6 小结 298

习题 298

第14章 信息安全 299

14.1 信息安全的基本概念 299

14.2 密码技术 300

14.2.1 基本概念 300

14.2.2 密码技术的发展阶段 300

14.2.3 古典密码算法 301

14.2.4 对称密码算法 301

14.2.5 非对称密码算法 303

14.3 数字签名技术 304

14.3.1 单向散列函数 304

14.3.2 数字签名 305

14.3.3 数字签名的应用 306

14.4 防火墙技术 306

14.4.1 防火墙的概念 306

14.4.2 防火墙的作用 306

14.4.3 防火墙的基本类型 307

14.4.4 防火墙的优缺点 309

14.5 计算机病毒 309

14.5.1 计算机病毒的概念 310

14.5.2 计算机病毒分类 311

14.5.3 计算机病毒的检测与防治 311

14.6 小结 312

习题 313

第15章 计算机应用新领域 314

15.1 计算机的发展历程 314

15.2 计算机及其应用现状 316

15.2.1 计算机及其应用现状 316

15.2.2 计算机应用面临的问题 316

15.3 计算机的发展趋势与未来的计算机 319

15.4 计算机应用的新领域 321

15.4.1 多媒体娱乐 321

15.4.2 3d浸入式视频会议 322

15.4.3 网格计算 323

15.5 小结 323

习题 324

附录 326

计算机科学与技术学科知识体系简介 327

参考文献 332