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

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

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