内容简介

　　《算法设计与分析习题解答与学习指导/21世纪大学本科计算机专业系列教材》主要包含分治策略、动态规划、贪心法、回溯与分支限界等算法设计技术和分析方法以及问题计算复杂度的界定。在此基础上简要介绍了NP完全理论的基础知识以及近似算法、随机算法等。本书可作为《算法设计与分析》的教学辅导用书。

内页插图

目录

第1章基础知识
1.1内容提要
1.2习题
1.3习题解答与分析
第2章分治策略
2.1内容提要
2.2习题
2.3习题解答与分析
第3章动态规划
3.1内容提要
3.2习题
3.3习题解答与分析
第4章贪心法
4.1内容提要
4.2习题
4.3习题解答与分析
第5章回溯与分支限界
5.1内容提要
5.2习题
5.3习题解答与分析
第6章算法分析与问题的计算复杂度
6.1内容提要
6.2习题
6.3习题解答与分析
目录算法设计与分析习题解答与学习指导第7章NP完全性
7.1内容提要
7.2习题
7.3习题解答与分析
第8章近似算法
8.1内容提要
8.2习题
8.3习题解答与分析
第9章随机算法
9.1内容提要
9.2习题
9.3习题解答与分析
第10章处理难解问题的策略
10.1内容提要
10.2习题
10.3习题解答与分析
参考文献120第1章绪论
1.1计算机的基本概念
1.1.1什么是计算机
1.1.2计算机的分类
1.1.3计算机的特点
1.1.4计算机的用途
1.1.5计算机的发展
1.2计算机科学与技术学科的定义
1.2.1计算机科学与技术学科
1.2.2计算机科学与技术学科的根本问题
1.2.3计算机科学技术的研究范畴
1.3计算机科学与技术学科的教育
1.3.1技术的变化
1.3.2文化的变化
1.3.3教育观念的变化
1.4对计算机科学与技术学科毕业生的基本要求
1.4.1知识、能力和素质
1.4.2检验标准
1.4.3优秀学生
1.5信息化社会的挑战
1.5.1信息化社会的特征
1.5.2Internet与信息化社会
1.5.3信息化社会对计算机人才的需求
1.6计算机科学与技术学科知识体系
1.6.1知识体系的结构
1.6.2学科知识体系一览
1.6.3课程体系结构
本章小结
习题
第2章计算机的基础知识
2.1计算机的运算基础
2.1.1数制
2.1.2数制间的转换
2.1.3码制
2.1.4数的定点表示和浮点表示
2.1.5信息的几种编码
目录算法设计与分析习题解答与学习指导2.2逻辑代数基础
2.2.1命题逻辑基础
2.2.2逻辑代数基础
2.3计算机的基本结构与工作原理
2.3.1计算机硬件的基本结构
2.3.2计算机的工作原理
2.3.3计算机组织与系统结构
2.4程序设计基础
2.4.1程序设计语言
2.4.2结构化程序设计
2.4.3良好的程序设计风格
2.5算法基础
2.5.1解题的步骤
2.5.2什么是算法
2.5.3怎样衡量算法的优劣
2.6数据结构基础
2.6.1什么是数据结构
2.6.2几种典型的数据结构
本章小结
习题
第3章计算机硬件系统
3.1计算机系统
3.1.1冯·诺依曼体系结构
3.1.2计算机体系结构的发展
3.1.3计算机体系结构的评价标准
3.1.4微型计算机的硬件结构
3.2系统单元
3.2.1系统主板与时钟频率
3.2.2电子数据与指令
3.2.3微处理器
3.2.4主存储器
3.3输入输出系统
3.3.1输入输出原理
3.3.2扩展槽和适配卡
3.3.3系统总线
3.3.4端口与连接电缆
3.4输入设备
3.4.1键盘输入
3.4.2定点输入设备
3.4.3扫描输入设备
3.4.4语音输入设备
3.4.5其他输入设备
3.5输出设备
3.5.1显示器
3.5.2打印机
3.5.3绘图仪
3.5.4其他输出设备
3.6辅助存储设备
3.6.1硬盘
3.6.2光盘
3.6.3闪存和U盘
3.6.4磁带
3.7平板电脑
3.7.1平板电脑的概念
3.7.2平板电脑的发展
3.7.3平板电脑的芯片
3.7.4ARM微处理器应用
本章小结
习题
第4章计算机系统软件与工具软件
4.1程序设计语言翻译系统
4.1.1汇编语言翻译系统
4.1.2高级程序设计语言翻译系统
4.1.3高级程序设计语言解释系统
4.2操作系统
4.2.1什么是操作系统
4.2.2操作系统的功能
4.2.3操作系统的分类
4.2.4几种常用的操作系统
4.3工具软件
4.3.1下载软件
4.3.2FTP工具软件
4.3.3图像浏览软件
4.3.4截图软件
4.3.5PDF文件阅读软件
4.3.6词典工具
4.3.7文件压缩软件
4.3.8防毒软件
本章小结
习题
第5章计算机应用软件
5.1文字处理软件
5.1.1Word 2007概述
5.1.2文档的基本操作
5.1.3文档的排版
5.2电子表格软件
5.2.1Excel 2007基本知识
5.2.2工作表的建立
5.2.3工作表的编辑和格式化
5.2.4数据的图表化
5.2.5数据列表
5.2.6页面设置和打印
5.3文稿演示软件
5.3.1文稿演示软件的基本操作
5.3.2格式化和美化演示文稿
5.3.3动画、超链接和多媒体技术
5.3.4放映和打印演示文稿
本章小结
习题
第6章数据库系统及其应用
6.1数据库系统的基本概念
6.1.1数据库系统的定义
6.1.2数据管理技术的发展
6.1.3数据库系统的体系结构
6.1.4数据库管理系统
6.2结构化查询语言SQL概述
6.2.1SQL的产生与发展
6.2.2SQL的特点
6.2.3SQL的功能
6.3SQL的数据定义操作
6.3.1基本表的定义、修改与撤消
6.3.2索引的定义与撤消
6.4SQL的数据查询操作
6.4.1查询语句的一般形式
6.4.2简单查询
6.4.3多表查询
6.4.4嵌套查询
6.5SQL的数据更新操作
6.5.1插入操作
6.5.2删除操作
6.5.3修改操作
6.6几种新型的数据库系统
6.6.1分布式数据库
6.6.2多媒体数据库
6.6.3并行数据库
6.6.4演绎数据库
6.6.5主动数据库
6.6.6数据仓库
6.7数据库系统的应用
6.7.1信息与信息系统
6.7.2事务处理系统
6.7.3管理信息系统
6.7.4决策支持系统
6.7.5数据挖掘系统
本章小结
习题
第7章多媒体技术及其应用
7.1多媒体
7.1.1媒体的定义
7.1.2多媒体系统的主要特征
7.1.3多媒体系统的技术研究与应用开发
7.2超文本与超媒体
7.2.1多媒体文档
7.2.2超文本与超媒体的概念
7.2.3超文本与超媒体示例
7.2.4超文本系统的体系结构
7.3多媒体技术
7.3.1音频技术
7.3.2图像和图形
7.3.3视频和动画
7.3.4多媒体数据压缩技术
7.4多媒体通信系统技术
7.4.1多媒体通信系统体系结构
7.4.2H.323电视会议
7.4.3H.324可视电话
7.4.4IP电话
7.5多媒体创作工具
7.5.1音乐制作
7.5.2图形与图像制作
7.5.3动画制作
7.5.4视频影像处理
7.5.5多媒体图文制作
7.5.6Web创作
7.5.7文字的艺术修饰与多媒体演示文稿制作
7.6多媒体编辑语言
7.6.1HTML与DHTML
7.6.2JavaScript
7.6.3ASP
7.6.4PHP
7.6.5XML
7.7虚拟现实技术
7.7.1VRML
7.7.2虚拟现实技术的应用
7.8全息幻影
7.8.1全息幻影的概念
7.8.2360度全息幻影成像的特点
本章小结
习题
第8章计算机网络及其应用
8.1数据通信与连通性
8.1.1数据通信与连通性的定义
8.1.2连通方法
8.1.3用户端连接选项
8.1.4通信信道
8.1.5数据传输
8.2计算机网络体系结构
8.2.1计算机网络的定义
8.2.2计算机网络的术语
8.2.3计算机网络的结构
8.2.4计算机网络的互联设备
8.3计算机网络的分类和使用方式
8.3.1计算机网络的分类
8.3.2构架计算机网络的策略
8.4Internet与TCP/IP协议
8.4.1Internet的起源
8.4.2Internet的应用
8.4.3Internet的工作方式
8.4.4Internet中计算机的地址和命名
8.4.5Internet的连接
8.5Internet的服务功能
8.5.1E�瞞ail
8.5.2讨论组
8.5.3FTP文件传输
8.5.4Telnet远程登录
8.6Web和浏览器
8.6.1Web
8.6.2浏览器
8.6.3搜索引擎
8.7局域网的基础构架
8.7.1以太网
8.7.2令牌环网
8.7.3FDDI网
8.7.4ATM网
8.7.5无线局域网
8.8物联网
8.8.1物联网的基本概念
8.8.2物联网的组成
8.8.3物联网的相关技术
8.8.4物联网的应用模式与在我国的应用现状
8.9企业内部网和外联网
8.9.1内部网
8.9.2外联网
8.10集群与网格技术
8.10.1集群系统
8.10.2网格
本章小结
习题
第9章软件工程
9.1软件工程的概念
9.1.1为什么提出软件工程
9.1.2什么是软件工程
9.1.3软件生存周期
9.2软件开发模型
9.2.1瀑布模型
9.2.2渐增模型
9.2.3演化模型
9.2.4螺旋模型
9.2.5喷泉模型
9.2.6转换模型
9.2.7智能模型
9.3软件开发方法
9.3.1模块化方法
9.3.2结构化方法
9.3.3面向数据结构方法
9.3.4面向对象方法
9.3.5统一建模语言
9.3.6软件复用和构件技术
9.4软件过程和过程改进
9.4.1软件过程
9.4.2软件过程工程
9.4.3软件过程模型
9.4.4软件过程实施
9.4.5软件过程改进
9.4.6软件能力成熟度模型
本章小结
习题
第10章计算机信息安全技术
10.1计算机信息安全面临的威胁
10.1.1信息安全的重要性
10.1.2安全问题的现状
10.1.3计算机信息安全的定义及威胁信息安全的手段
10.1.4计算机信息安全的因素
10.1.5信息安全的策略与网络安全体系结构
10.2保密技术
10.2.1保密防护技术与泄密发现技术
10.2.2计算机系统的保密技术
10.2.3Internet中使用的密码技术
10.3防御技术
10.3.1防火墙的概念
10.3.2防火墙技术
10.3.3防火墙的结构
10.3.4身份鉴别和访问权限控制
10.4虚拟专用网
10.4.1什么是VPN
10.4.2VPN的分类及其用途
10.5审计与监控技术
10.5.1审计与监控的准则
10.5.2审计与监控
10.6计算机病毒
10.6.1计算机病毒的定义
10.6.2计算机病毒的发展
10.6.3计算机病毒的检测与防治
10.7无线传感器网络与智能卡的安全
10.7.1无线传感器网络的安全
10.7.2智能卡的安全
本章小结
习题
第11章计算机的应用领域
11.1计算机在制造业中的应用
11.1.1计算机辅助设计
11.1.2计算机辅助制造
11.1.3计算机集成制造系统
11.2计算机在商业中的应用
11.2.1零售业
11.2.2电子数据交换
11.2.3电子商务
11.3计算机在银行与证券业中的应用
11.3.1电子货币
11.3.2网上银行与移动支付
11.3.3证券市场信息化
11.4计算机在交通运输业中的应用
11.4.1交通监控系统
11.4.2坐席预定与售票系统
11.4.3全球卫星定位系统
11.4.4地理信息系统
11.4.5智能交通系统
11.4.6车载GPS智能导航系统
11.5计算机在办公自动化与电子政务中的应用
11.5.1办公自动化
11.5.2电子政务
11.6计算机在教育中的应用
11.6.1校园网
11.6.2远程教育
11.6.3计算机辅助教育
11.6.4计算机教学管理系统
11.7计算机在医学中的应用
11.7.1医学专家系统
11.7.2远程医疗系统
11.7.3数字化医疗仪器
11.7.4病员监护与健康护理
11.7.5医学研究
11.8计算机在科学研究中的应用
11.8.1科技文献的存储与检索
11.8.2科学计算
11.8.3计算机仿真
11.9计算机在艺术与娱乐中的应用
11.9.1音乐与舞蹈
11.9.2美术与摄影
11.9.3电影与电视
11.9.4多媒体娱乐与游戏
本章小结
习题
第12章职业道德与择业
12.1信息产业界的道德准则
12.1.1"绿色"信息产业
12.1.2计算机科学技术专业人员的道德准则
12.1.3企业道德准则
12.1.4计算机用户道德
12.1.5安全与隐私
12.2信息产业的法律法规
12.2.1与计算机知识产权有关的法律法规
12.2.2计算机软件保护
12.2.3软件资产价值评估
12.3专业岗位与择业
12.3.1与计算机科学与技术专业有关的职业种类
12.3.2与计算机科学与技术专业有关的职位
12.3.3终生学习
本章小结
习题
参考文献

