計算思維的結(jié)構(gòu)

第1章 緒論 1
1．1 計算思維概述 2
1．2 計算思維的結(jié)構(gòu) 5
1．3 計算機方法論概述 8
習題1 10
第2章 計算學科的基本問題 12
2．1 漢諾塔問題 12
2．2 算法復雜性中的難解性問題 14
2．3 證比求易算法 14
2．4 P=NP？ 15
2．5 RSA公開密鑰密碼系統(tǒng) 16
2．6 停機問題 19
2．7 旅行商問題與組合爆炸問題 21
2．8 找零問題、背包問題與貪婪算法 23
2．9 GOTO語句與程序的結(jié)構(gòu) 24
2．10 哲學家共餐問題與計算機的
資源管理 26
2．11 兩軍問題與計算機網(wǎng)絡(luò) 27
2．11．1 兩軍問題 27
2．11．2 互聯(lián)網(wǎng)軟件的分層結(jié)構(gòu) 28
2．12 人工智能中的若干哲學問題 29
2．12．1 圖靈測試 29
2．12．2 西爾勒的“中文屋子” 31
2．12．3 計算機中的博弈問題 31
習題2 33
第3章 計算學科的3個學科形態(tài) 34
3．1 一個關(guān)于“學生選課”的例子 34
3．1．1 對“學生選課”例子的
感性認識 34
3．1．2 對“學生選課”例子的
理性認識 36
3．1．3 “學生選課”系統(tǒng)的工程設(shè)計 37
3．2 抽象形態(tài) 38
3．3 理論形態(tài) 38
3．4 設(shè)計形態(tài) 39
3．5 3個學科形態(tài)的內(nèi)在聯(lián)系 40
3．6 計算機語言的發(fā)展及其3個學科
形態(tài)的內(nèi)在聯(lián)系 42
3．6．1 自然語言與形式語言 42
3．6．2 圖靈機與馮 諾依曼計算機 44
3．6．3 機器指令與匯編語言 50
3．6．4 虛擬機 52
3．6．5 高級語言 54
3．6．6 應(yīng)用語言 55
3．6．7 自然語言 56
習題3 58
第4章 計算學科的核心概念 61
4．1 算法 61
4．1．1 算法的歷史簡介 61
4．1．2 算法的定義和特征 62
4．1．3 算法實例 63
4．1．4 算法分析 66
4．1．5 常用的兩類算法：搜索與排序 71
4．2 數(shù)據(jù)結(jié)構(gòu) 77
4．2．1 數(shù)據(jù)結(jié)構(gòu)的基本概念 77
4．2．2 基于Vcomputer機器的
數(shù)據(jù)結(jié)構(gòu)概述 78
4．2．3 基于Vcomputer機器的
數(shù)據(jù)的邏輯結(jié)構(gòu) 79
4．2．4 基于Vcomputer機器的
數(shù)據(jù)的存儲結(jié)構(gòu) 83
4．3 數(shù)據(jù)的存儲和表示 86
4．3．1 補碼在計算機中的表示 87
4．3．2 圖像 89
4．4 數(shù)據(jù)的編碼、校驗 90
4．4．1 字符、字符串和漢字 91
4．4．2 奇偶校驗算法 92
4．5 CC1991報告提取的核心概念 93
習題4 95
第5章 計算學科中的數(shù)學方法 99
5．1 數(shù)學的基本特征 99
5．2 數(shù)學方法的作用 100
5．3 計算學科中常用的數(shù)學
概念和術(shù)語 100
5．3．1 集合 100
5．3．2 函數(shù)和關(guān)系 102
5．3．3 代數(shù)系統(tǒng) 103
5．3．4 構(gòu)造計算學科的邏輯電路的
基礎(chǔ)——布爾代數(shù) 104
5．3．5 一位加法器的設(shè)計 105
5．3．6 定義、定理和證明 108
5．3．7 必要條件和充分條件 109
5．4 證明方法 109
5．4．1 直接證明法和間接證明法 109
5．4．2 反證法 110
5．4．3 歸納法 111
5．4．4 構(gòu)造性證明 112
5．5 計算學科構(gòu)造性的基礎(chǔ)
——遞歸和迭代 112
5．5．1 遞歸 113
5．5．2 迭代 115
5．6 隨機數(shù)和蒙特卡洛方法 116
5．6．1 隨機數(shù) 116
5．6．2 蒙特卡洛方法 118
5．7 公理化方法 119
5．7．1 理論體系 119
5．7．2 公理化方法的基本概念 120
5．7．3 實例 121
5．8 計算學科的形式化方法 122
5．8．1 形式系統(tǒng)的組成、基本
特點和局限性 122
5．8．2 形式化方法概述 123
5．8．3 形式規(guī)格 124
5．8．4 形式驗證 125
習題5 126
第6章 計算學科中的系統(tǒng)
科學方法 128
6．1 系統(tǒng)科學與系統(tǒng)科學方法 128
6．1．1 系統(tǒng)科學的基本概念 128
6．1．2 系統(tǒng)科學遵循的一般原則 130
6．1．3 常用的幾種系統(tǒng)科學方法 131
6．1．4 實例 131
6．2 軟件開發(fā)中使用系統(tǒng)科學方法的原因 132
6．2．1 人固有能力的局限性以及
使用工具后產(chǎn)生的力量 132
6．2．2 復雜性 133
6．2．3 軟件系統(tǒng)的復雜性 134
6．2．4 軟件開發(fā)的系統(tǒng)化方法
需要遵循的基本原則 135
6．3 使用系統(tǒng)方法的思考 137
習題6 138
第7章 跨學科的計算問題案例 139
7．1 社會與職業(yè)中3個典型的計算問題 139
7．1．1 職業(yè)化 139
7．1．2 道德的選擇 140
7．1．3 檢舉 140
7．2 割圓術(shù)的計算問題 141
7．2．1 割圓術(shù)的形式化描述 142
7．2．2 割圓術(shù)的步驟 142
7．2．3 實例 143
7．2．4 使用Raptor模擬割圓術(shù) 144
7．3 森林火災的計算問題 145
7．3．1 森林火災的形式化描述 146
7．3．2 模擬森林火災的步驟 146
7．3．3 實例 147
7．4 多普勒效應(yīng)的計算問題 149
7．4．1 多普勒效應(yīng)的形式化描述 149
7．4．2 模擬多普勒效應(yīng)的步驟 150
7．4．3 實例 150
7．5 小世界網(wǎng)絡(luò)模型的計算問題 151
7．5．1 小世界網(wǎng)絡(luò)重連的形式化描述 151
7．5．2 模擬小世界網(wǎng)絡(luò)重連的步驟 152
7．5．3 實例 152
7．6 科赫曲線 154
7．6．1 科赫曲線的形式化描述 154
7．6．2 模擬生成科赫曲線的步驟 155
7．6．3 實例 155
7．6．4 使用Raptor模擬科赫曲線 155
7．7 向日葵種子生長模擬 157
7．7．1 預備知識 158
7．7．2 向日葵種子生長模擬的
形式化描述 158
7．7．3 模擬向日葵種子生長的步驟 159
7．7．4 實例 159
7．7．5 使用Raptor模擬向日葵
種子生長 159
7．8 煙花模擬 161

7．8．1 煙花模擬的形式化描述 162
7．8．2 煙花模擬問題的粒子系統(tǒng)模型
中粒子運動的相關(guān)方程 163
7．8．3 煙花模擬的步驟 164
7．8．4 使用Raptor對煙花模型
進行仿真 164
7．9 俄羅斯方塊游戲 167
7．9．1 俄羅斯方塊游戲的形式化描述 167
7．9．2 構(gòu)建一個俄羅斯方塊模型
的算法步驟 168
7．9．3 使用Raptor模擬俄羅斯
方塊游戲 168
習題7 171
參考文獻 173