形式化構件裝配的領域算法構造

目錄
前言
第1章 引言 1
1.1 研究背景 1
1.2 研究目標和內(nèi)容 1
第2章 算法程序自動化方法概述 3
2.1 基于演繹推理的方法 3
2.2 程序變換方法 5
2.2.1 橫向變換 6
2.2.2 縱向變換 7
2.2.3 廣義縱向變換 9
2.3 基于歸納推理的方法 11
2.4 基于機器學習和進化的方法 12
2.5 模型驅動軟件開發(fā)方法 13
2.6 生成式程序設計方法 13
2.7 本章小結 14
第3章 PAR方法 15
3.1 循環(huán)不變式新定義和新開發(fā)策略 15
3.2 語言 16
3.2.1 Radl規(guī)約及其變換規(guī)則 17
3.2.2 Radl算法表示法 19
3.3 算法程序開發(fā)方法 19
3.4 本章小結 20
第4章 產(chǎn)生式編程與Apla語言泛型設計介紹 21
4.1 產(chǎn)生式編程 21
4.1.1 領域工程 21
4.1.2 特征建模 22
4.2 Apla語言中的泛型程序設計 22
4.2.1 泛型程序設計 22
4.2.2 Apla泛型 23
4.3 本章小結 24
第5章 基于PAR的算法形式化開發(fā) 25
5.1 自動問題分劃 25
5.2 啟發(fā)式規(guī)約變換 28
5.3 一個實例 30
5.4 本章小結 34
第6章 置換和查找類算法生成模型 35
6.1 置換問題的代數(shù)性質 35
6.2 領域分析 36
6.3 領域設計 38
6.4 排序算法類構件實現(xiàn) 39
6.4.1 類型構件SortingList 40
6.4.2 類型構件Heap 52
6.4.3 算法構件DBPSort 54
6.4.4 算法構件UBPSort 57
6.4.5 算法構件HSort 60
6.5 查找算法類構件實現(xiàn) 60
6.5.1 類型構件SearchingList 60
6.5.2 類型構件Hash 63
6.5.3 算法構件UnorderSearch 65
6.5.4 算法構件OrderSearch 67
6.6 本章小結 68
第7章 置換算法程序生成 70
7.1 荷蘭國旗問題 70
7.1.1 平衡分劃求解 70
7.1.2 非平衡分劃求解 72
7.1.3 算法分析和擴展 73
7.2 基于DBP分劃的排序算法 74
7.2.1 歸并排序 74
7.2.2 插入排序 75
7.2.3 二分插入排序 75
7.2.4 其他排序算法 75
7.3 基于UBP分劃的排序算法 76
7.3.1 快速排序 76
7.3.2 選擇排序 76
7.3.3 冒泡排序 76
7.3.4 堆排序 77
7.4 其他類排序算法 77
7.4.1 H-增量排序 77
7.4.2 雙向選擇排序 79
7.5 系統(tǒng)支持 83
7.6 本章小結 84
第8章 查找算法程序生成 85
8.1 無序查找 85
8.1.1 遞歸查找 85
8.1.2 線性查找 85
8.1.3 散列表查找 86
8.1.4 其他查找算法 88
8.2 有序查找 88
8.2.1 有序線性查找 88
8.2.2 二分查找 88
8.2.3 二叉樹查找 89
8.2.4 其他查找算法 89
8.3 本章小結 90
第9章 序列比對算法 91
9.1 序列比對簡介 91
9.1.1 序列比對問題簡述 91
9.1.2 空位罰分 91
9.1.3 替換矩陣 92
9.2 序列比對算法 92
9.2.1 雙序列比對算法 92
9.2.2 多序列比對算法 93
9.3 本章小結 94
第10章 DPPSAA構件設計與NW裝配實現(xiàn) 95
10.1 DPPSAA領域特征模型 95
10.1.1 DPPSAA特征模型 95
10.1.2 DPPSAA特征交互模型 95
10.2 基于Apla語言的DPPSAA構件實現(xiàn) 96
10.2.1 算法構件的Apla表示 96
10.2.2 NW算法裝配實現(xiàn) 100
10.3 基于Apla-C++轉換的NW算法裝配實現(xiàn) 101
10.3.1 Apla程序轉換為C++表示 101
10.3.2 實驗結果分析 102
10.4 本章小結 102
第11章 基于DPPSAA的星比對算法裝配實現(xiàn) 104
11.1 星比對算法介紹 104
11.2 星比對算法構件建立以及Apla實現(xiàn) 104
11.3 基于Apla-C++轉換系統(tǒng)的星比對算法的裝配實現(xiàn) 106
11.4 實驗結果分析 108
11.5 本章小結 109
參考文獻 110
附錄 Radl規(guī)約文法 118