离散空间上的容错搜索理论

第1章 离散空间上的容错搜索模型及其分类
1．1 R6nyi—Ulam问题与纠错编码
1．1．1 Renyi—Ulam问题
1．1．2 噪声通信与纠错编码
1．1．3 R6nyi—Ulaxn问题与噪声通信问题的联系
1．2 离散空间上的容错搜索模型的分类
1．2．1 一种描述形式：Renyi—Ulam模型
1．2．2 另一种描述形式：Coin—Weighing模型
1．3 研究现状
1．3．1 单目标情形
1．3．2 多目标情形
第2章 单目标2维自由提问格式搜索模型
2．1 差错总数e=1情形的worst—caLse最优算法
2．1．1 状态、状态转移律与体积守恒律
2．1．2 提问者取胜的必要条件
2．1．3 典型状态
2．1．4 提问者取胜的充分必要条件
2．2 差错总数e=2情形的worst—case最优算法
2．2．1 状态转移律与体积守恒律
2．2．2 典型状态
2．2．3 前两次提问及其最优性
2．2．4 最小提问次数及最优策略
2．3 差错总数e≥3情形的worst—case最优算法
第3章 单目标q维自由提问格式搜索模型
3．1 适应的q维自由提问格式e容错搜索模型
3．1．1 状态与状态转移律
3．1．2 体积的一般公式与守恒律
3．1．3 最小提问次数的信息论下界
3．1．4 状态的单调性
3．2 1 容错worst—case最优算法
3．2．1 状态转移律与体积守恒律
3．2．2 提问者取胜的必要条件
3．2．3 提问者取胜的充分必要条件
3．3 2 容错worst—case算法
3．3．1 搜索空间大小N=qi时的最优算法：Cicalese方法
3．3．2 搜索空间大小Ⅳ任意时的次最优算法
3．4 e容错worst—case最优算法初探
3．5 非适应的Q维自由提问格式1容错搜索模型
第4章 单目标3维e容错Coim—weighing模型
4．1 适应的1容错情况的最优算法
4．1．1 状态转移律与体积守恒律
4．1．2 normal状态与nice状态
4．1．3 最少试验次数的精确值
4．2 适应的2容错情况的最优算法
4．2．1 状态转移律与体积守恒律
4．2．2 典型状态
4．2．3 前两次试验及其最优性
4．2．4 最少试验次数的精确值
第5章 试验集受限制搜索模型
5．1 单目标2维■集提问格式e容错搜索模型
5．1．1 单目标2维■集提问格式非容错搜索模型
5．1．2 单目标2维■集提问格式e容错搜索模型
5．2 单目标3维■集e容错Coin—Weighing模型
5．2．1 序列算法worst—case最优长度
5．2．2 序列算法average—case最优长度
5．3 单目标e容错并行搜索Coin—Weighing模型
5．3．1 符号及预备知识
5．3．2 序列算法与预确定算法worst—case最优长度
5．3．3 预确定算法average—case最优长度
5．3．4 序列算法average—case最优长度
5．3．5 试验集受限制时序列算法worst—case最优长度
第6章 单目标双区间型提问格式搜索模型
6．1 常见提问形式之间的关系
6．2 2维双区间型提问格式2容错搜索模型
6．2．1 状态转移律与体积守恒律
6．2．2 well—shaped状态
6．2．3 临界值
6．2．4 nice状态
6．2．5 主要结果及其证明
6．3 g维双区间提问型格式1容错搜索模型
6．3．1 q维双区间型提问，wellshaped状态
6．3．2 主要结果及其证明
第7章 具有时滞和遗失的搜索模型
7．1 具有时滞和遗失的2维比较型提问搜索模型
7．2 具有时滞d遗失c=0的2维比较型提问的最优算法
7．2．1 搜索空间大小的下界
7．2．2 搜索空间大小的上界
7．2．3 搜索空间大小的最优值
7．3 具有时滞d遗失c=1的2维比较型提问的最优算法
7．3．1 搜索空间大小的上界
7．3．2 搜索空间大小的下界
7．3．3 搜索空间大小的最优值
第8章 对偶模型
8．1 对偶模型的定义及其简单性质
8．2 2维自由提问格式1容错对偶模型
附录 基础知识
1 函数〔X〕和|X|的定义与性质
2 树及其长度
3 算法的表示
4 两个最优序列算法
参考文献