离散空间上的容错搜索理论PDF电子书下载

第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