图书介绍
计算复杂性与算法分析PDF|Epub|txt|kindle电子书版本网盘下载
- 吴兴玲，黄成泉，罗里波编著 著
- 出版社： 成都：电子科技大学出版社
- ISBN：9787564702014
- 出版时间：2009
- 标注页数：152页
- 文件大小：8MB
- 文件页数：161页
- 主题词：计算复杂性；算法分析
PDF下载
下载说明
计算复杂性与算法分析PDF格式电子书版下载
下载的文件为RAR压缩包。需要使用解压软件进行解压得到PDF格式图书。建议使用BT下载工具Free Download Manager进行下载,简称FDM(免费,没有广告,支持多平台）。本站资源全部打包为BT种子。所以需要使用专业的BT下载软件进行下载。如BitComet qBittorrent uTorrent等BT下载工具。迅雷目前由于本站不是热门资源。不推荐使用！后期资源热门了。安装了迅雷也可以迅雷进行下载！
（文件页数 要大于 标注页数，上中下等多册电子书除外）
注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具
图书目录
第1章 有限自动机1
1.1有限自动机与计算机1
1.1.1计算机的发展1
1.1.2有限自动机与计算机的关系1
1.1.3物理机器与自动机2
1.1.4机器与语言的关系3
1.1.5语言与文法的关系4
1.1.6计算机的极限4
1.2有限自动机的定义5
1.2.1有限自动机的分类5
1.2.2有限接受机的定义5
1.2.3字母表（Alphabet）6
1.2.4有限自动机对输入字符串的动作7
1.2.5确定型自动机的构造方法8
1.3非确定型有限自动机NFA（Nondeterministic Finite Automation）11
1.3.1非确定型有限自动机的定义11
1.3.2非确定型自动机与确定型自动机的等价性14
1.3.3举例16
1.3.4由非确定型自动机构造等价的确定型自动机所用状态数的比较18
1.3.5带有ε移动的非确定型自动机18
1.3.6带有ε移动的非确定型自动机与不含有ε移动的非确定型自动机的等价性20
1.3.7DFA，NFA，ε-NFA的等价性22
1.4正则表达式与正则语言23
1.4.1正则表达式23
1.4.2DFA所接受的语言24
1.4.3正则语言能被机器ε-NFA（？NFA，DFA）所接受26
1.4.4正则表达式所满足的算律28
1.4.5语言的非正则性判定29
1.4.6正则语言的封闭性31
1.4.7正则语言的判定问题34
1.4.8自动机的等价和最小化36
第2章 下推自动机41
2.1上下文无关文法41
2.1.1上下文无关文法的定义41
2.1.2语法分析树（又称为推导树）45
2.2语法分析树与推导过程的定理46
2.2.1语法分析树的产品定理46
2.2.2最左推导与最右推导47
2.2.3歧义性48
2.3上下文无关文法的简化48
2.3.1无用变量，终端记号以及ε记号的处理方法48
2.3.2ε生产公式的处理50
2.3.3单传生产公式51
2.3.4固有的歧义性语言的例子52
2.3.5上下文无关文法的整理56
2.4下推自动机58
2.4.1下推自动机的定义58
2.4.2关于下推自动机的等价定理64
2.5上下文无关语言的判定问题77
2.5.1CFL的泵引理77
2.5.2关于CFL的判定问题79
第3章 递归函数81
3.1部分函数与函数运算81
3.1.1部分函数81
3.1.2函数运算81
3.2原始递归函数82
3.2.1原始递归函数的定义82
3.2.2原始递归函数的一些基本性质83
3.3部分递归函数84
3.3.1部分递归函数的概念84
3.3.2部分递归函数的性质85
3.4递归可枚举集85
第4章 图灵机87
4.1图灵机的基本概念87
4.1.1符号串与编码87
4.1.2图灵机的基本概念89
4.2图灵可计算函数92
4.3图灵机的变形93
4.3.1多带图灵机93
4.3.2非确定型图灵机95
4.4通用图灵机96
4.5对角线方法97
第5章 计算复杂性理论99
5.1算法的基本概念99
5.1.1算法的定义和特征99
5.1.2算法设计的例子——穷举法101
5.2计算模型102
5.2.1布尔函数103
5.2.2随机存取机（RAM—Random Access Machine）模型104
5.2.3随机存取存储程序机（RASP—Random Access Stored Program Machine）模型113
5.3算法复杂度分析的数学基础116
5.3.1集合论116
5.3.2逻辑学118
5.3.3概率论119
5.3.4求和与递归123
5.3.5快速估算法127
第6章 顺序算法设计的基本技术128
6.1分治策略128
6.1.1分治策略的基本思想128
6.1.2分治策略的适用条件128
6.1.3分治策略的基本步骤129
6.1.4分治策略的几种变形130
6.2动态规划130
6.2.1动态规划基本思想130
6.2.2动态规划基本步骤131
6.2.3动态规划算法的基本要素131
6.2.4备忘录方法133
6.3回溯法134
6.3.1问题的解空间135
6.3.2回溯法的基本思想135
6.3.3回溯法的一般性描述136
6.3.4回溯法的效率分析137
6.4贪心法138
6.4.1贪心算法138
6.4.2贪心算法分析140
6.4.3贪心算法的基本要素141
6.4.4贪心算法与动态规划算法的差异142
6.5概率算法144
6.5.1概率算法的基本思想145
6.5.2数值概率算法146
6.5.3蒙特卡罗算法147
6.5.4其他概率算法149
参考文献152