本教材为国家级“十一五”规划教材《算法设计与分析》的辅助教材. 主教材的主要内容包括基础知识、分治策略、动态规划、贪心法、回溯与分支限界、算法分析与问题的计算複杂度、NP完全性、近似算法、随机算法、处理难解问题的策略等。

本书对主教材所阐述的算法设计技术和分析方法进行了总结，并对其中100多道典型的习题给出了详尽的解答和分析。

本书可作为大学计算机科学与技术、软体工程、信息安全、信息与计算科学等专业本科生和研究生辅助教学用书，也可作为从事实际问题求解的算法设计与分析工作的参考书。

第1章基础知识1

1.1内容提要1

1.2习题3

1.3习题解答与分析6

第2章分治策略10

2.1内容提要10

2.2习题11

2.3习题解答与分析14

第3章动态规划28

3.1内容提要28

3.2习题31

3.3习题解答与分析34

第4章贪心法47

4.1内容提要47

4.2习题50

4.3习题解答与分析52

第5章回溯与分支限界66

5.1内容提要66

5.2习题68

5.3习题解答与分析69

第6章算法分析与问题的计算複杂度74

6.1内容提要74

6.2习题75

6.3习题解答与分析76

目录算法设计与分析习题解答与学习指导第7章NP完全性82

7.1内容提要82

7.2习题83

7.3习题解答与分析85

第8章近似算法91

8.1内容提要91

8.2习题92

8.3习题解答与分析93

第9章随机算法96

9.1内容提要96

9.2习题97

9.3习题解答与分析97

第10章处理难解问题的策略103

10.1内容提要103

10.2习题104

10.3习题解答与分析104

参考文献120第1章绪论1

1.1计算机的基本概念1

1.1.1什幺是计算机1

1.1.2计算机的分类2

1.1.3计算机的特点3

1.1.4计算机的用途3

1.1.5计算机的发展5

1.2计算机科学与技术学科的定义7

1.2.1计算机科学与技术学科7

1.2.2计算机科学与技术学科的根本问题8

1.2.3计算机科学技术的研究範畴8

1.3计算机科学与技术学科的教育10

1.3.1技术的变化10

1.3.2文化的变化11

1.3.3教育观念的变化11

1.4对计算机科学与技术学科毕业生的基本要求12

1.4.1知识、能力和素质12

1.4.2检验标準12

1.4.3优秀学生13

1.5信息化社会的挑战13

1.5.1信息化社会的特徵13

1.5.2Internet与信息化社会14

1.5.3信息化社会对计算机人才的需求16

1.6计算机科学与技术学科知识体系17

1.6.1知识体系的结构17

1.6.2学科知识体系一览17

1.6.3课程体系结构22

本章小结23

习题23

第2章计算机的基础知识26

2.1计算机的运算基础26

2.1.1数制26

2.1.2数制间的转换28

2.1.3码制32

2.1.4数的定点表示和浮点表示33

2.1.5信息的几种编码35

目录算法设计与分析习题解答与学习指导2.2逻辑代数基础38

2.2.1命题逻辑基础39

2.2.2逻辑代数基础42

2.3计算机的基本结构与工作原理43

2.3.1计算机硬体的基本结构43

2.3.2计算机的工作原理46

2.3.3计算机组织与系统结构47

2.4程式设计基础48

2.4.1程式设计语言48

2.4.2结构化程式设计49

2.4.3良好的程式设计风格49

2.5算法基础50

2.5.1解题的步骤50

2.5.2什幺是算法51

2.5.3怎样衡量算法的优劣52

2.6数据结构基础53

2.6.1什幺是数据结构53

2.6.2几种典型的数据结构54

本章小结56

习题57

第3章计算机硬体系统59

3.1计算机系统59

3.1.1冯·诺依曼体系结构59

3.1.2计算机体系结构的发展60

3.1.3计算机体系结构的评价标準60

3.1.4微型计算机的硬体结构61

3.2系统单元62

3.2.1系统主机板与时钟频率62

3.2.2电子数据与指令62

3.2.3微处理器63

3.2.4主存储器65

3.3输入输出系统68

3.3.1输入输出原理68

3.3.2扩展槽和适配卡69

3.3.3系统汇流排70

3.3.4连线埠与连线电缆71

3.4输入设备72

3.4.1键盘输入72

3.4.2定点输入设备73

3.4.3扫描输入设备74

3.4.4语音输入设备76

3.4.5其他输入设备77

3.5输出设备78

3.5.1显示器78

3.5.2印表机79

3.5.3绘图仪80

3.5.4其他输出设备80

3.6辅助存储设备81

3.6.1硬碟81

3.6.2光碟83

3.6.3快闪记忆体和随身碟84

3.6.4磁带85

3.7平板电脑86

3.7.1平板电脑的概念86

3.7.2平板电脑的发展86

3.7.3平板电脑的晶片87

3.7.4ARM微处理器套用88

本章小结89

习题89

第4章计算机系统软体与工具软体92

