离散空间上的容错搜索理论是一门新兴的交叉学科,它涵盖数学、通信、计算机等学科,有着重要的理论价值和广泛的应用前景。全书分为8章。第1章着重给出模型的分类及其研究现状;第2章展示寻找单目标2维自由提问格式模型的最优算法的方法;第3章阐述单目标q维自由提问格式模型的最优算法与数学工具;第4章将容错搜索方法应用到Coin-Weighing模型;第5章引入“大小受限”提问格式模型并研究其最优算法;第6章分析寻找单目标q维双区间型提问格式模型的最优算法的必要性和可能性;第7章和第8章分别介绍其他学者新近提出的“具有时滞和遗失的模型”与“对偶模型”,初步分析研究这两类模型的方法与手段。附录给出了必备的一些基础知识。
本书可作为高等院校高年级本科生、研究生的教材或参考书,也可作为数学、通信、计算机等领域研究人员的参考书。
样章试读
目录
- 第1章 离散空间上的容错搜索模型及其分类
§1.1 Rényi-Ulam问题与纠错编码
§1.1.1 Rényi-Ulam问题
§1.1.2 噪声通信与纠错编码
§1.1.3 Rényi-Ulam问题与噪声通信问题的联系
§1.2 离散空间上的容错搜索模型的分类
§1.2.1 一种描述形式:Rényi-Ulam模型
§1.2.2 另一种描述形式:Coin-Weighing模型
§1.3 研究现状
§1.3.1 单目标情形
§1.3.2 多目标情形
第2章 单目标2维自由提问格式搜索模型
§2.1 差错总数e=1情形的worst-case最优算法
§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 搜索空间大小N任意时的次最优算法
§3.4 e容错worst-case最优算法初探
§3.5 非适应的q维自由提问格式1容错搜索模型
第4章 单目标3维e容错Coin-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维l集提问格式e容错搜索模型
§5.1.1 单目标2维l集提问格式非容错搜索模型
§5.1.2 单目标2维l集提问格式e容错搜索模型
§5.2 单目标3维l集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 q维双区间提问型格式1容错搜索模型
§6.3.1 q维双区间型提问,well-shaped状态
§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 两个最优序列算法
参考文献