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

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

1．1R6nyiUlam问题与纠错编码

1．1．1RenyiUlam问题

1．1．2噪声通信与纠错编码

1．1．3R6nyiUlaxn问题与噪声通信问题的联系

1．2离散空间上的容错搜索模型的分类

1．2．1一种描述形式：RenyiUlam模型

1．2．2另一种描述形式：CoinWeighing模型

1．3研究现状

1．3．1单目标情形

1．3．2多目标情形

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

2．1差错总数e=1情形的worstcaLse最优算法

2．1．1状态、状态转移律与体积守恒律

2．1．2提问者取胜的必要条件

2．1．3典型状态

2．1．4提问者取胜的充分必要条件

2．2差错总数e=2情形的worstcase最优算法

2．2．1状态转移律与体积守恒律

2．2．2典型状态

2．2．3前两次提问及其最优性

2．2．4最小提问次数及最优策略

2．3差错总数e≥3情形的worstcase最优算法

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

3．1适应的q维自由提问格式e容错搜索模型

3．1．1状态与状态转移律

3．1．2体积的一般公式与守恒律

3．1．3最小提问次数的信息论下界

3．1．4状态的单调性

3．21容错worstcase最优算法

3．2．1状态转移律与体积守恒律

3．2．2提问者取胜的必要条件

3．2．3提问者取胜的充分必要条件

3．32容错worstcase算法

3．3．1搜索空间大小N=qi时的最优算法：Cicalese方法

3．3．2搜索空间大小Ⅳ任意时的次最优算法

3．4e容错worstcase最优算法初探

3．5非适应的Q维自由提问格式1容错搜索模型

第4章单目标3维e容错Coimweighing模型

4．1适应的1容错情况的最优算法

4．1．1状态转移律与体积守恒律

4．1．2normal状态与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容错CoinWeighing模型

5．2．1序列算法worstcase最优长度

5．2．2序列算法averagecase最优长度

5．3单目标e容错并行搜索CoinWeighing模型

5．3．1符号及预备知识

5．3．2序列算法与预确定算法worstcase最优长度

5．3．3预确定算法averagecase最优长度

5．3．4序列算法averagecase最优长度

5．3．5试验集受限制时序列算法worstcase最优长度

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

6．1常见提问形式之间的关系

6．22维双区间型提问格式2容错搜索模型

6．2．1状态转移律与体积守恒律

6．2．2wellshaped状态

6．2．3临界值

6．2．4nice状态

6．2．5主要结果及其证明

6．3g维双区间提问型格式1容错搜索模型

6．3．1q维双区间型提问，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．22维自由提问格式1容错对偶模型

附录基础知识

1函数[X]和|X|的定义与性质

2树及其长度

3算法的表示

4两个最优序列算法

参考文献

　　离散空间上的容错搜索理论是一门新兴的交叉学科，涵盖数学、通信、计算机等学科。本书的写作目的正是在于向读者介绍离散空间上容错搜索理论的研究背景、内容与方法，激发读者从事这一领域科学研究的热情。全书共分为8章，详细介绍了：单目标2维自由提问格式搜索模型、单目标q维自由提问格式搜索模型、单目标3维e容错Coimweighing模型、试验集受限制搜索模型等方面的内容。本书可作为高等院校高年级本科生、研究生的教材或参考书。　　离散空间上的容错搜索理论是一门新兴的交叉学科，它涵盖数学、通信、计算机等学科，有着重要的理论价值和广泛的应用前景，全书分为8章：第1章着重给出模型的分类及其研究现状；第2章展示寻找单目标2维自由提问格式模型的最优算法的方法；第3章阐述单目标q维自由提问格式模型的最优算法与数学工具；第4章将容错搜索方法应用到coin-weighing模型；第5章引入“大小受限”提问格式模型并研究其最优算法；第6章分析寻找单目标q维双区间型提问格式模型的最优算法的必要性和可能性；第7章和第8章分别介绍其他学者新近提出的“具有时滞和遗失的模型”与“对偶模型”，初步分析研究这两类模型的方法与手段，附录给出了必备的一些基础知识。　　本书可作为高等院校高年级本科生、研究生的教材或参考书，也可作为数学、通信、计算机等领域研究人员的参考书。