4.1程式设计语言翻译系统92

4.1.1彙编语言翻译系统93

4.1.2高级程式设计语言翻译系统93

4.1.3高级程式设计语言解释系统94

4.2作业系统94

4.2.1什幺是作业系统95

4.2.2作业系统的功能95

4.2.3作业系统的分类96

4.2.4几种常用的作业系统97

4.3工具软体106

4.3.1下载软体106

4.3.2FTP工具软体108

4.3.3图像浏览软体108

4.3.4截图软体109

4.3.5PDF档案阅读软体109

4.3.6词典工具110

4.3.7档案压缩软体110

4.3.8防毒软体110

本章小结111

习题111

第5章计算机套用软体113

5.1文字处理软体113

5.1.1Word2007概述113

5.1.2文档的基本操作117

5.1.3文档的排版127

5.2电子表格软体138

5.2.1Excel2007基本知识138

5.2.2工作表的建立140

5.2.3工作表的编辑和格式化149

5.2.4数据的图表化153

5.2.5数据列表157

5.2.6页面设定和列印159

5.3文稿演示软体161

5.3.1文稿演示软体的基本操作161

5.3.2格式化和美化演示文稿164

5.3.3动画、超连结和多媒体技术167

5.3.4放映和列印演示文稿171

本章小结172

习题173

第6章资料库系统及其套用177

6.1资料库系统的基本概念177

6.1.1资料库系统的定义177

6.1.2数据管理技术的发展178

6.1.3资料库系统的体系结构179

6.1.4资料库管理系统180

6.2结构化查询语言SQL概述182

6.2.1SQL的产生与发展182

6.2.2SQL的特点182

6.2.3SQL的功能183

6.3SQL的数据定义操作183

6.3.1基本表的定义、修改与撤消184

6.3.2索引的定义与撤消187

6.4SQL的数据查询操作187

6.4.1查询语句的一般形式188

6.4.2简单查询189

6.4.3多表查询190

6.4.4嵌套查询191

6.5SQL的数据更新操作191

6.5.1插入操作191

6.5.2删除操作192

6.5.3修改操作193

6.6几种新型的资料库系统193

6.6.1分散式资料库193

6.6.2多媒体资料库194

6.6.3并行资料库194

6.6.4演绎资料库194

6.6.5主动资料库195

6.6.6数据仓库195

6.7资料库系统的套用196

6.7.1信息与信息系统196

6.7.2事务处理系统197

6.7.3管理信息系统197

6.7.4决策支持系统198

6.7.5数据挖掘系统199

本章小结200

习题200

第7章多媒体技术及其套用204

7.1多媒体204

7.1.1媒体的定义204

7.1.2多媒体系统的主要特徵205

7.1.3多媒体系统的技术研究与套用开发205

7.2超文本与超媒体206

7.2.1多媒体文档206

7.2.2超文本与超媒体的概念207

7.2.3超文本与超媒体示例207

7.2.4超文本系统的体系结构208

7.3多媒体技术209

7.3.1音频技术209

7.3.2图像和图形210

7.3.3视频和动画211

7.3.4多媒体数据压缩技术212

7.4多媒体通信系统技术213

7.4.1多媒体通信系统体系结构213

7.4.2H.323电视会议214

7.4.3H.324可视电话215

7.4.4IP电话215

7.5多媒体创作工具215

7.5.1音乐製作215

7.5.2图形与图像製作216

7.5.3动画製作217

7.5.4视频影像处理217

7.5.5多媒体图文製作218

7.5.6Web创作219

7.5.7文字的艺术修饰与多媒体演示文稿製作219

7.6多媒体编辑语言220

7.6.1HTML与DHTML220

7.6.2JavaScript220

7.6.3ASP221

7.6.4PHP221

7.6.5XML222

7.7虚拟现实技术223

7.7.1VRML223

7.7.2虚拟现实技术的套用225

7.8全息幻影225

7.8.1全息幻影的概念225

7.8.2360度全息幻影成像的特点225

本章小结226

习题226

第8章计算机网路及其套用229

8.1数据通信与连通性229

8.1.1数据通信与连通性的定义229

8.1.2连通方法229

8.1.3用户端连线选项230

8.1.4通信信道231

8.1.5数据传输232

8.2计算机网路体系结构233

8.2.1计算机网路的定义233

8.2.2计算机网路的术语234

8.2.3计算机网路的结构234

8.2.4计算机网路的互联设备237

8.3计算机网路的分类和使用方式237

8.3.1计算机网路的分类238

8.3.2构架计算机网路的策略238

8.4Internet与TCP/IP协定239

8.4.1Internet的起源240

8.4.2Internet的套用240

8.4.3Internet的工作方式240

8.4.4Internet中计算机的地址和命名241

8.4.5Internet的连线242

8.5Internet的服务功能242

8.5.1Email243

8.5.2讨论组244

8.5.3FTP档案传输245

8.5.4Telnet远程登录246

8.6Web和浏览器246

8.6.1Web246