前言/序言

　　作为问题求解和程序设计的重要基础，算法设计与分析在计算机科学与技术专业的课程体系中是一门重要的必修课。通过该课程的学习，不但为学习其他专业课程奠定了扎实的基础，而且对培养学生分析与解决问题的能力及计算思维有着不可替代的作用。ACMIEEEComputingCurricula2004与我国教育部计算机科学与技术专业教学指导委员会提出的《计算机科学与技术专业规范2005》都把该课程列入本专业的核心课程之一。
　　本书是国家高等教育“十一五”规划教材《算法设计与分析》(清华大学出版社，屈婉玲等)的辅助教材。主教材包括算法设计、算法分析、计算复杂性理论等重要内容。结合各种典型应用，主教材首先深入分析了各种算法设计技术的适用范围、设计步骤、正确性证明与复杂度的分析方法、改进算法的途径、局限性等，为从事实际问题求解的算法设计与分析工作在理论上提供清晰的、整体的思路和方法，并在此基础上介绍了问题难度的分析方法和计算复杂性理论的基本框架和一些重要的结果。
　　算法具有广泛的应用背景，习题量大，方法灵活。针对给定算法问题，在建模、设计技术选择、效率分析、改进途径等方面，初学者往往不知道如何着手。本书在多年算法教学的基础上精选了100多道典型的习题，给出了详尽的解答和分析，以期对初学者有所帮助。
　　与主教材配套，本书也分为10章。第1章是基础知识；第2～5章分别阐述分治策略、动态规划、贪心法、回溯与分支限界等算法设计技术；第6章介绍算法分析和问题的计算复杂度；第7章是NP完全性理论；第8章是近似算法；第9章是随机算法；第10章介绍处理难解问题的策略。每章首先对所涉及的重要知识点和方法进行总结，然后给出习题和解答。
　　本书前4章由屈婉玲编写，第5～6章由王捍贫编写，第7～8章由张立昂编写，第9～10章由刘田编写。
　　为了提高本书的质量，欢迎广大读者的批评和指正！
　　作者
　　2014年3月于北京大学

