





定价:23元
印次:1-9
ISBN:9787302129424
出版日期:2006.06.01
印刷日期:2012.12.20
图书责编:袁勤勇
图书分类:教材
算法设计与分析是计算机科学技术中处于核心地位的一门专业基础课,越来越受到重视。本书将计算机经典问题和算法设计技术很好地结合起来,系统地介绍了算法设计技术及其在经典问题中的应用。全书共12章,第1章介绍了算法的基本概念和算法分析方法,第2章从算法的观点介绍了NP完全理论,第3章~第11章分别介绍了蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法等算法设计技术,第12章基于图灵机计算模型介绍了计算复杂性理论。每章均附有一篇阅读材料,以通俗易懂的笔触介绍了算法领域的一些最新研究成果。书中所有算法均给出了伪代码,大部分算法还给出了C++描述,书中所有问题均给出了若干应用实例。
算法设计与分析是计算机科学技术中处于核心地位的一门专业基础课,越来越受到重视,CC2001和CCC2002都将“算法和复杂性”列为主领域,将算法设计策略、基本可计算性理论、P和NP问题类等算法设计技术和复杂性分析方法列为核心知识单元。 无论是计算科学还是计算实践,算法都在其中扮演着重要角色,算法被公认为是计算机科学的基石。翻开重要的计算机学术刊物,算法都占有一席之地,没有算法,计算机程序将不复存在。对于计算机专业的学生,学会读懂算法、设计算法,应该是一项最基本的要求,而发明算法则是计算机学者的最高境界。 提高学生的问题求解能力是高等教育的一个主要目标,在计算机科学的课程体系中,安排一门关于算法设计与分析的课程是非常必要的,因为这门课程能够引导学生的思维过程,告诉学生如何应用一些特定的算法设计策略来解决问题。学习算法还能够提高学生分析问题的能力。算法可以看作是解决问题的一类特殊方法——它不是问题的答案,而是经过精确定义的、用来获得答案的求解过程。因此,无论是否涉及计算机,特定的算法设计技术都可以看作是问题求解的有效策略。 本书将计算机经典问题和算法设计技术很好地结合起来,系统地介绍了算法设计技术及其在经典问题中的应用。通过同一算法设计技术在不同问题中的应用进行比较,牢固掌握算法设计技术的基本策略;通过不同的算法设计技术在同一问题中的应用进行比较,更容易体会到算法设计技术的思想方法,收到融会贯通的效果。所以,本书采用了模块化的设计思想,读者除了按本书组织的章节学习外,还可以将每种算法设计技术的问题提取出来,比较解决相同问题的不同解决方法。随着本书内容的不断展开,读者也将感受到...
1.1算法的基本概念1
1.1.1为什么要学习算法1
1.1.2算法及其重要特性3
1.1.3算法的描述方法4
1.1.4算法设计的一般过程5
1.1.5重要的问题类型8
1.2算法分析10
1.2.1渐进符号10
1.2.2最好、最坏和平均情况12
1.2.3非递归算法的分析13
1.2.4递归算法的分析14
1.2.5算法的后验分析16
1.3实验项目——求最大公约数18
阅读材料——人工神经网络与BP算法19
习题121
第2章NP完全理论25
2.1下界25
2.1.1平凡下界26
2.1.2判定树模型26
2.1.3最优算法27
2.2算法的极限28
2.2.1易解问题与难解问题28
2.2.2实际问题难以求解的原因30
2.2.3不可解问题32
2.3P类问题和NP类问题34
2.3.1判定问题34
2.3.2确定性算法与P类问题35
2.3.3非确定性算法与NP类问题35
2.4NP完全问题36
2.4.1问题变换与计算复杂性归约37
2.4.2NP完全问题的定义38
2.4.3基本的NP完全问题40
2.4.4NP完全问题的计算机处理41
2.5实验项目——SAT问题43
阅读材料——遗传算法43
习题247算法设计与分析目录
第3章蛮力法49
3.1蛮力法的设计思想49
3.2查找问题中的蛮力法50
3.2.1顺序查找50
3.2.2串匹配问题52
3.3排序问题中的蛮力法56
3.3.1选择排序56
3.3.2起泡排序57
3.4组合问题中的蛮力法... 查看详情