算法设计与分析

出版时间:2012-1  出版社:高等教育出版社  作者:耿国华 编  页数:244  字数:330000  

内容概要

  本书内容共分四部分,第一部分算法概述,给出了算法的基本概念及算法分析的相关基础;第二部分六大经典算法的设计与分析技术,包括递归与分治策略、动态规划、贪心算法、回溯法、分支限界法、随机算法,从算法设计和算法分析的理论入手,根据各类算法的基本技术原理,给出算法的分析方法和证明过程,并将经典算法与应用问题相结合,提供多类别应用的范例;第三部分NP完全性理论,从计算本质的角度讨论计算模型的意义与作用,并分析NP完全问题的求解技术;第四部分神经网络智能算法,反映了近年来智能算法研究的新发展。各章附有大量算法示例和习题,这些解决问题的范例有利于学习者对书中内容的理解和应用。附录中编排了综合试题并附有参考答案提示,便于学习者总结与提高。
  《现代信息科学技术基础:算法设计与分析》可作为高等院校计算机算法设计与分析相关课程的本科生或研究生教学参考书,也可供计算机理论研究人员、计算机算法设计人员学习参考。

作者简介

  耿国华,教授,博士生导师,高等学校教学名师,享受国务院政府津贴,西北大学信息科学与技术学院副院长,教育部文科计算机基础教学指导委员会副主任,陕西省计算机学会副理事长,陕西省计算机教育学会副理事长,陕西省计算机学会人工智能与模式识别专业委员会副主任,西北大学计算机软件开发中心主任,长期从事智能信息处理、模式识别、信息可视化技术研究。

书籍目录

第1章 算法概述
1.1 算法的概念
1.1.1 算法的定义和特性
1.1.2 求解问题的基本过程
1.1.3 算法设计示例——计算最大公约数
1.2 算法设计与分析任务
1.3 算法分析准则
1.4 算法分析基础
1.4.1 常用数学术语
1.4.2 对数与指数
1.4.3 数学证明法
1.5 算法复杂性分析方法
1.5.1 复杂度函数
1.5.2 最好、最坏和平均情况
1.5.3 渐进分析
1.5.4 阶的证明方法
小结
习题
第2章 递归与分治策略
2.1 递归的概念
2.2 具有递归特性的问题
2.3 递归过程的设计与实现
2.4 递归算法分析
2.4.1 替换法
2.4.2 递归树法
2.4.3 主方法
2.5 分治法的基本思想
2.6 分治法的适用条件
2.7 分治法的基本步骤
2.8 分治法典型示例
2.8.1 n个数中求出最大/最小值
2.8.2 快速排序
2.8.3 大整数乘法
2.8.4 折半查找
2.8.5 矩阵乘法
小结
习题
第3章 动态规划
3.1 动态规划基础
3.1.1 动态规划的基本思想
3.1.2 动态规划的基本要素
3.1.3 动态规划的基本步骤
3.1.4 动态规划示例——组合数问题
3.2 线性动态规划——合唱队形问题
3.3 区域动态规划——矩阵连乘问题(最佳次序)
3.4 背包动态规划——0-1背包问题
3.5 树形动态规划——最优二叉搜索树
小结
习题
第4章 贪心算法
4.1 贪心算法基础
4.1.1 贪心算法的基本思想
4.1.2 贪心算法的基本要素
4.1.3 贪心算法适合的问题
4.1.4 贪心算法的基本步骤
4.1.5 贪心算法示例——背包问题
4.2 汽车加油问题
4.3 最优服务次序问题
4.4 区间相交问题
4.5 单源最短路径
小结
习题
第5章 回溯法
第6章 分支限界法
第7章 随机算法
第8章 NP完全性理论
第9章 神经智能算法
附录 试题及参考答案
参考文献

章节摘录

版权页:插图:递归与迭代是计算机科学中重要的数学理论方法,也是程序设计的本质技术。当计算机求解的问题规模较大,直接求解困难甚至根本没办法直接求解,往往会考虑能否将该问题划分为若干子问题,对这些子问题进行求解。如果被划分后得到的子问题规模仍然不够小,则可以将每个子问题继续划分为更小的子问题,以此类推,直到划分得到的问题规模足够小,能够较容易求出解为止。根据上述分治法的指导思想,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到容易求解。由于分治法产生的子问题往往是原问题的较小模式,子问题与原问题的类型一致,因此,在分治法中经常使用递归技术求解问题,递归与分治之间是相辅相成的。2.1 递归的概念递归是计算机科学的一个重要概念,是程序设计中的一种有效的方法,在程序设计语言中被广泛应用。它是指函数、过程、子程序在运行过程中直接或间接调用自身而产生的重入现象。采用递归编写程序能使程序变得简洁和清晰,使人容易理解。递归算法描述简捷,结构清晰,算法的正确性比较容易证明。但是,递归算法的执行效率低,空间消耗多,有时还会受到一些软、硬件环境条件限制,不能使用递归技术,因此,在某些时候.还需要将递归算法转换为非递归算法。

编辑推荐

《算法设计与分析》是现代信息科学技术基础。

图书封面

评论、评分、阅读与下载


    算法设计与分析 PDF格式下载


用户评论 (总计1条)

 
 

  •   估计是为了评职称凑数的著作~~
 

250万本中文图书简介、评论、评分,PDF格式免费下载。 第一图书网 手机版

京ICP备13047387号-7