　　本书前4章由屈婉玲编写，第5～6章由王捍贫编写，第7～8章由张立昂编写，第9～10章由刘田编写。

很好

　　虽说丢了工作，可人还是得挣钱活着。胡子刘找街坊朋友东拼西凑弄了点儿钱，在家属院的门口开了一家水果店。我去跟他学武术，就是在那家店里。

这书质量不错，学起来挺有趣的

对于学习计算机算法有帮助

大师的书，没话说。屈老师是难得的大师级别的好老师。

作为问题求解和程序设计的重要基础，算法设计与分析在计算机科学与技术专业的课程体系中是一门重要的必修课。通过该课程的学习，不但为学习其他专业课程奠定了扎实的基础，而且对培养学生分析与解决问题的能力及计算思维有着不可替代的作用。ACMIEEEComputingCurricula2004与我国教育部计算机科学与技术专业教学指导委员会提出的《计算机科学与技术专业规范2005》都把该课程列入本专业的核心课程之一。

　当时有一个乘客喝醉了酒，在车上闹事，对周围的女乘客动手动脚的。有乘务员过来劝阻，结果被醉酒的乘客打了两巴掌。胡子刘在旁边一看这样下去不行，就也走上前去，想帮着把事态压一压。没曾想他这人高马大一脸络腮胡的乘务员往那儿一走，反倒把醉酒的乘客给惊着了。那人估计是觉得长成胡子刘这样儿的人一定会对他动手，想着不如先下手为强，于是一句话没说，朝着胡子刘面门就是一拳。胡子刘下意识地一闪，紧跟着自己的胳膊一伸、拳头一抬，拳头外侧就顺着乘客的太阳穴擦过去了。