離散空間上的容錯(cuò)搜索理論

第1章 離散空間上的容錯(cuò)搜索模型及其分類
1．1 R6nyi—Ulam問題與糾錯(cuò)編碼
1．1．1 Renyi—Ulam問題
1．1．2 噪聲通信與糾錯(cuò)編碼
1．1．3 R6nyi—Ulaxn問題與噪聲通信問題的聯(lián)系
1．2 離散空間上的容錯(cuò)搜索模型的分類
1．2．1 一種描述形式：Renyi—Ulam模型
1．2．2 另一種描述形式：Coin—Weighing模型
1．3 研究現(xiàn)狀
1．3．1 單目標(biāo)情形
1．3．2 多目標(biāo)情形
第2章 單目標(biāo)2維自由提問格式搜索模型
2．1 差錯(cuò)總數(shù)e=1情形的worst—caLse最優(yōu)算法
2．1．1 狀態(tài)、狀態(tài)轉(zhuǎn)移律與體積守恒律
2．1．2 提問者取勝的必要條件
2．1．3 典型狀態(tài)
2．1．4 提問者取勝的充分必要條件
2．2 差錯(cuò)總數(shù)e=2情形的worst—case最優(yōu)算法
2．2．1 狀態(tài)轉(zhuǎn)移律與體積守恒律
2．2．2 典型狀態(tài)
2．2．3 前兩次提問及其最優(yōu)性
2．2．4 最小提問次數(shù)及最優(yōu)策略
2．3 差錯(cuò)總數(shù)e≥3情形的worst—case最優(yōu)算法
第3章 單目標(biāo)q維自由提問格式搜索模型
3．1 適應(yīng)的q維自由提問格式e容錯(cuò)搜索模型
3．1．1 狀態(tài)與狀態(tài)轉(zhuǎn)移律
3．1．2 體積的一般公式與守恒律
3．1．3 最小提問次數(shù)的信息論下界
3．1．4 狀態(tài)的單調(diào)性
3．2 1 容錯(cuò)worst—case最優(yōu)算法
3．2．1 狀態(tài)轉(zhuǎn)移律與體積守恒律
3．2．2 提問者取勝的必要條件
3．2．3 提問者取勝的充分必要條件
3．3 2 容錯(cuò)worst—case算法
3．3．1 搜索空間大小N=qi時(shí)的最優(yōu)算法：Cicalese方法
3．3．2 搜索空間大?、羧我鈺r(shí)的次最優(yōu)算法
3．4 e容錯(cuò)worst—case最優(yōu)算法初探
3．5 非適應(yīng)的Q維自由提問格式1容錯(cuò)搜索模型
第4章 單目標(biāo)3維e容錯(cuò)Coim—weighing模型
4．1 適應(yīng)的1容錯(cuò)情況的最優(yōu)算法
4．1．1 狀態(tài)轉(zhuǎn)移律與體積守恒律
4．1．2 normal狀態(tài)與nice狀態(tài)
4．1．3 最少試驗(yàn)次數(shù)的精確值
4．2 適應(yīng)的2容錯(cuò)情況的最優(yōu)算法
4．2．1 狀態(tài)轉(zhuǎn)移律與體積守恒律
4．2．2 典型狀態(tài)
4．2．3 前兩次試驗(yàn)及其最優(yōu)性
4．2．4 最少試驗(yàn)次數(shù)的精確值
第5章 試驗(yàn)集受限制搜索模型
5．1 單目標(biāo)2維■集提問格式e容錯(cuò)搜索模型
5．1．1 單目標(biāo)2維■集提問格式非容錯(cuò)搜索模型
5．1．2 單目標(biāo)2維■集提問格式e容錯(cuò)搜索模型
5．2 單目標(biāo)3維■集e容錯(cuò)Coin—Weighing模型
5．2．1 序列算法worst—case最優(yōu)長度
5．2．2 序列算法average—case最優(yōu)長度
5．3 單目標(biāo)e容錯(cuò)并行搜索Coin—Weighing模型
5．3．1 符號及預(yù)備知識
5．3．2 序列算法與預(yù)確定算法worst—case最優(yōu)長度
5．3．3 預(yù)確定算法average—case最優(yōu)長度
5．3．4 序列算法average—case最優(yōu)長度
5．3．5 試驗(yàn)集受限制時(shí)序列算法worst—case最優(yōu)長度
第6章 單目標(biāo)雙區(qū)間型提問格式搜索模型
6．1 常見提問形式之間的關(guān)系
6．2 2維雙區(qū)間型提問格式2容錯(cuò)搜索模型
6．2．1 狀態(tài)轉(zhuǎn)移律與體積守恒律
6．2．2 well—shaped狀態(tài)
6．2．3 臨界值
6．2．4 nice狀態(tài)
6．2．5 主要結(jié)果及其證明
6．3 g維雙區(qū)間提問型格式1容錯(cuò)搜索模型
6．3．1 q維雙區(qū)間型提問，wellshaped狀態(tài)
6．3．2 主要結(jié)果及其證明
第7章 具有時(shí)滯和遺失的搜索模型
7．1 具有時(shí)滯和遺失的2維比較型提問搜索模型
7．2 具有時(shí)滯d遺失c=0的2維比較型提問的最優(yōu)算法
7．2．1 搜索空間大小的下界
7．2．2 搜索空間大小的上界
7．2．3 搜索空間大小的最優(yōu)值
7．3 具有時(shí)滯d遺失c=1的2維比較型提問的最優(yōu)算法
7．3．1 搜索空間大小的上界
7．3．2 搜索空間大小的下界
7．3．3 搜索空間大小的最優(yōu)值
第8章 對偶模型
8．1 對偶模型的定義及其簡單性質(zhì)
8．2 2維自由提問格式1容錯(cuò)對偶模型
附錄 基礎(chǔ)知識
1 函數(shù)〔X〕和|X|的定義與性質(zhì)
2 樹及其長度
3 算法的表示
4 兩個(gè)最優(yōu)序列算法
參考文獻(xiàn)