8.6.2浏览器247

8.6.3搜寻引擎248

8.7区域网路的基础构架249

8.7.1乙太网249

8.7.2令牌环网251

8.7.3FDDI网252

8.7.4ATM网252

8.7.5无线区域网路253

8.8物联网253

8.8.1物联网的基本概念254

8.8.2物联网的组成255

8.8.3物联网的相关技术255

8.8.4物联网的套用模式与在我国的套用现状257

8.9企业内部网和外联网258

8.9.1内部网258

8.9.2外联网258

8.10集群与格线技术259

8.10.1集群系统259

8.10.2格线259

本章小结260

习题261

第9章软体工程263

9.1软体工程的概念263

9.1.1为什幺提出软体工程263

9.1.2什幺是软体工程264

9.1.3软体生存周期265

9.2软体开发模型265

9.2.1瀑布模型266

9.2.2渐增模型266

9.2.3演化模型267

9.2.4螺旋模型267

9.2.5喷泉模型268

9.2.6转换模型268

9.2.7智慧型模型268

9.3软体开发方法269

9.3.1模组化方法269

9.3.2结构化方法269

9.3.3面向数据结构方法270

9.3.4面向对象方法271

9.3.5统一建模语言272

9.3.6软体复用和构件技术274

9.4软体过程和过程改进276

9.4.1软体过程276

9.4.2软体过程工程277

9.4.3软体过程模型277

9.4.4软体过程实施279

9.4.5软体过程改进280

9.4.6软体能力成熟度模型280

本章小结283

习题284

第10章计算机信息安全技术285

10.1计算机信息安全面临的威胁285

10.1.1信息安全的重要性285

10.1.2安全问题的现状285

10.1.3计算机信息安全的定义及威胁信息安全的手段286

10.1.4计算机信息安全的因素287

10.1.5信息安全的策略与网路安全体系结构288

10.2保密技术289

10.2.1保密防护技术与泄密发现技术289

10.2.2计算机系统的保密技术290

10.2.3Internet中使用的密码技术293

10.3防御技术294

10.3.1防火墙的概念295

10.3.2防火墙技术295

10.3.3防火墙的结构297

10.3.4身份鉴别和访问许可权控制298

10.4虚拟专用网300

10.4.1什幺是VPN300

10.4.2VPN的分类及其用途301

10.5审计与监控技术302

10.5.1审计与监控的準则303

10.5.2审计与监控303

10.6计算机病毒305

10.6.1计算机病毒的定义305

10.6.2计算机病毒的发展305

10.6.3计算机病毒的检测与防治307

10.7无线感测器网路与智慧卡的安全308

10.7.1无线感测器网路的安全308

10.7.2智慧卡的安全309

本章小结310

习题310

第11章计算机的套用领域312

11.1计算机在製造业中的套用312

11.1.1计算机辅助设计312

11.1.2计算机辅助製造313

11.1.3计算机集成製造系统314

11.2计算机在商业中的套用315

11.2.1零售业316

11.2.2电子数据交换316

11.2.3电子商务317

11.3计算机在银行与证券业中的套用319

11.3.1电子货币319

11.3.2网上银行与移动支付320

11.3.3证券市场信息化321

11.4计算机在交通运输业中的套用321

11.4.1交通监控系统321

11.4.2坐席预定与售票系统322

11.4.3全球卫星定位系统322

11.4.4地理信息系统324

11.4.5智慧型交通系统325

11.4.6车载GPS智慧型导航系统326

11.5计算机在办公自动化与电子政务中的套用328

11.5.1办公自动化328

11.5.2电子政务328

11.6计算机在教育中的套用329

11.6.1校园网329

11.6.2远程教育330

11.6.3计算机辅助教育331

11.6.4计算机教学管理系统331

11.7计算机在医学中的套用331

11.7.1医学专家系统332

11.7.2远程医疗系统332

11.7.3数位化医疗仪器332

11.7.4病员监护与健康护理333

11.7.5医学研究333

11.8计算机在科学研究中的套用333

11.8.1科技文献的存储与检索333

11.8.2科学计算334

11.8.3计算机仿真335

11.9计算机在艺术与娱乐中的套用335

11.9.1音乐与舞蹈335

11.9.2美术与摄影335

11.9.3电影与电视336

11.9.4多媒体娱乐与游戏336

本章小结337

习题337

第12章职业道德与择业339

12.1信息产业界的道德準则339

12.1.1“绿色”信息产业339

12.1.2计算机科学技术专业人员的道德準则341

12.1.3企业道德準则342

12.1.4计算机用户道德342

12.1.5安全与隐私343

12.2信息产业的法律法规345

12.2.1与计算机智慧财产权有关的法律法规345

12.2.2计算机软体保护346

12.2.3软体资产价值评估348

12.3专业岗位与择业351

12.3.1与计算机科学与技术专业有关的职业种类351

12.3.2与计算机科学与技术专业有关的职位352

12.3.3终生学习353

本章小结354

习题355

参考文献357