《离散空间上的容错搜索理论》PDF下载

  • 购买积分:10 如何计算积分?
  • 作  者:刘文安著
  • 出 版 社:北京:科学出版社
  • 出版年份:2007
  • ISBN:7030194071
  • 页数:233 页
图书介绍:离散空间上的容错搜索理论是一门新兴的交叉学科。它涵盖数学、通信、计算机等学科,有着广泛的应用价值。目前,这一理论的框架体系尚未形成,提出的问题远远多于已解决的问题,研究内容、研究方法尚处于不断探索、逐步完善阶段。本书的目的在于向读者介绍离散空间上的容错搜索理论的研究背景、研究内容与基本方法,激发读者从事这一领域科学研究的热情。全书分为八章。第一章着重给出模型的分类以及研究现状与展望。第二章重点展示寻找单目标2-维自由提问格式模型的最优算法的方法与数学工具。第三章给出单目标3-维自由提问格式模型的最优算法,为下一章内容做准备。第四章重点阐述单目标q-维自由提问格式模型的最优算法,将第二、三、四章的内容统一起来。第五章引入了占用更少存储空间的“区间型提问格式”,探讨了寻找单目标2-维区间型提问格式模型的最优算法的可能性。第六章引入了更加实用的“大小受限”提问模式,研究了该模型的四类最优算法。第七章和第八章分别介绍了其他学者新近提出的“对偶模型”和“具有时滞和遗失模型”,初步分析了研究这两类模型的方法与手段。

第1章 离散空间上的容错搜索模型及其分类 1

1.1 Rényi-Ulam问题与纠错编码 1

1.1.1 Rényi-Ulam问题 1

1.1.2 噪声通信与纠错编码 1

1.1.3 Rényi-Ulam问题与噪声通信问题的联系 3

1.2 离散空间上的容错搜索模型的分类 4

1.2.1 一种描述形式:Rényi-Ulam模型 4

1.2.2 另一种描述形式:Coin-Weighing模型 6

1.3 研究现状 9

1.3.1 单目标情形 9

1.3.2 多目标情形 18

第2章 单目标2维自由提问格式搜索模型 25

2.1 差错总数e=1情形的worst-case最优算法 25

2.1.1 状态、状态转移律与体积守恒律 25

2.1.2 提问者取胜的必要条件 29

2.1.3 典型状态 31

2.1.4 提问者取胜的充分必要条件 34

2.2 差错总数e=2情形的worst-case最优算法 35

2.2.1 状态转移律与体积守恒律 35

2.2.2 典型状态 37

2.2.3 前两次提问及其最优性 41

2.2.4 最小提问次数及最优策略 49

2.3 差错总数e≥3情形的worst-case最优算法 50

第3章 单目标q维自由提问格式搜索模型 52

3.1 适应的q维自由提问格式e容错搜索模型 52

3.1.1 状态与状态转移律 52

3.1.2 体积的一般公式与守恒律 55

3.1.3 最小提问次数的信息论下界 57

3.1.4 状态的单调性 59

3.2 1 容错worst-case最优算法 62

3.2.1 状态转移律与体积守恒律 62

3.2.2 提问者取胜的必要条件 63

3.2.3 提问者取胜的充分必要条件 66

3.3 2 容错worst-case算法 72

3.3.1 搜索空间大小N=qi时的最优算法:Cicalese方法 72

3.3.2 搜索空间大小N任意时的次最优算法 78

3.4 e容错worst-case最优算法初探 85

3.5 非适应的q维自由提问格式1容错搜索模型 88

第4章 单目标3维e容错Coin-Weighing模型 93

4.1 适应的1容错情况的最优算法 93

4.1.1 状态转移律与体积守恒律 93

4.1.2 normal状态与nice状态 95

4.1.3 最少试验次数的精确值 101

4.2 适应的2容错情况的最优算法 104

4.2.1 状态转移律与体积守恒律 104

4.2.2 典型状态 107

4.2.3 前两次试验及其最优性 117

4.2.4 最少试验次数的精确值 127

第5章 试验集受限制搜索模型 130

5.1 单目标2维?集提问格式e容错搜索模型 130

5.1.1 单目标2维?集提问格式非容错搜索模型 131

5.1.2 单目标2维?集提问格式e容错搜索模型 136

5.2 单目标3维?集e容错Coin-Weighing模型 138

5.2.1 序列算法worst-case最优长度 138

5.2.2 序列算法average-case最优长度 139

5.3 单目标e容错并行搜索Coin-Weighing模型 159

5.3.1 符号及预备知识 160

5.3.2 序列算法与预确定算法worst-case最优长度 161

5.3.3 预确定算法average-case最优长度 162

5.3.4 序列算法average-case最优长度 168

5.3.5 试验集受限制时序列算法worst-case最优长度 172

第6章 单目标双区间型提问格式搜索模型 175

6.1 常见提问形式之间的关系 175

6.2 2 维双区间型提问格式2容错搜索模型 176

6.2.1 状态转移律与体积守恒律 176

6.2.2 well-shaped状态 177

6.2.3 临界值 180

6.2.4 nice状态 186

6.2.5 主要结果及其证明 188

6.3 q维双区间提问型格式1容错搜索模型 189

6.3.1 q维双区间型提问,well-shaped状态 190

6.3.2 主要结果及其证明 194

第7章 具有时滞和遗失的搜索模型 195

7.1 具有时滞和遗失的2维比较型提问搜索模型 195

7.2 具有时滞d遗失c=0的2维比较型提问的最优算法 196

7.2.1 搜索空间大小的下界 197

7.2.2 搜索空间大小的上界 198

7.2.3 搜索空间大小的最优值 202

7.3 具有时滞d遗失c=1的2维比较型提问的最优算法 202

7.3.1 搜索空间大小的上界 203

7.3.2 搜索空间大小的下界 205

7.3.3 搜索空间大小的最优值 210

第8章 对偶模型 211

8.1 对偶模型的定义及其简单性质 211

8.2 2维自由提问格式1容错对偶模型 215

附录 基础知识 220

1 函数「x?和?x」的定义与性质 220

2 树及其长度 221

3 算法的表示 223

4 两个最优序列算法 225

参考文献 229